基于Voronoi圖的蜂群優(yōu)化算法在WSN覆蓋中的應(yīng)用*

穆天圓，喬學(xué)工*，張 敏

（太原理工大學(xué)信息工程學(xué)院，太原030024）

基于Voronoi圖的蜂群優(yōu)化算法在WSN覆蓋中的應(yīng)用*

穆天圓1，喬學(xué)工1*，張 敏2

（太原理工大學(xué)信息工程學(xué)院，太原030024）

包含移動(dòng)節(jié)點(diǎn)的混合網(wǎng)絡(luò)成為無(wú)線傳感器網(wǎng)絡(luò)發(fā)展的主流。為了優(yōu)化混合無(wú)線傳感器網(wǎng)絡(luò)的部署質(zhì)量，提高部署效率，提出一種基于Voronoi圖的蜂群優(yōu)化算法來(lái)指導(dǎo)移動(dòng)節(jié)點(diǎn)的部署。通過(guò)Voronoi多邊形迅速找到固定節(jié)點(diǎn)部署的覆蓋漏洞，指導(dǎo)引領(lǐng)蜂的生成，利于迅速定位全區(qū)域覆蓋漏洞；通過(guò)評(píng)價(jià)漏洞大小代替輪盤賭選擇方式來(lái)實(shí)現(xiàn)跟隨蜂的開(kāi)采過(guò)程，利于局部?jī)?yōu)化。仿真結(jié)果表明，該算法簡(jiǎn)便易實(shí)現(xiàn)，能夠迅速收斂，提高網(wǎng)絡(luò)覆蓋率，達(dá)到混合網(wǎng)絡(luò)的最優(yōu)覆蓋效果。

無(wú)線傳感器網(wǎng)絡(luò)；網(wǎng)絡(luò)覆蓋優(yōu)化；人工蜂群算法；Voronoi多邊形

無(wú)線傳感器網(wǎng)絡(luò)（WSN）綜合了網(wǎng)絡(luò)技術(shù)、信號(hào)處理技術(shù)、應(yīng)用技術(shù)、現(xiàn)代網(wǎng)絡(luò)及無(wú)線通信技術(shù)，在國(guó)防、工業(yè)、交通等領(lǐng)域中得到了廣泛應(yīng)用［1］。

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

本文針對(duì)基本ABC算法的不足，引入Voronoi多邊形尋找覆蓋漏洞，用于改進(jìn)蜂群算法，并把改進(jìn)人工蜂群算法（Voronoi artificial bee colony，VABC）應(yīng)用到WSN的覆蓋優(yōu)化問(wèn)題中，從而實(shí)現(xiàn)傳感器節(jié)點(diǎn)的動(dòng)態(tài)優(yōu)化部署。仿真實(shí)驗(yàn)表明：該算法克服了基本ABC算法收斂速度慢和“早熟”的缺點(diǎn)，極大的提高了網(wǎng)絡(luò)覆蓋率，確保了良好的網(wǎng)絡(luò)服務(wù)質(zhì)量。

1 相關(guān)問(wèn)題描述

1.1 人工蜂群算法

人工蜂群算法是模擬蜜蜂采蜜行為的智能群算法，具有控制參數(shù)少，健壯性的優(yōu)點(diǎn)［9］，可以解決連續(xù)、組合優(yōu)化問(wèn)題。在基本蜂群算法中，蜜源初始位置在搜索空間內(nèi)隨機(jī)產(chǎn)生；引領(lǐng)蜂和偵察蜂進(jìn)行隨機(jī)性的位置更新，對(duì)新蜜源的開(kāi)采和探索具有很大的不確定性和偶然性；跟隨蜂采用輪盤賭的方法選擇引領(lǐng)蜂進(jìn)行跟隨搜索，這些隨機(jī)性過(guò)程使算法很容易出現(xiàn)收斂速度慢、早熟等問(wèn)題。

1.2 Voronoi多邊形

