王 珊， 王慶生， 樊茂森

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

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

王 珊， 王慶生， 樊茂森

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

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

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

0 引 言

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

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

1 基本假設(shè)

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

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

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

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

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

2 聯(lián)合補(bǔ)丁法

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

2.1 方案一

圖1 方案一

2.2 方案二

圖2 方案二

2.3 算法描述

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

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

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

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

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

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)序列與參考序列之間、參考序列與參考序列之間均需滿(mǎn)足方案二的約束條件。

3 算法性能分析

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

3.1 覆蓋度分析

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

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

3.2 冗余度分析

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

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

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

3.3 穩(wěn)定性分析

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

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

4 結(jié) 論

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

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

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

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

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

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

[9] 樊茂森,王慶生. 一種基于移動(dòng)節(jié)點(diǎn)的無(wú)線(xiàn)傳感器網(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)域?yàn)闊o(wú)線(xiàn)傳感器網(wǎng)絡(luò)。