免疫優化算法在農村5G 基站選址中的應用

陳東園，劉 芬，馮立營，高雪蘋，李保勝，劉曉倩

（天津職業技術師范大學電子工程學院，天津 300222）

近年來，我國大力發展第五代移動通信（5G）技術，基站建設數量以及用戶數量一直位于世界前列。隨著網絡直播深入農村，網絡作為直播帶貨最基礎的“必需品”，必須要得到有效保障。5G 網絡具有傳輸速度快、延時低等優勢。5G 網絡覆蓋鄉鎮有助于推動鄉鎮經濟發展，在振興農村經濟中起著至關重要的作用。目前，5G 信號在我國大城市覆蓋范圍廣，但在農村等地勢復雜的地方，因選址不易而導致5G 網絡覆蓋率并不高。因此，農村地區的5G 基站選址是一項難度較高、但又是極其重要的任務。

基站選址屬于多目標優化問題，不僅要盡可能多地覆蓋用戶，還要考慮降低成本。針對選址問題，目前許多學者已經做了相關的研究。文獻[1]針對原粒子群優化算法存在的早熟收斂和局部優化能力差的缺點，提出了一種改進的粒子群優化算法，并將其應用于通信基站的定位。實驗表明，在考慮人口密集分布情況下，改進后的算法能夠發掘出合理的基站坐標點。文獻[2]提出利用貪婪算法求解基站規劃問題，但貪婪算法存在易陷入局部極值的缺點，很難達到全局最優解。文獻[3]提出了一種基于遺傳算法的通信基站規劃方法，對選址原則和影響因素進行分析，利用遺傳算法尋找最佳建址位置，并在具體區域進行仿真模擬，驗證了遺傳算法的有效性。文獻[4]分析了基站選址的優化目標和約束條件，采用了加權最小模理想點法，求解5G 網絡基站的選址問題，主要思想是將優化目標代入算法進行仿真研究，根據權重的不同得出不同的建址方案，從而實現對選址優化問題的求解。多目標優化問題通常的處理方式有蟻群算法（ACO）[5]、粒子群算法（PSO）[6]、遺傳算法（GA）[7]等群智能算法，但這些算法在迭代后期往往存在種群多樣性減少的問題，而免疫算法具有自我調節功能，能有效保持種群的多樣性，可以避免算法在尋優后期陷入局部極值。鑒于此，本文提出一種基于免疫優化算法的尋址方案。

1 農村5G 基站選址模型的建立

1.1 問題描述

5G 技術在經濟發達的城鎮地區普及較廣，但在地形復雜，如山地、丘陵較多的農村地區覆蓋率并不高。當前在農村地區普及5G 通信技術，要在指定區域內建立基站，需要提前開展基站選址工作。選址原則不僅要求基站總數盡量少，還要保證盡可能多地覆蓋指定區域內的測試點（村莊）。

1.2 模型建立

在5G 基站選址模型中做如下假設：①5G 基站選址都在建設用地范圍之內；②5G 基站選址已滿足網絡結構合理、網絡覆蓋原則以及安全性原則；③在Matlab 仿真時，把農村點和基站當作點集，任意1 個農村點被網絡覆蓋代表該農村點整個地方都已被網絡覆蓋。

基于以上假設，建立選址模型。從某一區域內的n個農村找出最適合建設基站的目標農村點，使資源合理分配，在滿足5G 網絡覆蓋率高的情況下，盡可能降低成本。在本模型中，目標函數為建設基站所需費用與基站到各農村點的距離的乘積之和，其最小值即為問題的最優解，目標函數公式為

式中：N={1，2，3，…，31}為農村點的序號集合；i∈N，Mi?N；wi為建設基站所需費用；dij為從農村點i 到離其最近的基站中心j 的距離；Zij為屬于0～1 的變量，代表農村點和基站之間的分配關系，當Zij=1 時，為農村點i 的網絡由基站j 覆蓋，否則Zij=0。

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

2.1 免疫優化算法

免疫優化算法（immune optimization algorithm，IA）是模仿生物免疫系統的工作原理提出一種智能搜索算法，最早由Farmer 等[8]提出有關免疫概念，并將免疫系統與其他人工智能方法聯系起來。免疫優化算法具備良好的學習能力、記憶能力和模式識別能力，被廣泛應用于無人機協同目標搜索[9]、車輛調度路線優化問題[10]、無線傳感網絡部署[11]等領域。本文利用免疫優化算法解決基站選址問題，在一定程度上擴大了其應用范圍。應用免疫算法求解基站選址問題時，將選址問題當作免疫系統中的抗原，把可行性解看作免疫系統中的抗體（B 細胞），把可行解的質量看作生物免疫系統中免疫細胞與抗原的親和力。文獻[12]給出了免疫優化算法的實現過程，該算法同時具備保持種群多樣性、全局搜索能力強、魯棒性好的優勢，在解決多峰函數問題時，可以有效防止陷入局部極值的問題，采用免疫優化算法進行農村5G 基站選址時，能夠更合理且更快速地找出最優預測解。

