延迟/中断可容忍网络路由中的关键技术

刘水仙，周 健

（南京邮电大学 通信与信息工程学院，江苏 南京 210003）

0 引言

随着网络技术研究不断的进展，“受限网络”成为无线通信的一个新的领域，延迟/中断容忍网络简称为 DTN，是一种特殊受限网络，采用一种新型的网络体系结构，2003年SIGCOMM 国际会议上由Kevin提出[1]。典型例子有：陆地移动网络、外来媒体网络、军事无线自组织网络、传感器网络等，存在共同的特点：间歇的连通性、缺少端到端路径、网络分割/断开使得传输控制协议/因特网互联协议（TCP/IP）不适用，长而可变的延迟，非对称的数据速率，高差错率。

1 与DTNs路由相关的基本问题

1.1 DTN路由实现的目标

DTN用于描述自组织网络等无线网络中频繁发生长时间网络分割情形，它主要关注的是如何提高成功投递率，尽量减少交付延时，节约节点缓存和降低耗能，在实现相同路由性能的条件下，尽量降低算法的复杂度，提高算法的实用性。此外，针对不同的消息服务等级要求，应关注于不同的性能参数，采用满足相应要求的路由方法。

1.2 DTN路由算法分类

在ACM SIGCOMM2004 年会中, Jain等人提出了DTN网络中的路由问题[2]，提出了一个如何在 DTN 网络中评估路由算法性能的框架 ,明确提出了 DTN 路由的主要问题就是确定消息如何端到端地穿越一个随时间变化而连续变化的网络,且这种动态性是可能预知的。Zhang Z[3]在已有研究成果基础上,将 DTN 路由策略分为两大类:一类为确定性路由方案,它假定将来的移动和连接是可以知道的、是可预测的；另一类为随机性路由方案,它假定网络是动态的、不确定的。主要的确定性路由方法有：基于树的方法、时空路由、修正的最短路径方法；随机性路由算法根据不同的转发机制分为：传染性/ 随意散发方式，改进的算法有约束洪泛、Spray AndWait等；基于预测和历史消息的方法（如PROPHET ）、可控移动的方法、基于编码的方法。

2 DTN路由的关键技术

2.1 拥塞控制

DTN网络中消息传输采用存储转发模式，许多DTN路由协议在实际使用时，会产生长期的存储，节点缓存受限时易发生阻塞；另外，网络中数据单元称为“捆绑（束）”，是自载的应用级数据单元，它们常常是很大的，当移动性导致节点间短暂的接触时，可用带宽可能不足以使所有预定消息通信。因此，有效的丢弃策略是必要的。

目前的研究结果主要分为两类[4]：主动方法，通过缓存管理和保管传输的相应调整起到拥塞控制的作用；被动方法，采用接入控制避免在开始处的拥塞。文献[5]采用主动方法的思想，并结合传染路由算法，提出了一种基于传染路由的拥塞控制策略（当节点缓存完全占用又需存储新分组时，遍历缓存，找出转发次数大于等于N次的分组将其删除；若缓存中没有这样的分组，则删除最后一个存入的分组），为信息的集合建立SV索引,引入拥塞检测和拥塞避免操作，有效缓解了节点拥塞。

Zhang Z.分析了缓存区受限的epidemic路由[6]，并评估了一些简单的丢弃策略例如 drop-front 和 drop-tail。使用一个有效的联合调度和丢弃策略能够最优化不同的性能指标[7]，比如平均延迟和交付概率，首先分析一个最优联合调度和丢弃策略——基于全局知识的排序和丢弃（GBSD，GlobalAcknowledgeBasedScheduling& Drop），以最大化平均交付率或者最小化平均传递时延，用网络的全局信息来为一个给定的路由度量推导每个消息的特性，在实践中很难实现。为了修改这种方法，提出另一个策略，HBSD采用一个基于统计学习的分布式算法，从历史学习中估计当前网络的全局状态，能被用来计算message utility。

另外可通过控制复本或转发数目来避免过多耗用节点缓存，一些算法中使用单个复本，如FC、DD，可有效地缓解空间和带宽，但同时使得消息交付率很小，SprayAndWait设定消息被复制的数目，有一般模式和二进制模式，通过调整复本数目来平衡分发与耗用内存。

2.2 运动模式

考虑节点运动知识，将虚拟空间运用于DTN路由中[8]，算法将因此受益，它根据与节点在某个位置出现的可能性相关的坐标来描述节点，利用一个与节点运动模式相关的高维Euclidean空间结构，为DTNs定义一个一般的路由方案。

“移动空间”是一个高维的虚拟空间．节点活动的物理空间所划分的区域数是这个“移动空间”的维数，节点在这个区域出现的概率就是节点坐标在这个维上的截距。“移动空间”中的坐标并不是节点的物理坐标，而是用概率的方法反应了节点在物理空间中的运动规律，作为路由选择的依据。

