VANETs城市场景下基于自适应时延的Geocast路由协议

李 明，曹建国

(1.长江重庆航道局，重庆 401147；2.华中科技大学 计算机科学与技术学院，湖北 武汉 430074)

VANETs城市场景下基于自适应时延的Geocast路由协议

李 明1，曹建国2

(1.长江重庆航道局，重庆 401147；2.华中科技大学 计算机科学与技术学院，湖北 武汉 430074)

基于广播式的Geocast路由协议能够在特定的地理区域内高效地发布数据。然而，广播模式引起冗余重播，易导致广播风暴问题。另外，由于城市场景下建筑物的影响，现有的多数广播抑制方案难以应用于城市环境。为此，提出面向城市的基于自适应时延的Geocast路由协议UGAD。UGAD采用了基于自适应时延的广播抑制方案，降低发生广播风暴的概率。同时，考虑到交叉路口的地理优势，给位于交叉路口的车辆“优惠”时延，使其具有优先转发数据包权力，从而提高数据包到达率。此外，考虑到城市道路的复杂性，UAGD采用基于交叉路口转发IF和贪婪转发GF两个模式，依据不同的道路情况选择不同的转发模式，从而降低冗余重播，并保持高的数据包到达率。最后，针对城市场景进行仿真，结果表明提出的UGAD具有高的数据包到达率，低的数据包重播率。

车载网；Geocast；广播风暴；贪婪转发；基于交叉路口转发；时延

1 Geocast路由协议与DDT策略

车载网VANETs(Vehicular Ad Hoc Network)中，常需要向某个区域内的所有车辆发布数据[1]。因此，基于广播的数据发布算法广泛应用于VANETs。例如，地域性多播Geocast[2-4]协议。Geocast是一种基于地域位置的，向指定的目的区域内所有节点发布数据包的多播路由协议[5]。为此，Geocast路由协议被广泛应用于车辆间交通信息、紧急事件以及商业广播发布。如图1所示，发生交通事故，第一个发现此事故的车辆(源节点)需要将此消息发布后续车辆，即后续车辆是消息的目的区域。

图1 Geocast路由协议示意图

在Geocast路由协议中，目的区域ZOR(Zone of Relevance)中所有节点是数据包的目的节点。依据数据包传递到ZOR方式的不同，Geocast路由协议可分为基于传统泛洪的Geocast、定向泛洪的Geocast和非泛洪的Geocast[6]。

在基于传统泛洪的Geocast路由协议中，接收到数据包后，节点先判断是否位于目的区域ZOR中，若是则将数据包传递给上层应用，并同时继续广播该数据包，若不是则仅广播该数据包。定向泛洪的Geocast路由协议[7]，是通过特定的转发区域ZOF(Zone of Forwarding)转发数据包，而不是像传统泛洪那样向四周广播数据包。在非泛洪的Geocast路由协议中，源节点利用单播路由机制将数据包传递到ZOF中的某一个节点。该节点接收数据包之后，就在目的区域ZOR进行泛洪，致使ZOF中所有节点均收到该数据包。

在Geocast路由协议中，存在两个区域内数据包传递问题：一是如何将数据包从转发区域ZOF传递给目的区域ZOR；二是如何在目的区域ZOR节点将数据包发布给ZOR内所有节点。在第二区域(ZOR)内，主要采用泛洪机制发布数据包，以提高数据包到达率。针对第一区域(ZOF)，若采用泛洪机制将数据包传递至目标区域，可提高数据包到达率PRR(Packet Reachability Ratio)。PRR越高，表明数据包高效地传递了多个节点，但是，泛洪机制存在数据包冗余重播，易引起广播风暴问题；若采用单播机制，尽管抑制了数据包冗余重播，但是降低了数据包传递到目的区域的效率，特别是在城市场景下，车辆间的通信受到高楼等建筑物的阻挡，仅采用单播机制难以保证高的数据包传递率。