Voronoi多邊形是幾何學(xué)中的重要結(jié)構(gòu)，在很多領(lǐng)域都得到了廣泛使用，它的一個(gè)重要應(yīng)用是有效描述點(diǎn)與點(diǎn)之間的鄰近關(guān)系。本文利用Voronoi多邊形進(jìn)行固定節(jié)點(diǎn)部署后的覆蓋漏洞的查找及其大小的評(píng)價(jià)，具有很強(qiáng)的適用性。文中用d（·）表示括號(hào)中任意兩點(diǎn)的歐氏距離，R表示節(jié)點(diǎn)覆蓋圓的半徑。

1.2.1 Voronoi多邊形

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

稱為點(diǎn)A關(guān)于B的支配區(qū)域?？傻玫絊區(qū)域中以A點(diǎn)為中心的對(duì)應(yīng)Voronoi多邊形區(qū)域：

式中：Q表示S區(qū)域中所有節(jié)點(diǎn)的集合。

1.2.2 區(qū)域覆蓋漏洞

在監(jiān)測(cè)區(qū)域內(nèi)，對(duì)比各傳感器節(jié)點(diǎn)到它對(duì)應(yīng)的Voronoi多邊形的所有頂點(diǎn)的距離與本節(jié)點(diǎn)覆蓋圓半徑的大小，可以判斷是否有覆蓋漏洞的存在。Voronoi多邊形各頂點(diǎn)到傳感器的距離用d（A，v）表示，其中A表示傳感器節(jié)點(diǎn)，v表示任一Voronoi頂點(diǎn)，則

用R表示傳感器的感知半徑，如果d（A，v）＞R，則說(shuō)明節(jié)點(diǎn)A所在的Voronoi多邊形區(qū)域出現(xiàn)覆蓋漏洞。

1.2.3 尋找漏洞實(shí)例

將隨機(jī)分布的節(jié)點(diǎn)劃分Voronoi多邊形后，根據(jù)Voronoi多邊形內(nèi)部的點(diǎn)距離相應(yīng)節(jié)點(diǎn)最近的原理，通過(guò)比較Voronoi多邊形的頂點(diǎn)與對(duì)應(yīng)節(jié)點(diǎn)覆蓋區(qū)域的位置關(guān)系可以確定是否有覆蓋漏洞的存在。如果Voronoi多邊形的頂點(diǎn)未被覆蓋，則出現(xiàn)覆蓋漏洞，該頂點(diǎn)即被定義為覆蓋漏洞頂點(diǎn)。

圖1為隨機(jī)分布的40個(gè)傳感器節(jié)點(diǎn)對(duì)應(yīng)的網(wǎng)絡(luò)覆蓋圖，其中“·”表示傳感器節(jié)點(diǎn)，“○”表示節(jié)點(diǎn)對(duì)應(yīng)的覆蓋區(qū)域，“-”表示Voronoi多邊形的邊，“▲”表示覆蓋漏洞頂點(diǎn)。

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

1.3 區(qū)域覆蓋率

1.3.1 覆蓋模型

假設(shè)Si為區(qū)域S中任意一點(diǎn)，A為區(qū)域中的任意傳感器節(jié)點(diǎn)，Si與節(jié)點(diǎn)A的距離為d（A，Si）。在布爾模型中，節(jié)點(diǎn)A對(duì)目標(biāo)點(diǎn)Si的檢測(cè)概率由下式（1）得到：

將區(qū)域S離散化為m×n個(gè)網(wǎng)格點(diǎn)，則區(qū)域S中有效覆蓋的網(wǎng)格點(diǎn)數(shù)count為

1.3.2 覆蓋率Cov

覆蓋率Cov是指目標(biāo)監(jiān)測(cè)區(qū)域中能夠被部署的傳感器節(jié)點(diǎn)所覆蓋的面積與監(jiān)測(cè)區(qū)域總面積的比值，是評(píng)價(jià)無(wú)線傳感器網(wǎng)絡(luò)覆蓋質(zhì)量的重要指標(biāo)，是研究的熱點(diǎn)［10］。覆蓋率的好壞除與節(jié)點(diǎn)自身的感知能力有關(guān)外，節(jié)點(diǎn)的部署位置也很大程度上影響覆蓋率的大小。本文將區(qū)域S離散化為m×n個(gè)網(wǎng)格點(diǎn)，每個(gè)網(wǎng)格點(diǎn)是否被覆蓋用式（1）衡量，則覆蓋率Cov簡(jiǎn)化為有效覆蓋的網(wǎng)格點(diǎn)數(shù)count與總點(diǎn)數(shù)m×n的比值，即

