俞雙龍，于瀛

(中國傳媒大學 信息工程學院，北京 100024)

移動Ad Hoc網(wǎng)絡(luò)AODV路由協(xié)議的改進

俞雙龍，于瀛

(中國傳媒大學 信息工程學院，北京 100024)

針對目前AODV路由協(xié)議僅維持一條路由，在路由失效時本地修復(fù)機制不夠完善，重新發(fā)起路由建立過程必定增加了路由延時和開銷的問題，本文提出建立一種備用路由及本地修復(fù)相結(jié)合的路由協(xié)議。首先簡要介紹了移動Ad Hoc網(wǎng)絡(luò)和AODV路由協(xié)議，然后在對AODV路由協(xié)議進行了研究的基礎(chǔ)上實現(xiàn)一種帶備份路由和本地修復(fù)的優(yōu)化。最后通過NS2對改進的路由協(xié)議與AODV路由協(xié)議的仿真模擬，在延時、到達率和路由開銷方面進行了對比。仿真結(jié)果證明了修改后的路由協(xié)議能更好的提高了網(wǎng)絡(luò)的性能。

移動Ad Hoc網(wǎng)絡(luò)；AODV路由協(xié)議；備份路由；NS2

1 引言

移動Ad Hoc網(wǎng)絡(luò)是一種不依賴固定設(shè)施的、自組織的無線網(wǎng)絡(luò)。具有抗毀性強，組網(wǎng)靈活及使用方便的特點。既可應(yīng)用于救援、會議、戰(zhàn)場、探險或危險環(huán)境中的目標監(jiān)控等場合，又可用于有線網(wǎng)末端網(wǎng)絡(luò)的擴展。移動Ad Hoc網(wǎng)絡(luò)的動態(tài)變化的拓撲結(jié)構(gòu)，使得傳統(tǒng)的路由協(xié)議在該環(huán)境下無法正常運行。因此，Ad Hoc網(wǎng)絡(luò)的路由協(xié)議是研究熱點之一。目前已提出的平面路由算法分為表驅(qū)動路由協(xié)議和按需路由協(xié)議。由于表驅(qū)動路由協(xié)議要周期性地交換路由信息，導(dǎo)致路由開銷很大，因而當需要路由時才發(fā)起路由查找的按需路由協(xié)議更加適合于 Ad Hoc 網(wǎng)絡(luò)環(huán)境。

自組網(wǎng)按需距離矢量路由(Ad-Hoc On-Demand Distance Vector Routing，AODV)協(xié)議[1]是移動Ad Hoc網(wǎng)絡(luò)中被廣泛應(yīng)用的按需路由協(xié)議之一。

AODV協(xié)議借鑒了動態(tài)源路由(Dynamic Source Routing，DSR)協(xié)議[2]和目的節(jié)點序列號距離矢量路由(Destination-Sequenced Distance-Vector，DSDV)協(xié)議[3]的優(yōu)點，借用了DSR中的路由發(fā)現(xiàn)和路由維護的基礎(chǔ)程序，以及 DSDV 中的逐跳路由、順序編號等機制。近年來，人們針對AODV協(xié)議的特點提出了很多改進方法，如文獻[5]提出了避免路由斷裂的節(jié)能路由算法，文獻[6]提出了基于AODV改進型備用路由修復(fù)協(xié)議。本文提出另一種帶備用路由協(xié)議的新方案，在節(jié)點發(fā)生斷裂時首先判斷是否滿足本地修復(fù)條件，若滿足則進行本地修復(fù)，否則直接調(diào)用備用路由繼續(xù)通信。通過仿真證明了改進了的路由協(xié)議有效的降低了端到端延時和路由開銷，改善網(wǎng)絡(luò)性能。

2 AODV路由協(xié)議

AODV 路由協(xié)議中，每個節(jié)點分布式地生成并維護一個路由表。路由表信息主要包括目的節(jié)點地址、目的節(jié)點序列號、跳數(shù)、下一跳節(jié)點、前驅(qū)列表、壽命、路由標記等參數(shù)。協(xié)議不進行周期性路由信息的交換，而是在需要進行通信而路由表中又沒有路由的情況下才發(fā)起路由請求。AODV路由協(xié)議主要分為兩個過程：

