基于能量分级和位置预测的高效路由算法*

裴　芳,郑　莹，董龙明

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

基于能量分级和位置预测的高效路由算法*

裴芳1,郑莹2，董龙明3

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

针对车载传感器网络节点移动速度快、网络拓扑结构不稳定、终端传感器节点能量不确定性等特点，提出了一种能量分级和位置预测的高效路由算法ERLP（Energy Rank and Location Prediction based routing）。该算法根据具有不同能量等级的节点将消息传递距离的不同选择那些能量高的节点作为中转节点，并结合节点的分布区域和当前速度，尽量将多个消息副本传递给覆盖不同方向的节点，避免消息传递的局部性。仿真结果表明，与当前典型延迟容忍网络的路由算法相比，ERLP算法在传输成功率、平均延迟时间上具有较大提升。

车载传感器网络，能量分级，位置预测，路由算法

0　引言

车载传感器网络是一种新兴的技术，主要面向日益庞大的汽车用户群体,具有节点移动速度快、网络拓扑结构不稳定、车载终端传感器节点能量充足等特点。在传统的网络中，数据传输依赖于稳定的端到端连接，而车载传感器网络不可能存在一条完整的端到端路径，因此，传统的路由算法已经不再适用于车载传感器网络。为了解决车载传感器网络中移动节点间数据传输问题，出现了延迟-容忍网络DTN（Delay-Tolerant Network）［1-2］，一般采用“存储-携带-转发”的方式动态规划路由路劲，完成数据的传输。

国内外研究学者针对DTN网络特点相继提出了多种DTN路由算法，如：传染路由算法（Epidemic routing）［3］、PROPHET［4］、FAD［5］、SimBet［6］等。这些算法都是采用多复制路由策略实现DTN网络中消息的传递，将同一报文在移动网络中复制多次并发送到不同的节点中，通过增加复本数来增加消息传输的成功率和降低传输时延。这种方法消耗大量的带宽和移动节点的能量，在网络带宽和节点缓存资源充分的情况下可以获得较好的效果，但是移动传感器网络往往这些资源是有限的，会使网络的带宽开销特别大，随着节点的增多网络的性能急剧下降。王建新等人［7］针对多副本消息冗余问题以及消息扩散局部性问题，提出了一种基于副本限制和社会性的路由算法RACS，通过限制最大消息副本数来减少消息副本的冗余，在扩展中通过比较节点的中心性，使中心性较高的节点获得相对较多的消息副本，来完成消息副本的扩散和递交。但是，这种方法通过过去一段时间内所遇到其他节点个数距离计算中心节点的中心性，没有根据节点当前速度方向预测节点位置，可能多个中心性节点将来汇聚到某个区域，未能够避免消息传递的局部性。

本文根据车载传感器网络中具有不同能量等级的节点和消息传递距离的不同，选择那些能量高的节点，尽量将多个消息副本传递给覆盖不同方向的节点，尽可能地将消息传递给网络中其他区域，避免消息传递的局部性。

1　基于能量分级和位置预测路由算法

基于能量分级和位置预测的路由算法中，如何利用车载传感器网络中移动节点的通信能力和动态特性，选择最优的转发节点，在最少的延迟和带宽下把数据从源节点传输到目标节点，是路由算法的关键。

1.1节点能量分级模型

在车载传感器网络中，节点的能量等级决定了节点的通信能力和节点间的传送能力，能量等级较高的节点具有较强的信息传播能力，能让消息扩散到更远的节点，因此，选择能量高的节点作为转发节点比较合理。

车载传感器网络中，移动节点的能量可以多样，但一般都很有限，按照节点的类型可以分为多个等级：网络中中继节点一般具有较高的能量等级和较多的缓冲区单元，同时能够存储发送多个消息给较远的距离；一般传感器节点具有中等能量等级和有限的缓冲区单元，只能将消息转发给相邻单元；末端节点没有传输能量，只能接受其他节点传输的能量。车载传感器网络中存在大量的一般传感器节点，末端节点数量有限，为了提高网络传输效率，车载传感器网络一般设置有限的专门用来传输的中继节点，尽可能地理上均匀分布在车载移动网络中，减少了转发的次数，减少节点间传输的延迟。

车载传感器网络中，节点能量等级可以用EN表示，EN=｛0,1,2，…，max｝。可以根据网络中节点的类型，给所有节点赋予一个能量等级值，如下：

节点能量等级可以表示节点能够将消息传输的范围，每个en可以对应一个距离值Disen,表示在距离范围Disen内的目标节点能够接受到该消息。另一方面，节点能量等级en表示能将消息传输距离的能力，当节点选择转发节点时，节点的能量等级是一个重要的考核指标，可以使用en/max来衡量节点的中转能力。

1.2位置预测计算

车载传感器网络中的移动节点携带GPS模块，节点可以随时获取自己的位置信息和移动速度矢量，其位置可以通过广播形式使各个方向周围节点能够感知。

节点下一个时刻Δt的位置不仅与当前的位置有关，还与节点当前动态速度矢量有关。假设目标节点d的位置为：（xd，yd），速度为：v→d=＜x→d，y→d＞，源节点s的位置为：（xs，ys），速度为：v→s=＜x→s，y→s＞，可以得到源节点s和目标节点d的相对位置和速度：

Δxsd=xd-xs，Δysd=yd-xs。

Δvsd=-，各个分量上的相对速度分别为：

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

当Δxsd＞0时：

当Δxsd＜0时：

