《電子技術(shù)應(yīng)用》
您所在的位置:首頁(yè) > 通信與網(wǎng)絡(luò) > 設(shè)計(jì)應(yīng)用 > 基于沖突避免的DSR協(xié)議研究
基于沖突避免的DSR協(xié)議研究
來(lái)源:微型機(jī)與應(yīng)用2013年第16期
梁建武1,徐龍龍1,徐建明2
(1.中南大學(xué) 信息科學(xué)與工程學(xué)院,湖南 長(zhǎng)沙410075;2.長(zhǎng)江大學(xué) 電子信息學(xué)院,湖北 荊州4
摘要: 基于自適應(yīng)移動(dòng)多跳Ad Hoc網(wǎng)絡(luò),針對(duì)其DSR協(xié)議的路由緩存機(jī)制,分析不足之處,探索對(duì)現(xiàn)有的路由緩存機(jī)制的優(yōu)化方法。提出了緩存路由有效期的概念,為網(wǎng)絡(luò)中節(jié)點(diǎn)的路由表添加一個(gè)用于反饋的“緩存路由跳數(shù)”參數(shù),節(jié)點(diǎn)選擇此參數(shù)值最小者的路由信息。仿真實(shí)驗(yàn)表明,經(jīng)過(guò)改進(jìn)的緩存機(jī)制有效地避免了響應(yīng)沖突問(wèn)題,實(shí)現(xiàn)了路由的最短優(yōu)化,在平均傳輸延遲、分組投遞率、吞吐量性能方面都有提高。
Abstract:
Key words :

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

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

    本文提出的優(yōu)化建立在DSR協(xié)議已有的路由緩存機(jī)制上,因?yàn)楣?jié)點(diǎn)處于移動(dòng)狀態(tài),某節(jié)點(diǎn)在某一時(shí)刻可能正在運(yùn)動(dòng),也可能停止不動(dòng),并且運(yùn)動(dòng)的速度也有大有小。主要目標(biāo)是針對(duì)DSR協(xié)議的路由尋找與路由回復(fù)階段產(chǎn)生的響應(yīng)沖突問(wèn)題。
    本文為網(wǎng)絡(luò)中節(jié)點(diǎn)的路由表添加一個(gè)用于反饋的“緩存路由跳數(shù)”參數(shù)。各節(jié)點(diǎn)自有的緩存路由不會(huì)長(zhǎng)時(shí)間有效,根據(jù)運(yùn)動(dòng)速度的大小和停留時(shí)間確定緩存路由的有效期。在有效期內(nèi),源節(jié)點(diǎn)或中間節(jié)點(diǎn)向下一節(jié)點(diǎn)發(fā)送路由請(qǐng)求后,可能會(huì)收到兩個(gè)或多個(gè)中間節(jié)點(diǎn)的路由響應(yīng),這時(shí),發(fā)送路由請(qǐng)求的節(jié)點(diǎn)查看收到的路由響應(yīng)對(duì)應(yīng)的緩存路由跳數(shù)值,并選擇最小者的路由信息。一旦超過(guò)有效期,節(jié)點(diǎn)就啟動(dòng)路由緩存更新,重新進(jìn)行路由發(fā)現(xiàn),并刪除無(wú)效路由信息。如圖1、圖2所示,經(jīng)過(guò)改進(jìn)的路由請(qǐng)求報(bào)文r_req比原有的r_req增加的字段有緩存路由跳數(shù)m和緩存路由有效期TTL。

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

 


    dsrbca_bitreq只比dsr_bitreq多了兩個(gè)字段,即2 bit,而n可達(dá)到101或102,故BDSR>>BDSR-BCA。
3 仿真分析與性能比較
3.1 仿真平臺(tái)與性能指標(biāo)

    本文使用NS2 version 2.35仿真平臺(tái)[9],操作系統(tǒng)為Red Flag Linux 6.0。在仿真前要配置節(jié)點(diǎn)參數(shù),利用仿真結(jié)果進(jìn)行性能分析。性能指標(biāo)有以下3個(gè):平均傳輸時(shí)延,指從源節(jié)點(diǎn)發(fā)出一個(gè)分組到目的節(jié)點(diǎn)接收到此分組的時(shí)間間隔的平均值;分組投遞率,指目的節(jié)點(diǎn)接收到的報(bào)文數(shù)與源節(jié)點(diǎn)發(fā)送的報(bào)文數(shù)之比;歸一化路由開(kāi)銷,指平均每發(fā)送一個(gè)分組所需要的路由控制分組數(shù)占總分組數(shù)的比例。
3.2 仿真場(chǎng)景設(shè)置與結(jié)果分析
    利用NS2仿真平臺(tái)對(duì)優(yōu)化前后的協(xié)議性能進(jìn)行測(cè)試。節(jié)點(diǎn)運(yùn)動(dòng)模型采用Random Way Point模型,仿真平臺(tái)的參數(shù)設(shè)置如表1所示。

     如圖4所示,隨著節(jié)點(diǎn)的運(yùn)動(dòng)速度增大,DSR和DSR-BCA協(xié)議的分組投遞率緩慢減小。這是因?yàn)槭酚稍龆啵杏玫臄?shù)據(jù)傳輸受到的阻礙也會(huì)變大,源節(jié)點(diǎn)發(fā)送的報(bào)文也隨之丟失。從圖中可以看出,節(jié)點(diǎn)運(yùn)動(dòng)速度在15 m/s以內(nèi)時(shí),分組投遞率可以在98%以上,在這個(gè)指標(biāo)上,DSR-BCA比DSR的性能只是提高了一點(diǎn)。

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

    Ad Hoc網(wǎng)絡(luò)因其節(jié)點(diǎn)具有移動(dòng)、無(wú)中心、多跳的特點(diǎn),從而導(dǎo)致了網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)變化,因此路由協(xié)議的研究一直是熱點(diǎn)與難點(diǎn)。DSR協(xié)議作為按需路由的一種,其現(xiàn)有的路由機(jī)制仍然有一些缺陷,如路由響應(yīng)風(fēng)暴問(wèn)題、失效路由問(wèn)題。本文提出了緩存路由有效期、緩存路由跳數(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ì)算機(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é)橋,趙磊,賈小愛(ài),等.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.

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。