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

俞雙龍，于瀛

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

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

俞雙龍，于瀛

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

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

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

1 引言

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

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

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

2 AODV路由協(xié)議

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

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

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

3 改進(jìn)的AODV算法

3.1 改進(jìn)思想

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

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

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

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

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

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

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

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

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

圖1 簡單的拓?fù)浣Y(jié)構(gòu)

4 仿真及分析

4.1 仿真模型建立

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

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

4.2 性能評(píng)估參數(shù)

選擇以下三個(gè)參數(shù)作為性能評(píng)估參數(shù)：

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

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

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

4.3 仿真結(jié)果分析

從圖2可以看出，AODVB路由協(xié)議的延時(shí)要小于AODV路由協(xié)議。這是因?yàn)橹髀酚墒r(shí)，AODVB能及時(shí)進(jìn)行本地修復(fù)找到新的路由或使用備用路由，隨著節(jié)點(diǎn)移動(dòng)速度的逐漸增大，網(wǎng)絡(luò)變化的也越快，AODV和AODVB的延時(shí)基本保持平穩(wěn)，體現(xiàn)了按需路由協(xié)議適應(yīng)網(wǎng)絡(luò)拓?fù)渥兓膬?yōu)點(diǎn)。

圖2 平均端到端延時(shí)比較

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

圖3 分組到達(dá)率比較

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

圖4 歸一化路由開銷比較

5 結(jié)論

針對(duì)AODV每次發(fā)起路由發(fā)現(xiàn)過程都會(huì)廣播RREQ報(bào)文，這個(gè)過程會(huì)造成網(wǎng)絡(luò)開銷的增加和延時(shí)的增大，本文提出了一種帶備用路由協(xié)議的改進(jìn)型協(xié)議。仿真表明改進(jìn)的路由協(xié)議在延時(shí)、到達(dá)率和路由開銷方面都得到了改善。后面的工作將研究如何減少RREQ的盲目廣播，進(jìn)一步減少路由開銷，提高網(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ìn)[J].計(jì)算機(jī)工程與應(yīng)用，2006，(16).

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

[7]高芳，董澤，陸原，黃永平，陳義.移動(dòng)Ad Hoc網(wǎng)絡(luò)路由協(xié)議系能仿真分析[J].華北電力大學(xué)學(xué)報(bào)，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-)，男(漢族)，安徽人，中國傳媒大學(xué)碩士研究生.E-mail：ahnuysl@126.com

TP393.03

A

1673-4793(2013)04-0062-05

(責(zé)任編輯：王謙)