一种可靠的GPSR改进算法在内河航道中的应用研究

袁学松，袁　涛，王　蒙，张　静

(1.安徽机电职业技术学院 信息工程系，安徽 芜湖 241000；2.合肥工业大学 计算机与信息学院，安徽 合肥 230009)



一种可靠的GPSR改进算法在内河航道中的应用研究

袁学松1,2，袁涛1，王蒙1，张静1

(1.安徽机电职业技术学院 信息工程系，安徽 芜湖 241000；2.合肥工业大学 计算机与信息学院，安徽 合肥 230009)

摘要：内河航道船舶之间采用高频、甚高频等方式进行信息交换，存在着干扰严重、成本昂贵等问题，为改善并丰富内河航道的通信模式，将城市交通中应用较为成熟的车载自组网(Vanet)技术引入到航道通信中，建立了可靠的端到端的船舶通信方式。针对传统的Vanet中GPSR(GreedyPerimeterStatelessRouting)路由协议相关算法易形成“空洞”、节点传输不可靠的缺点，提出了改进算法GPSR-CH(GPSRforChannel)。该算法通过增加可靠航标节点、改进Hello包结构、预测船舶的运动轨迹等方案大大增强了传输的可靠性。在内河航道模型环境下的仿真结果表明，GPSR-CH比经典的GPSR及其他几种改进算法有更低的分组丢包率和传输时延。

关键词：航道通信;Vanet；GPSR；GPSR-CH；航标节点

DOI：10.13757/j.cnki.cn34-1150/n.2016.02.017

近年来，内河航道事故频发，有的是因为小范围的极端天气(如2015年的“东方之星号”事件)，有的是因为船舶不熟悉水文情况而导致的船只相撞事故，这些事故如果能早期预警并干预是完全可以避免的。随着“车联网”技术的日趋成熟，设想若将车载自组网(Vanet)[1]中GPSR(GreedyPerimeterStatelessRouting)[2]的路由算法应用到船舶预警和船舶通信管理上并加以改进，必将丰富船载设备单一的通信模式，提高船舶的通信效率。目前，基于GPSR的改进协议已有不少，如GPSR-AD(GPSRBasedonAngleandDistance)[3]从节点的运动轨迹和相对运动角度来考虑如何选择下一跳节点并维护邻居节点信息，在多节点复杂拓扑环境中能有效解决“空洞”问题；NGPSR(NewGPSR)[4]协议在处理多障碍物对数据包传输的影响上也比经典的GPSR协议有更高的分组到达率；GPSRIP(GPSRImproveProtocol)[5]协议可以根据节点自身的运动规律和相关自身特征增加下一跳的位置预测，从而减少路由的开销，降低了节点间传输时延；GPSR-PV(GPSRBasedonPositionVector)[6]协议通过冗余链路撤销方案来缩小目的节点的选择范围，该算法能有效提高链路质量。本文针对内河航道问题，提出一种新的改进算法GPSR-CH(GPSRforChannel)，并做了传真实验。

1内河航道的相关问题描述

内河航道较城市路面有很多不同之处。例如，航道不存在城市路面的十字路口、城市建筑物障碍、红绿灯交通规则等问题，但航道中存在不同于城市路面相关航行的规则。本文针对航道的相关地理特性提出以下两个设计要点：

(1)船舶的路由节点丢失问题

当航行中的节点A要发送数据包时，首先会查找自己的路由表，得到离自己最近的下一跳节点B。如果该节点在船舶节点A通信的边缘地带且高速运动，则当A传给B时，B已经不在A的传输范围内了，这种情况就会导致链路断开问题。在GPSR或其他的改进算法中会使用周边转发的方法进行数据转发，但是在特殊的航道上有时可能没有其他的节点传输，这样就会导致A在一定时间内无法传输信息。

(2)航道模型下地理障碍问题

