馬力鵬，冀涵葉

（中國移動通信集團(tuán)設(shè)計(jì)院有限公司，北京 100083）

0 引言

隨著5G 技術(shù)標(biāo)準(zhǔn)的不斷完善，以及大規(guī)模商用的不斷推進(jìn)，5G 無線通信技術(shù)正在逐步走進(jìn)人們的生活中。作為新一代的通信技術(shù)，5G 將從傳統(tǒng)的人與人之間的互聯(lián)擴(kuò)展到人與物、物與物之間的互聯(lián)。相信隨著應(yīng)用方式的不斷拓展，5G 技術(shù)在未來幾年將會為個人、企業(yè)以及社會帶來巨大的收益[1-2]。

相比于LTE 而言，5G 使用了更高的頻段，導(dǎo)致信號傳播損耗更高、衍射能力變?nèi)?，而解決這個問題的首選方式即為大規(guī)模的密集建站，去彌補(bǔ)覆蓋上的缺陷[3-4]。而對于大規(guī)模建站，以及同時完成小區(qū)工參配置而言，一個好的站址規(guī)劃與工參聯(lián)合優(yōu)化算法方案能夠?yàn)檫\(yùn)營商大大降低建站成本。本文針對這個問題給出了一種基于改進(jìn)的遺傳算法完成站址規(guī)劃和小區(qū)工參聯(lián)合優(yōu)化配置模型。

在已有的文獻(xiàn)中，基站站址規(guī)劃問題得到了廣泛的討論與研究[5-9]。優(yōu)化模型通常是通過生成初始隨機(jī)解，然后利用鄰近區(qū)域來完成的。如果相鄰的解決方案優(yōu)于當(dāng)前的解決方案，則它采用該解決方案。否則，通過一定的規(guī)則從之前的解決方案中選取一組?；具x址的常用優(yōu)化模型是基于元啟發(fā)式方法，包括模擬退火（SA,Simulated Annealing）、禁忌搜索（TS,Tabu Search）、遺傳算法（GA,Genetic Algorithm）和粒子群優(yōu)化技術(shù)（PSO,Particle Swarm Optimization）等。

在基站站址優(yōu)化中，模擬退火算法已被證明是一個好的方法[10-11]。SA 算法在搜索過程中，將基站在x 坐標(biāo)和y 坐標(biāo)方向上進(jìn)行隨機(jī)移動。當(dāng)且僅當(dāng)該新位置的價值函數(shù)更大時，才會接受該新位置。當(dāng)所有基站具有新的可接受位置時，形成新的系統(tǒng)“狀態(tài)”。該算法從新的狀態(tài)開始繼續(xù)進(jìn)行迭代優(yōu)化，并不斷估計(jì)與該狀態(tài)相關(guān)聯(lián)的價值。然而對于高維搜索空間，尤其是多種物理量維度組成的高維空間，模擬退火算法收斂需要耗費(fèi)大量的時間。

禁忌搜索同樣也能夠執(zhí)行基站站址規(guī)劃[12]。在對基站位置的局部搜索算法的比較中，TS 在多次運(yùn)行中提供了最恒定的最終目標(biāo)函數(shù)值。它以最少的基站數(shù)量最大化覆蓋。然而，其極易陷入局部最優(yōu)解，對于高維空間更是如此，故僅適合維度較低的組合解求解。

基于粒子群算法的基站站址規(guī)劃，將目標(biāo)區(qū)域分為若干個更小的區(qū)域，并為每個小區(qū)域編碼，然后拼接形成代表大區(qū)域的粒子個體，通過迭代得出建站位置[13]，這種方法需要對地理區(qū)域進(jìn)行細(xì)化分，才能滿足5G 大規(guī)模建站需要。然而細(xì)分意味著組合解向量維度更高，對于大規(guī)模的離散組合問題，粒子群算法極易陷入局部最優(yōu)。

基于聚類的遺傳算法首先通過聚類完成初始種群選取，然后使用遺傳算法完成站址規(guī)劃[14]，這種方法局限于初始隨機(jī)種群的優(yōu)劣以及量綱單一的問題，僅對站址位置優(yōu)化有效，無法完成對站址和小區(qū)朝向等不同物理量的參數(shù)聯(lián)合優(yōu)化，也即多量綱參數(shù)聯(lián)合優(yōu)化。

