免疫優(yōu)化算法在農(nóng)村5G 基站選址中的應(yīng)用

陳東園，劉 芬，馮立營(yíng)，高雪蘋(píng)，李保勝，劉曉倩

（天津職業(yè)技術(shù)師范大學(xué)電子工程學(xué)院，天津 300222）

近年來(lái)，我國(guó)大力發(fā)展第五代移動(dòng)通信（5G）技術(shù)，基站建設(shè)數(shù)量以及用戶數(shù)量一直位于世界前列。隨著網(wǎng)絡(luò)直播深入農(nóng)村，網(wǎng)絡(luò)作為直播帶貨最基礎(chǔ)的“必需品”，必須要得到有效保障。5G 網(wǎng)絡(luò)具有傳輸速度快、延時(shí)低等優(yōu)勢(shì)。5G 網(wǎng)絡(luò)覆蓋鄉(xiāng)鎮(zhèn)有助于推動(dòng)鄉(xiāng)鎮(zhèn)經(jīng)濟(jì)發(fā)展，在振興農(nóng)村經(jīng)濟(jì)中起著至關(guān)重要的作用。目前，5G 信號(hào)在我國(guó)大城市覆蓋范圍廣，但在農(nóng)村等地勢(shì)復(fù)雜的地方，因選址不易而導(dǎo)致5G 網(wǎng)絡(luò)覆蓋率并不高。因此，農(nóng)村地區(qū)的5G 基站選址是一項(xiàng)難度較高、但又是極其重要的任務(wù)。

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

1 農(nóng)村5G 基站選址模型的建立

1.1 問(wèn)題描述

5G 技術(shù)在經(jīng)濟(jì)發(fā)達(dá)的城鎮(zhèn)地區(qū)普及較廣，但在地形復(fù)雜，如山地、丘陵較多的農(nóng)村地區(qū)覆蓋率并不高。當(dāng)前在農(nóng)村地區(qū)普及5G 通信技術(shù)，要在指定區(qū)域內(nèi)建立基站，需要提前開(kāi)展基站選址工作。選址原則不僅要求基站總數(shù)盡量少，還要保證盡可能多地覆蓋指定區(qū)域內(nèi)的測(cè)試點(diǎn)（村莊）。

1.2 模型建立

在5G 基站選址模型中做如下假設(shè)：①5G 基站選址都在建設(shè)用地范圍之內(nèi)；②5G 基站選址已滿足網(wǎng)絡(luò)結(jié)構(gòu)合理、網(wǎng)絡(luò)覆蓋原則以及安全性原則；③在Matlab 仿真時(shí)，把農(nóng)村點(diǎn)和基站當(dāng)作點(diǎn)集，任意1 個(gè)農(nóng)村點(diǎn)被網(wǎng)絡(luò)覆蓋代表該農(nóng)村點(diǎn)整個(gè)地方都已被網(wǎng)絡(luò)覆蓋。

基于以上假設(shè)，建立選址模型。從某一區(qū)域內(nèi)的n個(gè)農(nóng)村找出最適合建設(shè)基站的目標(biāo)農(nóng)村點(diǎn)，使資源合理分配，在滿足5G 網(wǎng)絡(luò)覆蓋率高的情況下，盡可能降低成本。在本模型中，目標(biāo)函數(shù)為建設(shè)基站所需費(fèi)用與基站到各農(nóng)村點(diǎn)的距離的乘積之和，其最小值即為問(wèn)題的最優(yōu)解，目標(biāo)函數(shù)公式為

式中：N={1，2，3，…，31}為農(nóng)村點(diǎn)的序號(hào)集合；i∈N，Mi?N；wi為建設(shè)基站所需費(fèi)用；dij為從農(nóng)村點(diǎn)i 到離其最近的基站中心j 的距離；Zij為屬于0～1 的變量，代表農(nóng)村點(diǎn)和基站之間的分配關(guān)系，當(dāng)Zij=1 時(shí)，為農(nóng)村點(diǎn)i 的網(wǎng)絡(luò)由基站j 覆蓋，否則Zij=0。

2 農(nóng)村5G 基站選址的算法流程

2.1 免疫優(yōu)化算法

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

2.2 初始抗體群的產(chǎn)生和編碼

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

2.3 抗體親和度評(píng)價(jià)

本文為了使數(shù)學(xué)模型方便求解，需要將式（1）的多目標(biāo)求解問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題。則抗體親和度函數(shù)[13]為

