基于節(jié)點移動的WSNs覆蓋空洞修復(fù)算法

黃 祎

(重慶電子工程職業(yè)學院 通信工程學院， 重慶 401331)

無線傳感網(wǎng)絡(luò)(Wireless Sensor Networks,WSNs)已在各類應(yīng)用中廣泛使用，如森林火災(zāi)檢測、戰(zhàn)場偵察、入侵檢測、目標跟蹤以及健康康復(fù)[1-2]。這些應(yīng)用要求對感測區(qū)域具有足夠的覆蓋率。若有些區(qū)域未能覆蓋，就無法收集該區(qū)域數(shù)據(jù)，降低應(yīng)用性能。因此，感測覆蓋率也是檢測這些應(yīng)用性能的重要指標。

通常，以隨機或預(yù)定方式在檢測區(qū)域(Region of Interest,ROI)部署傳感節(jié)點。部署后，一旦傳感節(jié)點失效，就無法感測環(huán)境數(shù)據(jù)，便留下未覆蓋的區(qū)域，即形成覆蓋空洞問題[3]。而節(jié)點硬件故障、能耗殆盡均會引起節(jié)點失效。由于傳感節(jié)點隨時可能失效，網(wǎng)絡(luò)內(nèi)的任何一個區(qū)域均可能會出現(xiàn)覆蓋空洞。因此，覆蓋空洞是WSNs一個不可避免的現(xiàn)象[4]。

覆蓋空洞不但留下未覆蓋空白區(qū)域，也分裂了網(wǎng)絡(luò)，這影響了數(shù)據(jù)傳輸?shù)牧鲿承浴Ｒ虼?，需要引用機制[5]，使感測區(qū)域能夠被連續(xù)覆蓋。

然而，WSNs常部署于人難以進入或無法直接接入的區(qū)域，這就給維持網(wǎng)絡(luò)連通和覆蓋率提出了挑戰(zhàn)。此外，如何預(yù)測何時何區(qū)域發(fā)生了覆蓋空洞也是一個挑戰(zhàn)問題。因此，設(shè)計一個動態(tài)檢測、修復(fù)覆蓋空洞的機制十分重要[6]。

為此，提出了一個基于節(jié)點移動的覆蓋空洞的修復(fù) (Moving Node-based Coverage Hole Repair,MNCHR) 算法。MNCHR算法依據(jù)節(jié)點剩余能量、移動距離和相互重疊區(qū)域信息，尋找最合適的修復(fù)節(jié)點。通過修復(fù)節(jié)點的移動，覆蓋空洞區(qū)域，減少鄰居節(jié)點間的覆蓋重疊區(qū)域，進而滿足區(qū)域覆蓋率。

1 網(wǎng)絡(luò)模型及問題描述

1.1 網(wǎng)絡(luò)模型

假定在網(wǎng)絡(luò)區(qū)域內(nèi)有n個移動節(jié)點，且S={s1,s2,…,sn}隨機分布于二維區(qū)域。區(qū)域內(nèi)的信宿節(jié)點不受能量限制。n個移動節(jié)點自行組織并形成網(wǎng)絡(luò)，進而保證興趣區(qū)域被最大化覆蓋[7-8]。此外，每個移動節(jié)點si∈S具有感測、存儲數(shù)據(jù)的能力，并且能夠與其他節(jié)點進行通信。

此外，每個傳感節(jié)點si∈S具有6維信息si=[id,rs,rc,L,E,N],其中id為節(jié)點唯一標號，而rs是感測半徑，rc是通信半徑，而L表示節(jié)點的當前位置，E為節(jié)點的當前能量，N為節(jié)點的鄰居節(jié)點集。每個傳感節(jié)點能通過GPS或其他定位算法[9]獲取自己的位置。同時，節(jié)點的通信半徑是節(jié)點感測半徑的兩倍(rc=2rs)，致使任意兩個有相互重疊感測區(qū)域的節(jié)點能夠相互通信。

1.2 問題描述

