智能网联车环境下基于路段评分的数据转发模型

毕俊蕾 朱宗强 李致远

（1.江苏大学信息化中心，镇江，212013；2.江苏大学计算机科学与通信工程学院，镇江，212013；3.江苏省工业安全重点实验室，镇江，212013）

引 言

智能网联汽车(Intelligent connected vehicle，ICV)[1]是指车联网与智能车的有机联合。智能网联汽车搭载了先进的车载传感器、控制器和执行器等装置，并通过现代通信与网络技术，实现车与人、车、路和后台等智能信息交换共享。在智慧城市交通中，车辆间的组网和通信受到以下多方面的约束：（1）受道路场景约束，交通信号灯的存在对车辆在道路上的分布影响较大，表现为红灯时车辆在路口排队，绿灯时路口排队车辆逐渐通行，这种现象随交通信号灯变化而周期性变化，进而影响车辆在路段的整体连通性。（2）受驾驶者的工作时间约束，在工作日上下班高峰期道路车辆密度较高，而夜间道路车辆密度相对较低。（3）受地域范围的约束，城市中心地段车辆密集，城市外围车辆相对稀疏。

国内外学者对上述约束展开了广泛的研究，归纳起来分为3类：（1）基于洪范式的数据转发算法[2-3]。它是指整个转发过程中节点不依赖任何外界信息。这类转发算法具有简单易实现的特点，缺点是算法运行产生的控制开销较高。（2）基于地理位置的数据转发算法[4-5]。这类算法根据导航定位设备实时感知地理位置实现最优路径的规划。算法的不足之处在于容易陷入路由空洞。（3）基于路段评分的数据转发算法[6-14]，在选择下一跳时不再依赖局部节点信息，而是评估当前整条路段的状况，对该路段上网络连通状况进行评分，将统计评分高的路段连接在一起形成源到目的节点的有效数据转发路径。该类数据转发算法的优点是实现了全局路径规划，不足是对道路场景等约束考虑不足。比如，车辆的移动轨迹受道路限制，消息转发的改变通常集中在路口处，而现有数据转发模型通常会忽略路口处车辆受交通信号灯因素的影响，从而导致车辆间的链路生命周期较短，消息的投递成功率大大降低的现象。针对城市ICV环境中的上述特点和挑战，本文提出智能网联车环境下基于路段评分的数据转发模型(Road section scoringbased data forwarding model for intelligent connected vehicles，RSSM)。

1 相关工作

目前智能网联车环境下的数据转发策略归纳起来分为3类，即基于洪范式的数据转发算法[2-3]、基于地理位置的数据转发算法[4-5]和基于路段评分的数据转发算法[6-14]。文献[2,3]属于洪范式的数据转发算法，即携带消息的节点会将自身携带消息完整地拷贝给相遇的节点，若相遇节点为目标节点，则表示数据转发成功。其中，文献[2]提出的数据转发算法没有对消息的副本数量进行限制。尽管这种做法可以提高数据包的投递成功率，但是大量冗余的副本数据包会占用有限的节点存储空间并消耗有限的网络带宽资源。文献[3]提出的数据转发算法考虑了对副本数据包的限制。它将整个数据转发过程分为喷雾和等待两个阶段。其中，第1个数据转发阶段，源节点S携带的副本数为L（L＞1），当源节点S遇到节点T时，将数量为的副本发送给相遇节点T。若T为目标节点，则本次数据转发成功，结束本次数据转发。否则，节点T作为中继节点携带的数据包副本继续辅助转发，源节点S携带的副本数更新为，此过程反复迭代，直到数据包到达目标节点，数据转发过程结束。

文献[4,5]属于基于地理位置的数据转发算法。其中，文献[4]提出基于地理位置的定向车辆路由基于位置的车辆定向路由(Position-based directional vehicular routing，PDVR)。PDVR综合考量相邻车辆的位置、移动方向及目标节点的位置来选择下一跳节点，该过程反复迭代直到到达目标节点，从而构建一条稳定有效的数据转发路径。PDVR在无转向的直线道路上性能表现良好。但当车辆轨迹的曲率较大时，PDVR算法的性能会急剧下降，这意味着PDVR无法很好地适应由各类交叉路口、立交桥组成的智慧城市环境。文献[5]提出采用基于地理位置信息的贪心策略来构建源节点到目标节点的数据转发路径，与文献[4]不同的是文献[5]重点关注解决数据包非视距传输问题。文献[5]的不足之处在于数据包转发依赖交叉路口的辅助节点，当辅助节点负载过大时，会导致数据转发路径计算南辕北辙的现象，使得数据包的传输成功率降低。