路由建立：如果在源節(jié)點需要和目的節(jié)點通信時沒有可用路由，則源節(jié)點向周圍節(jié)點廣播 路由請求(Route Request，RREQ)消息。中間節(jié)點在第一次收到這個消息后，建立一條反向路由，而且對以后收到的同一個 RREQ 加以丟棄。當目的節(jié)點收到第一個 RREQ 消息后，向源節(jié)點沿著反向路由單播一個路由應(yīng)答(Route Reply，RREP)消息，從而沿著這條反向路由將正向路由建立，對以后收到的 RREQ 將不做 RREP 響應(yīng)。如果中間節(jié)點收到 RREQ 消息，先查找路由表，若發(fā)現(xiàn)已有通往目的節(jié)點的可用路由時，此中間節(jié)點將代替目的節(jié)點向源節(jié)點單播 RREP 消息，從而建立雙向路由。對于那些建立了反向路由，但沒有收到RREP 消息的中間節(jié)點，它們先前建立的反向路由將會在一定時間后自動變?yōu)闊o效。

路由維護：每個節(jié)點定時向周邊節(jié)點發(fā)送一個特殊的消息——HELLO 消息，以通知相鄰節(jié)點自己的存在，通過這種方法來維護網(wǎng)絡(luò)的連通性。當一段時間沒有收到某個下一跳節(jié)點的 HELLO 消息時，就代表這個路由已經(jīng)斷裂。如果此節(jié)點離目的節(jié)點較近的話，就會進行本地修復(fù)(Local Repair)工作——即上游節(jié)點發(fā)送一個 TTL 值合適的 RREQ，期間收到的數(shù)據(jù)包將被節(jié)點緩沖。如果此節(jié)點離源節(jié)點較近或者本地路由修復(fù)不成功的話，就向源節(jié)點發(fā)送 RERR 消息，以更新沿途節(jié)點的路由信息。當源節(jié)點收到這個 RERR 消息后，重新發(fā)起路由發(fā)現(xiàn)過程，來重新建立路由。

3 改進的AODV算法

3.1 改進思想

針對AODV只維護一條路由及本地修復(fù)不完善的情況，本文提出一種帶備用路由協(xié)議的新方案，在路由發(fā)起過程中，源節(jié)點路由表中不僅保存一條主路由，源節(jié)點和鄰居節(jié)點都保存一條到目的節(jié)點的其他路由。主路由失效時，根據(jù)斷裂節(jié)點的位置和周圍節(jié)點的情況而確定是否進行本地修復(fù)。若不滿足本地修復(fù)條件，則通知源節(jié)點，源節(jié)點則可直接通過調(diào)用備用路由繼續(xù)進行數(shù)據(jù)的傳送。

3.2 改進關(guān)鍵思想的實現(xiàn)

為了實現(xiàn)源節(jié)點維護兩條路由，需要修改原AODV路由協(xié)議的協(xié)議函數(shù)和路由表項以使源節(jié)點保存兩條最新的路由。首先分析節(jié)點中是否存在一條主路由，若存在，則比較目的節(jié)點序列號和路由跳數(shù)，若新的路由較優(yōu)，則將該新路由作為主路由，將原來的路由不刪除作為備用路由。若收到RREP的節(jié)點路由表中沒有路由，則直接將其作為主路由保存到路由表中?？傊ＷC將最優(yōu)和次優(yōu)路由作為主路由和備用路由。

在路由失效時，若斷裂的節(jié)點離目的節(jié)點較近時，進本地修復(fù)不僅可以快速進行路由維護減少數(shù)據(jù)包的丟失，也能減少源節(jié)點進行新的路由發(fā)現(xiàn)造成的路由開銷。為了控制本地修復(fù)的范圍，減少開銷，AODV 路由協(xié)議設(shè)置了能夠進行本地修復(fù)的最大修復(fù)長度(MAX_REPAIR_TTL)而且只有當下游節(jié)點斷開時才有可能進行本地修復(fù)。最大修復(fù)長度可以人為設(shè)定，文獻[7]發(fā)現(xiàn)隨著 AODV 路由協(xié)議本地修復(fù)的最大修復(fù)長度逐漸變大，數(shù)據(jù)分組投遞率也會逐漸變大。但若MAX_REPAIR_TTL過大，本地修復(fù)可能會適得其反，造成更大延時和開銷，當斷裂的節(jié)點離源節(jié)點較近時，重新發(fā)現(xiàn)路由可能更能發(fā)現(xiàn)最優(yōu)路由。因此本文中將發(fā)送斷裂的節(jié)點距目的節(jié)點跳數(shù)的參考值設(shè)為MAX_REPAIR_TTL+2。在某節(jié)點發(fā)生斷裂時，設(shè)該節(jié)點距目的節(jié)點的跳數(shù)為hop_count，根據(jù)斷裂節(jié)點與目的節(jié)點距離來判斷是否進行本地修復(fù)，分以下三種情況進行處理：