式中：Fv為目標(biāo)函數(shù)；C 為較大的正數(shù)。

2.4 評(píng)價(jià)解的濃度

計(jì)算出抗體的濃度Cv，因?yàn)樵诿庖邇?yōu)化算法中，抗體濃度求解是至關(guān)重要的，直接影響到能否找到最優(yōu)解?？贵w濃度Cv表達(dá)式[14]為

2.5 期望繁殖概率

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

式中：β 為常數(shù)。

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

3 仿真實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

依據(jù)農(nóng)村5G 基站選址優(yōu)化模型，本文在Window10系統(tǒng)、AMD 處理器4GB 內(nèi)存的運(yùn)行環(huán)境下，使用Matlab 2016B 版本繪圖工具[17]進(jìn)行仿真實(shí)驗(yàn)。為了驗(yàn)證免疫優(yōu)化算法和數(shù)學(xué)模型的有效性，每一個(gè)農(nóng)村坐標(biāo)數(shù)據(jù)和用戶的網(wǎng)絡(luò)需求量數(shù)據(jù)都經(jīng)過(guò)規(guī)范處理，但并不代表真實(shí)坐標(biāo)和真實(shí)用戶量。表1 詳細(xì)列出了農(nóng)村點(diǎn)的假設(shè)相對(duì)坐標(biāo)及用戶的網(wǎng)絡(luò)需求。

本實(shí)驗(yàn)?zāi)M了31 個(gè)農(nóng)村位置，將表1 數(shù)據(jù)導(dǎo)入Matlab 軟件中運(yùn)行，用圓圈代表農(nóng)村點(diǎn)，從這31 個(gè)農(nóng)村坐標(biāo)中選取適合做5G 基站選址的7 個(gè)坐標(biāo)，以求達(dá)到減少選址成本、提高覆蓋率的要求。模型按照免疫優(yōu)化算法的步驟求解，參數(shù)設(shè)置為：種群大小sizepop=50，記憶庫(kù)容量over best=10，最大迭代次數(shù)MAXGEN=70，交叉概率0.5，變異概率0.4，多樣性評(píng)估參數(shù)90%。

表1 農(nóng)村點(diǎn)相對(duì)坐標(biāo)及用戶用網(wǎng)需求量

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

為了驗(yàn)證本文提出的免疫優(yōu)化算法在基站選址問(wèn)題中的實(shí)用性和有效性，本研究與基于遺傳算法的基站選址方法進(jìn)行了對(duì)比。5G 基站位置與農(nóng)村點(diǎn)之間的關(guān)系如表2 所示。

表2 5G 基站位置與農(nóng)村點(diǎn)之間的關(guān)系

基于免疫優(yōu)化算法的選址方法得出的目標(biāo)函數(shù)值（成本）為5.093 8×105，而基于遺傳算法的選址方法得出的目標(biāo)函數(shù)值（成本）為2.818 0×106。5G 基站選址最佳方案為[2，4，5，15，20，27，31]?；诿庖咚惴ê突谶z傳算法的仿真結(jié)果分別如圖1 和圖2所示。

圖1 基于免疫算法的仿真結(jié)果

圖2 基于遺傳算法的仿真結(jié)果

圖1（a）和圖2（a）中分別被大圓圈和方框覆蓋的點(diǎn)，即為農(nóng)村5G 基站的最佳選址位置。從這2 幅圖中可以看出，基于免疫優(yōu)化算法的選址方案比基于遺傳算法的選址方案更優(yōu)。2 種方案雖然都能實(shí)現(xiàn)農(nóng)村點(diǎn)全覆蓋，但從圖1（a）中可以看出，每個(gè)基站都被合理利用，基站到被覆蓋農(nóng)村點(diǎn)的距離最短，成本更低。而從圖2（a）可以看出，基于遺傳算法的選址方案存在資源浪費(fèi)的現(xiàn)象，建設(shè)在村莊7 處的基站僅覆蓋了2 個(gè)村莊，建設(shè)在村莊5 處的基站到村莊1 的距離太遠(yuǎn)，可能會(huì)導(dǎo)致村莊1 接收的網(wǎng)絡(luò)信號(hào)較差等問(wèn)題，從而使用戶上網(wǎng)體驗(yàn)感較差。故采用本研究選用的免疫優(yōu)化算法進(jìn)行農(nóng)村點(diǎn)5G 基站選址方案相對(duì)來(lái)說(shuō)更好。

4 結(jié) 語(yǔ)

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