车载自组织网络RBVT-R协议的改进*

陈远龙，葛剑飞，刘南杰，赵海涛

（1.南京邮电大学通信与信息工程学院 南京 210003；

2.南京邮电大学网络基因工程研究所

南京 210003；3.国家电网上海市电力公司信息通信公司 上海 200122）

1 引言

车载自组织网络 （vehicular Ad Hoc network，VANET）是指道路上车辆间、车辆与固定接入点之间相互通信组成的开放移动Ad Hoc网络，可以实现事故告警、辅助驾驶、道路交通信息查询和Internet信息服务等应用[1]。VANET中节点移动快、网络拓扑变化迅速、车辆节点进出频繁以及车辆节点因紧急情况可能发生大量聚集等特点[2]，使得基于拓扑的路由协议[3,4]性能大大降低，而城市环境下，VANET中节点的移动轨迹受道路布局限制，并且通过GPS以及电子地图等可以很方便地获得车辆的位置和速度等信息，所以使得基于地理位置的路由协议[5～7]更适合VANET。本文将重点介绍VANET中的一种城市环境下的地理路由（reactivemode of road-based using vehicular traffic routing，RBVT-R[6]）协议，并针对该协议在路由建立及分组转发模式上的缺陷，提出改进策略，以提升RBVT-R协议在分组交付率和端到端平均时延等方面的性能。

2 现有RBVT-R协议

RBVT-R协议是一种城市环境下基于实时路况信息的反应式地理路由协议。当源节点向目的节点发送数据时，要先寻找路由，建立数据分组的传输路径。与锚路由机制[8]类似，源节点与目的节点之间建立的路由是数据分组传输所需经过的所有道路交叉口组成的序列。RBVT-R协议的路由建立过程包括路由发现和路由回复两个步骤，如图1所示，具体流程如下。

（1）源节点产生一个 RD（route discovery，路由发现）分组，该分组的头部包含源节点的名称和位置信息、目的节点的名称。因为目的节点不在源节点的传输范围内，所以RD分组的头部不包含目的节点的位置信息。

（2）从源节点开始，各中间节点在其传输范围内依次通过改进的洪泛机制[9]广播该RD分组，即当一个中间节点收到上一跳转发节点发送的RD分组后，它不会立刻转发该分组，而是等待一段时间，当等待时间结束，且在同一路段上没有其他离上一跳转发节点更远的节点转发该RD分组时，该中间节点才转发此RD分组，如图1（a）所示。当RD分组经过一个路口时，会将该路口的信息加入到RD分组的头部。此洪泛过程重复进行，直到RD分组达目的节点。

（3）当目的节点接收到RD分组后，按RD分组头部的路口序列信息，原路返回一个RR（route reply，路由回复）分组。当源节点接收到RR分组后，则路由建立成功。如图 1(b)所示，建立的路由为：I1-I6-I7-I4-I5-I8。

当路由成功建立之后，源节点就开始向目的节点发送数据。此时数据分组是按照建立的路口序列的顺序依次进行转发。在相邻两个路口的一个路段上，数据分组的转发采用改进的地理路由机制，即每次都选择传输范围内，距离下一个目标路口最近的节点进行转发。

图1 RBVT-R协议的路由建立过程

3 RBVT-R协议的改进

虽然RBVT-R协议采用改进的洪泛机制建立路由，并且通过改进的地理转发机制转发数据分组，使得路由性能在一定程度上得到了改进，但是该路由协议也存在一些问题，主要包括以下两方面。

·虽然RBVT-R协议在路由建立过程中采用了改进的洪泛机制，能在一定程度上解决广播风暴问题，但是该机制在路由发现过程中没有考虑到道路车辆密度对分组传输的影响，使得建立的路由稳定性不高，容易发生数据分组传输时延大，甚至分组丢失等情况。

·RBVT-R协议在相邻两个路口之间转发数据分组时，当前携带分组的节点选择的是其传输范围内距离下一个目标路口最近的节点作为下一跳转发节点，这种转发方式没有考虑到车辆行驶方向和数据分组的转发方向 （即数据分组到下一个路口的指向）之间的关系，有可能会导致分组在同一路段上反复传输，增加分组传输的时延。

根据RBVT-R协议中存在的问题，提出了一种改进算法。该算法包括两个部分，分别是对路由建立过程的改进和对数据分组传输过程的改进。

3.1 路由建立过程的改进

针对RBVT-R协议在路由发现过程中，其改进的洪泛机制没有考虑到道路车辆密度对路由稳定性影响的问题，在改进的算法中提出了一种逐段式道路车辆密度自主估算方法，并将估算出的道路车辆密度用于改善路由发现过程中的洪泛机制。

3.1.1 逐段式道路车辆密度自主估算方法

如图2所示，在一个路段上，当前的分组转发节点为ni，下一跳转发节点为nj，根据当前两个节点的邻居节点的数量以及它们之间的距离，估算这两个节点所在区域一跳范围内的路段的车辆密度，计算式如下：

