基于幾何算法的無線站址自動規(guī)劃方法研究及實(shí)現(xiàn)

王世魁+張紅霞+宋文韜+范云強(qiáng)+王欣玥

【摘 要】為了解決目前對于手動無線站址規(guī)劃及設(shè)計(jì)中的錯(cuò)誤及誤差問題，通過基于三角幾何的方式引入多種自動規(guī)劃方法，介紹了各種規(guī)劃算法的操作過程及優(yōu)缺點(diǎn)，選定了外接圓自動規(guī)劃算法并利用軟件加以實(shí)現(xiàn)，選取某省市數(shù)據(jù)試驗(yàn)驗(yàn)證了該算法能夠較好地滿足實(shí)際工作需要。

【關(guān)鍵詞】三角幾何 無線站址 自動規(guī)劃

doi：10.3969/j.issn.1006-1010.2017.08.013 中圖分類號：TN929.53 文獻(xiàn)標(biāo)志碼：A 文章編號：1006-1010（2017）08-0064-05

引用格式：王世魁，張紅霞，宋文韜，等. 基于幾何算法的無線站址自動規(guī)劃方法研究及實(shí)現(xiàn)[J]. 移動通信， 2017，41（8）： 64-68.

Research and Implementation of Base Station Location Automatic Planning Based on Geometric Algorithm

WANG Shikui ZHANG Hongxia SONG Wentao FAN Yunqiang WANG Xinyue

[Abstract] In order to deal with the mistake and the error in manual wireless site planning and design， the multiple automatic planning methods were introduced based on triangular geometry. The operation processes， advantages and disadvantages of different planning algorithms were introduced. The automatic planning algorithm based on circumcircle was selected and implemented on software. The algorithm was validated by the data in a certain province that it can meet the requirements of practical work.

[Key words]triangular geometry base station location automatic planning

1 引言

目前對于無線站址規(guī)劃及設(shè)計(jì)工作，仍以區(qū)域預(yù)測及手動布點(diǎn)為主，而手動布點(diǎn)勢必引入操作錯(cuò)誤或誤差，為實(shí)際的規(guī)劃設(shè)計(jì)工作帶來諸多不便。交底的無線站表一經(jīng)確定將難以再做調(diào)整或增減，在緊張且有限的時(shí)間窗口里，對站點(diǎn)位置的規(guī)劃提出了很高的要求，手動規(guī)劃的易錯(cuò)、不夠精準(zhǔn)等特點(diǎn)造成的站址不合理，只能通過后續(xù)的參數(shù)設(shè)置、網(wǎng)絡(luò)優(yōu)化等去消化，同時(shí)會進(jìn)一步加劇網(wǎng)絡(luò)結(jié)構(gòu)的不合理。

本文通過基于三角幾何的方式引入多種自動規(guī)劃方法，并結(jié)合站址分布的實(shí)際應(yīng)用，提出自動規(guī)劃算法并通過C#編程語言進(jìn)行了實(shí)現(xiàn)，為后續(xù)由于其他原因?qū)е碌恼颈碚{(diào)整及修改提供第一版站址原型。

2 無線站址的自動規(guī)劃

討論自動規(guī)劃問題，首先應(yīng)將具體的實(shí)際問題抽象、映射成某種數(shù)學(xué)問題，單純地考慮基站位置，可將基站抽象為點(diǎn)，站址結(jié)構(gòu)問題轉(zhuǎn)化為數(shù)學(xué)幾何問題，幾何問題的思考勢必從三角結(jié)構(gòu)開始。物理站址等效為抽象的點(diǎn)示意圖如圖1所示。

2.1 構(gòu)建站址三角網(wǎng)

