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

謝許凱　程松林

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

關鍵詞：遺傳算法;免疫算法;基站選址

中圖分類號：TN929.5;TP18? ? ? ?文獻標識碼：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? 引? 言

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

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

1? 5G基站選址的數學模型

面對龐大數量的新建基站，網絡優化和建設的代價非常大，因此在滿足覆蓋范圍和網絡容量的情況下，盡可能地降低建造成本，是基站選址規劃的一個重要目標[4]。基站選址的原則是要盡可能滿足理想的蜂窩結構，并優先考慮用戶需求量大的熱點區域[5]。為了方便構建數學模型，在此我們提出以下假設：（1）測試的區域不包括敏感區域，且都是理想的平地，無極端地形;（2）在MATLAB仿真時將基站和被測試點都看作點集，某個測試點被覆蓋，則該熱點區域被覆蓋。

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

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

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

2.2? 抗體親和度評價

上文中數學模型（1）是一個多目標優化模型，為了方便求解，將每個目標函數設置一個權重，將多個目標函數的優化問題轉化成為求一個目標函數優化的最優解，即得到[7]：

2.4? 選擇交叉變異操作

本文在選擇操作時采用輪盤賭的方法，即基于適應度權重和濃度權重的選擇策略。在進行交叉操作時，新的抗體產生的速度與交叉概率成正比，交叉概率大時會導致搜索范圍大，而當交叉概率過小時，可能會因為搜索過慢進而影響計算時長。此方法可以實現自適應交叉概率較優的解繼續迭代運算，從而減少計算的時間復雜度[8]。在進行變異操作時，變異算子基于適應度進行調整，當適應度較大時，變異概率應當降低，以抑制變異，當適應度偏小時，應當提高變異概率，從而促進變異操作。

2.5? 算法流程

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

3? 仿真實驗與結果分析

3.1? 仿真參數設置

本文算法仿真基于MATLAB2018b，在5km×5km的方形范圍內隨機選擇31個測試點，測試點位置如圖2所示，圖中每個點代表一個測試點，并且不同的點對網絡的需求量各不相同，假設從左往右、從上往下依次為：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。算法參數選擇如下：種群規模為50，記憶庫規模為10，迭代次數60次，交叉概率45%，變異概率33%。

3.2? 仿真結果分析

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

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

4? 結? 論

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

參考文獻：

[1] 張凌志.無線通信網絡基站覆蓋分析與基站選址設計 [J].通訊世界，2019，26（8）：198-199.

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

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

[4] 凌娟.基于混合免疫算法的TD-LTE網絡基站選址優化研究 [D].杭州：杭州電子科技大學，2015.

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

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

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

[8] 李紀魯，張曉，朱杰.基于自適應免疫算法的配送中心選址問題研究 [J].中國儲運，2019（8）：141-144.

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