一种基于地理信息的改进GPSR算法_张馨心.pdf

信 息 与 智 能 2023 NO.8 SCIENCE&TECHNOLOGY INFORMATION科技资讯SCIENCE&TECHNOLOGY INFORMATION科技资讯一种基于地理信息的改进GPSR算法张馨心 石振刚(沈阳理工大学 辽宁沈阳 110159)摘要：针对车载自组织网络（VANET）中基于地理信息的GPSR协议在转发数据包时通信链路不够稳定的问题，文章提出了一种改进的路由算法GPSR-S算法。该算法根据任一车辆节点在不同时刻的地理坐标，分别计算出它们的运行速度和运动方向，再通过速度和方向计算节点间通信链路的维持时间，兼顾链路稳定性和距离，选出可靠的下一跳。利用网络仿真平台 NS-3 对 GPSR、GPSR-S 进行仿真，结果表明，GPSR-S算法在数据包传递率、端到端时延方面的性能得到了提升，更适合在车载自组网中应用。关键词：车载自组织网络 路由算法 GPSR 数据包投递率 端到端时延中图分类号：TN92文献标识码：A 文章编号：1672-3791(2023)08-0009-04An Improved GPSR Algorithm Based on Geographic InformationZHANG Xinxin SHI Zhengang(Shenyang Ligong University,Shenyang,Liaoning Province,110159 China)Abstract:This paper proposes an improved routing algorithmthe 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算法1.1 GPSR简介贪婪周边无状态路由协议（Greedy Perimeter Stateless Routing，GPSR）3是典型的基于地理信息的路由协议。GPSR采用信标机制4，该算法中的节点会定时发送含有节点编号和位置的hello消息，每个节点的位置DOI：10.16661/ki.1672-3791.2209-5042-1999作者简介：张馨心（1998），女，硕士，研究方向为无线通信技术及应用。石振刚（1971），男，博士，副教授，研究方向为无线通信系统。9 2023 NO.8科技资讯SCIENCE&TECHNOLOGY INFORMATION 信 息 与 智 能SCIENCE&TECHNOLOGY INFORMATION科技资讯都能被得知。GPSR算法共有两种模式：贪婪转发和周边转发5。转发数据包时，GPSR首先调用贪婪转发，如图1（a）所示。图中，实线圆表示最大通信范围，黑色小圆表示节点。源节点S根据目的节点D的位置，选择通信范围内离D最近的节点为下一跳，将数据包转发给该节点。当某个节点发现通信范围内没有比自身离D更近的节点时就发生了局部最优，贪婪转发失败，GPSR采用周边转发。发生局部最优的区域称为路由空洞6，这时GPSR算法通过右手定则7确定下一跳。GPSR的周边转发如图1（b）所示，阴影部分表示路由空洞，S陷入局部最优，通过右手定则确定传输路径为SABCD。1.2 GPSR算法的不足由于贪婪规则，所以贪婪转发总是选取离目的节点最近的节点为下一跳，这些节点通常处于转发节点的通信边缘处8。在VANET中，车辆高速移动，边缘处的节点很容易驶出转发节点的通信范围，造成通信链路断裂、数据转发失败。2 改进的GPSR算法针对上述数据包转发过程中存在链路不稳定的问题，对其进行改进。改进GPSR-S算法不仅采用贪婪方式，还对链路质量加以考虑，选出稳定的下一跳。2.1 节点的运动速度和方向车载自组网中的车辆节点周期性地发送数据包，当节点不间断地收到来自同一节点的两个或更多的数据包时，就可以计算出该发送节点i的速度Vi和角度i，具体的计算公式如下。Vi=()Xi2-Xi12-()Yi2-Yi12()ti2-ti1（1）i=tan-1(Yi2-Yi1Xi2-Xi1)（2）式（1）、式（2）中，(Xi1,Yi1)、(Xi2,Yi2)分别为节点i在上一时刻ti1和当前ti2时刻的坐标。2.2 链路持续时间算法采用链路持续时间来衡量通信链路的质量，链路持续时间越长则代表链路质量越好。通过两个节点的运动速度和方向可以计算出链路持续时间。假定任意两个车辆节点为M和N，且在当前时刻建立了通信。此时M和N的位置坐标分别为(XM,YM)、(XN,YN)，通过式（1）和式（2）可计算出M和N的运动速度和方向。此外，还可以计算出此时M和N之间的距离d，计算公式如下。d=()XM-XN2+()YM-YN2（3）（a）贪婪转发（b）周边转发图1 GPSR算法两种转发模式示意图10信 息 与 智 能 2023 NO.8 SCIENCE&TECHNOLOGY INFORMATIONSCIENCE&TECHNOLOGY INFORMATION科技资讯科技资讯假定一段时间内车辆保持匀速行驶，运动速度和方向不变，车辆M、N的速度大小分别为VM、VN，节点的通信范围为R，则链路的维持时间T可分为以下5种情况。情况一：车辆M、N同向行驶，前车的速度大于后车，那么M与N之间的链路维持时间为T=R-d|VM-VN（4）情况二：车辆M、N同向行驶，前车速度小于后车速度，则M、N之间的链路维持时间为T=R+d|VM-VN（5）情况三：车辆M、N同向行驶，两车的速度相同且不变，则M、N之间的通信链路将会一直持续下去，链路维持的时间无穷尽。情况四：车辆M、N相向行驶，则M、N之间的链路维持时间为T=R2-()YM-YN2+()XM-XN|VM+VN（6）情况五：车辆M与N背向行驶，则车辆M、N之间的链路维持时间为T=R2-()YM-YN2-()XM-XN|VM+VN（7）2.3 与目的节点的距离发送节点的一跳范围内的任一邻居节点j与目的节点D之间的距离Dis可通过式（8）计算得出。Dis=()Xj-XD2+()Yj-YD2（8）式（8）中，(Xj,Yj)为任一邻居节点j的位置，(XD,YD)为目的节点D的位置坐标。2.4 权重函数通过上述计算可以得到发送节点和每个邻居节点间的链路持续时间T、每个邻居节点与目的节点间的距离Dis，设置一个权重函数具体如下。Weight=T+Dis（9）式（9）中，和为系数，且+=1，Weight为权重值。图2 不同节点数下的分组投递率对比图表1 仿真参数参数仿真工具仿真区域路由算法节点数量通信范围MAC层协议传输模型数据包类型数据包大小传输层协议仿真时间值NS-31 000 m1 000 mGPSR、GPSR-S20140250 mIEEE 802.11Two Ray GroundCBR512 byteUDP200 s/辆%/11 2023 NO.8科技资讯SCIENCE&TECHNOLOGY INFORMATION 信 息 与 智 能SCIENCE&TECHNOLOGY INFORMATION科技资讯当数据包被传送至某个节点后，通过式（9）可计算出该节点与每个邻居节点间的权重值，选择权重值最大的邻居节点为下一跳，这样选出来的节点具有稳定性。不断重复此过程，直至将数据包送达目的节点。3 仿真实验实验采用NS-39仿真平台对GPSR算法和改进的GPSR-S算法进行性能仿真，对两种算法的性能进行分析比较。3.1 仿真参数设置实验的仿真场景设置为 1 000 m1 000 m 的区域，节点的通信传输半径为250 m，其他仿真参数的设置如表1所示。设置实验，分析两种算法在不同节点数下的性能比较。在实验中，将车辆的速度固定为15 m/s，车辆数以20的步长从20逐渐增加到140。3.2 仿真结果分析图2是不同车辆数下的GPSR和GPSR-S的分组投递率对比图。由图2看出，当车辆数较少时，节点间的通信链路较少，二者的分组投递率较低。当车辆数目增加时，网络连通性增大，二者的分组投递率也有所提升。不同的是，GPSR-S还考虑了链路的可靠性，避免了 GPSR 通信链路易断裂问题。因此，GPSR-S 比GPSR的分组投递率更高。图3比较了GPSR和GPSR-S在不同车辆数目下的平均端到端时延。从图3中可以看出，随着节点数量的增加，二者的平均端到端时延减小。原因是当节点数较少时，算法经常进入周边转发，整体时延较大。随着节点数量增加，转发节点的邻居节点也增多，算法进入周边模式的概率降低，整体的时延减小。而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 SimulatorJ.Promet-Traffic&Transportation,2020,32(2):255-268.图3 不同节点数下的平均端到端时延对比图/辆 s/12