MANET路由協議在VANET中的研究

朱東杰 崔剛 傅忠傳

摘 要：車載自組網作為未來智能交通的基礎部分，通過車與車、車與路邊節點的通信構成統一的無線通信網絡，用于傳遞輔助駕駛或避免事故的實時信息，對人們的出行可以提供操作便利和安全保障，所以VANET中的路由協議至關重要，尤其是協議中數據包投遞率。本文首先對MANET中的路由協議進行研究，并建立了以實際真實道路網為背景的實驗平臺，并對運動的車輛進行模擬，研究了AODV、DSDV和DSR三種路由協議在VANET中的各個方面性能，實驗表明，MANET中路由協議能在VANET中使用，但是在數據包投遞率、路由負載和端到端延時方面都需要根據VANET的特性進一步優化。

關鍵詞：車載自組網；MANET；路由協議；SUMO

中圖分類號：TP393.1 文獻標識碼： A 文章編號：2095-2163（2014）05-

The Research on MANET Routing Protocol in VANET

ZHU Dongjie， CUI Gang， FU Zhongchuan

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）

Abstract： Vehicular Ad Hoc Networks （VANET） as a fundamental part of the future intelligent transportation， could constitute by communication between cars， cars and roadside node a unified wireless communication network， and it can transmit auxiliary driving or real-time information to avoid accidents， also can provide the operating convenience and security with people's travel， so VANET routing protocols is crucial， especially the packet delivery ratio in protocol. Firstly， the traditional routing protocols in MANET is researched and the actual real movement of vehicles on the road is built for network simulation， all aspects of the performance of the AODV， DSDV and DSR routing protocols are analyzed in VANET environment， Experimental results shows that routing protocols in MANET can be used in VANET， but with the characteristics of VANET， it need to be further optimized in packet delivery ratio， routing load and end to end delay.

Key words： VANET；MANET；Routing Protocol；SUMO

0 引 言

隨著交通業的飛速發展，道路上車輛數目激增，道路交通安全形勢已日趨嚴峻。在過去10年間，大量的國內外研究均致力于通過發展車輛駕駛輔助系統來解決交通安全問題，這一系統能夠準確及時地感知周圍交通和車輛情況，并在危急時刻向司機發出必要提醒。VANET（Vehicular Ad-hoc NETwork，車載自組織網絡） [1]即是相關的最重要研究成果，并已在ITS（Intelligent Transportation System， 智能交通系統）中發揮著高度重要的作用。VANET的預定目標是作為未來ITS的基礎部分，能夠通過車與車之間、車與路邊節點之間的通信構成統一的無線通信網絡，既可用于傳遞輔助駕駛或避免事故的實時信息，更可提供娛樂信息、網絡接入等升級服務。具體地，VANET一個典型的實例應用則如圖1所示。

圖1 VANET應用示意圖

Fig..1 VANET application

作為一種特殊的Ad-Hoc網絡，VANET與移動自組網（Mobile Ad-hoc Network， MANET）相比較而言，其相通指出在于，VANET可稱作MANET的一種延伸應用，因其基本架構相同，且同樣具有無基礎設施、多點式跳躍連接和動態拓撲等特性[2]，這就決定了VANET能夠借鑒并使用大量已有的MANET路由協議。但VANET同時卻又表現出很多區別于MANET的不同特點，諸如網絡規模大、車輛節點運動軌跡被嚴格限制在道路中[3]，網絡密度極不均勻，網絡狀況更易受時間、空間等因素影響、且其節點快速的移動速度將導致網絡拓撲結構變化更為頻繁，等[4]，為此將VANET與MANET特性對比列于表1。更進一步地，也將需要重新評估MANET中路由協議在VANET場景下的適用程度。

1 MANET路由協議介紹

1.1 動態源路由協議

動態源路由協議（Dynamic Source Routing， DSR）為反應式（Reactive）路由協議，即當源節點S并不知道通往目的節點D的路徑并且需要向節點D發送數據的時候，節點S便啟動路由發現過程，而源節點廣播路由請求消息（Route Request，RREQ消息）。此時每個節點均在其向前發送的RREQ消息上附加自己唯一的標識符[5]。

1.2 目的節點序列距離矢量協議

