一種無線傳感器網絡覆蓋空洞的修復方法

張 蕾，錢 峰

（銅陵學院 數學與計算機科學系，安徽 銅陵244000）

1 引 言

由于嵌入式系統技術在近幾年快速發展，無線傳感器網絡（WSN）已成為最重要的研究領域之一。覆蓋率是無線傳感器網絡有效的重要度量指標。根據Paikh等提出的理論：[1]傳感器網絡的覆蓋率為100%是不可能的，當覆蓋率≧70%時，網絡才有效。針對如何保持一個良好的網絡覆蓋率，許多方法陸續被提出，其中不少方法需要移動傳感器節點。文獻[2]中提出了VFA，方法中假設每個傳感器節點之間存在引力和斥力。如果任何兩個節點太近，斥力會將它們分開，反之，引力會拉近它們。VFA會使網絡拓撲更加的均衡，但需要所有節點知道其位置。由于方法中所有節點的感知半徑被假定為固定的，所以能量低的節點會快速耗盡其能量。EVFA[4]是VFA的分布式版本，這意味著剩余能量高的節點比低的節點有更大的感知半徑。能有效地利用網絡中的能量資源，延長網絡的生存時間。

2 問題描述和系統模型

2.1 覆蓋空洞

當傳感器網絡中某一節點因其本身能量耗盡或被破壞而失效，導致網絡原有的覆蓋區域缺失或者數據無法送達基站的現象，稱為 “覆蓋空洞”（coverage holes）現象。覆蓋空洞直接導致網絡覆蓋率下降，也會給一些應用帶來很多問題。如在醫療中，我們會使用實時傳感器來監控病人身體的健康情況，如果傳感器失效，將失去病人的病情信息。

在諸如VFA的方法中，當某個節點失效，基站會給網絡中每個活動節點計算出一個新的位置，然后移動傳感器節點修復覆蓋漏洞。因為移動節點需要耗費大量的能量，本文提出一個有效的方法來修補覆蓋空洞，是網絡保持一個良好的覆蓋率。

2.2 系統模型

假設無線傳感網絡系統由一個基站和多個傳感器節點構成，基站負責收集來自所有傳感器節點發送來的數據，我們采用文獻[2，4]中的概念，假設節點間存在虛擬力，利用節點間的虛擬力可以保證移動節點間的合作。因為能量的限制，每個節點采用多跳的方式傳輸包，因為單跳傳輸可能要耗費更多的能量。傳感器的感知模型為圓盤模型。

本文的方案基于以下假設：

1.基站是固定的，所有傳感器節點均可移動；

2.所有傳感器節點通過GPS或其他定位機制知道自己的位置信息；

3.所有傳感器節點都可調整自己的感知范圍和通信范圍。最大的感知半徑（RS）設為20m，最大的通信半徑（RC）設為40m。

圖1 節點g即將失效前

3 無線傳感器網絡覆蓋空洞修復

3.1 節點間信息的交換

為了減少修復覆蓋空洞所需移動節點的數目，我們將每個傳感器節點的通信范圍劃分成3個區間：-π/6到 π/2之間的區域為區間 1，π/2到-5π/6之間的區域為區間2，-5π/6到-π/6之間的區域為區間3。然后對各區間分別計算其每個鄰居節點的ED_value。

其中，d為節點與其鄰居節點的距離。節點會選擇該區間鄰居節點中ED_value值最大的節點作為節點在這個區間的指定節點。

最初，每個節點在其通信半徑內通過廣播hello消息包獲得鄰居節點的相關信息。一個Hello消息包含如下信息：節點id，節點位置，剩余能量和到基站的距離，鄰居節點及距其距離的列表，各區間所指定的節點。每個節點通過hello消息包記錄來自鄰居節點的信息。節點間信息交換完成后，每個節點選擇距基站距離最小的鄰居節點作為其向基站傳輸數據包的下一跳。

當hello包完成交換后，節點將知道其是否被其鄰居節點選擇為指定節點，這些信息被記錄在它們各自的表中。網絡完成部署后，每個節點開始工作并向基站傳送數據包。每個節點也將定期廣播hello包用于維護網絡拓撲。

3.2 節點的移動