文献[6-14]属于基于路段评分的数据转发算法。其中，文献[6]考虑车辆的行驶上下文信息、道路的交通状况，提出了道路交叉点评分策略流量感知的贪心路由协议(Greedy traffic aware routing protocol，GyTAR)。GyTAR在十字交叉路口处能够找到适合的路段作为数据转发路径，但对于分道线夹角小于90°的复杂交叉路口，GyTAR无法判定车辆将要驶入的路段，导致数据包很难准确地投递到目标节点。此外，GyTAR在路段评分方法上没有考虑道路车辆的行驶方向和速度及交通信号灯对车辆在道路分布上的影响。文献[8]根据实时车流量计算出每条道路的消息投递时延，以及连接时间的估计值，并据此动态地调整数据转发路径，所提出的数据转发算法基于交叉路口连通感知的车载路由协议(Intersection-based connectivity aware routing,iCAR)整体上表现出良好的路由性能。而其在转发路径计算过程需要的参数数据采集依赖于大量的控制报文，从而使得数据的传输效率大大降低。

2 基于路段评分的数据转发模型

定义1任意路段ξ路段评分与得分Scoreξ应该和路段长度Lξ、路段连通率Cv,ξ、车辆行驶的平均速度 Vˉξ有关，其计算方法为

式中：μ,η,β为权值，Cξ(t)为 t时刻路段 ξ的连通率，Vˉξ为编号为 ξ路段上车辆行驶的平均速度，Vmax,ξ为路段ξ的最大限速，Lξ为路段ξ的长度，LroID为路段编号为roID的路段长度。

定义2t时刻路段ξ的连通率路段连通率Cξ(t)为连通部分长度之和除以整条路段的长度L，即有

在计算路段评分时，需考虑车辆在道路分布上受交通信号灯的约束。于是将道路i分成两部分考虑，如图1所示，分别为路口两端lsta,1,lsta,2部分路段和除去lsta,1,lsta,2部分后的lfre部分路段。其中lsta,1,lsta,2部分路段上车辆受交通灯影响较大，该部分路段上车辆间距小且稳定，所以链路相对稳定，节点链路的总长度近似为排队车辆长度，lfre路段上车辆几乎不受交通信号灯影响，近似于自由行驶。这两部分的路段长度是随着车辆节点的分布情况不断变化的。为了叙述方便，本文将道路的两端处长度为车辆排队长度的部分路段称为稳定连通路段（即lsta,1,lsta,2部分路段），其余部分即lfre部分路段称为自由行驶路段。这两部分路段上的节点间的链路连通性相互影响。

图1 路段i划分示意图Fig.1 Diagram of road section division

2.1 稳定路段连通性评分

城市交通中道路类型较多，主要分为主干道路、次干路、支路和区间路，这些道路大多是双向道路，且道路两端均设有交通信号灯，为使模型更具一般性，本文选择双向多车道路段作为分析对象。如图1是一个双向车道路段，假设相同方向共有m（m≥1）条车道。

以1个交通控制周期为研究对象，定义交通信号灯周期为信号灯从红灯开始到变为绿灯，再由绿灯变为红灯的过程（黄灯时间段在此统计为绿灯时间）。Tr,beginj,Tg,beginj,Tg,endj分别为1个交通信号灯周期内路口j的红灯和绿灯的开始时刻及绿灯结束时刻（j=1或2，分别代表同一路段的两个路口）。路口j处交通灯在t时刻变为红色，则在路口j处排队等待的车辆数为Np,j随着时间变化关系为

式中：L为该路段的长度，Vˉj为路段上驶向路口j的车辆平均速度，Nsum,j为路段上驶向j路口的车辆总数。

如图2所示为车辆路口排队的示意图，lˉv为路口处排队车辆的平均车间距，lˉd为路口处排队车辆的平均长度。以停车线为坐标原点，车辆行驶的方向为正方向，可得路口处第n（n≤Np,j）辆排队车辆的坐标Xn为

