低功耗路由協(xié)議LEACH及PEGAS—IS對比分析

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

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

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

1．1 LEACH協(xié)議

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

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

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

在第O輪的時(shí)候（r=0），每個(gè)節(jié)點(diǎn)充當(dāng)簇頭節(jié)點(diǎn)的概率為p，在第O輪充當(dāng)簇頭節(jié)點(diǎn)的節(jié)點(diǎn)在后面1／p輪中不能再次充當(dāng)簇頭節(jié)點(diǎn)。這樣，剩下的節(jié)點(diǎn)的數(shù)目變少了，所以能夠充當(dāng)簇頭節(jié)點(diǎn)的概率必須增加才能保證每一輪中的簇的個(gè)數(shù)保持均衡。在經(jīng)過1／p一1輪以后，T=1，此時(shí)對于任何一個(gè)在過去的1／p中還沒有做過簇頭節(jié)點(diǎn)的節(jié)點(diǎn)，都可以成為簇頭節(jié)點(diǎn)，因?yàn)樗泄?jié)點(diǎn)的標(biāo)志值都在0～1之問。經(jīng)過1／p輪之后，所有節(jié)點(diǎn)又可以重新充當(dāng)簇頭節(jié)點(diǎn)了。

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

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

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

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

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

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

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

1．2 PEGASIS協(xié)議

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

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

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

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

（1）在本地?cái)?shù)據(jù)聚合階段，PEGASIS算法中每個(gè)節(jié)點(diǎn)只與離自己最近的鄰居節(jié)點(diǎn)進(jìn)行通信，而不是像LEACH算法一樣需要與簇頭節(jié)點(diǎn)進(jìn)行通信，PEGAS—IS算法大大減小了每輪通信中每個(gè)節(jié)點(diǎn)的通信距離，從而降低了每個(gè)節(jié)點(diǎn)在每一輪通信中所消耗的能量。

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

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

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

2．1 SPIN協(xié)議

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

2．2 DD協(xié)議

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

2．3 GEAR協(xié)議

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

2．4 SAR協(xié)議

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

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

節(jié)能是無線傳感器網(wǎng)絡(luò)最重要的特征，因而高效地利用能量是無限傳感器網(wǎng)絡(luò)路由協(xié)議設(shè)計(jì)的根本出發(fā)點(diǎn)。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é)點(diǎn)定位、具有可擴(kuò)展性、魯棒性、提供QoS支持等。依據(jù)上述性能指標(biāo)，對描述的路由協(xié)議特點(diǎn)進(jìn)行對比的結(jié)果如表1所示。

4 結(jié) 語

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

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

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

（3）局部協(xié)商技術(shù)。協(xié)商技術(shù)能夠有效地避免由于節(jié)點(diǎn)間重復(fù)地收發(fā)大量冗余信息所造成的能量浪費(fèi)。

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