混合式实时交通信息的VANETs的地理路由

潘韵，孙兰娟

池州学院数学与计算机科学系，安徽池州247000

1 引言

车辆自组织网络VANETs（Vehicle Ad hoc Networks）作为智能交通的重要组成部分，通过车间通信V 2V（Vehicle to Vehicle communication）以及车辆与路边设施间通信，高效地实现事故预警、辅助驾驶、道路交通信息查询，以及Internet接入服务等多种应用[1]。VANETs广泛应用于事故预警、保障交通安全、交通管理、乘客娱乐，并为用户提供舒适、安全的驾驶环境，使得VANETs在智能交通起着至关重要的作用，有望成为物联网的典型应用之一[1-2]。

相对于传统的移动自组织网络，VANETs具有高动态的拓扑结构、间断性的网络连接、高度不可靠的链路、深度开放的网络等特点。VANETs的这些特点使得传统的路由协议难于直接应用。为此，2000年，Karp[3]提出GPSR（Greedy Perimeter Stateless Routing）协议。GPSR无需复杂的维护路由，仅依据通信双方选择转发节点，开销低。尽管GPSR适用于节点高速运动的场景，但是GPSR寻找的转发节点不是最优解，从而导致路由经常中断，不得不恢复策略，造成数据传输时延增大。研究成果表明，传统的路由协议应用于VANETs时，数据包的成功传输率小于50%，延迟大且延迟抖动剧烈。如何设计有效的路由协议从而保障通信消息的安全、实时、可靠地传递，是VANETs研究的热点问题[4]。

GSR[5]属于基于位置的路由协议，根据地理信息，利用迪杰斯特拉Dijkstra算法计算最短路径，之后采用贪婪转发策略实现数据的转发。然而GSR的不足之处在于：当交通密度很低时，就没有足够的节点转发数据包。在低密度的交通情况下，端与端的连接率低。此外，A-STAR[6]也属基于位置的路由协议。A-STAR考虑了静态交通流量信息，并利用基于锚节点策略，为数据包寻找高连接率的路径。A-STAR将公交巴士作为锚节点。文献[7]也提出基于位置的路由协议GPCR，GPCR在每个十字路口选择一个节点作为协调节点。在数据转发过程中，转发节点采用贪婪策略，并择优选择协调节点作为下一跳转发节点。上述的这些路由协议在路由决策时并没有考虑交通的实时状态信息，这将会增加路由断裂的几率。

文献[8]提出VADD（Vehicle-Assisted Data Delivery）方案。VADD结合车辆的位置以及方向信息，并利用基于数据包传递到目的节点的概率。其主要有三种数据包转发模式：Intersection、Straightway、Destination。当数据包传递到道路交叉口时，就启用Intersection模式，择优选择延迟最小的路段组建路由。当离开道路交叉口时，就启用Straightway模式，并沿道路转发数据包。当数据包传递到目的节点附近时，进入Destination模式。Junichiro[9]提出新的方案，通过预先计算源节点与目的节点可能路由的概率，并基于一定的数学模型。通过计算这些概率，建立一拟用的路由表。

DTSG[10]（Dynamic Time-Stable Geocast）方案。DTSG将网络区域分为：目的区域定义为ZOR（Zone of Relevance）；转发区域为ZOF（Zone of Forwarding）。在ZOR内节点表示数据包的目的节点，而ZOF内的节点为数据包的转发节点。实施DTSG可分两步：首先在ZOR内扩散数据包，再使数据包在预设时长内持久的存在于ZOR中。可动态预设时长，无任何额外的开销。

许多学者也提出利用实时交通信息的路由协议。文献[11]提出优化的贪婪交通流量感知的路由协议GyTAR（Improved Greedy Traffic Aware Routing Protocol）。GyTAR利用实时的道路流量以及道路地图信息选择路由。如果转发节点处于十字路口区域，它将从邻近的十字路口收集道路的实时信息选择下一个转发的十字路口。然而，GyTAR仅从一跳邻居节点收集交通信息，这些信息并不充分。利用不充分的信息难以选择最优的路由。文献[12]提出静态节点辅助适应式路由SADV（Static-Node Assisted Adaptive Routing Protocol）。SADV在节点密度时，通过十字路口部署静态节点收集实时的信息，利用这些信息预测车辆的移动。静态节点在十字路口采取等待策略，直到有高的数据包递交率才转发数据。这种方式可以避免绕路，但是数据包传输时延取决于车辆密度。因此，SADV的性能优劣受到节点密度的影响。

为此，本文提出混合式的感知交通信息路由HTAR。HTAR不部署静态节点，同时利用道路流量以及网络流量信息决策路由。节点广播这些混合式信息。通过共享这些信息，有利于节点选择更优的路由。

2 HTAR

2.1 假设

