基于复制的DTN网络路由算法研究

从立钢，杨华民，王杨惠，底晓强

（1.长春理工大学计算机科学技术学院，长春　130022；2.长春理工大学化学与环境工程学院，长春　130022）

基于复制的DTN网络路由算法研究

从立钢1，杨华民1，王杨惠2，底晓强1

（1.长春理工大学计算机科学技术学院，长春130022；2.长春理工大学化学与环境工程学院，长春130022）

DTN是一种适用于挑战环境的新型网络，对长延迟、频中断等恶劣条件具有良好的适应性。目前，人们对于DTN网络的研究热点主要集中在传输协议、路由算法、安全防护等方面。本文针对基于复制的DTN路由算法展开研究，首先介绍了DTN的概念、结构、特点及应用，然后分析了四种典型路由算法的原理，最后利用仿真工具实现了对路由算法的仿真，并对不同条件下的算法性能进行了对比。实验结果表明，节点密度、节点缓存和数据包生存时间等网络因素对于算法的性能都有着显著影响，不同路由算法均有其特定的适用场景。

DTN；路由算法；网络仿真

DTN［1］是Delay/Disruption Tolerant Network的简写，被译为延迟/中断容忍网络，由于网络中断是造成延迟的重要原因，所以一般将中断容忍网络归为延迟容忍网络一类，所以DTN一般特指延迟容忍网络。DTN网络概念最早由DTNRG（Delay Tolerant Network Research Group，延迟容忍网络研究组）在2003年提出，试图通过DTN网络来解决星际网络频繁中断、时延大的问题。随后，在同年的SIGCOMM国际会议上，Kevin Fall发表了论文“A Delay-Tolerant Network Architecture for Challenged Internets”，该文章成为了DTN网络研究领域的经典。

图1　DTN网络体系结构

如图1所示，与传统网络结构不同，DTN网络在应用层与传输层之间添加了一个新层，即束层［2］（Bundle Layer），并制定了相应的束协议［3］（Bundle Protocol）。束层及相关束协议的出现，解决了DTN网络频繁中断、大延迟的问题，同时也为解决DTN网络与其他现有网络的兼容问题指明了方向。

1　DTN网络应用

DTN概念一经提出，便吸引了大量机构和研究者的关注，目前，DTN网络在空间激光通信［4］、星际网络［5］、野生动物研究［6］等众多领域都有广泛应用，其中比较典型的包括：（1）2012年10月，NASA与ESA（European Space Agency，欧洲航空航天局）合作，利用DTN技术在国际空间站实现了对地面实验室内乐高机器人的远程控制；（2）印度等国为解决边远地区网络无法覆盖的问题，利用DTN在部分地区建立了DakNet网络［7］，实现了偏远地区网络的覆盖；（3）水下延迟容忍网络项目SWIM［6］运用无线传感网络技术监视海洋鲸鱼，其中大量使用了DTN相关技术。

目前DTN网络的研究热点主要集中在应用/传输层协议、路由算法及协议、网络安全、仿真环境研究等方面。本文主要针对基于复制的DTN路由算法展开研究。

2　基于复制的DTN路由算法

DTN网络与传统TCP/IP网络在结构和运行环境上存在巨大差异，因此在路由上不能照搬TCP/IP的路由算法，为了解决这一难题，研究者提出了大量的DTN路由方案。根据机制不同可以被分成基于传播、基于场景、基于固定设施和基于移动设施四大类，其中基于传播的DTN路由算法又可以被分为基于复制和基于传播两类［8］，本文主要研究基于复制的DTN路由算法。

基于复制的DTN路由算法虽然有多种，但是基本思想都是将所要传递的消息复制多个副本，将这些副本传递给遇到的尚未携带相关信息的其他节点，通过多次消息复制过程，直到将消息交付给目的节点。常见的基于复制的路由算法包括Epidemic、MaxProp、PROPHET、Spray and Wait、SEPR、Controlled Flooding等，本文选取其中最具代表性的四种，它们是Epidemic、MaxProp、PROPHET和Spray and Wait，分别介绍四种其算法基本原理，并根据仿真结果分析算法性能。

