摘  要： 基于自適應(yīng)移動多跳Ad Hoc網(wǎng)絡(luò),，針對其DSR協(xié)議的路由緩存機(jī)制，分析不足之處,，探索對現(xiàn)有的路由緩存機(jī)制的優(yōu)化方法,。提出了緩存路由有效期的概念，為網(wǎng)絡(luò)中節(jié)點的路由表添加一個用于反饋的“緩存路由跳數(shù)”參數(shù),，節(jié)點選擇此參數(shù)值最小者的路由信息,。仿真實驗表明，經(jīng)過改進(jìn)的緩存機(jī)制有效地避免了響應(yīng)沖突問題,，實現(xiàn)了路由的最短優(yōu)化,，在平均傳輸延遲、分組投遞率,、吞吐量性能方面都有提高,。
關(guān)鍵詞： DSR；路由緩存,；緩存路由有效期,；跳數(shù)；NS2

    Ad Hoc網(wǎng)絡(luò)[1]是一種特殊的無線移動通信網(wǎng)絡(luò),，網(wǎng)絡(luò)中所有的節(jié)點地位平等,，無需設(shè)置任何的中心控制節(jié)點。對于Ad Hoc網(wǎng)絡(luò)而言,，路由協(xié)議算法是最關(guān)鍵的技術(shù),。目前存在的Ad Hoc網(wǎng)絡(luò)路由協(xié)議分為表驅(qū)動路由協(xié)議和按需路由協(xié)議兩種。近年來,，對于DSR協(xié)議已經(jīng)做了一系列研究,，DSR協(xié)議的不足有：(1)用于路由發(fā)現(xiàn)的控制報文會波及全網(wǎng)各節(jié)點，耗費(fèi)較大,；(2)路由響應(yīng)風(fēng)暴問題,，源節(jié)點會同時收到多個路由響應(yīng),，造成了響應(yīng)沖突；(3)無效緩存路由問題,，過期的路由信息會傳染其他節(jié)點,。目前的研究結(jié)果主要有：莊春梅等[2]提出了DSR的鄰居表結(jié)構(gòu)，根據(jù)節(jié)點狀態(tài)縮短路由,，同時節(jié)點通過延遲轉(zhuǎn)發(fā)路由發(fā)現(xiàn)包的時間來選擇生存時間長的路由,；AYUB J等[3]用一組參數(shù)描述節(jié)點的運(yùn)動規(guī)律，論述了基于鏈路穩(wěn)定性評估的路由協(xié)議的研究,；Chen Jiaxu等[4]采用節(jié)點局部自適應(yīng)機(jī)制,，對于路由斷路繞遠(yuǎn)等問題進(jìn)行自動恢復(fù)調(diào)整，對DSR協(xié)議的緩存機(jī)制進(jìn)行了改進(jìn),；TAMILARASI M等[5]提出了節(jié)點局部自適應(yīng)機(jī)制,，對于路由斷路繞遠(yuǎn)等問題進(jìn)行自動恢復(fù)調(diào)整；Zhou Nianjun等[6]針對DSR協(xié)議傳輸報文時,，遇到阻塞的路由開銷進(jìn)行了改進(jìn),；李學(xué)橋等[7]提出了分布式的緩存更新機(jī)制，讓各個節(jié)點異步地保持最新路由信息,。但是上述文獻(xiàn)中考慮的只是對已有路由失效后的策略,，并未避免路由響應(yīng)沖突問題。  
1 DSR協(xié)議
    DSR協(xié)議是一種基于源路由方式的按需路由協(xié)議,，主要包括路由發(fā)現(xiàn)和路由維護(hù)兩個過程,。當(dāng)源節(jié)點有報文發(fā)送要求時，首先檢查自己的緩存里是否有到達(dá)目的節(jié)點的路由,，若存在則直接使用,，否則發(fā)送r_req路由請求消息。當(dāng)中間節(jié)點接收到r_req時,，檢查是否收到過此消息,，若收到過則停止轉(zhuǎn)發(fā)，并回復(fù)路由響應(yīng),；若沒有,，則先檢查自己緩存中是否有到達(dá)目的節(jié)點的路由，若有則加入該路由并返回r_rep,，若沒有則將自己的地址加到r_req再轉(zhuǎn)發(fā)此r_req,，直到源節(jié)點成功地接收到路由響應(yīng)信息r_rep。在傳輸報文過程中,，當(dāng)中間節(jié)點檢測到通往目的節(jié)點的下一跳鏈路中斷時,，它將從自己的緩存中刪去包含該鏈路的路由并向源節(jié)點返回一個r_err出錯分組，源節(jié)點收到r_err后,，重新進(jìn)行路由發(fā)現(xiàn),。Fu Z等[8]測試了TCP協(xié)議代理下的傳輸吞吐量與報文丟失的數(shù)據(jù),，發(fā)現(xiàn)DSR協(xié)議在吞吐量方面有缺陷。
    由于無線廣播信道的特點,，節(jié)點可以處于“混合監(jiān)聽”狀態(tài),，這樣會出現(xiàn)“隱終端”問題，會產(chǎn)生報文響應(yīng)沖突,，進(jìn)而造成傳輸阻塞,。
