楊莉莉

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

[2] 包旭，巨永鋒.面向節(jié)點失效的無線傳感器網(wǎng)絡(luò)覆蓋空洞修復(fù)算法[J].計算機(jī)測量與控制，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ǎng)絡(luò)節(jié)點調(diào)度算法[J].電子學(xué)報，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] 戴國勇，陳麓屹，周斌彬等.基于Voronoi的無線傳感器網(wǎng)絡(luò)覆蓋空洞檢測算法[J].計算機(jī)應(yīng)用，2015.35（3）：620-623

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

[11] 吳昊然.GPS和無線傳感器網(wǎng)絡(luò)融合定位算法研究[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ò)中無需地理信息的空洞填補(bǔ)算法[J].計算機(jī)學(xué)報，2009.32（10）：1957-1970