VANET城市场景下一种优化的地理信息路由协议

赵博龙，杨 洁

(中国航空计算技术研究所，陕西 西安710119)

0 引言

车联网 VANETs(Vehicle Ad Hoc Networks)已成为研究热点，车联网的实施有利于提高行驶安全性[1-2]。车辆的快速移动及车辆分布的不均匀性，给VANETs路由协议设计提出了挑战。相比于基于拓扑路由，地理信息路由更适合应用于拓扑动态变化的车联网中，能更好地适应拓扑结构变化，具有简单高效、低负载等特点。因此受到更广泛的关注[3-6]。

地理信息路由常采用贪婪转发策略，其是从邻居节点中选择离目的节点最近的节点作为下一跳转发节点。该策略复杂度低、易实现，适用于动态变化的网络[7]。然而，真实环境中，仅利用邻居节点和目的节点位置信息决策路由的地理信息路由并不具有良好的路由性能。因为，随着源节点与下一跳转发节点间距离的增加，信号衰减和数据包丢失率也随之增加[8-9]，这就降低了数据包传输成功率，并增加了路由开销。

在2000年，B.Karp等人提出基于地理信息路由协议 GPSR（Greedy Perimeter Stateless Routing）[10]。 GPSR 协议实施贪婪转发策略，通过距离值选择下一跳节点，离目标节点最近节点作为下一跳节点。然而，仅采用简单的贪婪转发策略，很容易陷入局部最小化，即路由空洞。

文献[11]提出了基于GPSR的改进协议GPCR。当遭遇局部最小化(空洞)时，采用边界转发，数据包携带节点引用右手规则进行寻找下一跳转发节点。此外，文献[7]提出一种基于感知空洞形状的分段贪婪路由EMCG(Easy Modeling Greedy Routing)协议。EMGR协议采用了空洞边界探测包，通过这些探测包收集位于边界节点的信息，并依据这些信息，获取空洞形状，最后依据形状，寻找最合适的转发节点。然而，该协议需要耗尽过多资源收集边界节点信息。

文献[12]提出了基于在线导航系统的RBVT-R协议。通过一系列高网络连接率的十字路口建立源节点与目的节点间的路径。然而，由于路由决策过程中需要使用实时的交通信息，致使节点能够感知城市地图，增加了复杂度，提高了RBVT-R路由对网络条件的适应能力。

上述的路由协议均在强调如何提高数据包转发率问题，但是这些路由协议并没有考虑到城市环境下，长距离传输数据包的成功与否受多方面因素影响。特别是，这些协议均没有考虑节点间的移动的相对方向以及链路质量。为此，本文提出面向VANETs城市场景下一种优化的地理信息路由协议，记为IGR(Improved geographical)。IGR协议在选择下一跳转发节点时，不再使用贪婪转发策略，而是结合节点的位置、无线链路质量以及节点的移动方向这三方面信息，并将这些信息融合成竞争资本，最后，依据竞争资本选择下一跳转发节点。仿真结果表明，提出的IGR协议能够有效地提高数据包传递率、缩短了端到端传输时延，减少了平均跳数。

1 IGR协议

在动态拓扑网络中，仅基于单一指标选择从源节点至目的节点的路由可能是次优解。众多的因素影响了车辆间无线链路，如车辆行驶方向、距离以及链路质量。当数据包携带车辆需要寻找下一跳转发节点时，该车辆应该依据邻近车辆离目的节点的距离、行驶的相对方向以及链路质量等信息决策路由，进而选择最优的数据包转发节点。为此，提出的IGR协议将距离、行驶相对方向以及链路质量三项信息融合成一个竞争资本函数，源节点就通过竞争资本函数择优选择下一跳转发节点。

1.1 临近率

数据包携带车辆计算邻居车辆的临近率AR(Approaching the destination Ratio)，其反映了邻居车辆离目的节点距离的远近。假定车辆i的临近率ARi定义如式(1)所示。

其中Ds表示源车辆离目的车辆的距离、Di表示车辆i离目的车辆的距离。从式(1)可知，临近率AR反映了距离信息。AR越大，车辆离目的车辆越近，具有成为下一跳数据包转发节点的优先权越大。

1.2 相对方向

