摘要：文章分析了Ad Hoc網絡的特征以及路由設計協議所面臨的問題與挑戰，綜述了Ad Hoc網絡的傳統路由協議，針對理想自組網路由協議應滿足的7個方面，著重對適用于不同業務需求和網絡需求的路由協議進行了介紹，為Ad Hoc網絡路由協議的進一步研究提供了參考。
關鍵詞：Ad Hoc網絡；路由協議；改進型；綜述

移動Ad Hoc網絡(MANET)是由一組帶有無線收發裝置的移動節點形成一個多跳的、臨時性的自治系統。整個網絡沒有固定的基礎設施，每個節點都是移動和動態變化的，可以隨時隨地快速進行部署。與有中心網絡相比，Ad Hoc網絡靈活、健壯、投資少，具有自組織性、自成形性并能夠根據應用需要快速形成．特別適合于作戰指揮、搶險救災以及應付突發事件和執行臨時任務的場合。因為自組網中節點的傳輸范圍有限，源端向目的端發送數據時，通常需要其它節點的輔助，所以路由協議是自組網中不可缺少的一部分。由于Ad Hoc自身復雜多變的動態特性，路由協議的設計目前仍是一個人們關注的熱點問題。

1 Ad Hoc網絡的特征及路由協議設計面臨的挑戰
在Ad Hoc網絡中，網絡拓撲、移動節點的分布情況及其自組織能力對Ad Hoc網絡都具有重要的影響。正是因為Ad Hoc網絡具有其自身的特征，為路由協議的設計提出了新的問題和挑戰，主要表現在以下幾個方面：
1)網絡拓撲動態變化與多播支持。網絡節點可以任意自由移動，因此網絡的拓撲可以隨時發生快速動態隨機的變化。這使得Ad Hoc網絡中多播樹不再是靜態的，所以多播路由協議必須能夠處理節點的快速移動和動態地加入與離開。
2)多跳信道共享與單向信道支持。Ad Hoc網絡中節點之間的信道共享采用多跳的模式。當目標節點不在源節點的傳輸范圍之內時必須借助其他節點進行中繼轉發。由于網絡內的所有節點共享同一信道，所以形成了多跳模式的信道共享。同時，因發射功率、地理位置等因素的影響，可能存在單向信道，因此必須解決好認知的單向性、路由的單向性和匯點的不可達等問題。
3)對QoS的支持。QoS的支持主要是指能夠保證用戶所規定的一些服務特性，如延遲、帶寬、丟包率等。在無線自組網中，需要同時考慮網絡層和MAC層的QoS，必須充分考慮節點的動態性、終端的隱藏性和鏈路的波動性，深入研究支持端對端的QoS和自適應的QoS。
4)帶寬有限性。無線信道的容量比有線信道要低，且易受噪聲、路徑衰減、多徑衰落等因素的影響，所以實際能夠使用的信道帶寬十分有限，而且隨時間和環境的變化而變化。因此，必須充分考慮信號衰減、噪音干擾、信道間干擾等多種因素。
5)安全機制受限。和傳統有線網絡相比，這種網絡更容易受到物理上的安全威脅。無線信道的廣播特性致使Ad Hoc網絡易受來自惡意節點的攻擊，如偷聽(Eavesdropping)和拒絕服務(Denial-of-Service)，而且Ad Hoc網絡缺乏固定的網絡基礎設施進行用戶認證和授權。
6)能量有限性。Ad Hoc網路中的節點一般依賴于電池進行正常的工作。有限的電池能量不僅用于處理節點自身的數據，還用于處理和轉發來自其它節點的數據。因此，必須考慮電源因素。
7)地理位置支持。在Ad Hoc網中利用位置信息，可以使節點在尋找路由時避免簡單的洪泛：利用相鄰節點或目的節點的位置信息，可以提高路由尋找的效率，即路由是空間的。

