摘 要

近年来，随着无线网络和移动互联网的不断发展，相应的出现了越来越多的具有挑战性的通信环境，因此，延时容忍网络（Delay Tolerant Network，DTN）作为一种新型网络已经引起越来越多研究人员的关注。DTN是一种为满足端到端之间没有固定的传输链路的受限网络在正常情况下顺利进行通信而设计的体系结构，是无基础通讯设施且数据链路不稳定临时性网络，且网络中的节点都具有移动性。

DTN采取基于存储-等待-转发的机制来传递消息，所以也称为机会路由。DTN 网络中的路由协议的设计理念是：选择积极的转发策略来尽可能多地转发数据分组，从而增加源节点向目的节点发送的数据分组成功投递的概率。当DTN中的某个节点持有待转发的数据分组，但该节点又没有连接到其他节点时，待转发的数据分组将会暂时被存储在该节点的本地缓存当中，直到该节点和其他连接上；若所遇节点有利于将该数据分组转发到目标节点，则将该数据分组转发给所遇节点。使用这种方法的基本转发策略包括单个副本、多个副本和编码副本等。目前比较有代表性的DTN路由算法有Direct Delivery，Epidemic，PROPHET，MaxProp等。

本文在社区通信的条件下对Direct Delivery，Epidemic，PROPHET，MaxProp等经典DTN路由算法进行深入研究的基础上，利用仿真平台ONE对这些算法进行了仿真，并根据仿真结果作图，从网络递交率和传输延时两方面比较了算法的性能。

关键词：DTN，机会路由，路由算法，网络递交率，传输延时

Abstract

In recent years, with the continuous development of wireless networks and mobile Internet, more and more challenging communication environments have emerged. Therefore, Delay Tolerant Network (DTN), as a new type of network, has received more and more researchers' attention. DTN is a architecture designed to meet the normal transmission link between end-to-end networks without a fixed transmission link. It is a non basic communication facility and a data link unstable temporary network, and the nodes in the network have mobility .

DTN adopts based on storage wait to forwarding mechanism, so it is also called opportunistic routing. The design idea of routing protocol in DTN network is to choose a positive forwarding strategy to transmit data packets as much as possible,thereby increasing the probability of successful delivery of data packets sent by the source node to the destination node. When a node in DTN holds the data packet to be forwarded, but the node does not connect to the other nodes, the data packet to be forwarded will be temporarily stored in the node's local cache until the node and other connections; if the node is beneficial to forwarding the number of packets to the target node, the data packet will be transferred to the target node, then the data packet will be forwarded to the target node. The data packet is forwarded to the node. The basic forwarding strategy using this method includes single replica, multiple replica and coded copy. At present, more representative DTN routing algorithms include Direct Delivery, Epidemic, PROPHET,MaxProp and so on.

Based on the in-depth study of the classical DTN routing algorithms such as Direct Delivery, Epidemic, PROPHET and MaxProp under the condition of community communication, the simulation platform ONE is used to simulate these algorithms. According to the simulation results, the performance of the algorithm is compared from two aspects of network delivery rate and transmission delay.

Keywords: DTN, opportunistic routing, routing algorithm, network delivery rate, transmission delay

目录

摘要 I

Abstract II

第1章 绪论 1

1.1 课题研究的背景及意义 1

1.2 课题研究的目标 4

1.3 本文的主要工作与论文结构安排 4

第2章 典型的路由算法 5

2.1 基于转发策略的路由算法 5

2.1.1 First Contact路由算法 5

2.1.2 Direct Delivery路由算法 6

2.2 基于泛洪策略的路由算法 6

2.2.1 Epidemic路由算法 6

2.2.2 Spray and Wait路由算法 7

2.3 基于概率策略的路由算法 8

2.3.1 Prophet路由算法 8

2.4 基于调度策略的路由算法 9

2.4.1 MaxProp路由算法 9

2.5 本章小结 10

第3章 仿真及结果分析 11

