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

黃 祎

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

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

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

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

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

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

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

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

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

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

1.2 問題描述

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

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

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

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

2 MNCHR算法

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

2.1 移動距離

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

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

(1)

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

圖2 交叉點(diǎn)及移動距離示意圖

2.2 覆蓋冗余

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

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

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

(2)

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

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

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

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

(3)

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

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

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

(4)

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

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

(5)

圖5 算法1的偽代碼

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

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

(6)

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

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

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

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

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

圖6 算法2的偽代碼

3 性能分析

3.1 仿真平臺

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

為了更好地分析MNCHR算法的性能，選擇基于最小懶惰距離(Minimum Distance Lazy,MDL)[10]算法、基于自模糊邏輯空洞覆蓋 (Fuzzy-based self-healing coverage,FSHC)[11]算法以及Center[12]算法作為參照，并與算法MNCHR進(jìn)行比較。MDL算法通過節(jié)點(diǎn)的移動距離指標(biāo)選擇修復(fù)節(jié)點(diǎn)，并完成覆蓋空洞。而FSHC算法利用模糊邏輯系統(tǒng)選擇修復(fù)節(jié)點(diǎn)。這些算法都是以修復(fù)空洞區(qū)域?yàn)槟康模捎玫牟呗圆煌?/p>

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

3.2 仿真結(jié)果

3.2.1覆蓋率

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

圖7 覆蓋率

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

3.2.2移動距離

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

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

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

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

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

圖9 能耗

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

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

4 結(jié)論

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

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