劉邵華 ，黃廷磊 ，夏 鋒

(1.桂林電子科技大學 電子工程與自動化學院，廣西 桂林541004；2.桂林電子科技大學 計算機控制與工程學院，廣西 桂林541004)

無線Mesh網(wǎng)絡(luò)結(jié)合了Ad Hoc網(wǎng)絡(luò)和傳統(tǒng)固定網(wǎng)絡(luò)的特點，具有高性能、低功耗、自組織、自配置的特點，因此Mesh網(wǎng)絡(luò)成為家庭網(wǎng)絡(luò)、社區(qū)寬帶網(wǎng)絡(luò)、企業(yè)內(nèi)部網(wǎng)絡(luò)的優(yōu)先選擇[1]。對于Mesh網(wǎng)絡(luò)來說，關(guān)鍵問題在于如何實現(xiàn)高品質(zhì)的路由協(xié)議，協(xié)議不但要能夠及時應(yīng)對網(wǎng)絡(luò)拓撲的動態(tài)變化，還要實現(xiàn)多跳傳輸?shù)馁|(zhì)量服務(wù)。

Mesh網(wǎng)絡(luò)目前使用的路由協(xié)議基本上都是從Ad Hoc移植過來的，AODV作為 Ad Hoc網(wǎng)絡(luò)經(jīng)典的路由協(xié)議，適用于動態(tài)的、多變的Ad Hoc網(wǎng)絡(luò)，它同多數(shù)其他 Ad Hoc路由協(xié)議(如DSR、DSDV等)一樣,采用最短路徑路由算法,但是大量的實驗和實踐證明了該算法并不適用于無線Mesh環(huán)境，主要是因為它以源節(jié)點到目的節(jié)點的跳數(shù)作為路由評價的標準，然而跳數(shù)最少的路徑在實際中未必是最優(yōu)的[2-3]。如當跳數(shù)最少路徑上的節(jié)點嚴重過載時,就會引起大量數(shù)據(jù)包丟失，增加延遲和降低網(wǎng)絡(luò)性能。在Mesh中，由于802.11 MAC采用的是分布式協(xié)調(diào)功能,在同一時刻的沖突域內(nèi)只允許兩個節(jié)點進行通信,另外在沖突域內(nèi)存在隱藏節(jié)點和暴露節(jié)點,當網(wǎng)絡(luò)負擔較重時,無線網(wǎng)絡(luò)的性能下降尤為突出,網(wǎng)絡(luò)吞吐性能遠低于理論值[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é)議當中一個重要的特點就是添加了序列號，可以有效地阻止計數(shù)無窮大和路由環(huán)路問題。在AODV中每個節(jié)點維護一個路由表來記錄從路由包中獲得的路由信息。當源節(jié)點需要發(fā)數(shù)據(jù)時，會查看自己的路由表里有沒有該條路徑，如果有，則按照路由表項中的信息直接轉(zhuǎn)發(fā)數(shù)據(jù)；否則發(fā)起一個路由發(fā)現(xiàn)過程。首先，源節(jié)點創(chuàng)建一個RREQ包并廣播，當鄰居節(jié)點接收到RREQ包時，該節(jié)點將RREQ包中的跳數(shù)值加1并在自己的路由表中創(chuàng)建一個反向路由，如果該節(jié)點就是目的節(jié)點或者該節(jié)點存在到達目的節(jié)點的路由表項，則該節(jié)點就向源節(jié)點發(fā)送RREP，否則它只廣播RREQ。

RREP的傳播是由目的節(jié)點向源節(jié)點單播完成的。當一個節(jié)點收到RREP之后，創(chuàng)建正向路由表項，其中包含目的節(jié)點和下一跳節(jié)點。根據(jù)反向路由表繼續(xù)傳播RREP，直到RREP被源節(jié)點接收到。節(jié)點移動可以破壞之前的路由，為了增加成功的數(shù)據(jù)傳輸率，本地節(jié)點能夠修復損壞的鏈路。發(fā)生斷路時，網(wǎng)絡(luò)的上游節(jié)點向目的地發(fā)送RREQ，為了避免環(huán)路，應(yīng)該將RREQ中目的節(jié)點的序列號加1。若本地修復成功，目的節(jié)點或者包含目的節(jié)點路由信息的中間節(jié)點創(chuàng)建RREP；如果節(jié)點修復失敗，則向源節(jié)點發(fā)送一個RERR包，源節(jié)點則重新創(chuàng)建新的RREQ，重新開始路由發(fā)現(xiàn)過程[6]。

