基于混合遺傳優(yōu)化算法基站的最優(yōu)分布

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1.3 建立數(shù)學模型

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

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

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

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

2.1.4 多目標進化個體之間的支配關系

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

2.2 算法實現(xiàn)

混合改進遺傳算法的流程圖如圖1所示。

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

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

即初始化種群為

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

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

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

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

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

3 仿真結果與分析

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

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

經(jīng)過進化200代仿真結果如圖2所示。

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

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

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

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

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

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

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

4 結束語

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