張 軍， 邵曉倩， 侯向丹

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

0 引 言

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

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

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

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

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

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

1.2 跟隨蜂選擇策略

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

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

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

1.3 最差蜜源替換

(1)

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

1.4 IVABC的算法過程

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

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

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

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

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

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

2 實驗與結(jié)果分析

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

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

圖1 節(jié)點初始隨機部署

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

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

表1 10次覆蓋率仿真實驗結(jié)果 %

圖3 4種算法平均覆蓋率對比

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

3 結(jié)束語

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