移動Ad Hoc網絡AODV路由協議的改進

俞雙龍，于瀛

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

移動Ad Hoc網絡AODV路由協議的改進

俞雙龍，于瀛

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

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

移動Ad Hoc網絡；AODV路由協議；備份路由；NS2

1 引言

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

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

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

2 AODV路由協議

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

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

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

3 改進的AODV算法

3.1 改進思想

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

3.2 改進關鍵思想的實現

為了實現源節點維護兩條路由，需要修改原AODV路由協議的協議函數和路由表項以使源節點保存兩條最新的路由。首先分析節點中是否存在一條主路由，若存在，則比較目的節點序列號和路由跳數，若新的路由較優，則將該新路由作為主路由，將原來的路由不刪除作為備用路由。若收到RREP的節點路由表中沒有路由，則直接將其作為主路由保存到路由表中。總之保證將最優和次優路由作為主路由和備用路由。

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

若hop_count為3跳以內，則按原AODV方式進行本地修復。

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

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

3.3 改進后協議的工作過程

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

圖1 簡單的拓撲結構

4 仿真及分析

4.1 仿真模型建立

NS2是一種可擴展、可重用、基于離散事件驅動、面向對象的網絡仿真軟件。NS2是一個用C++編寫，并且以Otcl為前段的 面向對象的模擬器。模擬器支持C++中類的層次接口和Otcl解釋器中類似的層次結構。本文的仿真是在NS2中進行的，設定的運動場景如下：

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

4.2 性能評估參數

選擇以下三個參數作為性能評估參數：

1.平均端到端延時：各目的節點收到數據分組的時間與相應源節點生成數據分組的時間之差的平均值，丟棄的分組不統計在內。

2.分組到達率：應用層信宿接收到的分組數與信源發送的分組數之比，反映了網絡傳輸的可靠性，投遞率越高，可靠性越大。

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

4.3 仿真結果分析

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

圖2 平均端到端延時比較

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

圖3 分組到達率比較

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

圖4 歸一化路由開銷比較

5 結論

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

[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與網絡模擬[M].北京：人民郵電出版社，2003.

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

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

[7]高芳，董澤，陸原，黃永平，陳義.移動Ad Hoc網絡路由協議系能仿真分析[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

(責任編輯：王謙)