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

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

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

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

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

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