基于Voronoi圖的蜂群優化算法在WSN覆蓋中的應用*

穆天圓，喬學工*，張 敏

（太原理工大學信息工程學院，太原030024）

基于Voronoi圖的蜂群優化算法在WSN覆蓋中的應用*

穆天圓1，喬學工1*，張 敏2

（太原理工大學信息工程學院，太原030024）

包含移動節點的混合網絡成為無線傳感器網絡發展的主流。為了優化混合無線傳感器網絡的部署質量，提高部署效率，提出一種基于Voronoi圖的蜂群優化算法來指導移動節點的部署。通過Voronoi多邊形迅速找到固定節點部署的覆蓋漏洞，指導引領蜂的生成，利于迅速定位全區域覆蓋漏洞；通過評價漏洞大小代替輪盤賭選擇方式來實現跟隨蜂的開采過程，利于局部優化。仿真結果表明，該算法簡便易實現，能夠迅速收斂，提高網絡覆蓋率，達到混合網絡的最優覆蓋效果。

無線傳感器網絡；網絡覆蓋優化；人工蜂群算法；Voronoi多邊形

無線傳感器網絡（WSN）綜合了網絡技術、信號處理技術、應用技術、現代網絡及無線通信技術，在國防、工業、交通等領域中得到了廣泛應用［1］。

構建無線傳感器網絡首先要考慮網絡節點的部署及網絡覆蓋問題。由具有感知、計算、通信功能的大量固定節點和少量移動節點組成的混合無線傳感器網絡可以通過移動節點的位置調整，實現目標區域的優質覆蓋，具有良好的環境適應能力，日益受到人們的關注［2］。因此，本文就隨機部署情況下混合無線傳感器網絡移動節點的優化部署問題進行了研究。文獻［3］使用改進的粒子群算法指導無線傳感器網絡的部署，在一定程度上提高了網絡覆蓋率，但算法容易陷入局部最優解。文獻［4］提出了帶精英策略的非支配排序遺傳算法的網絡覆蓋方案，獲得了較好的網絡覆蓋率，但算法復雜度過大。文獻［5-6］使用人工蜂群（artificial bee colony，ABC）算法指導網絡布局，但算法收斂速度慢，容易陷入局部最優。近年來，計算幾何學中的Voronoi圖（即泰森多邊形）在無線傳感器網絡的覆蓋控制問題上得到了很好的應用。Lee等［7］提出了基于泰森多邊形形心的部署策略（Centroid-Based scheme，CBS），一定程度上降低了算法復雜度，但網絡覆蓋效果不夠理想。Han等［8］提出改進的CBS算法，結合虛擬力知識，提出形心導向虛擬力的節點自部署算法，但在算法實現過程中需要進行多次試驗。

本文針對基本ABC算法的不足，引入Voronoi多邊形尋找覆蓋漏洞，用于改進蜂群算法，并把改進人工蜂群算法（Voronoi artificial bee colony，VABC）應用到WSN的覆蓋優化問題中，從而實現傳感器節點的動態優化部署。仿真實驗表明：該算法克服了基本ABC算法收斂速度慢和“早熟”的缺點，極大的提高了網絡覆蓋率，確保了良好的網絡服務質量。

1 相關問題描述

1.1 人工蜂群算法

人工蜂群算法是模擬蜜蜂采蜜行為的智能群算法，具有控制參數少，健壯性的優點［9］，可以解決連續、組合優化問題。在基本蜂群算法中，蜜源初始位置在搜索空間內隨機產生；引領蜂和偵察蜂進行隨機性的位置更新，對新蜜源的開采和探索具有很大的不確定性和偶然性；跟隨蜂采用輪盤賭的方法選擇引領蜂進行跟隨搜索，這些隨機性過程使算法很容易出現收斂速度慢、早熟等問題。

1.2 Voronoi多邊形

