AODV路由協議的研究和改進

何綿祿,褚 偉,劉輝舟

(合肥工業大學管理學院,合肥230009)

AODV路由協議的研究和改進

何綿祿,褚 偉,劉輝舟

(合肥工業大學管理學院,合肥230009)

針對移動Ad-hoc網絡中存在路由不穩定、數據丟包率高的問題,提出一種基于節點信號強度的AODV路由協議AODV-SS,該協議在原路由協議的基礎上增加了節點的信號強度和路由警告消息機制,將節點的信號強度作為建立路由的一個參照指標,當節點的信號強度較低時將不考慮該節點,尋找信號強度好的節點作為中間節點。在已建立好的路由中,若某個節點的信號強度低于一定的值時,將發出一個路由警告通知上游節點和源節點重新尋找新的路徑。NS2仿真實驗結果表明,當節點信號強度低于臨界點時,改進路由協議的丟包率比AODV路由協議低,路由更加穩定。

移動自組織網絡;AODV協議;路由請求;路由維護;信號強度

1 概述

Ad-hoc在拉丁語里面是“特別的”的意思,所以移動Ad-hoc網絡[1]是一種特殊的網絡結構,它是一種自組織網絡,具有多跳、沒有中心等特點。網絡中的所有節點都能夠將消息轉發,因此Ad-hoc網絡中的每個節點具有路由器的功能,可以負責網絡拓撲結構和路由信息的更新維護,以及對數據報進行轉發的功能,也可以作為主機維護網絡中的節點連接,完成對移動終端的基本功能。

由于Ad-hoc網絡結構的特殊性,其與普通的網絡結構相比具有如下的特點[2]:

(1)無中心:Ad-hoc網絡中的每個節點都具有路由器的功能,并沒有一個嚴格意義上的控制中心。所有的節點都是平等的,網絡的路由協議采用的是分布式的控制方式,使得整個網絡具有很強的穩定性,任何節點的加入、離開或者發生故障,都不會影響整個網絡的運行[3]。

(2)自組織:相對于傳統的網絡,Ad-hoc網絡的顯著特點就是組網時不需要依賴于任何預設的網絡設施,每個節點可以通過分層協議和分布式算法協調的自己行為,自動進行網絡的組建,節點運行時,自動形成一個獨立的網絡。

(3)多跳路由。Ad-hoc網絡中的每個節點都可以轉發數據包,所以當一個節點需要和它的信號覆蓋范圍外的節點通信時,就可以通過中間節點的數據報轉發功能建立路由。

(4)動態拓撲。Ad-hoc網絡中的每個節點都可以隨時的添加和刪除,會使網絡的拓撲結構隨時發生變化。

目前移動Ad-hoc網絡中的路由協議比較多,在眾多的路由協議中AODV更能適應Ad-hoc網絡的特點。但是由于移動Ad-hoc網絡中的節點移動性比較強等特點,造成了網絡中的路由不穩定,數據丟包率高,傳統的AODV路由協議已經不能解決在尋找新的路徑過程中造成的數據丟包嚴重的問題。

本文對原AODV路由協議進行了研究和改進,提出了一種新的路由協議AODV-SS(Ad hoc Ondemand Distance Vector Routing-Signal Strength),其中引入了路由警告消息機制,當路由中的某一個或幾個節點的信號強度低于某個值時,就會發出路由警告,尋找新的路徑,在新的路徑建立起來之前,這條路徑將繼續維持數據的傳輸。當節點的信號強度高于一定值時,就會沿長發送hello包的間隔時間。

2 AODV路由協議

AODV[4]路由協議是一種按需路由協議,是DSDV[5]和DSR[6]兩者綜合的產物,借鑒了DSR的路由發現機制和路由維護機制,以及DSDV中的跳數和路由維護過程中的周期更新機制,結合了兩者的優點,形成了一種優秀的按需路由協議。在一個特定網絡的可移動節點中使用本協議,它能在動態變化的點對點網絡中確定一條道目的地的路由,并且具有接入速度快、計算量小、內存占用低、網絡負荷輕等特點[7]。它在路由表中采用了目的序列號字段,確保了路由在任何時候都不會出現回環,即使路由控制星系出現異常的時候也不活產生回環,有效地避免了傳統網絡中出現的網絡回環和無窮計數問題。

