AdHoc網(wǎng)絡(luò)中AODV路由協(xié)議性能分析

李陽(yáng)

摘 要 Ad Hoc 網(wǎng)絡(luò)（Mobile Ad Hoc Network，MANET）沒(méi)有任何的固定基礎(chǔ)設(shè)施，主機(jī)通過(guò)彼此無(wú)線電波通信，在軍事通信、野外通信、應(yīng)急通信等領(lǐng)域有著廣泛的應(yīng)用前景。

本文主要介紹用于Ad Hoc網(wǎng)絡(luò)的AODV路由協(xié)議的原理，利用NS2構(gòu)建一個(gè)網(wǎng)絡(luò)模擬場(chǎng)景，對(duì)AODV協(xié)議的性能進(jìn)行測(cè)試、分析。

從仿真來(lái)看，在相同的移動(dòng)速度下，DSR和AODV協(xié)議的丟包率明顯低于DSDV協(xié)議，特別是在網(wǎng)絡(luò)拓?fù)漭^穩(wěn)定時(shí)，DSR和AODV的丟包率相當(dāng)?shù)停ń咏?%），而DSDV的丟包率最高。隨著移動(dòng)速度的增加，各路由協(xié)議的端到端平均時(shí)延都在增加，其中DSR的增加幅度最大；在相同速度下，3個(gè)協(xié)議中DSDV具有最小的端到端時(shí)延，而DSR和AODV的端到端平均延遲較大。由于Ad Hoc網(wǎng)絡(luò)的移動(dòng)性使得AODV的性能有所下降，但總體來(lái)說(shuō)，路由協(xié)議的總體性能很好，即使在節(jié)點(diǎn)的移動(dòng)的情況下，網(wǎng)絡(luò)分組傳輸?shù)膩G包率、平均的端對(duì)端延時(shí)都保持在較好的水平上。事實(shí)上，算法的網(wǎng)絡(luò)性能隨著網(wǎng)絡(luò)參數(shù)的設(shè)計(jì)是不同的，受多方因素的影響，它們之間的關(guān)系還有待進(jìn)一步研究。在具體規(guī)劃網(wǎng)絡(luò)結(jié)構(gòu)時(shí)，應(yīng)該對(duì)AODV參數(shù)作具體的設(shè)計(jì)，以確保網(wǎng)絡(luò)性能的最優(yōu)。

關(guān)鍵詞 Ad Hoc 路由協(xié)議 仿真 AODV

1 課題背景及開(kāi)展研究的意義

Ad hoc網(wǎng)絡(luò)是一種自組織的無(wú)線多跳網(wǎng)，它不需要固定的基礎(chǔ)設(shè)施作支撐。路由協(xié)議是Ad hoc網(wǎng)絡(luò)協(xié)議棧的重要組成部分，在無(wú)線環(huán)境下Ad hoc網(wǎng)絡(luò)的移動(dòng)特性對(duì)路由協(xié)議提出了更高的要求。

（1）網(wǎng)絡(luò)中所有節(jié)點(diǎn)都是移動(dòng)的，并且都能以任意方式動(dòng)態(tài)地保持與其他節(jié)點(diǎn)的聯(lián)系，網(wǎng)絡(luò)節(jié)點(diǎn)可以隨處移動(dòng)，也可以隨時(shí)開(kāi)機(jī)和關(guān)機(jī)，這些都會(huì)使網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)隨時(shí)發(fā)生變化。

（2）兩個(gè)無(wú)法直接進(jìn)行通信的終端用戶可以借助其他節(jié)點(diǎn)進(jìn)行分組轉(zhuǎn)發(fā)，每個(gè)移動(dòng)節(jié)點(diǎn)兼?zhèn)渎酚善骱椭鳈C(jī)兩種功能。

（3）Ad hoc網(wǎng)絡(luò)通過(guò)分組轉(zhuǎn)發(fā)完成數(shù)據(jù)的交換，需要路由協(xié)議進(jìn)行分組轉(zhuǎn)發(fā)決策。無(wú)線信道變化的不規(guī)則性和節(jié)點(diǎn)的移動(dòng)、加入、退出都會(huì)引起網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)變化。從而路由協(xié)議完成監(jiān)控網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化、路由信息的交換、尋找目的節(jié)點(diǎn)、產(chǎn)生、維護(hù)并優(yōu)化路由，保持網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)臅惩ā?/p>