2 改進的AODV-LS路由協(xié)議

2.1 AODV-LS路由選擇量度

AODV-LS中組合量度使用帶寬、緩存飽和度兩個參數(shù)。本文采用了基于 NAV[5]的統(tǒng)計來估算可用帶寬，節(jié)點所在信道的空閑時間是一個很重要的參數(shù)，由節(jié)點以及鄰居節(jié)點的業(yè)務(wù)量綜合決定，在這段時間內(nèi)節(jié)點可以成功地傳輸數(shù)據(jù)。Bi=B×Ti/Tc，其中 Bi為節(jié)點的實時可用帶寬，B為信道帶寬，Tc為觀察時間，Ti為在觀察時間內(nèi)的信道空閑時間。這里還考慮了節(jié)點緩存隊列飽和度的影響，如果節(jié)點緩沖隊列已滿，網(wǎng)絡(luò)發(fā)生擁塞會引起網(wǎng)路性能的急劇下降，例如時延增大、丟包率增加等。如果在路由發(fā)現(xiàn)時考慮節(jié)點負載狀態(tài)，將會降低擁塞，提高網(wǎng)絡(luò)性能。本文定義緩存飽和度為緩存節(jié)點的包的數(shù)量與允許緩存的額定包數(shù)之比，定義為ri=Ci/Cm，其中，Cm為緩沖隊列最大值，Ci是緩沖隊列中包數(shù)值。

節(jié)點負載越大,緩沖越接近飽和,其同鄰居節(jié)點間的鏈路則越繁忙,可用帶寬越少,因而通信傳輸代價同時也就越高。節(jié)點i的鏈路權(quán)重Xi計算如下：

Xi=[Bi/B+(1-Rti)+(1-Rgi)]×10

其中，Rti表示發(fā)送緩沖飽和度，Rgi代表接收緩沖隊列飽和度。并且一條鏈路的關(guān)鍵因素是所有中間節(jié)點權(quán)重的最小值：Xmi=min（X1，X2，X3，X4，…，Xh-1），h 為該條路徑的跳數(shù)。若Xmi越大，說明該條鏈路負載越少；Xmi越小，說明該條路徑上負載越大。為了綜合考慮鏈路狀況，還要考慮路由節(jié)點的鏈路權(quán)重之和，即：

Wj=sum（X1+X2+X3，…，Xh-1）

最后給出路由判定量度組合：

Pj=α×Xmi+(β×Wj)/(h-1)

式中α、β值的選取通過試驗獲得，且 α+β=1。為了盡量避開負載較重的節(jié)點，在源節(jié)點到目的節(jié)點之間找到一條負載較輕的路徑，賦予α較大的權(quán)重。

2.2 路由發(fā)現(xiàn)與建立

2.2.1 請求報文與數(shù)據(jù)報文

2）生活習性。桃小食心蟲在渭北果區(qū)每年發(fā)生1～2代，以老熟幼蟲在土壤內(nèi)結(jié)繭越冬。一般5月下旬至6月上旬越冬幼蟲破繭出土，成蟲多產(chǎn)卵于果實梗（萼）洼處。幼蟲孵化后，蛀入果實，在果實內(nèi)蛀食20天左右，老熟后咬破果皮，脫果而出；脫果早的在土表作夏繭化蛹發(fā)生第2代，脫果晚的入土越冬。6月下旬至7月上中旬出現(xiàn)第1代成蟲，8月上中旬出現(xiàn)第2代幼蟲，在采果前大部分脫果。

(1)路由請求報文 RREQ，包括 Type，Hops，RequestNo，DestinationIP，OriginatorIP，PreNode，Xmi，Wj。

