移動Ａｄ ｈｏｃ網絡多徑路由協議

摘要:給出移動Ad hoc網絡多徑路由的分類方法，系統地描述了當前各種典型的MANETs多徑路由協議，并比較和分析了這些協議的特點及適用情況。最后結合該領域當前的研究現狀，指出多徑路由協議存在的問題和未來的研究重點。

關鍵詞:移動自組織網絡; 多徑路由; 路由協議

中圖分類號:TP393文獻標志碼:A

文章編號:1001－3695(2008)02－0591－03

現有的MANETs 路由協議在源和目的節點對之間建立并使用一條單路徑。由于節點移動性#65380;節點失敗以及無線信道的動態特征，單路徑中的鏈路可能會臨時失效從而導致路徑不可達，而尋找替代路徑的開銷大，并且可能帶來數據包轉發的額外延時。多徑路由[1]提供了到一個目的節點的多條路徑，源和目的節點可以使用這些路徑作為主路徑和候選路徑，也可以有選擇地在多條路徑上并發傳輸。多徑路由技術將通信傳輸分散到多條路徑上進行，可以實現載荷平衡;能夠提供較好的容錯能力和較高的帶寬;能夠補償Ad hoc網絡的動態特性和不可預測性;能夠在一定程度上解決高密度移動Ad hoc網絡的無線信號干擾問題;同時，在高密度移動Ad hoc網絡環境中采用多徑路由得到的吞吐量高于采用單徑路由得到的吞吐量。

1多徑路由協議分類及協議描述

目前，研究者們已提出了許多適用于Ad hoc網絡的多徑路由協議。歸納起來可將Ad hoc網絡的多徑路由協議分成六類，如圖1所示。

1.1平面式多徑路由協議

1.1.1主動式(表驅動)多徑路由協議

SR－MPOLSR(source routing based multi－path OLSR)[2]是最優化鏈路狀態(OLSR)[3，4]協議的多徑擴展。協議首先用源路由進行數據重發;然后用多重Dijkstra算法計算到達同一目的節點的多條路徑，并且同時使用這些路徑發送數據包。在使用多路徑分發數據包時，用類似動態源路由(DSR[5])機制避免了路徑相交。SR－MPOLSR仍然用OLSR協議中的HELLO消息進行鏈路狀態探測和鄰居發現，然后MPR(多點中繼)節點建立鄰節點表并且在泛洪過程中轉發TC (拓撲控制)消息。協議所采用的多重Dijkstra算法的基本思想是:首先用Dijkstra算法計算最短路徑，同時復制整個拓撲并且其他所有在已計算的最短路徑之間的節點將被刪除;其次再用Dijkstra算法計算次短路徑，這樣一直計算下去，直到找到所有的備選路徑;在找到所有的備選路徑之后就可以進行數據傳送。SR－MPOLSR采用基于權重的羅賓環策略來分配網絡負載。

1.1.2被動式(按需)多徑路由協議

AOMDV(Ad hoc on－demand multipath distance vector，Ad hoc按需多徑距離矢量)[6]路由協議是在AODV[7]路由協議基礎上擴充而成的。AOMDV協議計算多條開環#65380;鏈路不相交路徑，提供有效的容錯能力，快速#65380;有效地恢復動態網絡中的中斷路由。AOMDV協議采用廣告跳數(advertised hop count)這個概念來維護多條開環路徑。AOMDV協議在一次路由尋找進程中運用泛洪的一種特定屬性來確保所計算出來的多條路徑鏈路不相交。AOMDV協議的一個顯著特點就是盡可能地使用基本的AODV協議中已有的有效路由信息。因此計算多路徑所需的額外開銷非常少。它由兩個主要部分組成:路由更新規則，用于建立和維護到達每個節點的多條開環路徑;分布式協議，用于尋找鏈路不相交的多條路徑。

