DTN中基于时间因素的拥塞感知路由算法

2015-02-24 05:13任哲坡吴晓军
计算机工程与应用 2015年5期
关键词:保存率报文路由

良 梓 ,任哲坡 ,吴晓军 ,

1.陕西师范大学 计算机科学学院,西安 710062

2.西北工业大学 自动化学院,西安 710072

1 引言

延迟容断网络[1](Disruption Tolerant Network)的概念由美国国防部高级研究局DARPA在2004年提出,主要研究Internet交互式应用协议,来解决Internet通信时连接频繁断开的问题。Kevin Fall等科学家在SIGCOMM会议上首次提出DTN架构,它是一种位于区域网络(各种不同类型的网络,包括因特网)之上的覆盖网,以克服受限网络环境[2-4]中网络断开频繁、延迟高和异构性强[5]等问题。

在DTN网络中,网络节点的移动性强且缓存资源有限,网络拓扑结构呈动态变化[6],通常不存在一条完整的端到端路径,这导致网络存在传输延迟大,投递效率低等问题[7]。因此,传统路由协议不能在DTN网络中取得理想效果,DTN路由协议的研究,对提高DTN网络性能具有重要意义。

2 问题描述

目前,在DTN的研究中,路由算法主要分为单拷贝路由协议[8]和多拷贝路由协议。典型的单拷贝路由协议有Direct Delivery和First Contact,这两种路由协议虽然网络开销小、能耗低,但报文到达信宿节点的延迟大、概率低,无法保障网络性能。多拷贝路由协议中最具代表的路由协议有蔓延路由(Epidemic)[9]、散发等待路由(Spray and Wait)[10]和概率路由(Prophet)[11]。蔓延路由采用多副本洪泛机制传递报文,源节点对报文的下一跳节点的选择不做任何限制,其缺点是会导致网络中存在大量冗余副本。散发等待路由限制了转发的报文副本数量,避免了冗余报文的传输,但在转发报文时,直接将报文转发给最先遇到的节点,具有一定盲目性。概率路由基于节点相遇的历史信息定义转发概率,通过转发概率来选择下一跳节点,对下一跳节点给定一定的限制,但转发概率并不能完全代表报文实际递交的概率,节点相遇并不一定能保证报文转发成功。

针对上述存在的问题,目前已有一些改进算法。如文献[12]依据节点之间的历史接触成功率获取网络状态信息,在转发决策时引入接触成功率的影响,降低网络开销,文献[13]采用根据节点能量消耗改进转发概率,降低传输延迟,文献[14]根据节点间相遇概率对节点进行分簇,提出簇间转发算法,提高了消息投递率。但这些算法都不能在降低网络延时和开销的同时提高网络投递率。本文从时间因素的角度进行如下分析。首先,报文传输是需要一定时间的,节点的移动会导致正在传输的报文中断,所以,转发概率还需考虑节点相遇持续时间对报文完整传递的影响。另外,时间因素对网络拥塞也有一定影响,因为对于某些数据包会存在以下两种情况:一种是该包传输延时大,即节点间断开持续时间长,被成功传递的可能性小;另一种是经本节点的路径很难达到目的地,导致该包跳数较多,已生存时间较长。以上两种情况中的数据包都应该被丢弃。因此,可以通过计算节点断开持续时间、节点本身蕴含的跳数值和TTL值等信息来定义一个报文保存率,在网络拥塞时,通过该报文保存率衡量报文被保存的价值,以拥塞感知自适应的方式来优化路由算法。基于以上分析,本文结合概率路由和散发等待路由的各自优点,提出基于时间因素的拥塞感知路由算法(Congestion-Aware Routing Algorithm based on time factor,CARA 路由算法)。

3 CARA路由算法

3.1 算法思想

CARA算法采用改进的转发概率来进行路由选择,以拥塞感知自适应的方式进行拥塞控制。主要改进有以下三方面:

