基于免疫遺傳算法的5G基站選址規(guī)劃

謝許凱　程松林

摘? 要：基站選址的規(guī)劃，因其能夠提高通信服務(wù)質(zhì)量和降低新建基站成本而一直是學(xué)術(shù)界和業(yè)界關(guān)注的問題。文章綜合分析了基站選址問題的目標(biāo)、原則、方法和求解面臨的困難，結(jié)合遺傳算法和人工免疫算法的優(yōu)點(diǎn)，建立了基站選址的數(shù)學(xué)模型。為避免遺傳算法的“早熟”，在遺傳算法中加入免疫的因素，仿真結(jié)果表明，該模型算法具有很快的收斂速度，在某一區(qū)域內(nèi)需求已知的條件下可以提供一種有效的基站選址方案。

關(guān)鍵詞：遺傳算法;免疫算法;基站選址

中圖分類號：TN929.5;TP18? ? ? ?文獻(xiàn)標(biāo)識碼：A 文章編號：2096-4706（2020）02-0004-03

Abstract：The planning of base station location，because it can improve the quality of communication service and reduce the cost of new base station，has been the focus of academia and industry. In this paper，the goal，principle，method and the difficulty of solving the location problem of base station are analyzed synthetically. Combining the advantages of genetic algorithm and artificial immune algorithm，the mathematical model of location problem of base station is established. In order to avoid the “precocity” of genetic algorithm，the immune factor is added to the genetic algorithm. The simulation results show that the model algorithm has a fast convergence speed，and can provide an effective base station location scheme when the demand in a certain area is known.

Keywords：genetic algorithm;immune algorithm;base station location

0? 引? 言

隨著通信技術(shù)的飛速發(fā)展，越來越多的設(shè)備和終端接入了移動(dòng)通信網(wǎng)絡(luò)。為了滿足對于日益增長的移動(dòng)數(shù)據(jù)訪問的需求，更高帶寬和速率的5G技術(shù)應(yīng)運(yùn)而生。而5G技術(shù)的發(fā)展，即將帶來的不僅僅是簡單的網(wǎng)速提升，更標(biāo)志著科技時(shí)代通信行業(yè)的又一次重大革新。目前我國大部分地區(qū)都建立了大量的4G基站，另外已有少數(shù)地區(qū)進(jìn)行了5G網(wǎng)絡(luò)的商用試點(diǎn)。隨著未來接入5G網(wǎng)絡(luò)的用戶數(shù)量的增加，如何對5G基站進(jìn)行選址布局來保證對服務(wù)區(qū)域進(jìn)行有效的網(wǎng)絡(luò)覆蓋，從而提供可靠的通信傳輸服務(wù)是需要重點(diǎn)考慮的問題。

目前已有文獻(xiàn)對于基站選址規(guī)劃進(jìn)行了相關(guān)的研究，文獻(xiàn)[1]提出了室內(nèi)、室外及盲區(qū)的覆蓋方案;文獻(xiàn)[2]從不同階段分析了選址的技術(shù)要點(diǎn);文獻(xiàn)[3]建立了基站選址的數(shù)學(xué)模型，并基于遺傳算法進(jìn)行求解。遺傳算法在解決此類大規(guī)模問題時(shí)容易陷入局部最優(yōu)解，而免疫算法盡管效率不佳，但具有更好的多峰值搜索能力，特別是在多個(gè)極值點(diǎn)的情況下，可以快速地找到所有極值點(diǎn)，從而尋到全局最優(yōu)解。本文結(jié)合了遺傳算法的搜索特性和免疫算法的自適應(yīng)特性，采用免疫遺傳算法對于5G基站選址問題進(jìn)行數(shù)學(xué)建模和求解，很大程度上避免了過早收斂于局部極值。

1? 5G基站選址的數(shù)學(xué)模型

