基于Delaunay圖的人工蜂群算法在WSN覆蓋策略中的優(yōu)化研究

王 軍， 趙子君， 李國(guó)強(qiáng)

(沈陽(yáng)化工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 遼寧 沈陽(yáng) 110142)

隨著科學(xué)技術(shù)的發(fā)展和無(wú)線傳感器網(wǎng)絡(luò)的普及應(yīng)用，無(wú)線傳感器網(wǎng)絡(luò)在生活中扮演著越來(lái)越重要的角色，特別是在海上監(jiān)測(cè)、森林火災(zāi)等自然災(zāi)害方面，災(zāi)情信息的及時(shí)獲取都給我們帶來(lái)巨大便利[1].通過(guò)在監(jiān)測(cè)區(qū)域內(nèi)投放大量的無(wú)線傳感器節(jié)點(diǎn)來(lái)獲取實(shí)時(shí)信息，但是由于節(jié)點(diǎn)投放的隨機(jī)性導(dǎo)致監(jiān)測(cè)區(qū)域的覆蓋不均勻，節(jié)點(diǎn)分布稀疏的區(qū)域就會(huì)產(chǎn)生覆蓋漏洞，節(jié)點(diǎn)分布過(guò)于密集又會(huì)產(chǎn)生覆蓋冗余.因此設(shè)計(jì)一種移動(dòng)節(jié)點(diǎn)調(diào)度優(yōu)化方案來(lái)提高覆蓋質(zhì)量至關(guān)重要[2].

目前，傳統(tǒng)的無(wú)線傳感器網(wǎng)絡(luò)覆蓋問(wèn)題已經(jīng)進(jìn)行了很多研究.Penny等[3]使用改進(jìn)的粒子群算法指導(dǎo)無(wú)線傳感器網(wǎng)絡(luò)的部署，在一定程度上提高了網(wǎng)絡(luò)覆蓋率，但算法容易陷入局部最優(yōu)解.文獻(xiàn)[4-5]使用人工蜂群(artificial bee colony，ABC)算法指導(dǎo)網(wǎng)絡(luò)布局，但算法收斂速度慢，容易陷入局部最優(yōu).Lee 等[6]提出了基于泰森多邊形形心的部署策略(Centroid-Based scheme，CBS)，一定程度上降低了算法復(fù)雜度，但網(wǎng)絡(luò)覆蓋效果不夠理想.

由固定節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)共同組成的混合無(wú)線傳感器網(wǎng)絡(luò)隨機(jī)部署在二維目標(biāo)監(jiān)測(cè)區(qū)域可以通過(guò)移動(dòng)節(jié)點(diǎn)的位置調(diào)整，實(shí)現(xiàn)目標(biāo)區(qū)域的優(yōu)質(zhì)覆蓋[7].因此，對(duì)于傳統(tǒng)人工蜂群算法的缺點(diǎn)，首先利用Delaunay圖尋找覆蓋漏洞，再把改進(jìn)的人工蜂群算法(Delaunay artificial bee colony，D-ABC)對(duì)無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)覆蓋策略進(jìn)行優(yōu)化，提高了WSN的整體性能.

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

1.1 人工蜂群算法

人工蜂群算法(ABC)是由D.Karaboga[8]于2005年提出的一種人工模擬蜜蜂覓食行為的啟發(fā)式智能算法，其優(yōu)點(diǎn)在于優(yōu)化過(guò)程簡(jiǎn)單，控制參數(shù)少，易操作.但ABC算法也有啟發(fā)式智能算法都有的缺點(diǎn)即過(guò)度的隨機(jī)性：蜜源初始位置是隨機(jī)的；偵查蜂隨機(jī)探索新蜜源的位置.以上原因?qū)е路淙核惴ê笃谑諗克俣嚷?，容易陷入局部極值和早熟[9].

1.2 Delaunay圖

1.2.1 Delaunay圖

