無線自組織網路的路由協議類型

1. 自組織網的現有協議

路由選擇在自組織網中非常重要，它既是信息的傳輸策略問題，也涉及到網路的管理問題。目前自組織網的路由協議一般分為兩種：路由表協議（table driven）和源始發的按需路由協議（source-initiated on-demand driven）。路由表協議包括有：DSDV、CGSR、WRP等，源始發的按需路由協議有：DSR、AODV、LMR、TORA、ABR、SSR等。 路由表協議需網路中的每一個節點都要周期性的向其它節點發
送最新的路由信息，並且每一個節點都要保存一個或更多的路由表來存儲路由信息。當網路拓撲結構發生改變時，節點就在全網內廣播路由更新信息，這樣每一個節點就能連續不斷地獲得網路信息。
4.1.1、序列目的節點距離矢量路由協議(Destination-Sequenced Distance-Vector Routing)
DSDV是基於經典Bellman-Ford路由選擇過程的改進型路由表
演算法。DSDV以路由信息協議為基礎。它僅適用於雙向鏈路，是AD HOC 路由協議發展較早的一種。
依據DSDV，網路中的每一個節點都保存有一個記錄所有目的節點和到目的節點跳數的路由表(routing table)。表中的每一個條目都有一個由目的節點註明的序列號（sequence number），序列號能幫助節點區分有效和過期的路由信息。標有更大序列號的路由信息總是被接收。如果兩個更新分組有相同的序列號，則選擇跳數（metric）最小的，而使路由最優（最短）。路由表更新分組在全網內周期性的廣播而使路由表保持連貫性。
4.1.2、群首信關切換路由協議（Clusterhead Gateway Switch Routing）
CGSR和DSDV的不同之處在於定址方式和網路組織過程。CSGR是有幾種路由選擇方式的分群的多跳移動無線網路。通過群首控制網路節點，信關隔離群，信道接入可以分配路由和帶寬。群首選擇演算法用來選擇一個節點作為群首並在群內應用分布式演算法。信關為那些在兩個或多個群首的通信半徑之內的節點。節點發送數據包首先把它傳送到群首，通過信關到另一個群首，一直重復此過程直到目的節點所在群的群首收到此數據包。然後，數據被傳送到目的節點。用此方式，每個節點必須保存一個群成員表（cluster member table）和路由選擇表（routing table）。群首方式的缺陷在於當群首頻繁的變換時，節點忙於選擇群首而不是數據轉發，這樣反而會影響路由協議的實行。因此，當群內成員發生變化時，產生了最小群變化協議（Least Cluster Change）。利用LCC，只有當一個群內有兩個群首或一個節點在所有的群首通信范圍之外時，群首才發生變換。
4.1.3、無線路由協議（The Wireless Routing Protocol）
WRP是以維護網路中所有節點間的路由信息為目的的基於表的協議。依據WRP，每一個節點都需保存距離表、路由表、鏈路開銷表以及信息轉發表（Message Retransmission List）。
節點通過更新分組告知其它節點鏈路的變化狀況，通過接收相鄰節點的確認分組以及其它信息來獲知其它節點的情況。在WRP中，節點為網路中的每一個目的節點交流距離和下一跳到最後一跳的路由信息。WRP屬於有特殊例外的路徑搜尋演算法。它通過強迫每一節點檢查所有相鄰節點發送的信息記錄來避免無窮計（count-to-infinity）問題。這最終會消除環路現象和當鏈路斷開時提供更快的路由收斂。 （Source-Initiated On Demand Routing）
這種路由選擇方式只有當源節點需要時才建立路由。當一個節點需要到目的節點的路由時，它會在全網內開始路由發現過程。一旦檢驗完所有可能的路由排列方式或找到新的路由後就結束路由發現過程。路由建立後，由路由維護程序來維護這條路由直到它不再被需要或發生鏈路斷開現象。
4.2.1、自適應源路由協議（Dynamic Source Routing）
DSR是基於源路由概念的按需自適應路由協議。移動節點需保留存儲節點所知的源路由的路由緩沖器。當新的路由被發現時，緩沖器內的條目隨之更新。
DSR主要由兩部分組成：路由發現和路由維護。當一個節點欲發送數據到目的節點，它首先查詢路由緩沖器看是否有到目的節點的路由。如果有，則採用此路由發送數據。另一方面，如果沒有，源節點就開始路由發現程序。
路由維護通過路由錯誤分組（route error）和確認分組來實現。當鏈路層遇到傳輸問題時，錯誤分組開始傳送。一旦收到錯誤分組，節點就會把發生錯誤的那一跳從路由存儲緩沖器移走，並會在所有包含那一條的路由里刪掉那一跳。除路由錯誤分組外，確認分組用來驗證路由連接的正確運行。
4.2.2、自組織網按需距離矢量路由協議（Ad Hoc On-Demand Distance Vector Routing）
AODV實質上就是DSR和DSDV的綜合，它借用了DSR中路由發現和路由維護的基礎程序以及DSDV中跳到跳的路由選擇、序列號碼及周期性的更新信息的用法。
和DSDV保存完整的路由表不同的是，AODV通過建立基於按需的路由來減少路由廣播的次數，這是AODV對DSDV的重要改進。和DSR相比，AODV的好處在於源路由並不需包括在每一個數據包中，這樣會使路由協議的開銷有所降低。AODV是一個純粹的按需路由系統，那些不在路徑內的節點不保存路由信息也不參與路由表的交換。
4.2.3臨時排序路由演算法（Temporally-Ordered Routing Algorithm）
TORA是基於『逆向連接』概念的高度自適應、環路開放、分布式路由演算法。TORA主要應用在動態移動網路環境內。它是源始發的路由協議，能向每一對源-目的節點提供多徑路由。TORA的關鍵思想是把路由信息的傳送限制在網路拓撲結構變化處附近較小的范圍內。為了實現這一點，節點必需保留一跳之遠的節點的路由信息。TORA主要實現三個基本功能：路由建立、路由維護、路由刪除。
在路由建立和路由維護的過程中，節點應用『高度（height）』 metric來建立一個以目的節點為根部的指導性的非循環的圖表（Directed Acyclic Graph）。這樣鏈路根據相鄰兩個節點的高度值來確定向上或向下的方向。
4.2.4、基於聯合的路由協議（Associativity-Based Routing）
ABR協議是環路開放的、分組復用的，它為自組織網定義一個新的度量（metric）。這個metric就是聯合穩定性程度（dgree of associativity stability）。在ABR，路由的選擇基於節點的聯合穩定性程度。節點周期性地發送信標來表明自身的情況。一旦相鄰節點收到信標，它們的聯合路由表就會被更新。每接收一個信標，節點就增加一個關於發送信標的節點的聯合條目。聯合穩定性通過節點和其它節點在時間和空間的連接穩定性來定義。高聯合穩定性也許意味著節點的低移動率，而低穩定性意味著高移動率。當節點的相鄰節點或節點本身移動出相鄰的范圍時，聯合條目會被刷新。ABR的基本目標是為自組織網找出生命時間更長的路由。
4.2.5、信號穩定性路由協議（Signal Stability Routing）
SSR是基於自適應路由協議的按需路由協議。SSR選擇路由是基於節點間信號的強度以及節點位置的穩定性。這種路由選擇標准有選擇強連接性路由的作用。SSR可分成兩部分:DRP(Dynamic Routing Protcol)動態路由協議和SRP靜態路由協議(Static Routing Protcol)。
DRP主要負責路由表(Routing Table)和信號穩定程度表(Signal Stability Table)的維護。所有的傳送過程及接收都在DRP進行。SRP則負責處理節點接收的數據。

