徐玉佳，張華美，2

（1.南京郵電大學(xué)電子與光學(xué)工程學(xué)院、柔性電子（未來技術(shù)）學(xué)院，江蘇 南京 210023；2.東南大學(xué)毫米波國(guó)家重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210096）

0 引 言

近年來，電力無線專網(wǎng)規(guī)模和復(fù)雜性不斷提升，急需提高其通信傳輸能力來確保電力業(yè)務(wù)的正常開展。而提高電網(wǎng)通信能力勢(shì)必會(huì)增加對(duì)基站的需求，基站規(guī)劃不當(dāng)會(huì)導(dǎo)致整個(gè)電力無線專網(wǎng)業(yè)務(wù)開展效率低、通信質(zhì)量差等問題，因此合理的基站規(guī)劃是網(wǎng)絡(luò)規(guī)劃中的重要任務(wù)之一［1］。

傳統(tǒng)的基站選址方法主要依賴于工程師的經(jīng)驗(yàn)，適用范圍較小且準(zhǔn)確率較低［2］，不能適應(yīng)目前電力業(yè)務(wù)的通信需求。近年來，采用智能優(yōu)化算法對(duì)基站選址問題進(jìn)行優(yōu)化已成為研究的重點(diǎn)和熱點(diǎn)。

朱思峰等［3］在滿足規(guī)劃區(qū)域內(nèi)部覆蓋需求前提下以基站建設(shè)代價(jià)最小為目標(biāo)，提出了一種基于免疫算法的基站選址優(yōu)化方法；針對(duì)3G 基站選址方法的不足，張英杰等［4］繼續(xù)改進(jìn)免疫算法，利用改進(jìn)的免疫算法求解基站選址方案；Li 等［5］根據(jù)TD-LTE 通信網(wǎng)絡(luò)的特點(diǎn)，設(shè)計(jì)了一種基于免疫算法的基站選址優(yōu)化方案；宋黎［6］運(yùn)用遺傳算法以解決無線網(wǎng)絡(luò)中的基站規(guī)劃問題，該方案在降低成本和覆蓋盲區(qū)的同時(shí)提高了信號(hào)質(zhì)量；Wang［7］將基站選址問題與粒子群算法相結(jié)合以解決能耗問題；唐麗晴等［8］以基站覆蓋率為主要優(yōu)化目標(biāo)，將改進(jìn)的鯨魚優(yōu)化算法應(yīng)用到基站選址問題中。

單一的啟發(fā)式算法后期搜索效率較低，其規(guī)劃結(jié)果往往不能得到最佳的基站分布。隨著研究的深入，目前著重于多個(gè)算法融合。劉娟等［9］將粒子群算法和果蠅算法結(jié)合，提高了基站覆蓋性能。Zhou等［10］和馮佳勇［11］分別使用混合遺傳貪心算法和模擬退火—遺傳算法，在保證覆蓋質(zhì)量的前提下降低了成本預(yù)算。（這些混合）算法較單一算法極大地提高了優(yōu)化質(zhì)量。

本文參考的文獻(xiàn)中有一部分考慮了覆蓋和成本［10-17］。但是，因?yàn)門D-LTE 網(wǎng)絡(luò)使用了同頻組網(wǎng)方式［18］，相鄰小區(qū)之間的重疊覆蓋范圍變大，同頻干擾現(xiàn)象嚴(yán)重，導(dǎo)致業(yè)務(wù)終端頻繁掉線，業(yè)務(wù)開展效率難以保證，因此本文除了考慮覆蓋和成本，把重疊覆蓋也加入到優(yōu)化目標(biāo)中，旨在降低同頻干擾。

針對(duì)以上分析，本文提出一種基于改進(jìn)的多元宇宙優(yōu)化（Multi-Verses Optimizer，MVO）算法的基站選址方法。MVO 算法具有參數(shù)少、尋優(yōu)效率高等優(yōu)點(diǎn)，可用于解決多維度優(yōu)化問題［19］。首先，基站選址是一類具有二進(jìn)制解空間的優(yōu)化問題，而基本MVO算法僅適用于連續(xù)域，因此本文采用V型轉(zhuǎn)換函數(shù)進(jìn)行離散化處理。其次，改進(jìn)了算法中的TDR參數(shù)，平衡了算法的探索和開發(fā)能力。最后，將禁忌搜索算法融入到MVO 算法的尋優(yōu)過程中，增強(qiáng)了算法擺脫局部最優(yōu)的能力。仿真結(jié)果表明，本文算法對(duì)于解決基站選址優(yōu)化問題具有較高的求解效率和卓越的性能優(yōu)勢(shì)。

1 基站選址建模

1.1 鏈路預(yù)算模型

采用COST 231-HATA 模型，1.8 GHz 電力無線專網(wǎng)傳播模型的路徑損耗公式為：

