一種WSN三維覆蓋空洞動態檢測與修復算法

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

(1.西北師范大學 計算機科學與工程學院,蘭州 730070; 2.甘肅省物聯網工程研究中心,蘭州 730070)

0 概述

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

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

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

1 三維空間覆蓋模型及相關定義

1.1 三維空間覆蓋的優化問題描述

在對三維空間目標區域進行覆蓋時,將普通節點和移動節點混合后隨機部署在目標區域,但隨機部署會出現節點分布不均勻的問題。為了達到三維空間目標區域的覆蓋要求,需要對傳感器網絡中存在的覆蓋空洞進行動態檢測與修復,以提高網絡覆蓋率,實現對三維空間目標區域的有效監測。

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

圖1 三維覆蓋區域劃分示意圖

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

1)靜態節點和移動節點構成混合傳感器網絡。

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

1.2 三維空間覆蓋模型建立

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

(1)

假定整個環境網絡具有高斯白噪聲,信號在傳播過程中按固定的損耗因子γ和傳播因子衰減,信號傳播損耗與1/rγ成比例關系,γ的值由環境因素決定[13]。信號在室內自由傳播時,γ通常為2或4。假設所有節點均具有相同的能量etr,對于節點i,從目標節點所接收的能量為:

(2)

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

(3)

在M1狀態下,目標經過的行程2r=2Dti。因此,對于第i個傳感器,M1狀態下的探測概率為:

(4)

同理,在M0狀態下的探測概率為:

(5)

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

(6)

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

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

定義2(三維聯合探測概率) 在三維空間目標監測區域中,任意一個立方體網格被有效覆蓋的概率是多個傳感器節點共同作用的效果,因此,整個網絡對任意一個立方體網格的聯合探測概率Uk(P)可定義為:

(7)

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

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

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

定義5(移動節點利用率) 在隨機部署的混合傳感器網絡中,靜態節點和移動節點按一定比例混合,其中移動節點具有移動性,其主要作用是用來修復網絡的覆蓋空洞,但部分移動節點也會充當靜態節點。修復覆蓋空洞的移動節點數與總移動節點數的比值稱為移動節點利用率。

2 三維覆蓋空洞的動態檢測與修復算法

2.1 三維空間覆蓋空洞描述

在三維立體空間隨機部署節點時,由于外部因素的限制,網絡中會出現覆蓋空洞[14]。空洞是由周圍多個節點形成的一個閉合空間,如圖2所示,周圍節點之間也存在覆蓋冗余。感知節點1與覆蓋空洞有2個邊界端點W和S,即覆蓋空洞邊緣端點。設覆蓋空洞周圍有n個邊緣節點,Vi表示節點i感知范圍的體積大小,Vh表示覆蓋空洞的體積大小。

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

2.2 三維空間覆蓋空洞動態檢測

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

(8)

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

(9)

節點N與節點M對應的邊緣端點由式(10)表示:

(10)

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

當檢測到立方體網格中存在覆蓋空洞時,算法調用覆蓋空洞周圍的冗余移動節點修復覆蓋空洞。根據計算所得的移動方向和移動距離在三維空間中移動節點。首先確定移動節點的移動方向,在被檢測到的覆蓋空洞周圍冗余節點中隨機選擇一個移動節點,并標記為P,該移動節點P與覆蓋空洞邊緣所形成的關聯點為Pa和Pb,其中,節點P、關聯點Pa和Pb的坐標分別為(x,y,z)、(x1,y1,z1)和(x2,y2,z2)。

通過構造三維空間坐標向量來確定移動節點P的移動方向,如式(11)所示:

(11)

由三維空間向量公式可知,通過構造三維空間向量的方法就可以確定所選移動節點P的移動方向。在構造向量Vr的過程中,會出現圖3所示的2種情況,即假設向量Va和Vb的夾角為θ,則θ存在2種可能:θ<π和θ>π。當θ<π時,節點移動的方向為正確方向;當θ>π時,節點移動的方向為向量Vr的反方向;當θ=π時,節點不發生移動。

圖3 節點移動方向判斷示例

為了使所選移動節點完成對覆蓋空洞的修復,首先確定移動節點的移動方向,然后通過節點移動后的位置與先前鄰居節點的距離來確定節點的移動距離。同時,當節點移動到最優位置時需要考慮2個問題,一是保證移動節點移動后不會造成新的覆蓋空洞,二是適當地選擇移動節點的個數以免造成過度的覆蓋冗余[18]。

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

(12)

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

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

(13)

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

(14)

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

(15)

圖4 移動距離計算示意圖

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

2.3 算法描述

本文三維覆蓋空洞動態檢測與修復算法流程如圖5所示。

圖5 三維覆蓋空洞動態檢測與修復算法流程

