姜　波　張榮福

摘 要：路由協(xié)議是無線傳感器網(wǎng)絡(luò)的重要組成部分,節(jié)能是無線傳感器網(wǎng)絡(luò)路由協(xié)議設(shè)計所要解決的首要問題。重點深入分析了低功耗路由協(xié)議LEACH和PEGASIS,總結(jié)了它們各自的優(yōu)缺點,同時簡單介紹了其他幾種典型的路由協(xié)議,并對所述路由協(xié)議進行了綜合對比,最后,總結(jié)了路由協(xié)議能量優(yōu)化的方法。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；路由協(xié)議；節(jié)能；LEACH協(xié)議；PEGASIS協(xié)議

中圖分類號：TN915 文獻(xiàn)標(biāo)識碼：A

文章編號：1004-373X(2009)01-026-04

Research on Energy-saving Routing Protocol for Wireless Sensor Network

JIANG Bo,ZHANG Rongfu

(University of Shanghai for Science and Technology,Shanghai,200093,China)

Abstract：Routing protocol is a very important part of wireless sensor network,saving energy is the first problem in routing protocol design for wireless sensor network.This paper focuses on in-depth analysis of the low-power routing protocols LEACH and PEGASIS,then their respective advantages and disadvantages are summarized,and several other typical routing protocols are introduced briefly,and routing protocol described in the text are compared together.Finally,the routing protocol energy optimization approach is indicated.

Keywords：wireless sensor network;routing protocol;energy-saving;LEACH protocol;PEGASIS protocol

0 引 言

傳感器技術(shù)、微機電系統(tǒng)、現(xiàn)代網(wǎng)絡(luò)和無線通信等技術(shù)的進步,推動了具有現(xiàn)代意義的無線傳感器網(wǎng)絡(luò)的產(chǎn)生和發(fā)展。無線傳感器網(wǎng)絡(luò)擴展了人們的信息獲取能力,將客觀世界的物理信息同傳輸網(wǎng)絡(luò)連接在一起,在下一代互聯(lián)網(wǎng)中將為人們提供最直接、最有效、最真實的信息。無線傳感器網(wǎng)絡(luò)具有十分廣闊的應(yīng)用前景,能應(yīng)用于軍事國防、工農(nóng)業(yè)控制、城市管理、生物醫(yī)療、環(huán)境監(jiān)測、搶險救災(zāi)、防恐反恐、危險區(qū)域遠(yuǎn)程控制等諸多領(lǐng)域。

無線傳感器網(wǎng)絡(luò)設(shè)計的基本原則就是要以節(jié)能為前提。傳統(tǒng)無線通信網(wǎng)絡(luò)的首要設(shè)計目標(biāo)是提高服務(wù)質(zhì)量和高效帶寬利用,其次再考慮節(jié)約能源；而傳感器的首要設(shè)計目標(biāo)是能源的高效利用,這是傳感器網(wǎng)絡(luò)和傳統(tǒng)網(wǎng)絡(luò)的最重要的區(qū)別之一,能量問題是無線傳感器網(wǎng)絡(luò)的核心問題。傳感器節(jié)點由電池供電,而目前的技術(shù)水平下電池容量難以有大幅度提高,而且在許多應(yīng)用中,更換電池是不現(xiàn)實的(如軍事應(yīng)用),因此這就要求WSN路由協(xié)議必須以節(jié)約能源為主要目標(biāo),最大限度地延長網(wǎng)絡(luò)生存時間。

1 低功耗路由協(xié)議

1.1 LEACH協(xié)議

LEACH(Low-Energy Adaptive Clustering Hierarchy)是MIT的Chandrakasan等人為無線傳感器網(wǎng)絡(luò)設(shè)計的低功耗自適應(yīng)分層路由算法［1］。它的基本思想是以循環(huán)的方式隨機選擇簇頭節(jié)點,將整個網(wǎng)絡(luò)的能量負(fù)載平均分配到每個傳感器節(jié)點中,從而達(dá)到降低網(wǎng)絡(luò)能源消耗,提高網(wǎng)絡(luò)整體生存時間的目的。LEACH在運行過程中不斷地循環(huán)執(zhí)行簇的重構(gòu)過程。每個簇重構(gòu)過程可以用“輪”的概念來描述。每個輪可以分成兩個階段：初始化和穩(wěn)定工作兩個階段。為了避免額外的處理開銷,穩(wěn)定階段一般持續(xù)較長時間。