Ad hoc網(wǎng)絡(luò)的路由協(xié)議大致可以分為先驗(yàn)式（Proactive）路由協(xié)議（如：DSDV）、反應(yīng)式（Reactive）路由協(xié)議（如：DSR/ /TORA/ARP）以及混合式路由協(xié)議（如：AODV）。

先驗(yàn)式路由協(xié)議又稱為表驅(qū)動(dòng)路由協(xié)議（Table-driven），在這種路由協(xié)議中，每個(gè)節(jié)點(diǎn)維護(hù)一張包含到達(dá)其它節(jié)點(diǎn)的路由信息的路由表。當(dāng)檢測(cè)到網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時(shí)，節(jié)點(diǎn)在網(wǎng)絡(luò)中發(fā)送更新消息，收到更新消息的節(jié)點(diǎn)將更新自己的路由表，以維護(hù)一致的、及時(shí)的、準(zhǔn)確的路由信息，所以路由表可以準(zhǔn)確地反映網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。源節(jié)點(diǎn)一旦要發(fā)送報(bào)文，可以立即獲得到達(dá)目的節(jié)點(diǎn)的路由。因此這種路由協(xié)議的時(shí)延較小，但是路由協(xié)議的開(kāi)銷較大。

反應(yīng)式路由協(xié)議，又稱為按需路由協(xié)議（On-Demand Routing），是一種當(dāng)需要發(fā)送數(shù)據(jù)時(shí)才查找路由的路由算法。在這種路由協(xié)議中，節(jié)點(diǎn)不需要維護(hù)及時(shí)準(zhǔn)確的路由信息，當(dāng)向目的節(jié)點(diǎn)發(fā)送報(bào)文時(shí)，源節(jié)點(diǎn)才在網(wǎng)絡(luò)中發(fā)起路由查找過(guò)程，找到相應(yīng)的路由。與先驗(yàn)式路由協(xié)議相比，反應(yīng)式路由協(xié)議的開(kāi)銷較小，但是數(shù)據(jù)報(bào)傳送的時(shí)延較大。

在Ad hoc網(wǎng)絡(luò)中單純采用先驗(yàn)式或反應(yīng)式路由協(xié)議都不能完全解決路由問(wèn)題。由此可見(jiàn)，應(yīng)用結(jié)合先驗(yàn)式和反應(yīng)式路由協(xié)議優(yōu)點(diǎn)的混合式路由協(xié)議是一種較好的折衷方案。下面對(duì)混合式的路由協(xié)議AODV（Ad hoc On demand Distance Vector Routing）進(jìn)行具體的研究。

總之，AODV協(xié)議是一個(gè)比較好的路由協(xié)議，它能夠?qū)崿F(xiàn)路由的所用基本功能。同時(shí)AODV能夠應(yīng)對(duì)Ad hoc網(wǎng)絡(luò)的節(jié)點(diǎn)移動(dòng)的要求，在設(shè)定的路由延遲的情況下，表現(xiàn)出良好的性能。但由于未能考慮業(yè)務(wù)的QoS需求，在對(duì)傳輸質(zhì)量要求較高的網(wǎng)絡(luò)中，顯得力不從心，尚待進(jìn)一步完善。

通過(guò)對(duì)AODV路由協(xié)議的證明，我們可以得到衡量網(wǎng)絡(luò)路由協(xié)議的標(biāo)準(zhǔn)。只有在理論分析和網(wǎng)絡(luò)仿真的基礎(chǔ)上對(duì)原有協(xié)議進(jìn)行分析，才能改進(jìn)原有的路由協(xié)議，不斷提出有利于網(wǎng)絡(luò)的性能提高的新的策略。

2 研究方法、內(nèi)容 及預(yù)期目的

2.1 研究方法

