無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度技術(shù)研究

邱樹(shù)偉

(汕頭職業(yè)技術(shù)學(xué)院,汕頭 515078)

無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度技術(shù)研究

邱樹(shù)偉

(汕頭職業(yè)技術(shù)學(xué)院,汕頭 515078)

探討了無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)硬件體系結(jié)構(gòu)和網(wǎng)絡(luò)體系結(jié)構(gòu);論證了無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度的必要性和價(jià)值;從網(wǎng)絡(luò)覆蓋度及連通性等角度分析了若干較有代表性的節(jié)點(diǎn)調(diào)度算法.

無(wú)線傳感器網(wǎng)絡(luò);傳感器節(jié)點(diǎn);節(jié)點(diǎn)調(diào)度;網(wǎng)絡(luò)覆蓋;連通

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,簡(jiǎn)稱WSNs)由部署在監(jiān)測(cè)區(qū)域內(nèi)的一組靜態(tài)微型的傳感器節(jié)點(diǎn)和一個(gè)固定的基站節(jié)點(diǎn)組成,是一個(gè)任務(wù)型的信息采集平臺(tái).傳感器節(jié)點(diǎn)通過(guò)人工配置、飛行器撒播或火箭彈射等方式部署在室內(nèi)/外,通過(guò)無(wú)線通信方式形成一個(gè)多跳的自組織網(wǎng)絡(luò)系統(tǒng),協(xié)作地實(shí)時(shí)感知、采集和處理感知對(duì)象的信息,并發(fā)送給觀察者.無(wú)線傳感器網(wǎng)絡(luò)在工業(yè)、軍事、農(nóng)林業(yè)、海洋、醫(yī)療、環(huán)境等領(lǐng)域應(yīng)用非常廣泛.

但是,由于支撐傳感器節(jié)點(diǎn)正常工作的能量十分有限,加上大部分監(jiān)測(cè)任務(wù)都要求網(wǎng)絡(luò)有較長(zhǎng)的生命期,因此,如何提高節(jié)點(diǎn)能量的使用效率,最大化網(wǎng)絡(luò)的生命期,是設(shè)計(jì)此類網(wǎng)絡(luò)的一個(gè)基本挑戰(zhàn).網(wǎng)絡(luò)的生命期通常被定義為最先因電池能量耗盡而失效的傳感器節(jié)點(diǎn)的生命期[1].

為了延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生命期,學(xué)者們長(zhǎng)期從事該類網(wǎng)絡(luò)的節(jié)能研究,并從硬件和軟件兩方面提出了多種有效的節(jié)能方法.本文著重討論了節(jié)點(diǎn)調(diào)度技術(shù),給出全局的節(jié)能解決方案.

1 無(wú)線傳感器網(wǎng)絡(luò)概述

1.1 節(jié)點(diǎn)體系結(jié)構(gòu)

通用傳感器節(jié)點(diǎn)主要由傳感器模塊、處理器模塊、通信模塊和能量供應(yīng)模塊等四個(gè)部分組成.傳感器模塊與具體應(yīng)用密切相關(guān),主要包括采集物理信息的傳感器和模數(shù)轉(zhuǎn)換(AC/DC)部件.其它三個(gè)模塊相對(duì)獨(dú)立,其中,處理器模塊負(fù)責(zé)對(duì)節(jié)點(diǎn)進(jìn)行控制和管理、存儲(chǔ)和處理本身采集的數(shù)據(jù)以及其它節(jié)點(diǎn)發(fā)來(lái)的數(shù)據(jù);通信模塊負(fù)責(zé)與其它節(jié)點(diǎn)進(jìn)行信息交換;能量供應(yīng)模塊提供節(jié)點(diǎn)運(yùn)行所需的能量.部分節(jié)點(diǎn)還包括定位系統(tǒng)和執(zhí)行模塊等[2][3].如圖1所示.

圖1 傳感器節(jié)點(diǎn)體系結(jié)構(gòu)

