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

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

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

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

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

   從圖5中可以看到，由于MRABM和本文算法均采用目的節點更新mesh結構的機制,所以在節點移動造成網絡拓撲結構改變時，不會存在路由修護和路由重建過程，控制開銷將保持平穩,不會急劇增長。然而MRABM的路徑建立采用基于目的節點的方法,且定期進行路徑更新而不是采用事件驅動，將產生大量的控制開銷，本文算法基于源節點建立路徑節約了大量的控制開銷。
   如圖6所示， MRABM和本文算法的丟包率都較小，這是因為兩種算法都是當一條鏈路斷開后，節點將立即為數據分組選擇另一條路徑傳送數據，幾乎不會發生丟包現象，且它們能實時維護源節點到目的節點的最優路徑和其余多條路徑，所以大流量傳輸時，這兩種算法均能有效平衡網絡負載，減少網絡擁塞，降低丟包率。而AOMDV采用的固定多徑傳輸則容易造成網絡擁塞。
   由圖7可知，MRABM和本文算法的端到端時延都較小，這是因為當節點移動造成鏈路斷開時，這兩種算法都不需要等待路徑修復或路由重建過程，而AOMDV在所有路徑失效后，將由源節點發起路由重建，所以端到端時延較大。
   針對無線mesh網絡中目前存在的幾種多徑路由協議的局限性，提出了一種基于源節點建立和目的節點維護mesh結構的多徑路由協議。此協議中,在建立路由時,每個中間節點只需要轉發一次路由請求包,以后的路由完善、路由更新和路由維護均由目的節點完成,降低了路由維護的時間。路徑的最佳性和跟隨拓撲變化的實時性,提高了數據包的傳輸率,降低了網絡的平均延時。另外,基于源節點建立的路徑,有效地控制了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網絡多徑路由協議的研究與設計. 計算機工程與設計, 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).