曾雅麗 趙福雙

無線傳感器網(wǎng)絡(luò)覆蓋空洞修復(fù)策略

曾雅麗 趙福雙

隨著通信技術(shù)的發(fā)展，傳感器網(wǎng)絡(luò)給人們帶來了越來越多的便利。當(dāng)傳感器網(wǎng)絡(luò)中隨意一個節(jié)點因它自帶的電能消耗盡或者監(jiān)測的目標(biāo)區(qū)域環(huán)境被破壞而失去通信功能，可能導(dǎo)致網(wǎng)絡(luò)出現(xiàn)覆蓋空洞而無法通信。覆蓋空洞會使鄰居節(jié)點能耗速度加快而死亡，使得無線傳感器網(wǎng)絡(luò)的覆蓋質(zhì)量和通信效果變得不好，只有采用有效方案修復(fù)覆蓋空洞或?qū)W(wǎng)絡(luò)重新部署，才能提高網(wǎng)絡(luò)資源利用和延長網(wǎng)絡(luò)使用時間。

無線傳感器網(wǎng)絡(luò)是由大量傳感器節(jié)點構(gòu)成的無線網(wǎng)絡(luò)，其構(gòu)成方式是以自組織和多跳的方式，其任務(wù)為在網(wǎng)絡(luò)覆蓋區(qū)域中的收集到的數(shù)據(jù)信息發(fā)送給數(shù)據(jù)使用者就是終端用戶如圖1。傳感器網(wǎng)絡(luò)節(jié)點操控的數(shù)據(jù)在行經(jīng)其他節(jié)點逐跳傳達(dá)，在傳達(dá)的過程中數(shù)據(jù)或許會被節(jié)點處理過，經(jīng)過很多跳到匯聚節(jié)點最后通過互聯(lián)網(wǎng)或移動通信網(wǎng)絡(luò)到達(dá)具有管理功能的節(jié)點，終端用戶用管理節(jié)點就可以操控網(wǎng)絡(luò)，全程的關(guān)鍵問題是對目標(biāo)監(jiān)測區(qū)域?qū)崿F(xiàn)覆蓋。

移動傳感器網(wǎng)絡(luò)是由在需要采集信息的地方散開的可以移動的節(jié)點構(gòu)成，可以根據(jù)節(jié)點準(zhǔn)確的感知條件以及其通信功能實現(xiàn)節(jié)點的動態(tài)分布。與傳統(tǒng)的靜態(tài)傳感器網(wǎng)絡(luò)相比，擁有移動能力的傳感器網(wǎng)絡(luò)有覆蓋面積更大、對數(shù)據(jù)的反應(yīng)速度快、獲取信息可靠性較高等特點?，F(xiàn)在靜態(tài)的傳感器網(wǎng)絡(luò)有很多不足，例如獲取信息的能力不強(qiáng)、對巨大的數(shù)據(jù)不能進(jìn)行處理、無法快速勘測目標(biāo)監(jiān)測區(qū)域環(huán)境特征等等。

研究及發(fā)展概況

圖1　無線傳感器網(wǎng)絡(luò)圖

傳感器節(jié)點在能量耗盡時可能會導(dǎo)致網(wǎng)絡(luò)產(chǎn)生覆蓋空洞。覆蓋空洞的存在會使空洞邊緣節(jié)點的能量消耗增加，節(jié)點死亡的速度增加，導(dǎo)致網(wǎng)絡(luò)覆蓋質(zhì)量下降以及節(jié)點之間連通性降低，這樣一來整個網(wǎng)絡(luò)都會失去通信功能不能傳輸信息了，但仍然還有大很多節(jié)點沒有被使用到。

在大部分靜態(tài)傳感器網(wǎng)絡(luò)中使需要采集信息的地方每個節(jié)點對象都被k（k≥1）個節(jié)點覆蓋，多重覆蓋使得許多節(jié)點在能量消耗結(jié)束不起作用后，網(wǎng)絡(luò)仍然能保證需要采集信息地區(qū)的網(wǎng)絡(luò)密度，這樣的話在惡劣的條件下傳感器網(wǎng)絡(luò)能提高它的生命力。但是很多節(jié)點在同一時間都作用一個目標(biāo)節(jié)點這會浪費節(jié)點的數(shù)量浪費成本。文獻(xiàn)選擇了空洞邊緣節(jié)點數(shù)目很多的冗余節(jié)點進(jìn)行激活來修復(fù)覆蓋空洞，但該算法在一方面沒有周全考慮冗余節(jié)點的利用效率，另一方面忽略了多重覆蓋會形成很多經(jīng)濟(jì)損失。

移動節(jié)點用時最少算法

算法概述

