鄧德鑫，葛寅辰，馮經(jīng)緯，林若希，程乾開(kāi)昱

（1.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，無(wú)錫 214000；2.江南大學(xué)商學(xué)院，無(wú)錫 214000）

1 引言

21世紀(jì)是一個(gè)信息技術(shù)快速發(fā)展的時(shí)代，第五代移動(dòng)通信（5G）也悄然進(jìn)入人們的視野。從第一代移動(dòng)通信的基站還是現(xiàn)如今的第五代移動(dòng)通信。移動(dòng)通信的基站雖然發(fā)生了巨大的變化，但在基站的不斷變化中，基站的合理分布始終是任意一個(gè)移動(dòng)通信時(shí)代不得不考慮的一個(gè)問(wèn)題。

基站是固定在一個(gè)地方的高功率多信道雙向無(wú)線電發(fā)送機(jī)，被廣泛地應(yīng)用于低功率信道雙向無(wú)線通信。隨著通信技術(shù)的迅速發(fā)展，為了取得更快的通信速度和更好的通信質(zhì)量，通信網(wǎng)絡(luò)需要在原有的基礎(chǔ)上不斷的延伸和擴(kuò)展，因此必須建設(shè)新的基站并且在原有基站上進(jìn)行改造?；镜姆植紱Q定著通信的速度、質(zhì)量以及建設(shè)的成本。合理的基站分布規(guī)劃可以有效地降低成本、提高服務(wù)質(zhì)量。

基站最優(yōu)分布問(wèn)題實(shí)質(zhì)上也是多目標(biāo)規(guī)劃問(wèn)題。目前國(guó)內(nèi)外研究人員提出了很多方法來(lái)解決多目標(biāo)規(guī)劃問(wèn)題。文獻(xiàn)[1]采用傳統(tǒng)的遺傳算法對(duì)天線進(jìn)行最優(yōu)分布求解。雖然具有全局尋找最優(yōu)的能力，但存在容易陷入局部最優(yōu)解的問(wèn)題。文獻(xiàn)[2]采用NSGA-II算法解決基站分布優(yōu)化問(wèn)題，降低了算法的復(fù)雜度，但在交叉、變異過(guò)程中同代之間容易產(chǎn)生相同個(gè)體，從而限制了算法的搜索能力導(dǎo)致算法尋找結(jié)果很容易是局部最優(yōu)解。

文獻(xiàn)[3]采用了蟻群算法求解多目標(biāo)規(guī)劃問(wèn)題，雖然蟻群算法具有較強(qiáng)的全局搜索能力但蟻群算法需要較長(zhǎng)的搜索時(shí)間易出現(xiàn)早熟停滯現(xiàn)象。文獻(xiàn)[4]采用改進(jìn)的NSGA算法求解多目標(biāo)規(guī)劃問(wèn)題，比原有的方法種群收斂性更好。差分進(jìn)化算法（簡(jiǎn)稱：DE算法）是一種以群體只能理論為基礎(chǔ)模擬生物進(jìn)化的優(yōu)化算法，簡(jiǎn)單且高效的將適應(yīng)環(huán)境的個(gè)體保存下來(lái)。差分進(jìn)化以其較強(qiáng)的收斂能力、魯棒性和強(qiáng)大的全局尋優(yōu)能力使得該算法得到廣泛的應(yīng)用。

由于基站的分布問(wèn)題較為復(fù)雜，容易陷入局部最優(yōu)解所以本文結(jié)合了INSGA-II算法和DE算法的優(yōu)點(diǎn)，使將兩者的混合算法對(duì)基站最優(yōu)分布進(jìn)行求解，從而更有效的搜索最優(yōu)解。

2 基于混合遺傳算法的基站分布規(guī)劃建模

在保證一塊區(qū)域內(nèi)可建基站的位置不變的情況下，怎樣選擇基站的坐落位置，從而使覆蓋率最大，成本最低是一個(gè)多目標(biāo)規(guī)劃的問(wèn)題。本文注重分析解決GPS基站分布規(guī)劃問(wèn)題。

2.1 基站分布規(guī)劃模型建立

2.1.1 基站分布規(guī)劃問(wèn)題綜述