初始化階段即簇的形成階段。在每一輪的初始化階段,每個傳感器節(jié)點都要決定自己是否充當(dāng)簇頭節(jié)點。這個決定主要取決于網(wǎng)絡(luò)中所需要的簇頭節(jié)點數(shù)(在初始化的時候設(shè)置)和迄今為止該節(jié)點已成為簇頭節(jié)點的次數(shù)。簇頭節(jié)點必須從那些沒有當(dāng)過簇頭節(jié)點的節(jié)點中選擇,直到網(wǎng)絡(luò)中的所有節(jié)點都當(dāng)過簇頭節(jié)點,然后再進行重新選舉,所有節(jié)點獲得再次成為簇頭的機會。簇頭節(jié)點的選擇辦法是：每個傳感器節(jié)點隨機選擇0～1之間的一個值,如果選定的值小于某一個閾值T(n),那么這個節(jié)點成為簇頭節(jié)點。T(n)值的計算方法如下：

T(n)=p1-prmod1p, n∈G

0,其他(1)

其中,p是網(wǎng)絡(luò)中簇頭節(jié)點所占節(jié)點數(shù)目的百分比,r為當(dāng)前的輪數(shù),G是一個集合,集合中的節(jié)點是前1/p輪中沒有充當(dāng)過簇頭節(jié)點的節(jié)點。使用這個門限,每個節(jié)點會在1/p輪操作內(nèi)充當(dāng)一次簇頭節(jié)點,符號mod是求模運算符號。

在第0輪的時候(r=0),每個節(jié)點充當(dāng)簇頭節(jié)點的概率為p,在第0輪充當(dāng)簇頭節(jié)點的節(jié)點在后面1/p輪中不能再次充當(dāng)簇頭節(jié)點。這樣,剩下的節(jié)點的數(shù)目變少了,所以能夠充當(dāng)簇頭節(jié)點的概率必須增加才能保證每一輪中的簇的個數(shù)保持均衡。在經(jīng)過1/p-1輪以后,T=1,此時對于任何一個在過去的1/p中還沒有做過簇頭節(jié)點的節(jié)點,都可以成為簇頭節(jié)點,因為所有節(jié)點的標(biāo)志值都在0~1之間。經(jīng)過1/p輪之后,所有節(jié)點又可以重新充當(dāng)簇頭節(jié)點了。

一旦簇頭節(jié)點被選定,它們就使用相同的能量向網(wǎng)絡(luò)中的其他節(jié)點廣播一個廣告包。在這個過程中,其他非簇頭節(jié)點的接收機一直處于工作狀態(tài),以便接收來自不同簇頭的廣告包,它們根據(jù)最小通信能量原則,選取信號最強的廣告包的發(fā)送源節(jié)點作為自己的簇頭節(jié)點,并發(fā)送消息給其簇頭節(jié)點,告訴簇頭節(jié)點自己已經(jīng)加入該簇。