2 基于沖突避免的優(yōu)化
2.1 優(yōu)化的算法
    本文提出的優(yōu)化建立在DSR協(xié)議已有的路由緩存機(jī)制上，因為節(jié)點處于移動狀態(tài),，某節(jié)點在某一時刻可能正在運(yùn)動,，也可能停止不動，并且運(yùn)動的速度也有大有小,。主要目標(biāo)是針對DSR協(xié)議的路由尋找與路由回復(fù)階段產(chǎn)生的響應(yīng)沖突問題,。
    本文為網(wǎng)絡(luò)中節(jié)點的路由表添加一個用于反饋的“緩存路由跳數(shù)”參數(shù)。各節(jié)點自有的緩存路由不會長時間有效,，根據(jù)運(yùn)動速度的大小和停留時間確定緩存路由的有效期,。在有效期內(nèi),，源節(jié)點或中間節(jié)點向下一節(jié)點發(fā)送路由請求后,，可能會收到兩個或多個中間節(jié)點的路由響應(yīng)，這時,，發(fā)送路由請求的節(jié)點查看收到的路由響應(yīng)對應(yīng)的緩存路由跳數(shù)值,，并選擇最小者的路由信息。一旦超過有效期,，節(jié)點就啟動路由緩存更新,，重新進(jìn)行路由發(fā)現(xiàn)，并刪除無效路由信息,。如圖1,、圖2所示，經(jīng)過改進(jìn)的路由請求報文r_req比原有的r_req增加的字段有緩存路由跳數(shù)m和緩存路由有效期TTL,。

    改進(jìn)后的協(xié)議DSR-BCA(DSR based on Collision Avoi-
dance)運(yùn)作方式如下：
    (1)如果源節(jié)點S的下一節(jié)點就是目的節(jié)點D,，則節(jié)點D直接填充路由請求記錄字段，緩存此路由,，記錄跳數(shù)m=1,，并回復(fù)r_rep報文；否則轉(zhuǎn)到步驟(2),；
    (2)源節(jié)點S的下一節(jié)點是中間節(jié)點,，中間節(jié)點在收到r_req報文后，查看若發(fā)現(xiàn)自己的緩存路由信息中已有到達(dá)目的節(jié)點的路由,，則直接回復(fù)r_rep報文,，這樣減少了路由請求消息的廣播,，否則轉(zhuǎn)到步驟(3)；
    (3)源節(jié)點S的下一節(jié)點是中間節(jié)點,，且r_req報文中的源節(jié)點地址請求類型ID存在于此中間節(jié)點的序列對列表中,，表明此r_req報文已經(jīng)收到過，此中間節(jié)點不需處理該請求,；否則轉(zhuǎn)到步驟(4),；
    (4)如果中間節(jié)點的地址已在r_req報文的路由請求記錄字段中，表明經(jīng)過此中間節(jié)點的路由跳數(shù)必不是最小的,，回復(fù)一個r_rep報文給上一節(jié)點,，通知其再尋找下一跳節(jié)點；否則轉(zhuǎn)到步驟(5),；
    (5)如果此中間節(jié)點不滿足步驟(3)和步驟(4),，則將自己的地址添加到路由請求記錄字段，然后向鄰節(jié)點廣播該路由請求,，此中間節(jié)點仍然要緩存這個路由信息,，記錄跳數(shù)；然后轉(zhuǎn)到步驟(6),；
    (6)若r_req報文經(jīng)過轉(zhuǎn)發(fā)到達(dá)了目的節(jié)點D,，則報文中的路由請求記錄字段中節(jié)點地址序列構(gòu)成了從源節(jié)點S到目的節(jié)點D的完整路由信息，節(jié)點D會緩存此信息,，記錄跳數(shù),，并回復(fù)r_rep報文。
    (7)在路由維護(hù)階段,，對于不同運(yùn)動速度的節(jié)點,，設(shè)置不同的TTL。當(dāng)節(jié)點運(yùn)動速度大時,，它附近網(wǎng)絡(luò)的拓?fù)渥兓涂?，緩存路由的TTL就小,；反之則大,。一旦時長達(dá)到TTL，參與報文傳輸?shù)墓?jié)點丟棄原有的路由信息,，再次啟動路由發(fā)現(xiàn)過程,。

    dsrbca_bitreq只比dsr_bitreq多了兩個字段，即2 bit,，而n可達(dá)到101或102,，故BDSR>>BDSR-BCA。
