摘 要： 基于自適應移動多跳Ad Hoc網絡，針對其DSR協議的路由緩存機制，分析不足之處，探索對現有的路由緩存機制的優化方法。提出了緩存路由有效期的概念，為網絡中節點的路由表添加一個用于反饋的“緩存路由跳數”參數，節點選擇此參數值最小者的路由信息。仿真實驗表明，經過改進的緩存機制有效地避免了響應沖突問題，實現了路由的最短優化，在平均傳輸延遲、分組投遞率、吞吐量性能方面都有提高。
關鍵詞： DSR；路由緩存；緩存路由有效期；跳數；NS2
Ad Hoc網絡[1]是一種特殊的無線移動通信網絡，網絡中所有的節點地位平等，無需設置任何的中心控制節點。對于Ad Hoc網絡而言，路由協議算法是最關鍵的技術。目前存在的Ad Hoc網絡路由協議分為表驅動路由協議和按需路由協議兩種。近年來，對于DSR協議已經做了一系列研究，DSR協議的不足有：(1)用于路由發現的控制報文會波及全網各節點，耗費較大；(2)路由響應風暴問題，源節點會同時收到多個路由響應，造成了響應沖突；(3)無效緩存路由問題，過期的路由信息會傳染其他節點。目前的研究結果主要有：莊春梅等[2]提出了DSR的鄰居表結構，根據節點狀態縮短路由，同時節點通過延遲轉發路由發現包的時間來選擇生存時間長的路由；AYUB J等[3]用一組參數描述節點的運動規律，論述了基于鏈路穩定性評估的路由協議的研究；Chen Jiaxu等[4]采用節點局部自適應機制，對于路由斷路繞遠等問題進行自動恢復調整，對DSR協議的緩存機制進行了改進；TAMILARASI M等[5]提出了節點局部自適應機制，對于路由斷路繞遠等問題進行自動恢復調整；Zhou Nianjun等[6]針對DSR協議傳輸報文時，遇到阻塞的路由開銷進行了改進；李學橋等[7]提出了分布式的緩存更新機制，讓各個節點異步地保持最新路由信息。但是上述文獻中考慮的只是對已有路由失效后的策略，并未避免路由響應沖突問題。
1 DSR協議
DSR協議是一種基于源路由方式的按需路由協議，主要包括路由發現和路由維護兩個過程。當源節點有報文發送要求時，首先檢查自己的緩存里是否有到達目的節點的路由，若存在則直接使用，否則發送r_req路由請求消息。當中間節點接收到r_req時，檢查是否收到過此消息，若收到過則停止轉發，并回復路由響應；若沒有，則先檢查自己緩存中是否有到達目的節點的路由，若有則加入該路由并返回r_rep，若沒有則將自己的地址加到r_req再轉發此r_req，直到源節點成功地接收到路由響應信息r_rep。在傳輸報文過程中，當中間節點檢測到通往目的節點的下一跳鏈路中斷時，它將從自己的緩存中刪去包含該鏈路的路由并向源節點返回一個r_err出錯分組，源節點收到r_err后，重新進行路由發現。Fu Z等[8]測試了TCP協議代理下的傳輸吞吐量與報文丟失的數據，發現DSR協議在吞吐量方面有缺陷。
由于無線廣播信道的特點，節點可以處于“混合監聽”狀態，這樣會出現“隱終端”問題，會產生報文響應沖突，進而造成傳輸阻塞。
2 基于沖突避免的優化
2.1 優化的算法
本文提出的優化建立在DSR協議已有的路由緩存機制上，因為節點處于移動狀態，某節點在某一時刻可能正在運動，也可能停止不動，并且運動的速度也有大有小。主要目標是針對DSR協議的路由尋找與路由回復階段產生的響應沖突問題。
本文為網絡中節點的路由表添加一個用于反饋的“緩存路由跳數”參數。各節點自有的緩存路由不會長時間有效，根據運動速度的大小和停留時間確定緩存路由的有效期。在有效期內，源節點或中間節點向下一節點發送路由請求后，可能會收到兩個或多個中間節點的路由響應，這時，發送路由請求的節點查看收到的路由響應對應的緩存路由跳數值，并選擇最小者的路由信息。一旦超過有效期，節點就啟動路由緩存更新，重新進行路由發現，并刪除無效路由信息。如圖1、圖2所示，經過改進的路由請求報文r_req比原有的r_req增加的字段有緩存路由跳數m和緩存路由有效期TTL。
改進后的協議DSR-BCA(DSR based on Collision Avoi-
dance)運作方式如下：
(1)如果源節點S的下一節點就是目的節點D，則節點D直接填充路由請求記錄字段，緩存此路由，記錄跳數m=1，并回復r_rep報文；否則轉到步驟(2)；
(2)源節點S的下一節點是中間節點，中間節點在收到r_req報文后，查看若發現自己的緩存路由信息中已有到達目的節點的路由，則直接回復r_rep報文，這樣減少了路由請求消息的廣播，否則轉到步驟(3)；
(3)源節點S的下一節點是中間節點，且r_req報文中的源節點地址請求類型ID存在于此中間節點的序列對列表中，表明此r_req報文已經收到過，此中間節點不需處理該請求；否則轉到步驟(4)；
(4)如果中間節點的地址已在r_req報文的路由請求記錄字段中，表明經過此中間節點的路由跳數必不是最小的，回復一個r_rep報文給上一節點，通知其再尋找下一跳節點；否則轉到步驟(5)；
(5)如果此中間節點不滿足步驟(3)和步驟(4)，則將自己的地址添加到路由請求記錄字段，然后向鄰節點廣播該路由請求，此中間節點仍然要緩存這個路由信息，記錄跳數；然后轉到步驟(6)；
(6)若r_req報文經過轉發到達了目的節點D，則報文中的路由請求記錄字段中節點地址序列構成了從源節點S到目的節點D的完整路由信息，節點D會緩存此信息，記錄跳數，并回復r_rep報文。
(7)在路由維護階段，對于不同運動速度的節點，設置不同的TTL。當節點運動速度大時，它附近網絡的拓撲變化就快，緩存路由的TTL就小；反之則大。一旦時長達到TTL，參與報文傳輸的節點丟棄原有的路由信息，再次啟動路由發現過程。
dsrbca_bitreq只比dsr_bitreq多了兩個字段，即2 bit，而n可達到101或102，故BDSR>>BDSR-BCA。
3 仿真分析與性能比較
3.1 仿真平臺與性能指標
本文使用NS2 version 2.35仿真平臺[9]，操作系統為Red Flag Linux 6.0。在仿真前要配置節點參數，利用仿真結果進行性能分析。性能指標有以下3個：平均傳輸時延，指從源節點發出一個分組到目的節點接收到此分組的時間間隔的平均值；分組投遞率，指目的節點接收到的報文數與源節點發送的報文數之比；歸一化路由開銷，指平均每發送一個分組所需要的路由控制分組數占總分組數的比例。
3.2 仿真場景設置與結果分析
利用NS2仿真平臺對優化前后的協議性能進行測試。節點運動模型采用Random Way Point模型，仿真平臺的參數設置如表1所示。
如圖4所示，隨著節點的運動速度增大，DSR和DSR-BCA協議的分組投遞率緩慢減小。這是因為失效路由增多，有用的數據傳輸受到的阻礙也會變大，源節點發送的報文也隨之丟失。從圖中可以看出，節點運動速度在15 m/s以內時，分組投遞率可以在98%以上，在這個指標上，DSR-BCA比DSR的性能只是提高了一點。
如圖5所示，隨著節點的運動速度增大，DSR和DSR-BCA協議的歸一化路由開銷都在增加。隨著網絡拓撲結構的變化，路由更新的次數增多，用于路由維護的控制報文也增多了。DSR-BCA協議的路由維護過程的額外耗費比DSR協議的少，在節點移動速度達到40 m/s時可以少約18%，速度越大越明顯。
Ad Hoc網絡因其節點具有移動、無中心、多跳的特點，從而導致了網絡拓撲的動態變化，因此路由協議的研究一直是熱點與難點。DSR協議作為按需路由的一種，其現有的路由機制仍然有一些缺陷，如路由響應風暴問題、失效路由問題。本文提出了緩存路由有效期、緩存路由跳數的概念并將其應用到DSR協議中優化。NS2仿真結果表明，DSR-BCA的性能比DSR的優越。
參考文獻
[1] 鄭少仁，王海濤，趙志峰，等.Ad Hoc網絡技術[M].北京：人民郵電出版社，2005：1-48.
[2] 莊春梅，王利利，陸建德.DSR協議的路由緩存策略[J]. 計算機工程，2010，36(2)：100-101.
[3] AYUB J，GARRIDO G，MARANDIN D.A linkcache invalidation mechanism for dynamic source routing(DSR) in Ad Hoc networks[J].IEEE Journal on Selected Areas in Communications，2007(7)：1144-1148.
[4] Chen Jiaxu，Tang Yazhe，Fu Dian，et al.On the improving strategies upon the route cache of DSR in MANETs[C]. International Conference on Ubiquitous Intelligence and Computing，Xi′an，2010：26-29.
[5] TAMILARASI M，PALANIVELU T G.An efficient Hop count based adaptive route cache timeout(HART) mechanism for on-demand routing in MANETs[J].IETETechnical Review，2007(6)：68-73.
[6] Zhou Nianjun，Wu Huaming，ABOUZEID A A.The impact of traffic patterns on the overhead of reactive routing protocols[J].IEEE Journal on Selected Areas in Communications，2005(3)：547-560.
[7] 李學橋，趙磊，賈小愛，等.DSR協議Cache管理策略的優化[J].通信技術，2009，42(2)：85-87.
[8] FU Z，ZERFOS P，LUO H，et al.The impact of multi hop wireless channel on TCP throughput and loss[C].Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies，San Francisco，2003：1744-1753.
[9] 王輝.NS網絡模擬器的原理和應用[M].西安：西北工業大學出版社，2008：30-56.