改進人工蜂群算法的無線傳感器網絡覆蓋優化

李華+盧靜

摘 要： 由于無線傳感器網絡覆蓋屬于組合優化范疇，為了在有限節點數量情況下提高其覆蓋率，引入人工蜂群算法并進行改進。通過注入全局最優個體反饋來提高收斂速度，并升級了偵查蜂更新方法，采用一維高斯變異的方法，充分利用粒子先驗知識，使粒子既能夠保證足夠的活力，又提高了算法的全局搜索能力。在40個節點數量條件下進行仿真實驗，提出的改進算法覆蓋率達到了87.2%，與改進蛙跳算法和標準人工蜂群算法的覆蓋率相比分別提高了1.6%和3.87%。

關鍵詞： 無線傳感器網絡； 人工蜂群； 全局最優； 一維高斯變異； 概率測量模型； 覆蓋優化

中圖分類號： TN711?34； TP393.04 文獻標識碼： A 文章編號： 1004?373X（2018）03?0014?05

Abstract： Since the wireless sensor networks coverage belongs to the combinatorial optimization category， the artificial bee colony algorithm is introduced and perfected to improve the coverage rate in the condition of limited node quantity. The global optimal individual feedback is injected to improve the convergence rate， and update the refresh method of investigation bee. The one?dimensional Gaussian mutation method and particle prior knowledge are used fully to make the particles active， and improve the global search capability of the algorithm. The algorithm with 40 nodes was carried out with simulation experiment. The experimental results show that the coverage rate of the improved algorithm can reach up to 87.2%， and is increased by 1.6% and 3.87% respectively than that of the improved shuffled frog leaping algorithm and standard artificial bee colony algorithm.

Keywords： wireless sensor network； artificial bee colony； global optimization； one?dimensional Gaussian mutation； probabilistic measurement model； coverage optimization

0 引 言

無線傳感器網絡[1]具有低功耗和方便組網的優勢，在物聯網、智能交通、目標定位和環境探測等領域得到了廣泛應用[2?3]。但隨著網絡中傳感器節點數量的不斷增加，節點冗余問題也越加突出，怎樣才能低成本投入且高效的利用成為研究熱門，增大網絡的覆蓋面積成為無線傳感器網絡應用的關鍵問題。

由于傳統算法[4?5]存在節點覆蓋程度低的問題，要想實現全局最優在技術層面還有欠缺，鑒于無線傳感網絡的結構與群體智能算法的特點極其相似，因此，大量的學者開始使用智能算法優化無線傳感器網絡。

文獻[6]將改進的粒子群算法應用到無線傳感網絡的自組織中，有效地提高了節點的覆蓋面積；文獻[7]根據節點位置信息建立部署模型，提出一種基于改進混合蛙跳算法；文獻[8]將遺傳算法應用于優化無線傳感器網絡覆蓋；文獻[9]將螢火蟲算法用于網絡覆蓋優化。但這些應用于無線傳感網絡覆蓋問題的群體智能算法由于本身存在一些缺點，導致其優化的結果不是很理想。

人工蜂群算法[10?11]具有良好的全局性，已經在很多領域內被證明優于其他一些算法。結合無線傳感器網絡的結構特點，把節點的部署看成是蜂群尋找最優蜜源的過程，將改進人工蜂群算法應用到無線傳感器網絡覆蓋優化中，與其他幾種算法的比較實驗說明，提出算法得到的效果有明顯改善。

1 人工蜂群算法及改進方法

1.1 人工蜂群算法描述

根據蜜蜂在活動中扮演的角色，將其歸納為觀察蜂、采蜜蜂以及偵查蜂三種類型。偵查蜂在正常情況下是不存在的，當采蜜蜂結束采蜜后自動轉化為偵查蜂[12?13]。其搜索步驟為：首先采蜜蜂選取周圍最近的一個蜜源，然后觀察蜂通過信息跟隨其中一只采蜜蜂，在這個過程中選取出較好的蜜源，最后采蜜蜂放棄蜜源，轉化為偵查蜂，隨機搜索新蜜源。

