（通信与信息系统专业论文）延时可容忍网络路由算法研究.pdf

中国科学技术大学硕士学位论文摘要 摘要 随着网络技术的迅猛发展人们对网络应用的要求也越来越细化，从传统网络中不断分 离出新的网络类型来。其中有一类被称为挑战性网络，例如外层空问通信网络、稀疏a dh o e 网络、移动传感器网络等，其特点是不满足端到端路径存在和低延时等传统i n t e m e t 中的基 本假设，因此已有的路由协议不适用于此类环境。在这种情况下，人们提出了延时可容忍网 络( d e l a y - t o l e r a n t n e t w o r k d t n ) 的概念，为此类网络环境研究适用的体系结构，包括了 路由、安全、系统扩展等各方面的考虑，其中又以路由问题最为关键。 长延时、网络分割和节点能力低f 是d t n 路由问题中最大的困扰，也是与传统网络路 由问题的区别所在。研究者在这方面做了大量的工作提出了很多种路由算法，大体上可以 分为基于多报文和基于单报文两种类型。前者会向网络发送多个报文副本。以应对可能发生 的报文丢失，但也会因此引入数据冗余问题，并且难以解决。后者在网络中只使用一份报文 进行传输，从根本上避免了这个问题，近年来受到越来越多的关注，发展前景看好基于以 上考虑，本文将焦点集中在单报文路由中最具实用性和研究价值的一类使用统计信息的路由 算法上，将如何提高路由性能作为研究重点，创新性地做了以下研究： 本文第三章对此种类型已有算法做了深入分析发现没有考虑拓扑图上代价值的突然归 零是m e d ( m i n i m u me x p e c t e dd e l a y ) 算法的最大问题，而其改进算法m e d - p c ( m e dp e r c o n t a c t ) 及变种m e e d ( m i n i m a le s t i m a t e de x p e c t e dd e l a y ) 算法又存在计算量大等严重缺 路。在此基础上本文依照新的改进思路提出a m e d ( a d v a n e e dm i n i m u me x p e c t e dd e l a y ) 算法，可以在完全避免后两者缺陷的基础上大幅提升m e d 算法性能。随后的仿真实验对此 进行了验证。 本文第四章将a m e d 算法推广到节点行为相关性很强和很弱的两种特殊场景。利用前 者有大量本地连接( 指拓扑结构中临时出现的局部连通图) 存在的特点扩展a m e d 算法中 下一跳转发节点的选择范围，并以此提出a m e d l c ( a m e dw i t hl o c a lc o n n e c t i o n ) 算法。 利用后者中节点相遇近似满足独立泊松过程( 或者间歇性泊松过程) 的特点，提出将延时期 望的概念从考虑单条路径时的延时期望转变为考虑所有可能路径后的延时期望，然后对此概 念下的节点延时期望进行了理论推导，并以此为基础结合a m e d 算法提出迭代形式的 a m e d i p ( a m e dw i t hi n d e p e n d e n tp o i s s o np r o c e s s ) 算法。仿真实验验证了a m e d - l c 和 a m e d i p 算法在其相应场景下的有效性，还定性地表明a m e d i p 算法在偏离目标场景的 定范围内都能对a m e d 算法有性能提升。 关键词：延时可容忍网络f f r n路由算法m e d 中国科学技术大学琢士学位论文 a b s t r a e t t h er e q u i r e m e n t so fn e t w o r ka p p l i c a t i o n sa r eb e c o m i n gm o r ea n dm o r er i g o r o u sf o rt h e e v i d e n c eo fs w i ra d v a n c e m e n ti nn e t w o r kt e c h n o l o g i e s n e wt y p e so fn e t w o r k sa r ee m e r g i n g f r o mt r a d i t i o n a ln e t w o r k s t h e s en e t w o r k si n c l u d ec h a l l e n g i n gn a t w o r k , s u c ha so u t e rs p a c e c o m m u n i c a t i o nn e t w o r k , s p a r s ea dh o cn e t w o r ka n dm o b i l es e n s o rn e t w o r k i nc h a l l e n g i n g n e t w o r kt h eb a s i cr e q u i r e m e n t si nt r a d i t i o n a li n t e r o c tc a nn o tb es a t i s f i e d t h e s er e q u i r e m e n t s i n c l u d et h ee x i s t e n c eo f e n d - m - e n dp a t h 1 0 wd e l a y , a n de t c d e l a y - t o l e r a n tn e t w o r k ( d t n ) w a s t h e r e f o r ep r o p o s e dt oa c c o m m o d a t es u c han e wa r c h i t e c t u r e 。i ti n c l u d e sm e c h a n i s m so fr o u t i n g , s e c u r i t y a n ds y s t e ms c a l a b i f i t y r o u t i n gi sc u r r e n t l yt h em o s tc h a l l e n g ep a r ti nt h i sr e s e a r c ha r e a l t h ec h a r a c t e r sw h i c hd i s t i n g u i s h e dd t nf r o mt h et r a d i t i o n a ln e t w o r k si nr o u t i n gi n c l u d e l o n g - d e l a y , n e t w o r kp a r t i t i o na n dl o wn o d ec a p a c i t y r e s e a r c h e r sd i dal o to f w o r ki nt h i sa r e aa n d b r o u g h tf o r w a r dm a n yr o u t i n gp r o t o c o l s ，w h i c hc a l lg e n e r a l l yb ed i v i d e di n t ot w oc a t e g o r i e s ： m u l t i p a c k e tb a s e dt y p ea n ds i n g l e p a c k e tb a s e do n e t h ef o r m e rs e n d sm a n yc o p i e so fm e s s a g e t oh a n d l et e s tp a c k e t s t h u si tw i l li n t r o d u c ed a t ar e d u n d a n c yp r o b l e mw h i c hi sd i f f i c u l tt or e s o l v e o p p o s i t e l y , t h el a t t e ru s e sas i n g l ec o p yt ot r a n s f e ri nt h en e t w o r k , w h i c hn a t u r a l l ya v o i d st h i s p r o b l e m t h i sd i r e c t i o nh a sg o tm o r ea n dm o r ea t t e n t i o ni nr e c e n ty e a r s t h i sp a p e rf o c u s e so nt h e a l g o r i t h m su s i n gs t a t i s t i c a li n f o r m a t i o n ，w h i c ha r et h em o s tp r a c t i c a la n dv a l u a b l ed i r e c t i o ni nt h e s i n g l e p a c k e tb a s e dr o u t i n gf i e l d i ta i m st oi m p r o v et h er o u t i n gp e r f o r m a n c e w eb r i n gf o r w a r d f o l l o w i n gi n n o v a t i o n si nt h i st h e s i s ： i nc h a p t e r3w ef i r s ta n a l y z ee x i s t i n gr o u t i n ga l g o r i t h m s w ef o u n dt h a tt h em a i np r o b l e mo f t h em i n i m u me x p e c t e dd e l a y ( m e d la l g o r i t h mi si t si g n o r a n c eo ft h es u d d e n r e t u r n - t o z e r oo f w e i g h t si nt o p o l o g yg r a p h m o r e o v e r , t h ee x c e s s i v ec o m p u t i n go v e r l o a do ft h em e d p e rc o n t a c t ( m e d - p c ) a l g o r i t h ma n d 。t h em i n i m a l e s t i m a t e de x p e c t e dd e l a y ( m e e d la l g o r i t h mi s u n a c c e p t a b l e w et h e r e f o r ei n t r o d u c et h ea d v a n c e dm i n i m u me x p e c t e dd e l a y ( a m e d ) a l g o r i t h m w h i c hd i s t i n c t l yi m p r o v e st h ep e r f o r m a n c eo fi v i e dw i t h o u tt h ed e f i c i e n c i e so fm e d p co r m e e d w eu s es i m u l a t i o n st ov a l i d a t et h i sa l g o r i t h m i nc h a p t e r4 ，w ea p p l ya m e di n t ot w os p e c i a ls c e n e sw h e r et h er e l a t i v i t yo f n o d e s b e h a v i o r i st o os t r o n go r t o ow e a k i nt h ef o r m e rs c e n e ，t h e r ea r ep l e n t yo f l o c a lc o n n e c t i o n s t h i st e m p o r a l a p p e a r a n c eo fl o c a lc o n n e c t e dg r a p hc a nb eu s e dt oe x t e n da m e d ss e l e c t i o nr a n g eo ft h en e x t f o r w a r dn o d e w ei d e n t i f yt h i si m p r o v e m e n ta sa m e d - l c ( a m e dw i t hl o c a lc o a n e m i o m a l g o r i t h m i nt h el a t t e rs c e n e , n o d e s e n c o u n t e r sa p p r o x i m a t e l ym e e ti n d e p e n d e n tp o i s s o np r o c e s s ， w h i c hi su t i l i z e dt od e d u c tt h ee x p e c t e dd e l a yc o n s i d e r i n ga l lp o s s i b l ep a t h s ，i n s t e a do f o n l yo n e p a t h t h ea m e d - i p ( a m e dw i t hi n d e p e n d e n tp o i s s o np r o c e s s ) a l g o r i t h mi sp r o p o s e d ，w h i c hi s t h ei t e r a t i v ef o r i bo fs u c hd e d u c t i o n s i m u l a t i o nr e s u l t sa r cp r o v i d e dt os u p p o r tt h ev a l i d i t yo f a m e d - l ca n da m e d i pi nt h ec o r r e s p o n d i n gs c e n e s i ta l s od e m o n s t r a t e st h ev a l i d i t yo f a m 【e d - i pi ns c e n e sw i t h i nac e r t a i nd e v i a t i o nf r o mt h et a r g e to n e i i i 中国科学技术大学硕士学位论文 a b s t r a c t k e yw o r d s ：d t n0 ) cr a y - t o l e r a n tn e t w o r k ) , r o u t i n ga l g o r i t h m ，m e d 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含 任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本 研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 保密的学位论文在解密后也遵守此规定。 作者签名： 杯彩 z 一口7 年y , 9zg 日 中国科学技术大学硕士学位论文第一章绪论 第一章绪论 1 1 延时可容忍网络概述 1 1 1 导入背景 传统的i n t e r a c t 通信是基于分组交换来实现的。分组是一个完整用户数据块的组成部分 ( 例如，一条e m a i l 消息或者w e b 网页的组成部分) ，它在由路由器连接的链路所组成的网 络中独立地由源传送到目的地组成消息的每个分组可能使用不同的路径穿越网络如果某 条链路断开了，分组就会选择另一条链路。分组包括用户数据( 净荷部分) 和头标( 控制部 分) 。头标中包含有目的地址和分组从一个路由器交换到另一个路由器所需要的其它信息。 同一个消息中分组可能不是按顺序到达，目的端的传输机制能够将它们按序重组这种传 统的i n t e m e t 通信的可用性依赖于一些重要的假设： l持续的、双向的端到端路径：在源和目的之间的一个持续可用的双向连接以支持 端到端交互。 2 。 往返延时短。在发送分组和接收相应的应答分组时网络延时小而且相对一致。 3 数据速率对称。源和目的之间双向数据速率相对一致。 4 比特误码率小。在每个链路上的数据丢失和被破坏的可能性相对较小。 另一方面，如功率受限的无线移动、卫星和星际通信等应用需要独立的网络。并且支 持特殊的通信需求。最终形成了i n t e r a c t 之外的一大类无线网络，例如：1 ) 连接移动无线 设备，包括个人发报机、智能公路以及远程地面哨所的陆地民用网络；2 ) 连接军队、飞行 器、卫星和传感器( 在地上或者水中) 的无线军事战场网络；3 ) 外层空间网络，例如 i n t e r p l a n e t a r y ( i p n ) i n t e m e t 项目等等。这些网络不使用i n t e r a c t 协议，并且相互之间不兼 容。每个网络适应于一个特定的通信区域，在这个区域内通信特征相对一致。区域间的边 界由链路延时、链路连通性、数据速率不对称性、误码率、寻址和可靠机制、服务质量保 证以及信任边界等来定义。与i n t e r n e t 不同，这些无线网络支持长而且可变延时、任意长时 间的链路中断、高误码率和巨大的双向数据速率不对称性，被归类为挑战性网络。传统 i n t c r n e t 中的经典模式在这里不再适用，主要是可靠传输与路由方面会遇到巨大的困难。 首先是许多应用程序只在数据传输可靠的情况下工作正常，即保证发出的所有数据项 都被成功投递到预定目标( 不考虑系统底层发生需要人工干预的致命错误的情况) ，这就需 要使用某种类型的自动重传请求( a u t o m a t i cr e p e a t - r e q u e s t ，a r q ) 机制。t c p 和u d p 是 两种应用广泛的i n t e r a c t 传输层协议，均是基于i p 的。t c p 使用a r q ，但并不适合于有长 延时的路径。特别是当该路径还包含有时断时续的链路时因为t c p 通信要求发送和接收 方先协商建立用于控制操纵数据流的连接，这就需要在任何应用数据发送前先进行一个来 回的通信。如果传输延时超过允许通信的时间窗口长度，应用数据将无法发出另一个原 因是t c p 只能将收到的数据按照发送的顺序递交给应用程序，这就意味着旦有数据丢失 中国科学技术大学硕士学位论文第一章绪论 要进行重传，该连接上顺序在其之后的数据都将被延迟递交，直到数据重传完成。为了避 免这种阻塞，发送程序必需付出更大的代价以打开多个并行连接并将传输任务分布到这 些连接中最后，t c p 自身对数据丢失和网络拥塞的处理机制也会造成吞吐量随延时增加 而下降【1 0 1 。 在挑战网络中使用t c p 进行多跳通信还会遇到其它问题。t c p 的重传机制是基于端到 端的，这会延迟重传缓存的释放。以一个三跳的通信情况为例如图1 1 所示。假设有a b c d 四个节点a b 问延时5 0 0 r a s ，b c 间延时8 m i n ，c d 间延时l o o m s 为了支持重传，最初的 发送者必须保留报文宣到确信已不再需要重传( 例如目标节点通知该报文已收到) 。如果重 传是基于逐跳完成的，即只在每条链路的两个端节点问进行重传，那么a 节点可以在 1 0 0 0 m s ( a b 闫一个来回的通信时间) 后释放重传缓存空间如果是端到端的重传，a 节点 必须等待至少9 6 1 ，2 0 0 m s ( a - b - c - d - c - b - a ) 再考虑数据丢失的情况，a 节点需要 将报文保留更长的时间。这种延迟的增加实际上代表了对缓存空间消耗的加大。此例中端 到端情况下用于重传的缓存消耗将是逐跳情况下的近千倍以上，任何实际系统都不得不甚 重考虑这个问题。 9 6 1 ，2 0 0 m s 图1 1 端到端重传问题 基于u d p 的方案也不能适用于挑战网络u d p 虽然没有a r q 机制。但却只是把数据 可靠性保证和重传都留给上层( 应用程序或一些中间件系统) 来处理，t c p 遇到的问题在 这里依然存在。此外，出于软件工程方面的考虑，多数程序选择使用可重用的中间件提供 的标准重传机制，一般也是基于端到端的，在挑战性网络中不会比t c p 的重传机制表现更 好。 另一方面为了便于扩展。i n t c m e t 上的路由系统被设计成层次结构。处于顶层的是 b g p ( b o r d e rg a t e w a yp r o t o c 0 1 ) 协议，在由i p 地址聚类而成的a s ( a u t o n o m o u ss y s t e m ) 之间选择路由。在一个a s 内使用的是o s p f 、 s o 的i s i s 、c i s c o 的e i g r p 等路由协议。 这些协议在一个变动的、有多条可能路径的拓扑图中选择路径，因此要求适时地从网络中 的各个地方得到更新数据。这种更新一般都有超时设定，如果在正常的时间间隔内没有得 到某节点路由消息，则假定到该节点的连接已经断开同时这些协议还假定网络不会被分 割计算出的路径里只会包含当前存在直接或间接连接的网络元素。 b g p 是基于t c p 的其在高延时环境中的性能同样受上述t c p 自身问题的影响，特别 是当t c p 不能保持连接时情况尤为严重。而且分布式的路由计算本身对超时设置要求很 高。过早的超时会让路由算法错误地认为连接已断开，而过大的超时值设置又会延迟路由 算法对连接断开的感知从而导致不成功的路由。 2 中国科学技术大学硕士学位论文 第一章绪论 此外一些进行长间隔问歇性连接的网络还会遇到更严重的问题。在这些网络中很可能 某时刻根本没有到目的节点的直接或间接连接，一般的i p 路由计算将无法完成。 综上所述，挑战性网络与传统i n t e m e t 相比表现出很大的不同。如何解决前者遇到的诸 多问题也成为近年来的研究热点，弗且促成了一种新的称为延时可容忍网络( d e i a y t o l e r 锄t n e t w o r k 。斟) 的兴起， 就核心问题而言，研究者在挑战性网络上所做的工作主要是尝试将l n l e m e t 网络体系结 构扩展到有显著延时或中断的网络。由v i mc e r t 和n a s a 喷气推进实验室的工程师在于 1 9 9 8 年开始的i p n ( i n t e r p l a n e t a r yn e t w r o k ) 项目中所做的工作是最初的尝试。该项目致力 于开发星际间的i n t e r n e t ，其基本想法是让地球和距离很远的太空船之间的数据通信能够简 化到像发生在地球上的两个节点间一样在该项目之后有相当一批协议开发工作组和相 关项目得到资助并发展起来i p n 项目组最终发展成为| n t e m e t 协会( i n t e m e ts o c i e t y ， w w w i s o c o r g ) 下的i p n s i g ( i p ns p e c i a l - i n t e r e s tg r o u p ) 。i p n s i g 设计了一种用于大尺度 网络的体系结构。相关的协议开发工作也在推进之中。不过i p n s i g 却遇到了问题：在他们 设想下的星际间网络并不存在而创建一个这样的网络的代价又极其昂贵，因此相关的实 验难以完成。 与此同时。其它的研究者将注意力放在如何将i p n 的概念引入地面网络特别是传 感器网络之中。因为后者与i p n 理念有很多共通之处。由于在传感器网络上进行实验要容 易得多，i p n s i g 在相关研究中的重要性有所下降，基于以上考虑，i r t f ( i n t e m e tr e s e a r c h t a s kf o r c e ) 创建了一个新的研究组d t n r g ( d r nr e s e a r c hg r o u p ) ，d t n 作为一个比i p n 更宽广的概念受到越来越多的关注，并已成为d t n 体系和协议研究的主要力量d t n r g 继承了i p n s i g 的许多成果并提出了他们自己的解决方案，即所谓的束协议( b u n d l e p r o t o c 0 1 ) 另一方面，美国国防部下属的高级研究计划局( t h ed e f e n s ea d v a n c e dr e s e a r c hp r o j e c t s a g e n c y ，d a r p a ) 在2 0 0 4 年初提出一种称为中断可容忍网络的概念，也简称为d t n ( d i s r u p t i o n - t o l e r a n tn e t w o r k i n g ) ，可以认为是原有d t n 概念的另一种推广在此之前。 d t n 研究主要集中在高延时的情景，如 p n 或者稀疏传感器网络；但事实上其它原因也会 引起中断的发生如无线电屏蔽或者频繁进出基站的通信范围等，而这些情景与延时容 忍并没有明显的直接关系。d a r p a 的提案让d t n 的概念变的模糊不清，但就现阶段的研 究来看，在两种含义下的d t n 中使用相同体系结构和协议的可行性很高。 图1 2 描述了三个机构在d t n 研究中的关系本文接下来的内容主要是基于d t n r g 方面的相关工作。因为d t n r g 是三者之中唯一完全公开的研究组。 3 中国科学技术大学顽士学位论文 第一章绪论 t h ee x p e r i m e n t a l w o r ko fd t n r g 图1 2 主要的d t n 研究机构 1 1 2 延时可容忍网络体系结构 i p np r o j e c t c o n t r i b u t i o n st o t h ee x p e r i m e n t a l w o r ko f d t n r g d a r p a n a s a c o o p e r a t i v ew o r k c o f er e s e a r c h 就d t n 目前的发展而言，最具代表性也最披看好的是一种基于重叠网( o v e r l a y n e t w o r k ) 的方案。该方案在每个同质的网络环境中使用已有的全部协议以达到晟好的性 能，而在应用程序和本地原有协议栈之间插入个新的重叠层。该重叠层坍议提供一种在 同质网络环境的边界上进行两种不同协议栈之间相互转换的标准方式，并有效地实现了一 个通用的应用层网关架构，可以为任意数量的应用程序提供服务。d t n r g 的束协议就是 这样一种重叠层协议，运行在特定区域的不同种类的底层协议如现有的i n t e r n e t 协议和 其它更生僻的用于诸如太空通信、复杂传感器网络等挑战性环境的协议之上。该重叠层称 之为柬层。束层和特定区域的底层协议互相配合。使得应用程序可以跨越多个区域进行通 信。如图i 3 所示。 束也被称为消息束层在节点之问存储和转发整个柬( 或者束的分片) 。跨越所有网络 ( 区域) 的柬层协议组成了d t n 。与此相反，束层底f 的层( 传输层及其以下) 的选择要 适应于每个区域的通信环境。 应用程序应用程序 瓣鬻鬟鬣鬻麓鬻束层震戮黧燮黎 陋l 恻引吲 图1 3 束层 4 中国科学技术大学硕士学位论文第一章绪论 束协议描述的是一个比较完整的体系结构，细致地考虑了各方面的问题，以下仅对其中 的主要概念和特点做简要介绍： i 束和束封装 束由三部分组成：( i ) 源应用的用户数据；( 2 ) 控制信息，由源应用为目的应用提供， 描述了怎样处理，存储，抛弃和其它对用户数据的操作：( 3 ) 束头标，由束层插入。与应 用程序用户数据类似，束可以任意长。 束扩展了由i n t e m e t 协议执行的数据对象封装的层次，其封装方式也类似于i n t e r a c t 协 议。束层可以将整个束( 整个消息) 分片，与i p 层将整个数据包分片类似如果柬被分片， 则在最终目的上的束层需要重组这些分片。 2 非会话式的协议 对于具有长延时的间歇性连接的链路，包含了许多次端到端往返的会话式协议例如 t c p 可能需要大量的时间或者完全失败因此，d t n 束层之间的通信使用只需要很少或者 不需要往返的简单会话。任何来自接收节点的确认都是可选的，这依赖于所选的服务的类 别。 支持束层交换的底层协议可以是会话式的，例如t c p 。但是在具有长延时的间歇性连 接的链路上。要实现非会话式的或者最低限度会话式的底层协议。 呆 l 束层束层 、 可选的确认应答 特定区域 协议相关的传输 特定区域 的的 底层协议底层协议 协议相关的确认应答 图1 4 非会话式的束层和会话式的底层 3 d i n 节点 d t n 中的节点就是一个具有束层的实体。节点可以是主机、路由器或者网关( 或者某 种组合) 。用作柬的源、目的或者转发。 主机；发送和域接收柬。但是不转发它们。主机可以是一次束传送的源或者目的 节点在长延时链路上操作的主机的束层需要永久存储来进行束排队，以等待外 出链路可用。主机能够可选地支持监管传送。 路由器：在一个单独的d t n 区域中转发束，也可以成为主机。在长延时链路上操 作时的要求与主机相同。对路由器来说，监管传送支持也是可选的 网关：在两个或者多个d t n 区域之间转发束。也可以成为主机。网关的束层必须 5 中国科学技术大学硕士学位论文 第一章绪论 有永久存储并且支持监管传送。网关提供它们所跨越区域的底层协议之间的转 换。 4 。先存储后转发”的消息交换 d t n 使用“先存储后转发”消息交换来解决由于间歇性连接、长且可变延时，不对称 数据速率和高误码率所带来的问题。这是一个古老的方法，很久以前就在驿马快信制度和 邮政系统中使用。整个消息( 完整的应用编程的用户数据块) 或者消息分片沿着最终将到达 目的地的路径。从一个节点( 交换点) 上的存储位置转移( 转发) 到另一个节点上的存储位 置。 图1 5 。先存储后转发” “先存储后转发”方法也用于电子语音邮件和电子邮件系统，但是这些系统不是单向 中继。而是星形中继，源和目的独立地连接到一个位于链路中心的中心存储设备上。 d 【n 路由器需要永久存储它们的队列，这是因为以下的原因： 幻到下跳的通信链路可能在很长时间内都不可用。 ”通信双方中的一个节点发送或者接收数据可能比另一个节点快得多或者可靠得 多。 c )如果某个上游( 朝目的地方向) 节点或者链路出现错误，或者某个上游节点拒绝转 发消息，则消息发送后可能需要重新发送。 存储位置( 例如硬盘) 可以无限期地保持消息。它们提供一种永久的保存，而不是一般 存储器提供的短期存储i “i c m e t 路由器在查找路由表时使用存储器来存储( 排队) 进 入的分组，但这个时间比较短。一般为几百个毫秒束协议利用这种长期性的消息保持来 来实现延时隔离、监管传送和重发点前移。 5 由传输层终止导致的延时隔离 在i n t e m e t 上，t c p 协议通过重发任何没有经过目的端确认的分段来提供端到端( 源到 目的) 的可靠性。网络层、链路层和物理层提供其它类型的数据完整性服务。在d t n 中。 束层依赖于这些低层协议来确保通信的可靠性。 但是d t n 路由器和网关( 分别指那些能够在d t n 区域内和d t n 区域间转发束的节点) 在束层终止传输层协议柬层因此作为端到端的源和目的节点的代理。由此可以将低延时 区域的会话式低层协议在束层上与端到端路径上其它区域中的长延时隔离开来。 束层独立地支持端到端消息束通常从一个节点传递到下一个节点。尽管柬层可能将 一个束分成多个束片。但除了可选的应答外，束和柬之间是独立的 6 中国科学技术大学硕士学位论文第一章绪论 b i ts t r e a m - 卜节点发送的数据 节点接收的确认应答 口 a 区域的底层协议( 例如1 p ，i p ) 圆 b 区域的底层协议( 例如非1 p ，i p ) 图1 6 d t n 通信示意图 端到端 可靠性 点到点 可靠性 6 监管传送 d i n 在传输层和束层都支持节点到节点的对丢失或者被破坏数据的重传但是没有一 个统一的传输层协议( 可靠传送的主要方式) 能够跨越d t n 进行端到端的操作。端到端可 靠性只能在束层实现。 束层通过监管传送的方法支持节点到节点的重传。这种传送由源端请求，在连续节点 的束层之间进行。当当前束层监管者发送一个束给下一个节点时，它请求进行监管传送并 且启动一个应答时间重传定时器。如果下一跳柬层接受监管，它就回送一个应答给发送 者如果在发送者的应答时间超时之前没有返回应答发送者将重发束应答时间重传定 时器的值可以随路由信息分发给节点或者基于过去到某个特殊节点发送的经验在本地计算 得到。 一个束的监管者必须存储束直到：( i ) 另一个节点接受监管；或者( 2 ) 束的生存时间 过期，这个时间规定比监管者的应答时间要长得多但是应答时间应该足够长，以便底层 传输协议尽可能有机会完成可靠传送。 监管传送不能提供端到端可靠性保证，这只有在源端请求监管传送并且回执才有可能 实现在这种情况下源端必须保留一份束的拷贝直到接收到回执，否则它将重发束。 7 中国科学技术大学硕士学位论文第一章绪论 应用层 柬层 传输层 网络层 链路层 物理层 源节点目的节点 监管节点 篮管节点 i 潜在延时 i 在延时 l 者在延时 q 糨时 戛i - o c tc t i t l i il i - o 永久存储 c t 监管传输能力 柬的监管传输 。一一 监管传输确认应答 图1 7 监管传送 7 向前移动重发点 柬层使用可靠的传输层协议和监管传送一起来实现重发点向前朝着目的端移动重发 点的前进减少了重发跳数、由重发导致的额外的网络负载以及可靠地传送束到目的端所需 的时间。这对拥有长延时或者损耗非常大链路的网络很有用。对于包含有许多损耗链路的 路径。逐跳重发( 随跳数线性增长) 比端到端重发( 随跳数指数增长) 的重发要求要低得多。 s d t n 区域 d t n 是由网络构成的网络，网络中的每个网络都是一个具有相同通信特性的区域。例 如，区域可以是地球i n t e r a c t ，无线p d a 网络、传感器网络、军事战术网络、智能公路行 星表面或者空间b 行器。 每个区域都有一个被d t n 中其它所有区域都知道的唯一的区域标识( i d ) 区域i d 也是每个节点的名字的一部分。d t n 网关是两个或者更多区域的成员。而且是唯一在区域 之间转移消息的方法。 除了以上内容以外，柬协议还有安全等方面的详细考虑。构成了一个完整的体系架 构。本文接下来的讨论以束协议为背景，以上描述构成了d t n 在本文中的基本图像。 1 2 论文的选题意义 自2 0 0 2 年i r t f 成立了d t n r g 研究组以来d t n 方向的研究工作进展十分迅速。先 是k e v i nf a l l 等人为d t n 提出了明确的模型和体系结构【lj ，随后在d t n 的体系结构、安全 和路由等方面的大量工作相继展开，并形成了一系列的草案( d r a f t ) 与此同时d t n 的 应用前景也越来越清晰，在包括移动a d h o c 网络、普适计算( u b i q u i t o u s c o m p u t i n g ) 、生 态环境监测网络【l l 】【1 2 1 、灾害恢复网络【1 3 】和空间综合信息系统等方面都有相关应用，具 8 中国科学技术大学硕士学位论文 第一章绪论 有很强的现实意义这也从另一个方面推动d t n 成为全球范围内的新兴研究热点，一批国 际顶级会议，期刊( 如s i g c o m m 、j - s a c ) 相继推出d t n 专题讨论或特刊，越来越多的 人认同以d t n 的概念将一大批在传统i n t e m e t 模型下得不到很好支持的挑战性网络区分出 来，并为此构建通用的体系结构。以推进该类网络应用的广泛开展。 随着d t n 研究工作的深入d t n 实用化方面也取得了很大的进展，已经有越来越多的 实际应用从中受益。除了空间方面的i p n 和d a r p a 的军事应用之外研究者还将u r n 技 术用于或尝试用于诸如支持发展中国家乡村学校的网络接入，非洲斑马跟踪研究、爱尔兰 湖泊水质监测、北欧社区联网、澳大利亚生物入侵监控等形形色色的应用项目。可以说 d t n 已经开始走入我们地的现实生活这些项目不仅迥异于传统i n t e m e t ，相互之间也是千 差万别将诸多不同的网络纳入统一的框架之下正是d t n 的魅力所在这也使我们有理 由相信，随着d t n 研究的迸一步成熟，d t n 的应用范围将会更加广泛，更多的项目可以从 中受益，d t n 最终会与我们的生活密不可分。 在网络研究领域中。路由问题始终是一个研究中的核心问题。在这一点上相比传统 网络系统，d t n 有其自身非常明显的特点：现有的网络( 有线或无线) 模型中，路由机制都 是建立在一个前提下的，即“在某一时问段内存在一条从源端到目的端的路径”；而 d t n 模型下该假设是不成立的，网络节点( 节点域) 的高度移动性使得节点之闻的物理信道 不断建立和拆除网络长期处于分割状态。因此，解决d t n 中路由问题对整个d t n 研究 工作有着极为重要的意义，也是现阶段的迫切任务另一方面，d t n 的路由研究正处于起 步阶段，从总体上来说还远未成熟，相关的研究前景十分广阔。就现阶段的d t n 路由研究 而言，大量已有路由算法都是基于多报文方式来考虑的，即通过将报文副本发送给多个节点 来增加成功投递的概率。但这样会不可避免地造成大量的数据冗余，给本来就资源紧缺地 d t n 节点带来额外的负担，不利于路由性能的进一步提升。针对这一情况，研究者提出了 一类使用单报文的d t n 路由算法。在整个路由过程中只有唯一一份报文在网络中存在，在 资源消耗方面对比多报文方式有先天上的优势因此受到越来越多的关注，代表了d t n 路 由研究的一种趋势。在这一背景下，本文将研究的焦点集中于此，在提高单报文路由性能方 面做了大量工作，针对已有单报文路由算法的问题提出了一种新的改进算法a m e d ( a d v a n e e dm i n i m u me x p e c t e dd e l a y ) ，并将a m e d 算法分别推广到节点行为相关性很强和 很弱这两种特殊场景中，提出了相应的优化算法a m e d - l c ( a m e dw i t hl o c a lc o n n e c t i o n ) 和a i d e d i p ( a m e d w i t h i n d e p e n d e n t p o i s s o n p r o c e s s ) ，三种算法覆盖了节点行为相关性从 强到弱的大部分场景，构成一个比较完整的方案，具有很高的研究价值和现实意义 1 3 论文主要贡献和结构 本文首先对d t n 中现有地单报文路由算法及其改进迸行了细致的分析指出它们的缺 陷，然后提出一种新的改进算法a m e d ，能够在保留已有算法各自优点的同时避免其相应 的缺陷。接下来本文着重考察了节点行为相关性很高和很低两种特殊场景，利用前者有大量 本地连接存在的特点提出对a m e d 的优化算法a m e d l c ，同时针对后者中节点相遇近似 独立泊松过程的特性。对a m e l ) 算法的路由计算过程进行了该场景下的修正提出a m e d i p 优化算法。仿真结果和分析验证了a m e d 及其两种优化算法在各自场景下能有效提高路由 9 中国科学技术大学硕士学位论文第一章绪论 性能。而三种算法能够分别适应节点行为相关性不同的各种场景，作为一个整体有着宽广的 应用范围。 第一章主要介绍了d t n 的导入背景及其基本概念，描述了其发展过程、现状和趋势。 简单叙述了d t n 的典型体系结构。并指出在d t n 研究中路由问题特别是单报文路由问题 的重要性，强调了d t n 中单报文路由问题研究的前景和现实意义。 第二章介绍d t n 路由研究的现状，先总体概括了d i n 路由算法的特点，指出路由性 能的一般评价标准，然后分别对感染路由类和基于估计类路由算法做了概要的描述与分析。 接着对本文研究的重点基于单报文类的路由算法做了详细的介绍，做为本文后续部分的 背景知识 第三章在一般场景下考察了典型的单报文路由锋法m e d ( m i n i m u me x p e c t e dd e l a y ) 以及其改进算法i v i e d p c ( m e dp e rc o n t a c t ) 和变种m e e d ( m i n i m a le s t i m a t e de x p e c t c d d e l a y ) 算法。指出它们各自的设计缺陷。在此基础上，提出一种新的改进算法a m e d 既 能有效提升m e d 算法路由