基于遺傳算法的機動通信站址自動規劃方法

冀云剛 霍永華

摘要：針對山區復雜地形環境下機動通信網絡站址選擇需求，提出了一種基于遺傳算法的站址自動規劃方法。對機動通信網絡站址規劃需求進行了分析，確定了機動通信網絡站址規劃目標，通過對傳統遺傳算法在初始種群生成、選擇操作等方面進行改進，以超短波電臺為無線傳輸手段并結合實際組網實驗，對算法進行了驗證。結果表明，該算法在山區復雜環境下以超短波為傳輸手段的站址規劃中具有較高的準確率，能夠滿足機動通信網絡站址規劃需求。

關鍵詞：站址規劃；遺傳算法；ITU-R.P 526模型

中圖分類號：TP393文獻標志碼：A文章編號：1008-1739（2022）14-48-6

0引言

機動通信網絡是為了滿足某種任務而臨時開設的通信網絡。與固定網絡不同，機動通信網絡一般不依托固定基礎設施，多采用無線通信手段，一般采用“一事一規劃”的方式。因此，網絡規劃是機動通信網絡能否滿足任務通信保證需求的關鍵。站址規劃作為機動通信網絡規劃中的關鍵環節，從根本上決定了網絡規劃的可行性。站址規劃已成為通信保障人員面臨的主要任務，特別是在山區等復雜地形環境下，如何快速準確地進行站址選擇，已成為通信保障人員亟待解決的關鍵問題。目前針對該問題，多采用人工規劃方式，由通信保障人員利用無線覆蓋分析工具，計算不同點位無線覆蓋情況，并結合任務需求人工選擇站址。整個過程花費時間長，無法有效滿足機動通信網絡快速規劃開通的需求。

傳統站址規劃方法多基于幾何原理來尋找適合的站點位置，如幾何中心法[1]和外接圓法[2]等。近年來通過利用模糊推理[3]、聚類[4]和機器學習[5]等技術，使用粒子群算法、遺傳算法和模擬退火算法等，將站址規劃作為優化問題進行處理，較傳統方法在資源使用數量、覆蓋效果以及規劃效率等方面有了較大的進步。文獻[6]在TD-LTE基站規劃中將基站數目作為優化目標；文獻[7]在指定基站個數的情況下將覆蓋率和通信質量加權聚合為優化目標，利用遺傳算法進行基站規劃優化；文獻[8]利用多目標粒子群算法對基站覆蓋率、網絡效能比、網絡負載和建設成本進行優化，解決了LTE混合組網優化問題；文獻[9]基于NSGA-II算法實現對機動通信系統的站址規劃。這些研究成果尤其是文獻[9]中的研究成果對機動通信網絡站址規劃提供了很好的參考。但由于機動通信網絡是面向任務臨時開通的網絡，與傳統網絡有著較大的區別，主要體現在所采用的通信手段、部署使用的環境和規劃效率等方面。因此，需結合實際情況進行具體分析，選擇適合的算法和規劃流程，實現機動通信網絡站址的快速規劃，滿足任務快速開通保障的需求。本文從機動通信網絡快速規劃開通的需求出發，提出了一種基于遺傳算法的站址自動規劃模型，通過對機動通信網絡規劃因素進行分析，選擇優化目標，并通過參考歷史選擇結果，實現了一種自動站址選擇方法，提升復雜地形環境下機動通信網絡站址規劃效率。

1機動通信站址規劃

1.1站址規劃需求

機動通信站址規劃是根據任務保障需求，在某個區域內選擇合適的點位，利用有無線等各種通信手段形成能夠覆蓋各用戶的骨干網絡，滿足不同用戶間的信息交互需求。

根據組網需求的不同站址規劃約束也不相同，大致可分為區域互通和區域覆蓋2種。區域互通是根據用戶位置選擇站點，形成互聯網絡，滿足用戶間信息交互需求。區域覆蓋是在區域互通基礎上的更高要求，除滿足用戶間信息交互需求外，還可支持用戶通過任意站點接入網絡。在只考慮區域互通的站址規劃中，由于用戶位置相對固定，因此通過選擇合適的站點和站點間適合的通信手段，實現網絡的互聯互通即可，不需要考慮各站點的覆蓋情況。針對用戶機動接入的需求，在滿足區域互通的基礎上，還需要考慮各站點對用戶的覆蓋情況。由于區域覆蓋可轉化為多用戶的區域互通，為簡單起見在本文中只考慮區域互通需求。