綜上，對于已有的站址規(guī)劃文獻(xiàn)，僅僅是對于建站位置進(jìn)行了組合求解。然而受限于高維度組合解的困難尋優(yōu)，對于基站站址、小區(qū)工參等多種物理量參數(shù)進(jìn)行聯(lián)合優(yōu)化的問題并沒有給出相應(yīng)的方案。本文借鑒最大期望算法的思想[15]，以及模擬退火局部搜索的思想，并結(jié)合遺傳算法，將由不同物理含義或者不同量綱參數(shù)組成的染色體分步變異、分步交叉，迭代求解最優(yōu)組合，以期達(dá)到覆蓋和干擾的聯(lián)合優(yōu)化。在本文中，該算法簡稱為GAEM。為了能夠在達(dá)到覆蓋和干擾聯(lián)合最優(yōu)的基礎(chǔ)上，同時滿足小區(qū)容量需求，本文算法方案在每次完成覆蓋的同時，還需要對容量進(jìn)行評估。

1 大規(guī)模站址與小區(qū)工參聯(lián)合優(yōu)化方案簡述

在無線通信網(wǎng)絡(luò)中，一方面，對終端用戶而言，信號覆蓋強(qiáng)度（RSRP）以及覆蓋區(qū)域信號的質(zhì)量（SINR）對于感知非常重要，而決定這兩個指標(biāo)的關(guān)鍵有兩點(diǎn)：（1）區(qū)域內(nèi)每一個基站的建站位置；（2）區(qū)域內(nèi)每一個小區(qū)的扇區(qū)朝向。而另一方面，于運(yùn)營商而言，為了降低成本，同一區(qū)域內(nèi)，基站的數(shù)量越少越好。如何尋求這二者之間的平衡，顯得尤為重要。

假設(shè)一個基站有3 個小區(qū)，每一個小區(qū)均配備相同的波束，那么對于一個基站而言，需要優(yōu)化的參數(shù)如下：(x,y,z,α1,θ1,α2,θ2,α3,θ3)，其中(x,y)表示基站的平面坐標(biāo)，z表示基站小區(qū)的高度，(αi,θi)表示小區(qū)的方向角和下傾角。綜上，對于一個配備3 個小區(qū)的基站，需要優(yōu)化的參數(shù)有8 個，其中z軸不在優(yōu)化范圍內(nèi)，為設(shè)定值。

針對這種高維向量優(yōu)化問題，本文提出了一種基于遺傳算法的改進(jìn)算法，用以求解大規(guī)模站址尋優(yōu)及小區(qū)工參聯(lián)合優(yōu)化問題。仿真實(shí)驗(yàn)表明該算法對高維向量、且對各維度物理量不一致的問題表現(xiàn)良好。同時，考慮到小區(qū)容量也對用戶感知異常重要，所以本文也給出了一個估計(jì)容量的簡單方法。站址與小區(qū)工參聯(lián)合規(guī)劃流程圖如圖1 所示：

圖1 站址規(guī)劃方案流程圖

2 基于改進(jìn)遺傳算法的站址與小區(qū)工參聯(lián)合優(yōu)化

GAEM 算法完成站址規(guī)劃的主要步驟如下所示：

（1）柵格化。獲取目標(biāo)區(qū)域地理位置信息，對于目標(biāo)區(qū)域進(jìn)行柵格化劃分。一般情況下，室外柵格大小為建筑物柵格大小的整數(shù)倍，假設(shè)室內(nèi)柵格大小為d×d，室外柵格的大小為kd×kd，其中k為整數(shù)；柵格的高度為1.5 m，對于建筑物，僅取每一樓層相對高度為1.5 m 以內(nèi)的空間進(jìn)行柵格劃分。

（2）預(yù)規(guī)劃。根據(jù)目標(biāo)區(qū)域的大小預(yù)估計(jì)需要的基站數(shù)量，此步驟根據(jù)每一小區(qū)覆蓋有效范圍估算。

（3）基因編碼。在本文中直接采用實(shí)數(shù)方式完成編碼，編碼方式示例如下：x1,y1,...,xn,yn,α11,α12,α13,...,αn3,θ11,θθ12,θ13,...,θn3，其中xi,yi表示基站i的坐標(biāo)，i∈[1,n]，αi,j表示基站i的第j個小區(qū)的方向角，θi,j表示基站i的第j個小區(qū)的天線下傾角，本文中j∈[1,3]。