由于節(jié)點的能耗、硬件故障等原因，節(jié)點可能會失效，形成覆蓋空洞問題。而以隨機方式部署傳感節(jié)點，容易形成節(jié)點的重疊區(qū)域覆蓋，這就為修復(fù)覆蓋空洞提供了條件，即可利用重疊覆蓋區(qū)域修復(fù)覆蓋區(qū)域。

如圖1(a)所示，灰色表示由多個節(jié)點的覆蓋區(qū)域，而空白區(qū)域表示未覆蓋的區(qū)域，即覆蓋空洞。虛線表示失效節(jié)點的位置，而實線表示修復(fù)節(jié)點的位置。圖1(b)、圖1(c)顯示了利用節(jié)點的移動修復(fù)覆蓋空洞的過程。

圖1 覆蓋空洞的修復(fù)過程

如圖1所示，一旦形成覆蓋空洞，就選擇覆蓋空洞周圍的節(jié)點作為修復(fù)節(jié)點，并通過節(jié)點移動，修復(fù)覆蓋空洞。因此，這主要涉及兩個問題：1)如何選擇修復(fù)節(jié)點；2)修復(fù)節(jié)點移動距離。

2 MNCHR算法

MNCHR算法由3個階段構(gòu)成。其中第一個階段就是計算移動距離，即修復(fù)覆蓋空洞所需移動的距離；第二階段就是計算節(jié)點的冗余率；第三個階段就是選擇最合適的修復(fù)節(jié)點。

2.1 移動距離

為了修復(fù)覆蓋空洞，修復(fù)節(jié)點需要尋找最優(yōu)的移動距離以及目標位置。因此，每個節(jié)點計算需要移動的距離,再通過些距離來選擇最合適的修復(fù)節(jié)點。

每個節(jié)點計算它與覆蓋空洞區(qū)域交叉點的位置。交叉點一定是成對出現(xiàn)的，因此，只選擇其中一個節(jié)點用來計算此距離。將離覆蓋空洞最近的那個點的坐標位置保存，另一個點丟棄。所有鄰居節(jié)點通過分享自己的交叉點，如圖2(a)所示。因此，若自己成為修復(fù)節(jié)點，節(jié)點就計算所需的移動距離d，即：

(1)

式(1)中，(xi,yi)表示傳感節(jié)點si與覆蓋空洞區(qū)域交叉點的位置坐標；(xp,yp)為最遠的交叉點位置坐標，如圖2(b)所示。

圖2 交叉點及移動距離示意圖

2.2 覆蓋冗余

由兩個或兩個以上的節(jié)點同時覆蓋的區(qū)域稱為覆蓋冗余。節(jié)點覆蓋冗余等于覆蓋重疊區(qū)域與整個覆蓋區(qū)域面積之比。節(jié)點的覆蓋冗余是用來測量節(jié)點的感測區(qū)域的利用率。冗余率越高，節(jié)點利用率越低。

為了計算節(jié)點的覆蓋冗余，首先得計算節(jié)點與其鄰居節(jié)點的覆蓋重疊區(qū)域。為了尋找重疊區(qū)域，先計算每兩個交叉圓重疊區(qū)域Atwo。

假定兩個圓，半徑分別為r1、r2，并且這兩個圓中心的相距距離為d，則這兩個圓的重疊區(qū)域為Atwo[8]：

(2)

然而，在實際環(huán)境中，可能有三個圓共同重疊，即三個鄰居同時覆蓋同一區(qū)域。因此，必須要計算三個節(jié)點共同覆蓋的區(qū)域Athree。假定三個圓(C1,C2,C3)，且三個圓的半徑相同(節(jié)點感測半徑相同)。這三個圓發(fā)生共同重疊有二種情況，如圖3所示。

圖3 三個圓發(fā)生共同重疊的情況

圖3(a)描述了三個圓共同重疊的區(qū)域為兩個圓的重疊區(qū)域，而圖3(b)的共同重疊區(qū)域為三角形區(qū)域。要區(qū)分這兩種,首先，尋找任意一對圓的交叉點，然后，每一對圓，檢測交叉點是否位于第三圓內(nèi)。如果沒有位于第三個圓內(nèi)，就屬于圖3(b)情況。如果全部落在第三個圓內(nèi)，則屬于圖3(a)情況。

