基于tinyos的無線傳感器網(wǎng)絡(luò)路由協(xié)議的研究與實現(xiàn)

3、 低功耗自適應(yīng)聚類路由算法（LEACH）

LEACH是MIT的Chandrakasan等人為無線傳感器網(wǎng)絡(luò)設(shè)計的低功耗自適應(yīng)聚類路由算法，它是第一個在無線傳感器網(wǎng)絡(luò)中提出的層次式路由協(xié)議。其后的大部分層次式路由協(xié)議都是在它的基礎(chǔ)上發(fā)展而來的。與一般的平面多跳路由協(xié)議和靜態(tài)聚類算法相比，LEACH可以將網(wǎng)絡(luò)生命周期延長15%，主要通過隨機(jī)選擇聚類首領(lǐng)，平均分擔(dān)中繼通信業(yè)務(wù)來實現(xiàn)。LEACH定義了“輪”(round)的概念，一輪由初始化和穩(wěn)定工作兩個階段組成。為了避免額外的處理開銷，穩(wěn)定狀態(tài)一般持續(xù)相對較長的時間。

在初始化階段，聚類首領(lǐng)是通過下面的機(jī)制產(chǎn)生的。傳感器節(jié)點生成0，1之間的隨機(jī)數(shù)，如果大于閾值T，則選該節(jié)點為聚類首領(lǐng)。T的計算方法如下：

其中p為節(jié)點中成為聚類首領(lǐng)的百分?jǐn)?shù)，r是當(dāng)前的輪數(shù)。一旦聚類首領(lǐng)被選定，它們便主動向所有節(jié)點廣播這一消息。依據(jù)接收信號的強(qiáng)度，節(jié)點選擇它所要加入的組，并告知相應(yīng)的聚類首領(lǐng)。基于時分復(fù)用的方式，聚類首領(lǐng)為其中的每個成員分配通信時隙。在穩(wěn)定工作階段，節(jié)點持續(xù)采集監(jiān)測數(shù)據(jù)，傳與聚類首領(lǐng)，進(jìn)行必要的融合處理之后，發(fā)送到sink節(jié)點，這是一種減小通信業(yè)務(wù)量的合理工作模式。持續(xù)一段時間以后，整個網(wǎng)絡(luò)進(jìn)入下一輪工作周期，重新選擇聚類首領(lǐng)。

采用LEACH 方法使因能量耗盡而失效的節(jié)點呈隨機(jī)分布狀態(tài)，因而與一般的多跳路由協(xié)議和靜態(tài)聚類算法相比，LEACH 可以將網(wǎng)絡(luò)生命周期延長15%。但是LEACH 假設(shè)所有的節(jié)點都能直接與簇頭節(jié)點和終端節(jié)點通訊，采用連續(xù)數(shù)據(jù)發(fā)送模式和單跳路徑選擇模式，因此在需要監(jiān)測面積范圍大的應(yīng)用中不適用，而且動態(tài)分簇帶來了拓?fù)渥儞Q和大量廣播這樣的額外開銷。

4、 GEAR算法

GEAR[12]是充分考慮了能源有效性的基于位置的路由協(xié)議，它比其他的基于位置的路由協(xié)議能更好的應(yīng)用于無線傳感器網(wǎng)絡(luò)之中。

GEAR 算法提出既然傳感器網(wǎng)絡(luò)中的數(shù)據(jù)經(jīng)常包含了位置屬性信息，那么可以利用這一信息，把在整個網(wǎng)絡(luò)中擴(kuò)散的信息傳送到適當(dāng)?shù)奈恢脜^(qū)域中。同樣GEAR 也采用了查詢驅(qū)動數(shù)據(jù)傳送模式。它傳送數(shù)據(jù)分組到目標(biāo)域中所有的節(jié)點的過程包括兩個階段：目標(biāo)區(qū)域數(shù)據(jù)傳送和域內(nèi)數(shù)據(jù)傳送。

在目標(biāo)區(qū)域數(shù)據(jù)傳送階段，當(dāng)節(jié)點接收到數(shù)據(jù)分組，它將鄰接點同目標(biāo)域的距離和它自己與目標(biāo)域的距離相比較，若存在更小距離，則選擇最小距離的鄰接點作為下一跳節(jié)點；若不存在更小距離，則認(rèn)為存在“hole”，節(jié)點將根據(jù)鄰居的最小花銷來選擇下一跳節(jié)點。

在域內(nèi)數(shù)據(jù)傳送階段，可通過兩種方式讓數(shù)據(jù)在域內(nèi)擴(kuò)散：在域內(nèi)直接洪泛和遞歸的目標(biāo)區(qū)域數(shù)據(jù)傳送直到目標(biāo)域剩下唯一的節(jié)點。