为此，在Geocast路由协议中，一方面要抑制广播风暴，另一方面要提高数据包到达率。抑制广播风暴的目的在于避免网络堵塞以及数据包碰撞。在移动自组织网络MANET(Mobile Ad Hoc Network)，可将广播算法分为4类[8]：泛洪式广播、基于概率式广播、区域广播以及基于邻居信息广播。泛洪式广播就是所有节点均转播消息，这将引用过多的冗余(Redundancy)；基于概率式广播是指消息的接收者依据概率参数决定是否转播消息，但是这种方式依赖随机参数，仍会引用冗余重播。区域广播是指向某特定的范围内转播消息，如基于延时方案的区域广播，其利用距离作为参数，并转换成延时参量。离发送者越远，具有越高的转播优先权。基于邻居信息广播是指消息的接收者利用一跳或二跳邻居节点信息去获取网络拓扑，并选择下一跳的转发节点。比如，在VANETs中，每个车辆周期地发送beacon包，其包含节点ID、位置、速度等信息。消息的接收者接收来自邻居的beacon包，依据所有的beacon包的信息，选择下一跳节点重播消息，而不是采取分布式重播决定。然而，由于车辆高速移动，周期地从beacon包获取的邻居节点信息与实时的邻居信息总是存在差距，从beacon包获取的信息总是滞后的。

文献[9]提出了采用距离-推迟-时间算法DDT(Distance Defer Time)实现抑制广播风暴。在DDT方案中，收到数据包的每个车辆依据离发送者的距离设置等待转发该消息的时延。离发送者越远，时延越短。若在等待转发期间，收到数据包的复本(Duplicated packets)，车辆就取消息等待，也不转发此消息。因为收到数据包的复本，就意味着已有车辆转播了此消息。通过DDT抑制广播风暴，缓解数据包冗余重播，如图2所示。

图2 DDT中数据包转发过程

如图2所示，车辆A、B、C收到来自S的数据包，它们依据在数据包传播方向上距离S的长度设置等待转发时间。由于车辆A在数据包传播方向上离S最远，因此A具有最短的等待时延，依次是B、C。图中的1、2、3表示车辆A、B、C转发的优先级。一旦A转发了数据包，并且B、C收到来自A的数据包的复本，B、C就不再等待，也不再转发该数据包。

DDT策略适用于直路模型(高速公路场景)。然而，在城市场景下，其性能急剧下降，这主要因为城市环境的建筑物阻碍了车辆间的通信，阻碍了车辆间的直接通信，这直接降低了车辆间信息交互的效率[10]，如图3所示。

图3 城市环境中障碍物的影响

如图3所示，尽管A、C在车辆S的通信范围，但是由于建筑物存在，使得S无法向A、C直接传递数据包。城市环境中的障碍物阻碍了一跳通信，使得DDT方案无法直接应用于城市环境。

为此，考虑城市场景的特点，提出面向城市场景的基于自适应时延的Geocast路由协议UGAD(Urban Geocast based on Adaptive Delay)。UGAD采用基于交叉路口、贪婪两种转发模式。在基于交叉路口转发IF(Intersection based forwarding )模式中， 位于交叉路口的节点具有优先转发数据包权，即短的等待转发数据时间。IF模式利用交叉路口的地理优势(不失一般性，交叉路口车辆多，转发数据包容易)，提高数据包到达率。使用贪婪转发GF (Greedy Forwarding) 模式，目的是降低冗余重播。UGAD利用发送节点与接收者、目标区域ZOR位置，计算角度，通过这个角度值对两种模型进行切换。

2 UGAD方案

UGAD采用自适应时延机制，从而提高数据包到达率。考虑到城市环境的特点，给位于交叉路口的车辆分配优先转发权，提高了交叉路口广播的机会。同时，UGAD使用两个不同的转发模式，依据不同的环境，选用不同的转发模式，从而降低数据包冗余重播，同时保证数据包到达率。

2.1 基于交叉路口的机制

考虑到交叉路口特殊区域位置，不失一般性，交叉路口区域车辆较多，并且无障碍物，车辆间能够直接通信，如图4所示。处于交叉路口的车辆S，能够向周围车辆A、B、C直接发布数据包，不会出现图3情况。为此，应充分利用交叉路口的地理优势，使得位于交叉路口的车辆具有数据包优先转发权。