1.2 網(wǎng)絡(luò)體系結(jié)構(gòu)

無(wú)線傳感器網(wǎng)絡(luò)包括傳感器節(jié)點(diǎn)、匯聚節(jié)點(diǎn)和管理節(jié)點(diǎn)等.傳感器節(jié)點(diǎn)監(jiān)測(cè)到數(shù)據(jù)后,通過(guò)無(wú)線多跳的通信方式將數(shù)據(jù)傳送到匯聚節(jié)點(diǎn),匯聚節(jié)點(diǎn)再通過(guò)因特網(wǎng)、移動(dòng)通信網(wǎng)或衛(wèi)星等方式,與管理節(jié)點(diǎn)互聯(lián),最終由遠(yuǎn)程的觀察者來(lái)處理收集到的數(shù)據(jù).同時(shí),觀察者也可以通過(guò)管理節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)進(jìn)行配置、管理以及部署新的監(jiān)測(cè)任務(wù)等.傳感器節(jié)點(diǎn)不僅具備終端和路由雙重功能,而且還能進(jìn)行數(shù)據(jù)的存儲(chǔ)和處理等任務(wù),節(jié)點(diǎn)相互之間是一種協(xié)同的關(guān)系.

如果網(wǎng)絡(luò)規(guī)模較大,則可以采用聚類分層的管理模式.該模式將網(wǎng)絡(luò)劃分為若干個(gè)簇,每個(gè)簇由一個(gè)簇頭節(jié)點(diǎn)和若干個(gè)成員節(jié)點(diǎn)組成.這些簇頭節(jié)點(diǎn)互聯(lián)形成高一級(jí)的網(wǎng)絡(luò).在高一級(jí)的網(wǎng)絡(luò)中,又可以分簇,形成更高一級(jí)的網(wǎng)絡(luò)[4].如圖2所示.

圖2 無(wú)線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)

1.3 幾個(gè)典型的系統(tǒng)

目前,比較著名的無(wú)線傳感器網(wǎng)絡(luò)系統(tǒng)有弗吉尼亞大學(xué)的VigiNet,哈佛大學(xué)的Motelab以及加利福尼亞大學(xué)伯克利分校Trio等[5].由于不同系統(tǒng)有不同的應(yīng)用領(lǐng)域和需求,因此它們的規(guī)模、部署時(shí)長(zhǎng)、部署方式以及電源類型等有所不同.如表1所示.

表1 典型的無(wú)線傳感器網(wǎng)絡(luò)系統(tǒng)

2 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度探討

2.1 節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換

傳感器節(jié)點(diǎn)有四種狀態(tài):

工作狀態(tài)所有部件都處于工作狀態(tài),節(jié)點(diǎn)收集環(huán)境數(shù)據(jù)、收發(fā)消息以及對(duì)數(shù)據(jù)與消息進(jìn)行處理.

感知狀態(tài)感知部件和計(jì)算部件處于工作狀態(tài),通信部件關(guān)閉,節(jié)點(diǎn)不能收發(fā)消息.

通信狀態(tài)通信部件和計(jì)算部件處于工作狀態(tài),關(guān)閉感知部件,節(jié)點(diǎn)不能收集環(huán)境數(shù)據(jù).

睡眠狀態(tài)所有部件都被關(guān)閉,但節(jié)點(diǎn)可以通過(guò)定時(shí)器或其他方法激活.

傳感器節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換如圖3所示.圖中,四種節(jié)點(diǎn)狀態(tài)的能耗從低到高的順序是:睡眠狀態(tài)、感知狀態(tài)、通信狀態(tài)、工作狀態(tài)[2].

為簡(jiǎn)化本文的討論,將每個(gè)節(jié)點(diǎn)的狀態(tài)僅分為工作和休眠兩種.當(dāng)節(jié)點(diǎn)處于工作狀態(tài)時(shí)同時(shí)承擔(dān)感知和通信工作,而當(dāng)節(jié)點(diǎn)處于休眠狀態(tài)時(shí),節(jié)點(diǎn)不承擔(dān)任何工作,僅留較低的能量備用.