3.1 算法性能指标 12

3.2 仿真参数设置 12

3.3 仿真结果 13

3.4 结果分析 17

3.5 本章小结 18

第4章 总结 19

参考文献 20

附录A 22

致谢 23

第1章 绪论

1.1 课题研究的背景及意义

目前，我们使用的PC互联网及移动互联网的基础是由网络层的因特网互联协议和传输层的传输控制协议组成的TCP/IP协议族。TCP/IP协议族是现今互联网世界最基础的协议，是我们所使用的所有互联网服务的基础，比如电子邮件以及文件传输等服务。它的全称是Transmission Control Protocol/Internet Protocol，翻译为中文就是传输控制协议/因特网互联协议的意思，也可以称为网络通讯协议。TCP/IP协议族定义了数据终端（PC、工作站、手机等）如何接入因特网，以及数据如何在终端之间传输的标准。TCP/IP协议族采用了如下图1.1所示的自顶向下的4层结构：应用层，传输层，网络层，链路层（又名网络接口层或数据链路层），除最下面一层（即链路层）之外的每一层都使用它的下一层所提供的服务来完成自己的需求（不能隔层调用）。TCP/IP协议族的实现使得异构的网络能够相互连接，从而为应用层的进程提供了有效的端到端通信。但是TCP/IP协议族的实现必须满足几点假设：

（1）源端口和目的端口之间至少有一条完整的端到端路径来传递数据分组；

（2）源端口和目的端口的数据传输速率是对称的；

（3）任何源端口到目的端口之间的RTT不能太大；

（4）网络的丢包率较小。

各种服务及应用程序通过该层利用网络，常见协议HTTP，FTP，DNS

确认数据传输及进行纠错处理，常见协议：TCP，UDP

负责数据的传输、路由及地址的选择，常见协议：IP，ICMP

底层网络定义的各种协议，常见协议：FDDI，ATM，Ethernet

图1.1 TCP/IP协议族4层结构

最近几年，随着卫星通信、移动通信、水深通信以及无线通信技术的快速发展，这些技术在各个不同领域的相关应用也越来越多，因此，我们面临的网络环境变得日益复杂，在Internet之外形成了一类被称为“挑战网络”的新型网络。“挑战网络”因为其所处的恶劣的通信环境而不能满足传统的TCP/IP协议族的基本假设^[1]，比较有代表性的挑战网络有：

（1）军事自组织网络（Military Ad Hoc Network）^[2]：这类网络部署在军事环境中，一般由便于携带的或车载的野战通信装备组成，构建这种网络的主要目的是为了给作战部队的指挥提供保障，其主要是以移动（无线）通信作为通信手段。其特点是不同优先级的业务需要竞争使用带宽资源。此外，由于人为干扰、节点的移动性以及环境因素等因素也会造成通信的中断。例如，当高优先级的语音流量占用网络带宽时，低优先级的数据服务可能需要等待一段时间直至高优先级的业务停止占用网络带宽。

（2）传感器网络（Sensor Network）：这种网络是由许多微小的传感器节点通过一定方式组织而成的挑战网络，由于此类网络中每个数据终端节点的存储能力、运算能力以及功率都极其有限，所以为了节省数据终端节点的能量，网络中的通信通常是事先设置好的。

（3）星际互联网（Inter Planet Network，IPN）：此类网络是NASA（美国航空航天局）的研究人员为了向在执行深空探测任务中的飞行器提供地面支持而提出的一种网络模型^[3]。行星际网络与普通互联网的区别在于它是一种典型的“挑战网络”，特点是：数据分组传输延迟很大、网络中节点间的连接会发生间歇性中断、上行速率和下行速率不对称以及信道的信噪比较低等特性。在行星际网络中，上行速率和下行速率严重不对称，一般可以达到1000:1 甚至更高^[4]。

