監測無線傳感器網絡休眠調度算法

毛建兵，田永春，姜永廣

（中國電子科技集團公司第三十研究所，四川 成都 610041）

0 引言

無線傳感器網絡[1]是一種攜帶多種類型的微型傳感器元件，通過在監測區域內大量密集部署構成一個自組織網絡完成感知信息收集并分析處理的應用型網絡。傳感器網絡低成本、低功耗、無人值守、網絡化信息感知等優點使得其在民用和軍用上均體現出極高的應用價值，被譽為21世紀改變世界的十大新技術之一[2]。受限于工作環境條件，傳感器網絡節點能量供應通常依賴于電池，并且在使用過程中難以更換或是進行充電補充。能量的限制是影響傳感器網絡廣泛應用的關鍵問題之一[3]。

提高能量利用效率和延長網絡壽命是無線傳感器網絡設計的首要目標。相對于傳感器網絡節點其它功能模塊，通信模塊是能量消耗的主要部分[4]。因此，通信節能措施成為一直以來研究的重點。通信節能可以從2個方面進行考慮[5-6]：①功率控制，通過為節點選擇合適的發射功率避免無謂的功率消耗；②休眠調度，通過控制傳感器網絡節點在活躍狀態和休眠狀態之間合理切換，降低網絡整體能耗。

面向長時間監測應用的任務需求，無線傳感器網絡休眠控制技術提出了如下要求：

1）在滿足應用要求的條件下，應該盡可能多地讓冗余節點進入休眠狀態，減少區域能量消耗。

2）在適當的時機，休眠節點喚醒并接替活躍節點的任務，避免節點之間能量消耗水平的不均衡性，延長系統任務執行的生命時間。

3）在任意時間，網絡所覆蓋的區域保持一個連通的網絡，避免網絡出現區域分割而喪失完整系統的監測能力。

4）在目標事件發生時，傳感器網絡節點獲得的感知信息應該能夠保證及時、快速地向sink節點報告并處理，保證時效性。

5）休眠調度對所采用的無線傳輸技術體制、路由算法、平臺硬件特性等沒有特殊的依賴性和約束限制，適應性良好。

6）集中式算法難以保證應用系統的可靠性和安全性，因此調度算法要求采用分布式設計。

針對上述應用要求，提出了一種分布式自適應休眠調度算法。算法運用了構建極大獨立集的思想，通過各個網絡節點的本地鄰居信息交互和啟發式算法執行，動態自適應地調度決定節點的休眠與活躍工作狀態，在保證網絡連通的條件下使得活躍節點數量盡可能小，提高節點能量的利用效率。

1 系統模型

考慮一個區域監測覆蓋隨機部署的無線傳感器網絡，網絡中包含一個sink節點和若干個相同配置的傳感器節點。網絡隨機部署后，各節點相互連接構成一個全局連通的網絡，其中sink節點為網絡的信息匯聚中心，傳感器節點采集的各類感知數據均向sink節點進行遞交上報。面向目標監測應用，傳感器節點感知數據的獲取通常以目標事件為驅動，并在事件發生的整個過程中持續采集上報信息。

傳感器網絡節點部署工作之后，sink節點首先采用廣度優先搜索方法進行網絡發現和初始化，向網中廣播發送probe報文。報文中攜帶一個level計數器，各網絡節點收到probe報文后將level計數加1然后轉發。為了避免廣播冗余轉發，節點只轉發level值小于當前已收到的最小level的probe報文。這樣，通過sink節點的probe報文搜索，每個傳感器節點將獲得所處位置到 sink節點的通信層次距離，稱為層次級別。

2 節能休眠調度策略

由于大量節點密集部署的隨機性，無線傳感器網絡不可避免地存在很大一部分冗余節點。冗余節點在監測過程中被認為是能力過剩的多余節點。因此，如果整個網絡所有節點同時進行工作，不僅造成不必要的資源浪費，還會使得監測數據收集存在嚴重的高度相關性和冗余性，增加通信傳輸的沖突和開銷。

為了有效利用冗余節點資源，延長網絡使用時間，在不影響系統效能的條件下，自適應地對網絡節點進行有規律地休眠和喚醒調度操作，使得節點之間以輪替的方式交互進行工作，降低能量消耗速率，平衡各個節點的剩余能量水平，避免某些節點過早地能量耗盡而失效，致使整個傳感器網絡喪失應有的效能。

為了實現節點之間的輪替交互工作，休眠調度采用周期性調度方式。如圖1所示，網絡節點工作時間按周期T進行劃分，在每個周期T開始，所有網絡節點執行休眠調度算法。根據調度結果，各個網絡節點在周期T剩余時間內進行休眠或是保持活躍狀態。

圖1 休眠調度控制