(2)路由響應(yīng)報文 RREP，包括 Type，Hops，RequestNo，DestinationIP，OriginatorIP，PreNode，RREQSrc，Xmi，Wj。

2.2.2 路由發(fā)現(xiàn)過程

每個節(jié)點都保留一個路由表,用來存儲節(jié)點所需要的路由信息，其表項是一個向量（Destination，NextHop，Wj，Hops，Pj，S，X，Xmi，LF）， 其 中 Destination 表 示 目 的網(wǎng)絡(luò)，NextHop為到達目的網(wǎng)絡(luò)的下一跳,Wj為從該節(jié)點到達目的網(wǎng)絡(luò)的累計鏈路權(quán)重，Hops為從該節(jié)點達到目的網(wǎng)絡(luò)的累計跳數(shù)，S為路由發(fā)現(xiàn)發(fā)起的節(jié)點，X為路由請求序號，LF為路由表項的生存時間。

(1)當源節(jié)點s要向目的地d轉(zhuǎn)發(fā)數(shù)據(jù)時，若存在s到d的路由，則轉(zhuǎn)發(fā)數(shù)據(jù)即可，如果不存在 s到d的路由信息，則創(chuàng)建RREQ報文并廣播，RREQ中 Type=1，Hops=0，Xmi=0，Wj=0，DestinationIP=d，OriginatorIP=s，Pre-Node=s，RequestNo=(當前節(jié)點最新的路由請求序號+1)。

(2)當節(jié)點k接收到RREQ包時，首先查看自身的權(quán)重值，如果自身的權(quán)重值超過了規(guī)定的權(quán)重值范圍，則直接扔掉該RREQ報文，否則創(chuàng)建反向路由向量,并且用RREQ報文中的值來填充該路由向量（s,RREQ.PreN-ode,RREQ.Wj,RREQ.Hops，α ×RREQ.Xmi+β ×RREQ.Wj/（RREQ.Hops-1）,RREQ.RequestNo,RREQ.Xmi,LF）。 如果k≠d，并且k中不含有到達 d的向量，則修改 RREQ報文 ， 若 RREQ.Xmi〈k.Xmi,則 RREQ.Xmi=k.Xmi， 否 則RREQ.Xmi保持不變，RREQ.Hops=RREQ.Hops+1，RREQ.PreNode=k，RREQ.Wj+k.Xmi,修改后的報文繼續(xù)廣播。如果k=d或者k的路由表中存在到達d的路徑，則產(chǎn)生回復報文 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的向量，則RREP.Hops=RT.Hops,RREP.Xmi=min(K.Xmi,RT.Xmi)，RREP.Wj=RT.Wj+k.Xmi(這里假設(shè)RT是該節(jié)點到目的地的向量)，構(gòu)造響應(yīng)報文之后以單播的方式轉(zhuǎn)發(fā)。

(3)當節(jié)點 h收到 RREP之后，構(gòu)造h到下跳節(jié)點的正向路由向量（d,RREP.PreNode,RREP.Wj,RREP.Hops,RREP.Pj,RREP.RREQSrc,RREP.RequestNo,RREP.Xmi,LF）,如果h不是s，則更新RREP繼續(xù)單播下去，直至源節(jié)點s接收到 RREP。

2.3 路由維護過程

AODV-LS協(xié)議在路由維護方面也做了較大改變。在協(xié)議中，每個節(jié)點周期性地發(fā)送HELLO報文，用于同鄰居節(jié)點交換狀態(tài)信息。

(1)當鏈路斷開時，節(jié)點a不可達，這里假設(shè)a節(jié)點的下游節(jié)點到目的節(jié)點的路由仍然是有效的，則a節(jié)點的上游節(jié)點創(chuàng)建RREQ報文，并且把TTL設(shè)置為3，以此來限制廣播RREQ的范圍。舉例：圖1中原始路由是S-A-B-C-D，當B不可達時，節(jié)點A產(chǎn)生RREQ報文廣播，如果節(jié)點E收到報文并且自身的權(quán)重值滿足路由要求時，則E節(jié)點創(chuàng)建反向路由，并且繼續(xù)廣播包，如果此時C收到RREQ報文，并且C到D的路由還有效，則產(chǎn)生本地修復RREP報文并發(fā)送給節(jié)點A。當節(jié)點E接收到RREP報文，并且自身的鏈路權(quán)重滿足路由要求時，則產(chǎn)生正向路由向量，至此路由恢復過程完成，新的路徑變?yōu)镾A-E-C-D。