不同的空间概率分布代表了不同的移动模型，常用节点移动模型主要有随机模型、随机地图限制模型、人类行为模型。其中随机移动模型有随机移动（RW），随机路点（RWP）和随机方向（RD）模型；为了将实际移动性模型化，MBM根据实际的map数据中预定路径限制节点移动，例如随机地图移动（MBM）、基于最短路径的移动（SPMBM）、基于路线的移动（RMBM）；工作日移动模型（WDMM）。

文献[9]节点维护一个包含所有节点三维容量的矩阵，利用图像处理中的模板运算机制从中提出可能的运动模式，最后用一个通用的数据结构存储这些信息，并用于路由决策过程中。为了应对不同的运动模式，节点自定位是一个影响路由算法关键的因素，文献[10]通过引入修正因子的自定位方案，在节点移动过程中不断对节点坐标进行调整，最后收敛到一个可用范围，增强了路由算法的稳定性。

2.3 拓扑先念知识

文献[2]针对五种不同的先念信息等级，设计出几种具有代表性的路由算法。MED基于经典的Dijkstra算法，使用延时期望作为代价。改进算法有MED-PC算法[2.911]性能比MED有明显改善，增加了对先验知识的假设，每当一个链接到达，中间节点都要对队列中所有报文分别计算路由，计算强度较大。另一种改进算法AMED[12]，仍基于dijkstra算法，从目的节点开始计算到源节点的路由，返回反转后的永久节点序列，而不是传统意义上的单条路由，比MED-PC算法的计算量少，但性能相当，验证了oracle 2对Oracle 1的实际优势并不是很大。在ED算法基础上，引入了对节点运动精确性的考虑[13]，加入时间精确性因子ρ，反映出连接建立的时刻处在偏离预定时刻的某个领域的概率，并以之作为ED算法中的链接代价的权重，提出一种更稳健的路由算法AED，当节点运动不确定性增加时，AED维持较好的性能，而ED的性能则明显下降。

Oracle 3以上的先念等级不常用，虽然拥有先念知识越多，路由算法有更好的性能，但是先验知识的获取和计算处理的代价远远大于它们带来的优势。

由于长的传播延时和网络动态特性，先前的路由信息常常是过期或不准确的，信息陈旧成为机会网络路由性能的限制，文献[1.4.314]提出了云级别重排和接触能力最大化来解决这些限制，将云计算应用到DTN路由中（云路由），通过智能地利用转发机会避免了拥塞，由于云计算带来的性能改善和几乎可忽略的并行网络控制信道的成本，当有两个或多个不同特性的网络，它们应该被看作是一个平行网络架构并且采用云计算来提高各信道的联合性能。

2.4 延迟模型

DTN的特点决定了其路由算法适合选择延时作为基本的代价，其延迟主要来源于等待链路建立的时间，当缓存区的消息数量足够大时，排队延迟就不可忽略，一般而言，消息的传输时间相对很小，在精确度要求不高的计算中可以忽略，图1描述了一个基本的延迟结构，由基本的三类延迟组成，事实上对应了一种新的排队模型--带休假的排队模型，是设计DTN路由算法的基础。文献[15]从排队论的角度分析了 DTN的延时模型，并引入了休假规律的随机排队系统，通过分析得到平均队列长度和平均延时的表达式。

图1 两个节点间的消息延时结构

2.5 多播路由方案

实际的应用场景中常常要用到多播，可以使用受控的洪泛机制实现DTN中的多播[3.6.116]，从而研究多播路由机制的基本性能度量，例如消息交付率、消息延迟和占用缓存。在单播路由方案中可以使用基于两跳 3.6.12] [3.6.13].【3.6.5】【3.6.的方案可以缓解路由负载，这是因为源节点转发消息包给中继节点，中继节点只有遇到目的点时才将包转发给目的节点，文献。[3.6.317]将mobility-assist路由用于DTN无线多播中背景下，最后提出了RelayCast，将两跳路由扩展到多播场景中。这些方案都是在消息发送者知道消息接收组成员，且组成员在消息传递过程中不会改变的情况下提出的，文献[18]中设计了一个灵活的多播路由协议，解决多播组成员变化的问题。

2.6 域间路由方案

几乎所有的 DTN路由都专注于单个域内的消息传递，这个域的特点是有相同的网络架构和单个名字空间。文献[19]介绍了一个基于随机和确定转发机制的域间路由方案，说明了一个标准的路由框架应该考虑到不同的路由方案的整合，提出网络意识的机会多区域异步交付（NOMAD）框架来解决不同系统的共有设计问题，目标是讨论一个通用的架构的条件，它超越不同类型的通信模式和传输机制。

2.7 路由算法仿真

2.7.1 仿真平台

