VANET 城市场景下基于车流特征的路由算法

张 智，张 剑，聂 铃，李陆君

（上海工程技术大学 航空运输学院，上海 201620）

0 引言

当前社会中，汽车成为人们出行必不可少的交通工具，同时也引起了诸多的社会问题［1］。汽车数量的增多、驾驶员行为方式的差异，造成交通拥挤，以及各类道路交通伤害等。为改善此类事件的发生，智能交通系统（Intelligent Transportation System，ITS）应运而生。车载自组织网络（Vehicle Ad-hoc Network，VANET）是智能交通系统的一种高级运用，车联网VANET 是由搭载了无线通信装置的车辆作为节点而构成的一种特殊形式的移动自组织网络（Mobile Ad Hoc Network，MANET）［2］。

由于VANET 中节点移动速度快，网络拓扑变化快速，特别是在城市环境中，节点移动路线固定，受道路拓扑影响；节点数量多且速度受限；建筑物高大密集，影响无线传输的性能等因素影响，很多路由协议并不适用于城市环境中车辆之间的通信。因此，研究适合于城市环境VANET 的路由算法，是当前VANET 技术的热点问题［3］。

1 相关工作

路由协议大体上分为两大类：基于拓扑的路由协议和基于位置的路由协议。前者需要考虑整个网络拓扑的信息，后者仅依赖于部分位置信息。目前，许多研究人员均对VANET 相关路由协议进行了研究。文献［4-6］中指出，AODV 是一种基于拓扑的路由协议，该协议主要实现路由发现和路由维护［4-6］功能。当源节点需要向目的节点发送数据包时，启动路由发现过程，并定期发送HELLO 包进行路由维护［7］。对于城市环境下复杂的路况信息，AODV 协议并不适用。GPSR 是一种基于地理位置的路由协议，主要实现贪婪转发算法和周边转发算法［8］。GPSR 基于平面图遍历，动态性高，易引发路由循环问题，适用于节点分布均匀、场景开阔的空间，不适用于城市环境的VANET［9］。Hassan 等人提出了一种针对城市环境的多度量地理路由（MGEDIR）。采用动态转发技术，以接收信号强度、传输范围边界关键区域、车辆未来位置等指标来选择下一跳车辆（NHV），在选择NHV 时考虑了最大的权衡因素［10］。Abbasi 等人提出了一种可靠路径选择和分组转发路由协议（RPSPF）的路由方案，采用基于锚的路由方法进行分组路由。RPSPF 动态地选择两个直接交叉点来求解路径灵敏度，通过短曲线距离指标选择下一跳车辆［11］。

综上所述，研究人员提出了不同的适用VANET路由算法，但这些路由算法在一定程度上易产生传输开销和时延问题。为此，本文提出了一种基于车流特征的路由算法（TCR）。该算法利用车流特征等资源，设计了符合城市交通环境VANET 的路由算法，保障车间通信的高效稳定传输，提高道路上的交通效率和车辆行驶的安全性。

2 系统模型和约束条件

2.1 系统模型

本文对VANET 网络在城市环境下性能的研究，主要考虑城市场景中典型的道路模型，由十字路口和直路段道路建立而成。图1 所示为SUMO 仿真软件建立的城市道路模型图。

图1 城市道路模型图Fig.1 Urban road model diagram

其中，Ii表示第i个十字路口，Si，j表示直路段，每个路段均有自己的属性，包括长度、车道数、车流密度等。

2.2 约束条件

随着计算机和车联网技术的发展，车辆会成为可具备高计算处理能力的设备，本文提出的TCR 路由算法的实施基于以下的前提和假设：

（1）以VANETs 的城市场景为研究对象。

（2）每辆车预装数字地图和全球定位系统GPS，包括街道地图和交通统计数据。

（3）每辆车均配备车载单元OBU，每个车辆具有至少300 米的可访问通信范围，可通过信标交换获取实时信息。包括车辆ID、速度、当前位置及所在道路位置。