將現(xiàn)有站點(diǎn)數(shù)學(xué)抽象為初始點(diǎn)集，通過各離散的點(diǎn)構(gòu)建三角形網(wǎng)絡(luò)，三角網(wǎng)的構(gòu)造有多種方式，這里采用最常用的Delaunay三角網(wǎng)。Delaunay三角網(wǎng)由三個(gè)相鄰點(diǎn)連接而成，是相互鄰接且互不重疊的三角形集合，具有明顯的特點(diǎn)。每個(gè)三角形的外接圓內(nèi)不包含其他的離散點(diǎn)，稱為空圓特性。

最大化最小角特性，即指兩個(gè)相鄰的三角形構(gòu)成凸四邊形的對角線，在相互交換后，六個(gè)內(nèi)角的最小角不再增大，保證構(gòu)造的三角網(wǎng)最小角最大，此特性使得Delaunay三角網(wǎng)更接近于規(guī)則化，如圖3所示，右側(cè)三角形構(gòu)造更優(yōu)。

按照以上原則進(jìn)行三角網(wǎng)構(gòu)造，最終的網(wǎng)絡(luò)結(jié)構(gòu)結(jié)果是唯一的。

新增、刪除、移動某一個(gè)頂點(diǎn)時(shí)只會影響相鄰的三角形，即區(qū)域性。此特性將為自動規(guī)劃后的站表手動調(diào)整提供理論依據(jù)，如圖4所示，刪除節(jié)點(diǎn)8引起紅色線段的變化，由2、3、4、5、7節(jié)點(diǎn)構(gòu)成的區(qū)域外未引起波動。

2.2 站址自動規(guī)劃方案比選

在對現(xiàn)有站址完成三角網(wǎng)構(gòu)造的基礎(chǔ)上，將按照一定的原則進(jìn)行新站址的自動生成，自動規(guī)劃存在多種方式，每種方法各有其優(yōu)缺點(diǎn)，下面進(jìn)行各方案的探討。

（1）鄰邊判斷法

此方法的主要過程如下：

1）選取任一點(diǎn)作為計(jì)算的起始點(diǎn)，并以此點(diǎn)為中心依次判斷其與相鄰點(diǎn)的距離。

2）若兩點(diǎn)距離滿足新站址條件，則記錄此點(diǎn)或多個(gè)點(diǎn)并生成新點(diǎn)，新生成點(diǎn)盡可能選取在兩點(diǎn)中間。生成單點(diǎn)時(shí)，則位于線段中點(diǎn)，生成n多點(diǎn)時(shí)，位置選在線段n-1點(diǎn)上。若兩點(diǎn)距離不滿足新站址條件，則不作操作并計(jì)算下一個(gè)相鄰點(diǎn)。

3）按照新站址重新構(gòu)造三角網(wǎng)。

4）重復(fù)2）、3）兩步，直到所有點(diǎn)均滿足距離要求則停止計(jì)算。

（2）內(nèi)切圓法

此方法的主要過程如下：

1）選取任一三角形作為起始計(jì)算點(diǎn)，尋找并勾畫此三角形內(nèi)切圓。

2）計(jì)算內(nèi)切圓半徑，若半徑滿足一個(gè)站的新站址條件，則新增點(diǎn)的位置就是此內(nèi)切圓的圓心。若半徑不滿足新站址條件，則不作操作并計(jì)算下一個(gè)三角形。

3）按照新站址重新構(gòu)造三角網(wǎng)。

4）重復(fù)2）、3）兩步，直到所有點(diǎn)均滿足距離要求則停止計(jì)算。

（3）外接圓法

此方法的主要過程如下：

1）選取任一三角形作為起始計(jì)算點(diǎn)，尋找并勾畫此三角形外接圓。

2）計(jì)算外接圓半徑，若半徑滿足一個(gè)站的新站址條件，則新增點(diǎn)的位置就是此外接圓的圓心。若半徑不滿足新站址條件，則不作操作并計(jì)算下一個(gè)三角形。

3）按照新站址重新構(gòu)造三角網(wǎng)。

4）重復(fù)2）、3）兩步，直到所有點(diǎn)均滿足距離要求則停止計(jì)算。