（4）種群初始化。假設(shè)通過預(yù)規(guī)劃得到需要的基站數(shù)量為n，那么根據(jù)柵格化后的數(shù)據(jù)，隨機(jī)為每一個基站分配不重復(fù)的位置；同時，初始化時固定每個基站小區(qū)的方向角為0、120、240，下傾角均為5°。拼接到一起形成一個單獨(dú)的染色體個體，不斷重復(fù)這個操作，最后得到整個種群，數(shù)量為2N。每個個體表示如下[x1,y1,…xn,yn,0,120,240,…5,5,5,…]。每一個小區(qū)的縱坐標(biāo)值可通過柵格信息完成映射，非建筑物時，z=30 m，對于候選位置在建筑物內(nèi)的柵格，如果建筑物高度超過30 m，那么z取建筑物高度，否則z=30 m。

（5）目標(biāo)函數(shù)值。在站址規(guī)劃任務(wù)中，以覆蓋最優(yōu)、信噪比最高為目標(biāo)，目標(biāo)函數(shù)表示為區(qū)域內(nèi)所有柵格的平均RSRP 和SINR 值的加權(quán)平均，表示如下：

其中，γ表示RSRP 的權(quán)重，取值為0～1,；m為柵格數(shù)量。RSRPi和SINRi分別表示柵格i處的接收電平值以及信噪比值。默認(rèn)，同一基站的三個小區(qū)覆蓋柵格之間并無干擾。

（6）計(jì)算種群中每一個個體的目標(biāo)函數(shù)值，并按照降序取最好的N個個體作為待優(yōu)化的種群。

（7）變異。

對于傳統(tǒng)的遺傳算法，將編碼后的染色體上的每一個基因進(jìn)行變異，并作為新的個體，但這種方式僅針對基因之間物理量參數(shù)相同的情況有效，對于個體是由多種不同量綱物理量參數(shù)實(shí)數(shù)編碼組成的情況效果一般。針對這種情況，本文提出了一種改進(jìn)方式，也即分步變異，具體如下：

1）對于每一個個體，將基站坐標(biāo)和小區(qū)方向角下傾角分成兩部分，或者分為三部分：基站坐標(biāo)、小區(qū)方向角、小區(qū)下傾角。如[(x1,y1,...,xn,yn),(α11,...,αn3,θ11,...,θn3)]或[(x1,y1,...,xn,yn),(α11,...,αn3),(θ11,...,θn3)]。

2）根據(jù)實(shí)際設(shè)置的迭代步數(shù)分為2k段或者3k段，k為整數(shù)。以2k段為例，假設(shè)迭代步數(shù)為100，那么可分為每20 步為一段，那么在這20 步內(nèi)，前10 步迭代保持小區(qū)朝向角度不變，僅對基站坐標(biāo)進(jìn)行變異；后10 步迭代保持基站坐標(biāo)不變，僅對小區(qū)角度進(jìn)行變異。同時每次變異完之后保證新個體并不在種群中。如此迭代5 輪，輸出結(jié)果。

3）對于坐標(biāo)變異采取如下方式：生成-10d:10d:d的21 個數(shù)，隨機(jī)選取兩個數(shù)作為基站橫縱坐標(biāo)的變異量，同理隨機(jī)生成-10:10:2 的11 個角度數(shù)，隨機(jī)選取2 個作為小區(qū)方位角和下傾角的變異量，此處使用了模擬退火算法局部搜索的思想。

4）將變異得到的新個體和原來的個體合并為一個大小為2N的種群，計(jì)算每一個個體的目標(biāo)函數(shù)值，并保留最好的N個作為下一步操作的對象。

（8）交叉。交叉過程同樣遵循分步交叉法，對于每一個個體先保持小區(qū)工參（如無特別說明，本文指代小區(qū)天線方向角和下傾角）不變，隨機(jī)選取個體的基因點(diǎn)位，然后在除自身外的種群中隨機(jī)選取一個個體，并完成相同基因點(diǎn)位的交換；小區(qū)工參的交叉規(guī)則同樣按此方式處理。