基站分布規(guī)劃問(wèn)題實(shí)質(zhì)上是一個(gè)多目標(biāo)規(guī)劃的問(wèn)題。多目標(biāo)規(guī)劃就是多個(gè)優(yōu)化目標(biāo)在約束條件下同時(shí)得到最佳的解 ?；诨旌细倪M(jìn)遺傳算法和DE算法對(duì)問(wèn)題進(jìn)行求解，解決了INSGA和傳統(tǒng)遺傳算法的缺點(diǎn)，并且使算法在分布性和收斂性有所提高，搜索能力也有所提升[5]。

2.1.2 基站規(guī)劃的理想假設(shè)

對(duì)于GPS基站的分布優(yōu)化問(wèn)題，為了方便分析問(wèn)題的本質(zhì)，注重主要因素，忽略次要因素作如下假設(shè)：

（1）基站發(fā)生的是以電磁波的方式向外輻射，電磁波主要以直射波的方式進(jìn)行傳播，在這里不考慮電磁波受到空氣中的塵埃等物質(zhì)影響下的反射和散射。電磁波在自由空間的傳播損耗符合式（1）：

經(jīng)過(guò)計(jì)算5G基站的覆蓋半徑大約100-300米左右，假設(shè)每一個(gè)5G基站的輻射范圍是相等的為了方便計(jì)算均取值為200米。在一個(gè)基站輻射范圍內(nèi)的各點(diǎn)接受到該GPS基站信號(hào)強(qiáng)度是相同的?；疽?guī)劃的區(qū)域假設(shè)為一個(gè)二維平面。在這個(gè)二維平面上隨機(jī)設(shè)置基站的初始位置。在該區(qū)域內(nèi)設(shè)置N個(gè)基站。設(shè)區(qū)域內(nèi)的任意點(diǎn)為基站的坐標(biāo)集合為則兩點(diǎn)之間的距離為用的取值來(lái)表示B點(diǎn)是否被第i個(gè)基站所覆蓋。如果點(diǎn)被覆蓋則為1，如果點(diǎn)未覆蓋則取值為0。即公式（2）：

只要點(diǎn)在任意一個(gè)基站半徑范圍內(nèi)，則認(rèn)為這點(diǎn)被覆蓋，這些點(diǎn)的集合為P，則未被基站覆蓋的點(diǎn)為則P點(diǎn)的構(gòu)成的面積為Q。假設(shè)這塊區(qū)域總的面積為S，則覆蓋率為式（3）所示：

（2）在發(fā)射機(jī)和接受機(jī)之間因障礙物的復(fù)雜的地形，會(huì)產(chǎn)生多路徑效應(yīng)，不同的地形之間多路徑效應(yīng)的不同。位于地勢(shì)較為平坦開(kāi)闊的接收機(jī)多路徑效應(yīng)較小。又因?yàn)椴煌瑓^(qū)域基站周?chē)沫h(huán)境不同，信號(hào)的噪聲功率也不一樣等。這些不確定因素影響著基站的性能。現(xiàn)將基站的性能進(jìn)行性能假設(shè)，隨機(jī)產(chǎn)生50-100之間的隨機(jī)數(shù)來(lái)表示基站的性能。

（3）基站是一個(gè)物理設(shè)備，隨著時(shí)間的推移，部分產(chǎn)品會(huì)產(chǎn)生老化損壞的現(xiàn)象。在較為惡劣的環(huán)境下，設(shè)備的更換周期較良好環(huán)境下短。經(jīng)調(diào)研發(fā)現(xiàn)基站的建設(shè)資金相差不是懸殊。為了方便計(jì)算，將基站現(xiàn)實(shí)成本歸化到5到15的數(shù)值。最后隨機(jī)產(chǎn)生N個(gè)數(shù)值表示基站的成本。每一個(gè)點(diǎn)的成本記為

2.1.3 建立數(shù)學(xué)模型

混合遺傳算法優(yōu)化目標(biāo)包括最小成本，最大覆蓋率，SL表示表示基站的部署方案。

優(yōu)化目標(biāo)1：最小化基站建設(shè)維修的成本如式（4）所示：

優(yōu)化目標(biāo)2：最大化基站的覆蓋率如式（5）所示：

最終找出可實(shí)行的方案如式（6）所示：

2.1.4 多目標(biāo)進(jìn)化個(gè)體之間的支配關(guān)系

設(shè)p和q是進(jìn)化群體中的任意兩個(gè)不同的個(gè)體，若滿足對(duì)所有子目標(biāo)函數(shù)，p不比q差，即且至少存在一個(gè)子目標(biāo)函數(shù)，是的p比q好。即，使得其中m為子目標(biāo)的個(gè)數(shù)。則稱p為非支配的，q為被支配的。

