一種WSN三維覆蓋空洞動(dòng)態(tài)檢測(cè)與修復(fù)算法

郝占軍,徐宏文,黨小超,段 渝

(1.西北師范大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,蘭州 730070; 2.甘肅省物聯(lián)網(wǎng)工程研究中心,蘭州 730070)

0 概述

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)是一種具有自組織性、可靠性、可移動(dòng)性且節(jié)點(diǎn)間可以相互通信的無(wú)線覆蓋網(wǎng)絡(luò)[1]。目前,關(guān)于二維平面覆蓋策略的研究已經(jīng)取得較多成果,應(yīng)用于實(shí)際場(chǎng)景的三維空間覆蓋策略也逐漸引起學(xué)者們的關(guān)注。研究三維環(huán)境下的空間覆蓋策略的目的是解決現(xiàn)實(shí)生活中如安防部署、森林火災(zāi)檢測(cè)以及水下動(dòng)態(tài)檢測(cè)等問(wèn)題[2-3]。

在部署無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)時(shí),由于外部因素的限制,難以在目標(biāo)區(qū)域中對(duì)初始節(jié)點(diǎn)進(jìn)行均勻部署,會(huì)出現(xiàn)很多的覆蓋空洞從而導(dǎo)致通信受阻。為了提高整體網(wǎng)絡(luò)覆蓋和通信能力,針對(duì)不同類(lèi)型的覆蓋空洞,需要利用移動(dòng)節(jié)點(diǎn)對(duì)其進(jìn)行修補(bǔ)[4]。文獻(xiàn)[5]在混合傳感器網(wǎng)絡(luò)中針對(duì)部分節(jié)點(diǎn)失效導(dǎo)致的覆蓋空洞問(wèn)題,提出一種魯棒的空洞修復(fù)算法。該算法模擬魚(yú)群運(yùn)動(dòng)模式,利用移動(dòng)節(jié)點(diǎn)完成覆蓋空洞修補(bǔ),提高了網(wǎng)絡(luò)覆蓋率。文獻(xiàn)[6]為了避免網(wǎng)絡(luò)覆蓋空洞對(duì)網(wǎng)絡(luò)性能的影響,提出一種基于移動(dòng)節(jié)點(diǎn)的覆蓋空洞修補(bǔ)算法,并驗(yàn)證了該算法的高覆蓋率和低冗余度。文獻(xiàn)[7]針對(duì)網(wǎng)絡(luò)中存在大量冗余移動(dòng)節(jié)點(diǎn),提出一種移動(dòng)節(jié)點(diǎn)補(bǔ)償方法(DAVM),其充分利用冗余資源實(shí)現(xiàn)網(wǎng)絡(luò)全覆蓋,但該方法不適用于網(wǎng)絡(luò)中存在少量移動(dòng)節(jié)點(diǎn)的情況。文獻(xiàn)[8-10]分析移動(dòng)節(jié)點(diǎn)部署問(wèn)題,最小化移動(dòng)節(jié)點(diǎn)移動(dòng)距離從而完成目標(biāo)覆蓋和網(wǎng)絡(luò)連通。以上文獻(xiàn)主要針對(duì)二維平面覆蓋進(jìn)行了深入研究。文獻(xiàn)[11]為了實(shí)現(xiàn)三維空間目標(biāo)最大化覆蓋,提出一種三維空間目標(biāo)自主覆蓋算法,其使用虛擬力來(lái)減少重疊覆蓋并修復(fù)覆蓋空洞。文獻(xiàn)[12]為了加強(qiáng)網(wǎng)絡(luò)服務(wù)質(zhì)量,建立新的三維感知模型,提出一種三維覆蓋增強(qiáng)算法,該算法通過(guò)優(yōu)化調(diào)節(jié)使冗余節(jié)點(diǎn)均勻分布在監(jiān)測(cè)區(qū)域,提高了對(duì)監(jiān)測(cè)區(qū)域的覆蓋率。

近年來(lái),為了提高網(wǎng)絡(luò)覆蓋率,較多學(xué)者在覆蓋控制研究中引入移動(dòng)節(jié)點(diǎn),將其與靜態(tài)節(jié)點(diǎn)一起部署,形成一種混合節(jié)點(diǎn)部署的傳感器網(wǎng)絡(luò)。本文提出一種三維覆蓋空洞動(dòng)態(tài)檢測(cè)與修復(fù)算法,建立三維感知模型對(duì)網(wǎng)絡(luò)中存在的覆蓋空洞進(jìn)行檢測(cè),當(dāng)檢測(cè)到覆蓋空洞時(shí),選擇覆蓋空洞周?chē)娜哂嘁苿?dòng)節(jié)點(diǎn)完成覆蓋空洞修復(fù),從而提高整體網(wǎng)絡(luò)覆蓋率。

1 三維空間覆蓋模型及相關(guān)定義

