田曉光

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

0　引言

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

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

1　無線傳感器網絡特點

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

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

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

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

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

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

2　覆蓋空洞修復算法分析

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

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

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

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

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

3　結束語

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

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

參考文獻(References):

[1]楊璽.面向實時監(jiān)測的無線傳感器網絡[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的無線傳感器網絡覆蓋控制優(yōu)化策略[J].通信學報,2013.9:115-122

[7]包旭,巨永鋒.面向節(jié)點失效的無線傳感器網絡覆蓋空洞修復算法[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]王良民,李菲,秦穎.基于移動節(jié)點的無線傳感器網絡覆蓋洞修復方法[J].通信學報,2011,32(4):1-8.

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

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