2 基于VABC的覆蓋優(yōu)化策略

從蜂群算法的基本原理可知：算法中每個(gè)食物源對(duì)應(yīng)一個(gè)移動(dòng)節(jié)點(diǎn)的位置，搜索最優(yōu)食物源即尋找移動(dòng)節(jié)點(diǎn)最優(yōu)部署位置的過(guò)程。移動(dòng)節(jié)點(diǎn)的個(gè)數(shù)等于引領(lǐng)蜂的個(gè)數(shù)，同時(shí)也等于跟隨蜂的個(gè)數(shù)。

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

傳統(tǒng)ABC算法中，隨機(jī)產(chǎn)生新的蜜源，引領(lǐng)蜂的搜索過(guò)程也是隨機(jī)行為。VABC算法則首先根據(jù)節(jié)點(diǎn)的隨機(jī)部署情況，生成固定節(jié)點(diǎn)相對(duì)應(yīng)的Vor?onoi多邊形，利用Voronoi頂點(diǎn)找出固定節(jié)點(diǎn)的覆蓋漏洞，從覆蓋漏洞中選擇產(chǎn)生新蜜源，并指導(dǎo)引領(lǐng)蜂的搜索過(guò)程，迅速定位蜜源在整個(gè)目標(biāo)區(qū)域的大概位置，計(jì)算蜜源的適應(yīng)度值，根據(jù)貪婪算法選擇確定保留的蜜源，有利于全局尋優(yōu)，迅速收斂。

2.2 跟隨蜂選擇策略的改進(jìn)

在基本人工蜂群算法中，跟隨蜂采用輪盤賭的方法選擇引領(lǐng)蜂，具有很大的隨機(jī)性，容易陷入局部極值。而VABC算法通過(guò)評(píng)價(jià)覆蓋漏洞的大小來(lái)分配跟隨蜂。跟隨蜂在覆蓋漏洞頂點(diǎn)附近進(jìn)行局部調(diào)整，并計(jì)算蜜源的適應(yīng)度值，根據(jù)貪婪算法選擇確定保留的蜜源，有利于局部最優(yōu)值的尋找。

目標(biāo)區(qū)域經(jīng)Voronoi劃分后覆蓋漏洞的評(píng)價(jià)策略如下：

如圖2為傳感器節(jié)點(diǎn)A生成的Voronoi多邊形，連接節(jié)點(diǎn)A和Voronoi多邊形的頂點(diǎn)，將多邊形分為以A點(diǎn)和一條Voronoi邊（以M和N為頂點(diǎn)）構(gòu)成的不同的Voronoi三角形區(qū)域。根據(jù)節(jié)點(diǎn)A的覆蓋圓與Voronoi多邊形頂點(diǎn)的相對(duì)位置關(guān)系，可以計(jì)算評(píng)價(jià)覆蓋漏洞area（AMN）的大小［11］。

圖2 節(jié)點(diǎn)A生成的Voronoi多邊形

①當(dāng)節(jié)點(diǎn)A的覆蓋圓將頂點(diǎn)M和N完全覆蓋在內(nèi)，即距離比較公式d（A，M）≤R和d（A，N）≤R都成立時(shí)，則不存在覆蓋漏洞；

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

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

圖3 覆蓋漏洞判斷

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

（b）垂足P落在線段MN外部，則∠AMN＞∏/2，如圖3（b）所示，△AMN內(nèi)存在的覆蓋漏洞面積的計(jì)算與垂足落在線段MN內(nèi)原理相同，只是各個(gè)小區(qū)域面積計(jì)算略有不同?？傻萌切巍鰽MN內(nèi)存在的覆蓋漏洞面積為

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

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

2.3 最差蜜源的替換

