基于下一跳前向转发节点密度的GPSR改进协议*

伍龙昶 石 英 张焕清 华逸伦

(武汉理工大学自动化学院 武汉 430070)

基于下一跳前向转发节点密度的GPSR改进协议*

伍龙昶 石 英 张焕清 华逸伦

(武汉理工大学自动化学院 武汉 430070)

分析了一种适用的地理位置路由协议——贪婪周边无状态路由协议(greedy perimeter stateless routing protocol,GPSR).针对其路由空洞过多带来的投递率下降、时延增加等问题，提出了一种综合考虑接近率和下一跳节点前向转发区域密度的改进算法GPSR-D.利用网络仿真平台NS3对AODV、GPSR和GPSR-D协议进行仿真研究，结果表明基于位置的GPSR在投递率和平均时延上均较基于拓扑的AODV更好，改进后的GPSR-D在不增加平均端到端时延的基础上减少了约1/2的路由空洞数，分组投递率提高了5%.

车载自组网；贪婪周边无状态路由；路由空洞；接近率；前向转发区域；NS3仿真

0 引 言

车载自组织网络(vehicular ad hoc network,VANET)是一种临时的、自由组织的车间通信网络，融合了车辆间直接互连，间接互连及车辆与路边固定设施互连方式，用来传递紧急安全信息和提供网络服务[1-2].作为传统移动自组织网络的衍生，车载自组织网络具有无中心、自组织、临时性和多跳路由等特点，其高度动态的网络拓扑结构和有限的无线传输带宽严重制约了网络传输的可靠性，尤其是多媒体服务质量[3-4].交通信息能影响道路拥堵扩散过程[5]，有效缓解因车辆保有量激增和交通基础设施建设相对缓慢带来的交通问题，为了实现信息的有效传递，需要简洁高效、鲁棒性强的路由协议来提供网络服务支持.目前，车载自组网路由协议大多从传统的移动自组织网络发展而来，主要分为基于拓扑和基于地理位置信息的路由.其中，基于地理位置信息的路由协议结合了网络拓扑和地理位置拓扑，优化了路由决策，适用于受道路拓扑结构影响的无线网络.Karp等[6]提出了一种经典的地理位置路由协议——贪婪周边无状态路由协议(greedy perimeter stateless routing protocol,GPSR)，利用贪婪转发策略和周边转发恢复策略来建立路由，具有高效简洁、扩展性好的特点.但此算法在遇到路由空洞时存在跳数增加、非最佳路径等问题.文中通过仿真研究改进GPSR算法，以减少路由空洞，提高转发性能，为车联网提供更高效的通信服务.

1 GPSR基本原理

1.1 算法描述

GPSR协议是一种基于地理位置信息的自组网路由协议，核心思想是贪婪转发和周边转发.每个节点周期性地广播Hello信标，该信标包含本节点的ID标识及地理位置信息.与此同时，每个节点维护一个邻居位置表，接收到Hello信标后更新并存储其邻居节点的编号和位置信息.当有数据分组发送时，首先使用贪婪转发算法遍历邻居位置表，计算邻居节点与目的节点的欧式距离，选取距离值最小的邻居进行下一跳转发.类似的，每个中间节点通过贪婪转发算法进行分组转发直至到达目的节点或者贪婪转发失败.当转发节点到目的节点的距离比所有邻居节点到目的节点的距离更近时，贪婪转发失败，数据分组陷入局部最优，即传播路径上出现了路由空洞，此时，GPSR从贪婪转发模式转换到周边转发模式.周边转发模式通过相对邻域图、加百利图等平面化算法简化网络拓扑，消除拓扑图中的交叉边，然后通过右手法则选取下一跳节点，即源-目的节点的边以逆时针方向旋转遍历邻居节点，故数据分组在顺时针方向上围绕路由空洞进行转发，直至恢复贪婪转发模式或者到达目的节点.

1.2 算法特点

GPSR算法简洁高效、复杂度低，由于只利用一跳节点范围的状态信息进行路由选择，可扩展性强，适用于大规模网络.GPSR算法高效而完备，其贪婪算法充分利用了邻居节点的位置信息，选取传播最远的转发节点，实现了数据分组的高效转发；周边转发算法在平面图的基础上利用右手法则进行周边遍历，直至恢复贪婪转发模式，保障了路由协议的完备性.

GPSR也存在着一些局限性，贪婪算法选取的转发节点通常靠近通信边缘，如果节点在Hello周期内移动出了该范围，会导致传输失败.周边转发模式虽然能保证数据分组能够走出路由空洞，但每次转发都需要平面化拓扑来消除交叉边，以增加转发跳数为代价来减少路由环路，并且大多数情况下转发路径不是最佳，因此频繁的路由空洞会造成GPSR算法性能的剧烈下降.

