無(wú)線傳感器網(wǎng)絡(luò)覆蓋漏洞發(fā)現(xiàn)與修補(bǔ)算法綜述

楊莉莉

摘 要： 無(wú)線傳感器網(wǎng)絡(luò)因其能檢監(jiān)測(cè)目標(biāo)區(qū)域特定事件的發(fā)生，而被廣泛應(yīng)用到軍事國(guó)防、交通運(yùn)輸、智能家居等各個(gè)領(lǐng)域。無(wú)線傳感器節(jié)點(diǎn)通常是有電池供電，具有能量有限、難補(bǔ)給的特點(diǎn)，容易導(dǎo)致節(jié)點(diǎn)死亡，造成監(jiān)測(cè)區(qū)域內(nèi)出現(xiàn)監(jiān)測(cè)覆蓋漏洞的出現(xiàn)。為了保證傳感器網(wǎng)絡(luò)的覆蓋率，發(fā)現(xiàn)監(jiān)測(cè)區(qū)域內(nèi)的覆蓋漏洞并進(jìn)行修補(bǔ)，就需要有效的覆蓋漏洞發(fā)現(xiàn)和修補(bǔ)算法。文章詳細(xì)描述了幾種發(fā)現(xiàn)和修補(bǔ)覆蓋漏洞的算法，并對(duì)算法做了相應(yīng)的分析。

關(guān)鍵詞： 無(wú)線傳感器網(wǎng)絡(luò)； 覆蓋漏洞； 發(fā)現(xiàn)算法； 修補(bǔ)算法

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2017）05-34-03

The survey of discovery and repair algorithm for wireless sensor networks coverage holes

Yang Lili

（College of Computer and Information Engineering， Henan University， Kaifeng， Henan 475004， China）

Abstract： Wireless sensor networks are widely used in military defense， transportation， intelligent home and other fields because of its ability to detect the occurring of specific events in the target area. However， the wireless sensor nodes are usually battery-powered， and have the characteristics of limited energy and difficult to supply， which can lead to the death of the nodes， resulting in the emergence of coverage holes in the monitoring area. In order to ensure the coverage of the wireless sensor networks， to find the coverage holes in the monitoring area and repair them， the effective algorithms for finding and repairing are needed. This paper describes several coverage holes discovery algorithms and repair algorithms， and makes the corresponding analysis of them.

Key words： wireless sensor networks； coverage holes； discovery algorithm； repair algorithm

0 引言

無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks， WSNs）由無(wú)數(shù)個(gè)微型傳感器節(jié)點(diǎn)組成，并且每個(gè)傳感器節(jié)點(diǎn)能夠感知周圍環(huán)境，能夠?qū)崟r(shí)監(jiān)控感知區(qū)域內(nèi)特定事件的發(fā)生[1]。伴隨著微電子技術(shù)、傳感器技術(shù)、信息處理等技術(shù)的不斷發(fā)展，傳感器節(jié)點(diǎn)制造成本不斷降低，無(wú)線傳感器網(wǎng)絡(luò)迅速發(fā)展，其正被廣泛應(yīng)用于現(xiàn)代農(nóng)業(yè)、智能建筑、交通運(yùn)輸、森林防火等各個(gè)領(lǐng)域[2]。而服務(wù)質(zhì)量（Quality of Service， QoS）體現(xiàn)了無(wú)線傳感器網(wǎng)絡(luò)感知現(xiàn)實(shí)世界的能力，是對(duì)監(jiān)測(cè)區(qū)域的覆蓋程度衡量的一項(xiàng)重要指標(biāo)[3]。

傳感器網(wǎng)絡(luò)覆蓋漏洞是指監(jiān)測(cè)區(qū)域中存在一片連續(xù)未被任何節(jié)點(diǎn)所覆蓋的區(qū)域。而無(wú)線傳感器節(jié)點(diǎn)的能量通常都是由電池提供，具有能量有限、難補(bǔ)給的特點(diǎn)，同時(shí)無(wú)線傳感器網(wǎng)絡(luò)往往被部署在人難以到達(dá)的復(fù)雜區(qū)域。節(jié)點(diǎn)能量耗盡導(dǎo)致傳感器節(jié)點(diǎn)死亡使傳感器網(wǎng)絡(luò)中產(chǎn)生不被監(jiān)測(cè)的覆蓋漏洞出現(xiàn)。