當(dāng)簇頭節(jié)點收到了來自成員節(jié)點的“報道”消息后,根據(jù)成員節(jié)點的數(shù)目,產(chǎn)生一個TDMA的時隙表,告訴成員在什么時刻可以發(fā)送數(shù)據(jù)。這個表會通過廣播到達(dá)成員節(jié)點,由于形成了簇的結(jié)構(gòu),成員節(jié)點只與自己的簇頭節(jié)點通信,如果收到來自其他節(jié)點的消息,會自動屏蔽掉。因此不用擔(dān)心簇頭節(jié)點的時隙表被其他簇的成員錯誤接收。當(dāng)網(wǎng)絡(luò)中的簇已經(jīng)形成,而且TDMA時隙表也確定下來,就開始了數(shù)據(jù)傳送。成員節(jié)點只能在TDMA時隙表為其分配的時隙內(nèi)與簇頭節(jié)點進行通信。假設(shè)傳感器節(jié)點總是有數(shù)據(jù)要發(fā)送,在屬于自己的時隙里,成員節(jié)點會把數(shù)據(jù)發(fā)送給自己的簇頭節(jié)點。在發(fā)送階段,在自己的時隙沒有到來的時候成員節(jié)點可以關(guān)閉自己的收發(fā)機以節(jié)省能量。而簇頭節(jié)點必須一直使自己的接收機處于開啟狀態(tài),用于接收來自不同成員節(jié)點的數(shù)據(jù)。當(dāng)一輪的數(shù)據(jù)傳輸完畢后,簇頭節(jié)點會進行必要的數(shù)據(jù)融合處理,將多個數(shù)據(jù)融合成一個數(shù)據(jù),然后發(fā)送給基站。持續(xù)一段時間以后,網(wǎng)絡(luò)開始進入下一輪的工作周期。

LEACH協(xié)議運用了數(shù)據(jù)壓縮技術(shù)和分層動態(tài)路由技術(shù),通過本地的聯(lián)合工作來提高網(wǎng)絡(luò)的可擴展性和魯棒性,通過數(shù)據(jù)融合來減少發(fā)送的數(shù)據(jù)量,通過隨機選擇簇頭節(jié)點來達(dá)到網(wǎng)絡(luò)內(nèi)部負(fù)載均衡的目的,進而大大節(jié)約了能量。

盡管LEACH協(xié)議具備以上優(yōu)點,但也存在一些不足之處。

(1) 由于LEACH算法假定所有節(jié)點能夠與匯聚節(jié)點直接通信,并且每個節(jié)點都具備支持不同MAC協(xié)議的計算能力,因此該協(xié)議不適合在大規(guī)模的無線傳感器網(wǎng)絡(luò)中應(yīng)用。

(2) LEACH算法是讓網(wǎng)絡(luò)中自組織的形成簇,由于簇頭節(jié)點是隨機產(chǎn)生的,這樣無法保證簇頭節(jié)點的合理分布。因此,很有可能出現(xiàn)被選擇的簇頭節(jié)點集中在網(wǎng)絡(luò)中某一區(qū)域的現(xiàn)象,這樣就會使得一些節(jié)點的周圍沒有任何簇。

(3) LEACH算法忽略了被選簇頭在網(wǎng)絡(luò)內(nèi)的分布狀態(tài)和節(jié)點間不同的通信距離而導(dǎo)致的節(jié)點能量損耗的不平衡。

1.2 PEGASIS協(xié)議

PEGASIS(Power-Efficient Gathering in Sensor Information Systems)協(xié)議是在LEACH基礎(chǔ)上改進設(shè)計的［2］。PEGASIS算法的主要思想是在傳感器網(wǎng)絡(luò)中形成一條覆蓋所有節(jié)點的“鏈”,節(jié)點從它的一邊的鄰居節(jié)點接收數(shù)據(jù),然后將接收到的數(shù)據(jù)和自身的數(shù)據(jù)進行融合處理之后形成一個與原來數(shù)據(jù)包同樣大小的新數(shù)據(jù)包,再將得到的新數(shù)據(jù)包發(fā)送給它的另外一邊的鄰居節(jié)點,以此類推,數(shù)據(jù)最終被傳到一個“領(lǐng)導(dǎo)”節(jié)點,由這個“領(lǐng)導(dǎo)”節(jié)點把數(shù)據(jù)發(fā)送給基站。節(jié)點充當(dāng)“領(lǐng)導(dǎo)”節(jié)點與基站通信是輪流的,當(dāng)網(wǎng)絡(luò)中的所有節(jié)點都充當(dāng)過“領(lǐng)導(dǎo)”節(jié)點后,節(jié)點再進行新一回合的輪流通信。