AODV路由協議使用了3種消息機制[7],即路由請求(RREQ)、路由回復(RREP)和路由錯誤(RERR)。

2.1 AODV路由發現

AODV是一種按需路由協議,當源節點需要向目的節點發送數據包時,首先會在路由表中查找是否存在到目的節點的路由,若已存在該路由,則AODV路由協議會直接發送數據包到目的節點;反之,AODV路由協議就會通過廣播RREQ[7]包啟動路由發現過程,查找并建立相應的路由。

在AODV的路由發現過程中,中間節點和目的節點就會通過路由發現過程中建立的反向路由把RREP[8]包回發給源節點,其中RREQ分組中的源節點序列號就是用于維持到源節點的反向路由。當源節點把一個RREQ分組轉發到不同的目的節點的過程中所有節點都要自動創建到源節點的反向路由,節點通過收到的第一個RREQ分組的鄰居節點的地址來建立用于維護到源節點的反向路由,這些反向路由會維持一段時間,當RREQ分組到達目的節點時,目的節點就會產生RREP分組,RREP分組就會沿著剛剛建立起來的反向路由轉發RREP分組,在RREP分組轉發回源節點的過程中,沿著這條路徑上的每個節點都將建立到目的節點的同向路由。當源節點收到第一個RREP分組后,正向路由建立完成,此時就可以向目的節點發送數據包。

2.2 AODV路由維護

2.2.1 HELLO消息

在AODV路由協議中,當路徑建立起來以后,因為Ad-hoc網絡具有網絡拓撲動態變化的特點,路由中的每個節點可以隨時的加入或者離開,所以AODV路由協議中的節點需要不斷地監聽鄰居節點的控制消息,同時也需要維護本地鄰居節點的連接情況,為了實現這個目的,所以AODV路由協議引入了HELLO消息機制。

在HELLO消息機制中,一個節點通過定期廣播HELLO消息提供連接信息,可以確保鏈路的對稱,同樣也可以用于檢測鏈路是否失效。每當一個節點從鄰居節點收到一個hello消息,則確保了與鄰節點有一條有效路由。若不存在的路由,則需要新建。如果一條路由已經存在,那么這條路由的生命期應該增加。如果存在這條通向鄰居節點的路由,后來的hello消息包中必須包含節點最新的目的序列號。當前的節點可以使用這條路由轉發數據包。如果通過hello消息創建的路由沒有被其他活動的路由使用,它將擁有一個空的先驅表,如果鄰居節點移走或者超時不會觸發RRER消息。

2.2.2 本地連接維護

無論什么時候,每一個轉發消息的節點都應該對其與活動下一跳節點的連接性保持持續的跟蹤,也應該對在最近的ALLOWED_HELLO_LOSS?HELLO_INTERVAL時間內曾經發送過Hello消息的鄰居節點進行跟蹤。通過使用一個或多個可用連接或者網絡層的機制,節點可以維護關于其與這些活動下一跳節點之間連接的準確信息。

2.2.3 路由錯誤,路由超時和路由刪除

由于Ad-hoc的網絡拓撲結構是動態的,網絡中的節點不可預測性,導致Ad-hoc網絡易發生路由錯誤和連接中斷的情況,因此AODV路由協議會在以下3種情況下發出路由錯誤消息,通知前驅節點。

(1)當傳送數據或嘗試路由回復未果時,如果節點在路由表中,節點檢測到某個活動的路由上的下一跳發生了連接中斷,則發出RERR消息。

(2)如果節點接收到了一個數據包,本節點沒有活動路由而且也沒有修復時,則發出RERR消息。

(3)如果節點從鄰節點接收到了一個或者多個活動路由的RERR消息時,則發出RERR消息。

2.3 AODV路由表管理

AODV路由表[9]的數據結構中包含了源節點和目的節點的序列號,還包含了目的IP地址、網絡接口索引等其他的有用的信息,這些信息組成了路由項的軟狀態。例如,路由請求定時器,定時器的目的就是消除一段時間沒有使用的方向路由項。設置定時器取決于網絡規模的大小,另一個重要的參數與路由表的路由緩存相關的時間,超過這個時間后,相應的路由表變得無效。

