潘小清，王曉喃

（1.蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215000；2.常熟理工學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 常熟 215500）

按需路由協(xié)議AODV與DSR的對(duì)比分析

潘小清1，2，王曉喃2

（1.蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215000；
2.常熟理工學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 常熟 215500）

為了研究Ad Hoc網(wǎng)絡(luò)中的按需路由協(xié)議的性能，基于NS2仿真平臺(tái)，研究分析了移動(dòng)速度對(duì)兩種典型按需路由協(xié)議AODV和DSR的性能影響，并對(duì)DSR協(xié)議進(jìn)行了改進(jìn).性能參數(shù)包括分組投遞率、端到端的平均時(shí)延、路由發(fā)起率、歸一化路由開(kāi)銷(xiāo)等性能.仿真結(jié)果表明，DSR協(xié)議在移動(dòng)環(huán)境下的性能較好，并且改進(jìn)后的DSR協(xié)議在分組投遞率、端到端時(shí)延方面均優(yōu)于原DSR協(xié)議.

AODV；DSR；網(wǎng)絡(luò)仿真；NS2

Ad Hoc網(wǎng)絡(luò)中的移動(dòng)節(jié)點(diǎn)既作為路由器又作為主機(jī)，不依靠現(xiàn)有固定通信網(wǎng)絡(luò)基礎(chǔ)設(shè)施就能迅速工作.Ad Hoc是一種無(wú)任何中心實(shí)體、自組織的網(wǎng)絡(luò)，其路由協(xié)議作為反映Ad Hoc網(wǎng)絡(luò)性能的一個(gè)重要元素，其性能至關(guān)重要.

Ad Hoc的一個(gè)重要特點(diǎn)就是節(jié)點(diǎn)具有移動(dòng)性，節(jié)點(diǎn)的移動(dòng)速度對(duì)Ad Hoc路由協(xié)議性能的影響十分重要，因此本文從節(jié)點(diǎn)移動(dòng)速度角度對(duì)兩種典型的Ad Hoc路由協(xié)議AODV和DSR進(jìn)行了仿真比較，從而分析這兩種協(xié)議的優(yōu)缺點(diǎn)，并針對(duì)DSR協(xié)議的不足進(jìn)行了相應(yīng)的改進(jìn).

1 Ad Hoc網(wǎng)絡(luò)路由協(xié)議

Ad Hoc的路由協(xié)議大致由兩類(lèi)構(gòu)成：一類(lèi)為表格驅(qū)動(dòng)類(lèi)路由協(xié)議，而另一類(lèi)為源節(jié)點(diǎn)初始化按需驅(qū)動(dòng)類(lèi)路由協(xié)議.表格驅(qū)動(dòng)類(lèi)路由協(xié)議要求每個(gè)節(jié)點(diǎn)建立以及維護(hù)一張或多張存儲(chǔ)路由信息的表格，這類(lèi)協(xié)議包括最優(yōu)鏈路狀態(tài)路由協(xié)議（Optim ized LinkState Routing，OLSR），目的序列距離矢量路由協(xié)議（Destination-Sequenced Distance-Vector Routing，DSDV）等.按需路由協(xié)議與表格驅(qū)動(dòng)類(lèi)路由協(xié)議有所不同，按需路由協(xié)議是在源節(jié)點(diǎn)需要與目的節(jié)點(diǎn)進(jìn)行通信時(shí)建立路由，該類(lèi)路由協(xié)議包括動(dòng)態(tài)源路由協(xié)議（Dynamic Source Routing，DSR），按需距離適量路由協(xié)議（Ad-Hoc On-Demand Distance Vector，AODV）等.

Ad Hoc的一個(gè)重要特點(diǎn)就是節(jié)點(diǎn)具有移動(dòng)性，節(jié)點(diǎn)的移動(dòng)速度對(duì)Ad Hoc路由協(xié)議性能的影響十分重要，因此本文從節(jié)點(diǎn)移動(dòng)速度角度對(duì)兩種典型的Ad Hoc路由協(xié)議AODV和DSR進(jìn)行了仿真比較，目的在于比較這兩種協(xié)議在最大移動(dòng)速度變化的場(chǎng)景下的性能.

AODV協(xié)議包括路由建立和路由維護(hù)兩個(gè)部分，在建立路由的過(guò)程中，當(dāng)其中的一個(gè)節(jié)點(diǎn)需要將數(shù)據(jù)傳

