無線傳感器網絡覆蓋空洞修復算法綜述

田曉光

(河南大學計算機與信息工程學院，河南 開封 475000)

0　引言

無線傳感器網絡（WirelessSensor Networks,WSN）對人類的生活和生產方式帶來巨大的變革，被認為是21世紀最重要的技術之一。無線傳感器網絡由微機電系統的支持發展而來，是一種分布式傳感網絡，其具有大規模、動態性、自組織、以數據為中心等特點，被廣泛應用于軍事國防、醫療健康、智能家居等各個方面[1]。覆蓋質量是無線傳感器網絡應用中最重要的問題。評價傳感器網絡覆蓋質量的一個重要指標是節點覆蓋率[2]，如果節點覆蓋率過低會導致網絡中出現覆蓋空洞，造成數據監測不準確，更為嚴重的可能會導致對目標區域監測數據錯誤。

無線傳感器網絡常被用于緊急救援、空間探索、軍事應用等特殊環境。由于應用環境特殊，傳感器節點常被隨機布撒于目標區域，并通過自組織形成網絡。因此惡劣的環境、節點能量耗盡以及動物入侵等因素的影響都有可能造成節點死亡，從而導致網絡中會出現某些區域未被任何節點感知，形成覆蓋空洞。若不及時修復就可能引起節點通訊受阻、網絡數據監測不準確等問題[3]，嚴重的還有可能引起網絡癱瘓。為了保證網絡正常運行，需要對網絡中出現的覆蓋空洞采取合適的修復策略，以保證網絡覆蓋質量，維持網絡正常運行。

1　無線傳感器網絡特點

相比于一般網絡，無線傳感器網絡一般都應用于人類無法到達甚至危險的區域。無線傳感器網絡節點的位置一般是固定不變的，只有極少數節點需要移動。一般情況下通過隨機部署節點，利用節點自組織形成網絡。無線傳感器網絡還具有以下顯著特點。

⑴ 規模巨大。通常無線傳感網絡在運行的時候為了保證覆蓋質量一般要求網絡部署時一定要保證網絡中節點具有一定的冗余，因此網絡在部署初期需要部署大量的傳感器節點，這樣既減少了網絡對單個傳感器節點的依賴，同時也保障了網絡的健壯性。雖然要求網絡中具有一定的節點冗余，但并不是冗余越大越好，因為節點冗余過大不僅會造成監測成本過高而且會導致后期維護成本增大。

⑵ 動態性。動態性是指在網絡中節點增加或去除都有可能改變網絡的拓撲結構。在無線傳感器網絡運行的過程中，由于節點能量耗盡等其他因素的影響可能導致節點死亡造成網絡中拓撲結構的改變。新增傳感器節點到網絡中同樣會導致網絡拓撲結構發生變化，因此網絡中的拓撲結構并不是一成不變的。

⑶ 自組織。在監測區域內，一般都是隨機部署大量傳感器節點，由于節點沒有其他網絡可依賴，其通過自組織形成網絡，并以多跳的方式傳送和轉發數據。

⑷ 以數據為中心。無線傳感器網絡以數據為導向，當用戶指定監測目標，網絡會通過節點協作的方式監測用戶感興趣的目標屬性值，然后通過節點轉發將數據發送到匯聚節點，再由匯聚節點將數據通過衛星等發送到計算機，經計算機分析后將數據展現給用戶。

⑸ 相互協作執行任務。無線傳感器從部署到執行都是由多個傳感器節點共同參與完成的，在數據轉發階段傳感器節點需要互相通信，然后數據經過多個傳感器節點以多跳的方式將數據轉發到匯聚節點。

2　覆蓋空洞修復算法分析

針對無線傳感器網絡覆蓋空洞修復問題國內外眾多專家學者作了大量研究，也提出了很多開創性的算法思想，主要分為以下三類。

