（计算机应用技术专业论文）延迟容忍网络中message+ferry路由算法的研究.pdf

南京邮电大学 硕士学位论文摘要 学科 专业 工科 计算机应用技术 研究方向 计算机通信与网间互连技术 作 者 迎级硕士研究生夔盟 指导教师 童趁副数援 题 目 延迟容忍网络中m e s s a g ef e n y 路由算法的研究 英文题目 r e s e a r c ho nm e s s a g e f e r r yr u n t i n ga l g r i t h m fd t n 主j 题 词 延迟容忍网络 m e s s a g ef r e e y 路由设计 移动空间自定位 信息 队列管理 k e y w o r d s d e l a yt o r a n tn e t w o r k f e n yr o u t i n g m b i l e s p a c es e i fl c a l q u e u e m a n a g e m e n t 南京邮电人学硕上研究生学位论文摘要 摘要 本文以延迟容忍网络作为主要研究对象 叙述了延迟容忍网络的应用背景和技术架 构 分析了几种比较典型的延迟容忍网络路由协议 以及在此基础上提出性能改进的延迟 容忍网络的路由算法 在延迟容忍网络中 路由协议性能与网络资源消耗之间始终处于矛 盾的竞争关系 如何对这一矛盾进行权衡取舍 是设计延迟容忍网络路由协议的重点和难 点 同时 针对不同的网络环境和网络应用 协议性能与资源耗用量的各项指标的权重会 有显著差异 如何因地制宜的使这一指标序列达到最优 也是设计延迟容忍网络路由协议 的另一个重点 本文重点研究了m e s s a g ef e r r y 路由协议的原理 实现与性能 m e s s a g ef e r r y 路由协 议中f e r r y 在数据缓存不受限制的条件下 能够实现较高的数据到达率和较低的传输时延 但是由于此算法采用的是主动采集信息的存储转发机制 不同的通信半径 缓存队列管理 节点运动速度都会对协议性能产生较大影响 针对m e s s a g ef e r r y 路由协议的这些特点和不 足 本文对其进行了改进和优化 使f e r r y 根据概率对网络拓扑结构进行预知 从而空间 自定位 以及改进队列管理 控制网络中信息冗余度的平衡 在保证协议性能的前提下减 小了对网络资源的消耗 关键词 延迟容忍网络 m e s s a g ef r e e y 路由设计 移动空间自定位 信息队列管理 a b s t r a c t p a p e r d e l a yt o l e r a n tn e t w o r ka st h em a i n b j e c t fs t u d y d e s c r i b e dt h e d e l a yt o l e 啪tn e t w r k a p p l i c a t i o nb a c 蚝r o u i l da n dt e c h n i c a l a r c h i t e c t u r e a n a l y s i s fs e v e r a l t y p i c a ld e i a yt l e r 觚i n e t r k r o u t i n gp r o t o c o l s i n d t n r o u t i n gp r o t c 1p e r f b 咖a n c ea n dn e 帆 r k r e s u r c e c o n s u m p t l nh a sa l v a y sb e e na tt h ec n t r a d i c t i nb e t w e e nt h e c m p e t i t i v er e l a t i o n s h i p h wt d e a j 啪t hac n t r a d i c t i n i s d e s i g l l e dt ot l e r a t en e t w o r kd e l a y s 觚dd i 历c u l t i e si n r o u t i n 2 p r o t o c o l sf o c u so n a tt h es 锄e t i m e f o rd i f f e r e n tn e t w o r k e l l v i r o n m e n t s h o wt 0m a k eo d t i m a l n e 咖r kp e 哟锄a l l c e i sa l s od t n r o u t i n gp r o t o c 0 1 sf o c u s0 ft h es t u d y 1 i sd i s s e 咖i o n f o c u s e so nt h e p r i n c i p l e so f m e s s a g ef e 町r o u t i n g p r o t o c o i s l m p i e m e m a t l o na i l dp e r f o r m a n c e f e r r yi nt h ed a t ac a c h eu n r e s t r i c t e d c o n d i t i o n s c a na c h i e v e h 1 曲e rd a t a 删v a lr a t ea n dal o wp r o p a g a t i o n d e l a y b e c a u s et h i sa l g o r i t h mi s p r o a c t i v e l v a c q u i s i t i o n1 n f o n l l a t i o n s t o r a g e f o r w a r d i n gm e c h a n i s m d i f f e r e n t c o m m u n i c a t i o nr a d i u s c a c h i n gq u e u em a n a g e m e n t n o d ev e l o c i t yw o u l dp a i r sa l g o r i t h mp e r f o r m a n c e g r e a t e ri m p a c t m e s s a g ef e n yf o rt h ec n a r a c t e r i s t i c so f r o u t i n gp r o t o c o l s t h i sp a p e rh a sb e e ni m p r o v e da 1 1 d o p t i m i z e d a n db ec o m b i n e dw i t ht h en e t w o r kt o p o l o g ya n di n f o r m a t i o n r e d u n d a n c yo fb a l a n c e a 1 1 ds p a t l a lo n e n t a t i o nm e c h a n i s m t h e p e r f o r m a n c eg u a r a n t e ea g r e e m e n tu n d e r t h ep r e m i s eo fa n a g r e e m e n tt or e d u c et h ec o n s u m p t i o no f n e t w o r kr e s o u r c e s k e y w o r d s d t n m e s s a g ef e r r yr o u t i n g m s s l q u e u em a n a g e m e n t i i 蹦 锄 咖 血 矿 出 鸣 啪 舢 慨 嗽 咖 似 嘣 龇 龇呱 如 懿 m m 出 够b 吖 培 迅 暑 蛳 咖 咖 泐 鸭 一 雠 m 翩 呔啪 南京邮电大学硕1 研究生学位论文 目录 目录 摘要 i a b s t r a c t i i 目录 i i i 缩略词 v 第一章绪论 1 1 1 研究背景 1 1 2 无线传感器网络特点 1 1 3 无线传感器网络体系结构 2 1 4a dh o c 网络路由协议 3 1 4 1 表驱动的a dh o c 网络路由协议 4 1 4 2 源节点触发的a dh o c 网络路由协议 4 1 5 研究对象及创新点 7 1 6 本文内容安排 7 第二章延迟容忍网络及协议概述 9 2 1 延迟容忍网络的主要特性 1 0 2 2 典型的延迟容忍网络应用项目 11 2 2 1z e b r a n e t 1 1 2 2 2 车载网络 1 2 2 2 3d a t am u l e 1 2 2 3 延迟容忍网络路由协议设计的关键问题 1 3 2 4 延迟容忍网络关键技术与相关研究成果 1 4 2 4 1 基于洪泛思想的路由算法 1 4 2 4 2 基于历史信息思想的路由算法 1 5 2 4 3m e s s a g ef e r r y 路由协议 1 6 2 5 本章小结 1 9 第三章m e s s a g ef e r r y 路由协议及其改进 2 0 3 1m e s s a g ef e r r y 路由设计原理 2 0 3 2m e s s a g ef e r r y 路由设计中的问题 2 2 3 3m e s s a g ef e r r y 路由设计 2 3 3 3 1 网络模型和节点信息的体系结构 2 3 3 3 2m e s s a g ef e r r y 路由的路径节点选择 2 5 3 3 3m e s s a g ef e r r y 路由路径节点遍历 2 9 3 3 4m e s s a g ef e r r y 路径节点的坐标更新 3 0 3 3 5 节点中的副本消息 3 3 3 3 6 节点存储信息的生存管理 3 4 3 4 本章小结 3 6 第四章m e s s a g ef e r r y 路由协议的仿真研究 3 7 i l i 南京邮电人学硕上研究生学位论文 4 1 仿真模型 4 1 1 模拟仿真考虑的问题 4 1 2 模拟仿真参数 4 1 3 模拟仿真对比的算法 4 2 仿真结果与分析 4 2 1 四种算法的性能比较 4 2 2 路径节点效率 4 2 3 节点的通信半径对性能的影响 4 2 4 网络中节点数量的变化对网络性能的影响 4 2 5f e r r y 与节点之间接触的公平性 4 2 6 节点运动速度的变化对性能的影响 4 2 7 节点存储空间大小对性能的影响 4 2 8 网络寿命的分析 4 3 本章小结 第五章总结与展望 致 射 参考文献 发表论文 i v 5 0 5 1 5 2 5 6 录 7 8 8 9 9 9 o o 2 4 5 7 8 9 扣一3 3 3 3 3 3 4 4 4 4 4 4 4 4 南京邮电人学硕上研究生学位论文 缩略词 缩略词 缩略词英文全称 中文 d t n d e l a yt o l e r a n tn e t w o r k i n g延迟容忍网络 d t n r g d e l a yt o l e r a n tn e t w o r k i n gr e s e a r c hg r o u p延迟容忍网络研究组 m a n e t m o b i l ea dh o en e t w o r k 移动a dh o c 网络 d s r d y n a m i cs o u r c er o u t i n g 动态源路由算法 a o d va d h o co n d e m a n dd i s t a n c ev e c t o r 无线自组网按需平面距离矢 量路由协议 d s d v d e s t i n a t i o ns e q u e n c e dd i s t a n c ev e c t o r目标序列距离矢量路由协议 i p n r g i n t e r p l a n e t a r yi n t e r n e tr e s e a r c hg r o u p 星际互联网研究小组 e p i e p i d e m i cr o u t i n gp r o t o c o l洪泛路由协议 h c h o pc o u n t跳数 n i m fn o d ei n i t i a t e dm e s s a g ef e r r y i n g 普通节点初始化协议 f i m f f e r r yi n i t i a t e dm e s s a g ef e r r y i n g摆渡节点初始化协议 g p s g l o b a lp o s i t i o n i n gs y s t e m 全球定位系统 i e e ei n s t i t u t eo fe l e c t f i c a la n d e l e c t r o n i c s 电气电子工程师协会 e n g i n e e r s m f m e s s a g ef e r r y i n g摆渡信息协议 s v s u m m a r yv e c t o r需传输数据索引 b e rb i te r r o rr a t e 误码率 p e r p a c k e te r r o rr a t e 误组率 m i t m a s s a c h u s e t t si n s t i t u t eo ft e c h n o l o g y麻省理工学院 m s s lm o b i l es p a c es e l fl o c a l 移动空间自定位路由算法 r 订 r o u n d t r i pt i m e往返时间 v 南京邮电大学硕十研究生学位论文 第一章绪论 1 1 研究背景 第一章绪论 随着人们对移动通信的需求增强 近年来 移动通信技术得到了飞速普及和发展 新 技术不断涌现 蜂窝移动通信系统在短短十几年间就完成了从第一代到第二代和第二代半 的跨越 并正在向第三代系统演进 此外 无线局域网 i e e e8 0 2 1 1 蓝牙 b l u e t o o t h 家庭无线网 h o m e r f 等移动通信新技术也纷纷涌现 这些技术使得人与人之间的通信更加 方便快捷 也使人们的生活变得更加丰富多彩 通常提及的移动通信技术都是有统一接入入口的 但对于一些特殊的应用场合 这种 架构方式并不能胜任 比如 战场上部队的快速部署和推进 地震或水灾等大型灾害后的 营救 野外科考作业 以及临时性组织的大型会议等 这些场合的通信不能依赖于任何预 先部署的网络设施 或者预先部署的设施已经因灾害损毁而失去效用 而是需要一种能够 临时快速自动组网的移动通信技术 作为移动通信的一个重要分支 a dh o c 网络技术可以 满足这些特殊场合的需要 但是 a dh o e 自组网络也需要有连通的路径 如果网络长时间 处于不连接状态 如稀疏传感器网络 各个移动节点都长时间的不在相互的通信范围内 那么现有的网络协议就不能够有效的运行 本文就是在这样的背景下进行研究的 1 2a dh o c 网络 1 2 1a dh o c 网络介绍 a dh o c 网络 1 是由一组带有无线收发装置的移动终端组成的一个多跳动临时性自治系 统 网络中的移动终端具有路由和报文转发功能 可以通过无线连接构成任意的网络拓扑 这种网络可以独立工作 也可以接入i n t e r n e t 或蜂窝无线网络 在后一种情况中 a dh o c 网络通常是以末端子网的形式接入现有网络 考虑到带宽和功率的限制 a dh o c 网络一般 不适于作为中间承载网络 它只允许产生于或目的地是网络内部节点的信息进出 而不让 其它信息穿越本网络 从而大大减少了与现有i n t e r n e t 互操作的路由开销 k dh o c 网络 中 每个移动终端兼备路由器和主机两种功能 作为主机 终端需要运行面向用户的应用 程序 作为路由器 终端需要运行相应的路由协议 根掘路由策略和路由表参与分组转发 和路由维护工作 a dh o e 网络同时具备移动通信网络和计算机网络的特点 是一种特殊的 移动计算机网络 l 堕室堂皇奎兰婴主堕窒生兰堡笙壅笙二里堑笙 无线传感器网络是一种a dh o c 网络 可应用于布线和电源供给困难的区域 人员不能 到达的区域 如受到污染 环境不能被破坏或敌对区域 和一些临时场合 如发生自然灾 害时 固定通信网络被破坏 等 它不需要固定网络支持 具有快速展开 抗毁性强等特 点 可广泛应用于军事 工业 交通 环保等领域 引起了人们广泛关注 1 2 2 无线传感器网络体系结构 无线传感器网络典型的体系结构如图卜l 所示 节点具有传感 信号处理和无线通信 功能 它们既是信息包的产生者 也是信息包的转发者 通过网络自组织和多跳路由 将 数据向网关发送 网关可以使用多种方式与外部网络通信 如i n t e r n e t 卫星或移动通信 网络等等 大规模的应用可能使用多个网关 节点由于受到体积 价格和电源供给等因素的限制 通信距离较短 只能与自己通信 范围内的邻居交换数据 要访问通信范围以外的节点 必须使用多跳路由 为了保证网络 内大多数节点都可以与网关建立无线链路 节点的分布要相当的密集 如图卜l 图1 1 无线传感器网络应用模式 在不同的应用中 传感器节点设计也各不相同 但是它们的基本结构是一样的 节点 的典型硬件结构如图卜2 所示 主要包括电池及电源管理电路 传感器 信号调理电路 a d 转换器件 存储器 微处理器和射频模块等 节点采用电池供电 一旦电源耗尽 节 点就失去了工作能力 为了最大限度的节约电源 在硬件设计方面 要尽量采用低功耗器 件 在没有通信任务的时候 切断射频部分电源 在软件设计方面 各层通信协议都应该 以节能为中心 必要时可以牺牲其他的一些网络性能指标 以获得更高的电源效率 2 南京邮电大学硕上研究生学位论文第一奄绪论 图1 2 无线传感器网络节点结构图 平面a dh o c 模型灵活并且功耗较低 但只适合于中等规模的无线传感器网络 原因 是 网络内所有传感器的感知数据都要通过s i n k 节点附近的传感器节点中继 将信息转 发给s i n k 节点 当网络规模很大 数据很多时 s i n k 节点附近的传感器节点会很快因能 量耗尽而无法工作 最终导致网络无法联通 信息无法到达s i n k 节点 另外 对于移动 的传感器节点应用环境 现有的路由协议是不适用的 1 2 3a dh o c 网络路由协议 现在的通用的网络体系结构都是基于t c p i p 的 已成为不同网络互联的基础 而 t c p i p 协议族是一种提供了基于不同链路层技术的端到端通信机制 通常来说 t c p i p 协议簇的平稳运行依赖如下物理链路特性假定 1 在数据源和目的地之间存在端到端的连通路径 2 在网络中任何节点对之间的最大往返时间 r t t 不能太长 3 端到端的分组丢失率较小 然而现在有一类所谓的 受限网络 它可能违反了上述假定中的一个或多个 这使 得当前的t c p i p 模型不能很好地为其提供服务 特别是主机在通信时移动 易导致数据丢失 t c p 将其解释为拥塞 并激发拥塞控制 机制 但这是没有必要的 因为一旦移动停止 无线主机又开始接收数据了 这样做就导 致t c p 的性能下降 而如果无线主机频繁移动的话 则性能下降更快 所以移动a dh o c 的网络特点有 1 动态拓扑网络中的节点可以任意移动 因此 网络的拓扑结构也可能会变化 2 链路带宽受限 容量时变由于拓扑动态变化导致每个节点转发的非自身作为目的地 的业务量随时间而变化 因此它的链路容量表现出时变特征 同时竞争碰撞和干扰使得网 络的实际带宽小于理论计算得到的带宽 3 能量受限由于网络节点的移动特征 其中大多数节点以电池作为动力 因而 在进 行系统设计时节能就成为一个非常重要的指标 3 南京邮电大学硕士研究生学位论文第一荦绪论 4 物理上安全有限移动网络比固定网络有线和无线更易受到安全威胁 需要克服无线 链路的安全弱点及移动拓扑所带来的新的安全隐患 针对a dh o c 传感器网络的主要特点 单向链路 容量时变 带宽受限 易干扰 高 误码率 高功率消耗 能量限制等 研究人员提出了很多比较成熟的路由算法 1 表驱动的a dh o c 网络路由协议 常见的a dh o c 网络路由协议分为两类 一种是表驱动的路由协议 在这种路由协议中 要求每个节点维护一张或多张表格 这些表格存储到达其他节点的路由信息 路由协议不断地检测网络拓扑和链路质量的变 化 当检测到变化时 节点在网络中发送路由更新消息 收到更新消息的节点更新自己的 路由表 所以路由表可以准确地反映网络的拓扑结构 源节点一旦要发送分组 可以立即 获得到达目的节点的路由 先应式路由协议的时延较小 但是开销较大 不同的先应式路 由协议的区别在于所需路由信息表的数目和网络结构变化时更新消息在网络中传播的方 式 其典型的路由协议是d s d v d e s t i n a t i o ns e q u e n c e dd i s t a n c ev e c t o r 该路由协议 是建立在经典的分布式路由算法基础上的一种表驱动路由协议 它利用序列号的先后顺序 标的 避免路由环路的产生 其中 每个移动节点都保存并维护一个包括了所有可能的目 的节点 到该目的节点的跳数和目的地序列号信息的路由表 一个节点增加它的当前序列 号并把它添加到自己产生的更新消息中 这个序列号和距离信息一起进行传输 任何没有 下一跳而不能进人其目的节点接口的节点 需要增加这个序列号并在这条路由的下一次广 播中使用这个新的序列号 如果一个节点的邻节点收到了到相同目的节点的序列号大于此 节点的序列号 就把这个路由记录变为无效或是更改路由记录 当这个节点收到具有相同 序列号的路由信息时 这个无效记录就可以变为有效 d s d v 的实现依赖于更新消息的周期 性传输 这种传输所产生的开销以矛增长 d s d v 路由协议的优点 1 可以发现最短路径 2 路由表确定后 网络不变或者变化较小时 传送很方便 3 目的地序列号可以判别路由是否过时和避免路由环路的产生 缺点是需要定期广播和更新路由表 这样会占用大量的网络资源 2 源节点触发的a dh o c 网络路由协议 另外一种是源节点触发的按需路由协议 当源节点需要向目的节点发送数据时 在 4 大学硕十研究生学位论文 第一章绪论 发起一个路由发现过程 当一条路由被发现或者所有可能的路由排列被检查后 该 成 路由建立后 还需要路由维持过程 直到从源端发出的任何路径都不能到达目 或者不再需要路由 才停止路由维持 为了提高效率 节点可以将找到的路由保存 中供后续发送使用 与先应式路由协议相比 反应式路由协议开销较小 但是数据 的时延较大 典型的路由协议是d s r d y n a m i cs o u r c er o u t i n g 协议使用源节点路由而不是逐跳 每一个寻路的分组在其头部都携带了完整的必经节点的顺序列表 每个节点有一个 冲区用来存放到目的节点的所有路由 d s r 主要包括两个过程路由发现和路由维持 源节点使用洪泛算法发送路由请求消息 r r e q r r e q 包含源节点和目的节点地址 以及 惟一的标志号 中间节点转发r r e q 并附上自己的节点标识 当路由请求分组在网络中传 输时 它到达的每一个节点都检查自己的路由表中是否有到达目的节点的路由 如果有 该节点将向源节点发送路由应答消息 r r e q 并反转源节点到目的节点的路由供r r e q 消 息使用 当路由请求分组到达了目的节点时 中间节点就查看这条路径是否在高速缓冲区 中 如果 否 就把这个目的节点和路由加到自己的高速缓冲区中以备将来使用 d s r 的优点 1 按需发现 节点仅需要维持与它通信的节点的路由 消除了周期路由广播和其他 协议中所出现的邻节点的检测分组 这就减少了带宽的占用和所需的能量和协议开销 2 使用路由缓存技术减少了路由发现的耗费 3 一次路由发现过程可能会产生多条到目的点的路由 缺点 1 每个分组的头部都需要携带路由信息 额外开销较大 路径长时开销线形增长 2 路由请求消息采用洪泛方式 相邻节点路由请求消息可能发生传播冲突并且可能会 产生重复广播 3 由于缓存 过期路由会影响路由选择的准确性 4 路径不一定是最短的 源节点触发的按需路由协议比较常见的还有a o d v a dh o eo n d e m a n dd i s t a n c e v e c t o r a o d v 协议综合了d s r 算法和d s d v 算法 与d s d v 不同的是a o d v 是反向的 只维 持需要的路由 当源节点需要向目的节点发送分组时 广播一个路由请求信息给它的邻居 节点 其中包含了最近所知道的目的节点的序列号 邻居节点依次向周围节点广播此分组 直到分组到达有目的节点路由信息的中间节点或者目的节点本身 这个节点产生一个包含 到目的节点所需跳数和最近所知道的目的节点路由应答分组的序列号 避免路由环路的产 气 南京邮电大学硕士研究生学位论文 第一章绪论 生 并能判断中间节点是否响应了相应的路由请求 的应答 一个节点将丢弃重复收到的 请求分组 当节点转发路由请求分组时 它会将其上游节点的标志i d 写入路由表 从而 创建一条从目的节点到源节点的反向路由 a o d v 定时发送h e l l o 信息来维持路由表信息 当源节点移动时 它会重新发起路由发现 如果中间节点移动 那么与其邻节点会发现链 路失效并向上游节点发送链路失效消息一直传送到源节点 然后源节点根据情况重新发起 路由发现 a o d v 算法的优点 1 按需发现 减少了带宽的占用和所需的能量和协议开销 2 可以利用多播的优势 3 可以发现最短路径 缺点是依赖于对称性的链路 而不能处理非对称性链路的网络 1 3 特殊的a dh o c 网络 无线传感器网络典型工作方式如下 使用飞行器将大量传感器节点 数量从几百到几 千个 抛撒到感兴趣区域 节点通过自组织快速形成一个无线网络 节点既是信息的采集 和发出者 也充当信息的路由者 采集的数据通过多跳路由到达网关 网关 一些文献也 称为s i n kn o d e 是一个特殊的节点 可以通过i n t e r n e t 移动通信网络 卫星等与监控 中心通信 也可以利用无人机飞越网络上空 通过网关采集数据 通过对a dh o c 网络协议和应用的介绍 可以知道a dh o e 网络具有单向链路 容量时 变 带宽受限 易干扰 高误码率 高功率消耗 能量限制等特点 在此基础上也提出了 很多路由算法 但是对于特殊的a dh o c 网络 比如在大范围内的无线传感器网络中 节 点个数较少且移动 使得网络长时间的间断连通 还有超长距离数据传输 如星际网络之 间信息的传输 存在高延迟路径 应用在野生动物追踪 野生动物是在比较宽广的环境中 运动 由于网络信号不能全覆盖 收集野生动物的活动信息就比较困难 还有应用在车载 网络 行驶在道路上的车辆由于速度快 密度不均匀形成了一个车载网络 这种网络在交 通事故预警 路况检测 拥塞预报等交通安全应用中具有巨大的潜力 稀疏的传感器网络 星际网络 陆地移动网络等网络 使得当前的i n t e r n e t 体系结 构和其中许多协议以及a dh o c 网络路由算法 都无法很好的适用 当端节点具有严格的 能量和存储空间限制时 问题将更加恶化 由于移动性和特殊应用缺乏 常常连接 的基 础结构 使得这些特殊网络有它们自己的专有协议 为了实现这些网络之间的互联 研究 者们提出了在端到端连接和节点资源都受限时的一种网络体系结构和应用接口 6 南京邮电大学硕士研究生学位论文第一章绪论 这种由于资源环境限制 源节点与目的节点之间的链路中断持续时间较长 以至于源 节点和目的节点间不能时刻存在连接路径的网络 称为延迟容忍网络 在下一章将做详细 的介绍 1 4 研究对象及创新点 就目前而言 延迟容忍网络的研究处于起步阶段 其技术标准和规范还在起草中 一 些研究组织和项目开始建立起来 比如i e t f 下属的i r t f 和d a r p a 联合建立的i p n r g i n t e r p l a n e t a r yi n t e m e tr e s e a r c hg r o u p 星际互联网研究小组 由i r t f 资助建立的 d t n r g d e l a yt o l e r a n tn e t w o r k i n gr e s e a r c hg r o u p 口2 3 等等 延迟容忍网络不要求网络的全连通 更适合实际的自组网需求 且对于实现未来普适 口n 计算具有重大影响 因而近年来引起了科研人员的密切关注 在网络领域相关著名会议 上 如s i g c o m m m o b i c o m i n f o c o m m o b i h o c i c n p p e r c o m 等 相关的 重要研究成果逐年增多 此外 还专门成立了一些研讨会 如m o b i c o m 的c h a n t s m o b i s y s 的m o b i o p p i c d c s 的d t m n 以及p e r c o m 的i c m a n 等 供研究者交流 鉴于延迟容忍网络在国外的发展已经取得了一定的成果 进一步深入理解延迟容忍网 络的概念和发展趋势 是十分有意义的 本文主要对一下几个方面进行的研究 1 对d t n 网络进行了研究 详细阐述了d t n 网络的内涵 主要特性以及典型应用环 境 2 对d t n 网络路由进行了研究 叙述了目前研究比较多的d t n 网络路由协议 重点 研究了f e r r y 路由协议 对其进行改进 进一步研究了f e r r y 自定位算法和队列 信息管理 3 对改进的f e r r y 路由协议进行路由仿真 对不同的参数环境下进行性能分析 创新点 根据d t n 的特点 重点研究了其路由算法 对于f e r r y 移动路由设计了一个 新的框架 使得f e r r y 和普通节点之间不需要事先联机通信 通过f e r r y 自定位路由算法有 效地寻找节点 实现数据信息的采集 并且增加了队列管理机制 提高了算法的公平性和 性能的同时 并没有增加过多网络中的信息冗余 1 5 本文内容安排 第一章简要阐述了a dh o c 网络的体系结构和常用的路由协议 在此基础上提出了延 7 雨京邮电大学硕士研究生学位论文 第一章绪论 迟容忍传感器网络的研究背景 现状 应用领域和主要特点 指出了延迟容忍传感器网络 研究中的关键问题和研究热点 分析了其中的发展趋势与技术挑战 最后提出本文研究工 作 说明了研究思路和内容组织结构 第二章阐述了d t n 网络的主要特性 d t n 网络研究的相关热点问题加以介绍 包括延 迟容忍网络转发机制 节点移动模型和典型应用以及几种较有影响的d t n 路由协议 第三章重点对m e s s a g ef e r r y 路由协议进行了原理和性能研究 并针对其不足进行了 改进和优化 研究了f e r r y 路由的算法原理 协议实现及其改进优化 第四章重点放在了仿真方面 提出需要解决的主要技术难点并给出了解决方案 详细 描述了m s s l 路由协议仿真的实现和性能评估 第五章对本文所做的工作进行了全面的总结和展望 8 南京邮电大学硕上研究生学位论文第二章d in 网络介绍及协议概述 第二章延迟容忍网络及协议概述 对于传统的a dh o c 网络 一般假定从源端到目的端总是存在通路 即在一个不是很 大的通信范围内或者移动网络中节点的无线通信范围足够大 这样在绝大部分时间内 网 络中的任何一个节点都至少和另一个节点连通 彼此在对方的无线通信范围之内 从而保 证现有a dh o c 路由协议 d s d v d s r a o d v 等 能够有效运作 在一定程度上实现较高的数 据传输成功率 实时性 固定比特率传输 然而 随着新型无线网络设备 系统的出现 比如 蓝牙b l u e t o o t h 网络的覆盖距离只 有1 0 一1 0 0 米 很多无线传感器网络的节点传输半径也比传统无线设备小得多 和a dh o c 网络部署环境的变化 比如 将a dh o c 网络部署到更广阔的野外 战场 科考 救灾环境 中 上述普遍覆盖条件很难得到满足 同时 研究者将a dh o c 网络应用到许多对实时性 要求较低而对节点功耗较敏感的实际项目中去 普遍覆盖条件是否满足也变得不再那么重 要 鉴于这种新出现的a dh o c 网络中节点分布的稀疏性 称为稀疏a dh o c 网络n 3 捌 在稀疏a dh o c 网络啪 3 的概念基础上 本世纪初提出了d t n 堙1 d e l a yt o l e r a n c e n e t w o r k 网络 即全称为延迟容忍网络 是在总结了稀疏a dh o c 网络特点n 钔的基础上 提出的概念 本文在传感器网络的基础上研究延迟容忍网络的 随着研究的深入 d t n 应用环境越 来越多的被研究者发现并拓展开来 其它应用领域的研究者也逐渐开始考虑将d t n 网络系 统和技术引入本领域 比如 在微观上 无线传感器网络的研究和开发方兴未艾 在宏观 上 随着空间技术的发展和需要 星际间网络通信的研究也开始进入人们的视野 很多科 研人员在不发达的第三世界国家部署d t n 网络 帮助当地居民实现最基本的互联网体验 生物学者在野生动物身上挂载无线通信设备来研究其习性 很多时候只能依靠d t n 网络技 术才能完成这种面向广阔地域的研究工作 与此同时 软硬件技术的发展在很大程度上使d t n 网络的部署成为可能 比如极低功 耗芯片设计理论和工艺技术的出现 以及针对这种硬件的需要丌发出来的编译环境和嵌入 式操作系统 低功耗长距离无线电通信技术的发展也为d t n 网络部署所必须 例如 行驶 在公路上带有智能设备的车辆自组成车载网络 实现交通事故预警和其他道路安全应用 各种配备蓝牙或w i f i 接口的手持电子设备 如m p 3 播放器 手机 p d a 等自组成网络以 实现数据共享或协作访问互联网 放置在动物身上的传感器组成移动传感器网络收集动物 迁徙数据等 在上述的各种实际自组织网络应用中 节点移动 节点稀疏 射频关闭或障 9 两京邮电人学颂上研究生学位论义 第二章d t n 网络介绍及协议概述 碍物造成信号衰减等多种原因都可能导致网络大多数时候不能连通 这种网络环境中 传统的m a n e t m o b il ea dh o cn e t w o r k 刚n 们n 2 1 通信模式无法有效运 行 因为m a n e t 在传输用户数据之前 一需要预先通过a o d v a dh o co nd e m a n d d i s t a n c e v 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 等路由算法建立通信端点之间的路由 并将数据 分组按照节点路由表中确定的下 跳节点顺序转发到目标节点 这种工作模式隐含一个重 要的假设 网络大部分时候是连通的 任一节点对之间存在至少一条完整的端到端通信路 径 而在前述网络中 在一个特定时刻 网络可能被分割成不连通的子区域 源节点和目 标节点位于不同的连通域而导致m a n e t 路由协议不能发现去往目标节点的路由 然而 通 信源和目标不存在完整连通路径并不意味着不能实现通信 由于节点的移动 两个节点可 以进入相互通信范围而交换数据 延迟容忍网络就是利用这种节点对之间的逐跳转发将数 据从源节点传输到目标节点 m 3 m 蚍蜘 2 1 延迟容忍网络的主要特性 d i n 不同于现有的网络 它具有如下几个特性 1 路径和链路特性 高延迟 低数据传输率 端到端延迟表示在单向传输时每一跳的延迟总和 每一跳延 迟是由通过每一链路时的传输时间 处理时间和传播时间和排队时间组成的 对d t n 来说 传输率可能是比较小的 例如大约l k b p s 延迟可能是比较大的 大约5 秒或以上 而数 据传输率在很大程度上可能是不对称的 例如一个较大的数据下行返回信道和较小的上行 控制信道 n 射 网络断开时间较长 网络中端到端断开可能比端到端连接更普遍 一般说来 断开可 能是由于错误或其它原因造成的 非信息错误断开频繁地出现在无线传感器网络环境中 主要是由于传感器节点的移动或传感器节点能量耗尽引起的 长排队时间 在断开很普遍的d i n 中 排队时间可能是相当大 有可能达到几小时 这就表明 信息可能被存储在路由节点相当长的时间 2 端系统特性 有限的寿命 在某些延迟容忍网络中 如无线传感器网络 军事网络和紧急反映网络 等 中 端节点可能被放置在敌对环境或恶劣环境中 在这种情况下 由于环境恶劣或能 量消耗 网络节点的寿命通常较短 低占空比操作 当节点被放置在没有供电系统的区域时 它们通常使用电池 也可能 使用太阳能充电 即使可以充电 这些系统通常也通过限制他们的占空比去努力节约能 1 0 南京邮电大学硕 研冗生学位论文 第二章d t n 网络介绍及协议概述 量 在一些情况下 例如电池供电的传感器 为了实现整个网络的长寿命 占空比维持在 1 这样的设备定期收集数据 并以一定的速率 通常很小 进行数据汇报 对这样的系统 通常预先规划正常的运行时间 断开影响路由协议的操作 有限的资源 延迟容忍网络中节点的存储能力有限 例如 一个存储能力有限的传感 器只能收集数量有限的数据 因为它的存储被正在传输中的数据全部使用 除此之外 端 节点还需要至少保持r t t r o u n d t r i pt i m e 时间的重传缓存 在这期间 节点执行能量降 级模式操作 这使得系统设计非常复杂 特别是在收到其它异步信息或监测到一些突发事 件发生时尤其严重n 引 高误码率 链路上的误码需要更正 它需要更多的比特和更多的进程 或重新传递整 个包 这是大多数网络采取的方法 对于一个给定的链路误码率 逐跳 h o p b y h o p 的重传少于端到端 e n d t o e n d 的重传m 1 目前d t n 网络没有一个严格的定义 通过上面对d t n 网络特性的描述 可以做出一个 描述性的定义 d t n 网络是一种由于资源环境限制 源节点与目的节点之间的链路间歇性 中断且中断持续时间较长 以至于在任意时刻源节点和目的节点间可能不存在路径的网 络 2 2 典型的延迟容忍网络应用项目 下面介绍一下延迟容忍网络中比较典型的实验和应用 2 2 1z e b r a n e t z e b r a n e t 呦1 是普林斯顿大学开发的用来跟踪野生动物 该实验项目现阶段主要以非洲 野生斑马作为研究对象 故名为z e b r a n e t 生活习性的一套无线传感器网络 z e b r a n e t 通 过挂载在野生动物身上的小型传感器来跟踪其在极广阔地域上的活动 涉及到固定和移动 传感器的部署 管理和通信等方面问题 为了使传感器网络系统能够有效运作 z e b r a n e t 的研究者开发出了高功效 e n e r g y e f f i c i e n t 的无线节点 硬件上 z e b r a n e t 的无线节点集成了g p s g l o b a lp o s i t i o n i n gs y s t e m 卫星定位系统 嵌入式处理器单元 低功率无线收发器和f l a s hr o m 依靠小型的太阳能 电池提供能量 软件上 搭载了轻量级嵌入式操作系统和具有存储一转发式路由 s t o r e a n d f o r w a r dr o u t i n g 功能的点对点 p e e r t o p e e r 无线通信协议 并针对模块化 小型 化 自适应性和可维护性设计进行了优化 考虑到跟踪对象活动的地域非常广阔而节点收 发器的功率很小 无线节点到基站的多跳通路存在的几率很小 所以z e b r a n e t 只能采用单 南京邮电大学硕士研究生学位论文第二章d t n 网络介绍及协议概述 跳 j 则接收信息 s o o 源肖点s 口 圈i i i e l 一 麓发送 接收信息 9 o o 目的j 了点d 图2 1n i m f 协议工作原理示意图 图2 一l 是n i m f 实现的示意图 f e r r y 固定轨迹 轨迹在图上己标出 上移动 需要发送 1 7 由 删丫口 陀 图2 2n i m f 协议普通节点状态转移图 普通节点有w o r k i n g g ot of e r r y s e n d r e c v 和g 0t ow o r k 四种状态 初始状态 为w o r k i n g 需要向f e r r y 靠近 以发送或接收数据时进入g ot of e r r y 状态 如果此时 就在f e r r y 传输范围内 则直接进入s e n d r e c v 状态 进入f e r r y 传输范围内后转为 s e n d r e c v 状态并与之交换数据 交换完成后节点进入g ot ow o r k 状态回到原工作位置并 进入w o r k i n g 状态 如果恰好就在原工作位置 则直接从s e n d r e c v 转为w o r k j n g 状态 图2 3 是f i m f 实现的示意图 开始f e r r y 沿默认路径 d e f a u l tr o u t e 移动并用长距 离无线电广播自己的位置信息 f e r r yl o c a t i o n 节点s 收到该信息后发送服务请求 s e r v i c er e q u e s t 信息 f e r r y 收到请求后调整自己的移动轨迹向s 靠近 期间s 发送 l o c a t i o nu p d a t e 信息来通告自己的新位置 当f e r y 和s 靠近后 通过短距离无线电来交 换数据 数据交换完成后 f e r r y 重新回到自己的默认路径 对于f i m f 运行模式如下 1 8 南京邮电大学硕士研究生学位论文 第二章d t n 网络介绍及协议概述 f e r r y 向j 普通节点收集信息模式 f e r r y 路由 口 2 5 本章小结 发送 接收信息 口m n v o 州o a e j 短波通信 长波通信 图2 3f i m f 协议工作原理示意图 本章分别提出了d t n 网络中最典型的三种路由算法协议 对于洪泛算法 是最早提出 d t n 的算法 利用的是存储一转发思想 虽然这样会消耗大量的网络资源 从而影响了网络 的生存时间以 但是针对此问