1.1 三維空間覆蓋的優(yōu)化問(wèn)題描述

在對(duì)三維空間目標(biāo)區(qū)域進(jìn)行覆蓋時(shí),將普通節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)混合后隨機(jī)部署在目標(biāo)區(qū)域,但隨機(jī)部署會(huì)出現(xiàn)節(jié)點(diǎn)分布不均勻的問(wèn)題。為了達(dá)到三維空間目標(biāo)區(qū)域的覆蓋要求,需要對(duì)傳感器網(wǎng)絡(luò)中存在的覆蓋空洞進(jìn)行動(dòng)態(tài)檢測(cè)與修復(fù),以提高網(wǎng)絡(luò)覆蓋率,實(shí)現(xiàn)對(duì)三維空間目標(biāo)區(qū)域的有效監(jiān)測(cè)。

對(duì)目標(biāo)區(qū)域進(jìn)行網(wǎng)格劃分是二維區(qū)域覆蓋部署研究中的常用方法,其原理是將目標(biāo)覆蓋區(qū)域按一定的形狀進(jìn)行劃分,得到若干小規(guī)模的網(wǎng)格區(qū)域,通過(guò)劃分的方法可以更好地提高覆蓋率并降低能耗。受二維平面覆蓋網(wǎng)格劃分的啟發(fā),本文將網(wǎng)格劃分拓展到三維空間,設(shè)定覆蓋目標(biāo)區(qū)域D是一個(gè)三維立體空間,先對(duì)其進(jìn)行立方體網(wǎng)格劃分,如圖1(a)所示,再在該三維空間目標(biāo)區(qū)域內(nèi)隨機(jī)拋灑N個(gè)混合傳感器節(jié)點(diǎn)以進(jìn)行覆蓋部署,如圖1(b)所示。

圖1 三維覆蓋區(qū)域劃分示意圖

針對(duì)本文算法建立三維空間理論覆蓋模型,假設(shè)如下:

1)靜態(tài)節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)構(gòu)成混合傳感器網(wǎng)絡(luò)。

3)傳感器節(jié)點(diǎn)具有相同通信半徑R和感知半徑r,且R≥2r。

1.2 三維空間覆蓋模型建立

常見(jiàn)的感知模型主要應(yīng)用于二維平面覆蓋,為了滿(mǎn)足實(shí)際場(chǎng)景的需求,本文構(gòu)建三維覆蓋模型,采用基于誤警率的感知模型。設(shè)網(wǎng)絡(luò)中移動(dòng)節(jié)點(diǎn)si的位置坐標(biāo)為(xi,yi,zi),將被監(jiān)測(cè)目標(biāo)區(qū)域D劃分成m×n×w個(gè)立方體網(wǎng)格,其中,用P表示立方體內(nèi)的一點(diǎn),且點(diǎn)P的位置坐標(biāo)為(x,y,z),則點(diǎn)P與傳感器節(jié)點(diǎn)si之間的距離為:

(1)

假定整個(gè)環(huán)境網(wǎng)絡(luò)具有高斯白噪聲,信號(hào)在傳播過(guò)程中按固定的損耗因子γ和傳播因子衰減,信號(hào)傳播損耗與1/rγ成比例關(guān)系,γ的值由環(huán)境因素決定[13]。信號(hào)在室內(nèi)自由傳播時(shí),γ通常為2或4。假設(shè)所有節(jié)點(diǎn)均具有相同的能量etr,對(duì)于節(jié)點(diǎn)i,從目標(biāo)節(jié)點(diǎn)所接收的能量為:

(2)

其中,M1和M0分別表示目標(biāo)在位和目標(biāo)缺失的情況,Dti為目標(biāo)(xt,yt,zt)與傳感器節(jié)點(diǎn)(xi,yi,zi)之間的距離,ni是均值為0、方差為σ2的高斯噪聲,β定義為:

(3)

在M1狀態(tài)下,目標(biāo)經(jīng)過(guò)的行程2r=2Dti。因此,對(duì)于第i個(gè)傳感器,M1狀態(tài)下的探測(cè)概率為:

(4)

同理,在M0狀態(tài)下的探測(cè)概率為:

(5)

Neyman-Person準(zhǔn)則追求誤警率PF最小而探測(cè)概率PD最大。設(shè)定可以接受的誤警率為PF=α,則可得到:

(6)

式(6)即為支持誤警率的Neyman-Person概率探測(cè)模型。其中,φ( · )為標(biāo)準(zhǔn)高斯累積分布函數(shù)。

定義1(三維覆蓋率) 被節(jié)點(diǎn)完全覆蓋的空間區(qū)域大小與總的需要覆蓋的目標(biāo)空間區(qū)域大小的比值稱(chēng)為三維覆蓋率。本文三維空間覆蓋率的計(jì)算借助網(wǎng)格劃分的方法,將被監(jiān)測(cè)的覆蓋空間區(qū)域劃分成大小相等的立方體網(wǎng)格,計(jì)算每個(gè)立方體網(wǎng)格受到的覆蓋率,累加每個(gè)立方體的覆蓋率可以求得總的三維空間覆蓋率。