⑴ 基于幾何計算。核心思想是在保證網絡中節點冗余度的前提下，找出傳感器網絡中覆蓋空洞的最佳修復位置并修復。文獻[4-8]都是基于節點的位置在網絡中構建幾何關系，確定空洞的最佳修復點，最終根據修復點的位置新增正常節點，達到修復覆蓋空洞的目的。文獻[4]在監測區域內隨機部署傳感器節點并在節點感知范圍相同的前提下，提出分析近似算法。計算隨機部署節點的感知覆蓋率，并表示具有覆蓋重疊區域的任何兩個傳感器節點的頂點之間存在的邊緣，主要是近似至少一個感測節點覆蓋的感測區域的比例，并給定二維泊松過程中每單位面積的預期節點數目，通過幾何圖形的性質得到近似概率。該算法可以指導節點的部署，并在后期網絡出現覆蓋空洞時，指導節點修復。文獻[6]提出基于Voronoi覆蓋洞修復算法（EECHS），隨機部署的節點將監測區域劃分為若干Voronoi，將劃分后Voronoi分割為若干三角形并結合相鄰節點生成的Voronoi找到覆蓋空洞的位置，然后連接節點與相鄰公共邊兩端點形成一個夾角，在夾角平分線上找到最優空洞修復點。

雖然該算法可以較好的修復覆蓋空洞，但該算法復雜程度較高且修復后節點冗余較大。文獻[7]針對節點失效或死亡造成的網絡覆蓋空洞，提出在網絡部署時為每個傳感器節點設置一個能量閾值，當網絡運行過程中某個節點的能量低于設定的閾值時，該節點向匯聚節點發出信號，匯聚節點認為發出信號節點的所有鄰居都為覆蓋空洞的邊界點，然后在低于能量閾值節點的覆蓋范圍內找出冗余節點，該節點即為覆蓋空洞修復點。文獻[8]針對修復空洞問題提出最佳節點匹配算法（BFNP），該算法前提是在網絡部署初期部署部分惰性節點即未激活節點，當某惰性節點符合修復空洞要求時激活該節點。當網絡管理者發現網絡中由于節點死亡等原因造成節點失效時，檢測網絡中是否存在覆蓋空洞，如果存在覆蓋空洞則以覆蓋空洞邊緣為邊界，根據距離查詢空洞最近處未被激活的節點，激活該節點來達到修復覆蓋空洞的目的。

⑵ 移動節點輔助。在傳感器網絡中全部使用移動節點，實現節點以移動最短的距離最大程度地修復覆蓋空洞。文獻[9-11]為了使節點移動距離最小，全部采用移動節點修復覆蓋空洞。這樣雖然能較好地控制節點移動的距離，但網絡部署花費過高、運行代價過大。文獻[9]基于集群式的分布網絡提出虛擬力算法，網絡部署初期將傳感器節點隨機部署在監測區域并根據虛擬力算法中的排斥力將節點均勻分開，以達到監測區域被最大程度覆蓋的目的。當網絡中出現覆蓋空洞時，根據算法中的吸引力和排斥力，控制節點移動方向，將節點移動至最佳修復位置。由于移動節點的移動距離有限，為了使移動節點用最少的能量消耗去最大程度地修復覆蓋空洞，文獻[11]提出了基于移動節點的動態修復算法（DCM），該算法中網絡對節點的決策和移動完全自治，不需要外界干預，網絡控制部分傳感器節點，以確定的位置移動實現對網絡覆蓋最大化。

⑶ 靜動節點混合部署。部署網絡時在靜態傳感器節點中加入一定量的移動節點，當需要修復網絡覆蓋空洞時，采用移動節點修復覆蓋空洞并以最小的移動代價修復網絡覆蓋空洞，也在一定程度上降低了后期網絡維護成本。文獻[12-14]都是基于移動節點和混合節點組成的混合網絡修復覆蓋空洞。假設覆蓋空洞已經存在且位置已知，文獻[12]提出基于移動節點的覆蓋空洞修復算法（PATT），該算法將已知覆蓋空洞連接成多邊形，三個相鄰頂點將多邊形劃分為若干三角形，為保證新增節點最大程度地覆蓋三角形所在的空洞區域，在三角形邊的中垂線上計算出移動節點的最佳修復位置，然后將修復后的節點加入到網絡中。依據此算法將覆蓋空洞采用三角形逐步貼片的方式使覆蓋空洞逐步變小，直至達到滿意的修復效果。但是如果完全修復覆蓋空洞，所消耗的移動節點較多，網絡復雜度較高。文獻[13]基于文獻[12]提出基于距離的無線傳感器網絡覆蓋空洞修復算法，將已確定修復位置的移動節點加入傳感器網絡中，然后將覆蓋空洞邊緣連接成多邊形，連接不相鄰多邊形的兩個頂點并找出多邊形中兩頂點連線最長的線段，說明該線段上存在修復覆蓋空洞的最佳位置，根據文獻[12]計算多邊形中三個相鄰頂點形成三角形邊的中垂線，計算該中垂線，求出多邊形中不相鄰兩頂點連線的最長線段的交點，該交點即為移動節點最佳修復位置。該算法相較于文獻[12]減少了移動節點的數目，在一定程度上使網絡復雜度降低。文獻[14]提出基于探測率的覆蓋空洞修復策略。依據節點探測模型，在監測區域內所有點的探測概率連續，探測過程中若探測概率達到最低值則說明該點是需要修復的位置，然后在該位置放置一虛擬節點，直到探測完成。探測完成后將移動節點移到虛擬節點的位置即最佳修復點。該算法在保證網絡最大覆蓋的同時，也控制了移動節點的移動距離和節省了節點的資源。

