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

關(guān)鍵詞：基站選址；聚類；差分進(jìn)化；二進(jìn)制編碼

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

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

1 預(yù)備知識(shí)

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

1.1 差分進(jìn)化算法

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

1.2 峰值密度聚類算法

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

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

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

3 試驗(yàn)分析

3.1 試驗(yàn)環(huán)境設(shè)定

設(shè)定檢測區(qū)域?yàn)檫呴L20km的正方形，候選基站集合 S={s1，s2，…，s60}，P={p1，p2，…，p120}為測試點(diǎn)集合，基站和測試點(diǎn)的分布如圖1所示，其中星號(hào)表示測試點(diǎn)，模擬實(shí)際話務(wù)分布情況，圓形代表候選基站地址。

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

3.2 結(jié)果分析

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

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

4 結(jié) 論

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

參考文獻(xiàn)：

[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] 朱思峰，劉芳，柴爭義.基于免疫計(jì)算的WCDMA網(wǎng)絡(luò)基站選址優(yōu)化 [J].電子與信息學(xué)報(bào)，2011，33（6）：1492-1495.

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

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

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

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

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