基于活跃度和任务的目标导向VANETs路由算法*

李文芳，董龙明，郝丽波，李宏策

（1.湖南机电职业技术学院，长沙 410151；2.陆军驻南京地区军事代表室，南京 210000）

基于活跃度和任务的目标导向VANETs路由算法*

李文芳1，董龙明2，郝丽波1，李宏策1

（1.湖南机电职业技术学院，长沙 410151；2.陆军驻南京地区军事代表室，南京 210000）

针对车载自组织网络（VANETs）中节点移动速度快、节点任务分布不均、网络拓扑结构不稳定等特点，提出了一种基于节点活跃度和任务的目标导向VANETs路由算法GATRA（goal-oriented routing algorithm based on activity and task）。该算法根据当前运动节点的运动方向与目标节点的关系，以及任务饱和程度，综合考虑采用消息携带还是转发策略，以节约传输平均时延。在选择中继节点时，综合考虑邻接节点的位置、运动速度和方向等影响因素，设计节点活跃度的计算方法，作为选择中继节点的策略，从而提高了消息传输的成功率。仿真结果表明，与当前典型的VANETs路由算法相比，GATRA算法在传输成功率和平均延迟时间上具有较大提升。

车载自组织网络，目标导向，活跃度，路由算法

0 引言

车 载 自 组 网 （Vehicle Ad-Hoc Networks，VANETs）是移动网络领域一种新兴的技术，主要面向日益庞大的汽车用户群体，可以实现车与车、车与路边基础设施进行通信，从而实现信息共享，有助于事故预警、交通信息查询等多种应用［1］。与传统的网络相比，VANETs具有节点移动速度快、节点任务分布不均、网络拓扑结构不稳定等特点，因此，传统的路由算法难以适用于VANETs。另外，由于VANETs应用环境变化多端，车辆所承担的任务和运动速度方向随时间、地点变化而变化，从而导致车辆的分布密度和连通性呈机会性。VANETs这些新的特征给提供数据稳定可靠保证的路由算法设计带了极大挑战。

国内外研究学者针对VANETs车辆节点这些动态特性分别对路由策略进行相关的研究，根据网络特性可以分为5类路由算法：基于连通［2］、基于概率［3］、基于移动预测［4］、基于固定设施［5］和基于地理位置［6-7］。基于连通路由是采用广播的方式，通过节点广播传递数据包，直至数据传递到目的地才停止广播，该泛洪路由控制策略相对简单，易实现、操作性强，但是会增加网络负担，容易形成网络广播风暴，网络数据传输效率极低。基于概率的路由算法是针对VANETs拓扑结构动态变化，利用通信呈现机会性，结合概率统计理论，通过计算无线链接可用时间分布，建立网络传播模型，进行数据传输。基于移动预测是采集节点诸如速度、方向、加速度等运动特征，建立预测移动模型，进行数据传输。基于固定设施是将路边基础设施作为通信的中继节点，提供数据传输的可靠性。基于地理位置路由是根据节点的位置信息，选择不同策略进行贪婪转发和周边转发两种模式，具有高效、低路由开销和良好的可扩展性。

在VANETs的路由协议中，基于位置信息的贪婪路由算法是目前最为普遍采用的方法，如：贪婪周边无状态路由GPSR（Greedy Perimeter Stateless Routing）［8］和贪婪周边协调路由GPCR（Greedy Perimeter Coordinator Routing）［7］，选择离目标节点最近且距离自身最远的邻居节点作为下一跳进行路由转发，这种方法的优点是每一跳传递距离最远，能减少转发的跳数，其缺点是没有考虑转发节点的状态，如活跃度和承担任务情况，可能导致数据包的丢失。

本文是在贪婪路由算法基础上，在移动节点上设置一定大小的缓冲区来存储携带一定数量的数据，如果节点当前任务不是很饱满，且节点运动方向是与数据包目的地址一致，则采用携带策略，否则综合考虑邻接节点的位置、运动速度和方向等影响因素，设计节点活跃度的计算方法，作为选择中继节点的策略。这种方法能够一方面有效减少数据传输的中转跳数，节约传输时延；另一方面，传输和转发是以目标为导向，综合节点承担的任务情况，合理选择存储和转发策略，保证消息传输的成功率。

1 基于活跃度和任务的目标导向路由算法GATRA

