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

良 梓 ，任哲坡 ，吴晓军 ，

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.