針對覆蓋空洞可以采取移動冗余節(jié)點進(jìn)行修復(fù)，但移動的過程中會有能量的消耗，怎樣移動才能達(dá)到減少能耗又能修復(fù)空洞的目的？結(jié)合最小生成樹的思想提出了用時最少的算法，該算法的中心思想是當(dāng)探測到無線傳感器網(wǎng)絡(luò)中存在覆蓋空洞，選取一個空洞邊緣節(jié)點作為移動節(jié)點，移動一個邊緣節(jié)點到空洞范圍內(nèi)的網(wǎng)絡(luò)節(jié)點位置上，采取激活它能獲取信息的范圍距離內(nèi)位置信息最好的冗余節(jié)點進(jìn)行修復(fù)覆蓋空洞。

圖2　閉合空洞圖

問題描述

主要考慮已經(jīng)探測到無線傳感器網(wǎng)絡(luò)中覆蓋空洞大小及位置信息情況下，怎么喚醒冗余節(jié)點進(jìn)行覆蓋空洞修復(fù)。在圖2，節(jié)A-H以及節(jié)點M都是空洞邊緣節(jié)點，相互鄰接成閉合空洞區(qū)域，圖中紅色節(jié)點M為可移動節(jié)點，利用可移動節(jié)點行經(jīng)空洞中喚醒其通信范圍內(nèi)的冗余節(jié)點，根據(jù)可移動節(jié)點M的行走的路徑可以隨機(jī)選擇則可產(chǎn)生最優(yōu)的路徑，使得其修復(fù)時間最短。

存在如下兩種情況如圖3。

1.當(dāng)移動節(jié)點M移動到覆蓋空洞中網(wǎng)絡(luò)節(jié)點位置時，冗余節(jié)點在其通信范圍內(nèi)，則可將其喚醒。

2.當(dāng)移動節(jié)點M移動到覆蓋空洞中網(wǎng)絡(luò)節(jié)點位置時，冗余節(jié)點不在其通信范圍內(nèi)，即冗余節(jié)點在其通信范圍以外，在這樣的情況下查找其附近具有通信功能的冗余節(jié)點，計算出移動節(jié)點與能通信的冗余節(jié)點之間的距離選擇合適的位置重新部署一個具有通信功能的節(jié)點，使得兩網(wǎng)絡(luò)節(jié)點間能相互通信。如圖4，移動節(jié)點M移動到節(jié)點1的位置，冗余節(jié)點2不在其通信范圍內(nèi)，節(jié)點3為其附近具有通信功能的節(jié)點，節(jié)點N是節(jié)點1與節(jié)點3距離之間選取的合適位置，部署的新節(jié)點N的通信半徑為R，達(dá)到喚醒節(jié)點3且使得網(wǎng)絡(luò)能夠相互通信的目的。圓1與圓3與圓N的交點分別為a，b。

圖3　移動節(jié)點分類圖

圖4　喚醒節(jié)點圖

圖5　Kruskal算法步驟圖

算法描述

（1）最小生成樹Kruskal算法過程如圖5。

（2）最小生成樹Prim算法過程如圖6。

實驗驗證算法的優(yōu)勢

我們分別對三種算法進(jìn)行對比：最小生成樹Kruskal算法，最小生成樹Prim算法以及普通移動節(jié)點算法。對比結(jié)果如表1。

圖6　Prim算法步驟圖

表1　三種算法權(quán)重值圖

如表1隨著隨機(jī)產(chǎn)生節(jié)點數(shù)的不同，采用Kruskal，Prim兩種算法所得權(quán)重相等也就意味著采用兩種進(jìn)行修復(fù)所移動的距離是相同的，但都比普通算法所移動的距離少，即達(dá)到減少移動節(jié)點移動的距離來節(jié)約能量進(jìn)行修復(fù)空洞的目標(biāo)。在此過程中需要考慮時間因素，因為在移動相同距離，速度相同的情況下，只有時間最少的才能決定哪個算法更優(yōu)，因為節(jié)點在移動的過程中會消耗能量，移動的時間越少能量消耗越少，使用減少時間達(dá)到更優(yōu)修復(fù)空洞的目的。分析兩種的時間復(fù)雜度可知，Prim算法的時間復(fù)雜度為O（n2），Kruskal算法的時間復(fù)雜度為O（eloge）（e為邊的數(shù)量），綜合來說Kruskal算法比較適合邊數(shù)較少的時候，Prim算法比較適合邊數(shù)較多的時候，也就是說在節(jié)點較多時最佳選擇是Prim算法。

結(jié)束語

針對覆蓋空洞問題提出移動節(jié)點喚醒冗余節(jié)點的方法來進(jìn)行修復(fù)，采用兩種算法進(jìn)行對比，在不同情況下采取最優(yōu)的方法進(jìn)行修復(fù)。

10.3969/j.issn.1001-8972.2015.09.021