定義2(三維聯(lián)合探測(cè)概率) 在三維空間目標(biāo)監(jiān)測(cè)區(qū)域中,任意一個(gè)立方體網(wǎng)格被有效覆蓋的概率是多個(gè)傳感器節(jié)點(diǎn)共同作用的效果,因此,整個(gè)網(wǎng)絡(luò)對(duì)任意一個(gè)立方體網(wǎng)格的聯(lián)合探測(cè)概率Uk(P)可定義為:

(7)

其中,Pi為任意傳感器節(jié)點(diǎn)i的探測(cè)概率,φ表示滿(mǎn)足條件的節(jié)點(diǎn)集合,dk,i為監(jiān)測(cè)點(diǎn)k與節(jié)點(diǎn)i之間的距離,dc為節(jié)點(diǎn)之間的通信距離。本文通過(guò)聯(lián)合探測(cè)概率的定義計(jì)算監(jiān)測(cè)區(qū)域內(nèi)每個(gè)立方體網(wǎng)格的三維聯(lián)合探測(cè)概率,以確定目標(biāo)空間的覆蓋率并判定其是否滿(mǎn)足三維覆蓋要求。

定義3(節(jié)點(diǎn)移動(dòng)最短距離) 在無(wú)線傳感器網(wǎng)絡(luò)中利用冗余移動(dòng)節(jié)點(diǎn)修復(fù)覆蓋空洞,移動(dòng)節(jié)點(diǎn)的移動(dòng)距離與整個(gè)網(wǎng)絡(luò)的總能耗成正比,為了降低整體網(wǎng)絡(luò)能耗,需要根據(jù)式(12)～式(15)計(jì)算移動(dòng)節(jié)點(diǎn)的最短移動(dòng)距離。

定義4(冗余節(jié)點(diǎn)) 在三維空間覆蓋目標(biāo)區(qū)域隨機(jī)部署傳感器節(jié)點(diǎn)時(shí),由于節(jié)點(diǎn)分布不均,同一個(gè)目標(biāo)節(jié)點(diǎn)同時(shí)被多個(gè)節(jié)點(diǎn)監(jiān)測(cè),且某個(gè)節(jié)點(diǎn)監(jiān)測(cè)區(qū)域可以由其他幾個(gè)節(jié)點(diǎn)代替,則稱(chēng)該節(jié)點(diǎn)為冗余節(jié)點(diǎn)。通過(guò)整體覆蓋網(wǎng)絡(luò)中節(jié)點(diǎn)間的互相通信可以判斷該節(jié)點(diǎn)是否為冗余節(jié)點(diǎn)。

定義5(移動(dòng)節(jié)點(diǎn)利用率) 在隨機(jī)部署的混合傳感器網(wǎng)絡(luò)中,靜態(tài)節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)按一定比例混合,其中移動(dòng)節(jié)點(diǎn)具有移動(dòng)性,其主要作用是用來(lái)修復(fù)網(wǎng)絡(luò)的覆蓋空洞,但部分移動(dòng)節(jié)點(diǎn)也會(huì)充當(dāng)靜態(tài)節(jié)點(diǎn)。修復(fù)覆蓋空洞的移動(dòng)節(jié)點(diǎn)數(shù)與總移動(dòng)節(jié)點(diǎn)數(shù)的比值稱(chēng)為移動(dòng)節(jié)點(diǎn)利用率。

2 三維覆蓋空洞的動(dòng)態(tài)檢測(cè)與修復(fù)算法

2.1 三維空間覆蓋空洞描述

在三維立體空間隨機(jī)部署節(jié)點(diǎn)時(shí),由于外部因素的限制,網(wǎng)絡(luò)中會(huì)出現(xiàn)覆蓋空洞[14]?？斩词怯芍?chē)鄠€(gè)節(jié)點(diǎn)形成的一個(gè)閉合空間,如圖2所示,周?chē)?jié)點(diǎn)之間也存在覆蓋冗余。感知節(jié)點(diǎn)1與覆蓋空洞有2個(gè)邊界端點(diǎn)W和S,即覆蓋空洞邊緣端點(diǎn)。設(shè)覆蓋空洞周?chē)衝個(gè)邊緣節(jié)點(diǎn),Vi表示節(jié)點(diǎn)i感知范圍的體積大小,Vh表示覆蓋空洞的體積大小。

圖2 三維空間覆蓋空洞示意圖

2.2 三維空間覆蓋空洞動(dòng)態(tài)檢測(cè)