上述過程即為一個優化問題，將每個蜜源的位置看成一個解。假設蜜源位置表示為總數為其中，第個蜜源表示為為其收益度值。觀察蜂選取蜜源的概率表示如下[14]：

觀察蜂對周邊的蜜源進行權衡后，會選取較好的蜜源，蜜源位置更新公式為：

式中：為[0，1]之間的隨機數。如果，那么觀察蜂就會更新位置，否則不變。在更新的同時限定次數加1，當循環次數達到限定閾值時，會丟棄該蜜源，轉化為偵查蜂，生成位置公式為：

1.2 改進的人工蜂群算法

在蜂群算法中，當達到一定次數后適應值仍然沒有改進時，該蜜蜂會變成偵查蜂，然后隨機生成新的蜜源位置代替原位置。采用偵查蜂隨機搜索的目的是當算法處于收斂狀態，全部蜜蜂均匯聚在同一蜜源時，把蜜蜂強制轉移，以此保證蜜蜂的活力。但由于這種策略放棄了原來蜜源的所有信息，導致算法收斂速度較慢，為了讓蜜蜂既能夠保證足夠的活力，同時又可以充分地利用先驗知識，采用一維高斯變異的搜索策略，計算公式如下：endprint

人工蜂群算法采用概率選擇蜜源位置進行更新，所以具有全局搜索能力，從而使粒子具有很強的隨機性，即便是加入了收益度值的判定，并沒有明顯提高其收斂速度。所以又在更新公式中增加了最優蜜源位置這樣就使得其性能更加均衡，改進算法位置更新的表達式為：

改進人工蜂群算法的步驟如圖1所示。

2 網絡覆蓋優化的問題

無線傳感網絡覆蓋優化的問題可以描述為：在一個已知大小的空間內布置多個能夠感應與通信的節點，在保證節點之間連通性的同時，采取一定的措施來部署節點，且盡可能使用較少的節點達到網絡覆蓋范圍最大化。其中網絡覆蓋率是最重要的一個衡量標準。

常用的節點測量有二元測量法和概率測量法兩種模型[15]。由于前者具有本身的局限，容易導致測量的精度偏低，故這里通過概率測量模型研究無線傳感器網絡覆蓋率的問題。設測量范圍內有個節點，節點用表示，其中且每個節點的屬性和參數均相同，通信半徑為感應半徑為同時滿足

在二維空間中研究該問題，假設節點所處的位置為，測量范圍內任意點坐標為，所以相對的檢測概率可表示如下：

式中：是傳感節點測量的可靠性參數，且是到的歐氏距離；為傳感器節點屬性相關參數，且滿足與是輸入參數。

通過得到的能夠算出測量范圍內傳感器節點對點的聯合檢測概率，可表示如下：

式中表示測量范圍內的全部節點。在這里設定的檢測閾值為0.8，也就是說，當聯合檢測概率小于0.8時，就可以認為點不被檢測；反之，就認為點可以被檢測。

假設檢測區域為規則矩形，為了計算無線傳感器網絡覆蓋率，在檢測區域上劃分個面積相等的小矩形，然后把小矩形看作點利用式（8）算出所有點的檢測概率，同時計算出被檢測點的數量，兩者的乘積即為覆蓋面積，那么覆蓋率可以表示為：

3 實驗結果及分析

為了驗證改進人工蜂群算法在無線傳感器網絡覆蓋中的效果，使用Matlab軟件對其進行仿真實驗，并與標準粒子群算法、標準人工蜂群算法和文獻[7]中的改進蛙跳算法進行對比，進而說明本文提出算法的有效性。

3.1 相同節點數量對比實驗

在邊長50 m的正方形區域內，隨機部署40個節點，感應半徑5 m，通信半徑10 m，傳感節點測量的可靠性參數傳感器節點屬性相關參數。

參與比較算法的迭代次數極限為500，粒子數為50。其中，標準人工蜂群算法和改進人工蜂群算法參數設置一致，最大采蜜次數為50，改進蛙跳算法的迭代次數為5，粒子群算法參數且從0.5～0.2線性遞減。