（9）當(dāng)達(dá)到預(yù)設(shè)的迭代步數(shù)還未完成覆蓋目標(biāo)，如弱覆蓋占比大于某一閾值，則自動增加1 個站，重新迭代計(jì)算；當(dāng)弱覆蓋占比小于某一閾值時，則停止站址和小區(qū)工參聯(lián)合規(guī)劃，然后進(jìn)行容量評估工作。

3 容量評估

當(dāng)站址規(guī)劃完成后，需要對小區(qū)容量進(jìn)行評估，以滿足區(qū)域內(nèi)終端用戶的容量需求，小區(qū)容量計(jì)算的具體步驟如下：

（1）根據(jù)廣播波束確定柵格的歸屬。對于每一個柵格，均需要計(jì)算出接收到每一個小區(qū)的RSRP 強(qiáng)度，然后選擇RSRP 值最大的那個小區(qū)作為這個柵格的歸屬小區(qū)，當(dāng)所有柵格均計(jì)算完畢后，即可得到每一個小區(qū)覆蓋區(qū)域。

（2）根據(jù)業(yè)務(wù)波束計(jì)算柵格處的RSRP 值以及柵格受到鄰區(qū)的干擾。對于每一個柵格均需要計(jì)算其接收到主服務(wù)小區(qū)的RSRP 值以及鄰區(qū)的RSRP 值，并分別計(jì)算上行干擾和下行干擾。對于下行干擾，按照如下方式計(jì)算第i個柵格處的SINR：

其中，Si表示柵格i處接收到的主服務(wù)小區(qū)的RSRP 值，表示柵格i處接收到的j鄰區(qū)的RSRP 值，N表示噪聲。對于上行干擾，按照如下方式計(jì)算第i個柵格處的SINR：

其中表示j小區(qū)覆蓋區(qū)域的幾何中心到i柵格主服務(wù)小區(qū)的干擾功率。

（3）得到每個小區(qū)上行和下行的覆蓋每一個柵格的SINR 值后，將其分別折算到MCS 等級表[16]中，得到流數(shù)v、調(diào)制階數(shù)Qm以及目標(biāo)碼率R，并進(jìn)一步計(jì)算得到小區(qū)每符號全帶寬傳輸數(shù)據(jù)量大?。篘cell_sbl=NPRB×12*η*R*Qm*v，其中NPRB是物理資源塊的數(shù)量，為定值。，表示考慮系統(tǒng)開銷的業(yè)務(wù)信道資源。

（4）根據(jù)典型業(yè)務(wù)平均需求速率，折算小區(qū)用戶每符號包的大小NUE_sbl，如表1 所示。

表1 業(yè)務(wù)類型數(shù)據(jù)表

表2 中，μ為速率均值，λ為間隔參數(shù)期望的倒數(shù)，均可從典型業(yè)務(wù)平均速率表中獲得。

表2 每符號包大小轉(zhuǎn)換表

（5）根據(jù)小區(qū)每符號包的大小和用戶在典型業(yè)務(wù)中的每符號包的大小，即可得到小區(qū)每符號包容納的用戶數(shù)：

（6）小區(qū)覆蓋區(qū)域內(nèi)，使用用戶密度乘以柵格個數(shù)估計(jì)小區(qū)覆蓋區(qū)域的用戶數(shù)，然后與計(jì)算得到的容量相比，即可確定小區(qū)容量是否滿足。如果不滿足，則加站重新進(jìn)行站址規(guī)劃，否則輸出站址規(guī)劃結(jié)果以及小區(qū)方向角和下傾角的參數(shù)配置。

4 仿真實(shí)驗(yàn)

4.1 仿真場景設(shè)計(jì)與參數(shù)配置

在本文方案驗(yàn)證過程中，設(shè)計(jì)了一個包含兩棟建筑的區(qū)域。如圖2 所示：

圖2 仿真場景

