车辆网联环境下的交通感知路由协议综述

王 淼，徐志刚，赵祥模，刘丁贝，李骁驰

（长安大学 信息工程学院，西安 710064）

智能网联车辆的迅速发展，使道路上的车辆作为网络通信节点实时地进行信息交互成为现实，其中车辆节点的相互通信构成了车辆自组织网络（Vehicular Ad-hoc Networks，VANETs），VANETs实质上是移动自组织网络（Mobile Ad-hoc etworks，MANETs）在智能交通领域的一种具体的应用体现[1]。VANETs多采用多跳方式进行数据传输，基于传输的数据可进行交通信息的采集、交通事件的判决及预警等工作。但由于车辆节点的运动属性，车辆间的网络链接会频繁发生连接和断开，导致VANETs的网络连通性并不总是可靠的，所以完善的路由协议是保证VANETs中的智能网联车辆健壮通信的基础[2]。

与MANETs相比，VANETs中的网络节点——智能网联车辆，有着极其特殊的属性：节点速度跨度大导致节点间有效通信时间短；节点运动模式多变导致其网络拓扑结构频繁变化；道路及相关基础设施复杂导致其信息传输受阻碍因素多等。上述状况导致传统MANETs的路由协议难以直接应用在VANETs环境中[3-5]。

目前，很多研究人员考虑在传统距离度量的基础上引入新的路由度量标准，附加网络或者交通状态指标，以改善协议性能，基于这种思想构建的路由协议一般被称为基于交通信息感知的路由协议（Traffic Aware Routing，TAR），这类协议是未来VANETs网络路由协议研究的重要方向之一。本文简单总结了传统的MANETs路由协议的缺点，详细阐述了交通感知路由协议的概念，对现有TAR协议进行了分类，在此基础上概括了每一类交通感知路由协议的特点，并对下一步的研究方向进行了展望。

1 车载网络中的路由协议

早期VANETs路由协议基本分为三类：基于拓扑的路由协议、基于地理的路由协议和混合路由协议，它们主要继承了传统的MANETs路由协议[6]。混合路由协议是一种结合了基于地理路由协议和基于拓扑路由协议的综合性协议，这里不做介绍。

1.1 基于拓扑的路由协议

基于拓扑的路由协议又分为先应式和反应式，先应式路由协议又称为表驱动路由协议，特点是每个节点维护自己的路由表，并周期性地与其它节点进行路由信息的交换和更新并发现路由路径。路由是被预先得知的，当需要进行信息转发时，源点到目的节点的路径就已经建立，如序列目的节点距离矢量路由协议（Destination-Sequenced Distance-Vector，DSDV）[7]。反应式路由协议又称为按需驱动路由协议，其特点是当特定车辆节点发出请求时计算路由，不再需要周期性地进行消息的广播，转发路径在需要时才被建立，如无线自组网按需平面距离矢量路由协议（Ad-hoc On-demand Distance Vector，AODV）[8]、动态源路由协议 （Dynamic Source Routing，DSR）[9-10]等。

先应式路由协议提供了较佳的延时性能，但是对网络结构变化不敏感，不会实时更新，因此需要大量的控制包，增加了网络开销；反应式路由协议虽然开销小，但会产生较大的传输时延。拓扑路由协议做出路由决策需要获取整个网络的拓扑信息，而VANETs中的网络拓扑结构又频繁变化，导致它在车辆网联环境中的应用性能较差。

1.2 基于地理的路由协议

默认每个车辆节点都配备有定位设备，可获取自身和邻居节点的位置信息，根据地理位置选择转发路径，如贪婪周边无状态路由协议（Greedy Perimeter Stateless Routing，GPSR）[11]。车辆节点不需要维护路由表和存储拓扑信息，只需存储直接邻居节点的信息，与拓扑路由相比，基于地理的路由协议能更加灵活地适应VANETs。

地理位置的使用很大程度上提高了基于拓扑的路由协议的表现，但是仍然存在一些问题[12]，例如由于障碍物阻碍会导致车辆间的通信链路频繁断开，如图1所示，节点u、a，u、b之间由于障碍物阻碍使节点u、v之间传输链接断开；边界模式难以恢复，如图2所示，数据终点为D，在点S贪婪转发失败，切换至周边模式，试图以顺时针方向绕行，但是数据包在经历了A-B-C-D-E-F之后，才发现转发至错误的方向。

