無線傳感器網(wǎng)絡(luò)覆蓋算法綜述

陳曉東

摘要：無線傳感器網(wǎng)絡(luò)（WSN）是由大量微型，廉價和低功耗傳感器節(jié)點(diǎn)組成的網(wǎng)絡(luò)，這些節(jié)點(diǎn)之間通過無線通信多跳中繼，相互協(xié)作完成應(yīng)用程序任務(wù)并將感知數(shù)據(jù)轉(zhuǎn)發(fā)到中央采集匯聚節(jié)點(diǎn)。無線傳感器廣泛應(yīng)用于環(huán)境檢測，棲息地檢測，精細(xì)農(nóng)業(yè)甚至軍事領(lǐng)域。無線傳感器網(wǎng)絡(luò)一個很重要的問題是覆蓋問題，覆蓋問題主要分為三類，分別是區(qū)域覆蓋，目標(biāo)覆蓋以及柵欄覆蓋，下文分別對此三類覆蓋方式做一個綜述。

關(guān)鍵詞：WSN；覆蓋算法；節(jié)點(diǎn)調(diào)度

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2019）06-0023-02

1 無線傳感器網(wǎng)絡(luò)覆蓋算法

1.1 目標(biāo)覆蓋

目標(biāo)覆蓋是針對監(jiān)測區(qū)域內(nèi)某些特定的目標(biāo)進(jìn)行監(jiān)測，又稱為點(diǎn)覆蓋，如圖1所示，為了保證覆蓋質(zhì)量，通常需要每一個監(jiān)測對象被最少一個傳感器節(jié)點(diǎn)所感知，目標(biāo)覆蓋的主要應(yīng)用領(lǐng)域在于軍事領(lǐng)域。

（1）Saint_Louis[1]提出了一種基于權(quán)重的遺傳算法，該論文解決了傳感器節(jié)點(diǎn)集合最大化問題，從文獻(xiàn)中分析了一些經(jīng)典算法，并且提出了一個全新的集中式的思路，新算法的名稱稱為基于權(quán)重的貪婪算法，通過將傳感器節(jié)點(diǎn)分為多個集合，并且保證每個集合滿足完全覆蓋，基于權(quán)重的貪婪算法的目標(biāo)是從分區(qū)中最大化集合個數(shù)從而延長整體的網(wǎng)絡(luò)壽命。但是算法的分區(qū)選擇有些難度，并且由于算法是集中式的，擴(kuò)展性不夠好，并且時間復(fù)雜度有些高。

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

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

1.2 區(qū)域覆蓋

區(qū)域覆蓋，通常又稱為面積覆蓋，是在滿足無線傳感器網(wǎng)絡(luò)連通性下的前提下，考慮如何用更少的傳感器數(shù)量來監(jiān)測更大的覆蓋面積，圖2所示。理想情況下，應(yīng)該使得監(jiān)測區(qū)域內(nèi)的每個點(diǎn)都可以被至少一個傳感器感知。

1） PEAS算法

PEAS[4]算法是一種簡單的協(xié)議，通過大量經(jīng)濟(jì)，短壽命的傳感器來構(gòu)建一個長壽命的傳感器網(wǎng)絡(luò)。PEAS通過保持一組必要的傳感器工作并將其余傳感器置于睡眠模式來延長整體覆蓋壽命，不時喚醒休眠節(jié)點(diǎn)，探測周邊環(huán)境并且替換失敗的傳感器節(jié)點(diǎn)。因?yàn)镻EAS協(xié)議是每個節(jié)點(diǎn)都有自主檢測能力，其實(shí)可以認(rèn)為它是基于分布式的一種協(xié)議，因?yàn)閿U(kuò)展性算是該算法的一個優(yōu)點(diǎn)，并且每個節(jié)點(diǎn)檢測方式比較簡單，容易擴(kuò)展，時間復(fù)雜度也很低，然而該算法也有其弊端，那就是有些節(jié)點(diǎn)可能會過度使用，導(dǎo)致提前將能量耗盡，因而影響整體覆蓋效果。

2） SPAN算法

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

3） Node Self-scheduling算法

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

1.3 柵欄覆蓋

柵欄覆蓋主要是用來監(jiān)測一個或多個運(yùn)動目標(biāo)穿越無線傳感器網(wǎng)絡(luò)的一種覆蓋方式，傳感器節(jié)點(diǎn)能夠有效監(jiān)測處于覆蓋范圍內(nèi)的移動目標(biāo)的運(yùn)動軌跡[3]，如圖3所示，和區(qū)域覆蓋的不同在于它監(jiān)測的主要目標(biāo)是可移動的，不可確定的。

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

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

2 結(jié)論

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

參考文獻(xiàn)：

[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，F(xiàn)rance，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.

【通聯(lián)編輯：梁書】