Voronoi多邊形是幾何學中的重要結構，在很多領域都得到了廣泛使用，它的一個重要應用是有效描述點與點之間的鄰近關系。本文利用Voronoi多邊形進行固定節點部署后的覆蓋漏洞的查找及其大小的評價，具有很強的適用性。文中用d（·）表示括號中任意兩點的歐氏距離，R表示節點覆蓋圓的半徑。

1.2.1 Voronoi多邊形

設直線L（A，B）={Q∈S|d（A，Q）=d（B，Q）}為線段AB的垂直平分線，則L（A，B）將平面S分成兩個半平面。半平面area（A，B）表示S中更加靠近A點的區域：

稱為點A關于B的支配區域。可得到S區域中以A點為中心的對應Voronoi多邊形區域：

式中：Q表示S區域中所有節點的集合。

1.2.2 區域覆蓋漏洞

在監測區域內，對比各傳感器節點到它對應的Voronoi多邊形的所有頂點的距離與本節點覆蓋圓半徑的大小，可以判斷是否有覆蓋漏洞的存在。Voronoi多邊形各頂點到傳感器的距離用d（A，v）表示，其中A表示傳感器節點，v表示任一Voronoi頂點，則

用R表示傳感器的感知半徑，如果d（A，v）＞R，則說明節點A所在的Voronoi多邊形區域出現覆蓋漏洞。

1.2.3 尋找漏洞實例

將隨機分布的節點劃分Voronoi多邊形后，根據Voronoi多邊形內部的點距離相應節點最近的原理，通過比較Voronoi多邊形的頂點與對應節點覆蓋區域的位置關系可以確定是否有覆蓋漏洞的存在。如果Voronoi多邊形的頂點未被覆蓋，則出現覆蓋漏洞，該頂點即被定義為覆蓋漏洞頂點。

圖1為隨機分布的40個傳感器節點對應的網絡覆蓋圖，其中“·”表示傳感器節點，“○”表示節點對應的覆蓋區域，“-”表示Voronoi多邊形的邊，“▲”表示覆蓋漏洞頂點。

圖1 Voronoi多邊形尋找覆蓋漏洞

1.3 區域覆蓋率

1.3.1 覆蓋模型

假設Si為區域S中任意一點，A為區域中的任意傳感器節點，Si與節點A的距離為d（A，Si）。在布爾模型中，節點A對目標點Si的檢測概率由下式（1）得到：

將區域S離散化為m×n個網格點，則區域S中有效覆蓋的網格點數count為

1.3.2 覆蓋率Cov

覆蓋率Cov是指目標監測區域中能夠被部署的傳感器節點所覆蓋的面積與監測區域總面積的比值，是評價無線傳感器網絡覆蓋質量的重要指標，是研究的熱點［10］。覆蓋率的好壞除與節點自身的感知能力有關外，節點的部署位置也很大程度上影響覆蓋率的大小。本文將區域S離散化為m×n個網格點，每個網格點是否被覆蓋用式（1）衡量，則覆蓋率Cov簡化為有效覆蓋的網格點數count與總點數m×n的比值，即

2 基于VABC的覆蓋優化策略

從蜂群算法的基本原理可知：算法中每個食物源對應一個移動節點的位置，搜索最優食物源即尋找移動節點最優部署位置的過程。移動節點的個數等于引領蜂的個數，同時也等于跟隨蜂的個數。

2.1 引領蜂的產生

傳統ABC算法中，隨機產生新的蜜源，引領蜂的搜索過程也是隨機行為。VABC算法則首先根據節點的隨機部署情況，生成固定節點相對應的Vor?onoi多邊形，利用Voronoi頂點找出固定節點的覆蓋漏洞，從覆蓋漏洞中選擇產生新蜜源，并指導引領蜂的搜索過程，迅速定位蜜源在整個目標區域的大概位置，計算蜜源的適應度值，根據貪婪算法選擇確定保留的蜜源，有利于全局尋優，迅速收斂。