图1 车辆节点u、a之间的无线通信链路断开

图2 贪婪转发模式中的边界模式难以恢复

2 交通感知路由协议

多数地理路由协议都默认车辆节点可用性，然而并不是所有车辆节点都是可用的。此外，车辆节点密度会影响VANETs的网络连接状态，密度过低可能会导致网络连接断开，密度过高又可能产生很大的网络负载，车辆节点也会被看成影响传输的障碍物；道路等级会影响数据传递时间和车间通信质量；交通灯的存在会导致网络分区等[13-15]，因此，很多研究者在设计基于地理的路由协议时考虑引入网络状态信息和交通状态信息来优化协议性能，这类在地理路由中整合交通感知信息的路由协议称为交通感知路由协议。

2.1 交通感知路由协议的分类

多数交通感知路由协议是在地理路由协议的基础上产生的，是地理路由协议的一个分支，交通感知路由协议的设计大多基于以下三种基本的地理路由思想。

（1）地理源路由协议（Geographic Source Routing，GSR）[16]：源路由思想，使用区域地图和最短路径算法得到一条预测路径，数据转发依靠预测路径。TAR协议在预测路径时融入交通感知信息。

（2）贪婪周边协调器路由协议（Greedy Perimeter Coordinator Routing，GPCR）[17]：考虑交叉口节点的特殊性，认为交叉口处节点对数据包转发起引导作用，决定着数据包转发方向。TAR协议中，交叉口处的车辆节点根据路权公式计算相邻路段的路权值，选择权值最优的路段进行数据包转发。

（3）GPSR：基于节点选择思想，数据转发完全依靠节点。TAR协议根据节点的综合性能做出选择。

SEET等[18]提出的基于锚的街道和交通感知路由协议（Anchor-based Street and Traffic Aware Routing，A-STAR），和GSR一样采用源路由的思想，不同于GSR的是A-STAR有获取交通信息的能力。JERBI等[19]在其基础上进一步提出了改进的贪婪交通感知路由协议（Improved Greedy Traffic Aware Routing ，GyTAR），它在城市环境中有更佳表现。基于节点运动情况的路由算法（Movement-Based Routing Algorithm，MORA）[20]与基于运动预测的路由算法（Movement Prediction-Based Routing，MOPR）[21]，它们是在GPSR的基础上引入节点链路的质量信息。表1对这几种协议进行了对比。

表1 路由协议对比

由表1可知，融合感知交通信息后，由于节点运动速度过快，路边建筑物的干扰和局部最大所引起的问题均可得到改善，路由协议的表现明显优于GPSR和GSR。交通感知路由协议中的感知信息一般可分为两类：网络状态信息和交通状态信息。交通感知信息基本分类如图3所示。

图3 交通感知信息基本分类

网络状态信息感知：通过感知每条路段上的数据流量负载以避免数据包在拥塞路径上的传输。

交通状态信息感知：通过感知车辆密度和速度，可使数据包在转发过程中避免局部最优等问题。

根据上述GSR、GPCR和GPSR三种思路，交通感知路由协议可分为三个子类：基于源路由的路由协议、基于路权公式的路由协议和基于节点选择的路由协议，如图4所示。

2.2 基于源路由的交通感知路由协议

基于源路由交通感知路由协议的核心是源路由思想，常用最短路径算法Dijkstra获得一条预设路径，随后数据包按照预设路径进行转发。为了使用该算法，地图一般会提前被转化成权重图，路段的权重依协议所使用的度量因子而定。协议的设计围绕寻路和转发两个方面。表2对所涉及的协议进行了总结。

最早使用交通感知信息的源路由协议是A-STAR，协议认为拥有最多公交线路的街道有着最好的通信连接性，以公交线路的数量为基准给每条街道赋权值，使用Dijkstra算法选择路径，当出现局部最优的时候重新计算路径。

