一种基于地理信息的改进GPSR算法

张馨心 石振刚

摘要：针对车载自组织网络（VANET）中基于地理信息的GPSR协议在转发数据包时通信链路不够稳定的问题文章，提出了一种改进的路由算法——GPSR-S算法。该算法根据任一车辆节点在不同时刻的地理坐标，分别计算出它们的运行速度和运动方向，再通过速度和方向计算节点间通信链路的维持时间，兼顾链路稳定性和距离，选出可靠的下一跳。利用网络仿真平台NS-3对GPSR、GPSR-S进行仿真，结果表明GPSR-S算法在数据包传递率、端到端时延方面的性能得到了提升，更适合在车载自组网中应用。

关键词：车载自组织网络  路由算法  GPSR  数据包投递率  端到端时延

中图分类号：TN92         文献标识码：A

An Improved GPSR Algorithm Based on Geographic Information

ZHANG Xinxin  SHI Zhengang

（Shenyang Ligong University， Shenyang， Liaoning Province， 110159 China）

Abstract： This paper proposes an improved routing algorithm—the GPSR-S algorithm aiming at the problem that the GPSR protocol based on geographic information in vehicular ad hoc networks （VANET） is not stable enough for communication links when forwarding data packets. According to the geographical coordinates of any vehicle nodes at different times， the algorithm calculates their running speed and movement direction respectively， then calculates the maintenance time of the communication link among nodes by speed and direction， taking into account the stability and distance of the link， and selects a reliable next hop. The network simulation platform NS-3 is used to simulate GPSR and GPSR-S， and the results show that the performance of GPSR-S algorithm in terms of packet delivery rate and end-to-end delay is improved， which is more suitable for use in the VANET.

Key Words： Vehicular ad hoc network; Routing algorithm; GPSR; Packet delivery rate; End-to-end delay

隨着汽车数量增加，交通问题也日益严重，对人们的生活造成了影响。研究人员开发了智能交通系统（Intelligent Transport System， ITS）[1]以保证道路的利用率。车载自组织网络（Vehicular Ad Hoc Networks，VANET）[2]作为ITS的重要部分，受到了广泛关注。路由协议作为VANET中的重要一环，成为了研究的热点。

针对GPSR协议应用在车载自组网的不足之处，提出了改进的GPSR-S算法。GPSR-S对下一跳节点的选择进行了改进，综合考虑链路质量和距离两个因素的影响选出稳定的下一跳。仿真实验结果表明，改进后的算法，可以提高数据包投递的成功率，减少传输时延。

1 GPSR算法

贪婪周边无状态路由协议（Greedy Perimeter Stateless Routing，GPSR）[3]是典型的基于地理信息的路由协议。GPSR采用信标机制[4]，该算法中的节点会定时发送含有节点编号和位置的hello消息，每个节点的位置都能被得知。GPSR算法共有两种模式：贪婪转发和周边转发[5]。转发数据包时，GPSR首先调用贪婪转发，如图1（a）所示。图中，实线圆表示最大通信范围，黑色小圆表示节点。源节点S根据目的节点D的位置，选择通信范围内离D最近的节点为下一跳，将数据包转发给该节点。当某个节点发现通信范围内没有比自身离D更近的节点时就发生了局部最优，贪婪转发失败，GPSR采用周边转发。发生局部最优的区域称为路由空洞[6]，这时GPSR算法通过右手定则[7]确定下一跳。GPSR的周边转发如图1（b）所示，阴影部分表示路由空洞，S陷入局部最优，通过右手定则确定传输路径为S→A→B→C→D。

由于贪婪规则，所以贪婪转发总是选取离目的节点最近的节点为下一跳，这些节点通常处于转发节点的通信边缘处[8]。在VANET中，车辆高速移动，边缘处的节点很容易驶出转发节点的通信范围，造成通信链路断裂、数据转发失败。

2 改进的GPSR算法

针对上述数据包转发过程中存在链路不稳定的问题，对其进行改进。改进GPSR-S算法不仅采用贪婪方式，还对链路质量加以考虑，选出稳定的下一跳。

车载自组网中的车辆节点周期性地发送数据包，当节点不间断地收到来自同一节点的两个或更多的数据包时，就可以计算出该发送节点的速度和角度，具体的计算公式如下。

式（1）、式（2）中，、分别为节点在上一时刻和当前时刻的坐标。

算法采用链路持续时间来衡量通信链路的质量，链路持续时间越长则代表链路质量越好。通过两个节点的运动速度和方向可以计算出链路持续时间。

假定任意两个车辆节点为M和N，且在当前时刻建立了通信。此时M和N的位置坐标分别为、，通过式（1）和式（2）可计算出M和N的运动速度和方向。此外，还可以计算出此时M和N之间的距离，计算公式如下。

