MANET路由協(xié)議在VANET中的研究

朱東杰 崔剛 傅忠傳

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

關(guān)鍵詞：車載自組網(wǎng)；MANET；路由協(xié)議；SUMO

中圖分類號(hào)：TP393.1 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)：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 引 言

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

圖1 VANET應(yīng)用示意圖

Fig..1 VANET application

作為一種特殊的Ad-Hoc網(wǎng)絡(luò)，VANET與移動(dòng)自組網(wǎng)（Mobile Ad-hoc Network， MANET）相比較而言，其相通指出在于，VANET可稱作MANET的一種延伸應(yīng)用，因其基本架構(gòu)相同，且同樣具有無基礎(chǔ)設(shè)施、多點(diǎn)式跳躍連接和動(dòng)態(tài)拓?fù)涞忍匦訹2]，這就決定了VANET能夠借鑒并使用大量已有的MANET路由協(xié)議。但VANET同時(shí)卻又表現(xiàn)出很多區(qū)別于MANET的不同特點(diǎn)，諸如網(wǎng)絡(luò)規(guī)模大、車輛節(jié)點(diǎn)運(yùn)動(dòng)軌跡被嚴(yán)格限制在道路中[3]，網(wǎng)絡(luò)密度極不均勻，網(wǎng)絡(luò)狀況更易受時(shí)間、空間等因素影響、且其節(jié)點(diǎn)快速的移動(dòng)速度將導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化更為頻繁，等[4]，為此將VANET與MANET特性對(duì)比列于表1。更進(jìn)一步地，也將需要重新評(píng)估MANET中路由協(xié)議在VANET場(chǎng)景下的適用程度。

1 MANET路由協(xié)議介紹

1.1 動(dòng)態(tài)源路由協(xié)議

動(dòng)態(tài)源路由協(xié)議（Dynamic Source Routing， DSR）為反應(yīng)式（Reactive）路由協(xié)議，即當(dāng)源節(jié)點(diǎn)S并不知道通往目的節(jié)點(diǎn)D的路徑并且需要向節(jié)點(diǎn)D發(fā)送數(shù)據(jù)的時(shí)候，節(jié)點(diǎn)S便啟動(dòng)路由發(fā)現(xiàn)過程，而源節(jié)點(diǎn)廣播路由請(qǐng)求消息（Route Request，RREQ消息）。此時(shí)每個(gè)節(jié)點(diǎn)均在其向前發(fā)送的RREQ消息上附加自己唯一的標(biāo)識(shí)符[5]。

1.2 目的節(jié)點(diǎn)序列距離矢量協(xié)議

目的節(jié)點(diǎn)序列距離矢量協(xié)議 （Destination Sequenced Distance Vector Routing， DSDV）是一種點(diǎn)到點(diǎn)距離向量路由協(xié)議。其中，每個(gè)節(jié)點(diǎn)只是維持一跳到兩跳內(nèi)的相鄰節(jié)點(diǎn)之間的區(qū)域信息，而不需要知道整個(gè)網(wǎng)絡(luò)的全局拓?fù)浣Y(jié)構(gòu)，如此則有可能出現(xiàn)路由環(huán)路問題[6]。并且，DSDV亦是先應(yīng)式（Proactive）路由協(xié)議，每個(gè)節(jié)點(diǎn)需維護(hù)自身知道的所有目的節(jié)點(diǎn)的路由表，因而所有節(jié)點(diǎn)都要定期更新自身路由表。這就使得在整體網(wǎng)絡(luò)拓?fù)錄]有變化的時(shí)候，為了維護(hù)路由表，仍然會(huì)存在一定的網(wǎng)絡(luò)開銷，因此就可能維護(hù)一些尚未使用過的路由。距離矢量選路的經(jīng)典算例則是Bellman-Ford算法，對(duì)其實(shí)現(xiàn)可做如下描述：

