摘 要:在移動Ad hoc網中，多徑路由因其能夠更好地支持QoS而得到廣泛的研究#65377;從減少端到端延時#65380;降低能耗#65380;提高可靠度#65380;有效利用鏈路帶寬四個方面介紹多徑路由在Ad hoc網中的應用#65377;但是，現(xiàn)在大多數(shù)多徑路由協(xié)議只考慮到網絡層，而沒有考慮到其它層和多徑路由的相互關系，基于此，分析多徑路由在鏈路層和傳輸層所面臨的問題，并且提出解決這些問題的進一步的研究方法#65377;

關鍵詞:移動自組網絡;多徑路由;網絡性能

中圖分類號:TP393.04文獻標識碼:A

1 引 言

移動Ad hoc網絡是一種自治的無線多跳網絡，它沒有固定的基礎設施#65377;所有節(jié)點可以自由移動，既充當主機又兼?zhèn)渎酚善鞯墓δ?，以任意方式動態(tài)地保持與其它節(jié)點的聯(lián)系#65377;移動自組網因其建立方便#65380;快捷，不受網絡基礎設施制約而被廣泛應用于軍事領域#65380;災難救治#65380;共享信息的商業(yè)會議#65380;緊急通信等需要建立臨時通信網絡的環(huán)境中#65377;

由于移動Ad hoc網絡具有拓撲結構動態(tài)變化#65380;多跳無線通信#65380;鏈路帶寬有限#65380;節(jié)點的能量有限等特點，給Ad hoc網絡的路由研究帶來困難#65377;本文分析和討論了多徑路由在Ad hoc網絡中的應用和所面臨的問題#65377;

2 多徑路由的分類

2.1 根據(jù)使用路徑的方式劃分路由

根據(jù)使用路徑的方式不同多徑路由可以分為備用路由和多路徑路由#65377;

2.1.1 備用路由

備用路由是指在每個源節(jié)點和目的節(jié)點之間有一組路徑，它們由一條主路徑和多條備用路徑組成#65377;在建立好路由后，使用主路徑傳輸數(shù)據(jù)，當主路徑發(fā)生中斷時快速地切換到備用路徑上#65377;BSR#65380;Aodv-br#65380;AOMDV等協(xié)議就是采用這種方法#65377;

2.1.2 多路徑路由

多路徑路由(亦稱多徑路由，在這里僅為和備用路由作概念上的區(qū)分)是指源節(jié)點同時使用多條路徑傳輸數(shù)據(jù)#65377;這種方式因能在更短時間內把數(shù)據(jù)分組傳輸完，減少網絡的端到端延時而得到比較多的應用，如MSR#65380;SMR#65380;AODVM等協(xié)議#65377;

2.2 根據(jù)多路徑之間的相關性劃分路由

根據(jù)多路徑之間的相關性，多徑路由可以分為節(jié)點不相交路由#65380;鏈路不相交路由#65380;相交路由#65377;

節(jié)點不相交路由又稱完全不相交路由，是指各條路徑除了共享源節(jié)點和目的節(jié)點之外，相互之間無其它共享節(jié)點#65377;鏈路不相交多徑路由是指各條路徑相互之間沒有共享鏈路，但可有共享節(jié)點#65377;相交路由是指有共同的節(jié)點和鏈路#65377;由于不相交路由能夠提供比相交路由更高的容錯度和路徑之間的低干擾性，使之在多徑路由中應用廣泛#65377;比較有代表性的節(jié)點不相交路由有AODVM，SMR，鏈路不相交路由有AOMDV等#65377;

計算技術與自動化2007年6月第26卷第2期譚長庚等:多徑路由在移動Ad hoc網絡中的應用研究3 多徑路由在Ad hoc網絡中的應用

3.1 縮短端到端延時