假定一段时间内车辆保持匀速行驶，运动速度和方向不变，车辆M、N的速度大小分别为、，节点的通信范围为，则链路的维持时间可分为以下5种情况。

情况一：车辆M、N同向行驶，前车的速度大于后车，那么M与N之间的链路维持时间为

情况二：车辆M、N同向行驶，前车速度小于后车速度，则M、N之间的链路维持时间为

情况三：车辆M、N同向行驶，两车的速度相同且不变，则M、N之间的通信链路将会一直持续下去，链路维持的时间无穷尽。

情况四：车辆M、N相向行驶，则M、N之间的链路维持时间为

情况五：车辆M与N背向行驶，则车辆M、N之间的链路维持时间为

發送节点的一跳范围内的任一邻居节点与目的节点之间的距离可通过公式（8）计算得出。

（8）

式（8）中，为任一邻居节点的位置，为目的节点的位置坐标。

通过上述计算可以得到发送节点和每个邻居节点间的链路持续时间以及每个邻居节点与目的节点间的距离，设置一个权重函数如下。

（9）

式（9）中，和为系数，且，为权重值。

当数据包被传送至某个节点后，通过式（9）可计算出该节点与每个邻居节点间的权重值，选择权重值最大的邻居节点为下一跳，这样选出来的节点具有稳定性。不断重复此过程，直至将数据包送达目的节点。

3 仿真实验

实验采用NS-3[9]仿真平台对GPSR算法和改进的GPSR-S算法进行性能仿真，对两种算法的性能进行分析比较。

实验的仿真场景设置为1 000 m×1 000 m的区域，节点的通信传输半径为250 m，其他仿真参数的设置如表1所示。

设置实验，分析两种算法在不同节点数下的性能比较。在实验中，将车辆的速度固定为15 m/s，车辆数以20的步长从20逐渐增加到140。

图2是不同车辆数下的GPSR和GPSR-S的分组投递率对比图。由图看出，当车辆数较少时，节点间的通信链路较少，二者的分组投递率较低。当车辆数目增加时，网络连通性增大，二者的分组投递率也有所提升。不同的是，GPSR-S还考虑了链路的可靠性，避免了GPSR通信链路易断裂问题。因此，GPSR-S比GPSR的分组投递率更高。

图3比较了GPSR和GPSR-S在不同车辆数目下的平均端到端时延。从图中可以看出，随着节点数量的增加，二者的平均端到端时延减小。原因是当节点数较少时，算法经常进入周边转发，整体时延较大。随着节点数量增加，转发节点的邻居节点也增多，算法进入周边模式的概率降低，整体的时延减小。而GPSR-S与GPSR相较，时延更低，是因为GPSR-S选择的下一跳节点更加可靠，通信链路不易断裂。

4 结语

针对GPSR算法在车载自组织网络中应用存在的链路不稳定问题，改进后的GPSR-S算法综合考虑链路稳定性和距离，将二者联合作为决定因素选出稳定的下一跳，决定传输路径。仿真结果表明，GPSR-S算法在分组投递率和平均端到端时延方面的表现比GPSR算法均有提高，GPSR-S算法的性能更优于GPSR算法，可以更好地运用在车载自组织网络中。

参考文献

[1] 张乐乐，王丽，肖小玲.我国智能交通系统的发展现状和趋势[J].电脑知识与技术，2021，17（3）：247-249.

[2] 刘文晶，刘巧.IEEE 802.11p车载通信网络架构解析[J].广东通信技术，2022，42（4）：18-21.

[3] 祝经，周新力，宋斌斌，等.无人机自组网GPSR路由协议研究[J].兵器装备工程学报，2021，42（12）：81-86.

[4] 伍龙昶.车联网GPSR路由协议改进及城市交通下的性能仿真[D].武汉：武汉理工大学，2017.

[5] AMINA B， ASMAE B， MOHAMED E. A Novel Greedy Forwarding Mechanism Based on Density， Speed and Direction Parameters for Vanets [J].International Association of Online Engineering，2020，14（8）：196-204.

[6] 温卫，张衡阳.车载自组网切线切换路由空洞处理算法研究[J].江西理工大学学报，2019，40（5）：93-97.

[7] 谷志茹，李敏，龙永红，等.基于GPCR的车辆自组织网络路由优化方法[J].通信学报，2020，41（7）：152-164.

[8] 朱宏輝.车联网中基于地理位置路由协议研究[D].成都：西南交通大学，2020.

[9] MARIJA M， NENAD J. A Framework for Performance Evaluation of VANETs Using NS-3 Simulator[J]. Promet-Traffic&Transportation，2020，32（2）：255-268.