監測應用中，由于事先并不知道目標事件何時何地發生，因此傳感器網絡節點需要時刻保持感知“警惕”。在節點休眠過程中，可能因為目標事件的突然發生，節點收集獲得的數據需要立即向sink節點遞交上報，因此休眠節點周圍需要至少存在一個一跳可見的鄰居活躍節點，并且鄰居活躍節點能夠通過其它活躍節點完成向 sink節點的多跳中繼轉發，即活躍節點要形成網絡的連通骨干。為了更多地節能，調度算法還需要使得網絡中活躍節點數量盡可能少。

從數學模型角度分析，上述休眠調度問題可以視為求解最小連通支配集問題。在任意圖中求解最小連通支配集是NP（Non-deterministic Polynomial）問題[7]，因此在實際應用中通常采用啟發式算法來近似求解。傳感器網絡節點數量非常多，采用集中式算法依賴于網絡全局拓撲信息的獲取，實現上比較困難[8]。本文采用分布式算法設計，節點只需要知道鄰居信息。

3 算法設計

3.1 鄰居信息交互

在調度算法執行時間開始，每個節點首先廣播hello-1報文，表明自己的狀態。報文中包含節點的身份 ID，初始總能量信息tE，當前剩余能量信息Er，能量消耗速率 Ri（前一調度周期能量消耗量），節點層次級別 Li。這樣，每個節點在hello-1報文信息交互之后，可以收集獲得其所有1跳鄰居完整的狀態信息。

連通度反應了節點的通信覆蓋能力。為了使得每個節點能夠進一步掌握鄰居節點的連通度信息，節點發送第2輪hello-2報文。報文中攜帶節點連通度iC、身份ID等內容。

3.2 休眠調度控制

節點在獲得鄰居信息之后，采用啟發式機制在本地決定自身的休眠/活躍工作狀態。支配集節點的選取運用了構建極大獨立集的思想。初始時刻，節點狀態state均置0，執行算法設計如下：

1）節點比較自己的層次級別 Li和所有鄰居的層次級別 Lj，找出所有 Li= Lj的節點構成集合A，集合大小|A | = m 。

2）集合A中，將節點的連通度 Ci進行大小排列，即 C1≥ C2≥ … Cm，并分別計算各個節點的能量水平Ei= ErEt。

3）節點根據下列條件判斷是否成為支配節點：

條件1 如果節點是其中連通度最大的節點，并且能量水平滿足ErEt＞Eth（Eth為一門限參數）以及Ri＜（為集合A中平均能量消耗速率），則節點將其自身狀態state變更為1。

條件 2 如果 A中不存在滿足上述條件 1的節點，則從 C1至 Cm依次查看各連通度大小的節點。如果連通度為 Ck的節點 k，其能量水平滿足Ek＞&Ek＞（為集合A中節點平均能量水平），則節點將其自身狀態state變更為1。

條件3 如果A中不存在滿足上述條件2的節點，則集合 A中能量水平最大的節點 i，即有 Ei=max ｛ E1, E2,… ,Em｝，將其自身狀態state變更為1。

4）狀態state = 1的節點成為新的支配節點，并發送dominating消息通告周圍鄰居，消息中包括節點ID和狀態state。

5）狀態state = 0的節點接收到dominating消息后，變更自身狀態為state = 2，成為被支配節點。節點記錄消息發送的支配節點的ID和state，然后發送dominated消息，向自己的鄰居通告自身狀態的改變。收到 dominated消息的節點相應地修改鄰居節點的state狀態記錄。

6）如果鄰居節點中仍有state = 0的節點存在，則節點剔除state≠0節點后再次重復執行算法1~6。

利用上述算法，網絡中所有節點被分為2類：支配節點和被支配節點。支配節點將在接下來的剩余周期時間內一直處于活躍工作狀態，執行數據的收集和轉發任務。由于支配節點的選取始終圍繞節點的一跳范圍鄰居開展，因此支配節點集合能夠有效保證任一節點至多經過三跳通信可達另一個支配節點。

為了進一步構造一個連通的支配集，需要選擇部分被支配節點作為連通節點將分散的支配節點相互連通。為了減少活躍節點數量，增加的連通節點數量應該盡可能地少，從而保證整個連通支配集網絡具有較小的能量消耗。

由于算法在支配節點的選取過程中，已經充分考慮了節點的層次級別，并且考慮到傳感器網絡數據傳輸以sink節點為中心的匯聚特性，連通節點的選取只需要在能夠連接相鄰層次級別支配節點的被支配節點中產生。

連通節點的選取算法設計如下：

1）對于state = 2的被支配節點，若其鄰居節點中同時存在屬于相鄰2個不同層次級別的state = 1的節點，則節點廣播發送connector消息，其中包括自身的ID和相鄰支配節點的ID。