（4）异质通信网络（Exotic Media Network）：对于自由空间内的光通信、水深通信、近地卫星通信以及深空星际通信，由于偶尔可用通信服务（如低轨道近地卫星一天经过地球几次）、天气等环境因素造成的不可预知的通信中断和行星运动轨迹等造成的可预知的通信中断等原因，此类网络的通信延迟很长。

为了应对日益复杂的网络环境，实现异构受限网络间的互联及异步消息的传输，延时容忍网络（Delay Tolerant Network，DTN）应运而生。DTN是Kevin等人提出的面向消息的可靠的覆盖层网络体系结构，主要用于处理异构受限网络之间的连接断开的概率太高以及传输数据分组时的长延时的问题。当下对于DTN网络相关问题的研究主要集中在机会主义路由、拥塞控制以及网络安全等领域。

DTN 是一种新型的网络解决方案，主要用于处理某些网络环境中端到端连接容易中断和节点资源有限的情况，它可以满足随机的异步消息的可靠传递，一个典型的DTN网络应用图下图1.2所示。DTN 的研究将为军事战争、航天通信、灾难恢复、社区通信和应急救援等领域的信息交互提供有效的技术支持，随着DTN的快速发展未来的网络通信将会呈现出智能化以及融合化的趋势。

地面接收站和网络 地面传感器网络等

图1.2 典型DTN网络应用

DTN主要具有以下几个特点：

（1）长延时:例如，当地球与火星的距离最近的时候，光线在两地间的传输仅仅需要4分钟的时间，而当地球与火星的距离最远时的光线在两地间的传输时延会超过20分钟。而在Internet中，数据分组的传输时延通常是以毫秒为单位计算的。因此，对于DTN网络如此之长的数据分组传输时延，很多常见的基于TCP/IP协议族的应用都是难以实现的。

（2）节点资源有限: DTN在一般情况下分布于太空以及战场等通信条件十分恶劣的环境之中，故DTN网络中节点的体积和重量都有很多的限制，这就导致了节点能够携带的电源或者其他的设备资源都是极其有限的，这在一定程度上限制了网络中应用的有效性，因此，节点必须要采用一定的策略来节约设备资源，从而导致数据传输链路的性能变差。

（3）间歇性连接: DTN网络中节点之间的连接发生间歇性中断的原因很多。例如，目前没有连接网络中两个节点的端到端路径、某节点暂时关闭电源以节省设备资源、DTN的网络拓扑由于节点移动而改变，都会造成网络中的连接中断。都会造成网络中的连接中断。DTN网络中数据链路的中断可以是规律的，如卫星网络中的数据链路中断；也可以是完全随机的，如传感器网络中的数据链路中断。

（4）非对称数据速率:非对称数据速率意味着DTN网络系统中输入和输出流量之间的数据速率存在差异。在DTN网络系统中，数据传输的双向速率一般来说都是不对称的，在一些极端的通信条件下，数据传输的双向速率比甚至能够达到1000:1^[5]之高。

（5）低信噪比和高误码率^[6]:DTN网络中，由于通信条件恶劣导致的低SNR会引起信道中信号的高BER。例如，在通用的光通信系统中BER在～之间，然而，深空通信中的BER可能达到这一数量级，如此之高的BER会极大地影响到接收端对接收到的信号的解码和恢复。

1.2 课题研究的目标

本课题主要是学习各种经典的DTN路由算法，并对这些算法进行深入研究，了解这些路由算法的原理及优劣势，提出自己的思考。在对这些路由算法学习研究的基础上，利用ONE仿真平台对这些典型路由算法进行建模仿真，通过实验仿真从网络递交率和传输延时两方面分析对比这些典型路由算法的性能。课题的主要完成以下四个目标：

（1）了解DNT网络的基本知识以及国内外研究现状；

（2）了解不同的DNT路由算法的原理及转发策略；

（3）在充分考虑社区的中心性特点的基础上，研究经典DTN路由算法的性能，完成相应的设计内容；

（4）了解基于社区通信的DTN路由算法在未来的发展趋势，并提出自己的思考。

1.3 本文的主要工作与论文结构安排