在硬件條件不具備的情況下進(jìn)行Ad Hoc網(wǎng)絡(luò)AODV路由協(xié)議的性能分析，要花費(fèi)巨資去建立實(shí)際系統(tǒng)，這是不現(xiàn)實(shí)的。因此，我們采用網(wǎng)絡(luò)模擬（也稱網(wǎng)絡(luò)仿真）軟件NS-2進(jìn)行模擬分析。

NS-2是指 Network Simulator version 2，NS（Network Simulator） 是一種針對(duì)網(wǎng)絡(luò)技術(shù)的源代碼公開(kāi)的、免費(fèi)的軟件模擬平臺(tái)，研究人員使用它可以很容易的進(jìn)行網(wǎng)絡(luò)技術(shù)的開(kāi)發(fā)，而且發(fā)展到今天，它所包含的模塊已經(jīng)非常豐富，幾乎涉及到了網(wǎng)絡(luò)技術(shù)的所有方面。所以，NS成了目前學(xué)術(shù)界廣泛使用的一種網(wǎng)絡(luò)模擬軟件。在每年國(guó)內(nèi)外發(fā)表的有關(guān)網(wǎng)絡(luò)技術(shù)的學(xué)術(shù)論文中，利用NS給出模擬結(jié)果的文章最多，通過(guò)這種方法得出的研究結(jié)果也是被學(xué)術(shù)界所普遍認(rèn)可的，此外，NS也可作為一種輔助教學(xué)的工具，已被廣泛應(yīng)用在了網(wǎng)絡(luò)技術(shù)的教學(xué)方面。因此，目前在學(xué)術(shù)界和教育界，有大量的人正在使用或試圖使用NS。

學(xué)習(xí)用于Ad Hoc網(wǎng)絡(luò)的AODV路由協(xié)議的原理，利用NS2構(gòu)建一個(gè)網(wǎng)絡(luò)模擬場(chǎng)景，對(duì)AODV協(xié)議的性能進(jìn)行測(cè)試、分析，并用NAM對(duì)網(wǎng)絡(luò)運(yùn)行情況進(jìn)行動(dòng)畫(huà)演示。

2.2 研究?jī)?nèi)容

（1）在NS2中用setdest命令隨機(jī)生成一個(gè)無(wú)線網(wǎng)絡(luò)節(jié)點(diǎn)的運(yùn)動(dòng)場(chǎng)景，在500×500的區(qū)域中隨機(jī)分布30個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)隨機(jī)選擇運(yùn)動(dòng)方向和速度，最大運(yùn)動(dòng)速度為20m/s，到達(dá)目的地后停留10s繼續(xù)運(yùn)動(dòng)，模擬時(shí)間是100s；

（2）對(duì)移動(dòng)節(jié)點(diǎn)中各網(wǎng)絡(luò)構(gòu)件的主要類型參數(shù)進(jìn)行設(shè)置：無(wú)線信號(hào)傳輸模式為TwoRayGround，MAC層協(xié)議類型為802.11，接口隊(duì)列采用DropTail機(jī)制，采用全向天線；

（3）用cbrgen命令產(chǎn)生CBR業(yè)務(wù)，最大連接數(shù)是20，速率是每秒2個(gè)數(shù)據(jù)包，每個(gè)包的大小為512字節(jié)；

（4）用Gawk分析trace文件，并以端到端的延時(shí)和丟包率為指標(biāo)評(píng)估AODV協(xié)議的性能。

端到端的延時(shí)定義為數(shù)據(jù)包接收過(guò)程的總延時(shí)與接收的數(shù)據(jù)包數(shù)目之比。

丟包率定義為丟失的數(shù)據(jù)包與發(fā)送的數(shù)據(jù)包之比。

3 仿真內(nèi)容及結(jié)果分析

3.1 NS2仿真平臺(tái)的建立

NS2是一種事先驅(qū)動(dòng)的面向?qū)ο蟮木W(wǎng)絡(luò)仿真工具，它為用戶提供了擴(kuò)展、配置和編程的工具。它所用的仿真語(yǔ)言是Tool Command Language（TCL）語(yǔ)言的一個(gè)擴(kuò)展。仿真通過(guò)TCL語(yǔ)言進(jìn)行定義，利用ns命令編寫(xiě)腳本來(lái)定義網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、配置網(wǎng)絡(luò)信息流量的產(chǎn)生和接收以及收集統(tǒng)計(jì)數(shù)據(jù)。NS2軟件配有仿真過(guò)程動(dòng)態(tài)觀察器，可以在仿真運(yùn)行結(jié)束后，動(dòng)態(tài)察看仿真的運(yùn)行過(guò)程，觀察跟蹤數(shù)據(jù)。軟件還有圖形顯示器，顯示從仿真中得到的結(jié)果數(shù)據(jù)，直觀而且清晰。

