馬寶羅，賈振紅，覃錫忠，曹傳玲，牛洪梅

(1.新疆大學(xué) 信息科學(xué)與工程學(xué)院，新疆 烏魯木齊 830046；2.中國移動通信集團 新疆有限公司，新疆 烏魯木齊 830063)

改進免疫算法在無線網(wǎng)絡(luò)基站選址優(yōu)化中的應(yīng)用*

馬寶羅1，賈振紅1，覃錫忠1，曹傳玲2，牛洪梅2

(1.新疆大學(xué) 信息科學(xué)與工程學(xué)院，新疆 烏魯木齊 830046；2.中國移動通信集團 新疆有限公司，新疆 烏魯木齊 830063)

摘要:為了最小化網(wǎng)絡(luò)建設(shè)成本、提高用戶的服務(wù)質(zhì)量，提出了一種基于矢量距離免疫計算的基站選址問題求解方案。設(shè)計了基于矢量距離的抗體濃度計算方法，采用了反學(xué)習(xí)的種群初始化策略，給出了問題求解的數(shù)學(xué)模型。主要工作是準(zhǔn)確確定基站的位置和數(shù)目，以達到建站代價最小、且滿足用戶覆蓋率和系統(tǒng)容量的目的。仿真結(jié)果表明：所提算法有更突出的全局搜索能力和快速收斂性，能更好地實現(xiàn)用較低的建站成本滿足用戶覆蓋率和系統(tǒng)容量。

關(guān)鍵詞:無線網(wǎng)絡(luò)；基站選址優(yōu)化；免疫優(yōu)化算法；反學(xué)習(xí)

0引言

在網(wǎng)絡(luò)規(guī)劃過程中，基站選址優(yōu)化是一項靈活且至關(guān)重要的問題，被認(rèn)為是公認(rèn)的NP-難問題。對3G/4G網(wǎng)絡(luò)來說，容量和覆蓋需要同時來考慮，這就增加了問題的求解難度。如何選取合適的優(yōu)化算法求解基站選址優(yōu)化是國內(nèi)外學(xué)者廣泛關(guān)注的問題。文獻[1]研究了應(yīng)用多目標(biāo)進化算法求解4G基站規(guī)劃問題;文獻[2]給出了利用量子免疫進化求解了基站和中繼站聯(lián)合優(yōu)化問題；文獻[3，4]分析了基于免疫算法的基站選址問題。這些算法在求解過程中，沒有充分考慮各參數(shù)之間的相互影響，并且大多數(shù)算法不適用于將規(guī)劃區(qū)域按用戶密度分成許多子區(qū)域的情況,從而導(dǎo)致算法的性能差，求解速度慢等問題。

基站選址問題包括很多的優(yōu)化參數(shù)，被認(rèn)為是一個多目標(biāo)優(yōu)化問題[5]。本文主要考慮兩個重要的目標(biāo)函數(shù)：建設(shè)成本和覆蓋率。主要工作是從候選基站集合中選出基站的準(zhǔn)確位置和數(shù)目，在滿足用戶需求的前提下最小化成本。免疫算法在求解多目標(biāo)優(yōu)化問題方面有一定的優(yōu)勢，近年來在多領(lǐng)域得到了廣泛應(yīng)用[6～8]。為更好地解決此問題，本文給出了基于矢量距免疫計算的基站選址優(yōu)化方案。

1基站選址問題的系統(tǒng)模型

由于網(wǎng)絡(luò)用戶的迅速增長和頻譜資源的日益短缺，目前面臨的主要問題是網(wǎng)絡(luò)覆蓋差、信號不穩(wěn)定等問題。為解決此類問題，合理的基站建設(shè)顯得尤為重要，基站建設(shè)的合理與否直接影響著網(wǎng)絡(luò)的性能和后期的優(yōu)化、維護等工作。本文規(guī)定基站規(guī)劃區(qū)域的總面積為S，i,j分別為規(guī)劃區(qū)域S的長度和寬度，其表達式為

S={Xij,i=1,2,…,m;j=1,2,…,n}

(1)

為了驗證網(wǎng)絡(luò)的系統(tǒng)性能，本文主要考慮的兩個目標(biāo)函數(shù)描述如下：

第1個目標(biāo)函數(shù)是建設(shè)成本:本文采用文獻[3]中的表示方法，用基站的個數(shù)來表示成本，定義為

(2)

式中N為候選基站的總個數(shù)，N0為選中的基站數(shù)目。

