王文濤，王 豪，郭 峰，鄭 芳

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢430074)

移動(dòng)無線自組網(wǎng)[1](MANET)由一組無線移動(dòng)節(jié)點(diǎn)組成，是一種不需要依靠現(xiàn)有固定通信網(wǎng)絡(luò)基礎(chǔ)設(shè)施就能夠迅速展開使用的網(wǎng)絡(luò)體系，所需人工干預(yù)最少，是沒有任何中心實(shí)體、自組織、自愈的網(wǎng)絡(luò).MANET網(wǎng)絡(luò)是對(duì)有線網(wǎng)絡(luò)的補(bǔ)充和擴(kuò)展，也是未來一種主要的網(wǎng)絡(luò)接入方式.由于其組網(wǎng)靈活、易于擴(kuò)展，當(dāng)前發(fā)展十分迅猛.目前對(duì)于MANET網(wǎng)絡(luò)的研究主要集中在傳輸方式、組網(wǎng)方式和應(yīng)用層上，其中在組網(wǎng)方式的研究上，路由協(xié)議的研究是個(gè)熱門領(lǐng)域.MANET路由協(xié)議從拓?fù)浞绞絹矸?，主要分為先?yàn)式(proactive)路由協(xié)議和反應(yīng)式(reactive)路由協(xié)議[2].在文獻(xiàn)研究方面，傳統(tǒng)的反應(yīng)式MANET經(jīng)典路由協(xié)議DSDV[3]、DSR[4]和AODV[5]的性能比較研究已經(jīng)完成.文獻(xiàn)[6]在NS2仿真環(huán)境下闡述了AODV、DSR和DYMO協(xié)議的工作原理，文中采用平均時(shí)延、平均跳數(shù)、包傳遞率和路由負(fù)載4個(gè)參數(shù)比較了這3種反應(yīng)式路由協(xié)議，實(shí)驗(yàn)結(jié)果表明DYMO協(xié)議在平均時(shí)延和平均跳數(shù)上優(yōu)于AODV和DSR路由協(xié)議，但在包傳遞率和路由負(fù)載上其性能低于AODV和DSR路由協(xié)議.文獻(xiàn)[7]比較了DSDV、AODV和DSR的數(shù)據(jù)包分組投遞率、平均端到端時(shí)延和路由負(fù)載，指出先驗(yàn)式和反應(yīng)式路由協(xié)議分別適用于何種網(wǎng)絡(luò)環(huán)境，文獻(xiàn)[8]雖然提出了用于嵌入式和多種平臺(tái)的AODV-UU協(xié)議，但是并沒有和同樣用于嵌入式平臺(tái)的DSR-UU和DYMOUM路由協(xié)議進(jìn)行比較分析.目前的研究主要集中在經(jīng)典反應(yīng)式路由協(xié)議的性能仿真比較分析，在和硬件結(jié)合的嵌入式方面的改進(jìn)協(xié)議如AODV-UU、DSR-UU和DYMOUM則沒有進(jìn)行相應(yīng)的仿真比較分析.本文的主要貢獻(xiàn)是，采用OMNeT++網(wǎng)絡(luò)仿真工具，在不同的節(jié)點(diǎn)數(shù)目和移動(dòng)速度情況下，對(duì)這3種協(xié)議的分組投遞率、端到端時(shí)延和路由發(fā)現(xiàn)頻率3個(gè)指標(biāo)進(jìn)行分析比較，為嵌入式Linux環(huán)境下反應(yīng)式MANET路由協(xié)議的橫向比較提供參考.

1 協(xié)議簡介

1.1 AODV-UU

