基于區域內隨機喚醒機制的WSN覆蓋控制方法

鄧鑫，張樂君

(哈爾濱工程大學計算機科學與技術學院，黑龍江哈爾濱150001)

無線傳感器網絡(WSN)是由大量微型傳感器節點構成的，這些微型傳感器結構簡單，計算能力和電池能量等資源有限。因此通常采用節點高密度部署的方法(20 node/m3)［1］來提高網絡的整體工作性能、延長網絡生命周期。如果這種高密度部署的傳感器節點同時工作，勢必會導致無線信息干擾、能量耗費和信息大量冗余等問題，所以節點調度技術就成為了延長網絡工作時間、保證網絡工作質量的重要技術之一。節點調度技術是指通過調度方法合理轉換節點狀態，以達到在保證網絡需求覆蓋質量(QoC)的前提下節省節點能量，延長網絡生命周期的目的。

本文利用傳感器節點可以通過控制功率來調整通訊半徑的特性，給出了控制工作節點間相對距離的方法及網絡覆蓋度與相對距離的關系，并在此基礎上提出了基于限定區域內隨機喚醒機制的WSN覆蓋控制協議(random wake-up mechanism within a limited region，RWMLR)。

目前針對傳感器網絡覆蓋控制的問題已取得了一定的進展。Hefeeda等利用了幾何圓盤覆蓋的特性，針對圓盤感知模型提出了基于VC維和ξ-net的隨機選擇活躍節點的方法，并給出了該方法的集中式和分布式實現方案 RKC 和 DRKC［2］。Zou 等［3］提出了基于蟻群算法的傳感器網絡的節能覆蓋算法。孟凡治等［4］提出了的基于聯合感知模型的連通覆蓋控制協議，該協議分析了在節點隨機部署方式下，網絡覆蓋質量和網絡連通性與工作節點個數、監測區域面積和節點性能參數的關系。Zhang等［5］針對三維區域的覆蓋控制問題提出了基于概率模型的覆蓋控制算法，該算法能達到覆蓋度要求，但是在該算法中傳感器節點的能量消耗較大。王換招等［6］分析了傳感器感知半徑服從正態分布的無線傳感器網絡冗余度計算模型，以及保證網絡覆蓋質量所需最少工作節點的計算模型，并且在此基礎上提出了一種高效節能的無線傳感器網絡覆蓋保持協議(energy efficient coverage conserving protocol，EECCP)。李超良等［7］提出了一種節點覆蓋率和連通率的計算方法，該方法能描述節點感知半徑、檢測區域邊長以及節點數量與覆蓋率、網絡連通率之間的關系，計算所需節點數量，該方法考慮檢測邊界對覆蓋的影響。文獻［8］提出了一種節點判定是否為k重覆蓋的算法，并且提出了CCP(coverage configuration protocol)協議，該協議可以根據應用生成不同覆蓋度的網絡，并且在文中給出了通訊半徑大于等于感知半徑2倍時，能保證網絡的連通性。Zhou等［9］提出了基于多目標優化的能量平衡消耗的傳感器網絡覆蓋控制算法。

上述研究都是在節點的通訊半徑固定的基礎上展開的，而在文獻［10］中指出傳感器節點可以通過控制發送功率來改變其通訊半徑。本文針對這種由可變通訊半徑的傳感器節點所組成的高密度均勻部署的傳感器網絡的覆蓋控制問題進行研究。

1 網絡模型和相關理論

1.1 網絡模型及問題描述

假設傳感器網絡具有如下性質:

1)網絡中所有節點都均勻的隨機分布在一個平面區域Z內，并且密度足夠大(20 nodes/m2)。

2)每個傳感器節點的感知區域為圓形，即若感知半徑為RS，其感知區域面積S=πRs2。

3)節點采用布爾感知模型，即在感知范圍內的區域都能被傳感器所感知，屬于有效感知區域。

4)節點通訊半徑可通過調節發射功率來放大或縮小，且網絡工作時通訊半徑大小與節點感知半徑大小關系為Rc≥2Rs，以保證網絡連通性［8］。

5)所有傳感器感知半徑相同，能耗模型相同，無GPS系統。

本文要解決在上述網絡模型中，如何通過調度節點使得網絡在達到要求覆蓋度的前提下，生成覆蓋區域Z的最小節點集，從而延長網絡工作時間。

1.2 相關定義

