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.