在GPSR的基础上，唐国明等[7]提出了基于左、右手法则的改进算法，在遇到路由空洞时根据节点所处的区域选取相应的左右手法则进行转发，以减少路由跳数，提高分组投递率.Kumar等[8]通过速度和方向预测节点位置来选择下一跳转发节点，以减少Hello信标周期内因节点移动而导致的链路失效.Sabri等[9]结合转发方向角和当前节点范围分布因素选择下一跳节点，以减少路由环路并提高性能.Chung等[10]提出了基于定时器的贪婪转发策略，定时器与距离成反比，超时即广播数据分组，其他节点接收到该分组的副本时丢弃该分组，该策略避免了额外的信息交换.

这些改进方法虽然优化了路由效果，但均根据本地节点的状态信息作为转发策略依据，没有充分考虑网络中的其他信息，转发节点的选取具有一定的局限性.且改进后的算法虽然优化了路由空洞的恢复策略，但并没有从根本上解决或减少遇到空洞的问题.

2 GPSR算法改进

2.1 前提条件

1) 所有车辆节点均配备GPS或其他定位设备，可以实时获知自身所在位置信息并被统一编址.

2) 通过网格位置服务、反应式位置服务和层次位置服务等位置请求服务，能够获取目的节点的位置[11].

3) 车辆节点通信范围近似为一个平面，通信模块工作于混杂模式下.

2.2 基本思想

通过下一跳节点的邻居分布情况来加强转发节点寻优的过程，综合考虑接近率和下一跳节点前向转发区域密度因素，以此作目标评价函数，优化转发节点的选择，以减少路由空洞几率，提高路由性能，从而提出了基于下一跳节点前向转发区域密度的改进算法GPSR-D.

2.2.1 接近率

图1为接近率的示意图，由图1可知，车辆节点S为信息流源节点，车辆节点D为目的节点，节点X为节点S的任一邻居节点，R为S节点的通信范围.实线段表示节点之间的欧式距离，虚线弧表示以该距离为半径，目的节点为圆心作的圆弧.贪婪算法根据欧式距离选取距离目的节点最近的节点进行转发，定义接近率为

(1)

式中：x和y为各节点的坐标值；R为节点的通信范围.

图1 接近率示意图

接近率反映了邻居节点在数据传输方向上接近通信边缘的程度，其取值范围为[-1,1]，值为正且越大时，转发节点的优先权越大.值为负时则不列入候选转发节点.

2.2.2 前向转发区域密度

前向转发区域见图2，S为源节点，D为目的节点，X为节点S的任一邻居节点.以X节点为原点，将X的通信范围划分为4个象限，统计每个象限的邻居节点数，将之附加在Hello信标中进行广播.节点S接收到节点X的Hello信标后，计算X与D节点的方向角，该方向角所处的180°区域范围记作数据分组的前向转发区域.

图2 前向转发区域示意图

以图中X，D点位置为例，其夹角处于(315,45]范围，可以认为前向转发区域为1象限和4象限.定义前向转发区域密度的评价函数为

(2)

式中：∑ni为前向转发区域的节点数之和；N为区域内饱和节点阈值.fden取值范围为[0,1]，值越高，转发优先权越大.大于节点数阈值N，可认为前向转发区域内已有较好的连通性，此时fden取值1，转发策略恢复成贪婪转发.

结合上述接近率和密度模型作为节点优选评价指标，多目标函数为

maxF=max[fdis,fden]T

s.t. (xX-xS)2+(yX-yS)2≤R2

(3)

重构多目标函数的评价函数为

F=max{ρfdis+(1-ρ)fden}

s.t. (xX-xS)2+(yX-yS)2≤R2

(4)

式中：ρ为目标权重，表示接近率在评价机制中所占比重.经过实验，ρ从0.1～1.0，步长为0.1，N从2～10，步长为2，根据结果选取较优参数ρ=0.7和N=8.结果表明，贪婪算法中，距离对路由性能的影响更大，同时下一跳节点的前向区域密度也是不可忽视的因素.

为了利用下一跳节点的状态信息，Hello信标更改为

IDX0Y0N1N2N3N4

其中：ID为每个节点的唯一标识符；X0、Y0为节点在平面坐标下的当前位置；N1-N4分别为节点4个象限的邻居节点数.

2.3 算法流程

GPSR-D算法分为以下6步.

步骤1 网络中所有节点周期性广播Hello信标.收到信标，则更新位置表中邻居节点的位置、分区节点数等信息.

步骤2 信息源节点S通过位置请求服务获取目的节点D的地理位置.

步骤3 如果D在S通信范围内，则直接转发到目的节点.

步骤4 转发节点计算邻居节点集NN的接近率fdis.

