《電子技術應用》
您所在的位置：首頁 > 通信與網絡 > 設計應用 > 一種支持高速移動自組織網絡的路由協議
一種支持高速移動自組織網絡的路由協議
來源：電子技術應用2010年第5期
楊共燕, 鄺育軍, 隆克平
電子科技大學 光互聯網與移動信息網絡研究中心, 四川 成都 611731
摘要： 傳統(tǒng)的AODV（Ad-hoc On-demand Distance Vector）路由協議只以路由跳數為度量，沒有考慮到鏈路穩(wěn)定情況，因此,，無法更好地適應節(jié)點高速移動的網絡環(huán)境。為此,，提出了一種改進的AODV路由協議，即IMAODV（Improved AODV）路由協議。該協議主要從路由度量值、HELLO消息的發(fā)送頻率,、鄰居節(jié)點的監(jiān)聽方式等幾個方面對AODV進行改進，使之在移動網絡中具有較好的擴展性和魯棒性,。仿真結果表明，IMAODV協議能夠較好地適應高速移動的網絡環(huán)境，并在一定程度上降低網絡時延和增加網絡吞吐量,。
中圖分類號: TP391.9
文獻標識碼: A
A routing protocol for high speed mobile Ad-hoc networks
YANG Gong Yan, KUANG Yu Jun, LONG Ke Ping
Research Center of Optical Internet and Mobile Information Networks, University of Electronic Science and Technology of China, Chengdu 611731, China
Abstract： The traditional AODV’s routing metric, which is based on the hops, does not take the link stability into account, so it can not meet circumstances with high speed mobile network very well. In this paper, we propose a novel routing protocol named IMAODV (Improved AODV), which primarily improves the following aspects compared with AODV routing protocol: routing metric, the sending frequency of HELLO messages, and the neighbor monitor schemes. It can make AODV more expansibility and robust in mobile network. The simulation results show that IMAODV can work well for the high speed Mobile networks, and at the same time it can reduce average end-to-end delay and improve the throughput of ad hoc networks.
Key words : mobile Ad Hoc networks; AODV; combined metric; IMAODV

    移動自組網（MANET）是由一系列移動終端組成的無固定基礎設施的多跳自組織網絡系統(tǒng)[1],，其拓撲結構因為節(jié)點電量不足或是移動而變化，所以MANET的路由協議與傳統(tǒng)網絡的路由協議有著很大的區(qū)別,。
　目前,移動網絡中較成熟,、較典型的路由協議有DSDV、DSR,、AODV,、ZRP等[2]。其中,，AODV路由協議[3]是一種經典的按需路由協議,，它在一定程度上比其他協議有較小的路由開銷和更好的擴展性能，但是這種路由協議在網絡拓撲頻繁變化的情況下,路由斷鏈的幾率很大,，其網絡性能下降很快,，無法保證較高要求的服務質量。
　針對高速移動自組網的特性,，本文提出一種基于AODV的改進路由協議,，即IMAODV，它在路由度量值,、斷鏈修復策略以及HELLO消息機制上做了修改,，使之能有效地降低網絡延遲，提高網絡的吞吐量,。通過NS2仿真可以看到,，本文提出的IMAODV路由協議與傳統(tǒng)的AODV路由協議相比具有一定的優(yōu)勢：它既能降低中高速移動自組網的網絡延時，又能在一定程度上提高網絡吞吐量,；同時,，IMAODV路由協議能夠較好地適應無線網絡環(huán)境，有效提高網絡性能,。
1 IMAODV路由算法
1.1 AODV
　傳統(tǒng)自組網路由協議可分為主動路由協議和按需路由協議[4],，由于移動自組網存在著動態(tài)多變特性，主動路由協議應用在移動網絡中有著明顯的缺陷,，所以實際中經常使用的都是按需路由協議[5],。
   AODV是Ad-hoc網絡的經典路由協議，它是由路由發(fā)現和路由維護組成,。路由發(fā)現過程如圖1所示,。而在路由維護中,節(jié)點通過周期性地發(fā)送HELLO包維持與鄰居節(jié)點的連接，若一段時間后還未收到鄰居節(jié)點的HELLO包,，則開始鏈路修復過程,。若本節(jié)點離目的節(jié)點較近,，則進行本地修復，發(fā)送RREQ進行路由重建,，當中間節(jié)點有到不可達節(jié)點的有效路由或者不可達節(jié)點收到此RREQ后就發(fā)送一個路由回復RREP給源節(jié)點,，這樣路由就得到了重建。若鏈路修復失敗,，則節(jié)點向所有的鄰居節(jié)點廣播RERR包,，RERR包中的不可達節(jié)點列表不僅包括了鏈路斷開的鄰居節(jié)點，還包括了以此鄰居節(jié)點作為下一跳的所有目的節(jié)點,。通過RERR的廣播,，其他節(jié)點便知道鏈路斷開了，當此包傳到源節(jié)點時,，將進行新一輪的路由發(fā)現,。