在ABC算法迭代過(guò)程中，下一代引領(lǐng)蜂和跟隨蜂可能依據(jù)本代的最差蜜源產(chǎn)生新蜜源，但最差蜜源不利于獲得最優(yōu)結(jié)果，這在一定程度上影響了算法的收斂速度。在VABC算法中，通過(guò)Voronoi多邊形產(chǎn)生的蜜源會(huì)出現(xiàn)面積很小的覆蓋漏洞，這類漏洞在WSN網(wǎng)絡(luò)的聯(lián)通范圍內(nèi)是允許存在的，并不影響網(wǎng)絡(luò)的正常運(yùn)行，如圖4中的A點(diǎn)所示。

圖4 最差蜜源實(shí)例

這類覆蓋漏洞即被視為最差蜜源。當(dāng)搜索得到最差蜜源時(shí)，相應(yīng)的引領(lǐng)蜂轉(zhuǎn)變?yōu)閭刹榉洌艞壴凶畈蠲墼?，重新搜索，產(chǎn)生新蜜源來(lái)繼續(xù)算法的循環(huán)執(zhí)行。

2.4 算法執(zhí)行

蜂群按照基于Voronoi圖的蜂群優(yōu)化算法進(jìn)行搜索，根據(jù)蜂群的適應(yīng)度值大小進(jìn)行貪婪選擇優(yōu)化，重復(fù)上面的過(guò)程直到滿足終止條件。

算法的具體步驟描述如下：①隨機(jī)部署網(wǎng)絡(luò)節(jié)點(diǎn)，利用公式（3）計(jì)算網(wǎng)絡(luò)初始覆蓋率。根據(jù)固定節(jié)點(diǎn)部署情況生成對(duì)應(yīng)的Voronoi多邊形，并找出覆蓋漏洞頂點(diǎn)；②初始化種群規(guī)模、引領(lǐng)蜂數(shù)量、最大輪數(shù)等參數(shù)；③隨機(jī)選取漏洞頂點(diǎn)作為移動(dòng)節(jié)點(diǎn)初始位置，分配引領(lǐng)蜂，并進(jìn)行全局搜索，根據(jù)公式（3）評(píng)價(jià)網(wǎng)絡(luò)覆蓋率，由貪婪法則選擇其中較好的解來(lái)更新移動(dòng)節(jié)點(diǎn)位置，有利于迅速找到全局最優(yōu)解；④對(duì)步驟（c）進(jìn)行有限次循環(huán)后，若發(fā)現(xiàn)存在未提高網(wǎng)絡(luò)覆蓋率的移動(dòng)節(jié)點(diǎn)位置，則相應(yīng)的引領(lǐng)蜂轉(zhuǎn)變?yōu)閭刹榉溥M(jìn)行搜索，產(chǎn)生新的移動(dòng)節(jié)點(diǎn)位置取代原來(lái)的節(jié)點(diǎn)位置；⑤評(píng)價(jià)覆蓋漏洞大小，選取較大漏洞分配跟隨蜂，跟隨蜂進(jìn)行細(xì)致的局部搜索，根據(jù)公式（3）評(píng)價(jià)網(wǎng)絡(luò)覆蓋率，由貪婪法則選擇其中較好的解來(lái)更新移動(dòng)節(jié)點(diǎn)位置，利于局部最優(yōu)解的尋找；⑥判斷是否達(dá)到最大循環(huán)次數(shù)，如果達(dá)到最大執(zhí)行輪數(shù)，則停止循環(huán)，否則根據(jù)網(wǎng)絡(luò)覆蓋率對(duì)新的蜂群再一次進(jìn)行搜索，即轉(zhuǎn)到步驟（c）繼續(xù)搜索；⑦記錄最優(yōu)的移動(dòng)節(jié)點(diǎn)位置作為尋優(yōu)結(jié)果，生成最終的網(wǎng)絡(luò)覆蓋圖。

算法流程圖如下圖5。

圖5 算法流程圖

3 仿真實(shí)驗(yàn)分析