GEAR 將網(wǎng)絡(luò)中擴(kuò)散的信息局限到適當(dāng)?shù)奈恢脜^(qū)域中，減少了中間節(jié)點的數(shù)量，從而降低了路由建立和數(shù)據(jù)傳送的能源開銷，從而更有效的提高了網(wǎng)絡(luò)的生命周期。缺點是依賴節(jié)點的GPS 定位信息，成本較高。

5、定向擴(kuò)散算法（Direct Diffusion）

Directed Diffusion[10，12，13]是以數(shù)據(jù)為中心的路由協(xié)議發(fā)展過程的里程碑。其他的以數(shù)據(jù)為中心的路由協(xié)議都是基于定向擴(kuò)散改進(jìn)或者采用類似的關(guān)鍵思想來提出的。

Directed Diffusion 算法的主要思想是對網(wǎng)絡(luò)中的數(shù)據(jù)用一組屬性對命名，基于數(shù)據(jù)進(jìn)行通信。Directed Diffusion 采用查詢驅(qū)動數(shù)據(jù)傳送模式。當(dāng)Sink 節(jié)點對某事件發(fā)出查詢命令時就開始一個新的定向擴(kuò)散過程，它由查詢擴(kuò)散，初始梯度建立和數(shù)據(jù)傳送三個階段構(gòu)成（見圖2-1 ）。

在查詢擴(kuò)散階段，Sink 節(jié)點采用和目標(biāo)數(shù)據(jù)相似的一組屬性對（對象的名稱，數(shù)據(jù)發(fā)送間隔時間，持續(xù)時間，位置區(qū)域）來命名它發(fā)出的查詢信息，并將查詢信息通過廣播逐級擴(kuò)散，收到查詢信息的節(jié)點緩存信息，并進(jìn)行局部數(shù)據(jù)聚集，最終查詢信息遍歷全網(wǎng)，找到所有匹配的目標(biāo)數(shù)據(jù)。

初始梯度建立階段實際上和查詢擴(kuò)散階段是同時進(jìn)行的，當(dāng)節(jié)點從鄰接點接收到查詢信息時，若當(dāng)前查詢緩存沒有相同查詢記錄，則加入新記錄，記錄中包含了鄰接點指定的數(shù)據(jù)發(fā)送率也就是“梯度”。

在數(shù)據(jù)傳送階段時，Sink 節(jié)點會對最先收到新數(shù)據(jù)的鄰接點發(fā)送一個加強(qiáng)選擇信息（發(fā)送具有更大的“梯度”的查詢信息），接收到加強(qiáng)選擇的鄰接點同樣加強(qiáng)選擇它的最先收到新數(shù)據(jù)的鄰接點，將這個帶更大“梯度”值的查詢信息進(jìn)行擴(kuò)散，這樣最后會形成一條“梯度”值最大的路徑。目標(biāo)數(shù)據(jù)能沿這條加強(qiáng)路徑以較高的數(shù)據(jù)發(fā)送率來傳送數(shù)據(jù)，而其他數(shù)據(jù)發(fā)送率停留在較低水平的節(jié)點組成的路徑可以作為備選路徑以增加網(wǎng)絡(luò)可靠性。

Directed Diffusion 采用鄰居節(jié)點間通信的方式來避免維護(hù)全局拓?fù)?，采用查詢?qū)動數(shù)據(jù)傳送模式和局部數(shù)據(jù)聚集而減少網(wǎng)絡(luò)數(shù)據(jù)流，因此是一種高能源有效性的協(xié)議。它的缺點是，在需要連續(xù)數(shù)據(jù)傳送的應(yīng)用中（環(huán)境監(jiān)測等）不能很好的應(yīng)用；數(shù)據(jù)命名只能針對于特定的應(yīng)用預(yù)先進(jìn)行；初始查詢的擴(kuò)散開銷大。

6、典型路由算法的性能比較

DSR,LEACH，Directed Diffusion和GEAR協(xié)議克服了Flooding協(xié)議的一些固有缺陷，它們在設(shè)計中充分考慮了能源的有效利用，成倍的提高了整個網(wǎng)絡(luò)的生命周期。這些協(xié)議針對特定的應(yīng)用而設(shè)計，在不同的環(huán)境表現(xiàn)出各自的特色和優(yōu)勢，因此不能絕對的判斷哪種協(xié)議最優(yōu)。

我們分析了每種協(xié)議的特點，對它們的信息處理、路由優(yōu)化方式和網(wǎng)絡(luò)體系結(jié)構(gòu)的不同表現(xiàn)給出了一個綜合比較，如表1所示。

其中路徑優(yōu)化能力指的是在選路的過程中能不能根據(jù)路徑參數(shù)進(jìn)行路徑的優(yōu)化選擇，從多條路徑中選出一條或幾條較好的數(shù)據(jù)傳輸路徑。