無線傳感器網絡覆蓋漏洞發現與修補算法綜述

楊莉莉

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

關鍵詞： 無線傳感器網絡； 覆蓋漏洞； 發現算法； 修補算法

中圖分類號：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 引言

無線傳感器網絡（Wireless Sensor Networks， WSNs）由無數個微型傳感器節點組成，并且每個傳感器節點能夠感知周圍環境，能夠實時監控感知區域內特定事件的發生[1]。伴隨著微電子技術、傳感器技術、信息處理等技術的不斷發展，傳感器節點制造成本不斷降低，無線傳感器網絡迅速發展，其正被廣泛應用于現代農業、智能建筑、交通運輸、森林防火等各個領域[2]。而服務質量（Quality of Service， QoS）體現了無線傳感器網絡感知現實世界的能力，是對監測區域的覆蓋程度衡量的一項重要指標[3]。

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

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

1 傳感器網絡特點

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

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

⑵ 為了能夠獲得被監測區域內的詳細數據信息，無線傳感器節點往往被大量部署在檢測區域內，具有較高的部署密度。

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

⑷ 節點的發射功率有限，其通信范圍也很小，通常只能夠與其相鄰節點通信。如果節點想要與其覆蓋區域外的節點進行通信，必須借助其相鄰節點進行轉發。

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

2 覆蓋發現算法分析

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

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

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

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

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

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

3 覆蓋修補算法分析

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

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

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

4 結束語

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

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

參考文獻（References）：

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

[2] 包旭，巨永鋒.面向節點失效的無線傳感器網絡覆蓋空洞修復算法[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] 凡高娟，王汝傳，黃海平.基于容忍覆蓋區域的無線傳感器網絡節點調度算法[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的無線傳感器網絡覆蓋空洞檢測算法[J].計算機應用，2015.35（3）：620-623

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

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