图2 车辆路口排队示意图Fig.2 Diagram of vehicle queuing in road section

当t=Tjg,begin时，即在一个交通信号灯周期内红灯结束时刻，车辆在路口处排队长度lsta,j,max达到最大，如式（5）所示。此时，路口处的排队车辆车间距较小，相邻车辆是全连通的。那么，排队车辆的长度即为网络全连通的路段长度。

此外，设红灯结束时等待车辆通过路口停车线的时刻tr为

式中：t0为车辆的平均加速时间，Td为路口处前后两辆相邻车辆启动的平均时间间隔，Vˉj为车辆驶离路口时的平均速度

当Tr,beginj≤t＜Tg,beginj时，车辆在这个时间区间内受交通信号灯的影响，在路口处停车聚集，呈现局部比较稳定连通现象；当Tg,beginj≤t＜tr时，路口等待红灯的车辆陆续启动，但是同样有车辆到达路口处停车聚集，因此，近似认为在这个时间区间内，稳定连通路段长度不会改变，即在该时间段内路口j的聚集车辆数为Np,j(Tg,beginj)。当tr≤t＜Tg,endj时，路口处车辆和路段中间的车辆行驶状态类似，即自由行驶状态，因此稳定连通路段的长度为零。综上所述，路口j的稳定连通路段的长度随时间以及交通信号灯周期变化关系满足

由于路段两端场景近似相同，所以路段i总的稳定连通路段长度lsta为

上述统计量均可由RSU感知，因此，RSU能实时地计算出其所在路段的稳定连通路段长度。对路口处路段车辆连通长度的计算使自由行驶路段上的车辆密度计算更加准确，从而反映路段i上车辆网络的连通情况。

2.2 自由行驶路段连通性评分

假设道路上单向单车道有δj个车辆，其中λ个相邻车辆之间不连通，则有δ-λ-1个相邻车辆节点之间是全连通的。其发生的概率用PQ,j表示，有

道路上单向单车道内λ个相邻车辆之间是不连通的情况，在单向多车道的场景下，可借助相邻车道内车辆实现连通。在此场景下，自由路段在交叉路口j为1或2的方向上连通的概率PW,j(t,λ)为

综上所述，可得自由行驶路段上车辆链路整体的实时连通概率Pcn随时间变化的关系式为

2.3 基于路段评分的数据转发算法

图3为路网等效示意图，以路段两端的路口为参考点，将道路交通图抽象为无向加权图，图3中边上权重值大小即为评分值的大小。参考点之间的权值会随着路段车辆状态的改变而实时更新。在生成的路网无向图上使用贪心算法求源节点到目标节点的最短路径，求解过程如算法1所示。

算法 11：ShortPath(G,w,s,d)

输入：图G(V,E),边上权重w,源节点s,目标节点t。

输出：ShortPath(s,t)and ：ShortDist(s,t)。

Begin

Initialize-single-source(G)

for i=1to|V[G]|-1

for each edge(V,E)in G

RELAX V,E,w

while((each edge in G)and(j!=t))

if(w[s][i]+w[i][j]＜w[s][j])

then dist[s][t]=w[s][j],s.append(i,j)

End

图3 路网等效示意图Fig.3 Equivalent diagram of road network

创建源顶点v到图3中所有顶点的距离的集合distSet，为图3中的所有顶点指定一个距离值，初始均为无穷大，源顶点距离为0；对图3(b)执行V-1次遍历，对图3(b)中边上的权重w进行赋值，即路段得分Score；i,j为s到t的中间节点，计算源节点到目标节点的最小值，将中间过程存入队列，最后，输出最小值及源点到目标节点的转发路径。

3 仿真实验与评估

3.1 仿真环境和参数设置

实验在开源道路交通仿真软件SUMO和网络仿真平台 NS-3（Network Simulator-3，NS-3）上完成。SUMO用来提供真实的车辆在道路上运动的模型，NS-3用来仿真不同节点、不同TTL值的数据包条件下数据包的转发成功率和平均转发时延。实验在CPU为Core™i5-2450M、内存为8.00GB和操作系统为64位的Ubuntu16.04运行。仿真实验参数如表1所示，仿真实验场景和运行如图4所示。