(1)报文转发方式。CARA算法中,节点之间转发报文的条件由转发概率确定。为提高估算精准度,估算传输概率时考虑时间因素对转发概率的影响,优先选择转发概率较高的节点作为中继节点。

(2)报文转发数目。报文转发数目按照转发概率动态分配。节点转发概率越高,获得的报文数目也越多,反之,则获得的报文数目越少。

(3)拥塞控制。CARA算法中,根据节点断开持续时间、节点的跳数(Hopsm)、TTL值来定义报文保存率,衡量报文应被保存的价值大小。在报文转发过程中,先进行拥塞检测,若无拥塞,则转发报文;若拥塞,则执行拥塞避免,依次丢弃报文保存率小的报文,缓解拥塞,再转发报文。

3.2 路由过程

3.2.1 改进的转发概率

概率路由是根据节点历史相遇信息来预测节点移动方式,在节点相遇时,交换拥有相遇概率信息的摘要矢量,然后选择下一跳转发的节点[10]。本文将该算法进行改进,考虑节点相遇持续时间对转发概率的影响,通过分析两个节点建立连接的方式,定义需要提取的时间参数。

定义1(相遇时间)节点A和B在0时刻从初始位置开始移动,它们第一次到达对方通信范围内所需要的时间。

Sa(t)表示节点a在t时刻在网络中的位置,K是节点通信范围。

定义2(相遇持续时间)节点A和B最初在信息通信范围之外,假设在0时刻,到达对方的通信范围内,这两个节点在移出通信范围之前保持联系的时间为相遇持续时间。

定义3(相遇间隔时刻)在0时刻节点A和B在对方通信范围之内,在t1时刻移出通信范围,定义相遇间隔时刻为t1。

定义4(断开持续时间)A和B两节点再次到达对方通信范围需要的时间。

改进的转发概率变化公式分三种:概率更新公式、衰减公式和传递公式。

(1)概率更新公式:

(2)概率衰减公式:

(3)概率传递公式:

按照上述转发概率的变化,节点维护一张转发概率表,根据此表选择下一跳节点。

3.2.2 散发阶段

(1)S(源节点)要发送消息到目的节点R,S初始化报文拷贝数L(L>1)。

(2)S(或中继节点A)与中继节点B相遇时,更新各自摘要矢量并计算转发概率,PSR(S到达目的节点R的概率)<PBR(B到达R的概率),则S将报文转发给B,如果PSR≥PBR,则不转发,继续寻找下一节点。

(3)S报文数目为L,转发给节点B的报文数目为L′,若L>1,L′=PSR⋅L。

(4)判断是否发生拥塞,如拥塞,则进行拥塞避免,如无拥塞,数据发送成功。

3.2.3 等待阶段

(1)判断散发阶段是否与信宿节点相遇,若遇到,则递交报文,终止传输;若没遇到,按上述方式选择中继节点,继续散发报文。

(2)随着报文的散发,报文副本数减小。若当前中继节点上该报文副本数为1,则进行(3),若副本数不为1,继续散发,进行(2)。

(3)不再散发报文,直到该节点遇到信宿节点时才递交,即转为直接传输模式。

(4)判断是否发生拥塞,如拥塞,则进行拥塞避免,如无拥塞,数据发送成功。

3.2.4 拥塞检测及避免

定义5(报文保存率)反映报文应被保存的价值大小。

报文保存率见公式(9):

其中,公式(9)中w1,w2为权重系数,Qm为报文m的质量,Zm为报文m的生存时间分量。公式(10)中N表示全网节点数,Hopsm表示报文m的转发次数,即跳数。公式(11)中TTL为报文m的生存时间,δab为断开持续时间,可由公式(3)、(4)求出。由公式可见,Hopsm越大,TTL越小,δab越大,Pm越小,报文保存率越小,可被成功投递的可能性就越小。当网络拥塞时,丢弃报文保存率小的报文缓解拥塞。