在内河中有很多特殊的航道，比如超过50°弯的航道、超宽航道、有江心洲的航道等，这些航道需要按照特殊的地理条件设置障碍物，在仿真过程中障碍物的正确设置与否直接影响仿真网络性能的准确性。图1是针对内河实际航道环境对GPSR、GPSR-AD等算法进行仿真实验的结果。

图1　3种算法在内河航道环境下的分组到达率

仿真结果表明，经典算法在内河航道中分组送达率较低，该指标反映数据包传输的可靠性，当节点数增加时，分组送达率下降非常明显。针对以上问题，本文提出一种新的改进GPSR算法。

2一种可靠的路由算法

GPSR-CH算法是改进的GPSR算法，它通过增加固定航标节点，修改节点间传输信标报文来维护航道中各船舶节点的邻居关系表，并使用经典贪婪转发算法建立路由，来创建一个可靠的传输过程。该算法的关键问题和算法实现如下。

2.1船舶节点和航标节点的信标设计

在GPSR协议中，通信节点需周期性地交流信标报文，通知邻居节点自身的信息。但标准的GPSR信标报文只包含各个节点的IP地址和由外部设备得到的地理位置信息,很显然这并不能满足船舶通信的需求。在GPSR-CH协议中将信标报文分成两类。

(1)固定航标节点报文

该节点需周期性向周围的区域船舶广播，由相关传感器获得水流速度、风速及相关信息。图2为航标节点的信标报文格式，该格式中的节点IP和节点位置均为固定值，由传感器得到的流速和风速均为矢量值，不仅有大小，还有速度的偏向角θ。

图2航标节点信标格式

(2)船舶节点信标报文

图3为船舶节点的信标报文格式。由于要预测在生存周期中的邻居节点，故在信标中添加了由自身得到的矢量速度。同时，由于可能出现的节点故障，将节点健康状况加入到报文中。在算法中要规避船舶相撞，故在信标报文中添加了节点安全距离的标识，船舶节点的安全距离为该船舶全长的一半，在每个节点中该值为固定值。

图3船舶节点信标格式

2.2船舶的邻居关系相关预测方法

在GPSR协议中，如果要防止由于节点(船舶)运动而产生的“空洞”现象，只能根据实际拓扑环境预测各节点的相对移动位置(虽然北斗系统由恶劣天气引起的信号衰减非常小，适用于内河航道系统，但北斗系统的二维水平精度为100 m,对于长江内河航道而言100 m误差不足以避免船舶相撞)。本文使用船载北斗系统获取其大致的经度、纬度和矢量速度等参数。同时，航标节点通过自身传感器获取矢量风速、矢量水流速度等参数广播给区域内的各船舶，船舶节点根据该信息结合自身的运动参数，对船舶移动性进行预测估算，并维护邻居节点，从而很好地维护各船舶节点的通信关系。

图4　船舶邻居关系预测

若L′R，说明Δt时刻后互为无效节点，则在维护彼此路由时，删除该邻居节点。当经过Δt时间后，L′

2.3GPSR-CH算法

GRSR-CH算法是根据移动船舶节点和固定航标节点来保持邻居关系的完整性，不会因为节点数目过少而产生断路，也不会因为节点运动速度过快而产生“空洞”。图5和图6分别为船舶节点和航标节点的数据包转发方案和邻居节点的维护方案。

图5 船舶节点转发方法图6 航标节点转发方法

算法具体可描述为

(1)船舶节点根据周期性广播Hello包来维护邻居节点，同时，发现邻居航标S并记录在路由表中。若目的节点在邻居表中，则进行相关数据包的转发。若目的节点不在邻居中则进行(2)操作；

(2)使用贪婪转发和周边转发策略对数据进行转发操作，并且每个节点都通过邻居表信息管理来维护自身邻居表，直至发送成功。若无邻居节点或经过预测邻居节点均为无效节点则进入(3)；

(3)传输给相应的邻居航标S,同时显示数据转发成功；

