《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計應(yīng)用 > 一種支持高速移動自組織網(wǎng)絡(luò)的路由協(xié)議
一種支持高速移動自組織網(wǎng)絡(luò)的路由協(xié)議
來源：電子技術(shù)應(yīng)用2010年第5期
楊共燕, 鄺育軍, 隆克平
電子科技大學(xué) 光互聯(lián)網(wǎng)與移動信息網(wǎng)絡(luò)研究中心, 四川 成都 611731
摘要： 傳統(tǒng)的AODV（Ad-hoc On-demand Distance Vector）路由協(xié)議只以路由跳數(shù)為度量,，沒有考慮到鏈路穩(wěn)定情況,，因此，無法更好地適應(yīng)節(jié)點高速移動的網(wǎng)絡(luò)環(huán)境,。為此,，提出了一種改進的AODV路由協(xié)議，即IMAODV（Improved AODV）路由協(xié)議,。該協(xié)議主要從路由度量值,、HELLO消息的發(fā)送頻率、鄰居節(jié)點的監(jiān)聽方式等幾個方面對AODV進行改進,，使之在移動網(wǎng)絡(luò)中具有較好的擴展性和魯棒性,。仿真結(jié)果表明，IMAODV協(xié)議能夠較好地適應(yīng)高速移動的網(wǎng)絡(luò)環(huán)境,，并在一定程度上降低網(wǎng)絡(luò)時延和增加網(wǎng)絡(luò)吞吐量,。
中圖分類號: TP391.9
文獻標(biāo)識碼: 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

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

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

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

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

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

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

　本文針對移動自組織網(wǎng)絡(luò)中節(jié)點的移動速度對路由協(xié)議的影響對AODV協(xié)議做了改進，提出了一種新的改進路由協(xié)議IMAODV(Improved AODV),。該協(xié)議在對HELLO消息機制及路由修復(fù)機制做出優(yōu)化的同時,，在MAC層做了優(yōu)化以使節(jié)點具有偵聽功能，使之能夠在節(jié)點以中高速運動的條件下建立較穩(wěn)定的路由,，降低了分組傳輸端到端的平均延遲,，并提高了網(wǎng)絡(luò)的吞吐量。仿真結(jié)果表明,，該協(xié)議能較好地適應(yīng)移動自組織網(wǎng)絡(luò)的通信環(huán)境,。
    下一步工作將對路由協(xié)議做多接口擴展和跨層的優(yōu)化處理，以進一步提高路由算法的性能,。
參考文獻
[1]     RFC2501. Mobile Ad hoc networking (MANET): Routing protocol performance issues and evaluation considerations[s]
[2]     王金龍,，王呈貴. Ad Hoc移動無線網(wǎng)絡(luò)[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路由協(xié)議,儀器儀表學(xué)報,， 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]     鄭相全,，郭偉，李帆. 自組網(wǎng)AODV路由協(xié)議中鍛煉修復(fù)的改進[J].電子科技大學(xué)學(xué)報,，2003,32(5).
[9]     NS2[OL]. http://nsnam.isi.edu/nsnam/index.php.

此內(nèi)容為AET網(wǎng)站原創(chuàng),，未經(jīng)授權(quán)禁止轉(zhuǎn)載。