基于改進(jìn)人工蜂群算法的WSNs覆蓋優(yōu)化

王 鑫， 譚華忠, 蔣 華

(桂林電子科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西 桂林 541004)

0 引 言

人工蜂群(artificial bee colony，ABC)算法是Karaboga D[1]在2005年提出的一種用于解決數(shù)值優(yōu)化問(wèn)題的新型群智能算法，算法是仿照蜜蜂的覓食行為而提出的，具有操作簡(jiǎn)單、參數(shù)少和隨機(jī)優(yōu)化性等優(yōu)點(diǎn)，相比于差分進(jìn)化算法和粒子群算法也具有更強(qiáng)的靈活性與適應(yīng)性[2]。作為一種新型多目標(biāo)優(yōu)化算法，ABC算法被應(yīng)用于調(diào)度問(wèn)題[3]、圖像分割[4]、運(yùn)動(dòng)目標(biāo)檢測(cè)[5]等多個(gè)領(lǐng)域中。

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)現(xiàn)在被廣泛應(yīng)用到健康檢測(cè)、生態(tài)環(huán)境監(jiān)測(cè)、軍事監(jiān)控等領(lǐng)域[6]。WSNs的覆蓋控制問(wèn)題,可以看作是在WSNs節(jié)點(diǎn)能量、無(wú)線(xiàn)網(wǎng)絡(luò)通信帶寬、網(wǎng)絡(luò)計(jì)算處理能力等資源普遍受限情況下,通過(guò)網(wǎng)絡(luò)傳感器節(jié)點(diǎn)放置和路由選擇等手段,最終使WSNs的各種資源得到優(yōu)化分配,進(jìn)而使感知、監(jiān)視、傳感、通信等各種服務(wù)質(zhì)量得到改善[7]。文獻(xiàn)[8]基于粒子群算法提出一種覆蓋優(yōu)化方法，在一定程度上提高了覆蓋率，但方法容易收斂到局部最優(yōu)解。文獻(xiàn)[9]提出了基于帶精英策略的非支配排序遺傳算法的節(jié)點(diǎn)部署方案，獲得了很好的網(wǎng)絡(luò)覆蓋率，但算法復(fù)雜度過(guò)大。隨著網(wǎng)絡(luò)的運(yùn)行，節(jié)點(diǎn)的能量會(huì)不斷下降，上述文獻(xiàn)并沒(méi)根據(jù)節(jié)點(diǎn)能量的變化而動(dòng)態(tài)地對(duì)網(wǎng)絡(luò)進(jìn)行覆蓋優(yōu)化。

本文針對(duì)基本ABC算法的不足，引入自適應(yīng)混沌優(yōu)化改進(jìn)算法，并把改進(jìn)ABC(IABC)算法應(yīng)用到WSNs的覆蓋優(yōu)化問(wèn)題中，從而實(shí)現(xiàn)傳感器節(jié)點(diǎn)的動(dòng)態(tài)最優(yōu)部署。仿真實(shí)驗(yàn)證明:該算法不僅克服了基本ABC算法收斂速度慢和“早熟”的缺點(diǎn)，提高了網(wǎng)絡(luò)覆蓋率，而且能有效地延長(zhǎng)網(wǎng)絡(luò)壽命，確保了良好網(wǎng)絡(luò)服務(wù)質(zhì)量。

1 ABC算法與改進(jìn)算法

1.1 基本ABC算法

在ABC算法中，待優(yōu)化問(wèn)題的可能解由食物源的位置Xi={xi1,xi2,…,xid}表示，相應(yīng)解的質(zhì)量與食物源的花蜜數(shù)量有關(guān)。ABC有3種類(lèi)型蜜蜂：偵查蜂、觀察蜂和雇傭蜂。

偵查蜂負(fù)責(zé)新食物源的隨機(jī)搜索，觀察蜂在舞蹈區(qū)等待選擇一個(gè)食物源，而雇傭蜂則與一個(gè)已知食物源位置相關(guān)。觀察蜂是根據(jù)與食物源相關(guān)的概率pi對(duì)食物源進(jìn)行選擇的，這個(gè)概率pi的計(jì)算如下

(1)

其中，SN為食物源數(shù)量，與雇傭蜂的數(shù)量相等。fiti為由式(2)給出的解的適應(yīng)度，可以看出它與目標(biāo)函數(shù)值fi呈反比

