楊秀杰+華江鋒

摘 要：WSN區(qū)域覆蓋技術(shù)可以有效延長無線傳感器網(wǎng)絡(luò)（Wireless Sonsor Networks， WSN）的生存周期，一直都是人們研究的熱點(diǎn)問題之一。在保證網(wǎng)絡(luò)覆蓋質(zhì)量的基礎(chǔ)上，WSN區(qū)域覆蓋技術(shù)通過調(diào)度節(jié)點(diǎn)狀態(tài)，降低節(jié)點(diǎn)能耗從而延長網(wǎng)絡(luò)生存周期。本文對現(xiàn)階段典型的WSN區(qū)域覆蓋節(jié)點(diǎn)調(diào)度算法原理進(jìn)行扼要說明，分析它們各自的優(yōu)缺點(diǎn)并做出相關(guān)總結(jié)。

關(guān)鍵詞：WSN區(qū)域；NSS算法；Gao算法

中圖分類號：TN929 文獻(xiàn)標(biāo)志碼：A

0 引言

隨著科學(xué)技術(shù)的不斷更新與日益發(fā)展，無線傳感器網(wǎng)絡(luò)因其功耗低、隨機(jī)部署以及網(wǎng)絡(luò)組織方式多樣化等優(yōu)點(diǎn)在軍用和民用領(lǐng)域中大放異彩，發(fā)揮著愈加重要的作用。WSN被美國評為人類未來高新技術(shù)產(chǎn)業(yè)之一。無線傳感器的能量通常是由網(wǎng)絡(luò)節(jié)點(diǎn)攜帶的干電池供應(yīng)的，具有資源有限、不可再生的缺點(diǎn)。因此，如何節(jié)省節(jié)點(diǎn)能量從而延長網(wǎng)絡(luò)生命周期是WSN設(shè)計(jì)的一個重要考慮問題，區(qū)域覆蓋技術(shù)正是因此應(yīng)運(yùn)而生。近些年來，國內(nèi)外專家針對WSN區(qū)域覆蓋技術(shù)中的問題提出了許多節(jié)點(diǎn)調(diào)度算法。這些算法各有優(yōu)劣，應(yīng)根據(jù)具體應(yīng)用合理選擇。

1 典型的WSN節(jié)點(diǎn)調(diào)度算法

1.1 HCA算法

HCA（Heuristic Coverage Algorithm）算法是由國外學(xué)者提出的一種基于集合輪流概念的節(jié)點(diǎn)調(diào)度算法。該算法的主要思想是將傳感器節(jié)點(diǎn)分成幾個彼此之間沒有重合部分并且可以輪流對網(wǎng)絡(luò)區(qū)域進(jìn)行監(jiān)測的節(jié)點(diǎn)集合。算法中的節(jié)點(diǎn)覆蓋監(jiān)測區(qū)域如圖1所示。

在圖1中，監(jiān)測區(qū)域ABCD有n1、n2、n3和n4 4個節(jié)點(diǎn)，這4個節(jié)點(diǎn)監(jiān)測將區(qū)域ABCD劃分成9個子區(qū)域，即圖中的1～9所示區(qū)域。那么，這4個節(jié)點(diǎn)的覆蓋監(jiān)測區(qū)域分別為n1={1，4，7，2，5，8}，n2={1，2，3，4，5，6}，n3={4，5，6，7，8，9}，n4={2，5，8，3，6，9}。通過分析可知，圖1的最優(yōu)解為：M1={n1，n4}，M2={n2，n3}，即這4個節(jié)點(diǎn)可以劃分為兩個集合。

HCA算法的優(yōu)點(diǎn)是設(shè)計(jì)直觀，可以有效延長網(wǎng)絡(luò)生命周期。它的缺點(diǎn)是由于該算法是根據(jù)節(jié)點(diǎn)位置計(jì)算覆蓋區(qū)域集合的，因此不宜擴(kuò)展使用。而且，如果集合中的某些節(jié)點(diǎn)失效，就會大大影響該集合功能，甚至造成集合完全失效。

1.2 NSS算法

NSS（Node Self-Scheduling）算法是一種基于節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換的調(diào)度算法。該算法中的節(jié)點(diǎn)可以進(jìn)行自我調(diào)度，具體工作包括：首先，節(jié)點(diǎn)向自身的鄰居節(jié)點(diǎn)廣播包括自身id號與坐標(biāo)的信息包；其次，節(jié)點(diǎn)比較自身覆蓋面積與其鄰居節(jié)點(diǎn)的覆蓋范圍大小，如果前者大于后者，則該節(jié)點(diǎn)轉(zhuǎn)入休眠狀態(tài)，否則該節(jié)點(diǎn)仍然處于調(diào)度工作狀態(tài)。在節(jié)點(diǎn)自我調(diào)度過程中，可能會出現(xiàn)覆蓋空洞的情況。針對這個問題，國外學(xué)者提出在節(jié)點(diǎn)調(diào)度檢查之前執(zhí)行一個基于載波偵聽協(xié)議的退避機(jī)制。