（1）初始化——每個(gè)節(jié)點(diǎn)記為G，所有直接相連的目的地記為N，路由表中的記錄可用三元組（N，G，0）加以表示，即從G點(diǎn)到N點(diǎn)亦無需經(jīng)過路由轉(zhuǎn)發(fā)；

（2）節(jié)點(diǎn)G需要定期發(fā)送其路由表至相鄰節(jié)點(diǎn)，并同時(shí)更新信息中對(duì)應(yīng)每一個(gè)目的地N，此時(shí)可用一個(gè)三元組（N，V，D）進(jìn)行表示，即從G點(diǎn)出發(fā)到目的節(jié)點(diǎn)N的路徑上下一跳節(jié)點(diǎn)可記為V，而G到N的跳距則記為D；

（3）當(dāng)節(jié)點(diǎn)G收到G送來的路由信息時(shí)，更新信息中的每個(gè)目的節(jié)點(diǎn)，并在G的路由表中查找對(duì)應(yīng)的記錄，設(shè)為（N，V，D），而更新信息后的三元組則設(shè)為（N，V，D）；

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

（5）如果V = G，則G點(diǎn)的路由表對(duì)應(yīng)的記錄將隨之而更新為（N，G，D+ C）；

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

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

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

1.3 無線自組網(wǎng)按需平面距離矢量路由協(xié)議

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

2 MANET路由協(xié)議在VANET中的研究

2.1 實(shí)驗(yàn)平臺(tái)搭建

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

2.1.1SUMO的安裝

（1）準(zhǔn)備工作

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

④ Libfox-1.6-dev ⑤Libgdal 1.7.0

（2）安裝

① 進(jìn)入SUMO 執(zhí)行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，裁剪合適的地圖，對(duì)應(yīng)效果如圖2所示。

圖2 OpenStreetMap裁剪合適的地圖

Fig.2 Crop suitable map in OpenStreetMap

下載對(duì)應(yīng)的osm文件，再對(duì)其進(jìn)行轉(zhuǎn)換：

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

2.1.3地圖的導(dǎo)入

通過將修改后的地圖文件導(dǎo)入SUMO運(yùn)行，該過程如圖3所示。

圖3 SUMO地圖的導(dǎo)入

Fig.3 Import map in SUMO

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

圖4 放大后的SUMO地圖

Fig.4 Amplified map in SUMO

2.1.4路徑的生成

根據(jù)詳細(xì)設(shè)計(jì)中的randomTrips.py與DUAROUTER腳本生成已知地圖文件的車輛運(yùn)動(dòng)軌跡。對(duì)應(yīng)語句為：

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

得到對(duì)應(yīng)的trips文件，再接著構(gòu)建對(duì)應(yīng)的routes文件。具體過程為：

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

--continue-on-unbuild

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

2.1.5生成configure文件

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

2.1.6開始模擬

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

圖5 模擬實(shí)驗(yàn)的截圖

Fig.5 Screenshot of simulation experiment

由于此時(shí)車輛之間并未發(fā)生通信，環(huán)境搭建模塊也僅僅模擬了車輛的流動(dòng)過程，為其后的仿真模擬提供了必要且有效的研究基礎(chǔ)。

2.2 仿真模擬

2.2.1控制車輛數(shù)量

由SUMO的configure文件可知，其中設(shè)定了該文件的time域。在這里，由于模擬的tcl編寫規(guī)則是在1s內(nèi)新建若干個(gè)車輛節(jié)點(diǎn)，因此可以通過控制simulation的時(shí)間來間接控制車輛數(shù)量。

2.2.2控制通信路由協(xié)議

通過更改tcl腳本內(nèi)的rp（routing protocol） 項(xiàng)，來變換不同的路由協(xié)議。各種路由協(xié)議的實(shí)現(xiàn)方法可具體詳見NS2系統(tǒng)配置文件。

2.2.3 tcl腳本

