無線傳感器網絡區域覆蓋技術研究綜述

楊秀杰+華江鋒

摘 要：WSN區域覆蓋技術可以有效延長無線傳感器網絡（Wireless Sonsor Networks， WSN）的生存周期，一直都是人們研究的熱點問題之一。在保證網絡覆蓋質量的基礎上，WSN區域覆蓋技術通過調度節點狀態，降低節點能耗從而延長網絡生存周期。本文對現階段典型的WSN區域覆蓋節點調度算法原理進行扼要說明，分析它們各自的優缺點并做出相關總結。

關鍵詞：WSN區域；NSS算法；Gao算法

中圖分類號：TN929 文獻標志碼：A

0 引言

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

1 典型的WSN節點調度算法

1.1 HCA算法

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

在圖1中，監測區域ABCD有n1、n2、n3和n4 4個節點，這4個節點監測將區域ABCD劃分成9個子區域，即圖中的1～9所示區域。那么，這4個節點的覆蓋監測區域分別為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的最優解為：M1={n1，n4}，M2={n2，n3}，即這4個節點可以劃分為兩個集合。

HCA算法的優點是設計直觀，可以有效延長網絡生命周期。它的缺點是由于該算法是根據節點位置計算覆蓋區域集合的，因此不宜擴展使用。而且，如果集合中的某些節點失效，就會大大影響該集合功能，甚至造成集合完全失效。

1.2 NSS算法

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

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

1.3 PEAS算法

PEAS算法在保證網絡質量的基礎上，盡可能地降低網絡能耗，使某些節點處于休眠狀態。只有當這些休眠節點周圍沒有工作節點時，它們才轉換為工作狀態，否則繼續保持休眠狀態。節點即使處于休眠狀態，也要不定期地進行自我喚醒并監測周圍環境。如果該節點發現鄰居節點中有失效節點便將自身喚醒，替代失效節點完成相應工作，從而保證網絡工作正常運行。因此，該算法包括環境探測與自適應休眠兩部分內容。

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

1.4 SPAN算法

SPAN算法是國外學者提出的一種基于構造骨干網絡的節點調度算法。在該算法中，總共有3種節點類型：骨干節點和非骨干節點。骨干節點是構成骨干網絡的節點，它處于工作狀態并能保證網絡覆蓋質量。而非骨干節點則是處于休眠狀態的節點。骨干網絡中的節點彼此之間可以連通，非骨干節點也要確保能和骨干節點彼此通信。骨干節點還被用來轉發網絡數據的節點，它的負擔工作較重，因此需要節點輪流替換完成相應功能。非骨干節點可以通過競選稱為骨干節點，其狀態也相應地由休眠狀態轉換為工作狀態。整個骨干網絡都是在動態變化的，節點的狀態也會不斷轉換。

SPAN算法的優點是對各個節點狀態的工作做出明確劃分，同時盡可能地均衡節點能耗，因此在延長網絡生命周期方面具有一定優勢。該算法的主要不足是設計較為復雜，節點狀態轉換較為頻繁，同時由于骨干節點的負擔工作較重，因此會消耗較多能量，而且該算術對傳感器網絡的連通性也有一定要求。

1.5 Ditian算法

Ditian算法也是一種分布式算法，它通過節點間的幾何關系判斷節點是否冗余，在保證網絡覆蓋質量的基礎上讓冗余節點處于休眠狀態，從而降低節點能耗。算法原理圖如圖2所示。

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

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

1.6 Gao算法

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

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

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

Gao算法的主要優勢同樣是不依靠節點的具體坐標，可節省節點能耗，降低網絡系統成本。但其不足之處同樣是計算節點冗余性時只考慮了節點通信范圍內局部鄰居節點的影響因素，然而由于算法利用概率公式求解，其計算精確性比Ditian算法更為可靠。

結語

從20世紀開始，WSN區域覆蓋技術逐漸進入人們視野并得到了大力發展，對WSN的應用起到了極大作用。除了文章中所提到的節點調度算法，國內外還有很多相關研究成果正處于完善階段或者已投入實際應用。現階段的節點調度算法各有優勢與不足，具有各自的應用場景。未來的區域覆蓋技術除了從均衡節點能耗以及轉換節點狀態方面提高未來覆蓋質量，還可以從節點密度以及網絡連通性方面進行更多的探索和研究。

參考文獻

[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]凡高娟，孫力娟，王汝傳，等.距離輔助的無線傳感器網絡節點覆蓋判別模型[J].通信學報，2010，31（8）：128-133.

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