一种基于GyTAR道路连通性预测模型的改进算法

蔡震

摘 要：基于路口的VANETs路由协议GyTAR，其道路连通性预测模型方法设计新颖，但在CDP发送车辆的选取上存在一定缺陷，导致预测结果在实时性和准确性上效果不佳。针对此缺陷，本文进行了改进，在车辆进入道路后按照其先后时间选取CDP车辆，得以有效的控制CDP之间的发送时间间隔，提升了连通性模型的准确性和实时性，并通过仿真实验验证其效果。

关键词：VANETs；GyTAR；道路连通性预测

1）基于路口的VANETs路由形式能很好地适应城市环境[ 1-6 ]。这些路由协议均由处于路口车辆来进行路由决策，路由道路选择的判定因素有如下两点：

a.下一路口距离目的节点的距离，沿更短距离的道路传送数据包将会有效减少连接断开的几率；

b.待选道路上多跳链接的连通性预测或延迟时间预测，即道路上是否有足够多的继车辆節点使数据包在最短时间内成功传送到下一路口。

GyTAR[ 7 ]采用了一种比较新颖的连通性预测方法，在准确性和实时性上均表现不错，但其也存在一定的缺陷，本文将针对这些缺陷，提出一个新的改进算法。

2）GyTAR（Improved Greedy Traffic Aware Routing）中，在道路上行驶的车辆将自身的地理坐标位置通过信息交换，实时维护周围邻居车辆节点列表，其中邻居车辆的位置、行驶速度、行驶方向。路口节点通过其收集到的信息，会为每条道路通往的下一个路口计算出分数，公式如下：

此公式考虑了道路长度、每个区域的车辆数以及各个区域车辆数量分布是否均匀。公式的关键是如何有效获得每个区域的实时车辆数Ni，GyTAR的方法如下：按照车辆信号传输距离（通常VANETs为250m）每条道路被分为若干区域，处于每个区域中心范围（GyTAR模拟实验采用的是半径40m的圆）内且离中心位置最近的为未来发送CDP的车辆（以下简称CDP车辆），当每辆CDP车辆离到达下一路口时，便向后方发送一个CDP，其中包含道路ID、发包时间和此道路的区域列表（区域名称、区域中心位置、区域内车辆数）。

当发送到第一个区域中心范围内且离中心位置最近的车辆时，此车辆便把当前其邻居车辆的数量更新到CDP中，并继续向后转发数据包，同时把自己标志为CDP车辆。

换言之，只有更新过CDP的车辆在离开当前道路时，才会生成一个新的CDP向后发送。以此类推，当CDP传送至上一路口时，路口车辆节点便得到了整条道路上每个区域的车辆数量，然后可以按照以上模型公式，结合道路长度，进行分数计算。当有数据包到达此路口时，便可以以此分数来判断最佳的路由线路。

3）GyTAR应用从备选路口发回到当前路口的CDP控制信息获取道路车辆数，以此建立连通性模型，相较于从第三方获取以往某时段的平均车流量来说，更具有数据的实时性和可靠性。但其本身也存在的一些缺陷，如图1。

当CDP传送至C2区域时，处于中心位置的V-A更新本区域的车辆数到CDP，然后把自己标志为CDP车辆，当其向右继续行驶并驶离道路时，便会生成一个新的CDP数据包向后传送，这是一个标准的程序过程；但当CDP传送至C1区域时，车辆V-B把本区域的车辆数更新到CDP，但由于自身行驶方向并不是备选路口方向，所以其无法标志自己为CDP车辆，致使最终CDP发送时间间隔偏差较大，对用于车辆密度信息的实时性造成影响。

针对此问题，本文进行了改进：处于每个区域中心范围的车辆只负责更新CDP，不再标志自己为CDP车辆，我们规定在车辆进入一条道路后，通过“hello”信息查看处于道路前方的邻居车辆有无CDP车辆，如果没有则标记自己为CDP车辆，当其到达下个路口时，向后发送CDP进行更新；同时对于路口节点的道路车辆密度信息设置有效时间。

TTL=（信号传输距离 / 道路上车辆平均速度） * α

其中α为可调参数，当TTL过期后，信息将不被采用。改进后，虽然可能会增加一定的CDP数量（按照250m的信号传输距离计算，CDP增加最大值为原来的1倍），但可以有效控制每个CDP之间的发送时间间隔，从而提升连通性模型的准确性和实时性，下章中模拟实验数据可以显示其优越性。

4）本文采用SUMO（Simulation of Urban MObility）设计了两条同样的8车道双向城市道路，假定为道路路由候选，并使用原GyTAR和本文的改进算法进行道路连通性预测计算，根据各自的道路连通性得分选择其中之一，并通过MATLAB仿真得出该道路实时数据包的传输延迟时间，观察其路由选择的对比效果，模拟环境参数如表1。

如图2所示，其中最佳结果为每次皆选取实际延迟时间小的道路而得出的平均延迟时间，最差结果则为相反情况。图中可看出，因为改进算法在CDP发送的时间间隔上相对比较稳定，且道路车辆信息保存时间固定，不会出现过期数据的情况，所以道路延迟时间预测的实时性和准确性较原GyTAR有明显提高，实际数据包延迟时间明显减少。

5）总结：本文分析了基于路口的VANETs路由协议GyTAR的工作机制，指出了其因CDP发送车辆选取不均匀而容易导致的道路连通性预测实时性和准确性不高的缺陷，针对此问题进行了改进，并且通过模拟实验证明此改进算法在道路连通性预测的准确度较原GyTAR有了明显提高。

参考文献：

[1] 邢世宝.基于道路时延和车流量的VANET路由协议研究[D].吉林大学，2015.

[2] 雷亚星，李剑峰. 城市环境下VANET路由协议的研究[J].2011.

[3] 胡畔.城市环境下基于位置的车载自组网路由协议研究[D].武汉理工大学， 2014.

[4] 司桂芳.基于城市环境的车载自组织网络路由协议研究[D].南京邮电大学， 2013.

[5] 柳长青.城市VANET路由协议研究[D].天津大学，2012.

[6] 金晓烨.基于城市环境的车载网络路由机制研究[D].北京邮电大学，2013.

[7] M.Jerbi et al.“An Improved Vehicular Ad Hoc Routing Protocol for City Environments，”IEEE ICC07，pp.3972-79.