針對(duì)覆蓋空洞檢測(cè)問(wèn)題,本文建立三維空間覆蓋模型,提出一種三維覆蓋空洞動(dòng)態(tài)檢測(cè)與修復(fù)算法。假設(shè)立方體網(wǎng)格中任意一個(gè)節(jié)點(diǎn)M是覆蓋空洞的邊緣節(jié)點(diǎn),為了檢測(cè)該覆蓋空洞,需要根據(jù)邊緣節(jié)點(diǎn)M找到構(gòu)成該覆蓋空洞的所有邊緣節(jié)點(diǎn),并計(jì)算覆蓋空洞的邊緣弧和邊緣端點(diǎn)[15]。隨機(jī)選取2個(gè)相鄰節(jié)點(diǎn)N和M,節(jié)點(diǎn)M與節(jié)點(diǎn)N的坐標(biāo)分別為(xM,yM,zM)、(xN,yN,zN),兩者距離為d(M,N),則節(jié)點(diǎn)N和節(jié)點(diǎn)M的方向角αNM由式(8)表示:

(8)

節(jié)點(diǎn)N與節(jié)點(diǎn)M重疊部分之間所形成的夾角θNM由式(9)表示:

(9)

節(jié)點(diǎn)N與節(jié)點(diǎn)M對(duì)應(yīng)的邊緣端點(diǎn)由式(10)表示:

(10)

檢測(cè)覆蓋空洞需要找到任意傳感器節(jié)點(diǎn)M的所有鄰居節(jié)點(diǎn)集合S={A,B,C,D,…},相對(duì)應(yīng)的覆蓋方向夾角集合為K={θAM,θBM,θCM,θDM,…},則方向夾角集合K所對(duì)應(yīng)的弧都不是邊緣弧,可以根據(jù)其補(bǔ)集求出對(duì)應(yīng)的空洞角。根據(jù)式(8)～式(10),由每個(gè)邊緣節(jié)點(diǎn)的空洞角、邊緣弧和邊緣端點(diǎn)就可以找出該覆蓋空洞。循環(huán)執(zhí)行上述方法,直至檢測(cè)出所有的覆蓋空洞[16-17]。

當(dāng)檢測(cè)到立方體網(wǎng)格中存在覆蓋空洞時(shí),算法調(diào)用覆蓋空洞周?chē)娜哂嘁苿?dòng)節(jié)點(diǎn)修復(fù)覆蓋空洞。根據(jù)計(jì)算所得的移動(dòng)方向和移動(dòng)距離在三維空間中移動(dòng)節(jié)點(diǎn)。首先確定移動(dòng)節(jié)點(diǎn)的移動(dòng)方向,在被檢測(cè)到的覆蓋空洞周?chē)哂喙?jié)點(diǎn)中隨機(jī)選擇一個(gè)移動(dòng)節(jié)點(diǎn),并標(biāo)記為P,該移動(dòng)節(jié)點(diǎn)P與覆蓋空洞邊緣所形成的關(guān)聯(lián)點(diǎn)為Pa和Pb,其中,節(jié)點(diǎn)P、關(guān)聯(lián)點(diǎn)Pa和Pb的坐標(biāo)分別為(x,y,z)、(x1,y1,z1)和(x2,y2,z2)。

通過(guò)構(gòu)造三維空間坐標(biāo)向量來(lái)確定移動(dòng)節(jié)點(diǎn)P的移動(dòng)方向,如式(11)所示:

(11)

由三維空間向量公式可知,通過(guò)構(gòu)造三維空間向量的方法就可以確定所選移動(dòng)節(jié)點(diǎn)P的移動(dòng)方向。在構(gòu)造向量Vr的過(guò)程中,會(huì)出現(xiàn)圖3所示的2種情況,即假設(shè)向量Va和Vb的夾角為θ,則θ存在2種可能:θ<π和θ>π。當(dāng)θ<π時(shí),節(jié)點(diǎn)移動(dòng)的方向?yàn)檎_方向;當(dāng)θ>π時(shí),節(jié)點(diǎn)移動(dòng)的方向?yàn)橄蛄縑r的反方向;當(dāng)θ=π時(shí),節(jié)點(diǎn)不發(fā)生移動(dòng)。

圖3 節(jié)點(diǎn)移動(dòng)方向判斷示例

為了使所選移動(dòng)節(jié)點(diǎn)完成對(duì)覆蓋空洞的修復(fù),首先確定移動(dòng)節(jié)點(diǎn)的移動(dòng)方向,然后通過(guò)節(jié)點(diǎn)移動(dòng)后的位置與先前鄰居節(jié)點(diǎn)的距離來(lái)確定節(jié)點(diǎn)的移動(dòng)距離。同時(shí),當(dāng)節(jié)點(diǎn)移動(dòng)到最優(yōu)位置時(shí)需要考慮2個(gè)問(wèn)題,一是保證移動(dòng)節(jié)點(diǎn)移動(dòng)后不會(huì)造成新的覆蓋空洞,二是適當(dāng)?shù)剡x擇移動(dòng)節(jié)點(diǎn)的個(gè)數(shù)以免造成過(guò)度的覆蓋冗余[18]。

