摘 要: 介紹了移動自組織網(wǎng)絡(luò)中典型的路由協(xié)議——按需路由協(xié)議AODV以及AODV的改進協(xié)議AODV_BD。此外還介紹了一個實用的移動模型,,使仿真實驗更加接近實際應(yīng)用,。在Linux下使用網(wǎng)絡(luò)仿真工具NS2對這兩個協(xié)議進行仿真,并用分組交付率和端到端延時對仿真結(jié)果進行分析比較和性能評價,。由此得出,,AODV_BD協(xié)議與AODV協(xié)議相比,在一定程度上減少了分組時延,。
關(guān)鍵詞: 移動自組織網(wǎng)絡(luò),;車載自組織網(wǎng)絡(luò);移動模型,;AODV,;廣播數(shù)據(jù)分組
車載自組織網(wǎng)絡(luò)VANET(Vehicular Ad hoc Networks)作為移動自組織網(wǎng)絡(luò)MANET(Mobile Ad hoc Networks)的特例,既有MANET的一般特點,,又有其特殊性[1],。自組織網(wǎng)絡(luò)是由一組帶有無線收發(fā)裝置的移動節(jié)點組成的無線通信網(wǎng)絡(luò),它不依賴于預(yù)設(shè)的基礎(chǔ)設(shè)施而臨時組網(wǎng),,網(wǎng)絡(luò)中的移動節(jié)點利用自身的收發(fā)裝置交換信息,,使網(wǎng)絡(luò)中的節(jié)點共享有用的信息,。當(dāng)彼此不在自己的通信范圍時,可以借助其他中間節(jié)點中繼來實現(xiàn)多跳通信,。因此,,自組網(wǎng)是一種無線分布式、多跳,、自組織,、無中心、可移動的網(wǎng)絡(luò)[2],。而VANET中各種各樣的汽車就是MANET中的移動節(jié)點,。但是VANET中的節(jié)點移動速度很快,拓?fù)浣Y(jié)構(gòu)變化頻繁,,運動軌跡可預(yù)測,,不需要考慮節(jié)點的能量問題,這些特征使MANET中的許多技術(shù)(包括路由技術(shù))很難直接移植到VANET中,。這時就需要對MANET中的技術(shù)進行改進,,使之適應(yīng)VANET的需要。由于節(jié)點移動速度快,,拓?fù)浣Y(jié)構(gòu)變化頻繁,,而路由協(xié)議收斂速度緩慢,會使大量控制分組存在于鏈路上,,占用網(wǎng)絡(luò)帶寬,;數(shù)據(jù)分組因找不到合適的路由而延時等待,從而增加了時延,,降低了分組交付率,。當(dāng)節(jié)點移動速度和拓?fù)浣Y(jié)構(gòu)變化達到一定程度時,一般的路由協(xié)議就會失去作用,,而只能通過洪泛的方式達到傳遞數(shù)據(jù)分組的目的,。針對VANET中節(jié)點移動的特點,提出了一種改進協(xié)議——AODV_BD,,降低了分組時延,。
1 AODV路由協(xié)議及其改進
在帶寬資源有限、拓?fù)浣Y(jié)構(gòu)不斷變化的自組織網(wǎng)中,,沒有必要維護任意兩個節(jié)點之間的路由??焖僮兓耐?fù)浣Y(jié)構(gòu)會使路由有效時間縮短,,路由信息利用率下降。按需路由協(xié)議[3](又稱反應(yīng)式路由協(xié)議)就應(yīng)運而生,。
1.1 AODV路由協(xié)議
自組網(wǎng)按需距離矢量路由協(xié)議AODV[4](Ad-hoc On-Demand Distance Vector Routing)根據(jù)業(yè)務(wù)需求建立和維護路由,,是動態(tài)源路由協(xié)議DSR(Dynamic Source Routing)和目的序列號距離矢量路由協(xié)議DSDV(Destination Sequence Distance Vector)的結(jié)合,,并且是一種典型的按需路由協(xié)議。它采用了DSR協(xié)議的路由發(fā)現(xiàn)和維護的基礎(chǔ),;采用DSDV逐跳路由,、順序編號以及路由維護階段的周期更新機制。
AODV協(xié)議使用源節(jié)點路由重建和本地修復(fù)兩種方式維護正在使用的路由,。本地修復(fù)的原理:中間節(jié)點檢測到鏈路中斷時,,先緩存來自源節(jié)點的數(shù)據(jù)分組,同時發(fā)送路由請求分組RREQ,,如果目的節(jié)點收到該請求,,則回復(fù)路由應(yīng)答分組RREP,路由修復(fù)成功,;否則,,若在一定的時間內(nèi)目的節(jié)點沒有收到RREP,則向源節(jié)點報告路由失效消息,,由源節(jié)點進行相應(yīng)的處理,。
1.2 AODV路由協(xié)議的改進
從以上分析可知,當(dāng)鏈路中斷時,,本地修復(fù)通過發(fā)送路由請求分組和路由應(yīng)答分組重新建立到達目的節(jié)點的路由,,而此時的數(shù)據(jù)分組被緩存起來。當(dāng)?shù)竭_目的節(jié)點的路由建立后再發(fā)送數(shù)據(jù)分組,,這樣不僅會增加時延,,而且新建立的路由可能因為拓?fù)浣Y(jié)構(gòu)的變化而失效。AODV_BD通過本地修復(fù)時廣播帶有的控制信息數(shù)據(jù)分組來建立到目的節(jié)點的路由,。
具體流程是:當(dāng)節(jié)點檢測到鏈路中斷時,,不再發(fā)送RREQ分組而是廣播一個被增加了控制信息分組頭的數(shù)據(jù)分組的拷貝。這個分組頭部與RREQ的分組頭部類似,,也有建立反向路由和尋找路由的功能,。當(dāng)數(shù)據(jù)分組拷貝到達一個節(jié)點時,根據(jù)分組頭中的內(nèi)容建立反向路由并判斷此節(jié)點是否為目的節(jié)點或此節(jié)點是否包含到目的節(jié)點的有效路由,。反向路由的目的節(jié)點是發(fā)起路由修復(fù)的中間節(jié)點,,下一跳節(jié)點是將數(shù)據(jù)分組發(fā)送給本節(jié)點的鄰節(jié)點。如果此節(jié)點是目的節(jié)點或此節(jié)點包含到目的節(jié)點的有效路由,,就沿著反向路由發(fā)送一個RREP分組,,并在此過程中建立到目的節(jié)點的正向路由,正向路由的目的節(jié)點是RREP的源節(jié)點,,下一跳是將RREP發(fā)送給本節(jié)點的鄰節(jié)點,。當(dāng)RREP到達發(fā)起路由修復(fù)的中間節(jié)點時,此中間節(jié)點就將已發(fā)送的數(shù)據(jù)分組刪除,避免重復(fù)發(fā)送,;否則,,它再向周圍節(jié)點廣播此數(shù)據(jù)分組。這樣依次進行,,直至到達目的節(jié)點或包含到目的節(jié)點有效路由的節(jié)點,。這樣不僅建立了路由,而且減少了時延,。
2 移動模型產(chǎn)生器
本文所使用的移動模型產(chǎn)生器是VanetMobiSim[4] (Vehicular Ad Hoc Networks Mobility Simulator),。
VanetMobiSim的目的是使車輛移動模型更接近現(xiàn)實。VanetMobiSim可以設(shè)置模擬場景的大小,、模擬時間的長短,、節(jié)點個數(shù)和速度大小。它既允許用戶自己定義道路的拓?fù)浣Y(jié)構(gòu),,又可以隨機產(chǎn)生道路的拓?fù)浣Y(jié)構(gòu),,因此能夠很靈活地滿足用戶的不同需求。VanetMobiSim中還可以在十字路口處設(shè)置交通燈和交通燈的時間間隔,,當(dāng)紅燈時,,車輛就會自動停下來;當(dāng)變?yōu)榫G燈時,,車輛就會繼續(xù)前進,。使用帶有十字路口管理的智能駕駛員模型IDM_IM(Intelligent Driver Model with Intersection Management)可以很真實地模擬節(jié)點的運動。它可以根據(jù)鄰居車輛的運動來控制車輛的速度(例如,,當(dāng)一前方車輛剎車時,,隨后的車輛就會減速)。
3 仿真過程
本文使用NS2[5](Network Simulation 2)作為仿真平臺進行研究,。NS2是一款免費的,、面向?qū)ο蟮摹㈦x散事件驅(qū)動的網(wǎng)絡(luò)仿真軟件,,由Otcl和C++兩種語言編寫而成,。它具有開放性好、擴展性強,、適用于Windows和Linux系統(tǒng)平臺的特點,,是一款出色的研究網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、分析網(wǎng)絡(luò)傳輸?shù)哪M軟件,。
3.1 網(wǎng)絡(luò)性能指標(biāo)及其計算方法
本文將使用以下兩個性能指標(biāo)對仿真結(jié)果進行分析:
(1)分組交付率(Packet Delivery Ratio):到達目的節(jié)點應(yīng)用層的數(shù)據(jù)分組數(shù)目與源節(jié)點應(yīng)用層發(fā)送的數(shù)據(jù)分組數(shù)目的比值,。它反映了路由協(xié)議的可靠性和完整性。
(2)端到端時延(End-to-End Delay):數(shù)據(jù)分組到達目的節(jié)點應(yīng)用層的時間減去源節(jié)點發(fā)送此數(shù)據(jù)分組的時間,。
3.2 網(wǎng)絡(luò)參數(shù)
本文使用NS2-2.30進行仿真實驗,,天線通信范圍為250 m,,主要網(wǎng)絡(luò)參數(shù)如表1所示,。
3.3 數(shù)據(jù)流產(chǎn)生器
本文所使用的數(shù)據(jù)流產(chǎn)生器是NS2自帶的cbrgen工具,。它可以指定所產(chǎn)生的數(shù)據(jù)流的類型(包括cbr流和tcp流)、節(jié)點數(shù),、隨機種子數(shù),、節(jié)點間的最大連接數(shù)以及每對節(jié)點間數(shù)據(jù)的發(fā)送頻率等。
3.4 模擬場景
本文所使用的模擬場景由上述的VanetMobiSim所產(chǎn)生,,共有兩個模擬場景,,分別如表2和表3所示。
3.5 仿真結(jié)果分析
在上述兩種場景下,,數(shù)據(jù)分組的交付率,、端到端時延與節(jié)點的移動速度、數(shù)據(jù)分組的發(fā)送頻率之間的關(guān)系如圖1~如圖4所示,。
從圖1可以看出AODV協(xié)議的時延比AODV_BD協(xié)議的時延要大,,且這兩個協(xié)議的時延隨速度的起伏基本一致。AODV協(xié)議的最小時延約為0.013 s,,最大時延約為0.04 s,;而AODV_BD協(xié)議的最小時延約為0.008 s,最大時延約為0.027 s,。這兩個協(xié)議的時延曲線基本不受速度的影響,,呈鋸齒狀分布。當(dāng)節(jié)點檢測到鏈路斷開時,,采用廣播帶有路由請求的數(shù)據(jù)分組,,盡早完成部分?jǐn)?shù)據(jù)分組的轉(zhuǎn)發(fā),并且完成了到達目的節(jié)點的鏈路的修復(fù),,在一定程度上減少了時延,。
從圖2可以看出AODV協(xié)議的時延比AODV_BD協(xié)議要大,AODV協(xié)議的最小時延約為0.008 s,,最大時延約為0.064 s,;而AODV_BD協(xié)議的最小時延約為0.011 s,最大時延約為0.049 s,??傮w上,這兩個協(xié)議的時延都隨著分組發(fā)送頻率的增加而增加,,這是因為數(shù)據(jù)分組在單位時間內(nèi)的數(shù)量增加,,從而引起路由查詢的次數(shù)增加進而導(dǎo)致路由查詢的時間加大。AODV協(xié)議時延起伏較大,,這是由此協(xié)議的工作原理造成的,;而AODV_BD協(xié)議的起伏較平緩,隨著分組及交付率的增大而緩慢上升。
從圖3可以看出,, AODV協(xié)議的分組交付率與AODV_BD協(xié)議的分組交付率幾乎一樣,,受移動速度的影響很小。當(dāng)速度達到18 m/s時,,這兩個協(xié)議的分組交付率降到最低點,。
從圖4可以看出,AODV協(xié)議分組交付率與AODV_BD協(xié)議的分組交付率差別很小,。當(dāng)分組發(fā)送頻率小于3.5 p/s時,,這兩個協(xié)議的分組交付率隨發(fā)送頻率的增加逐漸變大,最大值可達0.997,;當(dāng)分組發(fā)送頻率大于3.5 p/s時,,兩個協(xié)議的分組交付率隨發(fā)送頻率的增加迅速變小,而AODV_BD協(xié)議的交付率優(yōu)于AODV協(xié)議的交付率,。
本文主要通過NS2對按需路由協(xié)議AODV及其改進的協(xié)議AODV_BD進行仿真,,分析評價其分組交付率和分組時延。通過使用移動模型產(chǎn)生器VanetMobiSim,,較為真實地模擬了車輛的移動和道路的布局,,對VANET的仿真研究具有一定的參考價值。通過仿真結(jié)果可以看出,,AODV_BD協(xié)議在一定程度上減少了分組時延,,達到了預(yù)定的目的。
參考文獻
[1] 常促宇,,向勇,,史美林.車載自組織網(wǎng)的現(xiàn)狀與發(fā)展[J].通信學(xué)報,2007,28(11):116-126.
[2] 于宏毅.無線移動自組織網(wǎng)[M].北京:人民郵電出版社,,2005.
[3] 張順亮,,葉澄清,李方敏.移動Ad Hoc網(wǎng)絡(luò)路由協(xié)議綜述[J].計算機科學(xué),,2003,,30(12):27-30.
[4] 陳模科,,陳勤,,張旻.基于hello消息的AODV路由協(xié)議的改進[J].計算機仿真,2009,,26(8):143-146.
[5] 方路平,,劉世華,陳盼.NS-2網(wǎng)絡(luò)模擬基礎(chǔ)與應(yīng)用[M]. 北京:國防工業(yè)出版社,,2008.