無線傳感器網(wǎng)絡(luò)區(qū)域覆蓋技術(shù)研究綜述

楊秀杰+華江鋒

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

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

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

0 引言

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

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

1.1 HCA算法

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

在圖1中，監(jiān)測區(qū)域ABCD有n1、n2、n3和n4 4個節(jié)點，這4個節(jié)點監(jiān)測將區(qū)域ABCD劃分成9個子區(qū)域，即圖中的1～9所示區(qū)域。那么，這4個節(jié)點的覆蓋監(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é)點可以劃分為兩個集合。

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

1.2 NSS算法

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

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

1.3 PEAS算法

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

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

1.4 SPAN算法

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

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

1.5 Ditian算法

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

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

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

1.6 Gao算法

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

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

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

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

結(jié)語

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

參考文獻

[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é)點覆蓋判別模型[J].通信學(xué)報，2010，31（8）：128-133.

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