AODV-UU[8]路由協(xié)議是由瑞典烏普薩拉大學(xué)(Uppsala University)和愛立信公司聯(lián)合發(fā)布的一種Ad Hoc網(wǎng)絡(luò)路由協(xié)議.AODV-UU路由協(xié)議是AODV路由協(xié)議在嵌入式Linux系統(tǒng)上的實(shí)現(xiàn)，同時(shí)又對(duì)AODV協(xié)議草案增加了其他功能.例如Hello消息增加了單向鏈路檢測(cè)和沖突避免.由于AODV路由協(xié)議MAC層采用802.11DCF標(biāo)準(zhǔn)，802.11DCF中的廣播信息傳輸速度要低于單播，并且傳輸范圍大于單播，因此，當(dāng)單播信息失敗后，節(jié)點(diǎn)還可能認(rèn)為鏈路是活動(dòng)的，這樣就會(huì)引起報(bào)文錯(cuò)誤率增加.AODV-UU同樣遵循RFC3561[9]路由協(xié)議標(biāo)準(zhǔn)，并且在平均端到端時(shí)延和路由開銷方面的性能要優(yōu)于AODV和AOMDV協(xié)議[10].AODV-UU是基于Netfilter框架實(shí)現(xiàn)的，AODV-UU至今仍在更新，AODV-UU主要包括路由發(fā)現(xiàn)和路由維護(hù)兩部分.路由發(fā)現(xiàn)：當(dāng)Netfilter從端口捕獲輸入或者輸出報(bào)文后，檢查報(bào)文當(dāng)中的目的地址是否在當(dāng)前路由表中，如果在，將報(bào)文放行，否則將報(bào)文放到緩存隊(duì)列中，然后向用戶層的守護(hù)進(jìn)程發(fā)送路由查找消息，如果找到有效路由表則通知緩存模塊，緩存模塊將含有目的地址的報(bào)文重發(fā)，在定時(shí)器時(shí)間內(nèi)如果沒有找到有效路由，此報(bào)文將被丟棄.路由維護(hù)：AODV-UU使用內(nèi)核交互的方式更新內(nèi)核路由表，AODV-UU的內(nèi)核模塊使用Netfilter鉤子來決定包是到來的還是出去的，并且決定它應(yīng)該被接收還是轉(zhuǎn)發(fā)，投遞到Netfilter鉤子上的IP數(shù)據(jù)包會(huì)被捕獲并可以通過添加自定義代碼進(jìn)行修改.

1.2 DSR-UU

DSR-UU[11]是比較經(jīng)典的按需路由協(xié)議的原型，DSR-UU主要由路由尋找和路由維護(hù)兩種機(jī)制組成.

路由尋找：當(dāng)某個(gè)源節(jié)點(diǎn)S產(chǎn)生一個(gè)新分組需要傳輸給目的節(jié)點(diǎn)時(shí)，S就在該分組的分組頭中添加一條源路由，從而給出沿著該條源路由轉(zhuǎn)發(fā)該分組至目的節(jié)點(diǎn)D的轉(zhuǎn)發(fā)跳序列.通常情況下，S通過搜索其路由存儲(chǔ)器(Route Cache)就能夠找到一條合適的源路由，路由存儲(chǔ)器用于存儲(chǔ)其以前獲得的路由.如果S在其路由存儲(chǔ)器中沒有找到任何可用路由，那么S初始化路由尋找協(xié)議來動(dòng)態(tài)地尋找一條到達(dá)D的新路由，并把源節(jié)點(diǎn)S和目的節(jié)點(diǎn)D分別稱為該路由尋找的發(fā)起節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn).

