姜威

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

關鍵詞： 無線傳感器網(wǎng)絡； 能耗； 節(jié)點調(diào)度； 算法

中圖分類號：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 引言

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

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

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

1 節(jié)點調(diào)度算法的含義和設計目標

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

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

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

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

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

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

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

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

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

2 典型的節(jié)點調(diào)度算法分析

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

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

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

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

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

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

3 結(jié)束語

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

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

參考文獻（References）：

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

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

[2] 胡湘華，楊學軍.傳感網(wǎng)節(jié)點調(diào)度方法綜述[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] 金巖，王玲，楊孝宗等.無線傳感器網(wǎng)絡節(jié)點調(diào)度算法及研究

進展[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