2. 移動自組織網路路由協議簡介

MANET 為Mobile Ad hoc network的簡稱，Ad hoc網路是一種自組織網路。
 由於 MANET 網路中無線通信節點的能量一般都是受限的，通信范圍並不能從源節點直接覆蓋網路中的所有其他通信節點。節點間進行數據通信時，一般需要其他網路節點的協助，通過 多跳傳輸 才可以轉發到並未直接相連的目的節點，所以路由協議是 MANET 網路關鍵技術中十分重要的一部分。在傳統的通信網路中，路由器一般不移動，很少出現路由器在通信的過程中隨意加入或者離開網路的情況，普通的路由協議對於 MANET 這類拓撲頻繁動態變化的網路顯然是不適用的。因此，有必要針對具體的移動無線自組織網路應用環境的特點，設計相應的 MANET 路由演算法。
 如圖所示，MANET 網路的路由協議分類方法有很多種，並且新的路由協議也在不斷的出現。根據路由發現機制的不同，基本可以被分為表驅動路由協議、按需路由協議以及混合式路由協議三種類型。

又稱為 先驗式路由協議 。網路中的節點維護一個包含其它網路節點信息的路由表。MANET網路中的每個節點都周期性地廣播路由分組，同時通過從網路接收到的路由分組信息，持續更新自身的路由表。在發生網路拓撲結構性改變的時候，通信節點打包更新消息並發送給其它通訊節點，讓它們更新最新路由。這樣網路中的節點都一直保持准確最新的路由信息，無論是否有數據通信的需要。當有數據轉發需求的時候，節點根據自身維護的路由表選擇路由，作為發送或者轉發數據包的下一跳節點。表驅動路由協議可以實現較低的端到端時延（End-to-End Delay），但是為了計算路由而周期性廣播信標會產生較大的網路開銷。 DSDV （目的序號距離矢量）協議、 OLSR （優化鏈路狀態路由）協議是此類協議的主要代表。

