無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度算法綜述

姜威

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

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

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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ú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）是可以感知和檢查外部世界的傳感器，是一種分布式傳感器網(wǎng)絡(luò)[1]，它是21世紀(jì)最具有影響力的科學(xué)技術(shù)之一；無(wú)線傳感器網(wǎng)絡(luò)具有規(guī)模大、成本低、資源高度受限、節(jié)點(diǎn)數(shù)目多和自組織等顯著的特點(diǎn)。WSN已經(jīng)廣泛應(yīng)用于環(huán)境監(jiān)控、目標(biāo)檢測(cè)、軍事民用、等多個(gè)領(lǐng)域。在這些應(yīng)用中，網(wǎng)絡(luò)生存時(shí)間是無(wú)線傳感器網(wǎng)絡(luò)監(jiān)測(cè)服務(wù)質(zhì)量的評(píng)價(jià)標(biāo)準(zhǔn)之一。

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

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

1 節(jié)點(diǎn)調(diào)度算法的含義和設(shè)計(jì)目標(biāo)

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

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

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

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

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

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

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

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

⑺ 簡(jiǎn)單性。目前傳感器的計(jì)算能力相當(dāng)有限，只有低開(kāi)銷(xiāo)的算法才適合傳感器節(jié)點(diǎn)。

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

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

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

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

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

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

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

3 結(jié)束語(yǔ)

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

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

參考文獻(xiàn)（References）：

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

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

[2] 胡湘華，楊學(xué)軍.傳感網(wǎng)節(jié)點(diǎn)調(diào)度方法綜述[J].計(jì)算機(jī)工程與

科學(xué)，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ú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度算法及研究

進(jìn)展[J].宇航學(xué)報(bào)，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