在PEGASIS算法中,“鏈”的形成過程是整個通信的關(guān)鍵?！版湣钡男纬刹捎玫姆椒ㄊ牵汗?jié)點發(fā)送能量遞減的測試信號通過監(jiān)測應(yīng)答來確定離自己最近的相鄰節(jié)點。通過這種方式,網(wǎng)絡(luò)中的所有節(jié)點能夠了解彼此的位置關(guān)系,找到自己的鄰居節(jié)點,每一輪通信中節(jié)點只需要與自己的鄰居節(jié)點進行通信。為確保每個節(jié)點都有其相鄰節(jié)點,從離基站最遠(yuǎn)的節(jié)點開始構(gòu)建,鏈中鄰居節(jié)點的距離會逐漸增大,因為已經(jīng)在鏈中的節(jié)點不能被再次訪問。依次下去,最終形成一條包含網(wǎng)絡(luò)中所有節(jié)點的鏈。

當(dāng)節(jié)點鏈形成并且選舉出領(lǐng)導(dǎo)節(jié)點后,就開始了數(shù)據(jù)傳輸過程。PEGASIS中的數(shù)據(jù)傳輸使用Token(令牌)機制,如圖1所示。Token很小,故能耗較少。在一輪通信中,領(lǐng)導(dǎo)節(jié)點用Token控制數(shù)據(jù)從鏈尾開始傳輸。圖中,C2為領(lǐng)導(dǎo)節(jié)點,將Token沿著鏈傳給C0,CO傳數(shù)據(jù)給C1,C1將C0數(shù)據(jù)和自身數(shù)據(jù)進行融合后形成一個相同長度的數(shù)據(jù)包,再傳給C2。然后,C2將Token傳給C4,C2以相同的方式接收來自C3,C4的數(shù)據(jù)。這些數(shù)據(jù)在C2處進行融合后,發(fā)給基站。

圖1 鏈?zhǔn)浇Y(jié)構(gòu)示意圖

PEGASIS是在LEACH基礎(chǔ)上建立的路由協(xié)議,PEGASIS比LEACH節(jié)省能量主要體現(xiàn)在以下幾個方面：

(1) 在本地數(shù)據(jù)聚合階段,PEGASIS算法中每個節(jié)點只與離自己最近的鄰居節(jié)點進行通信,而不是像LEACH算法一樣需要與簇頭節(jié)點進行通信,PEGASIS算法大大減小了每輪通信中每個節(jié)點的通信距離,從而降低了每個節(jié)點在每一輪通信中所消耗的能量。

(2) LEACH算法中,一個簇頭要接收多個簇成員節(jié)點發(fā)送過來的數(shù)據(jù),而PEGASIS算法中,一個領(lǐng)導(dǎo)節(jié)點最多只需要接收2個節(jié)點發(fā)送過來的數(shù)據(jù)包。

(3) 在每一輪通信中,PEGASIS算法只有1個領(lǐng)導(dǎo)節(jié)點與基站通信,而LEACH中則有多個簇頭節(jié)點與基站通信。PEGASIS也存在一些不足之處：節(jié)點維護位置信息(相當(dāng)于傳統(tǒng)網(wǎng)絡(luò)的拓?fù)湫畔?需要額外的資源,在網(wǎng)絡(luò)全局信息比較難以獲得的情況下就不合適了,而且領(lǐng)導(dǎo)節(jié)點的惟一性使得其成為整個通信過程的瓶頸。

2 其他典型路由協(xié)議

2.1 SPIN協(xié)議

