（通信与信息系统专业论文）基于社会关系的容滞网络路由算法研究.pdf

摘要 摘要 i i i iiii i i iii i iii i1 1i il y 2114 9 4 7 随着移动无线通信技术的高速发展，通信网络环境变得越来越复杂，通信网 络所面临的挑战也越来越多。比如深空通信网络、无线传感网络、野生动物追寻 网络、军事网络、应急通信网络等等。这些通信网络环境都面临着通信延迟大， 通信链路时断时续等问题的挑战。英特网体系结构和其他现有的网络体系结构不 能很好的解决面临这些挑战时的通信问题。学者提出了一种新型的网络技术 容滞网络( d t n ：d e l a y d i s r u p t i o nt o l e r a n tn e t w o r k s ) 来应对这些挑战。 d t n 在传统通信网络模型上加入聚束层，使用存储一携带一转发机制进行 报文传递。d t n 的研究大多集中在路由算法和应用上面。路由算法分成多拷贝 路由算法和单拷贝路由算法两种，常用的是多拷贝路由算法。蔓延路由算法采用 洪泛机制，可以取得较高的报文递交率和较低的延迟，但是所带来的网络开销比 较大。散发等待路由算法对网络中的报文拷贝数目进行了限制，减少了网络开销， 但是盲目选择报文拷贝的递交对象，浪费了网络资源。概率路由在报文拷贝的递 交对象上有所选择，但是没有考虑到网络中节点之间所具有的社会关系。本文考 虑了节点之间所具有的社会关系，研究基于社会关系的容滞网络路由算法，仿真 表明算法在报文递交率和延迟上都有所改进。 本文的主要方法和工作如下： ( 1 ) 对现有的多拷贝路由算法进行研究和分析，对他们的不足和优点进行了分 析。阐述了这些路由算法所适用的场景以及对网络环境的影响。 ( 2 ) 由人们手持设备和车载设备组成的多区域d t n ，传统的路由算法没有考虑 到网络中节点之间的社会关系。本文使用节点之间的社会亲密度q 和节点 的社会活跃度来描述节点之间的社会关系，把报文传递分为区域内和区 域间两个阶段。在区域间将报文递交给社会活跃度值高的节点，有利于 递交到目的节点所在的区域；在区域内则将报文递交给社会亲密度q 大的 节点，这样有更大的几率递交到目的节点。 ( 3 ) 使用t h eo n e 对本文所研究的路由算法与蔓延路由算法、概率路由算法以 及散发等待算法进行分析和比较。 摘要 关键字：容滞网络，社会关系，路由算法。 i i a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fm o b i l ew i r e l e s sc o m m u n i c a t i o nt e c h n o l o g y , c o m m u n i c a t i o nn e t w o r k sb e c o m ev e r yc o m p l e xa n dc o m m u n i c a t i o nc h a l l e n g e sa r e a l s oi n c r e a s e d ，s u c ha si p n ，w s n ，e m e r g e n c yc o m m u n i c a t i o n sn e t w o r k ，e t c t h e s e c o m m u n i c a t i o nn e t w o r k sa r ef a c i n gs o m ep r o b l e m ss u c ha sv e r yl o n gd e l a y , t h e i n t e r m i t t e n tc o m m u n i c a t i o nl i n ka n ds oo n i n t e r a c ta n do t h e re x i s t i n gn e t w o r k p r o t o c o l sc a n n o ts o l v et h ec o m m u n i c a t i o np r o b l e m sw h e nf a c i n gt h e s ec h a l l e n g e s r e s e a r c h e r sh a v ep r o p o s e dan e wt y p eo fn e t w o r kt e c h n o l o g yt oa d d r e s st h e s e c h a l l e n g e s b ya d d i n gt h eb u n d l el a y e ri nt h et r a d i t i o n a lc o m m u n i c a t i o nn e t w o r km o d e l ， d t nu s e st h es t o r a g e - c a r r y f o r w a r dm e c h a n i s mf o rm e s s a g et r a n s m i s s i o n r e s e a r c hi sf o c u s e do nr o u t i n ga l g o r i t h m sa n da p p l i c a t i o n s r o u t i n ga l g o r i t h m sa r e d i v i d e di n t om u l t i - c o p yr o u t i n ga l g o r i t h ma n ds i n g l e - c o p yr o u t i n ga l g o r i t h m s m u l t i c o p yr o u t i n ga l g o r i t h mi su s e di nm o s tc a s e s p a ya n dw a i tr o u t i n gl i m i t st h e n u m b e ro fm e s s a g ei nt h en e t w o r k ，a n dr e d u c e st h eo v e r h e a do fn e t w o r k ，b u ti tw a s t e s n e t w o r kr e s o u r c e sd u et od e l i v e r i n gm e s s a g eb l i n d l y ，w a s t i n gp r o b a b i l i s t i cr o u t i n g s e l e c t st h ea p p r o p r i a t en o d et of o r w a r dm e s s a g e ，w i t h o u tt a k i n gi n t oa c c o u n tt h e s o c i a lr e l a t i o n sa m o n gt h en o d e si nt h en e t w o r k t h i sa r t i c l ep r o p o s e sar o u t i n g a p p r o a c hb a s e do nt h es o c i a lr e l a t i o n s h i p s i ti si n d i c a t e db y t h es i m u l a t i o nr e s u l t st h a t t h i sm e t h o df e a t u r e sh i g hd e l i v e r yr a t i oa n dl o wd e l a yr a t ec o m p a r e dw i t ht h ee x i s t i n g r o u t i n ga l g o r i t h m s t h em a i nw o r ko ft h i sp a p e ri sa sf o l l o w s ( 1 ) t h ee x i s t i n gr o u t i n gp r o t o c o l s a n da l g o r i t h m si nd e l a yt o l e r a n tn e t w o r ka r e s t u d i e da n da n a l y z e d t h ei m p l e m e n t a t i o n sa n da p p l i c a t i o ns c e n a r i o so fe a c h p r o t o c o la r ed i s c u s s e d t h ea d v e r s e l ye f f e c to nn e t w o r kp e r f o r m a n c eu n d e rt h e c u r r e n ts i t u a t i o ni ss h o w n ( 2 ) t h em u l t i - z o n ed t nb yt h ep e o p l eo fh a n d h e l da n dv e h i c l ee q u i p m e n t ，t h e t r a d i t i o n a ld t n r o u t i n ga l g o r i t h m sd o e sn o tt a k et h es o c i a lr e l a t i o n sa m o n gt h e i i i a b s t r a c t n o d e si nt h en e t w o r ki n t oa c c o u n t t h i sa r t i c l ed e s c r i b e st h es o c i a lr e l a t i o n s b 咖e e nt h en o d e s b a s e do nn o d e s s o c i a lr e l a t i o n s h i p sd e s c r i b e db yu s i n g s o c i a l a c t i v i t vv a l u eo fna n ds o c i a lc l o s e n e s sv a l u eo fq m e s s a g ef o r w a r d i n gi s d i v i d e di n t ot w os t a g e s ，w h i c hi si n t r a r e g i o n a lf o r w a r d i n ga n di n t e r - r e g i o n a l f o r w a r d i n g m e s s a g ei sf o r w a r d e dt on o d eo fh i g h e rn v a l u ei ni n t e r - r e g i o n a l m o d e ，w h i c hi se a s yt or e a c ht h ed e s t i n a t i o nn o d e m e s s a g ei sf o r w a r d e dt on o d e o fh i g h e rqi nt h ei n t r a - r e g i o n a lm o d e ，w h i c ht h e r ei sag r e a t e rc h a n c et or e a c h t h ed e s t i n a t i o nn o d e ( 3 ) t h ed t nm u t i n gp r o t o c o ls i m u l a t i o ne n v i r o n m e n t i sb u i l ti nt h eo n es i m u l a t i o n p l a t f o r mt oc o m p a r e a n dt h ei m p r o v e dp r o t o c o lt ot h ee x i s t i n gp r o t o c o l s k e y w o r d s ：d e l a yt o l e r a n tn e t w o r k ；s o c i a lr e l a t i o n s h i p s ；r o u t i n g i v 第一章绪论 1 1 d t n 网络概述 第一章绪论 1 1 1 现代通信网络所面临的挑战 随着科学技术的发展，通信所面临的环境变的越来越复杂，越来越具有挑战 性。例如深空航天器与地面站点的通信【1 1 ，表现出存在路径损失、巨大的时延和 通信中断等问题。移动无线通信技术的发展，各种手持设备和车载通信设备的普 及使得人们可以随时随地的进行通信。但当有特殊的紧急情况发生时，例如地震、 海啸、洪水、飓风等自然灾害，以及军事或恐怖袭击行动，可能使现有的基站、 光纤等通信设施遭到破坏，通信节点失去了稳定的连接，给救援、调度和信息交 流带来挑战。下面介绍一种新的网络体系结构，是专家为了应对这些挑战所提出 的。 1 1 2d t n 的兴起，发展和应用 在2 0 0 2 年的i c t r 会议上，k f a l l 等科学家第一次将容滞网络( d t n ：d e l a y t o l e r a n tn e t w o r k s ) 的概念【2 】提出，并建立了体系结构。国内外越来越多的研究 者开始关注d t n ，目前有三个容滞网络的研究组织。 1 ) 最主要的互联网研究任务组为d t n r g 研究纠3 1 。该组织发布了两个最主要 的协议：链路传输协议l t p 4 1 和聚束协议b p 5 1 ，并且将其提交为r f c 。 2 ) i p n 特别兴趣组：于1 9 9 8 年建立的星际互联网i p n 组织 6 1 ，其中包括v i n tc e r f 和n a s a 的喷气推进实验室j p l ，日后更名。 3 ) 最后是美利坚合众国国家防御高级研究局( d a r p a ) 7 1 。 基于社会关系的容滞网络路由算法研究 i 一一一一一一一一一一一一一1 i p n p r o j e c t ： 一 一 c o n t r i b u t i o n st o e x p e r i m e n t a lw o r k 0 f d t n r g d a r p a n a s a c o o p e r a t i v ew o r k c o r er e s e a r c h 图1 1 容滞网络研究组的相互关系 下面介绍下d t n 网络的实际应用。 ( 1 ) 星际网络 星际网络即深空航天器和地面站点之间构成的通信网络。为了和地面的因特 网实现端到端的通信，完善空间探测服务，n a s a 将d t n 技术应用于星际网络。 2 0 1 1 年1 2 月，星际互联网【8 】项目测试已获得初步成功。 图1 2 星际网络模型 ( 2 ) 传感器网络 随着无线传感网络的发展，其使用的环境变得越来越复杂。网络中的节点通 常受到以下几个方面的约束：存储空间、电池损耗、计算能力等等，并且由于节 点本身的移动性和节点密度会导致的节点之间连接的间歇性。为了应对这些情况 研究者提出了延迟容忍移动传感器网络( d t m s n 【9 】) 。传统的d t m s n 中包括两种 节点：一种是移动的传感器节点；一种是汇聚节点。两种节点相互协作完成任务， 第一章绪论 下面是简单的d t m s n 网络模型。 薰菡 磐溱嘲 图1 3 简单的d t m s n 模型 ( 3 ) 车辆网络 最典型的车辆网络( v a n e t ) 是在城市中利用车辆作为信息载体，相互之 间传递信息的网络。通常这些信息包括一些基本的路面信息和紧急的突发情况 【l o 】。v a n e t 具有网络中节点移动速度快，网络拓扑结构不停变化，移动轨迹固 定在道路上等特点。 在偏远地区，因为通信基础设施比较差，有线和无线的网络服务还没有普及。 在印度和柬埔寨的一些地方，d a k n e t 1 1 1 已经架设并且使用。这个网络是通过公 交车载设备m a p ( m o b i l ea c c e s sp o i n t ) 和k i o s k 设备以及村民的手持设备之间 交换数据来完成通信。还有一个与之类似的m o t o p o s t 网络。 基于社会关系的容滞网络路由算法研究 ( 4 ) 野生动物追踪观察网络 相比起静态的观察网络，基于d t n 技术的动态观察网络可以更准确地观察到 动物的行动路线和相互之间的社交行为。比较著名的几个应用例子是观察斑马的 z e b r a n e t 【12 1 ，他是由普利斯顿大学研究完成的；以及观察鲸鱼的s w i m ，其为一 个水下的d t n 网络。在加拿大的安大略湖附近，科学家们也利用无线传感网络 和d t n 技术来监测白尾鹿的行为。使用了很少的传感器节点，却取得了很好的 效果【1 3 】。 ( 5 ) 军事和应急通信网络 移动无线通信技术的发展，各种手持设备和车载通信设备的普及使得人们可 以随时随地的进行通信。但当有紧急情况发生时，例如地震、海啸、洪水、飓风 等自然灾害，以及军事或恐怖袭击行动，可能使现有的基站、光纤等通信设施遭 到破坏，通信节点失去了稳定的连接，给救援，调度和信息交流带来挑战。我们 就基于d t n 技术利用人们手中各种手持设备和可以工作的基础设施组成一个应 急网络来应对这种挑战。美国军方已采用d t n 技术来确保偏远或者基础设施被 破坏的地区通信保持畅通【1 4 1 。 1 1 3d t n 的特点 d t n 与普通的分组网络不同，在链路特性方面和终端特性方面具有很多特 殊的地方。 ( 1 ) 链路特性方面 很大且可变的延迟：端到端的延迟是由传播延迟和可变的排队延迟组成。在 d t n 中，排队延迟占总的延迟中比重是最大的。这是因为d t n 采用的是存储一 携带一转发机制，报文在网络中传递时，到达中继节点，在没有遇到可靠的下一 跳节点时，就缓存在当前节点处。可靠的下一跳节点出现的时间也许会很长，可 能是以天为周期。等待时间以报文自身的生命周期完结为终点，当到达这个终点 时，节点会在缓存中将这个报文删除。 连接间歇性：除了很大且可变的延迟之外，由于网络中节点的移动和低占空 比造成网络频繁中断。目的节点和源节点之间没有可靠的连接，网络在大部分时 4 第一章绪论 间里是断开的。 低而且不对称的数据率：由于连接的问隙性，导致数据率也是不对称的，并 且很低，同时可能具有很高的误码率。 ( 2 ) 终端特性 有限资源：在d t n 中，由于采用的是存储一携带一转发机制，所以对节点 的存储能力有着非常高的要求。但是网络中节点的存储空间往往非常有限，由于 资源受到限制，在通信繁忙的节点处容易产生报文拥塞，导致很多报文在没有送 达则被丢弃。此外，网络中节点的计算能力也是不一样的，很多节点执行复杂算 法的时间很长，造成报文递交的高延迟。 有限节点寿命：d t n 的网络环境往往很恶劣，节点的工作时间变得非常的 有限，网络中的节点随时都可能因为环境原因而停止工作。 低占空比：因为节点能源有限，网络资源有限，节点的计算能力有限，在这 种情况下，必须考虑降低节点的能量消耗和使用时间，以延长节点的使用寿命。 通常采用限制节点的占空比来达到这个目的。 另外，d t n 中的存储一携带一转发机制不同于传统分组网络，传统分组网 络使用的是存储一转发机制。d t n 中的存储一携带一转发机制有个重要的携带 过程，即在节点处要对下一跳节点进行选择，通过计算对路由表重新更新，而不 是按照路由表进行转发。这样报文在节点处的缓存时间相对于传统的分组网络也 比较长。 1 1 4d t n 的模型结构 d t n 本质上是一种覆盖网络，即是一种位于多种区域网络之上的覆盖网【l 5 1 ， 这里的区域网络当然也包括因特网。因为d t n 采用的是特殊的存储一携带一转 发机制，它的网络模型结构与因特网有差别。 在这些网络模型中，下一层都向上一层提供服务，这些服务是依靠层与层之 间接v 1 来提供。下面首先来介绍t c p i p 协议模型1 1 6 1 和o s i 协议模型【1 7 1 。 ( 1 ) o s i 参考模型和t c p i p 参考模型 o s i 协议模型的制定者希望所有的国家都使用o s i 协议模型来构建网络，做 基丁社会关系的容滞网络路由算法研究 到全世界网络的互联。因此他们在一份国际标准化组织提案的基础上，制定了 o s i 协议模型，并在1 9 9 5 年进行了修订。但是o s i 在构建实际网络上却遇到了 困难。 t c p i p 协议模型与o s i 协议模型不同。它是对已经使用的网络体系结构的 一个描述。最初是由c e r f 和k a h n 在1 9 7 4 年定义，实用性远远大于o s i 协议模 型。下面是对o s i 与t c p i p 参考模型结构的比较 应用层 表示层 会话层 传输层 网络层 数据链路层 物理层 应用层 传输层 互联网层 网络接口层 o s i 参考模型t c p f l p 参考模型 图1 4o s i 与t c p i p 参考模型 ( 2 ) d t n 模型结构 d t n 的网络环境具有很大的特殊性，为了应对这种复杂的网络环境，采用 了存储一携带一转发机制，传统的t c p i p 模型无法描述d t n ，所以d t n 使用 了不同的网络模型。 因为d t n 是一种覆盖层的网络，所以在传统网络模型的传输层上加入一种 新的协议层聚束层即b u n d l e 层【1 8 , 1 9 】，通过这种特殊的网络结构来实现在复 杂的d t n 网络环境中的通信。存储一携带一转发机制也是在聚束层上实现的。 d t n 模型结构【2 0 1 在后面的图1 5 中会详细的列出。 6 第一章绪论 传统网络协议层 传输层 网络层 数据链路层 物理层 d t n 协议层 图1 5d t n 模型结构与传统协议层的比较 下面来具体描述下聚束层。 聚束层 图1 6d t n 不同区域异构网络之间的通信 如上图1 6 所示，聚束层的作用是整合区域间的各种不同的协议，在聚束层 中传递聚束，依靠这种机制实现在多个特定区域中的报文传输。在聚束层之下使 用最合适的协议进行通信。 聚束是由底层的报文封装的，由三部分组成： ( 1 ) 聚束头字段，能够被聚束层识别； ( 2 ) 源节点应用层的用户数据； ( 3 ) 源节点应用层的控制信息，用于描述对报文处理、存储及丢弃等功能。 基丁社会关系的容滞网络路由算法研究 应用层匿 二二二二二二二二二二二二二二二二二二二 、j t 堂蔓丝型! 主垒竺竖旦垫堡 f b u n d i e 层罂三三三三主三 、毡：j 曼竺2 垡! 宝签丕：、 传输层匡鎏鋈翌二二二二二二二重 二二二二二二二 蚕二二 仁j 盟塑- 一套、 、 网络层匡耋銮鋈二二二二二二二 虽量 二二二二二二l 塞三二二 1；=：!：2l!li：lgj、：i i 、 、 链路层匡薹薹蚕酒鋈 二二二二二二二重薹重互二二二二二二二重茎重i 二 仁巡l 一 i - 物理层 二二二二二二二二二二二二二二二二二二二二二二二二二二二二二 t些壁鎏 目i n t e m e t 头标 困 d t n 头标 口 用户数据 图1 7d t n 各协议层的数据封装 聚束也可以使用分块的方式增加递交的灵活性，并可以在目的节点处进行重 组，如图1 7 所示的是d t n 数据的封装。 1 2 论文的选题和意义 随着无线移动通信的发展，人们的通信环境和通信设备也有着大幅度地改 变，通信环境所面对的挑战也越来越多。比如传统的通信网络在面对雪灾、火灾、 军事打击和恐怖袭击时，会因为基础设施被摧毁而丧失通信能力。在观察野生动 物时，所使用的传感器节点分布在各处，并且有些节点在不停的移动，网络的拓 扑结构就随着时间发生变化，常用的路由算法无法完成报文递交，就无法实现信 息的汇聚和传递。在基础设施比较薄弱的农村山区，无法达到无线网络的覆盖， 就无法实现通信。等等以上所说的问题，都可以归结为网络中通信延迟比较大以 及通信链路不断发生变化。为了应对这些挑战，国际上提出了d t n 这种新兴的 r 第一章绪论 网络协议模型。 d t n 的研究大多集中在路由算法【2 1 2 3 1 和应用上面。一些常用的路由算法有 蔓延路由，概率路由，散发等待路由等等。人群网络便是一种特殊的多区域d t n ， 网络中的节点大多是手持设备和车载设备。这些节点之间具有特殊的社会关系， 有些节点之问联系紧密，有些节点通信的范围比较广。这些节点和他们常联系的 节点又自主的组成了一个个不同的区域。本文研究的基于社会关系的容滞网络路 由算法把报文的传递分成两个阶段：区域内传递阶段和区域问传递阶段，充分利 用网络中节点之间的社会关系制定转发规则。从仿真结果看，在开销可以容忍的 情况下，提高了报文递交率和降低递交延迟。 1 3 本文的主要工作和结构 第一章，主要介绍d t n 网络的发展和应用，介绍了聚束层和聚束的结构， 最后给出本文的选题意义。 第二章，主要研究分析了现有的d t n 路由算法，这些算法有单拷贝路由和 多拷贝路由两种类型。其中详细地介绍了直接递交路由，首次连接路由，蔓延路 由，概率路由，散发等待路由，并分析了这些路由算法适用的网络环境和对网络 环境造成的影响。 第三章，主要介绍了本文研究的基于社会关系的容滞网络路由算法，首先介 绍了网络节点大多是由手持设备和车载设备组成的人群网络，这是一种特殊的多 区域d t n 网络；然后介绍了转发规则，最后给出节点之间的亲密度和社会活跃 度的计算和更新方法。 第四章，前面部分重点叙述d t n 网络仿真软件t h eo n e ，在后面将文本提 出的路由算法进行了仿真分析，并和现有的算法进行比较。 第五章，描述了本文的工作情况。 1 4 本章小结 本章主要介绍了d t n 的一些基本的特性。下面将详细介绍常用的几种d t n 路由协议算法，并分析它们的优势和不足。 9 第二章路由算法介绍 2 1 引言 第二章路由算法介绍 一般的分组交换网络使用的模式是存储一转发模式，通过上一章内容我们得 知，d t n 的网络环境更为复杂，具有特殊性。在d t n 中报文将会被暂时缓存， 而不是像普通的存储转发模式立刻递交给下一跳；而是携带报文一段时间，等 待合适的下一跳出现，直到遇到合适的下一跳才会把报文转发出去。d t n 的路 由的关键就在于会有一个等待选择合适中继节点的过程，以应对复杂特殊的 d t n 通信环境。路由算法分为单拷贝路由和多拷贝路由。 2 2 单拷贝的路由模式 2 2 1 直接递交路由算法 ( 1 ) 基本思想 直接递交路由算法2 4 1 ( d i r e c td e l i v e r y ) 的路由规则非常简单：把报文递交 给目的节点，其他节点都不考虑。 ( a ) t l 时刻 7 、 亩( t d ) ( b ) t 2 时刻 图2 1 直接递交路由示意图 如上图2 1 ( a ) 所示，报文的目的节点就是图上的节点d 。随着网络中各个节 点位置的变化，在开始时刻，节点s 遇到了节点b 和节点c ，但是这两个节点 都不是目的节点d ，所以节点s 保留报文，不进行递交。如图2 1 ( b ) 所示，随着 网络中各个节点的位置变化，在此后的下一个时刻，节点s 遇到了节点a 和目 的节点d ，源节点s 将报文递交给目的节点d 【3 5 1 。 ( 2 ) 协议的优缺点 1 0 基于社会关系的容滞网络路由算法研究 优点：直接递交路由对网络环境依赖比较小，造成的影响也很少。 缺点：直接递交路由协议，使用简单的单拷贝路由机制，对遇到的中继节点 不进行转发，因此报文的递交率较低，延迟很大。现实中网络环境很少可以使用。 2 2 2 首次连接路由算法 ( 1 ) 基本思想 首次连接( f i r s tc o n t a c t ) 路由算法的路由规则：将报文递交给遇到的节点， 无论该节点是什么节点。 宙衢 n ( b ) 、 食 乡 、c i ，一 一一。 一 id ： ( a ) t l 时刻 ( b ) t 2 时刻 图2 2 首次连接路由示意图 如上图2 2 ( a ) 所示，报文的目的节点就是节点d 。随着网络中各个节点的位 置的变化，初始时刻，节点s 遇到了节点b ，那么它将存储在自身缓存中的报 文递交给节点b ，节点b 将此报文存储在其缓存中，携带报文在网络中移动，节 点s 对于该报文的递交活动已经完成。随着网络中的各个节点位置的变化，在后 面的时刻中，报文递交给任何遇到的节点，报文在网络中被转发直到报文最终被 递交到目的节点d 。即节点携带报文在网络中移动，遇到其他节点就递交报文， 此后该节点的报文递交任务已经完成，再遇到其他节点不需要递交报文。 ( 2 ) 协议的优缺点 优点：首次连接路由对网络资源依赖较小，没有进行复杂的计算。因为利用 了中继节点进行递交，比直接递交路由协议效率高【3 5 1 。 缺点：没有对遇到的节点进行评价和比较，盲目传递，因此报文到达目的节 点的递交率较低，延迟很大。 第二章路由算法介绍 2 3 多拷贝的路由模式 2 3 1 蔓延路由算法 ( 1 ) 基本思想 蔓延( e p i d e m i c ，另有翻译为传染) 路由2 5 1 算法的基本思想是，源节点将报 文递交给相遇到的每一个节点。这些节点作为中继，继续地交给它所遇到的每一 个节点，直到报文到达目的节点【3 5 1 。 b ) 一7 佰、) ! s 、 ( a ) t l 时刻 图2 3 蔓延路由示意图 ( a ) r _ 厂一o ( 、乡信1 盆仨、一 i 乙， ( ”t 2 时刻 如上图2 3 ( a ) 所示，源节点s 产生一个报文并且存储在缓存空间中，该报文 的目的节点就是节点d 。随着网络中各个节点位置的变化，在开始时刻，源节点 s 遇到了节点b 和节点c ，便将报文复制，分别递交给节点b 和节点c 。这两个 节点分别将报文储存在自己的缓存空间中，携带报文在网络中移动，继续运行洪 泛机制；如上图所示，在此后的时刻，节点b 遇到了节点a ，将报文复制，递 交给节点a ，自己继续保留报文副本。节点c 遇到了目的节点d ，将报文递交给 节点d ，完成报文传输。 ( 2 ) 协议的优缺点 优点：蔓延路由采用洪泛机制，利用了网络中遇到的所有节点进行中继转发， 使得报文递交的路径增加，从而使得效果比较好。 缺点：网络中出现很多多余的报文副本，在报文递交给目的节点后，网络中 依然保留着很多该报文拷贝副本，所以蔓延路由算法产生了过多的报文副本，容 易导致网络拥塞和浪费网络资源，增加能源消耗【3 5 1 。 1 2 基丁社会关系的容滞网络路由算法研究 2 3 2 概率路由算法 ( 1 ) 基本思想 在现实的d t n 中如有轨电车，邮递员等等这些节点，他们的移动具有一定 规律。如果某一个节点经常沿着某个路线移动，那么它以后的运动轨迹很有可能 就是遵循这种移动路线。基于这种情况，就可以得到概率路由协议( p r o p h e t ) 【2 6 1 。它是通过节点之间的通信经历，这样的先验式的历史信息来预测节点的后续 移动轨迹。 在概率路由中，两节点之间用概率值来描述节点之间相遇的可能性。这个值 有两种更新方式：一是节点相遇；二是时间流逝。所以这个概率是一个动态变化 的值【3 6 1 。 概率路由也是多拷贝路由，在寻找合适的中继节点上与蔓延路由有些区别。 下面将通过更新相遇概率和转发策略这两个部分详细介绍概率路由协议。 更新相遇概率 更新相遇概率： i ) 节点之间的每次相遇都增加他们之间的概率值，实现方法如下公式所示 公式如下： 最口，6 ) = 最皿b ) o t d + ( 1 一只口，b ) o t d ) p i n i t ( 2 1 ) 其中，既f f o ，1 】，是一个初始常量。这样的计算的话，相遇次数多的节点 之间的概率值就高【3 6 1 。 i i ) 随着时间的流逝，两个节点的相遇概率数值会逐步的减少，这个过程叫 做衰减过程。相遇概率会一直减少，意味着他们相遇的可能性在减少，那么传递 报文的可能性也在减少。例如在现实里，这个节点只在这个区域里出现了一次， 就再没出现过，那么就不应该利用这个节点把报文递交到这个区域内。下面的公 式表现的就是衰减过程。 最口，6 ) = p ( 皿b ) o t a 广( 2 2 ) 其中) ，的值在0 到1 之间。 i i i ) 如果两个节点都频繁的和同一个节点相遇，那么它们之间递交报文的可 能性也很大，那么相应的，它们之间的概率值就会很高。下面的公式表现的就是 第二章路由算法介绍 节点之间相遇概率的传递性【3 6 】。 p ( a ，c ) = p ( a ，c ) o l d + ( j - p ( a ，c ) o t d ) x p ( a ，b ) x p ( b ，c ) 卢 ( 2 3 ) o ，l 】，是一个常量，用以表示相遇概率的传递程度大小。 转发策略 首先，当节点接收到报文之后，如果此时与目的节点之间不存在端到端的连 接，这样的话该节点会将报文先存储在自己这里，携带报文在网络中移动，直到 与其它节点相遇，然后决定是否将这个节点作为中继节点，是否转发此报文。由 于在网络中有很多的节点，那么潜在的下一跳的节点数目很多，如果递交给很多 节点，报文就具有很大的可能性成功递交到目的节点。但是，在实际中如何选择 下一跳节点呢? 递交给每一个相遇的节点就是蔓延路由协议的做法，但是这种路 由算法会带来大量的冗余报文副本。为了减少网络中的冗余报文数量，只有相遇 的节点到目的节点的概率值比较大，该节点才会被作为中继节点，此报文才会被 转发给该节点【3 6 1 。 在p r o p h e t 路由协议中，当两个节点相遇，与目的节点相遇概率低的节点 将报文递交给相遇概率高的节点，以提高报文的递交率。 b ， ，一 一一，7 fa ( 乡 石 ( a ) t l 时刻 l 、乡 ( b ) t 2 时刻 图2 4 概率路由示意图 如上图2 4 所示，源节点是节点s ，目的节点是节点d 。当携带报文的节点 遇到其他节点，通过比较双方与目的节点的概率大小来决定是否递交报文。若节 点b 的概率比较大，那么在遇到节点b 时，则递交报文。若节点c 的概率小于 携带报文的节点，那么就不递交。 ( 2 ) 协议的优缺点 优点：控制了网络中的报文数量，对网络资源的消耗较少，产生网络拥塞的 1 4 口、汪 、】、佰) 基于社会关系的容滞网络路由算法研究 可能性也比较小。 缺点：如果两个节点频繁相遇，每次相遇的时问比较短，那么他们之间的相 遇概率虽然很高，但是完成通信的可能性就比较低，如果把报文递交给这样的节 点，会影响报文的递交率。同时，报文可能会在些特殊节点上富集，会造成在 这些节点上的报文拥塞，导致报文丢失。 2 3 3 散发等待路由算法 散发等待路由算法【2 7 】( s p r a ya n d 、i t ) 控制了网络中报文拷贝的数量。散 发等待路由协议有两种方案：源端散发等待路由算法以及二分散发等待路由算 法。 ( 1 ) 基本思想 i ) 源端散发等待路由算法 节点状态分为两个阶段：散发阶段和等待阶段。 为了控制报文在网络中的数目，报文在源节点处拷贝n 份。节点携带的报 文数超过1 时，该节点处于散发阶段，将报文拷贝递交一份给所遇到的每个节点， 这个过程类似于蔓延路由算法。 当节点的报文数目减少到1 或者只有1 份时，节点就处于等待阶段，即等待 着遇到目的节点完成递交【3 2 1 ，这个过程类似于直接递交路由算法。 ( b ，一、一 八 一_ 一 i a 嘲lb ( 1j ， 7 啊r s ! l ) ) 一+ j i s ( + l 一- 1 1 j ( a ) 1 l 时刻 d ( b ) t 2 时刻 图2 5 源端散发等待路由示意图 如上图2 5 ( a ) 所示，在开始时刻，源节点s 产生了一个目的节点是节点d 的 报文。在缓存中将其拷贝n 份。如上图所示，随着网络中各个节点位置的变化， 在此后的时刻，源节点s 遇到节点b ，则递交一份给节点b ，此时节点s 缓存中 的该报文的拷贝数则变为n 1 。而后源节点继续把报文递交给所遇到的节点，直 到只有一个报文在缓存中。因为整个散发过程只有源节点参与进来，所以该路由 1s 第二章路由算法介绍 算法称为源端散发等待路由。被递交报文的节点都在接到报文的那一刻，进入等 待阶段。由于网络中存在n 份相同的报文副本，这样就提高了报文的递交率 3 5 , 3 6 。 i i ) 二分散发等待路由算法 节点状态同样分为散发阶段和等待阶段，只是参与散发报文的节点不只是源 节点，还包括了网络中的其他节点。 同样，为了控制网络中的报文数目，在源节点处将报文拷贝n 份。散发阶 段由源节点开始，遇到第一个节点，则分一半的报文给该节点。那么这个节点在 接收到一半的报文的时候，也进入了散发阶段。因为每次都递交本身的一半报文， 所以称为二分散发等待路由算法【3 5 , 3 6 】。 只有当节点携带的报文仅有一个的时候，才进入等待阶段，等待遇到目的节 点。二分散发等待路由协议的散发节点不只一个，网络中同时存在着多个携带超 过一个报文的节点。 ( a ) t l 时刻 ，一、一 c ( l 4 ) )， 、 fd ( c ) t 3 时刻 一夥。 埒 ( 三) 盆亩 图2 6 二分散发等待路由示意图 如图2 6 ( a ) 所示，在开始时刻，源节点s 产生一个目的节点是节点d 的报文。 在缓存中将其拷贝n 份，随着网络中节点位置的变化，源节点s 遇到节点b ， 源节点s 将自身数目一半的报文拷贝递交给节点b ，递交完成后，源节点具有数 目为n 2 的报文拷贝，节点b 也具有数目为n 2 的报文拷贝。在后面的时刻， 节点b 和s 分别将所存储的报文转发一半给相遇的节点a 和c ，此时四个节点 缓存的拷贝数目都为n 4 。这些节点都是散发节点，都将继续这个二分散发过程， 1 6 一d r 、 盆，、 捌渺时 一刚 h 一刚 盆 基于社会关系的容滞网络路由算法研究 散发过程直到报文减少到1 【3 5 ，3 6 1 。只有当节点携带的报文仅有一个的时候，才进 入等待阶段，等待遇到目的节点。二分散发等待路由算法的散发节点不只一个， 网络中同时存在着多个携带的报文数目超过一个的节点。 ( 2 ) 协议的优缺点 优点：控制了报文在网络中的数量，对网络的影响小于蔓延路由。 缺点：对于相遇的节点没有进行评价，即对报文散发的节点没有限制，只是 递交给最先相遇的节点，这样有些递交潜力大的节点就可能没有被散发到报文拷 贝。同时盲目递交报文的策略，会造成网络资源的浪费。 2 4 本章小结 本章主要介绍了常用的几种d t n 路由算法，并分析了它们的优势和不足。 d t n 路由算法主要分为单拷贝路由和多拷贝路由两种类型。其中多拷贝路由是 我们的重点研究方向。 报文副本如何选择中继节点是几种多拷贝路由算法的不同之处。下面将介绍 在多区域的人群网络中，如何利用节点之间的社会关系选择中继节点，制定报文 转发的策略。 1 7 第三章基于社会关系的容滞网络路由算法研究 第三章基于社会关系的容滞网络路由算法 研究 3 1 引言 在研究d t n 路由协议时，往往认为节点移动轨迹是完全随机且没有规律的。 随着手持设备和车载设备的研发和兴起，越来越多的移动通信终端加入到通信网 络中。如果遇到极端天气的影响，比如雪灾、火灾或者受到军事打击和恐怖袭击。 网络的基础设施被部分毁坏，那么由这些移动终端设备为主体，辅助还可以使用 的通信网络基础设施则构成一个d t n 。 不只在这种灾难的环境中，在日常环境中，这些手持设备和车载设备之间构 成的人群网络也是d t n 中的一种，网络中的节点的移动轨迹是有一定规律的。 在人群网络的网络模型中，节点在一定的时间段里，会更倾向于到达特殊的兴趣 点，比如白天会到学校、公司。晚上会去商店、公园。这样，节点的移动就会有 一定的规律性。同时这些作为网络中节点的人和车辆都有自身的社交网络，这样 不同的节点与其他节点相遇的可能性也会有差别。上海市区的车载网络 s u v n e t 2 8 1 ( s h a n g h a iu r b a nv e h i c u l a rn e t w o r k ) ，便是这种d t n 的一种。如图3 1 所示，图中的小黑点代表了行驶中的出租车。通过在上海市内的4 0 0 0 辆出租车 组成一个特殊的d t n ，它们相互之间可以传递消息进行通信，通过这个网络来 验证一些路由算法是否可行。 围绕一些特殊的兴趣点，网络中的节点自主组成多个区域，有些节点穿梭于 多个区域之间，而区域内的有些节点之问的联系则更为紧密一些。那么在这样的 多区域网络中通信，可以利用节点的移动规律和相互之间的社会关系来设计适合 使用的路由算法。 基于社会关系的容滞网络路由算法研究 3 2 提出问题 图3 1 上海市区的车载网络s u v n c t 在第二章，我们提到路由算法分成两类。一个是网络中始终只有一个报文拷 贝的单拷贝路由算法，这种路由算法从源节点产生报文后，一直转发该报文，直 到成功到达目的节点。这种算法在开销上表现比较好，因为没有冗余的报文拷贝 在网络中。但是只依靠一个报文拷贝，在复杂的网络环境中很难成功地达到目的 节点，所以单拷贝路由算法的报文递交率比较低，在d t n 网络中不是很实用。 另一种就是多拷贝路由算法，常用的算法包括蔓延路由算法，概率路由算法 和散发等待路由算法。这些多拷贝路由算法的作法都是让网络中存在大量的报文 副本，通过尝试多种不同的路径来递交报文，提高报文的递交率。这样做是在牺 牲网络开销的情况下，达到提高递交率和降低