在計(jì)算移動(dòng)節(jié)點(diǎn)的移動(dòng)距離時(shí),假設(shè)節(jié)點(diǎn)的移動(dòng)距離為d,向量Vr和VMC的夾角為θ1,當(dāng)NC=RC時(shí),覆蓋率取得最大值,節(jié)點(diǎn)C的坐標(biāo)記為(x3,y3,z3),節(jié)點(diǎn)M與節(jié)點(diǎn)C的距離由式(12)表示:

(12)

向量VMC的計(jì)算如式(13)所示:

VMC=(x3-x)i+(y3-y)j+(z3-z)k

(13)

夾角θ1的計(jì)算如式(14)所示:

(14)

如圖4所示,根據(jù)三角形性質(zhì)可得|MC|=d1,|MN|表示移動(dòng)距離為d,NC=RC,則移動(dòng)距離的計(jì)算如式(15)所示:

(15)

圖4 移動(dòng)距離計(jì)算示意圖

通過(guò)以上步驟即可得到隨機(jī)選取的移動(dòng)節(jié)點(diǎn)P的移動(dòng)方向Vr和移動(dòng)距離d。在移動(dòng)節(jié)點(diǎn)移動(dòng)到覆蓋空洞位置后,整體更新覆蓋空洞修復(fù)信息,繼續(xù)在覆蓋空洞周?chē)鷮ふ倚碌娜哂嘁苿?dòng)節(jié)點(diǎn)P′,重新初始化相關(guān)參數(shù),再次執(zhí)行上述方法進(jìn)行覆蓋空洞的修復(fù)。經(jīng)過(guò)數(shù)次迭代后,當(dāng)找不到合適的移動(dòng)節(jié)點(diǎn)或所有覆蓋空洞已被修復(fù),結(jié)束覆蓋空洞修復(fù)過(guò)程。

2.3 算法描述

本文三維覆蓋空洞動(dòng)態(tài)檢測(cè)與修復(fù)算法流程如圖5所示。

圖5 三維覆蓋空洞動(dòng)態(tài)檢測(cè)與修復(fù)算法流程

算法步驟具體如下:

步驟1初始化N個(gè)混合傳感器節(jié)點(diǎn),并對(duì)三維空間目標(biāo)區(qū)域進(jìn)行立方體網(wǎng)格劃分。

步驟2設(shè)置感知模型的誤警率參數(shù),采用聯(lián)合探測(cè)概率模型探測(cè)每個(gè)立方體網(wǎng)格的覆蓋率。

步驟3在每個(gè)立方體網(wǎng)格中隨機(jī)選擇一個(gè)傳感器節(jié)點(diǎn)X,其坐標(biāo)為(x,y,z),找出節(jié)點(diǎn)X的所有鄰居節(jié)點(diǎn),構(gòu)成集合N={n1,n2,…,nx}。

步驟4根據(jù)覆蓋空洞動(dòng)態(tài)檢測(cè)算法計(jì)算出選定節(jié)點(diǎn)X的邊緣節(jié)點(diǎn)、邊緣弧和空洞角,從節(jié)點(diǎn)X的所有鄰居節(jié)點(diǎn)集合N中找出該覆蓋空洞的邊緣節(jié)點(diǎn)。對(duì)這些邊緣節(jié)點(diǎn)繼續(xù)計(jì)算其邊緣端點(diǎn)、邊緣弧和空洞角,以檢測(cè)覆蓋空洞。

步驟5當(dāng)檢測(cè)到覆蓋空洞后,選擇空洞周?chē)哂嘁苿?dòng)節(jié)點(diǎn),根據(jù)移動(dòng)方向和移動(dòng)距離逐個(gè)修復(fù)覆蓋空洞。

步驟6重復(fù)步驟4和步驟5,循環(huán)至覆蓋空洞完全修復(fù)。

步驟7依據(jù)目標(biāo)區(qū)域信息監(jiān)測(cè)要求,判斷整體覆蓋率是否達(dá)標(biāo),若是,轉(zhuǎn)步驟8;否則轉(zhuǎn)步驟4。

步驟8結(jié)束算法。

2.4 算法分析

2.4.1 三維覆蓋率分析

本文目的是通過(guò)修復(fù)三維空間目標(biāo)區(qū)域覆蓋空洞,提高整體網(wǎng)絡(luò)覆蓋率。網(wǎng)絡(luò)覆蓋率可由式(16)計(jì)算得到:

(16)