1.2 IMAODV路由算法
　AODV雖然也能適應動態(tài)變化的網絡，但是它的機制并不靈活,不能根據網絡環(huán)境動態(tài)調節(jié)發(fā)送頻率,，再者路由度量值僅僅考慮了跳數信息,，且路由單一，所以不能滿足移動環(huán)境較為復雜或移動速度較高的網絡環(huán)境,。為了更好地滿足移動自組網的服務要求,，本文將針對高速移動環(huán)境提出的IMAODV，在AODV協議的基礎上做出以下改進,，以改善網絡的吞吐量和平均端到端延遲,。
1.2.1節(jié)點度量值的選取
    以跳數為度量的AODV,容易造成大量數據通過少量節(jié)點傳輸引起網絡的阻塞，而導致分組延時過大,，吞吐量下降[6],。為了緩解這種情況，本文在路由度量值的選取中將考慮以下因素：
    節(jié)點移動速度：節(jié)點的移動速度越大,，鏈路越不穩(wěn)定,，所以在選擇路由時要選移動速度較低的中間節(jié)點，避免因節(jié)點移動造成斷鏈的路由重啟過程,，以降低網絡開銷,。
    延遲：路由過程中，延遲越小,，數據傳輸才能顯示其時效性,。
　 跳數：跳數越少，在某種程度上,，所消耗的網絡資源越少,。
　 考慮到節(jié)點的計算復雜度，路由度量值：
   
其中hop代表跳數,，nodenum表示網絡總的節(jié)點數,，delay代表上一跳節(jié)點到本節(jié)點的延遲,，speed代表本節(jié)點的移動速度，max speed代表網絡中節(jié)點的最大移動速度,，w1,、w2和w3分別代表權值,其中，w1+w2+w3=1,，本協議中w1、w2和w3的值分別取為0.7,、0.2和0.1,。當metric的值越小，路由鏈路的穩(wěn)定度越高,，網絡延遲越小,。
1.2.2 節(jié)點功能的改進
　傳統(tǒng)AODV中源節(jié)點只保留一條到目的節(jié)點的路由，當主路由上的鏈路斷開時,，源節(jié)點重新開始進行路由發(fā)現幾率較大,，容易造成過大的路由開銷和較大時延。為改善這種情況,，本文提出的IMAODV,，利用無線通信中廣播信道偵聽到的相鄰節(jié)點發(fā)給其他節(jié)點的RREP信息建立備用路由[7-8],通過增加節(jié)點的功能,使之具有監(jiān)聽路由控制信息的能力。
1.2.3 Hello機制的改進
   IMAODV中對HELLO消息做兩方面改進： (1)是為HELLO消息設置了一個標志,。初始化為TURE,，節(jié)點發(fā)送HELLO消息，當節(jié)點有路由或數據信息需要廣播時,，標志設為FALSE,。如果HELLO發(fā)送周期再次到來，先檢查標志,，如果為FALSE,，則改變狀態(tài)為TURE后不作任何處理，直至下一個周期的到來,，再繼續(xù)檢查標志,；當標志為TURE時，則發(fā)送HELLO消息,，同時每個節(jié)點在接收路由包或是數據包的時候,，要更新鄰居的生存時間，這樣可以降低發(fā)送HELLO消息的開銷,。(2)由于節(jié)點的移動,，會造成網絡拓撲的變化，HELLO消息的固定發(fā)送肯定不能有效地捕捉到網絡拓撲信息,，為了保證鏈路的有效性,，本文將根據節(jié)點自身的速度來調節(jié)HELLO包的發(fā)送頻率,發(fā)送頻率與節(jié)點的移動速度成正比,，流程如圖2所示。