送到另一個(gè)新的目標(biāo)節(jié)點(diǎn)時(shí)，便廣播一條RREQ消息，尋找一條到達(dá)該目的節(jié)點(diǎn)的路由.當(dāng)一個(gè)節(jié)點(diǎn)接收到一個(gè)RREQ分組后，首先建立或者更新到達(dá)沒(méi)有有效序列號(hào)的前一跳的路由，然后確定自己在路徑查找時(shí)間內(nèi)是否收到過(guò)相同源節(jié)點(diǎn)的IP地址和相同RREQ ID的RREQ分組.若該節(jié)點(diǎn)已接收過(guò)此分組則將該分組丟棄.當(dāng)目的節(jié)點(diǎn)或具有足夠新的到達(dá)該目的節(jié)點(diǎn)的路由的中間節(jié)點(diǎn)接收到該RREQ消息時(shí)，該節(jié)點(diǎn)就照單目標(biāo)方式給該RREQ消息源節(jié)點(diǎn)回送一條RREP消息，這條路由則變成有效路由.在路由維護(hù)中，當(dāng)一條正在使用的路由中發(fā)生鏈路中斷時(shí)，若發(fā)生中斷的節(jié)點(diǎn)與目的節(jié)點(diǎn)的距離在最大修復(fù)長(zhǎng)度跳內(nèi)，那么中斷處的上行節(jié)點(diǎn)將選擇本地修復(fù)該中斷鏈，若在查找周期結(jié)束時(shí)，目的節(jié)點(diǎn)回送的RREP分組仍沒(méi)有被修復(fù)節(jié)點(diǎn)接受，一條路由錯(cuò)誤RERR消息會(huì)被廣播，同時(shí)源節(jié)點(diǎn)會(huì)重新發(fā)起路由發(fā)現(xiàn)過(guò)程.

在DSR初始化路由查找過(guò)程中，源節(jié)點(diǎn)以一個(gè)單獨(dú)本地廣播分組方式發(fā)送一個(gè)RREQ消息.當(dāng)RREQ消息被一個(gè)節(jié)點(diǎn)接收到時(shí)，若同時(shí)此節(jié)點(diǎn)就是本次路由查找的目的節(jié)點(diǎn)，那么該節(jié)點(diǎn)將回送一個(gè)路由應(yīng)答給本次路由查找的源節(jié)點(diǎn).當(dāng)源節(jié)點(diǎn)接收到路由應(yīng)答后，這條路由會(huì)被存儲(chǔ)在對(duì)應(yīng)的路由存儲(chǔ)器里.否則，此節(jié)點(diǎn)會(huì)將本地地址添加到此次路由請(qǐng)求的路由記錄列表中，然后以本地廣播分組方式發(fā)送該路由請(qǐng)求，從而找到一條到達(dá)目的節(jié)點(diǎn)的路由.若該節(jié)點(diǎn)已接收到源節(jié)點(diǎn)的另一個(gè)路由請(qǐng)求或發(fā)現(xiàn)自己的地址已在路由記錄表中，該路由請(qǐng)求會(huì)被丟棄.在路由維護(hù)中，當(dāng)源節(jié)點(diǎn)正在使用一條到達(dá)目的節(jié)點(diǎn)的源路由時(shí)，如果網(wǎng)絡(luò)拓?fù)浒l(fā)生變化，導(dǎo)致源節(jié)點(diǎn)正在使用的那條到達(dá)目的節(jié)點(diǎn)的源路由上一條鏈路已經(jīng)不再起作用，為了將數(shù)據(jù)分組傳輸給目的節(jié)點(diǎn)，源節(jié)點(diǎn)將使用任何一條已獲知的路由，或者重新調(diào)用路由查找機(jī)制找到一條新路由.

2 仿真實(shí)驗(yàn)

我們對(duì)按需路由協(xié)議中的兩個(gè)典型的協(xié)議AODV和DSR的性能進(jìn)行了分析比較，并將改進(jìn)后的DSR和原DSR的性能進(jìn)行對(duì)比分析.

我們采用NS2作為AODV和DSR協(xié)議仿真平臺(tái).NS2是一個(gè)通用多協(xié)議網(wǎng)絡(luò)模擬軟件.它是由C++構(gòu)造仿真部件，由OTCL腳本驅(qū)動(dòng).NS2中的無(wú)線模塊主要包括信道，網(wǎng)絡(luò)接口，無(wú)線信號(hào)傳輸模塊、MAC協(xié)議、接口隊(duì)列、鏈路層、地址解析協(xié)議等構(gòu)件，本實(shí)驗(yàn)采用NS2.34.

