無線傳感器網絡覆蓋算法綜述

陳曉東

摘要：無線傳感器網絡（WSN）是由大量微型，廉價和低功耗傳感器節點組成的網絡，這些節點之間通過無線通信多跳中繼，相互協作完成應用程序任務并將感知數據轉發到中央采集匯聚節點。無線傳感器廣泛應用于環境檢測，棲息地檢測，精細農業甚至軍事領域。無線傳感器網絡一個很重要的問題是覆蓋問題，覆蓋問題主要分為三類，分別是區域覆蓋，目標覆蓋以及柵欄覆蓋，下文分別對此三類覆蓋方式做一個綜述。

關鍵詞：WSN；覆蓋算法；節點調度

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2019）06-0023-02

1 無線傳感器網絡覆蓋算法

1.1 目標覆蓋

目標覆蓋是針對監測區域內某些特定的目標進行監測，又稱為點覆蓋，如圖1所示，為了保證覆蓋質量，通常需要每一個監測對象被最少一個傳感器節點所感知，目標覆蓋的主要應用領域在于軍事領域。

（1）Saint_Louis[1]提出了一種基于權重的遺傳算法，該論文解決了傳感器節點集合最大化問題，從文獻中分析了一些經典算法，并且提出了一個全新的集中式的思路，新算法的名稱稱為基于權重的貪婪算法，通過將傳感器節點分為多個集合，并且保證每個集合滿足完全覆蓋，基于權重的貪婪算法的目標是從分區中最大化集合個數從而延長整體的網絡壽命。但是算法的分區選擇有些難度，并且由于算法是集中式的，擴展性不夠好，并且時間復雜度有些高。

（2） Manju[2]提出了一種新的節能啟發式方法，可以在不同時間段對傳感器進行調度，不同非相交傳感器節點集合有助于最大化網絡生存周期。首先，作者的啟發式算法可以識別出所有關鍵目標也就是最少被覆蓋的目標，以及關鍵節點，也就是覆蓋關鍵目標的節點。關鍵目標由最少的傳感器節點覆蓋，將會是最先未被覆蓋的，有效的利用關鍵節點將會延長網絡壽命，作者嘗試尋找使用最少的傳感器數量來覆蓋迷宮集合以至于關鍵目標可以被覆蓋更長時間。由于算法使用的非相交的集合，因此和那些使用可以存在重疊的傳感器集合相比，會有更少的集合數量。

（3） Babacar[3]提出了一種貪心集合的算法來解決目標覆蓋問題，該貪心算法將節點集合分為相交和不相交兩種。將傳感器劃分為最大數量的集合覆蓋，并通過連續激活這些集合來安排傳感器活動，在網絡生命周期的某個時刻，只有一個子集被激活，屬于該子集的所有傳感器負責檢測目標，所有其他傳感器處于休眠狀態，直到它們所屬的集合被激活。該算法可以有效延長整體生存周期，但是貪心算法并不一定是最優解，并且此論文并未有給出令人信服的證明。

1.2 區域覆蓋

區域覆蓋，通常又稱為面積覆蓋，是在滿足無線傳感器網絡連通性下的前提下，考慮如何用更少的傳感器數量來監測更大的覆蓋面積，圖2所示。理想情況下，應該使得監測區域內的每個點都可以被至少一個傳感器感知。

1） PEAS算法

PEAS[4]算法是一種簡單的協議，通過大量經濟，短壽命的傳感器來構建一個長壽命的傳感器網絡。PEAS通過保持一組必要的傳感器工作并將其余傳感器置于睡眠模式來延長整體覆蓋壽命，不時喚醒休眠節點，探測周邊環境并且替換失敗的傳感器節點。因為PEAS協議是每個節點都有自主檢測能力，其實可以認為它是基于分布式的一種協議，因為擴展性算是該算法的一個優點，并且每個節點檢測方式比較簡單，容易擴展，時間復雜度也很低，然而該算法也有其弊端，那就是有些節點可能會過度使用，導致提前將能量耗盡，因而影響整體覆蓋效果。

2） SPAN算法

