摘  要： 在分析經(jīng)典路由協(xié)議AODV的基礎(chǔ)上,，結(jié)合Mesh網(wǎng)絡(luò)的特點(diǎn)，提出了一種新的路由協(xié)議AODV-LS,。新的路由協(xié)議根據(jù)節(jié)點(diǎn)帶寬以及實(shí)時(shí)負(fù)載量這兩個(gè)參數(shù)計(jì)算出節(jié)點(diǎn)權(quán)重值,，根據(jù)節(jié)點(diǎn)權(quán)重值評(píng)估鏈路的性能，根據(jù)鏈路性能選擇最優(yōu)路徑,。實(shí)驗(yàn)結(jié)果表明,，AODV-LS協(xié)議在數(shù)據(jù)分組投遞率、端到端延時(shí)和標(biāo)準(zhǔn)化路由負(fù)載方面都優(yōu)于AODV,。
關(guān)鍵詞： AODV,；節(jié)點(diǎn)權(quán)重值；分組投遞率,；端到端延時(shí)

    無(wú)線Mesh網(wǎng)絡(luò)結(jié)合了Ad Hoc網(wǎng)絡(luò)和傳統(tǒng)固定網(wǎng)絡(luò)的特點(diǎn),，具有高性能、低功耗,、自組織,、自配置的特點(diǎn)，因此Mesh網(wǎng)絡(luò)成為家庭網(wǎng)絡(luò),、社區(qū)寬帶網(wǎng)絡(luò),、企業(yè)內(nèi)部網(wǎng)絡(luò)的優(yōu)先選擇[1]。對(duì)于Mesh網(wǎng)絡(luò)來(lái)說(shuō),，關(guān)鍵問(wèn)題在于如何實(shí)現(xiàn)高品質(zhì)的路由協(xié)議,，協(xié)議不但要能夠及時(shí)應(yīng)對(duì)網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)變化，還要實(shí)現(xiàn)多跳傳輸?shù)馁|(zhì)量服務(wù),。
    Mesh網(wǎng)絡(luò)目前使用的路由協(xié)議基本上都是從Ad Hoc移植過(guò)來(lái)的,，AODV作為 Ad Hoc網(wǎng)絡(luò)經(jīng)典的路由協(xié)議，適用于動(dòng)態(tài)的,、多變的Ad Hoc網(wǎng)絡(luò),，它同多數(shù)其他Ad Hoc路由協(xié)議(如DSR,、DSDV等)一樣,采用最短路徑路由算法,但是大量的實(shí)驗(yàn)和實(shí)踐證明了該算法并不適用于無(wú)線Mesh環(huán)境，主要是因?yàn)樗栽垂?jié)點(diǎn)到目的節(jié)點(diǎn)的跳數(shù)作為路由評(píng)價(jià)的標(biāo)準(zhǔn),，然而跳數(shù)最少的路徑在實(shí)際中未必是最優(yōu)的[2-3],。如當(dāng)跳數(shù)最少路徑上的節(jié)點(diǎn)嚴(yán)重過(guò)載時(shí),就會(huì)引起大量數(shù)據(jù)包丟失，增加延遲和降低網(wǎng)絡(luò)性能,。在Mesh中,，由于802.11 MAC采用的是分布式協(xié)調(diào)功能, 在同一時(shí)刻的沖突域內(nèi)只允許兩個(gè)節(jié)點(diǎn)進(jìn)行通信, 另外在沖突域內(nèi)存在隱藏節(jié)點(diǎn)和暴露節(jié)點(diǎn),當(dāng)網(wǎng)絡(luò)負(fù)擔(dān)較重時(shí), 無(wú)線網(wǎng)絡(luò)的性能下降尤為突出,網(wǎng)絡(luò)吞吐性能遠(yuǎn)低于理論值[4-5]。
    由于Ad Hoc路由協(xié)議先天不足,，以及Mesh網(wǎng)絡(luò)自身的特殊性,，現(xiàn)有的Ad Hoc路由協(xié)議不能滿足Mesh網(wǎng)絡(luò)的要求，因此本文提出了新的路由算法AODV-LS,。