本次仿真中，采用的業(yè)務(wù)流為CBR，MAC協(xié)議采用802.11，采用Two-ray ground reflection的網(wǎng)絡(luò)傳輸模型，接口隊(duì)列AODV協(xié)議采用的是PriQueue的隊(duì)列類(lèi)型，DSR協(xié)議采用的是CMUPriQueue的隊(duì)列類(lèi)型.

考慮從節(jié)點(diǎn)最大移動(dòng)速度方面對(duì)協(xié)議性能的影響來(lái)設(shè)置仿真場(chǎng)景，節(jié)點(diǎn)運(yùn)動(dòng)的最大速度分別為0 m/s，2 m/s，7 m/s，12 m/s，17 m/s，22 m/s，節(jié)點(diǎn)暫停時(shí)間為1 s，網(wǎng)絡(luò)中有10對(duì)通信連接、每秒鐘發(fā)送兩個(gè)CBR數(shù)據(jù)流，每個(gè)數(shù)據(jù)包長(zhǎng)度為512 byte，所有仿真區(qū)域?yàn)?000 m×300 m的長(zhǎng)方形，具有50個(gè)移動(dòng)節(jié)點(diǎn)，仿真時(shí)間300 s.

按需路由協(xié)議中的各個(gè)協(xié)議都有各自的優(yōu)缺點(diǎn)，為了更好的判斷AODV和DSR路由協(xié)議在不同最大速度影響下的性能，本文從分組投遞率，端到端的平均時(shí)延，歸一化路由開(kāi)銷(xiāo)和路由發(fā)起率四個(gè)性能參數(shù)著手，研究這兩種協(xié)議的性能.

路由發(fā)起率如圖1所示，當(dāng)節(jié)點(diǎn)的最大移動(dòng)速度較小，即網(wǎng)絡(luò)狀態(tài)不劇烈的情況下，AODV的路由發(fā)起率比DSR協(xié)議的路由發(fā)起率高.在移動(dòng)速度低時(shí)，鏈路中斷率低.但是，節(jié)點(diǎn)常常會(huì)成群的低速移動(dòng)，由此導(dǎo)致網(wǎng)絡(luò)中某個(gè)區(qū)域出現(xiàn)重流量，發(fā)生網(wǎng)絡(luò)擁塞.擁塞反過(guò)來(lái)會(huì)導(dǎo)致鏈路層反饋，即使節(jié)點(diǎn)相對(duì)靜止、節(jié)點(diǎn)之間存在物理鏈路，鏈路層仍然會(huì)報(bào)告鏈路中斷.在AODV中鏈路中斷導(dǎo)致調(diào)用新的路由尋找過(guò)程，因此在移動(dòng)速度低的情況下AODV的路由發(fā)起率比DSR高.隨著移動(dòng)節(jié)點(diǎn)的速度增大，AODV路由協(xié)議的路由發(fā)起率比DSR協(xié)議高，并且變化劇烈.在高速移動(dòng)下，鏈路中斷可能頻繁

發(fā)生，在AODV中，路由表中為每個(gè)目的節(jié)點(diǎn)最多存儲(chǔ)一條路由，所以鏈路中斷導(dǎo)致新的路由建立頻繁發(fā)生，而DSR為每個(gè)節(jié)點(diǎn)存儲(chǔ)多個(gè)路由，因此在鏈路中斷時(shí)路由建立的頻率低于AODV.

分組投遞率如圖2所示，隨著節(jié)點(diǎn)的最大移動(dòng)速度的增加，DSR路由協(xié)議和AODV協(xié)議的分組投遞率都在減少，DSR路由協(xié)議的減少速度比AODV協(xié)議平緩，且DSR的分組投遞率比AODV高.在高速移動(dòng)下，鏈路中斷頻繁發(fā)生，AODV協(xié)議中，路由表為每個(gè)目的節(jié)點(diǎn)最多存儲(chǔ)一條路由，因此AODV的鏈路中斷會(huì)導(dǎo)致分組投遞率急劇下降.DSR為每個(gè)節(jié)點(diǎn)存儲(chǔ)多條路由，DSR利用存儲(chǔ)路由，產(chǎn)生的鏈路中斷沒(méi)有AODV那樣頻繁，因此分組投遞率下降的較為平緩，且高于AODV.