(i)航标S在收到源节点的信息后存储到闪存中，并寻找目的节点是否在自身的服务范围内，若在则直接转发，并回复源节点ACK信息。若不在自身的服务范围内则转至(ii)；

(ii)组播到拓扑中相应的航标Sn,Sn-1,Sn+1,…。各航标通过方法(i)寻找目的节点并传输，并回复源节点ACK信息，传输结束。

3仿真实验分析

为验证本文提出的GPSR改进算法的有效性，现通过NS-2仿真软件分析该算法的各种性能。为了更真实地反映航道情景，算法采用MOVE[8](Mobility Model Generator for Vehicular Networks)软件构建真实航道场景。

3.1船舶运动模型与航道模型的构建

在一般的航道上，船舶都不会过分集中运动在边界上，在考虑多种运动模型后，根据船舶的运动特点选择了高斯-马尔科夫移动模型[9]。各船舶节点运行均受到航道的制约，各节点的运动轨迹均不可逾越相应的航道，同时节点的信号传输也会遇到许多障碍物的影响。在图7中，由于航道的弯曲虽然船舶可能均在有效的通信范围内，但信号的传输受到了航道弯曲的影响，导致通信中断。本算法认为河道的弯曲和障碍物可以完全阻断信号传输，故航道模型采用了OM(Obstacle Mobility)[10]模型。

图7仿真场景局部图

本次仿真以真实的长江航道为依据，同时使用节点运动模拟器SUMO(Simulation of Urban Mobility)[11]仿真运动船舶节点。仿真场景为长10 km、宽2 km左右的弯曲河道，节点的传输范围为250 m，船舶航行速度范围为18.52-27.78 km/h，上下行航道均约为500 m，航标按照航道实际设计，约500 m设置1个，分组长度为512 B，流量类型为CBR，仿真时间为600 s，节点数由10-200逐渐增加。

3.2仿真结果与分析

本次实验主要从分组送达率、路由开销以及平均端到端延时等3个方面对GPSR-CH与GPSR、GPSR-AD以及NGPSR算法的性能进行比较，并分析这4个算法在内河航道真实场景中的性能，如图8-10所示。

图8　节点端到端平均延时

图9　节点的分组到达率

图10　节点的路由开销

由图8可知，当内河航道的船舶数量增加时，GPSR-CH、GPSR、GPSR-AD和NGPSR算法端到端的平均传输延时均有所增加。GPSR-CH算法由于增加了固定式航标节点，当节点增加时该性能指标优于其他算法。由图9可知，GPSR-CH算法的分组送达率在节点数增加时，始终保持在一个比较稳定的状态，而其他算法当节点增加可能会导致不可靠传输。由图10可知，随着船舶节点的增加，GPSR-CH算法的路由开销较大，这是由于为增加传输可靠性增加了很多冗余的航标节点。同时，在算法中加长了各类信标报文也会加重网络负担。但总体来看，随着节点增加，GPSR-CH的路由开销和经典GPSR算法相当，仍处于可控状态，但传输时延和丢包率大大减小。

4结束语

本文将GPRS改进协议应用在内河航道的船舶通信领域中，提出了一种新的GPSR-CH算法，该算法可以很好地保证数据的送达率，但由于增加了广播包并加长了与邻居节点通信的信标报文，路由开销性能与GPSR相当。仿真实验证明，GPSR-CH算法较其他类似算法更适合于内河航道的可靠数据传输，在现实的内河航道中有较大的应用价值。

参考文献:

[1] Liu Haiqing,Yang Licai,Ding Sijing,et al.Logical connectivity prediction models for VANET based on nonlinear regression and ELM: An example of the AODV protocol[J]. International Journal of Future Generation Communication and Networking, 2014, 17(6):.217-230.

[2] Karp B,Kung H T.GPSR: Greedy perimeter stateless routing wireless networks[C].ACM/IEEE International Conference on Mobile Computing and Networking, Boston Massachusetts USA, 2000 : 243-254.