1 AODV算法
    AODV是基于DSDV和DSR提出的一種按需路由,。AODV協(xié)議當(dāng)中一個(gè)重要的特點(diǎn)就是添加了序列號(hào)，可以有效地阻止計(jì)數(shù)無(wú)窮大和路由環(huán)路問(wèn)題,。在AODV中每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)路由表來(lái)記錄從路由包中獲得的路由信息。當(dāng)源節(jié)點(diǎn)需要發(fā)數(shù)據(jù)時(shí),，會(huì)查看自己的路由表里有沒(méi)有該條路徑,，如果有，則按照路由表項(xiàng)中的信息直接轉(zhuǎn)發(fā)數(shù)據(jù),；否則發(fā)起一個(gè)路由發(fā)現(xiàn)過(guò)程,。首先，源節(jié)點(diǎn)創(chuàng)建一個(gè)RREQ包并廣播,，當(dāng)鄰居節(jié)點(diǎn)接收到RREQ包時(shí),，該節(jié)點(diǎn)將RREQ包中的跳數(shù)值加1并在自己的路由表中創(chuàng)建一個(gè)反向路由，如果該節(jié)點(diǎn)就是目的節(jié)點(diǎn)或者該節(jié)點(diǎn)存在到達(dá)目的節(jié)點(diǎn)的路由表項(xiàng),，則該節(jié)點(diǎn)就向源節(jié)點(diǎn)發(fā)送RREP,，否則它只廣播RREQ。
    RREP的傳播是由目的節(jié)點(diǎn)向源節(jié)點(diǎn)單播完成的,。當(dāng)一個(gè)節(jié)點(diǎn)收到RREP之后,，創(chuàng)建正向路由表項(xiàng)，其中包含目的節(jié)點(diǎn)和下一跳節(jié)點(diǎn),。根據(jù)反向路由表繼續(xù)傳播RREP,，直到RREP被源節(jié)點(diǎn)接收到。節(jié)點(diǎn)移動(dòng)可以破壞之前的路由,，為了增加成功的數(shù)據(jù)傳輸率,，本地節(jié)點(diǎn)能夠修復(fù)損壞的鏈路。發(fā)生斷路時(shí),，網(wǎng)絡(luò)的上游節(jié)點(diǎn)向目的地發(fā)送RREQ,，為了避免環(huán)路，應(yīng)該將RREQ中目的節(jié)點(diǎn)的序列號(hào)加1。若本地修復(fù)成功,，目的節(jié)點(diǎn)或者包含目的節(jié)點(diǎn)路由信息的中間節(jié)點(diǎn)創(chuàng)建RREP,；如果節(jié)點(diǎn)修復(fù)失敗，則向源節(jié)點(diǎn)發(fā)送一個(gè)RERR包,，源節(jié)點(diǎn)則重新創(chuàng)建新的RREQ,，重新開(kāi)始路由發(fā)現(xiàn)過(guò)程[6]。
2 改進(jìn)的AODV-LS路由協(xié)議
2.1 AODV-LS路由選擇量度
    AODV-LS中組合量度使用帶寬,、緩存飽和度兩個(gè)參數(shù),。本文采用了基于 NAV[5]的統(tǒng)計(jì)來(lái)估算可用帶寬，節(jié)點(diǎn)所在信道的空閑時(shí)間是一個(gè)很重要的參數(shù),，由節(jié)點(diǎn)以及鄰居節(jié)點(diǎn)的業(yè)務(wù)量綜合決定,，在這段時(shí)間內(nèi)節(jié)點(diǎn)可以成功地傳輸數(shù)據(jù)。Bi=B×Ti/Tc,，其中Bi為節(jié)點(diǎn)的實(shí)時(shí)可用帶寬,，B為信道帶寬，Tc為觀察時(shí)間,，Ti為在觀察時(shí)間內(nèi)的信道空閑時(shí)間,。這里還考慮了節(jié)點(diǎn)緩存隊(duì)列飽和度的影響，如果節(jié)點(diǎn)緩沖隊(duì)列已滿,，網(wǎng)絡(luò)發(fā)生擁塞會(huì)引起網(wǎng)路性能的急劇下降,，例如時(shí)延增大、丟包率增加等,。如果在路由發(fā)現(xiàn)時(shí)考慮節(jié)點(diǎn)負(fù)載狀態(tài),，將會(huì)降低擁塞，提高網(wǎng)絡(luò)性能,。本文定義緩存飽和度為緩存節(jié)點(diǎn)的包的數(shù)量與允許緩存的額定包數(shù)之比,，定義為ri=Ci/Cm，其中,，Cm為緩沖隊(duì)列最大值,，Ci是緩沖隊(duì)列中包數(shù)值。
    節(jié)點(diǎn)負(fù)載越大,緩沖越接近飽和, 其同鄰居節(jié)點(diǎn)間的鏈路則越繁忙, 可用帶寬越少, 因而通信傳輸代價(jià)同時(shí)也就越高,。節(jié)點(diǎn)i的鏈路權(quán)重Xi計(jì)算如下：
    Xi=[Bi/B+(1-Rti)+(1-Rgi)]×10