2）支配節點收到 connector消息后，由層次級別更小的支配節點決定選擇哪個connector發送節點作為連通節點。選擇的依據為當前剩余能量最大的connector發送節點。

3）支配節點將選擇結果通告給 connector發送節點。

4）收到通告的 connector發送節點確認自己的連通節點身份，修改狀態為state = 3，并廣播通告周圍鄰居節點。收到通告的節點將其記錄為一個新的支配節點進行使用。

通過上述算法執行，節點state = 1&3的節點成為網絡的連通支配集，在接下來的調度周期時間內一直工作，構成網絡數據傳輸的主干。其余state = 2的節點則可以進入休眠狀態，根據自身需要或在異常事件發生時喚醒，通過鄰居支配節點向sink節點發送數據。

為了保證節點將能量消耗的平衡性，算法設計節點周期性地調度決定自身的工作狀態。在一個周期時間結束之后，所有休眠節點通過定時器喚醒，再次執行調度算法，決定下一個周期的工作狀態。

4 算法性能分析

通過仿真技術對算法進行比較分析。場景設定如下：在1 000 m×1 000 m大小的區域內，采取隨機方式布設一定數量為n的傳感器節點，sink節點位于區域的中心。節點初始能量2J，在每個周期時間T=600 s內將有 10個節點隨機產生業務量128 byte的事件通告數據向sink節點傳輸。采用與文獻[9]相同的經典能耗模型，假設節點發送和接收的能耗為 5 0 nJ/bit，傳輸能耗為 1 00pJ/bit/m2。網絡中節點采用最短路徑優先算法確定向sink節點轉發的選路。此外，節點在活躍狀態下單位時間能耗為10 uJ/s，在休眠狀態下單位時間能耗為100 nJ/s。節點失效的能量閾值為0.05 J。

仿真試驗將提出的算法與文獻[10]基于節點 ID的調度算法擴展多點中繼（EMPR，Extended Multipoint Relays）進行比較，分別對比分析了在不同網絡節點數量條件下的活躍節點數量和網絡生命周期大小，算法中thE 門限參數設置為 0.5。如圖 2所示，分析結果表明，在一定的網絡覆蓋區域大小內，良好的調度算法設計使得節點數量的增加并不會導致最終活躍節點數量的大幅增加，新的調度算法也保持了較小的活躍節點數量。

網絡生命周期以第1個節點“失效”前網絡持續的有效工作時間為準。如圖3所示，與EMPR算法相比，新設計的算法由于考慮了冗余節點能量的利用，因此使得網絡獲得了更長的生命周期。并且可以看到，隨著網絡節點數量的增加，冗余節點也不斷增加，更多節點通過調度算法參與輪替交互工作，使得網絡的生命周期越來越長。

圖2 網絡活躍節點數量分析

圖3 網絡生命周期分析

5 結語

面向監測應用的無線傳感器網絡，冗余節點大量存在。研究提出了一種休眠調度算法，通過分布式算法執行，綜合考慮節點層次級別、實時的能量消耗、連通度等因素進行休眠控制，使得節點之間輪替交互工作，提高能量利用效率。仿真分析結果表明，算法能夠很好地控制網絡中活躍節點數量，提升網絡生命周期時間性能。

[1] 夏少波, 許娥.無線傳感器網絡WSN探究[J].通信技術,2010,43(08):18-19.

[2] 李建中, 高宏. 無線傳感器網絡的研究進展[J]. 計算機研究與發展, 2008, 45(01): 1-15.

[3] 王彥明, 朱怡安, 龔彬. 基于 Mobile Agent的無線傳感器網絡管理框架[J].信息安全與通信保密, 2008(06):98-101.

[4] ANASTASI G, CONTI M, FRANCESCO M D, et al. Energy Conservation in Wireless Sensor Networks: A Survey[J]. Ad Hoc Networks, 2009, 7(03): 537-568.

[5] PODURI S, PATTEM S, KRISHNAMACHARI B, et al. A Unifying Framework for Tunable Topology Control in Sensor Networks[R].USA:University of Southern California, 2005:1-15.

[6] 吳雪, 馬興凱. 無線傳感器網絡拓撲控制策略研究[J].通信技術, 2009, 42(03): 161-163.

[7] 唐勇, 周明天. 基于極大獨立集的最小連通支配集的分布式算法[J]. 電子學報, 2007, 35(05): 868-874.

[8] 曾曦. 論無線自組織網絡的基本原理與操作[J]. 信息安全與通信保密, 2009(05): 106-108.

[9] HEINZELMAN W R, CHANDRAKASAN A, BALAKRISHNAN H. An Application-specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications, 2002,1(04): 660-670.

[10] WU J, WEI L, DAI F. Extended Multipoint Relays to Determine Connected Dominating Sets in MANETs[J]. IEEE Transactions on Computers, 2006,55(03): 334-347.