VANETs路由协议综述*

吕代刚，王静蕾，李英豪

(1.郑州职业技术学院，河南 郑州450121；2.郑州大学 电子信息工程学院，河南 郑州451150；3.成都理工大学 地球物理学院，四川 成都610059)

VANETs路由协议综述*

吕代刚1，王静蕾2，李英豪3

(1.郑州职业技术学院，河南 郑州450121；2.郑州大学 电子信息工程学院，河南 郑州451150；3.成都理工大学 地球物理学院，四川 成都610059)

随着车联网VANETs(Vehicular Ad hoc Networks)应用日益受到关注,研究者对VANETs路由协议进行了深入研究。为此，首先总结VANETs的特点及应用，再介绍了基于位置的、基于拓扑以及基于广播路由的概念，并着重分析和总结了近期路由协议的核心思想以及特点，此外，还从应用场景、前提条件、虚拟设备要求、电子地图需求、路由恢复策略以及转发模式六个方面对路由协议进行全面比较，最后，展望了VANETs路由技术的未来研究方向。

车联网；路由协议；位置；广播；拓扑；鲁棒性

0 引言

随着汽车技术的发展，城市车辆日益增长，交通压力迅速上升[1]，交通事故频频发生。为此，迫切需要将现代技术引入交通系统，使得行驶人更安全、出行更便捷，交通更畅通。移动自组织网络 MANET(Mobile Ad hoc Network)属于无线通信网络的一类，该网络可以不需要基础设施，或者仅需很少的基础设施，形成完全移动的网络。MANETs(Mobile Ad hoc Networks)具有一些显著的特性，如动态拓扑、有限的带宽、有限的能量等。

车联网VANETs(Vehicular Ad hoc Networks)属MANETs中的特例，具有一些独特的特性。VANETs主要由两部分组成：车与车（Vehicle to Vehicle，V2V）和车与设施（Vehicle to Infrastructure，V2I），如图1所示。VANETs作为一种特殊的自组织网，它依靠无线通信技术实现V2V以及V2I的通信，使驾驶者能实时地知晓其他车辆部分信息和路况信息，并预先采取适当的措施，减少和避免交通事故[2]。

与MANETs不同，VANETs具有无限能量供应、移动受道路模型限制以及定位等特性。这些独特的特性，为实施VANETs内的车间通信V2V和车与基础设施V2I通信提出了挑战。车辆的快速移动是VANETs网络的最

显著特性之一。节点的快速移动，导致拓扑结构变化不定，这为部署VANETs带来许多技术挑战[3]。尤其路由技术面临着诸多问题。由于节点的移动，使得节点间的通信链路持续时间短、稳定性差，从而增加数据的丢失率，增大了数据传输时延。

为此，本文在介绍VANETs特性和应用研究的基础上，综述了现有 VANETs路由技术的特点，并分析路由协议的未来发展方向。

图1 VANETs的网络模型

1 VANETs的特性和应用

1.1 VANETs的特性

与传统的移动自组织网络MANET相比，VANETs具有如下特性：

(1)车辆频繁的移动性

在VANETs中，车辆一直在移动，除了偶尔的临时停车外。在不同的节点移动模型(Mobility model)中，即便是相同的VANETs算法，其性能也会迥然不同。

(2)车辆运动模式局限性

在VANETs中，车辆的运动模式受道路拓扑结构、周边的环境以及交通规则等多个客观因素影响。从另一个角度来说，受限的运动模式使得车辆的运动轨迹具有一定的规律性和预测性。

(3)车辆移动的高速性

在高速公路行驶的车辆其速度近 100 km/h；当两车相向而行时，他们的相对速度就近200 km/h。因此，车辆间的交互时间非常短，通信窗口就很短。

(4)通信数据的多样性

由于车辆装载的传感器型号的多样化，促使通信数据种类丰富多样。这也为各类数据间进行数据融合提供了条件。同时，各类的传感数据使得系统设计具有更大的灵活性。

(5)计算、存储能力的强大性