式中，PL 是路徑損耗（dB）；f是頻率（MHz）；hb是基站天線高度（m）；hm是終端天線高度（m）；d是終端與基站之間的距離（km）；a（hm）是終端天線高度校正因子；CM是環(huán)境校正因子。

參考信號(hào)接收功率RSRP（Reference Signal Receiving Power）是LTE 小區(qū)網(wǎng)絡(luò)中接收功率電平的測(cè)量值，其公式為：

式中，PBS為基站發(fā)射功率（dBm）；G為基站天線和終端天線的增益之和（dB）；Lf+p+b為饋線損耗、穿透損耗、人體損耗之和（dB）；Mf+I為陰影余量和干擾余量之和（dB）。

本文以測(cè)試點(diǎn)的RSRP 作為衡量覆蓋率的標(biāo)準(zhǔn)，若某個(gè)測(cè)試點(diǎn)的RSRP＜-105 dBm，則認(rèn)為該測(cè)試點(diǎn)沒有被基站覆蓋。通過式（1）和式（2）求出每個(gè)基站覆蓋范圍內(nèi)RSRP=-105 dBm 的點(diǎn)到基站的距離，作為基站的覆蓋半徑。

1.2 數(shù)學(xué)建模

基于以上基站選址的原則，本文把多目標(biāo)的基站選址問題分解為3 個(gè)子目標(biāo)：成本函數(shù)fcost、覆蓋函數(shù)fcover和重疊覆蓋函數(shù)foverlap，并將覆蓋率作為約束條件。

假設(shè)實(shí)驗(yàn)區(qū)域長(zhǎng)度為a，寬度為b，候選基站站址集合為BS={1，2，…，n}，測(cè)試點(diǎn)集合為test={1，2，…，m} 。候選基站被選中的情況可用表示，即：

第一個(gè)目標(biāo)函數(shù)是成本函數(shù)，與基站個(gè)數(shù)有關(guān)。由于一般選取適應(yīng)度較大的解作為優(yōu)勢(shì)解，因此轉(zhuǎn)化成求解最大值，故做如下定義：

式中，distij表示基站i到測(cè)試點(diǎn)j的距離，Ri表示基站i的覆蓋半徑。

第二個(gè)目標(biāo)函數(shù)是覆蓋率，其值等于基站覆蓋的測(cè)試點(diǎn)個(gè)數(shù)/測(cè)試點(diǎn)總數(shù)，由式（5）推出，即：

由于基站的重疊面積計(jì)算較為復(fù)雜，純數(shù)學(xué)方法難以求解，故本文采用蒙特卡洛方法，首先建立起概率模型和待求解問題的聯(lián)系，將點(diǎn)的概率等效為面積的概率；然后采用計(jì)算機(jī)技術(shù)在區(qū)域內(nèi)隨機(jī)抽取n′個(gè)試驗(yàn)點(diǎn)（本文設(shè)為2000）；最后借助統(tǒng)計(jì)規(guī)律求出基站重疊覆蓋面積。

衡量試驗(yàn)點(diǎn)是否被重疊覆蓋可用式（7）表示：

由式（7）可以推出區(qū)域重疊面積，即：

選中的基站覆蓋總面積如式（9）：

第三個(gè)目標(biāo)函數(shù)是重疊覆蓋函數(shù)，可由式（7）～式（9）推出，為了使優(yōu)化方向一致，轉(zhuǎn)換為求解最大值問題，即：

本文采用權(quán)重法將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，建立的數(shù)學(xué)模型如下：

式中，ε表示覆蓋率閾值，本文設(shè)為0.95。α、β和γ分別表示各個(gè)目標(biāo)函數(shù)的權(quán)重系數(shù)，并且α+β+γ=1，這使得f（x）∈［0，1］。f（x）越大，越接近最優(yōu)值。

2 改進(jìn)多元宇宙優(yōu)化算法在基站選址中的應(yīng)用

2.1 二進(jìn)制多元宇宙優(yōu)化算法

MVO 算法［20］中每個(gè)宇宙代表優(yōu)化問題的一個(gè)可行解，宇宙的膨脹率代表解的適應(yīng)度值，通過模擬黑洞、白洞和蟲洞的互相作用，尋找最優(yōu)宇宙。算法描述如下：

式中，N為宇宙?zhèn)€數(shù)，D為宇宙維度，為第i個(gè)宇宙的第j個(gè)分量。

式中，為第k個(gè)宇宙（即白洞）的第j個(gè)分量；NI（x）i為第i個(gè)宇宙的歸一化膨脹率。r1為［0，1］之間的隨機(jī)數(shù)。

宇宙位置更新方式為：

式中，X（j）為全局最優(yōu)宇宙的第j個(gè)分量；ubj和lbj分別為變量的上下界；r2、r3和r4都是［0，1］之間的隨機(jī)數(shù)。WEP 表示蟲洞存在率，TDR 表示旅行距離率，更新公式為：