其中,，Rti表示發(fā)送緩沖飽和度，Rgi代表接收緩沖隊(duì)列飽和度,。并且一條鏈路的關(guān)鍵因素是所有中間節(jié)點(diǎn)權(quán)重的最小值：Xmi=min（X1,，X2，X3,，X4,，…,，Xh-1），h為該條路徑的跳數(shù),。若Xmi越大,，說(shuō)明該條鏈路負(fù)載越少；Xmi越小,，說(shuō)明該條路徑上負(fù)載越大,。為了綜合考慮鏈路狀況，還要考慮路由節(jié)點(diǎn)的鏈路權(quán)重之和,，即：
    Wj=sum（X1+X2+X3,，…，Xh-1）
最后給出路由判定量度組合：
    Pj=?琢×Xmi+(?茁×Wj)/(h-1)
式中?琢,、?茁值的選取通過(guò)試驗(yàn)獲得,，且?琢+?茁=1。為了盡量避開(kāi)負(fù)載較重的節(jié)點(diǎn),，在源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間找到一條負(fù)載較輕的路徑,，賦予?琢較大的權(quán)重。
2.2 路由發(fā)現(xiàn)與建立
2.2.1 請(qǐng)求報(bào)文與數(shù)據(jù)報(bào)文
    (1)路由請(qǐng)求報(bào)文RREQ,，包括Type,，Hops，RequestNo,，DestinationIP，OriginatorIP,，PreNode,，Xmi，Wj,。
    (2)路由響應(yīng)報(bào)文RREP,，包括Type，Hops,，RequestNo,，DestinationIP，OriginatorIP,，PreNode,，RREQSrc，Xmi,，Wj,。
