城市场景中GPSR路由协议的改进

童孟军，陈焕银

(杭州电子科技大学计算机学院，浙江杭州310018)

0 引言

在无线传感网络中，一种由移动车辆节点组成的车载自组织网络 VANET(Vehicular Ad hoc Networks，VANET)具有巨大的应用价值，目前成为新兴的研究热点［1－3］。相对于传统的自组织网络AODV和DSR路由协议，GPSR路由协议基于地理位置信息，它不需要存储路由信息，性能指标更好［4－6］。然而由于城市场景中的各种限制条件，使得现有的GPSR路由协议还存在着缺陷。为了改进GPSR路由协议存在的这些不足，本文在详细研究了GPSR路由协议的基础上，提出了相应的改进方案(改进后的协议称为GPSR_IMP路由协议)。仿真实验结果分析表明，GPSR_IMP路由协议在数据报文成功投递率和路由负载上均优于GPSR路由协议。

1 一种新的基于GPSR的改进协议

本文对GPSR路由协议的改进策略主要体现在以下几个方面:

(1)当节点处于数据报文转发选择下一跳节点时，对本节点维护的邻居列表中的所有邻居节点的位置坐标进行预测分析，下一跳节点不仅需要满足贪婪转发机制或者边缘转发机制的要求，还必须满足新提出的一些条件;

(2)对GPSR路由协议中节点周期性发送Hello报文的机制进行修改，使节点能够根据当前本节点的状态自适应的发送Hello报文，提高Hello报文的效率;

(3)提出一种数据报文转发的应急处理机制，使得当节点在进行数据报文转发时未能找到下一跳节点时，并不立即将数据报文丢弃而是采用应急处理机制作进一步处理。

本文主要从节点的位置预测、动态发送Hello报文和应急处理机制3个方面对GPSR路由协议进行改进。

1.1 节点位置坐标的预测

节点位置坐标的预测首先需要获取到本节点的速度(包括X轴和Y轴的速度)。节点速度的计算随仿真软件的不同而有所差别。在NS2仿真工具中较为简单，移动类直接提供了速度参数的函数接口，通过函数接口可以直接获取到移动节点的三维速度矢量(包含X轴速度、Y轴速度甚至Z轴速度)。对于其它的仿真软件有一种较好的通用解决方法，对于一个节点U，在得到节点U的两个位置信息的前提下，其速度的计算公式如下:

通过式1、2便可以计算出X轴、Y轴方向的速度，Z轴方向的速度被认为是0。

当节点接收到携带速度信息的Hello报文时，节点需要将邻居节点的速度信息保存到邻居列表中以便能够对邻居节点的位置信息进行预测。节点W的位置信息预测公式如下所示:

式中，(Xpre，Yrecv)为经过预测后的节点W的坐标，Tnow为当前的系统时间，即节点U进行数据报文转发选择下一跳节点的时间。经过式3、4预测节点W的位置信息后，通过下下式来判断节点W是否在节点U的通信范围之内:

如果DIS大于节点U的通信范围，则认为节点W不能作为数据报文转发的下一跳节点。

1.2 动态发送Hello报文

改进后的GPSR路由协议的Hello报文发送时机包括以下几点:(1)如果节点在周期性更新本节点坐标及速度等参数后，感知本节点已经进入了一条新的街道;(2)如果节点按照上一次发送Hello报文时的速度以及坐标信息所预测的本节点位置坐标与实际节点的位置坐标之差超过阈值HELLO_THRESHOLD;

(3)如果上次发送Hello报文的时间与当前时间相隔超过HELLO_TIMEMAX;(4)在应急处理机制中，当节点收到紧急Hello报文时也将会回复Hello报文。

依据这些规则可以实现动态调整Hello报文广播发送的次数。由于改进后的GPSR路由协议取消了Hello报文的发送周期，所以相应的节点邻居列表的维护也将做出相应的调整。在GPSR_IMP路由协议中，节点将邻居节点从邻居列表中删除的时机有:(1)对该邻居节点进行地理坐标预测，预测后的地理坐标已经超出本节点的通信范围;(2)上一次收到邻居节点Hello报文的时间距离现在已经超过HELLO_TIMEMAX －1)。