与传统的无线传感器网络相比，VANETs的车辆均装载了许多硬件设备，实现密钥的存储、加密解密的计算，并且可以记录车辆位置、速度和加速度等行驶信息。这些特殊硬件设备为车辆提供了强大的计算能力以及大容量的存储空间。

(6)基础设施的辅助性

在构建VANETs网络时，经常在某些地区或重要位置区域设立一定数量功能的路边基础设施，承担网络接入点的功能，为VANETs中的车辆提供服务。通常，随着网络建设的发展以及其覆盖区域面积的扩大，基础设施的数量也随之增加。

1.2 VANETs应用

作为智能交通系统应用之一的VANETs，随着系统功能不断完善以及基础设施的逐步加强，其应用研究范围也随之不断延深，如图2所示。从最初的保障车辆行驶安全到现在的改善交通管理、提升驾车环境，其应用在不断地拓展。

图2 VANETs的应用分类

VANETs应用可分以下两类：

(1)安全相关的应用，如碰撞避免、辅助驾驶和交通流量优化等。如利用车辆间相互交换状态信息提前通知司机，使得司机能根据情况做出及时、适当的驾驶行为，尤其是得知前面的车辆发生了事故后面的车辆来不及紧急刹车，造成一系列的连锁碰撞现象，可通过VANETs中的安全应用进行有效避免。辅助驾驶是指帮助驾驶员快速、安全地通过“盲区”，如高速公路出入口、交通十字路口等。交通流量优化是指通过VANETs获取实时的交通信息，综合出与自身相关的车流量状况，从而更高效地决定路径规划。

(2)其他应用，如支付服务(如自动计费系统)、位置相关的服务(如路径规划、找到最近的加油站)、信息服务(如Internet访问)等。这类应用其主要目的是为乘客提供附加服务，享受娱乐、视频点播、汽车会议等，如在线游戏和Internet接入等。

2 VANETs消息传播机制

目前，现有的 VANETs消息传播机制可分为三类：(1)基于地理位置(Position based)的消息传播机制；(2)基于拓扑(Topology based)的消息传播机制；(3)基于广播(Broadcast based)的消息传播机制。图3列举三类典型的路由方案，并将各协议进行归类。

接下来，分别分析这三类消息传播机制的特点。

图3 典型的VANETs路由协议

2.1 基于位置的消息传播机制

基于位置的消息传播机制，源节点和目的节点利用它们的位置进行通信，根据数据包的目的节点位置以及邻居节点的位置选择转发路径。无需网络内的全局信息。在实施过程中，可通过周期广播的 beacons进行传递，也可通过位置服务请求获取。该类机制需利用全球定位系统GPS获取节点的位置信息，典型的基于位置的消息传播机制有GPSR、DREAM[6-7]。

KARP B等人于 2000年首次提出 GPSR（Greedy Perimeter Stateless Routing）[5]消息传播机制。在 GPSR机制中，源节点利用邻居节点的位置计算邻居节点离目标节点距离，并依据距离信息决策下一跳转发节点。离目标节点最近的节点作为下一跳转发节点，如图4所示，源节点S向目标节点D发送消息。为此，源节点S向邻居节点A、C、B发送转发请求，邻居节点A、C、B收到后，回复自己的位置信息。源节点S收到来自邻居节点的消息后，依据邻居节点的位置，计算离目标节点的距离，选择离目标节点最近的节点作为下一跳转发节点，即节点B。

图4 GPRS消息传播机制

基于位置的消息传播机制在消息传播过程中，无需网络拓扑，仅基于邻居节点及目标节点的位置信息。该类机制的优/缺点如下。

(1)优点：在节点高速移动的环境中，具有高的性能。能够应对车辆的快速移动；无需源节点至目的节点的全局路由，降低了系统的处理开销；更适应节点分布式环境。

(2)缺点：需要GPS提供位置，一旦 GPS不能正常工作，可能会导致消息传播机制失效；道路障碍物影响距离的计算；需beacon包。

2.2 基于拓扑的消息传播机制

基于拓扑的消息传播机制在决策路由时，主要利用链路信息选择从源节点至目的节点的消息传播路径。如 DSDV(Destination-Sequenced Distance-Vector)[8]、OLSR(Optimized Link State Routing)[9]属典型的基于拓扑路由。依据工作方式，基于拓扑的路由协议可进一步分为先应式(Proactive)和反应式(Reactive)两类。

