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

冀云剛 霍永華

摘要：針對山區(qū)復(fù)雜地形環(huán)境下機動通信網(wǎng)絡(luò)站址選擇需求，提出了一種基于遺傳算法的站址自動規(guī)劃方法。對機動通信網(wǎng)絡(luò)站址規(guī)劃需求進(jìn)行了分析，確定了機動通信網(wǎng)絡(luò)站址規(guī)劃目標(biāo)，通過對傳統(tǒng)遺傳算法在初始種群生成、選擇操作等方面進(jìn)行改進(jìn)，以超短波電臺為無線傳輸手段并結(jié)合實際組網(wǎng)實驗，對算法進(jìn)行了驗證。結(jié)果表明，該算法在山區(qū)復(fù)雜環(huán)境下以超短波為傳輸手段的站址規(guī)劃中具有較高的準(zhǔn)確率，能夠滿足機動通信網(wǎng)絡(luò)站址規(guī)劃需求。

關(guān)鍵詞：站址規(guī)劃；遺傳算法；ITU-R.P 526模型

中圖分類號：TP393文獻(xiàn)標(biāo)志碼：A文章編號：1008-1739（2022）14-48-6

0引言

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

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

1機動通信站址規(guī)劃

1.1站址規(guī)劃需求

機動通信站址規(guī)劃是根據(jù)任務(wù)保障需求，在某個區(qū)域內(nèi)選擇合適的點位，利用有無線等各種通信手段形成能夠覆蓋各用戶的骨干網(wǎng)絡(luò)，滿足不同用戶間的信息交互需求。

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

1.2無線覆蓋分析

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

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

1.3站址規(guī)劃流程

典型的站址規(guī)劃流程包括確定規(guī)劃區(qū)域、站點預(yù)選和站點選擇3個步驟。

（1）確定規(guī)劃區(qū)域

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

（2）站址預(yù)選

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

（3）站址選擇

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

2遺傳算法

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

主要流程包括：

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

②初始化種群，生成第一代種群，設(shè)置遺傳算法相關(guān)參數(shù)。

③適應(yīng)度評價，通過設(shè)置的種群適應(yīng)度函數(shù)進(jìn)行評估，評估當(dāng)前種群中各個體對環(huán)境的適應(yīng)度。

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

⑤判斷個體的適應(yīng)值是否滿足當(dāng)前結(jié)束條件，如果滿足結(jié)束條件則結(jié)束進(jìn)化過程，輸出當(dāng)前的最優(yōu)個體，如果不滿足結(jié)束條件，則返回步驟③，直到滿足結(jié)束條件為止。

3基于遺傳算法的站址規(guī)劃算法

3.1問題描述

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

3.6交叉變異設(shè)計

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

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

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

3.7算法流程

4實驗及結(jié)果分析

4.1實驗準(zhǔn)備

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

4.2實驗結(jié)果

（1）第1次實驗結(jié)果

第1次實驗選用山區(qū)地形環(huán)境1，備選站點數(shù)量為17，用戶數(shù)為7，分別選用5輛和9輛通信車輛，站址規(guī)劃時間分別為27，31 min，生成的規(guī)劃結(jié)果與實際組網(wǎng)拓?fù)鋵Ρ热鐖D4和圖5所示。（其中圖4為5輛通信車輛的規(guī)劃結(jié)果與實際組網(wǎng)拓?fù)鋵Ρ?，圖5為9輛通信車輛的規(guī)劃結(jié)果與實際組網(wǎng)拓?fù)鋵Ρ?。圖中圓圈表示用戶節(jié)點，空心三角表示備選節(jié)點，實心三角表示選中的節(jié)點。）

（2）第2次實驗結(jié)果

第2次實驗選用山區(qū)地形環(huán)境2，備選站點數(shù)量為17，用戶數(shù)為7，分別選用5輛和9輛通信車輛，站址規(guī)劃時間分別為39，43 min，生成的規(guī)劃結(jié)果與實際組網(wǎng)拓?fù)鋵Ρ热鐖D6和圖7所示。

經(jīng)2次規(guī)劃結(jié)果與實際組網(wǎng)結(jié)果對比，可以看出站址規(guī)劃基本可滿足實際使用需求，除個別站點由于無線覆蓋計算結(jié)果不準(zhǔn)確導(dǎo)致實際選擇與規(guī)劃不一致外，其余節(jié)點均可按規(guī)劃結(jié)果布設(shè)通信車輛并開通網(wǎng)絡(luò)。

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

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

5結(jié)束語

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

參考文獻(xiàn)

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

[2]王世魁，張紅霞，宋文韜，等.基于幾何算法的無線站址自動規(guī)劃方法研究及實現(xiàn)[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]黃驊，江俊.基于聚類的無線網(wǎng)絡(luò)基站選址優(yōu)化算法研究[J].現(xiàn)代信息科技，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系統(tǒng)的改進(jìn)粒子群優(yōu)化算法及應(yīng)用[D].濟南：山東師范大學(xué)，2017.

[7]謝慶喜.基于智能優(yōu)化算法的基站選址優(yōu)化問題研究與實現(xiàn)[D].濟南：山東師范大學(xué)，2018.

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

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

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

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

[12]謝文晴.基于遺傳算法的深度學(xué)習(xí)優(yōu)化方法研究[D].哈爾濱：黑龍江大學(xué)， 2021.