無線傳感器網絡具有與傳統(tǒng)網絡不同的特點，它與應用緊密相關。傳統(tǒng)網絡路由協(xié)議不能有效地用于無線傳感器網絡，因而人們研究了眾多的無線傳感器網絡路由協(xié)議。本章對幾種典型的無線傳感器網絡路由協(xié)議做一些分析介紹，比較他們的優(yōu)劣，為后面要設計的路由提供理論基礎。

無線傳感器網絡中信道非常復雜，節(jié)點所處的環(huán)境無法預測，因此給無線傳感器網絡帶來了很多不確定因素，對無線傳感器網絡中的路由協(xié)議的研究是一項極負挑戰(zhàn)性的工作。根據不同的分類標準無線傳感器網絡中的路由協(xié)議可進行多種分類，比如：

1、根據應用要求，傳感器網絡可分為：能量感知路由、基于查詢的路由、地理位置路由和可靠性路由。

無線傳感器網絡具有與傳統(tǒng)網絡不同的特點，它與應用緊密相關。傳統(tǒng)網絡路由協(xié)議不能有效地用于無線傳感器網絡，因而人們研究了眾多的無線傳感器網絡路由協(xié)議。本章對幾種典型的無線傳感器網絡路由協(xié)議做一些分析介紹，比較他們的優(yōu)劣，為后面要設計的路由提供理論基礎。

§2.1 無線傳感器網絡路由協(xié)議的分類與性能指標

無線傳感器網絡中信道非常復雜，節(jié)點所處的環(huán)境無法預測，因此給無線傳感器網絡帶來了很多不確定因素，對無線傳感器網絡中的路由協(xié)議的研究是一項極負挑戰(zhàn)性的工作。根據不同的分類標準無線傳感器網絡中的路由協(xié)議可進行多種分類，比如：

1、 根據應用要求，傳感器網絡可分為：能量感知路由、基于查詢的路由、地理位置路由和可靠性路由。

2、 根據數據收集方式又可分為傳統(tǒng)的當需要時再建立路徑的按需路由機制比如動態(tài)源路由(On-Demand Source Routing protocol , DSR)和基于數據驅動的主動路由機制比如定向擴散路由(Directed diffusion, DD)以及后面本文提出混合路由機制——動態(tài)擴展多路徑路由機制。

3、 根據傳輸過程中采用的路徑的跳數，可分為單路徑路由和多路徑路由。

4、 根據路由是否考慮Qos約束，可分為保證Qos的路由協(xié)議與不保證Qos的路由協(xié)議。保證Qos的路由協(xié)議是指在路由建立的時候綜合考慮時延、誤碼率等Qos參數，從多條路由中選出一條適合Qos約束的最佳路徑。

5、 根據節(jié)點路由過程是否有層次結構，節(jié)點在選路過程中所起到的作用又可分為平面路由和層次路由。平面路由結構簡單，健壯性好，適應傳感器節(jié)點計算功能不強、存儲能力低以及信道復雜多變的特點，但是維護路由的開銷大，擴展性不好，數據傳輸跳數多，適合小型網絡。層次路由擴展性好，適合大型網絡，但是對于簇的維護開銷大，算法復雜，對節(jié)點功能要求高。

針對無線傳感器網絡路由機制的特點，評價一個路由協(xié)議設計是否成功，往往采用以下指標：

1、能量的有效利用節(jié)點所帶的能源有限，如果過多的使用會使部分節(jié)點提前失效，這樣容易產生路由空洞，甚至導致某個區(qū)域的不可到達。為了維持無線傳感器網絡最大的生命周期，設計路由不僅要考慮能量消耗少的路徑，而且要綜合考慮整個網絡的生命周期，均衡整個網絡中節(jié)點能量的消耗，避免出現過度使用某些節(jié)點，使其失效以致出現路由空洞。

2、擴展性

在無線傳感器網絡中，由于布置的節(jié)點所處的地理位置環(huán)境不同，節(jié)點的生存周期也不盡相同。有時甚至是隨即放置節(jié)點，比如：軍方應用時，通過飛機向敵方陣地播撒節(jié)點，這時節(jié)點有的可能會被撒在障礙物比較多的地方，甚至是直接掉進洞里無法于其他節(jié)點聯絡，有的可能放在比較潮濕的地方使電池及早失效，有的在使用過程中由于某種原因引起了位置的移動等等?？偠灾捎诠?jié)點的失效等原因可能要引起整個網絡拓撲的變化，這就要求路由機制能動態(tài)的適應這種變化，具有擴展性，隨著網絡拓撲的變化動態(tài)調整路由。

3、可靠性