2 傳統路由協議及其特性
無線自組網路由協議具有預先獲取(proactive)和按需獲取(reactive)兩種路由策略。其中，主動路由采用Proactive策略，按需路由采用Reactive策略。本文根據協議的工作機制將現有協議分為3類：主動路由協議、按需路由協議及混合路由協議。
2．1 主動路由協議
要求每個節點維護一張或幾張路由表，其中包含了網絡中所有其他節點的路由信息。所有節點周期性地更新這些路由表，以保證路由信息是一致和最新的，當網絡拓撲結構改變時，節點向整個網絡傳播路由變更消息。主動路由的優點是獲取路由的延時小。因為每個節點都保存著到其它節點的路由信息，這非常適合于有實時要求的應用。缺點是需要花費較大的開銷保持路由更新。當網絡規模較大、移動速度較高時，會消耗大量的帶寬和節點能量，同時也浪費了一些資源來建立和重建那些根本沒有被使用的路由。
主動路由協議主要有DSDV、WRP、CGSR、GSR、AGSR、FSR、HSR、ZHLR、LANMAR，研究最深入的是基于經典Bellman—Ford算法基礎之上的表驅動路由協議DSDV。
2．2 按需路由協議
與主動路由協議不同，按需路由協議只有在需要時才進行路由發現，以緩解主動路由協議由于周期性交換更新信息帶來的開銷和擴展性問題。這類協議一般通過請求／應答過程來發現到一個目標的路由。在需要路由信息時，都經過一個路由發現階段。當節點要發送數據包時，先以泛洪式廣播路由請求包。當路徑發現后或者所有可能的路徑都查找完時這個階段結束。接下來路由維護階段一直持續到這條路由不再需要或者目的地變成不可到達時。采用按需路由協議的優點是不需要進行周期性的路由信息廣播，節省了一定的網絡資源；缺點是獲取路由延時相對較大、出現“廣播風暴”以及單向鏈路問題。
按需路由協議主要有AODV、DSR、ABR、SSR、CBRP、LAR，常用的有AODV、DSR、TORA等。
2．3 混合路由協議
混合路由協議是在Ad Hoc網絡規模大、組成員關系變化快、而少量成員的位置和鏈路連接狀態穩定的條件下提出的。它結合主動和按需兩類路由協議，避免了主動路由協議中過量的控制消息流量問題和按需路由協議中的長時延問題，達到取長補短的效果。此類協議的關鍵點在于兩種協議應用區域的劃分，合理的劃分方法應該隨不同情況采用自適應的策略，協議的性質在主動和按需之間應隨網絡的具體環境變化可以自動調整。
混合路由協議主要有ZRP、DDR、CEDAR、HARP、BRP、IARP、IERP等，其中最具代表性的就是區域路由協議ZRP(Zone Routing Protocol)。