其中,C(A)為三維空間整體網(wǎng)絡(luò)覆蓋率,P為立方體網(wǎng)格中的任意點(diǎn),m為所有節(jié)點(diǎn)個(gè)數(shù),n為探測(cè)點(diǎn)的個(gè)數(shù),d(si,P)表示節(jié)點(diǎn)si到節(jié)點(diǎn)P的距離,ci(A)為三維空間中任意節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的覆蓋率,cP(si)表示點(diǎn)P處的覆蓋率,0≤cP(si)≤1。在檢測(cè)到覆蓋空洞后,移動(dòng)節(jié)點(diǎn)根據(jù)計(jì)算出的移動(dòng)方向和移動(dòng)距離進(jìn)行覆蓋空洞修復(fù)。移動(dòng)節(jié)點(diǎn)si與覆蓋空洞中心k之間的距離為:

(17)

在實(shí)際移動(dòng)過(guò)程中,移動(dòng)節(jié)點(diǎn)si到覆蓋空洞中心k的距離也會(huì)發(fā)生變化,具體如下:

d(si,k)′=d(si,k)+diri

(18)

由式(18)減去式(17)得到:

(19)

2.4.2 能耗分析

本文算法整體能耗由檢測(cè)網(wǎng)絡(luò)覆蓋空洞、收發(fā)信息和節(jié)點(diǎn)移動(dòng)的能耗組成。設(shè)E1為動(dòng)態(tài)檢測(cè)覆蓋空洞的能耗,E2為節(jié)點(diǎn)收發(fā)信息的能耗,E3為節(jié)點(diǎn)移動(dòng)的能耗,則整體網(wǎng)絡(luò)能耗E的計(jì)算公式為:

E=E1+E2+E3

(20)

設(shè)Ei表示移動(dòng)節(jié)點(diǎn)i移動(dòng)單位距離的能耗,移動(dòng)總能耗E3為:

(21)

3 實(shí)驗(yàn)結(jié)果與分析

3.1 仿真環(huán)境與參數(shù)設(shè)置

為驗(yàn)證本文三維覆蓋空洞動(dòng)態(tài)檢測(cè)與修復(fù)算法在覆蓋效果和能量消耗等方面的性能[20],采用MATLAB2015b軟件進(jìn)行仿真。無(wú)線傳感器網(wǎng)絡(luò)的部署環(huán)境是100 m×100 m×100 m的立方體區(qū)域,初始條件下傳感器節(jié)點(diǎn)隨機(jī)部署,各仿真參數(shù)如表1所示。

表1 仿真參數(shù)設(shè)置

3.2 性能分析

對(duì)本文算法的主要性能進(jìn)行驗(yàn)證分析,在算法運(yùn)行不同次數(shù)時(shí),覆蓋空洞檢測(cè)率隨節(jié)點(diǎn)個(gè)數(shù)變化的曲線關(guān)系如圖6所示。

圖6 覆蓋空洞檢測(cè)率隨節(jié)點(diǎn)個(gè)數(shù)的變化曲線

由圖6可知,當(dāng)傳感器節(jié)點(diǎn)個(gè)數(shù)在0～90內(nèi)變化時(shí),算法執(zhí)行不同迭代次數(shù)時(shí)覆蓋空洞檢測(cè)率相同;當(dāng)節(jié)點(diǎn)個(gè)數(shù)在90～210內(nèi)變化時(shí),算法迭代次數(shù)不同,覆蓋空洞的檢測(cè)率發(fā)生很大變化,迭代次數(shù)為120次和150次時(shí)的覆蓋空洞檢測(cè)率明顯高于迭代次數(shù)為100次時(shí)的檢測(cè)率;當(dāng)節(jié)點(diǎn)個(gè)數(shù)在210～300內(nèi)變化時(shí),3種迭代次數(shù)的空洞檢測(cè)率都在逐步增大。通過(guò)實(shí)驗(yàn)結(jié)果可以看出,當(dāng)節(jié)點(diǎn)個(gè)數(shù)為300個(gè)、迭代次數(shù)為150次時(shí),覆蓋空洞檢測(cè)率達(dá)到92%以上,滿(mǎn)足了整體覆蓋空洞檢測(cè)率要求。

在調(diào)用移動(dòng)節(jié)點(diǎn)對(duì)覆蓋空洞進(jìn)行修復(fù)時(shí),覆蓋空洞修復(fù)率隨算法迭代次數(shù)的變化曲線如圖7所示。

圖7 覆蓋空洞修復(fù)率隨迭代次數(shù)的變化曲線

由圖7可知,在前60次算法迭代時(shí),由于存在大量的冗余節(jié)點(diǎn),3種情況的覆蓋空洞修復(fù)率都在平緩上升,變化幅度不大,其中,移動(dòng)節(jié)點(diǎn)數(shù)目為90個(gè)時(shí)空洞修復(fù)率略高于其他2種情況;在60次～110次迭代時(shí),移動(dòng)節(jié)點(diǎn)個(gè)數(shù)越多,覆蓋空洞修復(fù)率增長(zhǎng)得越快;在110次～150次迭代時(shí),3種情況的修復(fù)率穩(wěn)定增長(zhǎng)。通過(guò)實(shí)驗(yàn)對(duì)比可以看出,當(dāng)算法迭代150次、移動(dòng)節(jié)點(diǎn)數(shù)目為90個(gè)時(shí),可以很好地完成覆蓋空洞修復(fù),從而達(dá)到整體網(wǎng)絡(luò)覆蓋空洞修復(fù)要求。