而為了保證網(wǎng)絡(luò)的服務(wù)質(zhì)量往往部署節(jié)點(diǎn)數(shù)量大大超過(guò)實(shí)際需求，但是這種高密度的大量部署節(jié)點(diǎn)同時(shí)工作時(shí)會(huì)導(dǎo)致采集信息冗余、通信沖突等問(wèn)題，反而縮短了網(wǎng)絡(luò)生存時(shí)間[4]。因此對(duì)無(wú)線傳感器網(wǎng)絡(luò)覆蓋漏洞的發(fā)現(xiàn)和修補(bǔ)成為新的研究熱點(diǎn)。而無(wú)線傳感器網(wǎng)絡(luò)覆蓋漏洞的發(fā)現(xiàn)既是覆蓋漏洞修補(bǔ)的前提，又是覆蓋漏洞研究的難點(diǎn)。

1 傳感器網(wǎng)絡(luò)特點(diǎn)

無(wú)線傳感器網(wǎng)絡(luò)通過(guò)在環(huán)境中部署大量節(jié)點(diǎn)來(lái)實(shí)現(xiàn)對(duì)物理現(xiàn)實(shí)世界感知的能力，是物理世界和信息世界溝通的橋梁，一般由傳感器節(jié)點(diǎn)、感知對(duì)象、觀察者構(gòu)成。大量的傳感器節(jié)點(diǎn)被部署在檢測(cè)區(qū)域內(nèi)通過(guò)自組織的方式構(gòu)成無(wú)線傳感器網(wǎng)絡(luò)。無(wú)線傳感器網(wǎng)絡(luò)被部署在惡劣環(huán)境與常見(jiàn)的無(wú)線網(wǎng)絡(luò)（如：無(wú)線局域網(wǎng)、Ad hoc網(wǎng)絡(luò)）相比，無(wú)線傳感器網(wǎng)絡(luò)具有以下顯著特點(diǎn)。

⑴ 傳感器節(jié)點(diǎn)受體積、成本的影響，其計(jì)算能力和存儲(chǔ)能力都有限；節(jié)點(diǎn)受實(shí)際應(yīng)用環(huán)境的影響，往往是由電池提供電力，通常能量有限、不易補(bǔ)給。

⑵ 為了能夠獲得被監(jiān)測(cè)區(qū)域內(nèi)的詳細(xì)數(shù)據(jù)信息，無(wú)線傳感器節(jié)點(diǎn)往往被大量部署在檢測(cè)區(qū)域內(nèi)，具有較高的部署密度。

⑶ 傳感器網(wǎng)絡(luò)沒(méi)有嚴(yán)格的控制中心，所有節(jié)點(diǎn)地位平等，節(jié)點(diǎn)能夠自己決定是否加入自組織成網(wǎng)絡(luò)，具有較強(qiáng)的動(dòng)態(tài)性。

⑷ 節(jié)點(diǎn)的發(fā)射功率有限，其通信范圍也很小，通常只能夠與其相鄰節(jié)點(diǎn)通信。如果節(jié)點(diǎn)想要與其覆蓋區(qū)域外的節(jié)點(diǎn)進(jìn)行通信，必須借助其相鄰節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)。

無(wú)線傳感器網(wǎng)絡(luò)的特點(diǎn)導(dǎo)致部署在惡劣環(huán)境中的節(jié)點(diǎn)常常因?yàn)樽陨碓蚧蜃匀粸?zāi)害等各種隨機(jī)因素造成的物理設(shè)備損壞或軟件故障，從而導(dǎo)致傳感器節(jié)點(diǎn)失去監(jiān)測(cè)周圍環(huán)境的能力，致使覆蓋網(wǎng)絡(luò)受損出現(xiàn)覆蓋漏洞。

2 覆蓋發(fā)現(xiàn)算法分析