基于活跃度和任务的目标导向路由算法中，如何根据VANETs节点任务饱和程度选择合适的数据传输策略，如何根据邻居节点的活跃度选择最优的中转节点，将数据从源节点传输到目标节点，是路由算法的关键。可以量化表示为其中：l为当前节点携带的消息个数，L为节点缓冲区的大小，τ∈[0，1]。τ取不同值时，可以描述节点承担任务的繁重程度，从而采取不同的策略：

当τ∈[0.8，1]时，节点承担通信任务很重，一旦有邻居节点就需要将携带的消息转发出去；

当τ∈[0.5，0.8]时，节点承担通信任务适中，有方向一致的邻居时将携带的消息转发出去，同时可以接受方向一致的中转消息；

当τ∈[0，0.5]时，节点承担通信任务很少，可以存储待发消息和接受其他节点的消息。

车载移动节点通过环境预测和传输日志可以对目标的位置和运动速度进行预测，判断目标的方位，并与当前位置和运动速度进行对比，对目标导向路由算法进行量化，使数据朝目标方向进行传输。

可以根据 Δxsd和的值判断目标节点与节点的将来距离情况。节点在x轴方向上距离和速度表示含义如下，节点在y轴方向上距离和速度同x轴方向。

当 Δxsd＞0 时：

1.1 携带-中转策略

车载自组网中，为了保证消息可靠传输，车载移动节点设置一定的缓冲区，用来暂时存储待发或接受的数据。当周围环境有合适的相邻节点时，发送这些数据，可以节点处在孤立的环境或者周围节点通信任务过重无法中转数据时，保证数据不丢失。携带-中转策略除了考虑结点周围环境因素外，还需要考虑消息目的地址与节点运动方向的关系，当运动方向与目标一致时，可以携带该消息，可以确保减少消息中转的频次，减少节点间传输的延迟，同时减少了中转过程消息丢失的可能性，提高了消息投递成功率。

定义1任务Task刻画了节点携带消息的多少，

当 Δxsd＜0 时：

定义2目标导向Goal刻画了当前节点距离目标节点的程度，使用公式如果g∈[-1，0]表示节点在整体效果上距离目标节点越来越近；如果g∈[0，1]表示节点在整体效果上距离目标节点越来越远。

根据本节点和邻居节点的任务因子和目标导向因子值，节点可以决策采用消息携带策略还是中转策略，流程图如图1所示。

1.2 中转节点选择策略

中转节点的选择不但可以影响消息是否能传输成功，同时还能影响路由算法的效率。因此，选择合适的中转节点在路由算法中尤其重要。节点在选择邻居节点中转消息时，当出现多个邻居节点可供选择时，需要一个合理的中转节点选择策略，选择最合适的节点数据传输，考虑的因素有：邻居节点的任务因子和目标导向因子。

定义3 活跃度Activity刻画了节点相对目标节点的活跃程度，包括接受数据传输的能力和运动特性，描述了节点将消息传输到目标节点的容易程度，可以量化表示为其中：τ为节点的任务因子，g为节点的目标导向因子，ε为权重因子。

图1 携带-中转策略流程图

1.3 算法描述

综上分析，本文提出的GATRA路由算法具体描述如下：

①节点首先根据发送消息预测目的节点的位置、运动特性，如果能够直接发送目的节点，则发送该消息到目的节点，从缓冲区删除该消息，该轮询结束；否则，结合自身的缓冲区情况、位置、运动特性，求得任务因子和目标导向因子。

②根据任务因子的值和感知的邻居节点情况，决策采用中转还是携带策略，如果是携带策略，存储该消息，继续运动等待下一轮询；否则，进入③。

③当时采用中转策略，收集相邻节点的当前任务因子和位置运动特性，求得相邻节点的活跃度，选择活跃度最大的节点作为中继节点，转发给消息。该算法伪代码描述如下：

2 仿真实验及结果分析

本文采用基于Java的DTN仿真工具ONE（Opportunistic Network Environment）［9］进行仿真实验。仿真环境区域面积为：15 000 m×15 000 m，整个网络由50个～200个移动节点组成，节点的速度区间为：0 m/s～50 m/s，相当于汽车等交通工具的速度，节点的通信半径为：0 m～250 m，传输消息大小为：100 KB～500 KB，权重因子 ε=0.2。

图2 平均端到端时延比较

从图2中可以看出：当节点个数增加时，3种协议平均端到端时延变化的比较。当节点个数增多时，连通性更好，平均时延在减少，由于GATRA路由算法采用目标导向的路由算法，在选择路由策略时尽量向目标运动方向的节点传递节点。图3显示了数据成功递交率在不同节点数的情况比较，相比之下，可以看出：GATRA路由算法数据投送成功率在85%之上，由于GATRA路由算法针对不同情况采取不同的中转-携带策略，减少了消息的丢失，提高了消息的递交成功率。