自适应连通性路由协议（Adaptive Connectivity Aware Routing，ACAR）根据预估的数据传输质量和通信连接性选择路径[22]。车辆节点可获取道路拓扑信息和交通统计数据。数据包转发的同时收集实时车辆密度，当统计数据和测量数据不一致并且差值超过预定的阈值时，当前节点向源节点发出预警信息，源节点更新密度信息并重新计算路由。其中，通信连接性的计算是基于道路路段的长度和路段内车辆数目完成的，传输质量的计算是基于包投递率完成的。

图4 交通感知路由协议分类

表2 基于源路由思想的交通感知路由协议

MOUZNA等[23]提出了车辆密度感知路由协议（Density-Aware Routing，DAR-RH），DAR-RH 中首次引入了路等级的概念，只考虑两个等级的道路，如图5所示，A点数据包要传递至B点，可在二级公路上传递A-B或者城市道路上传递A-C-B。在两条路上分别用Dijkstra算法得到预选路径并使用测试包在两个预选路径上实时收集交通感知信息，这两条路的测试包传递至终点后，终点根据测试包携带信息选择有最小延迟的路径。一旦初始选择的路径在数据包传递过程中发生路由失败，数据包开始沿着另一条路径传输。

图5 DAR-RH数据包传递示意图

HASHEMI等[24]提出了一种负载平衡路由协议（VANET Load Balanced Routing，VLBR），使用Dijkstra算出k条预设路径，如果当前转发路径发生拥塞，转发节点会向源点发出警告消息，源节点收到消息后切换路径。一段时间之后，源节点会自动切换回原始路径。此外，通过与预先设定的密度阈值做对比，每条路径被定义为稀疏或密集，节点根据不同的道路状态执行不同的转发机制。

XIANG等[25]提出地理无状态VANET路由协议（Geographic Stateless VANET Routing，GeoSVR），其核心是最佳转发路径算法（Optimal-Forwarding Path，OFP）和限制转发算法（Restricted Forwarding Algorithm，RFA）。OFP指定道路的宽度和长度代表车辆密度，根据这两个指标确定路权后算出最短路径，解决了局部最优和车间通信断开问题；限制转发算法是通过分析无线信道的特性得出最佳传输半径，解决了多跳通信之间不可靠的问题。但GeoSVR使用路的长度和宽度度量车辆密度是不可靠的。

CAO 等[26]提出一种使用了交通感知路由算法（Traffic Aware Routing Algorithm，TARA）的协议，该协议采用距离、数据包平均传输时间、车辆密度和速度四个度量标准，目的是发现一条有最小延迟和需要最少跳点的路径。TARA设置了一个定时器周期地发起路由发现过程，以保证路由的有效性。

LEE等[27]提出混合交通感知路由协议（Hybrid Traf fi c-Aware Routing，HTAR），根据车辆密度和网络负载计算最短路径，数据包中携带的路径可根据实时交通信息动态进行改变。HTAR最特别的地方是，它是一个实时的交通感知协议，可以通过实时信息调整路径。另一种与之相似的路由协议是基于结点的交通感知路由协议（Junction-Based Traf fi c-Aware Routing，JTAR）[28]，JTAR使用了新的方法收集交通感知信息，如图6所示，当两个收集包在路径中的某一节点相遇时，会彼此交换信息，然后直接返回各自出发时的交叉口，该方法有效地减少了收集交通信息的时间。

图6 JTAR收集交通感知信息示意图

基于源路由的路由协议一般都遵循先寻路、后感知路况的顺序，导致计算出的最短路径往往不是最终的转发路径，当路径失效时，只能重新计算路径。但是IBR[29]、HTAR和JTAR采取了实时采集路况并更新路径的策略，这进一步提高了投递率、降低了网络负载。

基于源路由的路由协议一般都使用Dijkstra算法计算预设路径，这需要遍历整个地图，由此带来额外的计算复杂度。但是GeoSVR很好地改进了这一点，只关注源点和终点之间的地图区域，这个方法有效地降低了计算复杂度，如图7所示。

图7 GeoSVR使用了区域地图

部分协议使用特定的数据包收集路况信息，如DAR-RH中使用了测试包，HTAR 和JTAR使用了收集包，但是这些数据包均采用了贪婪转发方式，贪婪转发的缺点会导致路况信息收集有误，在GeoSVR中对贪婪算法做出了优化，这可以作为参考方案用于以后的设计协议。