第2個目標(biāo)函數(shù)為覆蓋率：基站的覆蓋范圍表示基站發(fā)射的信號在下行鏈路所能達到的的最大距離[9]。對服務(wù)測試點TPS，為了確保信號服務(wù)質(zhì)量能夠滿足用戶需求，要求測試點接收到的信號強度必須大于某個閾值Sq，本文用規(guī)劃區(qū)域內(nèi)被覆蓋的測試點個數(shù)與候選測試點個數(shù)的比值定義為網(wǎng)絡(luò)覆蓋率fcov，即

(3)

(4)

式中nTPS為測試點的個數(shù)。

2基于矢量距免疫算法的基站選址優(yōu)化

2.1抗體編碼

在基站選址規(guī)劃過程中，候選站址只存在被選擇或未被選擇兩種情況，因此，本文采用了最常見的二進制編碼，將每個候選基站表示為二進制變量ui∈{0,1}，即

(5)

2.2種群初始化

在免疫算法中，最常用的方法是采用隨機生成的方式產(chǎn)生初始解[10]。為了得到高質(zhì)量的初始種群、增加種群的多樣性，采用了基于混沌映射機制的反學(xué)習(xí)種群初始化方法[11]，該方法的步驟描述如下：

首先,隨機產(chǎn)生初始化變量x0，j∈ {0,1}且x0,j?{0.2,0.4,0.6,0.8}；利用混沌映射機制產(chǎn)生初始種群xij為

(6)

然后,利用反學(xué)習(xí)的方法產(chǎn)生初始種群xi,j相對應(yīng)的反向解oxi,j，如式(7)所示

(7)

2.3親和度計算

在種群的評估過程中，一項非常重要的工作就是在綜合考慮各種影響因素和已定義的所有目標(biāo)函數(shù)的情況下設(shè)計一個親和度函數(shù)[12]。本文中通過綜合評估建站成本和覆蓋率來反映親和度函數(shù)。親和度函數(shù)定義為

ffit=wcosfcos+wcovfcov

(8)

式中wcos和wcov分別為建站成本權(quán)重和覆蓋率權(quán)重。

2.4抗體濃度

為了增加種群多樣性、提高算法的收斂速度，本文采用了基于矢量距的抗體濃度計算方法[13]。根據(jù)現(xiàn)代免疫學(xué)原理，將抗原看作需要解決的問題、B細胞看作問題的其中一個解、抗體xi對應(yīng)于解的適應(yīng)度函數(shù)為ffit(xi)。定義抗體xi在種群集合N上的矢量距為

(9)

抗體的濃度定義為

(10)

則抗體xi基于抗體濃度和抗體矢量距的選擇概率[14]為

(11)

由式(11)可知，矢量距越大，說明種群N中與xi相似的抗體越少，則抗體xi有更多的機會被選擇；反之,亦然。

2.5相關(guān)算子設(shè)計

為了提高算法的收斂速度和性能，本文使用了克隆變異、種群更新2個算子。

1)克隆變異

首先，對記憶庫中的CL個抗體進行克隆增殖。采用文獻[7]提出的方法，將CL個抗體按親和度值由小到大排列，對其中的任意抗體Ai(t)(1≤Ai(t)≤CL),設(shè)其克隆規(guī)模為qi(t),如式(12)所示，則第t代產(chǎn)生的克隆副本的總個數(shù)Q如式(13)所示。然后按變異概率pm對副本種群進行變異

(12)

(13)

式中Int(x)為不小于x的最小整數(shù)；nt為根據(jù)克隆規(guī)模設(shè)定的參數(shù)，且滿足nt>CL；f(x)為抗體x的親和度。

2)種群更新

計算抗體的親和度值和濃度值，選出濃度較高的部分抗體，并將剩余的抗體重新初始化，構(gòu)成新的種群。

2.6改進算法流程

1)設(shè)定種群規(guī)模為Popsize，記憶庫種群規(guī)模為CM，克隆母體種群規(guī)模CL，迭代次數(shù)t。

2)利用混沌反學(xué)習(xí)法對種群進行初始化生成初始種群A0，并隨機取出CM個組成記憶庫種群W。

3)計算種群A0中抗體的親和度值，選出較優(yōu)的CL個組成克隆母體種群B0，對B0進行克隆增殖并按概率pm進行變異得到種群C0。

4)計算B0∪C0中抗體的親和度值，并用矢量距法計算其濃度值。

5)從B0∪C0中選出親和度值較優(yōu)的抗體去更換記憶庫中的原有抗體，更新記憶庫。

6)對種群B0∪C0進行更新，產(chǎn)生新的種群。

7)若滿足t>tmax，則輸出最優(yōu)解；否則,令t→t+1,轉(zhuǎn)步驟(3)繼續(xù)執(zhí)行。

3仿真結(jié)果