多徑路由在一次路由發(fā)現(xiàn)過程中找到多條路徑，減少路由發(fā)現(xiàn)次數(shù)，提高了各個連接的投遞率，降低了控制開銷與端到端延時#65377;MSR^[1]采用帶權重的循環(huán)調度算法在多路徑上進行負載分配，在這種機制中，一條路徑上的延遲RTT(round-trip time)反應當前路徑的擁塞狀況，源節(jié)點根據(jù)每條路徑的RTT值來分配負載，RTT值越小，相應的路徑分配的負載就越多#65377;為了避免一條路徑上過量的負載分配而使多路徑退化成單路徑，數(shù)據(jù)分組會在不同的路徑之間進行切換#65377;仿真結果顯示，在輕載的網絡中MSR在多數(shù)連接上的平均延時低于DSR#65377;Ad hoc網絡按需多徑距離矢量AOMDV^[2]路由協(xié)議是在AODV 路由協(xié)議基礎上擴展的，該協(xié)議計算多條開環(huán)#65380;鏈路不相交路徑，提供有效的容錯能力，快速#65380;有效地恢復動態(tài)網絡中的中斷路由#65377;為了排除路徑任何可能的閉環(huán)，該協(xié)議采用廣告跳數(shù)(advertised hopcount)這個新概念來維護多條開環(huán)路徑#65377;同時AOMDV協(xié)議在一次路由發(fā)現(xiàn)過程中運用泛洪的一種特定屬性來確保所計算出來的多條路徑鏈路不相交#65377;仿真結果表明AOMDV能夠顯著改善端到端時延，但協(xié)議沒有考慮備用路徑的維護，節(jié)點的移動在導致主路徑中斷的同時也可能會導致備用路徑失效，使用陳舊的備用路由可能導致更多的包丟失#65377;對此，文獻[3]提出的路由協(xié)議MP-AOMDV，添加了對備用路徑的維護，由源節(jié)點周期性地在每條備用路徑上發(fā)送一個heartbeat的更新信息包，路徑上的每個節(jié)點都會將本節(jié)點的MP(mobility prediction)度量值添加到信息包中，這里的MP是用來估量一個節(jié)點從上游鄰居節(jié)點收包的信號強度#65377;用一條路徑上所有節(jié)點的MP值之和作為判斷路徑穩(wěn)定度的標準#65377;當主路徑失效后，選擇最穩(wěn)定的備用路徑，如果所有的備用路徑都是失效的，則重新建路#65377;仿真結果顯示，節(jié)點不相交MP-AOMDV協(xié)議與AOMDV協(xié)議相比，端到端延時要減少將近75%#65377;

3.2 降低能耗

由于Ad hoc網絡節(jié)點由電池供電，一旦能量耗盡，該節(jié)點就不能繼續(xù)使用#65377;所以能量保護在Ad hoc網絡中具有非常重要的意義#65377;文獻[4]提出了一種MEER協(xié)議，在傳輸數(shù)據(jù)時，將負載分配到多條路徑上，以平衡網絡能量消耗，延長網絡壽命#65377;使用多路徑一是為了同時分配負載到不同的路徑上，二是為了避免節(jié)點過度使用;另一方面，使用多徑路由能滿足無線網絡的可靠性，當某些路徑失效后源節(jié)點到目的節(jié)點之間的數(shù)據(jù)傳輸仍然可通過網絡中其它路由完成#65377;MEER將多路徑上的負載分配和能量效率結合起來，提出了基于梯度投影算法來分配負載，每個節(jié)點周期性地更新它的能量消耗率，同時源節(jié)點周期性地在收集到的多條路徑上發(fā)送一個探測包，路徑上的節(jié)點收到探測包后會發(fā)送一個包含有本節(jié)點當前能量消耗率的回復包給源節(jié)點#65377;源節(jié)點收集到路由上所有節(jié)點的能量消耗率，然后采用梯度投影算法在多條路徑上調整#65380;分配負載#65377;仿真結果表明，MEER能有效延長網絡壽命和減少網絡能量消耗#65377;

文獻[5]提出了一種局部路徑增援機制，這種機制用來測量節(jié)點短時間內的負載，并從多條路徑中選擇出一條主路徑和一組備用路徑#65377;在源節(jié)點使用主路徑傳輸數(shù)據(jù)時，周期性地在備用路徑上傳輸keep-alive的數(shù)據(jù)包，這種連續(xù)的keep-alive數(shù)據(jù)包會在主路徑失效時，源節(jié)點能迅速地切換到一條備用路徑上#65377;其中，多徑路由機制采用辮子多路徑算法，辮子多徑路由沒有節(jié)點不相交路由那樣要求嚴格，一個辮子中的多路徑僅需要滿足部分路徑是不相交#65377;通過這種方法找到的路徑通常比節(jié)點不相交路徑短，因此消耗的能源較少#65377;仿真結果顯示采用辮子多路徑算法的協(xié)議要比節(jié)點不相交路由節(jié)能33%#65377;

3.3 提高通信可靠度

