無線傳感器網絡節點調度算法綜述

姜威

摘 要： 無線傳感器網絡以其自組織、低功耗、傳輸穩定等特點，被應用于監測平臺、預警系統、高度危險無人區域的監控系統。由于無線傳感器網絡中傳感器節點由電池供電，電池能量有限，因此能耗問題成為無線傳感器網絡發展和應用的阻礙，而節點調度是減少網絡能耗、延長網絡生存時間的重要機制之一。文章詳細描述了幾種節點調度算法，并對算法做出分析。

關鍵詞： 無線傳感器網絡； 能耗； 節點調度； 算法

中圖分類號：TP393 文獻標志碼：A 文章編號：1006-8228（2017）04-47-03

Abstract： Wireless sensor networks have been applied to the detection platform， early warning systems and highly dangerous no man's land monitoring system because of their characteristics like self-organization， low power consumption， transmission stability. For the sensor nodes in the wireless sensor network are powered by batteries， and battery energy is limited， the problem of energy consumption hinders the development and application of wireless sensor networks， and the node scheduling is one of the important mechanisms to reduce network energy consumption and extend the lifetime of network. This article describes several node scheduling algorithms and analyzes the algorithms.

Key words： wireless sensor networks； energy consumption； node scheduling； algorithm

0 引言

無線傳感器網絡（Wireless Sensor Networks，WSN）是可以感知和檢查外部世界的傳感器，是一種分布式傳感器網絡[1]，它是21世紀最具有影響力的科學技術之一；無線傳感器網絡具有規模大、成本低、資源高度受限、節點數目多和自組織等顯著的特點。WSN已經廣泛應用于環境監控、目標檢測、軍事民用、等多個領域。在這些應用中，網絡生存時間是無線傳感器網絡監測服務質量的評價標準之一。

在無線傳感器網絡中，傳感器節點是體積微小的嵌入式設備，一般靠電池供電。一方面由于節點體積及資源的受限，導致其能量極其有限；另一方面傳感器節點在惡劣的環境下工作，有可能使節點通信受到強烈的干擾甚至遭到破壞，造成能量消耗，無法及時進行能量補充，導致無線傳感器網絡無法維持正常的工作狀態。因此，在保證滿足網絡通信要求的情況下，如何做到盡可能的降低節點能耗以延長網絡的生命周期，就成為研究的重點和難點。對于這樣的問題，目前比較合理有效的方法是節點調度策略。

研究人員在節點調度這一領域開展了大量工作并取得一定的進展。本文綜述了近年來在該領域取得的一些研究成果。

1 節點調度算法的含義和設計目標

節點調度是指在不影響網絡服務質量（如網絡覆蓋、節點間的連通性）的前提下，將傳感器網絡中的冗余節點進入休眠狀態，使一部分節點保持活動狀態而另一部分節點進入休眠狀態，降低活動節點的密度，從而降低整個網絡能量消耗，延長網絡生存時間。

網絡壽命是節點調度方法的主要評價指標。但是，傳感器網絡的最終目的是完成應用相關的感知和傳輸任務。因此，完成任務的質量也是需要考慮的。除此之外，設計者還需要考慮算法的健壯性、可擴展性和簡單性等性能層次的目標[2]。

⑴ 網絡壽命。網絡壽命有多種不同的定義。最簡單的一種是：所有節點都保持正常的時間長度，亦或者定義為正常節點數目高于一定比例的時間。在實際應用中，WSN的網絡壽命定義往往需要結合考慮其他設計目標，主要包括下面列出的感知質量和通信質量。

⑵ 感知質量。感知信息是WSN的基本任務，感知質量是評價WSN性能重要指標。感知覆蓋率是一項基本的感知質量指標。不同類型的WSN任務對感知質量有不同的要求。例如，目標探測任務的感知質量又稱為探測質量，一般被定義為探測到入侵目標的概率和時間長度等；而環境監測任務的感知質量又稱為感知精度，一般被定義為收集到的環境信息的準確度。

