移動Ａｄ ｈｏｃ網(wǎng)絡(luò)多徑路由協(xié)議

摘要:給出移動Ad hoc網(wǎng)絡(luò)多徑路由的分類方法，系統(tǒng)地描述了當(dāng)前各種典型的MANETs多徑路由協(xié)議，并比較和分析了這些協(xié)議的特點及適用情況。最后結(jié)合該領(lǐng)域當(dāng)前的研究現(xiàn)狀，指出多徑路由協(xié)議存在的問題和未來的研究重點。

關(guān)鍵詞:移動自組織網(wǎng)絡(luò); 多徑路由; 路由協(xié)議

中圖分類號:TP393文獻標(biāo)志碼:A

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

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

1多徑路由協(xié)議分類及協(xié)議描述

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

1.1平面式多徑路由協(xié)議

1.1.1主動式(表驅(qū)動)多徑路由協(xié)議

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

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

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

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

1.1.3混合多徑路由協(xié)議

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

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

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

1.2分簇式多徑路由協(xié)議

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

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

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

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

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

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

1.4多徑組播路由協(xié)議

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

1.5多徑安全路由協(xié)議

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

1.6多徑節(jié)能路由協(xié)議

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

2協(xié)議比較和分析

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

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

3結(jié)束語

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

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

參考文獻:

[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－h(huán)ealing 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.

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