Ad hoc網絡是由一組易受攻擊的節(jié)點組成的，多路徑是提高傳輸信息的可靠性的方式之一#65377;可以通過找源-目的節(jié)點對之間的多條不相交路由來提供冗余，文獻[6]提出了一種基于簇的多徑路由協(xié)議CMDSR，該協(xié)議利用分簇的層次結構來有效搜索多路徑，利用多路徑并行傳輸數(shù)據(jù)#65377;路徑的端到端可靠性定義為該路徑上所有鏈路的有效性之和#65377;在路由發(fā)現(xiàn)過程中，選擇滿足可靠性最低要求的路徑來建立不相交路由#65377;成功地找到路由后，源節(jié)點選擇其中的一組路由發(fā)送數(shù)據(jù)#65377;但是由于Ad hoc網絡拓撲動態(tài)變化，這些路徑可能會在任何時候斷裂，當所有的路徑斷裂后源節(jié)點不再傳輸數(shù)據(jù)#65377;為了維護一個可靠的#65380;無縫的網絡連接，當主路徑的端到端可靠性低于最低值時，源節(jié)點會發(fā)送RCHK包檢測路由緩沖中的路由狀態(tài)，并等待一個時間段，在收到回復包RCHK-RP后源節(jié)點會重新計算這些路徑的端到端可靠性，更新路由緩存并選擇滿足可靠性最低要求的路徑傳輸數(shù)據(jù)#65377;仿真結果顯示CMDSR的分組成功遞交率都要比MSR高#65377;

節(jié)點不相交路由的數(shù)目與網絡節(jié)點密度有關，而且隨著源節(jié)點和目的節(jié)點的距離增大，難免會發(fā)生瓶頸問題，因此要找到不相交路由的可能性比較小#65377;文獻[7]提出了一種利用可靠節(jié)點構建可靠路徑的機制，在這種機制中，一條可靠路徑由幾段組成，每段由可靠節(jié)點組成或是由多條節(jié)點不相交路徑組成#65377;通過一種配置策略來確定可靠節(jié)點的位置和運動軌跡，即使在只有很少的可靠節(jié)點，建立一條可靠路徑的概率仍很大，仿真結果表明網絡即使只提供少量的可靠節(jié)點也能有效地在任意源—目的節(jié)點對之間找到可靠路徑#65377;

3.4 減少鏈路帶寬開銷

由于無線信道本身的物理特性，它所能提供的網絡帶寬相對有線信道要低很多#65377;文獻[8]提出了一種帶寬預留的多徑路由協(xié)議，用一種基于ticket的方法來尋找多路徑，為了減少因泛洪導致的網絡風暴，源節(jié)點只發(fā)送一定數(shù)量的探索包ticket，每個探索包負責找一條路由#65377;每個ticket由ticket ID，帶寬要求來標識，源節(jié)點啟動路由發(fā)現(xiàn)過程后，ticket將沿著滿足帶寬要求的鏈路轉發(fā)#65377;當一個中間節(jié)點收到ticket包后，首先檢查它的鏈路中是否有滿足帶寬要求的，如果有這樣的鏈路，就選擇其中一條鏈路轉發(fā)該包#65377;如果沒有符合帶寬要求的鏈路，就選擇多條鏈路之和滿足帶寬要求的鏈路#65377;也就是說，將帶寬要求分為子帶寬要求，而原始的ticket包也被劃分為sub-ticket包，每個sub-ticket包會沿鏈路之一轉發(fā)#65377;這樣，又由每個sub-ticket負責找到滿足子帶寬要求的路由#65377;如果前兩種方法都沒有找到符合帶寬要求的鏈路，該中間節(jié)點會丟棄該sub-ticket#65377;目的節(jié)點可能收到多個ticket包或由多個sub-ticket組成的ticket包，單個的ticket包代表單路徑，由一組sub-ticket組成的ticket代表著多路徑#65377;

4 多徑路由在Ad hoc網絡中面臨的問題

在有線網中，多徑路由能增加網絡吞吐量#65380;提供更好的負載均衡#65377;但是這些優(yōu)點在移動Ad hoc網中并不明顯，因為數(shù)據(jù)流在不同的路徑上傳輸時，各個路徑之間會因為電磁波的廣播特性互相干擾#65377;另外，如果網絡拓撲變化太快，有效地搜尋多條路徑并不容易#65377;本節(jié)從鏈路層和傳輸層分析了多徑路由在Ad hoc網絡中應用時所面臨的問題#65377;

4.1 多徑路由在鏈路層存在的問題