2.2 初始抗體群的產生和編碼

針對本文案例所提出的數學模型，抗原等同于要解決的問題，抗原識別等同于問題識別，對需要解決的問題仔細分析后，可以設計出滿足問題的所有表達式。本文采用的編碼方法為：將抗體編碼表示為AV=（v1，v2，v3，…，vr），其中，vr（r∈N），N 表示基站數量。將每個5G 基站選址方案都可以看作一個長度為N 的抗體，每個抗體代表5G 基站選址選擇的序列。選擇一個模型包含35 個需求點，從中選擇10 個作為5G 基站位置，如代表需求點，則抗體[4，8，9，13，15，20，25，28，30，35]代表1 個可行解向量，其表示4、8、9、13、15、20、25、28、30、35 被選為5G 基站選址位置。

2.3 抗體親和度評價

本文為了使數學模型方便求解，需要將式（1）的多目標求解問題轉化為單目標優化問題。則抗體親和度函數[13]為

式中：Fv為目標函數；C 為較大的正數。

2.4 評價解的濃度

計算出抗體的濃度Cv，因為在免疫優化算法中，抗體濃度求解是至關重要的，直接影響到能否找到最優解。抗體濃度Cv表達式[14]為

2.5 期望繁殖概率

本文采用函數excellence 計算個體繁殖概率。在免疫優化算法中，在抑制高濃度個體時，容易導致最優解的丟失，因此采用精英保留策略[15]。每個個體的期望繁殖概率由2 個因素決定，一個是抗體之間的親和力Av，另一個是抗體濃度Cv，表達式為[16]

式中：β 為常數。

根據以上公式可得出：個體的適合度與預期的繁殖概率成正比；個體濃度與預期的繁殖概率成反比。

3 仿真實驗與分析

3.1 實驗參數設置

依據農村5G 基站選址優化模型，本文在Window10系統、AMD 處理器4GB 內存的運行環境下，使用Matlab 2016B 版本繪圖工具[17]進行仿真實驗。為了驗證免疫優化算法和數學模型的有效性，每一個農村坐標數據和用戶的網絡需求量數據都經過規范處理，但并不代表真實坐標和真實用戶量。表1 詳細列出了農村點的假設相對坐標及用戶的網絡需求。

本實驗模擬了31 個農村位置，將表1 數據導入Matlab 軟件中運行，用圓圈代表農村點，從這31 個農村坐標中選取適合做5G 基站選址的7 個坐標，以求達到減少選址成本、提高覆蓋率的要求。模型按照免疫優化算法的步驟求解，參數設置為：種群大小sizepop=50，記憶庫容量over best=10，最大迭代次數MAXGEN=70，交叉概率0.5，變異概率0.4，多樣性評估參數90%。

表1 農村點相對坐標及用戶用網需求量

3.2 實驗結果分析

為了驗證本文提出的免疫優化算法在基站選址問題中的實用性和有效性，本研究與基于遺傳算法的基站選址方法進行了對比。5G 基站位置與農村點之間的關系如表2 所示。

表2 5G 基站位置與農村點之間的關系

基于免疫優化算法的選址方法得出的目標函數值（成本）為5.093 8×105，而基于遺傳算法的選址方法得出的目標函數值（成本）為2.818 0×106。5G 基站選址最佳方案為[2，4，5，15，20，27，31]。基于免疫算法和基于遺傳算法的仿真結果分別如圖1 和圖2所示。

圖1 基于免疫算法的仿真結果

圖2 基于遺傳算法的仿真結果

圖1（a）和圖2（a）中分別被大圓圈和方框覆蓋的點，即為農村5G 基站的最佳選址位置。從這2 幅圖中可以看出，基于免疫優化算法的選址方案比基于遺傳算法的選址方案更優。2 種方案雖然都能實現農村點全覆蓋，但從圖1（a）中可以看出，每個基站都被合理利用，基站到被覆蓋農村點的距離最短，成本更低。而從圖2（a）可以看出，基于遺傳算法的選址方案存在資源浪費的現象，建設在村莊7 處的基站僅覆蓋了2 個村莊，建設在村莊5 處的基站到村莊1 的距離太遠，可能會導致村莊1 接收的網絡信號較差等問題，從而使用戶上網體驗感較差。故采用本研究選用的免疫優化算法進行農村點5G 基站選址方案相對來說更好。

4 結 語

本文基于影響農村5G 網絡選址相關因素及其特點，構建了農村5G 基站選址優化數學模型，采用免疫優化算法（IOA）對模型求解。從仿真結果可以看出，本研究算法具有較快的收斂速度，能夠提供相對合理的農村5G 基站選址方案，為農村用戶提供更滿意的網絡體驗。本文在對農村5G 基站選址分析中，僅考慮了影響農村5G 基站選址的2 個因素，即基站建設成本和農村5G 網絡覆蓋程度，為了使模型更加貼近實際，影響基站選址的其他因素有待進一步研究。