仿真環(huán)境：本文選取一個面積為S(20 km×20 km)的平坦區(qū)域進行實驗，如圖1所示。設(shè)定候選基站個數(shù)為N=60、候選測試點個數(shù)為nTPS=128；選取種群規(guī)模為100，最大進化代數(shù)為200代。記憶庫種群CM為30，克隆母體種群個數(shù)CL為60，權(quán)重系數(shù)α 取0.65。為了得到更好的仿真結(jié)果，本文首先討論了參數(shù)變化對算法性能的影響，然后談?wù)摫舅惴ㄅc其他算法的對比實驗。

圖1　候選基站與測試點分布圖Fig 1　Distribution of candidate stations and test point

3.1免疫算法參數(shù)調(diào)整

設(shè)定種群的初始化概率為0.6。這里首先討論了不同交叉概率(pc)和變異概率(pm)對算法性能的影響。

3.1.1交叉概率調(diào)整

為了驗證不同交叉概率對算法性能的影響，設(shè)定變異概率為0.6的。交叉概率分別取0.2，0.4，0.6和0.8。對算法運行20次，實驗結(jié)果分別如圖2～圖4所示。

當(dāng)交叉概率為0.8時，由圖2可知，平均親和度達到最優(yōu)值，且收斂速度最快。親和度值的優(yōu)劣直接反映著所得解的質(zhì)量好壞，親和度越大，說明求出的解質(zhì)量越高；由圖3可知，此時覆蓋率達到最大值，且明顯高于其他3種情況；由圖4可知，方案性價比達到最大值，其值隨進化代數(shù)的增加上升速度最快，且最先達到收斂狀態(tài)。

圖2　平均親和度隨代數(shù)的變化Fig 2　Average affinity change with algebra

圖3　覆蓋率隨代數(shù)的變化Fig 3　Coverage rate change with algebra

圖4　方案性價比隨代數(shù)的變化Fig 4　Cost performance of scheme change with algebra

3.1.2變異概率調(diào)整

為了驗證變異概率的調(diào)整對算法性能的影響，此時設(shè)定交叉概率為0.8，選取變異概率分別為0.2，0.4，0.6和0.8。對算法運行20次，實驗結(jié)果如圖5、圖6、圖7所示。

圖5　平均親和度隨代數(shù)的變化Fig 5　Average affinity change with algebra

圖7　方案性價比隨代數(shù)的變化Fig 7　Cost performance of scheme change with algebra

圖5顯示了不同變異概率對算法親和度的影響，當(dāng)變異概率為0.6時，算法的平均親和度值最高，且收斂速度最快。由圖6可知，變異概率為0.6時，算法的覆蓋率最高，且遠高于其他情況；圖7驗證了不同變異概率對方案性價比的影響，可以明顯看出,當(dāng)變異概率為0.6時，方案的性價比值最大，表明此時算法的性能最優(yōu)。

3.2對比實驗

根據(jù)上述討論，本文算法中選取交叉概率為0.8，變異概率為0.6。并與文獻[3]進行了對比實驗。文獻[3]中選取交叉概率和變異概率均為0.6。對兩種算法分別運行20次，取其平均值，對比結(jié)果如圖8、圖9、圖10所示。

圖8　平均親和度的比較Fig 8　Comparison of average affinity

圖9　方案性價比的比較Fig 9　Comparison of cost performance

圖10　覆蓋率的比較Fig 10　Comparison of coverage rate

由圖8可知，在進化過程中，所提算法平均親和度曲線上升速度較快，且其值始終高于文獻算法，這說明所提算法具有較好的收斂性能，且解的質(zhì)量明顯高于文獻算法。

方案的性價比是綜合評價建站成本與覆蓋率的重要指標(biāo)，定義為覆蓋率率與建站成本的比值。由圖9可知，在進化過程中，所提算法的性價比上升速度快于文獻算法，且其值一直高于文獻算法。這說明所提算法具有搜索能力強、收斂速度快的優(yōu)點，能用相對少的基站數(shù)量滿足網(wǎng)絡(luò)的覆蓋率。克隆變異算子的使用，根據(jù)抗體親和度值和濃度值自適應(yīng)地調(diào)整抗體的克隆規(guī)模，很好地保持了種群的多樣性，提高了解得質(zhì)量。

由圖10可知，所提算法的覆蓋率相比于文獻算法提高了4.54 %，且收斂代數(shù)明顯少于文獻算法，這是因為抗體克隆規(guī)模的自適應(yīng)調(diào)整，降低了算法的復(fù)雜性，提高了算法的性能。

4結(jié)束語