圖2 中，假設(shè)建筑物部分已經(jīng)完成室內(nèi)規(guī)劃，在本文中并不考慮室內(nèi)覆蓋，故建筑物僅做信號遮擋作用。圖2 中，覆蓋區(qū)域?yàn)榛窘ㄕ镜膮^(qū)域，優(yōu)化的任務(wù)是目標(biāo)函數(shù)V最大化。本文中，站址規(guī)劃階段，采用區(qū)域柵格化的方式完成；在容量評估階段，采用撒點(diǎn)的方式模擬終端，主要分為三部分用于小區(qū)容量評估，分別是軌跡用戶、固定用戶和隨機(jī)用戶。其中軌跡用戶的移動軌跡為隨機(jī)分配，且取軌跡中最差的30%樣本點(diǎn)參與容量評估；固定用戶是根據(jù)區(qū)域內(nèi)用戶終端位置分布統(tǒng)計(jì)得到的結(jié)果，在仿真中位置固定不變；隨機(jī)用戶是在覆蓋區(qū)域內(nèi)的非建筑物部分隨機(jī)撒點(diǎn)。在仿真過程中，固定用戶、隨機(jī)用戶和軌跡用戶總數(shù)設(shè)置為1 000 或2 000，按照統(tǒng)計(jì)分布完成用戶類型數(shù)的分配。仿真實(shí)驗(yàn)部分參數(shù)如表3 所示：

表3 算法模型仿真部分參數(shù)[17]

表3 中，頻率、帶寬、上下行時隙、SCS、小區(qū)天下發(fā)射功率、終端發(fā)射功率等均為固定參數(shù)值。RSRP 弱覆蓋門限用于衡量弱覆蓋比例，當(dāng)弱覆蓋占比小于1% 即可認(rèn)為覆蓋良好，并提前中斷站址規(guī)劃算法，進(jìn)行容量評估。

4.2 結(jié)果與分析

在容量評估階段，對于每個小區(qū)需要容納的用戶數(shù)可使用小區(qū)服務(wù)的柵格數(shù)與終端密度的乘積得到，在本文中分別對設(shè)置需要容納用戶數(shù)為1 000 和2 000 的情況進(jìn)行容量評估。首先對于用戶數(shù)為1 000 時，算法模型目標(biāo)函數(shù)V隨著迭代次數(shù)的仿真迭代結(jié)果如圖3 所示：

圖3 目標(biāo)函數(shù)值V隨著迭代次數(shù)的仿真變化圖

圖3 是GAEM 算法在站址和小區(qū)工參聯(lián)合尋優(yōu)達(dá)到滿足覆蓋（小于-110 dB 的柵格數(shù)比例小于1%）和容量的迭代結(jié)果圖，同時也給出了目前主流的元啟發(fā)式智能算法在任務(wù)中的表現(xiàn)。GA 圖像和GA_ 算法圖像均經(jīng)過了平滑處理。從圖3 可知，本文GAEM 方法可在短時間內(nèi)達(dá)到一個穩(wěn)定值，這主要?dú)w因于站址和小區(qū)工參分步變異、分布交叉的結(jié)果，這種方式相比于傳統(tǒng)的GA 方式，在解空間維度較大的情況下，降低了陷入局部極值點(diǎn)的風(fēng)險。其次，對于SA 算法，根據(jù)圖像趨勢，在迭代很長時間后，其結(jié)果有可能較GAEM 方法更優(yōu)，但很明顯產(chǎn)生了很大的時間消耗。TS 算法，由于其依賴于初始條件和鄰域映射關(guān)系，更容易限于局部最優(yōu)。對于PSO 而言，其本身更適合與連續(xù)型變量求解，對于離散的高維組合解，效果較差。在仿真過程中，當(dāng)目標(biāo)函數(shù)值V>0.85時，覆蓋與容量已經(jīng)滿足了要求，按照這一指標(biāo)，只有GAEM 方法和SA 算法能夠達(dá)到要求，然而SA 算法所需時間更長。而其他算法，只能通過加站操作完成。表4 中給出了主要迭代節(jié)點(diǎn)的目標(biāo)函數(shù)值對比表，仿真過程中，發(fā)現(xiàn)當(dāng)目標(biāo)函數(shù)V值達(dá)到0.85 時，覆蓋和容量已經(jīng)滿足要求。對于各算法模型，僅GAEM 方法和SA 算法能夠在迭代停止前完成最少基站的建站要求，而其他算法需要增加基站個數(shù)才能完成任務(wù)。對于本文所研究任務(wù)而言，從表5 中亦可明顯看出各算法的優(yōu)劣，取穩(wěn)定階段的目標(biāo)函數(shù)值作為衡量性能的依據(jù)，本文所提算法比SA 算法提升4.7%，比傳統(tǒng)的GA 算法性能提升9.8%。對于1 000用戶的容納需求，3 小區(qū)的最終優(yōu)化結(jié)果，基站容量計(jì)算值為1 146，可滿足。具體的基站站址、小區(qū)朝向和覆蓋效果如圖4 所示。