拥塞策略流程如图1所示。

图1 拥塞策略流程

4 仿真及性能分析

4.1 仿真参数

为了检验CARA算法的有效性,本文采用离散事件模拟器ONE[15](Opportunity Networking Environment)对CARA算法进行仿真。本文采用ONE中自带的芬兰首都赫尔辛基(Helsinki)地图[16],仿真场景大小为4 500 m×3 400 m。仿真网络共126个节点,分为6组,第一、三组为行人节点,第二组为出租车节点,第四、五、六组为有轨电车节点,具体如表1所示。消息大小为350 kB,传输速率250 kB/s,仿真时间20 h,数据包产生间隔时间30~40 s,采用基于地图路径方式[17-18]移动。实验仿真参数见表1。

表1 实验仿真参数

4.2 仿真结果及分析

为了全面验证CARA算法,本文通过仿真实验,将Prophet算法、二分散发等待路由(BSW)算法、Epidemic算法、CS-DTN[14]同CARA算法相比较,分析在报文递交率、平均延迟及网络开销率三方面[19-20]随时间的变化情况。

(1)报文递交率

报文递交率可以衡量路由算法对报文的传递能力,其定义如下。

实验结果如图2所示。从图2中可以看出,Epidemic算法在起始阶段递交率高,增加速度快,但到10 000 s之后,开始逐渐降低,这是由于Epidemic算法的洪泛机制易使网络拥塞所致。图中还可以看出,CARA算法比Prophet算法、CS-DTN算法的递交率都有了明显提高,这是由于本文在Prophet算法的基础上考虑了节点持续连接时间对递交概率的影响,同时,拥塞感知策略丢弃了节点缓存中保存率小的报文,使到达目的节点可能性高的报文得以保存和转发,从而提高了全网报文递交率。

图2 递交率随时间的变化

(2)平均延迟

平均延迟用来衡量算法的性能,其定义如下。

实验结果如图3所示。从图3中可以看出,Epidemic算法的平均延迟开始较低,但随时间的增加延迟逐渐增大,这是因为Epidemic算法的洪泛机制导致节点处报文拥塞无法递交,而使得延迟增大。Prophet算法、CS-DTN算法同CARA算法相比,CARA算法延迟要小于前两个算法。这是因为CARA算法限制了对中继节点的选择,使报文转发概率不会随节点之间相遇频率的增加而增加,所以延迟逐渐增加,但随着时间的增加,这种增加的趋势逐渐减小,平均延时趋于稳定。这是由于CARA算法中采用拥塞感知机制,抛弃那些持续断开时间很长的报文,使得全网平均延迟变小。

(3)开销率

开销率可以用来衡量路由算法的总体传输性能,其定义如下。

实验结果如图4所示。从图4中看出,Epidemic算法开销最大,这是因为Epidemic算法的洪泛机制使报文递交效用低,所以开销大。BSW算法在源端限制报文拷贝数,所以其开销率小且稳定。从图4中可以看出,CS-DTN算法比BSW算法的开销大,这是因为CS-DTN算法中,消息不断地向中心性高的节点累计,簇间的转发导致开销大。而CARA算法开销最小,这是因为CARA算法合理地丢弃冗余报文,增大了成功递交数据包数量,减小了网络中冗余报文的存储和转发,进而减小网络开销。

图4 开销率随时间的变化

5 结语

本文分析了时间因素对路由选择和网络拥塞的影响,提出了一种基于时间因素的拥塞感知路由算法CARA。考虑节点相遇持续时间对报文完整传递的影响,改进了传统概率路由的转发概率,根据改进的转发概率动态分配转发报文,同时定义报文保存率来衡量报文的保存价值,以拥塞感知的方式实现拥塞控制的优化。实验表明,与其他算法相比,CARA算法在降低网络延迟和开销,提高网络投递率上,优越性明显。