式中，WEPmin和WEPmax為WEP 的最小值和最大值；t和T為當(dāng)前和最大迭代次數(shù)；p為開采準(zhǔn)確度。

基本MVO 算法僅適用于連續(xù)域，因此本文采用V型函數(shù)將實(shí)數(shù)映射到［0，1］區(qū)間，即：

最后進(jìn)行位置更新：

本文將基本二進(jìn)制多元宇宙優(yōu)化算法簡(jiǎn)稱為BMVO算法。

2.2 改進(jìn)二進(jìn)制多元宇宙優(yōu)化算法

針對(duì)BMVO算法存在的早熟收斂、后期局部搜索能力弱等缺點(diǎn)，對(duì)BMVO 算法進(jìn)行改進(jìn)，提出離散禁忌-多元宇宙優(yōu)化算法（TS-BMVO）。改進(jìn)如下：1）借鑒其他智能優(yōu)化算法［21-22］改進(jìn)TDR 以均衡算法的全局和局部搜索能力；2）引進(jìn)禁忌搜索算法抑制算法早熟收斂。

2.2.1 改進(jìn)旅行距離率TDR

在BMVO算法中，算法能夠在迭代前期依靠積累的經(jīng)驗(yàn)迅速收斂到最優(yōu)解附近，但是由于p值固定導(dǎo)致TDR 下降緩慢，算法后期局部搜索精度和能力較弱。因此，針對(duì)算法中存在的問題，本文采取動(dòng)態(tài)p值，即：

改進(jìn)前后的TDR 隨p值的變化如圖1 所示，經(jīng)過改進(jìn)TDR之后，算法在迭代前期迅速下降，依靠前期積累的經(jīng)驗(yàn)迅速向最優(yōu)宇宙移動(dòng)，而從迭代總次數(shù)的1/3處開始，TDR下降的幅度趨于穩(wěn)定，有利于后期深度局部搜索。相較于原始算法，減小了旅行距離，能夠有效提升算法中后期搜索最優(yōu)宇宙的精度與效率。

圖1 TDR變化曲線對(duì)比圖

僅僅用迭代次數(shù)決定算法收斂方向是片面的，故將TDR作進(jìn)一步改進(jìn)：

式中，fmean表示第t次迭代所有宇宙適應(yīng)度值的均值。對(duì)于適應(yīng)度值優(yōu)于平均水平的宇宙，其對(duì)應(yīng)的TDR值較小，不發(fā)生明顯位置變化，有利于宇宙在旅行范圍內(nèi)進(jìn)行深度局部開發(fā)；反之，對(duì)于性能較差的宇宙，其對(duì)應(yīng)的TDR 較大，擴(kuò)大搜索空間，快速向最優(yōu)宇宙靠攏。本文將僅改進(jìn)TDR 的MVO 算法稱為TBMVO算法。

2.2.2 引進(jìn)禁忌搜索算法

由于MVO 算法局部搜索能力有所不足，而禁忌搜索算法（Tabu Search，TS）［23］具有獨(dú)特的“記憶功能”，局部尋優(yōu)能力較強(qiáng)，因此引進(jìn)TS 算法。在MVO算法尋優(yōu)過程中，當(dāng)檢測(cè)到算法搜索能力較差時(shí)，將某次迭代中性能最差的解作為TS算法的初始解進(jìn)行鄰域搜索，并且設(shè)置禁忌表來禁忌最近若干次找到的局部最優(yōu)解。當(dāng)禁忌表達(dá)到容量上限時(shí)，按先后順序依次釋放禁忌對(duì)象。

鄰域解采取2 點(diǎn)變異的方式，即隨機(jī)選取當(dāng)前解中2 個(gè)位置上的值進(jìn)行“取反”操作，即0 變成1，1 變成0。

TS算法的流程如圖2所示。

圖2 禁忌搜索算法流程圖

2.2.3 TS-BMVO算法

TS-BMVO 算法的總體流程如圖3（a）所示，虛線框部分是本文算法的重點(diǎn)，分為2個(gè)步驟：

圖3 TS-BMVO算法流程圖

1）建立哨兵檢測(cè)機(jī)制，輔助算法及時(shí)發(fā)現(xiàn)性能較差的宇宙，通過設(shè)置sentinel 變量實(shí)時(shí)記錄各宇宙的性能沒有超過平均水平的連續(xù)次數(shù)，其原理如圖3（b）所示。若某次迭代中宇宙的適應(yīng)度值超過平均水平，則對(duì)應(yīng)的sentinel 值清零，直至算法結(jié)束停止sentinel 更新。迭代若干次后，認(rèn)為sentinel 值最大的宇宙最有可能陷入局部最優(yōu)，將該宇宙作為TS 算法的初始解。