SPAN[5]算法是一種用于多跳ad hoc無線網絡的節能技術，可在不顯著降低網絡容量或連接性的情況下降低能耗。SPAN是一種基于分布式的算法，其中節點在是否休眠做出本地決策，或者作為協調器加入骨干網絡。每個節點的決策基于如果它蘇醒的話，有多少鄰居節點可以從之獲取好處。SPAN算法的核心創新就是提出了骨干網絡，并且通過對骨干網絡的選擇節省能量，并且延長整體網絡壽命。SPAN算法的缺點是，因為骨干網絡需要承擔更多的轉發數據的任務，顯然需要消耗更多的能量，進而影響整體網絡覆蓋質量。

3） Node Self-scheduling算法

Node Self-scheduling[6]算法提出了一種節點調度方案，通過對冗余節點的感知覆蓋進行識別，然后分配一種比正常活躍節點能耗更低的休眠模式，從而降低系統的整體能耗，從而提高系統的壽命，該算法從理論上完全保留原始傳感器覆蓋范圍，并且可以在保證覆蓋的同時維持一個比較低的冗余度，然后在節點判斷是否休眠的過程中，容易出現多個節點同時休眠，導致出現覆蓋黑洞的出現。

1.3 柵欄覆蓋

柵欄覆蓋主要是用來監測一個或多個運動目標穿越無線傳感器網絡的一種覆蓋方式，傳感器節點能夠有效監測處于覆蓋范圍內的移動目標的運動軌跡[3]，如圖3所示，和區域覆蓋的不同在于它監測的主要目標是可移動的，不可確定的。

（1）謝歡[7]針對柵欄覆蓋提出了一種最小化覆蓋集合探測算法，該算法在概率感知模型的協同檢測下研究目標檢測問題，基于圖論，提出一種最小化覆蓋的，尋求用最小的激活節點實現一個強大的屏障，用來延長整體網絡壽命。并且算法有較低的時間開銷以及準確性可以得到較好的保證。但是算法的冗余度有些高，會導致使用過多的節點。

（2）馮全友[8]等人提出一種針對柵欄覆蓋的分布式調度策略，首先將監測區域劃分為垂直區域塊，稱之為切片，基于這種劃分，作者將如何調度傳感器滿足柵欄覆蓋并且實現最大化網絡壽命周期問題稱為屏障覆蓋調度問題，并且作者們提出了對應的分布式算法，這個分布式算法有兩個優點，低通信開銷和低計算開銷。并且十分適應于大規模網絡。但是算法不太適應于覆蓋面積比較不規則的場合，切片時比較難以劃分。

2 結論

上文對無線傳感器網絡的三種覆蓋方式作了一些簡單概述，分析了其不同的特點以及應用場景，并且不同的覆蓋方式也舉了一些覆蓋算法的例子。正是由于無線傳感器網絡覆蓋方式的多樣，才會有其廣泛的應用以及研究價值，無線傳感器網絡覆蓋技術已經越來越成為一種不可或缺的技術。

參考文獻：

[1] Diop B ， Diongue D ， Thiare O . A weight-based greedy algorithm for target coverage problem in wireless sensor networks[C]// International Conference on Computer. IEEE， 2014.

[2] Kumar B ， Manju， ， Chand S . Maximising network lifetime for target coverage problem in wireless sensor networks[J]. IET Wireless Sensor Systems， 2016.

[3] Diop B ， Diongue D ， Thiare O . Managing Target Coverage Lifetime in Wireless Sensor Networks with Greedy Set Cover[C]// International Conference on Multimedia. IEEE， 2014.

[4] Ye F，Zhong G，Lu S，Zhang L.PEAS：A robust energy conserving protocol for long-lived sensor networks. Proceedings Internation Conference on Network Protocols（ICNP），Pairs，France，2002：200-201.

[5] Chen B，Jamieson K， Balakrishnan H，et al. SPAN：An energy efficient coordination algorithm for topology maintenance in ad-hoc wireless sensor networks[J].ACM Wireless Networks，2002，8（5）：481-494.

[6] Tian D ， Georganas N D . A node scheduling scheme for energy conservation in large wireless sensor networks[J]. Wireless Communications & Mobile Computing， 2010， 3（2）：271-290.

[7] Huan X ， Lin K ， Chaowei W ， et al. Minimal coverage set detecting algorithm for barrier coverage in wireless sensor networks[C]// IEEE International Conference on Network Infrastructure & Digital Content. IEEE， 2015.

[8] Ban D ， Feng Q ， Han G ， et al. Distributed Scheduling Algorithm for Barrier Coverage in Wireless Sensor Networks[C]// Third International Conference on Communications & Mobile Computing. IEEE Computer Society， 2011.

【通聯編輯：梁書】