2.2 跟隨蜂選擇策略的改進

在基本人工蜂群算法中，跟隨蜂采用輪盤賭的方法選擇引領蜂，具有很大的隨機性，容易陷入局部極值。而VABC算法通過評價覆蓋漏洞的大小來分配跟隨蜂。跟隨蜂在覆蓋漏洞頂點附近進行局部調整，并計算蜜源的適應度值，根據貪婪算法選擇確定保留的蜜源，有利于局部最優值的尋找。

目標區域經Voronoi劃分后覆蓋漏洞的評價策略如下：

如圖2為傳感器節點A生成的Voronoi多邊形，連接節點A和Voronoi多邊形的頂點，將多邊形分為以A點和一條Voronoi邊（以M和N為頂點）構成的不同的Voronoi三角形區域。根據節點A的覆蓋圓與Voronoi多邊形頂點的相對位置關系，可以計算評價覆蓋漏洞area（AMN）的大小［11］。

圖2 節點A生成的Voronoi多邊形

①當節點A的覆蓋圓將頂點M和N完全覆蓋在內，即距離比較公式d（A，M）≤R和d（A，N）≤R都成立時，則不存在覆蓋漏洞；

②頂點M，N中的一個落在節點A的覆蓋圓內，不妨設點M落在覆蓋圓內，即d（A，M）≤R，而d（A，N）＞R。顯然這種情況下△AMN不能被節點A的覆蓋圓完全覆蓋，必然出現覆蓋漏洞。過A點作邊MN的垂線，設垂足為P。利用余弦公式可求出∠AMN的值：

根據∠AMN是否為鈍角判斷垂足P是否落在線段MN內部，分兩種情況計算漏洞面積，如圖3所示。

圖3 覆蓋漏洞判斷

（a）垂足P落在線段MN內部，則∠AMN≤∏/2，如圖3（a）所示：

（b）垂足P落在線段MN外部，則∠AMN＞∏/2，如圖3（b）所示，△AMN內存在的覆蓋漏洞面積的計算與垂足落在線段MN內原理相同，只是各個小區域面積計算略有不同。可得三角形△AMN內存在的覆蓋漏洞面積為

area(AMN)=area(ΔAMN)-area(ΔAMQ)-area(QAW)

③頂點M，N都在節點A的覆蓋圓外，即距離比較公式d（A，M）＞R和d（A，N）＞R都成立，根據Vor?onoi三角形的形狀和相對節點覆蓋圓的位置分四種情況進行討論，其覆蓋漏洞面積計算原理與上文中有一個頂點落在覆蓋圓內相同，此處不再贅述。

2.3 最差蜜源的替換

在ABC算法迭代過程中，下一代引領蜂和跟隨蜂可能依據本代的最差蜜源產生新蜜源，但最差蜜源不利于獲得最優結果，這在一定程度上影響了算法的收斂速度。在VABC算法中，通過Voronoi多邊形產生的蜜源會出現面積很小的覆蓋漏洞，這類漏洞在WSN網絡的聯通范圍內是允許存在的，并不影響網絡的正常運行，如圖4中的A點所示。

圖4 最差蜜源實例

這類覆蓋漏洞即被視為最差蜜源。當搜索得到最差蜜源時，相應的引領蜂轉變為偵查蜂，放棄原有最差蜜源，重新搜索，產生新蜜源來繼續算法的循環執行。

2.4 算法執行

蜂群按照基于Voronoi圖的蜂群優化算法進行搜索，根據蜂群的適應度值大小進行貪婪選擇優化，重復上面的過程直到滿足終止條件。