如圖4所示，三個圓所形成的覆蓋區(qū)域可近似為三角形。因此，可利用三角形計算理論，估計覆蓋區(qū)域。依據(jù)Heron公式，可計算三角形Atriangle為：

(3)

式(3)中，s=0.5(a+b+c)，而a、b、c分別為三個交叉點的相互距離。

圖4 三角形覆蓋區(qū)域

因此，三個圓的共同覆蓋區(qū)域Athree可表示為：

(4)

算法1總結(jié)計算冗余區(qū)域的過程，其中C1、C2和C3分別表示三個圓。首先，計算交叉點，然后，再判斷這些交叉點是否落在第三個圓內(nèi)。最后，再通過式(2)和式(4)計算冗余區(qū)域。算法1的偽代碼如圖5所示。

利用式(4)和式(2)，可計算覆蓋冗余R，其等于任意兩個圓的重疊面積與由三個圓的重疊面積之差，與節(jié)點的感測面積之比，即：

(5)

圖5 算法1的偽代碼

2.3 修復(fù)節(jié)點的選擇

本小節(jié)分析選擇修復(fù)節(jié)點的具體過程。先定義權(quán)值ρ，其定義為：

(6)

式(6)中，E為節(jié)點的剩余能量。

每個節(jié)點計算權(quán)值ρ，將自己的ρ值傳輸至鄰居節(jié)點。具有最大ρ值的節(jié)點作為修復(fù)節(jié)點。從式(6)可知，R越大，即冗余率越大的節(jié)點，成為修復(fù)節(jié)點的概率也越大。將冗余率大的節(jié)點選為修復(fù)節(jié)點，這使得此節(jié)點移動后，不會形成新的覆蓋空洞。

此外，盡可能地選擇剩余能量大的節(jié)點作為修復(fù)節(jié)點，避免了因移動而導致能量過早耗盡。同時，選擇移動距離d小的節(jié)點作為修復(fù)節(jié)點，這利于減少因移動而產(chǎn)生的能耗。

整個過程如圖6所示。先獲取失效節(jié)點sidle坐標和鄰居節(jié)點集。再計算相關(guān)的交叉點，并將交叉點傳輸至鄰居節(jié)點。隨后，再從鄰居節(jié)點收集交叉點信息，并依據(jù)這些信息確認空洞區(qū)域。

依據(jù)式(1)計算移動距離d，如圖6的Step3。并依據(jù)式(6)計算式權(quán)值ρ，如圖6的Step6。再將此值傳輸至鄰居節(jié)點。再從鄰居節(jié)點中選擇具有最大ρ值的節(jié)點作為修復(fù)節(jié)點s′，并由s′移動距離d后到達目標位置，如Step7。

圖6 算法2的偽代碼

3 性能分析

3.1 仿真平臺

利用MATLAB R2105a建立仿真平臺，且90個傳感節(jié)點隨機分布于300 m×300 m方形區(qū)域。假定這些傳感節(jié)點的感測半徑rs=25 m、通信半徑rc=50 m。傳感節(jié)點的初始能量不同，能量在1～100 J范圍內(nèi)隨機設(shè)定。此外，節(jié)點每移動1 m消耗1 J。

為了更好地分析MNCHR算法的性能，選擇基于最小懶惰距離(Minimum Distance Lazy,MDL)[10]算法、基于自模糊邏輯空洞覆蓋 (Fuzzy-based self-healing coverage,FSHC)[11]算法以及Center[12]算法作為參照，并與算法MNCHR進行比較。MDL算法通過節(jié)點的移動距離指標選擇修復(fù)節(jié)點，并完成覆蓋空洞。而FSHC算法利用模糊邏輯系統(tǒng)選擇修復(fù)節(jié)點。這些算法都是以修復(fù)空洞區(qū)域為目的，但采用的策略不同。