1.2無線覆蓋分析

無線覆蓋分析是站址規劃的基礎，基于電子地圖和無線電波傳播模型，對地圖上兩點間的無線電波傳播損耗進行預測，形成站點的無線覆蓋分析結果。本文針對山區復雜地形環境和VHF無線傳輸手段，采用ITU-R.P 526模型計算直射、反射和繞射路徑損耗。

在山區復雜地形環境下，有不同類型的損耗組合，包括直射、繞射和反射。山區環境下傳播損耗計算流程如圖1所示[10]。

1.3站址規劃流程

典型的站址規劃流程包括確定規劃區域、站點預選和站點選擇3個步驟。

（1）確定規劃區域

確定規劃區域是根據用戶位置確定站址規劃的區域，即確定站點的選擇范圍。該步驟一般由規劃人員根據地圖和實際任務情況進行人工選擇。

（2）站址預選

站址預選是規劃人員基于電子地圖，在規劃區域內選定若干個位置作為備選站點。根據任務需求，機動通信網絡一般在山區等復雜地理環境下開通，站址選擇需要考慮的因素較多，比如是否遮擋、能否到達以及能否展開等。受限于電子地圖的精度，一般需要規劃人員根據任務具體情況進行站址的人工預選，甚至針對某些特殊的任務，需要進行實地勘測，最終形成備選站址庫。

（3）站址選擇

站址選擇是在備選站址庫中選擇適合的站址作為此次任務的通信站點，一般根據選擇的無線通信手段，采用無線覆蓋計算方式，分析各站點的無線覆蓋范圍，最終確定具體的站址。站址選擇實際上是多目標優化問題，即如何從備選站點庫中找出滿足需求的最優的站點組合，也是本文需要解決的問題。

2遺傳算法

遺傳算法是一種以遺傳進化理論為基礎的啟發式算法[11]。在遺傳算法中，將問題潛在的解集作為初始種群，每個種群都是由一定數量的個體組成，每個個體通過一定的方式進行編碼表示。初始種群經過不斷迭代，并通過遺傳算子的操作產生新種群，通過對當前種群個體的適應度進行評估，將其中優秀個體保留至下一代種群中。經過不斷迭代，末代種群中的個體會比前代種群更適應所在環境。最后，末代種群中的最優個體就是目標問題的最優解[12]。遺傳算法流程如圖2所示。

主要流程包括：

①染色體編碼，將問題空間中的解轉換為遺傳算法能夠識別的數字串或字符串，以便于遺傳算法中的交叉與選擇操作。

②初始化種群，生成第一代種群，設置遺傳算法相關參數。

③適應度評價，通過設置的種群適應度函數進行評估，評估當前種群中各個體對環境的適應度。

④通過選擇、交叉和變異等操作不斷產生新個體。

⑤判斷個體的適應值是否滿足當前結束條件，如果滿足結束條件則結束進化過程，輸出當前的最優個體，如果不滿足結束條件，則返回步驟③，直到滿足結束條件為止。

3基于遺傳算法的站址規劃算法

3.1問題描述

假設機動通信系統共有個備選站點，所有站點布設的通信車輛相同，即有相同類型的天線和數量，在進行站址規劃時不考慮天線和設備之間的差異。根據無線傳輸設備性能指標、電波傳播損耗和接收機靈敏度等參數，站點的最大可覆蓋距離為。

3.6交叉變異設計

①選擇操作：在本文中選擇操作采用輪盤賭選擇算子和精英保留策略相結合的方式，既保證每一代種群中優秀的個體有較大的概率優先參與后續操作，又能保證算法朝著最優解方向進化。

②交叉操作：隨機選擇種群中的2個解作為父代個體，按照一定的概率進行交叉操作。

③變異操作：對子代個體按照變異概率進行0/1取反變異操作。

3.7算法流程

4實驗及結果分析

4.1實驗準備

本文通過設計實例進行驗證分析的方式，按照文中思路采用C++語言設計實現了站址規劃原型，并以超短波電臺為傳輸手段，選用山區地形環境進行2次驗證，備選站點數量分別為12和17，用戶數均為7，最大可用通信車輛數為9。實驗環境為Windows7，Intel i5處理器，內存16GB，GIS系統選用國產某地理信息系統，地圖比例尺為1：50 000，僅考慮經緯度和高程數據。規劃結果結合系統實驗進行驗證。