若hop_count為3跳以內(nèi)，則按原AODV方式進行本地修復(fù)。

若hop_count大于3小于MAX_REPAIR_TTL+2，則將本地修復(fù)定時器LOCAL_REPAIR_WAIT_TIME設(shè)為T1(T1值小于原AODV的定時值)，先進行本地修復(fù)，若T1時間內(nèi)修復(fù)不成功則發(fā)送RERR給源節(jié)點。

若hop_count1大于等于MAX_REPAIR_TTL+2，則直接發(fā)送RERR給源節(jié)點，收到RRER源節(jié)點檢查是否存在有效的備用路由，若存在則直接使用備用路由，若不存在則重新啟用路由發(fā)現(xiàn)機制。

3.3 改進后協(xié)議的工作過程

改進后的協(xié)議，如圖1所示，當源節(jié)點S要與目的節(jié)點D進行通信時，節(jié)點S沒有到D的有效路由，節(jié)點S會廣播一個RREQ分組發(fā)起路由查詢。一段時間后節(jié)點S會收到不同路由的RREP分組，同原AODV協(xié)議一樣，源節(jié)點S會選擇一條最優(yōu)路由作為路由發(fā)送數(shù)據(jù)。對與收到的其他RREP，源節(jié)點和周圍一跳節(jié)點范圍內(nèi)的節(jié)點選一條次優(yōu)路由保存在路由表中。當主路由失效斷裂時，首先判斷發(fā)生斷裂的節(jié)點離源節(jié)點和目的節(jié)點的距離，若發(fā)現(xiàn)離目的節(jié)點D較近，如圖1中節(jié)點4到目的節(jié)點斷裂，且發(fā)現(xiàn)節(jié)點4周圍鄰居節(jié)點數(shù)較多，則進行定時并開始本地修復(fù)，此時進行本地修復(fù)成功率一般較高，若在一定時限內(nèi)本地修復(fù)未成功，則向源節(jié)點報錯，源節(jié)點則進行相應(yīng)的處理。若發(fā)現(xiàn)斷裂的節(jié)點離目的節(jié)點較遠而離源節(jié)點距離較近，如圖1中節(jié)點8與節(jié)點9發(fā)送斷裂，則節(jié)點8直接向源節(jié)點S發(fā)送路由出錯RERR分組，源節(jié)點收到報錯后，直接調(diào)用備用路由繼續(xù)進行數(shù)據(jù)傳輸，若備份路由也失效，則源節(jié)點直接廣播RREQ分組發(fā)起新的路由建立過程。我們把改進后的AODV協(xié)議命名為AODVB(AODV with Backup route)協(xié)議。

圖1 簡單的拓撲結(jié)構(gòu)

4 仿真及分析

4.1 仿真模型建立

NS2是一種可擴展、可重用、基于離散事件驅(qū)動、面向?qū)ο蟮木W(wǎng)絡(luò)仿真軟件。NS2是一個用C++編寫，并且以O(shè)tcl為前段的 面向?qū)ο蟮哪M器。模擬器支持C++中類的層次接口和Otcl解釋器中類似的層次結(jié)構(gòu)。本文的仿真是在NS2中進行的，設(shè)定的運動場景如下：

50個移動節(jié)點的網(wǎng)絡(luò)，隨機分布在1500m×300m的平面矩形內(nèi)。節(jié)點的無線傳輸范圍默認為250m，節(jié)點間的最大連接數(shù)為30，分組的發(fā)送率設(shè)為4，即每秒發(fā)4個512字節(jié)的分組，隨機種子數(shù)設(shè)為1。節(jié)點到達目的節(jié)點后都停留60s，再往其他地方移動，整個模擬時間設(shè)定為900s，節(jié)點的最大移動速度分別設(shè)為0m/s，5m/s，10m/s，15m/s，20m/s和25m/s。節(jié)點的移動速度越大，表示網(wǎng)絡(luò)的拓撲結(jié)構(gòu)變化越頻繁。MAC 層協(xié)議采用的是 IEEE 802.11，無線電傳播模型是Two-Ray Ground Re-flections Model。

4.2 性能評估參數(shù)

選擇以下三個參數(shù)作為性能評估參數(shù)：

1.平均端到端延時：各目的節(jié)點收到數(shù)據(jù)分組的時間與相應(yīng)源節(jié)點生成數(shù)據(jù)分組的時間之差的平均值，丟棄的分組不統(tǒng)計在內(nèi)。