在先应式路由协议中，每个节点先建立到网络内其他节点的路由表，并且实时对路由表进行维护。先应式路由协议采用预先建立路由表的策略，当需要进行传递数据包时，只需进行查表，无需再进行路由发现，降低数据传递时延。但是，在拓扑动态变化的VANETs中，预先建立路由表是非常困难的，开销很大。此外，维护路由表的开销也不容忽视。

与先应式路由协议相比，反应式路由协议不是预先建立路由表，而是当节点需要数据传输时，才启动路由发现工作，并且节点只需建立到其他部分节点的路由表，而不是像先应式路由协议要建立所有网络内节点的路由表。

DSR(Dynamic Source Routing)[11]和AODV(Ad-hoc Ondemand Distance Vector)[13]属经典的基于拓扑路由协议。然而，经研究实证，DSR和AODV难以应对VANETs内节点的高速移动。当节点高速移动，产生动态的拓扑，延缓DSR和AODV收敛速度，产生了大量的不可靠路由，由此产生的开销无法容忍。为此，研究者提出一些改进协议。文献 [9]提出基于AODV的改进路由协议PGB (Preferred Group Broadcasting)。尽管PGB方案通过降低转发数量提高路由的稳定性，降低因路由发现所产生的开销，但是转发数量的减少会增加延时。一旦PG为空时，路由发现失败。

概括来说，基于拓扑优/缺点如下：

(1)优点：依据拓扑信息，提供从源节点至目的节点路由表，降低了数据包传递时延；能够发送单播、组播及广播类消息；无需beacon包。

(2)缺点：由于需要路由发现和路由维护，增加了额外开销；由于依据拓扑信息建立路由，难以应对高速移动的车辆环境；会出现不必要的路由泛洪。

2.3 基于广播路由协议

广播路由协议就是将数据包向通信范围内的所有节点进行传递。最简单的广播方式就是泛洪。泛洪机制只适合节点数量较少的情况，一旦节点数量较多时，多个节点同时广播数据，相互竞争信道，导致广播风暴问题。为此，研究者提出众多的基于泛洪的改进策略。

文献[18]提出面向城市的多跳广播UMB(Urban Multi-Hop)协议。UMB首先利用节点通信范围及密度对道路分段，并采用两种模式传递数据：定向广播交叉口广播。在定向广播模式中，首先引用链路层的RTB/CTB握手机制寻找道路中最远的邻居节点，再将此节点作为下一跳

转发节点。而在交叉口广播模式中，先在交叉口装设转发器，利用转发器向不同路段的邻居节点进行定向广播。可见，UMB方案的实施是以电子地图、转发器为前提条件。

文献[19]提出了REAR(Receipt Estimation Alarm Routing)方案。REAR方案先利用信标消息实现节点间信息的交互。一旦收到广播数据包后，节点与邻居节点进行比较，判决自己是否是最佳的转发节点，若是，则继续广播数据包，否则由邻居节点承担数据包的转发任务。

文献[20]提出基于退火算法的多跳车辆广播MHVB (Multi-Hop Vehicular Broadcast)方案。MHVB首先利用退火算法计算退火区域。处于退火区域内的节点无需继续广播数据包。接收到数据包的节点采用交通拥塞检测算法计算需等待多久方可转发数据包，在时间未到之前，就处于等待状态。如果交通拥塞，需延长等待时间。

文献[21]针对紧急消息广播，提出了BROADCOMM方案。BROADCOMM先依据MAC层协议的传输距离将高速公路划分多个虚拟的区域。处于区域中心位置或临近中心位置的节点作为该区域的Reflector节点。Reflector节点承担与邻居Reflector节点的通信，控制数据包的广播，并管理区域内节点数据包的接收、发送。

文献[22]提出CAID方案。在CAID方案中，持有数据包的节点在选择下一跳转发节点时，先计算邻居节点与数据包的相关性，将具有最大相关性的节点作为最佳下一跳转发节点。相关性包括数据包的相关性(如产生时间)、车辆相关性(如车速)以及信息相关性。

