容迟网络路由算法

容迟网络中路由算法摘要：容迟网络的主要目标是支持具有链路间歇性连通、时延大、错误率高等通信特征的不同网络的互联和互操作；由于节点移动性、链路间歇连通、网络频繁割裂等特点，容迟网络中的源节点和目的节点之间在多数情景下不存在一条连通路径，因此节点采用“存储携带转发”的路由模式。

数据转发算法是移动容迟网络研究的一个重要方面。

相比传统无线传感器网络的路由算法，移动容迟网络的数据转发算法不仅要提高网络节点的能量效率、延长网络生存期，对如何提高消息传输成功率、降低消息传输时延与通信开销的研究则更加具有实际意义。

现有的移动容迟网络数据转发算法大致可分为：基于消息复制的转发算法、基于历史信息的转发算法、基于先验知识的转发算法、基础设施辅助的转发算法和基于社会网络的转发算法。

关键词容迟网络；社会网络；路由协议；数据分发；优化算法容迟网络（Delay Tolerant Networks,DTNs）是近年来无线网络领域内的一个研究热点，泛指部署在极端环境下由于节点的移动或者能量调度等原因而导致节点间只能间歇性进行通倍甚至长时间处于中断状态的一类网络[1-3]。

其概念起源于星际网络（Interplanetary Internet,IPN），与传统通信网络模型相比，移动容迟网络具有网络间歇性连通、节点资源受限、传播时延高等特点。

DTN作为未来互联网络发展的一个新方向，在环境监测、交通管理、水下探测和发展中国家偏远地区网络基础建设具有广泛的应用前景和实用价值。

如何做出正确高效的路由选择一直是无线网络领域内的关键技术和主要研究课题，然而传统的基于的路由协议、移动网络和无线传感网络的路由协议均很难在容迟网络中工作。

一方面，与传统通信网络模型不同，移动容迟网络中不存在稳定可靠的端到端链路，使得现有的基于端到端连通性假设的无线传感器网络路由算法不能适用于该网络环境。

另一方面，相对于传统的无线传感器网络路算法，移动容迟网络数据转发算法不仅需要综合考虑如何提高网络节点的能量效率、延长网络生存期，研究如何提高消息传输成功率、降低消息传输延迟与通信开销则具有更加实际的意义。

目前，移动容迟网络的数据转发算法大致可分为以下几种方式：基于消息复制的转发算法、基于历史信息的转发算法、基于先验知识的转发算法、基础设施辅助的转发算法和基于社会网络的转发算法。

1容迟网络概述1.1 容迟网络起源上世纪九十年代，美国国家航空航天局(National Aeronautics and Space Administration, NASA)等研究机构在美国国防部高级研究计划署(DefenseAdvanced Research Projects Agency, DARPA)的支持下开始了对星际互联网(Interplanetary Internet, IPN)的研究。

IPN 的基本思想是让深空通信(Deep Space Communications)中的不同节点(如地面站与航天器)之间像Internet 上的主机一样进行通信。

然而行星自转与航天器运动导致了通信链路的间歇性连通，使得基于端到端连通性假设的Internet 协议不能直接应用于IPN。

面对深空通信中遇到的高时延与网络断开等问题，研究人员逐渐认识到了IPN环境与传统Internet 环境的主要区别是网络协议须容迟容断(Delay/Disruption-tolerant)。

随着IPN研究的开展，互联网研究任务组(Internet Research Task Force, IRTF)成立了星际互联网研究组(Interplanetary Internet Research Group, IPNRG)，为相关的研究工作提供支持。

随后，由互联网研究专家Vinton Cerf 等人提出了最初的IPN 体系结构，用于解决深空通信中的高时延与丢包问题。

随着IPN相关研究的不断深入，IPNRG 于2002年提出了改进的IPN 架构，并描述了将所提出的IPN 体系结构应用于更具一般性的容迟容断网络环境(Delay/Disruption-Tolerant Networks, DTN) 的结构设计中。

随后，容迟网络研究组(Delay-Tolerant Networking Research Group, DTNRG) 在IPNRG的支持下成立，并致力于受限网络体系结构研究与网络协议设计。

与此同时，针对如何将IPN的设计思想应用与其他受限网络环境的研究也受到了研究者们越来越多的重视。

2003年，Kevin Fall 针对异构网络互联问题提出了基于“束”(Bundle) 的DTN体系结构[4]，。

随着针对受限网络环境的应用场景逐渐增多[5,6]，相关的研究工作涉及到了DTN 的方方面面，包括体系结构设计、转发算法设计、安全问题以及可靠性验证等等。

1.2 容迟网络的特点相比传统的基于TCP/IP 协议族的互联网，容迟网络有以下几个特点[7]：1 ）网络节点移动性容迟网络中各节点的工作方式不依赖于网络基础设施，并且在移动容迟网络中不存在通信范围足以覆盖整个网络的特殊节点。

网络中各节点能够按照预先指定的或者完全随机的路径在网络中移动，并利用移动带来的通信机会进行通信。

当节点相遇时，即移动进入到彼此的通信范围之后，消息将在有限的相遇时间内在相遇的节点之间进行转发。

通过这种方式，消息将最终逐跳地由源节点发送至目的节点。

因此网络节点的移动性是容迟网络的主要特点。