以上幾種方法分別具有其數(shù)學(xué)意義及實(shí)際意義。從數(shù)學(xué)角度看，不同的幾何特征進(jìn)行差值運(yùn)算，不同的方法復(fù)雜程度不同，同時(shí)其迭代次數(shù)也有差異。從站址規(guī)劃的實(shí)際應(yīng)用角度看，站址分布的均勻程度越高，則實(shí)際價(jià)值越大。表1列舉了幾種方法的優(yōu)缺點(diǎn)，通過對比，選取外接圓法作為自動規(guī)劃的算法方案。

無論通過哪種自動規(guī)劃的算法生成的新站址都需要進(jìn)行校準(zhǔn)，即進(jìn)行新增點(diǎn)的合理性判斷。通過若干次的迭代算法會逐層生成新站址，最后需要對全部的站點(diǎn)進(jìn)行合并、刪除等處理，對于多點(diǎn)的合并采用外接圓逐漸逼近的方式，最后給出唯一點(diǎn)。

對于規(guī)劃區(qū)域的外邊界，無論選定的邊界如何，均采用最外圍基站所構(gòu)成的凸多邊形加設(shè)定距離作為實(shí)際的邊界，目的在于盡可能降低由于邊界不合理引起的邊界布點(diǎn)錯(cuò)亂。

2.3 站址自動規(guī)劃的實(shí)現(xiàn)及驗(yàn)證

確定了核心的外接圓規(guī)劃算法，在Microsoft Visual Studio.NET Framework環(huán)境下主體采用C#語言進(jìn)行軟件開發(fā)及算法實(shí)現(xiàn)，形成最終軟件，即BePoint。軟件采用應(yīng)用層、業(yè)務(wù)邏輯層、基礎(chǔ)數(shù)據(jù)層三層架構(gòu)，單機(jī)版開發(fā)，考慮實(shí)際工作需要，軟件支持脫網(wǎng)工作，軟件的系統(tǒng)結(jié)構(gòu)如圖8所示。

無線站址自動規(guī)劃功能作為BePoint軟件整體功能的重要組成部分，主要包括基礎(chǔ)數(shù)據(jù)處理功能、規(guī)劃區(qū)操作功能、自動規(guī)劃功能、GIS交互四大部分。基礎(chǔ)數(shù)據(jù)處理實(shí)現(xiàn)數(shù)據(jù)的導(dǎo)入、導(dǎo)出、入庫、格式化、清洗等；規(guī)劃區(qū)操作功能實(shí)現(xiàn)規(guī)劃區(qū)的繪制、導(dǎo)入、屬性編輯、參數(shù)設(shè)置等；自動規(guī)劃功能采用內(nèi)置外接圓算法實(shí)現(xiàn)迭代規(guī)劃；GIS交互提供人機(jī)交互界面，實(shí)現(xiàn)地圖、站址、規(guī)劃區(qū)的放大、縮小、拖拽、新增基站、刪除基站、編輯基站、查詢、測距等常見GIS功能。

為了驗(yàn)證算法的正確性和有效性，以廣州市某區(qū)域規(guī)劃為例，著重考慮規(guī)劃過程中與算法相關(guān)的小區(qū)位置因素。收集現(xiàn)網(wǎng)站表數(shù)據(jù)，現(xiàn)網(wǎng)LTE網(wǎng)絡(luò)共計(jì)1518個(gè)小區(qū)，均為F頻段，對于不同的頻段建設(shè)集團(tuán)公司已有相應(yīng)的建設(shè)指導(dǎo)原則和成熟的經(jīng)驗(yàn)值。軟件中此部分可手動進(jìn)行配置，此次驗(yàn)證中設(shè)置為F頻段站間距為500 m，軟件中通過對規(guī)劃區(qū)的屬性——規(guī)劃區(qū)的場景類型來關(guān)聯(lián)此值。規(guī)劃區(qū)的手動繪制采取盡可能貼近站址輪廓的外層邊緣，減少算法對空白區(qū)域的無效運(yùn)算，規(guī)劃區(qū)除了5個(gè)不集中站點(diǎn)外包括了其他的全部數(shù)據(jù)。自動規(guī)劃過程采用無限迭代方式，直到滿足站間距設(shè)置的停止條件，整個(gè)驗(yàn)證過程如圖9所示。

