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

陳曉東

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

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

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

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

1.1 目標(biāo)覆蓋

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

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

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

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

1.2 區(qū)域覆蓋

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

1） PEAS算法

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

2） SPAN算法

SPAN[5]算法是一種用于多跳ad hoc無(wú)線網(wǎng)絡(luò)的節(jié)能技術(shù)，可在不顯著降低網(wǎng)絡(luò)容量或連接性的情況下降低能耗。SPAN是一種基于分布式的算法，其中節(jié)點(diǎn)在是否休眠做出本地決策，或者作為協(xié)調(diào)器加入骨干網(wǎng)絡(luò)。每個(gè)節(jié)點(diǎn)的決策基于如果它蘇醒的話(huà)，有多少鄰居節(jié)點(diǎn)可以從之獲取好處。SPAN算法的核心創(chuàng)新就是提出了骨干網(wǎng)絡(luò)，并且通過(guò)對(duì)骨干網(wǎng)絡(luò)的選擇節(jié)省能量，并且延長(zhǎng)整體網(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)度方案，通過(guò)對(duì)冗余節(jié)點(diǎn)的感知覆蓋進(jìn)行識(shí)別，然后分配一種比正?；钴S節(jié)點(diǎn)能耗更低的休眠模式，從而降低系統(tǒng)的整體能耗，從而提高系統(tǒng)的壽命，該算法從理論上完全保留原始傳感器覆蓋范圍，并且可以在保證覆蓋的同時(shí)維持一個(gè)比較低的冗余度，然后在節(jié)點(diǎn)判斷是否休眠的過(guò)程中，容易出現(xiàn)多個(gè)節(jié)點(diǎn)同時(shí)休眠，導(dǎo)致出現(xiàn)覆蓋黑洞的出現(xiàn)。

1.3 柵欄覆蓋

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

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

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

2 結(jié)論

上文對(duì)無(wú)線傳感器網(wǎng)絡(luò)的三種覆蓋方式作了一些簡(jiǎn)單概述，分析了其不同的特點(diǎn)以及應(yīng)用場(chǎng)景，并且不同的覆蓋方式也舉了一些覆蓋算法的例子。正是由于無(wú)線傳感器網(wǎng)絡(luò)覆蓋方式的多樣，才會(huì)有其廣泛的應(yīng)用以及研究?jī)r(jià)值，無(wú)線傳感器網(wǎng)絡(luò)覆蓋技術(shù)已經(jīng)越來(lái)越成為一種不可或缺的技術(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)編輯：梁書(shū)】