3 改進型路由協議及其特性
一個理想的自組網的路由協議應當滿足以下7個方面的要求：分布式運行、提供無環路由、按需操作、單向信道支持、提供節能策略、可擴展性、安全性。目前，大量的Ad Hoc網絡路由協議針對不同的設計要求，使用了不同的技術方法，適用于不同的網絡環境。下文將依次介紹在節能策略、QoS支持、GPS輔助、多播支持、多路徑支持、安全性等方面具有一定優越性的路由協議。
3．1 基于節能的路由協議
能量問題是制約Ad Hoc網絡發展要解決的主要問題之一。目前提出的具有能量意識的路由協議可以分為四類：最小能量路由(MER)、最小電池耗費路由(MBCR)、最小最大電池耗費路由(MMBCR)、受限的最大最小電池容量路由(CMMBCR)。對DSR協議進行優化，提出以下基于能量控制的改進協議。
SDDRP(Source-Destination Determined Delay Routing Protocol)：同時考慮網絡的連通信息和節點剩余能量來選擇路由，在保證網絡正常運行的基礎上保護了剩余能量不多的節點，均衡了各個節點的能量損耗。
MMPEW-DSR(Maximum Minimum Power-Energy Weight DSR)：節點剩余能量和傳輸功率鏈路狀態函數作為路由選擇的參數，減少節點的能量消耗，保護低能量節點，延長網絡的生存時間。
TBDB(Traffic balanced Degree-based)：選擇路由的原則是最小條路由，由節點根據本身負荷的情況決定是否作為新建路由的轉發節點，對可選的路徑集合進行了限制，避免了擁塞路徑，獲得了很高的網絡利用率。
3．2 基于QoS的路由協議
Q_AODV根據帶寬來選擇QoS參數，為每個路由條目定義了5種狀態：空閑、接收路由請求、已經預約、上游斷路和下游斷路，為每個狀態設置計時器來保證QoS的有效性。當計時器超過或者收到路由控制消息，節點轉移到另外一個狀態。
CEDAR(Core-Extraction Distributed Ad Hoc Routing)根據帶寬來選擇QoS參數，是一種分級路由協議。它通過在網絡中建立一個穩定的虛擬核心來擴散路由信息，按需式的且由核心節點基于局部狀態計算路由，適用于中小規模的移動Ad Hoc網絡。
STARA(System and Traffic Dependent Adaptive Routing Algorithm)根據平均時延最短來選擇QoS參數，該協議采用最短路徑算法計算路徑，但“最短”路由度量采用平均延時時間，而非跳數，即在進行分組路由時，考慮無線鏈路的容量和排隊延時等因素。
ABGP(Advanced Bandwidth Guaranteecl Routing)根據電池剩余量和帶寬選擇QoS參數，采用了多種限制擴散的機制來解決網絡中盲目擴散而導致的帶寬損耗問題，并充分考慮了節點的電能受限問題，試圖在路由選擇的過程中延長網絡的完整性，避免由于部分節點過早地耗盡電能而使網絡被分割。
TBP(Ticket-Based Probing)是基于標簽探測的路由協議，該協議基于標簽方式進行一跳一跳地尋找出多條較優的路徑。首先源節點發送標簽來探測路徑，如果發送的標簽只有n個標簽，那么最多就只能找n條路徑；其次中間節點收到標簽，根據自己以往統計信息，判斷是否要拆分標簽并重新分發標簽，發往代價最小的下游結，最后目的節點響應相應多條路徑給源節點。
3．3 基于GPS輔助的路由協議
在自組網中利用GPS提供的有關節點位置信息，可以使節點在尋找路由時避免簡單的洪泛；利用相鄰節點或目的節點的位置信息，可以提高路由尋找的效率。其缺點是依賴于GPS可能限制其應用范圍。該類協議的關鍵點是如何有效利用GPS提供的位置信息又能盡量減小交換位置信息帶來的開銷，以免得不償失。典型協議的有以下幾個：
DREAM(Distance Routing Effect Algorithm For Mobility)的特點就是距離效應和移動速率兩個規則的運用。每個節點維持一個包含所有節點位置信息的表，根據上述規則定期廣播控制信息來通知其它節點自己的位置信息。DREAM對于節點移動速度表現出很好的強壯性，但是在重負荷環境下效果較差。
LAR(Location-Aided Routing)利用GPS提供的信息執行一種“有限泛洪”路由請求方式。需要發送路由請求包時，源節點根據目標節點的位置和速度信息計算一個區域作為請求范圍并附之于包頭。只有位于請求范圍內的節點才可進行路由請求信息的轉發，從而減小了發現路由的開銷。
此類協議還包括GPSR、GRA、GLS、GEOCAST、GEDIR等。
3．4 基于多播的路由協議
多播是一種一點對多點或多點對多點的分組傳輸方式，它能夠最優化地利用網絡資源，很好地適應Ad Hoc網絡帶寬受限和能量受限的環境，提高網絡的整體性能。多播路由協議設計的基本思想是以最少的冗余建立組成員的路徑。根據采用轉發結構、拓撲結構的不同，可分為：基于樹多播協議、基于格網多播協議、混合多播協議和無狀態多播路由協議。
基于樹的多播路由協議在有線網絡中具有突出的優越性能，將其特性運用于Ad Hoc網絡，設計出適合Ad Hoc網絡的典型協議有MAODV、AMRIS、LGT、LAM、ABAM、ADMR。
基于格網的多播路由中，多播發送者與接收者問存在多條路徑，這就提高了網絡的動態適應能力，健壯性好，不需要因為少量鏈路的失效而重新配置多播網結構，路由維護開銷少。典型的基于格網多播路由協議有ODMRP、CAMP、FGMP、NSMP。
基于樹的多播路由具有較高的分組轉發有效性，但魯棒性差。基于格網的多播路由魯棒性好，但以犧牲有效性為代價。混合的多播路由綜合了兩種多播路由的優點來提高總體性能。典型的混合多播路由協議有AMRoute協議和MCEDAR協議。
無狀態的多播路由主要用于小規模的多播，并由單播路由協議根據分組的報頭轉發到各個接收者，避免了因頻繁的拓撲變化導致的開銷過大，但可擴展性較差。典型的無狀態多播路由協議是DDM。
3．5 基于多路徑的路由協議
多路徑路由是指在Ad Hoc網絡中找出到達目的節點的多條路徑，作為當前路徑的備份路徑，當前路徑斷裂后，從備份路徑中選擇一條最佳路徑繼續進行路由，從而提高帶寬使用效率，增加傳輸可靠性以及減輕擁塞，實現網絡負載均衡和網絡資源的充分利用。現有的多路徑路由協議大多是在原有單路徑路由協議的基礎上通過添加多路徑的方法實現的。
D—AOMDV協議是對AODV路由協議的多路徑擴展，以距離矢量概念為基礎，通過計算多條開環、節點或鏈路不相交路徑，充分利用已有的有效路由信息，達到提高路由效率的目的，在動態高速環境下具有較高的效率。
文章提出了一種新的多路徑路由算法。該算法基于穩定性因子計算路徑間海明距離并據此選擇多條相似的穩定不相交多路由，從而進一步提高該路由算法的性能。
目前多路徑路由協議還有OLSR、OSPF、TYBRPF、AOMDV、TORA、MP—DSR、ROAM、SMR等。
3．6 基于安全機制的路由協議
Ad Hoc網絡具有分布式控制、開放傳輸媒介、有限傳輸帶寬和有限終端等特點，路由協議中引入安全機制尤為重要。移動Ad Hoc網絡的安全策略分為三類：加密、檢測和冗余路徑。目前典型的安全路由協議有以下幾種：
ARIADNE協議是在DSR的基礎上開發的，該協議在TESLA廣播認證協議的廣播認證消息中添加MAC保證路由安全。采用類單向Hash鏈表在兩個端節點之間建立共享對稱密鑰來保證端到端的完整性。該協議可以防止惡意節點進行路由黑洞攻擊，主要缺點是需要時鐘同步。
SEAD協議構建于DSDV基礎上，該協議利用Hash鏈表來認證路由更新信息的序列號、度量值和跳數，并提出了節點之間的相互認證機制。該協議可以抵御黑洞攻擊及一定程度的DoS攻擊，但需要同步時鐘，且無法抵御增大度量值的偽造攻擊。
ARAN協議是基于按需路由協議開發的，該協議利用公鑰證書體制提供消息鑒別、完整性以及不可抵賴性等安全機制，可以檢測和防止Ad Hoc網絡中的第三方和窺探者的攻擊。ARAN的缺陷在于路徑中每個節點僅有下一跳信息，因而無法保證路徑的最優性。
此外該類協議還有SRP、SAR、MRM、SNS、NUGLETS等。

4 結束語
由于Ad Hoc網絡復雜多變的特性，路由協議設計仍是Ad hoc網中一個非常重要的研究方向。當前，雖然此項研究取得了較大進展，但出現的各種網絡路由協議都只是在某些性能上具有優勢，只能滿足部分需求。設計一種快速、準確、高效、可擴展性好的Ad Hoc網絡協議，必須綜合現有各種路由協議的優點并加以改進完善，尚需開展大量的研究工作。此外，Ad Hoc網絡與蜂窩網的結合技術ODMA(機會驅動多址接入)以及Ad Hoc網絡中OFDM(正交頻分復用)技術的運用也是研究的熱點。