為了保證無(wú)線傳感器網(wǎng)絡(luò)的覆蓋率，需要對(duì)覆蓋漏洞的進(jìn)行發(fā)現(xiàn)，同時(shí)覆蓋漏洞的發(fā)現(xiàn)是實(shí)現(xiàn)覆蓋漏洞修補(bǔ)的基礎(chǔ)與前提。而對(duì)傳感器網(wǎng)絡(luò)覆蓋漏洞的發(fā)現(xiàn)算法主要分為三個(gè)方面的研究。

第一類研究主要是在保證一定的覆蓋率時(shí)用概率計(jì)算的方法來(lái)計(jì)算節(jié)點(diǎn)密度。這些研究通常假設(shè)傳感器節(jié)點(diǎn)均勻分布，計(jì)算所需的傳感器密度滿足覆蓋和網(wǎng)絡(luò)壽命要求[5-6]，但是這些研究并不能完全解決覆蓋漏洞檢測(cè)問(wèn)題。

第二類關(guān)于覆蓋漏洞發(fā)現(xiàn)的研究主要是用幾何計(jì)算的方法來(lái)實(shí)現(xiàn)漏洞檢測(cè)。文獻(xiàn)[7-9]等基于幾何學(xué)中的Voronoi圖和Delaunary三角形原理，提出了不同的覆蓋漏洞探測(cè)方法。戴國(guó)勇[10]通過(guò)計(jì)算Voronoi區(qū)域內(nèi)節(jié)點(diǎn)到該區(qū)域的頂點(diǎn)和邊的距離，來(lái)判斷是否存在覆蓋漏洞，評(píng)估節(jié)點(diǎn)密度、節(jié)點(diǎn)感知半徑不同時(shí)對(duì)算法的空洞檢測(cè)時(shí)間和能量消耗的影響，并且比典型的路徑密度（Path Destiny， PD）在空洞檢測(cè)時(shí)間和能量消耗有一定提升。而趙春江[11]在檢測(cè)到覆蓋漏洞的同時(shí)，能夠較準(zhǔn)確的計(jì)算出覆蓋漏洞的面積，找出最佳漏洞修復(fù)位置，部署較少節(jié)點(diǎn)的同時(shí)保證網(wǎng)絡(luò)的連通性。

第三類研究主要是在保證覆蓋要求的前提下，提出拓?fù)淇刂平鉀Q方案，通過(guò)調(diào)度最大限度地提高傳感器網(wǎng)絡(luò)的生命時(shí)間。文獻(xiàn)[4]作者結(jié)合移動(dòng) Agent 的特點(diǎn)， 提出了一種基于移動(dòng)Agent的無(wú)線傳感器網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)機(jī)制，該拓?fù)浒l(fā)現(xiàn)機(jī)制相對(duì)于當(dāng)前存在的拓?fù)浒l(fā)現(xiàn)算法具有很好的穩(wěn)定性和良好的節(jié)能效果。

以上幾類對(duì)應(yīng)無(wú)線傳感器網(wǎng)絡(luò)覆蓋漏洞發(fā)現(xiàn)算法的研究，都是在無(wú)線傳感器節(jié)點(diǎn)的位置信息已知的條件下進(jìn)行的。而節(jié)點(diǎn)的地理位置信息的獲取主要依靠全球定位系統(tǒng)（Global Positioning System，GPS）定位設(shè)備[11]。采用GPS裝置不僅會(huì)增加傳感器網(wǎng)絡(luò)的運(yùn)行成本，在衛(wèi)星信號(hào)被干擾或無(wú)法達(dá)到的區(qū)域（如深水環(huán)境、地下深井），傳感器節(jié)點(diǎn)將無(wú)法獲取到精確的地理位置信息。隨著研究的深入，Gao[12]首次提出了在沒(méi)有地理位置信息的條件下實(shí)現(xiàn)對(duì)空洞邊緣的確定方法，并在不同的空洞形狀條件下實(shí)現(xiàn)了空洞邊緣節(jié)點(diǎn)的確定。