圖3 傳感器節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換圖

2.2 節(jié)點(diǎn)調(diào)度的必要性和價(jià)值論證

在無(wú)線傳感器網(wǎng)絡(luò)中,節(jié)點(diǎn)是體積微小的嵌入式設(shè)備,一般依靠電池供電,因而對(duì)能源的限制很大,加上節(jié)點(diǎn)的分布數(shù)量較多,且有些監(jiān)測(cè)環(huán)境非常惡劣,人們難以接近,因此要對(duì)所有節(jié)點(diǎn)可持續(xù)的補(bǔ)充能源非常困難.同時(shí),現(xiàn)時(shí)傳感器電池供應(yīng)技術(shù)的發(fā)展還不能夠讓節(jié)點(diǎn)在沒(méi)被替換或回收充電的情況下長(zhǎng)時(shí)間工作.近年來(lái),研究者積極研發(fā)先進(jìn)的節(jié)能方法,主要包括:節(jié)能傳感器硬件體系結(jié)構(gòu)的設(shè)計(jì)、優(yōu)化網(wǎng)絡(luò)拓?fù)涔芾?、改善路由算法、調(diào)節(jié)節(jié)點(diǎn)的發(fā)射功率等等.但是,以上各種方法仍無(wú)法明顯降低系統(tǒng)的能耗.

較合理的節(jié)能方法是節(jié)點(diǎn)調(diào)度技術(shù),即在保證網(wǎng)絡(luò)覆蓋范圍的基礎(chǔ)上,在一定的時(shí)空范圍內(nèi)合理的對(duì)節(jié)點(diǎn)進(jìn)行調(diào)度,選擇一部分節(jié)點(diǎn)進(jìn)入工作狀態(tài),而另一部分節(jié)點(diǎn)進(jìn)入睡眠狀態(tài)并在合適的時(shí)候被喚醒,節(jié)點(diǎn)進(jìn)行切換的同時(shí),其工作部件也進(jìn)行切換[6].

采用節(jié)點(diǎn)調(diào)度技術(shù)的原因有以下兩點(diǎn)[2]:

(1)傳感器節(jié)點(diǎn)收發(fā)器的狀態(tài)有:傳輸、接收、空閑和休眠四種.一般節(jié)點(diǎn)功耗比例為:傳輸狀態(tài)為0.38～0.7 W,接收狀態(tài)為 0.36 W,空閑狀態(tài)為0.34 W,休眠狀態(tài)為0.03 W,其中完全用于感知任務(wù)的能耗為0.02 W.研究表明空閑狀態(tài)的能耗同傳輸和接收狀態(tài)的能耗幾乎相等,由以上分析得知,為了節(jié)省能耗,應(yīng)盡量增加休眠節(jié)點(diǎn)的數(shù)量和節(jié)點(diǎn)休眠時(shí)間.

(2)為了提高監(jiān)測(cè)質(zhì)量,觀察者通常將傳感器節(jié)點(diǎn)大規(guī)模、高密度地部署在監(jiān)測(cè)區(qū)內(nèi),從而導(dǎo)致節(jié)點(diǎn)通信半徑內(nèi)的鄰居節(jié)點(diǎn)間有較高的重疊感知區(qū)域,并且鄰居節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)信號(hào)有較大的相關(guān)性(即對(duì)同一事件有多個(gè)節(jié)點(diǎn)對(duì)此產(chǎn)生相同的數(shù)據(jù)),觀察者并不需要來(lái)自所有節(jié)點(diǎn)的數(shù)據(jù),而且當(dāng)它們與基站通信時(shí)將不可避免地出現(xiàn)數(shù)據(jù)冗余、信道干擾或網(wǎng)絡(luò)擁塞等問(wèn)題,造成不必要的能耗.因此,在不影響網(wǎng)絡(luò)基本性能的前提下,可以利用調(diào)度技術(shù)來(lái)協(xié)調(diào)節(jié)點(diǎn)的狀態(tài),避免以上問(wèn)題的出現(xiàn).