目的節點序列距離矢量協議 （Destination Sequenced Distance Vector Routing， DSDV）是一種點到點距離向量路由協議。其中，每個節點只是維持一跳到兩跳內的相鄰節點之間的區域信息，而不需要知道整個網絡的全局拓撲結構，如此則有可能出現路由環路問題[6]。并且，DSDV亦是先應式（Proactive）路由協議，每個節點需維護自身知道的所有目的節點的路由表，因而所有節點都要定期更新自身路由表。這就使得在整體網絡拓撲沒有變化的時候，為了維護路由表，仍然會存在一定的網絡開銷，因此就可能維護一些尚未使用過的路由。距離矢量選路的經典算例則是Bellman-Ford算法，對其實現可做如下描述：

（1）初始化——每個節點記為G，所有直接相連的目的地記為N，路由表中的記錄可用三元組（N，G，0）加以表示，即從G點到N點亦無需經過路由轉發；

（2）節點G需要定期發送其路由表至相鄰節點，并同時更新信息中對應每一個目的地N，此時可用一個三元組（N，V，D）進行表示，即從G點出發到目的節點N的路徑上下一跳節點可記為V，而G到N的跳距則記為D；

（3）當節點G收到G送來的路由信息時，更新信息中的每個目的節點，并在G的路由表中查找對應的記錄，設為（N，V，D），而更新信息后的三元組則設為（N，V，D）；

（4）如果在新三元組中找不到相應的記錄，就在G的路由表中增加一項（N，G，D+ C）；

（5）如果V = G，則G點的路由表對應的記錄將隨之而更新為（N，G，D+ C）；

（6）否則，比較D+ C和D：

（7）如果D+ C < D，則G點路由表中的記錄即更新為（N，G，D+ C）；

（8）否則，繼續保持G點中的路由表不變，即仍舊記為（N，V，D）。

1.3 無線自組網按需平面距離矢量路由協議

DSR協議在每個分組消息的首部都包含了源路由信息，然而當首部信息過大，特別是當數據分組中的有用信息相對較少時，就必然會帶來嚴重的性能損失，并將降低性能表現。而無線自組網按需平面距離矢量路由協議（Ad-hoc On-demand Distance Vector Routing，ADOV）則通過對每個節點相應維護路由表的方法來改進DSR的性能，因此數據分組將不再需要包含路徑的信息。同時，AODV只是保留了DSR協議中維持需要通信節點之間的有效路徑，并采用類似DSR中構建的向前發送路由請求消息（RREQ消息）的方式，就是當一個節點接收到來自上一個節點所發送的RREQ消息，而且又再次廣播一個路由請求消息的時候，也將同時建立起一條指向源節點的反向路徑（AODV假定鏈路是雙向的對稱鏈路）。當RREQ消息到達目的節點的時候，就將沿著由RREQ消息建立路徑的反方向回傳一個路由應答（Route Reply）消息，即RREP消息 [7]。

2 MANET路由協議在VANET中的研究

2.1 實驗平臺搭建

本文先是利用開源地圖網站OpenStreetMap上公布的美國舊金山灣的電子地圖，構建真實道路網作為仿真場景，同時搭建以SUMO（Simulation of Urban MObility）[8]、MOVE（Mobility model generator for Vehicular networks）和NS2（Network Simulator version 2）為核心的VANET仿真實驗平臺。具體地，SUMO是一個微觀、連續的道路交通仿真軟件，主要由德國宇航中心開發。而MOVE則是一個方便用戶對VANET進行模擬，并快速生成理想流動模型的免費軟件。此外的NS2將作為底層的網絡仿真器。本實驗平臺可通過SUMO構建真實城市道路和節點移動模擬模型，同時模擬出正確的車輛運動軌跡。而為了測試不同路由協議的性能指標，即需仿真車輛節點間的信息交換。并且將該模型編寫Tcl腳本導入NS2，再通過分析生成的trace文件，由此就分別測試了在不同車輛密度下的三種MANET路由協議（AODV、DSDV和DSR）的分組成功傳輸率（Packet Delivery Ratio， PDR）、歸一化路由負載（Normalized Routing Load， NRL）和平均端到端延時（Average End-to-end Delay， AEL）。

2.1.1SUMO的安裝

（1）準備工作

① Gcc ② G++ ③ Gdal proj xerces-c

④ Libfox-1.6-dev ⑤Libgdal 1.7.0

（2）安裝

① 進入SUMO 執行configure，具體代碼如下：

/configure

--with-fox-includes=/usr/include/fox-1.6