面對龐大數(shù)量的新建基站，網(wǎng)絡(luò)優(yōu)化和建設(shè)的代價(jià)非常大，因此在滿足覆蓋范圍和網(wǎng)絡(luò)容量的情況下，盡可能地降低建造成本，是基站選址規(guī)劃的一個(gè)重要目標(biāo)[4]?；具x址的原則是要盡可能滿足理想的蜂窩結(jié)構(gòu)，并優(yōu)先考慮用戶需求量大的熱點(diǎn)區(qū)域[5]。為了方便構(gòu)建數(shù)學(xué)模型，在此我們提出以下假設(shè)：（1）測試的區(qū)域不包括敏感區(qū)域，且都是理想的平地，無極端地形;（2）在MATLAB仿真時(shí)將基站和被測試點(diǎn)都看作點(diǎn)集，某個(gè)測試點(diǎn)被覆蓋，則該熱點(diǎn)區(qū)域被覆蓋。

2? 5G基站選址的算法流程

2.1? 種群的初始化及編碼方案

對于本文提出的數(shù)學(xué)模型，由于待選的基站位置只存在被選擇和未被選擇兩種情況，我們采用二進(jìn)制編碼，抗體編碼Ab表示為Ab={b1，b2，b3，…，bN}，其中N是待選基站個(gè)數(shù)，bi表示第i個(gè)基站被選擇的情況：

2.2? 抗體親和度評價(jià)

上文中數(shù)學(xué)模型（1）是一個(gè)多目標(biāo)優(yōu)化模型，為了方便求解，將每個(gè)目標(biāo)函數(shù)設(shè)置一個(gè)權(quán)重，將多個(gè)目標(biāo)函數(shù)的優(yōu)化問題轉(zhuǎn)化成為求一個(gè)目標(biāo)函數(shù)優(yōu)化的最優(yōu)解，即得到[7]：

2.4? 選擇交叉變異操作

本文在選擇操作時(shí)采用輪盤賭的方法，即基于適應(yīng)度權(quán)重和濃度權(quán)重的選擇策略。在進(jìn)行交叉操作時(shí)，新的抗體產(chǎn)生的速度與交叉概率成正比，交叉概率大時(shí)會(huì)導(dǎo)致搜索范圍大，而當(dāng)交叉概率過小時(shí)，可能會(huì)因?yàn)樗阉鬟^慢進(jìn)而影響計(jì)算時(shí)長。此方法可以實(shí)現(xiàn)自適應(yīng)交叉概率較優(yōu)的解繼續(xù)迭代運(yùn)算，從而減少計(jì)算的時(shí)間復(fù)雜度[8]。在進(jìn)行變異操作時(shí)，變異算子基于適應(yīng)度進(jìn)行調(diào)整，當(dāng)適應(yīng)度較大時(shí)，變異概率應(yīng)當(dāng)降低，以抑制變異，當(dāng)適應(yīng)度偏小時(shí)，應(yīng)當(dāng)提高變異概率，從而促進(jìn)變異操作。

2.5? 算法流程

免疫遺傳算法流程如圖1所示，基于達(dá)爾文進(jìn)化論的自然選擇和遺傳原理，將問題的解做成一個(gè)由經(jīng)過編碼的基因個(gè)體組成的種群，在初代種群生成后，按照模擬自然界優(yōu)勝劣汰的原則，對未滿足親和度要求的種群進(jìn)行基因的交叉、變異，再加入免疫因素對其進(jìn)行抗體的選擇、抑制操作，生成新的“更適應(yīng)環(huán)境”的種群，即更接近問題要求的近似解。末代種群經(jīng)過解碼后輸出結(jié)果，即為最接近要求的近似解。

3? 仿真實(shí)驗(yàn)與結(jié)果分析

3.1? 仿真參數(shù)設(shè)置

本文算法仿真基于MATLAB2018b，在5km×5km的方形范圍內(nèi)隨機(jī)選擇31個(gè)測試點(diǎn)，測試點(diǎn)位置如圖2所示，圖中每個(gè)點(diǎn)代表一個(gè)測試點(diǎn)，并且不同的點(diǎn)對網(wǎng)絡(luò)的需求量各不相同，假設(shè)從左往右、從上往下依次為：20，90，90，60，70，70，40，90，90，70，60，40，40，40，20，80，90，70，100，50，50，50，80，70，80，40，60，90，70，50，30。算法參數(shù)選擇如下：種群規(guī)模為50，記憶庫規(guī)模為10，迭代次數(shù)60次，交叉概率45%，變異概率33%。

