改进的贪婪型周边无状态路由协议

张继荣, 赵晓彤, 屈军锁, 崔 燕

(1.西安邮电大学 通信与信息工程学院, 陕西 西安 710121; 2.电信科学技术第四研究所 研发中心, 陕西 西安 710061)

改进的贪婪型周边无状态路由协议

张继荣1, 赵晓彤1, 屈军锁1, 崔 燕2

(1.西安邮电大学 通信与信息工程学院, 陕西 西安 710121; 2.电信科学技术第四研究所 研发中心, 陕西 西安 710061)

对贪婪型周边无状态路由协议加以改进。在报头中加入邻居节点的移动速度和方向信息，当节点转发过程遭遇路由空洞时，据此信息预测邻居节点下一时刻的位置。若预测位置不符合贪婪转发要求，仍继续周边转发模式，否则，进入“等待转发模式”，即经过一个极小的等待时延后，跳转回到贪婪转发模式，以减少周边转发过程存在的大量冗余。借助仿真软件Network Simulator version 2搭建网络环境，对改进协议与原协议在节点速度为10～40 m/s的情况下仿真，比较其端到端时延和平均跳数，结果显示，改进协议在给定环境中能够降低时延5%～17%，减少跳数5%左右。

路由空洞；贪婪型周边无状态路由协议；Network Simulator

贪婪型周边无状态路由协议(Greedy Perimeter Stateless Routing, GPSR)[1]是移动自组网中一种常用路由协议，它通过预先获取位置信息，利用源节点和目的节点的位置来制定数据包转发策略，其具体转发过程包括两种模式[2]，即贪婪转发模式和周边转发模式。

GPSR协议优先采用贪婪转发模式，源节点选择距离目的节点最近的邻居节点作为下一跳转发节点，邻居节点收到转发分组时，会继续采用同样的方法进行转发，最终被传至目的节点。贪婪转发的缺点是路由空洞问题[3]。当遭遇路由空洞时，则会转入周边转发模式，顺着路由空洞的周边通过右手定则寻找新的路由。当贪婪转发条件再次满足时，可以自动转回贪婪模式，直到数据分组发送到目的节点[4]。

GPSR 协议使用贪婪思想进行转发分组，降低了开销，提高了协议的稳定性[5]，但协议存在的问题也很多。针对局部区域内节点多次承担转发任务而能量耗尽的问题，文献[6]提出一种改进的路由算法IGPSR，该算法结合能量的前向区域划分机制和概率传输机制在邻居节点中选择下一跳节点，有效保证邻居节点能量的均衡消耗；针对可能出现的路由隔断和延时增加问题，文献[7]所给改进方案，有效改善了路由错误和冗余问题；针对边界节点能量消耗大和遇到路由空洞时路由效率低下的问题，文献[8]提出一种基于机会转发的改进协议O-GPSR；为了实现传输节点路径的最优化，文献[9]根据每个节点中维护的邻居节点相关信息进行分析，选择转发过程的下一跳节点。

本文拟针对周边转发过程中由于使用右手定则而产生的跳数增多和路径冗余问题，给出一种新的GPSR协议改进方法。通过在报头中添加邻居节点的移动速度和方向信息，使节点在遇到路由空洞时能够预测邻居节点下一时刻的位置，从而判断是否能够符合贪婪转发的条件，添加了“等待转发模式”，即在等待一个极小的时延后，再次跳转到贪婪转发模式，以减少周边转发过程存在的大量冗余。

1 GPSR协议改进

1.1 GPSR协议存在的问题

在周边转发的过程中，数据包会开拓一条到目的节点的转向路径，而这条路径通常会很长，造成了能量的浪费和过多的延时。如图1所示，假设节点S检测到路由空洞，自身成为了最佳主机，则采用周边转发模式，转发过程为S→L→M→N→P→Q→D，且在节点密度增大的时候，周边转发模式也会使路由跳数增多，导致信道资源浪费和时延的增加。这一问题正是需要改进之处。

图1 GPSR协议遭遇路由空洞转发过程

1.2 GPSR协议改进思想

(1) 在每个节点维护的邻居表中，加入邻居节点的移动方向、速度等信息，在获取邻居节点的地理坐标位置的同时，也需要获得邻居节点X，Y，Z三个方向的速度，通过方向和速度预测邻居节点位置。

(2) 考虑到MANET网络的随机移动性，网络的拓扑结构是随时间不断变化的，给出一种“等待转发模式”。节点S在转发过程中遭遇路由空洞时，对邻居表进行维护，获取其他节点的速度和方向，对节点的移动位置进行预测，并预测节点邻居关系的变化，选取在下一时刻能够跳入自己转发范围且在目的节点方向上的点，作为最佳边缘节点。如果存在这样的最佳边缘节点，则等待一个最小时间间隔Δt，在下一时刻最佳边缘节点跳入后继续采取贪婪转发模式进行下一跳转发。如果不存在这样的边缘转发节点，则仍然采用周边转发模式，使用右手定则进行转发。

改进后的路由转发过程如图2所示。源节点S的边缘节点Q和M在下一时刻跳入S的转发范围之内，且Q即为最佳边缘节点，下一时刻新增点Q′和点M′，此刻S不再是最佳主机，则可以继续采用贪婪策略进行转发，转发过程为S→Q′→D，最终到达目的节点D。

图2 改进协议遭遇路由空洞时的转发过程