图3 数据成功投递率比较

3 结论

本文针对车载自组织网络节点移动速度快、节点任务分布不均、网络拓扑结构不稳定等特点，提出了一种基于活跃度和任务的目标导向VANETs路由算法。充分考虑了节点的活跃度和当前数据传输任务情况，选择任务不是很饱满、运动方向与目标移动方向一致并活跃度高的节点携带或中转数据，保证了路由策略的最优化。通过仿真实验验证：该算法在数据传输中具有较高的数据递交成功率和较少的时延。各种实际应用场景的车载自组网路由优化算法是将来下一步研究重点。

［1］PERKINGS C E，ROYER E M.Ad-Hoc on-demand distance vector routing［C］//Proc of IEEE Workshop on Mobile Computing Systems and Applications （WMCSA），2011：90-100.

［2］LI X，CUTHBERT L.On-demand node-disjoint multipath routing in wireless Ad-Hoc network［C］//Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks，LCN’04，Washington DC，USA，IEEE Computer Society，2004：419-420.

［3］JIANG H，GUO H，CHEN L.Reliable and efficient alarm message routing in vanet［C］//Proceeding of the 2008 International Conference on Distributed Computing Systems Workshops，ICDCSW’08，Washington DC，USA，IEEE Computer Society，2008：186-191.

［4］ABEDI O，FATHY M，TAGHILOO J.Enhancing AODV routing protocol using mobility parameters in vanet［C］//Proceedings of the 2008 IEEE/ACS International Conference Society，2008：229-235.

［5］HE R，RUTAGEMWA H，SHEN X.Differentiated reliable routing in hybrid vehicular Ad-Hoc networks［C］//IEEE International Conference on Communications （ICC），2008：2353-2358.

［6］KARP B，KUNG H T.GPSR：Greedy perimeter stateless routing for wireless networks［C］//Proc.of 6th Annual International Conference on Mobile Computing and Networking，2000：243-254.

［7］DALY E，HAAHR M.Social network analysis for routing in disconnected delay-tolerant MANETs ［C］//Proceddings of ACM Mobi-Hoc，2007：32-40.

［8］LOCHERT C，MAUVE M，FUSSLER H，et al.Geographic routing in city scenarios［J］.ACM SIGMOBLE Mobile Computing and Communications Review，2005，9（1）：69-72.

［9］KARP B，KUNG T H.GPSR：Greedy perimeter stateless routing for wireless networks［C］//Proceeding of the 6th Annual International Conference on Mobile Computing and Networking （MOBICOM’00），Boston，MA，USA，ACM，2000：243-254.

［10］KERANEN A，OTT J，KARKKAINEN T.The ONE simulator for DTN protocol evaluation［C］//SIMUTools’09：Proceedings of the 2nd International Conference on Simulation Tools and Techniques，New York，NY，USA，2009.

Activity and Task Based Goal-oriented Routing Algorithm in VANETs

LI Wen-fang1，DONG Long-ming2，HAO Li-bo1，LI Hong-ce1
（1.Hunan Mechanical and Electrical Polytechnic，Changsha 410151，China；2.Nanjing Military Representative Office of PLA Army，Nanjing 210000，China）

Nodes move rapidly and their tasks are unevenly distributed，the topology of network is instable in the vehicular ad-hoc networks.A goal-oriented routing algorithm （GATRA）is proposed based on activity and task.The algorithm chooses the carrying or forwarding of the messages，according to the saturation level of its task and the relationship between the movement direction of the current node and the target node.It can save mean delay time.When selecting a relay node，the computation of the node activity is designed as selection policy of the relay node，according to the impact factors such as the location，velocity and direction of the adjacent nodes.Hence，it can improve the success rate of message transmission.In the end，the simulation results show that compared with other typical routing algorithms，GATRA can performs better on transmission rate and mean delay time.

vehicle Ad-Hoc networks，goal-oriented，activity，routing algorithm

TP316.4

A

10.3969/j.issn.1002-0640.2017.07.026

1002-0640（2017）07-0119-05

2016-05-05

2016-06-07

湖南省教育厅高等学校科学研究项目（15C0491）

李文芳（1982- ），女，山西繁峙人，硕士，讲师。研究方向：自动控制与应用、高职教育。