NSS算法的優(yōu)點(diǎn)在于可以有效降低節(jié)點(diǎn)能耗與延長網(wǎng)絡(luò)生命周期，此外，即使網(wǎng)絡(luò)中出現(xiàn)節(jié)點(diǎn)失效與信息包丟失的情況，也不會對整體算法的運(yùn)行產(chǎn)生嚴(yán)重影響，即該算法的魯棒性較好。該算法的不足在于為了實(shí)現(xiàn)節(jié)點(diǎn)坐標(biāo)精確定位，會增加節(jié)點(diǎn)硬件成本與節(jié)點(diǎn)能耗，而且，該算法的網(wǎng)絡(luò)連通性設(shè)計(jì)不夠合理，會對網(wǎng)絡(luò)性能造成一定影響。

1.3 PEAS算法

PEAS算法在保證網(wǎng)絡(luò)質(zhì)量的基礎(chǔ)上，盡可能地降低網(wǎng)絡(luò)能耗，使某些節(jié)點(diǎn)處于休眠狀態(tài)。只有當(dāng)這些休眠節(jié)點(diǎn)周圍沒有工作節(jié)點(diǎn)時(shí)，它們才轉(zhuǎn)換為工作狀態(tài)，否則繼續(xù)保持休眠狀態(tài)。節(jié)點(diǎn)即使處于休眠狀態(tài)，也要不定期地進(jìn)行自我喚醒并監(jiān)測周圍環(huán)境。如果該節(jié)點(diǎn)發(fā)現(xiàn)鄰居節(jié)點(diǎn)中有失效節(jié)點(diǎn)便將自身喚醒，替代失效節(jié)點(diǎn)完成相應(yīng)工作，從而保證網(wǎng)絡(luò)工作正常運(yùn)行。因此，該算法包括環(huán)境探測與自適應(yīng)休眠兩部分內(nèi)容。

PEAS算法是一種分布式算法，因此擴(kuò)展性良好，可以在大規(guī)模的WSN中投入使用。而且由于網(wǎng)絡(luò)中的部分節(jié)點(diǎn)某些時(shí)段會處于休眠狀態(tài)，因此網(wǎng)絡(luò)的整體開銷也相對較小。此外，通過調(diào)整節(jié)點(diǎn)的探測區(qū)域大小可以有效改善網(wǎng)絡(luò)的覆蓋冗余度。該算法的主要缺點(diǎn)是可能會造成網(wǎng)絡(luò)中的節(jié)點(diǎn)能耗不均衡，導(dǎo)致某些節(jié)點(diǎn)因負(fù)擔(dān)工作過重而過早的死亡，從而進(jìn)一步影響到整體的網(wǎng)絡(luò)覆蓋質(zhì)量。

1.4 SPAN算法

SPAN算法是國外學(xué)者提出的一種基于構(gòu)造骨干網(wǎng)絡(luò)的節(jié)點(diǎn)調(diào)度算法。在該算法中，總共有3種節(jié)點(diǎn)類型：骨干節(jié)點(diǎn)和非骨干節(jié)點(diǎn)。骨干節(jié)點(diǎn)是構(gòu)成骨干網(wǎng)絡(luò)的節(jié)點(diǎn)，它處于工作狀態(tài)并能保證網(wǎng)絡(luò)覆蓋質(zhì)量。而非骨干節(jié)點(diǎn)則是處于休眠狀態(tài)的節(jié)點(diǎn)。骨干網(wǎng)絡(luò)中的節(jié)點(diǎn)彼此之間可以連通，非骨干節(jié)點(diǎn)也要確保能和骨干節(jié)點(diǎn)彼此通信。骨干節(jié)點(diǎn)還被用來轉(zhuǎn)發(fā)網(wǎng)絡(luò)數(shù)據(jù)的節(jié)點(diǎn)，它的負(fù)擔(dān)工作較重，因此需要節(jié)點(diǎn)輪流替換完成相應(yīng)功能。非骨干節(jié)點(diǎn)可以通過競選稱為骨干節(jié)點(diǎn)，其狀態(tài)也相應(yīng)地由休眠狀態(tài)轉(zhuǎn)換為工作狀態(tài)。整個骨干網(wǎng)絡(luò)都是在動態(tài)變化的，節(jié)點(diǎn)的狀態(tài)也會不斷轉(zhuǎn)換。

SPAN算法的優(yōu)點(diǎn)是對各個節(jié)點(diǎn)狀態(tài)的工作做出明確劃分，同時(shí)盡可能地均衡節(jié)點(diǎn)能耗，因此在延長網(wǎng)絡(luò)生命周期方面具有一定優(yōu)勢。該算法的主要不足是設(shè)計(jì)較為復(fù)雜，節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換較為頻繁，同時(shí)由于骨干節(jié)點(diǎn)的負(fù)擔(dān)工作較重，因此會消耗較多能量，而且該算術(shù)對傳感器網(wǎng)絡(luò)的連通性也有一定要求。

1.5 Ditian算法