NS2是一個(gè)用C++編寫(xiě)的面向?qū)ο蠓抡嫫?，它的前端是一個(gè)OTCL解釋器。仿真器內(nèi)核定義了有層次結(jié)構(gòu)的多種類，稱為編譯類結(jié)構(gòu)。在OTCL解釋器中有相似的類結(jié)構(gòu)，稱為解釋類結(jié)構(gòu)。從用戶的角度來(lái)看，兩種結(jié)構(gòu)的類之間有一一對(duì)應(yīng)的關(guān)系。用戶通過(guò)解釋器創(chuàng)立新的仿真對(duì)象之后，解釋器對(duì)它進(jìn)行初始化，與編譯類結(jié)構(gòu)中相應(yīng)的對(duì)象建立映射。

NS2仿真器封裝了許多功能模塊，最基本的是節(jié)點(diǎn)、鏈路、代理、數(shù)據(jù)包格式等等，下面分別來(lái)介紹一下各個(gè)模塊。

（1）事件調(diào)度器：目前NS2提供了四種具有不同數(shù)據(jù)結(jié)構(gòu)的調(diào)度器，分別是鏈表、堆、日歷表和實(shí)時(shí)調(diào)度器。

（2）節(jié)點(diǎn)（node）：是由TclObject對(duì)象組成的復(fù)合組件，在NS2中可以表示端節(jié)點(diǎn)和路由器。

（3）鏈路（link）：由多個(gè)組件復(fù)合而成，用來(lái)連接網(wǎng)絡(luò)節(jié)點(diǎn)。所有的鏈路都是以隊(duì)列的形式來(lái)管理分組的到達(dá)、離開(kāi)和丟棄。

（4）代理（agent）：負(fù)責(zé)網(wǎng)絡(luò)層分組的產(chǎn)生和接收，也可以用在各個(gè)層次的協(xié)議實(shí)現(xiàn)中。每個(gè)agent連接到一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)上，由該節(jié)點(diǎn)給它分配一個(gè)端口號(hào)。

（5）包（packet）：由頭部和數(shù)據(jù)兩部分組成。一般情況下，packet只有頭部、沒(méi)有數(shù)據(jù)部分。

NS2軟件是一個(gè)軟件包，包括Tcl/Tk，OTCL，NS，Tclcl。其中Tcl是一個(gè)開(kāi)放腳本語(yǔ)言；Tk是Tcl的圖形界面開(kāi)發(fā)工具；OTCL是基于Tcl/Tk的面向?qū)ο髷U(kuò)展，有自己的類層次結(jié)構(gòu)；NS2為本軟件包的核心，是面向?qū)ο蟮姆抡嫫鳎肅++編寫(xiě)，以O(shè)TCL解釋器作為前端；Tclcl則提供NS2和OTCL的接口，使對(duì)象和變量出現(xiàn)在兩種語(yǔ)言中。

NS2仿真分兩個(gè)層次：一個(gè)基于OTCL編程，NS2已有的網(wǎng)絡(luò)仿真元素實(shí)現(xiàn)仿真，無(wú)需對(duì)NS2本身作任何改動(dòng)，只要編寫(xiě)Tcl腳本便可；另一個(gè)層次是基于C++和OTCL的編程，用戶可以利用OTCL和NS2的接口，編寫(xiě)C++程序，更新NS2來(lái)實(shí)現(xiàn)新的功能。