Delaunay圖即對(duì)于一組無(wú)線傳感器固定節(jié)點(diǎn)，可以得到很多種不用的三角剖分，其中最優(yōu)三角剖分就是Delaunay三角網(wǎng)[10].體現(xiàn)在其最重要的兩個(gè)性質(zhì)：唯一性，一組點(diǎn)無(wú)論如何構(gòu)造都能得到同一個(gè)delaunay三角網(wǎng)；不相交性，delaunay三角網(wǎng)內(nèi)各邊都不相交.在此根據(jù)Delaunay三角網(wǎng)內(nèi)每個(gè)三角形外接圓圓心的位置得到引領(lǐng)蜂的初始位置和個(gè)數(shù).還要根據(jù)每個(gè)delaunay三角形的面積計(jì)算每個(gè)三角形內(nèi)部需要部署的偵察蜂個(gè)數(shù).

1.2.2 覆蓋漏洞的估算方法

想要確定引領(lǐng)蜂和偵查蜂的位置和個(gè)數(shù)，首先需要找到Delaunay三角形的外接圓圓心，三角形的外接圓圓心到三角形三個(gè)頂點(diǎn)的距離相等，通過(guò)比較外接圓圓心到節(jié)點(diǎn)的距離與傳感器節(jié)點(diǎn)通信半徑的大小關(guān)系來(lái)判斷三角形內(nèi)是否存在覆蓋漏洞.

本文研究的是由靜態(tài)節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)組成的混合網(wǎng)絡(luò)，由靜態(tài)節(jié)點(diǎn)在每個(gè)三角形內(nèi)計(jì)算覆蓋空洞面積以及計(jì)算出移動(dòng)節(jié)點(diǎn)的位置，然后命令移動(dòng)節(jié)點(diǎn)修復(fù)覆蓋漏洞.現(xiàn)在需要解決的問(wèn)題是在每個(gè)三角型內(nèi)判斷是否存在覆蓋空洞，計(jì)算覆蓋空洞的面積和移動(dòng)節(jié)點(diǎn)位置信息.

1.3 網(wǎng)絡(luò)覆蓋率

網(wǎng)絡(luò)覆蓋率指全部傳感器節(jié)點(diǎn)覆蓋的總面積占監(jiān)測(cè)區(qū)域總面積的百分比[11].在此令So為傳感器節(jié)點(diǎn)所覆蓋的總面積，a×b為監(jiān)測(cè)區(qū)域總面積，覆蓋率為：

(1)

1.4 感知模型

1.4.1 二元感知模型

二元感知模型也稱(chēng)布爾感知模型，如果監(jiān)測(cè)節(jié)點(diǎn)的感知范圍覆蓋了目標(biāo)節(jié)點(diǎn)，監(jiān)測(cè)概率為1；反之，監(jiān)測(cè)節(jié)點(diǎn)的感知范圍沒(méi)有覆蓋目標(biāo)節(jié)點(diǎn)，監(jiān)測(cè)概率則為0.這就是所謂的0-1感知模型，又稱(chēng)之為二元感知模型，最典型的例子當(dāng)屬圓盤(pán)感知模型[12]，如圖1所示.節(jié)點(diǎn)o(xo,yo)的感知區(qū)域定義為節(jié)點(diǎn)o為圓心、以ro為半徑的圓形區(qū)域Ro(o,ro)，則位于Ro(o,ro)內(nèi)的任意點(diǎn)都能被o監(jiān)測(cè)到.其中，ro也被稱(chēng)作o的感知半徑，且節(jié)點(diǎn)的物理特性決定了ro的大小.設(shè)平面上任一目標(biāo)點(diǎn)P(xp,yp)，節(jié)點(diǎn)o監(jiān)測(cè)到點(diǎn)p處發(fā)生事件的概率表示為：

(2)

圖1 二元感知模型

1.4.2 概率感知模型

概率感知模型是一種離散的理想模型，符合無(wú)線傳感器網(wǎng)絡(luò)的真實(shí)覆蓋效果，即假定目標(biāo)點(diǎn)是否被傳感器節(jié)點(diǎn)監(jiān)測(cè)到的情況是確定的，也就是監(jiān)測(cè)到設(shè)為1，確定不覆蓋設(shè)為0.概率感知模型存在一個(gè)“中間區(qū)域”，即在確定不覆蓋和確定覆蓋中間，如圖2所示.而在實(shí)際應(yīng)用場(chǎng)景中，節(jié)點(diǎn)的無(wú)線信號(hào)由于受到如障礙物、噪聲等外界環(huán)境的干擾，概率感知模型反映出節(jié)點(diǎn)感知能力隨著距離變化而變化的特征[13].