[1]Fall K.A delay tolerant network architecture for challenged Internets[C]//SIGCOMM,2003:27-34.

[2]Nichols R A,Hammons A R.DTN-based free-space optical and directional RF networks[C]//Military Communications Conference,2008:1-6.

[3]Luo Peien,Huang Hongyu,Li Minglu,et al.Performance evaluation of vehicular DTN routing under realistic mobility models[C]//Wireless Communications and Networking Conference.Las Vegas,NV:[s.n.],2008:2206-2211.

[4]Chan C Y M,Motani M.An integrated energy efficient data retrieval protocol for underwater delay tolerant net-works[C]//IEEE Oceans.Washington DC:IEEE,2007:1-6.

[5]樊秀梅,单志广,张宝贤,等.容迟网络体系结构及其关键技术研究[J].电子学报,2008,36(1):161-170.

[6]Daly E M,Hahr M.The challenges of disconnected delay tolerant MANETs[J].Ad Hoc Networks,2010,8:241-250.

[7]Whitbeck J,Conan V.HYMAD:hybrid DTN-MANET routing for dense and highly dynamic wireless networks[C]//IEEE WoWMoM Workshop on Autonomic and Opportunistic Communications,2010.

[8]Jain S,Fall K,Patra R.Routing in a delay tolerant network[C]//Proceedings of the 2004 Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications,NewYork,2004:145-158.

[9]Vahdat A,Becker D.Epidemic routing for partially connected ad hoc networks[R].San Diego:University of Carolina,2000.

[10]Spyropoulos T,Psounis K,Raghavendra C.Spray and wait,an efficient routing scheme for intermittently connected mobile networks[C]//WDTN’05,2005:252-259.

[11]Lindgreny A,Doria A,Schelen O.Probabilistic routing in intermittentlyconnectednetworks[J].ACM SIGMOBILE Mobile Computing and Communications Review,2003,7(3):19-20.

[12]付凯,夏靖波,尹波.DTN中一种网络状态感知的概率路由算法[J].小型微型计算机系统,2013,34(1):145-149.

[13]刘唐,彭舰,杨进.异构延迟容忍移动传感器网络中基于转发概率的数据传输[J].软件学报,2013,24(2):215-229.

[14]张振京,金志刚,舒炎泰.基于节点运动预测的社会性DTN高效路由[J].计算机学报,2013,36(3):626-635.

[15]TKK/COMNET.Project page of the ONE simulator[EB/OL].[2012-12-11].http://www.netlab.tkk.fi/tutkimus/dtn/theone.

[16]Keranen A,Ott J,Karkkainen T.The ONE simulator for DTN protocol evaluation[C]//Proceedings of the 2nd International Conference on Simulation Tools and Techniques,2009:1-10.

[17]Keranen A,Ott J.Increasing reality for DTN protocol simulations[R].[S.l.]:Networking Laboratory,Helsinki University of Technology,2007.

[18]Peng Min.Research on mobility model and routing in delay tolerant network[D].Hefei:University of Science and Technology of China,2010.

[19]Ahmed S,Kanhere S.Cluster-based forwarding in delay tolerant public transport networks[C]//Proceedings of the 32nd IEEE Conference on Local Computer Networks,2007:625-634.

[20]Li Yun,Chen Xinjian,Liu Qilie,et al.A novel congestion controlstrategy in delay tolerantnetworks[C]//IEEE 2010 2nd International Conference on Future Networks,China,2010:233-237.

猜你喜欢
保存率报文路由
基于J1939 协议多包报文的时序研究及应用
阜新矿区矸石山适生树种分析
不同因素对林下参保存率的影响
CTCS-2级报文数据管理需求分析和实现
浅析反驳类报文要点
探究路由与环路的问题
ATS与列车通信报文分析
PRIME和G3-PLC路由机制对比
WSN中基于等高度路由的源位置隐私保护
eNSP在路由交换课程教学改革中的应用