如果一個本地修復請求到期時，則斷路節(jié)點的上游節(jié)點產(chǎn)生RERR報文，通知源節(jié)點本條路由已斷路，如果需要，重新發(fā)起路由請求。

(2)節(jié)點過載的路由維護。AODV-LS中節(jié)點a發(fā)送的HELLO報文,還會計算a與鄰居的鏈路權(quán)重。當權(quán)重值超出規(guī)定的范圍時,就廣播節(jié)點過載LRRERR報文，鄰居節(jié)點b收到LRRERR報文后，節(jié)點b則繼續(xù)按照(1)中的方式，按節(jié)點a不可達時的情況進行路由維護。

3 仿真與分析

利用 NS2(v2.34)對 AODV-LS進行仿真，分別對數(shù)據(jù)包平均端到端延遲、數(shù)據(jù)包轉(zhuǎn)發(fā)率、標準化路由負載等性能進行分析。MAC層采用IEEE802.11標準規(guī)定的分布式協(xié)調(diào)功能,利用CSMA/CA作為傳輸機制，網(wǎng)絡(luò)帶寬為2 Mb/s，發(fā)送數(shù)據(jù)包的大小為512 B。在仿真過程中，50個無線路由節(jié)點在一個800 m×800 m的矩形區(qū)域內(nèi)隨機移動，移動速度分布在0～4 m/s的范圍內(nèi)。數(shù)據(jù)源節(jié)點的個數(shù)為 20，發(fā)包率為每秒分別發(fā)送 1、2、4、7、10個包來產(chǎn)生不同的負載。分別對AODV-LS協(xié)議和AODV協(xié)議進行模擬仿真，并對仿真結(jié)果進行分析，得到兩個協(xié)議在不同停留時間下的數(shù)據(jù)包轉(zhuǎn)發(fā)率、數(shù)據(jù)包平均端到端延遲和標準化路由負載。

圖2顯示了網(wǎng)絡(luò)中節(jié)點發(fā)包率變化時，AODV、AODV-LS數(shù)據(jù)包轉(zhuǎn)發(fā)率的曲線。結(jié)果表明在網(wǎng)絡(luò)負載很小時，AODV、AODV-LS都有較高的、相近的數(shù)據(jù)轉(zhuǎn)發(fā)率。而當網(wǎng)絡(luò)負載增加時，AODV-LS的性能提高十分明顯。這是因為AODV-LS盡量避開負載較重的節(jié)點，選擇負載較輕的路徑傳輸數(shù)據(jù)，間接地提高了整個網(wǎng)絡(luò)的吞吐量。

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

圖4顯示，AODV-LS在標準化路由負載方面略優(yōu)于 AODV。這主要由于不斷轉(zhuǎn)發(fā)RREQ在AODV的路由分組中占用了大量的網(wǎng)絡(luò)開銷，而在AODV-LS中過載的中間節(jié)點直接丟棄RREQ，大大減少了網(wǎng)絡(luò)路由開銷。同時，由于AODV-LS的分組轉(zhuǎn)發(fā)率比AODV高，相同情況下目的節(jié)點接收到更多的分組，所以標準化路由負載較小。

本文針對Mesh網(wǎng)絡(luò)自身的特點，對AODV算法做了改進，提出了新的AODV-LS路由協(xié)議，該協(xié)議采用節(jié)點權(quán)重值作為路由建立標準。實驗結(jié)果表明，由于采用了權(quán)重值作為路由判據(jù)，整個網(wǎng)絡(luò)的吞吐性能、包轉(zhuǎn)發(fā)率、端到端延時等方面都要優(yōu)于AODV，體現(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)的無線Mesh網(wǎng)絡(luò)路由協(xié)議[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仿真實驗——多媒體和無線網(wǎng)絡(luò)通信[M].北京：電子工業(yè)出版社，2009.