研究發(fā)現(xiàn)，一個(gè)傳感器不相鄰覆蓋洞只有當(dāng)其感應(yīng)邊界被它的鄰居節(jié)點(diǎn)完全由覆蓋，繼而提出了“傳感器邊界”的概念。Bejerano[13]等借助傳感器邊界的概念提出循環(huán)邊界序列獲得各節(jié)點(diǎn)與其相鄰節(jié)點(diǎn)的邊界信息，判斷各個(gè)節(jié)點(diǎn)是否被完全覆蓋，并且將傳感器覆蓋的概念擴(kuò)展到k（k>1）層覆蓋，實(shí)現(xiàn)了覆蓋區(qū)域k-覆蓋的漏洞的發(fā)現(xiàn)，進(jìn)一步提升了覆蓋網(wǎng)絡(luò)的可靠性。在文獻(xiàn)[14]中，作者提出分布式覆蓋無(wú)線傳感器網(wǎng)絡(luò)的覆蓋漏洞恢復(fù)算法設(shè)計(jì)使用矢量方法來(lái)決定幅度和方向。并且，以自組織的方式通過(guò)移動(dòng)節(jié)點(diǎn)來(lái)修復(fù)網(wǎng)絡(luò)的覆蓋漏洞。為了使節(jié)點(diǎn)的移動(dòng)過(guò)程能量消耗最小，算法設(shè)計(jì)為移動(dòng)性僅限于節(jié)點(diǎn)的一跳內(nèi)，并且節(jié)點(diǎn)的最高k覆蓋之后不增加其移動(dòng)性。該覆蓋漏洞恢復(fù)算法顯示在其通信范圍內(nèi)移動(dòng)節(jié)點(diǎn)有可能百分之百實(shí)現(xiàn)覆蓋恢復(fù)。

3 覆蓋修補(bǔ)算法分析

在覆蓋漏洞填補(bǔ)方面，很多方法都假定傳感器節(jié)點(diǎn)擁有精確的地理位置信息，在缺乏地理位置信息的條件下，現(xiàn)有的空洞填補(bǔ)算法都將失去作用。對(duì)于傳感器網(wǎng)絡(luò)，通常通過(guò)放置節(jié)點(diǎn)裝備GPS定位設(shè)備或者通過(guò)設(shè)置信標(biāo)節(jié)點(diǎn)來(lái)獲得節(jié)點(diǎn)的粗略的地理位置，但是這些裝置的使用都存在一定的限制。

在已提到的文獻(xiàn)[11]中，采用幾何圖形向量方法對(duì)節(jié)點(diǎn)感知范圍和Voronoi多邊形的位置特性相結(jié)合的理論分析方法，該方法引入部署傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)來(lái)降低覆蓋空洞大小。一些算法采用網(wǎng)格覆蓋的方式對(duì)傳感器網(wǎng)絡(luò)目標(biāo)區(qū)域進(jìn)行劃分，將部署密度高的區(qū)域中的傳感器節(jié)點(diǎn)逐步移動(dòng)到部署密度低的區(qū)域來(lái)保證網(wǎng)絡(luò)的覆蓋率。蘇瀚在Bejerano的空洞探測(cè)算法的基礎(chǔ)上，提出了傳感器網(wǎng)絡(luò)中空洞填補(bǔ)的兩個(gè)準(zhǔn)則，即：①填補(bǔ)節(jié)點(diǎn)的引入至少消除一段空洞邊緣?。虎谔钛a(bǔ)節(jié)點(diǎn)的引入不能造成空洞的分裂。該算法將空洞填補(bǔ)工作分布到空洞邊緣節(jié)點(diǎn)上分別執(zhí)行，并最終實(shí)現(xiàn)分布式的空洞填補(bǔ)。

現(xiàn)有的空洞填補(bǔ)算法雖然都在一定假設(shè)條件下達(dá)到了一定的效果，但都依賴于精確地理位置信息。因此，對(duì)于未知地理位置信息的傳感器網(wǎng)絡(luò)中覆蓋漏洞的監(jiān)測(cè)成為無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用發(fā)展的新的研究方向。

4 結(jié)束語(yǔ)