AODV路由協議在執行過程中,在用戶層的路由表中,程序定義了各種操作函數,可以輕易地對路由表項進行刪除和添加等操作。

3 改進路由協議的基本思想

改進路由協議的過程如下:

(1)在原AODV路由協議消息機制的基礎上添加了路由警告(RWARN)消息機制,用于通知上游節點和源節點,這個節點已經不足以維持整條路徑的穩定性,需要尋找新的節點建立新的路由。

(2)在改進的AODV路由協議中添加2個信號強度的臨界點,HIGH表示信號強度高于80%的狀態,信號非常好;LOW表示信號強度低于30%的狀態,這時信號就比較不穩定。需要重新建立路徑。

(3)鄰節點收到RREQ分組的處理方法

1)首先檢查該分組是否是由本節點產生的,如果是,則丟棄。如果這個節點以前接收過相同的RREQ消息,則比較本節點的信號強度與路由表項中的信號強度關系,如果比路由表項中的信號強度強,說明2個節點的相對位置變化了,則更新路由信息,否則,這個節點就會丟棄這個RREQ分組,不作任何操作。

2)若這個節點就是目的節點,分析這個節點的信號強度,若信號強度低于LOW,則發送RREP回應同時發出來一條路由警告,建立路由,將節點的相關信息保存到路由表中,并告訴源節點這條路徑不穩定,在進行通信的同時需要重新發出RREQ消息搜索路徑。

3)如果該節點不是目的地,而是知道到目的節點的新路徑,檢查該節點的信號強度,若當前節點的信號強度低于LOW時,作出響應并沿反向路由發出警告消息,需要重新發出RREQ路由請求;若信號強度高于LOW,則直接進行響應。并在源節點和目的節點的前驅列表中分別插入到源節點和目的節點的下一跳節點。

4)如果節點不是目標節點,也不知道到目的節點的路由,則檢查信號強度,若低于臨界點,則繼續轉發數據包,并沿反向路由發出路由警告,跳數加1;否則直接將跳數加1,繼續轉發。

(4)AODV-SS路由選擇

當中間節點或者目的節點把RREP分組回發到源節點時,這時所需要的反向路由和同向路由建立起來。然后查看路由表,若路由表中沒有到目的節點的路由,則把該路由加入到路由表中,若路由表中已經存在一條到目的節點的路由,先根據式(1)計算出2條路由信號強度的平均數,去掉較大的路由,若平均信號強度相同則,計算根據式(2)方差,取方差較小的路徑,則將另一條路由標記為無效,并刪除。

其中,Si表示的路由中每個節點的信號強度;n表示目的節點中跳數;表示路由中的平均信號強度。

(5)AODV-SS路由維護

與AODV路由協議相同,AODV-SS也使用hello消息機制定期廣播HELLO包,在廣播HELO包的同時,檢查節點的信號強度,如果信號強度高于HIGH時,則沿長HELLO包廣播的間隔時間,這樣可以減少信道的浪費。當信號強度低于LOW的時候,發出路由警告,通知鄰節點重新發出RREQ消息,尋找信號強度更好的路徑,當新的路徑建立起來以后,則刪除原有路徑。

若某個活動節點突然發生中斷時,即該節點的信號強度突然消失,則發出RERR消息通知前驅節點。前驅節點或源節點收到RERR消息,將從路由表中刪除不可達節點,重新發送RREQ分組,建立新的路由。

4 改進的AODV路由協議AODV-SS

移動Ad-hoc網絡中的每個節點相當于無線路由器,可以完成數據轉發功能,無線網絡的傳輸速率和數據的傳輸的成功率都與無線路由的信號強度有很大的關系,信號強度越強,傳輸成功率就越高,在移動的環境中,信號強度變化大,存在由強變弱,節點直接的相互距離增大,所以為了提高數據的傳輸成功率,提出了一種基于信號強度的AODV路由協議AODV-SS。AODV-SS在源協議基礎上增加了獲取節點的信號強度函數,在建立鏈路和維護鏈路的過程中,把相互間的信號強度作為參數,并且添加了RouteWarn(RWARN)作為控制消息。

4.1 節點信號強度的獲取