（4）道路交叉路口配备路测单元RSU，RSU 根据相邻的两个道路获取实时信息，包括当前道路ID、长度、车辆数及车辆密度。

（5）车辆拥有协作感知消息（CAM）：节点会按照ETSI 标准中指定的方式发送CAMs；包括状态矢量信息，如物理位置、目的地、当前速度和方向。信息包报头包括源节点ID、源节点位置、信息包生成时间、过期时间。

（6）将城市VANET 抽象为G＝｛V，E｝，V 表示车辆，E 表示通信链路。

3 TCR 路由算法

3.1 最优路段选择

3.1.1 连通度计算

首先，定义辅助节点AN：每个道路段最外层的两个节点，如图1 所示。AN 节点将会帮助节点之间进行车辆密度信息交换和连接度值的估计。车辆周期性地广播beacon 消息，并与附近的车辆节点和路测单元RSU 进行信息交换。随着传输范围的扩大，HELLO 包消息定期更新相关的邻居表，进行邻居表的维护。所以车辆节点在进入到一个路段后，车辆会意识到自己的位置，判断自身是否为AN 节点，获取该路段上的ID 以及车辆密度，路段Si，j上的车辆密度ρi，j。计算公式如式（1）所示。

其中，Si，j表示十字路口Ii和十字路口Ij之间的路段；Ni，j表示路段Si，j上的车辆总数；Li，j表示路段Si，j的长度；n表示车道数。

AN 节点收集RSU 和其它候选节点的相关信息。其中包括路段ID、传输时间、传输范围、路段上车辆密度等，并将这些信息传送给附近可以传输的AN 节点。AN 节点根据收集到的相关信息选择合适的路段。

一个路段可由两个端点的元组表示［12］。一个道路的两端路口可表示为（S，dS）和（S，dd），而网格区域内各线段的结节点坐标可表示为：对于给定的道路路段，连通度ECD 的计算为式（2）所示［13］。

3.1.2 车流分布偏差的计算

为进一步反映车流量，定义车辆的相对位置变量。对于车辆Vehm，其在路段Si，j上的相对位置为如式（3）所示。

其中，表示车辆Vehm的位置，是beacon消息中的载入位置，定义车辆的相对位置是为了方便计算车流分布情况，并将道路长度为L的路段等间隔分成N个路段，则每个均分后路段长度Lav如式（4）所示。

定义nh表示第h个路段，则路段Si，j上车流分布的标准方差σij如式（5）所示［14］。

为了进一步反映车流分布的均匀性，依据概率论计算道路段Si，j车流分布的偏差γij，如式（6）所示。

偏差γij越小，表示车流分布越均匀。

为选出最优的路段进行数据包转发，通过预估的连通度和车流分布的偏差两个参数，构成评价函数F，如式（7）所示。

其中α、β是权重因子，且α+β＝1，α ＞0、β ＞0，具体参数值需要结合仿真调试获得。通过预估连通度，计算有效节点间的连接性，尽可能地保证候选车辆在传输范围内；通过车流分布均匀性的计算，也保证了候选车辆的充分性。

评价函数F不仅考虑了源节点到目的车辆节点之间所有候选路径的质量，还考虑了源节点到目的车辆节点之间的跨路径的分段连接。由式（7）可知，当连通度和车流分布都达到最好参数值时，评价函数F就会取得最大值，此时，所选的路段就是数据包转发的最优路段。

3.2 道路段内数据包的转发

道路段内数据包转发采用改进的贪婪转发算法，与传统的贪婪转发算法比较存在3 个方面的优化：增加了链路状态因子L、方向因子F、距离因子D，避免传输跳数和路由中断次数的增加，进而减少端到端的时延，保证链路的稳定性。

3.2.1 链路状态因子L

城市VANET 拓扑结构变化快速，大多是由车辆的速度和运行方向变化引起的，这些因素将影响链路的稳定性。本文利用车辆节点之间的相对位移量来计算链路状态，节点之间进行周期性地广播信标消息，节点之间的距离通过式（8）即可获得。