SMR(split multipath routing，分離多徑路由)[8]協議采用請求/應答交互機制建立和使用最大不相交路徑的兩條路由。兩條路由是按需尋找的，其中有一條是最短時延路徑。建立的各條路由不必等長度。SMR協議有兩種維護方法:一種是當一個會晤使用的兩條路由只要任何一條路由失去連接后則建立一對新路由;另一種是只有兩條路由全部中斷后才重新進行路由尋找。源節點在泛洪一個RREQ消息接收到一個RREP消息后，使用最先找到的路由來發送緩存數據包;當源節點接收到第二個RREP消息后就有兩條到達目的節點的路由，可以將其傳輸分配到兩條路由上來進行。這樣可以提高數據包傳送率，減少網絡延遲。

1.1.3混合多徑路由協議

AntHocNet(ant agents for hybrid multipath routing in mobile Ad hoc networks)[9]協議是基于ACO(ant colony optimization ，蟻群優化)框架設計的MANET多徑路由協議。它包括主動(proactive)和被動 (reactive)兩個組件。算法僅在有數據會話時才建立路徑，這一步驟在被動路徑建立階段完成。其中，被動前向螞蟻(reactive forward ants)負責找到到達目的節點的多條路徑，然后后向螞蟻(backward ants)返回源節點建立數據傳送路徑。與其他ACO算法一樣，路徑的建立是由荷爾蒙表(Pheromone table)中特定參數決定的。當路徑建立之后，數據包就按荷爾蒙表沿不同的路徑隨機傳送至目的節點。在數據會話進行的過程中，源節點按照數據發送率發送主動前向螞蟻(proactive forward ants)來維護和更新路由信息。當發生斷鏈時，算法采用被動策略。

在被動路徑建立過程中，如果表中的荷爾蒙信息有效，被動前向螞蟻將選擇概率為 Pnd的下一跳節點n:

如果對于目的節點d而言沒有可用的荷爾蒙信息，螞蟻采用廣播的方式分布到整個網絡中。在隨機路由過程中，仍然采用式(1)選擇下一跳節點，只是此時選擇的參數值β(β是降低螞蟻探索行為的參數值)較前次的 β值大( β2≥β1)，這是為了選取更好的路由。采用這種策略，可以使數據開銷沿路徑估算的質量進行傳播，最終達到平衡網絡負載的目的。

1.2分簇式多徑路由協議

CMDSR(cluster－based multipath dynamic source routing)[10]協議是在DSR協議的基礎上擴展而來的。其主要思想是在分簇算法中將網絡分成單元簇(1－cell cluster)和中心簇(2－server cluster)兩級層次結構(圖2)，將路由發現功能遷移到2－server層以防止類似DSR路由發現過程中的泛洪，實現路由開銷最小化;同時提高網絡的可擴展性，能夠有效地適應節點數目和密度增大的網絡。此外，CMDSR通過選擇可靠的路徑和發送端到端的可靠性軟保證的方法提高了傳輸可靠性。

算法首先通過簇的初始化#65380;簇的更新及中心簇server的選舉來建立簇結構，然后開始執行CMDSR協議。CMDSR協議用路徑可靠性模型[11]來評估源節點和目的節點之間有效路徑的路由可靠性。源節點i與目的節點j之間第k條路徑的可靠性定義為PkS，D(t)=∏(i， j)∈kPi， j(t)。

源節點通過向其簇頭節點發送RREQ消息建立到目的節點的連接，收到RREQ消息的簇頭節點判斷此源節點和目的節點是否在一個簇中。如果在一個簇中，源節點立即發起路由發現過程;否則，簇頭節點將這一RREQ消息向上發給server節點，由server節點找到目的節點所在的簇，并將可能的穩定的連接路徑以隊列的方式發給源節點。對于收到的大量RREQ消息，目的節點采用反向路徑標注算法找出能夠提供大于最低可靠性值(Plower)的不相交的路徑集合。反向路徑標注算法由三步組成:首先采取路徑排序算法將所有可能的路徑(由RREQ消息得到)按路徑可靠性累加和值的大小降序排列;然后用不相交路徑選擇算法選擇有效路徑;最后目的節點將選擇好的路徑結果通過RREP消息回復給源節點，這樣源節點與目的節點之間就可以傳送數據了。CMDSR協議采用動態可靠性路徑的修復和維護策略。

