陳運海

摘要： 該文通過研究移動自組網(wǎng)AODV路由協(xié)議，分析了AODV路由協(xié)議在鏈路斷鏈時進行鏈路修復(fù)時的缺點，提出了AODV-OPT路由協(xié)議；新協(xié)議通過一個更加合理的鏈路修復(fù)方案提高了網(wǎng)絡(luò)的性能。仿真實驗表明AODV-OPT路由協(xié)議提高了網(wǎng)絡(luò)中數(shù)據(jù)包的抵達率，同時減小了網(wǎng)絡(luò)中傳送數(shù)據(jù)時端到端的時延。

關(guān)鍵詞： 移動自組網(wǎng)；AODV協(xié)議；優(yōu)化；仿真

中圖分類號：TP393 文獻標(biāo)識碼：A 文章編號：1009-3044（2016）09-0039-03

Improvement and Simulation of AODV Routing Protocol in Mobile Ad Hoc Network

CHEN Yun-hai

（Department of Electronic Information Technology， Shenzhen Institute of Technology， Shenzhen 518116， China）

Abstract： In this paper，the author researched the AODV routing protocol in mobile Ad Hoc network，analyzed the drawback of the AODV routing protocol when it repair the broken link，and proposed AODV-OPT routing protocol to improve the network performance by a more reasonable way to fix the broken link. The simulation results prove that the AODV-OPT routing protocol can increase the Packet delivery ratio and reduce the Average end to end Delay.

Key words ：Ad Hoc network； AODV protocol ； improvement；simulation

1 引言

移動無線自組網(wǎng)絡(luò)是一種自組織、快速配置而且無需固定設(shè)施的動態(tài)網(wǎng)絡(luò)。網(wǎng)絡(luò)節(jié)點能夠以任意的速度和移動模式移動，也可以隨時開機和關(guān)機，這些因素導(dǎo)致網(wǎng)絡(luò)拓撲結(jié)構(gòu)的不斷變化。無線自組網(wǎng)絡(luò)的路由協(xié)議可以分為表驅(qū)動和按需兩大類。在按需路由協(xié)議中，只有節(jié)點需要進行通信時，才建立路由，以減少路由開銷。目前用得比較多的典型按需路由協(xié)議為AODV（Ad Hoc on-demand Distance Vector）。

AODV是一種優(yōu)秀的按需路由協(xié)議。在網(wǎng)絡(luò)的拓撲結(jié)構(gòu)發(fā)生改變的時候，它能快速收斂，計算量相對較小，占用的存儲資源小，同時能夠自我修復(fù)斷路，占用網(wǎng)絡(luò)帶寬較小。并且AODV協(xié)議在網(wǎng)絡(luò)中引入了節(jié)點序列號機制，可以有效避免網(wǎng)絡(luò)環(huán)路和無窮計數(shù)問題。但在有效路由發(fā)生鏈路中斷的情況下，在選擇源節(jié)點修復(fù)還是本地修復(fù)的選擇上，有可能選擇不恰當(dāng)?shù)姆绞?，從而引起網(wǎng)絡(luò)的整體性能下降。

本文通過研究和分析現(xiàn)有的AODV路由協(xié)議的工作過程，在現(xiàn)有的AODV路由協(xié)議的基礎(chǔ)上，提出了一個優(yōu)化后的路由協(xié)議AODV-OPT。在AODV-OPT路由協(xié)議中，我們根據(jù)鏈路中斷節(jié)點的上一跳節(jié)點的即時地理位置，選擇合適的路由修復(fù)方案，減少了網(wǎng)絡(luò)中的路由維護開銷。通過仿真表明，這種協(xié)議很好地解決了鏈路中斷時原AODV路由協(xié)議丟包率過高和數(shù)據(jù)分組傳送延遲較高的問題。

2 AODV路由協(xié)議的工作過程

2.1 AODV路由協(xié)議的路由發(fā)現(xiàn)

在AODV協(xié)議中，當(dāng)一個源節(jié)點希望發(fā)送一個數(shù)據(jù)到目標(biāo)節(jié)點時，這時候才需要建立一個源節(jié)點到目標(biāo)節(jié)點的路徑。為了找到通往目的節(jié)點的路徑，源節(jié)點就發(fā)起一個路徑發(fā)現(xiàn)程序，它廣播一個路由請求信息RREQ到鄰居節(jié)點，鄰居節(jié)點再轉(zhuǎn)發(fā)這個RREQ到下一跳鄰居節(jié)點，直到到達目標(biāo)節(jié)點或一個擁有達到目標(biāo)節(jié)點的有效路徑的中間節(jié)點。