為了驗證提出的改進算法的優越性，將標準粒子群算法（PSO）、改進蛙跳算法（GSFLA）和標準人工蜂群算法（ABCA）進行比較，得到的結果如表1所示。

從表1得到的結果可以看出，采用改進人工蜂群算法的無線傳感器網絡覆蓋率達到了87.2%，與改進蛙跳算法相比提高了1.6%，與標準人工蜂群算法相比提高了3.87%，網絡覆蓋率得到了明顯的改善。

為了從直觀上觀察覆蓋效果，將上述實驗結果輸出，分別得到40個初始節點、改進蛙跳算法、標準人工蜂群算法和改進人工蜂群算法的直觀覆蓋效果如圖2～圖6所示。

從上面幾種算法對應的覆蓋圖可以看出，利用智能算法對初始節點覆蓋進行優化后，大塊空白的現象消失，節點分布趨于均衡，改進人工蜂群算法的優化效果最佳。

3.2 不同節點數量對比實驗

為進一步驗證改進人工蜂群算法在無線傳感器網絡覆蓋中的效果，與標準人工蜂群與改進蛙跳算法在不同節點數量下的覆蓋率進行了對比實驗，配置參數不變，得到的結果如表2所示。

從表2可以看出，改進人工蜂群算法不管是在節點數量較多時，還是在節點數較少時均比其他幾種算法能更加有效地提高無線傳感器網絡覆蓋率。為方便對比在節點變化情況下算法覆蓋優化效果變化差異，將節點數量與覆蓋率的關系變化繪制成曲線圖，如圖7所示。

從節點數量與覆蓋率關系曲線圖中可以看出：隨著無線傳感器節點數量的增多，網絡覆蓋率均得到了明顯的提升。節點的利用率體現在曲線的斜率上，隨著無線傳感器節點數量的增多，均表現出減弱的趨勢，但是改進人工蜂群算法的下降速率要小于標準人工蜂群的下降速率，說明改進人工蜂群算法的全局搜索能力更強，在同等條件下具有更優的節點利用率，網絡覆蓋效果更好。

4 結 語

結合無線傳感器網絡的結構特點，引入改進人工蜂群算法，在更新策略中添加全局最優個體反饋，提升了算法的收斂速度，并借助一維高斯變異的更新方法，保證了粒子的活力，同時具有良好的全局搜索能力。在40個節點時進行了對比實驗，結果顯示，使用改進人工蜂群算法的網絡覆蓋率均優于其他幾種算法，比改進蛙跳算法提高了1.6%，比標準人工蜂群算法提高了3.87%，且能夠使節點分布更加均勻，在不同節點的實驗中，改進人工蜂群算法依然能夠保持較好的全局搜索能力和魯棒性，相比其他算法具有更優的節點利用率和覆蓋效果。

參考文獻

[1] 龍宇翔，趙英杰.基于WSN覆蓋問題及自愈算法的研究[J].現代電子技術，2016，39（1）：27?30.

LONG Yuxiang， ZHAO Yingjie. Study on coverage control problem for WSN and self?healing algorithm [J]. Modern electronics technique， 2016， 39（1）： 27?30.

[2] FERNANDO L， ANTONIO?JAVIER G， FELIPE G， et al. A comprehensive approach to WSN?based ITS applications： a survey [J]. Sensors， 2011（11）： 10220?10265.endprint

[3] 張敖木翰，張平，曹劍東.基于物聯網的公路交通運行狀態評估與預測[J].公路，2015，60（9）：178?183.

ZHANG Aomuhan， ZHANG Ping， CAO Jiandong. Estimate and prediction of traffic state on expressway under Internet of Things [J]. Highway， 2015， 60（9）： 178?183.

[4] CRISTINA A， PEDRO S， ANDR?S I， et al. Wireless sensor networks for oceanographic monitoring： a systematic review [J]. Sensors， 2010， 10（7）： 6948?6968.