(2)

觀察蜂和雇傭蜂用式(3)從舊的食物源位置產(chǎn)生新候選位置，并把新位置和舊位置進(jìn)行比較保留較優(yōu)者

newij=xij+φij(xij-xkj).

(3)

其中，k∈{1,2,…，SN}為一個(gè)不等于i的隨機(jī)數(shù)，SN為解(種群)的總數(shù)，j∈{1,2,…,d}(d為維數(shù))，φij為[-1,1]間的隨機(jī)數(shù)，控制著xij鄰近食物源產(chǎn)生。

如果食物源位置在超過(guò)預(yù)先定義的次數(shù)還沒(méi)得到進(jìn)一步改進(jìn)，則放棄該食物源并且這個(gè)食物對(duì)應(yīng)的雇傭蜂成為偵查蜂。然后，由偵查蜂生成的新食物源代替原來(lái)的食物源，新食物源的計(jì)算如下

(4)

1.2 改進(jìn)算法

在基本ABC算法中，雇傭蜂和觀察蜂是進(jìn)行隨機(jī)性的位置更新，得到好食物源和不好食物源位置的可能性是一樣的，容易使算法出現(xiàn)收斂速度慢、早熟等問(wèn)題。為克服上述問(wèn)題，本文引入了文獻(xiàn)[10]中的自適應(yīng)混沌優(yōu)化算法，通過(guò)用改進(jìn)的Tent映射產(chǎn)生混沌變量，然后映射到優(yōu)化變量的取值空間，優(yōu)化變量的搜索空間通過(guò)混沌遍歷性得到細(xì)化，最后根據(jù)蜂群迭代狀態(tài)自適應(yīng)地調(diào)整搜索精度。改進(jìn)的Tent映射

ifxk=0,0.25,0.5,0.75 orxk=xk-m,

xk+1=T′(xk)=T(xk)+0.1rand(0,1);

else then

xk+1=T′(xk)=T(xk).

(5)

其中

根據(jù)式(5)生成混沌向量α(i,j)，則混沌優(yōu)化后的食物源位置為

(6)

(7)

式中c為當(dāng)前迭代次數(shù)，C為最大迭代次數(shù)。

從式(6)可以看出：混沌向量α(i,j)的遍歷性避免了算法“早熟”，自適應(yīng)因子μ隨著迭代的進(jìn)行而自適應(yīng)調(diào)整搜索范圍，克服了收斂過(guò)慢。

2 基于IABC算法的WSNs覆蓋優(yōu)化方法

2.1 相關(guān)假設(shè)

假設(shè)在待監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)部署n個(gè)節(jié)點(diǎn)，用si代表WSNs中的第i個(gè)節(jié)點(diǎn)，則傳感器節(jié)點(diǎn)集合為S={s1,s2,…,sn}。針對(duì)WSNs特性，對(duì)網(wǎng)絡(luò)作如下假設(shè)：

1)網(wǎng)絡(luò)中的各節(jié)點(diǎn)具有相同的感知半徑Rs和通信半徑Rc，且有Rc=2Rs;

2)各節(jié)點(diǎn)能夠獲取自身和其鄰居節(jié)點(diǎn)的位置信息;

3)移動(dòng)節(jié)點(diǎn)能量較充足，能夠支持移動(dòng)節(jié)點(diǎn)完成位置遷移過(guò)程。

2.2 感知模型

事實(shí)上，感知器節(jié)點(diǎn)是通過(guò)測(cè)量接收到的能量來(lái)得知目標(biāo)的出現(xiàn)，而這個(gè)能量會(huì)隨著目標(biāo)與傳感器節(jié)點(diǎn)的距離變化。不同于布爾感知模型，概率感知模型考慮了信號(hào)檢測(cè)過(guò)程的不確定性，同時(shí)假設(shè)相應(yīng)的感知概率函數(shù)值與距離呈反比?？梢?jiàn)，概率感知模型比布爾感知模型更適合應(yīng)用于實(shí)際中傳感器節(jié)點(diǎn)對(duì)目標(biāo)事件的推斷。本文采用文獻(xiàn)[11]中的概率感知模型，pi為傳感器節(jié)點(diǎn)si檢測(cè)到目標(biāo)事件j的概率

(8)