SPIN(Sensor Protocols for Information via Negotiation)協(xié)議［3］的設(shè)計思想是：每個節(jié)點在發(fā)送數(shù)據(jù)前通過協(xié)商來確定其他節(jié)點是否需要該數(shù)據(jù)；同時,節(jié)點通過“元數(shù)據(jù)”確定接收數(shù)據(jù)中是否有重復(fù)信息存在。節(jié)點通過3種消息進行通信：ADV(數(shù)據(jù)描述),REQ(數(shù)據(jù)請求)和DATA(數(shù)據(jù))。源節(jié)點在傳送DATA信息之前,首先向相鄰節(jié)點廣播包含DATA數(shù)據(jù)描述機制的ADV信息,需要該DATA信息的鄰節(jié)點向信息源發(fā)送REQ請求信息,源節(jié)點在收到REQ信息后,有選擇地將DATA信息發(fā)送給相應(yīng)的鄰節(jié)點。收到DATA后,該鄰節(jié)點可以作為信息源,按照前述過程將DATA信息繼續(xù)傳播到網(wǎng)絡(luò)中的其他節(jié)點。該協(xié)議的優(yōu)點是：ADV消息減輕了內(nèi)爆問題；通過數(shù)據(jù)命名解決了交疊問題；節(jié)點根據(jù)自身資源和應(yīng)用信息決定是否進行ADV通告,避免了資源利用盲目的問題,進而有效地節(jié)約了能量。其缺陷是：當(dāng)產(chǎn)生或收到數(shù)據(jù)的節(jié)點的所有鄰節(jié)點均不需要該數(shù)據(jù)時,將導(dǎo)致數(shù)據(jù)不能繼續(xù)轉(zhuǎn)發(fā),會使較遠(yuǎn)節(jié)點無法得到數(shù)據(jù)。

2.2 DD協(xié)議

DD(Directed Diffusion)是Estrin等人專為無線傳感器網(wǎng)絡(luò)設(shè)計的路由協(xié)議［4］。匯聚節(jié)點將查詢?nèi)蝿?wù)封裝成興趣消息(interest)的形式,采用洪泛方式傳播興趣消息到其他節(jié)點,興趣消息用來表達(dá)用戶對監(jiān)測區(qū)域內(nèi)感興趣的信息。在興趣消息的傳播過程中,協(xié)議逐跳地在每個節(jié)點上建立反向的從數(shù)據(jù)源到匯聚節(jié)點的數(shù)據(jù)傳輸梯度。節(jié)點將采集到的數(shù)據(jù)沿著梯度方向傳送到匯聚節(jié)點。定向擴散的最大特點是引入網(wǎng)絡(luò)梯度的概念,其優(yōu)勢在于擴散過程能夠?qū)凑战?jīng)驗選取的較優(yōu)路徑緩存以實現(xiàn)節(jié)能,并且提高節(jié)點間的有效性、魯棒性和協(xié)作的可擴展性。

2.3 GEAR協(xié)議

GEAR(Geographical and Energy Aware Routing)是一種典型的地理位置路由協(xié)議［5］。該算法的提出基于以下思想：在傳感器網(wǎng)絡(luò)中向適當(dāng)區(qū)域發(fā)送查詢時,此查詢數(shù)據(jù)中包含了位置屬性信息,因此,可以利用這一信息將在整個網(wǎng)絡(luò)中擴散的信息傳送到適當(dāng)?shù)奈恢脜^(qū)域中。該算法引入了預(yù)估費用(estimated cost)和學(xué)習(xí)費用(learning cost),通過比較兩者值的大小來選取更接近匯聚節(jié)點的傳感器節(jié)點作為下一跳。GEAR利用能量和地理信息作為啟發(fā)式選擇路徑向目標(biāo)區(qū)域傳送數(shù)據(jù),它是在DD的基礎(chǔ)上提出的,但由于GEAR只考慮向某個特定區(qū)域發(fā)送興趣,而不是像DD那樣發(fā)布到整個網(wǎng)絡(luò),因此,GEAR相對DD更加節(jié)省能量。

2.4 SAR協(xié)議

SAR(Sequential Assignment Routing)協(xié)議是一個典型的具有QoS意識的路由協(xié)議［6］。該協(xié)議通過構(gòu)建以匯聚節(jié)點的單跳鄰節(jié)點為根節(jié)點的多播樹來實現(xiàn)傳感器節(jié)點到匯聚節(jié)點的多跳路徑,即匯聚節(jié)點的所有下一跳鄰節(jié)點都以自己為根創(chuàng)建生成樹,在創(chuàng)建生成樹過程中考慮節(jié)點的時延,丟包率等QoS參數(shù)以及最大數(shù)據(jù)傳輸能力,這樣就反向建立了到匯聚節(jié)點的具有不同QoS參數(shù)的多條路徑。SAR的一個突出優(yōu)點是綜合考慮了能效和QoS,仿真結(jié)果表明,與只考慮路徑能量消耗的最小能量度量協(xié)議相比,SAR的能量消耗較少。