當某個傳感器節點能量即將耗盡，即向其3個區間所指定的節點發送cover_request消息通知它們覆蓋其工作區域。計算每個指定節點需要移動的距離為：

dist(i)為該節點與鄰居節點i的距離，k為所有3個區間指定節點的數目（1≤k≤3）。average_energy為所有指定節點能量的均值。如果鄰居節點沒有定期收到來自于節點g的hello消息，它將假定節點g已經死亡，將計算移動距離并自動移向目標位置。

圖1中，經過信息交換階段后，節點g分別選擇a，b，d作為其3個區間的指定節點，因為這3個節點分別在其所在區間的ED_value最大。如果節點g即將死亡，其向3個區間的指定節點發送coverrequest消息，這些節點收到消息后將各自計算移動距離并移向目標位置。

3.3 增大感知半徑

節點在收到cover_request消息并移動到目標位置后，它將擴大其感知半徑以覆蓋死亡節點的范圍。新的感知半徑由初始感知半徑加上移動距離，這樣使得原有的區域仍然能覆蓋。圖2顯示了節點g死亡后的拓撲，節點a，b和d移動到一個新的位置并且擴大他們的感知半徑。節點a，b和d再次通過廣播hello消息獲取其鄰居節點的相關信息。

圖2 節點g死亡后

4 仿真實驗

利用JAVA編寫程序模擬我們的仿真環境，假定網絡100個傳感器節點隨機部署在大小為100m*100m的方形區域內，所有的節點均可移動，傳感器節點的初始能量在150J到3000J的范圍內。離基站越近的節點擁有越多的能量，因為離基站越近其負載越大，依式（3）計算節點能量消耗。

α和 β是兩個調整參數。Rs為感知半徑，Rc為通信半徑，l為數據包大小，固定為512byte，實驗中我們假設各節點接收能耗為一固定值0.205j，節點移動每米消耗能量為27.96j。通過仿真實驗，對本文提出的方法與VFA與EVFA在3個方面的性能進行比較，分別是覆蓋率，剩余能量，連接節點的數目。

圖3顯示的3種方法的網絡覆蓋率。因為覆蓋率在0到300個時間單位下沒有變化，我們僅顯示300個時間單位后的結果。當節點開始失效，覆蓋率開始下降。在這里，我們只統計那些與基站仍然保持連接的節點數目。可以看到，當VFA與EVFA得覆蓋率下降很快時，我們的方法仍然能保持好的覆蓋率。EVFA中的傳感器節點可根據其能量調整感知半徑，故其覆蓋率有時會小于VFA。

圖5 連接基站節點數量

5 結束語

針對無線傳感器網絡中節點因能量耗盡或環境破壞而失效導致產生覆蓋空洞的現象，本文提出了1種解決辦法，基本思想是選擇最多3個ED_value值最大的節點，通過節點移動并擴大其感知半徑來修復覆蓋空洞。通過仿真實驗表明了改方法能保證較好的網絡覆蓋率，延長了網絡的生存時間。

圖4顯示網絡剩余能量。本文的方法比VFA與EVFA有更高的能量剩余，因為在這兩種方案中，當節點死亡時，所有的傳感器節點都可能移動，這需要消耗大量的能量。而本文的方法最多只需要移動3個節點。

圖5中可以看出本文的方法比VFA與EVFA能保持更多的節點連接，因為節點花很多的能量在移動上，所有死亡的更快。

[1]Parikh S，Vokkarane V M，Liudong X，Kasilingam D.Node-ReplacementPoliciestoMaintainThreshold-CoverageinWireless Sensor Networks[C].Proceedings of 16th International Conference on Computer Communications and Networks，2007:760-765.

[2]Zou Y，Chakrabarty K.Sensor deployment and target localization based on virtual forces[C].in Proc.IEEE INFOCOM Conference，2003:1293-1303.

[3]Zhang S，Liu Y，Pu J，Xiao Z，Zhang X.An Enhanced Coverage Control Protocol for Wireless Sensor Networks[C].Hawaii International Conference on System Sciences，2009:1-7.

[4]Younghwan Yoo，Agrawal D P，Mobile Sensor Relocation to Prolong the Lifetime of Wireless Sensor Networks[C].IEEE Vehicular Technology Conference，2008:193-197.