尤其对于某些特定的网络场景（例如利用由人携带的手持设备进行分布式组网），人的移动将直接影响到网络节点间的相遇间隔时间、相遇持续时间以及相遇频率等，并进而影响到数据转发算法的设计。

2 ）高时延与低带宽容迟网络的端到端时延指的是消息从源节点发送到目的节点经过的端到端传输路径上的每一跳传输时延的总和。

其中，每一跳传输时延又包括消息通过该链路时的发送时间、传播时间、排队时间和处理时间。

在移动容迟网络中，节点移动导致网络拓扑结构的不断变化以及网络的间歇性连通，也使得消息在发送至下一跳节点之前需要经过很长的排队时间，从而产生了较高的时延。

另一方面，网络节点的移动性也决定了在移动容迟网络环境中适宜采用无线通信技术，而受限于无线信道的物理特性以及无线信号的干扰衰减等因素，节点之间的网络带宽通常比较低。

3）网络间歇性连通在容迟网络中，节点的频繁移动导致网络拓扑结构不断变化。

当节点移动超出彼此的通信范围时，节点间的无线通信链路即被中断。

网络中各节点之间通信链路的中断往往会导致整个网络被划分为多个互不连通的区域，从而导致源节点与目的节点之间通常不存在稳定可靠的端到端链路。

对于因节点移动而产生的网络间歇性连通情况，有的可以提前预测（如IPN 中的链路通断），而有的难以进行预测（如PSN 中设备携带者之间的相遇）。

另外，移动容迟网络中节点的休眠或失效也会导致网络的间歇性连通。

4）网络节点自组性容迟网络是对等式网络，即网络中的所有节点地位平等，因而具有自组织的特性。

一方面，移动容迟网络能够提供不依赖于基础设施的网络服务，网络节点间互相作为消息转发的载体；另一方面，网络中节点的加入或离开不会影响到整个网络的正常运行，从而提高了网络的生存能力；再者，网络中各节点之间通过分布式算法进行控制与协作，共同对整个网络进行构建和管理。

5）网络节点资源有限容迟网络中的各网络节点仅具备有限的存储与计算能力。

同时，移动容迟网络特殊的应用环境（如战场环境、水下环境等）限制了网络节点的体积和重量，从而间接地限制了网络节点的资源。

这一特点使得如何更加有效地利用有限的节点资源并且提高消息传输成功率，成为了移动容迟网络数据转发算法设计中需要考虑的一个主要方面。

2容迟网络路由算法容迟网络的路由算法通常可分为五种不同类型，包括：基于消息复制的(Replication-based)路由算法、基于历史信息的(History-based) 路由算法、基于先验知识的(Knowledge-based) 路由算法、基础设施辅助的(Infrastructure-assisted) 路由算法和基于社会网络的(Social-based) 路由算法。

1）基于消息复制的路由算法基于消息复制的路由算法(Replication-based forwarding algorithm) 包括传染路由方式(Epidemic Routing)和控制洪泛方式(Controlled Flooding)。

传染路由是最简单的移动容迟网络数据转发算法[8]，其思想是通过源节点向相遇节点发送消息副本，再由相遇节点重复该过程将消息副本发送至更多节点，最终将该消息传播到整个网络从而送达目的节点。

这种转发方式的优点在于能够达到较高的消息传输成功率，但同时也具有明显的缺点。

随着网络中节点数量的增多，大量的消息副本将耗尽网络中各节点的资源，因此该算法不具有可扩展性。

针对传染路由的缺点，多种限制消息副本数的转发算法被相继提出。

这类算法被称为控制洪泛方式的转发算法。

例如在文献[9]中，作者提出了四种用于限制消息副本数的机制用于降低节点的资源消耗（如限制消息可被转发的最大跳数），然而该算法的缺点是增大了消息传输时延。

喷射等待路由算法(Spray and wait)算法和喷射焦点路由算法(Spray and focus）[10]都将路由算法分为两阶段且第一阶段称为喷洒(Spray)：在网络中产生固定数目数据包拷贝进行传播，第二阶段分别为等待(Wait）和焦点(Focus)，在等待阶段携带数据包的节点对除碰到目的节点外不再传播数据包，在焦点阶段携带数据包的节点对除碰到目的节点或者碰到效用值比本节点高的节点外不再传播数据包，这两个算法可以控制网络中数据包副本数量。

2）基于历史信息的路由算法不同于基于消息复制的路由算法，基于历史信息的数据路由算法(History-based forwarding algorithm) 利用网络中各节点之间的相遇历史记录或者节点间的相遇概率为下一跳节点的选择提供依据。

在文献[11]中提出的PROPHET (Probabilistic Routing Protocol)算法是比较有代表性的基于历史信息的移动容迟网络数据转发算法。

该算法基于节点非随机移动的假设，即经常经过同一区域的节点将来再次经过该区域的概率较高。

网络中各节点预先计算与其他节点相遇的概率并在节点相遇时对该信息进行交换，然后利用相遇概率的传递性将消息转发给具有更大概率与目标节点相遇的节点。

MV (Meetings and Visits)算法[12,13]通过学习网络中节点的移动模式(Mobility Pattern)，即节点之间相遇的概率以及节点经过特定区域的概率，将消息转发给分发概率更高的节点。