近年來，無線mesh網絡（WMN）由于其靈活性和實用性受到越來越多的關注與應用。WMN是一種高容量、高速率的分布式網絡。它不同于任何傳統(tǒng)的有線或無線網絡，正是網絡的特殊性使得傳統(tǒng)網絡的路由技術無法直接應用于WMN，使WMN路由算法的探討成為這個領域的研究熱點。而多徑路由因其有效利用帶寬、減小擁塞和增加傳輸可靠性、實現負載和能耗均衡等一系列優(yōu)點，得到了廣泛的重視。
    目前存在的多徑路由協(xié)議基本上可以分為兩類：一類是表驅動協(xié)議（如QOLSR[1]）。在該類協(xié)議中，各節(jié)點通過周期性的廣播路由信息分組，交換路由信息，主動發(fā)現路由，同時，節(jié)點必須維護去往全網所有節(jié)點的路由；另一類是按需路由協(xié)議(如AOMDV[2]、MSR[3]和MRABM[4])，這類協(xié)議僅在源節(jié)點要發(fā)送分組但沒有去往目的節(jié)點的路徑時，才“按需”進行路由發(fā)現。這些路由協(xié)議都在不同程度上提高了網絡的路由性能，但仍存在一定不足。除MRABM以外，其余幾種路由協(xié)議均是基于源節(jié)點或中間節(jié)點維護的路由協(xié)議，當所有路徑都失效時，再重新發(fā)起路由建立過程。這樣，當網絡拓撲變化較快或網絡負載較高時，將面臨嚴重的丟包問題，最重要的是不能實時維護到目的節(jié)點的最優(yōu)路徑。而MRABM采用的基于目的節(jié)點維護mesh結構的方法，則能很好地解決實時維護最優(yōu)路徑這個問題。但由于該算法的路徑建立也采用基于目的節(jié)點的方法，將產生較大的控制開銷。本文結合以上兩點，提出一種基于源節(jié)點建立、目的節(jié)點維護mesh結構的路由協(xié)議。該協(xié)議既能為源節(jié)點建立到目的節(jié)點的實時最優(yōu)路徑，有效利用網絡資源，減少網絡擁塞，降低丟包率，又能盡量減少控制開銷。
1 mesh網絡模型
    由多個節(jié)點互聯(lián)而成的mesh結構中，每個節(jié)點既是主機，也是路由器。當源節(jié)點與目的節(jié)點不能直接通信時，就需要其他中間節(jié)點通過存儲轉發(fā)幫助完成通信，這樣便構成了多跳網絡。而mesh結構中兩個節(jié)點之間具有不只一條路徑的特性，使得網絡中任何一條鏈路的中斷或任何一個節(jié)點的離開均不會導致通信的中斷。mesh結構示意圖如圖1所示。

    鏈路AC斷開后，上游節(jié)點A由于收不到下游節(jié)點C的聯(lián)絡信息便可知道鏈路AC已中斷，這條路由已不可用，從而不再把數據發(fā)給節(jié)點C，轉而把數據發(fā)給它的另一個相鄰節(jié)點B，節(jié)點B將沿它到節(jié)點D的最優(yōu)路徑把數據發(fā)送至目的節(jié)點D?？梢?，鏈路AC的中斷不會導致通信的中斷。
2 多徑路由協(xié)議
    在無線mesh網絡中，數據從需要發(fā)送到發(fā)送完畢，主要經歷mesh的建立、mesh的完善、mesh的維護、數據發(fā)送和mesh結構的消失幾個階段。
2.1 mesh的建立
    當源節(jié)點要向目的節(jié)點發(fā)送數據時，首先檢查自己的路由緩沖器，如果有到達目的節(jié)點的路徑，就開始發(fā)送數據；若沒有，就通過廣播路由請求分組RREQ（route request）發(fā)起路由發(fā)現過程，RREQ報文格式如圖2所示。

    接收到路由請求分組的中間節(jié)點，檢查它是否有到達目的節(jié)點的路徑。若有，就沿反向路徑發(fā)送路由回復分組RREP（route reply），并將RREQ沿其最短路徑傳送至目的節(jié)點；若無，則判斷是否第一次收到該RREQ分組，如果是，就將該節(jié)點添加到路由信息表中，繼續(xù)廣播路由請求分組，否則就丟棄該分組。直到RREQ分組到達的節(jié)點有到目的節(jié)點的路徑或RREQ分組到達目的節(jié)點為止，然后該節(jié)點或目的節(jié)點返回路由回復分組RREP，并將RREQ沿其最優(yōu)路徑傳送至目的節(jié)點（若已是目的節(jié)點則不需要傳送）。RREP格式如圖3所示。
    源節(jié)點收到RREP后，開始傳送數據。