1.2.4 鏈路修復的改進
   由于IMAODV路由中每個節(jié)點對路由應答包具有偵聽功能,，所以主路徑上節(jié)點的一跳鄰居都能夠偵聽到此包,，所以都能通過主路徑上的節(jié)點建立到目的節(jié)點的路由，這樣就形成了多個到目的節(jié)點的備份路由,。當主路由上的某條鏈路斷開時,，便可以通過路由請求RREQ進行局部修復。為了減小路由請求的開銷,，本文設置了路由請求的生存期為2跳,，中間節(jié)點收到路由請求時，若路由生存期不為0,，則查找自己是否有到目的節(jié)點的路由,。若有，則按原AODV的方式進行應答,，若沒有則繼續(xù)廣播路由請求消息,，直到生存期變?yōu)?時丟棄包。當局部修復失敗時,，節(jié)點再廣播路由錯誤包,。
1.2.5 IMAODV路由協議
　IMAODV在路由請求、路由應答以及路由表中添加metric字段,，以記錄路徑上每個節(jié)點的累計路由度量值,。當源節(jié)點需要通信路由時，先初始化metric為0,，再廣播這個RREQ包啟動路由發(fā)現過程,。中間節(jié)點的路由表段中添加一個rt_metric，記錄從源節(jié)點到該節(jié)點路徑上的路徑度量最小值,，中間節(jié)點收到非重復的RREQ包時,，將自身的metric值累加到路由RREQ中的rq_metric上，再繼續(xù)轉發(fā),。如果節(jié)點已經收到了同一源節(jié)點相同的廣播ID的RREQ,，且包的目的序列號大于路由表中序列號，則直接更新路由,，若相等就通過比較rq_metric與rt_metric,，選較小者作為本路由表項中的rt_metric，即更新路由表項再轉發(fā)包,。當路由請求包到達目的節(jié)點時,，目的節(jié)點將選擇一個擁有較小metric的路由，發(fā)送路由回復RREP,。路由應答是以單播的方式傳送,，接收到此包的節(jié)點時,首先根據接收包中下一跳信息判斷本節(jié)點是監(jiān)聽節(jié)點還是正常的路由應答節(jié)點,如下一跳ID不等于本節(jié)點ID,，則本節(jié)點是監(jiān)聽節(jié)點，此時記錄到目的節(jié)點的路由后不再轉發(fā),否則是主路徑上的節(jié)點,，則按照傳統(tǒng)AODV路由應答的方式進行處理,。圖3為IMAODV路由建立的流程。
   在圖3中,，路由建立或更新是根據路由序列號和路由度量值來決定的,。如果是第一次收到路由請求包，則建立路由,；若收到請求包中的目的節(jié)點序列號大于路由表中存儲的目的節(jié)點序列號或是等于路由表中存儲的目的序列號,，但路由表中的路由度量值大于請求包中的路由度量值，則更新路由,。“是否忽略”檢查是否收到重復的包，若是,，則丟棄,；否則更新路由表和請求包信息再轉發(fā)。