本文提出了一種基于矢量距的免疫算法求解基站選址優(yōu)化問題，首先討論了主要參數(shù)的變化對算法性能的影響，并與參考文獻進行了對比實驗。仿真結(jié)果顯示，所提算法的親和度值、覆蓋率、方案性價比等性能均得到了顯著的提高。另外，免疫算子的改進，增加了種群的多樣性，提高了算法的收斂性能。下一步將考慮與其它智能算法相結(jié)合，同時，將地形特征等更多參數(shù)考慮到基站選址優(yōu)化中，使其更貼近實際。

參考文獻:

[1]Mai Wentian,Liu Hailin,Chen Lei.Multi-objective evolutionary algorithm for 4G base station planning[C]∥2013 Ninth International Conference on Computational Intelligence &Security,2013:85-89.

[2]Ali H M,Oberoi J S,Liu Jiangchuan.Base station and relay station broadband network using immune quantum evolutionary algorithm[C]∥2013 IEEE 78th Vehicular Technology Conference,2013:1-6.

[3]張英杰,毛賜平.基于免疫算法的TD-SCDMA網(wǎng)絡(luò)基站選址優(yōu)化[J].通信學(xué)報,2014,35(5):45-48.

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

[5]Djalma de Melo,Carvalho Filho.Base station deployment based on artificial immune system[C]∥2008 ICCS,2008:1591-1596.

[6]石悅,邱雪松.基于免疫算法的電力通信網(wǎng)線路規(guī)劃方法[J].北京郵電大學(xué)學(xué)報,2014,37(2):14-17.

[7]夏巧橋,田茂,汪鼎文,等.基于免疫克隆算法的認(rèn)知無線電多信道聯(lián)合感知方法[J].電子與信息學(xué)報,2014,36(1):55-60.

[8]朱思峰,陳國強.多目標(biāo)優(yōu)化量子免疫算法求解基站選址問題[J].華中科技大學(xué)學(xué)報,2012，40(1):49-52.

[9]Wang Chenshu,Chen Yidung.Base station deployment with the capacity and coverage in WCDMA systems using genetic algorithm at different height[C]∥Sixth International Conference on Genetic and Evolutionary Computing,2012:546-549.

[10] 王獻榮，蘇小玲.無線傳感器網(wǎng)絡(luò)中基于免疫補體優(yōu)化的感知資源分配算法[J].傳感器與微系統(tǒng)，2014,33(1):141-143.

[11] Kuang Fangjun,Jin Zhong,Xu Weihong.A novel Chaotic artificial bee colony algorithm based on tent map[C]∥2014 IEEE Congress on Evolutionary Computation(CEC),2014:235-241.

[12] Munyaneza J,Kurien A.Optimization of antenna placement in 3G network using genetic algorithm[J].The 3th International Conference on Broadband Communications &Information Technology,2009,6(2):70-80.

[13] Lu Gang,Tan Dejian,Zhao Heming.Improvement on regulating definition of antibody density of immune algorithm[C]∥Procee-dings of the 9th International Conference on Neural Information Processing,2002:2669-2672.

[14] 葉洪濤，羅飛，許玉格,等.基于新型免疫算法的污水處理過程最優(yōu)控制[J].華南理工大學(xué)學(xué)報，2010，38(2):137-141.

Application of improved immune algorithm in wireless network base station location planning optimization*

MA Bao-luo1,JIA Zhen-hong1,QIN Xi-zhong1,CAO Chuan-ling2,NIU Hong-mei2

(1.School of Information Science and Engineering,Xinjiang University,Urumqi 830046,China;2.Subsidiary Company of China Mobile in Xinjiang,Urumqi 830063,China)

Abstract:In order to minimize network construction cost,improve quality of user’s service,a solution for base station location planning based on vector distance immune computation is proposed.The method for antibody concentration calculation based on vector distance is designed,a population initialization strategy based on opposition-based learning is adopted,mathematical model for problem solving is presented.The main task is to accurately determine locations and numbers of base stations,in order to reach the purpose of the minimum cost,and meet user coverage rate and system capacity.Simulation results shows that the proposed algorithm has outstanding global searching ability and fast convergence ability,can well meet user’s coverage rate needs and system capacity with low cost of station construction relatively.

Key words:wireless network;base station location planning optimization;immune optimization algorithm;opposition-based learning

DOI:10.13873/J.1000—9787(2016)05—0154—04

收稿日期：2015—08—24

*基金項目：中國移動通信集團新疆有限公司研究發(fā)展基金資助項目(XJM2013—2788)

中圖分類號:TP 393

文獻標(biāo)識碼:A

文章編號:1000—9787(2016)05—0154—04

作者簡介:

馬寶羅(1987-)，男，河南開封人，碩士研究生，研究方向為移動通信網(wǎng)絡(luò)規(guī)劃、無線通信。