為了達(dá)到覆蓋要求且節(jié)省成本,需要傳感器網(wǎng)絡(luò)靜態(tài)節(jié)點(diǎn)與動(dòng)態(tài)節(jié)點(diǎn)比例適中。不同移動(dòng)節(jié)點(diǎn)比例時(shí)三維覆蓋率隨節(jié)點(diǎn)個(gè)數(shù)的變化關(guān)系如圖8所示。由圖8可知,當(dāng)傳感器節(jié)點(diǎn)個(gè)數(shù)在200個(gè)以?xún)?nèi)時(shí),隨著節(jié)點(diǎn)個(gè)數(shù)的增加,三維覆蓋率也逐漸增加,但移動(dòng)節(jié)點(diǎn)所占比例對(duì)覆蓋率的影響不夠明顯;當(dāng)節(jié)點(diǎn)個(gè)數(shù)從200個(gè)增加到300個(gè)時(shí),移動(dòng)節(jié)點(diǎn)占比越高,覆蓋率增加得越快;當(dāng)節(jié)點(diǎn)個(gè)數(shù)為300個(gè)、移動(dòng)節(jié)點(diǎn)占比為30%時(shí),三維覆蓋率達(dá)到95%,完成了對(duì)三維目標(biāo)區(qū)域的覆蓋。

圖8 三維覆蓋率隨傳感器節(jié)點(diǎn)個(gè)數(shù)的變化曲線

在整個(gè)網(wǎng)絡(luò)能耗中,最主要的是移動(dòng)節(jié)點(diǎn)的移動(dòng)能耗。在不同移動(dòng)節(jié)點(diǎn)個(gè)數(shù)情況下,每個(gè)移動(dòng)節(jié)點(diǎn)的能耗隨算法迭代次數(shù)的變化曲線如圖9所示。

圖9 節(jié)點(diǎn)能耗隨算法迭代次數(shù)的關(guān)系曲線

由圖9可知,算法迭代前60次時(shí),調(diào)用覆蓋空洞周?chē)哂嘁苿?dòng)節(jié)點(diǎn)修復(fù)覆蓋空洞,節(jié)點(diǎn)移動(dòng)距離大致相同,因此,移動(dòng)節(jié)點(diǎn)的個(gè)數(shù)對(duì)節(jié)點(diǎn)能耗影響不大。隨著算法迭代次數(shù)的增加,越來(lái)越多的空洞被檢測(cè)到,在修復(fù)這些空洞時(shí),需要大量的移動(dòng)節(jié)點(diǎn)移動(dòng)較遠(yuǎn)的距離,因此,每個(gè)節(jié)點(diǎn)能耗增大。通過(guò)實(shí)驗(yàn)對(duì)比可以看出,當(dāng)移動(dòng)節(jié)點(diǎn)個(gè)數(shù)為90個(gè)時(shí),既可以滿(mǎn)足覆蓋要求又可以最大程度地節(jié)省能耗。

3.3 本文算法與相似算法的對(duì)比

為了進(jìn)一步驗(yàn)證本文算法的性能,經(jīng)對(duì)比分析后,選擇三維覆蓋中常用的經(jīng)典粒子群算法(PSO)和文獻(xiàn)[21]中提出的二維平面CPA算法,與本文算法在覆蓋率、移動(dòng)節(jié)點(diǎn)利用率和移動(dòng)能耗等方面進(jìn)行對(duì)比分析。3種算法較為相似,目的都是使用移動(dòng)傳感器節(jié)點(diǎn)對(duì)覆蓋空洞進(jìn)行修復(fù),提高整體網(wǎng)絡(luò)的覆蓋率和連通性,從而更有效地監(jiān)測(cè)目標(biāo)區(qū)域。