定義1 鄰居節點集:對于任意節點i∈?，其鄰居節點集的定義為V(i)={j∈?|d(i，j)＜Rc，i≠j}，其中?為部署在區域Z中所有節點的集合，d(i，j)表示節點i和節點j之間的物理距離，Rc表示節點i的通訊半徑。

定義2 冗余覆蓋面積:對于全體節點集合中任意工作節點i，它與其鄰居節點集中任意工作節點感知區域重合部分的面積即為冗余覆蓋面積Sr=Si∩Sj(j∈V(i))，其中Si表示節點i的感知區域面積，Sj表示節點j的感知區域面積。

定義3 網絡覆蓋度:網絡中所有工作節點形成的監測區域總面積占被監測區域Z面積的百分比，稱為網絡的覆蓋度。即

定義4 覆蓋目標區域的最小節點集合:由文獻［11］可知完全覆蓋特定區域的最少圓集合的模型如圖1所示。

圖1 覆蓋區域最小圓集合模型Fig.1 Minimum circle of coverage set model

在感知半徑RS相同的條件下，傳感器節點間距離為，即每個節點有6個鄰居節點時，區域覆蓋度為100%且所生成的區域覆蓋圓集為最少覆蓋圓集，其對應的傳感器節點集為覆蓋區域的最少節點集。

定義5 限定區域:對于任意節點i∈?，其工作時產生的外點限定區域為S(K)={K|ε1Rs＜d(K，i)≤ε2Rs}，內點限定區域為S(K)={K|d(K，i)≤ε1Rs}，其中 ε1、ε2為傳感器通訊半徑參數，且1.5 ≤ε1＜ε2≤2，如圖 2所示。

圖2 限定區域示意圖Fig.2 Limited region schematic

2 網絡覆蓋質量分析

引理1若2個距離為εRs的鄰居節點產生的冗余覆蓋面積為Sr，那么

式中:Rs為節點的感知半徑，ε為通訊半徑參數，并且ε≤2。

證明:如圖3所示，陰影部分為傳感器節點O1，O2所產生的冗余面積為Sr，O1、O2之間的物理距離為 εRs。

則Sr=2*(S扇ABO2－ SΔABO2)

證畢。

圖3 節點冗余面積圖Fig.3 Redundant area of working nodes

定理1設網絡最低復雜度要求為k，達到最低復雜度要求時，鄰居節點距離均為εRs，則

式中:ε為通訊半徑參數。

證明:若使網絡達到最低復雜度要求則節點間的距離達到最遠距離，即εRs。如圖4所示A、B、C為網絡中3個工作節點，且任意兩個不同節點間的物理距離為εRs，圖中虛線部分區域為節點間的冗余覆蓋區域，網格部分區域為覆蓋盲區。

圖4 最壞覆蓋度示意圖Fig.4 Worst coverage degree schematic

則3個工作節點對△ABC區域的覆蓋度為:

∵ △ABC為等邊三角形，且邊長為εRs

又∵式(1)

證畢。

由式(2)的函數圖象可知k與ε的關系如圖5所示。由式(2)可以得出，當通訊半徑參數為2時網絡的覆蓋度達到最低點，約為90.8%。并且從圖中可以看出網絡覆蓋度隨通訊半徑參數的增大而降低。因此將網絡要求覆蓋度視為網絡最壞覆蓋度來計算網絡通訊半徑參數，然后按照RWMLR協議所生成的傳感器網絡覆蓋都不小于要求的網絡覆蓋度。

圖5 最壞覆蓋度與通訊半徑參數關系Fig.5 Relationship between worst coverage degree and transmission parameter

3 RWMLR協議

由定義4可知，若要在保證不同的覆蓋質量的前提下利用最少的節點生成網絡，則節點間的物理距離應該保持在，左右。由定理1可知，網絡覆蓋度僅與通訊半徑參數有關，因此本協議的目的是根據網絡需求的覆蓋質量，合理的調整通訊半徑參數，使生成的網絡中工作節點保持合理的物理距離。

3.1 協議描述

在協議開始工作前，傳感器節點根據覆蓋度要求由式(2)計算出傳感器網絡達到最低覆蓋度要求時的通訊半徑參數。網絡初始狀態時所有的傳感器節點處于休眠狀態，在網絡中隨機選取一個節點轉換為工作狀態。