⑶ 通信質量。通信能力是WSN的基本功能，通信質量也是評價WSN性能的重要指標。類似于感知覆蓋率，網絡連通度是一項基本的通信指標，用于衡量傳感器網絡維持節點間多跳聯通的能力。此外，對于實時采集任務來說，通信質量一般被定義為有效數據傳送比率以及傳送時間長度等。

⑷ 能耗均衡性。假如部分節點的能量消耗快于其他節點，那么一旦這些節點提前失效，很容易造成感知覆蓋的空洞和網絡的分塊。

⑸ 健壯性。節點失效在WSN中是常見的現象。例如，部署在災害現場的節點可能被爆炸損壞，處于休眠狀態的節點可能無法被喚醒，算法必須充分考慮各種無法預料的失效造成的后果，保證網絡在意外發生的情況下保持正常工作。

⑹ 可擴展性。WSN節點數量巨大，通信開銷隨鄰居數目呈線性或者更快的速度增長。因此，不具有擴展性的算法是不能被接受的。

⑺ 簡單性。目前傳感器的計算能力相當有限，只有低開銷的算法才適合傳感器節點。

2 典型的節點調度算法分析

基于節點均勻分布的假設，Wu等[3]人提出了一種基于部署特征的輕量級節點調度算法（Lightweight Deployment-Aware Scheduling，LDAS）。該算法假設節點無法獲取準確的位置信息，而是通過獲取鄰居節點的數量來實現概率覆蓋。如果鄰居節點數目超過某個閾值（根據應用對于感知覆蓋的需求來確定），該節點將從鄰居中隨機選擇部分節點，并發送關閉它們的通知。當一個節點接收到的關閉通知達到一定數量后，它將在一個隨機的退避時間間隔后進入休眠狀態。該算法不需要準確的位置信息和時間同步支持，保證概率覆蓋度，關閉通知的累積可以在一定程度上實現能耗的均衡分布。但是該算法假定節點均勻分布，需要維護鄰居節點的數量信息。

Berman等[4]人將節點調度問題視為具有電池壽命和網絡覆蓋度兩重約束的網絡壽命最大化問題（Maximization of Sensor Network Life，MSNL），給出了在保持K度覆蓋的前提下使網絡壽命最大化的分布式算法。節點可以處于活動、休眠和過渡狀態。過渡狀態下的節點通過判斷自己的感應區域能否被其他活動節點或者過渡節點所覆蓋，以決定轉換到活動狀態或休眠狀態。該算法通常能保證K度覆蓋。但是算法需要精確的位置信息，需要交換狀態的狀態信息、能量信息，并且沒有考慮并發問題，多個鄰居節點可能同時進入休眠狀態而產生覆蓋漏洞。

Yan等[5]人提出參考時間調度方法（Reference Time-based Scheduling Scheme，RTSS）算法，是一種基于時間序列的節點調度方法。整個監測區域被劃分為網格，設計目的是減少活動節點的數目，同時保證在連續時間內覆蓋所有的網格節點。RTSS把算法過程劃分為輪。在初始階段，每個節點會在[0，T]內隨機產生一個候選時刻（T是每輪調度的時間長度），然后廣播給位于兩倍傳感半徑范圍內的所有鄰居節點。對于自己覆蓋半徑內的每個節點位置，節點對所有覆蓋該位置的鄰居節點的參考時刻進行排序。對每個網格節點，節點活動狀態的起始時刻選擇在自己的候選時刻和前一個節點的參考時間的中間點。同樣，活動狀態的結束時刻選擇在自己的候選時刻和后一個節點的候選時刻的中間點。把所有被覆蓋的網格節點相關的時間表合并，就得到這個節點最終的調度時間表。為了提高健壯性，這種方法可以支持對制定位置的多重覆蓋。該算法實現簡單，維護了時間上連續的網絡覆蓋，基于時間序列的方式實現了負載均衡。但是算法需要精確地節點位置信息和時間的同步支持。

Liu等[5]提出了一種保證連通和局部覆蓋的隨機節點劃分調度方法（Random Coverage with Guaranteed Connectivity，RCGC）。該方法首先使用隨機調度方法為每個節點確定組號，然后每組節點工作時再調度其他組的節點進入活動狀態來保證連通性。該算法可以保證網絡連通和一定的覆蓋，將節點調度方法與能源有效的路由算法結合進行了討論，不需要位置信息，隨機調度方法實現簡單。但是，算法無法保證目標區域的完全覆蓋，隨機節點劃分方法沒有考慮節點能量差異。