图4 交叉路口的转发

此外，由于交叉路口车辆较多，为了提高数据包到达率，使位于交叉路口的车辆具有优先转发权。

2.2 假设条件

UGAD假定每个车辆通过GPS系统知道交叉路口的位置以及自己的坐标位置。Geocast 的目的区域ZOR表示以p(x,y)为中心，r为半径的圆。源节点发送数据包，其包含ZOR的信息，发送节点的位置信息。

此外，在UGAD内，定义转发区域ZOF：比源节点S发离目的区域ZOR更近的区域。

在城市环境中，依据路边建筑物的阴影衰弱可将道路拓扑分割为直线道路和交叉路口。具体而言，两个交叉路口之间的直线道路区域为一个路段，如交叉路口Ii和Ij之间的直线道路区域rij。

2.3 数据包的处理过程

假定源节点S发送数据包M，节点i收到数据包M，并决定是否转发数据包M。为此，首先节点i确认自己是否位于转发区域ZOF内，如果在，节点i就有机会转发数据包M，进而设置时延。如果不在，节点i就丢去数据包M，因为位于转发区域ZOF外的节点不需要转发数据包M。另外，节点i通过GPS确认自己的位置，同时从数据包M提取源节点S、目的区域ZOR的位置，从而保证节点i知道是否位于转发区域ZOF内，具体过程如图5所示。转发区域ZOF的车辆，自行计算时延，一旦时延结束，就转发数据包。若在等待期间，收到数据包的复本，车辆将中断等待，并取消转发数据包的安排。通过这种模式，抑制数据包冗余重播。

图5 处理数据包的流程图

2.4 时延的计算

为了满足Geocast的性能要求，UGAD采用两个不同的转发模式，即贪婪转发和基于交叉路口转发。车辆依据不同的模式，计算时延。

1) 贪婪转发GF模式

GF模式的目的在于最大化每一跳传播增益，同时最小化冗余数据包问题。在GF模式中，节点i接收来自源节点j的数据包M，节点i依据式(1)计算时延。

(1)

2) 交叉路口转发IF模式

IF模式的目的在于提高交叉路口数据包转发的机会，从而增加数据到达率。在这种模式下，位于交叉路口的车辆具有“优惠”的时延，使得位于交叉路口的车辆比其他车辆具有优先转发数据包的权力。在IF模式中，节点i接收来自源节点j的数据包M，节点i依据式(2)计算时延。

(2)

从式(2)可知，在IF模式下，位于交叉路口的车辆具有“优惠”的时延，离发送者越远，退让时间越短。通过IF模式，提高了数据包到达率。因此，当要求高数据包到达率，而不考虑冗余重播时，可采用IF模式。图6显示了IF模式的数据包转发示例。

如图6所示，源节点S发送数据包M，数据包从左向右传输，邻居节点A、B、C、D、E、F均收到数据包M，其中F、C、B位于交叉路口，A、D、E位于非交叉路口。依据式(2)，F、C、B获取优惠退让时间，具有优先转发数据包M的权力。同时，由于B离S最远，其退让时间最短，因此，B最先转发数据包M。当收到来自B的数据包M的复本，A、C、D、E、F就取消等待。

2.5 转发模式的选择

转发模式的选择依赖于转发节点至源节点的向量与转发节点至目的区域的向量之间夹角。如果转发节点有一维路径(One-dimensional Path)到达目的区域ZOR，就启用贪婪转发GF模式，否则，就启用交叉路口IF模式，使得位于交叉路口的车辆具有数据包的优先转发权。可通过计算源节点与转发节点的连线和转发节点与目标区域连线的夹角，表示这两种情况差异，如图7所示。

图7 两个向量的夹角

一旦收到来自节点A的数据包，节点B从数据包提取A以及目的区域的中心点位置，并计算BA与BC的夹角θ的值，即

θ=arccos(BA·BC)

(3)