2.1Epidemic路由算法

Epidemic路由算法由杜克大学的Amin Vahdat和David Becker在文献［9］中提出。如图2所示，Epidemic路由协议的基本过程分为三个阶段：

（1）当网络中任意两个节点A、B进入彼此通信范围后，节点A将其所存储的报文概要向量信息SVA（Summary Vector）发送给节点B；

（2）B节点获得SVA后，将自身所存储的报文概要向量信息SVB取反，并与SVA进行逻辑与操作，通过与运算结果B节点即可获知A节点拥有但自身不具有的报文信息，随后B节点将向A节点发送一个向量请求信息，要求A节点发送B节点不具备的报文信息；

（3）A节点获得请求信息后，将B节点请求的报文信息发送给B即可，此时节点B获得了A的信息。

图2　Epidemic路由协议信息交换过程示意图

2.2Spray and Wait路由算法

Spray and Wait路由算法最早由Thrasyvoulos Spyropoulos等人在国际会议SIGCOMM’05上首次提出。［10］该路由算法将数据报转发分成两个阶段，分别是Spray阶段和Wait阶段，每个阶段所采用的策略不同。

（1）Spray阶段：该阶段，数据源节点会产生L个数据报副本，并将L个副本发送给L个与源节点接触的中继节点；

（2）Wait阶段：如果没有在Spray阶段找到目的节点，则路由算法进入Wait阶段，在该阶段，每一个携带报文副本的节点将采用直接传输的方式传递消息，指导报文传递给目的节点。

Spray and Wait路由算法将Epidemic算法与直接传输路由算法相结合，利用了直接传输路由算法的简洁，同时限制了Epidemic路由算法对于资源的占用，集成了两种算法的优点。但是，对于Spray and Wait路由算法来说，确定Spray阶段的L值是整个算法的关键，如果L值过大，将增加系统的开销；如果L值过小，数据报的可达性会降低。在Spray and Wait路由算法基础上又改进出了Binary Spray and Wait算法，进一步提高了该算法的性能。

2.3PROPHET路由协议

PROPHET路由算法最早由瑞典吕勒奥理工大学的Anders Lindgren等人首次提出，［11］PROPHET是Probabilistic Routing Protocol using History of Encounters and Transitivity的缩写，该路由算法在Epidemic算法的基础上进行改进，引入投递概率值P（Delivery Predictabilities），避免泛洪似的数据分发方式，提高了网络的效率。PROPHET路由算法中对于P值得计算可以分成encounter、age和transitive三部分，分别使用三个公式用于更新投递概率值P，三部分的简要说明如下：

（1）encounter：当节点A、B相遇机会越来越频繁时，投递概率值P（a，b）也应逐渐变大，随着每次相遇将更新投递概率值，此时采用的计算公式为

其中Pinit为初始化参数，范围在（0，1］。

（2）age：如果A、B长时间未相遇，则需要定时更新P（a，b），该值将随着不相遇的时间变长而不断变小，此时采用的计算公式为

其中γ为一个常数，范围为（0，1），k为P值距离上次更新的时间单元数。

（3）transitive：如果A与B时常相遇，B与C又时常相遇，那么A与C之间存在传递性联通，则A与C之间投递概率值得计算公式为

其中β为放大常数，取值范围为［0，1］。

2.4MaxProp路由协议

MaxProp路由算法由美国马萨诸塞州大学的John Burgess等人在INFOCOM 2006上首次提出。［12］MaxProp路由算法引入了优先级对数据进行标记，优先级高的数据先发送，同样优先级低的数据先删除，这样大大提高了节点资源的利用率。

MaxProp路由算法由三部分组成，分别是相遇概率预估、数据交换管理和节点缓存管理。

（1）相遇概率预估部分用于计算网络中节点间信息传递的概率。在初始阶段将对每一个节点利用公式=1/（|s|—1）进行初始化赋值，该值代表该节点与相应节点进行信息传递的可能性，其中s代表一个DTN网络，任意一个节点i将信息传递给另一个节点j的概率记为。当i与j实际相遇时值将增1，并重新平衡概率值，使各节点概率值更新，接下来利用公式（4）计算源节点到目的节点的成本，在进行数据传递时选择成本较低的路径。