由此可見(jiàn),節(jié)點(diǎn)調(diào)度技術(shù)的研發(fā)不僅很有必要,而且很有價(jià)值,是無(wú)線傳感器網(wǎng)絡(luò)設(shè)計(jì)的核心問(wèn)題之一,它決定了系統(tǒng)是否能夠滿足日益增長(zhǎng)的用戶需求.

2.3 節(jié)點(diǎn)調(diào)度模型設(shè)計(jì)

為了實(shí)現(xiàn)對(duì)傳感器節(jié)點(diǎn)的有效調(diào)度,設(shè)計(jì)了節(jié)點(diǎn)調(diào)度模型.該模型將整個(gè)調(diào)度過(guò)程分為若干個(gè)相等的周期,在每個(gè)周期開(kāi)始時(shí),采用一定的策略來(lái)決定節(jié)點(diǎn)處于工作狀態(tài)還是休眠狀態(tài).

如圖4所示,假設(shè)每個(gè)節(jié)點(diǎn)的工作過(guò)程分為N輪(N為正整數(shù)且N≥1),每輪周期為T(mén),在每一輪開(kāi)始的時(shí)候,按照特定的算法進(jìn)行節(jié)點(diǎn)工作/休眠調(diào)度,使部分節(jié)點(diǎn)工作,其他的節(jié)點(diǎn)休眠,整個(gè)網(wǎng)絡(luò)的監(jiān)測(cè)工作僅由處于工作狀態(tài)的節(jié)點(diǎn)來(lái)完成[4].

圖4 節(jié)點(diǎn)調(diào)度模型

3 經(jīng)典節(jié)點(diǎn)調(diào)度算法分析

3.1 基于網(wǎng)絡(luò)覆蓋的節(jié)點(diǎn)調(diào)度算法

根據(jù)監(jiān)測(cè)目標(biāo)的不同,網(wǎng)絡(luò)覆蓋問(wèn)題可分為三類,即點(diǎn)覆蓋、區(qū)域覆蓋和柵欄覆蓋.限于篇幅,筆者重點(diǎn)討論點(diǎn)覆蓋及區(qū)域覆蓋問(wèn)題.

3.1.1 基于點(diǎn)覆蓋的節(jié)點(diǎn)調(diào)度算法

點(diǎn)覆蓋是指在一些特定應(yīng)用中,需要對(duì)某些離散的目標(biāo)點(diǎn)進(jìn)行監(jiān)測(cè)而在其附近隨機(jī)部署大量傳感器節(jié)點(diǎn).為了延長(zhǎng)網(wǎng)絡(luò)生命期,將目標(biāo)點(diǎn)附近的節(jié)點(diǎn)分成若干互不相交的節(jié)點(diǎn)集,每個(gè)節(jié)點(diǎn)集都能夠?qū)崿F(xiàn)對(duì)若干個(gè)目標(biāo)點(diǎn)的有效覆蓋.通過(guò)周期性地調(diào)度節(jié)點(diǎn)集的工作狀態(tài),就能夠延長(zhǎng)網(wǎng)絡(luò)生命期.

文獻(xiàn)[7]提出了離散點(diǎn)覆蓋問(wèn)題:給定網(wǎng)絡(luò)中一些需要監(jiān)測(cè)的離散目標(biāo)點(diǎn),通過(guò)調(diào)度節(jié)點(diǎn)使得任意時(shí)刻隨機(jī)分布的節(jié)點(diǎn)能夠覆蓋到所有目標(biāo)點(diǎn),并且最大化網(wǎng)絡(luò)的持續(xù)工作時(shí)間.將所有感知節(jié)點(diǎn)劃分為互不相交的覆蓋集.顯然這樣的覆蓋集越多,網(wǎng)絡(luò)生命期就越長(zhǎng).這就是基于混合整數(shù)規(guī)劃的啟發(fā)式算法.