定义门限值α。通过cosθ与α进行比较，从而决定选用不同的转发模式，并用格状的道路拓扑表示城市场景。当接收到数据包，节点i确认位置。如果位于目的区域内，就选用IF模式。因为目的区域内，通过优先让交叉路口车辆转发数据包，可提高数据包的到达率；反之，就计算夹角θ，并将cosθ与α比较。如果小于α，就选择IF模式，否则就采用贪婪转发GF模式，算法流程图如图8所示。

3 性能仿真

3.1 仿真模型以及参数

图8 转发模式的选择算法

图9 仿真场景

参数值仿真平台Scenargie16数据包大小500byte通信协议80211p调制制式OFDM(QPSK1/2)传输功率20dBm带宽10MHz传输率60Mbit/s传播模型ITU-RP1411

表2描述了车辆通信的参数，包括车辆移动模型、车辆密度以及速度等参数信息。

表2 车辆通信参数

3.2 性能参数

为了充分地评估提出的UGAD算法性能，将GAD与定向泛洪DF(Directed Flooding)、结合DDT的DF方案(DDT+DF)一起仿真，并进行比较。DF方案属于Geocast路由协议，但是其没有采取广播抑制机制。而DDT+DF方案结合DF，并运用DDT机制抑制广播。从下列两个指标分析方案的性能：

2)数据包重播率(packet rebroadcast ratio)，数据包重播率越高，表明数据包冗余重播越严重，发生广播风暴的概率越高。

3.3 仿真结果分析

1) GAD与DF、DF+DDT相比较

图10显示了在目标区域ZOR中3个方案的NVP-ZOF。NVP-ZOF的值越高，表明数据包传递率越高。

图10 NVP-ZOF随车辆密度的变化曲线

如图10所示，与DF、DF+DDT相比，UGAD具有最高的NVP-ZOF，DF的NVP-ZOF最低。这主要是因为DF方案中的转发区域内所有车辆都转发数据包，引起数据包碰撞，降低了数据包传递率。而UGAD采用了基于退避时间的广播抑制算法，同时，将位于交叉路口的车辆给予优先转发权，提高数据包到达率。与DF相比，DF+DDT具有较好的NVP-ZOF性能，原因在于DF+DDT采用DDT的广播抑制机制。DF、DF+DDT以及UGAD的数据包重播率如图11所示。数据包重播率越高，发生广播风暴概率越高。从图11可知，DF方案存在很严重的风暴，这主要是因为DF没有采用广播抑制机制。而UGAD和DF+DDT通过广播抑制机制将数据包重播率控于0.1之内，有效地解决了广播风暴问题。

图11 数据包重播率随车辆密度的变化曲线

2)GAD比较

图12描述了门限值a对UGAD的到NVP-ZOF的性能影响，在UGAD中，若a=1.0，那么位于交叉路口的车辆总是使用IF模式。从图12可知，在低车辆密度情况下，即5～25 Vehicle/km，a为0.3、0.5、0.7、1.0下的NVP-ZOF没有什么变化。然而当车辆密度大于30 Vehicle/km，a值越大，NVP-ZOF越大。不过，在a=0.7变为1.0时，NVP-ZOF变化不大。这也说明，没有必要在所有的交叉路口重播数据包。如图13所示，当门限值a较小时，比如0.3或0.5，UGAD具有非常低的数据包重播率，这主要是因为多数车辆采用了贪婪转发GF模式。而与a=1.0相比，a=0.7的数据包重播率性能较好。

图12 UGAD的NVP-ZOF随车辆密度的变化曲线

4 总结

针对Geocast路由协议，提出面向城市场景的自适应时延的Geocast协议UGAD。UGAD的目的在于提高数据包到达率，同时减少冗余重播的数据包。为此，UGAD采用基于时延的交叉路口转发IF以及贪婪转发GF两个模式，并依据源节点、数据包接收节点以及目标区域ZOR所在位置的不同，进行IF与GF模式的转换，从而满足不同的道路要求。在UGAD中，给位于交叉路口的车辆优先转发数据包权限，提高数据包到达率。仿真结果表明，UGAD在目的区域内具有高的数据包到达率，同时保持低的冗余重播性能。