3　結束語

無線傳感器網絡具有對外界環境感知能力，是由若干個傳感器節點自組織形成網絡，通過多跳的方式發送和轉發數據。當某個或某些傳感器節點因能量耗盡或其他因素造成節點死亡，可能會出現網絡覆蓋空洞從而導致網絡發送或轉發數據異常，因此當網絡中出現覆蓋空洞時需進行及時的修復。

文本介紹了無線傳感器網絡的特點以及出現覆蓋空洞的主要原因，并針對傳感器網絡空洞修復問題詳細介紹了幾類覆蓋空洞修復算法并作必要分析。文中算法大部分都采用MATLAB理想環境下進行仿真實驗，未考慮算法在實際應用中溫度、濕度等環境因素的影響，如何在考慮環境因素的條件下也能達到理想的修復效果也是未來研究的重點。

參考文獻(References):

[1]楊璽.面向實時監測的無線傳感器網絡[M].人民郵電出版社,2010.

[2]Wei An,Nan Qu,et al.Coverage hole problem under sensing topology in flat wirelesssensornetworks[J].WirelessCommunications andMobileComputing,2016.10:578-589

[3]Surjit S,Rajeev M S.Some Aspects of Coverage Awareness inWirelessSensorNetworks[J].Procedia Computer Science,2015.10:160-165

[4]Xiaoyun Li,David K.Coverage Properties of the Target Area in Wireless Sensor Networks[J].IEEE Transactions on Information Theory,2012.58(1):430-437

[5]LINJW,CHENYT.Improvingthecoverageof randomized schedul-ing in wireless sensor networks[J].IEEE Transactions on WirelessCommunications,2008.7(1):4807-4812

[6]趙春江,無華瑞,劉強等.基于Voronoi的無線傳感器網絡覆蓋控制優化策略[J].通信學報,2013.9:115-122

[7]包旭,巨永鋒.面向節點失效的無線傳感器網絡覆蓋空洞修復算法[J].計算機測量與控制,2011.19(6):1516-1518

[8]胥楚貴,鄧曉衡,鄒豪杰.無線傳感器網絡覆蓋空洞修復策略[J].傳感技術學報,2010.23(2):256-259

[9]ZOU Y,CHAKRABARTY K.Sensor deployment and targetlocalization based on virtual forces[A].INFOCOM2003[C],2003.1293-1303

[10]WANG G,CAO G,PORTA T.Movement-assisted sensordeploy-ment[J].IEEETransaction onMobile Computing,2006.5(6):640-652

[11]SEKHA A,MANOJ B,MURTHY C.Dynamic coverage maintenancealgorithms for sensor networks with limited mobility[A].Proceedingsof the 3rd IEEE Int'l Conf on Pervasive Computing and Communica-tions[C].Kauai,Island,2005:51-60

[12]王良民,李菲,秦穎.基于移動節點的無線傳感器網絡覆蓋洞修復方法[J].通信學報,2011,32(4):1-8.

[13]韓春延.基于距離的無線傳感器網絡覆蓋洞修復算法[J].傳感器與微系統,2013.32(4):91-94

[14]黃月,吳成東,張運洲,等.基于移動節點的無線傳感器網絡覆蓋優化[J].東北大學學報(自然科學版),2012.33(2):165-168