歸一化路由開(kāi)銷(xiāo)如圖3所示.隨著節(jié)點(diǎn)的最大移動(dòng)速度的增加，DSR路由協(xié)議和AODV協(xié)議的歸一化開(kāi)銷(xiāo)都呈現(xiàn)出增加的趨勢(shì)，同時(shí)AODV協(xié)議的歸一化路由開(kāi)銷(xiāo)增加迅速，且一直都比DSR協(xié)議高.DSR中使用源路由，訪問(wèn)的路由信息明顯多于AODV.在DSR中，在一個(gè)路由請(qǐng)求與路由應(yīng)答過(guò)程中，源節(jié)點(diǎn)不僅能夠獲得到達(dá)目的節(jié)點(diǎn)，同時(shí)還能獲得到達(dá)路由上每個(gè)中間節(jié)點(diǎn)的路由，并且每個(gè)中間節(jié)點(diǎn)也可以獲得此次路由上的其他中間節(jié)點(diǎn)的路由.通過(guò)混合收聽(tīng)數(shù)據(jù)分組發(fā)送方式，DSR可以獲取大量路由信息并且建立到達(dá)源路由上每個(gè)節(jié)點(diǎn)的路由.由于AODV中既沒(méi)有源路由，也不采取混合收聽(tīng)方式，并且路由獲取只受被轉(zhuǎn)發(fā)的路由分組的源節(jié)點(diǎn)限制，因此AODV只能收集有限的路由信息并且更加頻繁地依靠網(wǎng)絡(luò)泛洪來(lái)尋找路由，最終增加了網(wǎng)絡(luò)開(kāi)銷(xiāo).

端到端的平均時(shí)延如圖4所示，在節(jié)點(diǎn)的移動(dòng)速度較小時(shí)，AODV路由協(xié)議的端到端平均時(shí)延比DSR協(xié)議高，隨著移動(dòng)速度增加，AODV路由協(xié)議的端到端平均時(shí)延增加緩慢，且比DSR協(xié)議的低.AODV自動(dòng)優(yōu)先選擇擁塞最輕的路由而不是選擇最短路由.而DSR主動(dòng)利用存儲(chǔ)路由，DSR存儲(chǔ)路由在移動(dòng)性較弱時(shí)能夠明顯提高路由性能，但對(duì)于移動(dòng)性較強(qiáng)的網(wǎng)絡(luò)，由于路由更新頻繁，因此路由存儲(chǔ)的作用有限.此外，DSR選擇路由長(zhǎng)度作為存儲(chǔ)路由的唯一度量參數(shù)，并未考慮路由的新鮮程度，所以經(jīng)常選擇過(guò)時(shí)的失效路由，盡管最終分組被丟棄或者被推遲，但是消耗了額外的接口排隊(duì)時(shí)間和網(wǎng)絡(luò)帶寬.

3 改進(jìn)的DSR協(xié)議

針對(duì)DSR協(xié)議存在的不足，實(shí)驗(yàn)對(duì)DSR協(xié)議進(jìn)行了相應(yīng)的改進(jìn).本方案路由最后一跳的路由建立時(shí)間為ta，路由中間節(jié)點(diǎn)的路由建立時(shí)間為t，其中ta為t的最大值；記錄相鄰節(jié)點(diǎn)從路由建立到失效的時(shí)間為路由生存時(shí)間tb，路由剩余生存時(shí)間tc=tb-（td-ta），td為當(dāng)前時(shí)間.在進(jìn)行路徑選擇時(shí)，首先選擇路由長(zhǎng)度最短的路徑，若此類(lèi)路徑多于一條則選擇tc值最大的路徑.當(dāng)路由緩存器滿時(shí)，刪除tc值最小的路徑，本文對(duì)改進(jìn)后的DSR協(xié)議和原協(xié)議進(jìn)行了仿真.其中dsr1為原協(xié)議dsr2為改進(jìn)后的協(xié)議.

如圖5所示，改進(jìn)后協(xié)議的端到端平均時(shí)延比原協(xié)議的有所降低，其原因是改進(jìn)后的協(xié)議不僅將路由跳數(shù)作為度量參數(shù)，同時(shí)還考慮了路由的剩余生存時(shí)間，從而提高了路由質(zhì)量，減少了因選擇過(guò)時(shí)路由而產(chǎn)生的時(shí)延.

