基于混合遺傳優化算法基站的最優分布

鄧德鑫，葛寅辰，馮經緯，林若希，程乾開昱

（1.江南大學物聯網工程學院，無錫 214000；2.江南大學商學院，無錫 214000）

1 引言

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

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

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

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

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

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

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

2.1 基站分布規劃模型建立

2.1.1 基站分布規劃問題綜述

基站分布規劃問題實質上是一個多目標規劃的問題。多目標規劃就是多個優化目標在約束條件下同時得到最佳的解 。基于混合改進遺傳算法和DE算法對問題進行求解，解決了INSGA和傳統遺傳算法的缺點，并且使算法在分布性和收斂性有所提高，搜索能力也有所提升[5]。

2.1.2 基站規劃的理想假設

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

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

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

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

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

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

2.1.3 建立數學模型

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

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

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

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

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

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

2.2 算法實現

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

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

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

即初始化種群為

步驟2：對每一代內各體進行非支配排序。

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

交叉：為了增加干擾參數向量的多樣性，引入交叉操作。則試驗向量變為：

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

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

3 仿真結果與分析

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

表1 仿真的部分參數

經過進化200代仿真結果如圖2所示。

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

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

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

在相同的實驗仿真環境下，傳統的退火法得到的結果如圖3所示，經計算覆蓋率只有85%。

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

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

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

4 結束語

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