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

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

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

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

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

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

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

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

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

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

       1、能量的有效利用

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

       2、擴展性

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

       3、可靠性

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

       4、時延    

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

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

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

       1、 泛洪式算法（Flooding）

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

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

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

       動態源路由算法(Dynamic Source Routing protocol)[2]是按需建立

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

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

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

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

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

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

       4、 GEAR算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

       §2.3路由協議接入方式

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

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

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

【聲明】物流產品網轉載本文目的在于傳遞信息，并不代表贊同其觀點或對真實性負責，物流產品網倡導尊重與保護知識產權。如發現文章存在版權問題，煩請聯系小編電話：010-82387008，我們將及時進行處理。