（2）数据交换管理发生在节点间进行数据交换的过程中，在节点间进行数据交换时首先交换向量链表，该链表其中包括节点相遇概率、源节点信息、目的节点信息等，在链表信息传递结束后节点根据已知的信息完成数据信息的传递，传递过程中根据阈值来判断数据包是否应该被发送，只有超过阈值的数据才被发送。

（3）节点缓存管理用来管理节点内存，在三种情况下节点可以删除内存中的数据，情况一：节点p中保存的数据包m已经被传送到目的节点，则m可以被删除；情况二：在数据报m的生命周期内，节点p与目的节点间没有够的带宽完成数据传输，则m可以被删除；情况三：即使节点P上的数据包m的副本被丢弃，该消息在其他节点上的副本也会被正常发送，则此种情况下m在p上的副本可以被删除。节点缓存管理正式以以上三种规则作为删除数据包的依据。

3　路由分析方法

3.1仿真工具简介

本文所使用的仿真工具为ONE［13］（Opportunistic Network Environment，机会网络仿真环境），该工具最早由芬兰赫尔辛基阿尔托大学的Ari Keränen和Jörg Ott等人利用Java编程语言开发，目前由芬兰阿尔托大学与德国墨尼黑工业大学共同维护，该工具在Windows、Linux和MacOS等平台上都可以编译运行。

3.2仿真场景设置与评估参数

本文的仿真场景为市区内行人所持智能手机所构成的DTN网络，每部智能手机都安装了类似于DroidDTN的DTN客户端。仿真场景主要参数如表1所示。

表1中的所有参数均在ONE仿真工具的配置文件中设置，除表中参数外，仿真的其他参数还包括网络节点数、路由协议、节点缓存等参数，这些参数将作为变量参与仿真，用于比较不同环境下的路由算法的性能。

表1　仿真场景设置

仿真工具ONE可以根据使要求生成相应的报告文件，报告中的主要参数包括created、dropped、delivery_prob、latency_avg以及overhead_ratio等，其中：delivery_prob（网络交付率）是指数据的成功到达率，即成功发送数据数量与产生数据总量的比值，该值越大代表性能越好；latency_avg（成功到达数据包的平均延迟）是指所有成功到达数据的延迟平均值；overhead_ratio（网络开销比率）由数据转发总数和数据成功到达数决定，转发总数越大，网络开销比率越大，相反成功到达数目越大，网络开销比率约小；以上三个参数可以比较全面的体现路由算法的具体性能，因此本文选择以上三值作为路由算法性能的评估依据。

4　仿真结果分析

4.1节点密度对路由算法性能的影响

本节研究节点密度与路由算法性能之间的关系。以表1仿真场景为基础，定义节点缓存为10M，消息生存周期为2h，通过修改节点数量，考察移动节点密度对于不同DTN路由算法性能的影响，实验结果如图3至图5所示。

图3　节点数量与传输成功率关系图

图3说明，在网络交付率方面，节点密度对于不同路由算法的影响不尽相同。对于MaxProp算法，随着节点数量的增加，其交付率显著提高；相反，对于Epidemic和PROPHET算法而言，节点密度的增加非但没有提高数据交付率，反而有所降低；而Spray and Wait算法的交付率对于结点密度并不敏感，随着节点密度的增加交付率并无较大波动。

图4　节点数量与平均时延关系图

图4说明，随着节点密度的增大，四种路由算法的数据包平均延迟均有所降低，其中Epidemic、PROPHET和Spray and Wait路由算法随着节点的增加其数据包的平均延迟趋于稳定；MaxProp算法数据包的平均延迟随着节点数量的增加持续降低。

图5　节点数量与路由开销率关系图

图5说明，Spray and Wait路由算法的路由开销与节点密度基本无关，在四种算法中一直保持较低水平；其余三种路由算法的路由开销随着节点密度的变大而持续增加，其中Epidemic和PROPHET两种算法的增加趋势最为明显。