同時，收到RREQ的中間節(jié)點根據(jù)RREQ中的信息，建立到源節(jié)點的路由---在路由表中增加一個路由條目---稱為“反向路由”。反向路由條目的目的節(jié)點是廣播RREQ的源節(jié)點，下一跳節(jié)點是將RREQ發(fā)送給本節(jié)點的鄰居節(jié)點。

如果到達目標(biāo)節(jié)點或一個擁有達到目標(biāo)節(jié)點的有效路徑的中間節(jié)點時，這時候，此節(jié)點回復(fù)路由應(yīng)答消息（RREP）到源節(jié)點，向源節(jié)點傳送是沿著之前建立的方向路由進行單播傳送。在傳送的過程中，收到RREP的節(jié)點建立到目標(biāo)節(jié)點的路由---在路由表中增加一條“正向路由”的路由條目。正向路由條目的目的節(jié)點是發(fā)送RREP的源節(jié)點，下一跳是將RREP發(fā)送給本節(jié)點的鄰居節(jié)點。

2.2 AODV路由保持過程

路由建立后，為維護已建立的路由，每個節(jié)點周期性地廣播發(fā)送Hello消息，以提供與相鄰節(jié)點的相互連接信息，該消息的傳播僅限于發(fā)送節(jié)點和相鄰節(jié)點之間。收到Hello消息的節(jié)點將建立或更新一條至發(fā)送節(jié)點的路由。在AODV中，任何時候節(jié)點收到任何控制報文，也具有和收到顯性的Hello消息一樣的意義，從而隨時保證節(jié)點的有效連接性。

如果在路由有效的時間沒有被使用而引發(fā)路由過期，或者節(jié)點在確定的有效路由的下一跳無法到達（如節(jié)點移動或鏈路故障等）時，該路由無效。當(dāng)節(jié)點檢測到某一路由無效時，它在路由表中將該路由表項設(shè)置成無效，且經(jīng)過一段時間后才將其刪除。

如果在傳送數(shù)據(jù)的過程中，有效路由發(fā)生鏈路中斷，AODV協(xié)議中有兩種處理方式：本地修復(fù)和源節(jié)點重建路由。如果斷鏈處的上一個節(jié)點距離目標(biāo)節(jié)點在MAX_REPAIR_TTL跳以內(nèi)，則該節(jié)點就會進行本地修復(fù)，本地修復(fù)是發(fā)生斷鏈的上一個節(jié)點發(fā)起路由發(fā)現(xiàn)，為了修復(fù)鏈路，節(jié)點將關(guān)于目標(biāo)節(jié)點的序列號增加1，然后廣播關(guān)于目的節(jié)點的RREQ；發(fā)起修復(fù)的節(jié)點等待路由發(fā)現(xiàn)周期來獲得對RREQ進行訪問的RREP。如果斷鏈處的上一個節(jié)點距離目標(biāo)節(jié)點大于MAX_REPAIR_TTL，則進行源節(jié)點修復(fù)，源節(jié)點修復(fù)是發(fā)生斷鏈處的上一個節(jié)點向源節(jié)點發(fā)送RERR消息，源節(jié)點收到RERR消息后，由源節(jié)點發(fā)起路由發(fā)現(xiàn)，源節(jié)點將目標(biāo)節(jié)點的序列號增加1，然后廣播關(guān)于目標(biāo)節(jié)點的RREQ。

如圖1，假定MAX_REPAIR_TTL=4；發(fā)生節(jié)點6與7之間的斷鏈時，由于節(jié)點6到D的距離為2<4，所以發(fā)起本地修復(fù)，只要修復(fù)6到D之間的路徑即可。如圖2，同樣假定MAX_REPAIR_TTL=4；發(fā)生節(jié)點3與4之間的斷鏈時，此時，節(jié)點3與D的距離為5>4，所以發(fā)起源節(jié)點修復(fù)。

2.3 AODV路由協(xié)議的路由修復(fù)過程的缺陷