開始工作的節點會根據要求覆蓋度計算出的通訊半徑參數，并以ε1Rs和ε2Rs為通訊半徑兩次廣播Hello包，對其鄰居節點區域進行內點區域和外點區域的劃分。Hello包中包含3個域:包類型域，節點編號域和節點狀態域。收到兩個Hello包的區域為內點區域，收到一個Hello包的區域為外點區域。因此外點與工作節點間的距離被限制為d∈［ε1Rs，ε2Rs］。由定理1可知網絡的最差覆蓋率只與通訊半徑參數有關，因此在外點區域內喚醒節點而產生的覆蓋度是可控的。工作節點會根據節點的優先級在外點區域內喚醒休眠節點。當工作節點的能量即將耗盡時，工作節點會根據節點優先級在內點區域內喚醒節點。

3.2 節點優先級確定

節點初始優先級為零，若i工作節點，則i的外點集中的節點優先級加1，內點集中的節點優先級減1。如圖2所示陰影部分區域中的節點優先級為1，非陰影部分的節點優先級為 －1。

3.3 節點狀態轉換模型

本協議分為兩個階段，初始化階段和穩定階段。網絡中每個節點都有6種狀態:選舉狀態(ELECTION)，工作狀態(WORK)，失效狀態(DEAD)，休眠狀態(SLEEP)，預工作狀態(PRE_WORK)，預睡眠狀態(PRE_SLEEP)。

初始化階段中，被選定的節點開始工作時會觸發其外點限定區域內的節點從SLEEP狀態轉換為ELECTION狀態。ELECTION狀態的節點向觸發其狀態轉換的工作節點發選舉消息，工作節點選擇優先級高的節點并使其轉換為PRE_WORK狀態，優先級低的節點轉為SLEEP狀態。處于PRE_WORK狀態的節點等待時間T，若在此時間段內被選為工作節點則節點轉換為WORK狀態;否則將節點狀態轉換為SLEEP狀態。

在穩定階段中所有工作節點的選取發生在有節點失效的區域。當節點即將失效時會觸發其內點限定區域中的節點轉為ELECTION狀態，剩余過程與初始化階段節點狀態轉移相同。因為節點失效與新節點選取都是在小范圍區域內進行，從而不影響整個傳感器網絡的感知工作。網絡中的狀態轉換如圖6所示。

圖6 網絡中節點狀態轉移圖Fig.6 Node state transition diagram

4 RWMLR協議性能分析

為了檢驗協議的性能，使用omnet++作為仿真實驗平臺。實驗中監控區域大小為20×20 m2，節點的能耗模型為文獻［4］中所采用的實驗節點能耗模型，即發送接收和休眠狀態的能耗比例為20∶4∶0.01。

圖7為初始節點規模不同的情況下，網絡的覆蓋質量和所要求達到的覆蓋質量之間的關系。可以看出本文所提出的協議能夠保證網絡的覆蓋質量高于要求的覆蓋質量，由于節點的通訊參數是按照所要求的網絡最低覆蓋度計算出的，因此網絡實際覆蓋質量會略高于所需要的覆蓋質量，但是從圖中可以看出隨著要求覆蓋度的增加，本協議所生成的網絡覆蓋度與最優覆蓋度的差距逐漸減小。

圖7 需求覆蓋質量與實際覆蓋質量的關系Fig.7 Relationship between require coverage degree and real coverage degree

圖8 滿足不同的QoC網絡的工作時間Fig.8 Network working time under different Qocs

如圖8所示為在區域中部署5 000個節點時，網絡在不同的覆蓋質量要求下工作的時間，從圖中可以看出在不使用調度策略時，網絡中所有的節點始終工作，并且保證網絡的覆蓋度始終保持在100%，但是在很短的時間內隨著節點的能量耗盡網絡的覆蓋度迅速下降;在使用了本協議調度節點后，網絡中的傳感器節點輪流工作，降低了冗余覆蓋面積，有效的減少了網絡中的能量消耗，如圖所示達到同樣覆蓋度的情況下，網絡工作時間比不使用調度策略的工作時間延長了約1.3倍。但是由于網絡中的節點是隨機分布的，不同區域內節點分布不均勻，覆蓋度并沒有快速下降為0。