同時，選擇覆蓋率、總移動距離以及能量消耗作為性能指標。每次實驗獨立重復(fù)20次，取平均值作為最終仿真數(shù)據(jù)。

3.2 仿真結(jié)果

3.2.1覆蓋率

首先考查覆蓋率隨網(wǎng)絡(luò)內(nèi)失效節(jié)點數(shù)的變化情況，實驗數(shù)據(jù)如圖7所示。此外，圖7也繪制了靜態(tài)節(jié)點環(huán)境下的覆蓋率，即節(jié)點失效后，節(jié)點不移動，即對覆蓋不進行修復(fù)。

圖7 覆蓋率

從圖7可知，MDL算法的覆蓋率逼近于靜態(tài)節(jié)點環(huán)境，原因在于：MDL算法對節(jié)點移動有嚴格的限制。而FSHC算法的覆蓋率略好于MDL算法，但其覆蓋率仍較低，這主要是因為FSHC算法只是讓節(jié)點隨機移動去修復(fù)覆蓋空洞。與MDL、FSHC算法相比，MNCHR算法的覆蓋率得到有效地提高，這在于MNCHR算法充分利用節(jié)點能量信息以及移動距離，選擇最合適的修復(fù)節(jié)點，使得修復(fù)節(jié)點在修復(fù)空洞時，不影響原有的覆蓋區(qū)域，即不會出現(xiàn)“拆東墻，補西墻”的現(xiàn)象。

3.2.2移動距離

圖8顯示了各算法的在修復(fù)覆蓋空洞時所移動的距離。顯然，移動的距離越短，越利于保存能量，但是短的移動距離可能也意味著空洞修復(fù)的質(zhì)量越差。因為移動的距離反映了能耗與覆蓋增益間的折衷。

圖8 移動距離隨失效節(jié)點的變化情況

從圖8可知，MDL移動的距離最少，原因在于：MDL算法是通過移動最少距離來保存節(jié)點能量。而MNCHR算法和FSHC算法所移動的所有距離相近，但MNCHR算法保持較好的覆蓋率。當一個節(jié)點失效，MNCHR算法就移動距離，致使能通過移動此距離來彌補因節(jié)點移動而產(chǎn)生的覆蓋空洞。與Center算法相比，MNCHR算法移動得少、保存了更多的能量，修復(fù)了更多的覆蓋空洞。

3.2.3能量消耗及修復(fù)的空洞區(qū)域

圖9顯示了各算法的能耗。從圖9可知，MNCHR算法允許節(jié)點快速移動，因此，MNCHR算法比MDL算法消耗了更多的能量。而圖10顯示能量消耗更多用于修復(fù)覆蓋空洞。MDL算法最多修復(fù)了10%的空洞區(qū)域，F(xiàn)SHC算法修復(fù)了50%，而MNCHR算法幾乎修復(fù)了70%的空洞區(qū)域。

圖9 能耗

圖9和圖10的實驗數(shù)據(jù)表明：MDL算法的嚴格能量限制導致低的覆蓋空洞修復(fù)，而MNCHR算法和FSHC算法在修復(fù)空洞時消耗了更多能量。換而言之，它們是以能量為代價，滿足覆蓋率的要求。

圖10 修復(fù)的空洞率

4 結(jié)論

針對無線傳感網(wǎng)絡(luò)內(nèi)因節(jié)點失效而引用的覆蓋空洞問題，提出了基于節(jié)點移動的覆蓋空洞修復(fù)算法MNCHR。MNCHR算法利用失效節(jié)點的一跳鄰居節(jié)點信息，并利用這些節(jié)點的剩余能量、覆蓋冗余以及移動距離選擇最優(yōu)的修復(fù)節(jié)點。通過修復(fù)節(jié)點的移動，實現(xiàn)對覆蓋空洞的修復(fù)。

仿真數(shù)據(jù)表明，提出的MNCHR算法能夠有效地修復(fù)空洞區(qū)域。然而，相比于同類算法，盡管在修復(fù)空洞區(qū)域方面有較大的提高，但是其是以消耗更多能量為代價的。后期，將優(yōu)化算法，降低能耗。