其中，Nij=Ni∪Nj是两个节点 ni和 nj的邻居节点的总数，它不是邻居节点数的单纯相加，因为节点ni和nj互为邻居节点，它们之间存在共同邻居节点，如图2中三角形节点所示，Nij对共同的邻居节点只添加一次；dij是节点ni和nj之间的距离，R是无线传输半径。2R是因为无线信号是全方位传播的，因此其邻居节点分布也是全方位的。

3.1.2 RBVT-R协议洪泛机制的改进

在RBVT-R协议采用的改进洪泛机制中，中间节点在收到RD分组后会等待一段时间，直到等待时间结束才进行判断，决定是否转发该RD分组，等待时间的计算如式（2）所示：

其中，dmin=min{d,Range}，d是RD分组的接收节点与发送节点之间的距离，Range是无线传输范围，MaxWT是最大等待时间。

但是，这个改进洪泛机制只考虑了RD分组接收节点和发送节点之间的距离，没有考虑到两节点所在区域一跳范围内的车辆密度，本质上还是一种贪婪转发策略，因此存在频繁发生局部最大的问题。针对这个问题，下面结合自主获取的道路车辆密度对此等待函数进行了改进。

通过GPS获得RD分组发送节点ni和接收节点nj之间的距离dij，根据式（1）获得两个节点之间的道路车辆密度ρij。根据参考文献[10]中的多标准映射函数，可以得到包含距离和车辆密度这两个参数的等待函数计算式：

3.2 数据分组传输过程的改进

当路由成功建立之后，源节点开始向目的节点发送数据，此时它会把建立的路口序列保存到数据分组的头部，数据分组就按照这个序列进行转发。分组从源节点到目的节点的转发过程实质上就是按照建立的路口序列中的路口顺序，从一个路口转发到下一个路口，不断重复直到到达目的节点。

针对RBVT-R协议中数据分组在同一路段反复传输的问题，在改进的算法中提出了一种基于方向和位置预测的分组转发方法。该方法需要考虑车辆节点之间链路的有效持续时间并比较各个节点的转发优先权值，下面首先分析了上述两个内容，然后在此基础上提出了基于方向和位置的分组转发方法的完整方案。

3.2.1 链路有效持续时间

车辆之间相对方向关系有：同向行驶（其中同向行驶根据前后车辆的车速大小还分为赶超和落后两种情况，分别如图3、图4所示），相向行驶如图5所示，背向行驶如图6所示。上述4种情况下，车辆之间的链路有效持续时间分别如式（4）～式（7）所示。

同向行驶（赶超）：

同向行驶（落后）：

相向行驶：

图3 车辆A赶超车辆B的相对位置关系

图4 车辆B逐渐远离车辆A的相对位置关系

图5 A、B相向行驶的相对位置关系

图6 A、B背向行驶的相对位置关系

背向行驶：

其中，VA、VB分别为节点 A和 B的行驶速度，R为节点的传输半径，dAB为节点A和B之间的相对距离。由以上式子可以看到，同向运行的车辆节点之间的链路有效时间是最长的，因此在路由选择过程中应首先考虑在同向车辆中选择下一跳转发节点，这样可以选择更加稳定的路径，提高路由协议的性能。

3.2.2 节点转发优先权值计算

假设，当前携带数据分组的节点为S，待选的下一跳转发节点为A。首先，根据节点S与A之间的相对关系，选择对应的链路有效持续时间计算公式计算lifetimeSA；然后，采用式（8）预测经过Δt时间后节点A的位置：

其中，(xA,yA)为节点A的当前位置，(vAx,vAy)为A的速度，(xA′,yA′)为经过 Δt时间后节点 A 的位置。

通过地图获得下一个将要到达的路口Ii的位置(xIi,yIi)，节点A在经过Δt时间后与路口Ii之间的距离DAIi为：

根据链路有效持续时间lifetimeSA以及节点A经过Δt时间后与下一个路口Ii的距离DAIi，计算节点A的优先转发权值为：

其中，MaxLifetime是文中设定的一个链路时间的上限值，用来约束在车辆同向行驶且速度很相近的情况下，链路时间无限大的情况，lifetimeSA不能超过该上限值；Dp=DAIi/DSIi代表了待选节点A距离目标路口的远近程度，其中DSIi为节点S到目标路口Ii的距离，Dp越小代表A在经过时间Δt后距离路口Ii越近；α、β分别是链路有效持续时间和节点A到路口距离的加权值，且α+β=1，它们的取值大小代表了各参数对计算结果的影响程度，根据节点运动方向和分组转发方向之间的关系不同，α、β的取值也不同。

3.2.3 基于方向和位置预测的分组转发

通过前面的分析，下面提出一种基于方向和位置预测的分组转发方案，具体的分组转发过程如下。

（1）携带数据分组的节点S在选择下一跳转发节点时，首先根据邻居列表中邻居节点的位置判断在分组转发方向上是否有可转发的节点，也就是在S和下一个路口之间是否有节点，若有，则进行下一步，否则就由节点S暂时携带该数据分组，等待可转发车辆的出现。