NS2定義了一個(gè).tr格式的文件用于記錄仿真的結(jié)果，通過(guò)腳本配置，可以指定文件名并對(duì)仿真過(guò)程進(jìn)行跟蹤，通過(guò)NS2中xgraph的解釋，此記錄文件可以以圖形的方式顯示仿真結(jié)果。為了使顯示結(jié)果更逼真，NS2提供了一個(gè)用于產(chǎn)生動(dòng)畫(huà)效果的可視化工具：nam（NetworkAnimotar）。nam用于有線和無(wú)線網(wǎng)絡(luò)的可視化，在nam中，執(zhí)行仿真的人可以控制動(dòng)畫(huà)演示的速度，如正向播放、快速前進(jìn)、快速后退停止運(yùn)行等，以監(jiān)視網(wǎng)絡(luò)的行為（如隊(duì)列的變化）。

3.2 生成運(yùn)動(dòng)場(chǎng)景

我們可以使用setdest來(lái)生成運(yùn)動(dòng)場(chǎng)景。setdest是CMU大學(xué)在NS中提供無(wú)線網(wǎng)模擬模塊時(shí)提供的一個(gè)工具，可以用來(lái)隨機(jī)生成無(wú)線網(wǎng)所需要的節(jié)點(diǎn)運(yùn)動(dòng)場(chǎng)景，即一定數(shù)量的節(jié)點(diǎn)在某個(gè)固定大小的矩形區(qū)域中隨機(jī)朝某個(gè)目的節(jié)點(diǎn)運(yùn)動(dòng)，在到達(dá)該目的地后做一段時(shí)間的停留（也可以不停留）后選擇另一個(gè)目的地隨機(jī)選擇一個(gè)速度繼續(xù)運(yùn)動(dòng)。setdest可以指定場(chǎng)景的節(jié)點(diǎn)數(shù)，節(jié)點(diǎn)運(yùn)動(dòng)區(qū)域的長(zhǎng)度和寬度及模擬場(chǎng)景的持續(xù)時(shí)間，節(jié)點(diǎn)在運(yùn)動(dòng)到一個(gè)目的地后停留的時(shí)間，節(jié)點(diǎn)隨機(jī)運(yùn)動(dòng)速度的最大值等。最后還能指定生成場(chǎng)景的輸出文件。使用setdest生成的場(chǎng)景文件，可以在NS控制臺(tái)或者運(yùn)行腳本中使用source命令調(diào)入。

實(shí)驗(yàn)中我們生成的場(chǎng)景是構(gòu)建隨機(jī)的節(jié)點(diǎn)運(yùn)動(dòng)場(chǎng)景，場(chǎng)景規(guī)模500m×500m，場(chǎng)景包括30個(gè)節(jié)點(diǎn)，信源采用CBR方式，在30個(gè)節(jié)點(diǎn)中隨機(jī)選擇20個(gè)節(jié)點(diǎn)，啟動(dòng)20個(gè)cbr數(shù)據(jù)流，每個(gè)流每秒鐘產(chǎn)生2個(gè)512字節(jié)大小的數(shù)據(jù)包。這里節(jié)點(diǎn)運(yùn)動(dòng)的最大速率分別選擇為0，10 m/s ，20m/s，30m/s，40m/s，50m/s，100m/s，200 m/s，其中速度100m/s，200m/s表示整個(gè)場(chǎng)景運(yùn)動(dòng)很激烈。

對(duì)于在NS2中 用setdest命令隨機(jī)生成一個(gè)無(wú)線網(wǎng)絡(luò)節(jié)點(diǎn)的運(yùn)動(dòng)場(chǎng)景以及用cbrgen命令產(chǎn)生CBR業(yè)務(wù)。

3.3 生成傳輸負(fù)載

我們可以使用cbrgen來(lái)生成傳輸負(fù)載（traffic overland），可以產(chǎn)生TCP流或者CBR流（Constant Bytes Rate Stream）。該工具能夠指定有多少個(gè)節(jié)點(diǎn)，這些節(jié)點(diǎn)間的最大連接數(shù)，隨機(jī)種子數(shù)，還可以指定每個(gè)連接間的流的負(fù)載量。如果產(chǎn)生的是cbr流，則包長(zhǎng)固定為512MByte，rate值指定的是每秒發(fā)送多少個(gè)包。