2.2.2 路由發(fā)現(xiàn)過(guò)程
    每個(gè)節(jié)點(diǎn)都保留一個(gè)路由表, 用來(lái)存儲(chǔ)節(jié)點(diǎn)所需要的路由信息，其表項(xiàng)是一個(gè)向量（Destination,，NextHop,，Wj,，Hops，Pj,，S,，X，Xmi,，LF）,，其中Destination表示目的網(wǎng)絡(luò)，NextHop為到達(dá)目的網(wǎng)絡(luò)的下一跳, Wj為從該節(jié)點(diǎn)到達(dá)目的網(wǎng)絡(luò)的累計(jì)鏈路權(quán)重,，Hops為從該節(jié)點(diǎn)達(dá)到目的網(wǎng)絡(luò)的累計(jì)跳數(shù),，S為路由發(fā)現(xiàn)發(fā)起的節(jié)點(diǎn)，X為路由請(qǐng)求序號(hào),，LF為路由表項(xiàng)的生存時(shí)間,。
    (1)當(dāng)源節(jié)點(diǎn)s要向目的地d轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)，若存在s到d的路由,，則轉(zhuǎn)發(fā)數(shù)據(jù)即可,，如果不存在s到d的路由信息，則創(chuàng)建RREQ報(bào)文并廣播,，RREQ中Type=1,，Hops=0，Xmi=0,，Wj=0,，DestinationIP=d，OriginatorIP=s,，Pre-Node=s,，RequestNo=(當(dāng)前節(jié)點(diǎn)最新的路由請(qǐng)求序號(hào)+1)。
    (2)當(dāng)節(jié)點(diǎn)k接收到RREQ包時(shí),，首先查看自身的權(quán)重值,，如果自身的權(quán)重值超過(guò)了規(guī)定的權(quán)重值范圍，則直接扔掉該RREQ報(bào)文,，否則創(chuàng)建反向路由向量,并且用RREQ報(bào)文中的值來(lái)填充該路由向量（s,RREQ.PreNode,RREQ.Wj,RREQ.Hops,，α×RREQ.Xmi+β×RREQ.Wj/（RREQ.Hops-1）,RREQ.RequestNo,RREQ.Xmi,LF）。如果k≠d,，并且k中不含有到達(dá)d的向量,，則修改RREQ報(bào)文，若RREQ.Xmi<k.Xmi,則RREQ.Xmi=k.Xmi,，否則RREQ.Xmi保持不變,，RREQ.Hops=RREQ.Hops+1，RREQ.PreNode=k,，RREQ.Wj+k.Xmi,修改后的報(bào)文繼續(xù)廣播,。如果k=d或者k的路由表中存在到達(dá)d的路徑,，則產(chǎn)生回復(fù)報(bào)文RREP,RREP中Type=2，RREP.RequestNo=RREQ.RequestNo,RREP.OriginatorIP=d,RREP.RREQSrc=RREQ.OriginatorIP,RREP.DestinationIP=RREQ.PreNode,，如果k=d,，則RREP.Hops=0，RREP.Xmi=0,，RREP.Wj=0,，若k路由表中存在到達(dá)d的向量，則RREP.Hops=RT.Hops,RREP.Xmi=min(K.Xmi,RT.Xmi),，RREP.Wj=RT.Wj+k.Xmi(這里假設(shè)RT是該節(jié)點(diǎn)到目的地的向量),，構(gòu)造響應(yīng)報(bào)文之后以單播的方式轉(zhuǎn)發(fā)。
    (3)當(dāng)節(jié)點(diǎn)h收到RREP之后,，構(gòu)造h到下跳節(jié)點(diǎn)的正向路由向量（d,RREP.PreNode,RREP.Wj,RREP.Hops,RREP.Pj,RREP.RREQSrc,RREP.RequestNo,RREP.Xmi,LF）,如果h不是s,，則更新RREP繼續(xù)單播下去，直至源節(jié)點(diǎn)s接收到RREP,。
    在尋找路由定時(shí)器超時(shí)前,，如果源節(jié)點(diǎn)s收到相對(duì)應(yīng)的RREP報(bào)文，則構(gòu)建從s到d的路由向量,。如果在定時(shí)器時(shí)間內(nèi)源節(jié)點(diǎn)s收到多個(gè)RREP回應(yīng),，本設(shè)計(jì)選擇前3個(gè)做比較。從中選擇鏈路值最大的一個(gè)回應(yīng),。如果出現(xiàn)鏈路值相等的情況,，則選擇鏈路最短的一個(gè)?？紤]到鏈路的延時(shí)問(wèn)題,，接收到3個(gè)RREP包后多余的就直接放棄。

    如果一個(gè)本地修復(fù)請(qǐng)求到期時(shí),，則斷路節(jié)點(diǎn)的上游節(jié)點(diǎn)產(chǎn)生RERR報(bào)文，通知源節(jié)點(diǎn)本條路由已斷路,，如果需要,，重新發(fā)起路由請(qǐng)求。
    (2)節(jié)點(diǎn)過(guò)載的路由維護(hù),。AODV-LS中節(jié)點(diǎn)a發(fā)送的HELLO報(bào)文,還會(huì)計(jì)算a與鄰居的鏈路權(quán)重,。當(dāng)權(quán)重值超出規(guī)定的范圍時(shí), 就廣播節(jié)點(diǎn)過(guò)載LRRERR報(bào)文，鄰居節(jié)點(diǎn)b收到LRRERR報(bào)文后,，節(jié)點(diǎn)b則繼續(xù)按照(1)中的方式,，按節(jié)點(diǎn)a不可達(dá)時(shí)的情況進(jìn)行路由維護(hù)。