1.3 改进协议的优势

改进GPSR协议在贪婪转发失败时，选定最佳边缘节点并等待某一极小的时间间隔Δt，可避免平面周边转发中的多跳问题。对比图1与图2可知，相对于直接选取周边转发模式，改进GPSR协议在S点明显降低了路由跳数，从而相对提高协议的效率。

2 仿真分析

基于Ubuntu采用NS2.35作为仿真平台，仿真区域为670 m×670 m，传输范围250 m，仿真时间为250 s，利用setdest工具生成四个速度不同的场景文件，分别包含最大移动速度为10 m/s， 20 m/s， 30 m/s， 40 m/s的100个随机节点的坐标以及移动信息。相关仿真参数如表1所示。

表1 主要的网络仿真参数

使用NAM动画演示工具记录仿真过程，动画截图如图3所示。

图3 NAM动画演示

平均端到端时延[10]是网络中所有数据包端到端时延的平均值，包括了数据包在传输过程中的所有时延。图4显示了节点移动速度不断增大，平均端到端时延的变化曲线,从中可见，随着速度增大，GPSR协议以及改进协议的时延逐渐增加，这是由于速度变快时网络拓扑结构的变化也会加速，而改进协议能够减少路由转发的跳数，进而减少节点间的传输时间和排队时间，相比原协议的端到端时延减小。

图4 平均端到端时延对比

数据分组从源节点转发到目的节点所经历的平均跳数,可以表示为发送数据包与转发数据包之和除以发送数据包的个数。原GPSR协议和改进协议在不同速度转发过程中的路由平均跳数变化情况如图5所示，从中可见，改进协议可以适当地降低平均跳数。

图5 不同速度下的跳数对比

3 结束语

针对GPSR协议中周边转发模式产生过多冗余的问题，通过在报头中加入邻节点的移动速度和方向信息，并引入一种“等待转发模式”，从而给出改进策略，使其在遭遇路由空洞时可以减少原协议的路由跳跃次数。借助NS2仿真验证，结果显示，改进协议还能够降低平均时延。

[1] 黄乔永. 基于移动模型的Ad Hoc路由协议仿真研究[D].昆明：昆明理工大学，2012:2-14.

[2] 林彦汝. 一种基于地理位置的Ad Hoc路由协议[D].广州：暨南大学，2010:5-7.[3] 唐国明，谢羿，唐九阳. 一种基于左、右手法则的GPSR分区边界转发路由协议[J]. 计算机应用研究，2011(3)：1099-1101.

[4] 王志刚. 车载Ad hoc网络中基于车辆流密度的GPSR协议的改进研究[D].长春：吉林大学，2012:13-16.

[5] 张鹏明，李洪烈，林成浴. 基于地理定位信息的移动自组网路由协议综述[J].电讯技术，2012，52(9):3-7.

[6] 吴三斌，王小明，杨涛，等. 改进的GPSR模型及其仿真分析[J]. 计算机工程与应用，2011(1)：100-104.

[7] 彭好佑. 车载自组织网络GPSR路由协议研究及算法改进[D].海口：海南大学，2013:4-20.

[8] 于耕，孙翔，李洪烈，等. 基于机会转发原理改进的GPSR算法[J]. 科学技术与工程，2014(10)：42-47.

[9] Shu Wenjie, Wang Ping, Guo Aihuang, et. al. Enhanced GPSR using neighbor-awareness position update and beacon-assist geographic for-warding in vehicular ad hoc networks[C]//Proceedings of the 2007 IEEE International Conference on Inetlligent Vehicles Symposium. Xi’an: IEEE, 2009: 1143-1147.

[10]雷文君. 基于时分同步码多址的无线数据传输方案[J].西安邮电学院学报，2012，17(6):9-10.

[责任编辑:瑞金]

An improved greedy perimeter stateless routing protocol

ZHANG Jirong1, ZHAO Xiaotong1, QU Junsuo1, CUI Yan2

(1. School of Communication and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China; 2.Research and Development Center, The 4th Research Institute ofTelecommunications Science and Technology, Xi’an 710061, China)

An improvement to the greedy perimeter stateless routing protocol is proposed by adding the moving speed and direction of adjacent node to the header. According to the added information, the next location of an adjacent node can be predicted, as the forwarded node is suffering routing empty. If the predicted position does not match with the requirement of a greedy forwarding, it goes on with the perimeter forwarding mode, otherwise, it goes into a waiting mode, which means, after a minimal waiting time delay, it jumps back to the greedy forwarding mode, thus a large amount of redundancy in perimeter forwarding can be reduced. With simulation software Network Simulator version 2, a network environment is set up, in which, the end-to-end delay and the average hop count of the improved protocol and the original protocol is compared as the node speed varies in 10 ～ 40 m/s. Results show that, the improving methods can bring an reduce to the time delay of 5% ～ 17%, and to the hop of 5% around.

routing empty, greedy perimeter stateless routing protocol, Network Simulator

10.13682/j.issn.2095-6533.2015.04.003

2015-01-04

陕西省科技厅科学技术研究发展计划资助项目(2012K06-50)

张继荣(1963-)，女，博士，教授，从事现代通信网研究。E-mail:comnet@xupt.edu.cn 赵晓彤(1990-)，女，硕士研究生，研究方向为通信网技术与应用。E-mail:306967739@qq.com

TP393

A

2095-6533(2015)04-0016-04