本文提出的算法基于以下几点假设：

（1）网络中的节点均装有GPS设备，能获取自己准确的位置信息；同时节点都有无线通信设备，任何两个节点在其通信范围内，就能彼此通信。

（2）源节点在向目标节点发送数据前，通过位置服务已获取目标节点、邻居节点的位置信息。

（3）网络中的节点能获取街道信息，包括：（a）道路的拓扑结构；（b）交叉路口的ID、位置；（c）道路ID、长度。

2.2 HTAR基本概念

2.2.1 邻居节点的相关信息

HTAR方案的节点周期性向邻居广播“Hello”消息，以便邻居节点能获取周围节点的实时信息。接收节点依据实时信息，选择最合适的数据转发节点。Hello消息的格式如下所示：

其中，Road ID为此节点所处的道路号，Location（x，y）表示节点所在的位置。A t junction（True or False）代表此节点是否处于在交叉路口。表中的最后一列的内容取决于A t junction的值。如果A t junction是“True”，最后一列存放节点停留于十字路口的时间（Time to Leave Junction，TTLJ），否则的话，就存放Channel load，其表示道路拥堵率。

一旦节点收到来自其他节点的“Hello”消息，将其存放在自己的邻居信息表中，格式如下所示：

2.2.2 交叉功能节点的选取

在每个交叉路口，需选择一个功能节点，作为此交叉路口的信息收集者，负责从邻近道路周期地收集实时交通信息。功能节点主要负责以下三方面的任务：

（1）及时收集邻近道路交通、网络流量信息；

（2）根据所收集的信息，依据算法计算道路的权值；

（3）向邻近交叉路口分发道路的权值数据。

在HTAR方案中，根据节点所处不同的情况，将节点的状态分为四种，分别为：休眠（sleep）、监视（monitor）、竞争（com pete）、发布（spread）。根据不同的输入信息（激励），四种状态可相互转换。

当节点不处于交叉路口，就进入sleep状态。每次节点第一次进入交叉路口，它将sleep状态转变为monitor状态。在monitor状态时，节点设定一个Tm秒的倒数计时器。设置计时器的目的就是监视交叉路口是否存在功能节点。因为功能节点周期地向邻居节点分发更新过的权值信息包W IU（Updated Weight Information），如果在Tm内未收到权值信息包，表明当前没有功能节点。如果在Tm内，节点收到了W IU，则节点仍处于monitor状态并重新设置当前的计数器。如果没有收到，节点进入compete状态。

处于com pete状态的节点需设置Tc倒数计时器与其他节点竞争成为功能节点。Tc由式（1）计算。

所有处于spread状态的节点都是功能节点。它们必须周期性收集邻近交通信息，并向邻居节点广播已更新的权值信息。当功能节点离开交叉路口，它需要从处于交叉路口的节点中选择一个节点继承它的位置，即作为下一轮功能节点。TTLJ可通过式（2）计算：

其中，D(t)表示节点离交叉路口的路程，V(t)表示节点当前速度。如果HTAR能获取其他的一些信息，如交通灯时间，TTLJ的值将更准确。TTLJ值越大，表明节点停留在交叉路口的时间越长。如前所述，处于交叉路口的节点周期地广播含有TTLJ值的Hello消息。当前的功能节点依据TTLJ的值择优选取功能节点的继承者，具有TTLJ最大值的节点，被选中。通过这种方式，HTAR能够降低因更换功能节点的开销。继承节点选定后，节点将离开交叉路口，同时进入sleep状态。继承节点也随之进入spread状态。

四种不同状态的转移如图1所示。

图1 节点状态转移图

2.2.3 功能节点的任务

由上述分析可知，功能节点有三项任务必须完成，分别为汇集交通信息、评估道路权值，以及广播道路权值。

2.2.3.1 汇集交通信息

在HTAR中，功能节点需收集两类交通信息。一类是道路中节点的密度信息，另一类是网络交通拥塞信息，其用道路堵塞率Channel Load表示。通过此值判断道路是否堵塞。

为此，功能节点向邻近的功能节点发送交通信息收集包（Traffic Information Collection，TIC）。在收集信息的开始，HTAR将道路进行分段。将每两个交叉路口间的道路依据通信范围R分段，按式（3）划分：其中，Nseg为道路所分的段数，L为两交叉路口之间的道路长度。如图2为道路划分示意图。

图2 道路划分示意图

在信息收集过程中，每个TIC包尽量传递到每段道路的中心。为此，每次转发时，从邻居信息表中选取离此段中心最近的节点作为转发点。一旦接收节点发现自己是离此段道路中心最近的节点，就将此段道路的节点密度以及道路堵塞信息加入到TIC包中，然后再转发给下一段道路，直到没有下一跳转发TIC包或新的继任功能节点收到此TIC包。如果新的继任功能节点收到TIC包，它将此TIC包复制并发送给源功能节点。原功能节点收到后，将分析交通信息并更新道路的权值。如下描述了TIC的格式：