1.3基于地理位置信息的多徑路由協議

MLAR(multipath location aided routing)[11，12]協議是LAR(location aided routing)[13]協議的多徑擴展版本。LAR協議是一個按需的源路由協議，與DSR協議類似;不同的是:源節點S用前向區域(forwarding zone)的方法發送附帶位置信息的路由請求到目的節點D。S和D的中間節點用LAR協議的兩種策略之一(LAR box或LAR step)來決定一個路由請求的前向區域。MLAR協議采用LAR box策略(圖3)，通過添加一個笛卡兒Z軸，可以將二維LAR協議擴展到三維。

MLAR協議設計的初衷就是為了解決MANET節點的移動性使LAR協議的路徑失效問題。其基本思想是在一個特定時間僅使用一條路徑，保存其他已發現的路徑作為主路徑失敗時的備用路徑。緩存兩條最近接收到的路徑，如果這兩條路徑到達緩存的時間幾乎相同，那么其中較短的路徑就作為主路徑。如果備用路徑也失敗，就重新發起一個新的路由請求過程。如果MLAR的節點發現斷鏈，就用本地路由緩存中的備用路徑重新傳送數據，或者發送路由錯誤消息到源節點。此外，如果有可用的位置信息，MLAR協議采用節點位置信息的先驗知識;如果沒有，源節點以逐漸增加范圍的方式泛洪路由請求消息，直到找到目的節點或超時。這樣，計算目的節點位置的開銷就可以被忽略。

1.4多徑組播路由協議

MPoolODMRP(multipath PoolODMRP)[14]是PoolODMRP[15]協議的多徑擴展協議。MPoolODMRP協議將多樣性編碼(diversity coding)[16]和多徑技術相結合可以平衡負載，同時當某條路徑失敗時，多樣性編碼技術可以提供一定的容錯能力。MPoolODMRP協議由三部分組成，即轉發網的建立#65380;數據包的傳遞及本地路由的維護。當源節點有數據包要發送但路由不可知時，就全網發送join query消息，join query在網中的傳播方式與ODMRP[17]一致。收到join query的成員節點采用路徑選擇策略選擇本身和源節點之間的路徑來回復join replay消息，建立轉發子網;然后，源節點廣播數據包d1#65380;d2及等價包c。接收到數據包或等價包的節點按包的處理策略將數據包傳遞到目的節點中。MPoolODMRP協議采用動態本地路徑維護策略。

1.5多徑安全路由協議

SecMR(secure multipath routing)[18，19]協議對于給定的最大跳數距離，能夠找到源節點到目的節點之間存在的非循環#65380;節點完全不相交的路徑集合。協議分為鄰節點認證及路由發現和維護兩個主要階段。在認證階段，通過橢圓曲線加密體系[20]為每一個Ad hoc網絡的移動節點ni分配一對公鑰(PKi ，Ski);然后節點ni的公鑰再通過certi進行認證。算法假定節點可以使用分布式的認證(CA)服務，對實現認證的具體技術不作考慮。經過一段時間，節點ni向它的下一跳鄰節點廣播有符號的消息，包括當前時間和惟一的標志，即nit(t，IDi，sigi(t，IDi)，certi) 。這樣，每個節點都會生成一個簽名并且對于其每一個鄰節點都會生成一個簽名進行認證。

1.6多徑節能路由協議