其中，(xs，ys)表示发送节点的坐标；(xi，yi) 表示一跳传输范围内的邻居节点坐标。

链路的稳定性如式（9）所示。

其中，R为常量，表示通信传输半径，di（t）表示t时刻发送节点与一跳范围内邻居节点的距离。通过式（9）可知，节点之间相对位移量变化越小，则链路越稳定。同时，链路的维持时间也是链路可靠性的关键因素。本文通过节点之间发送的beacon数据包，计算链路的维持时间ti，如式（10）所示。

其中，(xs，yS)表示发送节点的坐标；(xi，yi) 表示一跳传输范围内的邻居节点坐标；R为通信传输半径；v表示节点的相对速度。相对速度的计算如式（11）所示。

其中，vi表示邻居节点的速度，vs表示发送数据包的节点速度。

为更准确地表示链路的维持时间ti，本文将其进行归一化处理，如式（12）所示。

其中，Tmax表示最大持续时间。

根据上述度量指标，可得出链路状态因子L，如式（13）所示。

3.2.2 方向因子F

本文算法定义车辆运行方向与数据分组的传输方向一致时，数据包标志位Flag标识为+1，反之，则标识为-1。如式（14）所示。相同方向的节点给予同样的优先权，同时对车辆行驶方向与数据分组传输方向相同的车辆节点给予更高的优先权，这些车辆节点优先作为候选的下一跳节点。

3.2.3 距离因子D

除上述链路状态、车辆的行驶方向和数据分组的传输方向以外，本文算法还增加了车辆之间距离因子度量指标，如式（15）所示。在具有相同方向优先级的情况下，优先选择距离目的节点最近的邻居节点。