算法的具體步驟描述如下：①隨機部署網絡節點，利用公式（3）計算網絡初始覆蓋率。根據固定節點部署情況生成對應的Voronoi多邊形，并找出覆蓋漏洞頂點；②初始化種群規模、引領蜂數量、最大輪數等參數；③隨機選取漏洞頂點作為移動節點初始位置，分配引領蜂，并進行全局搜索，根據公式（3）評價網絡覆蓋率，由貪婪法則選擇其中較好的解來更新移動節點位置，有利于迅速找到全局最優解；④對步驟（c）進行有限次循環后，若發現存在未提高網絡覆蓋率的移動節點位置，則相應的引領蜂轉變為偵查蜂進行搜索，產生新的移動節點位置取代原來的節點位置；⑤評價覆蓋漏洞大小，選取較大漏洞分配跟隨蜂，跟隨蜂進行細致的局部搜索，根據公式（3）評價網絡覆蓋率，由貪婪法則選擇其中較好的解來更新移動節點位置，利于局部最優解的尋找；⑥判斷是否達到最大循環次數，如果達到最大執行輪數，則停止循環，否則根據網絡覆蓋率對新的蜂群再一次進行搜索，即轉到步驟（c）繼續搜索；⑦記錄最優的移動節點位置作為尋優結果，生成最終的網絡覆蓋圖。

算法流程圖如下圖5。

圖5 算法流程圖

3 仿真實驗分析

假設無線傳感器網絡監測區域為100 m×100 m的正方形，在這個區域內隨機放置30個傳感器固定節點，20個傳感器移動節點，每個傳感器節點的感知距離為10 m，通信距離為20 m。ABC算法和VABC算法參數為：種群規模50，雇傭蜂數20，食物源數20，最大迭代次數1 000。

圖6（a）是節點隨機部署的情況，黃色表示固定節點，藍色表示移動節點，生成固定節點的Voronoi多邊形，尋找到固定節點部署漏洞，網絡初始覆蓋率為72.82%；圖6（b）是使用VABC算法優化后的節點位置，移動節點很好的填補了覆蓋漏洞，網絡覆蓋率達到95.42%，移動節點覆蓋均勻，達到了很好的覆蓋效果。

為了進一步驗證VABC覆蓋優化策略的性能，將本文算法與文獻［12］中提出的混沌人工蜂群算法CABC進行比較。圖7是使用ABC算法、CABC算法和VABC算法優化后區域的覆蓋率提升曲線對比圖，可以看出CABC算法能夠較快收斂，達到算法的最大覆蓋率，最終區域覆蓋率穩定在93.48%；ABC算法的最終區域覆蓋率可達到90.81%，但它的收斂速度慢，需要運行一段時間才能穩定；VABC覆蓋優化策略運行20輪后迅速提升網絡覆蓋率到90.12%，這是由于Voronoi多邊形漏洞頂點指導算法迅速定位全局漏洞，提高收斂速度；通過調整移動節點與覆蓋漏洞的相對位置，最終優化網絡覆蓋率達到95.42%，明顯優于CABC算法和基本ABC算法，提高了網絡覆蓋率，具有很好的覆蓋效果。

本文中定義覆蓋率達到本算法最大覆蓋率的97%所需執行的輪數來評價算法的收斂速度。表1通過不同算法的相關數據比較來直觀反映基本ABC算法、混沌人工蜂群算法和Voronoi人工蜂群算法的性能優劣。

圖7 不同算法收斂速度比較

表1 不同算法的數據比較

4 結束語

本文將幾何學中的Voronoi多邊形理論與蜂群算法相結合，提出VABC算法并應用于無線傳感器網絡的移動節點部署。通過仿真實驗對VABC算法進行分析，實驗結果表明：該算法結構簡單，能很好的避免基本ABC算法收斂速度慢，易陷入局部極值的缺點，具有很好的實用效果。

［1］李岳衡，王慧斌.無線傳感器網絡與監測應用［M］.北京：國防工業出版社，2011：7-11.

［2］徐凌偉，張浩，Gulliver T A，等.移動無線傳感器網絡系統在n-Rayleigh信道下的性能分析［J］.傳感技術學報，2015（2）：265-270.