[5] 戴寧，毛劍琳，付麗霞，等.基于虛擬勢場的有向傳感器網絡覆蓋優化算法[J].計算機應用研究，2014，31（3）：905?907.

DAI Ning， MAO Jianlin， FU Lixia， et al. Virtual potential field based coverage optimization algorithm for directional sensor networks [J]. Application research of computers， 2014， 31（3）： 905?907.

[6] 王巍，彭力.基于改進微粒群算法的移動傳感器網絡自組織[J].計算機工程與設計，2009，30（3）：654?659.

WANG Wei， PENG Li. Self?deployment of mobile sensor network based on improved particle swarm optimization [J]. Computer engineering and design， 2009， 30（3）： 654?659.

[7] 李響，鄭瑞娟.基于改進蛙跳算法的無線傳感器網絡覆蓋優化[J].計算機測量與控制，2014，22（6）：1993?1995.

LI Xiang， ZHENG Ruijuan. Wireless sensor network coverage optimization based on improved leapfrog algorithm [J]. Computer measurement & control， 2014， 22（6）： 1993?1995.

[8] 屈巍，汪晉寬，趙旭，等.基于遺傳算法的無線傳感器網絡覆蓋控制優化策略[J].系統工程與電子技術，2010，32（11）：2476?2479.

QU Wei， WANG Jinkuan， ZHAO Xu， et al. Optimal coverage stra?tegy based on genetic algorithm in wireless sensor networks [J]. Systems engineering and electronics， 2010， 32（11）： 2476?2479.

[9] 劉洲洲，王福豹，張克旺.基于改進螢火蟲優化算法的WSN覆蓋優化分析[J].傳感技術學報，2013，26（5）：675?682.

LIU Zhouzhou， WANG Fubao， ZHANG Kewang. Performance analysis of improved glowworm swarm optimization algorithm and the application in coverage optimization of WSNs [J]. Chinese journal of sensors and actuators， 2013， 26（5）： 675?682.

[10] 張鵬，劉弘，劉鵬.改進的蜂群算法及其在CBD選址規劃中的應用[J].計算機科學，2013，40（8）：210?213.

ZHANG Peng， LIU Hong， LIU Peng. Improved artificial bee colony algorithm and its application in CBD location planning [J]. Computer science， 2013， 40（8）： 210?213.

[11] 陳杰，沈艷霞，陸欣.基于信息反饋和改進適應度評價的人工蜂群算法[J].智能系統學報，2016，11（2）：172?179.

CHEN Jie， SHEN Yanxia， LU Xin. Artificial bee colony algorithm based on information feedback and an improved fitness value evaluation [J]. CAAI transactions on intelligent systems， 2016， 11（2）： 172?179.

[12] BARRON J L， FLEET D J， BEAUCHEMIN S S. Performance of optical flow techniques [C]// Proceedings of 1992 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 1992： 236?242.

[13] 張玲，王玲，吳桐.基于改進的粒子群算法優化反向傳播神經網絡的熱舒適度預測模型[J].計算機應用，2014，34（3）：775?779.

ZHANG Ling， WANG Ling， WU Tong. Thermal comfort prediction model based on improved particle swarm optimization?back propagation neural network [J]. Journal of computer applications， 2014， 34（3）： 775?779.

[14] 孫澤宇，伍衛國，王換招，等.概率模型下的一種優化覆蓋算法[J].軟件學報，2016，27（5）：1285?1300.

SUN Zeyu， WU Weiguo， WANG Huanzhao， et al. Optimized coverage algorithm in probability model [J]. Journal of software， 2016， 27（5）： 1285?1300.

[15] 孫偉，朱正禮，鄭磊，等.基于人工魚群和微粒群混合算法的WSN節點部署策略[J].計算機科學，2012，39（11）：83?85.

SUN Wei， ZHU Zhengli， ZHENG Lei， et al. Deployment strategy of wireless sensor network nodes based on AFSA?PSO hybrid algorithm [J]. Computer science， 2012， 39（11）： 83?85.endprint