2 仿真分析
2.1仿真環(huán)境
　仿真工具采用NS-2.30[7]版本,，網絡的拓撲環(huán)境是一個包含50個移動節(jié)點的網絡模型,，節(jié)點隨機分布在1 000 m×1 000 m的正方形區(qū)域內，并設置節(jié)點的移動速度在0 m/s~40 m/s之間,每個節(jié)點的無線接口帶寬為2 Mb/s,有效無線發(fā)射范圍為250 m,鏈路層采用無線802.11 MAC協議,在50個節(jié)點中隨機產生4對恒定比特率的CBR連接,，每個分組的長度為512 B,每秒發(fā)送4個包,為了考察改進的協議在網絡仿真環(huán)境中的性能,，本文將模擬節(jié)點速度在0~20 m/s時由于停留時間(pause time)、網絡中節(jié)點間最大連接數以及節(jié)點的速度的變化對網絡吞吐量的影響,，還有節(jié)點移動速度變化對網絡平均端到端延遲的影響,設置了在相同環(huán)境下與AODV作比較,，給出了仿真結果。
2.2 仿真結果及性能分析
   圖4顯示了端到端延遲與節(jié)點移動速度的關系,，由此可知IMAODV協議的平均端到端延遲隨節(jié)點移動速度的增大優(yōu)于AODV協議,，其原因是在路由度量中考慮了每一跳的延遲，且改進的HELLO機制的發(fā)送頻率與節(jié)點移動速度有關,，能較快地發(fā)現路由斷鏈情況并做出相應處理,。圖中節(jié)點最大速度為5 m/s時，由于處于低速狀態(tài),，IMAODV優(yōu)勢并不突出,，較AODV的延遲大，但是隨著節(jié)點的移動速度的增加,，IMAODV的平均端到端延遲低于AODV,；當節(jié)點最大移動速度達到40 m/s時，IMAODV的延遲約為AODV延遲的1/2,。從總體來看,隨著節(jié)點移動速度的增加,，IMAODV延遲有所下降,。

   圖5中IMAODV在路由度量值和HELLO消息機制中考慮到節(jié)點移動速度的影響，并且節(jié)點具有偵聽路由應答的功能,，使其具有多條到目的節(jié)點的路由,。這樣在斷鏈的時候能夠及時地恢復路由，進行數據傳輸,，隨著節(jié)點速度的提高,，IMAODV的吞吐量明顯優(yōu)于AODV，如圖5所示,在節(jié)點最大移動速度為10 m/s和15 m/s時,，IMAODV能提供比AODV高29.4%和34.3%的網絡吞吐量,。
   圖6中反映了節(jié)點停留時間與吞吐量的關系，此時場景中節(jié)點的最大移動速度為20 m/s,停留時間在40  s,、50 s以及150 s時,，IMAODV的吞吐量較AODV略有下降，原因是這些場景中中間節(jié)點的移動速度較小,，由于新協議中路由度量是多個方面的折中考慮,，所以在移動速度不明顯的時候，IMAODV的優(yōu)越性就不太明顯,，但總體性能較AODV好,。

　圖7是最大節(jié)點移動速度為20 m/s時，網絡中節(jié)點連接增加對網絡吞吐量的影響,。圖中兩個協議的吞吐量都隨著網絡中節(jié)點連接數的增加而增大,。明顯地，由于考慮了節(jié)點的移動速度,，改進后的協議能夠較快地捕捉節(jié)點間的斷鏈情況,，并做出較快的路由重建處理，使得圖中IMAODV比AODV能產生較高的吞吐量,。

　本文針對移動自組織網絡中節(jié)點的移動速度對路由協議的影響對AODV協議做了改進,，提出了一種新的改進路由協議IMAODV(Improved AODV)。該協議在對HELLO消息機制及路由修復機制做出優(yōu)化的同時,，在MAC層做了優(yōu)化以使節(jié)點具有偵聽功能,，使之能夠在節(jié)點以中高速運動的條件下建立較穩(wěn)定的路由，降低了分組傳輸端到端的平均延遲,，并提高了網絡的吞吐量,。仿真結果表明，該協議能較好地適應移動自組織網絡的通信環(huán)境,。
    下一步工作將對路由協議做多接口擴展和跨層的優(yōu)化處理,，以進一步提高路由算法的性能。
參考文獻
[1]     RFC2501. Mobile Ad hoc networking (MANET): Routing protocol performance issues and evaluation considerations[s]
[2]     王金龍，王呈貴. Ad Hoc移動無線網絡[M]. 北京：國防工業(yè)出版社,，2004：81-83
[3]     RFC3561. Ad hoc on-demand distance vector (AODV)Routing [S].
[4]     PERKINS C E. Ad hoc on demand distance vector Routing [J]. Mobile Computing Systems and Applications, 1991.
[5]     王力超,林綠洲,陸起涌. 基于AODV的改進型ad hoc路由協議,儀器儀表學報,， 2006,27(6).
[6]     PERKINS D D, HUGHES H D, OWEN C B. Factors  affecting the performance of Ad hoc networks[C]. IEEE  International Conference on Communications,2002.Michigan    State University, 2002:2048-2052.
[7]     LWW S J, MARIO G AODV-BR: Backup routing in Ad hoc networks[C]. IEEE Wireless Communications and Networking Conference,2000(WCNC 2000),2000,3:1311-1316.
[8]     鄭相全，郭偉,，李帆. 自組網AODV路由協議中鍛煉修復的改進[J].電子科技大學學報,，2003,32(5).
[9]     NS2[OL]. http://nsnam.isi.edu/nsnam/index.php.

此內容為AET網站原創(chuàng)，未經授權禁止轉載,。