(通信与信息系统专业论文)容断网络中的摆渡路由算法研究.pdf_第1页
(通信与信息系统专业论文)容断网络中的摆渡路由算法研究.pdf_第2页
(通信与信息系统专业论文)容断网络中的摆渡路由算法研究.pdf_第3页
(通信与信息系统专业论文)容断网络中的摆渡路由算法研究.pdf_第4页
(通信与信息系统专业论文)容断网络中的摆渡路由算法研究.pdf_第5页
已阅读5页,还剩50页未读, 继续免费阅读

(通信与信息系统专业论文)容断网络中的摆渡路由算法研究.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

重庆大学硕十学位论文 中文摘要 摘要 容断网络为资源受限网络场景提供了一种通信的基本手段,为不同网络之间 提供了互操作性。容断网络作为一种覆盖型的网络架构,其相关理论还不够成熟, 其中,路由转发机制是容断网络的一个研究热点,也是一个难点。 首先,本文集中探讨了容断网络场景下的消息摆渡路由机制,剖析了现有主 要的几种单摆渡路由机制和多摆渡路由机制;接着,针对这些路由机制给出了自 己对单摆渡路由的改进方案和一种多摆渡路由的设计方案。本文主要工作如下: 给出了一种f i m f n n 算法的改进方案,称之为m o f i m f 。在f i m f 小烈 算法中,当f e n y 节点收到多个d t n 节点的服务消息请求时,f e n y 节点总是选择 距离最近的d t n 节点,与之靠近,进行通信;而在m o f i m f 算法中,f e n y 节点 将会选择通信数据量最大的d t n 节点最为访问对象。并通过仿真实验,证明了改 进后算法的优越性。 给出了一种e z f 算法的改进方案,称之为m o e z f 。针对e z f 路由算法 没有很好地设计f e n y 节点如何从源d t n 节点接收数据的不足,m o e z f 算法做 了进一步的完善:根据面向消息的思想,f e n y 节点选择通信数据量最大的源d t n 节点作为访问对象;根据椭圆转发的思想,f e n y 节点确定相应的摆渡路线,经过 中间的某个d t n 节点,然后访问目的d t n 节点。并通过仿真实验,验证了改进 方案的有效性。 提出了一种简单的多摆渡路由机制,称之为m f m f s 。由于单个f e n y 节点 获得的网络性能有限,并受到现实生活交通枢纽的启发,设计了m f m f s 这种多 f e q 节点路由机制:在网络中引入两种f e n y 节点,两种节点具有不同的缓存容 量和移动速率,各自服务于不同节点。通过仿真实验,证明了m f m f s 算法比f i m 、 e z f 算法等单摆渡路由机制带来了更好的网络性能。 关键词:容断网络,资源受限,单摆渡路由机制,多摆渡路由机制 重庆人学硕士学位论文茎窒塑墨 - _ _ _ - 一一 a b s t r a c t d i s m p t i o nt b l e 舢tn e t 、) 旧r k ( d 7 r n ) p r o v i d e sab 嬲i cc o m m 血c a t i o nm e a i l sf o r c h a l l e n g i n gn 咖o r k j n g锄v 的m e n t ,嬲 w e n觞i n t e r o p e r a b i l 畸b e t w e e nd i f l e r e n t n e t w o f k s a san e wt y p eo fn e r ka r c h i t e c t u r e ,m et l l e o r yo fd t n i sa l s on o te n o u 曲 m a :t u r e d t nr o u t i n gf o r v 旧r d i n gs c h e m ei sar e s e a r c hh o ts p o t ,锄di sa l s od i 伍c u l t f i r s to fa l lt k sa r t i c l ef o c u so nt h em e s s a g ef e r r y i n ga p p r o a c hi 1 1s c e n e so ft l l c d t nn e 咖r k ,锄l a l y s i ss e v e r a lm 旬o rf e n y i l l gr o u _ t cm e c h 越s m ;触e rt h a t ,g i v e sm y o 啪i m p v e i i l e n tp r o 铲锄c o n t r a r yt ot h e s er o u t i n gm e c h a i l i s m s ;f i i l a l l y ,d e s i g n s a s 呻l e 舢l t i n o d ef e r r y i n gr o u t i n ga l g o r i t l l l l l t 1 1 em a i nw o r k s a r ea sf o l l o w s : a n 呻m v e dp r o g r 锄n 锄e dm o f i m f ,w 嬲p r o p o s e d f o rf i m f 删 a l g o r i n l i i l 。u n d e rt l l ea l g o r i t h mo ff i m f 小附,w h e nf e n yn o d er e c e i v e san 啪b e ro f s e i c em e s s a g er e q u e s t 舶md t nn o d e s ,e v e r yt i m e ,m ef e n yn o d e 谢ug ot 0 恤 n e a r e s td t nn o d et oc o m 彻m j c a t i o n ,b u tf o r 廿1 em o f i m fa l g o t h ef e r 巧n o d e 谢nc h o o s e st h ed t nn o d e 谢t 1 1t h el a r g e s td a :t at o 触n s f i e r 嬲t h ev i s i t i n go b j e c t a n d p r o v et h es u p e r i o r i 够o f t h eh p r o v e d 甜g o r i t l l i nt l l r o u g hs i r n u l a t i o ne x p 耐m e n t ani m p r o v e dp r o g r 帅r 姗e dm o e z f ,、v a sp r o p o s e df o re z fa l g o r i t f o r 吐1 ee z fa l g o r i m mn o t 、e uc o n s i d e ri i lm ef i e l do fh o w 呻n o d e t or e c e i v eb u i l d l e 丘o ms o u r c ed t nn o d e ,m o e z fa l g o r 弛mg i v e sai r n p r o v e dw a y :a c c o r d i n gt ot h e t 1 1 i l l l d n go fm e s s a g i l l g - o r i e n t e d ,t h ef e n yn o d e 埘l lc h o o s em es o 眦e d 1 nn o d e 谢t h t h el a r g e s tm e s s a g e st ov i s i t ,觚da c c o r d i n gt ot h ei d e ao fe l l i p t i c a lz o n ef 0 删i n g ,t h e f - c n 、rn o d ew i l ls e l e c tt h ea l li n t e n n e d i a :t ed t n n o d et ov i s i ta 1 1 d l e ng ot od e s t i n a t i o n d t nn o d e 知l dn l r d u 9 1 ls i i 硼1 a t i o ne x p e r i m e n t s ,v e r i 母m ee f i e c t i v e n e s s 0 fm e i i r l p r o v e i n e n tp r o 铲a m as i m p l em u l t i f e 仃i e sp r o g 姗n 锄e dm f m f s w 鹤p r o p o s e d d ut 0as i l l g l e f e r r yn o d eh a v el i m i tn e r kp e r f o m a n c e ,a n ds u 均e c tt 0r e a l - l i f e 仃 m s p o r th u b i i l s p n d ,d c s i g nas i n l p l em u l t i f e r r i e sr o u t i n gs c h e m e :i m o r d u c t 铆ot ) ,p e so ff e r r yn o d e i l ld t n ,m e yh a v e ( 1 i 骶r e n tc a c h ec 印a c 匆a 1 1 dm o b i l 埘r a t i ea n ds e r v i c ei i ld i 位r e l 吐 咖r kn o d e s n 帅u 曲s i m u l a t i o ne x p e r i m e n t sp r o v et l l a tm f m f sr o u t i n ga l g o r i t h 【n h a sb e t t e rn e m o r kp e 墒n i l a i l c et l l 趾f i m f ,e z fa l l g o r i t l l i l l k e yw o r d s :d i s m p t i o nt o l e 啪tn e w o r k ,r e s o u r c e - c o n s 仃a i n e d ,s i n 酉e - f e n y i n gr o u t h l g s c h e m e ,m u l t i f i e r r y i i l gr o u t i n gs c h e m e 学位论文独创性声明 本人声 明所呈交的! 卫 士 学位论文 窒。蒸盟国丝生堕! 里! 继堕魄选纽氢 是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知,除了文中特别加以标注和致谢的地方外,论 文中不包含其他人己经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 学位论文作者签名: 1 f = 级i 导师签名:乃锄夕勿 ? 签字日期: 签字日期:矽唧,够 学位论文使用授权书 本人完全了解重庆大学有关保留、使用学位论文的规定。本人完全同意中 国博士学位论文全文数据库、中国优秀硕士学位论文全文数据库出版章程( 以 下简称“章程”) ,愿意将本人的一士学位论文提 交中国学术期刊( 光盘版) 电子杂志社( a 暇i ) 在中国博士学位论文全文数据 库、中国优秀硕士学位论文全文数据库以及重庆大学博硕学位论文全文数 据库中全文发表。中国博士学位论文全文数据库、中国优秀硕士学位论文 全文数据库可以以电子、网络及其他数字媒体形式公开出版,并同意编入c n 中国知识资源总库,在中国博硕士学位论文评价数据库中使用和在互联 网上传播,同意按“章程”规定享受相关权益和承担相应义务。本人授权重庆大学 可以采用影印、缩印或其他复制手段保存论文,可以公开论文的全部或部分内容。 作者签名: 生:丝l 导师签名: 备注:审核通过的涉密论文不得签署“授权书 ,须填写以下内容: 该论文属于涉密论文,其密级是,涉密期限至 年一月一日。 说明:本声明及授权书! l 逝装订在提交的学位论文最后一页。 重庆大学硕士学位论文2 容断网络概述 l 绪论 1 1 课题背景 膝上电脑( l a p t o p s ) 、个人数字助理( p e r s o r 试d 珥t a la s s is t 锄t ) 、蜂窝式便携无线 电话( c e l l p h o n e ) 等无线终端设备的演进,我们有目共睹,这些设备能够完成 d a y - t o d a y 的任务交互,无线终端技术已经取得了长足进步的同时,用户的移动 变得越来越快速,激发了在新的无线环境中的通信技术的发展。这种新的无线环 境包括:卫星网络、行星与星际通信、军事战术网络,灾难应急以及其他大规模 移动网络。该资源受限网络环境临着一系列的挑战:网络频繁分离,间断性连接 或不连接,长延时,高调度成本、缺少端到端的路径等等。 这些新的挑战激发了人们对这种新的资源受限网络环境更多的研究,但是, 大多数的研究都关注于移动自组网( m 趟忆t s 以o b i l ea dh o cn e t w o r k s ) ,m 舢忆t s 是一种多跳的网络环境,在该网络环境下,网络节点兼有主机和路由的功能,他 们通过维护网络的端到端的路径,相互协作地进行通信。大多数m a n e t s 相关文 献 1 4 主要工作都是研究网络中的路由问题,但是这些文献当中的路由机制,并 不能很好地应用到资源受限网络场景中,因为m 伽姬t s 中的路由机制都是基于端 到端的,而资源受限网络并不能提供可靠的端到端路径。 容断网络( d t n d i s m p t i o nt 0 1 e 删1 tn e t 、o r k ) 网络j 下是在这样的背景下出现的, 它为这种受限场景下的无线通信提供了一种手段。容断网络最早是由k e v i nf a l l 2 0 0 5 年在m i l c o m 会议上为实现异构a d - h o c 网络互连而提出的一种覆盖型网络 架构。d t n 给出了解决受限网络环境和特殊场景下数据传输的基本指导思想 对数据进行存储转发,它也可以满足特殊场合的应用,如军事网络【5 】、深空通信【6 】、 空降网络【7 1 、日常车载环境眇】、环境监测1 们、边远地区的因特网接入【1 1 1 等等。 d t n 采用网络异构技术,路由转发机制作为d t n 网络的关键技术,其好坏关 系到了整个网络的性能,d t n 使用存储转发( s t o r e a n d f o 刑a r d ) 的路由机制,能够 对消息进行长时间缓存,直到传输链路建立后将消息转发出去。但是这种路由机 制更多的是去依靠节点间的链路重新建立,然后将缓存的消息转发下去,这样使 得网络的性能不能达到最佳,后来人们提出了一种的存储转发运载 ( s t o r e - c 哪f o 删) 的路由机制( 即消息摆渡路由机制) ,该机制明显地改善了网络 的性能。 1 2 研究现状 在d t n 网络中,由于节点的快速移动性、节点分布的稀疏性、节点存储容量 4 重庆大学硕士学位论文 2 容断网络概述 的有限性、无线传输距离的有限性、节点电池能源的有限性、拒绝服务攻击等等, 使得网络节点间断性连接或者不连接,节点间的链路呈现为机会性,可预测性, 周期或非周期性,其传统的存储转发路由机制在d t n 这种网络场景下面临着极大 的挑战。 消息摆渡机制不同于传统的存储一转发机制,是一种存储运载一转发机制,它 通过在网络中引入一种特殊的节点( 摆渡节点f e n y 节点) ,专门地为d t n 节点之间 消息传输提供服务。存储转发机制,主要利用网络节点固有的移动性,被动地等 待连接机会的到来,再将消息转发出去。消息摆渡机制不仅要对消息进行存储转 发,而且还有运载操作,它会主动地向目的地节点靠近,然后转发数据。 消息摆渡机制给d t n 这种资源受限的网络场景中的数据通信提供了一个有效 的手段,目前国外的一些学者已致力于容断网络中消息摆渡路由算法研究,并取 得了较为丰硕的成果【1 2 2 0 1 ,但是,现有的摆渡算法更多的是借鉴了现有无线自组 网络中路由算法的基本思想,并没有很好地针对d t n 这种网络的特点,而提出具 有d t n 特色的消息摆渡路由算法,其算法还有一些可以进行改进的地方。 1 3 研究内容 本人在d t n 网络的相关概念和关键技术的基础之上,针对该网络的相关研究 难点和热点,剖析了现有d t n 网络的主要消息摆渡路由算法,并改进和提出了自 己的摆渡路由算法,用c 程序搭建网络仿真环境,在v c 编译环境下,对算法进 行了仿真比较,实验表明:改进和设计的路由算法提高了网络的性能,达到了预 期的目标。 本文的研究内容组织结构如下: 第一章绪论,主要内容包括本课题的研究背景、研究现状、以及研究内容。 第二章容断网络概述,简单概述了d t n 网络的体系架构、关键技术以及网 络的主要特点。 第三章容断网络中的典型摆渡路由算法,主要介绍了现有几种主要单摆渡和 多摆渡路由算法的基本思想,并对它们作了分析和比较。 第四章容断网络单摆渡节点路由机制改进,借助面向消息的基本思想,分别 对f i m f ( f e 订了- “t i a t e dm e s s a g ef e n y i i l g ) 和e z f ( e 1 1 i p t i c a lz o n ef o n ) w d i n g ) 算法进 行了改进,给出了改进的基本思路,并进行了仿真实验。 第五章容断网络多摆渡节点路由机制设计,设计了一种新的多摆渡节点路由 转发机制,给出了算法的原理框图,并与单摆渡节点的路由转发机制进行了仿真 比较。 第六章结论和展望,论文的工作总结和以后的工作展望。 5 重庆大学硕士学位论文 2 容断网络概述 2 容断网络概述 2 1 容断网络的体系结构 在d t n 体系结构中,定义了一个端到端的面向消息的覆盖层叫作b u n d l e 层【2 , 它存在于应用层之下传输层( 也可以是其他层) 之上。b u n d l e 层形成一个网络覆盖 层,使用持久存储来克服网络中断。它包括一个逐跳的可靠交付责任转移和可选 的端到端的确认。为了提供互操作性,它使用一个非常灵活的命名机制( 基于统一 资源识别符) ,可以用一个同样的命名语法来封装不同的命名和寻址模式。它也包 含一个基本的安全模型,用来保护网络设备不被未授权的使用,安全模型是可选 的。b u n d l e 层提供了类似于网关的功能,在各个底层协议之间提供互操作性,并 用持久存储设备提供存储转发的功能。在某种意义上说,d t n 体系结构为互连异 构的使用存储转发消息来克服通信中断的网关或代理提供了一种通用的方法。它 提供了类似电子邮件的服务,但增强了命名,路由和安全能力。图2 1 展示了i n t 锄e t 与d t n 的体系结构的比较。 t r a n s p o r t ( t c p ) n e t w o r k ( i p ) l i n k p h y s i c a l a p p li c a t i o n 易易呖嬲嬲嬲嘲 秘n 魏琏i t r a n s p o r t n e t w o r k l i n k p h y s i c a l ( :o m m o n a c r o s sa l l d t nr e g i o n s s p e c i f i ct o e a c h d t n 增g l o n i n t e m e tl a y e r sd t nl a y e r s 图2 1i n t e m e t 与d t n 体系结构对比 f i g u 鹏2 1i n t e m e t 锄d 【) t na r c l l i t e c t u r ec o m p a r i s o n 从物理实现上来看,d t n 可以看作是在原有底层网络( 如移动a h o c 网络、无 线传感器网络等) 之上的一覆盖层口2 1 ,它由自己特殊的节点( 称之为d t n 节点) 组成, 每个d t n 节点兼备主机和路由器的功能,节点间以束为单位收发数据。相应地, 我们把其底层的网络节点称之为即普通节点( n n 节点) ,该节点不具有d t n 节点的 功能发送和接收束。图2 2 给出了该d t n 网络的一个简单模型。 6 重庆大学硕士学位论文 2 容断网络概述 7 i、f 少 图 、r ? j1 一一,“良、? “ 幅h 嘛 、o 7 ; i 弋以 凸j 、 、一 歹7 7 a1u f d t nn o d e d t nl l n k o r n l a in o d e 一 r n l a i i i n k 图2 2 d t n 网络简单模型 f i 9 2 2as i m p l ee x a m p l eo fd t n n e t w o r k 2 2 容断网络的关键技术 可靠性和保管传输【2 3 矧 b u n d l e 层提供的最基本的服务是无确认的有优先等级的单播消息交付。它也提 供可选的两种加强的交付责任:端到端的确认和保管传输( c u s t o d yt r a i l s 矗砷。希 望实现他们自己的端到端的确认的应用层可以不用b u i l d l e 层的确认。d t n 体系结 构的保管传输的特色只是指定了一个粗粒度的重传能力。发送保管传输需求选项 被设置的b u i l d l e 通常包括在不同的d t n 节点之间移动可靠交付的责任。 对于单播交付,这个过程典型的包括向离最终目的地更近的节点移动消息的一 份拷贝。接收到这些拷贝的节点称之为保管员( c u s t o d i a l l ) 。保管传输允许源节点委 派重传责任和在发送b u n d l e 后相对快速的恢复重传资源。不是所有的d t n 节点 都需要接受保管传输,所以它不是一个真正的逐跳机制。例如有些节点在有足够 存储资源时可以作为保管员,但当在拥塞或低功耗运行时可以选择不提供这种服 务。保管员的存在可以改变d t n 路由执行的方式。在某些情况下,尽快的把一个 消息转移到一个保管员那里是有益的,即使它远离最终目的地。 保管传输不仅提供了一个跟踪需要特别处理的消息的方法和识别参与保管传 输的节点,它还提供了一个加强可靠消息交付的弱的机制。通常,保管传输依赖 于底层的可靠交付协议,当需要保管传输时,b u i l d l e 层提供一个粗粒度的超时和 重传机制和一个保管员到保管员的确认信号机制。当一个节点接收带有保管传输 需求选项的b u l l d l e 时,一个保管传输接收的信号被b u n d l e 层发送到包含在b u l l d l e 头部的当前保管e i d ,当前保管e i d 被更新成接收保管传输的节点的e i d 。当应 用层需要一个消息被保管传输时,这个需求是建议性质的。在某些情况下,一个 7 重庆大学硕十学位论文 2 容断网络概述 b u n d l e 的源可能没有能力提供这种服务,这个b u i l d l e 在获得保管员之前可能要穿 过多个d t n 节点。这个b u n d l e 的当前保管员e i d 被设置成空的端点。 l 掣e 娼 a p p l i c a t i o n b 岫d l e t 啪s p o r t n e m o r l ( l i n _ k p h y s i c a l s o u r c e k e y : p 粥i 蝴l t 咖船g e 、, o c tc l i s t o d yt r a n s f e rc a p a b i l n y 一 c u s t o d y 打锄s f 打o f b 吼d l e e - 一一 图2 3 保管传输示意图 f i g u 托2 3c u s t o d yt m n s f e ri l l u s 仃纰i o n 路由和转发 d t n 体系结构提供了在b u n d l e 层路由和转发的框架。因为d t n 节点可能使 用不止一种底层网络技术互连,一个d t n 网络可以抽象的描述为一个多图。图2 4 中的边通常是时变的,当边的容量变成零时,可以认为他们是断开的。d t n 图中 的边可能有相当大的时延。我们采用在数据被放入网络边的节点来度量时间,边 的容量和延迟表示为时间的函数。例如,在时间t ,一个边有容量c ( t ) 和延迟d ( t ) , 如果在时间t 有b 个比特被放入边,这些比特将在什d ( t ) + ( 1 c ( t ) ) 木b 到达。边可 能在正的和零容量之间变化,可能存在一个时间间隔,在这个间隔内,边的容量 是严格大十零的,为了便于研究,可以把这个时间间隔内的时延和容量简单的认 为是恒定的。这个时间间隔被称之为接通( c o n t a c t ) ,时间间隔和边的容量的乘积定 义为这个接通的容量。如果接通和他们的容量可以被预先知道,智能的路由和转 发决定就可以被做出。为了最佳的利用接通的容量,大的消息可能被分成较小的 可路由单元。当接通的间隔和容量不可精确的预知时,路由计算将会变得非常的 困难。根据接通性能特征的可预知性和是否要采取一些动作来使他们出现,接通 可以分成一下几类: 8 重庆大学硕士学位论文 2 容断网络概述 l a y e 娼 a p p l i c a l i t r 锄s p o n n e t w o i k l i n k p h y s i c a l l a y e 俗 a p p i i c 砒i o n b u n d l e 胁n s p o r t n e t w o t l i n k p h y s i c a l s o u r c e d e s t i n a t i o n j u u i o u j o o : t e pt g p i 【pmi p 坤 ;”考 : i n t e n l e th o s t1 l l t e m e tr o l i t 盯i i l t e m e tr 伽t 盯i l l t 钿e th o s t : p o t d h t i a t p o t dn t i 五厂 一目 p o t c n t i a l 目 p o t en t i a l 目 d e l a vd ea y 一 c t d e l a y ? c t ? d ea y ? t l:p t 军p t 西 t g p n o n 盯c p c t n o n t c p t 螂p o r t t m n p o n i 毒 n o li - i p n o ii i p i p i i 1 1b n e no f k n e t lv o l l 【 : d t nh o s t y i nr 0 u t e rd t ng a t e w a yd t nh o s t l t 二二二二二二二型 r e g i o n1 ( 1 c m pr e g i o n )r e g i 2 ( n o n 1 m pr c g i o n ) k c y :e j p e 幅i 咖f i ts t o m g ec t c 璐t o d y 讹m f 打c 印a b i l 时 图2 41 1 1 t e n l e t 路由和d t n 路由的比较 f i g u 陀2 4i m e m e t 锄dd t n r o u t ec o m p 撕s o n 持久接通:持久接通永远是可用的,没有连接发起的动作来开始一个持久接 通。一个永远在线的i n t e r n e t 接入,如d s l 或电缆调制解调器连接可以看成是持 久接通的例子。 按需接通:按需接通需要某些动作来开启,但直到被结束前,它们都和持久 接通表现的一样。拨号连接就是一个按需接通的例子( 从拨号者的角度来看) 。 间歇的调度接通:调度接通是一个在特定时间开始建立的一个接通,持续特 定的时间。低轨道卫星链路就是一个调度接通的例子。 间歇的机会接通:机会接通不是预定的,而是有些出乎意料。例如,一个非 预定的航空器飞过头顶,通告它现在可用于通信。 间歇的预报接通:预报接通不是基于固定的调度,而是根据以前的观察或其 他信息的历史来预测接通的可能时间。 目前i l 玎f 还没有给出一些标准的路由算法,d t n 的路由算法还处在进一步的 研究当中。 9 重庆大学硕士学位论文 2 容断网络概述 b 岫d l e 层的拥塞和流控制 d t n 的流控制必须基于一些b u i l d l e 层资源的信息在b u n d l e 层被做出。当存储 资源很稀少时,d t n 节点只有很少的自由度来处理这些情况。当b u i l d l e 过期时总 是可以将他们丢弃。当b u i l d l e 没有过期但没有被保管传输时也可能被丢弃。节点 应该避免丢弃已经被保管传输的b u l l d l e 。除了b u i l d l e 层的一些机制外,d t n 节点 也可以从底层协议的流控制获得一些资源利用的好处。目前,b u i l d l e 层具体的拥 塞和流控制机制还在研究当中,i r t f 没有对拥塞和流控制的标准达成一致。 安全性 在一些d t n 中严重的资源稀缺要求某种形式的鉴权和接入控制。未授权的用 户不能轻易的向网络注入通信业务量。许多现存的为低延迟,持续连接环境而设 计的鉴权和接入控制方法可能运行的不是很好。特别的,更新控制列表和撤回信 任状尤其的困难。需要经常接入中央服务器来完成鉴别和授权的方法也没有吸引 力。为了满足这些安全需求,d t n 体系结构采用了一个标准的但是是可选的安全 体系,它使用逐跳和端到端鉴别和完整性机制。采用两种方法的目的是能分别处 理数据转发的接入控制和应用层数据完整性。当鉴权或接入控制检查失败时,d t n 节点尽可能早的丢弃非法通信业务量。具体的d t n 安全协议可参见文献【2 5 】。 2 3 容断网络的主要特点 路径和链路特性方面 高延时,低数据率( h i 曲l a t e n c y ,l o wd a t a & 此) :端到端的延时表示单向传 输的每跳路径的时延总和。每一跳路径延时包括通过该链路的传输时间、处理时 间、传播时间以及排队时间。如果忽略处理时间和排队时间,处理时间和传播时 间是直接受下层媒体影响的。对于受限网络来说,传输率可能是比较小的,延时 是比较大的,而数据率在很大程度上是不对称的。 网络断开:在许多受限网络中,端到端断开比端到端连接更普遍。一般说来, 断开可能是由于错误或其他的原因造成的,由于错误而断开在传统网络中已有很 多的研究,非错误断开频繁地出现在无线场景中,主要是由于移动和低占空比( l o w d u t yc y c l e ) 系统操作引起的。 长排队时间:d t n 网络中,与传输和传播延时相比,排队延时通常占据主导 地位。信息可能必须被存储在路由节点相当长的时间,并且下一跳的路由选择可 能作废,也就是说,如果发现信息转发的更好路由器,消息就应当被传递到新的 下一跳。 网络结构方面 互操作性:在大多数的网络中,网络体系结构主要是由链路和媒体接入控制 l o 重庆大学硕士学位论文 2 容断网络概述 协议组成,基本没有考虑互操作性问题,其原因在于大多数的情况下,链路上几 乎很少有受限的网络中的通信,且在互联网中使用这样的链路还没有成为一个主 要需求这还只是一个研究领域。而d t n 网络就是为实现不同网络的异构而提 出的,它为不同的低层网络之间提供互操作性。 安全方面:d t n 体系结构采用了一个标准的但是是可选的安全体系,它使用 逐跳和端到端鉴别和完整性机制。 端系统特性方面 有限的寿命( l i n l i t e dl o n g e v i 劬:在一些受限网络( 如无线传感器网、军事网络 和紧急反应网络等) 中,端节点可能被放置在敌对的环境或者恶劣环境中。在这种 情况下,由于环境恶劣或者能量消耗,设计者可能并不期望网络节点有较长寿命。 如果这样的网络长期断开,那么一个特殊信息传输往返时间或单位时间都有可能 超过发送节点的寿命。显然,在这种情况下,不能使用通常的反馈确认机制去检 验信息递送,因此可靠传送的责任应该被委派给一些其他的设施。 低占空比操作( l o wd u _ t ) rc y c l eo p e r a t i o n ) :当节点被仿真在没有供电系统的区 域是,他们通常使用电池( 也可能使用太阳能电池) 。即使可以充电,这些系统通常 也通过限制他们的占空比去努力节约能量。在一些情况下( 例如电池供电的传感 器) ,为了实现整个网络的长寿命,占空比维持在1 。这样的设备定期收集数据, 并以移动的速率( 通常很小) 进行数据汇报。对这样的系统,通常预先规划正常的运 行时间,断开影响路由协议的操作。 有限的资源( l i m i t e dr e s o u r c e ) :受限网络中使用了有限的存储和处理能力的节 点,例如,一个存储能力有限的传感器被禁止收集更多的数据,因为它的存储正 在被传输中的数据全部使用。除次之外,端节点还需要至少保持r 1 盯时间的重传 缓存,在这期间,节点执行能量降级模式操作,这使得系统非常复杂,特别是在 收到其他异步信息或者监测到一些突发事件发生尤其重要。 针对如上的特性,d t n 结构旨在提供各种网络之间的互操作性。从网络管理 的角度看,d t n 网络里的通信属于非交互式通信,适合采用长度适中的报文交换 ( 在d t n 网络中被称为b u i l d l e ) ,而不适合传统网络里的数据包交换。因为使用报 文,网络可以事先知道传输数据的大小和性能要求,便于进行路径选择和时序安 排。为了实现不同网络之间的互操作性,需要在连接的节点布置特殊的d t n 网关。 重庆大学硕+ 学位论文3 容断网络中的典型摆渡路由算法 3 容断网络中的典型摆渡路由算法 本章首先对d t n 网络中路由算法作了归类,接着探讨了d t n 网络中的现有 主要的单摆渡和多摆渡的路由机制,对它们进行了分析与比较。 3 1 容断网络中的路由算法分类 f m l 提出d t n 这种新的网络架构,采用了异步消息传输机制,主要用来为受 限网络之间提供互操作性,如传感器网络和星际网络。在d t n 网络中,同样具有 两种路由机制:被动路由机制和主动路由机制。在被动路由机制下,主要利用网 络中节点或则设备的固有移动来帮助完成消息传输;在主动路由机制下,网络中 的节点将会主动或者有意识地向目的通信节点靠近,然后完成消息传输。 在d t n 主动路由机制下,根据网络中是否采用摆渡( f e 训节点,我们可以将 d t n 主动路由算法分为两类:d t n 摆渡路由机制和d t n 普通路由机制;根据d t n 网络的覆盖范围,我们可以将摆渡路由算法分为两类:单区域摆渡路由机制和多 区域摆渡路由机制。 再次,在d t n 摆渡路由机制下,根据摆渡节点的数目,我们又可以将算法分 为两类:单摆渡路由机制和多摆渡路由机制。 3 2 典型摆渡路由算法分析比较 在d t n 摆渡路由机制下,根据节点在网络中扮演的角色,我们将网络中的节 点分为两个类型,即d t n 节点和f e n y 节点,d t n 节点主要执行束( b u i l d l e ,一种 数据报文) 的接收和发送,f e n y 节点主要为d t n 节点存储运载一转发束,作为d t n 节点之间束传输的媒介。 3 2 1 算法基本思想 m f s m f s ( m e s s a g ef e 玎了i n gs c h e m e ) 2 6 】是w e i 唧iz h a o 等人提出的单一摆渡节点的 路由算法,它首次将消息摆渡机制引入稀疏a d h o c 网络,为不连接的网络节点之 间提供数据通信,其基本思想:在网络环境中引入摆渡节点移动的非任意性,并 利用这种非任意性来协助数据传输。在m f s 中,网络节点分为两大类,即f e n y 节点和一般性节点,f e n y 节点在预先确定的轨迹上来回移动,为不连接的一般性 节点提供数据传输。 该算法主要研究了静态一般性节点稀疏分布网络场景下的数据通信问题,在 这种节点静态分布的场景下引入了单个摆渡节点,作为一般性节点之间数据传输 1 2 重庆大学硕士学位论文 3 容断网络中的典型摆渡路由算法 的中介,并且摆渡节点沿着预先确定的路径进行移动并为一般性节点提供数据传 输服务。 ( 多n i m f f i m f n i m 伊i ( n o d e 一“t i a t e dm e s s a g ef e r r ) r i n g f e n y - “t i a 蜘m e s s a g e f e n y i l l g ) 【2 7 】是w r e n m iz h a o 等人在同一篇文章中提出的两种消息摆渡机制。其共同 基本思想:在网络环境中引入一特殊节点( f e y 节点) 移动的非任意性,并利用这 种非任意性协助数据传输。在n i m f 中,f e n y 节点沿着预先确定的路径移动,并 周期广播自己的地理位置信息,一般性节点在获得f e n y 节点的地理信息后,周期 地调整自己的运动轨迹,与f e q 节点相遇,完成数据交互传输;在f i 中,f e n y 节点为实现和一般性节点之间的通信,采用主动的移动形式,另外一般性节点和 f l e n y 节点都封装有长距离无线电设备。f e y 节点最初在一条默认的轨迹上移动, 通过长距离无线电周期地广播自己的位置信息;当一个源节点( 一般性节点) 发现 f e n y 节点的靠近时,如果与f e n y 节点有数据要传输时,它也通过长距离无线电 向f e n y 节点发送一个服务请求消息( s i t m s e r v i c er e q u e s tm e s s a g e ) ,该消息包含 有源节点的地理位置信息,收到该请求消息后,f e n y 节点调整自己的移动轨迹, 向源节点靠近,直到进入彼此的通信范围;接着彼此通过短距离无线电完成数据 交换;通信完毕后,f e n y 节点又重新回到自己的默认轨迹上。 该两种路由算法,主要研究了一般性节点移动情况的消息摆渡机制,在该网 络场景下引入了单个f e r r y 节点,且f e n y 节点的资源不受约束,而一般性节点的 电池能源、存储容量、计算能力有限。 e z f e z f ( e l l i p t i c a lz o n ef o r w a r d i n g ) 【2 8 】是由m o o ic h o oc h u a l l 等人提出的一种路由 算法,在这种算法中,摆渡节点维护有两个列表:一是摆渡节点需要访问的目的 地节点列表l 1 ;一是摆渡节点已经接收的预留列表l 2 ( 如需要访问的带有消息的 d t n 节点列表) 。并且,列表l 1 中的节点比l 2 中的节点的服务优先级高。当d t n 节点需要摆渡服务时,它通过长距离无线电发送摆渡服务请求。以图3 1 为例,我 们简单的介绍该摆渡路由算法的基本思想: 假定摆渡节点位于x 位置,目的d t n 节点位于y j 位置,摆渡节点以x 和 y :j 为椭圆的两个焦点,并计算消息从当前摆渡节点位置发送到目的节点y j 位置的 延迟要求鼬( 鼬= a b ) 。以砒为椭圆的长半轴长,创建椭圆。摆渡节点在到达y :j 节点过程中,仅仅访问满足条件x z + z y i m 的中间z 节点。当有多个这样的z 节点存在时,摆渡节点将选择x z + z y j 最小的z 节点。若找不到满足条件x z + z 的中间z 节点,摆渡节点将直接访问目的节点y j 。在数据转发过程中,摆渡节点 经常检查缓存中或者将要接收的消息列表中的过期消息,摆渡节点仅仅转发那些 1 3 重庆大学硕士学位论文3 容断网络中的典型摆渡路由算法 在生命周期中的消息。 图3 1 椭圆转发示意图 f i g u r e3 1e l l i p t i c a lz 0 n ef o 九) l r a r d i n g b 这种算法减少了消息的整体传输时延,但是降低了消息传输的传输比率。同 时该算法还有一个较大的缺陷:l 2 列表中d t n 节点缓存的需要被服务的紧急消息 可能比l 2 列表中d t n 节点缓存的紧急消息具有更短的生存时间,则该算法将有 可能丢失一些更需要服务的紧急消息。 ( df k l a s f k l a s ( f i x e dk - l o o k a h e a ds c h e m e ) 【2 9 】是由m o o ic h o oc h u a h 等人提出的一种 路由算法,该算法对e z f 做了一些改进。在该算法中,摆渡节点维护一张紧急消 息的列表l ( 包括了已经接收到的紧急消息和需要接收的紧急消息) ,并依据消息的 生存时间( 最后期限) ,对其排序存放,列表中的每则消息包含了一些与本消息相关 的信息( 如消息是否被摆渡节点接收、消息的生存时间、消息的源节点和目的地节 点) ;同时,摆渡节点还维护一个将进行访问的节点列表s 。摆渡节点浏览l 链表, 并以此为依据,判断是否向s 插入目的节点或者源节点。当s 中的节点数达到门 限值k 时,则停止插入,摆渡节点将漫游于该k 个节点之间,直到该k 个节点全 部被访问。接着,更新s 列表。当网络中有紧急消息和普通消息这两种服务级别 的业务时,f k l a s 可以维护两个列表l l 和l 2 ,分别包含紧急消息和普通消息以 及两种消息对应的相关信息,l 1 列表中的k 个紧急消息会被首先调度,当l 1 中 的紧急消息小于k 时,将用普通消息进行填充,满足消息数目之和为k ,然后进 行调度。 该摆渡路由算法能够很好地解决紧急消息的传输时延问题,但是降低了消息 的平均延时。 d l a s d l a s ( d y n a i n i ck l o o k a l l e a ds c h e m e ) 是m o o ic h o oc h u a l l 等人在文献【2 9 】中 提出的对f k l a s 的一种改进的路由算法。在d l a s 算法中,摆渡节点每次循环访 1 4 重庆大学硕士学位

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论