混合無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法*

張 軍， 邵曉倩， 侯向丹

(1.河北工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院, 天津 300401；2.河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室，天津 300401)

0 引 言

混合無(wú)線網(wǎng)絡(luò)可以有效利用移動(dòng)節(jié)點(diǎn)的動(dòng)態(tài)部署彌補(bǔ)固定節(jié)點(diǎn)所形成的信號(hào)覆蓋盲區(qū)，從而與僅有固定節(jié)點(diǎn)組成的傳感器網(wǎng)絡(luò)[1]相比能更好地解決網(wǎng)絡(luò)資源浪費(fèi)、易出現(xiàn)覆蓋盲區(qū)等問(wèn)題。文獻(xiàn)[2]將遺傳算法引入混合無(wú)線傳感器網(wǎng)絡(luò)中。文獻(xiàn)[3]應(yīng)用改進(jìn)的蜂群算法對(duì)無(wú)線傳感器網(wǎng)絡(luò)進(jìn)行部署優(yōu)化，將傳感器感知節(jié)點(diǎn)部署問(wèn)題轉(zhuǎn)化為組合優(yōu)化問(wèn)題。但2種方法收斂效果不是很明顯。文獻(xiàn)[4]提出了將反向?qū)W習(xí)策略方法加入基本的人工蜂群(artificial bee colony,ABC)算法中，其改進(jìn)的ABC(improved ABC,IABC)算法收斂效果非常好，但網(wǎng)絡(luò)覆蓋效果不是很滿意。文獻(xiàn)[5]提出一種基于Voronoi多邊形和ABC算法相結(jié)合的新型混合優(yōu)化算法(Voronoi-ABC,VABC)，應(yīng)用VABC來(lái)部署節(jié)點(diǎn)，收斂速度很好，目標(biāo)區(qū)域覆蓋率效果明顯，但跟隨蜂產(chǎn)生新食物源的時(shí)，依賴本代的最壞食物源的可能性比較大，不利于獲得最優(yōu)的結(jié)果。

本文利用Voronoi多邊形來(lái)確定固定節(jié)點(diǎn)的覆蓋盲區(qū)作為指引移動(dòng)節(jié)點(diǎn)的移動(dòng)參數(shù)。利用蜂群算法對(duì)移動(dòng)節(jié)點(diǎn)進(jìn)行分析，確定最佳移動(dòng)節(jié)點(diǎn)及移動(dòng)位置。應(yīng)用反向?qū)W習(xí)策略加快算法的收斂速度的同時(shí)避免算法陷入局部最優(yōu)。確定移動(dòng)節(jié)點(diǎn)的最終位置，達(dá)到覆蓋率最優(yōu)。

1 基于IVABC的覆蓋優(yōu)化策略

針對(duì)傳統(tǒng)的蜂群算法中的輪盤賭方式會(huì)使種群多樣性被降低，從而引發(fā)收斂速度慢、易陷入局部最優(yōu)解的缺點(diǎn)[6]，本文提出了將Voronoi多邊形和反向?qū)W習(xí)算法結(jié)合到人工蜂群算法里來(lái)解決覆蓋優(yōu)化問(wèn)題。

1.1 引領(lǐng)蜂的產(chǎn)生

在ABC中，食物源的產(chǎn)生是隨機(jī)的，同時(shí)引領(lǐng)蜂的搜索過(guò)程也是隨機(jī)的。將Voronoi多邊形引入ABC算法中，應(yīng)用Voronoi多邊形頂點(diǎn)找出固定節(jié)點(diǎn)的覆蓋盲區(qū)位置,并且將覆蓋盲區(qū)作為產(chǎn)生新蜜源的移動(dòng)位置。與此同時(shí)，指導(dǎo)引領(lǐng)蜂的搜索位置，快速鎖定蜜源在整個(gè)目標(biāo)區(qū)域的大致位置，并且計(jì)算食物源的適應(yīng)度值。同時(shí)引領(lǐng)蜂更新食物源位置。

1.2 跟隨蜂選擇策略

通過(guò)Voronoi多邊形加入蜂群算法中，跟隨蜂通過(guò)距離評(píng)價(jià)覆蓋盲區(qū)的大小來(lái)選取引領(lǐng)蜂進(jìn)行跟隨。評(píng)價(jià)覆蓋盲區(qū)大小策略如下：

1)如果頂點(diǎn)VA,VB完全被節(jié)點(diǎn)s的覆蓋圓所覆蓋，則不存在覆蓋盲區(qū)；

2)如果頂點(diǎn)VA,VB中的兩個(gè)點(diǎn)有一個(gè)落在節(jié)點(diǎn)s的覆蓋圓內(nèi)，另一個(gè)落在覆蓋圓外，假設(shè)頂點(diǎn)VA落在覆蓋圓內(nèi)，而頂點(diǎn)VB落在覆蓋圓外,必然出現(xiàn)覆蓋盲區(qū)。利用Voronoi多邊形將頂點(diǎn)VB做出標(biāo)記，此時(shí)頂點(diǎn)VB為覆蓋盲區(qū)，頂點(diǎn)VA不進(jìn)行標(biāo)記。

1.3 最差蜜源替換

(1)

式中xijU為xi的第j個(gè)分量的上界，xijL為x的第j個(gè)分量的下界。本文更新最差食物源都采用式(1)得到新食物源，如果新食物源效果更好，則代替舊食物源。