在此基礎(chǔ)上,Cardei等指出,設(shè)計(jì)互不相交的覆蓋集并不一定是最優(yōu)的,某些感知節(jié)點(diǎn)可以屬于多個(gè)覆蓋集.如圖5所示,感知節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的覆蓋關(guān)系為:S1={O1,O3},S2={O1,O2},S3={O1,O2,O3},S4={O2,O3}.假定感知節(jié)點(diǎn)的初始能量相同且每個(gè)節(jié)點(diǎn)最多可以持續(xù)工作1T(T=1個(gè)單位時(shí)間),根據(jù)以上討論,得出兩種情況:(1)一個(gè)可能最大數(shù)量互不相交的覆蓋集S={{S1,S2},{S3,S4}},即網(wǎng)絡(luò)的最大工作時(shí)間為2T;(2)當(dāng)節(jié)點(diǎn)可以屬于多個(gè)不同的覆蓋集時(shí),一個(gè)可能的覆蓋集為S={{S1,S2},{S2,S4},{S1,S4},{S3}},其中令集合{S1,S2}工作0.5T,令集合{S2,S4}工作0.5T,令集合{S1,S4}工作0.5T,令集合{S3}工作1T,則網(wǎng)絡(luò)的最大工作時(shí)間為2.5T.顯然,第二種情況可以更有效地延長(zhǎng)網(wǎng)絡(luò)生命期.

圖5 點(diǎn)覆蓋示意圖

3.1.2 基于區(qū)域覆蓋的節(jié)點(diǎn)調(diào)度算法

區(qū)域覆蓋可分為全局覆蓋和局部覆蓋.全局覆蓋要求工作節(jié)點(diǎn)的傳感范圍完全覆蓋整個(gè)區(qū)域(即區(qū)域中的任意一點(diǎn)能夠至少被一個(gè)工作節(jié)點(diǎn)覆蓋).局部覆蓋僅要求滿足一定的網(wǎng)絡(luò)覆蓋度即可.

比較典型的算法是 RTSS(Reference Timebased Scheduling Scheme),該算法能夠根據(jù)不同監(jiān)測(cè)區(qū)域的服務(wù)要求而動(dòng)態(tài)調(diào)整網(wǎng)絡(luò)覆蓋度[8],它將監(jiān)測(cè)區(qū)域分為若干網(wǎng)格,通過(guò)保證每個(gè)網(wǎng)格的覆蓋實(shí)現(xiàn)區(qū)域的局部/全局覆蓋.

算法分為兩個(gè)執(zhí)行階段:傳感階段和初始化階段.在傳感階段,將時(shí)間分為等長(zhǎng)的輪,各節(jié)點(diǎn)之間的時(shí)間輪是同步的.在初始化階段,節(jié)點(diǎn)首先確定自身的絕對(duì)或相對(duì)位置,并與鄰居節(jié)點(diǎn)實(shí)現(xiàn)時(shí)間同步;之后每個(gè)節(jié)點(diǎn)在[0,t](t為時(shí)間輪的長(zhǎng)度)之間產(chǎn)生一個(gè)隨機(jī)的時(shí)間基準(zhǔn),并廣播該時(shí)間基準(zhǔn)信息和節(jié)點(diǎn)位置信息.一段時(shí)間之后,每個(gè)節(jié)點(diǎn)都能得到鄰居節(jié)點(diǎn)的時(shí)間基準(zhǔn)和位置信息,然后根據(jù)各自感知區(qū)域內(nèi)每個(gè)網(wǎng)格的覆蓋情況來(lái)決定自身的調(diào)度.由于每個(gè)節(jié)點(diǎn)都對(duì)應(yīng)多個(gè)網(wǎng)格,所以會(huì)得到多個(gè)不同的調(diào)度結(jié)果,最后進(jìn)行節(jié)點(diǎn)調(diào)度融合,得到最終的調(diào)度結(jié)果.如果增加每個(gè)節(jié)點(diǎn)的調(diào)度長(zhǎng)度,則各節(jié)點(diǎn)之間的調(diào)度會(huì)相互重合,網(wǎng)格的覆蓋度也會(huì)得到提高,這樣就實(shí)現(xiàn)了對(duì)不同監(jiān)測(cè)區(qū)域的區(qū)分服務(wù).為了提高健壯性,該算法還可以支持對(duì)指定位置的多重覆蓋.