表4 不同算法在不同迭代次數(shù)時的目標(biāo)函數(shù)值比較

表5 設(shè)置1 000個用戶時站址和小區(qū)工參聯(lián)合規(guī)劃結(jié)果

圖4 設(shè)置1 000個用戶時的覆蓋圖

當(dāng)設(shè)置用戶數(shù)為2 000 時，使用本文給出的算法模型得到目標(biāo)函數(shù)V隨著迭代次數(shù)的仿真迭代結(jié)果如圖5 所示：

圖5 設(shè)置總用戶數(shù)為2 000時的仿真迭代圖

圖5 表示增加用戶數(shù)到2 000 時，算法迭代過程中不斷加站、優(yōu)化的過程圖。從圖5 中明顯能夠看到有三個不同的階段。首先，在第一個階段，此時基站數(shù)量只有一個，當(dāng)完成站址規(guī)劃時，容量評估并不滿足要求，所以進(jìn)行了加站操作。然后，加站完成后并達(dá)到穩(wěn)定時，可以看到V值有一個很明顯的降低，這是因?yàn)榇藭r干擾在增加，導(dǎo)致V值降低。最后，增加到3 個基站且穩(wěn)定時，可進(jìn)一步看到干擾在增大，總的V值在降低。最終結(jié)果顯示，由于干擾增大，2 個基站最終只能容納1 887 個用戶，所以只能增加基站數(shù)量滿足要求。圖6 為最終的基站站址和小區(qū)工參聯(lián)合優(yōu)化的區(qū)域覆蓋圖。

圖6 三個基站完成場景覆蓋時的效果圖

圖6 展示的是3 個基站覆蓋目標(biāo)區(qū)域的效果圖。在圖6 中，可以看到一個基站的三個扇區(qū)，部分出現(xiàn)了重疊，這并不是由于小區(qū)朝向一致造成的，而是渲染工具中，扇面設(shè)置較大導(dǎo)致的，具體的站址和小區(qū)工參規(guī)劃結(jié)果數(shù)據(jù)如表6 所示：

表6 設(shè)置2 000個用戶時站址與小區(qū)工參聯(lián)合規(guī)劃結(jié)果

5 結(jié)束語

本文提出了一種改進(jìn)型的遺傳算法用以解決大規(guī)模站址和小區(qū)工參的聯(lián)合優(yōu)化。該算法相對于傳統(tǒng)的遺傳算法變異和交叉階段，采用最大期望算法思想，使用分步變異、分步交叉迭代的方式，分別對不同物理量參數(shù)依照設(shè)置條件交替完成變異、交叉迭代。在算法中，使用了鄰域搜索，使得算法在尋優(yōu)過程中高效、穩(wěn)定。該方法對于不同物理量參數(shù)形成的高維組合解的求解非常有效，且能夠?qū)⑦@一方式擴(kuò)展到其他啟發(fā)式智能算法中。同時為了能夠在達(dá)到覆蓋最優(yōu)的同時，保證小區(qū)的容量能夠容納覆蓋范圍內(nèi)的用戶，給出了一種簡單的容量評估方式。仿真結(jié)果表明，在進(jìn)行高維度空間搜索時，本文所提采用最大期望思想的方法完成遺傳算法中的變異交叉過程，能夠快速收斂，并達(dá)到一個準(zhǔn)最優(yōu)值；SA 算法雖然也能夠達(dá)到要求，但是其收斂速度較慢，而其他啟發(fā)式算法在高維物理量不同的離散空間搜索任務(wù)中，結(jié)果較差。本文所提方案相對于傳統(tǒng)的GA 算法，目標(biāo)函數(shù)值提升9.8%，相對于使用站址規(guī)劃最多的SA 算法，目標(biāo)函數(shù)值提升4.7%，但收斂時間約為SA 的五分之一。該算法方案能夠在有效解決規(guī)模站址和小區(qū)工參聯(lián)合優(yōu)化問題的同時保證小區(qū)能夠接入覆蓋區(qū)域的所有用戶，提高用戶感知。