其中，两列Junction ID分别表示源交叉路口、目的交叉路口；Numbers of Nodes表示某路段的节点的数目；Segment ID表示道路的段数号；Channel Load表示此段道路的堵塞率。

（1）道路密度交通信息

靠近每段中心区域的节点收到TIC数据包，并首先计算邻居节点的数目，然后将此值存入上述TIC格式中的“Number of Nodes”区域。如下显示了由功能节点收到TIC包的示例，其中，A、B表示源交叉路口、目的交叉路口。

（2）网络流量堵塞信息

如前所述，在道路的节点必须周期地广播hello消息，该消息中包含了Channel Load的信息。一旦进入道路，功能节点监视道路情况，计算道路堵塞时间，并计算堵塞率。如式（4）所示：

其中，Tmeasure(n)表示节点n检测路段的时间，Tbusy(n)表示此路段忙的时间。

多个节点一起检测路段忙的时间。整个路段上的CLi由式（5）计算：

其中，i∈Nseg；Ni为此路段i的节点数目；Time Stam p表示产生TIC包时戳；Channel Load表示道路堵塞率。

2.2.3.2 评估道路权值

评估道路权值时，利用Dijkstra算法去计算最短路径。功能节点收到TIC包，就按式（6）计算道路的权值Weiroad：

其中，Li表示路段的长度；C1、C2为两个常数，且C1＞C2；CTth为路段负荷的门限值；Weiroad值越小，路由路径越好。

功能节点计算了每条路段的权值后，将这每条权值存于权值信息表，其格式如下所示：

2.2.3.3 道路权值信息的分发

功能节点利用权值信息更新包（Weight Information Update，W IU）周期性地分发最新的道路权值，格式如下所示：

源节点获取每条路段的权值后，从中选取权值最小的路段作为数据包的转发路途。

3 路由决策过程

定义G=(V，E)：节点逻辑关系的图论表示方法，V、E分别表示点集和边集。

与GSR、A-STAR一样，HTAR利用最短路径算法去计算路由。在路由发现过程中，将交叉路口（junction）看成点V，道路看成边E，每条边均有它自己的权值。对于给定的两个点，HTAR能找出最佳路由。此外，HTAR是实时交通感知路由，因此可根据实时的信息更新权值。

每个源节点在数据开始传输时需建立路由。根据当前所处区域的不同，路由的建立分两种情况。

第一类，节点处于非交叉口。不处于交叉口的节点收到一个数据包时，首先检查这个包目的地，如果这个节点本身不是这个包的目的节点，那么节点根据数据包的目的地，寻求适合下一跳的转发节点。如果能成功找到转发节点，就将数据包传递给转发节点；如果不能找到合适的转发节点，就采用存储缓存，直到能获取下一跳节点。

第二类，节点处于交叉路口。处于交叉路口的节点收到数据包时，同样先查看数据包的目的地，如果自己不是数据包的目的地，就进一步检测这个包是否第一次到达此交叉路口。如果是第一次，立即为此数据包重新计算路由路径并寻求最佳下一跳转发节点。与第一类情况不同的是，处于交叉路口的节点如果不能为数据包找到下一个转发节点，则重新计算路由路径，并依据此路径重新寻找下一跳转发节点。具体的方案流程如图3所示，假定节点ni收到数据包。

图3 HTAR方案流程图

4 仿真以及性能分析

为了评估所提出的路由的VANETs性能，对HTAR以及GSR、GyTAR、SADV进行仿真。选择这两个协议进行对比仿真，主要原因是：GSR是不考虑交通信息的代表协议；GyTAR是利用交通信息辅助路由的代表协议，并支持携带转发技术。采用Network Simulator 2.31作为仿真平台；仿真场景采用TraNS[13]的模型。仿真的具体参数如表1所示。

表1 仿真参数

为了更好地分析HTAR协议的性能，本文分别从数据包传输率（delivery ratio）、平均传递时延（delay）、网络开销（network cost）进行协议分析。数据包传输率是指源节点发送的数据包与被目标节点成功接受到的数据包之比，如式（7）所示。平均传递时延是指数据包从源节点到达目标节点所需要的平均时间长度。网络开销，即在运行协议期间为实现数据包传递功能，网络中所产生的数据包与其传递跳计数的乘积的总和，包括位置服务数据包、交通信息数据包以及路由维护数据包等[14]。

本文针对节点数目为400时，数据包传输率、平均传递时延、网络开销随CBR速率的变化情况进行仿真分析。

图4给出了数据包传输率随CBR速率的变化曲线。

图4 Deliver Ratio随CRB的变化情况