我們知道，無線自組網(wǎng)的每個節(jié)點是不斷移動的，如圖3所示，如果節(jié)點6到7之間斷鏈，目標(biāo)節(jié)點D移動到距離源節(jié)點S一跳的位置，這時節(jié)點6發(fā)起本地修復(fù)將會引起整個網(wǎng)絡(luò)系統(tǒng)性能的下降。這時反而采用源節(jié)點修復(fù)比較合理。

同樣的，如果節(jié)點3到4之間斷鏈，目標(biāo)節(jié)點D移動到距離源節(jié)點附近幾跳的節(jié)點3位置，如圖4所示；這時通過源節(jié)點發(fā)起重建路由將會引起整個網(wǎng)絡(luò)系統(tǒng)性能的下降。這時反而采用本地節(jié)點修復(fù)比較合理。

3 AODV路由協(xié)議的優(yōu)化

3.1 AODV路由協(xié)議的改進思想

為了避免無線自組網(wǎng)在發(fā)生斷鏈時在鏈路修復(fù)上浪費過多的時間，必須根據(jù)節(jié)點的移動狀況來判定選用合適的路由修復(fù)方案。無線自組網(wǎng)發(fā)生斷鏈時，很多情況下是由于節(jié)點的移動造成的，所以，我們要隨時跟蹤目標(biāo)節(jié)點的地理位置情況。我們設(shè)目標(biāo)節(jié)點離斷鏈處的上一個節(jié)點的距離為hop1，源節(jié)點離斷鏈處的上一個節(jié)點的距離為hop2；當(dāng)hop1< hop2 時，采用本地節(jié)點修復(fù)；否則，采用源節(jié)點修復(fù)。為了準(zhǔn)確捕捉目標(biāo)節(jié)點的地理位置，需要在發(fā)起修復(fù)時，探測目標(biāo)節(jié)點和源節(jié)點的相對位置，根據(jù)探測結(jié)果來采取相應(yīng)的修復(fù)方案。我們稱這種新的路由協(xié)議為AODV-OPT路由協(xié)議。

3.2 AODV-OPT路由協(xié)議的實現(xiàn)

NS3網(wǎng)絡(luò)模擬器是一個優(yōu)秀的網(wǎng)絡(luò)模擬器，本身集成了對一些通用網(wǎng)絡(luò)實體的建模，并且自帶了對于AODV路由協(xié)議的仿真源程序。本文以AODV協(xié)議的源代碼為基礎(chǔ)框架，對改進后的路由協(xié)議進行編程改進，得到了改進后的AODV-OPT協(xié)議仿真源碼。然后分別運行改進前后的源代碼程序，并設(shè)定一定的場景。運行后，得出跟蹤信息，然后收集跟蹤信息進行對比分析。

4 AODV-OPT路由協(xié)議的性能仿真與分析

為了對AODV-OPT路由協(xié)議的性能進行分析，我們采用比較優(yōu)秀的網(wǎng)絡(luò)模擬器NS3，分別對AODV、AODV-OPT路由協(xié)議進行了分析，通過仿真分別得到了它們的數(shù)據(jù)包傳送率、端對端的平均延遲，用來衡量比較兩種路由協(xié)議的性能。

4.1 模擬場景設(shè)計

我們知道，在移動無線自組網(wǎng)中，影響移動無線自組網(wǎng)的性能指標(biāo)的節(jié)點因素有：節(jié)點運動拓撲區(qū)域的大小范圍、網(wǎng)絡(luò)中節(jié)點的個數(shù)、有多少節(jié)點在發(fā)送數(shù)據(jù)（即數(shù)據(jù)鏈路數(shù)）、節(jié)點發(fā)包速率、節(jié)點的移動速度、節(jié)點傳輸能量等。我們?nèi)?0個節(jié)點隨機分布在300m*1500m的平坦區(qū)域內(nèi)，節(jié)點采用Random Waypoint隨機運動模型，節(jié)點發(fā)包速率為2048bit/s，節(jié)點的傳輸能量為7.5 dBm。我們分別記錄節(jié)點的最大移動速度為10m/s、20m/s、30m/s、40m/s、50m/s、60m/s、70m/s、80m/s、90m/s、100m/s的數(shù)據(jù)發(fā)送和接收情況，端到端的傳送延遲情況，然后再進行統(tǒng)計分析。