选取南京市郊区为仿真道路的实验场景，命名为nanjing.osm，如图4(a)所示。将SUMO的轨迹文件导出成NS-3能够使用的tcl文件，操作步骤如下：使用bin目录下的sumo程序将nanjing.sumocfg文件转换成nanjing.Trace.xml文件，再由traceExporter.py将nanjing.Trace.xml文件转换成nanjing.tcl文件供NS-3使用。使用NetAnim展示节点运动和数据转发的运行图如图4(b)所示。

表1 仿真实验参数Tab.1 Parameters of simulation experiments

图4 仿真实验运行图Fig.4 Diagram of simulation experiments

3.2 实验结果分析

本文选用PDVR[4]，GyTAR[6]，iCAR[8]作为本方法的对比对象，从节点移动速度和数据包的生命周期(Time to live，TTL)值两个方面在投递成功率和平均投递时延方面进行比较。

如图5所示为节点移动速度变化情况下的数据投递成功率仿真。当节点移动速度较低时，网络拓扑变化较慢，通信链路比较稳定，各类算法的投递成功率均较高。随着节点移动的平均速度加快，链路的稳定性变差，各类算法的数据投递成功率均有所下降。而RSSM在数据转发路径上实现了对节点速度快导致的网络拓扑变化场景下的实时调整，尽力保障了数据转发路径的最大连通性，与同类方法比，实现了较高的数据转发投递成功率。

如图6所示为节点移动速度变化情况下的平均投递时延仿真。当节点移动速度较低时，网络拓扑变化较慢，通信链路比较稳定，各类算法的平均投递时延均较低。随着节点移动的平均速度加快，链路的稳定性变差，重传次数增加，各类算法的平均投递时延均有所上升。而RSSM除了在数据转发路径上做了实时调整，尽力保障数据转发路径的最大连通性外，还使用了消息均衡分配方法，避免部分节点消息缓存过高，导致消息不能及时转发的现象，与同类方法比，实现了用户可容忍的平均投递时延。

如图7所示为数据包TTL值变化情况下平均投递成功率的仿真。若数据包在TTL值将要达到事先设定的阈值时，不能将其投递至目标节点，就会从网络中删除，将其按照数据投递失败统计。随着TTL值的增大，各类算法的投递成功率随之增大。当TTL值达到一定数值时，数据包投递成功率趋于稳定。这是由于TTL设置较大时，各类算法的数据投递成功率与数据包在网络中的生命周期无关，由其各自的路径规划算法决定。本文提出的RSSM从全局上根据整个路网的状态进行动态的路径规划和修复，这是与同类算法相比RSSM具有较高投递成功率的原因。

图5 节点速度对投递成功率仿真Fig.5 Simulation for node speed versus delivery success rate

图6 节点速度对平均投递时延仿真Fig.6 Simulation for node speed versus average delay

如图8所示为数据包TTL值变化情况下平均投递时延的仿真。显然，数据的平均投递时延与数据的TTL值成正比。当数据包的TTL值较低时，数据包被投递成功所需时延较低。随着数据包TTL值的增加，有更多的消息被投递成功，而单个消息被投递成功的时延增加，因此平均投递延迟随之增加。文中提出的RSSM在路径规划上考虑整体最优，使单个消息投递成功的耗时最低，整体表现出较低的平均投递时延。

图7 TTL值对投递成功率仿真Fig.7 Simulation for TTL to delivery success rate

图8 TTL值对平均投递时延仿真Fig.8 Simulation for TTL value to average delay

4 结束语

本文面向智能网联车环境，提出一种基于路段评分的数据转发模型。主要工作包括：对稳定路段和自由连通路段的连通性评估，并基于路段连通性评估设计路段和路网的评分标准。之后将其抽象为无向加权图，并在其基础上实现全局最优的路径规划。最后，通过仿真实验比较和分析得出文章提出的RSSM模型在节点不同移动速度和数据包不同TTL值情况下，其数据包投递成功率和平均投递时延均优于同类型方法。本文下一步的工作是考虑短时交通流预测及链路信道质量等因素，进一步优化路段评分和下一跳路径选择算法。