又稱為 反應式路由協議 。當自組織網路中的節點有通信需求的時候，進行路由搜索操作，本身並不保存路由信息。當通訊節點有發送數據包的需求時，該節點將會在網路中進行路由搜索，查找可以到達目的節點的路徑；只有找到一條滿足條件的可用路徑後，數據包的發送過程才執行。把先前獲得的路由信息緩存到本地當中，作為後續發送使用，可以加速網路效率。比起表驅動路由，按需路由沒有周期性廣播控制消息，因此降低了路由開銷，極大的節省了網路帶寬。按需路由協議有一個缺點是，如果在發送數據包的時候，找不到可用的路由路徑信息，需要發起路由搜索。端到端時延（End-to-End Delay）在按需路由協議中可能比較高。 AODV （無線自組網按需平面距離向量路由）協議、 DSR （動態源路由）協議是按需路由協議的主要代表。

混合（分級）路由協議，就是結合上述兩種路由協議的優勢而得到的一類路由協議。在上文提到的兩種路由協議中，所有節點的功能都為平等的，通常來說這兩種路由協議都是單層架構的平面路由協議。而在分級路由協議中，層次指的是一個「區」或「簇」，可以採用兩種方法來對節點分級。一種分級的方式是隱式的，被稱為邏輯分級：每一個網路節點都被包含於某一個本地范圍內，而對於本地范圍的內部與外部則分別使用不同的路由發現機制。另一種分級的方式是物理分級。首先是構建簇，將那些在地理位置方面具有緊密聯系的相關節點構建成一個顯式的簇，然後從每個簇中選擇出一個節點作為該簇的簇首，選擇出的簇首節點與同一個簇內的各個節點都是可以直接進行一跳通信的。網路由若干個節點組成，在層內的節點使用先驗式路由演算法，在層間節點間則用反應式路由演算法。混合路由協議避免了前面兩類協議的缺陷：表驅動路由協議中過量的拓撲控制消息流量問題和按需路由協議中的長時延問題。常見的混合路由協議有 ZRP （區域路由）協議、CBRP（分簇路由）協議等。

這是不同於以前提到的三種路由協議。由於目前大量的通信節點都帶了定位裝置，使這類型協議開始流行。利用位置信息，可以優化的路由性能的自組織網路，再通過限制路由發現的洪泛，以減少拓撲控制消息的數量。 GPSR （貪婪周邊無狀態路由）和LAR（地理信息輔助路由）路由協議都屬於地理位置輔助路由協議。