基于聚類的無線網(wǎng)絡基站選址優(yōu)化算法研究

摘 要：本文針對現(xiàn)有基站選址優(yōu)化方法存在的問題，提出一種基于聚類的無線網(wǎng)絡基站選址優(yōu)化算法。建立包括節(jié)點利用率和覆蓋率的優(yōu)化模型，引入聚類策略對初始解集合進行優(yōu)化，采用基于二進制編碼的差分進化算法求解優(yōu)化模型，得到最優(yōu)覆蓋方案。試驗結果表明，本文提出的方法能夠有效提升優(yōu)化效果，具有一定的實用性。

關鍵詞：基站選址；聚類；差分進化；二進制編碼

中圖分類號：TN929.5 文獻標識碼：A 文章編號：2096-4706（2018）09-0050-03

Abstract：This paper aims at the problems of the existing base station location optimization method，a clustering based optimization algorithm for the location of wireless network base stations is proposed. The optimization model is established，which includes the utilization rate and coverage rate of nodes. The clustering strategy is introduced to optimize the initial solution set. The optimal model is solved by using the differential evolution algorithm based on binary coding，and the optimal coverage scheme is obtained. The experimental results show that the method proposed in this paper can effectively enhance the optimization effect and is practical.

Keywords：base station location；clustering；differential evolution；binary coding

0 引 言

基站選址優(yōu)化是無線網(wǎng)絡規(guī)劃的一項重要內容，即在綜合考慮信號質量、建設代價、覆蓋約束以及其他網(wǎng)絡約束的條件下，規(guī)劃基站的數(shù)目和位置。隨著無線通信網(wǎng)絡的進一步發(fā)展，這一問題引起了學術界和工業(yè)界的廣泛重視。Zhang[1]等將全局優(yōu)化問題分解為多個子問題，以求解大范圍區(qū)域內的基站選址問題。朱思峰[2]等提出了基于免疫計算的選址優(yōu)化方案，并給出了對應的算法框架。張宏遠[3]等基于預測控制中的滾動優(yōu)化原理設計了基于滾動窗口的基站選址優(yōu)化方法。馬寶羅[4]等提出了一種基于矢量距離免疫計算的基站選址問題求解方案，結合了基于矢量距離的抗體濃度計算方法和反學習的種群初始化策略，具有較好的應用價值。另外，基站選址優(yōu)化多采用智能演化算法[5，6]，隨機生成初始解集。在實際場景中，通信業(yè)務量分布往往是不均勻的，例如住宅小區(qū)業(yè)務量往往較大，在基站建設的時候需要優(yōu)先考慮此類區(qū)域。采用隨機生成初始解集的方式往往會導致收斂緩慢，甚至陷入局部最優(yōu)。

為解決上述問題，本文提出一種基于聚類的無線網(wǎng)絡基站選址優(yōu)化算法。通過引入聚類策略對初始解集合進行優(yōu)化，并引入差分進化算法求解。試驗結果表明：該方法能夠以較小的建設代價滿足覆蓋要求，收斂速度較快，具有一定的應用價值。

1 預備知識

為了方便理解本文提出的算法，本節(jié)介紹以下基本概念和原理，分別是差分進化算法、峰值密度聚合和基站選址優(yōu)化模型。

1.1 差分進化算法

差分進化（Differential Evolution，DE）是一種基于群體演化的算法，通過種群內個體間的合作與競爭來實現(xiàn)對優(yōu)化問題的求解。算法的基本思想是對當前種群進行變異和交叉操作，產(chǎn)生另一個新種群，然后利用基于貪婪思想的選擇操作對這兩個種群進行一對一地選擇，產(chǎn)生最終種群。

1.2 峰值密度聚類算法

本文算法需要對測試點集合進行聚類運算，因此選取合適的聚類算法至關重要。目前廣泛運用的經(jīng)典聚類算法普遍存在參數(shù)敏感、計算量大、難以處理、不均勻分布數(shù)據(jù)集等問題。密度峰值聚類算法（Clustering by fast Search and Find of Density Peaks，CFSFDP），是一種基于密度的聚類方法，不需要預先確定聚類數(shù)目，參數(shù)變化魯棒性較好，適合本文中的場景。

1.3 基站選址優(yōu)化模型

完成種群初始化之后，進行變異、進化以及選擇操作，算法的終止條件為達到最大進化代數(shù)Gm。

3 試驗分析

3.1 試驗環(huán)境設定

設定檢測區(qū)域為邊長20km的正方形，候選基站集合 S={s1，s2，…，s60}，P={p1，p2，…，p120}為測試點集合，基站和測試點的分布如圖1所示，其中星號表示測試點，模擬實際話務分布情況，圓形代表候選基站地址。

算法參數(shù)設置如下：種群規(guī)模popSize=50，最大進化代數(shù)Gm=200，K=0.2，λ=0.05，采用二進制編碼，交叉概率CR為0.1，目標函數(shù)中的系數(shù)w1和w2分別為0.35，0.65。

3.2 結果分析

首先采用算法1對測試點集合進行聚類運算，得到聚類中心。分別采用DE算法和本文算法對該優(yōu)化模型進行求解，運行次數(shù)為30次，取平均值，優(yōu)化效果如圖1所示。

由圖1可以看出，針對本文提出的例子，DE算法大約在120代收斂，本文算法大約在80代收斂。采用聚類算法引入較優(yōu)解，因此本文算法收斂更快，能夠更快搜索到最優(yōu)解。綜合來看，本文提出的算法優(yōu)于DE算法，具有一定的實用價值。

4 結 論

基站選址優(yōu)化是無線網(wǎng)絡規(guī)劃的重點和難點之一，本文對無線網(wǎng)絡基站選址問題進行了分析，以覆蓋率和和節(jié)點利用率為指標建立了最優(yōu)化模型，并提出一種基于聚類策略的二進制編碼差分進化算法，求解最優(yōu)覆蓋方案。試驗結果表明，本文提出的方法能夠有效提升優(yōu)化效果，具有一定的實用性。

參考文獻：

[1] ZHANG H Y，XI Y G，GU H Y. A rolling window optimization method for large-scale WCDMA base stations planning problems [J].European Journal of Operational Research，2007，183（2）：370-383.

[2] 朱思峰，劉芳，柴爭義.基于免疫計算的WCDMA網(wǎng)絡基站選址優(yōu)化 [J].電子與信息學報，2011，33（6）：1492-1495.

[3] 張宏遠，席裕庚，谷寒雨.基于滾動窗口的WCDMA無線網(wǎng)絡規(guī)劃 [J].自動化學報，2007，33（4）：432-434.

[4] 馬寶羅，賈振紅，覃錫忠，等.改進免疫算法在無線網(wǎng)絡基站選址優(yōu)化中的應用 [J].傳感器與微系統(tǒng)，2016，35（5）：154-157+160.

[5] 沈海洋.基于遺傳PSO的無線傳感網(wǎng)絡覆蓋優(yōu)化算法研究 [J].微電子學與計算機，2013，30（3）：148-151.

[6] 朱思峰.基于免疫計算的無線通信網(wǎng)絡資源優(yōu)化 [D].西安：西安電子科技大學，2012.

作者簡介：黃驊（1983-），通迅作者，男，博士。研究方向：人工智能、自然語言處理；江俊（1983-），男，講師，博士。研究方向：人工智能、多數(shù)據(jù)融合。