其中，re為對(duì)傳感器不確定性的一種估量，a=dij-(rs-re),k和m為目標(biāo)事件落入不確定區(qū)域時(shí)概率的衰變因子。容易看出，這個(gè)概率隨著傳感器節(jié)點(diǎn)與目標(biāo)位置之間距離的增加，而呈現(xiàn)出指數(shù)型的下降。

如文獻(xiàn)[12]所描述，目標(biāo)事件j能被傳感器網(wǎng)線(xiàn)檢測(cè)到是指目標(biāo)事件的聯(lián)合感知概率p(j)大于一定的閾值ε，這個(gè)閾值ε的大小視具體的應(yīng)用而定

(9)

在給定一個(gè)監(jiān)測(cè)區(qū)域R，包含了目標(biāo)事件集T={tj|j=1,2,…,m}和傳感器節(jié)點(diǎn)集S={si|i=1,2,…,n}，每個(gè)si都有一個(gè)相應(yīng)的權(quán)值wi，這個(gè)權(quán)值與節(jié)點(diǎn)剩余能量相關(guān)，WSNs覆蓋優(yōu)化問(wèn)題指的就是尋找能覆蓋區(qū)域R中T的具有最小權(quán)值和的S的子集C，即使式(10)的值最小化

(10)

所求得子集C滿(mǎn)足式(11)，aij和δ分別為關(guān)于pi(j)和ε的函數(shù)

(11)

其中

(12)

2.3 基于IABC的WSNs覆蓋優(yōu)化

在ABC算法中，群體中雇傭蜂或觀察蜂的數(shù)量等于待優(yōu)化問(wèn)題解(食物源)的數(shù)量。假設(shè)SN表示解的數(shù)量，每只蜜蜂的位置代表著一種傳感器節(jié)點(diǎn)的分機(jī)，即

xi=(xi1,yi1,xi2,yi2,…,xik,yik,…,xin,yin).

基于IABC算法的WSNs覆蓋優(yōu)化問(wèn)題就是求解使式(10)取得最小值的最佳位置xbest，其具體實(shí)現(xiàn)步驟為：

1)初始化蜂群，隨機(jī)生成SN個(gè)可行解fi;

2)根據(jù)式(10)計(jì)算解的適應(yīng)度f(wàn)iti;

3)對(duì)于每只雇傭蜂根據(jù)式(6)產(chǎn)生新的解newi，計(jì)算相應(yīng)的適度f(wàn)iti，應(yīng)用貪婪規(guī)則選擇舊解與新解之間較優(yōu)者;

4)根據(jù)式(1)計(jì)算每個(gè)解fi的選擇概率pi;

5)對(duì)于每只觀察蜂根據(jù)概率pi選擇解fi，并重復(fù)步驟(3)的操作;

6)超過(guò)閾值limit沒(méi)有改進(jìn)的蜜蜂變?yōu)閭刹榉洌允?4)隨機(jī)產(chǎn)生的新解替代原來(lái)的解；

7)記錄當(dāng)前最優(yōu)位置xbest，如果已經(jīng)達(dá)到最大循環(huán)次數(shù)，則輸出找到的最優(yōu)位置;否則,返回步驟(2)。

由于被激活傳感器節(jié)點(diǎn)的能量是不斷減少的，其權(quán)值也應(yīng)該是隨著動(dòng)態(tài)變化的，所以,算法中設(shè)置了一個(gè)當(dāng)前覆蓋子集的門(mén)限權(quán)值wth和一個(gè)限定時(shí)間tmax，當(dāng)前覆蓋子集的權(quán)值和超過(guò)門(mén)限權(quán)值wth，或運(yùn)行時(shí)間超過(guò)限定時(shí)間tmax，則重新運(yùn)行上述算法步驟選擇新的最優(yōu)覆蓋子集。

3 仿真實(shí)驗(yàn)

3.1 參數(shù)設(shè)置

假設(shè)WSNs的監(jiān)測(cè)區(qū)域?yàn)?0 m×40 m的方形區(qū)域，在區(qū)域內(nèi)隨機(jī)部署120個(gè)傳感器節(jié)點(diǎn)，設(shè)置WSNs概率感知模型參數(shù)，rs=1 m，re=0.5rs，k=0.5，m=0.5，ε=0.7。

