摘  要： 在分析經典路由協議AODV的基礎上，結合Mesh網絡的特點，提出了一種新的路由協議AODV-LS。新的路由協議根據節點帶寬以及實時負載量這兩個參數計算出節點權重值，根據節點權重值評估鏈路的性能，根據鏈路性能選擇最優路徑。實驗結果表明，AODV-LS協議在數據分組投遞率、端到端延時和標準化路由負載方面都優于AODV。
關鍵詞： AODV；節點權重值；分組投遞率；端到端延時

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

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

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

    本文針對Mesh網絡自身的特點，對AODV算法做了改進，提出了新的AODV-LS路由協議，該協議采用節點權重值作為路由建立標準。實驗結果表明，由于采用了權重值作為路由判據，整個網絡的吞吐性能、包轉發率、端到端延時等方面都要優于AODV，體現了良好的性能。
參考文獻
[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] 符云清，王松健，吳中福.基于鏈路狀態加權的無線Mesh網絡路由協議[J].計算機研究與發展，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仿真實驗——多媒體和無線網絡通信[M].北京：電子工業出版社，2009.