4.2 數(shù)據(jù)包抵達率的統(tǒng)計和分析

數(shù)據(jù)包抵達率（Packet delivery ratio）是源節(jié)點產(chǎn)生的數(shù)據(jù)包與目的節(jié)點收到的數(shù)據(jù)包的比值。該指標(biāo)反映了網(wǎng)絡(luò)的吞吐量，表明路由協(xié)議的有效性和適應(yīng)網(wǎng)絡(luò)變化的性能。我們可以利用下面這個計算機公式來進行求解數(shù)據(jù)包抵達率：

數(shù)據(jù)包抵達率=目的節(jié)點接收到的數(shù)據(jù)包個數(shù)/源節(jié)點發(fā)送的數(shù)據(jù)包個數(shù)

我們根據(jù)仿真過程中產(chǎn)生的數(shù)據(jù)，得出了兩種路由協(xié)議數(shù)據(jù)包抵達率的變化情況，如圖5所示。我們可以看出，在節(jié)點移動速度變大時，對于兩種路由協(xié)議，數(shù)據(jù)包抵達率都有下降的趨勢。但總體上看，AODV-OPT路由協(xié)議的數(shù)據(jù)包抵達率明顯高于AODV路由協(xié)議，優(yōu)化造成了網(wǎng)絡(luò)性能的明顯提高。

4.3 平均端到端時延的統(tǒng)計和分析

平均端到端時延反映了在實際網(wǎng)絡(luò)應(yīng)用中的時間特性，特別是對于按需路由協(xié)議來說顯得更為重要。它包括了節(jié)點進行路由查找和在端口排隊時，數(shù)據(jù)分組在緩沖區(qū)中的延遲，同時也包括了MAC層進行重組以及分組傳播的時間。平均端到端時延即為所有成功傳送數(shù)據(jù)分組時延的平均數(shù)。我們可以用下面的公式來計算：

平均端到端時延 = ∑（接收到數(shù)據(jù)包的時間 - 發(fā)送包數(shù)據(jù)包的時間）/發(fā)送的數(shù)據(jù)包個數(shù)

我們根據(jù)仿真過程中產(chǎn)生的數(shù)據(jù)，得出了兩種路由協(xié)議數(shù)據(jù)包平均延時的變化情況，如圖6所示。我們可以看出，AODV-OPT路由協(xié)議的數(shù)據(jù)包平均延時明顯小于AODV路由協(xié)議。端到端延時越小，說明網(wǎng)絡(luò)傳送數(shù)據(jù)越順暢，表明網(wǎng)絡(luò)的性能越好。因此，通過仿真實驗證明，優(yōu)化路由協(xié)議明顯提高了無線自組網(wǎng)的性能。

5 結(jié)束語

本文主要對無線自組網(wǎng)中的AODV路由協(xié)議進行了研究和改進。首先介紹了無線自組網(wǎng)AODV路由協(xié)議的工作過程，然后指出了AODV在路由修復(fù)中存在的缺點和不足，并提出了一種改進的AODV路由協(xié)議。最后利用NS3網(wǎng)絡(luò)模擬器進行編程仿真，運行仿真程序，收集仿真過程中的數(shù)據(jù)進行統(tǒng)計和分析；并通過對比分析，從而證明了改進的路由協(xié)議AODV-OPT在性能上是優(yōu)越的。

參考文獻：

[1] 陳娟.基于Ad Hoc網(wǎng)絡(luò)的自適應(yīng)中斷容忍路由協(xié)議的研究[D].北京：北京郵電大學(xué)，2015.

[2] 麻晉文.移動Ad hoc網(wǎng)絡(luò)中AODV路由協(xié)議的研究[D] .蘭州：蘭州大學(xué)，2014.

[3] 翟振輝.自組織網(wǎng)絡(luò)中的AODV路由協(xié)議的優(yōu)化研究[D].北京：北京郵電大學(xué)，2011.

[4] Mehdi Zarei，Karim Faez，Javad Moosavi Nya，Modified Reverse AODV Routing Algorithm using Route Stability in Mobile Ad Hoc Networks[C].Multitopic Conferenee，2008，：255-259.

[5] ns-3 developers[EB/OL]. http：//www.nsnam.org/developers/overview

[6] ns-3documentation[EB/OL]. http：//www.nsnam.org/docs/doxygen/index.html.