1.3 应急处理机制

在GPSR_IMP路由协议中，当节点通过贪婪转发机制或者边缘转发机制都未能找到数据转发的下一跳节点时，节点并不立即将数据报文丢弃。节点首先将数据报文缓存到本地，然后发送一个紧急Hello报文。邻居节点收到紧急Hello报文后必须在［0，E_TIME］内随机选择一个时刻回复发送普通的Hello报文。

节点在等待DELAY_TIME(必须大于E_TIME)后，将再次尝试通过贪婪转发机制或者边缘转发机制来查找下一跳节点。如果本节点能够找到符合条件的下一跳节点，则数据报文的转发继续进行，否则将数据报文丢弃。

2 GPSR协议改进后仿真分析

对改进后的GPSR_IMP路由协议进行仿真实验，仿真实验环境如表1所示。

表1 仿真实验网络参数设置

2.1 数据报文的成功投递率

数据报文成功投递率与车辆节点数量的关系如图1、2所示，在实验中车辆节点的速度被设置为≤40 km/h，车辆节点的数量从60递增至140。从图1、2中可以看出，随着车辆节点数目的增加，GPSR路由协议和GPSR_IMP路由协议的数据报文成功投递率都有着显著的提升。在整个的仿真实验中，GPSR_IMP路由协议的数据报文成功投递率始终都优于GPSR路由协议。GPSR_IMP路由协议优势体现在:(1)速度参数的引入有效的降低了RET类型丢包数;(2)动态的Hello报文发送机制使得Hello报文只有在有需求的时机才会发送，这不仅减少了Hello报文的发送个数，而且提高了Hello报文的效率;(3)应急处理机制也发挥了相应的作用。

图1 PDF与车辆节点数量的关系

图2 PDF与车辆节点速度的关系

2.2 路由协议负载

数据报文路由负载与车辆节点速度的关系如图3所示。在实验中设置车辆节点数量为100，车辆节点的速度由20 km/h递增至60 km/h。从图3中可以看出GPSR_IMP路由协议和GPSR路由协议的路由负载都随着车辆节点速度的增加而增加。在整个仿真实验过程中，GPSR_IMP路由协议的路由负载均小于GPSR路由协议。这种情况的出现主要是由于GPSR_IMP路由协议采用动态的Hello报文发送机制，能够有效的减少仿真过程中总的Hello报文的数量，从而降低了路由协议负载。

3 结束语

图3 路由负载与车辆节点速度的关系

本文提出了一种基于GPSR路由协议在城市场景中的改进策略，改进方案有节点的位置预测、Hello报文的动态发送以及增加数据报文转发时的应急处理机制等。仿真实验结果表明，改进后的路由协议在数据报文成功投递率和路由负载上均优于GPSR路由协议。

［1］Wang Y，Li F.Vehicular ad hoc networks［C］.London:Springer-Verlag，2009:503 －525.

［2］Liu Y，Bi J，Yang J.Research on vehicular ad hoc networks［C］.Guilin:Control and Decision Conference.2009:4 430－4 435.

［3］Tarik Taleb，Ehssan Sakhaee，Abbas Jamalipour，etal.A stable routing protocol to support ITS services in VANET networks［J］.IEEE Transactions on Vehicular Technology.2007，56(6):3 337 －3 347.

［4］Perkins C E，Royer E M.Ad-hoc on-demand distance vector routing［C］.New Orleans:Mobile Computing Systems and Applications.1999:90 －100.

［5］Johnson D B，Maltz D A.Dynamic Source Routing in Ad Hoc Wireless Networks［J］.Mobile computing.1996，353:153－181.

［6］Karp B，Kung H.GPSR －:Greedy perimeter stateless routing for wireless networks［C］.Boston:Association for Computing Machinery，2000，243 －254.