MPSR(multipath power sensitive routing)[21]是一個用源節點響應多個路由回復消息的按需源路由協議。源節點緩存多條路由并且根據網絡的特定情況轉換路由。路由函數基于權重(剩余能量)建立路由表;傳送函數基于啟發式的方法來選擇路由，啟發式方法可以減少路徑中節點的能量消耗。當源節點向某一目的節點發送數據時，它先檢查緩存中是否存在到達這一目的節點的路徑，如果沒有，就發起路徑發現過程。源節點廣播route request消息，路徑中各節點的權重(當前剩余能量)附加在其地址中并且隨節點傳遞的route request消息一起傳遞到目的節點;目的節點再將自身的地址和權重附加在route reply消息中返回源節點。任何有到目的節點路徑的中間節點也向源節點回復route reply消息。在目的節點計算出每條路徑的平均能量值。源節點選擇具有最大平均能量和最小跳數值的路徑。每個節點的路由緩存按優先隊列的方式將最有效的路由排在隊列的前面。當路徑建立起來后開始數據包的傳送過程，基于兩個策略，即最小能量策略和羅賓環策略來選擇傳送路徑。在路徑維護過程中采取的策略與DSR協議類似。

2協議比較和分析

前面按照多徑路由的分類從不同角度討論了一些典型MANET的多徑路由協議。SR－MPOLSR協議相對于單徑OLSR協議而言可以顯著地提高數據包的傳送率，特別是在負載較大時，可以減少端到端延時和丟包率。但是為了實現多重Dijkstra算法及應用源路由機制使節點的處理代價大，就需要占用更多的CPU和內存。AOMDV協議是AODV的多徑擴展。仿真試驗表明，AOMDV協議由于端到端延時較短，性能表現較AODV協議更好，但是，AOMDV協議只能找到等長的多條路徑，當網絡規模變稀疏時就不可行了。在大型網絡中，采用兩段鏈路不相交路徑增加了路由出錯信息傳送的開銷，因此AOMDV協議較適用于移動節點較為密集的小型網絡。SMR協議只提供兩條最大不相交的路徑，那么這兩條路徑并不一定是節點不相交路徑，因此協議的擴展性不好。AntHocNet協議較好地發揮了主動和被動式協議的優點，特別是在移動性較強#65380;規模較大的網絡中性能更好，并且具有較好的擴展性。但是，算法實現復雜造成的開銷較大。基于DSR的CMDSR協議，采用分層結構克服了DSR路由泛洪開銷大的缺點，實現路由開銷最小化。同時有效地處理節點數量增大和節點密度增大的問題，進一步提高了網絡的可擴展性。但其簇頭的任務相對較重，它要維護到達其他簇頭的路由，還要負責管理和協調簇內的節點，有可能成為網絡的瓶頸。 MLAR協議是LAR協議的多徑擴展，可以應用于二維#65380;特別是三維空間的網絡，如海洋傳感器網絡#65380;在城市屋頂架設的網絡及一些軍事或災難恢復的應用。

MPoolODMRP協議適用于有多媒體需求的Ad hoc網絡，如視頻會議。SecMR適用于有安全需求的網絡，可以對抗惡意節點的DoS(denial－of－service)攻擊及提供一定的容錯能力，保持網絡的可用性。MPSR協議在數據包的傳送過程中，采取最小能量和羅賓環策略使網絡負載均分，可以增強網絡的穩定性，延長網絡使用壽命。

3結束語

本文給出了移動Ad hoc網絡多徑路由的分類方法，系統地描述了當前各種典型的MANETs多徑路由協議。可以看出，使用多徑路由較大地減少了路由尋找次數，因此極大降低了路由開銷，改善了分組丟失率。但是由于備用路徑一般比主路徑長，必然在一定程度上增大了端到端傳輸時延。這就表示端到端時延與路由開銷之間需要進行一些折中考慮。

盡管MANETs多徑路由研究取得了很大進展，但還有一些問題有待于進一步研究:如何充分利用多路徑并行傳輸，提高網絡資源的利用率和信息傳輸流量;如何提高多路徑并行傳輸可靠性和可擴展性等都是亟待解決的問題。如何提供QoS保證是移動Ad hoc網絡多徑路由所面臨的挑戰和發展方向。