Ditian算法也是一種分布式算法，它通過節(jié)點(diǎn)間的幾何關(guān)系判斷節(jié)點(diǎn)是否冗余，在保證網(wǎng)絡(luò)覆蓋質(zhì)量的基礎(chǔ)上讓冗余節(jié)點(diǎn)處于休眠狀態(tài)，從而降低節(jié)點(diǎn)能耗。算法原理圖如圖2所示。

在圖2中，節(jié)點(diǎn)O與節(jié)點(diǎn)S的覆蓋圓形范圍相交于點(diǎn)P與點(diǎn)N，兩個節(jié)點(diǎn)的相交重合區(qū)域?yàn)镽_PQMN。由圖中的幾何關(guān)系可知，節(jié)點(diǎn)重合區(qū)域的面積不易求出，而扇形區(qū)域PQN的面積則相對容易計(jì)算。扇形區(qū)域PQN的面積是S節(jié)點(diǎn)對O節(jié)點(diǎn)的貢獻(xiàn)面積。只要求出扇形PQN對應(yīng)圓心角∠CON的角度在0～360°，就可以確定A是冗余節(jié)點(diǎn)，進(jìn)而令其處于休眠狀態(tài)。endprint

Ditian算法的優(yōu)點(diǎn)是不依靠節(jié)點(diǎn)的具體坐標(biāo)，這樣便減少了節(jié)點(diǎn)的能源消耗，大大降低了系統(tǒng)開發(fā)成本。 該算法的缺點(diǎn)是在判斷節(jié)點(diǎn)是否冗余過程中只考慮了節(jié)點(diǎn)通信范圍內(nèi)局部鄰居節(jié)點(diǎn)的貢獻(xiàn)面積，并沒有考慮全部可通信的鄰居節(jié)點(diǎn)對自身的面積貢獻(xiàn)，因此其計(jì)算結(jié)果不夠精確。

1.6 Gao算法

Gao算法是國外學(xué)者提出的一種基于概率統(tǒng)計(jì)思想的WSN節(jié)點(diǎn)調(diào)度算法，同Ditian算法一樣，該算法也是將判斷節(jié)點(diǎn)冗余性作為自身的核心設(shè)計(jì)部分。但不同的是，Gao算法是通過概率計(jì)算節(jié)點(diǎn)冗余性。節(jié)點(diǎn)冗余概率的具體計(jì)算過程為：

上式中的n表示概率節(jié)點(diǎn)的鄰居節(jié)點(diǎn)個數(shù)。同時(shí)，節(jié)點(diǎn)沒有被n個鄰居節(jié)點(diǎn)覆蓋的期望為：

從上面兩個計(jì)算公式可以看出，如果某個節(jié)點(diǎn)通信范圍內(nèi)存在11個一跳鄰居節(jié)點(diǎn)，則該節(jié)點(diǎn)有90%以上的概率具有完全的冗余性，如果某個節(jié)點(diǎn)通信范圍內(nèi)存在5個一跳鄰居節(jié)點(diǎn)，則該節(jié)點(diǎn)的冗余覆蓋面積超過了90%。

Gao算法的主要優(yōu)勢同樣是不依靠節(jié)點(diǎn)的具體坐標(biāo)，可節(jié)省節(jié)點(diǎn)能耗，降低網(wǎng)絡(luò)系統(tǒng)成本。但其不足之處同樣是計(jì)算節(jié)點(diǎn)冗余性時(shí)只考慮了節(jié)點(diǎn)通信范圍內(nèi)局部鄰居節(jié)點(diǎn)的影響因素，然而由于算法利用概率公式求解，其計(jì)算精確性比Ditian算法更為可靠。

結(jié)語

從20世紀(jì)開始，WSN區(qū)域覆蓋技術(shù)逐漸進(jìn)入人們視野并得到了大力發(fā)展，對WSN的應(yīng)用起到了極大作用。除了文章中所提到的節(jié)點(diǎn)調(diào)度算法，國內(nèi)外還有很多相關(guān)研究成果正處于完善階段或者已投入實(shí)際應(yīng)用。現(xiàn)階段的節(jié)點(diǎn)調(diào)度算法各有優(yōu)勢與不足，具有各自的應(yīng)用場景。未來的區(qū)域覆蓋技術(shù)除了從均衡節(jié)點(diǎn)能耗以及轉(zhuǎn)換節(jié)點(diǎn)狀態(tài)方面提高未來覆蓋質(zhì)量，還可以從節(jié)點(diǎn)密度以及網(wǎng)絡(luò)連通性方面進(jìn)行更多的探索和研究。

參考文獻(xiàn)

[1]Zhu Chuan， Zheng Chun-lin， Shu Lei， et al. A survey on coverage and connectivity issues in wirelesss sensor networks[J].Journal of Network and computer Applications， 2012，35（2）：619-632.

[2]凡高娟，孫力娟，王汝傳，等.距離輔助的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋判別模型[J].通信學(xué)報(bào)，2010，31（8）：128-133.

[3]樂俊，張維明，肖衛(wèi)東，等.一種能量高效和均衡的無線傳感器網(wǎng)絡(luò)分簇?cái)?shù)據(jù)融合算法[J].國防科技大學(xué)學(xué)報(bào)，2012，34（6）：66-71.endprint