基于移動節(jié)點的無線傳感器網絡覆蓋空洞修復方法

王 珊， 王慶生， 樊茂森

(太原理工大學 計算機科學與技術學院，山西 太原 030024)

基于移動節(jié)點的無線傳感器網絡覆蓋空洞修復方法

王 珊， 王慶生， 樊茂森

(太原理工大學 計算機科學與技術學院，山西 太原 030024)

無線傳感器網絡(WSNs)一旦產生覆蓋空洞，則會嚴重影響網絡性能，針對此問題，提出了一種基于移動節(jié)點的覆蓋空洞修復算法——聯合補丁法，該算法按照預先制定的縫制方案把所需的移動節(jié)點“縫制”成一塊大的“布”，然后對空洞進行直接修復。首先,在理論上證明了該算法的性能;其次,用Matlab進行仿真實驗，并與基于移動節(jié)點的三角形逐個貼片修復算法(PATT)在所需節(jié)點數和冗余度兩方面進行對比；最后，對算法的穩(wěn)定性進行了分析。最終表明：該算法具有較高的覆蓋率和較低的冗余度。

無線傳感器網絡； 空洞修復； 移動節(jié)點

0 引 言

無線傳感器網絡(wireless sensor networks,WSNs)在軍事、防災害、工業(yè)監(jiān)測等眾多領域都有廣泛應用[1]。然而在實際運用中，由于部署不合理、故障、攻擊或能耗不均使得一些節(jié)點提前死亡，導致網絡中產生覆蓋空洞，從而嚴重影響采集數據的完整性，因此,對覆蓋空洞進行修復是保證網絡可靠性的必要手段。

近年來，各專家學者提出了多種覆蓋空洞修復方法[2～6]，總體來說可以分為兩大類，一類是基于仿生智能算法的修復策略，如蔣丹提出的“一種蟻群算法進行空洞修復”[7]，但此方法容易使同一空洞被多個移動節(jié)點發(fā)現，從而導致被重復修復，造成極大浪費；另一類是基于幾何圖形的修復策略，如王良民等人提出的“基于移動節(jié)點的三角形逐個貼片修復方法(PATT)”[8]，該方法雖然具有較高的覆蓋率，但是冗余度同樣較高，這樣移動節(jié)點利用率便會下降。針對此問題，本文提出了一種新的基于幾何圖形的空洞修復方法——聯合補丁法，它在滿足較高覆蓋率的同時，具有較低的節(jié)點冗余度。

1 基本假設

為方便描述和討論，下面做如下假設：

1)本文中所有靜態(tài)節(jié)點和移動節(jié)點都同構，初始能量、數據處理及通信能力均相同。不同之處在于靜態(tài)節(jié)點能量無法得到補充，而移動節(jié)點能量能得到補充，且能在控制下自行移動；

2)傳感器節(jié)點通信距離Rc為感知距離Rs的2倍，即Rc=2Rs；

3)節(jié)點感知范圍是以節(jié)點為圓心，Rs為半徑的圓，并稱之為感知圓[9]；

4)覆蓋率大于90 %的網絡滿足可靠性要求[8]。

2 聯合補丁法

現有的幾何修補方法都是向空洞中逐個添加移動節(jié)點進行修復，在這類方法中，可以認為，每添加一個移動節(jié)點，就相當于在空洞中縫制了一小塊補丁。因此，受上述思維啟發(fā)，本文提出了一種新的空洞修復方法——聯合補丁法，該方法不同之處在于它不是逐個添加移動節(jié)點進行修復的，而是根據空洞形狀把所有“補丁”縫制成一塊大的“布”，然后再把這塊“布”移植到空洞中進行直接修復。然而，這些補丁按何種方式進行縫制能具有較好的性能，以下提出了兩種縫制方案。

2.1 方案一

圖1 方案一

2.2 方案二

圖2 方案二

2.3 算法描述

基于以上兩種方案，下面以方案二為例描述空洞的修復過程：

1)在已被檢測到的空洞多邊形上隨機選取一點Ai，并在此多邊形上求距離Ai最遠的一個點Aj；

2)在線段AiAj之間，從Ai開始，按照方案二中同組節(jié)點的約束條件逐漸生成節(jié)點序列，并稱此序列為基準節(jié)點序列；

3)if(基準序列上方沒有空洞)轉向步驟(5)

Else在基準序列上方生成新的節(jié)點序列，此時該節(jié)點序列仍需滿足方案二的約束條件，并稱此序列為參考節(jié)點序列；

4)if(參考序列上方沒有空洞)轉向步驟(5)

Else 在參考序列上方生成新的參考序列，并轉向步驟(4);

5)if(基準序列下方沒有空洞) 修復完成，退出程序

Else在基準序列下方生成新的參考序列;

6)if(參考序列下方沒有空洞) 修復完成，退出程序

Else 在參考序列下方生成新的參考序列，并轉向步驟(6)。

注：算法中所有基準序列與參考序列之間、參考序列與參考序列之間均需滿足方案二的約束條件。

3 算法性能分析

本節(jié)對算法的性能進行驗證[10]。利用Matlab 2010搭建實驗平臺，針對修復同樣面積的空洞所用移動節(jié)點數和冗余度進行實驗，并與PATT進行對比，同時對本算法的穩(wěn)定性進行了分析。為簡化實驗，把空洞形狀模擬成邊長為L的正方形(這樣便于生成基準節(jié)點序列和參考節(jié)點序列)，并假設移動節(jié)點感知半徑為1 m，通信半徑為2 m。