从图4可知，CBR速率的增加，数据包传输率呈下降趋势。同GSR、GyATR相比，HTAR具有较高的数据包传输率。这主要是原因HTAR充分考虑了交通实时信息，转发路径断裂的机率下降，数据包传输率提高，能够达到约0.85。而GSR协议没有充分考虑到车流信息，遇到网络分割时数据包丢失严重，数据包传输率极低。GyTAR协议在数据转发时，考虑到道路上的局部交通信息，其数据包传输率高于GSR，但是由于其只考虑到局部的交通信息，没有整个网络的交通信息，所以数据包传输率低于HTAR。

图5表述了CBR对平均传递时延的的影响情况。三个协议相比，GSR的时延最小，这主要是因为总是由最短的传递路径向目标节点传输数据包。而HTAR、GyATR采用无线转发、存储转发方式，数据包的平均时延相差不大。与GyATR相比，HTAR考虑到全网的交通信息，选择节点密集的道路，充分利用了无线转发功能，其时延低于GyATR。

图5 平均传递时延随CBR的变化情况

如图6所示，随着CBR速率的增加，三种协议的网络开销也随之增加。由于GSR协议简单，复杂度低，其所占用的网络开销最小，增加幅度缓慢。相对GSR，GyATR和HTAR协议较复杂，网络开销也同步增加。在低速时，HTAR的网络开销低于GyATR。

图6 网络开销随CBR的变化情况

5 结束语

基于VANETs的特性，提出适用于VANETs的路由协议HTAR。该协议通过功能节点的设置，获取交通的实时信息。每个交叉路口设置一个功能节点，负责收集实时交通信息。根据车辆的通信范围将道路分成路段，功能节点计算每条路段的权值，并将这些信息向邻居节点以及邻近的交叉路口发布。为了适应VANETs的拓扑结构的动态性，功能节点将节点密度以及每条路段的负荷信息融入交通信息中。因此，节点能选择最佳的转发节点，使路由路径更健壮、更稳固。同时，提出通过设置倒数计时器方案选取功能节点，以减少网络开销。仿真结果表明，HTAR的数据包传输率达到0.85，平均传输时较小，不高于2 s，并且网络开销与同类协议相关，没有明显的增大。

[1]陈辰，韩伟力，王新.VANETS安全技术综述[J].小型微型计算机系统，2011，32（5）：896-904.

[2]M inhas U F，Zhang J，Tran T，et al.Towards expanded trust management for agents in vehicular ad-hoc networks[J].International Journal of Computational Intelligence Theory and Practice，2010，5（1）：3-15.

[3]Karp B，Kung H T.GPSR：greedy perimeter stateless routing for wireless networks[C]//Proceedings of the 6th Annual International Conference on Mobile computing and Networking（Mobi Com’00）.Boston，MA，USA：ACM Library，2000：243-254.

[4]Chen C，Zhang J.A trust modeling framework for message propagation and evaluation in VANETSS[J].International Journal of Computational Intelligence Theory and Practice，2010，5（2）：8-16.

[5]Lochert C.A routing strategy for vehicular Ad hoc networks in city environments[C]//IEEE Intelligent Vehicles Symposium Proceedings，June 2003：156-161.

[6]Seet B.A-STAR：a mobile Ad hoc routing strategy for metropolis vehicular communications[C]//Proceedings of the 3rd International IFIP-TC6 Networking Conference，M ay 2004：989-999.

[7]Lochert C.Geographic routing in city scenarios[J].ACM SIGMOBILE Mobile Computing and Communication Review，2005，9（1）：69-72.

[8]Zhao J，Cao G.VADD：vehicle-assisted data delivery in vehicular ad hoc networks[J].IEEE Transactions on Vehicular Technology，2008，2（5）：123-128.

[9]Junichiro F.A probabilistic protocol for multi-hop routing in VANETs[C]//Proceedings of the IEEE International Conference on Communications Workshops，2009：345-352.

[10]Rahbar H，Naik K，Nayak A.DTSG：dynamic time-stable geocast routing in vehicular Ad hoc networks[C]//Proceedings of the 9th IFIP Annual Mediterranean，2010：1-7.

[11]Jerbi M.An improved vehicular Ad hoc routing protocol for city environments[C]//Proceeding of the IEEE International Conference on Communications，2007：3972-3979.

[12]Ding Y，Wang C，Xiao L.A static-node assisted adaptive routing protocol in vehicular networks[C]//Proceedings of the 4th ACM International Workshop on Vehicular Ad Hoc Networks，2007：59-68.

[13]肖玲，李仁发，罗娟.车载自组网的仿真研究综述[J].系统仿真学报，2009，21（17）：5330-5336.

[14]白翔宇，叶新铭，李军.感知实时车流信息的VANETS路由仿真研究[J].系统仿真学报，2012，24（2）：428-436.