图13 数据包重播率随车辆密度的变化曲线

[1]CHEN W，GUHA R K，KWON T，et al. A survey and challenges in routing and data dissemination in vehicular ad-hoc networks[C]//Proc.IEEE ICVES 2008.[S.l.]：IEEE Press，2008： 328-333.

[2] MAIHOFER C. A survey of geocast routing protocols[J]. IEEE Communications Surveys and Tutorials， 2004，6(2)：32-42.

[3]于海宁，张宏莉.VANETs路由协议的研究进展[J].电子学报，2011，39(12)：2868-2880.

[4]彭沙婴，林亚平，李超. 一种适用于稀疏无线网的定向Geocast路由协议[J].计算机工程与科学，2010，28(5)：8-13.

[5]Maihoer C.A survey of geocast routing protocols[J].IEEE Communications Surveys & Tutorials，2004，6(2)：32-42.

[6]李元振，廖建新，李彤红，等.城市场景车载Ad Hoc网络竞争转发关键参数分析[J].电子学报，2011，38(5)：1154-1158.

[7]KO Y B，VAIDYA N H. Flooding-based geocasting protocols for mobile ad hoc networks[J]. Mobile Networks and Applications， 2012，7(6)：471-480.

[8]WILLIAMS B，CAMP T. Comparison of broadcasting techniques for mobile ad hoc networks[C]//Proc. ACM MobiHoc ’10. Switzerland：[s.n.]，2010：194-205.

[9]BACHIR A，BENSLIMANE A. A multicast protocol in ad hoc networks inter-vehicle geocast[C]//Proc. IEEE VTC 2003. [S.l.]：IEEE Press，2003：2456-2460.

[10]FLEURY M，QADRI N N，GHANBARI M. Improving propagation modeling in urban environments for vehicular ad hoc networks[J]. IEEE Trans. Intelligent Transportation Systems， 2011，12(3)：705-716.

[11]OHWADA Y，MAENO T，KANEDA S，et al. Realistic ITS simulation with scenargie simulator[C]//Proc. IPSJ DICOMO. Turku：[s.n.]，2008：233-234.

Adaptive Delay-based Geocast Protocol in Urban VANETs

LI Ming1, CAO Jianguo2

(1.ChangjiangChongqingWaterwayBureau,Chongqing401147,China; 2.SchooleofComputerScience&Technology，HuazhongUniversityofScienceandTechnology，Wuhan430074,China)

The broadcast-based geocast enables efficient data dissemination to vehicles within a given geographical region, but when dealing with broadcast, unnecessary retransmissions must be suppressed by controlling the packet forwarding to avoid the broadcast storm problem. However, most of existing broadcast suppression methods do not work in urban environments since buildings block the communication between two vehicles. In this paper, Urban Geocast based on Adaptive Delay (UGAD) protocol is proposed which adopts delay-based broadcast suppression scheme for urban environments. UGAD makes vehicles at intersections rebroadcast quickly by assigning them preferential delay values. Furthermore, vehicles use two different forwarding modes as parameters in order to fulfill the requirements of geocast. This develops the packet arrival ratio within a given geocast region, while reducing redundant rebroadcasts. Simulation results in an urban scenario show that UGAD achieves high packet arrival ratio as well as low packet rebroadcast ratio compared with existing methods.

VANETs; Geocast; broadcast storm; greedy forwarding; intersection forwarding; delay

�域内收数据包的车辆NVP-ZOF(Number of vehicles

the Packet within the Given ZOF)，NVP-ZOF越高，表明数据包到达率越高。

TP393

A

10.16280/j.videoe.2015.05.023

2014-07-11

【本文献信息】李明，曹建国.VANETs城市场景下基于自适应时延的Geocast路由协议[J].电视技术,2015，39(5).

李 明(1981— )，硕士，工程师，主研智能交通，无线传感器网络；

曹建国(1985— )，博士研究生，主研集群与网格计算、分布式软件性能评估、对等计算、语义网。

责任编辑：闫雯雯