前面說過無線傳感器節(jié)點所處的環(huán)境非常復雜，而且難以預測，再加上無線信道非常復雜，數據傳輸的可靠性就顯得非常重要。尤其是某些敏感區(qū)域的探測，比如外太空某區(qū)域環(huán)境的監(jiān)測，煤礦礦井下的瓦斯的監(jiān)測等等，這些數據非常寶貴，數據的安全到達要求無線傳感器網絡的路由機制具有較強的容錯能力。

4、時延

傳感器網絡具有相當多的不確定因素，比如拓撲會動態(tài)變化，節(jié)點間的通信鏈路質量隨著網絡中信息包發(fā)送的數量和節(jié)點間的距離動態(tài)變化等，這些都對數據成功到達目的地的時間提出了挑戰(zhàn)。無線傳感器網絡路由協(xié)議必須能夠快速收斂，特別是一些對實時任務對時間有較高的的要求時。在這方面一般都是減小通信開銷，提高網絡傳輸的效率。

§2.2現有典型無線傳感網絡路由算法的介紹與比較

目前對于無線傳感網絡路由算法的設計，國內外提出了很多解決方案，其中比較具有代表性的有泛洪式算法（Flooding）[7]、動態(tài)源路由算法(DSR)[2]、低功耗自適應聚類路由算法（LEACH）[8，11]、GEAR算法[9]和定向擴散算法（Direct Diffusion）[10，12，13，14]。這些路由算法各有其優(yōu)勢也有缺陷，而且針對不同的具體應用表現出來的性能也大不一樣，但是他們提供了幾種不同的思考方向，對后來的很多路由算法提供了借鑒。接下來將簡單對他們進行介紹。

1、 泛洪式算法（Flooding）

泛洪式算法是一種傳統(tǒng)的洪泛式路由技術，它不需要維護網絡的拓撲結構和路由計算，接收到消息的節(jié)點以廣播形式轉發(fā)數據包給所有的鄰節(jié)點，這個過程重復執(zhí)行，直到數據包到達目的地或者已經達到預先設定的最大跳數。

對于自組織的傳感器網絡，泛洪路由是一種較直接簡單的實現方法，但存在消息的“內爆”（implosion）和“重疊”（overlap）以及“資源盲點”（resource blindness）的特點。

2、動態(tài)源路由算法(DSR)

動態(tài)源路由算法(Dynamic Source Routing protocol)[2]是按需建立路由的一種自適應算法。當某個傳感器節(jié)點采集到數據后，調用路由選取機制，從它的鄰居節(jié)點中選取一個信道較好、能量充沛或者致匯聚節(jié)點（sink節(jié)點）距離最近的節(jié)點作為其轉發(fā)節(jié)點。其他節(jié)點收到這樣的數據包后運行同樣的算法，從其鄰居節(jié)點中找出一個最佳轉發(fā)節(jié)點進行轉發(fā)，直到數據包被發(fā)送到目的地。這種算法簡單，要維護的數據結構簡單，路由維護開銷小，但是它路由選擇時只考慮眼前最優(yōu)，沒有考慮網絡負載，容易導致部分節(jié)點提前失效；單路徑發(fā)送可靠性低，路由的選取具有盲目性，容易走向網絡空洞。

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

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

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

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

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

4、 GEAR算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

路由容錯性能是指路由算法的魯棒性，數據通過該路由算法確定的路徑到達目的地的可靠性。比如當某個傳感器節(jié)點失效時，路由算法可以通過路徑修補繞過該點，當網絡里信道間誤碼率較高或傳感器節(jié)點所處的環(huán)境影響信號傳輸時能夠保證數據的安全傳輸等等。

數據傳輸方式是指信息在傳感器網絡里是通過直接的點對點傳輸還是通過中間節(jié)點，以接力棒的形式進行數據傳輸。

網絡生命周期指的是所布置的無線傳感器網絡能夠進行有效工作的時間，如果網絡中某些節(jié)點由于過度使用而提前失效，致使其他節(jié)點不能進行組網而破壞了網絡的聯通性，這樣雖然其他節(jié)點本身能夠采集并發(fā)送數據，但是由于網絡聯通性被破壞，數據不能到達目的節(jié)點。網絡生命周期是傳感器網絡里非常周要的一個指標。

數據發(fā)送模式指的是數據是主動發(fā)送的還是通過其他節(jié)點的要求來發(fā)送的。主動發(fā)送的數據是根據本地的設定的采樣頻率連續(xù)發(fā)送的，當傳感器采集到數據便打包發(fā)送；通過其他節(jié)點的要求來發(fā)送的模式一般是指匯聚節(jié)點根據需要向目的監(jiān)測區(qū)域發(fā)送查詢命令，通知目的區(qū)域發(fā)送某種類型的數據，目的區(qū)域節(jié)點接到命令后，開啟數據采集功能，根據命令中要求的頻率進行采樣并發(fā)送。