步骤5 如果fdis>0，计算该邻居节点的评分F并加入候选转发节点集CN，否则回到步骤4计算下一邻居节点.

步骤6 如果候选转发节点集为空，则进入周边转发模式，否则选取评分F最高的节点进行转发.

2.4 算法特点

GPSR-D优点在于不仅仅考虑本地节点获取的状态信息，还考虑下一跳节点的邻居分布情况，保证了下一跳仍处于高效的贪婪转发模式.同时数据分组在前向转发区域上密度越大，不失一般性，可以认为其连通性越强，出现路由空洞的几率越小，可以有效减少路由空洞带来的性能下降问题.相较于GPSR的本地优化策略，GPSR-D考虑两跳状态信息优选节点，既给转发策略提供更多的选择信息，又避免了多跳状态信息造成的路由开销.

3 仿真实验与结果分析

3.1 仿真场景搭建

利用开源网络仿真平台NS3搭建仿真场景，对GPSR-D进行仿真，并与GPSR和AODV路由协议进行比较.分析路由协议在数据分组投递率、平均端到端时延，以及路由空洞数等方面的性能表现.

仿真实验以空旷地带车辆节点自由行驶作为仿真场景，为了增加转发跳数，将交通场景抽象成1 500 m×300 m的矩形区域，采用随机游走模型，仿真场景参数见表1.

表1 仿真场景参数

设计两组实验，一组实验中车辆最高速度为20 m/s，车辆数从20～160变化，步进值为20，验证协议在不同节点密度下的性能表现；另一组实验中车辆数为40，车辆最高速度从0～40 m/s变化，步进值为5，验证协议在不同速度下的性能表现.

3.2 仿真结果分析

对于两组实验，以不同的随机数种子执行5次，取结果的平均值.实验1仿真研究AODV、GPSR和GPSR-D在不同节点密度下关于分组投递率、平均端到端时延，以及路由空洞数等方面的性能表现，实验结果见图3～5.

图3为不同节点密度下的分组投递率对比结果.由图3可知，在40个节点之后，随着节点数的增加，AODV的投递率从85%急剧下降到40%附近，由于AODV基于网络拓扑进行路由选择，需要泛洪路由消息控制帧：请求包RREQ、应答包RREP和错误包RERR，网络规模越大，转发路径越长，路由控制信息就越多，容易造成广播泛洪和网络拥塞.GPSR和GPSR-D的投递率随节点数曲线下降缓慢，

图3 不同节点密度投递率

维持在80%附近，由于其贪婪特性，理论上在达到一定的密度阈值即可有较好表现，但受信道竞争和退避算法的影响，随着节点数增加，其投递率略有下降，其中改进后的算法GPSR-D投递率表现平均比GPSR高5个百分点以上，体现了GPSR-D考虑下一跳前向区域连通性进行转发的优点.

图4为不同节点密度下的平均端到端时延对比结果，反映出基于拓扑的AODV协议有着较高的时延基数，并受节点密度影响较大.GPSR-D的平均时延较GPSR相近，基本处于0.018 s以下的较小值，说明GPSR-D保持了贪婪算法的特性，转发跳数少且受节点密度影响较小.

图4 不同节点密度平均端到端时延

图5为GPSR和GPSR-D在不同节点密度下遇到路由空洞的次数.节点数为20时，路由空洞数均较高，这是由于节点分布稀疏，容易导致找不到合适的节点进行贪婪转发.在节点数为40节点以上时，路由空洞数大幅下降，因为密度增加而能够维持较高效的贪婪转发.结果显示GPSR-D较GPSR遇到路由空洞的几率减少了约一半，有着更好的转发性能.

图5 不同节点密度路由空洞数

实验2仿真研究AODV，GPSR和GPSR-D在不同节点速度下的性能表现，实验结果见图6～8.

图6为不同速度下的分组投递率对比结果.在低速情况下，链路中断率低，三种路由协议均有较好的表现，GPSR和GPSR-D可以接近100%的投递率.随着速度的增加，网络拓扑断裂越来越频繁，数据分组投递率也逐渐下降.结果显示，GPSR-D在5 m/s以上的运动速度时，比GPSR有更高的投递率.这是由于周边转发过程对位置信息较敏感，当速度增加时，节点位置信息更容易失效而导致丢包现象，故减少了路由空洞数的GPSR-D丢包更少.

图6 不同节点速度投递率

图7为不同速度下的平均端到端时延对比结果.AODV的时延呈波动上升到约0.05 s，说明传输链路断裂时，AODV需要额外的路由控制帧来进行路由恢复.GPSR-D的时延保持在0.008 s以下，大部分情况下传输时延相较于GPSR更低，表明减少路由空洞后，在一定程度上减少了平均端到端时延.