不失一般性，可认为两车辆之间要么以相同方向行驶，要么以相反方向行驶，并且车辆行驶方向受限于街道和十字路口。由于车辆行驶方向的两极性，相比于反方向车辆间的路由，处于同方向行驶的车辆间的路由更趋于稳定[13]。

因此，将车辆行驶方向纳入选择下一跳数据包转发的指标，将同方向的行驶车辆给予更高的转发优先权。需要指明的是，同方向不是指两车辆方向夹角为0°，而方向夹角小于预设的值，就认为两车辆同向。下面计算方向夹角。

如图 1所示，设定节点i在t1时刻的位置为(x1，y1)，在t2时刻它移动到了位置(x2，y2)。拥有数据包的节点C的位置是(xC，yC)，目标节点 d 的位置为(xd，yd)。在这种情况下，邻居节点i的移动速度，数据包转发方向vi与节点移动方向之间的切角φi由式(2)和式(3)计算得到。

图1 方向计算示意图

当 0≤φi≤π/2时，节点i与源节点同向行驶，否则逆向行驶，由于安全消息传递的后向性，只需要向同向行驶的后方车辆发送安全消息。因此，定义节点i的方向变量DRi：

除了考虑方向因素之处，在数据转发过程中还需考虑无线信道质量。

1.3 Beacon接收率

假定车辆i，其一跳邻居车辆集为Ni，则车辆i的Beacon接收率 BRR(Beacon Reception Rate)：

其中，表示第k个邻居车辆在RRI时区内所接收到的beacon包的数量；|Ni|表示一跳邻居集内含有的节点数目；T为周期，车辆周期性地发送 beacon包，例如，当T=0.5 s、RRI=7 s，接收了 10个 beacon包，则该车辆的 BRR等于0.714。

1.4 竞争资本函数

其中，Γ为评价函数，SPmax表示评价函数最大时的选择概率，β为变量，其标识了路由指标的最大值 α1、α2、α3为三个指标的权值系统。

当式(7)的导数等于零时，Γi达到最大。因此，β为：

式(7)中各项分别取最大值时，可计算β值。ARmax值可依据车辆无线通信范围以及仿真进行估计，可得ARmax=10，而方向最大值DRmax=1。beacon接收率BRR在0～1间取值，因此 BRRmax=1。SPmax为概率，SPmax=1。

2 性能分析

2.1 仿真模型

利用MATLAB软件以及NS2建立仿真平台，对提出的IGR协议进行仿真，并与GPCR和RBVT-R协议进行比较。主要考查数据包传递率PDR(Packet Delivery Ratio)、端到端传输时延EED(End to end delay)以及跳数HC(Hop Count)三方面的路由性能。

仿真区域选取上海市大小为3 968 m×1 251 m的矩形区域，含有370条道路、124个十字路口。在仿真过程中，利用STRAW(STreet RAndom Way)建立车辆随机移动模型。

在仿真区域内，车辆数从100～350变化。每个车辆产生beacon包的周期为0.5 s，产生的数据包大小为512 B。详细的仿真参数如表1所示。

表1 仿真参数

2.2 仿真结果及分析

本次实验目的在于考查交通密度对IGR协议的性能影响。通过实验，能够观察三个协议应对交通密度的性能。实验中，车辆的速度设为50 km/h，数据包源车辆数为15个，密度数从100～350变化。仿真结果如图2所示。

从图2可知，GPCR协议的PDR性能最差，特别是在低密度区域。这主要是因为GPCR利用贪婪转发策略去选择下一跳数据包转发车辆，即选择离目的车辆最短路径的车辆作为下一跳转发车辆。由于车辆的快速移动，车辆间的链路是非常脆弱的，这就导致转发至目的车辆的数据包非常少。然而，随着车辆密度的增加，GPCR协议向目的节点成功转发的数据包也随之增加。此外，RBVT-R协议在车辆数增加时具有更好的性能，这是由于车辆数增加，网络连接概率随之提高，促进了更多的数据包转发。相比于GPCR、RBVT-R，提出的IGR协议具有较好的性能，因为IGR协议从链路质量、方向以及距离三方面信息选择下一跳转发节点。

图2 数据包传递率随节点数的变化曲线