目標(biāo)區(qū)域內(nèi)任一目標(biāo)點(diǎn)p被傳感器節(jié)點(diǎn)o監(jiān)測(cè)到的概率表示為:

(3)

圖2 概率感知模型

2 基于D-ABC的覆蓋優(yōu)化策略

從蜂群算法的基本原理可知：算法中每個(gè)食物源與引領(lǐng)蜂的位置和數(shù)量一一對(duì)應(yīng)，偵查蜂圍繞引領(lǐng)蜂進(jìn)行局部搜索.移動(dòng)節(jié)點(diǎn)的個(gè)數(shù)等于引領(lǐng)蜂的個(gè)數(shù)與偵查蜂的個(gè)數(shù)之和.

2.1 Delaunay三角網(wǎng)覆蓋漏洞的估算

根據(jù)討論三角形外接圓圓心到節(jié)點(diǎn)距離與節(jié)點(diǎn)通信半徑的大小關(guān)系來(lái)判斷三角形內(nèi)是否存在覆蓋漏洞.首先求出外接圓圓心So=(Xo,Yo).

(4) 如果三角形的外接圓圓心So(Xo,Yo)到三角形任意一點(diǎn)的距離都小于節(jié)點(diǎn)的通信半徑，那么三角形內(nèi)不存在覆蓋漏洞，反之一定存在覆蓋漏洞.分為以下情況進(jìn)行討論：

1) 一定不存在覆蓋漏洞

當(dāng)d(Oi,So)≤Ro時(shí)，3個(gè)節(jié)點(diǎn)的通信半徑覆蓋的面積會(huì)兩兩相交，并且一定不存在覆蓋漏洞，如圖3所示.

圖3 不存在覆蓋漏洞

2) 存在覆蓋漏洞情況

A：如果d(Oi,So)>Ro，即O1、O2、O3這3個(gè)節(jié)點(diǎn)每?jī)蓚€(gè)都不相交而且3個(gè)節(jié)點(diǎn)到外接圓圓心的距離都大于節(jié)點(diǎn)的通信半徑，那么delaunay三角形內(nèi)一定存在覆蓋漏洞，如圖4所示.可計(jì)算出覆蓋漏洞的面積為三角形的面積減去3個(gè)扇形的面積之和：

(5)

圖4 情況A:存在覆蓋漏洞

B：如果d(Oi,So)>Ro，并且其中一個(gè)節(jié)點(diǎn)和另兩個(gè)節(jié)點(diǎn)相交時(shí)，delaunay三角形將會(huì)形成鈍角三角形，如圖5所示.由圖5可知：

(6)

那么若想求出S1需先求出兩圓相交面積的一半，用扇形面積SO1C1C2減去三角形面積SΔO1C1C2，計(jì)算出d(O1,c)和三角形面積SΔO1C1C2：

(7)

兩圓相交的面積SC1C2C2C1和S1為：

(8)

圖5 情況B:存在覆蓋漏洞

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

在傳統(tǒng)ABC算法中，蜜源初始位置是隨機(jī)的，引領(lǐng)蜂的搜索過(guò)程也是隨機(jī)的[14].D-ABC算法是根據(jù)固定節(jié)點(diǎn)的隨機(jī)部署情況，生成固定節(jié)點(diǎn)對(duì)應(yīng)的 Delaunay三角網(wǎng)，利用 Delaunay三角網(wǎng)找出固定節(jié)點(diǎn)覆蓋漏洞，根據(jù)三角形面積確定是否生成蜜源，從而確定是否生成引領(lǐng)蜂；三角形的外接圓圓心的位置即蜜源位置，得到引領(lǐng)蜂的位置.

2.3 偵查蜂的改進(jìn)

在傳統(tǒng)ABC算法中，偵查蜂隨機(jī)尋找蜜源，尋找蜜源的過(guò)程對(duì)應(yīng)最優(yōu)解的過(guò)程[15].D-ABC算法蜜源位置即引領(lǐng)蜂的位置，通過(guò)判斷覆蓋漏洞的大小，分配偵查蜂的數(shù)量.

2.4 矩形內(nèi)創(chuàng)建delaunay三角網(wǎng)

由于delaunay三角網(wǎng)是一個(gè)凸多邊形，不能完整覆蓋整個(gè)監(jiān)測(cè)區(qū)域，這里在矩形內(nèi)建立delaunay三角網(wǎng).如圖6所示.

