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

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

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

0 概述

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

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

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

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

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

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

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

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

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

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

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

1.2 三維空間覆蓋模型建立

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

(1)

假定整個環(huán)境網(wǎng)絡(luò)具有高斯白噪聲,信號在傳播過程中按固定的損耗因子γ和傳播因子衰減,信號傳播損耗與1/rγ成比例關(guān)系,γ的值由環(huán)境因素決定[13]。信號在室內(nèi)自由傳播時,γ通常為2或4。假設(shè)所有節(jié)點(diǎn)均具有相同的能量etr,對于節(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)過的行程2r=2Dti。因此,對于第i個傳感器,M1狀態(tài)下的探測概率為:

(4)

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

(5)

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

(6)

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

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

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

(7)

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

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

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

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

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

2.1 三維空間覆蓋空洞描述

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

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

2.2 三維空間覆蓋空洞動態(tài)檢測

針對覆蓋空洞檢測問題,本文建立三維空間覆蓋模型,提出一種三維覆蓋空洞動態(tài)檢測與修復(fù)算法。假設(shè)立方體網(wǎng)格中任意一個節(jié)點(diǎn)M是覆蓋空洞的邊緣節(jié)點(diǎn),為了檢測該覆蓋空洞,需要根據(jù)邊緣節(jié)點(diǎn)M找到構(gòu)成該覆蓋空洞的所有邊緣節(jié)點(diǎn),并計算覆蓋空洞的邊緣弧和邊緣端點(diǎn)[15]。隨機(jī)選取2個相鄰節(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對應(yīng)的邊緣端點(diǎn)由式(10)表示:

(10)

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

當(dāng)檢測到立方體網(wǎng)格中存在覆蓋空洞時,算法調(diào)用覆蓋空洞周圍的冗余移動節(jié)點(diǎn)修復(fù)覆蓋空洞。根據(jù)計算所得的移動方向和移動距離在三維空間中移動節(jié)點(diǎn)。首先確定移動節(jié)點(diǎn)的移動方向,在被檢測到的覆蓋空洞周圍冗余節(jié)點(diǎn)中隨機(jī)選擇一個移動節(jié)點(diǎn),并標(biāo)記為P,該移動節(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)。

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

(11)

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

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

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

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

(12)

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

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

(13)

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

(14)

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

(15)

圖4 移動距離計算示意圖

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

2.3 算法描述

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

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

算法步驟具體如下:

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

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

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

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

步驟5當(dāng)檢測到覆蓋空洞后,選擇空洞周圍冗余移動節(jié)點(diǎn),根據(jù)移動方向和移動距離逐個修復(fù)覆蓋空洞。

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

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

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

2.4 算法分析

2.4.1 三維覆蓋率分析

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

(16)

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

(17)

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

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

(18)

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

(19)

2.4.2 能耗分析

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

E=E1+E2+E3

(20)

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

(21)

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

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

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

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

3.2 性能分析

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

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

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

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

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

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

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

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

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

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

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

3.3 本文算法與相似算法的對比

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

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

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

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

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

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

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

4 結(jié)束語

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