3 仿真與分析
    利用NS2(v2.34)對(duì)AODV-LS進(jìn)行仿真,，分別對(duì)數(shù)據(jù)包平均端到端延遲,、數(shù)據(jù)包轉(zhuǎn)發(fā)率,、標(biāo)準(zhǔn)化路由負(fù)載等性能進(jìn)行分析。MAC層采用IEEE802.11標(biāo)準(zhǔn)規(guī)定的分布式協(xié)調(diào)功能,利用CSMA/CA作為傳輸機(jī)制,，網(wǎng)絡(luò)帶寬為2 Mb/s,，發(fā)送數(shù)據(jù)包的大小為512 B。在仿真過(guò)程中,，50個(gè)無(wú)線路由節(jié)點(diǎn)在一個(gè)800 m×800 m的矩形區(qū)域內(nèi)隨機(jī)移動(dòng),，移動(dòng)速度分布在0～4 m/s的范圍內(nèi)。數(shù)據(jù)源節(jié)點(diǎn)的個(gè)數(shù)為20,，發(fā)包率為每秒分別發(fā)送 1,、2、4,、7,、10 個(gè)包來(lái)產(chǎn)生不同的負(fù)載。分別對(duì)AODV-LS協(xié)議和AODV協(xié)議進(jìn)行模擬仿真,，并對(duì)仿真結(jié)果進(jìn)行分析,，得到兩個(gè)協(xié)議在不同停留時(shí)間下的數(shù)據(jù)包轉(zhuǎn)發(fā)率、數(shù)據(jù)包平均端到端延遲和標(biāo)準(zhǔn)化路由負(fù)載,。
    圖2顯示了網(wǎng)絡(luò)中節(jié)點(diǎn)發(fā)包率變化時(shí),，AODV、AODV-LS數(shù)據(jù)包轉(zhuǎn)發(fā)率的曲線,。結(jié)果表明在網(wǎng)絡(luò)負(fù)載很小時(shí),，AODV、AODV-LS都有較高的,、相近的數(shù)據(jù)轉(zhuǎn)發(fā)率,。而當(dāng)網(wǎng)絡(luò)負(fù)載增加時(shí)，AODV-LS的性能提高十分明顯,。這是因?yàn)锳ODV-LS盡量避開(kāi)負(fù)載較重的節(jié)點(diǎn),，選擇負(fù)載較輕的路徑傳輸數(shù)據(jù)，間接地提高了整個(gè)網(wǎng)絡(luò)的吞吐量,。

    圖3顯示分組平均端到端時(shí)延的變化曲線,，節(jié)點(diǎn)發(fā)包率較小時(shí)，AODV-LS與AODV平均端到端延遲相近,，但隨著節(jié)點(diǎn)發(fā)包率的增加,，AODV-LS延遲明顯小于 AODV。當(dāng)網(wǎng)絡(luò)負(fù)載增大時(shí),，AODV-LS試圖找到一條鏈路狀況最好的路徑,，繞過(guò)堵塞的節(jié)點(diǎn)，減小了擁塞等待時(shí)間。

    本文針對(duì)Mesh網(wǎng)絡(luò)自身的特點(diǎn),，對(duì)AODV算法做了改進(jìn),，提出了新的AODV-LS路由協(xié)議，該協(xié)議采用節(jié)點(diǎn)權(quán)重值作為路由建立標(biāo)準(zhǔn),。實(shí)驗(yàn)結(jié)果表明,，由于采用了權(quán)重值作為路由判據(jù)，整個(gè)網(wǎng)絡(luò)的吞吐性能,、包轉(zhuǎn)發(fā)率,、端到端延時(shí)等方面都要優(yōu)于AODV，體現(xiàn)了良好的性能,。
參考文獻(xiàn)
[1] AKYILDIZI F,，WANG X D，WANG W L.Wireless Mesh networks：Asurvey[J].Computer Networks,，2005,，47(4)：445-487.
[2] WAHARTE S，BOUTABA R,，IRAQI Y,，et al.Routing protocols in wireless mesh networks：challenges and design considerations[J].Springer Multimed.Tool Appl.2006，31(3)：285-303.
[3] 符云清,，王松健,，吳中福.基于鏈路狀態(tài)加權(quán)的無(wú)線Mesh網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)研究與發(fā)展，2009,，46(1)：137-143.
[4] JUN J,，SICHITIU M L.MRP：wireless mesh networks routing protocol[J].Comput.Commun，2008,，31(7)：1413-1435.
[5] CHEN L,，HEINZELMAN W B.QoS-aware routing based on bandwidth estimation for mobile Ad Hoc networks[J].IEEE Journal on Areas in Communications，2005,，23(3)：561-572.
[6] PERKINS C E,，ROYER E M.Ad-Hoc on-demand distance  vector routing(AODV)[C].RFC 3561，2003.
[7] 柯志亨,，程榮祥,，鄧德雋.NS2仿真實(shí)驗(yàn)——多媒體和無(wú)線網(wǎng)絡(luò)通信[M].北京：電子工業(yè)出版社，2009.