--with-gdal-includes=/usr/include/gdal --with-proj-libraries=/usr

--with-gdal-libraries=/usr --with-proj-gdal

/configure

--with-fox-includes=/usr/include/fox-1.6

--with-gdal-includes=/usr/include/gdal --with-proj-libraries=/usr

--with-gdal-libraries=/usr --with-proj-gdal

② Make

③ Make install

鑒于本文需要用到MOVE軟件，為此選擇了SUMO 0.12.3版本。

2.1.2地圖的處理

登陸OpenStreetMap，裁剪合適的地圖，對應效果如圖2所示。

圖2 OpenStreetMap裁剪合適的地圖

Fig.2 Crop suitable map in OpenStreetMap

下載對應的osm文件，再對其進行轉換：

netconvert --osm-files download.osm.xml -o download.net.xml

2.1.3地圖的導入

通過將修改后的地圖文件導入SUMO運行，該過程如圖3所示。

圖3 SUMO地圖的導入

Fig.3 Import map in SUMO

放大后即可顯見具體交通燈，車道等，放大后結果則如圖4所示。

圖4 放大后的SUMO地圖

Fig.4 Amplified map in SUMO

2.1.4路徑的生成

根據詳細設計中的randomTrips.py與DUAROUTER腳本生成已知地圖文件的車輛運動軌跡。對應語句為：

/randomTrips.py -n cabs.net.xml -r cabs.rou.xml

得到對應的trips文件，再接著構建對應的routes文件。具體過程為：

duarouter -n cabs.net.xml -t cabs.trips.xml -o cabs.rou.xml --repair --randomize-flows

--continue-on-unbuild

生成路徑時，需要考慮到地圖裁剪的不完整性，即要添加后面的修復參數，以及忽略錯誤的參數。

2.1.5生成configure文件

其中，input域定義了地圖network文件與車輛routes文件的位置。Output域則定義了運行后產生的trace文件與各類info文件的位置。該段程序中還涉及到時間time域與reports域。

2.1.6開始模擬

運行2.1.5中的configure文件，得到simulation工程，放大至街口即如圖5所示。

圖5 模擬實驗的截圖

Fig.5 Screenshot of simulation experiment

由于此時車輛之間并未發生通信，環境搭建模塊也僅僅模擬了車輛的流動過程，為其后的仿真模擬提供了必要且有效的研究基礎。

2.2 仿真模擬

2.2.1控制車輛數量

由SUMO的configure文件可知，其中設定了該文件的time域。在這里，由于模擬的tcl編寫規則是在1s內新建若干個車輛節點，因此可以通過控制simulation的時間來間接控制車輛數量。

2.2.2控制通信路由協議

通過更改tcl腳本內的rp（routing protocol） 項，來變換不同的路由協議。各種路由協議的實現方法可具體詳見NS2系統配置文件。

2.2.3 tcl腳本

網絡試驗參數表2所示。

根據具體的tcl語法編寫腳本，即可完成車輛運動與車輛間通信的過程。

3.2.4運行腳本分析trace文件

運行腳本后，通過NAM工具就可形象、直觀地將車輛運動及通信展現出來，局部結果如圖6所示。

圖6 NAM運行截圖

Fig.6 NAM running diagram

根據仿真過程，還需分析三種路由下的四種車輛密度，共12個trace文件的PDR、NRL與AEL參數。并且，為了減少偶然誤差，每組實驗將重復多次，再對實驗結果求取平均值。其下，即給出本次仿真的實驗結果分析。

3 實驗結果及分析

3.1 路由性能指標介紹

（1）分組成功傳輸率（Packet Delivery Ratio， PDR），表示所有源節點發送的CBR分組總數與所有目的節點接收的 CBR分組總數之比。分組成功傳輸率表征了路由協議的業務分組投遞能力，值越高說明協議的選徑能力越強，傳輸路徑的穩定性也就越好。

（2）歸一化路由負載（Normalized Routing Load， NRL），表示成功發送一個CBR分組所需發送的平均路由控制分組數量。歸一化路由負載指標體現了路由協議投遞業務分組的效率，可以用來評估路由開銷。該值越小，表明投遞單位數量業務分組所需要的路由協議控制分組越少，相應地路由開銷也就越小。