2）運(yùn)用TS算法求解優(yōu)化問題，其最優(yōu)解將代替上述性能較差的宇宙，繼續(xù)搜索全局最優(yōu)解，直至結(jié)束。

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

本文選取某5 km×5 km城市區(qū)域，采用上述基站選址問題的測(cè)試算例，分別運(yùn)用BMVO 算法、TBMVO算法和TS-BMVO算法這3種不同算法進(jìn)行仿真實(shí)驗(yàn)。同時(shí)，在相同模型下利用基本離散粒子群算法（BPSO）進(jìn)行仿真實(shí)驗(yàn)，并與上面3 種算法進(jìn)行比較分析。在基站選址問題的測(cè)試算例中，候選基站個(gè)數(shù)為65，測(cè)試點(diǎn)個(gè)數(shù)為170，基站覆蓋半徑為1.2909 km。

實(shí)驗(yàn)平臺(tái)為：Windows10，Matlab R2021a。實(shí)驗(yàn)參數(shù)設(shè)置為：解的數(shù)量N為300，最大迭代次數(shù)Max-Iter 為500，均采用二進(jìn)制編碼。本文參考文獻(xiàn)［24］的因素重要性比較結(jié)果，結(jié)合本文研究?jī)?nèi)容，在滿足95%的覆蓋閾值的前提下，以節(jié)約成本為第一優(yōu)化目標(biāo)，覆蓋和重疊覆蓋為其次，最后設(shè)置目標(biāo)函數(shù)中的α為0.65、β為0.2、γ為0.15。

表1 比較了各個(gè)算法的適應(yīng)度值、收斂代數(shù)、需要的基站個(gè)數(shù)、覆蓋率、重疊覆蓋面積。圖4～圖7 是仿真得到的基站分布圖。其中藍(lán)色點(diǎn)代表測(cè)試點(diǎn)；黑色空心圓圈為未被選中的基站，紅色實(shí)心圓圈為被選中的基站。

表1 各個(gè)算法的尋優(yōu)結(jié)果

圖4 基于BPSO算法仿真得到的基站分布圖

圖5 基于BMVO算法仿真得到的基站分布圖

圖6 基于TBMVO算法仿真得到的基站分布圖

圖7 基于TS-BMVO算法仿真得到的基站分布圖

由圖4～圖7 和表1 可以看出，TS-BMVO 算法優(yōu)化之后的建站數(shù)量和重疊覆蓋面積明顯優(yōu)于另外3個(gè)算法；雖然覆蓋率稍低于TBMVO 算法，但是TBMVO 算法覆蓋率高的代價(jià)是建站成本增加，并不滿足電力無線專網(wǎng)長(zhǎng)期可持續(xù)發(fā)展的原則，而TSBMVO 算法能夠在滿足覆蓋率閾值的前提下兼顧電網(wǎng)經(jīng)濟(jì)性原則，抑制同頻干擾的效果更好，且未來可用于成本較低的中繼站或者微站補(bǔ)充覆蓋。因此本文提出的TS-BMVO 算法可以運(yùn)用到基站選址問題中，在最小成本的前提下，獲得最優(yōu)的網(wǎng)絡(luò)質(zhì)量。

各個(gè)算法的適應(yīng)度函數(shù)變化曲線如圖8 所示。由圖8 可以看出：1）在迭代前期TS-BMVO 算法的適應(yīng)度值迅速增加，并且持續(xù)高于另外3個(gè)算法；2）TSBMVO 算法明顯具有優(yōu)越的收斂性能。這是因?yàn)楸疚耐ㄟ^改進(jìn)TDR 很好地平衡了算法迭代前后期的收斂過程，又引進(jìn)了TS算法，避免了算法無意義的迂回搜索。綜上，本文提出的TS-BMVO 算法的全局搜索能力較強(qiáng)。

圖8 各個(gè)算法的適應(yīng)度函數(shù)曲線圖

4 結(jié)束語(yǔ)

本文根據(jù)TD-LTE 電力無線專網(wǎng)當(dāng)前實(shí)際需求，確定了基站選址的主要目標(biāo)，基于此，構(gòu)建了基站選址優(yōu)化的數(shù)學(xué)模型，并采用改進(jìn)的MVO 算法進(jìn)行求解。主要對(duì)MVO 算法進(jìn)行了2 點(diǎn)改進(jìn)：1）改進(jìn)TDR參數(shù)；2）融入禁忌搜索算法。仿真結(jié)果表明TSBMVO 算法具有優(yōu)越的性能，在滿足電網(wǎng)的基站規(guī)劃特征和覆蓋率要求的同時(shí)，能夠以最少的投資預(yù)算獲得最大的經(jīng)濟(jì)效益，并且有效保證了終端信號(hào)質(zhì)量。