無(wú)線傳感器網(wǎng)絡(luò)由無(wú)數(shù)傳感器節(jié)點(diǎn)組成，具有感知物理世界的能力，被廣泛應(yīng)用于各個(gè)生產(chǎn)、生活領(lǐng)域。但是無(wú)線傳感器節(jié)點(diǎn)的能量有限導(dǎo)致節(jié)點(diǎn)失去監(jiān)測(cè)能力，使無(wú)線傳感器網(wǎng)絡(luò)出現(xiàn)未被監(jiān)測(cè)的覆蓋漏洞。

本文介紹了無(wú)線傳感器網(wǎng)絡(luò)的特點(diǎn)以及導(dǎo)致覆蓋漏洞出現(xiàn)的原因。針對(duì)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)位置信息是否已知的兩種前提下，詳細(xì)介紹了幾種傳感器網(wǎng)絡(luò)覆蓋漏洞發(fā)現(xiàn)算法，以及節(jié)點(diǎn)的位置信息已知時(shí)，覆蓋漏洞的修復(fù)算法，并且對(duì)其進(jìn)行了分析。而節(jié)點(diǎn)的地理位置信息未知是傳感器網(wǎng)絡(luò)覆蓋漏洞修補(bǔ)的重要挑戰(zhàn)，也是無(wú)線傳感器網(wǎng)絡(luò)的新的研究方向。

參考文獻(xiàn)（References）：

[1] 鄧鑫，張樂(lè)君.無(wú)線傳感器網(wǎng)絡(luò)可生存性增強(qiáng)技術(shù)研究概述[J].傳感器與微系統(tǒng)，2014.33（1）：1-4

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

[3] Xiao-heng Deng， Chu-gui Xu， Fu-yao Zhao， et al. Repair policies of coverage holes based dynamic node activation in wireless sensor networks[C]. In Proc. of the 2010 IEEE/IFIP International Conference on Embedded and Ubiquitous Computing.

[4] 凡高娟，王汝傳，黃海平.基于容忍覆蓋區(qū)域的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度算法[J].電子學(xué)報(bào)，2011.39（1）：89-94

[5] S. Shakkottai， R. Srikant， N. Shroff. Unreliable sensor grids： Coverage， connectivity and diameter[C]. In Proc. of IEEE Infocom'03，April 2003.

[6] S. Kumar， T. H. Lai， J. Balogh. On k-Coverage in a Mostly Sleeping Sensor Network[C]. In Proc. of ACM Mobicom'04， Sep. 2004.

[7] Fang Q， Gao J， Guibas L J. Locating and bypassing routingholes in sensor networks[C]. In Proc. of IEEE INFOCOM，2004.4（2）：2458-2468

[8] Wang G， Cao G， Porta T L. Movement-Assisted Sensor Deployment[J].IEEE Transactions on Mobile Computing，2006.5（6）：640-652

[9] 戴國(guó)勇，陳麓屹，周斌彬等.基于Voronoi的無(wú)線傳感器網(wǎng)絡(luò)覆蓋空洞檢測(cè)算法[J].計(jì)算機(jī)應(yīng)用，2015.35（3）：620-623

[10] 趙春江，吳華瑞，劉強(qiáng)，朱麗.基于Voronoi的無(wú)線傳感器網(wǎng)絡(luò)覆蓋控制優(yōu)化策略[J].軟件通信，2013.34（9）：115-122

[11] 吳昊然.GPS和無(wú)線傳感器網(wǎng)絡(luò)融合定位算法研究[J].計(jì)算機(jī)仿真，2009.26（11）：145-148

[12] Gao J ，Lederer S， Wang Y. Connectivity-based localization of large scale sensor networks with complex shape[J]. ACM Transactions on Sensor Networks （TOSN），2009.5（4）：789-797

[13] Yigal Bejerano. Coverage Verification without Location Information[J]. IEEE Transactions on Mobile Computing，2012.11（4）：631-643

[14] Prasan Kumar Sahoo， Jang-zern Tsai，Hong-lin ke.Vector method based coverage hole recovery in wireless sensor networks[C]. International Conference on Communication Systems & Networks，2010：1-9

[15] 蘇瀚，汪蕓.傳感器網(wǎng)絡(luò)中無(wú)需地理信息的空洞填補(bǔ)算法[J].計(jì)算機(jī)學(xué)報(bào)，2009.32（10）：1957-1970