［3］Penny J S，David J B，Steven B，et al.A Study to Evaluate a Low Cost Virtual Reality System for Home-Based Rehabilitation of the Up-Per Limb Following Stroke［J］.International Journal on Dis?ability and Human Development，2011，10（4）：337-341.

［4］Stone E E，Skubic M.Evaluation of an Inexpensive Depth Camera for Passive In-Home Fall Risk Assessment［C］∥2011 5th Interna?tional Conference on Pervasive Computing Technologies for Healthcare（Pervasive Health 2011），2011：71-77.

［5］胡珂.基于人工蜂群算法在無線傳感網絡覆蓋優化策略中的應用研究［D］.成都：電子科技大學，2012.

［6］0zturk C，Karaboga D，Gorkemli B.Probabilistic Dynamic Deploy?ment of Wireless Sensor Networks by Artificial Bee Colony Algo?rithm［J］.Sensors，2011，11（6）：6056-6065.

［7］Lee H J，Kim Y H，Han Y H，et al.2009 Proceedings of the IEEE 70th Vehicular Technology Conference Fall（VTC 2009-Fall）An?chorage，AK，September 20-23，2009 p1.

［8］Han Y H，Kim Y H，Kim W，et al.2011 Simulation 88 1152.

［9］Karaboga D，Bpasturk B.On the Performance of Artificial Bee Col?ony（ABC）Algorithm［J］.Applied S0ft Comuting，2008，8（1）：687-697.

［10］秦寧寧，陳家樂，丁志國.覆蓋率均衡區域覆蓋算法［J］.傳感技術學報，2015（4）：578-584.

［11］周則順.無線傳感器網絡覆蓋與連通優化算法的研究［D］.武漢：武漢理工大學，2013.

［12］文政穎，翟紅生.基于混沌人工蜂群算法的無線傳感器網絡覆蓋優化［J］.計算機測量與控制，2014，22（5）：1609-1612.

穆天圓（1990-），男，碩士研究生，主要研究方向為無線傳感器網絡節點部署及覆蓋，972130219@qq.com；

喬學工（1968-），女，副教授，碩士生導師，主要研究方向為無線傳感器網絡，qiaoxg1968@aliyun.com；

張 敏（1990-），男，碩士研究生，主要研究方向為無線傳感器網絡定位，1259104763@qq.com。

The Application of Bee Colony Optimization Algorithms Based on Voronoi in the Coverage of Wireless Sensor Networks*

MU Tianyuan1，QIAO Xuegong1*，ZHANG Min2
（College of Information Engineering，Taiyuan University of Technology，Taiyuan 030024，China）

The hybrid network which is composed of fix and mobile nodes has become the mainstream in the devel?opment of wireless sensor networks（WSNs）.In order to optimize the deployable quality of the mixed wireless sensor network，and improve the efficiency of deployment，a Bee Colony Algorithm optimized with Voronoi was proposed to guide the deployment of mobile nodes.The covering loopholes of the fixed nodes can be quickly found by the algo?rithm through the Voronoi polygons，which guide the development of the leading bees.It is conducive to quickly lo?cating all the covering loopholes in the target area.Instead of roulette algorithm method，evaluating the size of gap?ing holes by following bees’exploiting process is conductive to local optimization.The simulation results show that the algorithm is simple to implement，converges rapidly，improves the coverage ratio of the network and achieves the optimal coverage of the network.

wireless sensor networks（WSNs）；coverage optimization；artificial bee colony algorithm；Voronoi polygon

TP393

A

1004-1699（2015）10-1525-06

??6150P

10.3969/j.issn.1004-1699.2015.10.019

項目來源：國家自然科學基金項目（51279122）；山西省自然科學基金項目（2012011013-5）；山西省軟科學基金項目（2014041048-4）

2015-04-12 修改日期：2015-07-25