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

摘要 作为一种新型的端到端网络体系结构，容迟网络( d e l a yt o l e r a n tn e t w o r k ) 具有 间歇连接、频繁割裂、时延大等特点，传统的i n t e m e t 路由协议难以有效应用在容 迟网络中，容迟网络路由面临新的挑战。现有一些路由算法通过向网络中发送多 个副本来提高数据传输的成功概率，但网络开销很大。另一些路由算法通过获得 网络知识来提高转发策略的投递成功率，但网络拓扑频繁变化，网络的全部先验 知识无法准确的获得。因此，本文提出采用灰色马尔科夫链位置预测模型预测节 点位置，并利用这些预测位置完成d t n 的路由决策。 本文根据灰色马尔科夫链预测机制，将灰色马尔科夫链位置预测模型与 s w r ( s p r a ya n dw a i tr o u t i n g ) 路由算法相结合，提出了一种新的适用于容迟网络的 路由算法( s w r - g m ) 。该算法根据节点经过路径的历史信息，利用灰色马尔科夫 链预测模型预测目的节点的位置，采用混合的转发方式进行路由选择，使数据包 的扩散具有更好的方向性，提高了数据包的成功投递概率。针对多数路由算法未 考虑节点移动模式和节点活动性能的情况，本文第四章提出了增强型s w r - g m 路 由算法。该算法提出节点活跃系数的概念，并利用节点活跃系数来量化节点活动 性能的强弱，以预测位置为基准，基于节点活跃系数的喷射转发，减少了网络中 的包副本数，降低了网络开销。仿真结果显示，在相同网络条件下，本文所提出 的两种路由算法均表现出更好的网络性能。 关键词：容迟网络路由算法 灰色一马尔科夫模型节点活跃系数 a b s t r a c t a sn e w l yp r o p o s e de n d - t o e n dn e t w o r k s ，d e l a yt o l e r a n tn e t w o r k s ( d t n ) a r e c h a r a c t e r i z e db yi n t e r m i t t e n tc o n n e c t i v i t y ，f r e q u e n tp a r t i t i o n s ，e x t r e m e l yh i g hl a t e n c y ， e t c h e n c e ，t r a d i t i o n a lr o u t i n gp r o t o c o l sf o ri n t e m e ta r ed i f f i c u l tt ob ea p p l i e de f f i c i e n t l y i nd t ns c e n a r i o s ，a n dr o u t i n gi nd t nf a c e sm a n yn e wc h a l l e n g e s s o m ee x i s t e d r o u t i n ga l g o r i t h m ss e n dm u l t i p l ec o p i e st ot h en e t w o r kt oi m p r o v et h ed a t as u c c e s s d e l i v e r yr a t e ，b u tm a k et h eb i gn e t w o r ko v e r h e a d s o m eo t h e rr o u t i n ga l g o r i t h m s i m p r o v es u c c e s sd e l i v e r yr a t eu s i n gm o r en e t w o r kk n o w l e d g e ，b u tg e t t i n ga l lo r a c l e k n o w l e d g ei nn e t w o r ki si m p o s s i b l e ，b e c a u s eo ft h ef r e q u e n tc h a n g e so fn e t w o r k t o p o l o g y c o n s i d e r i n ga b o v e ，w ep r o p o s e dl o c a t i o np r e d i c t i o nu s i n gg r e ym a r k o v p r e d i c t i o nm o d e l ，a n ds t u d i e dt h er o u t i n gd e c i s i o n sa b o u tt h e s el o c a t i o n s f i r s t l y ，u s i n gt h em a r k o vf o r e c a s t i n gm e c h a n i s m ，an o v e la p p r o a c hn a m e ds p r a y a n dw a i tr o u t i n ga l g o r i t h mb a s e do ng r e ym a r k o vp r e d i c t i o nm o d e l ( s w r - g m ) f o r d t ni sp r o p o s e d ，w h i c hc o m b i n e sg r e ym a r k o vl o c a t i o np r e d i c t i n gm o d e lw i t ht h e s p r a ya n dw a i tr o u t i n ga l g o r i t h m a c c o r d i n gt ot h eh i s t o r i c a li n f o r m a t i o no fp a t h sa l o n g w h i c hn o d e sm o v e ，i tp r e d i c a t e st h el o c a t i o no ft h ed e s t i n a t i o nn o d eb yu t i l i z i n gg r e y m a r k o vl o c a t i o np r e d i c t i n gm o d e la n du s e sah y b r i da p p r o a c ht of o r w a r dp a c k e t s i tc a n i m p r o v et h et r a n s f e rd i r e c t i o n a la n di m p r o v et h ep a c k e ts u c c e s sd e l i v e r yr a t e s e c o n d l y ， m o s tr o u t i n ga l g o r i t h m sd on o tt a k ei n t oa c c o u n tt h ed i f f e r e n c e sm o v e m e n tm o d e la n d a c t i v i t i e sp e r f o r m a n c eo ft h en o d e ，t h ef o u r t h c h a p t e ri n t r o d u c e st h ea d v a n c e d s w r - g mr o u t i n ga l g o r i t h m ( a s w r - g m ) i ti n t r o d u c e st h ec o n c e p to ft h ea c t i v i t y c o e f f i c i e n to fan o d e ( a c o n ) t oq u a n t i f yt h es t r e n g t ho fan o d e sa c t i v i t yp e r f o r m a n c e i na d d i t i o n ，t h ea l g o r i t h ms p r a y sa n df o r w a r d sp a c k e t so nt h eb a s i so fa c o n ，s oi tc a n e f f e c t i v e l yr e d u c et h ec o p i e so fad a t ap a c k e ta n dd e c r e a s et h en e t w o r ko v e r h e a d s i m u l a t i o nr e s u l t ss h o wt h a tb o mt h ep r o p o s e da l g o r i t h m sa r ep r o v e db e t t e rn e t w o r k p e r f o r m a n c eu n d e rt h es a m en e t w o r kc o n d i t i o n s k e yw o r d s ：d t n r o u t i n ga l g o r i t h mg r a ym a r k o vm o d e l a c o n 第一章绪论 第一章绪论 1 1 引言 互联网( i n t e m e t ) 在当今多种异构网络中已经占据着主导地位，当前的互联网采 用t c p i p 协议簇作为其主要的体系结构，t c p i p 协议簇为不同的链路提供端到端 的通信保证。但是t c p i p 协议簇的正常通信保证都是依赖对物理链路特性的如下 假赳1 l ： a ) 源节点和目的节点之间存在端到端的持续连接： b ) 网络中任何节点之间的最大往返传输时间( r t t ) 不能太长； c ) 对称的双向数据速率，以及较低的端到端的丢包率和误码率。 随着计算机网络技术的不断发展及无线通信技术在各个领域的广泛应用，一 种新型的网络类型“受限网络( c h a l l e n g e dn e t w o r k s ) ”出现了。由于受节点的移动、 部署密度、能量消耗、资源有限以及障碍物的阻挡等多种因素的影响，可能不存 在端到端的路由持续连接、存在非常大的传输延迟、非对称的数据速率、较高的 误码率与丢包率以及异构互连等，使得当前的t c p i p 协议簇无法正常地为其提供 服务 2 1 ，所以不能使用现有的i n t e r n e t 网络结构体系。典型的受限网络有1 3 】： 星际网络( i n t e r p l a n e t a r yn e t w o r k s ，i p n ) 4 】：这类网络是一个把各种飞行器、探 测器、登陆车以及其他航空发射装置和太空星球( 如月球、火星等) 等连接起来的互 联网络。星际网络通信具有如下特点：极端长且多变的网络传输时延；向前和返 回通信链路具有不对称的通信负载能力；射频( r f ) 通信链路有较高的比特出错率； 间歇性链路连接且缺少固定的通信基础设施等。 陆地移动网络( t e r r e s t r i a lm o b i l en e t w o r k s ) ：在许多情况下，由于节点的移动 或者射频的干扰，可能会出现不可预测的网络割裂。而在一些情况下，网络可能 难以形成一条端到端的路径，并且网络的割裂方式可以预测。 军事无线自组织网络( m i l i t a r ya d h o cn e t w o r k s ) ：这类网络大多部署在军事网 络环境中。由于节点的移动、不可预测的环境变化或者敌对的人为干扰都可能引 起网络的割裂。除此之外，当业务具有不同的优先级时，低优先级业务需要和高 优先级业务去竞争带宽，这将使得消息转发经历更大的排队延迟。同时，出于可 靠与安全考虑，这类系统需要有严格保护措施的下层基础结构。 传感器网络( s e n s o r n e t w o r k s ) ：这类网络中的节点存在着能量、存储空间和计 算能力的不足的影响。此外，这类网络可能规模很大，包含数千乃至数百万量级 的节点。为了减少能量消耗，这类网络中的通信链路不是持续存在的。传感器网 2 容迟网络中路由算法研究 络通常通过具有协议转换能力的代理节点与其他网络互联。 针对于上述“受限网络 ，最直接、最简单的方式是将i n t e m e t 体系结构应用 于其中，但是由于这些网络可能不存在端到端的持续连接、出现巨大的网络传输 延迟、出现能量供给与存储能力不足等问题，对现有i n t e m e t 体系结构提出了巨大 的挑战。为了能够更好地应用“受限网络”，就需要提出一种新型的网络体系结 构。 1 2 延迟容忍网络概述 现有i n t e m e t 的网络架构和网络协议对于大多数异构网络来说是充足且高效 的，这些网络具备t c p i p 协议簇所要求的端到端的持续连接，对称的双向数据速 率，以及较低的端到端的丢包率和传输时延。 然而，在某些没有固定网络基础设施的地区和情况下，网络往往是分离的， 因此不能保证提供持续、稳定的连接。此外，这些环境中的网络设备常受限于其 自身的发射范围、处理能力、存储空间和电源供给。在这种“受限网络 环境中， 传统的网络协议往往不再适合。为了解决“受限网络 的数据传输，2 0 0 3 年提出 了延迟容忍网络( d e l a yt o l e r a n tn e t w o r k ，d t n ) ，定义了一个新的网络体系结构 模型。 1 2 1d t n 网络的概念 延迟容忍网络( d t n ) 模型是从一类特殊的网络场景模型中抽象出来的。d t n 最早是用来解决星际网络( i p n ) t 5 1 通信问题，现在广泛应用于多种“受限网络”环 境中，主要包括移动自组织网络( m o b i l ea d h o en e t w o r k s ，m a n e t ) 和无线传感器 网络( w i r e l e s ss e n s o r n e t w o r k ，w s n ) 6 1 。将所有这些“受限网络”中的共同特性 抽象出来就是d t n 网络模型。 d t n 网络体系结构能够很好的适应于多种“受限网络”环境中，为其提供一 种通用的网络通信方法。同时，d t n 网络模型还能够为多种异构网络之间建立有 效的通信。 d t n 网络是完全不同于传统t c p i p 网络的一种新型的网络结构，因此，d t n 网络与传统t c p i p 网络相比有着自身独特的特点f 1 1 7 - 8 ： 1 ) 数据传输长延时。端到端时延表示端到端路由上每一跳的时延总和 9 1 ，每 一跳上经历的时延可由等待时间、排队时间、传输时间和传播时间组成。例如在 星际网络中地球与火星通信，在近地点时，光传播最快需要4 m i n 的时间，而如果 在远地点时，单向传播的时间就会超过2 0 m i n 【2 1 。在传统i n t e r n e t 网络中，数据传 第一章绪论 输时间一般以毫秒计算，因此，面对如此巨大传输延时，大多数基于t c p i p 的应 用是无法实现的。 2 ) 节点资源有限。d t n 网络节点往往分布于深空、湖面、战场等环境中，其 受到体积和重量的限制，节点资源非常有限，因此，在一定程度上限制了应用的 效能。导致节点不得不采用一定的策略以节省资源，从而影响链路性能。 3 ) 间歇性连接。在许多“受限网络 中，端到端断开可能比端到端连接更普 遍。一般说来，d t n 网络断开可能是由于错误或其他原因造成的。由于移动和低 占空1 ：1 5 ( 1 0 w - d u t y c y c l e ) 影响，非错误( n o n - f a u l t y ) 性断开是最经常出现的。其中由于 移动引起的断开可能是可预测的( 例如卫星通信系统、作为数据载体的公共汽车 等) ，也可能是随机的( 例如通过漫游到达通信范围的节点) ；由于低占空比引起的 断开在低能力设备( 例如无线传感器) 中普遍存在。 4 ) 不对称数据速率。在d t n 网络中，数据传输的双向速率在很大程度上可 能是不对称的( 例如一个高速率的下行数据信道和低速率的上行控制信道) 。在完成 空间任务时，典型的双向信道的带宽容量的不对称性将达到1 0 0 0 ：1 2 ( t c p i p 协 议仅能容忍1 0 0 ：1 ) ，有的甚至只有单向信道。 5 ) 低信噪比和高误码率。d t n 网络中，环境导致的低信噪比引起信道中信号 的高误码率，如一般的光通信系统中误码率达到1 0 q 5 1 0 j 2 ，而在深空通信中，误 码率通常可以达到1 0 。1 ( t c p i p 协议能够容忍的误码率仅为1 0 巧) ，极大地影响接收 端对传输信号的解码和恢复。 6 ) 随机动态拓扑。节点由于环境变化等因素可能随机移动，也可能因为能量 耗尽或故障脱离网络，还可能由于任务需求加入网络，导致d t n 拓扑结构动态变 化。此外，d t n 链路的间歇连接使其拓扑具有很大的不确定性，体现为d t n 节点 和链路的数量及概率分布的变化，决定了路由应当能够适应随机动态拓扑的需要。 7 ) 安全性差。节点处于真实物理世界，d t n 除受到传统无线通信网络面临的 安全威胁以外，还可遇到窃听、消息修改、路由欺骗、拒绝服务( d e n i a lo f s e r v i c e ， d o s ) 和恶意代码等安全攻击。 1 2 2d t n 网络研究现状 d t n 网络最初主要是针对i p n 通信而提出来的，1 9 9 8 年i p n r g ( i p n s p e c i a l i n t e r e s tg r o u p ，星际网络研究组) 岭j 开始制订一系列星际网络通信协议，主 要研究高延迟环境下的太空通信和缺少持续连接的异构网络的协同工作环境【1 0 1 ， 为以后的发展奠定了基础。为了将i p n 的观点应用到陆地网络上，特别是传感器 网络，i r t f ( i n t e m e tr e s e a r c ht a s kg r o u p ，网络研究任务组) 创建了一个新的研究小 组d t n r g ( d t n r e s e a r c hg r o u p ，延迟容忍网络研究组) 来进行研究。d t n r g 发展 4容迟网络中路由算法研究 了两个主要协议：覆盖层体系协议( t h eb u n d l ep r o t o c 0 1 ) 和链路传输协议( l i n c k l i d e r t r a n s m i s s i o np r o t o c o l ，l t p ) 。另一方面，2 0 0 4 年初，美国国防部下的国防高级研 究计划署d a r p a ( 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 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 t n 。容断网络【l l j 主要是为了 解决链路频繁断裂的网络环境。可以看作同一概念下的另一种表述。目前，i r t f 将d t n 定义为延迟和中断容忍的交互网络( d e l a y - a n dd i s r u p t i o n - t o l e r a n t i n t e r o p e r a b l en e t w o r k i n g ) 。 通过将d t n 网络和现有的t c p i p 网络进行比较分析，可以得出现有的t c p i p 协议簇难以支持d t n 网络中的上层应用1 2 u 1 i i2 1 ，需要开发新型的网络协议，来支持 d t n 网络的上层服务。、 在现有的d t n 研究中，已经提出了束层和传输层的相关协议标准。但是，由 于d t n 网络环境复杂，还没有统一的路由标准。现阶段，d t n 的研究热点都主要 集中在其路由问题上。下面将详细介绍关于d t n 已有的体系结构，关于路由问题 的研究将在下章展开。 1 2 3d t n 体系结构及协议标准 传统的i n t e m e t 网络体系结构主要分为五层，包括物理层、数据链路层、网络 层、传输层和应用层。针对d t n 网络性能特性与i n t e m e t 网络的不同，需要在i n t e m e t 网络体系结构中应用层和传输层之间构造一个覆盖层，即“束层( b u n d l el a y e r ) ， 就是一种“容忍延迟的面向异步消息传输的覆盖层体系结构【1 3 】 ，使用“存储等 待转发 模式来克服网络中断。b u r l e i g h 等人提出了一个端到端覆盖层网络协议， 称为“束层( b u n d l i n g ) 协议”，它的功能类似于i n t e m e t 中网关的功能。d t n 网络 结构体系的具体分层如图1 1 所示。 i n t e r n e tl a y e rd t n l a y e r 图1 i i n t e m e t 与d t n 的分层体系结构对比f j o 】l 第一章绪论5 1 束层协议 束层协议( b u n d l ep r o t o c o l ，b p ) t 1 4 】是典型的覆盖网络协议之一，它可以基于现 有的i n t e m e t 协议之上，也可以基于深空通信、传感器网络等“受限网络”的特定协 议之上。该协议的基本原理是将所有必须的数据包裹在一个束( b u n d l e ) 里面，每个 节点传输这个束。在d t n 网络中，束层位于应用层与传输层之间，束层和底层协 议互相配合，使得应用程序可以跨越多个区域进行通信，如图1 2 所示。图1 2 中 假设束层协议基于的传输层协议为t c p 和s c t p 。 a p p l i c a t i o na p p l i c a t i o n j l ib u n d l e b u n d l ee n d p o i n tb u n d l ee n d p o i n tb u n d l e le n d p o i n t l e n d p o i n t t r a n s p o r tt r a n s p o r tt r a n s p o r tt r a n s p o r t l ( t c p ) ( t c p ) ( s c t p )( s c t p ) ， n e t w 。r n - p ，1 斗 一n e t w o r k ( i p ) n e t w o r k ( i p ) - i pn e t w o r k ( i p ) 图1 2 覆盖网络中的束层 由于r f c 中没有定义b u n d l e 层的具体内部结构，为了方便理解b u n d l e 层的 工作过程，可以简单给出b u n d l e 层的结构如图1 3 所示。 一 图1 3b u n d l e 层内部不恿结构图 当消息通过传输层发送到b u n d l e 层时，首先会到达存储转发模块，若消息的 目的节点就是此节点，则消息将被传送到应用层相应的端口去；若消息的目的节 点不是此节点，则存储转发模块先将消息发送到路由协议模块，路由协议通过计 算得出此消息应当被转发的下一跳，然后将消息传回给存储转发模块，存储转发 模块将根据缓存情况判断将此消息暂存在缓存中或是丢弃；随后存储转发模块根 据消息的下一跳，将数据包传递到传输层进行转发。 6容迟网络中路由算法研究 束层协议的主要功能包括【b j ： 1 1 基于保管方式的重传； 2 ) 可以处理间歇式的连接； 3 ) 除了持续性连接，可以利用预订、预测和机会连接； 4 ) 通过覆盖层端节点标识符后绑定，形成网络地址。 r f c 5 0 5 0 中详细介绍了束层协议的基本术语，束层协议格式、束的处理过程、 管理记录过程等。束层协议构造一个存储转发的覆盖网，同时还需要一个汇聚层 适配器，利用底层的网络协议实现束的发送和接收。 ( 1 ) 束层协议的基本术语 束( b u n d l e 卜_ 束是d t n 束层协议的协议数据单元。每一个束中包含两个或 更多的协议数据“模块 ，用来服务于各种不同的目的。在网络中的一个或多个 通信节点的缓存中可能同时存在着具有不同形式的相同的束。 束节点( b u n d l en o d e 卜任意可以接收和发送束的实体都可以称之为束节 点。在通常的情况中，束节点被具体化成为单个处理过程运行在通用计算机上， 但是一般的定义更为广泛：束节点可以被看成一条路线，或者一个面向对象操作 系统中的对象，一个特殊作用的硬件，等等。每个束节点有三个组成部分：束层 协议代理( b u n d l ep r o t o c o la g e n t ) 、零个或多个汇聚层适配器( c o n v e r g e n c el a y e r a d a p t e r s ) 、一个应用代理( a p p l i c a t i o na g e n t ) 。 束层协议代理( b u n d l ep r o t o c o la g e n t ，b p a 卜一节点的束层协议代理是节点的 一部分，提供柬层协议( b p ) 服务和束层协议程序的执行。 汇聚层适配器( c o n v e r g e n c el a y e ra d a p t e r s ，c l a 卜- 、汇聚层适配器发送和接 收以b p a 为代表的束，利用“本地的”因特网网络协议。 应用代j 望( a p p l i c a t i o na g e n t ，a a 卜_ 节点的应用代理是节点的一部分，它利 用束层协议服务为一些特殊目的来影响通信。应用代理由两个元素组成：管理元 素和特殊应用元素。特殊应用元素是一种要求可以传输的，接收发送的和处理特 殊应用的应用数据单元；b p a 与a a 中特殊应用元素的唯一接口是b p 服务接口。 ( 2 ) 束层协议格式 每一个束必须有至少两个部分组成。第一块必须是首要头结构，并且任何束 只有一个首要头结构。其之后是附加头部分，支持束层协议的扩展，最常见的是 载荷头结构( p a y l o a dh e a d e r ) 。 第一章绪论7 v e r s i o n p r o c e s s i n gf l a g s c o s f l a g s i s r r f l a g s h e a d e rl e n g t h ( s d n v ) d e s t i n a t i o ns c h e m e0 f f s e td e s t i n a t i o ns s p0 f b ；e t s o u r c es c h e m e0 f f s e ts o u r c es s po f f s e t r e p o r t - t os c h e m eo f f s e tr e p o r t - t os s po f f s e t c u s t o d i a ns c h e m e0 f f s e tc u s t o d i a ns s po f f s e t c r e a t i o nt i m e s t a m p ( 8b y t e s ) l i f e t i m e ( 4b y t e s ) d i c t i o n a r yl e n g t h ( s d n v ) d i c t i o n a r ya r r a y f r a g m e n to f f s e t ( s d n v ，o p t i o n a l ) t o t a la p p l i c a t i o np d ul e n g t h ( s d n v o p t i o n a l ) 图1 4 束头结构图 图1 4 是束头结构示意图。其中大多数的长度都是自划定数字值 ( s e l f - d e l i m i t i n gn u m e r i cv a l u e ，s d n v ) 。图中灰色的部分是可选的。 ( 3 ) 束层协议小结 束层协议是一类用于容忍延迟和中断的覆盖层网络协议。其主要的目的是为 了能够适用于非常广泛的环境范围，从深空通信到传感器网络中相对于传统因特 网主机更具挑战性的节点。作为覆盖网络中的束层协议可以用在多种汇聚层之上， 一方面，束层协议可以在d t n 网络中的某些受限部分之间相互过渡，另一方面， 束层节点可以部署在潜在网络拓扑中的许多地方。 2 链路传输协议 ( 1 ) d t n 网络传输层 d t n 网络的传输层与传统i n t e m e t 网络的传输层相比有着很大的不同。首先， 网络带宽利用率有限。在d t n 网络中，网络环境恶劣，在网络带宽有限的情况下， 需要最大化的利用有限带宽。传统的t c p 协议采用三次握手、慢启动、a r q 等机 制，极大的浪费了带宽，降低了链路利用率。其次，节点缓存有限。由于d t n 采 用保管传输( c u s t o d yt r a n s f e r ) 的方式迸行传输，节点的缓存就显得尤为重要，当节 点缓存不足时，就会发生拥塞，因此需要能够很快的释放节点缓存。 束层协议能够解决d t n 网络中的很多问题，但是面对d t n 网络传输层新的 特点，我们需要一种新的传输层协议，一种d t n 网络的“点到点协议”。链路传 输协议( l i n c k l i d e rt r a n s m i s s i o np r o t o c o l ，l t p ) t 1 乒18 】可以处理点到点通信中的延迟 和中断，尤其是长延迟链路的问题。l t p 是个点到点协议，所以不需要考虑路由 或者拥塞控制问题。l t p 协议能够支持束层协议，所以可以配置b u n d l e l t p 的协 议结构。 8容迟网络中路由算法研究 ( 2 ) l t p 片段结构 l t p 片段( s e g m e n 妒- i t p 数据传输的单元。它是在一个会话( s e s s i o n ) 过程 中，l 1 1 p 引擎之间相互传送的数据结构。每一个l t p 片段都是由以下三部分组成： 一个“头结构( h e a d e r ) ”、零个或多个字节的“内容( c o n t e n t ) 、零个或多个字节 的“尾部( t r a i l e r ) 一般由头结构中扩展区域表示。l t p 片段结构如图1 5 所 示。 图1 5l 1 嘈片段结构 l t p 片段的头结构包含三个数据项：一个字节的控制字节，会话i d 和扩展区 域。 l t p 片段的内容根据不同的属性通常分为四种类型：数据片段、报告片段、 报告确认片段、会话管理片段。 l t p 片段的尾部由0 到1 5 个“类型- 长度值( t y p e l e n g t h - v a l u e ，r v l ) 序列组 成。 ( 3 ) l t p 与束层协议的比较 上面介绍了容迟网络中的两种协议，现在我们对这两个协议进行简单的比较。 具体如表1 1 。 l t p 与束层协议主要的区别是，l t p 是一个“点到点协议”，而束层协议是 一个“端到端协议”。这使得l t p 能更好地适用于受限制的环境。同时，l t p 也 可以在u d p 上运行，使其可以用在一些端到端的情况。 两个协议在对于时间和节点接入实时时钟的假设不同。束层协议明确的需要 所有节点都接入一个相对精确的实时时钟。另一方面，l 耶没有如此的要求，l t p 只需要节点对通过一个粗略的同步时钟进行同步。 第一章绪论9 两个协议都可以选择性的提供安全服务，但是束层协议同时要求完整性 ( i n t e g r i t y ) 和保密性( c o n f i d e n t i a l i t y ) ，l t p 不需要保密性。 表1 1l t p 与束层协议比较 l t pb u n d l ep r o t o c o l i n t e r m e d i a t e sn o tm o d e l e dm o d e l e d c 0 0 r d i n a t e dc l o c k sn o tr e q u i r e d r e q u i r e d r e a l - t i m ec l o c k sn o tr e q u i r e d r e q u i r e d s e c u r i t ys e r v i c e si n t e g r i t yo n l yi n t e g r i t ya n dc o n f i d e n t i a l i t y ( 4 ) l t p 协议的改进 l t p t ( l t pt r a n s p o r t ) 协议是基于l t p 协议的扩展，适用于多跳环境中。作为 点到点协议的l t p 不需要携带目的节点标识，也不需要考虑拆分和路径中节点间 的拥塞。然而作为传输协议的l t p t 必须考虑这些，因此，相对于l t p ，l t p t 添加了源地址、目的地址、数据块的估计大小、端口、跳数、数据经过l t p 的主 机和时间标记、端到端的认证和拥塞通告。相对于l t p ，l t p t 有着以下的不同： 1 ) l t p t 采用a r q 逐跳进行错误重传，而l t p 使用报告确认机制。 2 ) l t p t 允许节点在整个数据块没有接收完前，将数据块转发，有时甚至将 未确认的字节转发给下一跳。 3 ) 当下一跳的m t u 对于分段来说太小时，中间节点可能会重新拆分分段。 但是，不能拆分数据块的红色部分。 4 ) 由于每个节点需要保管每个分段的比特，l t p 节点可能会因为存储有限而 产生拥塞。为了减少这种情况的发生，就需要估计数据块的大小，预留一定的空 间，当发生拥塞时取消会话。 ( 5 ) l t p 小结 l t p 协议是一个相对简单和较容易实现的延迟的容忍点到点协议。它的核心 原理是使用标记计时器( p u n c t u a t e dt i m e r ) 来抵抗延时。尽管其最主要的是用在深空 通信等大延迟网络中，在陆地网络中，例如传感器网络，也是非常有用的。l t p 不仅可以作为束层协议的汇聚层，而且还可以适用于传统无连接传输层( 例如u d p ) 之上。 1 0容迟网络中路由算法研究 1 3 论文主要工作和结构安排 本论文主要针对d t n 网络路由算法进行研究，文章的主要内容如下： 1 介绍了d t n 网络的概念，特点以及分层结构体系，对各层的协议进行了 详细的描述。 2 详细分析了现有常见d t n 路由算法，具体包括基于复制泛洪策略的路由 算法，基于转发策略的路由算法，基于历史预测策略的路由算法，基于概率策略 的路由算法和基于编码策略的路由算法。 3 根据灰色理论预测方法和马尔科夫链预测方法，建立了d t n 网络中基于 灰色一马尔科夫链位置预测模型。 4 提出了基于灰色。马尔科夫链位置预测模型的d t n 路由算法( s w r - g m ) 。 该算法利用位置预测模型得到目的节点位置，有目的性的对数据包进行传输，提 高了数据传输的方向性，使得路由算法提高了传递成功率和降低了传输时延。最 后，仿真分析证明该算法相比传统复n 泛洪策略路由算法( e p i d e m i c 算法和s w r 算法) 具有更好的网络性能。 5 提出了d t n 网络中增强型s w r g m 路由算法。该算法结合了基于节点活 跃系数喷射策略的s w r - g m 算法，使得节点在喷射数据包副本时，按照节点活跃 系数的比例，动态的转发包副本，该算法能够使得活动性能强的节点迅速的转发 数据包副本，在提高数据成功投递概率的同时，最大限度的降低路由的开销，节 约网络资源。通过仿真证明，该算法相比s w r - g m 路由算法能够在较低网络开销 的情况下，提升网络的性能。 本论文共分为五章，各章内容安排如下： 第一章介绍容迟网络及其主要研究内容。主要包括容迟网络的产生背景及特 点，容迟网络相对于传统因特网分层体系结构的不同，以及分层的协议标准。 第二章主要详细介绍容迟网络的路由问题。详细分析现有路由算法的优缺点， 引出本文的算法。 第三章详细阐述基于灰色马尔科夫链位置预测模型的d t n 路由算法，并进行 仿真验证其性能。 第四章在第三章的基础上介绍了增强型s w r - g m 路由算法，并进行仿真验证。 第五章总结了全文的工作，指出研究中的不足，并讨论了下一步的工作方向。 第二章d i n 网络中路由技术的研究 第二章d t n 网络中路由技术的研究 2 1d t n 路由概述 传统i n t e m e t 网络路由协议在“受限网络”中的性能会急剧恶化，使得 r i p ( r o u t i n gi n f o r m a t i o np r o t o c 0 1 ) 和o s p f ( o p e ns h o r t e s tp a t hf i r 蚋等路由协议无法 正常工作。由于a dh o c 网络仍然假设“存在端到端的路径 ，所以a o d v ( a dh o e o n d e m a n dd i s t a n c ev e c t o r ) 和d s r ( d y n a m i cs o u r c er o u t i n g ) 等路由协议也无法在 “受限网络”环境中使用。d t n 网络的特点决定了d t n 路由问题的复杂性。 由于链路频繁断裂或节点资源有限造成数据包丢失，d t n 路由最主要的目的 就是最大化的数据传输成功概率，同时最小化的端到端传输时延和资源消耗。在 2 0 0 4 年a c ms i g c o m m 会议中，j a i n 等人提出了d t n 网络中的路由问题，提出 了d t n 网络中评估路由算法性能的框架【1 9 】。 选择一种怎样的路由策略以保证端到端的数据传输是d t n 路由研究中的重点 与热点问题，研究人员针对不同的d t n 应用场景提出了不同的路由协议。根据路 由策略的不同，现有d t n 路由策略主要可分为消息复, 0 洪泛策略、转发策略、历 史预测策略、概率策略和编码策略等1 2 0 l 。消息复n 洪泛策略路由为增加消息传输 成功概率，由中继节点将消息进行复制，并以泛洪机制转发到下一跳节点，直至 目的节点为止；转发策略路由根据网络拓扑信息选择最佳路径，消息由此路径以 逐跳方式转发至目的节点；历史预测策略路由采用估计的方式，将历史消息传输 到目的节点的情况作为先验知识，中继节点通过决策，决定消息的转发；概率策 略路由根据节点移动类型或网络拓扑信息的某种概率分布来进行消息转发；编码 策略路由转变了传统路由策略的思路，将网络编码或纠删编码引入消息转发中， 解决消息传输过程中面临的丢弃问题，提高网络吞吐量，均衡网络负载。 2 2d t n 路由算法分析 2 2 1 基于复n 泛洪策略的路由算法 在基于复n 泛洪策略的路由算法中，网络中的节点在转发数据包时向与之关 联的多个节点发送该数据包的副本。数据包的传输是通过包的复制来实现的，网 络中存在同一个包的多个副本在传输，这种方法通过提高消息的冗余度来增加端 到端传输的成功投递率并降低网络传输时延。 1 2容迟网络中路由算法研究 1 流行性路由算法 流行性路由算法( e p i d e m i cr o u t i n g ) 1 2 q 是典型的基于复制泛洪策略的路由算 法。该算法模仿生物环境中病毒扩散传播方式，即每个被病毒传染的个体将把病 毒传给与其接触的其他个体。流行性路由算法将应用消息分布在网络中一些被称 为“携带者”的节点上。这样，消息就能够迅速的分散到整个网络中。流行性路 由算法通过“携带者”节点的移动性将消息传递到网络中的其他部分。通过这样 的数据传输方式，消息能够有很高的到达概率。图2 1 描述了流行性路由算法的基 本原理，其中移动节点用圆点表示，阴影部分为其无线通信范围。图2 1 ( a ) 中，源 节点s 希望将消息传递到目的节点d ，但是没有可用的连接路径。节点s 则将消 息传递给其通信范围内的邻节点c l 和c 2 。经过一段时间后，如图2 1 ( ”所示，c 2 运动到另一节点c 3 的通信范围内，将消息传递给c 3 。而c 3 在目的节点d 的通信 【砷l 图2 1 流行性路由算法基本工作过程 流行性路由的目标是：1 ) 在部分连接的a dh o c 网络中高效的传输消息；2 ) 最 小化的降低传输单个消息的资源消耗；3 ) 最大化的将消息传递到目的节点。流行性 路由面临以下几个问题： 路由的不确定性( r o u t i n gu n d e ru n c e r t a i n t y ) ：消息发送节点无法确定系统中节 点的位置信息。因此，一个关键问题就是确定节点是否将消息传递给潜在的“携 带者 。 资源分配( r e s o u r c ea l l o c a t i o n ) ：不同于标准的路由，流行性路由可能会同时出 现多个消息副本在传输。通常，系统需要平衡最大的传输成功率和最小的资源消 耗。 性能( p e r f o r m a n c e ) ：一个给定的数据交换和路由协议可以通过许多不同的方面 来评估。这些评估的性能指标包括消息传递的平均时延，单个信息传递的平均系 统存储与通信带宽消耗和消息传递到目的节点的能量消耗。 可靠性( r e l i a b i l i t y ) ：考虑到需要一定的传输概率，某些应用可能要求确认信息 的成功传递。 安全性( s e c u r i t y ) ：消息在到达最终目的节点之前，可能会通过任意的节点路 第二章d t n 网络中路由技术的研究 径。根据消息的敏感度和个别应用的要求，接收者可能需要某些对于消息可靠性 的认证。 流行性