4.2實驗結果

（1）第1次實驗結果

第1次實驗選用山區地形環境1，備選站點數量為17，用戶數為7，分別選用5輛和9輛通信車輛，站址規劃時間分別為27，31 min，生成的規劃結果與實際組網拓撲對比如圖4和圖5所示。（其中圖4為5輛通信車輛的規劃結果與實際組網拓撲對比，圖5為9輛通信車輛的規劃結果與實際組網拓撲對比。圖中圓圈表示用戶節點，空心三角表示備選節點，實心三角表示選中的節點。）

（2）第2次實驗結果

第2次實驗選用山區地形環境2，備選站點數量為17，用戶數為7，分別選用5輛和9輛通信車輛，站址規劃時間分別為39，43 min，生成的規劃結果與實際組網拓撲對比如圖6和圖7所示。

經2次規劃結果與實際組網結果對比，可以看出站址規劃基本可滿足實際使用需求，除個別站點由于無線覆蓋計算結果不準確導致實際選擇與規劃不一致外，其余節點均可按規劃結果布設通信車輛并開通網絡。

（3）運行時間實驗結果另外，在相同實驗環境下，還針對算法的運行時間進行了實驗，分別選用備選站點數量為12，17，21，25，用戶數為7，通信車輛數分別為5和9，通過打樁輸出方式分別記錄無線覆蓋計算算法運行時間和總時間。算法運行時間實驗結果如表1所示。

站址規劃運行時間主要包括無線覆蓋計算時間和規劃算法運行時間兩部分，其中無線覆蓋計算運行時間與地圖精度有直接關系，與規劃算法運行時間相比，無線覆蓋計算時間占整個運行時間的70%以上。

5結束語

本文針對山區復雜地形環境下機動通信網絡站址規劃需求，采用基于電子地圖的無線覆蓋計算和遺傳算法的站址規劃模型，實現山區復雜地形環境下機動通信網絡站址的自動規劃，能夠在一定程度上滿足山區復雜地形環境下快速站址選擇的使用需求。針對算法運行時間長等問題，后續可結合云平臺等環境，采用任務并發執行策略，降低算法運行時間，提升整體效率。

參考文獻

[1]焦良全，孫宜軍，李廣平.鐵塔公司通信站址規劃方法研究（I）[J].中國新通信，2016，18（ 6） ： 23-25.

[2]王世魁，張紅霞，宋文韜，等.基于幾何算法的無線站址自動規劃方法研究及實現[J].移動通信， 2017，41（8）：64-68.

[3] CHANG J Y，LIN Y S. An Efficient Base Station and Relay Station Placement Scheme for Multi-hop Relay Networks[J]. Wireless Personal Communications，2015，82（3）： 1907-1929.

[4]黃驊，江俊.基于聚類的無線網絡基站選址優化算法研究[J].現代信息科技，2018，2（9）：50-52.

[5] ROMERO D，LEUS G. Non-cooperative Aerial Base Station Placement via Stochastic Optimization[C]//2019 15th International Conference on Mobile Ad-Hoc and Sensor Networks （MSN）. Shenzhen： IEEE，2019： 131-136.

[6]李月.基于P系統的改進粒子群優化算法及應用[D].濟南：山東師范大學，2017.

[7]謝慶喜.基于智能優化算法的基站選址優化問題研究與實現[D].濟南：山東師范大學，2018.

[8]董宏成，王騰云. LTE混合組網中基于多目標粒子群的自規劃[J].無線電工程，2019，49（10）： 893-898.

[9]顏陸紅，郭文普，徐東輝，等.基于NSGA-II算法的機動通信系統站址規劃方法[J].計算機應用研究，2022，39（1） ：226-230.

[10]孫威.基于電子地圖的地域無線電波傳播預測研究[D].西安：西安電子科技大學， 2010.

[11]陶郎.基于遺傳算法的復雜背包問題模型優化方法研究[D].安慶：安慶師范大學， 2021.

[12]謝文晴.基于遺傳算法的深度學習優化方法研究[D].哈爾濱：黑龍江大學， 2021.