3.2 基于網(wǎng)絡(luò)連通的節(jié)點(diǎn)調(diào)度算法

對(duì)于無(wú)線傳感器網(wǎng)絡(luò)而言,要真正完成監(jiān)測(cè)任務(wù),除了要保證網(wǎng)絡(luò)對(duì)目標(biāo)區(qū)域的有效覆蓋度,還必須保證網(wǎng)絡(luò)的連通.只有這樣才能使節(jié)點(diǎn)將采集的數(shù)據(jù)傳送到匯聚節(jié)點(diǎn),并最終傳送給觀察者.在某些應(yīng)用中,一定程度的有效覆蓋面積的丟失是可以容忍的,但是網(wǎng)絡(luò)如果不連通,節(jié)點(diǎn)采集的數(shù)據(jù)將毫無(wú)價(jià)值.因此,許多應(yīng)用中要以保證網(wǎng)絡(luò)連通為基礎(chǔ).

具有代表性的是GAF(Geographic Adaptive Fidelity)算法.它是一種依據(jù)節(jié)點(diǎn)的地理位置進(jìn)行分簇,并對(duì)各簇內(nèi)的節(jié)點(diǎn)選擇性地進(jìn)行休眠的路由算法[9].GAF算法中,每個(gè)節(jié)點(diǎn)需要知道自身的位置信息并利用該信息將整個(gè)區(qū)域劃分為若干個(gè)大小相同的正方形網(wǎng)格,網(wǎng)格的劃分恰好使得相鄰網(wǎng)格內(nèi)的任意對(duì)節(jié)點(diǎn)均能一跳可達(dá)(直接通信),從而在任意時(shí)刻每個(gè)網(wǎng)格中只有一個(gè)節(jié)點(diǎn)參與數(shù)據(jù)的傳輸而網(wǎng)格內(nèi)其它節(jié)點(diǎn)進(jìn)入休眠以節(jié)省能量.如圖6所示,當(dāng)每個(gè)網(wǎng)格的大小為R2時(shí),若要保證網(wǎng)絡(luò)的連通則每個(gè)節(jié)點(diǎn)的通信半徑至少為R .為平衡節(jié)點(diǎn)間的能耗,同一網(wǎng)格內(nèi)的節(jié)點(diǎn)需要輪流進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā).GAF算法所提出的節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換機(jī)制和按虛擬單元格進(jìn)行分簇的思想非常有價(jià)值.

圖6 GAF算法示意圖

3.3 基于網(wǎng)絡(luò)覆蓋和連通的節(jié)點(diǎn)調(diào)度算法

網(wǎng)絡(luò)覆蓋性與連通性是傳感器網(wǎng)絡(luò)的兩個(gè)必備條件,節(jié)點(diǎn)必須同時(shí)滿足連通和覆蓋這兩個(gè)條件,無(wú)線傳感器網(wǎng)絡(luò)才有實(shí)際意義.因此,基于網(wǎng)絡(luò)覆蓋和連通的節(jié)點(diǎn)調(diào)度算法也是眾多研究者關(guān)注的熱點(diǎn).