源节点在选择中转结点时，应该考虑在将来的方向上选择越来越远的节点作为中转结点。

距离因素Dsd可以使用下面公式表示：

速度因素Vsd可以使用下面公式表示：位置综合因素可以使用公式，位置综合因子α取值的大小表示位置预测是速度主导还是距离主导。移动节点如果网络分布距离不是很远，节点移动平凡速度比较快，α取值比较小，一般为：0.2；移动节点如果网络分布距离很广，移动速度比较慢，α取值比较大，一般为：0.8。

1.3算法描述

算法ERLP能够将网络中数据以最快的方式扩散从源节点转发给目标节点，在进行数据转发前，根据中转节点的能量和位置预测信息进行综合分析，选择最优的转发节点d，尽量将数据扩散到网络其他区域。节点d的综合传递能力Q（d），计算方式如下：。

平衡因子β取值的大小表示能量分级因素和位置预测因素所占的比重，β一般取值为：0.5。算法的基本原理是：源节点s需要将消息m传递给目标节点d，当前，节点s通信范围内有若干相邻节点，首先节点通过广播和简单的握手收集相邻节点的通信信息，包括：相邻的节点能量等级ei/max、节点的位置、速度等信息，然后计算相邻节点的综合传递能力，选择最优的相邻节点传递消息，接收到消息的中转节点将消息传递给下一个节点，直至将消息传递给目表节点d。

该算法伪代码描述如下：

2　仿真实验及结果分析

本文采用基于Java的DTN仿真工具ONE（Opportunistic Network Environment）［8］进行仿真实验。仿真环境区域面积为：18 000 m×18 000 m，整个网络由100个移动节点组成，节点的速度区间为：5.6 m/s～33 m/s，相当于汽车等交通工具的速度，节点的通信半径为：0 m～250 m，根据50 m共分为5个能量等级，传输消息大小为：100 kB～500 kB。实验中，位置综合因子α=0.8，β=0.5。

对ERLP算法进行仿真，选取与经典的算法Epidemic和多副本的社会网络SimBet路由算法进行比较，分别从传输成功率和平均延迟进行性能比较。

图1　不同缓存下传输成功率

图2　不同缓存下平均延迟时间

图1和图2分别表示在不同的缓存情况下，节点的传输成功率及传输平均延时。由图可知：由于ERLP路由算法根据节点的能量等级及位置预测综合传输效能选择性地选取传输节点，减少了节点的转发次数，能更迅速地扩散消息到不同区域，提高了消息传输成功率，并且减少了传输延时。

3　结论

本文针对车载传感器网络节点移动速度快、网络拓扑结构不稳定、终端传感器节点能量不确定性等特点，提出了一种能量分级和位置预测的高效路由算法。该算法选择能量等级高的节点作为中转节点，并结合节点的分布区域和当前速度，尽量将多个消息副本传递给覆盖不同方向的节点，避免消息传递的局部性。仿真结果表明，与当前典型延迟容忍网络的多副本路由算法相比，有更好地适用于车载传感器网络的特点，在消息传输成功率和平均延迟时间上具有较好的效果。建立各种实际特定应用的车载传感器移动自组织网络模型是下一步研究重点。

［1］F K，F S.DTN：An architectural retrospective［J］.IEEE Journal on Selected Areas in Communications，2008，26（5）：828-836.

［2］肖明军，黄刘生.容迟网络路由算法［J］.计算机研究与发展，2009，46（7）：1065-1073.

［3］MUSOLESI M，HAILES S.Adaptive routing for intermittently connected mobile ad hoc networks［C］//Proceedings of WOWMOM'2005.Taormina：IEEE Computer Society Press，2005：813-820.

［4］LINDGREN A，DORIA A，SEHELEN O.Probabilistic routing in intermittently connected networks［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2003，7 （3）：19-20.

［5］WANG Y，WU H.Analytic，simulation，and empirical evaluation of delay-fault-tolerant mobile sensor networks［J］.IEEE Transactions onWireless Communications，2007，6（7）：3287-3296.

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

［7］王建新，朱敬，刘耀.基于副本限制和社会性的延迟容忍网络路由算法［J］.华南理工大学自然学报（自然科学版），2009，37（5）：84-89.

［8］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.

Efficient Routing Algorithm based on Energy Rank and Location Prediction

PEI Fang1，ZHENG Ying2，DONG Long-ming3
（1.Hunan Mechanical and Electrical Polytechnic，Changsha 410151，China；2.Changde Vocational Technical College，Changde 415000，China；3.Nanjing Military Representative Office of PLA Army，Nanjing 210000，China）

Nodes move rapidly，the topology of network is instable and energy of terminal sensors cannot be undetermined in the vehicular sensor networks.An efficient routing algorithm is proposed based on energy rank and location predication.Nodes with different energy can transfer messages to ones in the different distance.So，the algorithm chooses nodes with high energy as transfer ones.Also，the algorithm transfers message copies to nodes of different direction according to their distributed region and current speed and can overcome the local message transmission.In the end，the simulation results show that compared with other routing algorithms of delay-tolerant networks，our algorithm performs better on transmission rate and mean delay time.

vehicular sensor networks，energy rank，location predication，routing algorithm

E911

A

1002-0640（2016）07-0014-04

2015-06-05

2015-07-07
*

湖南省教育厅基金（13C258）；湖南省常德市科技局基金资助项目（2014JF11）

裴芳（1977-），女，湖南常德人，硕士，副教授。研究方向：无线传感器网。