為了進一步體現本協議的性能，取不需要地理位置的LDAS［12］協議作為比較。實驗結果如圖9、圖10所示。如圖9所示，網絡中不同時間階段工作節點數量LDAS協議普遍高于本文提出的協議。由圖10可知其網絡覆蓋度在達到要求覆蓋度的同時也比本文提出的協議高。這是由于LDAS協議判斷節點自身冗余度時，沒有考慮到其兩跳鄰居節點對覆蓋度做的貢獻，因此網絡中仍然存在許多的冗余節點。從這兩種協議的比較中得出RWMLR協議在保證達到要求的冗余覆蓋度的同時，有效的減少了網絡中冗余節點的數量，從而延長了網絡的工作時間。

圖9 工作節點數量對比Fig.9 Comparison of the number of working nodes

圖10 獲得網絡覆蓋度對比Fig.10 Comparison between network coverage degrees

5 結束語

本文針對通訊半徑可控的傳感器節點組成的傳感器網絡覆蓋度進行了分析，給出了覆蓋度與通訊半徑參數之間的關系，提出了基于限定區域內隨機喚醒機制的覆蓋控制方法(RWMLR)。仿真實驗表明，本協議可以在保證網絡覆蓋度的前提下，使盡量少的傳感器節點進入工作狀態，從而減少了網絡的整體能耗，延長了網絡生命周期。并通過對比實驗體現出本協議的優越性。

［1］SHIH E，CHO S H，ICKES N，et al.Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks［C］//Proc of the 7th Int＇l Conf on Mobile Computing and Networking(MobiCom).Rome:ACM Press，2001:272-287.

［2］HEFEEDA M.Randomized k-coverage algorithms for dense sensor networks［C］//INFOCOM 26th IEEE International Conference on Computer Communications.Anchorage，AK，2007:2376-2380.

［3］ZOU Ming，ZHANG Ping.A novel energy efficient coverage control in WSNs based on ant colony optimization［C］//2010 International Symposium on Computer，Communication，Control and Automation.Tainan，China，2010:523-527.

［4］孟凡治，王換招，何暉.基于聯合感知模型的無線傳感器網絡連通性覆蓋協議［J］.電子學報，2011，39(4):772-779.MENG Fanzhi，WANG Huanzhao，HE Hui.Connected coverage protocol using cooperative densing model for wireless sensor networks［J］.Acta Electronica Sinica，2011，39(4):772-779.

［5］ZHANG Junqing，WANG Ruchuan.A coverage control algorithm based on probability model for three-dimensional wireless sensor networks［C］//2012 11th International Symposium on Distributed Computing and Applications to Business，Engineering ＆ Science，(s.l.)，2012:169-173.

［6］王換招，孟凡志，李增智.高效節能的無線傳感器網絡覆蓋保持協議［J］.軟件學報，2010，12(21):3124-3137.WANG Huanzhao，MENG Fanzhi，LI Zengzhi.Energy efficient coverage conserving protocol for wireless sensor networks［J］.Journal of Software，2010，12(21):3124-3137.

［7］李超良，邢蕭飛，劉躍華.一種新型覆蓋連通率計算方法［J］.計算機應用，2011，12(31):3204-2306.LI Chaoliang，XING Xiaofei，LIU Yuehua.New method of calculating coverage and connectivity rate［J］.Journal of Computer Applications，2011，12(31):3204-2306.

［8］XING Guoliang，WANG Xiaorui.Integrated coverage and connectivity configuration for energy conservation in sensor networks［J］.ACM Transactions on Sensor Networks，2005，1(1):36-72.

［9］ZHOU Hui，LIANG Tian.Multiobjective coverage control strategy for energy-efficient wireless sensor networks［J］.International Journal of Distributed Sensor Networks，2012:1-10.

［10］JIANG J R，SUNG T M.Maintaining connected coverage for wireless sensor networks［C］//The 28th International Conference on Distributed Computing Systems Workshops.Beijing，China，2008:297-302.

［11］汪學清，楊永田.無線傳感器網絡中連通與覆蓋問題的研究［J］.計算機工程與應用，2006，42(36)，136-139.WANG Xueqing，YANG Yongtian.Research on connectivity and cover age problem of wireless sensor networks［J］.Computer Engineering and Applications，2006，42(36):136-139.

［12］WU K，GAO Y，LI F，et al.Lightweight deployment-aware scheduling for wireless sensor networks［J］.ACM/Kluwer Mobile Networks＆ Applications(MONET)，2005，10(6):837-852.