（2）首先选择和分组转发方向相同的节点，若没有，则再选择反方向上的节点，然后根据邻居列表中邻居节点的速度大小和方向等信息，计算S和它们之间链路的有效持续时间和这些节点在Δt时间后的位置，根据式（9）得到这些邻居节点到下一个路口Ii的距离，再计算各节点的转发优先权值。

（3）节点S选择优先权值最大的节点转发分组。

4 仿真分析

采用基于VanetMobisim和NS-2的仿真平台。使用VanetMobisim进行车辆移动模型的模拟，并在NS-2上实现了对RBVT-R协议的改进，将改进后的路由协议叫作IRBVT-R（improved RBVT-R）。

车辆节点的移动模型采用VanetMobisim中带有路口管理的智能驾驶者模型 （intelligent driver model with intersectionmanagement，IDM-IM）。采用南京市新街口附近2 000m范围内的道路布局作为仿真场景，详细的仿真参数见表1，所有道路交叉口都设有红绿灯。仿真结果如图7、图8所示。

表1 仿真参数

从图7、图8中可以看出，随着车辆节点数的增加，RBVT-R和IRBVT-R两个协议的分组交付率都增大，并且端到端平均时延都减小。这是因为这两个协议都结合了实时的道路车辆信息，在车辆节点数很少时，道路车辆密度小，节点的可连接性差，分组在转发时会经常因找不到下一跳转发节点而被暂时携带，甚至被丢弃，从而导致端到端平均时延大，且分组交付率低；随着车辆节点数的增加，道路车辆密度逐渐增大，节点的可连接性提高，使得分组能被及时可靠地转发，从而提高了分组交付率，并减小了端到端平均时延。

从图7、图8中还可以看出，IRBVT-R协议在分组交付率和端到端平均时延这两个指标上，其性能都要优于RBVT-R协议。这是因为IRBVT-R协议在路由建立阶段考虑了道路的车辆密度，选择车辆密度大的路段作为分组传输的路径，提高了所建路由的稳定性，并且在分组传输阶段，考虑了车辆行驶方向与分组转发方向的关系，优先选择与分组转发方向相同且转发优先权值最大的车辆作为下一跳转发节点，减小了分组在同一路段重复传输的概率，从而减小了端到端平均时延，并提高了分组交付率。

5 结束语

VANET是由车辆节点组成的Ad Hoc网络。VANET路由协议的最大挑战就在于车辆节点的移动导致网络拓扑的频繁变化以及城市环境下节点的移动受道路布局的限制导致节点分布不均匀。本文在现有的RBVT-R协议的基础上，提出了一种改进的IRBVT-R协议，该协议在路由建立阶段考虑了道路的车辆密度，并且在分组传输阶段还考虑了车辆行驶方向与分组转发方向的关系，提高了分组传输的可靠性。仿真结果表明，IRBVT-R协议在分组交付率和端到端平均时延等方面，其性能都要优于RBVT-R协议。

1 胡云斌,夏玮玮,宋铁成等.一种应用于VANET的改进GPSR路由协议.2009通信理论与技术新发展——第十四届全国青年通信学术会议论文集,大连，中国，2009

2 Toor Y,Muhlethaler P,Laoriti A.Vehicle Ad Hoc networks:applications and related technical issues.IEEE Communications Surveys&Tutorials,2008,10(3):74～88

3 Pei G,Gerla M,Chen T W.Fisheye state routing:a routing scheme for Ad Hoc wireless networks.Proceedings of 2000 IEEE International Conference on ICC,New Orleans,USA,2000:70～74

4 Das S R,Belding-royer E M,Perkins C E.Ad Hoc on-demand distance vector (AODV)routing.Proceedings of WMCSA’99,New Orleans,USA,2003

5 Karp B,Kung T H.GPSR:greedy perimeter stateless routing for wireless networks.Proceedings of the 6th annual International Conference on Mobile Computing and Networking(MOBICOM’00),Boston,USA,2000:243～254

6 Nzouonta J,Rajgure N,Wang Guiling.VANET routing on city roads using real-time vehicular traffic information.IEEE Transactions on Vehicular Technology,2009,58(7):3609～3626

7 Namboodiri V,Gao L X.Prediction-based routing for Vehicular Ad Hoc networks.IEEE Transactions on Vehicular Technology,2007,56(4):2332～2345

8 Lochert C,Mauve M,Hartenstein H,et al.Geographic routing in city scenarios.ACM SIGMOBILE Mobile Computing and Communications Review,2005,9(1):69～72

9 Li D,Huang H Y,Li X,et al.A distance-based directional broadcast protocol for urban vehicular Ad Hoc network.Proceedings of IEEEWiCOM,Shanghai,China,2007:19～24

10 Egoh K,De S.A multicriteria receiverside relay election approach in wireless Ad Hoc networks.Proceedings of MILCOM,Washington DC,USA,2006:1～7