網(wǎng)絡(luò)試驗(yàn)參數(shù)表2所示。

根據(jù)具體的tcl語法編寫腳本，即可完成車輛運(yùn)動(dòng)與車輛間通信的過程。

3.2.4運(yùn)行腳本分析trace文件

運(yùn)行腳本后，通過NAM工具就可形象、直觀地將車輛運(yùn)動(dòng)及通信展現(xiàn)出來，局部結(jié)果如圖6所示。

圖6 NAM運(yùn)行截圖

Fig.6 NAM running diagram

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

3 實(shí)驗(yàn)結(jié)果及分析

3.1 路由性能指標(biāo)介紹

（1）分組成功傳輸率（Packet Delivery Ratio， PDR），表示所有源節(jié)點(diǎn)發(fā)送的CBR分組總數(shù)與所有目的節(jié)點(diǎn)接收的 CBR分組總數(shù)之比。分組成功傳輸率表征了路由協(xié)議的業(yè)務(wù)分組投遞能力，值越高說明協(xié)議的選徑能力越強(qiáng)，傳輸路徑的穩(wěn)定性也就越好。

（2）歸一化路由負(fù)載（Normalized Routing Load， NRL），表示成功發(fā)送一個(gè)CBR分組所需發(fā)送的平均路由控制分組數(shù)量。歸一化路由負(fù)載指標(biāo)體現(xiàn)了路由協(xié)議投遞業(yè)務(wù)分組的效率，可以用來評(píng)估路由開銷。該值越小，表明投遞單位數(shù)量業(yè)務(wù)分組所需要的路由協(xié)議控制分組越少，相應(yīng)地路由開銷也就越小。

（3）平均端到端延時(shí)（Average End-to-end Delay， AEL），表示目的節(jié)點(diǎn)接收分組與源節(jié)點(diǎn)相應(yīng)分組發(fā)送時(shí)間的平均差值。平均端到端延時(shí)指標(biāo)表征了路由協(xié)議投遞業(yè)務(wù)分組的及時(shí)程度，該值越小，說明路由協(xié)議將業(yè)務(wù)分組發(fā)送到目的端的速度則越快。

3.2 實(shí)驗(yàn)結(jié)果

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

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

作為一種表驅(qū)動(dòng)路由協(xié)議，DSDV在車輛運(yùn)動(dòng)時(shí)劇烈變化的拓?fù)洵h(huán)境中，即需要不斷地更新路由表，就會(huì)經(jīng)常中斷路由鏈路，這就使得數(shù)據(jù)分組的PDR相應(yīng)地較低。

圖7 PDR對(duì)比

Fig.7 PDR comparison

3.2.2 標(biāo)準(zhǔn)化路由負(fù)載（NRL， Normalized Routing Load）

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

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

圖8 NRL對(duì)比

Fig.8 NRL comparison

3.3.3 端到端延時(shí)（AEL， Average End-to-end Delay）

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

圖9 AEL對(duì)比圖

Fig.9 AEL comparison

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

綜上所述，現(xiàn)將三種路由協(xié)議在VANET中的各自實(shí)驗(yàn)結(jié)果列成表格，具體如表3所示。

4 結(jié)束語

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

參 考 文 獻(xiàn)

[1] 常促宇，向勇，史美林. 車載自組網(wǎng)的現(xiàn)狀與發(fā)展[J]. 通信學(xué)報(bào)， 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] 魏達(dá)， 王沿錫， 王健，等， 車載自組網(wǎng)移動(dòng)模型綜述[J]. 計(jì)算機(jī)學(xué)報(bào)， 2013， 36（4）：677-698.

[4] 中國車聯(lián)網(wǎng)產(chǎn)業(yè)技術(shù)白皮書（2011）， 中國車聯(lián)網(wǎng)產(chǎn)業(yè)技術(shù)創(chuàng)新戰(zhàn)略聯(lián)盟， 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.