3 仿真分析與性能比較
3.1 仿真平臺與性能指標(biāo)
    本文使用NS2 version 2.35仿真平臺[9]，操作系統(tǒng)為Red Flag Linux 6.0,。在仿真前要配置節(jié)點參數(shù),，利用仿真結(jié)果進(jìn)行性能分析。性能指標(biāo)有以下3個：平均傳輸時延,，指從源節(jié)點發(fā)出一個分組到目的節(jié)點接收到此分組的時間間隔的平均值,；分組投遞率，指目的節(jié)點接收到的報文數(shù)與源節(jié)點發(fā)送的報文數(shù)之比,；歸一化路由開銷,，指平均每發(fā)送一個分組所需要的路由控制分組數(shù)占總分組數(shù)的比例。
3.2 仿真場景設(shè)置與結(jié)果分析
    利用NS2仿真平臺對優(yōu)化前后的協(xié)議性能進(jìn)行測試,。節(jié)點運(yùn)動模型采用Random Way Point模型,，仿真平臺的參數(shù)設(shè)置如表1所示。

     如圖4所示,，隨著節(jié)點的運(yùn)動速度增大,，DSR和DSR-BCA協(xié)議的分組投遞率緩慢減小。這是因為失效路由增多,，有用的數(shù)據(jù)傳輸受到的阻礙也會變大,，源節(jié)點發(fā)送的報文也隨之丟失。從圖中可以看出,，節(jié)點運(yùn)動速度在15 m/s以內(nèi)時,，分組投遞率可以在98%以上，在這個指標(biāo)上,，DSR-BCA比DSR的性能只是提高了一點,。

    如圖5所示,，隨著節(jié)點的運(yùn)動速度增大,，DSR和DSR-BCA協(xié)議的歸一化路由開銷都在增加。隨著網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化,，路由更新的次數(shù)增多,，用于路由維護(hù)的控制報文也增多了。DSR-BCA協(xié)議的路由維護(hù)過程的額外耗費(fèi)比DSR協(xié)議的少,，在節(jié)點移動速度達(dá)到40 m/s時可以少約18%,，速度越大越明顯。

    Ad Hoc網(wǎng)絡(luò)因其節(jié)點具有移動,、無中心,、多跳的特點，從而導(dǎo)致了網(wǎng)絡(luò)拓?fù)涞膭討B(tài)變化,，因此路由協(xié)議的研究一直是熱點與難點,。DSR協(xié)議作為按需路由的一種，其現(xiàn)有的路由機(jī)制仍然有一些缺陷，如路由響應(yīng)風(fēng)暴問題,、失效路由問題,。本文提出了緩存路由有效期、緩存路由跳數(shù)的概念并將其應(yīng)用到DSR協(xié)議中優(yōu)化,。NS2仿真結(jié)果表明,，DSR-BCA的性能比DSR的優(yōu)越。
參考文獻(xiàn)
[1] 鄭少仁,，王海濤,，趙志峰，等.Ad Hoc網(wǎng)絡(luò)技術(shù)[M].北京：人民郵電出版社,，2005：1-48.
[2] 莊春梅,，王利利，陸建德.DSR協(xié)議的路由緩存策略[J]. 計算機(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,，F(xiàn)u 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] 李學(xué)橋,，趙磊,，賈小愛，等.DSR協(xié)議Cache管理策略的優(yōu)化[J].通信技術(shù),，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網(wǎng)絡(luò)模擬器的原理和應(yīng)用[M].西安：西北工業(yè)大學(xué)出版社,，2008：30-56.