（3）平均端到端延時（Average End-to-end Delay， AEL），表示目的節點接收分組與源節點相應分組發送時間的平均差值。平均端到端延時指標表征了路由協議投遞業務分組的及時程度，該值越小，說明路由協議將業務分組發送到目的端的速度則越快。

3.2 實驗結果

3.2.1 分組成功傳輸率（PDR， Packet Delivery Ratio）

在圖7中，AODV協議作為DSDV路由與DSR路由的一種結合，借鑒了DSDV的逐跳路由、定期維護以及DSR的路由發現策略，因而PDR較高，但隨著車輛密度變大，車輛間的無線碰撞沖突必將加劇，PDR則會有所下降。

作為一種表驅動路由協議，DSDV在車輛運動時劇烈變化的拓撲環境中，即需要不斷地更新路由表，就會經常中斷路由鏈路，這就使得數據分組的PDR相應地較低。

圖7 PDR對比

Fig.7 PDR comparison

3.2.2 標準化路由負載（NRL， Normalized Routing Load）

從圖8可見，總體上DSDV協議的NRL最高，AODV次之，DSR最低。理論上，隨著車輛數的增多，NRL應該有所增加，但是實驗中的模擬車輛數量較為有限，為此導致了增加到一定程度后NRL趨于平緩的現象。

具體地，DSDV需要定期廣播路由鏈路信息，這就增加了網內packet流量，故路由負載較高。而AODV作為借鑒DSDV定期維護的路由協議，路由負載則次之。相較而言，DSR就是三者中的最低。

圖8 NRL對比

Fig.8 NRL comparison

3.3.3 端到端延時（AEL， Average End-to-end Delay）

這一實驗進行了多次，實驗結果均為AODV與DSDV基本相同，只是后來增加實驗次數才得到了如圖9中所示的略微差距。由圖9可知，DSR的延遲最高，AODV與DSDV則是次之。

圖9 AEL對比圖

Fig.9 AEL comparison

經過分析可知，由于DSR是源路由方式，就需要進行路由發現策略，使得延遲最大。與其類似，AODV借鑒了這種策略，所以AODV次之，而DSDV則最低。

綜上所述，現將三種路由協議在VANET中的各自實驗結果列成表格，具體如表3所示。

4 結束語

本文首先對MANET和VANET進行分析對比，并對MANET中三種路由協議DSR、DSDV和AODV展開了分析論述，然后用構建實際真實道路網作為仿真場景，同時基于SUMO、MOVE和NS2對運動的車輛進行模擬，而且又對車輛間的通信進行了仿真。仿真過程研究了三種MANET路由協議在不同車輛密度下的PDR、NRL和AEL性能，對其結果分析表明，三種路由協議雖然各有利弊，但在VANET中卻基本上都能適用，只是由于VANET具有節點移動速度快、移動模式受道路制約等特點，路由協議在傳輸數據時易受到連接保持時間短而中斷的困擾，為此保持車聯網環境下節點連接時間，將是下一步新路由設計的重點和難點。

參 考 文 獻

[1] 常促宇，向勇，史美林. 車載自組網的現狀與發展[J]. 通信學報， 2007， 28（11）： 116-126.

[2] WANG B，YAN B，YUAN D H. The basic study of the features of the ad hoc nodes mobility model[J]. Journal of Sichuan University， 2006， 42（1）：68-72.

[3] 魏達， 王沿錫， 王健，等， 車載自組網移動模型綜述[J]. 計算機學報， 2013， 36（4）：677-698.

[4] 中國車聯網產業技術白皮書（2011）， 中國車聯網產業技術創新戰略聯盟， 2011：2-8.

[5] PERKINS C， BELDING-ROYER E， DAS S.Ad hoc On-Demand Distance Vector（AODV）Routing[S].IETF RFC 3561，2003.

[6] PERKINS C E， BHAGWAT P. Highly dynamic destination-sequenced distance-vector routing （DSDV） for mobile computers[C]//ACM SIGCOMM Computer Communication Review. ACM， 1994， 24（4）： 234-244.

[7] JOHNSON D， MALTZ D， HU Y C. The Dynamic Source Routing Protocol for Mobile Ad hoc Networks （DSR）[S]. IETF Internet Draft， draft-ietf-manet-dsr- 10.txt， 2004.

[8] BEHRISCH M， BIEKER L， ERDMANN J， et al. SUMO-simulation of urban mobility-an overview[C]//The Third International Conference on Advances in System Simulation， 2011： 55-60.