Kumar[6]使用的是隨機獨立調度模式RIS（Random Independent Scheduling）。這種模式通過將時間分段成各個時隙來使各個時隙中的不同節點間的狀態相互不受到干擾，節點進入活動狀態或者進入休眠狀態由數值P來決定，P是一個概率值，從而可以使網絡生命周期延長1/P倍。該模式具有簡單易行、方便操作、消耗節點能量較少等優點。但是這種模式僅僅適用于節點分布稀疏的網絡中，而且受到節點失效問題的影響。

Slijepcevic等[7]根據延長無線傳感器網絡生命周期、大規模隨機拋灑節點產生的節點冗余等網絡特性，通過將所有傳感器節點的覆蓋范圍劃分成若干個覆蓋子集，這些子集互不相交，同一時刻只有一個子集節點處于工作狀態，各個子集通過一定的調度機制輪流對監測區域進行監控，從而達到優化網絡能量消耗并對整個監測區域形成完全覆蓋的目的。但是，該算法在如何劃分子集，劃分子集的數目才能達到最優是一個NP難問題，很難找到最優解。

3 結束語

本文從節點調度算法的必要性出發，對經典的節點調度算法進行了分析探討。如何在節點能量有限、生存時間較短還要保證網絡服務質量的情況下，利用節點部署的內在冗余特性，延長網絡生存時間，是無線傳感器網絡設計中的一個重要挑戰，也是要研究的一個重要內容。

目前的節點調度算法還存在許多待解決的問題，如：現有的無線傳感器網絡大多假設節點和sink節點位置固定，但在一些特殊的應用場景中節點和sink節點可以連續移動，如何合理的設計算法應對這種變化，同時保證算法的節能高效是一個非常值得研究的問題。此外，文中的算法大多是通過Matlab仿真軟件進行模擬，沒有在試劑的無線傳感器網絡應用環境中進行真實的實驗，真實的環境中，節點可能會受到溫度、濕度等各種因素干擾，如何將這些影響因素考慮進算法中也是值得研究的問題。總而言之，無線傳感器網絡節點調度算法是延長網絡生存時間的一種非常重要的思路，值得進一步深入研究。

參考文獻（References）：

[1] Akyildiz I， Su W， Sankarasubdam Y. Wireless sensor

networks： a survey[J]. Computer Networks，2002.38（4）：393-422

[2] 胡湘華，楊學軍.傳感網節點調度方法綜述[J].計算機工程與

科學，2008.30（3）：93-96

[3] Wu K， Gao Y， Li F， et al. Lightweight deployment-aware

scheduling for wireless sensor networks[J]. Mobile Networks & Applications，2005.10（6）：837-852

[4] Berman P， Calinescu G， Shah C， et al. Power efficient

monitoring management in sensor networks[J]. Proceedings of 2004 IEEE Wireless Communications and Networking Conference. Atlanta： IEEE Press，2004.4：2329-2334

[5] Yan T， He T， Stankovic J A. Differentiated surveillance for

sensor networks[C]// International Conference on Embedded Networked Sensor Systems，2003：51-62

[6] Kumar S， Lai T H， Balogh J. On k-coverage in a mostly

sleeping sensor network[J]. Wireless Networks，2008.14（3）：277-294

[7] Slijepcevic S， Potkonjak M. Power efficient organization of

wireless sensor networks[C]//IEEE International Conference on Communications. IEEE，2001.2：472-476

[8] Kumar D. Performance analysis of energy efficient

clustering protocols for maximising lifetime of wireless sensor networks[J]. Iet Wireless Sensor Systems，2014.4（1）：9-16

[9] 金巖，王玲，楊孝宗等.無線傳感器網絡節點調度算法及研究

進展[J].宇航學報，2007.28（5）：1086-1093

[10] Hai Mo， Zhang Yan-mei， Zhang Yue-jin. Survey on

clustering protocols in wireless sensor network[J].Computer Science，2015.42（1）：6-11