路由維護(hù)：當(dāng)使用一條源路由產(chǎn)生或者轉(zhuǎn)發(fā)一個(gè)分組的時(shí)候，發(fā)送該分組的每個(gè)節(jié)點(diǎn)都要負(fù)責(zé)證實(shí)該分組能夠通過本節(jié)點(diǎn)到達(dá)該條源路由下一跳節(jié)點(diǎn)的鏈.如圖1，節(jié)點(diǎn)A使用一條經(jīng)過中間節(jié)點(diǎn)B、C、D的源路由為節(jié)點(diǎn)E產(chǎn)生一個(gè)分組.節(jié)點(diǎn)C經(jīng)過若干次確認(rèn)請(qǐng)求之后仍然沒有接收到節(jié)點(diǎn)D的確認(rèn)，則認(rèn)為從其到節(jié)點(diǎn)D的鏈已經(jīng)中斷，并且給節(jié)點(diǎn)A以及所有中間節(jié)點(diǎn)回送一個(gè)路由錯(cuò)誤：自C接收到D的最后一個(gè)確認(rèn)以來，這些節(jié)點(diǎn)可能已經(jīng)使用從C到D的鏈.節(jié)點(diǎn)A接收到錯(cuò)誤路由后，從其路由存儲(chǔ)器中刪除中斷鏈；如果需要重傳，分組的重傳由上層協(xié)議(如TCP)執(zhí)行.

圖1 DSR-UU路由維護(hù)

1.3 DYMOUM

DYMOUM[12]并不是AODV-UU協(xié)議的擴(kuò)展，而是將AODV-UU的序列號(hào)、跳數(shù)計(jì)數(shù)和RERR保留，并加入DSR-UU的源路徑積累思想，DYMOUM主要也是由路由發(fā)現(xiàn)和路由維護(hù)兩個(gè)機(jī)制組成.

路由發(fā)現(xiàn)：DYMOUM的路由發(fā)現(xiàn)機(jī)制和DSR-UU的路由發(fā)現(xiàn)機(jī)制類似，當(dāng)一個(gè)節(jié)點(diǎn)需要通信時(shí)，創(chuàng)建一個(gè)到目的節(jié)點(diǎn)的路由.當(dāng)源節(jié)點(diǎn)要和目的節(jié)點(diǎn)通信時(shí)，源節(jié)點(diǎn)廣播RREQ包，直到目的節(jié)點(diǎn)收到RREQ包，目的節(jié)點(diǎn)返回給源節(jié)點(diǎn)RREP包建立反向路由.

路由維護(hù)：與DSR-UU相比，DYMO - UM發(fā)現(xiàn)斷路后會(huì)通知全網(wǎng)中使用該斷裂鏈路的節(jié)點(diǎn)，但沒有在傳輸數(shù)據(jù)的時(shí)候采用源路由，而是僅僅在路由發(fā)現(xiàn)過程中，使用路由控制包攜帶更多路由信息，沒有沿用DSR-UU在數(shù)據(jù)包中攜帶源路由的做法.

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

2.1 仿真場(chǎng)景

實(shí)驗(yàn)采用OMNeT++作為仿真工具，OMNeT++是面向?qū)ο蟮碾x散事件網(wǎng)絡(luò)仿真工具，它使用C++編程，支持OSI七層網(wǎng)絡(luò)結(jié)構(gòu)，與NS-2、OPNET等網(wǎng)絡(luò)仿真軟件相比，OMNeT++能夠運(yùn)行于多個(gè)操作系統(tǒng)平臺(tái)，能夠把網(wǎng)絡(luò)拓?fù)浜凸?jié)點(diǎn)定義模塊化，大大提高了仿真效率.協(xié)議采用inetmanet-2.0包里面的grid_aodv協(xié)議，仿真場(chǎng)景分別是AODV-UU、DSR-UU和DYMOUM.仿真的運(yùn)動(dòng)場(chǎng)景是：每個(gè)移動(dòng)節(jié)點(diǎn)在2000×1000m的矩形區(qū)域不停地隨機(jī)運(yùn)動(dòng)(運(yùn)動(dòng)模型是MassMobility)，仿真時(shí)間設(shè)置為100s.仿真的消息長度是512 Byte，應(yīng)用層開始發(fā)送UDP包的時(shí)間服從uniform(1s,60s,1)均勻分布，延時(shí)限制為20s，目的節(jié)點(diǎn)隨機(jī)生成.仿真時(shí)采用的業(yè)務(wù)場(chǎng)景見表1.

表1 業(yè)務(wù)場(chǎng)景