2.2 mesh的完善
    mesh初步結構建立以后，源節(jié)點便具有了至少一條通往目的節(jié)點的路徑。源節(jié)點沿已有的路徑向目的節(jié)點發(fā)送數據包。同時，目的節(jié)點接收到RREQ后，將向周圍節(jié)點廣播一種叫做RRTB的消息分組，RRTB消息分組的內容包括：
    (1)RRTB:控制分組的類型;
    (2)源節(jié)點id:發(fā)送RREQ消息的節(jié)點標示;
    (3)目的節(jié)點id:發(fā)送該RRTB消息的節(jié)點標示;
　 (4)序列號:該RRTB分組的序列號;
　 (5)距離目的節(jié)點的跳數:該節(jié)點距離目的節(jié)點的跳數;
　 (6)父節(jié)點id:發(fā)送該RRTB消息分組到該節(jié)點的節(jié)點標示。
　 目的節(jié)點為RRTB消息產生的節(jié)點，所以其距離目的節(jié)點的跳數為0，其父節(jié)點id為目的節(jié)點標示。序列號由目的節(jié)點更新，采用序列號逐漸增大的方式。
　中間節(jié)點收到RRTB消息分組后，檢查是否第一次收到該消息分組，若是則修改路由表：在路由表中增加一個路由條目；若不是則丟棄。該路由條目的源節(jié)點為發(fā)送RREQ的節(jié)點,目的節(jié)點為發(fā)送RRTB的節(jié)點，并建立與鄰居節(jié)點的關系。中間節(jié)點建立路由表的內容有：
　(1)源節(jié)點id:發(fā)送RREQ消息的節(jié)點標示;
　(2)目的節(jié)點id:發(fā)送RRTB消息的節(jié)點標示;
　(3)鄰居節(jié)點id:發(fā)送該RRTB消息到本節(jié)點的節(jié)點標示;
　(4)距離目的節(jié)點的跳數:鄰居節(jié)點距離目的節(jié)點的跳數;
　(5)鄰居節(jié)點的父節(jié)點id:發(fā)送該RRTB消息分組到鄰居節(jié)點的節(jié)點標示;
　(6)收到時間:本節(jié)點收到該RRTB消息分組的時間。
　中間節(jié)點選擇到目的節(jié)點最少跳數的鄰居節(jié)點為最優(yōu)路徑,且作為本節(jié)點的RRTB消息分組的內容,向周圍節(jié)點廣播。以此類推，直到源節(jié)點收到鄰居節(jié)點發(fā)送的RRTB消息，建立源節(jié)點到鄰居節(jié)點的路由表,而不再向周圍節(jié)點廣播自己的RRTB消息分組。這樣,源節(jié)點和中間節(jié)點都建立了到目的節(jié)點的最優(yōu)路徑和其他路徑，mesh結構得到了進一步完善。
   中間節(jié)點在收到第一個RTBB消息后，延時一段時間再向周圍節(jié)點廣播自己的RRTB消息分組，以獲得足夠的路由信息來選出最優(yōu)路徑。為了防止路由表膨脹，節(jié)點僅記錄符合一定跳數條件的RRTB消息攜帶的路徑信息，否則丟棄該RRTB消息。
2.3 mesh的維護
   mesh結構的更新采用事件驅動的方式。在數據傳輸過程中，如果某個中間節(jié)點沒有到達目的節(jié)點的路由時，就廣播路由錯誤分組RERR（route error），RERR僅廣播一跳，鄰居節(jié)點收到該分組后，將從路由表中刪除該節(jié)點，并沿最優(yōu)路徑首先向目的節(jié)點傳輸該消息分組，目的節(jié)點收到該分組后，將啟動路由更新，向周圍節(jié)點廣播新的RRTB消息分組，中間節(jié)點和源節(jié)點將根據新收到的RRTB消息分組更新自己的路由表，建立新的最優(yōu)路徑和其余多條路徑。
　可見,這樣的路由維護方式不需要源節(jié)點發(fā)起RREQ的重建過程，只需要目的節(jié)點發(fā)起RRTB消息分組，比一般的路由重建時間少，且采用事件驅動更新方式，更新次數少，直接進行路由更新避免了路由陳舊問題。
2.4 數據傳送
    源節(jié)點收到周圍節(jié)點發(fā)送來的RRTB消息,建立到目的節(jié)點的完善的路由表。低負載時,源節(jié)點可以選擇一條到目的節(jié)點的最優(yōu)路徑傳送數據,也可以選擇多條路徑傳送數據。高負載時,源節(jié)點可以選擇多條路徑甚至所有的路徑同時傳送數據。各路徑可以等概率傳輸,也可以按需傳輸。數據分配采用每包分配粒度。