部分路由协议在确定车辆节点速度和路段密度时使用了统计数据，像A-TARA、ACAR、VLBR和TARA，但在车载网络中这些数值是高频变化的，统计数据常会引起误差。

王永福[30]提出的基于公交节点路由协议（Bus Node Routing，BCR），也属于源路由协议，但是它是一种表驱动路由协议，它引入了公交车信息，将公交车作为移动网络的主干节点，这个方法存在局限性，它只适用于公交车发达的城市环境。

数据包的传递都倾向于选择高质量的传输路径，这可能会在这条路径上造成网络拥塞和冲突，但是除了VLBR、HTAR、JTAR之外，都没有考虑负载平衡问题，虽然VLBR中使用了警告消息通知源点切换路径，但是它仅用来提示而没有阻止拥塞发生。

2.3 基于路权公式的交通感知路由协议

基于路权公式的路由协议的核心是根据路况信息为相邻路段判定路权，择优转发数据包。协议重点在于路况信息的收集和路权公式的建立。交叉口在路由中起引导作用，每两个连续交叉口之间的路段有一个唯一ID标识，转发车辆在交叉路口处根据感知信息对可选路段进行路权决策。交通信息的感知依靠在待测评路段上转发数据收集包。

最早提出的协议是GyTAR，之后的EGyTAR[31]和轻量级基于交叉口的交通感知路由协议（Lightweight Intersection-based Traffic-Aware-Routing，LITAR）[32]都是再此基础上进行的改进。GyTAR在每个交叉口处依照路权公式做出决策，使用数据收集包收集路况信息，每条路根据通信距离将其分为几个单元，数据收集包由单元的中心车辆产生。

图8 GyTAR中数据收集包的转发

EGyTAR（Enhanced GyTAR）在GyTAR的基础上对车辆密度的计算进行了改进，计算密度时只考虑运动方向朝向终点的车辆，而GyTAR只计算本单元内的全部车辆。

LITAR在之前的两个协议基础上又做了三点改进：（1）计算车辆密度时给不同方向的车辆密度赋予不同的权值。（2）产生回复收集包（Collector Packet Reply，CPR），使一次收集过程中路段的两个路口都能感知交通信息。（3）提出增强有效周期计算算法（Enhanced Validity Period Calculation，EVPC）和限制数据收集包（Collector Packet，CP）回复算法（Restricted Collector Packet Reply，RCPR）来消除不必要的CP和CPR的产生。

链接感知最小延迟路由协议（Intersection-Based Connectivity Aware Routing，ICAR）[33]，以车辆密度和传输延迟为度量指标做出决策，路况信息收集采用类似LITAR中的机制，ICAR中规定：如果没有收到CPR，则认为该路段不可使用。

图9 LITAR中数据收集包的产生和转发

该类交通感知协议对比总结见表3，其特性如下：大部分采用实时道路估计方法来获取交通感知信息，过程如图10所示，即从一条道路的端点向另一端生成、传输收集包，转发方式一般是贪婪转发；协议一般由两个并行过程组成，路权决策过程和数据包转发过程；协议多采用如下评分公式判定路权：

路权=α×度量标准1＋β×度量标准2＋γ×度量标准3

公式中的权重因子一般赋予相同的值（α=β=γ γ=0. 33）。这样的分配也许并不是最合理的，可根据协议的应用场景需要进行不同的权值分配。少数协议使用了路侧单元收集信息，因为实际情况中设置路侧单元经济成本高，如区域实时交通感知路由协议（Regional Real-Time Traffic Awareness Routing，LRTWR）[34]和 D-hop[35]。

图10 路况信息收集过程示意图

LRTWR在每个路口设置路侧单元，实时感知区域内车流量与路段内车间距离，以此建立交通流量-时延模型，并基于此模型进行路径选择。D-hop动态区域化协议，使用路侧单元获取路段的长度和最大速度，建立公式计算传输时间，选择传输时间最小的路段进行数据转发。

表3 基于评分思想的交通感知路由协议

2.4 基于节点选择的交通感知路由协议