OGDC(Optimal Geographical Density Control)算法是一種分布式、局部化的最優(yōu)地理位置密度控制算法[10].在該算法中,任意時(shí)刻節(jié)點(diǎn)只能是以下三種狀態(tài)之一:UNDECIDED、ON或OFF狀態(tài).網(wǎng)絡(luò)生存時(shí)間被劃分為若干個(gè)時(shí)間段,在每個(gè)時(shí)段的開(kāi)始階段,網(wǎng)絡(luò)中一個(gè)或多個(gè)節(jié)點(diǎn)首先作為工作節(jié)點(diǎn),其它節(jié)點(diǎn)的狀態(tài)置為 UNDECIDED.經(jīng)過(guò)一段隨機(jī)退避時(shí)間后,初始工作節(jié)點(diǎn)開(kāi)始向外廣播POWERON消息,該P(yáng)OWERON消息中包含了發(fā)送節(jié)點(diǎn)的位置信息以及所期望的下一個(gè)工作節(jié)點(diǎn)理論上所處的方向信息,該方向由POWERON消息的發(fā)送節(jié)點(diǎn)隨機(jī)選擇.通過(guò)隨機(jī)選擇每個(gè)時(shí)間段開(kāi)始階段的初始工作節(jié)點(diǎn),可以確保網(wǎng)絡(luò)中各節(jié)點(diǎn)的均勻能量消耗.同時(shí)隨機(jī)退避機(jī)制有利于避免信道沖突.通過(guò)消息的交換,每個(gè)節(jié)點(diǎn)都會(huì)得到鄰居節(jié)點(diǎn)位置的列表信息.

OGDC算法規(guī)定了節(jié)點(diǎn)收到POWERON消息后所應(yīng)該采取的動(dòng)作.如果發(fā)現(xiàn)鄰居節(jié)點(diǎn)能夠覆蓋自身的覆蓋區(qū)域,則該節(jié)點(diǎn)成為休眠節(jié)點(diǎn),狀態(tài)置為OFF.否則,如果周?chē)延袃蓚€(gè)工作節(jié)點(diǎn)且自身與這兩個(gè)工作節(jié)點(diǎn)的距離最接近于最佳距離(即與這兩個(gè)節(jié)點(diǎn)的距離均為3Rs)的話,該節(jié)點(diǎn)也將成為工作節(jié)點(diǎn),狀態(tài)置為ON.據(jù)此,每個(gè)節(jié)點(diǎn)設(shè)定自己的狀態(tài)為ON或者OFF狀態(tài),然后節(jié)點(diǎn)在該時(shí)間段內(nèi)狀態(tài)保持不變,直到下一個(gè)時(shí)間段開(kāi)始.節(jié)點(diǎn)重復(fù)上述過(guò)程,重新決定狀態(tài).實(shí)踐表明,OGDC算法在監(jiān)測(cè)區(qū)域的覆蓋比率、工作節(jié)點(diǎn)的數(shù)量以及網(wǎng)絡(luò)生存時(shí)間等方面性能優(yōu)越.

由本節(jié)的討論可以看出,研究者從不同的角度出發(fā)提出了眾多的節(jié)點(diǎn)調(diào)度算法,本文為了突出討論的代表性,只分析了部分經(jīng)典的算法.更詳細(xì)的關(guān)于節(jié)點(diǎn)調(diào)度算法的內(nèi)容請(qǐng)參考文獻(xiàn)[6].

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

無(wú)線傳感器網(wǎng)絡(luò)將邏輯上的信息世界與真實(shí)世界融合在一起,極大地提高了人們認(rèn)識(shí)和改造世界的能力[11].它擴(kuò)展了計(jì)算機(jī)網(wǎng)絡(luò)的功能,廣泛深入地影響著人類社會(huì)各領(lǐng)域的發(fā)展,有著重要的應(yīng)用前景和空間.因此,研究支撐其運(yùn)行的節(jié)能節(jié)點(diǎn)調(diào)度技術(shù)顯得格外重要.學(xué)者們?cè)谔岢龈鞣N軟節(jié)能技術(shù)的同時(shí),硬節(jié)能技術(shù)也要同步發(fā)展,比如電池供應(yīng)技術(shù)、能源的利用和再生、節(jié)能傳感器硬件體系結(jié)構(gòu)設(shè)計(jì)以及智能技術(shù)等方面都需要更深入研究.