參考文獻:

[1]MUELLER S，TSANG R P， GHOSAL D. Multipath routing in mobile Ad hoc networks: issues and challenges[C]//Proc of Lecture Notes in Computer Science.[S.l.]:Springer Press， 2004: 209－234.

[2]ZHOU Xun，LU Yu，XI Bin.A novel routing protocol for Ad hoc sensor networks using multiple disjoint paths[C]//Proc of the 2nd International Conference on.2005:944－948.

[3]CLAUSEN T，JACQUET P， LAOUITI A， et al. Optimized link state routing protocol for mobile Ad hoc networks[C]//Proc of IEEE INMIC.Pakistan:[s.n.]，2001.

[4]JACQUET P，MUHLETHALER P，QAYYUM A. Optimized link state routing protocol.[EB/OL].(2002－06).http//:draft－ietf－manet－olsr－10.txt.

[5]JOHNSOND B， MALTZ D A. Dynamic source routing in Ad hoc wireless networks[M].New York:kluner Academic Press，1996:153－181.

[6]MARINA M，DAS S. On－demand multipath distance vector routing in Ad hoc networks[M]. Riverside: IEEE Press，2001:14－23.

[7]PERKINS C E， ROYER E M. Ad hoc on－demand distance vector routing[M]. New Orleans: IEEE Press， 1999:90－100.

[8]LEE S，GERLA M. Split multipath routing with maximally disjoint paths in Ad hoc networks[M]. Helsinki: IEEE Press， 2001:3201－3205.

[9]DUCATELLE F， CARO G D， GAMBARDELLA L M. Ant agents for hybrid multipath routing in mobile Ad hoc networks[M]. St. Moritz， Switzerland:IEEE Press， 2005:44－53.

[10]AN H Y， LUX C， PENG W. A cluster－based multipath routing for MANET[M]. Bordum:[s.n.]， 2004:405－413.

[11]NANDA S，GRAY R S. Spatial multipath location aided Ad hoc routing:Computer Communications and Networks[C]//Proc of the 13th International Conference.2004.

[12]NANDA S，GRAY R S.Multipath location aided routing in 2D and 3D[M].[S.l.]:IEEE Press， 2006:311－ 317.

[13]KO Y B，VAIDYA N H. Location－aided routing (LAR) in mobile ad hoc networks[M]. Dallas， Texas: IEEE Press，1998:66－75.

[14]CAI Shao－bin， YAO Wen－bin， YAO Nian－min， et al.MPoolODMRP: an extended PoolODMRP based on multi－path policy[C]//Proc of IMSCCS.2006:75－80.

[15]CAI S，YANG X. The performance of PoolODMRP[M]. Belfast， Northern Ireland: IEEE Press， 2003:90－101.

[16]AYANOGLU E， GITLIN R CI， MAZO J. Diversity coding for transparent self－healing and fault－tolerant communication networks[J]. IEEE Trans on Communications， 1993，41(11):1677－1686.

[17]LEE S，SU W， GERLA M. On－demand multicast routing protocol (ODMRP) for Ad hoc networks[K].[S.l.]:IETF，2000.

[18]KOTZANIKOLAOU P，MAVROPODI R，DOULIGERIS C. Secure multi－path routing for mobile Ad hoc networks[M]. St. Moritz， Switzerland:IEEE Press， 2005:89－96.

[19]MAVROPODI R，DOULIGERIS C. Multipath routing protocols for mobile Ad hoc networks: security issues and performance evaluation[M].[S.l.]:Springer－Verlag， 2005:165－176.

[20]KOBLITZ N. Elliptic curve cryptosystems[J]. Math Comput，1997， 48:203－209.

[21]SUBRAMANIAN A P， ANTO A J， VASUDEVAN J， et al. Multipath power sensitive routing protocol for mobile Ad hoc networks[M]. Italy: Springer Press， 2004:171－183.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”