假設(shè)無(wú)線傳感器網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域?yàn)?00 m×100 m的正方形，在這個(gè)區(qū)域內(nèi)隨機(jī)放置30個(gè)傳感器固定節(jié)點(diǎn)，20個(gè)傳感器移動(dòng)節(jié)點(diǎn)，每個(gè)傳感器節(jié)點(diǎn)的感知距離為10 m，通信距離為20 m。ABC算法和VABC算法參數(shù)為：種群規(guī)模50，雇傭蜂數(shù)20，食物源數(shù)20，最大迭代次數(shù)1 000。

圖6（a）是節(jié)點(diǎn)隨機(jī)部署的情況，黃色表示固定節(jié)點(diǎn)，藍(lán)色表示移動(dòng)節(jié)點(diǎn)，生成固定節(jié)點(diǎn)的Voronoi多邊形，尋找到固定節(jié)點(diǎn)部署漏洞，網(wǎng)絡(luò)初始覆蓋率為72.82%；圖6（b）是使用VABC算法優(yōu)化后的節(jié)點(diǎn)位置，移動(dòng)節(jié)點(diǎn)很好的填補(bǔ)了覆蓋漏洞，網(wǎng)絡(luò)覆蓋率達(dá)到95.42%，移動(dòng)節(jié)點(diǎn)覆蓋均勻，達(dá)到了很好的覆蓋效果。

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

本文中定義覆蓋率達(dá)到本算法最大覆蓋率的97%所需執(zhí)行的輪數(shù)來(lái)評(píng)價(jià)算法的收斂速度。表1通過(guò)不同算法的相關(guān)數(shù)據(jù)比較來(lái)直觀反映基本ABC算法、混沌人工蜂群算法和Voronoi人工蜂群算法的性能優(yōu)劣。

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

表1 不同算法的數(shù)據(jù)比較

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

本文將幾何學(xué)中的Voronoi多邊形理論與蜂群算法相結(jié)合，提出VABC算法并應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)的移動(dòng)節(jié)點(diǎn)部署。通過(guò)仿真實(shí)驗(yàn)對(duì)VABC算法進(jìn)行分析，實(shí)驗(yàn)結(jié)果表明：該算法結(jié)構(gòu)簡(jiǎn)單，能很好的避免基本ABC算法收斂速度慢，易陷入局部極值的缺點(diǎn)，具有很好的實(shí)用效果。

［1］李岳衡，王慧斌.無(wú)線傳感器網(wǎng)絡(luò)與監(jiān)測(cè)應(yīng)用［M］.北京：國(guó)防工業(yè)出版社，2011：7-11.

［2］徐凌偉，張浩，Gulliver T A，等.移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)系統(tǒng)在n-Rayleigh信道下的性能分析［J］.傳感技術(shù)學(xué)報(bào)，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］胡珂.基于人工蜂群算法在無(wú)線傳感網(wǎng)絡(luò)覆蓋優(yōu)化策略中的應(yīng)用研究［D］.成都：電子科技大學(xué)，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］秦寧寧，陳家樂(lè)，丁志國(guó).覆蓋率均衡區(qū)域覆蓋算法［J］.傳感技術(shù)學(xué)報(bào)，2015（4）：578-584.

［11］周則順.無(wú)線傳感器網(wǎng)絡(luò)覆蓋與連通優(yōu)化算法的研究［D］.武漢：武漢理工大學(xué)，2013.

［12］文政穎，翟紅生.基于混沌人工蜂群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化［J］.計(jì)算機(jī)測(cè)量與控制，2014，22（5）：1609-1612.

穆天圓（1990-），男，碩士研究生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署及覆蓋，972130219@qq.com；

喬學(xué)工（1968-），女，副教授，碩士生導(dǎo)師，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)，qiaoxg1968@aliyun.com；

張 敏（1990-），男，碩士研究生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)定位，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

項(xiàng)目來(lái)源：國(guó)家自然科學(xué)基金項(xiàng)目（51279122）；山西省自然科學(xué)基金項(xiàng)目（2012011013-5）；山西省軟科學(xué)基金項(xiàng)目（2014041048-4）

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