冀云剛 霍永華

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

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

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

0引言

機(jī)動(dòng)通信網(wǎng)絡(luò)是為了滿足某種任務(wù)而臨時(shí)開設(shè)的通信網(wǎng)絡(luò)。與固定網(wǎng)絡(luò)不同，機(jī)動(dòng)通信網(wǎng)絡(luò)一般不依托固定基礎(chǔ)設(shè)施，多采用無線通信手段，一般采用“一事一規(guī)劃”的方式。因此，網(wǎng)絡(luò)規(guī)劃是機(jī)動(dòng)通信網(wǎng)絡(luò)能否滿足任務(wù)通信保證需求的關(guān)鍵。站址規(guī)劃作為機(jī)動(dòng)通信網(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)鍵問題。目前針對(duì)該問題，多采用人工規(guī)劃方式，由通信保障人員利用無線覆蓋分析工具，計(jì)算不同點(diǎn)位無線覆蓋情況，并結(jié)合任務(wù)需求人工選擇站址。整個(gè)過程花費(fèi)時(shí)間長(zhǎng)，無法有效滿足機(jī)動(dòng)通信網(wǎng)絡(luò)快速規(guī)劃開通的需求。

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

1機(jī)動(dòng)通信站址規(guī)劃

1.1站址規(guī)劃需求

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

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

1.2無線覆蓋分析

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

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

1.3站址規(guī)劃流程

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

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

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

（2）站址預(yù)選

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

（3）站址選擇

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

2遺傳算法

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

主要流程包括：

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

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

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

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

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

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

3.1問題描述

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

3.6交叉變異設(shè)計(jì)

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

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

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

3.7算法流程

4實(shí)驗(yàn)及結(jié)果分析

4.1實(shí)驗(yàn)準(zhǔn)備

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

4.2實(shí)驗(yàn)結(jié)果

（1）第1次實(shí)驗(yàn)結(jié)果

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

（2）第2次實(shí)驗(yàn)結(jié)果

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

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

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

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

5結(jié)束語

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

參考文獻(xiàn)

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

[2]王世魁，張紅霞，宋文韜，等.基于幾何算法的無線站址自動(dòng)規(guī)劃方法研究及實(shí)現(xiàn)[J].移動(dòng)通信， 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].濟(jì)南：山東師范大學(xué)，2017.

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

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

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

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

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

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