[3] 李道全, 刘海燕, 曹齐光, 等. 基于地理位置的路由算法:GPSR-AD[J]. 计算机应用，2009, 29(12): 3215-3217.

[4] 张好. 动态车载自组网密钥管理方案的研究与仿真[D]. 北京: 北京邮电大学, 2014.

[5] 包伟阳. 基于地理位置的车载网络路由协议的研究[D]. 杭州: 杭州电子科技大学, 2012.

[6] 吴晶, 吴怡.基于位置矢量的GPSR改进协议[J]. 计算机应用, 2012,32(S2):.65 -67,72.

[7] 李超, 韩江洪, 魏振春, 等.VANET场景下的GPSR_R路由算法[J]. 合肥工业大学学报(自然科学版), 2015, 38(2): 181-185.

[8] Karnadi F K,Mo Z H,Lan K.Rapid generation of realistic mobility models for VANET[C]. Proc of IEEE Wireless Communications and Networking Conference 2007. Hong Kong, China,2007:2506-2511.

[9] Tolety V.Load reduction in ad hoc networks using mobile servers[D].Dept. of Mathematical and Computer Sciences，Colorado School of Mines,1999.

[10] Jardosh A,Belding-roger E M,Almeroth K C, et al.Towards realistic mobility models for mobile ad hoc networks[C]. MobiCom '03 Proceedings of the 9th annual international conference on Mobile computing and networking, ACM, NY, USA, 2003: 217-229.

[11] Smith D, Djahel S，Murphy J.A SUMO based evaluation of road incidents' impact on traffic congestion level in smart cities，Local Computer Networks Workshops (LCN Workshops)[C]. 2014 IEEE 39th Conference on Edmonton, AB, 2014：702-710.

StudyonApplicationofReliableGPSRRoutingAlgorithminInlandWaterway

YUANXue-song1,2，YUANTao1,WANGMeng1，ZHANGJing1

(1.DepartmentofInformationEngineering,AnhuiTechnicalCollegeofMechanicalandElectricalEngineering,Wuhu,Anhui241000,China；2.SchoolofComputerandInformation,HefeiUniversityofTechnology,Hefei,Anhui230009,China)

Abstract:Inthepastresearch,theinlandnavigationshipreliesonsatellite,highfrequencybandandveryhighfrequencybandradiocommunicationfordatatransmission.Inordertoenrichthecommunicationmethods,weestablishareliableend-to-endcommunicationforinnerriverships.InthispaperweintroducethematureVanettechnologyincitytrafficadhocvehiclenetwork.WefocusedontheGPSRroutineprotocolalgorithmsinVanet.Thetraditionalalgorithmiseasytoformholeandthetransmissionnodesarenotrobust.TheproposedalgorithmGPSR-CHcanimprovethereliabilitybyaddingnavigationindicationnodes,improvedHellopackagestructure,andpredictionofshipmotiontracks.Simulationresultsshowthat,theproposedalgorithmhaslowerpackageerrorrateandlowertransmissiondelayscomparedwiththetraditionalGPSRalgorithmanditsvariantsininlandnavigationchannelenvironment.

Keywords:channelcommunication;vanet;GPSR;GPSR-CH;beaconnode

* 收稿日期：2016-01-19

基金项目：安徽省教育厅2016年度高校领军人才引进与培育计划项目(gxfxZD2016324)和安徽省教育厅省级教学团队(2014jxtd99)。

作者简介：袁学松，男，安徽芜湖人，硕士，安徽机电职业技术学院信息工程系讲师，研究方向为网络仿真技术、无线传感网、数据挖掘。E-mail: ahjdyxs@126.com

中图分类号：TPT393

文献标识码：A

文章编号：1007-4260(2016)02-0072-05

网络出版时间：2016-06-08 12:57网络出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160608.1257.017.html