3.1 覆蓋度分析

圖3給出了修復不同空洞面積和所需移動節(jié)點數的關系。由圖可以看出:隨著空洞面積的增加，方案一和方案二所用移動節(jié)點數目明顯少于PATT，同時方案一少于方案二，且隨著空洞面積的增長，這種趨勢越來越明顯。因此,本算法所需節(jié)點數較少。

圖3 空洞面積和所需節(jié)點個數關系圖

3.2 冗余度分析

由圖4所示的冗余度關系圖可以看出:隨著空洞面積的增加，方案一和方案二的冗余度呈下降趨勢，而PATT呈上升趨勢。方案一冗余度沒有達到1，是因為該方案不能對空洞進行全覆蓋，但由上一節(jié)證明可知，其覆蓋率達到90 %以上，故滿足有效性要求。同時，該方案在進行空洞修復時，只有小片的盲區(qū)分散在網絡中，不會出現大片空洞，因此，對一些覆蓋率要求不太高的網絡，此方案為最佳。

圖4 空洞面積與冗余度關系圖

而在全覆蓋的情況下，可以看出PATT冗余度最終穩(wěn)定在1.45左右，而方案二穩(wěn)定在1.25左右，減少了約0.25，即移動節(jié)點利用率提高了17.24 %，因此,對于覆蓋率要求較高的網絡，方案二具有較好性能。

3.3 穩(wěn)定性分析

由圖3可以看出:方案一、方案二和PATT一樣，隨著空洞面積的增加，所用節(jié)點數目呈線性增長趨勢，這說明本算法具有很好的穩(wěn)定性，即不會隨著空洞面積大小的變化呈現劇烈波動。

同時，由圖4的冗余度分析圖可以看出：當空洞面積較小時，兩種方案冗余度波動均較大，但隨著面積不斷增加，當達到1 000 m2時，兩種方案開始收斂，最終穩(wěn)定在一定數值之間，這同樣也說明了本算法具有很好的收斂穩(wěn)定性。

4 結 論

本文采用移動節(jié)點進行空洞修復，提出了一種新的算法——聯合補丁法，并設計了兩種補丁縫制方案，分析了其性能，隨后對這兩種方案進行了仿真實驗，并與傳統的PATT進行了對比分析，通過分析可知，本算法可根據實際需要靈活選擇修復方案，且所需移動節(jié)點數較少，同時具有較高的節(jié)點覆蓋率和較小的冗余度，因此,該方法是一種性能較好的算法。

[1] 毛曉峰，楊 珉，毛迪林.無線傳感器網絡應用綜述[J].計算機應用與軟件，2008,25(3):179-181.

[2] 包 旭,巨永鋒. 面向節(jié)點失效的無線傳感器網絡覆蓋空洞修復算法[J].計算機測量與控制,2011,19(6):1516-1522.

[3] 楊 凱. 無線傳感器網絡中覆蓋空洞的修復算法研究[D].蘇州:蘇州大學,2012.

[4] 錢志鴻,王義君. 面向物聯網的無線傳感器網絡綜述[J].電子與信息學報,2013,35(1):215-227.

[5] Wang G,Cao G,Porta T. Movement-assisted sensor deployment[J]. IEEE Transaction on Mobile Computing,2006,5(6):640-652.

[6] Hwa chun,Prasan Kumar Sahoo,Chen Yenwen. Computational geometry based distributed coverage hole detection protocol in wireless sensor networks [J]. Journal of Network and Computer Applications,2011,34(5):1743-1756.

[7] 蔣 丹. 無線傳感器網絡覆蓋盲區(qū)的發(fā)現與修復方法研究[D].沈陽:東北大學,2008.

[8] 王良民,李 菲,秦 穎. 基于移動節(jié)點的無線傳感器網絡覆蓋空洞修復方法[J]. 通信學報,2011,32(4):1-8.

[9] 樊茂森,王慶生. 一種基于移動節(jié)點的無線傳感器網絡修復方法[J]. 傳感器與微系統,2013,32(9):25-27.

[10] Ali Q I,Abdulmaowjod. Simulation and performance study of wireless sensor networks using Matlab[J]. Energy,Power and Control,2011,7(2):112-119.

Repairing method for coverage hole of WSNs

based on mobile node WANG Shan, WANG Qing-sheng, FAN Mao-sen

(College of Computer Science and Technology，Taiyuan University of Technology,Taiyuan 030024,China)

Once coverage holes appeared in wireless sensor networks(WSNs),performance of network will be severely affected. Aiming at this problem,“joint patch method”, a kind of coverage hole repairing algorithm based on mobile nodes is proposed.This algorithm “sews” all the needed mobile nodes into a large “cloth” ,according to the sewing program,which is pre-established,and then repair the hole directly. Firstly,performance of the algorithm is proved theoretically,and then by using Matlab simulation;both of the number of nodes required and redundancy are compared with PATT algorithms;finally,stability of the algorithm is analyzed. Eventually,it shows that this algorithm has a higher coverage rate and lower redundancy.

wireless sensor networks(WSNs); hole repairing; mobile node

2014—08—05

10.13873/J.1000—9787(2015)04—0134—03

TP 393

A

1000—9787(2015)04—0134—03

王 珊(1989-)，女，山西臨汾人，碩士研究生，主要研究領域為無線傳感器網絡。