（信息与通信工程专业论文）dtn路由算法的研究与改进.pdf

：一，l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：匿垂里日期：业年上月上日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：盥啦导师签名习蛐日期：址年上月l 日 摘要 越来越多的新型网络呈现出长链路延迟、高链路差错率、端到端 的路径断开频繁、存储能力有限、缺乏连续的能量供给等特点。这些 网络在网络体系结构和性能特征等方面都和i n t e r n e t 有着较大的不 同，所以传统的网络协议并不适用。在这种背景下，研究人员提出了 延迟容忍网络( d e l a y t o l e r a n tn e t w o r k ，d t n ) 的概念，并在此基础 上对其各个方面进行了研究。路由技术是目前d t n 的一个研究热点。 由于d t n 环境的多样性和复杂性，路由算法被分为很多种。其中按 照节点所掌握的网络拓扑信息可分为确定性路由算法和随机性路由 算法。 本文首先研究了d t n 的一种确定性路由算法e d 算法，分析 了其计算延时开销函数，并在此基础上充分考虑传播延时、节点之间 链路的连接规律，引入链路连接状态表来选取路由决策时刻，优化延 时开销的计算。实验结果表明，改进后的e d 算法可以有效地降低延 时，提高路由成功率，减小路由开销。 然后，在随机性路由的基础上，分析了p r o p h e t 算法在传输预 期值计算、路由选择以及网络拥塞处理上存在的不足，提出了一种改 进型p r o p h e t 算法。该算法引入节点链路周期表来优化传输预期值 的计算，根据消息的生存时间长短建立了一种合理的节点队列缓存管 理机制，并给出了网络拥塞处理方案。仿真结果表明，改进后的 p r o p h e t 算法在路由成功率、端到端平均延时、路由开销等方面比 原p r o p h e t 算法具有更好的性能。 关键词延迟容忍网络，路由算法，延时开销，传输预期值 a b s t r a c t i n c r e a s i n gn u m b e ro fn e wn e t w o r ki sc h a r a c t e r i z e dw i t hl o n gl i n k d e l a y , h i g hl i n ke r r o rr a t e ，e n dt oe n dp a t hd i s c o n n e c t e df r e q u e n t l y , l i m i t e ds t o r a g er e s o u r c e sa n dl a c ko fc o n t i n u o u se n e r g ys u p p l y , a n ds oo n t h en e t w o r ka n di n t e m e ta r ed if f e r e n ti nt h en e t w o r ka r c h i t e c t u r ea n d n e t w o r kp e r f o r m a n c ec h a r a c t e r i s t i c s ，s ot h et r a d i t i o n a ln e t w o r kp r o t o c o l d o e sn o tw o r k i nt h i sc o n t e x t ，r e s e a r c h e r sp r o p o s ean e wc o n c e p to f d e l a yt o l e r a n tn e t w o r k ( d t n ) o nt h i sb a s i s ，i t sv a r i o u sa s p e c t sh a v e b e e nr e s e a r c h e d d t nr o u t i n gt e c h n o l o g yi sah o tr e s e a r c ht o p i c b e c a u s e o fd t nn e t w o r ke n v i r o n m e n td i v e r s i t ya n dc o m p l e x i t y , r o u t i n ga l g o r i t h m i sa l s od i v i d e di n t od i f f e r e n tc a t e g o r i e s a c c o r d i n gt ot h em a s t e rn o d e n e t w o r kt o p o l o g yi n f o r m a t i o n ，i tc a nb ed i v i d e di n t od e t e r m i n i s t i ca n d r a n d o mr o u t i n ga l g o r i t h m t h i sp a p e rf o c u s e so no n eo fd t n sd e t e r m i n i s t i cr o u t i n ga l g o r i t h m e d ，a n dm a k e sa na n a l y s i so fi t sc a l c u l a t i o no fd e l a yc o s tf u n c t i o n t os e l e c tt h ea c c u r a t et i m eo fr o u t i n gd e c i s i o n m a k i n ga n do p t i m i z et h e c a l c u l a t i o no fd e l a yc o s t ，al i n kc o n n e c t i o ns t a t et a b l ei se m p l o y e d o n t h i sb a s i s ，t h et r a n s m i s s i o nd e l a ya n dr u l e so fn o d e l i n kc o n n e c t i o na r e t a k e ni n t oa c c o u n t e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ei m p r o v e de dc a n e f f e c t i v e l yr e d u c et h ed e l a ya n dt h er o u t i n go v e r h e a d ，i m p r o v er o u t i n g s u c c e s sr a t e t h e n ，b a s e do nt h ea n a l y s i so ft h er a n d o mr o u t i n ga l g o r i t h m p r o p h e t sc a l c u l a t i o no fd e l i v e r yp r e d i c t a b i l i t y , r o u t i n g ，a n dn e t w o r k c o n g e s t i o n ，a ni m p r o v e dp r o p h e ti sp r o p o s e d a c c o r d i n gt o t h e s u r v i v a lt i m eo fi n f o r m a t i o n ，ar e a s o n a b l en o d eq u e u ec a c h em a n a g e m e n t m e c h a n i s mi sc r e a t e d an o d el i n kt a b l et oo p t i m i z et h ec a l c u l a t i o no f d e l i v e r yp r e d i c t a b i l i t yi se m p l o y e da n dan e t w o r kc o n g e s t i o nt r e a t m e n t p r o g r a mi s i n t r o d u c e d s i m u l a t i o nr e s u l t ss h o wt h a tt h ei m p r o v e d p r o p h e th a sb e t t e rp e r f o r m a n c eo fd e l i v e r yr a t i o ，a v e r a g el a t e n c ya n d r o u t i n go v e r h e a d ，c o m p a r e dw i t hp r o p h e t 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 ( d t n ) ，r o u t i n ga l g o r i t h m ，d e l a y c o s t ，d e l i v e r yp r e d i c t a b i l i t y 目录 摘要i a b s t r a c t i i 第一章绪论l 1 1课题来源及研究背景l 1 2国内外研究现状1 1 3 研究目的和意义3 1 4 本文的结构安排4 第二章d t n 及其路由算法5 2 1 d t n 概述5 2 2 2 3 2 4 第三章 3 1 3 2 3 3 3 4 第四章 4 1 4 2 2 1 1d t n 特点一5 2 1 2d t n 体系结构5 d t n 路由框架9 2 2 1d t n 路由拓扑模型1 0 2 2 2d t n 路由预测信息库1 0 d t n 路由算法分类1 1 2 3 1 确定性路由算法1 2 2 3 2随机性路由算法14 本章小结1 7 确定性路由e d 算法的分析与改进1 8 e d 算法分析18 对e d 算法的改进j 2 0 3 2 1建立链路连接状态表2l 3 2 2 优化路由决策时间2 1 3 2 3改进后的e d 算法流程2 2 仿真与分析2 2 3 3 1仿真环境2 2 3 3 2 性能指标2 5 3 3 3 仿真结果分析2 6 本章小结2 8 随机性路由p r o p h e t 算法的分析与改进2 9 p r o p h e t 算法分析2 9 对p r o p h e t 算法的改进3 2 i l l f 4 2 1考虑节点链路状态的传输预期值的计算3 2 4 2 2 节点队列缓存管理机制的实现3 3 4 2 3 拥塞路由解决方法3 4 4 2 4 改进后的p r o p h e t 算法流程3 4 4 3 仿真与分析3 6 4 3 1仿真环境3 6 4 3 2 仿真结果分析3 8 4 4 本章小结4 0 第五章总结与展望4 1 5 1 论文总结：4 1 5 2 研究展望4 1 参考文献4 3 致 谢4 8 攻读硕士学位期f b j 的主要研究成果4 9 i v 硕士学位论文第一章绪论 第一章绪论 1 1课题来源及研究背景 i n t e m e t 将全球大部分的主机和网络都联接到了一起，从而实现了计算机的 通信和资源的共享。i n t e m e t 通过使用t c p i p 协议簇来进行路由转发以及保证数 据交换的可靠性，它的可用性主要依赖于一些重要的假设【l j ： ( 1 ) 连续的、双向的端到端的路径：一个连续、可用的在源端和目的地之 间的双向连接，其主要用于支持端到端的通信。一 ( 2 ) 较短的往返时间：从发送数据包到接收相应的确认数据包的网络延时 应该比较小。 ( 3 ) 对称的数据传输速率：在源端和目的地之间的双向数据传输速率要相 对一致。 ( 4 ) 低差错率：每条链路上丢失或者损坏的数据量应该比较少。 随着计算机技术、微电子技术的发展以及军事和其他领域研究的需要，越来 越多的新型网络开始出现。这些网络经常由于主机或路由器的移动性，以及能量 受限或干扰而断丌连接，或者是传播时延非常巨大等原因，可能不再满足以上的 一些基本假设，因此也被称为挑战网络( c h a l l e n g e dn e t w o r k ) 【2 1 。由于挑战网络 可能有非常大的链路延迟、不存在端到端路由、缺乏连续的能量供给、缺乏大存 储能力等，这些特性对现有i n t e m e t 体系结构和协议的应用都提出了严峻的挑战。 挑战网络在性能特性和网络体系结构等方面都和i n t e m e t 不同。研究表明， 试图在这种网络上通过修改、增强已有的协议簇来进行数据通信是非常困难的； 另外，通过增加一个代理层使得它在合适的时候使用互联网协议，但在其他时候 使用支持特殊环境下的其他协议簇的方法也并不理想【3 】。因此，为了解决挑战网 络所存在的种种问题，延迟容忍网络( d e l a yt o l e r a n tn e t w o r k ，d t n ) i lj 的概念 首次于2 0 0 2 年被f a l l 等人提出。d t n 的体系结构是一种基于消息的存储转发模 式，它用持久的存储设备来克服链路的频繁断开。d t n 在应用层和传输层之间 添加了一个b u n d l e 层，在b u n d l e 层完成路由转发和一些其他功能。 1 2 国内外研究现状 d t n 体系结构目前主要由容迟网络研究组( d t n r g ) 【4 1 、因特网研究任务 组( i r t f ) 1 5 1 和星际网络研究组( i p n s i g ) 【6 1 这三个机构进行研究。其最初是针 对太空通信提出的，主要根据星际网络的特点设计相应的体系结构方案。 硕士学位论文 第一章绪论 目前延迟容忍网络的研究重点主要集中在路由技术、传输协议、网络安全、 组播技术等方面。其中路由技术是一个研究的热点和难点问题，根据d t n 复杂 的网络环境，研究人员提出了多种各具特点的路由方法以适应不同的实际情况。 1 d t n 路由技术 文献 7 】首次提出d t n 中的路由问题，给出了d t n 路由框架，并将网络中 路由所需信息分成了五类预测知识，提出了基于不同预测知识的多种路由算法， 并通过仿真比较了它们的性能。另外，文献 8 】研究了当网络拓扑的变化为不可 预测的情况时，在移动a d h o c 网络中如何提供链路连接的方式。 文献 9 具体讨论了基于各节点链接信息概要信息库的e d 算法。考虑到节点 运动精确性和延时误差，引入了一个精确性因子来修正延时开销计算结果，进而 提出了一种增强型e d 算法a e d ，但该算法没有具体考虑等待延时和传播延 时之问的关系以及路由决策时刻的选取。文献【1 0 】分析了m e d 算法所存在的问 题，给出了当中间节点有新的连接到来时，根据链接信息概要重新计算路由的改 进方案，并提出了一种最低估计预期延迟算法m e e d 。该算法有效地改善了 m e d 算法的效率，但是路由计算的开销较大。文献 1 1 】考虑到m e e d 算法路由 计算开销较大的问题，计算从目的节点到源节点的路由，并返回反转后的节点路 径序列，而不是传统的单条最短路径。最后提出了一种增强型m e d 路由算法一 _ a m e d 。该算法性能与m e e d 算法相当，但计算开销远低于m e e d 。文献 1 2 1 针对d t n 中确定性事件影响链路中断的统计特性问题进行了分析，采用寻找两 节点可通信时间的方法，并使用m a t l a b 对其仿真，从而得出了链路间断随时 间变化的规律，预测了链路未来的连接趋势。 d t n 中通过利用临时的链接来代替端到端的网络连接进行消息传输 1 3 - t 5 】， 当今的快递和邮政系统也是采用类似的方式。在d t n 环境中，节点通常缓存有 限，甚至不存在持续可用的端到端路径，这就限制了传统路由方式的使用。针对 间断连接网络最早提出的一种路由方式是感染路由( e p i d e m i cr o u t i n g ) 【1 6 1 ，节 点向周围所有邻居节点复制消息，直到每个邻居节点都有一个消息的拷贝，这样 消息就可以在网络中快速转发直到目的节点。f a l l 等人首先提出一个评估d t n 中路由算法性能的框架，并给出了几个具体的基于预测知识的路由算法。由于最 大可能地传递消息是d t n 路由的主要目标，所以消息可能会因为节点缓存空间 有限、节点能量消耗过多以及网络带宽较小等原因被丢弃。由于在随机性d t n 中的延时、网络资源、链路连接丌始时间和连接断丌时间等参数都是随机的、不 确定的，文献 1 7 】首次提出了随机d t n 的网络模型，并分析了几种路由算法来 解决不确定性随机d t n 中消息传输概率低、路径选择困难等因素而导致的路由 性能差的问题。 2 硕士学位论文第一章绪论 e v a n 等人在文献 1 8 1 提出了一种实用的仅使用网络观测信息的d t n 路由协 议。该文设计了一个参数矢量去评估消息被传递到下一跳之前必须等待的时间。 文献f 1 9 1 提出了一个适合间断连接网络的概率路由协议p r o p h e t ，它在路由发 现过程中利用以往节点相遇和转移的历史信息，即传输预期值。总之，d t n 路 由是一个富有挑战性的问题，它要求选择路径、调度管理、能量管理、评估传输 性能和缓存合理利用等技术。 2 d t n 组播技术 组播技术【2 2 在互联网和移动a d h o c 网中已有深入广泛的研究，组播服务 支持面向一组用户的数据转发。许多潜在的d t n 应用是基于组播方式的，但是 由于d t n 链路断开频繁的特性使得d t n 中的组播技术是一个有挑战性的难题： d t n 组播不仅要求新的组播定义，而且带来了路由设计的新问题。a m m a r 等人 首次提出了d t n 组播的语义模型，设计了四类采用不同路由方法的组播路由算 法【2 3 j ，并且对这些算法进行了仿真评估。s y m i n g t o n 等人提出了d t n 中的非保 管尽量传输的组播方案，定义了在d t n 中为了提供非保管捆绑组播传输【2 4 】的数 据格式、传输要求和一些具体的网络限制。在绑定协议基础上，还进行了扩展来 支持d t n 中保管组播捆绑传递【2 5 | 。 3 d t n 安全技术 在d t n 中的安全问题不同于传统网络的安全，有其自身的特殊性。d t n 基 础结构的保护和接入基础结构控制都是相当重要的。大多数网络安全方法认证用 户的身份和消息的完整性，而不认证转发消息的路由器。但在d t n 中，转发节 点( 路由器或网关) 也需要被认证。如文献 2 6 1 讨论了d t n 中的一些强制约束， 并根据这些约束给出了具体的基础保护方案。 4 d t n 传输协议 d t n 体系结构使用面向消息的存储转发绑定层方法处理挑战网络中频繁网 络断开、长延迟和网络拓扑变化等问题。其中一个重要的建议是采用保管传递来 加强端到端的可靠传递。f a l l 等人描述了保管传递【2 7 】的方式和结构，并指出保管 传递在d t n 中和i n t e r n e t 中的不同。 1 3 研究目的和意义 d t n 不仅仅是在i n t e r n e t 体系结构上进行修改，而是对其进行了大幅度的改 进。这种改进主要体现在以下几个方面：消息替代分组、名称二元组路由替代地 址路由、多跳路由替代端到端的路由。 路由问题是d t n 中的一个难点问题。当前，对d t n 的研究大多处在理论 和仿真的阶段。当前和将来最主要的任务是在d t n 体系特征的基础上搭建合适 硕十学位论文第一章绪论 的d t n ，并通过真实的网络测量数据来设计和调整各种路由算法和协议，使之 能应用于现实的网络环境中。 d t n 在全球移动网、军用a d h o c 网、长距离无线链路网、水下声学调制通 信网络、自由空间光通信网、卫星通信网、传感器网络等多种现实网络中都可以 应用，这对今后网络技术以及数据通信等领域研究都具有重要的意义。 1 4 本文的结构安排 本文主要研究延迟容忍网络的路由技术，分析了两种比较典型的路由算法， 并指出其在应用中的不足。在此基础上，针对算法的不足做出了相应的改进，并 通过仿真实验进行了性能比较。 全文共分为五章，每章的内容如下： 第一章主要介绍了本课题来源及研究背景、d t n 的国内外研究现状以及研 究目的和意义。 第二章首先阐述了d t n 特点及体系结构，接着讨论了d t n 的路由算法， 介绍d t n 的路由拓扑模型以及路由预测知识库，然后将路由算法进行了分类， 重点分析了确定性路由算法和随机性路由算法。 第三章分析了一种确定性路由算法e d 算法，讨论了其在延时计算以及 路由选择上的不足，并在此基础上充分考虑了传播延时、节点之间链路的连接规 律，引入链路连接状态表来选取路由决策时刻，优化延时开销的计算。最后对改 进的e d 算法进行了仿真和分析。 第四章分析了一种随机性路由算法一p r o p h e t 算法。该算法在传输预期 值计算、路由选择以及网络拥塞处理上存在不足，因此引入节点链路周期表来优 化传输预期值的计算，应用节点队列缓存管理机制，给出了网络拥塞路由处理方 案，并对改进的p r o p h e t 算法进行了仿真和分析。 第五章总结了全文的内容，对今后的工作进行了展望。 4 硕十学位论文 第二章d t n 及其路由算法 第二章d t n 及其路由算法 由于延迟容忍网络具有链路中断频繁、长延时、高数据传输差错率等特点， 因此其体系结构具有一些新的特征，其路由框架和路由算法与传统的网络相比也 有较大的差异。 2 1d t n 概述 2 1 一d t n 特点 。 延迟容忍网络不符合互联网的基本假设，它具有以下特点： ( 1 ) 间歇性的连接：如果通信源和目的地之i 、b j 不存在终端到终端的路径， 即被称为网络分割，那么端到端之间使用t c p i p 协议的数据传输就不能正常工 作。 ( 2 ) 长延时或者可变延时：除了间歇性连接，节点之间的长传播延时和可 变排队延时等端到端的路径延时对于依赖快速返回数据或确认信息的互联网协 议和应用程序提出了很大的挑战。 ( 3 ) 非对称数据传输速率：互联网支持有非对称的d s l 或有线电视接入用 户的双向数据传输。但是如果这种不对称性很大的话，它们就不适应于对话协议。 ( 4 ) 高数据链路差错率：链路位错误需要更正( 这需要更多的位和更强大 的处理) 或者整个数据包重传。对于给定的链路误码率，下- - 孵, 1 下一跳的路径 比终端到终端的路径需要较少的数据重传。 2 1 2d t n 体系结构 由于延迟容忍网络在很多方面都与传统的互联网有非常大的差异，所以现有 的基于t c p i p 的四层体系结构并不适用于d t n 。在d t n 体系结构中，主要提 出了一个绑定层( b u n d l el a y e r ) ，覆盖在不同类型网络的传输层上。d t n 体系 结构的分层模型如图2 1 所示。 硕十学位论文第二章d t n 及其路由算法 应用层 b u n d l e 层 传输层 网络层 网络接l 层 应用层 传输层 网络层 网络接u 层 d t n 分层i n t e r n e t 分层 图2 - 1d t n 与i n t e r n e t 分层模型比较 与现有的通信网络相比较，d t n 提出了一些新的技术特征，下面将详细介 绍一下。 1 问歇性连接 越来越多的通信设施处于移动状态或者能量有限状念【2 8 】。这种情况在星际 空间中很常见，同时在地球上移动无线通信设备之间也变得更加普遍。当通信节 点在运动时，链路很可能会被干扰。当通信节点需要节省能量消耗或者保密传输 时，链路可能会被关闭。这些情况将会导致间歇性连接，因此当源节点和目的节 点之间不存在路径连接时，整个网络将会被分割开来。 2 机会接触 网络中节点在机会接触过程中需要通信，其中发送端和接收端可能在一个不 确定的时间内存在接触。当移动的人群、车辆、飞机或者卫星之间的距离足够近， 并且在视线范围内时，就可以利用它们可用的能量( 通常是有限的) 来制造链接 并交换信息【2 9 1 。在现实生活中也有利用机会接触进行沟通的例子。如人们在街 上偶尔相遇了，想互相问候一下或聊几句，就可以马上进行对话。当人们离开后， 对话也就结束了。此模型同样可以应用于电子通信领域。例如当无线个人数字助 理( p d a ) 在可通信范围内存储了一些过去的有效信息时，就可以发送或接收数 据。 3 预定接触 在宇宙中，几乎所有运动的物体都存在一定的延迟。如果潜在的通信节点按 预定的路径移动，它们就可以预测其未来移动位黄的时刻，从而安排自己未来通 信会话。预定接触【3 0 1 可能涉及节点之间的消息发送。它们还可能涉及到存储信 息，直到存储信息被转发或者直到接收应用程序可以捕获发送方的数据传输速 率。预定接触在d t n 中需要时间同步。 4 存储和转发的消息交换机制 d t n 通过使用存储和转发的消息交换机制【3 1 】来解决网络的间歇性连接、长 6 硕十学位论文 第二章d t n 及其路由算法 或可变延时、非对称数据传输速率以及高链路差错率等问题。自古以来，在快递 和邮政系统中都是采用这种方法。整个消息( 应用程序用户数据块) 或消息的部 分片段从一个节点的存储空间移动到另一个节点的存储空间，沿着这样的路径最 终到达目的节点。存储和转发的方法还用在今天的语音邮件和电子邮件系统中， 虽然这些系统不是单向的继承，而是多向继承，但是源端和目的端单独接触的中 央存储设备是在链路的中间。这些存储设备( 如硬盘) 可以无限期地持有消息。 相对于存储时间非常短的内存芯片，它们被称为持久性存储。 i n t e m e t 路由器使用内存芯片来存储几毫秒传入的数据包，同时它们也在等 待它们的下一跳路由表查找和即将转发的可用端e l 。而d t n 路由器需要队列持 ： 久存储是基于以下原因： ( 1 ) 在很长一段时| 、日j 内，一条到下一跳节点的可用通信链路可能并不存在。 ( 2 ) 相对于其他节点，正处于通信状态的节点能够更快或更可靠地发送和 接收数据。 ( 3 ) 一个消息一旦发送出去，如果在上游节点或链路产生错误，或者上游 节点对转发消息的接收效率下降，此时就需要重新发送消息。 通过将整个消息单一传输，消息的交换技术提供消息大小即时信息给网络中 的节点，因此对中间存储空间大小和传输带宽也有所要求。 5 绑定层 d t n 的体系结构实现了存储转发消息交换，它在非均匀异质区域底层顶部 覆盖了一个新的协议层，被称为绑定层【3 2 1 。绑定层与特定区域底层联系在一起， 使得应用程序可以在多个区域进行通信。捆绑包也被称为消息，这个绑定层存储 和转发节点之间的捆绑包或捆绑包片段。单个绑定层协议应用于整个网络就组成 了一个d t n 。相比之下，绑定层下面的协议层选择适宜的区域来通信。捆绑包 由三个部分组成： ( 1 ) 源应用程序的用户数据。 。 ( 2 ) 控制信息：由源应用程序为目的应用程序提供，描述如何处理、存储、 丢弃用户数据。 ( 3 ) 捆绑头：由绑定层插入，像应用程序的用户数据，捆绑可以任意长。 捆绑扩展的数据对象的层次结构封装由i n t e r n e t 协议执行。绑定层可以将整 个捆绑包分成一个一个的片段，就像i p 层将整个数据报分成一个一个的数据块。 如果捆绑包被分成一个一个片段，那么在目的节点绑定层可以将这些片段重新组 合。 6 捆绑服务等级 绑定层为捆绑包提供了6 类服务等级【3 3 】： 7 硕士学位论文第二章d t n 及其路由算法 ( 1 ) 保管传输：将传输责任委托给一个接收节点，这样发送节点就可以恢 复其传输资源。该接收节点返回一个保管接收确认信息给前一保管节点。 ( 2 ) 返回确认：确认消息来源或回复实体，即捆绑包已被目标应用程序接 收。 ( 3 ) 保管传递通知：当一个节点接收到捆绑包的保管传输，通知消息来源 或回复实体。 ( 4 ) 捆绑包转发通知：通知消息来源或回复实体，当一个捆绑包转发到其 他节点。 ( 5 ) 传输优先级：大批、普通、快速。 ( 6 ) 验证：该方法( 如数字签名) 用来验证发送者的身份和消息的完整性。 7 保管传输 d t n 支持在传输层和绑定层中的节点到节点丢失或损坏的数据重传。然而， 因为没有单一的传输层协议在d t n 端到端中运行，端到端的可靠性只能在绑定 层中实施。绑定层通过保管传输【3 4 】的方式支持节点到节点传输。这种传输被安 排在成功节点的捆绑层，在源应用程序的初始请求中。如果当前的绑定层发送一 个捆绑包到下一跳节点，它需要保管传输，并且启动确认重发的计时器。当下一 跳节点的捆绑包收到了保管，它将返回一个确认信息到发送节点。如果发送节点 的计时器过期后还没有收到确认信息，发送方将重发捆绑包。计时器的值可以是 分布于各节点的路由信息或计算本地信息，其根据过去的历史信息传输到特定节 点。 绑定层保管要存储捆绑包直到另外一个节点接收保管或者捆绑包的生存时 问到期，该时间应该要比保管的确认时间长。因此，确认时间应足够长以使得底 层传输协议可以完成可靠地传输，保管传递不提供保证端到端的可靠性。只有当 源节点要求保管传输以及返回确认信息时才能这样做。在这种情况下，源节点必 须保留捆绑包的副本直到收到一个返回确认信息，如果没收到返回确认信息将会 重发该捆绑包。 8 d t n 节点 在d t n 中，一个节点就是一个具有绑定层的实体。一个节点可能是一个主 机、路由器、网关或者它们的组合，作为源节点、目的节点或捆绑转发代理【3 5 1 。 ( 1 ) 主机：主机发送或接收捆绑包，但不转发它们。主机可以是捆绑包传 输的源端或目的端。为了连接长延时链路，主机捆绑层需要持久的存储空间，直。 到排队等待的捆绑包有可用的出站链路。主机可以选择支持保管传输。 ( 2 ) 路由器：路由器是连接单个d t n 区域的转发捆绑，它也可能是一个主 机。为了连接长延时链路，路由器的捆绑层需要持久的存储空间，直到排队等待 8 硕士学位论文 第二章d t n 及其路由算法 的捆绑包有可用的出站链路。路由器也可以选择支持保管传输。 ( 3 ) 网关：网关是连接两个或多个d t n 区域的存储转发，它也可能是一个 主机。网关的捆绑层必须有持久的存储并且支持保管传输。网关提供跨度底层协 议区域的转换。 在i n t e m e t 中，t c p 协议提供端到端( 源端到目的端) 的可靠路径，转发不 被目的节点承认的数据段。该网络、链路和物理层提供数据完整性服务的各种类 型。在d t n 中，绑定层依赖底层协议来保证通信的可靠性。d t n 路由器和网关 能在d t n 区域中转发捆绑包，并在绑定层终止传输协议。这个绑定层因此充当 终端到终端的源节点和目的节点的代理。其缺点是低延迟区域的对话底层协议隔 离在长延迟区域的绑定层。 、 9 非对话协议 在长延时的问歇性连接链路中，会话协议如t c p 涉及到端到端的路由往返， 这会导致不正确的时间计算或路由失败。基于这个原因，d t n 中绑定层之间的 通信中使用简单的会话或者没有往返的会话。任何接收节点的确认是可以选择 的，这取决于所选的服务类型。底层协议支持绑定层的数据交换，当然这与t c p 层会话相类似。但是在长延时的间歇性连接链路中，非对话或较少对话底层协议 可以应用。 1 0 d t n 区域 一 一个d t n 区域是一个网络的网络。其中每个网络的通信特征是相类似的。 例如，一个区域可以是地球的互联网、无线个人数字助理网络、传感器网络、军 事战术网络、智能高速公路网络、行星或飞行器网络。每个区域都有一个独立的 区域i d ，用来区分各个d t n 区域，并作为每个节点名称的一个部分。其中网关 包括两个或两个以上的区域成员，是区域之间消息传输的唯一手段。 2 2d t n 路由框架 传统路由策略的目标是找到源节点与目的节点之间的最短路径，减少数据传 输的跳数，但延迟容忍网络中的路由目标并不是如此简单。延迟容忍网络中的消 息在中间节点的等待时i 日j 比传统网络中的长的多，这样会由于缓冲的溢出导致丢 失消息的情况出现，所以需要减少这种消息丢失的可能性。为了减少这种可能性， 可以通过让d t n 中消息尽量快的传输到目的节点来解决，这说明d t n 的路由 应该尽量减少d t n 中的传输延迟。综上所述，d t n 的路由目标就是减少消息传 输的延迟以及网络中的丢包率。 9 硕七学位论文第二章d t n 及其路由算法 2 2 1 d t n 路由拓扑模型 1 节点与边 如图2 2 所示，由于每两个节点之间的链路不止一条，可能存在多条，所以 d t n 的拓扑是一个有向多图。使用多图的原因很简单：网络可能会选择两条独 立的链路在两个节点对之间传输数据。另外，节点之问链路的容量函数也是时变 的。因此，图中边的开销与边的时变容量函数和传播延时都有关系。 源节点 e n 。( ( u ，v ) n ，c ( t ) ，d ( ) ) 目的节点 存储容最 e 3 图2 - 2d t n 的拓扑结构图示例 2 接触 一个接触就是通过一条边发送数据的机会。更确切的说，这是一条特殊的边， 在相对应的时间间隔内，边的容量函数值严格为正。 3 消息 用消息来表示通信的需求。其中消息中包括了源节点、目的节点、消息开始 在系统中传输的时间以及消息的大小等信息。所有消息的集合组成了通信的需 求。 4 存储 d t n 中的节点拥有有限的持久存储空间用来保存正在网络中传输的数据或 者等待目的节点的应用程序处理的数据。在本文模型中存储队列空间主要用来保 存正在网络中传输的数据，而目的节点都能够及时处理等待的数据。 5 路由 路由都是通过存储转发方式产生的。路由算法决定了一条消息应该往哪一条 边转发，有时候消息要等到接触产生时才可以被发送出去。 2 2 2 d t n 路由预测信息库 延迟容忍网络的路由问题与很多变量有关，如网络的动态拓扑特征以及通信 需求的大小。这些变量的完整信息可以帮助计算得出最优路径。如果只得到这些 l o 硕十学位论文第二章d t n 及其路由算法 变量的部分信息，找到最优路径可能就比较困难，最后得出的路由表现就不如预 期的效果。因此，可以通过建立一个抽象的预测知识来表示路由性能与网络特征 信息的关系。这些预测信息【7 1 被封装成特定的知识库用在不同的路由算法中，如 表2 1 所示。 表2 - 1 路由预测知识组成 预测知识描述 0 ：无+ 1 7 点不使用任何信息库知识 节点对网络的整体链路连接信息有一个估计值，该值 l ：链接概要预测 是1 时变的 节点了解网络中任意两1 y 点在任一时刻的链路连接 2 ：链接预测 信息，该信息值是时变的 3 ：链接预测+ 队列预测：宵点了解链接信息利各1 ，点的队列信息 4 ：链接预测+ 队列顶测+ 通信需求 除了链接信息和队列信息，仃点还了解网络中的通信 预测需求，如需要传输数据的大小以及其目的地 1 链接概要预测 这个预测表示了网络中所有链接的汇总统计。特别是链接概要预测可以提供 平均等待时间直到边的下一次链接到来。因此链接概要预测只能适应非时变的或 链接总体特征的情况。 2 链接预测 这个预测可以回答两个节点之间在任意时刻的链接信息的问题。这相当于知 道时变的d t n 有向多图。链接信息概要预测可以由链接预测得出，但反过来， 链接预测不能从链接信息概要预测得出。 3 队列预测 这个预测提供了任意时刻节点的瞬间队列缓存大小信息，它能被用来处理拥 塞节点的路由问题。与其他预测知识有所不同，队列预测受到系统中新到达消息 以及路由算法本身的选择有关。 4 通信需求预测 这个预测可以回答关于现在或将来通信需求大小的任何问题。它可以使消息 在任意时刻在网络中传输。 2 3d t n 路由算法分类 延迟容忍网络的路由算法分类，从不同的角度，有不同的算法。按照路由策 略可分为洪泛路由算法和转发路由算法；按照路由所使用报文的份数可分为单报 文路由算法和多报文路由算法；按照节点所掌握的网络拓扑信息还可分为确定性 路由算法和随机性路由算法。 硕十学位论文第二章d t n 及其路由算法 1 按照路由策略分类 ( 1 ) 洪泛路由算法：每个节点以复制的方式来传输数据消息，使网络中存 在多份消息副本，借此来提高消息成功传输的概率，所以在每一时刻，网络中都 存在大量的消息副本，这样就造成了带宽、缓存、能量等资源的极大消耗。 ( 2 ) 转发路由算法：每个节点根据收集到的网络中的预测知识计算出消息 转发的最优路径，然后沿着最优路径逐跳地转发消息，网络中只有一个消息的副 本在传输，资源消耗明显比洪泛路由算法少。 2 按照使用报文的份数 ( 1 ) 单报文路由算法：在网络中只传输一份报文，该算法节省大量的网络 资源，但路由成功率不高，消息很可能在传输过程中丢失。 ( 2 ) 多报文路由算法：在网络中传输多份报文，这样可以提高消息的传输 成功率，但同时会消耗较多的网络资源和节点能量，占用更多的网络带宽。 3 按照节点掌握的网络拓扑信息分类 ( 1 ) 确定性路由算法：节点未来的移动和连接是可预测的，即事先知道网 络未来的运动和连接机会，以及整个网络的拓扑结构。 ( 2 ) 随机性路由算法：网络拓扑是动态的、不确定的。如果节点对网络状 态一无所知，那么所有节点只能是随机地向邻居节点转发数据，这种情况属于路 由扩散；如果一个节点可以预测出它到其他邻居节点的转发概率，并根据此概率 选择一条好的路径，这就属于基于历史或是预测的转发。 本文主要研究的是确定性路由算法和随机性路由算法，下面将着重介绍这两 种算法。 2 3 1 确定性路由算法 根据各种不同的路由所使用的预测知识库，将确定性路由算法分为下面的三 类【7 1 。 1 零预测知识库路由算法 这类路由算法几乎没有使用到任何预测知识库的帮助。零预测知识库路由算 法比较简单，它是随机选择可用的链接来进行路由转发。 零预测知识库路由算法中主要的路由算法是最先连接算法( f c ) ，它是随机 选择一个可用的链路来发送消息，如果此时没有任何链接到来，消息将会暂时存 储在节点队列中直到出现第一次链接才发送出去。 2 部分预测知识库路由算法 这类算法通过使用链接概要预测、链接预测、队列预测中的一种或几种预测 知识来计算最优路径。这类算法都是基于边的开销计算以及最小开销路径的选 1 2 硕十学位论文 第二二章d t n 及其路由算法 择。其中部分预测知识库路由算法主要有最小期望延迟算法( m e d ) 、最早传递 算法( e d ) 、拥有本地队列预测的最早传递法( e d l q ) 、拥有所有队列预测的最 早传递法( e d a q ) 。 ( 1 ) 最小期望延迟算法( m i n i m u me x p e c t e dd e l a y ，m e d ) m e d 算法所用到的是链接概要预测，它寻找一条延迟最小的路径进行数据 的传输，并且一旦选定一条路径以后，所有的源和目的节点相同的数据都要通过 这条相同的路径传输。如果路径断开或暂不可用，则数据将在节点等待直到此路 径可用为止。这种算法认