混合無線傳感器網絡覆蓋優化算法*

張 軍， 邵曉倩， 侯向丹

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

0 引 言

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

本文利用Voronoi多邊形來確定固定節點的覆蓋盲區作為指引移動節點的移動參數。利用蜂群算法對移動節點進行分析，確定最佳移動節點及移動位置。應用反向學習策略加快算法的收斂速度的同時避免算法陷入局部最優。確定移動節點的最終位置，達到覆蓋率最優。

1 基于IVABC的覆蓋優化策略

針對傳統的蜂群算法中的輪盤賭方式會使種群多樣性被降低，從而引發收斂速度慢、易陷入局部最優解的缺點[6]，本文提出了將Voronoi多邊形和反向學習算法結合到人工蜂群算法里來解決覆蓋優化問題。

1.1 引領蜂的產生

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

1.2 跟隨蜂選擇策略

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

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

2)如果頂點VA,VB中的兩個點有一個落在節點s的覆蓋圓內，另一個落在覆蓋圓外，假設頂點VA落在覆蓋圓內，而頂點VB落在覆蓋圓外,必然出現覆蓋盲區。利用Voronoi多邊形將頂點VB做出標記，此時頂點VB為覆蓋盲區，頂點VA不進行標記。

1.3 最差蜜源替換

(1)

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

1.4 IVABC的算法過程

1)目標區域內隨機部署無線傳感器網絡的固定節點，對固定節點進行Voronoi劃分;根據無線傳感器固定節點的覆蓋圓到Voronoi頂點之間的相對位置找到覆蓋盲區,并計算初始覆蓋率。

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

4)計算網絡覆蓋率，同時應用貪婪算法尋找相對較好的解來更新當前移動節點位置。

5)有限次循環步驟(3)后，假如有移動節點位置不能提高網絡覆蓋率，則由對應的引領蜂轉變為偵查蜂進行搜索，應用反向學習策略產生新移動節點位置取代原來的節點位置。

6)對最大循環次數進行判斷，假如達到最大執行次數，循環停止；否則，根據網絡覆蓋率重新對蜂群進行搜索。

7)檢驗循環結束的條件是否得到滿足：若是，就輸出記錄最優的移動節點位置作為尋優結果，最終生成的無線傳感器網絡覆蓋圖。

2 實驗與結果分析

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

應用本文提出的IVABC算法的實驗仿真結果中節點隨機部署情況如圖1、圖2所示，圖2中深色區域表示移動節點覆蓋區域，淺色區域表示固定節點覆蓋區域。由結果可知，初始網絡覆蓋率為67.81 %。圖2算法優化后的，最終目標區域覆蓋率為97.13 %，從而使覆蓋率達到最大化。

圖1 節點初始隨機部署

圖2 優化完成后節點最終部署

表1為10次仿真實驗的覆蓋率數據統計表。從表1中可以看出應用本文提出的IVABC算法后，混合無線網覆蓋率每次均有很大的提升。圖3為4種算法的平均覆蓋率的尋優曲線。

表1 10次覆蓋率仿真實驗結果 %

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

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

3 結束語

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