改進后的AODV路由協議,其中的關鍵點就是要獲取每個節點的信號強度。在Linux環境下,可以通過對設備輸入輸出通道進行管理的函數iotcl()來獲取節點的信號強度。ioctl函數原型為ioctl(int fd,int command,(char?)argstruct),其中,fd是由socket()系統調用返回的文件描述符,command的取值為SIOCGIWSTATUS,argstruct為structiwreq。

在AODV路由協議中添加如下函數:

4.2 路由警告消息格式

路由警告(RWARN)消息格式如圖1所示。

圖1 路由警告消息格式

當某個節點的信號強度低于LOW時,這時候這個節點已經不能滿足數據傳輸的安全性了,丟包率已經開始增加,則需要發出警告信息給源節點,通知源節點重新發出RREQ分組,尋找新的路徑。

4.3 改進后路由表的數據結構

在原有路由表的數據結構的基礎上,添加了下一跳的信號強度,其路由表的數據結構如表 1所示[10]。

表1 AODV路由表的數據結構

4.4 改進的路由回復

傳統的AODV路由回復的消息格式中包含的一些主要的信息為跳數、目的IP地址、目的序列號、源IP地址、源序列號、生命期等。

通過 AODV路由協議的研究,在源協議的RREP基礎上,添加了本節點的信號強度字段,其數據格式如表2所示。

表2 路由回復數據格式

4.5 路由網絡拓撲圖

AODV-SS路由協議中,路由發現的過程如圖2所示,當源節點S需要向目的節點D發送數據時,源節點就會向節點1和節點4發出RREQ消息分組,當節點1和節點4收到RREQ時,若節點1知道,通向目的節點D的最新路由,則節點1沿反向路由發出RREP作出響應,并沿著節點1所知道的路由經過節點2和節點3到達目的節點 D建立路由。節點4將繼續轉發RREQ分組到節點5,由節點5將繼續轉發,最終到達目的節點D,目的節點D將沿反向路由回發RREP作出響應,由于節點D已經接受過相同的RREQ分組,此時路由表中將會分析2條路由信號強度的平均值,選擇最優的路由。

圖2 路由發現

在建立路由的過程中,若節點3的信號強度低于LOW時,則發出一跳路由警告消息通知上游節點該路由不穩定,需要繼續尋找新的路由。

AODV-SS路由維護如圖3所示。當圖中路由S-4-5-D最優時,則路由已經建立加入路由表中。隨著節點的移動,若中間節點5的信號強度越來越弱,則節點5會沿著反向路由發出路由警告,通知上游節點和源節點重新尋找路由,繼續發出RREQ分組。當節點2收到節點1和節點4的RREQ分組時,比較2個節點的信號強度,選擇最優的,這里選擇節點1的,丟棄節點4的RREQ分組。

圖3 路由維護

在路由建立過程中,當每一個節點收到RREQ分組時,都會檢查節點本身的信號強度,當信號強度比較弱的時候,在建立路由的同時,還需要沿反向路由發出RWARN消息,通知上游節點和源節點要重新發送RREQ分組,繼續尋找新的路徑,當更穩健的路由建立起來后,從路由表中刪除源路由。

5 AODV-SS路由協議的性能仿真與分析

為了對AODV-SS路由協議的性能進行分析,采用當前比較流行的仿真軟件 NS2[11-12]對 AODV, AODV-SS路由協議進行性能仿真,主要通過仿真得到改進后的AODV路由協議與原路由協議的丟包率,通過丟包率來衡量路由協議的性能。

5.1 仿真環境

實驗采用的仿真環境為在1 000 m×1 000 m的矩形區域,隨機生成50個節點,并針對節點的信號強度0～100%區間內的節點的丟包率進行仿真實驗,使用Trace文件記錄實驗過程中的數據、用gawk程序提取和處理數據、用gnuplot工具繪制二維圖對AODV和AODV-SS的丟包率進行性能分析。仿真環境的參數如表3所示。

表3 仿真參數及取值

5.2 仿真結果與分析

本文根據節點的不同型號強度對 AODV和AODV-SS路由協議進行的丟包率進行仿真測量,測量結果如圖4所示。

圖4 節點丟包率

由圖4可知,當節點的信號強度高于30%時,路徑比較穩定,AODV和AODV-SS路由協議的丟包率差別不大,但是當信號強度低于30%時,原路由協議繼續按照以前的路徑發包,而改進后的路由協議就開始重新尋找路徑建立新的路由發包,由圖可見,改進后的路由協議的丟包率明顯低于原路由協議,性能優于AODV路由協議。