在我的仿真中，是在30個(gè)節(jié)點(diǎn)當(dāng)中選擇20對(duì)節(jié)點(diǎn)啟動(dòng)20個(gè)cbr數(shù)據(jù)流，每個(gè)流每秒鐘產(chǎn)生2個(gè)512M字節(jié)大小的數(shù)據(jù)包（ns cbrgen.tcl -type cbr -nn 30 -seed 1 -mc 20 -rate 2.0 >cbr）。

我們實(shí)驗(yàn)中將產(chǎn)生的cbr流文件輸入到文件cbr中去。

3.4 編寫(xiě)tcl腳本文件

用于仿真的TCL腳本的編寫(xiě)是仿真中關(guān)鍵的一步。NS2主要通過(guò)TCL腳本來(lái)實(shí)現(xiàn)模擬場(chǎng)景的建立、配置和模擬中運(yùn)行的程序。只有通過(guò)TCL腳本才能創(chuàng)建和管理拓?fù)浣Y(jié)構(gòu)，進(jìn)行事件調(diào)度等。無(wú)線網(wǎng)絡(luò)的腳本得編寫(xiě)，主要包括以下幾個(gè)模塊：

隨著移動(dòng)速度的增加，路由協(xié)議的丟包遞率都呈上升趨勢(shì)。這是因?yàn)殡S著移動(dòng)速度的增加，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化越來(lái)越劇烈，網(wǎng)絡(luò)中的無(wú)線信道勢(shì)必增加了大量的路由更新報(bào)文，特別是表驅(qū)動(dòng)路由協(xié)議DSDV。每一次拓?fù)涞淖兓夹枰侣酚杀碇械膬?nèi)容，而DSR和AODV都是按需路由協(xié)議，只有在要發(fā)送分組時(shí)才需要建立路由。因此，按需路由協(xié)議對(duì)網(wǎng)絡(luò)拓?fù)涞淖兓拿舾卸纫缺眚?qū)動(dòng)路由協(xié)議要低得多。

在相同的最大移動(dòng)速度下，DSR和AODV協(xié)議的丟包率明顯低于DSDV協(xié)議，特別是在網(wǎng)絡(luò)拓?fù)漭^穩(wěn)定時(shí)，DSR和AODV的丟包率相當(dāng)?shù)停ń咏?%），而DSDV的丟包率最高。隨著移動(dòng)速度的增加，各路由協(xié)議的端到端平均時(shí)延都在增加，其中DSR的增加幅度最大；在相同最大速度下，3個(gè)協(xié)議中DSDV具有最小的端到端時(shí)延，而DSR和AODV的端到端平均延遲較大。這是因?yàn)樵谛枰l(fā)送數(shù)據(jù)時(shí)，DSDV路由協(xié)議通過(guò)查找路由表直接獲取路由，因而延遲時(shí)間較??；而DSR和AODV是按需路由協(xié)議，它們?cè)谛枰l(fā)送數(shù)據(jù)時(shí)才啟動(dòng)路由發(fā)現(xiàn)過(guò)程，查找可用的路由，因此延遲較大。移動(dòng)速度的增加導(dǎo)致拓?fù)浣Y(jié)構(gòu)的頻繁變化，從而使得各路由協(xié)議的端到端平均時(shí)延也相應(yīng)地增加。

時(shí)延結(jié)果與AODV協(xié)議理論上是相符的，AODV協(xié)議采用了路由緩存技術(shù)，所以它的時(shí)延比DSDV協(xié)議大很多。在場(chǎng)景運(yùn)動(dòng)緩慢的情況下，時(shí)延幾乎是DSDV協(xié)議的10倍。

另外，由于AODV路由協(xié)議是DSR和DSDV的綜合，因此，在相同條件下AODV的時(shí)延較DSR要小得多。

通過(guò)對(duì)AODV的各個(gè)性能的仿真，我們可以看出AODV協(xié)議在不同的場(chǎng)景下保持良好的性能，可見(jiàn)這個(gè)協(xié)議的丟包率很低，時(shí)延也維持了一個(gè)比較平均的水平。可見(jiàn)AODV協(xié)議是一個(gè)較為穩(wěn)定的，適用于各種網(wǎng)絡(luò)場(chǎng)景的較好的路由協(xié)議。