图7 不同速度平均端到端时延

GPSR和GPSR-D在不同节点速度下遇到路由空洞的次数见图8.在5 m/s的低速下，路由空洞几乎为0，这是因为节点位置的初始分配造成空洞数较少.在速度增加到10 m/s以上时，拓扑变换增强，路由空洞数增加，而GPSR-D平均减少一半以上遇到路由空洞的几率，这是由于其通过下一跳状态信息的收集处理，选取连通性更好的节点进行转发.

图8 不同速度路由空洞数

4 结 束 语

针对传统GPSR路由转发决策非全局最优及遇到路由空洞存在的效率下降问题，提出了基于下一跳前向转发区域密度的改进算法GPSR-D.通过NS3仿真平台对AODV，GPSR和GPSR-D协议进行仿真比较，证实基于地理位置的路由在大规模网络中的分组投递率、平均端到端时延较基于拓扑的路由协议有较好的表现，且改进后的GPSR-D算法虽然考虑更多约束条件，相较于GPSR算法，在不同节点密度和不同节点速度下，并未增加平均端到端时延，由于减少了路由空洞出现的次数，获得了更高的分组投递率.

[1]URQUIZA A, TRIPP B, ROMERO M A. Mitigation of packet duplication in VANET unicast protocols[J]. AD HOC Networks,2016,52(SI):63-77.

[2]ELIAS C E, ZHANG S J, LIU E J. Vehicular ad hoc networks (VANETs): current state, challenges, potentials and way forward[C]. Automation and Computing (ICAC), 2014 20th International Conference on, Bedfordshire，IEEE,2014.

[3]任智，姚玉坤，曹建玲，等.无线自组织网络路由协议及应用[M].北京:电子工业出版社,2015.

[4]冯振新，李腊元.典型Ad hoc网络协议传输多媒体数据的性能分析[J].武汉理工大学学报(交通科学与工程版),2007,31(6):1075-1078.

[5]叶晓飞，包哲宁，邓社军，等.信息化条件下交通拥堵瓶颈识别与扩散判别[J].武汉理工大学学报(交通科学与工程版),2014,38(5):1060-1064.

[6]KARP B, KUNG H T. GPSR: greedy perimeter stateless routing for wireless networks[C]. Proceedings of the 6th Annual International Conference on Mobile Computing and Networking(MobiCom2000), Boston，ACM,2000.

[7]唐国明，谢羿，唐九阳，等.一种基于左、右手法则的GPSR分区边界转发路由协议[J].计算机应用研究,2011,28(3):1099-1101.

[8]KUMAR R, RAO S V. Directional greedy routing protocol (DGRP) in mobile ad-hoc networks[C]. International Conference on Information Technology, Bhubaneswar，IEEE,2008.

[9]SABRI M H, MOHAMMAD M K, TAT C W. Density-aware directional forwarding strategy for vehicular ad hoc networks[C]. Communications (MICC), 2015 IEEE 12th Malaysia International Conference on, Malaysia，IEEE,2015.

[10]CHUNG M H, SHIH Y L. Timer-based greedy forwarding algorithm in vehicular ad hoc networks[J]. Intelligent Transport Systems,2014,8(4):333-344.

[11]OMER K A A, LOBIYAL D K. Efficient grid location service scheme for MANET[J]. Inst of Electronics and Telecommunication Engineers,2015,52(2):177-185.

The Improvement of GPSR Protocol Based on the Node Density of the Next Hop’s Forwarding Region

WU Longchang SHI Ying ZHANG Huanqing HUA Yilun

(School of Automation, Wuhan University of Technology, Wuhan 430070, China)

A suitable routing protocol based on the geographic location, Greedy Perimeter Stateless Routing Protocol, is analyzed. In order to improve the performances of packet delivery rate and the delay caused by excessive routing void, an improved algorithm GPSR-D taking the approaching rate and the forwarding node density of the next hop into account for the optimum selecting of the forwarding node, is proposed. Through the network simulator of NS3, the performances of AODV, GPSR and GPSR-D are studied. It shows that from the view of packet delivery and the average delay, GPSR based on geographic location is better than that of AODV based on topology, and GPSR-D does better than GPSR for one half of the routing void decrease and the packet delivery rate increase of more than 5% without the extra average end-to-end delay.

vehicular ad hoc network; greedy perimeter stateless routing protocol; routing void; approaching rate; forwarding region; NS3 simulation

2017-04-07

*江苏省重点研发计划项目(BE2016155)、国家自然科学基金项目(61374050，61673306，51477125)资助

TP393

10.3963/j.issn.2095-3844.2017.03.023

伍龙昶(1992—)：男，硕士生，主要研究领域为车联网