如圖6所示，改進(jìn)后協(xié)議的分組投遞率比原協(xié)議的分組投遞率有所提高.在仿真環(huán)境配置一樣的情況下，改進(jìn)的DSR協(xié)議能夠選擇跳數(shù)少且剩余生存時(shí)間高的路由，減少了因選擇過(guò)時(shí)路由而導(dǎo)致的時(shí)延，同時(shí)也減少了因選擇過(guò)時(shí)路由所導(dǎo)致的數(shù)據(jù)分組的丟失，從而提高了分組投遞率.

4 結(jié)束語(yǔ)

Ad Hoc的一個(gè)重要特點(diǎn)就是節(jié)點(diǎn)具有移動(dòng)性，節(jié)點(diǎn)的移動(dòng)速度對(duì)Ad Hoc路由協(xié)議性能的影響十分重要，因此本文從節(jié)點(diǎn)移動(dòng)速度角度對(duì)兩種典型的Ad Hoc路由協(xié)議AODV和DSR進(jìn)行了仿真比較，從而分析這兩種協(xié)議的優(yōu)缺點(diǎn)，并針對(duì)DSR協(xié)議存在的不足進(jìn)行了改進(jìn)，改進(jìn)后協(xié)議的分組投遞率和端到端平均時(shí)延等性能優(yōu)于原DSR協(xié)議，為維護(hù)網(wǎng)絡(luò)和提高網(wǎng)絡(luò)的健壯性提供參考.

[1]柯志亨，成榮祥，鄧德雋.NS2仿真實(shí)驗(yàn)：多媒體和無(wú)線網(wǎng)絡(luò)通信[M].北京：電子工業(yè)出版社，2009.

[2]Khatawkar SD,Pandyaji K K,Patil R M,et al.Performance Comparison of DSDV,AODV,DSR Routing Protocols for MANETs[J]. International Conference of Computer Network sand Communication System,2012,35.

[3]張鵬，崔勇.移動(dòng)自組織網(wǎng)絡(luò)路由選擇算法研究進(jìn)展[J].計(jì)算機(jī)科學(xué)，2010，37（01）.

[4]王琦進(jìn)，齊曉霞，候整風(fēng).移動(dòng)Ad Hoc網(wǎng)絡(luò)路由協(xié)議性能仿真研究[J].微計(jì)算機(jī)信息，2011（4）.

[5]徐雷鳴，龐博，趙耀.NS與網(wǎng)絡(luò)模擬[M].北京：人民郵電出版社，2003.

[6]陳林星，曾曦，曹毅.移動(dòng)Ad Hoc網(wǎng)絡(luò)：自組織分組無(wú)線網(wǎng)絡(luò)技術(shù)[M].北京：電子工業(yè)出社，2012.

[7]藺紹良，龍海南.Ad Hoc網(wǎng)絡(luò)路由協(xié)議綜述[J].電子設(shè)計(jì)工程，2013，21（09）.

[8]劉利強(qiáng)，王岳斌.無(wú)線網(wǎng)絡(luò)路由協(xié)議性能的研究與仿真[J].電子技術(shù)，2013（2）.

[9]Parma Nand.Performance study of Broadcastbased Mobile Adhoc Routing Protocols AODV,DSR and DYMO[J].International Journal of Security and Its App lications,2011,5(1).

[10]張大亮，陳濤，黃琳.移動(dòng)Ad Hoc網(wǎng)絡(luò)中AODV和DSR路由協(xié)議的性能對(duì)比[J].湖北師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2013，（1）.

An Analysis of On-dem and Routing Protocol AODV and DSR

PAN Xiao-qing1,2,WANG Xiao-nan2
(1.School of Computer Science and Technology,Soochow University,Suzhou 215000,China;
2.School of Computer Science and Engineering,Changsu Institute of Technology,Changshu 215500,China)

In order to study the effect of the speed on the performance of the on-demand routing protocols in Ad Hoc network,two typical routing protocols AODV and DSR are simulated in NS-2 simulation p latform and an improved DSR is proposed.The performance parameters include packet delivery ratio,average end-to-end delay,routing rate,and normalized routing overhead.Simulation results demonstrate that DSR has a better performance and that the improved DSR is superior to the original on packet delivery ratio and average end-to-end delay.

AODV;DSR;network simulation

TP393.04

A

1008-2794（2014）04-0083-04

2013-12-02

國(guó)家自然科學(xué)基金項(xiàng)目“基于IPv6的全I(xiàn)P無(wú)線傳感器網(wǎng)絡(luò)關(guān)鍵技術(shù)研究”（61202440）

王曉喃，副教授，博士，碩士生導(dǎo)師，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)與應(yīng)用，E-mail：wxn_2001@163.com.