上述广播方案的特点总结如表1所示。

表1 广播路由协议总结

此外，在设计广播协议时，应考虑到达率Reachability、时延 Delay、平均开销 Overhead以及碰撞率 Collison 4个参数，可分别按式(1)～式(4)进行计算。

其中N为网络内节点数，L为最大传输距离，R为广播次数。Ri表示第i轮广播。、分别表示源节点在第i轮广播产生数据包的时刻、网络中最后一个节点收到数据包的时刻。Mi表示在第i轮广播中转发了数据包的节点数，Ki表示在第i轮广播中收到数据包的节点数，Ci表示在第i轮广播中发生数据包碰撞的次数。

3 总结与展望

表2分别从应用场景、电子地图需求、路由恢复策略以及转发模式四个方面对路由协议进行总结和比较。从表2可知，不同的路由协议应用场景不一，解决问题的出发点也各不相同。

表2 不同路由协议对比

从分析结果可知，VANETs中的路由协议应对车辆的快速移动具有鲁棒性，必须具有自适应能力，同时控制开销少、可扩展性强。下面在分析各类路由协议的基础上，预测VANETs路由协议的发展方向。

(1)鲁棒性

现有的路由协议的前提条件过于理想化，在实际环境中，难以实现这些条件。此外，VANETs内一些不确定因素对路由协议的稳定性提出挑战。因此，路由协议的鲁棒性必须考虑。

(2)安全性

现有的路由协议仅追求路由性能，未考虑路由协议的安全需求，包括用户数据授权、隐私保护以及通信安全。因此，如何在路由协议中引入安全保障是亟待解决的问题。

(3)仿真平台统一性

现有的VANETs路由协议实验仿真平台各不相同，未统一，并且一些路由协议的道路结构、车辆移动模型过于简单，设定的实验仿真场景与实际场景差异较大。因此，需进一步研究VANETs路由协议的仿真平台。

总体之言，国内外的研究人员针对VANETs不同场景提出了众多的VANETs路由协议，然而，在VANETs路由协议研究领域中，仍存在许多问题需解决。

[1]ZEADALLY S，HUNT R，CHEN Y S，et al.Vehicular ad hoc networks(VANETS)：status，results and challenges[J]. Science Business Media，2010，3(6)：23-39.

[2]李元振，廖建新，李彤红.城市场景车载 Ad Hoc网络竞争转发关键参数分析[J].电子学报，2011，38(5)：1154-1158.

[3]LEE J H，CHILMAKURTI N.Performance analysis of PMIPv6 based network mobility for intelligent transportation systems[J]. IEEE Transaction on Vehicular Technology，2011：23-32.[4]CHAN E，LI W.Two-step joint scheduling scheme for road side units(RSUs)-based Vehicular Ad Hoc Networks (VANETs)[C].Databse System for Advanced Application (DAS-FAA’2011)，2011：569-574.

[5]KARP B，KUNG H.Greedy perimeter stateless routing for wireless networks[C].Proceedings of ACM International Conference on Mobile Computing and Networking，2000：243-254.

[6]BASAGNI S，CHLAMTAC I，SYROTIUK V，et al.A distance routing effect algorithm for mobility(DREAM)[C].In Proceedings of ACM International Conference on Mobile Computing and Networking，2008：76-84.

[7]HAAS Z，PEARLMAN M.The performance of query control schemes for the zone routing protocol[J].ACM/IEEE Trans. Net.，2012，9(4)：427-438.

[8]PERKINS C，BHAGWAT P.Highly dynamic destination sequenced distance vector routing(dsdv)for mobile computers[C]. Comp.Commun.Rev.，Oct.2010：234-244.

[9]WEI R，DONG Y N，ZHAO H T.Improvement on locationbased routing protocols in wireless mesh networks[J].Journal of Nanjing University of Posts and Telecommunications(Natural Science),2012，32(1)：75-82.

[10]LI X，CUTHBERT L.On-demand node-disjoint multipath routing in wireless ad hoc network[C].In Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks(LCN04).Washington,DC,USA：IEEE Computer Society,2004,419-420.