圖10所示為3種算法移動(dòng)節(jié)點(diǎn)利用率隨移動(dòng)節(jié)點(diǎn)個(gè)數(shù)的變化關(guān)系曲線。從圖10可以看出,在初始階段,隨著移動(dòng)節(jié)點(diǎn)數(shù)量的增加,逐漸出現(xiàn)節(jié)點(diǎn)冗余現(xiàn)象,3種算法節(jié)點(diǎn)利用率都呈平緩的下降趨勢(shì);當(dāng)移動(dòng)節(jié)點(diǎn)數(shù)量大于25時(shí),PSO算法和CPA算法移動(dòng)節(jié)點(diǎn)利用率出現(xiàn)了大幅下降,而本文算法的節(jié)點(diǎn)利用率則下降比較緩慢;當(dāng)移動(dòng)節(jié)點(diǎn)數(shù)量大于45時(shí),3種算法的移動(dòng)節(jié)點(diǎn)利用率又出現(xiàn)了平穩(wěn)的下降現(xiàn)象;當(dāng)移動(dòng)節(jié)點(diǎn)個(gè)數(shù)為90個(gè)時(shí),完成了對(duì)目標(biāo)覆蓋空洞的最大化覆蓋。本文算法總體的移動(dòng)節(jié)點(diǎn)利用率高于PSO算法和CPA算法,其總體使用節(jié)點(diǎn)更少。

圖10 移動(dòng)節(jié)點(diǎn)利用率隨移動(dòng)節(jié)點(diǎn)個(gè)數(shù)的變化曲線

圖11所示為3種算法覆蓋率隨迭代次數(shù)的變化曲線關(guān)系。從圖11可以看出,在初始階段,隨著算法迭代次數(shù)逐漸增加,覆蓋率也在穩(wěn)步增大,PSO算法的覆蓋率一直略高于其他2種算法;當(dāng)?shù)螖?shù)在50次～70次之間時(shí),3種算法的覆蓋率都出現(xiàn)了明顯的上升波動(dòng),本文算法的覆蓋率超過(guò)了其他2種算法;當(dāng)?shù)螖?shù)在70次～120次之間時(shí),隨著迭代次數(shù)的增加,3種算法的覆蓋率都在穩(wěn)步大幅增加;當(dāng)?shù)螖?shù)達(dá)到150次時(shí),本文算法率先達(dá)到了網(wǎng)絡(luò)整體覆蓋率要求。通過(guò)對(duì)比實(shí)驗(yàn)可以看出,本文算法在相同迭代次數(shù)下可以更快地達(dá)到覆蓋率要求,從而節(jié)省算法運(yùn)行的時(shí)間。

圖11 覆蓋率隨迭代次數(shù)的變化曲線

在整個(gè)無(wú)線傳感器網(wǎng)絡(luò)中,不僅要達(dá)到覆蓋要求,還要節(jié)省網(wǎng)絡(luò)能耗[22]。3種算法的移動(dòng)能耗率隨移動(dòng)節(jié)點(diǎn)個(gè)數(shù)的變化曲線如圖12所示。從圖12可以看出,在0～30個(gè)移動(dòng)節(jié)點(diǎn)范圍內(nèi),移動(dòng)節(jié)點(diǎn)的移動(dòng)距離短,3種算法的移動(dòng)能耗都較小;當(dāng)節(jié)點(diǎn)個(gè)數(shù)在30個(gè)～60個(gè)內(nèi)時(shí),節(jié)點(diǎn)個(gè)數(shù)增加的同時(shí)移動(dòng)距離也在逐漸增多,3種算法的節(jié)點(diǎn)能耗都在增加,但本文算法的節(jié)點(diǎn)能耗明顯低于其他2種算法;當(dāng)節(jié)點(diǎn)個(gè)數(shù)從60個(gè)增加到90個(gè)時(shí),PSO算法節(jié)點(diǎn)移動(dòng)能耗率大幅升高,CPA算法節(jié)點(diǎn)移動(dòng)能耗率次之,本文算法移動(dòng)能耗率較低。因此,本文算法移動(dòng)節(jié)點(diǎn)能耗率相對(duì)較低,其網(wǎng)絡(luò)壽命更長(zhǎng)。

圖12 移動(dòng)能耗率隨移動(dòng)節(jié)點(diǎn)個(gè)數(shù)的變化曲線

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

為了對(duì)三維空間目標(biāo)區(qū)域進(jìn)行有效監(jiān)測(cè),本文提出一種三維覆蓋空洞動(dòng)態(tài)檢測(cè)與修復(fù)算法。通過(guò)采用基于誤警率的聯(lián)合探測(cè)概率模型檢測(cè)每個(gè)立方體網(wǎng)格的覆蓋率,動(dòng)態(tài)檢測(cè)三維部署區(qū)域所有覆蓋空洞并移動(dòng)覆蓋空洞周?chē)娜哂嘁苿?dòng)節(jié)點(diǎn)以修復(fù)覆蓋空洞,從而使目標(biāo)區(qū)域網(wǎng)絡(luò)連通。實(shí)驗(yàn)結(jié)果表明,本文算法可以達(dá)到整體網(wǎng)絡(luò)覆蓋要求,其節(jié)點(diǎn)利用率和覆蓋率等性能優(yōu)于PSO和CPA算法,整體網(wǎng)絡(luò)能耗較低。但本文算法存在移動(dòng)能耗過(guò)高和靈活性較低等不足,下一步將優(yōu)化算法性能以解決移動(dòng)能耗問(wèn)題。