仿真的信道參數(shù)見表2.信道頻率是2.4GHz，最大發(fā)送功率2.0mW，路徑損耗系數(shù)是2，信道數(shù)量是1，Mac層協(xié)議選取的是802.11.

表2 信道參數(shù)

2.2 仿真步驟

用OMNeT++進(jìn)行仿真的流程如下：

(1)一個(gè)OMNeT++模型是通過交換信息來通訊的組件(模塊)來構(gòu)建的.模塊可以嵌套，也就是說，幾個(gè)模塊可以組成一個(gè)復(fù)合模塊.在創(chuàng)建模型時(shí)，需要將系統(tǒng)映射到一個(gè)相互通訊的模塊體系中；

(2)用NED語言定義模型的結(jié)構(gòu).可以在OMNeT++提供的IDE中以文本或圖形化方式來編輯NED文件；

(3)模型的活動(dòng)組件(簡單模塊)需要用C++來編程，當(dāng)中要使用仿真內(nèi)核及類庫；

(4)提供一個(gè)擁有配置和參數(shù)的omnetpp.ini文件給模型，一個(gè)配置文件可以用不同的參數(shù)來描述若干個(gè)仿真過程；

(5)構(gòu)建仿真程序并運(yùn)行.可以將代碼鏈接到OMNeT++的仿真內(nèi)核及其提供的一個(gè)用戶接口：命令行和交互式接口或圖形化接口；

(6)將仿真結(jié)果寫入輸出向量和輸出標(biāo)量文件中，使用IDE中提供的分析工具來進(jìn)行可視化.結(jié)果文件是普通的文本，所以能用R、MATLAB或其它工具來進(jìn)行繪圖.

仿真流程圖如圖2.得到*.vec矢量文件之后，我們用MATLAB軟件進(jìn)行繪圖.

2.3 仿真結(jié)果及分析

我們選擇了以下在Ad Hoc網(wǎng)絡(luò)中評(píng)估網(wǎng)絡(luò)性能的指標(biāo)：

(1)平均端到端時(shí)延：數(shù)據(jù)分組從源節(jié)點(diǎn)到目的節(jié)點(diǎn)所需要的平均時(shí)間，包括路由發(fā)現(xiàn)時(shí)延、數(shù)據(jù)包在隊(duì)列中的等待時(shí)間、傳輸時(shí)延以及MAC層的重傳時(shí)延，反映路由有效性.

(2)丟包率：應(yīng)用層收到的丟失分組數(shù)與發(fā)送的分組數(shù)之比，反映路由可靠性.

(3)路由發(fā)現(xiàn)頻率：每個(gè)節(jié)點(diǎn)傳輸數(shù)據(jù)量.反映路由傳輸錯(cuò)誤率和網(wǎng)絡(luò)競(jìng)爭水平.

圖2 仿真流程圖

仿真共使用7種不同的節(jié)點(diǎn)運(yùn)動(dòng)速度：0，50，100，150，200，250，300 m/s，根據(jù)節(jié)點(diǎn)運(yùn)動(dòng)速度的不同，網(wǎng)絡(luò)拓?fù)渥兓瘎×页潭炔煌?我們?nèi)?0個(gè)或者100個(gè)節(jié)點(diǎn)的平均值，用MATLAB工具繪制仿真結(jié)果圖.AODV-UU、DSR-UU和DYMOUM在50個(gè)節(jié)點(diǎn)和100個(gè)節(jié)點(diǎn)的平均端到端時(shí)延、丟包率、路由發(fā)現(xiàn)頻率，分別如圖3～5所示.

圖3 平均端到端時(shí)延與節(jié)點(diǎn)移動(dòng)速度仿真結(jié)果圖

圖4 丟包率與節(jié)點(diǎn)移動(dòng)速度仿真結(jié)果圖

圖5 路由發(fā)現(xiàn)頻率與節(jié)點(diǎn)移動(dòng)速度仿真結(jié)果圖