6 結束語

本文對原AODV路由協議進行了研究和改進,提出了一種新的路由協議AODV-SS。改進的AODV路由協議加入了信號強度字段和路由警告消息,在建立路徑時,信號強度低于LOW的中間節點將不作考慮,這樣建立的路徑將更加穩定。在路由維護時,當某個節點的信號強度低于LOW時,將發出路由警告消息,通知上游節點和源節點重新發送RREQ分組,尋找新的路徑,在新路徑建立起來以前,舊路徑將繼續用于傳送數據。通過改進使得建立的路由更加穩健,信號傳輸的丟包率大大減少。

[1] 臧小東.Ad-hoc網絡路由協議的改進研究[D].南京:南京郵電大學,2013.

[2] Ad-hoc網絡結構[EB/OL].[2013-10-10].http:// baike.baidu.com/view/28428.htm?fromId=632724.

[3] 陳 玲,王 華.移動 Ad-hoc網絡路由協議的研究[J].微計算機信息,2006,22(3):167-169.

[4] Kumar P,Kumar R.Improved Modified Reverse AODV Protocol[J].International Journal of Computer Applications,2010,12(4):22-26.

[5] 王北光,李立新,謝 濤.移動Ad-Hoc網絡DSR路由協議的改進[J].計算機技術與發展,2011,21(8): 121-128.

[6] 吳全玉,孫怡寧.井下無線傳感器網絡 AODV和DSDV協議的仿真對比[J].傳感技術學報,2009, 22(10):1515-1518.

[7] Perkins C,Belding E,Royer B,et al.Ad-Hoc on Demand DistanceVector(AODV) Routing[S]. RFC 3561,2003.

[8] 陳曉曙,李 霞.一種高效的Ad-hoc網絡AODV改進路由協議[J].東南大學學報,2003,33(2):127-130.

[9] 張愛民,馬志強,易曉蓉.Ad-hoc路由協議實現技術[J].計算機系統應用,2011,20(7):165-168.

[10] 徐四委.基于AODV的物聯網路由協議的研究[D].沈陽:遼寧大學,2012.

[11] 李 勇,周麗芬.基于NS2平臺的AODV路由協議仿真研究[J].現代計算機,2013,(3):52-55.

[12] 王 輝.NS2網絡模擬器的原理和應用[M].西安:西北工業大學出版社,2008.

編輯 索書志

Research and Improvement of AODV Routing Protocol

HE Mianlu,CHU Wei,LIU Huizhou
(School of Management,Hefei University of Technology,Hefei 230009,China)

This paper improves Ad-hoc On-demand Distance Vector(AODV)routing protocol and proposes AODVSignal Strength(AODV-SS)routing protocol which is based on signal strength of node.The AODV-SS routing protocol increases the warning message of routing and signal strength of node.The signal strength as a reference indicator when it establishes the routing.It does not consider this node if the signal strength of node is lower than critical point when establishing the routing.It finds a node as intermediate node of which the signal strength is better than critical point.In the established route,it sends a warning message of routing to the upstream node and the source node when the signal strength is lower than critical point.Simulation experimental results of NS2 show that the improved routing protocol packet loss rate is lower than AODV routing protocol when the signal is not good,and the route is more stable.

mobile Ad-hoc network;Ad hoc On-demand Distance Vector(AODV)protocol;Route Request(RREQ); route maintaining;signal strength

1000-3428(2015)01-0110-05

A

TP391

10.3969/j.issn.1000-3428.2015.01.020

何綿祿(1988-),男,碩士研究生,主研方向:Ad-hoc網絡,信息化管理;褚 偉,副研究員、博士;劉輝舟,碩士研究生。

2013-11-25

2014-02-21 E-mail:hfuthml@126.com

中文引用格式:何綿祿,褚 偉,劉輝舟.AODV路由協議的研究和改進[J].計算機工程,2015,41(1):110-114.

英文引用格式:He Mianlu,Chu Wei,Liu Huizhou.Research and Improvement of AODV Routing Protocol[J].Computer Engineering,2015,41(1):110-114.