4.2节点缓存大小对路由算法性能的影响

本节研究节点缓存大小与路由算法性能之间的关系。以表1仿真场景为基础，定义节点数量为300个，消息生存周期为2h，通过修改节点缓存大小，考察移动节点缓存大小对于不同DTN路由算法性能的影响，实验结果如图6至图8所示。

图6　节点缓存与传输成功率关系图

图6说明，网络交付率方面，在节点密度相同的条件下，Epidemic和PROPHET两种算法随着节点缓存的不断增加，其数据包的交付率也相应增大；节点缓存大小对于MaxProp路由算法的影响分成两个阶段，当缓存有5M变为10M，数据包交付率显著提高，但是从10M到30M，数据报交付率并无变化；对于Spray and Wait算法而言，节点缓存大小的变化对其数据包交付率并无影响。

图7　节点缓存与平均时延关系图

图7说明，随着节点缓存的变大，MaxProp路由算法数据包的平局延迟不断变小，当超过20M后平均延迟逐渐趋于稳定；Epidemic、PROPHET和Spray and Wait三种路由算法数据包平均延迟的变化随节点缓存变化不大。

图8说明，Spray and Wait路由算法的路由开销与节点缓存大小基本无关，一直保持较低水平；其余三种路由算法的路由开销随着节点缓存的变大均有所降低。

图8　节点数量与路由开销率关系图

4.3数据包生存时间对路由算法性能的影响

本节研究数据包生存时间与路由算法性能之间的关系。以表1仿真场景为基础，定义节点数量为300个，节点缓存为10M，通过修改数据包生存时间，分析数据包生存时间与DTN路由算法性能之间的关系，实验结果如图9至图11所示。

图9　数据包生存时间与传输成功率关系图

图9说明，在网络交付成功率方面，数据包生存时间的变化对于不同路由算法性能的影响并不一致。随着生存时间的增加，Epidemic和PROPHET两种路由算法的数据传输成功率不断降低；Spray and Wait算法的数据传输成功率则不断升高；对MaxProp算法而言，数据包生存时间的改变基本不会影响其数据传输成功率。

图10　数据包生存时间与平均时延关系图

图10说明，四种路由算法的平均时延在数据包生存时间增大初期均随之增大，但是随着生存时间持续变大，路由算法数据包平均时延的变化又有所区别，其中PROPHET和MaxProp算法的平均时延将逐渐稳定；Spray and Wait的平均时延将一直增大；当数据包生存时间超过一定值（150分钟）时，Epidemic的平均时延将出现降低趋势。

图11　数据包生存时间与路由开销率关系图

图11说明，MaxProp和Spray and Wait路由算法的路由开销率与数据包生存时间的大小基本无关；Epidemic和PROPHET路由算法的路由开效率随着数据包生存时间的延长不断变大。

5　结论

经过对不同条件下仿真结果的对比分析，主要得出以下结论：（1）网络环境对于DTN路由算法性能的影响较大，在进行DTN网络设计时应根据网络环境和设计目标选择合适的路由方案；（2）当节点较为稀疏时，Epidemic路由算法的性能与其他算法的性能较为接近，但是当节点变密时其性能急剧降低；（3）PROPHET路由算法的性能在大多数情况下强于Epidemic算法，但是并无出色表现，在各种条件下其数据传输成功率均维持较低水平；（4）MaxProp路由算法的性能在各种环境下均比较优秀，尤其体现在对于节点密度变化的容忍度上，无论节点密度增大还是减少，均保持了较高的数据传输成功率、较低的时延和较少的开销；（5）Spray and Wait路由算法对于网络环境也具有较好的适应性，在各种条件下均表现出优秀的性能，尤其是结点缓存较大时，其性能明显优于其他路由算法。

本文对基于复制的DTN路由算法的原理进行了说明，并利用仿真工具分析了四种路由算法在不同环境下的具体表现，为DTN网络的路由方案选择提供了一定依据。

［1］Burleigh S，Hooke A，Torgerson L，et al.Delay-tol