平均端到端時(shí)延:由圖3可知，DYMOUM協(xié)議的平均端到端時(shí)延優(yōu)于AODV-UU和DSR-UU協(xié)議，主要是DYMOUM協(xié)議使用了路徑積累，更能有效發(fā)現(xiàn)路由，此外，DYMOUM的路由維持效率比AODV-UU和DSR-UU高.從圖3中還可以看出，AODV-UU的時(shí)延在節(jié)點(diǎn)移動(dòng)速度為100m/s時(shí)到達(dá)一個(gè)峰值，DSR-UU時(shí)延在節(jié)點(diǎn)移動(dòng)速度為50m/s時(shí)到達(dá)一個(gè)峰值，而DYMOUM表現(xiàn)比較穩(wěn)定，隨著節(jié)點(diǎn)移動(dòng)速度的增加，3個(gè)協(xié)議的時(shí)延都出現(xiàn)增長，這是因?yàn)楣?jié)點(diǎn)移動(dòng)速度越快，拓?fù)渥兓絼×遥酚芍亟ù螖?shù)就越多，時(shí)延就會(huì)升高.

丟包率:從圖4可以看出，在50個(gè)節(jié)點(diǎn)的情況下，節(jié)點(diǎn)移動(dòng)速度較低時(shí)，DYMOUM丟包率較低，表現(xiàn)較好，而且整體表現(xiàn)較為平穩(wěn)，但是當(dāng)節(jié)點(diǎn)速度較高時(shí)，DYMOUM和AODVUU丟包率接近，均大于DSRUU的丟包率；在100個(gè)節(jié)點(diǎn)的情況下，DYMOUM的丟包率比AODVUU和DSRUU要高出很多，AODVUU和DSRUU的丟包率基本接近.因此，在節(jié)點(diǎn)較少的情況下，3個(gè)協(xié)議的丟包率基本一致，在節(jié)點(diǎn)較多時(shí)，DYMOUM的丟包率急劇上升，這是因?yàn)镈YMOUM只對(duì)基本的路由維護(hù)作出規(guī)定，并沒有說明路由維護(hù)是采用傳統(tǒng)的Hello包維護(hù)機(jī)制、鏈路檢測(cè)反饋機(jī)制還是像AOMDV的多路徑維護(hù)機(jī)制.

路由發(fā)現(xiàn)頻率:在路由發(fā)現(xiàn)頻率上，DYMOUM的表現(xiàn)明顯要優(yōu)于AODVUU和DSRUU，不過DSR由于其源路徑累積思想，在路徑基本建立完成之后，路由發(fā)現(xiàn)頻率趨于穩(wěn)定.

由以上仿真結(jié)果及性能分析可知，DYMOUM的平均端到端時(shí)延和路由發(fā)現(xiàn)頻率優(yōu)于AODVUU和DSRUU協(xié)議.當(dāng)節(jié)點(diǎn)數(shù)目較少時(shí)，DYMOUM協(xié)議的丟包率略高于AODVUU和DSRUU協(xié)議，三者差別并不大；當(dāng)節(jié)點(diǎn)數(shù)目較多時(shí)，DYMOUM協(xié)議的丟包率明顯高于AODVUU和DSRUU協(xié)議.因此，DYMOUM協(xié)議適用于對(duì)時(shí)延和開銷要求較高的網(wǎng)絡(luò)，而AODVUU和DSRUU適合對(duì)丟包率要求較高的網(wǎng)絡(luò).在節(jié)點(diǎn)數(shù)目較大時(shí)，AODVUU和DSRUU的丟包率基本一致，DYMOUM的丟包率明顯不如AODVUU和DSRUU，這是因?yàn)镈YMOUM并沒有規(guī)定鏈路維護(hù)部分的明確規(guī)定，因此在保持鏈路完整性方面不如AODVUU和DSRUU，但在路由發(fā)現(xiàn)頻率方面性能卻提高了很多，這是因?yàn)镈YMOUM無法探測(cè)鏈路完整性，因而也就無法感知鏈路中斷，因此在源節(jié)點(diǎn)路由發(fā)現(xiàn)頻率方面性能有所提高.

