楊莉莉

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 覆蓋修補算法分析

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

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

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

4 結(jié)束語

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

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

參考文獻（References）：

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

[2] 包旭，巨永鋒.面向節(jié)點失效的無線傳感器網(wǎng)絡覆蓋空洞修復算法[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)絡節(jié)點調(diào)度算法[J].電子學報，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)絡覆蓋空洞檢測算法[J].計算機應用，2015.35（3）：620-623

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

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