DTN路由性能高度地依赖潜在的移动性和节点的特性，通过许多场景估计协议性能要求有一个合适的仿真工具。现有比较成熟的网络仿真平台主要有NS2、OMNet++和OPNET，但是没有一个是专门针对DTN的。dtnsim和dtnsim27是为DTN环境开发的用于路由仿真的平台，随后提出的ONE[7.one20]可以实现DTN路由和应用协议的仿真，允许用户基于不同的移动模型创建应用场景，并且提供了一个实现路由和应用协议的框架，ONE的核心是一个基于代理的离散事件模拟引擎，在每一个模拟时间片断，这个引擎更新一些实现主要仿真功能的模块，。主要的功能模块有节点移动模块、事件产生模块、路由模块、结果可视化模块。

2.7.2 仿真参数的选择

研究者们大多数关注路由算法的设计，然而，各种路由协议面临一个根本性的挑战：选择合适的协议参数和正确的仿真时间尺度，这些依赖于不同场景下节点的运动特性。在一个场景内或者是不同场景间，移动节点运动特性很可能不同，文献[21]使用两个具有代表性的路由协议交付概率路由（PROPHET）和最大概率路由（MaxPROP），推导了独立动态和独立决定移动节点中路由参数的机制，分析了时间尺度对DTN路由算法的影响。

3 结语

由于 DTN网络自身的特点，实现一个适用于这种特定环境的路由方案面临许多问题，需要有相应的技术来解决这些限制，总结设计过程中的关键技术是有必要的，将来的研究仍然要从这些关键点出发，提出新的思路和解决方法，设计出一个通用的性能良好的路由机制，克服网络的受限特性，从而实现DTNs中有效可靠的通信。

[3]参考文献

[1] FAL1 K.A Delay Tolerant Network Architecture for Challenged Intemets[C]. New York:ACM Press,2003:27-34.

[2] JAIN S, FALL K, PATRA R. Routing in a Delay Tolerant Networking[C]. New York: ACM Press, 2004:145-158.

[8][3] ZHANG Z. Routing in Intermittently Connected Mobile Ad Hocnetworks and Delay Tolerant Networks: Overview and Challeng[C]. USA:IEEE,2006: 24-37.

[4] 樊秀梅. 容迟网络的体系结构及关键技术[EB/OL]. (2006-12-06).[2010-01-14].http://www.paper.edu.cn.

[5] 赵玲,刘占军,李云,等.DTN中基于传染路由的节点拥塞控制策略[J].通信技术,2009, 42 (02):136-140.

[6] ZHANG X, NEGLIA G, KUROSE J, et al. Performance Modeling of Epidemic Routing[J].In Proceedings of IFIP Networking,2007,51(10):2867-2891.

[7] KRIFA A, BARAKAT C. An Optimal Joint Scheduling and Drop Policy for Delay Tolerant Networks[C].USA:IEEE,2008:1-6.

[8] LEGUAY J, FRIEDMAN T, CONAN V. DTN Routing in a Mobility Pattern Space[M].USA:ACM,2005:276-283.

[9] 周晓波,张幸,彭敏,等.DTN网络中基于泛模板运算的运动模式发现机制[J]电子与信息学报,2009,31(02):472-475.

[10] 王行甫,卫平青,苗付友,等.一种节点自定位方案及其性能分析[J].中国科学院研究生院学报,2008,25(03):367-371.

[11] EVAN P C, LI J L,PAUL A S W. Practical Routing in Delay-Tolerant Networks[M].USA:ACM,2005:237-243.规划局

[12] 陈飘,卢汉成,李津生,等.用于延时可容忍网络的增强型MED路由算法[J].计算机工程,2007,33(21):90-98.快乐

[13] 周晓波,卢汉成,李津生,等.AED:一种用于DTN 的增强型Earliest-Delivery算法[J].电子与信息学报,29(08):1956-1960.

[14] MIKE P W, HARRAS K A, ALMEROTH K C, et al. On the Implications of Routing Metric Staleness in Delay Tolerant Networks[J].Computer Communications,2009(32):1699-1709.

[15] 周晓波,周健,卢汉成,等. DTN网络的延时模型分析[J].计算机研究与发展,2008,45(06):960-966.

[16] ABDULLA M, SIMON R. Controlled Epidemic Routing for Multicasting in Delay Tolerant Networks. Modeling, Analysis and Simulation of Computers and Telecommunication Systems[C].USA:IEEE,2008:1-10.

[17] Lee U, Young O S, Lee K W, et al. RelayCast: Scalable Multicast Routing in Delay Tolerant Networks[C].USA:IEEE,2008:218-227.

[18] YIN L, LU H M, LONG K,et al. A Flexible Multicast Routing Scheme for Multicasting in Delay Tolerant Networks[C].USA:IEEE,2009:1-5.

[19] MUSOLESI M, MASCOLO C. A Framework for Multiregion Delay Tolerant Networking. Proceedings of ACM International Workshop on Wireless Networks and Systems for Developing Regions (WiNS-DR)[M].USA:ACM,2008.

[20] Keranen A.Opportunistic Network Environment Simulator[EB/OL](2008-05-29)[2010-01-14].http://www.dtnrg.org/wiki/Code.

[21] KARVO J,JÖRG OT. Time Scales and Delay-tolerant Routing Protocols[M].USA:ACM.2008:13-19.