（计算机软件与理论专业论文）延迟容忍网络路由算法研究.pdf

延迟容忍网络路由算法研究 学位论文完成日期： 指导教师签字： 答辩委员会成员签字： fiylurlfllllllfr8flflll2llffll7illlll8flilllofi114lllll fy 18 2 7 8 0 4 一 谭口謦。誊磨攀“。 露 耋 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含未获得( 注! 翅逡直基丝益噩挂型 直盟丝：奎拦卫窒! 或其他教育机构的学位或证书使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：声蓬灸签字日辨5 月髟日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信息 研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公 众提供信息服务。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：声蒸灾 签字日期：州。年箩月形日 + 导师签象锄岳父 签字日期：刃易年万月彳日 肚 延迟容忍网络路由算法研究 摘要 随着网络通信技术的发展和各种实际应用的需要，出现了一些受限网络，这 类网络具有通信难度大，通信环境复杂的特点，传统的通信模式已无法适用。延 迟容忍网络( d e l a yt o l e r a n tn e t w o r k ，d t n ) e 是在这种背景下应运而生，从自组织 无线网络中抽象出来作为一种新的网络模型，这种网络模型可以广泛应用于陆地 移动网络、水下声学网络、军事无线自组织网络、传感器网络等多种应用场景， ， 有着很强的理论研究和实用价值。 由于延迟容忍网络特殊的网络特点，有效可靠的路由算法设计成为延迟容忍 网络中的关键问题。本文以研究延迟容忍网络的路由算法为主要研究对象，首先 介绍了延迟容忍网络的研究背景、特点、体系结构以及延迟容忍网络的应用前景 及存在的问题，接着分析了典型的延迟容忍网络路由算法，并在已有研究的基础 上，对延迟容忍网络路由算法问题进行了深入的研究。 本文在m e s s a g ef e r r y i n g 思想的基础上，结合j e r e m i el e g u a y 等人提出的“移 动空间 ( m o b y s p a c e ) 概念，提出一种基于移动空间的f e r r y 自适应路由算法。 该算法利用移动空间是用概率的方法反映节点在物理空间中的运动规律的特性， 使f e r r y 根据节点在移动空间出现的概率，选择合适的路径节点，自己确定遍历 路由。这样保证以一个最佳的概率与节点接触，使得f e r r y 与节点连续接触的间 隔时间最小。由于节点的移动，f e r r y 选择的路径节点是随着网络情况的改变而 改变的，因此可以更好地提高网络性能。 本文还对分簇d t n 的路由问题进行研究，提出了一种基于m e s s a g ef e r r y i n g 的分簇d t n 混合路由机制，在这种特殊的网络环境，通过簇内网关节点的使用， 将一般移动a dh o e 网路由与d t n 的路由结合在一起，簇内可以使用较小变动的 一般移动a dh o e 路由算法，簇间则使用f e r r y 在各个簇间转发消息，提供有规律 的连接。该机制不需要节点与f e r r y 的在线交互，降低了多跳传输引起的干扰， 也减少了多数据交换环节的无线干扰，最后通过仿真实验验证了该路由机制的有 效性。 最后对本文所做的研究工作进行了总结，并阐述了d t n 路由问题的进一步 研究思路。 关键字：延迟容忍网络；移动空间；自适应；路由算法； 玎 r e s e a r c ho f r o u t i n ga l g o r i t h m si nd e l a yt o l e r a n tn e t w o r k s a b s t r ac t w i t ht h ed e v e l o p m e n to fn e t w o r kc o m m u n i c a t i o nt e c h n o l o g ya n dt h er e q u i r eo f v a r i o u s p r a c t i c a la p p l i c a t i o n s ，i ta p p e a r ss o m ec h a l l e n g i n gn e t w o r k st h a tw i t h c o m m u n i c a t i o nd i f f i c u l ta n dc o m p l i c a t e dc o m m u n i c a t i o ne n v i r o n m e n t t r a d i t i o n a l c o m m u n i c a t i o nm o d e li sn o ts u i t a b l ef o rt h es p e c i a ln e t w o r k d e l a yt o l e r a n tn e t w o r k s ( d t n ) i se x a c t l yu n d e rt h i sk i n do fb a c k g r o u n dt oe m e r g e 、 ，i 廿lt h et i d eo ft h et i m e s i ti sf r o mt h es e l f - o r g a n i z i n gw i r e l e s sn e t w o r ka b s t r a c t e da san e wn e t w o r km o d e l w h i c hi sw i d e l ya p p l i e di ns c e n a r i o sl i k et e r r e s t r i a lm o b i l en e t w o r k ，u n d e r w a t e r a c o u s t i cn e t w o r k s ，m i l i t a r ya d h o en e t w o r k ，s e n s o rn e t w o r ka n ds oo n i ti s v a l u a b l ef o rb o t hr e s e a r c ha n d p r a c t i c e d u et ot h es p e c i a lf e a t u r e so ft h ed e l a yt o l e r a n tn e t w o r k ，t h ee f f i c i e n ta n dr e l i a b l e r o u t i n ga l g o r i t h md e s i g ni st h ek e yi s s u e so fd e l a yt o l e r a n tn e t w o r k t h i st h e s i s f o c u s e so nd e l a yt o l e r a n tn e t w o r k i n gr o u t i n gp r o b l e m s a tf i r s t ，t h i sp a p e ri n t r o d u c e t h es u m m a r y , r e s e a r c hb a c k g r o u n d ，c h a r a c t e r i s t i c s ，s y s t e ma r c h i t e c t u r e ，t h ea p p l i c a t i o n f o r e g r o u n da n de x i s t i n gp r o b l e m si nd e l a yt o l e r a n tn e t w o r k t h e nt h et y p i c a lr o u t i n g a l g o r i t h m so fw i r e l e s ss e n s o rn e t w o r ki sa n a l y z e d a f t e r w a r d s ，w eg i v et h ed e p t h r e s e a r c ho nt h ei s s u eo fd e l a yt o l e r a n tn e t w o r kr o u t i n gp r o b l e mb a s e do nt h ee x i s t i n g r e s e a r c h b a s e do nt h em e s s a g ef e r r y i n g ，w ep r o p o s ea na d a p t i v ef e r r yr o u t i n ga l g o r i t h m c o m b i n i n gw i t ht h em o b y s p a c ec o n c e p tt h a tp r o p o s e db yj e r e m i el e g u a y t h e a l g o r i t h mu s e st h ec h a r a c t e r i s t i ct h a tm o b y s p a c ei sb ym e a n so ft h ep r o b a b i l i t yt o r e f l e c tt h em o v ef e a t u r e so ft h en o d ei nt h ep h y s i c a ls p a c e ，w h i c hr e n d e rt h ef e r r yt o s e l e c tt h ea p p r o p r i a t ew a y p o i n t st od e t e r m i n et h e i ro w nt r a v e r s er o u t ea c c o r d i n gt o t h ep r o b a b i l i t yo fn o d e si nt h em o b i l es p a c e i tc a ne n s u r ef e r r yc o n t a c tan o d ew i t h a no p t i m a lp r o b a b i l i t yt om i n i m u mt h es u c c e s s i v ei n t e r v a ln o d e f e r r yc o n t a c t s a s n o d e sm o v i n g ，f e r r ya l w a y sc h o o s et h ew a y - p o i n t st h a ti ss u i t a b l ef o rt h ec h a n g e so f t h en e t w o r k ，s oi tc a ni m p r o v et h en e t w o r kp e r f o r m a n c e a d d i t i o n a l l yt h i st h e s i ss t u d i e sc l u s t e r e dd t nr o u t i n gp r o b l e m ，p r o p o s e sah y b r i d i i i r o u t i n gi nc l u s t e r e dd t nw i t hm e s s a g ef e r r y i n g i nt h i ss p e c i a le n v i r o n m e n t ，o u r r o u t i n ga p p r o a c hc o m b i n e sd t nr o u t i n gw i t ht h em o b i l ea d h o en e t w o r kr o u t i n g t h r o u g ht h eu s eo fg m e w a yn o d e sw h i c hi ne v e r yc l u s t e r w i t h i ne a c hc l u s t e r , w ec a l l u s em i n i m a lm o d i f i c a t e dm o b i l ea d h o cn e t w o r kr o u t i n ga l g o r i t h m ；a n du s et h ef e r r y r e l a y i n gm e s s a g e sb e t w e e nt h ev a r i o u sc l u s t e r st op r o v i d ear e g u l a rl i n k t h eh y b r i d m e c h a n i s md o e sn o tr e q u i r ec o l l a b o r a t i o nb e t w e e nf e r r ya n do t h e rn o d e si nt h e n e w o r k ，w h i c hr e d u c e st h ei n t e r f e r e n c ec a u s e db ym u l t i h o pt r a n s m i s s i o na n dt h ed a t a e x c h a n g eo v e rt h ew i r e l e s sl i n ki n t e r f e r e n c e a s l ot h es i m u l a t i o nr e s u l t sd e m o n s t r a t e t h ee f f e c t i v e n e s so ft h er o u t i n gm e c h a n i s m f i n a l l y , t h et h e s i ss u m m a r i z e st h er e s e a r c h i n gw o r k sh a v e b e e nd o n e ，a n d p r o v i d e ss o m ef u r t h e ri n t e r e s t i n gd i r e c t i o n so ft h ed t nr o u t i n gp r o b l e m k e yw o r d s ：d e l a yt o l e r a n tn e t w o r k s ；m o b y s p a c e ；a d a p t i v e ；r o u t i n ga l g o r i t h m s ； i v ， 1 1 廖 目录 1 绪论1 1 1 延迟容忍网络综述1 1 1 1 延迟容忍网络研究背景一1 1 1 2 延迟容忍网络的特征一2 1 2 延迟容忍网络的体系结构j 3 1 3 延迟容忍网络的应用1 2 1 4 延迟容忍网络存在的问题_ 1 3 1 5 论文的组织结构1 4 2 典型路由算法分析。1 6 2 1 路由算法的设计目标1 6 2 2 路由分类：一1 7 2 3 典型的路由算法1 8 2 3 1 基于分发的路由1 8 2 3 2 基于知识的路由2 0 2 3 3 基于固定基础设施的路由2 2 2 3 4 基于移动基站的路由j 2 3 2 4 本章小结_ 2 4 3 基于移动空间的d t n 自适应路由算法2 5 3 1 相关工作2 5 3 1 1m e s s a g ef e r r y i n g 思想2 5 3 1 2 基于f e r r y 的两类路由2 6 3 2 基于移动空间的f e r r y 自适应路由一3 3 3 2 1 基本思想3 3 3 2 2 概率阈值的确定3 4 3 2 3 选择合适的路径节点3 8 3 2 4 最短遍历路径节点3 9 3 3 实验仿真及结果分析4 l v 3 3 1 模拟环境j 4 1 3 3 2 相关性能指标4 2 3 3 3 仿真结果及分析4 2 3 4 本章小结4 5 4 分簇d t n 的混合路由算法4 6 4 1 网络模型4 6 4 1 1 相关环境4 6 4 1 2 基本思想4 7 4 2 混合路由4 7 4 2 1 簇内路由4 8 4 2 2 簇问路由4 9 4 3 实验仿真及结果分析一：一5 1 4 4 本章小结5 3 5 总结与展望二。5 4 5 1 论文总结5 4 5 2 进一步研究工作5 4 参考文献5 6 致谢：6 0 个人简历6 1 发表的学术论文6 l v 1 延迟容忍网络路由算法研究 1 绪论 1 1 延迟容忍网络综述 1 1 1 延迟容忍网络研究背景 随着计算机技术、通信技术的发展以及人类对未知世界的探索，出现了大量 低成本、具备短距离无线通信能力的智能设备，同时推动了无线自组织网络应用 的迅速发展。但在许多实际自组织网络应用中，由于节点的任意移动、障碍物等 多种原因都可能导致网络大多数时候不能连通。例如，行驶在公路上带有智能设 备的车辆自组成车载网络，实现交通事故预警和其他道路安全应用【l j ；各种配备 蓝牙接口的手持电子设备，如手机、p d a 等自组成网络以实现数据共享或协作 访问互联网1 2 1 ；放置在动物身上的传感器组成移动传感器网络收集动物迁徙数据 【3 1 笔 寸o 这类网络在特定的时刻，可能被分割成不连通的子区域，传统的网络通信模 式已不再适用，给传统的基于t c p i p 的端到端通信的i n t e m e t 技术带来严峻的 挑战。为使这种网络更好的与现有i n t e m e t 之间互操作，并改善网络的传输性能， 必须要提出一种保证可靠的异步消息传输的新的网络架构，并考虑端到端链路中 断，中间传输节点资源有限的情况。 延迟容忍网络( d e l a yt o l e r a n tn e t w o r k ，d t n ) 4 】便从自组织无线网络中抽象出 来作为一种新的网络模型，这种网络以“存储一携带转发 的路由模式实现节点 间通信，其完全不同于传统网络通信模式的新兴组网方式引起了研究界广泛的关 注。d t n 大多数时候是不连通的，需要通信的节点之间没有假设存在至少一条 完整的端到端的通信路径，并且允许节点之间任意连接或断开。当源节点和目的 节点没有同时连接到同一网络时，延迟容忍网络仍然可以允许它们之间交换消 息，在传递过程中，消息被存储直到遇到目标节点。图1 1 是一个d t n 的例子， 战士之间形成了a dh o c 网络，通过直升飞机机会性地将数据转发给附近的军舰 【5 1 。 延迟容忍网络路由算法研究 。 、 图1 - 1d t n 网络举例 d t n 是在各种异构网络的传输层之上覆盖了一层即d t n 层( 或称b u n d l e 层) ，d t n 层充分利用了下层网络提供的服务进行数据传输等工作。由于d t n 网络拓扑结构的动态特性，链路的中断可能比连接更加频繁，因此设计合理有效 的路由算法成为d t n 的关键问题。它的网络特点也决定了d t n 路由设计所面 临的挑战，如尽可能地减小时延，提高数据率；能够充分利用链路的间歇性或可 预测性，以便及时传输数据；要求考虑节点所剩的能量层次和存储空间，否则可 能导致数据的丢失。 1 1 2 延迟容忍网络的特征 延迟容忍网络不同于传统的a dh o e 网络，我们从延时、数据率、链路稳定 性等方面分别来介绍延迟容忍网络的特点。 ( 1 ) 高延迟，低数据率 端到端延迟表示端到端传输路径上每一跳的延迟总和，而每一跳上经历的延 迟是由通过相关链路时的传输时间、处理时间和传播时间组成的，可能还要加上 排队时间。如果我们暂时先不考虑消息的处理和排队时间，则消息的传输时间和 传播时间将直接受下层传输设备的影响。对延迟容忍网络来说，传输率可能较小， 比如水下声学调制解调器和传感器节点中的低功率无线电接收装置，而延迟相对 来说却很大。同时数据率在很大程度上可能是不对称的，例如一个高速率的下行 数据信道和低速率的上行控制信道。在一些特殊的情况下，单向链路的可能性也 是存在的，如在军用中同一些需要隐蔽的装备进行通信。 2 延迟容忍网络路由算法研究 ( 2 ) 频繁的网络中断 在延迟容忍网络中，网络中断可能比连接更普遍，而且中断的原因也不一定 全都是由于出错导致的。尤其是在无线网中，连接中断的原因主要来自节点的运 动和低占空比操作。由于移动引起的断开时可预测的( 例如通过卫星系统、扮演 数据载体的公共汽车等) ；由于低占空比系统操作引起的断开在低能力设备( 如 无线传感器) 中试普遍存在的，也是可以预知的。 ( 3 ) 较长的排队时间 在统计复用分组网络的多跳路径中，与传输和传播时间相比，消息的排队时 间经常对整个延时是起决定性作用的。这样的网络中，排队时间是很短的，很少 超过1 秒( 通常会更小) ，而且当下一个节点无法连接时，数据包就会丢失。相 反，延迟容忍网络的连接断开情况比较常见，节点的排队时间相对而言是非常大 的，有可能达到几个小时甚至几天。因此，这就要求节点必须能够长时间地保存 数据以免丢失。延迟容忍网络和传统网络的链路特点比较见表1 1 ： 表1 1 延迟容忍网络和传统网络的链路特点比较 特点延迟容忍网络传统互联网络 延迟高，可以是几分钟，甚至几天低，毫秒级 数据率不可靠的数据率，上行和下行数据一般能确保双向稳定的 率可能不对称甚至单向链路数据率 网络中断频繁出现，不能简单地丢弃数据包出错，直接丢弃数据包 排队时间较长短暂 1 2 延迟容忍网络的体系结构 延迟容忍网络由于存在频繁的网络分割、节点存储容量有限、设备能源短缺 等各种问题，以致t c p i p 协议在这种网络环境下己不再适用，因此我们必须提 出一种新的独立于i n t e m e t 的体系结构。为了实现这个目的，i r t f 提出了一个 d t n 体系结构标准，在应用层和传输层之间插入一个新的覆盖层网络协议。覆 盖层协议用标准的方式在区域网络的边界上桥接不同的协议栈，能为应用层提供 一个可靠和有效的端到端的数据传输服务。 延迟容忍网络路由算法研究 传输层( t c p ) 网络层( i p ) 数据链路层 物理层 d t n u 图1 - 2i m e m e t 与d t n 体系结构对比 在d t n 体系结构中，定义了一个端到端的面向消息的覆盖层叫做包裹 ( b u n d l e ) 层，它存在于应用层之下传输层( 也可以是其他层) 之上。图1 2 展示 了i n t e m e t 和d t n 的体系结构的比较。 b u n d l e 层提供存储转发的功能，很好地克服了网络的中断【6 。这里介绍的 是d t n r g 组织提出的包裹层协议( b u n d l ep r o t o c o l ，b p ) n 。包裹层的关键功能 包括： 1 处理间歇性的连接。 2 利用预定的、预知的、随机的连接。 3 绑定网络终端标识符和互联网地址。 b pa p p 。 b pa p p jl j b pb pb p b p t r a n s lt l 仃2 1 = v t 3t h n s 3 n e t ln l ，n 2n 2 ，n 3n e t 3 1r l 1r l 图1 - 3b u n d l e 层协议处于互联网模型的应用层 包裹层协议使用本地互联网协议通信( 这里的互联网是广义，不仅仅是 t c p h p 协议) 。在包裹层协议和互联网协议之间是汇聚层适配器。图1 3 显示了 4 延迟容忍网络路由算法研究 三个不同的传输网络协议。 b u n d l e 层形成一个网络覆盖层，使用持久存储来克服网络中断。它包括一 个逐跳的可靠交付责任转移和可选的端到端的确认。为了互操作性，它使用基于 统一资源识别符的非常灵活的命名机制，可以用相同的命名语法来封装不同的命 名和寻址模式。此外，它也包含一个基本的安全模型，用来保护网络设备必须经 过授权才能使用。b u n d l e 层提供了类似网关的功能，在各个底层协议之间提供 互操作性，并且用持久存储设备提供存储转发的功能。在某种意义上说，d t n 体系结构为互连异构的使用存储转发消息来克服通信中断的网关或代理提供了 一种通用的方法，它提供了类似电子邮件的服务，但增强了命名，路由和安全能 力。图1 4 展示了d t n 的体系结构 ( a 用户主机) 图i - 4d t n 的体系结构 针对d t n 的特性，d t n 结构旨在提供各种网络之间的互操作性。从网络管 理的角度看，d t n 网络里的通信属于非交互式通信，适合采用长度适中的报文 交换，而不适合传统网络里的数据包交换。因为使用报文，网络可以预先知道传 输数据的大小和性能要求，便于进行路径选择和时序安排。为了实现不同网络之 间的互操作性，需要在连接点布置特殊的d t n 网关。在d t n 网络中有一些新 的概念和术语，主要有如下一些： ( 1 ) 域和网关 5 延迟容忍网络路由算法研究 d t n 体系结构中包含域、网关，如果两个节点不需要通过网关即可进行通 信，那就称这两个节点在同一个域内，一般使用域内的本地路由协议。域边界用 来表示不同网络协议和地址族之间的互联点，可以使用数量不多的域类型( 例如 i n t e m e t ，移动a d h o c ，周期连接的网络等) 涵盖d t n 网络，并且每种类型都有 相对应的下层协议栈。 d t n 网关类似于a r p a n e t 网关，但是和a r p a n e t 网关不同的是： d t n 关注的是可靠路由，而不是尽力传输的数据包交换； 当要求可靠传输时，d t n 网关负责非易失性的保管报文： d t n 网关要对数据流量进行安全检查。 在图1 4 所示的例子中有四个域，分别为a ，b ，c ，d 。域b 网关3 和网关 5 之间通过布置一辆来回行驶的公交车传送数据。域d 包含一个近地卫星，提供 周期性的连接。 ( 2 ) 名称数组 为了支持d t n 信息的路由，d t n 的命名机制采用名称数组( n a m et u p l e s ) 来标识目标或目标组。名称数组由两个可变长度部分组成，其形式为 域名，实 体名) ， 域名，实体名) 也被称为节点的端点标识符( e i d ) 。在图1 4 中，每个终 端和路由器都是以这种形式表示的。 对于域名而言，有以下特点： 域名是全球唯一的，是通过分级构建的； 域名由d t n 路由器解析送到其它的d t n 网关； 可以采用静态或者动态路由； 不需要像d n s 那样解析到地址。 实体名标识在某一特定域内的名称，只有域名用于路由，实体名则用于在本 地进行解析，目前没有对其强加任何限制，可以采用任何合理的命名机制。当一 个信息传输经过一个长的、不同的域集合时，仅仅用域名来选择路由。在到达目 的域边界时，如果必要，实体名信息被翻译成本地适用的协议标准名( 或地址) 。 这种解析名字的方法导致一个与典型的i n t e m e t 中d n s 解析发生在i p 层数据交 换之前相对的后期绑定的形式。i n t e m e t 中名字到地址的转换发生在数据被发送 到网络之前，可以称之为早期绑定。而在一个经常断丌连接的网络中，后期绑定 6 延迟容忍网络路由算法研究 是非常有利的，因为一个消息的通过时间可能超过一个绑定的有效时间。而且， 使用基于名字的路由和后期绑定可以减少必须在网络中传播的管理信息的数量 和限制映射同步需求的范围。 ( 3 ) 服务级别 d t n 体系结构对交付的通信业务量的优先权提供相对的度量，这些优先权 基于应用层影响交付代理的愿望来区分通信业务量。通信业务通常不是交互的， 经常是单向的，一般没有对及时交付很强的保证，但仍然有一些形式的服务等级。 目前关于d t n 结构的草案里定义了三个传送级别，在发送者队列，这些级别通 常意味着不同的时序优先级。 大块的( b u l k ) ：优先权为大块的b u n d l e 的等级是最低的，这些包会被“尽 力 传输，只有从相同源到相同目的地的所以其他等级的b u n d l e 都被发送后才 能被发送。 。普通的( n o r m a l ) - 普通等级的b u n d l e 优先级大于大块的，在大块等级的 b u n d l e 前发送。 加急的( e x p e d i t e d ) ：加急的等级的b u n d l e 优先级高于其它类型的，可以在 其它等级的b u n d l e 之前被发送。 应用层可以为每个消息指定一个优先权等级和生存期，具体应用程序会指明 等待发送的每个报文的优先级别和生存时间，这些信息和d t n 节点执行的路由 和转发消息的策略影响着消息交付的可能性和适时性。一个消息的优先权等级一 般只和同源消息的优先权相关，这意味着从一个源来的高优先权的消息不一定比 从另一个源来的低优先权等级的消息先发送。 ( 4 ) 使用存储转发操作的消息交换 一个d t n 应用层发送的消息，也叫应用数据单元( a p p l i c a t i o nd a t au n i t ， a d u ) ，该消息可以是任意长度，受具体实现的限制。消息被转换成一个协议数 据单元叫做b u n d l e ，它包含a d u 和用来把b u n d l e 交付给目的地的其他消息。消 息一般以一个完整的单元被应用层发送和交付到应用层。但是在传输过程中，消 息可能被分割成多个b u n d l e ，b u n d l e 也可能被分割成多个组成片段。b u n d l e 的源 和目的地是用可变长度的端点识别符( e i d ) 来标识的。b u n d l e 也包含一个报告 给e i d ，用来把诊断信息直接发送给一个实体。虽然i p 网络也是基于存储转发 7 延迟容忍网络路由算法研究 操作的，但这里有一个假设：存储是不持久的，一般不会超过一个适当的时间， 以排队和传输的时间阶数为限。相反，d t n 体系结构不期望网络链路一直可用 或可靠，而是期望节点可以选择把消息存储一段时间。我们期望大多数d t n 节 点可以使用某种形式的持久存储设备，例如磁盘，闪存等，而且存储的消息可以 在系统重启动时保存着。 一个基于消息的抽象提供了b u n d l e 层在预先知道需要传输数据的大小和性 能需求下的路由。当网络中存在相当多的队列时，知道这些信息对做出调度和路 径选择有很大的优势。而其他的抽象( 如基于流的交付) 将会使得做出这样的调 度变得困难得多。虽然基于数据包的抽象也和基于消息的抽象有一样的好处，但 更大的聚集给网络提供了一种对应用层有用的整个数据单元实行调度和缓存管 理的方法。基于消息的方式的操作的一个基本的要素是消息应该有个地方来存 储，直到有一个可用的通信机会。这突出了下面的假设： ( 1 ) 存储是可获得的，而且很好的分布于整个网络。 ( 2 ) 存储可以足够的持久和稳健的保存消息，直到可以进行转发。 ( 3 ) 这种存储转发的模式比起试图获得持续的连通性来说是一种更好的选 择。 对于一个有效的支持d t n 体系结构的网络来说，这些假设必须被认真的考 虑和保持。图1 5 为消息存储转发示意图： 存储 图l 5 消息存储转发示意图 ( 5 ) 可靠性和保管传输 b u n d l e 层提供的最基本的服务是无确认的有优先等级的单播消息交付。它 也提供可选的两种加强的交付责任：端到端的确认和保管传输( c u s t o d yt r a n s f e r ) 。 希望实现他们自己的端到端的确认的应用层可以不用b u n d l e 层的确认。 d t n 体系结构的保管传输的特色只是指定了一个粗粒度的重传能力。发送 保管传输需求选项被设置的b u n d l e 通常包括在不同的d t n 节点之间移动可靠交 付的责任。对于单播交付，这个过程典型的包括向离最终目的地更近的节点移动 8 延迟容忍网络路由算法研究 消息的一份拷贝。接收到这些拷贝的节点称之为保管员( c u s t o d i a n ) 。保管传输允 许源节点委派重传责任和在发送b u n d l e 后相对快速的恢复重传资源。不是所有 的d t n 节点都需要接受保管传输，所以它不是一个真正的逐跳机制。例如有些 节点在有足够存储资源时可以作为保管员，但当在拥塞或低功耗运行时可以选择 不提供这种服务。保管员的存在可以改变d t n 路由执行的方式。 在一些情况下，尽快的把一个消息转移到一个保管员那里是有益的，即使它 离最终目的地很远。保管传输不仅提供了一个跟踪一个需要特别处理的消息的方 法和识别参与保管传输的节点，它还提供了一个加强可靠消息交付的弱的机制。 通常，保管传输依赖于底层的可靠交付协议，但当需要保管传输时，b u n d l e 层提 供一个粗粒度的超时和重传机制和一个保管员到保管员的确认信号机制。当一个 节点接收带有保管传输需求选项的b u n d l e 时，一个保管传输接收的信号被b u n d l e 层发送到包含在b u n d l e 头部的当前保管e i d ，当前保管e i d 被更新成接收保管 传输的节点的e i d 。当应用层需要一个消息被保管传输时，这个需求是建议性质 的。在某些情况下，一个b u n d l e 的源可能没有能力提供这种服务，这个b u n d l e 在获得保管员之前可能要穿过多个d t n 节点，这个b u n d l e 的当前保管员e i d 被 设置成空的端点。 ( 6 ) 路由和转发 由于d t n 节点可能使用不止一种底层网络技术互联，一个d t n 网络可以 抽象的描述为一个多图，图中的边通常是时变的，当边的容量变成零时，可以认 为他们是断开的。d t n 图的边可能有相当大的时延，我们采用在数据被放入网 络边的节点来度量时间，边的容量和延迟表示为时间的函数。例如，在时间t ， 一个边有容量c ( t ) 矛l l 延迟d ( t ) ，如果在时间t 有b 个比特被放入边，这些比特将 在t + d ( t ) + ( 1 c ( t ) ) 木b 到达。边可能在正的和零容量之间变化，可能存在一个时 间间隔，在这个间隔内，边的容量是严格大于零的，为了便于研究，可以把这个 时间间隔内的时延和容量简单的认为是恒定的。这个时间间隔被称之为接通 ( c o n t a c t ) ，时间间隔和边的容量的乘积定义为这个接通的容量。如果接通和他们 的容量可以被预先知道，智能的路由和转发决定就可以被做出。为了最佳的利用 接通的容量，大的消息可能被分成较小的可路由单元。当接通的间隔和容量不可 精确的预知时，路由计算将会变得非常的困难。目前i r t f 还没有给出一些标准 9 延迟容忍网络路由算法研究 的路由算法，d t n 的路由算法还处在进一步的研究当中。 源节点i n t e r n e t 传输目的节点 应用层 传输层 网络层 数据链路层 物理层 应用层 b u n d l e 层 传输层 阿络层 数据链路层 物理层 i n t e r n e t 主机，i n t e r n e t 路由 i n t e r n e t 路卣l a t e r n e t 主机 源节点dtn传tt目的节点 p o t e h 。t i a l橱 ，o e n 糊d e a y目擎雠钮“柚d 譬a y目 p o t e n t i a l d e 枷 d e l a y c t c t 非t c p 传 c t 非1 1 c p t t 牢p t c p t p 崭传 禽 ； ； ll pl plp 非l 珏网络 非i l网络 ： 8 持续存储 c t c u s t o d yt r a m f e rc a p a b i l i l y 图1 - 6i n t e r n e t 路由和d t n 路由的比较 d t n 体系结构提供了在b u n d l e 层路由和转发的框架，图1 - 6 显示了i n t e r n e t 路由和d t n 路由的比较。 ( 7 ) 时钟同步 d t n 体系结构要求通信方之间时间同步来确认消息部分网，对于d t n 而言， 需要时钟同步是针对面临挑战网络的以下特性： a 网络设备通常布置在偏远或者敌方环境中。这些设备要收集数据，它们 的位置通常是时间的函数，需要对时间进行控制； b d t n 结构不支持实时的传输控制，旨在提供一种机制，用来传输事先规 划好的控制命令，没有时钟同步，这种预先数据分析和规划控制很难实现； c 当报文终止时，同步时钟用来移除报文。 ( 8 ) 安全 1 0 延迟容忍网络路由算法研究 大多数网络安全机制是通过鉴定用户身份和报文完整性来实现的，并没有对 路由器进行鉴定。在一些d t n 中严重的资源稀缺要求某种形式的鉴权和接入控 制，未授权的用户不能轻易的向网络注入通信业务量。许多现存的为低延迟、持 续连接环境而设计的鉴权和接入控制方法可能运行的不是很好。特别的，更新控 制列表和撤回信任状尤其的困难。为了满足这些安全需求，d t n 体系结构采用 了一个标准的但是可选的安全体系，它使用逐跳和端到端鉴别和完整性机制。采 用两种方法的目的是能分别处理数据转发的接入控制和应用层数据完整性。当鉴 权或接入控制检查失败时，d t n 节点尽可能早的丢弃非法通信业务量。具体的 d t n 安全协议可参见 10 】。 ( 9 ) d t n 体系结构的实现原型 i r t f 的d t n 研究小组已经在l i n u x 操作系统下实现了d t n 的原型1 1 】。这 个原型主要包括b u n d l e 路由和转发模块，收敛层模块，持久存储模块，分段模 块，接通管理模块，管理接口模块，控制台和配置模块，应用层i p c 和注册模块， 系统框图如图1 7 所示 蒋久存储模块 收敛层模块 图1 7d t n 原型系统框图 从框图我们可以看出，b u n d l e 路由模块是实现的最中心的部分，它需要关于 延迟容忍网络路由算法研究 系统状态的最详细的信息。路由模块做出的决定被作为一组指令传递到转发模 块，转发模块执行动作。策略和功能的分离允许很容易的扩展修改和替换潜在的 复杂路由模块。 1 3 延迟容忍网络的应用 在许多实际应用领域无法建立结构化的全连通网络，导致传统的a dh o c 网 络协议无法运行，而延迟容忍网络能够更好的满足这些应用需求，因此d t n 的 应用非常广泛，并还在不断的发展之中，今后将有更广阔的应用前景。 ( 1 ) 深空探测 在未来的几十年里，n a s a 以及其他一些机构计划了一系列的月球探测、火 星探测等项目。2 0 0 3 年9 月，c i s c o 低轨路由器( c l e o ) 在英国灾害监测星座的 卫星上搭载升空，至2 0 0 8 年1 2 月，c l e o 在太空环境中进行了很多路由试验， 其中就包括用改进为b u n d l e 覆盖层的s a r a t o g a 协议代替c c s d s c f d p ，以更充 分地利用链路资源和应对极度不对称的链路环境，加快数据的传输，成功证明了 在太空