（通信与信息系统专业论文）容迟网络路由路由算法研究以及改进.pdf

重庆邮电大学硕士论文 摘要 摘要 容迟网络是一种通用的、面向消息的、具有可靠体系结构的网络模型。这种网 络模型适用于全球移动网，卫星通信网，长距离无线链路，水下声学调制通信，自 由空间光通信、军用a d - h o c 网、传感器网等多种网络模型，有着很强的理论研究 和实用价值。 本文以容迟网络的组播路由算法为主要研究对象，分析了现有的组播路由算法 在容迟网络应用中的优缺点，并在此基础之上，提出了一种在e p i d e m i c 算法上进行 改进的组播路由算法。 本文的核心是将动态编制引入到e p i d e m i c 算法中。目前容迟网络的组播路由算 法主要分两类：一类是基于知识库的，另一类是基于概率的。基于知识库的组播路 由算法鲁棒性太弱而基于概率的组播路由算法信息量又太大，针对这两个问题，本 文提出了动态编制的概念。动态编制的基本思想就是根据历史信息按照节点相遇率 来划分节点，将经常相遇的的节点划分为同一编制。在传输信息到目的节点的时候 按照两级寻址方式对信息进行转发，这种改进的e p i d e m i c 算法将信息的转发范围控 制在一定范围内，在有限范围内进行洪泛，达到提高算法鲁棒性同时减少网络负荷 的作用，本文从信息传输成功率和平均端到端延迟两个方面对改进的e p i d e m i c 算法 的改进性能进行评估。 本文在改进的e p i d e m i c 算法中也提出了对容迟网络的组播成员管理的改进和 对信息转发优先级的改进，由于容迟网络频繁中断和长延时的特性，我们很难确定 实际的组成员，所以需要建立容迟网络的组播网络模型，根据模型来对组播成员的 筛选，本文主要采用的是t m 模型得到信息的组播成员。此外，由于容迟网络采用 “存储转发”的方式来传输信息，但是因为节点的存储能力是有限的，所以在节 点所存储的排队信息中，应该按照一定的策略选择哪个信息最先转发，本文提出了 o l d e r s t ( o l d e rs t a m p e r ) 、f i f o ( f i r s ti nf i r s to u t ) 和r a n d o mw a yo u t 三种转发策略， 来保证信息的达到率。 本文主要是在o n e 仿真平台上实现各种组播路由算法的仿真，通过在不同的 节点密度、信息量和节点移动速度的条件下，对比各种组播路由算法的信息到达率 和端到端的延迟，最终得出基于编制的e p i d e m i c 组播路由算法的性能更优。 关键词：容迟网络，组播路由算法，动态编制，e p i d e m i c 路由算法 重庆邮电大学硕士论文 a b s t r a c t a b s t r a c t d e l a y - t o l e r a n tn e t w o r k ( d t n ) i sac o m m o n , m e s s a g e - o r i e n t e d ，s t a b l ea r c h i t e c t u r et o c o n n e c tn e t w o r k sw i t hh i g hl a t e n c ya n dl o wd a t ar a t e i ti ss u i t a b l ef o rt e r r e s t r i a l m o b i l e n e t w o r k s ， s a t e l l i t e c o m m u n i c a t i o n s ， v e r yl o n g - d i s t a n c e r a d i ol i n k s ， c o m m u n i c a t i o nu s i n ga c o u s t i cm o d u l a t i o ni nw a t e r , f r e e - s p a c eo p t i c a lc o m m u n i c a t i o n , m i l i t a r ya d h o cn e t w o r k s ，s e n s o rn e t w o r k sa n ds oo i li ti sv 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 t h i st h e s i sf o c u s e s0 1 1d e l a y - t o l e r a n tn e t w o r k i n gm u l t i c a s t i n gr o u t i n gp r o b l e m s a f t e r t h ek e yf e a t u r e sa n ds e m a n t i cm o d e la r ei n t r o d u c e d , w ec o m p a r et h et y p i c a lm u l t i c a s t r o u t i n ga l g o r i t h m s ，a n a l y z et h ea d v a n t a g e sa n dd i s a d v a n t a g e s ，u p o nt h i s , w ec o m b i n e 谢li td t no w nc h a r a c t e r i s t i c a n dp r o p o s ean e wm u l t i c a s t i n ga l g o r i t h r n s ，w h i c hi st h e i m p r o v e m e n tu p o ne p i d e m i ca l g o r i t h m s 。 i nt h ec o r ec h a p t e r , p r o p o s i n gai d e ao fa p p l y i n gd y n a m i cp r e p a r a t i o nt oe p i d e m i c a l g o r i t h m s c o n t r a r yt or o b u s t n e s so fg e n e r a lm u l t i c a s tn e t w o r kp r o t o c o l a n dm o l e r e d u n d a n c et r a f f i co fe p i d e m i ca l g o r i t h m s t o i m p r o v et h ep e r f o r m a n c eo fn o d e d e l i v e r yr a t i oa n da v e r a g ed e l a yb e t w e e nn o d s w ep r o p o s et h ec o n c e p to fd y n a m i c p r e p a r a t i o n i n t h i sv i e w , w ec l a s s i f yt h en o d e s ，o nt h eb a s i so f n o d em e e t i n gp r o b a b i l i t y t h em e s s a g ef l o o d sb e t w e e nc a b l er a n g ei n s t e a do f e v e r y w h e l ei nt h en e t w o r k o t h e r w i s e s ，w ea l s oh a v es o m er e s e a r c ho nt h eg r o u pm e m b e r s h i pm a n a g e m e n ta n d i n f o r m a t i o nm u l t i c a s tf o r w a r d i n gs t r a t e g y a c o r d i n gt od t nn e t w o r kl i n kc h a r a c t e r i s t i c s , w ee s t a b l i s hd t nm u l t i e a s t i n gn e t w o r km o d e a n dt h e r ea r et h r e em e t h o & t os e l e c t m u l t i c a s tm e m b e r s a n dt h e nw eg e tt h ei n t e n d e dr e c e i v e r sw h i c hc a l lr e a l l yg e tt h e m e s s a g e w i t ht h i sm e t h o d , w ec a l li n c r e a s et h ed e l i v e r yr a t i oo fm e s s a g e t h ed t n n e t w o r ku s i n g s t o r a g e - f o r w a r d m e t h o dt ot r a n s m i ti n f o r m a t i o n a n dn o d es t o r a g e c a p a c i t yi sl i m i t e d , s oi t i sn e c e s s a r yt oc h o o s eam e t h o dw h i c hc a nd e f i n eh o wt o t r a n s m i tt h em e s s a g ew h i c ha r eq u e u i n gi nt h en o d e , h e r e , w ep r o p o s e da o l d e r s t s t r a t e g yt ot r a n s m i tt h em e s s a g e i nt h i sp a p e r ，ec a l ls i m u l a t et h es i m u l a t i o na c c o r d i n gt os i m u l a t i o ns o f t w a r e , a n dw e c a nc o m p a r et h ep e r f o r m a n c eo fe a c ha l g o r i t h r n si nd i f f e r e n tc o n d i t i o n s 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 ，m u l t i c a s t i n gr o u t i n ga l g o r i t h m s ，d y n a m i c p r e p a r a t i o n ，e p i d e m i ca l g o d t h m s 重庆邮电大学硕士论文 第一章绪论 1 1 研究背景 第一章绪论 当前，因特网成功的体系结构和t c p i p 协议使它成为全世界大部分地区用于通 信互联的事实标准。但是，当面对长时间延迟的路径，频繁的网络重新分割，而节 点存储容量有限，设备能源短缺等情况时，原有的因特网体系结构的不足就暴露出 来。针对这个问题，很多人提出了解决方法，但是所有人都是在原来的网络协议的 基础上来做改进的，人们认为现在的因特网标准协议已经足够解决这个问题了，但 是在一些特定的场景中，这些协议是行不通的，因为现有的因特网体系结构所用到 的t c p i p 协议族之所以能够平稳运行是依赖如下物理链路特性假定的：在数据源 和目的地之间存在端到端的路径；在网络中任何节点对之间的最大往返时间( r ，i ，r ) 不能太长；端到端的分组丢失率较小【l 】。因此，在一些移动通信网中不使用一般 的网络协议而采用专用协议。k f a l l 等科学家于2 0 0 2 年在i c i r 会议上提出了延迟容 忍网络( d e l a yt o l e r a n tn e t w o r k ，d t n ) 【2 】的架构用于专门解决上述问题的，延迟 容忍网络获得也因此受到了广泛的关注。 为了解决容迟网络( d e l a y t o l e r a n tn e t w o r k ，d t n ) 的延迟和中断问题，科 学家提出了很多解决方案，在三个层次上定义了容迟网络协议：链路和传输层协议、 传输层协议、覆盖网络( 即应用层) 协议，但是就目前容迟网络的发展来看，最具 代表性的也就是最被看好的就是一种基于覆盖网( o v e r l a yn e t w o r k ) 【z j 的方案。并 且在这个层次上提出了新的协议b u n l l e 协议( 包裹层协议) 和l t p 协议( 链路传输协 议) 等等，来解决容迟网络延迟和中断的问题。 容迟网络组播是节点之间- n 多或者多到的数据传输方式。随着通信网络的发 展以及通信研究领域的深入，一方面，组播技术已经成为容迟网络研究中的一种关 键的技术，例如在军事战场中，利用组播技术可以将控制中心的命令快速、可靠地 发送到各个现场指挥基地，并实现士兵之间的有关战场周边环境信息的共享；在灾 难营救过程中，通过组播技术，可以快速地实现营救工作者之间共享伤者有关的信 息以及现场可能存在的一些潜在危险。另一方面，组播路由能够提高网络的资源利 用率，降低通信成本，节约带宽。因此，如何根据容迟网络的特点，设计有效的组 播路由算法，是当前的一个研究热点。 重庆邮电大学硕士论文 第一章绪论 1 2 研究现状 容迟网络的研究热点很多，比如容迟网络的路由问题，组播问题、安全问题、 拥塞控制和流量控制问题等等。 在路由问题上，研究者更多的研究的是单播协议，目前已经有了许多单播路由 协议，比j z i f c ( f i r s tc o n t a c t ) 、m e d ( m i n i m u me x p e c t e dd e l a y ) 、e d ( e a r l i e s td l i v e r y ) 、 e d l q ( e a d i e s td e l i v e r yw i t hl o c a lq u e u i n g ) t 3 1 ，此外，还有一种专门针对稀疏节点提出 的协议e p i d e r n i c 协议，此协议类似于洪范算法，在节点比较稀疏的网络能够提 高信息的传输成功率，但是当信息量比较大的时候会增加网络的负荷，还有一种在 e p i d 谢c 协议【4 】上改进的基于历史信息的p r o p h e t 协议【5 】，但是这里提到的协议都是针 对单播路由的，对组播以及多播瞄】的相对要少一些。国外的一些学者致力于容迟网 络中的组播技术的研究，也取得了一定的成果。但其研究还处在一个起步的阶段， 到目前为止，还是没有一种有效的组播路由协议。 在安全问题上，容迟网络的安全模型与传统的网络安全模型有很大不同。现有 的大多数网络安全方法试图去认证用户的身份和消息的完整性，而不认证转发消息 的路由器。但在容迟网络中，转发节点( 路由器或网关) 也需要被认证，且发送者消 息被转发节点认证以使得通过防止禁止流而使得网络资源被保存。为了实现安全模 型，每个消息通过加一个不变的“邮戳( p o s t a g es t a m p ) ”来保持发送者标识、一个 和消息相关的请求c o s 的批准、及其他密码方法来校验消息内容的正确度在容迟网 络的每一跳，容迟网络的路由器检查证书，并尽可能早地丢弃认证失败的业务流。 在拥塞和流量控制问题上，作为一个逐跳通信体系结构，容迟网络的流量控制 和拥塞控制是紧密相联的。容迟网络中的流量控制指的是限制容迟网络转发器向它 的下一跳的发送速率。拥塞控制指的是如何处理长期存储在d t n 转发器中的内容。对 于流量控制机制的执行，容迟网络转发器试图利用本区域中下层传输协议使用的流 量控制机制。对大多数成熟网络来说，这样的一些机制已经存在，例如t c p ，x 2 5 ， r t s c t s ，x o n x o f f ，直接接人速率控$ ! | t 6 j 等。通常情况下，在容迟网络中是假定 流量控制机制是存在的，并可以确保消息的可靠传递。和其他网络相比，d t n 的拥塞 控制是相对困难实现的，主要因为如下两个特性：第一，在将来的一段时间可能无 法建立连接( 如此累积的数据可能在不久的将来没有机会传出去) ；第二，除非在极 端情况或过期后，否则已经收到的保管消息不能被丢弃。目前主要使用基于优先级 的f c 来分配保管存储。如果容迟网络转发器接受合同外的保管消息，那么将出现阻 塞。这样，节点的长期存储可能被完全消耗掉，因此，要避免非保管消息传输。拥 塞控制机制可以分为主动和被动两类。主动( p r o a e t i v e ) 方法通常包括一些接人控制 2 重庆邮电大学硕士论文第一章绪论 形式去避免在开始处的拥塞攻击。许多情况下，一个单区域可能是在一个单实体的 管理控制之下，这种方法是实用的。除此之外，任何过期的消息都将被安全丢弃。 如果主动方式是不够的或不可用时，则就需要使用被动( r e a c t i v e ) 方法，这将使得 性能下降。 除此之外，如何实现容迟网络与传统网络互联、如何设计容迟网络的缓存机制、 如何在容迟网络中传递大量模块等问题仍在研究当中。 1 3 论文主要工作及创新点 本文主要讨论容迟网络的组播路由问题，主要对以下几个问题进行研究： 第一，分析容迟网络的链路特征，分析容迟网络的单播以及组播模型的特点； 第二，根据历史相遇概率，建立节点相遇概率信息库，将节点归类( 编制) ； 第三，简单分析e p i d e m i c 算法，将节点的编制号考虑到路由的选择中，对此协 议进行改进，使之能够传输组播； 第四，根据组播模型，将加入到这个组的组成员进行筛选，得至u i n t e n d e d r e c e i v e r s ； 第五，使用仿真软件o n e 对容迟网络进行场景仿真。在不同的资源条件和链路 条件的模型中对改进的e p i d e m i c 算法的性能以及其它的算法进行仿真研究和评估。 1 4 论文结构 本论文共分为六章。各章的内容做如下安排： 第一章介绍了本文的研究背景、研究现状，概括了本文的主要工作内容，已经 本文的主要创新点。 第二章介绍了容迟网络的发展状况，对客迟网络和传统互联网的体系结构作了 比较，同时也介绍了单播和组播的网络模型。 第三章分析了容迟网络的组播设计目的，给出了信息库的概念，并且分析了现 有的组播网络路由算法，分析其优缺点。 第四章提出了动态编制的概念，将动态编制引入到e p i d e m i c 算法中，提出一种 新的组播算法。 第五章介绍了o n e 仿真平台，在这个仿真平台上对改进的e p i d e m i c 算法和其 它组播算法的性能进行比较 第六章对本文所做的工作进行总结和展望，指出存在的不足以及下一步的工作。 3 重庆邮电大学硕士论文 第二章容迟网络的概述 第二章容迟网络的概述 2 1 容迟网络的产生 容迟网络最早的提出是在1 9 9 8 年为了解决星际网络( i n t e r p l a n e t a r y i n t e r n e t ，i p n ) 【7 】之间的通信，由n a s a 喷气推进实验室( j p l ) 提出来的，他们的 最初设想是使得地球和距离很远的卫星的通信像地球上任意两点间通信一样容易， 这个小组最后发展成为i n t e r n e t 协议特别兴趣小组，即i p n s i g o 。不过i p n s i g o 在研 究过程中发现模仿星际网络是非常困难的，许多的研究者开始研究如何将星际网络 应用在陆地网络上面，人们发现传感器网络比较类似于星际网络，而且这种网络在 实现上比星际网络要简单很多，由于这个原因，i r t f 研究组( i n t e r n e tr e s e a r c ht a s k f r o c e ) 成立了新的工作组寻找更通用的延迟可容忍网络，这个工作组称为d t n r g ( d t n r e s e a r c hg r o u p ) ，是现在d t n 体系结构和协议研究的主要公开组织。2 0 0 4 年初，美 国国防部下的d a r p a ( d e f e r i c ea d v a n c e dr e s e a r c hp r o j e c t sa g e n c y ) 提出了 “d i s r u p t i o nt o l e r a n tn e t w o r k i n g ”，这种网络可以看作同容迟网络( d e l a y t o l e r a n tn e t w o k i n g ，d t n ) i s 】同一概念下的另一种叙述也简称为d t n ，但是这里的d 是中断的意思。d 在d t n 中可以表示中断也可以继续表示延迟，但是在很多时候，同 一个体系结构或者协议能够同时支持这两种情况。图2 1 为d t n 网络发展概况。 嚣t 蹦i 咻拱删工f # 图2 1d t n 的发展以及各发展小组关系 4 重庆邮电大学硕士论文第二章容迟网络的概述 2 2 容迟网络的体系架构 容迟网络的体系结构不同于i n t e n e t 的体系结构瞄1 ，它被设计来解决受限网络存 在的问题。在容迟网络中引进了一个“捆绑层( b u n d l el a y e r ) ，这个层是在应用层 和传输层之间插入的确保端到端可靠的数据传输服务，是一个面向异步消息传输的 覆盖网，操作在不同网络的传输层上。“捆绑层 提供和i n t e n e t 网关相似的功能， 但有很大区别，因为它聚集在虚消息转发而不是分组交换。 容迟网络的体系架构是基于消息( 1 订e s s a g e ) 交换【9 】的，其数据单元可能是消息、 分组或“捆绑( b u n d l e s ) 。一些消息聚合在一起传递被称为“捆绑 ，处理它们的 路由器被称为“捆绑转发器( b u n d l ef o r w a r d e r s ) 或d t n 网关。b u r l e i g h 等人提出了 一个新的端到端覆盖层网络协议，称为“绑定( b u n d l i n g ) ”，它的功能类似于i n t e n e t 中d n s 的域名到地址的映射。包裹层提供存储转发的功能，很好地克服了网络的 中断，图2 2 比较了i n t c t n e t 和d t n 网络的体系结构【l o 】。 传输层 网络层 数据链路层 物理层 应用层 b u n d l e 层 传输层 网络层 数据链路层 物理层 图2 2i n t e r n c t 与d t n 架构的区别 2 3 容迟网络主要特点 2 3 1 容迟网络链路特征 传统的互联网通常用以下特征描述：延时、数据率、错误率、链路稳定性。我 们以此为基础介绍延迟容忍网络的链路特点： 高延迟，低数据率 如果我们先暂时不考虑消息的处理和排队时间，则消息的传输和传播时间将直 接受到传输设备的影响。有些网络的传输速率很低( 如水下声学调制解调器和传感器 节点中的低功率无线电接收装置) ，延迟相对来说却很大。同时，上行和下行的数据 重庆邮电大学硕士论文 第二章容迟网络的概述 率很可能是不对称的。在一些特殊的情况下，单向链路的可能性也是存在的，如在 军用中同一些需要隐蔽的装备进行通信。 连接中断 在延迟容忍网络中，连接中断频繁，中断的原因也不一定全都是由于出错导致 的。尤其是在无线网中，连接中断的原因主要来自节点的运动和低占空比操作。由 运动造成的断开是比较容易预测的( 如卫星的运动) ，同时也具有比较大的偶然性( 如 节点通过随机运动进入通信范围) 。后者在低能量设备( 如传感器网络) 中比较常见， 也是可以预测到的。 较长的排队时间 对于跳数较多的传统的分组网络中，消息的排队时间经常对整个延时是起决定 性作用的。但在这些网中，排队时间是非常短的，一般都远远小于1 秒钟。而且， 当下一个节点无法连接时，数据包就会丢失。相比之下，延迟容忍网络的连接断开 情况比较常见，节点的排队时间相对而言是非常大的，有可能达到几个小时甚至几 天。因此，这就要求节点必须能够长时间地保存数据以免丢失。 2 3 2 容迟网络终端系统的特点 容迟网络的节点有主机和路由器两种功能，而且容迟网络的节点有能量消耗等 方面的特征，具体如下： 有限的寿命 在很多环境下，如军事用途中，传感器网，或者在紧急情况下搭建的节点，它 们的寿命都是比较短的。理由很简单，在敌对的环境下，或者能源紧缺的地方，网 络节点随时都可能被拆除或由于能源问题停止工作。在这种情况下，一个特定的消 息的双向或单向传递时间就很有可能超过它的发送节点的寿命，而这就会导致端到 端的认证方式不起作用。在这种情况下，我们就需要使用其他的认证方式来确保消 息的传递。 低占空比操作 当节点的工作环境是缺乏能源的时候，它的数据通信方案就要被预先安排好。 占空比低于l 的情况是比较理想的，因为它可以保持网络较长的寿命。这样的设 备会周期性地收集数据，并以一个另外的频率( 可能比较低) 报告它的数据。对于这 样的网络，传输时间的安排就同路径的选择一样，对路由算法就有了特别的要求。 有限的资源 在我们所提到的一些网络中，节点的存储空间和数据处理能力是有限的。我们 假设有一个传感器网络的节点，它的存储容量并不大，我们用它来收集一些随机物 6 重庆邮电大学硕士论文第二章容迟网络的概述 理现象的数据。这样，由于数据有可能不能及时发送出去，则这些数据的拷贝将会 被保存在节点中。由于节点的存储空间有限，这就使得节点无法正常地继续搜集数 据并予以存储。同时，终端节点的重发送缓冲区必须把数据保存一定的时间，这个 时间至少等于每次重发送的回路时间乘以需要重发送的次数，而这个时间有可能是 非常长的。在这个时间段内，如果这个节点具有非易失性存储功能的话，它也许会 将节点关闭以节省能源。这样就大大复杂化了系统的设计。我们举这个例子是要说 明，如果网络的设计是要保证数据传输的可靠性，终端节点必须具备快速地清空它 们的重发送缓冲区的能力，并不需要等待一个端到端的安全认证。 2 4 容迟网络的应用 容迟网络是由于网络的频繁分割断开( n a w o r kp a r t i t i o n d i s c o n n e c t i o n ) 而形成 的。它不是某一种特定的网络而是网络中某些特殊节点形成的，在这里我们将容迟 网络看作一个建立在u n d e rl y i n g ( l 匕如a dh o c 网络) 上面的覆盖层，它的网络架构是 基于异步消息( 捆绑束) 传输的，只有具有容迟网络功能的节点才能发送和接收消 息，其它的节点为正常节点，一个容迟网络链路可能包含下面网络的很多链路( 物 理链路) ，下图2 3 是d t n 网络的简单例子i l o 】。 0 1 nr 蝴d e 昕科l i n k o n o 舢1 d p 一囊r “1 1 “h 图2 3d t n 网络的简单例子 由上图我们可以看出容迟网络可以应用于不同类型的网络，以下是容迟网络的 应用范围： 陆地移动网络( t e r r e s t r i a lm o b i l en e t w o r k s ) 在许多情况下，由于节点的移动性或射频( i 江) 冲突，这些网络可能变得不可想 象的割裂开。在一些情况下，网络可能难以形成一条端到端( e 2 e ) 的路径，并且网络 的割裂方式可以预测。例如，一辆经常往返的公共汽车可以被用作消息存储和转发 的工具，因为它只有有限的r f 通信能力，也就是有限的通信范围。当这类公共汽车 重庆邮电大学硕士论文 第二章容迟网络的概述 从一个地方行进到另一个地方时，它可以在附近的客户机( c l i e n t s ) 和它将去往地点的 远程机( r e m o t ec l i e n t s ) 之间提供消息交换服务。 外来媒体网络( e x o t i cm e d i an e t w o r k s ) 外来通信媒体包括近地卫星通信、长距离无线链路( 例如秒级或分钟级传播延迟 的太空通信) 、在空气或水中采用声波调制的通信等。这些系统可能有可预言的高延 迟( 例如由于行星的动态性) 、也可能因环境因素引起的损耗、或者提供一种可预期 的偶尔可用的存储转发网络服务( 例如每天一次或多次通过的低地轨道通信卫星) 。 军事无线自组织网络( m i l i t a r y a d h o en e t w o r k s ) 这类网络可能部署在敌对环境中。节点的移动性、不可预测的环境因素或者故 意的人为干扰都可能引起网络割裂。除此之外，当有高优先级的业务时，低优先级 业务需要和高优先级业务去竞争带宽，这将使得消息转发经历更大的排队延迟。同 时，出于可靠与安全考虑，这类系统需要有严格保护措施的下层基础结构。 传感器和传感器执行器网络( s e n s o ra n ds e n s o r a c t u a t o rn e t w o r k s ) 这类网络中的节点存在着严重的能量、存储空间和计算能力的不足。此外，这 类网络可能规模很大，包含数千乃至数百万量级的节点。为了保存能量，这类网络 中的通信常常是预订的，可能在一段时间内不存在及时的通信路径。传感器和传感 器执行器网络通常通过具有协议转换能力的代理节点与其他网络互联。 2 5 容迟网络的网络模型 由上图2 3 我们可以知道一对d t n 节点之间的链路可能不止一条，所以可以得 出在两个相同d t n 节点之间传递数据的时候可能会用到截然不同的两个物理链路， 这样，链路( 频繁中断) 的容量是时间独立的( 当链路不可用的时候，链路的容量 为零) ，因此，我们必须掌握每条边的变化的容量和传播延迟。如下图2 4 是用图形 表示两点之问的链路情况。 2 5 1 容迟网络的单播网络模型 8 重庆邮电大学硕士论文 第二章容迟网络的概述 图2 4 d t n 节点之间链路 由于容迟网络的特殊性，所以在容迟网络节点对之间链路可能有很多，我们通 过如下特点来定义网络的模型【1 1 1 。 连接( c o n t r a c t ) ：一个连接就是一个通过一条边传输数据的机会。更准备地说， 它就是一个特定的边以及一个相对应的时间段的集合，在这个时间段内边的传输容 量是一个正数，其值等于在单位时间可以传递的最大数据量。更精确的说，一次连 接( c o n t r a c t ) 就是一条特殊的边，这个边在特定的时间段里面是有效的，比如上图 2 4 ，在时间5 和时间l o 之间以及在时间5 0 和时间6 0 之间e 1 是有效的，而在时间 3 0 和时间3 5 之间e 2 有效。如果有一个节点在时间0 在节点a 产生，那么最优的路 由就是e 1 ，最短的等待时间是5 。 信息( m e s s s a g e ) ：通信是通过信息来传递的。一个信息包含四个参数，由一个 组0 ，v , t ，m ) 来表示的，在这里材代表信息的源端，代表信息的目的端，f 代表消息 到达的时间，m 代表信息的大小。通信的需求是通过消息来体现的。所有的消息的 集合被称为通信量需求( ( t r a f f i cd e m a n d ) 。 存储( s t o r g e ) ：在d t n 中的节点具有一定的存储能力，用于存储在转发中的 信息和等待被目的节点使用的信息。在这里，我们说的存储能力专门用于存储转发 信息。 路由( r o u t i n g ) ：路由先存储在这个节点上面。然后用路由算法的出最佳的路 由，信息在节点中等到，直到路由可用。 2 5 2 容迟网络的组播网络模型 图2 5 组播网络模型 传统网络比如i n t o n e t 和m a n e t 的组播模型是非常直观的，因为网络中数据 的传输延时非常小，所有在数据传输中的组播成员关系变化是非常容易获取的，而 9 重庆邮电大学硕士论文第二章容迟网络的概述 且因为延迟非常小，这样在组播成员变化的时间之内，消息就可能已经传送到目的 节点了。但是在容迟网络中，由于频繁分割和随之而来的比较大的延迟，所以很难 确定组播成员的变化，所以怎么样去定义一个组播包的接受者就变得非常困难。举 一个简单的例子，源端在时间t 发送数据到一个组，我们设t 是其它节点能够接受 到消息的最早时间，节点a 加入这个组在( 厶 f ，) ，离开在时间t ，t t 2 f ，从 来没有离开了过，从传统组播网络的观点来看，我们不能确定哪一个节点接受了这 个消息，或者是a 、或者是b 、或者它们两个都接收了或者都没有接受。对于节点 a ，在消息产生的时候它是组里面的成员，但是对于在消息能够到达的最早之前节 点a 已经离开了，对于b 来说，情况恰好相反，所以我们需要新的组播模型，通过 这种模型可以清楚的定义组播包的接受者，在容迟网络的这种模型下，消息的接受 者和组成员是不一样的，前者是消息能够送到的目的点的集合，而后者随着目的端 发送的加入和离开信息而不断改变的组，通过组播模型对成员的限制，我们能够确 定消息能够送到的目的点的集合。在这里，主要有三种组播模型 i 临时成员模型( t e m p o r a lm e m b e r s h i pm o d e l ) 【1 2 】 在t m 模型中，一个消息包含一个成员间隔时间，用来确定这个时间内的目的 成员，对于一个消息( i d 为g ) ，设置间隔时间【f l ，t 2 】，那么消息的接受者就可以定 义为 f l ，t ，】时间段内都有效的组播成员。在t m 模型中，我们可以有效的定义一个 组播组的接受者，但是在t m 模型中并没有考虑到传输的限制，所以消息在任何时 刻都可以传送。由于环境以及路由算法的限制，消息的实际接受者只能是这个消息 的一个子集。t m 模型允许用户在不同的时间段选择不同的接受者，以图2 5 的模 型为例，一个消息在节点s 上于时间0 产生，如果间隔时间设为【0 ，l 】，那么接受者 为 足，尺2 ，r ，蜀 o 临时传送模型( t e m p o r a ld e l i v e r ym o d e l ) 【1 2 】 t d 模型是在t m 模型上发展起来的，这种组播模型主要考虑的是组播组成员 在传输上面的限制，消息明确指定成员间隔时间和传输最高时间，传输最高限制时 间指的是在这段时间段里面消息必须传送给接受者，这种组播模型是建立在上面所 提到的t m 模型的基础之上的，所以消息的接收者应该是在t m 模型中确定的节点 中选择，将r 设为网络中所有目的节点的结合，成员( r f ，f ”) 满足目的节点r 是 在【f 1 ，t ，】时间内是组成员，t o 是消息的产生时间，d ( t ，) 是以时间t 开始消息的源端 到达目的端的最小延迟。我们可以通过d i j k s t r a 算法来确定d ( t ，) ，对于d 为d 的 消息的组成员，成员间隔为 f l ，乞】，传输间隔为 f ，f 4 】。接受者的集合k 确定如下： = r m e m b e r ( r , ，”) - - t r u ea n da ( t o ，) + t o 其中乙，是m a x ( d ( t o ，) + 气，t 3 ) ，m e m b e r ( r , ，) = 白眦表示在【f m ，t 4 】期间，r 是 组成员。 如图2 5 所示，对于一个消息的成员间隔为 o ，l 】，传输间隔为 o ，3 5 ，c m df l a g 被设置了，那么接受者就是 置，心) 。 2 6 本章小结 本章主要介绍了容迟网络的体系架构、容迟网络与传统i n t e m e t 网络的区别以 及容迟网络的主要特点、应用范围。此外，本文根据容迟网络是一种覆盖网络，容 迟网络下面的物理链路可能有很多条的，介绍了容迟网络的单播模型，根据容迟网 络高延迟和频繁中断，而导致的组播成员难以确定的特点，提出了容迟网络的三种 组播模型，提出了三种判断容迟网络组播成员的方法，为第四章中组播成员的管理 提供依据。 重庆邮电大学硕士论文 第三章容迟网络组播路由算法研究 第三章容迟网络组播路由算法研究 3 1 容迟网络路由算法设计的原则 所谓路由选择，是指在分组交换网中选择一条最佳的分组传送路径的能力。也 就是说，节点能够根据一些局部或全局信息按照一定的原则做出最佳的路径选择。 负责确定所收到的消息的继续传送的路线。路由选择算法的主要功能有两个。第一 是做出源节点和目的节点间的路径选择，第二是将报文传送到它们的目的节点。第 一项功能主要包括一组运行在不同节点上的算法，以及节点之间的业务和信息的交 换。第二项功能比较简单，它包括一个被称为路由表的数据结构。一般每个节点都 有一个路由表，节点通过查找路由表上目的地址与传输线路的对应关系来确定消息 的输出路径。路由表会跟据不同的原则进行更新以正确反映当前网络的运行情况。 一个理想的路由选择算法应当具备以下的特点： 正确性：路由算法必须正确无误，这是对路由算法最根本的要求。 计算简单：由于对路由选择的计算会占用一定的资源，增加开销和延时，因 此路由算法的计算应当尽量简单化，计算非常复杂的算法是很难表现出优秀的性能 的。 自适应性：算法应当能够适应网络拓扑和业务量的变化，并随之做出相应的 改变。比如，当某个节点出现故障的时候，算法要能够迅速找到另一条路径来代替。 稳定性：既算法必须有避免出现振荡的能力。所谓振荡，就是指算法得到的 一些路由只是在几条路由之间不停的变化而已。 公平性：算法必须对所有的用户都是公平的，比如仅仅考虑某一对节点间的 延时最小就是不公平的体现。 最优性：路由应当能够提供最佳的路径，使得其平均分组延时最小而吞吐量 最大。这里最佳可以指在各种衡量标准下的最佳，如延时，出错率，缓冲区被占用 程度等。 总体上来讲，路由选择的目的大致有以下几点： 迅速，准确，合理地传送报文信息。 能适应网络的拓扑结构由与各种故障而引起的变化，并能在故障的情况下依 然完成报文的传递。 能够适应网络流量的变化，使整个网络的各条路线的流量均匀。 1 2 重庆邮电大学硕士论文第三章容迟网络组播路由算法研究 算法尽量简单以减少开销。 虽然在容迟网络的路由设计领域，研究者已经做了大量工作并取得了很大成就， 但由于容迟网络的路由选择需要许多输入变量，如动态拓扑特性、队列缓存、节点 寿命、以及通信量。如果我们获得了整个延迟容忍网络的全部信息的话，我们会比 较简单地计算出一条优化的路径。当然，如果我们只获得或者只使用一部分的信息 的话，我们也许会在路径的计算中遇到一些麻烦，而这样计算出来的路径的性能也 许并不是最优化的。因此，我们在算法中所用到的信息量同计算得到的路径的性能 是有直接的关系的。为了了解这种关系，我们建立了一系列抽象的信息库。我们将 这些信息称之为节点信息库，具体的节点信息库包括如下几个部分： 连接( c o n t a c t ) 概要信息库 这个库包含了关于整个网络的所有连接的特征数据。这样就可以计算出平均每 条边( e d g e ) 上出现两个连接之间的时间间隔，以此来大概地估算下一个连接到达地 时间。这个库只能表示关于连接的非时变性质。 连接信息库 这个库可以提供在任何一个时刻，任意两个节点之间的连接的信息。如通过这 个库，就能提前计算出未来某个时刻内某条边上是否会出现连接以及容量( c a p a c i t y ) 是多少。这样就相当于了解了整个延迟容忍网络的动态拓扑结构。 队歹l j ( q u e u i n g ) 信息库 这个库包含了在任一时刻任一节点上的缓冲区的瞬时占有率。因此，它比较适 用于出现拥塞的网络。与其他信息知识库不同，队列信息库同新到达消息和路由选 择算法所选择的路径有关。 节点寿命信息库 这个库包含某些有限寿命的节点。当超出节点的最大工作时间时，节点关闭， 队列中未发送的消息丢失。所以需要预先估计节点寿命和队列的长度，防止消息丢 失。 通信量信息库 这个库包含当前和未来通信量需求的信息。它可以提供在任何时刻进入到系统 中等待传输的消息的信息集合，即预测到未来某个时间段内网络系统中新增加的需 要被传输的信息量。 历史信息信息库 这个库包含了任意两个节点之间的连接概率，当每两个节点之间有了连接的时 候，连接概率就会增加。 重庆邮电大学硕士论文第三章容迟网络组播路由算法研究 3 2 容迟网络现有路由技术的研究 传统的网络根据寻路机制和路由结构的不同，将组播路由算法分为三类：基于 树的组播路由算法、基于网格的组播路由算法、混合组播路由算法。由于容迟网络 的独特网络环境，传统的组播路由算法已经不再适合容迟网络。目前根据寻路路由 机制的不同，我们将容迟网络组播路由算法分为两类：基于知识的组播路由算法和 基于概率的组播路由算法。 ns o u r c e 、- 4 6 r e c i v e r b r o k e n l i n k 图3 1u - m u l t i c a s t s t - m u l t i c a s t d t b r 3 2 1 基于知识的路由算法 所谓的基于知识的组播路由就是按照一定的网络知识来做出路由的选择，这些 网络知识包括网络的拓扑结构、节点的生命周期、节点之间的连通情况、节点的运 动时刻表、节点的历史相遇概率等等，网络预先知道网络中特殊节点的相关网络知 识，然后根据这些信息用改进的d i j k s t m 算法来计算最佳路径，以这个路径来传输 消息。 m u l 邱l e - u n i c a s t - b a s e dm u l t i c a s t ( u m u l t i c a s t ) 旧 这种路由方法是实现组播的最简单算法，它通过使用多个从源节点到目的节点 的单播服务来实现组播数据传输。工作过程为4 个步骤： 1 ) 对于每个目的节点，源节点通过寻访下部的网络收集到该目的节点的历史端 到端的路径，然后选择一条最小开销的路径，