1.4 IVABC的算法過(guò)程

1)目標(biāo)區(qū)域內(nèi)隨機(jī)部署無(wú)線傳感器網(wǎng)絡(luò)的固定節(jié)點(diǎn)，對(duì)固定節(jié)點(diǎn)進(jìn)行Voronoi劃分;根據(jù)無(wú)線傳感器固定節(jié)點(diǎn)的覆蓋圓到Voronoi頂點(diǎn)之間的相對(duì)位置找到覆蓋盲區(qū),并計(jì)算初始覆蓋率。

2)對(duì)蜜蜂種群規(guī)模、最大迭代次數(shù)等進(jìn)行初始化處理。

4)計(jì)算網(wǎng)絡(luò)覆蓋率，同時(shí)應(yīng)用貪婪算法尋找相對(duì)較好的解來(lái)更新當(dāng)前移動(dòng)節(jié)點(diǎn)位置。

5)有限次循環(huán)步驟(3)后，假如有移動(dòng)節(jié)點(diǎn)位置不能提高網(wǎng)絡(luò)覆蓋率，則由對(duì)應(yīng)的引領(lǐng)蜂轉(zhuǎn)變?yōu)閭刹榉溥M(jìn)行搜索，應(yīng)用反向?qū)W習(xí)策略產(chǎn)生新移動(dòng)節(jié)點(diǎn)位置取代原來(lái)的節(jié)點(diǎn)位置。

6)對(duì)最大循環(huán)次數(shù)進(jìn)行判斷，假如達(dá)到最大執(zhí)行次數(shù)，循環(huán)停止；否則，根據(jù)網(wǎng)絡(luò)覆蓋率重新對(duì)蜂群進(jìn)行搜索。

7)檢驗(yàn)循環(huán)結(jié)束的條件是否得到滿足：若是，就輸出記錄最優(yōu)的移動(dòng)節(jié)點(diǎn)位置作為尋優(yōu)結(jié)果，最終生成的無(wú)線傳感器網(wǎng)絡(luò)覆蓋圖。

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

使用MATLAB 2014軟件進(jìn)行仿真，仿真目標(biāo)區(qū)域?yàn)?00 m×100 m，混合無(wú)線傳感器總節(jié)點(diǎn)數(shù)為50個(gè)，其中固定節(jié)點(diǎn)30個(gè)，移動(dòng)節(jié)點(diǎn)20個(gè)，通信距離20 m，感知半徑10 m。在ABC和IVABC中，參數(shù)分別為：種群規(guī)模50，引領(lǐng)蜂數(shù)20，蜜源數(shù)20，最大迭代次數(shù)1 000次。實(shí)驗(yàn)中傳感器部署選定監(jiān)測(cè)區(qū)域?yàn)槎S網(wǎng)絡(luò)空間，所有傳感器節(jié)點(diǎn)處于同一平面內(nèi)，同構(gòu)，具有相同的傳感半徑R。傳感器節(jié)點(diǎn)感知模型為概率感知模型，每個(gè)傳感器節(jié)點(diǎn)覆蓋圓范圍為πR2。

應(yīng)用本文提出的IVABC算法的實(shí)驗(yàn)仿真結(jié)果中節(jié)點(diǎn)隨機(jī)部署情況如圖1、圖2所示，圖2中深色區(qū)域表示移動(dòng)節(jié)點(diǎn)覆蓋區(qū)域，淺色區(qū)域表示固定節(jié)點(diǎn)覆蓋區(qū)域。由結(jié)果可知，初始網(wǎng)絡(luò)覆蓋率為67.81 %。圖2算法優(yōu)化后的，最終目標(biāo)區(qū)域覆蓋率為97.13 %，從而使覆蓋率達(dá)到最大化。

圖1 節(jié)點(diǎn)初始隨機(jī)部署

圖2 優(yōu)化完成后節(jié)點(diǎn)最終部署

表1為10次仿真實(shí)驗(yàn)的覆蓋率數(shù)據(jù)統(tǒng)計(jì)表。從表1中可以看出應(yīng)用本文提出的IVABC算法后，混合無(wú)線網(wǎng)覆蓋率每次均有很大的提升。圖3為4種算法的平均覆蓋率的尋優(yōu)曲線。

表1 10次覆蓋率仿真實(shí)驗(yàn)結(jié)果 %

圖3 4種算法平均覆蓋率對(duì)比

可見本文提出的IVABC算法收斂速度快，且收斂效果好。由表1中仿真10次的網(wǎng)絡(luò)平均覆蓋率數(shù)據(jù)比較，看出IVABC算法覆蓋效果更好，平均最大覆蓋率最后達(dá)到96.39 %。IVABC在迭代95次后，達(dá)到最大覆蓋率的95 %，由此可見，收斂速度加快的同時(shí)，覆蓋效果明顯。

3 結(jié)束語(yǔ)

針對(duì)混合無(wú)線網(wǎng)覆蓋優(yōu)化問(wèn)題和無(wú)線傳感器節(jié)點(diǎn)的部署問(wèn)題，本文提出一種IVABC算法，并通過(guò)與ABC,IABC,VABC算法在混合無(wú)線網(wǎng)絡(luò)中的最終覆蓋率、平均覆蓋率和迭代次數(shù)等方面的對(duì)比，說(shuō)明了IVABC算法能較好避免基本ABC易陷入局部最優(yōu)解的同時(shí)減少了迭代次數(shù)。