Ad Hoc網(wǎng)絡(luò)路由協(xié)議綜述

摘要：文章分析了Ad Hoc網(wǎng)絡(luò)的特征以及路由設(shè)計協(xié)議所面臨的問題與挑戰(zhàn)，綜述了Ad Hoc網(wǎng)絡(luò)的傳統(tǒng)路由協(xié)議，針對理想自組網(wǎng)路由協(xié)議應(yīng)滿足的7個方面，著重對適用于不同業(yè)務(wù)需求和網(wǎng)絡(luò)需求的路由協(xié)議進行了介紹，為Ad Hoc網(wǎng)絡(luò)路由協(xié)議的進一步研究提供了參考。
關(guān)鍵詞：Ad Hoc網(wǎng)絡(luò)；路由協(xié)議；改進型；綜述

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

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

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

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

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