式中，(xD，yD) 表示目的节点坐标；(xi，yi）表示一跳传输范围内的邻居节点坐标；n 表示具有相同优先级节点的个数。应避免因城市VANET 的高度动态性，造成边缘节点下一跳移出通信范围，从而引起链路中断，造成数据包的丢失或重发。

3.2.4 转发节点的选择

在道路段内进行数据包的转发，本文结合链路状态、方向因子、距离因子3 个方面因素，权衡选取下一跳转发节点，不仅保证了链路的稳定性，同时也在传输方向优先级相同的情况下，优先选取距离目的节点更近的邻居节点作为下一跳的转发数据包节点。转发节点的选择如式（16）所示。

其中，L指发送节点s与邻居节点i之间的链路状态；F是节点的运行方向与数据包传输方向的一致性判定；D是邻居节点与目的节点的最小距离判定；di指发送节点与邻居节点之间的距离。由于本文只计算一跳范围内的邻居节点，则di还包括一跳范围内的邻居节点与发送节点之间的距离，其中权重系数ω1＝ω2＝ω3＝0.33。

当Rank ＞0 时，根据式（16）选择下一跳转发节点；当Rank＝0 时，说明形成了局部最优问题。此时只需发送节点携带数据包，继续等待下一个合适的转发节点进行转发即可。等待时间T 设定一个阈值ε，当T ＞ε时，发送节点结束等待，放弃相应的数据包，源节点进行重发。

4 性能分析

为了更好地评估TCR 算法的性能，对TCR 算法进行仿真试验，并与AODV、GPSR 两个协议进行对比。仿真主要是从数据传输成功率、平均端到端时延两个方面进行性能的比较和分析。

4.1 仿真模型

本文利用SUMO 和NS 软件建立仿真平台，从OpenStreetMap 官网上选择上海松江大学城区域图作为仿真地图，如图2 所示。图3 为SUMO 软件可打开的对应场景拓扑图。在SUMO 中编写车辆移动模型，利用NS2 脚本调用SUMO 中相关文件，并进行相应的参数和流量配置。经过仿真实验的不断调试，对于最优路段评价函数性能较佳时的权重参数选定为α＝0.75，β＝0.25，其它仿真参数详见表1。

图2 松江大学城区域图Fig.2 Regional map of Songjiang University Town

图3 松江大学城拓扑图Fig.3 Topology of Songjiang University Town

表1 仿真参数Tab.1 Simulation parameters

4.2 仿真结果与分析

4.2.1 数据传输成功率

数据传输成功率，是指网络中目的节点接收到的数据分组总数与源节点发送的数据分组总数之比，反映的是数据传输的可靠性。

图4 反映了3 种协议下数据传输成功率与车辆数的变化曲线关系。本研究设置车辆数为50、100、150、200、250、300。由图可见，当车辆速度固定时，随着车辆数的递增，车辆节点之间链路数增多，传输成功率也随之增加。3 种协议中传输成功率最低的为AODV 协议，其次为GPSR 协议，本文提出的TCR协议的传输成功率明显高于AODV 与GPSR 协议。由于AODV 与GPSR 协议都未考虑车流特征相关因素，而TCR 协议结合车辆密度与车流分布情况，计算每个路段的连通度，选择源节点与目的节点之间链路质量最优的路径，不仅提升了数据包到达目的节点的概率，同时也提高了数据包的传输成功率。

图4 数据传输成功率与车辆数关系图Fig.4 Relationship between data transmission success rate and number of vehicles

图5 反映了3 种协议下数据传输成功率与车辆速度之间的变化曲线关系。本研究设置车辆速度为10、20、30、40、50 km／h。由图可见，当车辆节点固定时，3 种协议的传输成功率都受车辆速度因素影响，随着车辆速度的增加，数据传输成功率都有不同程度的下降，当车辆速度增加时，网络拓扑结构变化大，车辆节点之间链路持续时间减少，链路稳定性变差，易发生断裂，数据包丢失概率增加，所以数据传输成功率相应下降。由于AODV 协议是基于拓扑的路由协议，GPSR 协议考虑因素单一，都不适合VANET。TCR 协议权衡密度信息与全局搜索，选择最佳路段，实时性较低，因此TCR 协议数据传输成功率始终高于AODV 与GPSR 协议，且变化趋于平缓。

图5 数据传输成功率与车辆速度关系图Fig.5 Relationship between data transmission success rate and vehicle speed

4.2.2 端到端平均时延

平均端到端时延是指数据分组，从源节点到目的节点的平均发送时间，反映的是数据传输的有效性。

平均端到端时延与车辆数变化曲线关系如图6所示。本研究设置车辆数为50、100、150、200、250、300。由此可见，当车辆速度固定时，随着车辆数的增加，3 种路由协议的平均端到端时延都有明显的下降，TCR 协议进行路段选择时，计算各个路段以及跨路段的连通性，相比于AODV 与GPSR 协议，平均端到端延迟最少，且随着车辆数的不断增加，TCR的平均端到端延迟下降变化趋势愈加平缓。

图6 平均端到端时延与车辆数关系图Fig.6 Relationship between average end -to -end delay and number of vehicles

图7 给出了平均端到端时延与车辆速度之间的变化曲线关系。本研究设置车辆速度为10、20、30、40、50 km／h。由图中可知，当车辆节点固定时，车辆速度变大时，3 种协议的时延都在增加。在车辆速度不断增加的过程中，车辆节点位置快速发生变化，网络拓扑结构快速改变，网络中车辆节点之间的连通性不断降低，在数据包转发的过程中，车辆节点一跳范围内可选的下一个转发节点概率在减少，数据包传输到目的节点的时间就会增加，相应的平均端到端时延增加。TCR 协议与AODV、GPSR 协议相比，在保证链路可靠性的基础上，增加了链路因子、方向因子、距离因子3 方面因素的考虑，减少了平均端到端时延。

图7 平均端到端时延与车辆速度关系图Fig.7 Relationship between average end-to-end delay and vehicle speed

5 结束语

针对城市场景VANET 的网络特性，提出了基于车流特征的路由算法TCR，通过预估实时车辆密度信息和路段连通度，进行最优路段选择外，对道路段内数据转发进行了优化改进。仿真表明，TCR 算法在数据传输成功率和平均端到端时延方面都要优于AODV、GPSR 协议，能够更好的满足城市场景下VANET 的通信需求。