3 結(jié)語

本文利用OMNeT++網(wǎng)絡(luò)仿真軟件，選取平均端到端時(shí)延、丟包率和路由發(fā)現(xiàn)頻率3個(gè)指標(biāo)對(duì)嵌入式MATNET網(wǎng)絡(luò)協(xié)議AODVUU、DSRUU和DYMOUM進(jìn)行仿真和性能分析.實(shí)驗(yàn)結(jié)果表明，DYMOUM協(xié)議適用于對(duì)時(shí)延和開銷要求較高的網(wǎng)絡(luò)，而AODVUU和DSRUU適合對(duì)丟包率要求較高的網(wǎng)絡(luò).同時(shí)，針對(duì)DYMOUM草案在路由維護(hù)方面沒有做出明確的規(guī)定，導(dǎo)致丟包率低下的問題，我們可以從幾個(gè)方面來改進(jìn)：對(duì)于MAC層，我們考慮從鏈路斷裂感知方面來改進(jìn)；對(duì)于路由層，可以借鑒AOMDV的多路徑方法進(jìn)行改進(jìn)，也可以從延時(shí)容忍方向進(jìn)行改進(jìn)；對(duì)于應(yīng)用層，可以從服務(wù)質(zhì)量QoS方面進(jìn)行改進(jìn)，來提高DYMOUM協(xié)議特定環(huán)境下的性能.

[1] 陳林星,曾 曦,曹 毅. 移動(dòng)Ad Hoc網(wǎng)絡(luò)[M]. 北京：電子工業(yè)出版社,2012：4.

[2] 于海寧,張宏莉. VANETs路由協(xié)議的研究進(jìn)展[J]. 電子學(xué)報(bào),2011,39(12):2868-2879.

[3] Perkins C,Bhagwat P. Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers[C]//IEEE. Proceedings of the conference on Communications architectures,protocols and applications. New York: IEEE,1994: 234-244.

[4] Johnson D,Maltz D,Broch J. DSR: The dynamic source routing protocol for multi-hop wireless Ad Hoc networks[C]//IEEE. Ad Hoc Networking,Perkins C E ,Ed. Addison-Wesley. New York:IEEE,2001: 139-172.

[5] Perkins C,Royer E. Ad Hoc on-demand distance vector routing[J]. IEEE Workshop on Mobile Computing Systems and Applications (WMCSA),1999(8):192-196.

[6] 顏興建,趙東風(fēng),洪 偉,等. Ad Hoc DYMO路由協(xié)議性能研究[J]. 云南大學(xué)學(xué)報(bào): 自然科學(xué)版,2009,31(6): 580-583.

[7] Khandakar A. Step by step procedural comparison of DSR,AODV and DSDV routing protocol[C]//IEEE. ICCET. Orlando:IEEE,2012: 36-40.

[8] Mubarik A,Khan A,Hassan S. Implementation of geocast enhanced AODV-UU in Linux testbed[J]. Computer and Information Science,2009(174): 803-807.

[9] Perkins C,Royer E,Das S. Ad Hoc On-Demand Distance Vector (AODV) routing[J]. IETF Network Working Group,2003(8): 49-86.

[10] Gowrishankar S,SubirKumarSarkar T,Basavaraju T. Performance analysis of AODV,AODVUU,AOMDV and RAODV over IEEE 802.15.4 in wireless sensor networks [J]. Computer Science and Information Technology,2009(11): 59-63.

[11] Lorincz J,Ukic N,Begusic D. Throughput comparison of AODV-UU and DSR-UU protocol implementations in multi-hop static environments[C]//ACM.ConTel. Washington D C: ACM,2007:195-202.

[12] Miao Quanxing ,Xu Lei. DYMO routing protocol research and simulation based on NS2[J]. Computer Application and System Modeling,2010(14): 46-55.