3个协议的数据包平均传输时延随节点密度变化曲线如图3所示。从图3可知，提出的IGR协议的EED最小。原因在于IGR协议向目的节点传输数据包时选择了最优链路的路径，降低了因链路不稳定而引起的数据包丢失概率。然而，随着车辆密度的增加，时延也随之增加。由于车辆密度的增加，使得IGR协议需要消耗更多时间去决策下一跳数据包转发节点。此外，从图3可知，RBVT-R协议的EED随车辆密度增加而呈下降趋势，原因在于已建立的路由在较长时间内仍保持稳定，避免了频繁建立路由，进而缩短了传输时延。

图3 平均传输时延随节点数的变化曲线

图4描述了传输的平均跳数随车辆密度的变化曲线。与GPCR协议相比，提出的IGR协议在向目的节点传输数据包时，需要更多的跳数，传输路径更长。IGR协议在数据包传递率和平均时延方面优于GPCR协议。

3 总结

图4 平均跳数随节点数的变化曲线

为了满足VANET城市场景下路由协议的性能要求，提出了一种地理信息路由的优化协议。提出的IGR协议在数据包转发过程中，不再考虑传统地理信息路由协议的基于地理位置贪婪转发策略，而是利用源车辆离候选车辆间的相对移动方向、候选车辆离目的车辆间的距离以及beacon接收率三方面信息选择下一跳转发节点。仿真数据证实了IGR协议在降低数据包传输时延，提高数据包传输率方面的优越性。

[1]MISRA S，Venkata Krishna，SARITHA V.LACAV：an energyefficient channel assignment mechanism for vehicular ad hoc networks[J].J.Supercomput.，2012，62(3)：1241-1262.

[2]AKYIDIZ I F，MELODIA T，CHOWDHURY K R.A survey on wireless multimedia sensor networks[J].Comput.Netw.，2007，51(4)：921-960.

[3]CHEN Y，LIN Y.Dir：diagonal-intersection-based routing protocol for vehicular adhoc networks[J].Telecommunication systems，2010，3(5)：1-18.

[4]CHENG P，LEE K，GERLA M.Geodtn+nav：geographic dtn routing with navigator prediction for urban vehicular environments[J].Mobile Networks and Applications，2010，15(1)：61-82.

[5]DJAHEL S，GHAMRI-DOUDANE Y.Arobust congestion control scheme for fast and reliable dissemination of safety messages in vanets[C].In Proceeding of the 2012 IEEE conference wireless communications and networking，2012：2264-2269.

[6]GHAFOOR K，BAKAR K.A novel delay and reliability aware inter vehicle routing protocol[J].Network Protocols and Algorithms，2014，2(2)：66-88.

[7]范敏，谢思佳.基于空洞模型的地理位置路由改进算法研究[J].传感技术学报，2012，25(11)：1556-1561.

[8]LEE K，LEE U，GERLA M.To-go：topology-assist geoopportunistic routing in urban vehicular grids[C].In Proceedings of the 2009 IEEE international conference on wireless on-demand network systems and services，Snowbird，2013：11-18.

[9]YAN G，OLARIU S.A probabilistic analysis of link duration in vehicular ad hoc networks[J].IEEE Transactions on Intelligent Transportation Systems，2012，12(4)：1227-1236.

[10]Ghafoor K Z，Mohammed M A.Routing protocols in vehicular ad hoc networks:Survey and research challenges[J].Network Protocols and Algorithms，2013，5(4)：39-83.

[11]LOCHERT C，MAUVE M，HARTENSTEIN H.Geographic routing in city scenarios[J].Mobile Computing and Communications Review，2015，9(1)：69-72.

[12]NZOUONTA J，RAJGURE N.Vanet routing on city roads using real-time vehicular traffic information[J].IEEE Transactions on Vehicular Technology，2009，58(7)：3609-3626.

[13]徐会彬.关于VANETs关键理论技术研究[D].博士学位论文，2014.

[14]SADIQ A，ABU BAKAR K.A fuzzy logic approach for reducing andover latency in wireless networks[J].Network Protocols and lgorithms，2011，2(4)：61-87.

[15]KAYHAN Z G，JAIME L，ALI S S.Improved geographical routing in vehicular Ad Hoc networks[J].Wireless Pers ommun，2015，80：785-804.