圖6 矩形內(nèi)的delaunay三角網(wǎng)

2.5 算法執(zhí)行過(guò)程

算法具體步驟如下：

(1) 隨機(jī)部署固定節(jié)點(diǎn)，并且根據(jù)固定節(jié)點(diǎn)部署情況生成對(duì)應(yīng)的delaunay三角網(wǎng).

(2) 通過(guò)計(jì)算每個(gè)delaunay三角形的覆蓋漏洞面積，確定需要填充覆蓋漏洞的delaunay三角形.

(3) 根據(jù)delaunay三角形外接圓圓心的數(shù)量，初始化引領(lǐng)蜂的數(shù)量.

(4) 根據(jù)delaunay三角形的面積，確定偵查蜂的數(shù)量.

(5) 根據(jù)引領(lǐng)蜂和偵察蜂的數(shù)量隨機(jī)部署移動(dòng)節(jié)點(diǎn)，計(jì)算無(wú)線傳感器網(wǎng)絡(luò)的初始覆蓋率.

(6) 根據(jù)delaunay三角形外接圓圓心的位置，初始化引領(lǐng)蜂的位置.

(7) 偵查蜂進(jìn)行delaunay三角形內(nèi)部的局部搜索，計(jì)算有限次后，停止局部搜索.

(8) 記錄移動(dòng)節(jié)點(diǎn)的最終位置并且生成最終的網(wǎng)絡(luò)覆蓋圖并計(jì)算網(wǎng)絡(luò)覆蓋率.

3 仿 真

建立100 m×100 m的正方形仿真區(qū)域，初始條件下隨機(jī)放置40個(gè)固定節(jié)點(diǎn).由固定節(jié)點(diǎn)構(gòu)成的delaunay三角網(wǎng)計(jì)算得到需要的31個(gè)移動(dòng)節(jié)點(diǎn)(20個(gè)引領(lǐng)蜂和11個(gè)偵查蜂).得到初始情況的隨機(jī)部署，如圖7所示.網(wǎng)絡(luò)覆蓋率為73.63 %.使用D-ABC算法后，網(wǎng)絡(luò)覆蓋率為95.71 %.如圖8所示.

圖7 初始部署狀態(tài)

圖8 優(yōu)化后部署狀態(tài)

為更好地體現(xiàn)D-ABC算法的性能，與其他的群智能算法進(jìn)行對(duì)比.在Matlab中對(duì)蜂群算法(ABC)、混沌蜂群算法(CABC)、和D-ABC算法的網(wǎng)絡(luò)覆蓋率進(jìn)行了對(duì)比，3種算法的迭代次數(shù)與網(wǎng)絡(luò)覆蓋率的折線圖如圖9所示，可以直觀看出：ABC算法最終可達(dá)到的網(wǎng)絡(luò)覆蓋率為90.11 %，CABC算法可達(dá)到93.48 %，CABC算法相較于ABC算法收斂速度更快，網(wǎng)絡(luò)覆蓋率有明顯提高[16]，D-ABC算法相較于CABC收斂速度更快并且網(wǎng)絡(luò)覆蓋率可達(dá)到95.71 %.

圖9 ABC、CABC、D-ABC算法對(duì)比

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

覆蓋問(wèn)題是無(wú)線傳感器網(wǎng)絡(luò)中的基本問(wèn)題.本文在傳統(tǒng)的人工蜂群算法的基礎(chǔ)上結(jié)合delaunay三角網(wǎng)算法提出D-ABC算法，用于解決無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)覆蓋不均勻，覆蓋率低等問(wèn)題.D-ABC算法能夠快速估算覆蓋漏洞的大小，并且提高網(wǎng)絡(luò)覆蓋效率，實(shí)現(xiàn)無(wú)線傳感器網(wǎng)絡(luò)的覆蓋優(yōu)化.本文目前解決了混合無(wú)線傳感器網(wǎng)絡(luò)覆蓋中的區(qū)域覆蓋問(wèn)題，需要進(jìn)一步研究柵欄覆蓋問(wèn)題，以及在此過(guò)程中的移動(dòng)路徑和節(jié)點(diǎn)能量消耗等問(wèn)題，完成完整的無(wú)線傳感器網(wǎng)絡(luò)部署.