3 路由協(xié)議對比分析

節(jié)能是無線傳感器網(wǎng)絡(luò)最重要的特征,因而高效地利用能量是無限傳感器網(wǎng)絡(luò)路由協(xié)議設(shè)計的根本出發(fā)點。LEACH和PEGASIS具備很好的節(jié)能策略,SPIN,DD,GEAR,SAR 也分別具備相應(yīng)的節(jié)能策略。但是,無線傳感器網(wǎng)絡(luò)與應(yīng)用高度相關(guān),所以路由協(xié)議在節(jié)能的前提下還要滿足以下方面的性能要求：以數(shù)據(jù)為中心、支持?jǐn)?shù)據(jù)融合、基于節(jié)點定位、具有可擴展性、魯棒性、提供QoS支持等。依據(jù)上述性能指標(biāo),對描述的路由協(xié)議特點進行對比的結(jié)果如表1所示。

4 結(jié) 語

深入分析了低功耗路由協(xié)議LEACH及PEGASIS,希望能對以后LEACH及PEGASIS協(xié)議的改進起到一定的推動作用。在綜合所述的路由協(xié)議基礎(chǔ)之上,總結(jié)出以下幾種無線傳感器網(wǎng)絡(luò)路由協(xié)議能量優(yōu)化方法：

(1) 數(shù)據(jù)融合。節(jié)點通過對數(shù)據(jù)進行融合,降低網(wǎng)絡(luò)開銷,節(jié)省能量。

(2) 數(shù)據(jù)命名。數(shù)據(jù)命名機制能高度搜索用戶所需數(shù)據(jù),避免數(shù)據(jù)在網(wǎng)絡(luò)中的重復(fù)發(fā)送,降低了網(wǎng)絡(luò)開銷。

(3)局部協(xié)商技術(shù)。協(xié)商技術(shù)能夠有效地避免由于

節(jié)點間重復(fù)地收發(fā)大量冗余信息所造成的能量浪費。

(4) 隨機路由選擇。路由協(xié)議支持到目的地的低開銷多種路由會使網(wǎng)絡(luò)負(fù)載趨于平衡,延長網(wǎng)絡(luò)壽命。除了能量高效,無線傳感器網(wǎng)絡(luò)路由協(xié)議還存在一些挑戰(zhàn),如QoS和帶寬的高效利用,在能量有效性的前提下提供對節(jié)點移動的支持,網(wǎng)絡(luò)安全問題等。這些問題將在以后的工作中繼續(xù)深入研究。

參考文獻(xiàn)

［1］Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-efficient Communication Protocols for Wireless Sensor Networks［A］.IEEE Proceedings of the Hawaii International Conference System Sciences′00.2000:3 005-3 014.

［2］Lindsey S,RaghavendraC.PEGASIS:Power-Efficient Gathering in Sensor Information Systems［A］.Proceeding of the IEEE Aerospace Conference′02.2002:1 125-1 130.

［3］Kulik J,Heinzelman W,Balakrishnan H.Negotiation-based Protocols for Disseminating Information in Wireless Sensor Networks［J］.Wireless Networks,2002,8(3):169-185.

［4］Intanagonwiwat C,Govindan R,Estrin D.Directed Diffusion for Wireless Sensor Networking［J］.Transactions on Networking,2003,11(1):2-16.

［5］Yu Y,Govindan R,Estrin D.Geographical and Energy Aware Routing:A Recursive Data Dissemination Protocol for Wireless Sensor Networks［R］.UCLA Computer Science Department Technical Report UCLA/CSD-TR-01-0023,2001.

［6］Sohrabi K,Gao J,Ailawadhi V,et al.Protocols for Self- organization of a Wireless Sensor Network［J］.IEEE Personal Communications,2000,7(5):16-27.

作者簡介

姜 波 男,1983年出生,安徽潁上人,碩士研究生。研究方向為短距離無線通信與計算機網(wǎng)絡(luò)。

張榮福 男,1971年出生,安徽廬江人,副教授,博士。研究方向為信息處理技術(shù)。