基于幾何算法的無線站址自動規劃方法研究及實現

王世魁+張紅霞+宋文韜+范云強+王欣玥

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

【關鍵詞】三角幾何 無線站址 自動規劃

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

引用格式：王世魁，張紅霞，宋文韜，等. 基于幾何算法的無線站址自動規劃方法研究及實現[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 引言

目前對于無線站址規劃及設計工作，仍以區域預測及手動布點為主，而手動布點勢必引入操作錯誤或誤差，為實際的規劃設計工作帶來諸多不便。交底的無線站表一經確定將難以再做調整或增減，在緊張且有限的時間窗口里，對站點位置的規劃提出了很高的要求，手動規劃的易錯、不夠精準等特點造成的站址不合理，只能通過后續的參數設置、網絡優化等去消化，同時會進一步加劇網絡結構的不合理。

本文通過基于三角幾何的方式引入多種自動規劃方法，并結合站址分布的實際應用，提出自動規劃算法并通過C#編程語言進行了實現，為后續由于其他原因導致的站表調整及修改提供第一版站址原型。

2 無線站址的自動規劃

討論自動規劃問題，首先應將具體的實際問題抽象、映射成某種數學問題，單純地考慮基站位置，可將基站抽象為點，站址結構問題轉化為數學幾何問題，幾何問題的思考勢必從三角結構開始。物理站址等效為抽象的點示意圖如圖1所示。

2.1 構建站址三角網

將現有站點數學抽象為初始點集，通過各離散的點構建三角形網絡，三角網的構造有多種方式，這里采用最常用的Delaunay三角網。Delaunay三角網由三個相鄰點連接而成，是相互鄰接且互不重疊的三角形集合，具有明顯的特點。每個三角形的外接圓內不包含其他的離散點，稱為空圓特性。

最大化最小角特性，即指兩個相鄰的三角形構成凸四邊形的對角線，在相互交換后，六個內角的最小角不再增大，保證構造的三角網最小角最大，此特性使得Delaunay三角網更接近于規則化，如圖3所示，右側三角形構造更優。

按照以上原則進行三角網構造，最終的網絡結構結果是唯一的。

新增、刪除、移動某一個頂點時只會影響相鄰的三角形，即區域性。此特性將為自動規劃后的站表手動調整提供理論依據，如圖4所示，刪除節點8引起紅色線段的變化，由2、3、4、5、7節點構成的區域外未引起波動。

2.2 站址自動規劃方案比選

在對現有站址完成三角網構造的基礎上，將按照一定的原則進行新站址的自動生成，自動規劃存在多種方式，每種方法各有其優缺點，下面進行各方案的探討。

（1）鄰邊判斷法

此方法的主要過程如下：

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

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

3）按照新站址重新構造三角網。

4）重復2）、3）兩步，直到所有點均滿足距離要求則停止計算。

（2）內切圓法

此方法的主要過程如下：

1）選取任一三角形作為起始計算點，尋找并勾畫此三角形內切圓。

2）計算內切圓半徑，若半徑滿足一個站的新站址條件，則新增點的位置就是此內切圓的圓心。若半徑不滿足新站址條件，則不作操作并計算下一個三角形。

3）按照新站址重新構造三角網。

4）重復2）、3）兩步，直到所有點均滿足距離要求則停止計算。

（3）外接圓法

此方法的主要過程如下：

1）選取任一三角形作為起始計算點，尋找并勾畫此三角形外接圓。

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

3）按照新站址重新構造三角網。

4）重復2）、3）兩步，直到所有點均滿足距離要求則停止計算。

以上幾種方法分別具有其數學意義及實際意義。從數學角度看，不同的幾何特征進行差值運算，不同的方法復雜程度不同，同時其迭代次數也有差異。從站址規劃的實際應用角度看，站址分布的均勻程度越高，則實際價值越大。表1列舉了幾種方法的優缺點，通過對比，選取外接圓法作為自動規劃的算法方案。

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

對于規劃區域的外邊界，無論選定的邊界如何，均采用最外圍基站所構成的凸多邊形加設定距離作為實際的邊界，目的在于盡可能降低由于邊界不合理引起的邊界布點錯亂。

2.3 站址自動規劃的實現及驗證

確定了核心的外接圓規劃算法，在Microsoft Visual Studio.NET Framework環境下主體采用C#語言進行軟件開發及算法實現，形成最終軟件，即BePoint。軟件采用應用層、業務邏輯層、基礎數據層三層架構，單機版開發，考慮實際工作需要，軟件支持脫網工作，軟件的系統結構如圖8所示。

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

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

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

3 結束語

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

參考文獻：

[1] 王映民. TD-LTE技術原理及系統設計[M]. 北京： 人民郵電出版社， 2011.

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

[3] 應倩嵐. 基于蜂窩網實測數據的基站位置與業務空間分布研究[D]. 杭州： 浙江大學， 2015.

[4] 唐宇亮. 基于GIS無線基站可視化系統的設計和實現[D]. 四川： 電子科技大學， 2014.

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

[6] 高峰. TD-LTE技術標準與實踐[M]. 北京： 人民郵電出版社， 2011.

[7] 劉寶昌，胡恒杰，朱強. TD-LTE無線網絡規劃研究[J]. 電信工程技術與標準化， 2010，23（1）： 16-20.

[8] 胡恒杰，趙旭凇，徐德平，等. TD-LTE無線網絡規劃若干問題探討[J]. 電信工程技術與標準化， 2010，23（11）： 47-52.

[9] 趙訓威. 3GPP長期演進（LTE）系統架構與技術規范[M]. 北京： 人民郵電出版社， 2010.

[10] 張曉. 3GPP LTE部分關鍵技術研究及系統級仿真驗證[D]. 武漢： 武漢理工大學， 2008.

[11] 李樹東. 基于博弈論的TD-LTE網絡規劃[D]. 大連： 大連海事大學， 2011.