2.分組到達率：應(yīng)用層信宿接收到的分組數(shù)與信源發(fā)送的分組數(shù)之比，反映了網(wǎng)絡(luò)傳輸?shù)目煽啃?，投遞率越高，可靠性越大。

3.歸一化路由開銷指的是每發(fā)送一個數(shù)據(jù)報文所需要的路由控制報文數(shù)。使用歸一化路由開銷比單純使用路由開銷即路由控制分組更能說明協(xié)議的開銷情況。

4.3 仿真結(jié)果分析

從圖2可以看出，AODVB路由協(xié)議的延時要小于AODV路由協(xié)議。這是因為主路由失效時，AODVB能及時進行本地修復(fù)找到新的路由或使用備用路由，隨著節(jié)點移動速度的逐漸增大，網(wǎng)絡(luò)變化的也越快，AODV和AODVB的延時基本保持平穩(wěn)，體現(xiàn)了按需路由協(xié)議適應(yīng)網(wǎng)絡(luò)拓撲變化的優(yōu)點。

圖2 平均端到端延時比較

從圖3可以看出，由于網(wǎng)絡(luò)環(huán)境較復(fù)雜，分組到達率都較低，隨著節(jié)點移動速度的增加，分組的到達率整體都有下降的趨勢，但AODVB路由協(xié)議由于其改進的本地修復(fù)及帶有備用路由，減少了路由斷裂時重新發(fā)起路由建立而造成的分組丟失，其分組到達率要高于AODV路由協(xié)議。

圖3 分組到達率比較

圖4顯示了兩種路由協(xié)議的歸一化路由開銷情況，由圖可見隨著網(wǎng)絡(luò)變化的頻繁，路由開銷都有增大的趨勢，但AODVB由于其本地修復(fù)和備用路由的存在，減少了路由發(fā)現(xiàn)的次數(shù)，故減少了廣播分組新建路由，從而大大降低了路由開銷。

圖4 歸一化路由開銷比較

5 結(jié)論

針對AODV每次發(fā)起路由發(fā)現(xiàn)過程都會廣播RREQ報文，這個過程會造成網(wǎng)絡(luò)開銷的增加和延時的增大，本文提出了一種帶備用路由協(xié)議的改進型協(xié)議。仿真表明改進的路由協(xié)議在延時、到達率和路由開銷方面都得到了改善。后面的工作將研究如何減少RREQ的盲目廣播，進一步減少路由開銷，提高網(wǎng)絡(luò)性能。

[1]Perkings C，Royer E，Das S.Ad Hoc On-demand Distance Vector Routings[R].RFC3561，2003.

[2]Johnson D B，Maltz D A，Hu Yih-Chun.The dynamic source routing protocol for mobile ad hoc networks[EB/OL].http：//tools.ietf.org/html/draft-ietf-manet-dsr-10.2004-07.

[3]Perkins C E，Bhagwat P.Highly dynamic destination sequenced Distance Vector routing(DSDV) for mobile computers[C].Proc of ACM SIGCOMM，London，1994：134-244.

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

[5]張昱.Ad Hoc 網(wǎng)絡(luò)中避免路由斷裂的節(jié)能 AODV 算法改進[J].計算機工程與應(yīng)用，2006，(16).

[6]潘有芬，黃波，趙春霞.一種基于AODV的備用路由協(xié)議[J].通信市場，2012，(7).

[7]高芳，董澤，陸原，黃永平，陳義.移動Ad Hoc網(wǎng)絡(luò)路由協(xié)議系能仿真分析[J].華北電力大學學報，2008，35(2)：108-112.

ImprovementofAODVRoutingProtocolinMobileAdHocNetwork

YU Shuang-long，YU Ying

(Communication University of China，Beijing 100024，China)

As current AODV routing protocol maintain only one routing，re-initiate route establishment process would increase the routing delay and overhead.This paper established a routing protocol with a combination of an alternate route and local repair.First this paper introduced the Ad Hoc network and AODV routing protocol.Than it proposed an optimization method based on studying its inadequacies.The average delay，arrive ratio，normalized routing load were compared by simulating new routing protocol and the AODV routing protocol through NS2.Results indicated that the optimized protocol decreased the expense of network and showed better performance than AODV routing protocol.

Mobile Ad Hoc network；AODV routing protocol；alternate routing；NS2

2013-05-08

俞雙龍(1988-)，男(漢族)，安徽人，中國傳媒大學碩士研究生.E-mail：ahnuysl@126.com

TP393.03

A

1673-4793(2013)04-0062-05

(責任編輯：王謙)