基于tinyos的無線傳感器網絡路由協議的研究與實現

3、 低功耗自適應聚類路由算法（LEACH）

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

在初始化階段，聚類首領是通過下面的機制產生的。傳感器節點生成0，1之間的隨機數，如果大于閾值T，則選該節點為聚類首領。T的計算方法如下：

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

采用LEACH 方法使因能量耗盡而失效的節點呈隨機分布狀態，因而與一般的多跳路由協議和靜態聚類算法相比，LEACH 可以將網絡生命周期延長15%。但是LEACH 假設所有的節點都能直接與簇頭節點和終端節點通訊，采用連續數據發送模式和單跳路徑選擇模式，因此在需要監測面積范圍大的應用中不適用，而且動態分簇帶來了拓撲變換和大量廣播這樣的額外開銷。

4、 GEAR算法

GEAR[12]是充分考慮了能源有效性的基于位置的路由協議，它比其他的基于位置的路由協議能更好的應用于無線傳感器網絡之中。

GEAR 算法提出既然傳感器網絡中的數據經常包含了位置屬性信息，那么可以利用這一信息，把在整個網絡中擴散的信息傳送到適當的位置區域中。同樣GEAR 也采用了查詢驅動數據傳送模式。它傳送數據分組到目標域中所有的節點的過程包括兩個階段：目標區域數據傳送和域內數據傳送。

在目標區域數據傳送階段，當節點接收到數據分組，它將鄰接點同目標域的距離和它自己與目標域的距離相比較，若存在更小距離，則選擇最小距離的鄰接點作為下一跳節點；若不存在更小距離，則認為存在“hole”，節點將根據鄰居的最小花銷來選擇下一跳節點。

在域內數據傳送階段，可通過兩種方式讓數據在域內擴散：在域內直接洪泛和遞歸的目標區域數據傳送直到目標域剩下唯一的節點。

GEAR 將網絡中擴散的信息局限到適當的位置區域中，減少了中間節點的數量，從而降低了路由建立和數據傳送的能源開銷，從而更有效的提高了網絡的生命周期。缺點是依賴節點的GPS 定位信息，成本較高。

5、定向擴散算法（Direct Diffusion）

Directed Diffusion[10，12，13]是以數據為中心的路由協議發展過程的里程碑。其他的以數據為中心的路由協議都是基于定向擴散改進或者采用類似的關鍵思想來提出的。

Directed Diffusion 算法的主要思想是對網絡中的數據用一組屬性對命名，基于數據進行通信。Directed Diffusion 采用查詢驅動數據傳送模式。當Sink 節點對某事件發出查詢命令時就開始一個新的定向擴散過程，它由查詢擴散，初始梯度建立和數據傳送三個階段構成（見圖2-1 ）。

在查詢擴散階段，Sink 節點采用和目標數據相似的一組屬性對（對象的名稱，數據發送間隔時間，持續時間，位置區域）來命名它發出的查詢信息，并將查詢信息通過廣播逐級擴散，收到查詢信息的節點緩存信息，并進行局部數據聚集，最終查詢信息遍歷全網，找到所有匹配的目標數據。

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

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

Directed Diffusion 采用鄰居節點間通信的方式來避免維護全局拓撲，采用查詢驅動數據傳送模式和局部數據聚集而減少網絡數據流，因此是一種高能源有效性的協議。它的缺點是，在需要連續數據傳送的應用中（環境監測等）不能很好的應用；數據命名只能針對于特定的應用預先進行；初始查詢的擴散開銷大。

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

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

我們分析了每種協議的特點，對它們的信息處理、路由優化方式和網絡體系結構的不同表現給出了一個綜合比較，如表1所示。

其中路徑優化能力指的是在選路的過程中能不能根據路徑參數進行路徑的優化選擇，從多條路徑中選出一條或幾條較好的數據傳輸路徑。