對輸出新舊站表進(jìn)行GIS呈現(xiàn)，可見新建站點(diǎn)均勻分布在原站點(diǎn)間，使用標(biāo)尺測量可保證任意兩點(diǎn)間距離大于初始設(shè)定的500 m，計(jì)算后生成新小區(qū)7896個(gè)，進(jìn)一步分析發(fā)現(xiàn)原站址分布疏密不均，統(tǒng)一的間距導(dǎo)致原稀疏區(qū)域插值較多。而稀疏是由于該區(qū)域不適合基站建設(shè)，關(guān)于此部分，將有三維地圖數(shù)據(jù)進(jìn)行二次驗(yàn)證并剔除，形成瘦身后站表，此部分功能由地形地貌識別模塊完成，不在本文討論范圍內(nèi)。綜合來說，采用外接圓算法能夠?qū)崿F(xiàn)站址的自動規(guī)劃。

3 結(jié)束語

在三角幾何的基本思路基礎(chǔ)上，通過引入外接圓自動規(guī)劃算法進(jìn)行站址的自動規(guī)劃能夠很好地滿足自動規(guī)劃需求，降低手動布點(diǎn)的人為出錯(cuò)率，同時(shí)填補(bǔ)了目前市場尚未有自動規(guī)劃至站址級別算法及軟件的空白。后續(xù)將持續(xù)進(jìn)行算法的優(yōu)化并將更多因素納入到站址規(guī)劃的考慮范圍。

參考文獻(xiàn)：

[1] 王映民. TD-LTE技術(shù)原理及系統(tǒng)設(shè)計(jì)[M]. 北京： 人民郵電出版社， 2011.

[2] 譚云婷，熊珊. 基于空間相鄰分析的基站數(shù)據(jù)模型與算法研究[J]. 移動通信， 2016（1）： 34-38.

[3] 應(yīng)倩嵐. 基于蜂窩網(wǎng)實(shí)測數(shù)據(jù)的基站位置與業(yè)務(wù)空間分布研究[D]. 杭州： 浙江大學(xué)， 2015.

[4] 唐宇亮. 基于GIS無線基站可視化系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)[D]. 四川： 電子科技大學(xué)， 2014.

[5] 孫瑞雪. 蜂窩基站空間分布特性研究[D]. 天津： 南開大學(xué)， 2015.

[6] 高峰. TD-LTE技術(shù)標(biāo)準(zhǔn)與實(shí)踐[M]. 北京： 人民郵電出版社， 2011.

[7] 劉寶昌，胡恒杰，朱強(qiáng). TD-LTE無線網(wǎng)絡(luò)規(guī)劃研究[J]. 電信工程技術(shù)與標(biāo)準(zhǔn)化， 2010，23（1）： 16-20.

[8] 胡恒杰，趙旭凇，徐德平，等. TD-LTE無線網(wǎng)絡(luò)規(guī)劃若干問題探討[J]. 電信工程技術(shù)與標(biāo)準(zhǔn)化， 2010，23（11）： 47-52.

[9] 趙訓(xùn)威. 3GPP長期演進(jìn)（LTE）系統(tǒng)架構(gòu)與技術(shù)規(guī)范[M]. 北京： 人民郵電出版社， 2010.

[10] 張曉. 3GPP LTE部分關(guān)鍵技術(shù)研究及系統(tǒng)級仿真驗(yàn)證[D]. 武漢： 武漢理工大學(xué)， 2008.

[11] 李樹東. 基于博弈論的TD-LTE網(wǎng)絡(luò)規(guī)劃[D]. 大連： 大連海事大學(xué)， 2011.