3.2? 仿真結(jié)果分析

采用本文算法進(jìn)行優(yōu)化迭代運(yùn)算選址，最終在測試區(qū)域內(nèi)求得7個(gè)最優(yōu)基站位置，仿真結(jié)果如圖3所示，其中被方塊圈出的點(diǎn)即為可以覆蓋31個(gè)測試點(diǎn)的基站最佳選址位置，與測試點(diǎn)相連的連線代表這個(gè)測試點(diǎn)被哪個(gè)基站覆蓋。另外，最初假設(shè)的需求量不同會(huì)導(dǎo)致不同基站所涵蓋的測試點(diǎn)數(shù)量也不同，需求量小的點(diǎn)和需求量大的點(diǎn)被合理安排，每個(gè)基站承擔(dān)的需求量大致相同。從圖3中可以看出，此時(shí)的選址方案較為合理，在保證覆蓋到每一個(gè)測試點(diǎn)的同時(shí)，合理分配資源，不會(huì)出現(xiàn)某個(gè)基站因需求量過大而產(chǎn)生較差的用戶體驗(yàn)。

算法收斂曲線如圖4所示，由圖4結(jié)果可知，本文提出的算法收斂速度快，同時(shí)具有遺傳算法和免疫算法的優(yōu)點(diǎn)，在保留遺傳算法搜索特性的同時(shí)，又利用免疫算法的自適應(yīng)特性，因此在5G基站選址優(yōu)化問題上具有較好的參考運(yùn)用價(jià)值。

4? 結(jié)? 論

本文討論分析了5G通信基站選址的數(shù)學(xué)模型，并結(jié)合遺傳算法以及免疫算法去求優(yōu)化問題的解。但是本文模型僅僅考慮了基站建造成本、信號覆蓋范圍、網(wǎng)絡(luò)容量這幾個(gè)因素，在后續(xù)研究中可以考慮每個(gè)基站的傳輸半徑等因素，使選址模型更加合理和實(shí)用。

參考文獻(xiàn)：

[1] 張凌志.無線通信網(wǎng)絡(luò)基站覆蓋分析與基站選址設(shè)計(jì) [J].通訊世界，2019，26（8）：198-199.

[2] 劉海鋒.探析移動(dòng)通信工程中的微波傳輸基站勘察選址要點(diǎn) [J].中國新通信，2017，19（8）：1.

[3] 陳志濤，楊小東，蘇鐘.基于遺傳算法的分時(shí)長期演進(jìn)（TD-LTE）多目標(biāo)站址選址方法 [J].科學(xué)技術(shù)與工程，2014，14（7）：29-33+44.

[4] 凌娟.基于混合免疫算法的TD-LTE網(wǎng)絡(luò)基站選址優(yōu)化研究 [D].杭州：杭州電子科技大學(xué)，2015.

[5] 王春蕾.基于改進(jìn)粒子群算法的通信基站選址 [D].南京：南京郵電大學(xué)，2017.

[6] 李道國，李連杰.基于混合免疫算法的TD-LTE網(wǎng)絡(luò)基站選址研究 [J].杭州電子科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，36（5）：57-61.

[7] 牟曉曄.改進(jìn)的并行遺傳算法在基站選址中的應(yīng)用 [J].電腦知識與技術(shù)，2010，6（33）：9529-9532.

[8] 李紀(jì)魯，張曉，朱杰.基于自適應(yīng)免疫算法的配送中心選址問題研究 [J].中國儲(chǔ)運(yùn)，2019（8）：141-144.

作者簡介：謝許凱（1998.06-），男，漢族，上海人，2016級本科生，研究方向：電子信息工程;程松林（1983.05-），男，漢族，湖北黃岡人，講師，博士，研究方向：網(wǎng)絡(luò)信息論。