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

    移動(dòng)自組網(wǎng)(MANET)是由一系列移動(dòng)終端組成的無固定基礎(chǔ)設(shè)施的多跳自組織網(wǎng)絡(luò)系統(tǒng)[1],其拓?fù)浣Y(jié)構(gòu)因?yàn)楣?jié)點(diǎn)電量不足或是移動(dòng)而變化,所以MANET的路由協(xié)議與傳統(tǒng)網(wǎng)絡(luò)的路由協(xié)議有著很大的區(qū)別。
 目前,移動(dòng)網(wǎng)絡(luò)中較成熟、較典型的路由協(xié)議有DSDV、DSR、AODV、ZRP等[2]。其中,AODV路由協(xié)議[3]是一種經(jīng)典的按需路由協(xié)議,它在一定程度上比其他協(xié)議有較小的路由開銷和更好的擴(kuò)展性能,但是這種路由協(xié)議在網(wǎng)絡(luò)拓?fù)漕l繁變化的情況下,路由斷鏈的幾率很大,其網(wǎng)絡(luò)性能下降很快,無法保證較高要求的服務(wù)質(zhì)量。
 針對高速移動(dòng)自組網(wǎng)的特性,本文提出一種基于AODV的改進(jìn)路由協(xié)議,即IMAODV,它在路由度量值、斷鏈修復(fù)策略以及HELLO消息機(jī)制上做了修改,使之能有效地降低網(wǎng)絡(luò)延遲,提高網(wǎng)絡(luò)的吞吐量。通過NS2仿真可以看到,本文提出的IMAODV路由協(xié)議與傳統(tǒng)的AODV路由協(xié)議相比具有一定的優(yōu)勢:它既能降低中高速移動(dòng)自組網(wǎng)的網(wǎng)絡(luò)延時(shí),又能在一定程度上提高網(wǎng)絡(luò)吞吐量;同時(shí),IMAODV路由協(xié)議能夠較好地適應(yīng)無線網(wǎng)絡(luò)環(huán)境,有效提高網(wǎng)絡(luò)性能。
1 IMAODV路由算法
1.1 AODV

 傳統(tǒng)自組網(wǎng)路由協(xié)議可分為主動(dòng)路由協(xié)議和按需路由協(xié)議[4],由于移動(dòng)自組網(wǎng)存在著動(dòng)態(tài)多變特性,主動(dòng)路由協(xié)議應(yīng)用在移動(dòng)網(wǎng)絡(luò)中有著明顯的缺陷,所以實(shí)際中經(jīng)常使用的都是按需路由協(xié)議[5]。
   AODV是Ad-hoc網(wǎng)絡(luò)的經(jīng)典路由協(xié)議,它是由路由發(fā)現(xiàn)和路由維護(hù)組成。路由發(fā)現(xiàn)過程如圖1所示。而在路由維護(hù)中,節(jié)點(diǎn)通過周期性地發(fā)送HELLO包維持與鄰居節(jié)點(diǎn)的連接,若一段時(shí)間后還未收到鄰居節(jié)點(diǎn)的HELLO包,則開始鏈路修復(fù)過程。若本節(jié)點(diǎn)離目的節(jié)點(diǎn)較近,則進(jìn)行本地修復(fù),發(fā)送RREQ進(jìn)行路由重建,當(dāng)中間節(jié)點(diǎn)有到不可達(dá)節(jié)點(diǎn)的有效路由或者不可達(dá)節(jié)點(diǎn)收到此RREQ后就發(fā)送一個(gè)路由回復(fù)RREP給源節(jié)點(diǎn),這樣路由就得到了重建。若鏈路修復(fù)失敗,則節(jié)點(diǎn)向所有的鄰居節(jié)點(diǎn)廣播RERR包,RERR包中的不可達(dá)節(jié)點(diǎn)列表不僅包括了鏈路斷開的鄰居節(jié)點(diǎn),還包括了以此鄰居節(jié)點(diǎn)作為下一跳的所有目的節(jié)點(diǎn)。通過RERR的廣播,其他節(jié)點(diǎn)便知道鏈路斷開了,當(dāng)此包傳到源節(jié)點(diǎn)時(shí),將進(jìn)行新一輪的路由發(fā)現(xiàn)。

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

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

2 仿真分析
2.1仿真環(huán)境

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

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

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

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