基于節能的無線傳感器網絡路由協議研究

姜　波　張榮福

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

關鍵詞：無線傳感器網絡；路由協議；節能；LEACH協議；PEGASIS協議

中圖分類號：TN915 文獻標識碼：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 引 言

傳感器技術、微機電系統、現代網絡和無線通信等技術的進步,推動了具有現代意義的無線傳感器網絡的產生和發展。無線傳感器網絡擴展了人們的信息獲取能力,將客觀世界的物理信息同傳輸網絡連接在一起,在下一代互聯網中將為人們提供最直接、最有效、最真實的信息。無線傳感器網絡具有十分廣闊的應用前景,能應用于軍事國防、工農業控制、城市管理、生物醫療、環境監測、搶險救災、防恐反恐、危險區域遠程控制等諸多領域。

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

1 低功耗路由協議

1.1 LEACH協議

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

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

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

0,其他(1)

其中,p是網絡中簇頭節點所占節點數目的百分比,r為當前的輪數,G是一個集合,集合中的節點是前1/p輪中沒有充當過簇頭節點的節點。使用這個門限,每個節點會在1/p輪操作內充當一次簇頭節點,符號mod是求模運算符號。

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

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

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

LEACH協議運用了數據壓縮技術和分層動態路由技術,通過本地的聯合工作來提高網絡的可擴展性和魯棒性,通過數據融合來減少發送的數據量,通過隨機選擇簇頭節點來達到網絡內部負載均衡的目的,進而大大節約了能量。

盡管LEACH協議具備以上優點,但也存在一些不足之處。

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

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

(3) LEACH算法忽略了被選簇頭在網絡內的分布狀態和節點間不同的通信距離而導致的節點能量損耗的不平衡。

1.2 PEGASIS協議

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

在PEGASIS算法中,“鏈”的形成過程是整個通信的關鍵。“鏈”的形成采用的方法是：節點發送能量遞減的測試信號通過監測應答來確定離自己最近的相鄰節點。通過這種方式,網絡中的所有節點能夠了解彼此的位置關系,找到自己的鄰居節點,每一輪通信中節點只需要與自己的鄰居節點進行通信。為確保每個節點都有其相鄰節點,從離基站最遠的節點開始構建,鏈中鄰居節點的距離會逐漸增大,因為已經在鏈中的節點不能被再次訪問。依次下去,最終形成一條包含網絡中所有節點的鏈。

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

圖1 鏈式結構示意圖

PEGASIS是在LEACH基礎上建立的路由協議,PEGASIS比LEACH節省能量主要體現在以下幾個方面：

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

(2) LEACH算法中,一個簇頭要接收多個簇成員節點發送過來的數據,而PEGASIS算法中,一個領導節點最多只需要接收2個節點發送過來的數據包。

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

2 其他典型路由協議

2.1 SPIN協議

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

2.2 DD協議

DD(Directed Diffusion)是Estrin等人專為無線傳感器網絡設計的路由協議［4］。匯聚節點將查詢任務封裝成興趣消息(interest)的形式,采用洪泛方式傳播興趣消息到其他節點,興趣消息用來表達用戶對監測區域內感興趣的信息。在興趣消息的傳播過程中,協議逐跳地在每個節點上建立反向的從數據源到匯聚節點的數據傳輸梯度。節點將采集到的數據沿著梯度方向傳送到匯聚節點。定向擴散的最大特點是引入網絡梯度的概念,其優勢在于擴散過程能夠將按照經驗選取的較優路徑緩存以實現節能,并且提高節點間的有效性、魯棒性和協作的可擴展性。

2.3 GEAR協議

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

2.4 SAR協議

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

3 路由協議對比分析

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

4 結 語

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

(1) 數據融合。節點通過對數據進行融合,降低網絡開銷,節省能量。

(2) 數據命名。數據命名機制能高度搜索用戶所需數據,避免數據在網絡中的重復發送,降低了網絡開銷。

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

節點間重復地收發大量冗余信息所造成的能量浪費。

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

參考文獻

［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年出生,安徽潁上人,碩士研究生。研究方向為短距離無線通信與計算機網絡。

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