王 珊， 王慶生， 樊茂森

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

基于移動節(jié)點的無線傳感器網(wǎng)絡(luò)覆蓋空洞修復(fù)方法

王 珊， 王慶生， 樊茂森

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

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

無線傳感器網(wǎng)絡(luò)； 空洞修復(fù)； 移動節(jié)點

0 引 言

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

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

1 基本假設(shè)

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

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

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

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

4)覆蓋率大于90 %的網(wǎng)絡(luò)滿足可靠性要求[8]。

2 聯(lián)合補丁法

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

2.1 方案一

圖1 方案一

2.2 方案二

圖2 方案二

2.3 算法描述

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

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

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

3)if(基準(zhǔn)序列上方?jīng)]有空洞)轉(zhuǎn)向步驟(5)

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

4)if(參考序列上方?jīng)]有空洞)轉(zhuǎn)向步驟(5)

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

5)if(基準(zhǔn)序列下方?jīng)]有空洞) 修復(fù)完成，退出程序

Else在基準(zhǔn)序列下方生成新的參考序列;

6)if(參考序列下方?jīng)]有空洞) 修復(fù)完成，退出程序

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

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

3 算法性能分析

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

3.1 覆蓋度分析

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

圖3 空洞面積和所需節(jié)點個數(shù)關(guān)系圖

3.2 冗余度分析

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

圖4 空洞面積與冗余度關(guān)系圖

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

3.3 穩(wěn)定性分析

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

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

4 結(jié) 論

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

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

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

[3] 楊 凱. 無線傳感器網(wǎng)絡(luò)中覆蓋空洞的修復(fù)算法研究[D].蘇州:蘇州大學(xué),2012.

[4] 錢志鴻,王義君. 面向物聯(lián)網(wǎng)的無線傳感器網(wǎng)絡(luò)綜述[J].電子與信息學(xué)報,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] 蔣 丹. 無線傳感器網(wǎng)絡(luò)覆蓋盲區(qū)的發(fā)現(xiàn)與修復(fù)方法研究[D].沈陽:東北大學(xué),2008.

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

[9] 樊茂森,王慶生. 一種基于移動節(jié)點的無線傳感器網(wǎng)絡(luò)修復(fù)方法[J]. 傳感器與微系統(tǒng),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-)，女，山西臨汾人，碩士研究生，主要研究領(lǐng)域為無線傳感器網(wǎng)絡(luò)。