3.2 實(shí)驗(yàn)結(jié)果與分析

如圖1所示，對(duì)比分析了IABC算法相對(duì)基本ABC算法性能的提升。網(wǎng)絡(luò)的初始覆蓋率為55.36 %，IABC算法經(jīng)過(guò)大約160次迭代循環(huán)后收斂到穩(wěn)定值88.23 %；而在基本ABC算法中，此時(shí)的網(wǎng)絡(luò)覆蓋率為78.66 %，并在220次循環(huán)之后才達(dá)到穩(wěn)定值81.52 %。這表明，IABC算法相對(duì)基本ABC算法提高收斂速度，增強(qiáng)了全局尋優(yōu)能力，有效地提高了網(wǎng)絡(luò)覆蓋率。

圖1 網(wǎng)絡(luò)覆蓋曲線(xiàn)

在相同時(shí)間內(nèi)激活的傳感器節(jié)點(diǎn)越少，網(wǎng)絡(luò)能量的消耗也越少，這樣整個(gè)網(wǎng)絡(luò)的生存時(shí)間就更長(zhǎng)。為了評(píng)價(jià)本文算法的有效性，圖2描述了文獻(xiàn)[12]中貪婪算法與IABC算法隨著時(shí)間變化而激活的傳感器節(jié)點(diǎn)數(shù)。可以看出，IABC算法隨著時(shí)間增加，激活的傳感器節(jié)點(diǎn)的數(shù)目并沒(méi)有出現(xiàn)過(guò)快地增加，因此，可以更加有效地延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。

圖2 激活傳感器節(jié)點(diǎn)數(shù)

4 結(jié) 論

本文針對(duì)基本ABC算法不足，提出了一種IABC算法，并用于WSNs的覆蓋優(yōu)化問(wèn)題中，并通過(guò)最優(yōu)覆蓋子集的動(dòng)態(tài)更新實(shí)現(xiàn)網(wǎng)絡(luò)生存時(shí)間最大化。由于IABC算法克服了原算法收斂速度慢、“早熟”等缺點(diǎn)，因此,更有利于得到全局最優(yōu)解。仿真實(shí)驗(yàn)結(jié)果表明:本文提出的IABC算法明顯提高了網(wǎng)絡(luò)覆蓋率，有效地延長(zhǎng)了網(wǎng)絡(luò)的壽命。

參考文獻(xiàn):

[1] Karaboga D,Ozturk C.A novel clustering approach: Artificial bee colony(ABC) algorithm[J].Applied Soft Computing,2011,11:652-657.

[2] Karabago D,Basturk B.A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm[J].Journal of Global Optimization,2007,39(3):459-471.

[3] 趙良輝,王天擎.蜂群算法解決集聚約束調(diào)度問(wèn)題[J].計(jì)算機(jī)工程與科學(xué),2011,33(11):84-88.

[4] 梁建慧,馬 苗.人工蜂群算法在圖像分割中的應(yīng)用研究[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(8):194-196,229.

[5] 陳 雷,張立毅,郭艷菊,等.基于人工蜂群算法的運(yùn)動(dòng)目標(biāo)檢測(cè)方法[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(21):178-181,221.

[6] Ammari H M,Das S K.Centralized and clustered k-coverage protocols for wireless sensor networks[J].IEEE Transactions on Computers,2012,61(1):118-133.

[7] 任 彥,張思東,張宏科.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法[J].軟件學(xué)報(bào),2006,17(3):422-433.

[8] 林祝亮,馮遠(yuǎn)靜.基于粒子群算法的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化策略[J].計(jì)算機(jī)仿真,2009,26(4):190-193.

[9] 李燕君,潘 建.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)智能部署方法研究[J].計(jì)算機(jī)科學(xué),2012,39(8):115-118,135.

[10] 王瑞琪,張承慧,李 珂.基于改進(jìn)混沌優(yōu)化的多目標(biāo)遺傳算法[J].控制與決策,2011,26(9):1391-1397.

[11] Zou Y,Chakraharty K.Sensor deployment and target localization in distributed sensor networks[J].ACM Transaction on Embe-dded Computing System,2004,3(1):61-91.

[12] Altinel I,Aras N,Gney E.Binary integer programming formulation and heuristics for differentiated coverage in heterogeneous sensor network[J].Computer Network,2008,52(12):2419-2431.