移動Ad hoc網絡中的節(jié)點在無線媒介上進行通信，如果使用共享信道，那么相鄰節(jié)點必須競爭信道#65377;當發(fā)送節(jié)點使用信道發(fā)送分組時候，相鄰節(jié)點接受到該分組而無法接受其它源節(jié)點的發(fā)送#65377;而且根據(jù)鏈路層協(xié)議，相鄰節(jié)點可能推遲發(fā)送，直到信道空閑為止#65377;即使采用多信道，相鄰節(jié)點的發(fā)送質量也可能由于干擾而下降，也就是說相互處在對方傳輸覆蓋范圍內的節(jié)點處在相同的碰撞區(qū)域內#65377;

在同時采用多條路徑發(fā)送數(shù)據(jù)，即使多條路徑節(jié)點不相交，仍有某些節(jié)點處在相同的碰撞區(qū)域，那么多條路徑上的發(fā)送仍然可能相互干擾#65377;在多信道網絡中，不同路徑經過相同的中間節(jié)點時就會發(fā)生耦合，而單信道網絡中耦合問題更嚴重，只要一條路徑經過另一條路徑的無線覆蓋區(qū)域就會產生耦合#65377;節(jié)點不相交性能夠確保路由中繼的獨立性，但是卻不能保證發(fā)送的獨立性#65377;因此，在選擇多條路由的時候，選擇的路徑盡可能地獨立，確保路徑間的耦合最低#65377;

4.2 多徑路由在傳輸層存在的問題

TCP協(xié)議是一個根據(jù)有效網絡帶寬控制其承載載荷的自適應傳輸協(xié)議#65377;在固定網中，擁塞定義為由瓶頸路由中緩沖器溢出造成的分組丟失#65377;在Ad hoc網絡中運行TCP機制時，緩存器溢出或者隱含終端造成的鏈路層競爭都可能造成分組的丟失，這些分組丟失直接影響TCP 窗口的自適應#65377; 在多徑路由中，同時使用多條路徑傳輸數(shù)據(jù)容易導致分組的亂序交付，此時TCP分組亂序交付就會觸發(fā)ACK拷貝，而ACK拷貝又反過來觸發(fā)TCP擁塞控制機制，這樣TCP必須減少窗口#65377;而且多徑路由協(xié)議下平均往返時間RTT估計不準確，即多條路徑上的平均RTT可能比最長路徑上的RTT小很多，因此，TCP發(fā)送方可能沿著最長路徑傳遞分組，這又會導致分組的重傳率增加，從而降低TCP性能#65377;

文獻[9]針對多路徑對傳輸層帶來的影響在測試床上對TCP協(xié)議在MSR和DSR上的性能做了比較，試驗結果表明由于多徑路由中包的亂序導致更多重傳使得TCP性能下降#65377;文獻[10]通過比較在SMR和DSR上各自運行TCP協(xié)議后的吞吐量，仿真結果表明當TCP同時使用多條路徑時，其性能總是比只使用單條路徑時的性能差#65377;此外，從分組重傳率的角度來考慮，由于SMR協(xié)議上的TCP分組重傳率高于DSR協(xié)議上的TCP分組重傳率，使得TCP擁塞窗口不能變得足夠大而達到高吞吐量#65377;

5 結束語

在Ad hoc網絡中，由于各節(jié)點都具有路由功能，因而一個源-目的節(jié)點對之間通常有多條路徑#65377;多徑路由所具有的穩(wěn)定性和提高網絡資源利用率的特點，使得多徑路由更適合QoS路由的要求#65377;本文從端到端延時#65380;能耗#65380;可靠度#65380;鏈路帶寬四個方面介紹了多徑路由在Ad hoc網絡中的應用#65377;但是，現(xiàn)在大多數(shù)多徑路由協(xié)議只考慮了網絡層，而沒有考慮其它層和多徑路由的相互關系#65377;本文分析了多徑路由在鏈路層產生的耦合問題;同時指出，在運行TCP協(xié)議時，分組的亂序交付會增加分組的重傳率，從而導致TCP性能下降#65377;多徑路由協(xié)議的研究將主要集中在以下幾個方面:構建代價最小的低耦合多徑路由;綜合考慮網絡層和傳輸層的信息共享和相互影響，實現(xiàn)跨層設計;在使用多條路徑同時傳輸分組時，盡量減少分組的亂序交付，建立合理的負載分配機制來實現(xiàn)網絡的負載均衡，以更好地綜合利用網絡資源和提高網絡的整體性能#65377;

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