erant networking：an approach to interplanetary Internet［J］.Communications Magazine，IEEE，2003，41（6）：128-136.

［2］Cerf V，Burleigh S，Hooke A，et al.RFC 4838：Delay-tolerant networking architecture［S］.USA：IETF，April 2007.

［3］ScottK，BurleighS.RFC5050：Bundleprotocol specification［S］.USA：IETF，November 2007.

［4］吕春雷，佟首峰，姜会林，等.深空激光通信的研究现状及关键技术［J］.长春理工大学学报：自然科学版，2012，35（1）：1-5.

［5］林闯，董扬威，单志广.基于DTN的空间网络互联服务研究综述［J］.计算机研究与发展，2014（5）：931-943.

［6］P Juang，H Oki，W Yong，et al.Energy-efficient computing for wildlife tracking：design tradeoffs and earlyexperienceswithZebraNet［J］.AcmSigops Operating Systems Review，2002，36（5）：96-107.

［7］Pentland A，Fletcher R，Hasson A.DakNet：Rethinking connectivity in developing nations［J］.Computer，2004，37（1）：78-83.

［8］任智，黄勇，陈前斌.机会网络路由协议［J］.计算机应用，2010（3）：723-728.

［9］A Vahdat，D Becker.Epidemic routing for partially connected ad hoc networks［R］.Technical Report CS-200006，Duke University，2000.

［10］T.Spyropoulos，K.Psounis，and C.S.Raghavendra.Spray and wait：an efficient routing scheme forintermittentlyconnectedmobilenetworks［C］. ACM SIGCOMM 2005，Philadelphia：ACM，2005.

［11］A.Lindgren，A.Doria，O.Schel.Probabilistic routing in intermittently connected networks［J］.SIGMOBILE Mob.Comput.Commun.Rev.2003，7（3）：19-20.

［12］J.Burgess，B.Gallagher，D.Jensen，et al.MaxProp：Routingforvehicle-baseddisruption-tolerant networks［J］.Proceedings-IEEE INFOCOM，2015（6）：1-11.

［13］AriKeränen，JörgOttandTeemuKärkkäinen. The ONE simulator for DTN protocol evaluation［C］.SIMUTools'09：2ndInternationalConference onSimulationToolsandTechniques.Rome，March 2009.

［14］于海洋，杨华民，姜会林，等.一种全球覆盖的多层星座链路分析［J］.长春理工大学学报：自然科学版，2014，37（3）：56-59.

［15］孙践知，刘乃瑞，张迎新，等.机会网络典型路由算法性能分析［J］.计算机工程，2011（16）：86-89.

［16］王朕，王新华，隋敬麒.机会网络模拟器ONE及其扩展研究［J］.计算机应用研究，2012（1）：272-277.

The Research on DTN Routing Algorithm Based on Replication

CONG Ligang1，YANG Huamin1，WANG Yanghui2，DI Xiaoqiang1
（1.School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022；
2.School of Chemistry and Environmental Engineering，Changchun University of Science and Technology，Changchun 130022）

DTN is a new kind of network which is suitable for the challenge environment，and it has good adaptability to the long delay and frequency interruption.At present，the research hotspots of DTN are transmission protocol，routing algorithm，security protection and so on.This paper focuses on the research of DTN routing algorithm based on replication，Firstly，we introduce the DTN concept，structure，characteristics and applications，and then analyze the principle of four typical routing algorithm.Finally，we use simulation tools to simulate the routing algorithm，and compare the performance of the algorithm under different conditions.The experimental results show that the network factors，such as node density，node cache and TTL，have a significant impact on the performance of the algorithm，and the different routing algorithms have their specific application scenarios.

DTN；routing algorithm；network simulation

TP393

A

1672-9870（2016）04-0119-06

2016-03-21

“863”计划信息技术领域课题资助项目（2015AA015701）；吉林省科技发展计划资助项目（20140101206JC）；吉林省计算中心公共计算平台资助项目（20140101206JC-12）

从立钢（1983-），男，硕士，讲师，E-mail：clg_cust@126.com