算法步驟具體如下:

步驟1初始化N個混合傳感器節點,并對三維空間目標區域進行立方體網格劃分。

步驟2設置感知模型的誤警率參數,采用聯合探測概率模型探測每個立方體網格的覆蓋率。

步驟3在每個立方體網格中隨機選擇一個傳感器節點X,其坐標為(x,y,z),找出節點X的所有鄰居節點,構成集合N={n1,n2,…,nx}。

步驟4根據覆蓋空洞動態檢測算法計算出選定節點X的邊緣節點、邊緣弧和空洞角,從節點X的所有鄰居節點集合N中找出該覆蓋空洞的邊緣節點。對這些邊緣節點繼續計算其邊緣端點、邊緣弧和空洞角,以檢測覆蓋空洞。

步驟5當檢測到覆蓋空洞后,選擇空洞周圍冗余移動節點,根據移動方向和移動距離逐個修復覆蓋空洞。

步驟6重復步驟4和步驟5,循環至覆蓋空洞完全修復。

步驟7依據目標區域信息監測要求,判斷整體覆蓋率是否達標,若是,轉步驟8;否則轉步驟4。

步驟8結束算法。

2.4 算法分析

2.4.1 三維覆蓋率分析

本文目的是通過修復三維空間目標區域覆蓋空洞,提高整體網絡覆蓋率。網絡覆蓋率可由式(16)計算得到:

(16)

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

(17)

在實際移動過程中,移動節點si到覆蓋空洞中心k的距離也會發生變化,具體如下:

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

(18)

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

(19)

2.4.2 能耗分析

本文算法整體能耗由檢測網絡覆蓋空洞、收發信息和節點移動的能耗組成。設E1為動態檢測覆蓋空洞的能耗,E2為節點收發信息的能耗,E3為節點移動的能耗,則整體網絡能耗E的計算公式為:

E=E1+E2+E3

(20)

設Ei表示移動節點i移動單位距離的能耗,移動總能耗E3為:

(21)

3 實驗結果與分析

3.1 仿真環境與參數設置

為驗證本文三維覆蓋空洞動態檢測與修復算法在覆蓋效果和能量消耗等方面的性能[20],采用MATLAB2015b軟件進行仿真。無線傳感器網絡的部署環境是100 m×100 m×100 m的立方體區域,初始條件下傳感器節點隨機部署,各仿真參數如表1所示。

表1 仿真參數設置

3.2 性能分析

對本文算法的主要性能進行驗證分析,在算法運行不同次數時,覆蓋空洞檢測率隨節點個數變化的曲線關系如圖6所示。

圖6 覆蓋空洞檢測率隨節點個數的變化曲線

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

在調用移動節點對覆蓋空洞進行修復時,覆蓋空洞修復率隨算法迭代次數的變化曲線如圖7所示。

圖7 覆蓋空洞修復率隨迭代次數的變化曲線

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

為了達到覆蓋要求且節省成本,需要傳感器網絡靜態節點與動態節點比例適中。不同移動節點比例時三維覆蓋率隨節點個數的變化關系如圖8所示。由圖8可知,當傳感器節點個數在200個以內時,隨著節點個數的增加,三維覆蓋率也逐漸增加,但移動節點所占比例對覆蓋率的影響不夠明顯;當節點個數從200個增加到300個時,移動節點占比越高,覆蓋率增加得越快;當節點個數為300個、移動節點占比為30%時,三維覆蓋率達到95%,完成了對三維目標區域的覆蓋。

圖8 三維覆蓋率隨傳感器節點個數的變化曲線

在整個網絡能耗中,最主要的是移動節點的移動能耗。在不同移動節點個數情況下,每個移動節點的能耗隨算法迭代次數的變化曲線如圖9所示。

圖9 節點能耗隨算法迭代次數的關系曲線

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

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

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

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

圖10 移動節點利用率隨移動節點個數的變化曲線

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

圖11 覆蓋率隨迭代次數的變化曲線

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

圖12 移動能耗率隨移動節點個數的變化曲線

4 結束語

為了對三維空間目標區域進行有效監測,本文提出一種三維覆蓋空洞動態檢測與修復算法。通過采用基于誤警率的聯合探測概率模型檢測每個立方體網格的覆蓋率,動態檢測三維部署區域所有覆蓋空洞并移動覆蓋空洞周圍的冗余移動節點以修復覆蓋空洞,從而使目標區域網絡連通。實驗結果表明,本文算法可以達到整體網絡覆蓋要求,其節點利用率和覆蓋率等性能優于PSO和CPA算法,整體網絡能耗較低。但本文算法存在移動能耗過高和靈活性較低等不足,下一步將優化算法性能以解決移動能耗問題。