基于节点选择的路由协议核心是节点选择的思想，不存在预设路径，寻径过程根据每个节点感知的信息进行，数据包只需获得下一跳点ID和终点ID即可。评估的对象一般是每个节点，相比源路由类的协议它有更低的网络负载，但是它没有考虑路段的整体状况，仅感知一跳范围内的邻居状态，所以这种协议一般适用于小范围传输。

直接贪婪路由协议（Directional Greedy Routing，DGR）是基于GPSR的改进[36]，在位置信息的基础上加入方向指标，增强的贪婪边界路由（Gpsrj+）[37]利用电子地图判断节点位置，通过预测数据包转发方向判断下一跳转发是否需要用过交叉口节点转向。在GPCR的基础上提高了数据包传递率，并且降低了跳数。马志维等[38]提出了基于节点速度信息的路由协议（Based on Node Speed Information Routing，NSRP），用车辆速度推算路段车辆密度，高密度时采用贪婪转发，低密度时则选择距离转发节点较近的车辆节点转发数据分组。表4展示了基于GPSR的改进协议的分析。

表4 基于GPSR的改进协议分析

多尺度地图感知路由协议（Multi-Metric Mapaware Routing，MMMR）[39]，使用多重度量标准选择邻居节点，MMMR中使用了四个度量因素，加强了节点转发的稳定性，带来了高投递率，但与此同时也增加了跳数和端到端延迟，在低车辆密度下易造成数据包丢失。如果传输可靠性和高投递率是数据包传输时考虑的主要因素，该协议是非常实用的。TIAN等[40]提出了一种数据分发算法，也使用了多重标准。以节点的邻居数量，距离当前转发点的距离，以及节点网络状态对节点进行建模评价，并根据计算结果选择转发节点。

链接感知地理机会路由协议（Link State Aware Geographic Opportunistic Routing，LSGO）[41]借鉴了极端机会路由协议（Extremely Opportunistic Routing，ExOR）[42]的思路，先寻找候选转发点集合，然后取转发优先级高的节点转发数据包，有效地提高了节点可靠性和数据包投递率，节点的选择参考地理位置和预期传输次数（Expected Transmission Count，ETX）。

基于节点质量的自适应机会路由协议（Quality of Node Basted Adaptive Opportunistic Routing，QAOR）[43]通过数据库统计数据评估节点的可靠性，在路口根据距离指标和节点可靠性选择下一跳，并在直路上采用加入携带转发机制的贪婪算法。

表5中对这几种路由协议进行了总结。

表5 基于节点的交通感知路由协议

3 结论

交通感知路由协议是近年来网联车辆通信领域新兴的研究方向，它更能适应VANETs中网络和交通状况随时间变化的特性，并且有着更高的数据包投递率和更低的延迟和负载。本文分析了早期路由协议的不足，引申出交通感知路由协议的概念，对最近出现的交通感知路由协议做了简单总结和分类，并针对每个子类进行总体概括和分析。

在今后的研究和探索中需要考虑以下几个问题：交通信息的实时感知是以牺牲网络负载为代价的，如何用更低的负载感知足够的信息是未来研究的重点。不同的协议中常使用同一路由度量标准（如车辆密度），但是不同协议中度量标准的计算和测量方法是不同的，下一步需要考虑更可靠的算法获得合理的路由度量值。如何使用度量标准作出最优决策，这与协议的应用场景相关，涉及到了路权公式的建立。针对不同的应用场景要灵活设计不同的方案，可考虑根据驾驶员意图为路由度量因子分配不同的权重，从而作出最优决策。此外，协议的设计一定要考虑恢复机制，交通感知路由协议无法应对全部的突发事件，如由驾驶员疲惫状态或心理因素等导致的车辆轨迹突变，为防止未知因素引起的路由失败，恢复机制的存在是十分必要的，然而现存大部分交通感知协议中并没有设计恢复机制。未来智能网联车辆具备驾驶员意图检测和预测能力后，可考虑引入车辆节点驾驶员疲惫指数、心理状态等因子建模，以提高协议的健壮性。最后，要考虑路由协议的安全性，这是保证道路安全的首要条件，引入安全算法考虑检测节点的可靠性，排除恶意节点对路由的影响，引入加密算法防止消息泄露等。