[11]JOHNSON D B，MALTZ D A，HU Y C.The dynamic source routing protocol for mobile ad hoc networks[C]. IETF MANET Working Group,Tech.Rep,February 2007：34-42.

[12]CHAN E，LI W.Two-step joint scheduling scheme for road side units(RSUs)-based Vehicular Ad Hoc Networks (VANETs)[C].Databse system for Advanced Application (DAS-FAA’2011),2014：569-574.

[13]PERKINS C E，BELDING E M，DAS S R.Ad hoc ondemand distance vector(aodv)routing.RFC Experimental 3561[EB/OL].(2013-07)[2014-11-10]：http：//rfc.net/ rfc3561.txt.

[14]李昕，李刚.基于网关信息素更新的 MANET接人 Internet开销控制方法[J]．电子学报，2010,38(4)：870-874.

[15]徐会彬,夏超.VANETs路由综述[J].计算机应用研究, 2013,30(1)：1-6.

[16]LIU K，LEE V C.RSU-based real-time data access in dynamic vehicular systems[J].Vehicular Technology,IEEE Transactions on,2010,56(6)：3337-3347.

[17]RAHBAR H,NAIK K,NAYAK A.Dynamic time-stable geocast routing in vehicular ad hoc networks[C].Proceedings of the 9th IFIP Annual Mediterranean,2010：1-7.

[18]KORKMAZ G，EKICI E，OZGIINER F，et a1．Urban multi-hop broadcast protocol for inter-vehicular communication systems[C]．Proceedings of the 1st ACM International Workshop on Vehicular Ad Hoc Network，Philadelphia：ACM Press，2004：76-85．

[19]JIANG H,GUO H,CHEN L.Reliable and efficient alarm message routing in VANET[C]．Proceedings of the 28th International Conference on Distributed Computing Systems Workshops，Beijing，2008：186-191.

[20]OSAFUNE T，LENARDI M．Multi-hop vehicular broadcast (MHvB)[C]．Proceedings of the 6th International Conference on Telecommunications．Chengdu，2005：757-760．

[21]DURRESI M，DURRESI A，BAROLLI L．Emergency broadcast protocol for inter-vehicle communications[C]．Proceedings of the 11th International Conference on Parallel and Distributed Systems，Fukuoka，2005：402-406.

[22]ADLER C，EICHLER S，KOSCH T，et a1．Serf-organized and context adaptive information diffusion in vehicular ad hoc networks[C]．Proceedings of the 3rd International Symposium on Wireless Comunication Systems，Valencia，2006：307-311.

VANETs routing protocols：issues and challenges

Lv Daigang1，Wang Jinglei2，Li Yinghao3
(1.Zhengzhou Technical College，Zhengzhou 450121，China；2.Department of Electronically and Information Engineering,Zhengzhou University，Zhengzhou 451150，China；3.College of Geophysics,Chengdu University of Technology，Chengdu 610059，China)

With the development of vehicular ad hoc networks(VANETs)application,VANETs routing protocols is in-depth studied by researcher.Firstly,the characteristic features and application of VANETs are described.Then this paper introduces the conception of position-based routing,topology-based routing and broadcast-based routing,and emphatically analyzes and summarizes the core thoughts and characteristics of recent routing protocols.Moreover,a qualitative comparison of these routing protocols in terms of application environment,recovery strategy,forwarding method and digital map requirement is given in this paper.Finally,this paper discusses the directions for further for researchers of VANETs routing protocols.

vehicular ad hoc networks；routing protocol；position；broadcast；topology；robustness

TP393

A

0258-7998(2015)04-0016-04

10.16157/j.issn.0258-7998.2015.04.001

2014-11-10)

吕代刚（1975-），男，硕士，讲师，主要研究方向：计算机应用技术，信息处理，电子器件设计。

王静蕾（1979-），女，硕士，讲师，主要研究方向：计算机网络，数据挖掘，集成架构。

李英豪（1980-），男，博士，讲师，主要研究方向：图形图像处理及地理信息系统。

2013年河南省科技厅重点科技攻关项目（132102210181）