數據/查詢緩存是指路由算法是否設置緩沖池用來為那些已經發(fā)送的數據在本地保留副本以便數據包丟失后進行重傳，或者用來緩存那些接收到的查詢命令等控制信息。數據/查詢緩存的使用一方面可以用于保證數據的可靠性或優(yōu)化路徑，但是另一方面它增加了維護路由的開銷，設計路由要均衡利弊選擇使用。

數據聚集指的是在數據包發(fā)到目的地之前是否都發(fā)到某一個中間節(jié)點進行一些必要的處理，比如某個監(jiān)測區(qū)域監(jiān)測到的數據先發(fā)往一個控制節(jié)點進行數據融合，進行一些必要的數據過濾或者對數據進行求平均值等必要的計算，然后再發(fā)往目的地，這樣可以減少網絡通信量。資源有效性是指監(jiān)測區(qū)域收集的數據與匯聚節(jié)點實際想得到的數據是否一致，監(jiān)測區(qū)域收集數據的頻率和發(fā)送時延是否滿足要求。

分層是指無線傳感器網絡中的節(jié)點之間功能的劃分，如果傳感器網絡中各個節(jié)點的功能一樣，都是即可以采集數據又可以控制路由選擇，那么這種路由是不分層的，又叫平面路由；如果節(jié)點收集到數據后要發(fā)往一個專門的控制節(jié)點進行選路，那個專門的節(jié)點又稱為簇頭，這種路由機制屬于分層的路由，又叫做層次路由。

§2.3路由協(xié)議接入方式

前面說過無線傳感器網絡不同于一般的Ad Hoc網絡，它在資源、傳輸方式以及應用對象方面有自己的特點。無線傳感器網絡的路由協(xié)議與傳感器網絡的特點對應，是與應用緊密相連的。前面提到的幾個應用分別應用的場合也不盡相同，每種協(xié)議都有自己獨特的優(yōu)勢和缺點。這就要求對于不同的應用能夠進行自由的切換路由，路由能夠進行方便的更替?，F在一些應用于無線傳感器網絡的系統(tǒng)中有一些對路由層做了封裝，以配置文件的形式可以動態(tài)的鏈入，比如：加州大學伯克利分校研究的tinyos系統(tǒng)把路由層以組件的形式實現，提供給上層接口進行調用。組建可以自由的更換，只要提供的接口一致，給上層應用的開發(fā)提供了極大的方便，路由層的加入也很方便。Jennic公司研制的bos系統(tǒng)類似于tinyos，相當于tinyos簡化版，傳感器網絡中各部分也是以API接口的形式提供給應用層調用。這些系統(tǒng)的共同之處是為方便應用，把下層包括路由層封裝起來，以API接口的形式提供功能調用。下面以tinyos中路由層的調用方式[3]來說明無線傳感器網絡中路由層的自由變更方式。

如圖2-3所示，AM模塊用于連接發(fā)送模塊，和下面的mac層、物理層通信，調用下層功能完成信息的收發(fā)功能。路由模塊MultiHopRouter利用AM層的收發(fā)接口完成路由選擇、路徑優(yōu)化等功能，提供給上層收發(fā)接口和Intercept接口，其中Intercept接口用于那些收到的不是發(fā)給本地節(jié)點的信息。其中AM模塊（Active Message）用專門的組件封裝好，提供基本的數據的發(fā)送和接收功能。路由層架設在AM層之上，提供路由功能，在路由層之上是傳輸層，由于并沒有在系統(tǒng)中實現，所以用虛線表示。路由層之上實際上是應用層，實現的路由都提供這些接口，上層應用在使用時直接調用這些接口，根本不關心具體的實現。這樣封裝有利于路由層的靈活替換，只要提供相同的接口，就可以很方便的連入應用程序。

傳感器網絡可能需要在相同的監(jiān)測區(qū)域內完成不同的任務，如果為每種任務部署專門的傳感器網絡將增加傳感器網絡的成本。因此，為了完成任務，傳感器網絡需要根據應用環(huán)境和網絡條件自主選擇適用的路由協(xié)議，并在各個路由協(xié)議之間自主切換。靈活的路由自主切換為應用提供了方便，節(jié)省了成本，但是為路由協(xié)議的開發(fā)增加了約束條件，加大了開發(fā)難度，提出新的挑戰(zhàn)。