　 若某個中間節(jié)點與其所有下游節(jié)點的鏈路都斷開,則該節(jié)點將向上游節(jié)點回傳數據分組,上游節(jié)點收到回傳的數據分組,就沿其他路徑傳送數據,并刪除到該節(jié)點的路由,從而盡量減少數據分組的丟失。
　若節(jié)點移動造成網絡分割,而數據包在網絡分割點上時,則該節(jié)點首先緩存該數據分組。若超過mesh結構的更新時間仍沒有收到目的節(jié)點的更新分組,便丟棄該數據分組。
2.5 mesh結構的消失
   當源節(jié)點向目的節(jié)點的傳送完數據以后,源節(jié)點沿最短路徑向目的節(jié)點發(fā)送stop消息分組,目的節(jié)點收到該stop消息分組后,將停止發(fā)送mesh更新消息分組。stop消息格式如圖4所示。

　中間節(jié)點若在超時范圍內仍沒有收到目的節(jié)點的更新消息分組，則自動從路由表中刪除本項路由信息。
3 實驗仿真和評價
　本文采用OPNET進行仿真實驗，比較本文提出的協(xié)議和MRABM、AOMDV路由協(xié)議的性能。仿真條件為40個節(jié)點在1 000 m×1 000 m的正方形區(qū)域內隨機移動，移動符合waypoint模型。設節(jié)點的最大移動速度分別為0 m/s、2 m/s、4 m/s、6 m/s、8 m/s和10 m/s,停留時間為0 s。節(jié)點通信距離為200 m，鏈路帶寬為2 Mb/s，MAC層采用IEEE802.11介質訪問控制，傳輸層采用UDP協(xié)議，應用層采用恒定比特率數據流，數據流為10，分組長度為512 B，產生時間間隔為0.1 s，仿真時間為1 000 s。
   仿真關注以下性能參數：
   (1)路由開銷：路由協(xié)議建立路由和維護路由，所有節(jié)點發(fā)送的路由包。
   (2)端到端延時：從源節(jié)點的網絡層發(fā)送數據包，到目的節(jié)點網絡層收到該數據包的時間平均值。
   (3)丟包率：丟失的數據包占所發(fā)送數據包的比率。
　仿真結果如圖5、圖6、圖7所示。

   從圖5中可以看到，由于MRABM和本文算法均采用目的節(jié)點更新mesh結構的機制,所以在節(jié)點移動造成網絡拓撲結構改變時，不會存在路由修護和路由重建過程，控制開銷將保持平穩(wěn),不會急劇增長。然而MRABM的路徑建立采用基于目的節(jié)點的方法,且定期進行路徑更新而不是采用事件驅動，將產生大量的控制開銷，本文算法基于源節(jié)點建立路徑節(jié)約了大量的控制開銷。
   如圖6所示， MRABM和本文算法的丟包率都較小，這是因為兩種算法都是當一條鏈路斷開后，節(jié)點將立即為數據分組選擇另一條路徑傳送數據，幾乎不會發(fā)生丟包現象，且它們能實時維護源節(jié)點到目的節(jié)點的最優(yōu)路徑和其余多條路徑，所以大流量傳輸時，這兩種算法均能有效平衡網絡負載，減少網絡擁塞，降低丟包率。而AOMDV采用的固定多徑傳輸則容易造成網絡擁塞。
   由圖7可知，MRABM和本文算法的端到端時延都較小，這是因為當節(jié)點移動造成鏈路斷開時，這兩種算法都不需要等待路徑修復或路由重建過程，而AOMDV在所有路徑失效后，將由源節(jié)點發(fā)起路由重建，所以端到端時延較大。
   針對無線mesh網絡中目前存在的幾種多徑路由協(xié)議的局限性，提出了一種基于源節(jié)點建立和目的節(jié)點維護mesh結構的多徑路由協(xié)議。此協(xié)議中,在建立路由時,每個中間節(jié)點只需要轉發(fā)一次路由請求包,以后的路由完善、路由更新和路由維護均由目的節(jié)點完成,降低了路由維護的時間。路徑的最佳性和跟隨拓撲變化的實時性,提高了數據包的傳輸率,降低了網絡的平均延時。另外,基于源節(jié)點建立的路徑,有效地控制了RREQ在全網的泛洪,減少了控制開銷,更合理地利用了網絡資源。
   本文提出的算法雖在已有算法的基礎上有所改進,但仍需要進一步完善和深入。
參考文獻
[1] BADIS H, AGHA K A. QOLSR multi-path routing for mobile Ad Hoc network based on multiple metrics: Bandwidth and delay.Vehicular Techonology Conference,2004.VTC 2004-Spring.2004 IEEE 59th.
[2] 劉經緯,雷濤,徐海川,等.Ad-hoc網絡多徑路由協(xié)議的研究與設計. 計算機工程與設計, 2007，28(17):4145-
4148.
[3]  WANG L. Multipath source routing in wireless Ad Hoc networks[A]. Canadian Conf Elec Comp Eng. Vol 1[C]. 2000:479-83.
[4] 劉麗云,陳曙,朱偉.一種新的基于mesh結構的多徑路由算法.計算機工程與應用,2007,43(3).