2.2 算法實(shí)現(xiàn)

混合改進(jìn)遺傳算法的流程圖如圖1所示。

圖1 混合INSGA-II和DE算法流程圖流程圖

步驟1：群體初始化：群體每個(gè)個(gè)體是在初始范圍內(nèi)的隨機(jī)二進(jìn)制數(shù)組合，使種群在演化時(shí)有充分的搜索范圍。利用編碼映射，建立種群。初始種群有M個(gè)體組成，每個(gè)個(gè)體的染色體由N個(gè)基因片段構(gòu)成。

即初始化種群為

步驟2：對(duì)每一代內(nèi)各體進(jìn)行非支配排序。

步驟3：利用DE算法的交叉變異和復(fù)制。

交叉：為了增加干擾參數(shù)向量的多樣性，引入交叉操作。則試驗(yàn)向量變?yōu)椋?/p>

選擇：為決定試驗(yàn)向量是否會(huì)成為下一代中的成員，DE按照貪婪準(zhǔn)則將試驗(yàn)向量與當(dāng)前種群中的目標(biāo)向量進(jìn)行比較。如果目標(biāo)函數(shù)要被最小化，那么具有較小目標(biāo)函數(shù)值的向量將在下一代種群中占有優(yōu)勢(shì)，下一代中的所有個(gè)體都比當(dāng)前種群的對(duì)應(yīng)個(gè)體更佳或者至少一樣好。

步驟4：去除重復(fù)的種群個(gè)體，然后重組種群，再進(jìn)行步驟3直到種群滿足條件，退出循環(huán)，該種群就是最優(yōu)解。

3 仿真結(jié)果與分析

為了驗(yàn)證算法的解決問(wèn)題的能力，本文對(duì)于1000m×1000m的目標(biāo)區(qū)域進(jìn)行規(guī)劃，為了簡(jiǎn)化分析，假設(shè)目標(biāo)區(qū)域內(nèi)平坦，采用全向天線覆蓋面積為圓形，經(jīng)過(guò)計(jì)算基站的覆蓋區(qū)域?yàn)榘霃?00米的圓形區(qū)域。參數(shù)如表1所示。

表1 仿真的部分參數(shù)

經(jīng)過(guò)進(jìn)化200代仿真結(jié)果如圖2所示。

圖2 混合遺傳算法得到的基站分布

通過(guò)圖1我們可以看出基于DE和NSGA算法求得基站位置分布合理，通過(guò)計(jì)算覆蓋率高達(dá)93%。

圖3 退火法得到的基站分布

在相同的實(shí)驗(yàn)仿真環(huán)境下，傳統(tǒng)的退火法得到的結(jié)果如圖3所示，經(jīng)計(jì)算覆蓋率只有85%。

為了驗(yàn)證混合遺傳算法的處理基站分布問(wèn)題的能力，在覆蓋率和成本兩個(gè)方面將它與傳統(tǒng)的模擬退火法進(jìn)行對(duì)比。

表2 不同迭代次數(shù)下兩種算法基站成本及覆蓋率

通過(guò)仿真結(jié)果對(duì)比可以看出，混合遺傳算法在成本和覆蓋率兩個(gè)方面性能都優(yōu)于傳統(tǒng)退火算法。因此該方法具有很好的解決效果。

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

為了能保證更好的通信質(zhì)量，本文采用一種基于混合DE和NSGA算法的基站規(guī)劃優(yōu)化的方法。該方法在基站分布規(guī)劃中同時(shí)考慮了信號(hào)衰減，成本和覆蓋率三個(gè)因素，設(shè)計(jì)了具體的實(shí)現(xiàn)流程，進(jìn)行了仿真實(shí)驗(yàn)并與傳統(tǒng)的模擬退火法進(jìn)行了比較。仿真結(jié)果展示了基于混合DE和NSGA算法的方法的有效性?；旌线z傳算法能有找到最優(yōu)的5G基站的分布方案。并且具有全局尋優(yōu)的優(yōu)勢(shì)。合理的基站分布使得通信質(zhì)量得到顯著提高。因此基于混合DE和NSGA算法的基站規(guī)劃的方法具有十分重要的實(shí)用價(jià)值和進(jìn)一步的研究意義。