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

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

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

　中間節(jié)點若在超時范圍內(nèi)仍沒有收到目的節(jié)點的更新消息分組，則自動從路由表中刪除本項路由信息。
3 實驗仿真和評價
　本文采用OPNET進行仿真實驗，比較本文提出的協(xié)議和MRABM、AOMDV路由協(xié)議的性能。仿真條件為40個節(jié)點在1 000 m×1 000 m的正方形區(qū)域內(nèi)隨機移動，移動符合waypoint模型。設(shè)節(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介質(zhì)訪問控制，傳輸層采用UDP協(xié)議，應用層采用恒定比特率數(shù)據(jù)流，數(shù)據(jù)流為10，分組長度為512 B，產(chǎn)生時間間隔為0.1 s，仿真時間為1 000 s。
   仿真關(guān)注以下性能參數(shù)：
   (1)路由開銷：路由協(xié)議建立路由和維護路由，所有節(jié)點發(fā)送的路由包。
   (2)端到端延時：從源節(jié)點的網(wǎng)絡層發(fā)送數(shù)據(jù)包，到目的節(jié)點網(wǎng)絡層收到該數(shù)據(jù)包的時間平均值。
   (3)丟包率：丟失的數(shù)據(jù)包占所發(fā)送數(shù)據(jù)包的比率。
　仿真結(jié)果如圖5、圖6、圖7所示。

   從圖5中可以看到，由于MRABM和本文算法均采用目的節(jié)點更新mesh結(jié)構(gòu)的機制,所以在節(jié)點移動造成網(wǎng)絡拓撲結(jié)構(gòu)改變時，不會存在路由修護和路由重建過程，控制開銷將保持平穩(wěn),不會急劇增長。然而MRABM的路徑建立采用基于目的節(jié)點的方法,且定期進行路徑更新而不是采用事件驅(qū)動，將產(chǎn)生大量的控制開銷，本文算法基于源節(jié)點建立路徑節(jié)約了大量的控制開銷。
   如圖6所示， MRABM和本文算法的丟包率都較小，這是因為兩種算法都是當一條鏈路斷開后，節(jié)點將立即為數(shù)據(jù)分組選擇另一條路徑傳送數(shù)據(jù)，幾乎不會發(fā)生丟包現(xiàn)象，且它們能實時維護源節(jié)點到目的節(jié)點的最優(yōu)路徑和其余多條路徑，所以大流量傳輸時，這兩種算法均能有效平衡網(wǎng)絡負載，減少網(wǎng)絡擁塞，降低丟包率。而AOMDV采用的固定多徑傳輸則容易造成網(wǎng)絡擁塞。
   由圖7可知，MRABM和本文算法的端到端時延都較小，這是因為當節(jié)點移動造成鏈路斷開時，這兩種算法都不需要等待路徑修復或路由重建過程，而AOMDV在所有路徑失效后，將由源節(jié)點發(fā)起路由重建，所以端到端時延較大。
   針對無線mesh網(wǎng)絡中目前存在的幾種多徑路由協(xié)議的局限性，提出了一種基于源節(jié)點建立和目的節(jié)點維護mesh結(jié)構(gòu)的多徑路由協(xié)議。此協(xié)議中,在建立路由時,每個中間節(jié)點只需要轉(zhuǎn)發(fā)一次路由請求包,以后的路由完善、路由更新和路由維護均由目的節(jié)點完成,降低了路由維護的時間。路徑的最佳性和跟隨拓撲變化的實時性,提高了數(shù)據(jù)包的傳輸率,降低了網(wǎng)絡的平均延時。另外,基于源節(jié)點建立的路徑,有效地控制了RREQ在全網(wǎng)的泛洪,減少了控制開銷,更合理地利用了網(wǎng)絡資源。
   本文提出的算法雖在已有算法的基礎(chǔ)上有所改進,但仍需要進一步完善和深入。
參考文獻
[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] 劉經(jīng)緯,雷濤,徐海川,等.Ad-hoc網(wǎng)絡多徑路由協(xié)議的研究與設(shè)計. 計算機工程與設(shè)計, 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結(jié)構(gòu)的多徑路由算法.計算機工程與應用,2007,43(3).