雖然無(wú)線傳感器網(wǎng)絡(luò)領(lǐng)域已取得豐碩的成果,但仍存在若干關(guān)鍵問(wèn)題需要進(jìn)一步解決:①感知精確度問(wèn)題;②網(wǎng)絡(luò)動(dòng)態(tài)自適應(yīng)能力問(wèn)題;③服務(wù)質(zhì)量支持問(wèn)題等[12].我們相信,通過(guò)科研工作者們的不斷努力,尚存的難題將得到解決,無(wú)線傳感器網(wǎng)絡(luò)將對(duì)社會(huì)的發(fā)展做出更大貢獻(xiàn).

[1]唐 偉,郭 偉.無(wú)線傳感器網(wǎng)絡(luò)中的最大生命期基因路由算法[J].軟件學(xué)報(bào),2010,21(7):1646-1656.

[2]王 娟.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度算法的研究[D].西安:西安電子科技大學(xué),2009,1.

[3]崔 莉,劉 強(qiáng),李 棟.物聯(lián)網(wǎng)系統(tǒng)及核心設(shè)備[J].中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊,2010,6(4):18-22.

[4]趙 霽.基于人工免疫算法的無(wú)線傳感器網(wǎng)絡(luò)調(diào)度[D].成都:電子科技大學(xué),2009,5.

[5]劉云浩.綠野千傳.突破自組織傳感網(wǎng)大規(guī)模應(yīng)用壁壘[J].中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊,2010,6(4):35-37.

[6]胡湘華,楊學(xué)軍.傳感網(wǎng)節(jié)點(diǎn)調(diào)度方法綜述[J].計(jì)算機(jī)工程與科學(xué),2008,30(3):93-96、129.

[7]Cardei M,Du D Z.Improving Wireless Sensor Network Lifetime through Power Aware Organization[J].Wireless Networks,2005,11(3):333-340.

[8]T yan,T He,J Stankovic.Differentiated Surveillance for Sensor Networks[C].In:Proc of ACM SENSYS＇03,New York:ACM Press,2003:51-62.

[9]趙學(xué)鵬,鄒傳云.無(wú)線傳感器網(wǎng)絡(luò)GAF算法的性能分析與仿真[J].計(jì)算機(jī)仿真,2008,25,(11):154-156.

[10]Xing Guo-liang,Wang Xiao-rui,Zhang Yuan-fang,et al.Integrated Coverage and Connectivity Configuration for Energy Conservation in Sensor Networks[J].ACM Trans on Sensor Networks,2005,1(1):36-72.

[11]任 彥,張思東,張宏科.無(wú)線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法[J].軟件學(xué)報(bào),2006,17(3):422-433.

[12]康 波,柯 欣,孫利民,任 雍.無(wú)線傳感器網(wǎng)絡(luò)中的調(diào)度算法研究[J].計(jì)算機(jī)科學(xué),2008,35(2):47-51.

Research on Node Scheduling Technology for Wireless Sensor Networks

QIU Shu-wei
(Shantou Polytechnic,Shantou 515078,China)

Node hardware architecture and network architecture of wireless sensor networks are discussed in this paper.The necessity and value of node scheduling technology for wireless sensor networks are revealed.Several node scheduling algorithm of the most representative from the network coverage and connectivity point of view are analyzed.

wireless sensor networks;sensor nodes;node scheduling;network coverage;connectivity

TP212

A

1671-119X(2011)01-0059-05

2010-10-15

邱樹(shù)偉(1979-),男,碩士,講師,研究方向:網(wǎng)絡(luò)與分布計(jì)算、人工智能.

book=97,ebook=97