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

黃 祎

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

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

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

覆蓋空洞不但留下未覆蓋空白區(qū)域，也分裂了網(wǎng)絡(luò)，這影響了數(shù)據(jù)傳輸?shù)牧鲿承浴Ｒ虼耍枰脵C(jī)制[5]，使感測(cè)區(qū)域能夠被連續(xù)覆蓋。

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

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

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

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

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

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

1.2 問(wèn)題描述

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

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

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

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

2 MNCHR算法

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

2.1 移動(dòng)距離

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

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

2.2 覆蓋冗余

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

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

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

(2)

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

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

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

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

(3)

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

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

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

(4)

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

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

(5)

圖5 算法1的偽代碼

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

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

(6)

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

每個(gè)節(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)移動(dòng)后，不會(huì)形成新的覆蓋空洞。

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

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

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

圖6 算法2的偽代碼

3 性能分析

3.1 仿真平臺(tái)

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

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

同時(shí)，選擇覆蓋率、總移動(dòng)距離以及能量消耗作為性能指標(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)不移動(dòng)，即對(duì)覆蓋不進(jìn)行修復(fù)。

圖7 覆蓋率

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

3.2.2移動(dòng)距離

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

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

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

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

圖9顯示了各算法的能耗。從圖9可知，MNCHR算法允許節(jié)點(diǎn)快速移動(dòng)，因此，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ù)空洞時(shí)消耗了更多能量。換而言之，它們是以能量為代價(jià)，滿足覆蓋率的要求。

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

4 結(jié)論

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

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