本文主要研究了典型的DTN路由算法。通过阅读大量的参考文献及参考资料，了解DTN出现的技术背景及国内外研究现状，重点在社区通信的条件下对First Contact路由算法^[7]、Direct Delivery路由算法^[8]、Epidemic路由算法^[9]、PROPHET路由算法^[10]、MaxProp路由算法^[11]、Spay and Wait路由算法^[12]等典型的DTN路由算法进行了学习研究，并通过仿真获得网络递交率和传输延时的相关数据，利用matlab软件作图分析比较算法性能。论文具体结构安排如下：

第一部分介绍了DTN的相关背景，包括DTN出现的背景、DTN的发展前景、DTN的特点以及课题研究的目标，最后介绍了论文的组织结构。

第二部分介绍了First Contact路由算法、Direct Delivery路由算法、Epidemic路由算法、PROPHET路由算法、MaxProp算法、Spay and Wait路由算法的原理及策略。

第三部分对典型的DTN路由算法在社区通信的条件下进行仿真，并利用仿真所得到的网络递交率和传输延时的相关数据作图，分析算法性能。

第四部分对本次毕业设计所做的工作进行了总结，并整理了自己的收获。

第2章 典型的路由算法

在延时容忍网络(delay tolerant network, DTN)中，当节点持有需要它转发的数据分组，但该节点并没有连接到其他节点时，就把数据分组暂时存储在节点的本地缓存当中，直到该节点连接到其他并未存储该数据分组的节点。根据DTN中节点传输数据分组的策略可以将DTN中的路由算法分为基于转发策略的路由算法、基于泛洪策略的路由算法、基于概率策略的路由算法以及基于调度策略的路由算法。

2.1 基于转发策略的路由算法

基于转发策略的路由算法也可以称为单副本路由算法。在使用该类路由算法的网络中，对于网络中的源节点发出的任何一个数据分组，与源节点相遇的任何一个节点都不会对该数据分组进行复制，而是只转发该数据分组，整个网络中有且仅有这一个数据分组副本。单副本路由算法主要应用在网络中节点的能量、网络带宽及节点的存储空间受限的条件下，该算法能够使网络消耗的资源得到大幅度的降低，但相应的可靠性就要低一些，时间开销会大一些。其最具有代表性的路由协议有：First Contact路由算法、Direct Delivery路由算法。

2.1.1 First Contact路由算法

First Contact路由算法翻译为中文的意思就是首次连接路由算法。在使用首次连接路由算法的网络中，源节点在产生数据分组后会将数据分组存储在自身的存储空间中，并尝试将数据分组转发到目标节点。在使用首次连接路由算法的网络中只保存一个数据分组的副本，通过中间节点的相互转发，最终将数据分组转发到目标节点。该算法与Direct Delivery不同之处在于：在使用该路由算法的网络中，源节点在网络允许的节点的通信范围之内移动的过程中，无论它遇到的节点是不是数据分组的目标节点，它都会把自身所存储的数据分组转发给第一个与它相遇的节点；如果出现源节点同时与多个节点相遇的情况，源节点会将待转发的数据分组随机地转发给和它相遇节点中的任意一个。

首次连接路由算法是基于单复制机制的，所以使用该路由算法的网络中的节点的存储空间不需要太大。但是，在使用该算法的网络中节点携带数据分组，并且只将数据分组转发给移动过程中到遇的第一个节点，因此，传输延迟比较大。

2.1.2 Direct Delivery路由算法

Direct Delivery路由算法翻译为中文的意思就是直接递交路由算法。直接递交路由算法是最简单的基于单复制机制的路由算法。直接递交路由算法的转发策略是源节点将产生的数据分组存储在自身的存储空间中，源节点在网络中移动，只要没有遇到目的节点，源节点都不会转发数据分组，直到源节点和目的节点相遇时直接把数据分组转发给目的节点。这种转发策略消耗的网络资源是最少的，但其时间开销非常大。