（通信与信息系统专业论文）基于多区域社会网络的dtn路由研究.pdf

摘要 摘要 f f l l l l l l l t l l f i l l l l l t l l f l l f f l f t t f i i i f r l l l l f l l f f r l l l y 19 7 5 7 7 8 - 当前应用最广泛的因特网采用的是t c p i p 协议，其应用前提是采用端对端 方式收发报文。但是随着科学技术的不断发展，各种新型通信设备进一步得到普 及，从而使传统意义上的网络进一步扩大。在一些特殊应用场合，如野生动物跟 踪、海洋探测、卫星通信、偏远地区通信等，网络中节点变得异常稀疏，报文的 收发很难再满足端对端方式。为了实现在这些场合网络的连接，人们提出了一种 新型网络体系结构，即容迟网络( d t n ：d e l a yt o l e r a n t n e t w o r k s ) 。 容迟网络的主要特点是网络中节点所处位置在不断变化，即网络拓扑结构动 态变化，这造成节点之间的连接具有间断性、报文传输延迟时间巨大、数据率非 对称性等。衡量容迟网络的性能主要包括：报文成功转发递交率、传输延时时间、 网络开销等。 社会网络是一种特殊的网络，其构成主要是由汽车、人以及其他交通工具所 携带的移动通信设备。由于手机等无线移动通信设备的普及，社会网络已经成为 d t n 网络研究的一个热点方向。在社会网络中，针对每个节点经过的社会区域 多少以及在每个区域中停留时间不同，本文提出了在多区域社会中基于节点社会 活跃度( 删：s o c i a la c t i v i t y ) 的路由算法。 本文根据多区域社会网络构成的特点，提出下列研究方法： 1 对构成多区域社会网络中的节点进行探索。由于在现实世界中，城市是由 多个社区构成的，而社区又是由人和各种交通工具构成，所以可以将城市看作是 一个大的社会网络，社区看作小区域，人及交通工具就是网络中的节点。在城市 这样的社会网络中，节点的移动模式不是随机的，节点移动区域范围大小以及在 i 摘要 某个区域中停留时间的长短都各不同，所以确定网络中节点的活跃程度，对于路 由算法的提出具有重要意义。 2 根据节点活跃程度的不同，本文提出了基于节点活跃度的路由，将那些经 过区域最多、在某个固定区域中停留时间最短的节点看作是活跃度最高的节点， 把活跃度高的节点作为转发节点。 3 使用网络仿真工具t h eo n e 构建仿真平台，对所提出的路由算法进行仿 真，最后得出仿真结果和结论。 关键字：社会网络、多区域、d t n 、路由算法、社会活跃度 i i a b s t r a c t a b s t r a c t t h em o s tw i d e l yu s e di n t e m e tu s e sat c p i pp r o t o c o lc u r r e n t l y , w h i c hu s e se n d t oe n dm a n n e rt os e n da n dr e c e i v em e s s a g e s b u t 、i t ht h ed e v e l o p m e n to fs c i e n c ea n d t e c h n o l o g y , av a r i e t yo ff u r t h e rs p r e a do fn e wc o m m u n i c a t i o ne q u i p m e n t ，s ot h a tt h e t r a d i t i o n a ln e t w o r kf u r t h e re x p a n d e d i ns o m es p e c i a la p p l i c a t i o n s ，s u c ha sw i l d l i f e t r a c k i n g ，o c e a ne x p l o r a t i o n ，s a t e l l i t ec o m m u n i c a t i o n s ，。r e m o t ea r e ac o m m u n i c a t i o n s ， n e t w o r kn o d e sb e c o m ev e r ys p a r s ea n dd i f f i c u l tt os e n da n dr e c e i v ep a c k e t st om e e t e n dt oe n dm a n n e r i no r d e rt oa c h i e v en e t w o r kc o n n e c t i v i t yo nt h e s eo c c a s i o n s ，i t p r e s e n t san e w n e t w o r ka r c h i t e c t u r e ，w h i c hi sd t n ( d t n ：d e l a yt o l e r a n tn e t w o r k s ) t h em a i nf e a t u r e so ft h ed t na r et h en o d e sl o c a t i o n ，w h i c hi sc o n s t a n t l y c h a n g i n g ，t h a ti s ，t h ed y n a m i cn e t w o r kt o p o l o g y i tc a u s e dt h ec o n n e c t i o nb e t w e e n n o d e sh a sad i s c o n t i n u i t y , ah u g ep a c k e tt r a n s m i s s i o nd e l a yt i m e ，t h ed a t ar a t eo f n o n s y m m e t r ya n d o t h e rc h a r a c t e r i s t i c s m e a s u r et h ep e r f o r m a n c eo ft h ed t ni n c l u d e ： p a c k e td e l i v e r yr a t i o ，t h et r a n s m i s s i o nd e l a yt i m e ，n e t w o r k o v e r h e a da n ds oo n s o c i a ln e t w o r ki sas p e c i a lk i n do fn e t w o r k ，i t sc o m p o s i t i o nm a i n l yb yc a r s ， p e o p l e ，a n do t h e rt r a n s p o r t i n ge q u i p m e n t ，w h i c hc a r r i e db ym o b i l ec o m m u n i c a t i o n s e q u i p m e n t a sm o b i l ep h o n e sa n do t h e rw i r e l e s s m o b i l ec o m m u n i c a t i o nd e v i c e s p o p u l a r , s o c i a ln e t w o r k i n gh a sb e c o m ea h o td t nn e t w o r kr e s e a r c hd i r e c t i o n i nt h e s o c i a ln e t w o r k ，f o re a c hn o d ea f t e ran u m b e ro fs o c i a la r e a sa n dt h er e s i d e n c et i m ei n e a c hd i f f e r e n ta r e a , t h i sp a p e rp r e s e n t st h ed e g r e eo fs o c i a la c t i v i t y ( s a ：s o c i a l a c t i v i t y ) r o u t i n ga l g o r i t h m b a s e do nt h ec o m p o s i t i o no fm u l t i - r e g i o n a lc h a r a c t e r i s t i c so fs o c i a ln e t w o r k s ， t h i sp a p e rp r e s e n t st h ef o l l o w i n gm e t h o d s ： 1 w ee x p l o r et h en o d e s ，w h i c hc o n s t r u c tm u l t ir e g i o n a ls o c i a ln e t w o r k s a si n t h er e a lw o r l d ，t h ec i t yi sc o n s t i t u t e db yan u m b e ro fc o m m u n i t i e s ，a n dt h ec o m m u n i t y i sc o n s t i t u t e db yp e o p l e sa n dt r a n s p o r t i n ge q u i p m e n t s ，s ot h ec i t yc a nb es e e na sa m a j o rs o c i a ln e t w o r k s ，c o m m u n i t ya sas m a l la r e a ，p e o p l ea n dt r a f f i c t o o la st h e i i i 摘要 n e t w o r kn o d e s u c has o c i a ln e t w o r ki nt h ec i t y , t h en o d em o b i l i t yp a t t e mi sn o t r a n d o m ，t h ea r e as i z eo fn o d em o b i l i t ya n dl e n g t ho fs t a yi no n er e g i o na r ea l l d i f f e r e n t s oi t si m p o r t a n tt od e t e r m i n et h el e v e lo fn o d e sa c t i v i t y , w h i c hh a sg r e a t s i g n i f i c a n c et ot h er o u t i n ga l g o r i t h m 2 a c c o r d i n gt ot h ed i f f e r e n tn o d e sa c t i v i t y , t h i sp a p e rp r e s e n t st h er o u t i n g r e s e a r c hb a s e do nn o d e sa c t i v i t y s ot h en o d ew h i c h t h r o u g ht h ea r e ai sm o s ta n dt h e t i m ei ts t a yi nt h ea r e ai ss h o r t e s th a st h eh i 曲e s ta c t i v i t yd e g r e eo fn o d ea n dt h i sn o d e 3 w eu s et h eo n es i m u l a t o rt ob u i l ds i m u l a t i o np l a t f o r m a n dw eu s et h eo n e t os i m u l a t et h ep r o p o s e da l g o r i t h m ，a n dt h e ng i v et h ef i n a ls i m u l m i o nr e s u l t sa n d c o n c l u s i o n k e y w o r d s ：s o c i a ln e t w o r k ，m u l t i - r e g i o n s ，d t n ，r o u t i n ga l g o r i t h m ，s o c i a la c t i v i t y i v 第一章绪论 1 1d t n 网络概述 第一章绪论 1 1 1 计算机网络 计算机网络就是将众多分散的计算机通过有线或无线的通信线路有机连接 在一起，达到相互通信，实现资源共享的综合系统。自计算机网络产生之日起， 其对人类社会的进步做出了极大的贡献。从计算机网络的产生和发展经历来看， 主要经历从简单到复杂、从单机系统到多机系统三个阶段，但是这三个阶段并非 截然分开而是有部分重叠。 第一阶段是具有通信功能的单机系统阶段。在2 0 世纪5 0 年代初期，计算机 刚诞生不久，其主要特点是体积巨大，价格十分昂贵，由专业的技术人员进行管 理与操作，一般人接触不到。当时，人们需要利用计算机，只能将程序交给计算 机管理人员，等待一段时问之后再去取出运行结果。到2 0 世纪5 0 年代后期，计 算机主机依然昂贵，但通信线路和设备相对便宜，为了共享计算机资源和进行信 息处理，产生了具有通信功能的单机系统。其主要思想是在计算机上增加一个通 信设备，使主机具有通信功能，这样，用户就可以在离主机很远的终端上输入自 己的程序和数据，再通过通信线路将结果返回给用户，如图1 1 所示。单机系统 的优点是减轻了用户来回路途的时间，但其缺点也很明显，即主机自身负担加重， 既要处理数据，又要完成通信控制；同时线路的利用率也很低。为了克服这些缺 点，出现了面向终端的计算机通信网，即具有多通信功能的多机系统。 第二阶段是具有通信功能的多机系统阶段。其主要思想是在单机系统的基础 上添加了专门用于通信控制的通信控制处理机，这样就能够让主机专门用于数据 处理，从而提高了主机数据处理的效率；同时为了克服通信线路利用率低的缺点， 在低速终端集中的地方添加了终端集中器，终端集中器的作用是负责从终端到主 机的数据集中和从主机到终端的数据分发，如图1 2 所示。2 0 世纪6 0 年代，随 基于多区域社会网络的d t n 路由研究 端 图1 1 具有通信功能的单机系统 着技术的发展，这种多机互联系统的网络得到进一步发展，代表有美国通用电气 ( g e ) 公司的信息服务网络。 图1 2 具有通信功能的多机系统 第三阶段是计算机网络阶段。随着科学技术的不断发展，出现了将多台计算 机互联的要求，这种要求主要来自科学研究、军事领域、国家与地区经济信息分 析、企业经营管理等。他们的希望是将处于不同地点的计算机通过通信线路互连 成为一个网络，即计算机计算机网络，用户既可以使用本地计算机的软硬件与 数据资源，也可以通过网络使用其他地方计算机的资源，达到计算机资源共享的 目的。美国国防部高级研究计划局( a r p a ，a d v a n c e dr e s e a r c hp r o j e c t s a g e n c y ) 的a r p a 网就是满足这些需要的网络，其结果如图1 3 所示。图中i m p ( 接口信 息处理机) 用于通信处理和通信控制，h ( 主机) 用于数掘处理，t i p ( 终端接 口处理机) 用于将终端连入网络。a r p a 网研究的成果对计算机网络的发展具有 深远的意义，在其基础上，计算机网络发展十分迅速，当前覆盖全球最广的计算 2 第一章绪论 机网络是因特网，即是在a r p a 网的基础上发展起来的。 1 1 2i ) t n 网络由来 图1 3 a r p a 网结构 随着科学技术的不断发展，计算机网络也在不断的拓展，连接介质由最初仅 仅依靠导线的有线连接，发展到现在诸如卫星等无线连接，从而网络所覆盖的区 域也在不断的增加，从原来的城市区域发展到偏远乡村甚至无人居住地区。当前 计算机网络得到如此普遍的使用，一个重要的原因是全球最大互联网因特网 采用统一的通信协议，即t c p i p 协议。在因特网中成千上万个子网，网络设备 在进行路由选择、报文交换时都要遵循这个协议。因特网采用t c p i p 协议，其 主要特点是网络中的链路必须是端到端的持续连接川，所以信源到信宿路径上的 延迟和差错率很低，且双向数据率稳定。 在传统的计算机网络之外，比如能量有限( 受限) 的移动无线通信、卫星通 信、星际之间通信等，这些通信都有各自的特殊要求。而对于各自通信需求，都 必须由独立的网络来完成，这些网络也不使用传统的t c p i p 协议，各自之间也 互不相容。这些网络在其内部通信区域，通信特征具有相对一致性，但是在网络 区域边界区域，诸如链路延迟、链路导通性、数据率、差错率、可靠性、服务质 量等都不具有好的性质。与传统网络比较，这些网络具有延迟巨大、链路连接随 时断开、差错率大以及数据率非对称等特性。 在一些特殊场合，诸如野生动物跟踪、野外勘察、军事网络、星际通信等， 由于在这些网络中，链路的连接不具有端到端的特点，所以传统的因特网就不能 够满足要求。同时，在某些自然灾难发生时，如2 0 0 8 年四j i l 汶川大地震，造成 基于多区域社会网络的d t n 路由研究 城镇内基础通信设施损坏，使这些地区内部与外部的通信连接断开。 针对于上面的情况，人们将这类网络进行归类，用图1 4 来表示与传统因特 网的区别口】。于是2 0 0 2 年，在i c i r 会议上，k f a l l 等科学家首次提出容迟网 络( d t n ：d e l a yt o l e r a n tn e t w o r k s ) 概念p j ，并引起国内外许多学者和研究机构 关注。由于d t n 网络的性能与传统网络相比较，在传输性能上存在着很多缺点， 所以现在人们主要关注d t n 网络如何在路由算法、拥塞控制、能量节约、实际 应用等方面更进一步对其性能进行优化。 m a r s k e y ：- - w i r e l e s si i n k w i r e d1 i n k a n t e n n a p e r s o no rv e h i c l e 1 2 3d t n 网络结构及特点 e a r t h ss u r f a c e 0 t e l e p h o n en e t w o r ko f f i c e os e n s o r s a t e l l i t e _a i r c r a f t 图1 4 各种受限网络模型 d t n 网络是由多个区域网络组成的大网络，构成d t n 网络的子网络是异构 的，所以它是区域网络之上的覆盖网络【4 j 。d t n 网络内部的每个区域网络，既 可以是使用传统设备的因特网，也可以是使用其他诸如无线传感器、雷达、卫 星等设备的无线网络。由于每个区域网络内部所使用的协议可能不同，所以区 域之间的连接还需要进行协议转化。在2 0 0 2 年，国际互联网研究组专门成立了 容迟网络研究组( d t n r g ) ，将d t n 网络体系结构确定为与传统网络不同的通 用网络，随后在2 0 0 3 年，k f a l l 等研究学者j 下式提出了该网络结构，如图1 5 所示。 4 第一章绪论 图1 5d t n 网络构成结构 d t n 网络与传统的计算机网络不同，其主要特点可以表现为下面几点【5 卅： 1 连接具有间断性：由于构成d t n 网络的多个区域之间，链路连接由于 网络环境比较恶劣，从而使网络在连接时经常发生断连，即网络处于 断开状态，同时这种断开状态是经常发生。所以d t n 网络的间断是经 常发生，且无法事先预料。 2 传输延迟巨大：d t n 在连接时，不但会出现连接间断，而且节点和节 点之间在对报文进行传递时，由于连接时间的不确定性，经常报文无 法传输成功，所以会出现多次重新传递。同时在节点中传递报文还会 出现可变的排队延迟，即节点在无法找到下一跳节点时，必须要先把 消息进行存储，所以会造成某些报文需要等待很长时间才会被传递。 由于上面原因，造成网络延迟巨大。 3 非对称数据率：由于d t n 网络上由多个异构网络组成，对于那些使用 诸如电缆或有线导线等传统通信设备的用户，数据成功传递的概率非 常大，但是对于某些使用诸如能量有限的无线设备，由于网络环境恶 劣，数据成功传递的概率就存在着很大随机性。 4 高差错率：在传统通信网络中，链路中的比特误码都需要去纠正( 需 要更多的比特和进一步处理) ，或对整个进行分组重传。但是对于d t n 基于多区域社会网络的d t n 路由研究 网络，连接经常会间断，逐跳重传的次数很难得到保证。 5 存储转发报文交换：由于d t n 网络具有连接间歇、传输延迟巨大、非 对称数据率、高差错率等缺陷，为了提高网络的性能，d t n 网络采用 “存储携带转发 路由方法。当节点获得所需要传递的报文 时，由于在该节点周围可能不存在转发节点，于是报文首先会被存储 到该节点的缓存中，所存储的报文也会随节点一起移动，即节点携带 报文，当携带报文的节点遇到可以传递的节点，再将报文转发给相遇 节点，其过程见图1 6 所示。 节点 9 存储 节点 9 存储 节点 9 存储 节点 转发 转发 。 a 转发 。 aaa 1 2 4 聚束层 图1 6 节点a 存储转发过程 存储 与传统的因特网比较，由于d t n 网络的构成具有异构性特点，所以对于 区域相关的异构底层协议，d t n 网络通过在其顶部覆盖一个新的协议层， 即聚束层【7 】( b u n d l el a y e r ) 来实现存储转发报文交换的目的。底层协议与添加 聚束层捆绑在一起，就可以让应用程序穿越多个区域进行通信了。 从报文转发意义上看，聚束通常也可以称为报文，主要有三个部分组成： ( 1 ) 信源所需要传递的数据；( 2 ) 传递给信宿的控制信息；( 3 ) 插入的聚 束头标。在结构上，单一的聚束层用于全网中各个区域，而聚束层之下，却 选择与各个区域通信环境相适应的不同协议层。聚束层所处位置如图1 7 所 示，即在传统的t c p i p 层之间添加一层。 6 第一章绪论 传输层 网络层( i p ) 链路层 物理层 互联网协议层d t n 协议层 图1 7 聚束层所处位置 1 2 5d t n 网络的主要应用 所有d t n 区域 都相同 每一d t n 区域 可熊不同 d t n 网络从诞生之日起，得到十分广泛的应用，主要有车辆网络【8 1 1 1 、军事 网络f 1 2 1 、星际通信【1 3 】、野生动物考察、偏远地区通信【1 4 。15 1 、人群网络【1 6 - 1 7 】等。+ 1 车辆网络 在城市中，汽车是一种最常见的交通工具，当汽车携带一定的无线传感器设 备后，众多汽车就会形成一个大的网络1 1 。以汽车为连接媒介，来传递道路上 的交通信息或者是应急信息。这种网络在高速公路上也同样可以使用，当高速公 路上发生交通事故或者出现雨雪等灾害信息时，利用车辆网络通信将这些信息逐 渐传递出去。同时，在城市中，由于出现某些不可预见事故或灾难，使基础通信 设施损坏，这时也可以通过汽车在城市中运行，将城市重新连成一个网络，从而 保持紧急信息可以传递出去。 2 星际网络 随着人类活动范围的扩大以及对宇宙的探索，地球向周围星球通信的需求越 来越多，比如地面空间站与火星上的飞船进行通信，这种通信方式被称为星际通 信【1 3 】。由于星际之间没有固定的通信连接，所以传统的通信方式就不能满足这 种通信，这时d t n 网络就可以应用在此处。 3 野生动物跟踪考察 人们为了观察一些濒危动物的生活习性，经常需要在一些条件艰苦或偏远区 域去观察，而在这样环境恶劣地区，传统网络同样也无法接入，这时可以通过安 装在动物或者行人身上的移动无线设备进行相互之间的通信。普林斯顿大学曾经 7 基于多区域社会网络的d t n 路由研究 在非洲大草原上设计出一种被称为斑马网络的d t n 网，即通过安装在斑马身上 的无线传感器来收集斑马的迁徙数据，数据的收集是通过安装在汽车上的移动基 站来获取的。 4 偏远地区通信 。 在一些偏远地区，比如非洲某些大沙漠，由于经济和自然环境的制约，造成 传统网络的基础设施无法建立。生活在这样条件艰苦地区的人们，同样也需要获 取外界信息，但是他们也无法通过诸如卫星通信设备这样昂贵的设备与外界联 系，由于建立d t n 网络相对于其他通信方式来说价格非常低廉，这时可以通过 建立一个d t n 网络来达到人们传递消息的目的【1 4 1 5 】。在印度偏远山区，科学家 曾经建立一种被称为m o t o p o s t 的网络，其构成如图1 8 所示。在m o t o p o s t 网络 中，每个村庄被看作是一个小的区域，位于村庄边上的电话亭部署了k i o s k 设备， 用于存储本村需要传输出去的信息以及接收外面的信息，公路上行驶的公共汽车 安装了车载移动设备，主要是用于存储转发村罩和外面接收的信息，在城镇公共 汽车经过的某些地方安装了a p 设备，a p 设备连接到互联网。当有外界信息需 要传递给村庄里的某个人，首先是通过互联网将信息传递到a p 设备上，当公共 汽车经过a p 附件时，再通过无线设备将信息存储到公共汽车里的移动设备中， 公共汽车经过那人村庄时，将信息发送到k i o s k 设备，最后接收者就可以在k i o s k 获取所需信息。 ；辩辑日伊g u 船栅赫戤甜； ；v o b ，缸：i 嚷# c b j r t ，撕幽厶 - 、厂一 芯鼬n 墼： 遵型一：二： 糕： f i g u r e1 m o t o p o s t t mn e t w o r k 图1 8m o t o p o s t 网络 固 第一章绪论 1 , 2 6 衡量d t n 网络的性能指标 1 传输延迟。在通信中，延迟是指一个报文或分组从一个网络的一端传送到 另外一端所消耗的时间，包括以下几个组成部分： ( 1 ) 发送延迟，是节点在发送数据时使数据块从节点进入到传输介质所需的时 间，即从数据块的第一个比特开始发送计算，到最后一个比特发送完所花费的时 间。从数学上计算，发送延迟等于数据库长度与信道带宽之比。 ( 2 ) 传输延迟，是电磁波在信道中传播所消耗的时间，等于信道长度与电磁波 在信道上传播速率之比。对于d t n 网络来说，由于网络连接具有不确定性，也 就是即使在信道长度一定时，报文传播速率也是不能确定的，所以对于d t n 网 络来说，传输延迟将巨大。 ( 3 ) 处理延迟，是数据在交换节点为存储转发而进行一些必要的处理所消耗的 时间，如在节点缓存队列中分组排队所经历的时间消耗是处理延迟的一个重要组 成部门。 2 误码率。误码率是指二进制数据位传输出错的概率，其计算方法是：数据 传输后，出错的位数与传输的数据总位数之比。所以误码率是衡量数据通信系统 是否能够正常工作的一个重要指标。 3 投递率。在d t n 中，投递率被定义为在整个通信过程中，信宿节点成功接 收到数据包数量与在信源节点所传递的所有数据包比值大小。即： 投递率= 成功递交报文数量数据包总数量。 4 网络开销率。指在d t n 网络中被中继的数据包与成功传递的数据包之差除 于成功递交的数据包。即： 开销率= ( 中继数据包数量一成功传递的数据包数量) 成功递交数据包数量。 对于传统的计算机网络，由于链路一直连接，即保持端到端连接，所以传统 网络具有传输延迟很小、误码率极低、投递率很高等特点。但是对于容迟网络而 言，由于网络中连接具有不可预知性，即网络经常断开，断开时间难以预料，同 时网络中节点一般都是随机运动的，运动的节点能力有限，所以d t n 网络与传 统网络相比，具有高延迟、高误码率、低投递率以及网络丌销大的特点。 9 基于多区域社会网络的d t n 路由研究 1 2 论文的选题及研究意义 自d t n 网络提出起，人们对该网络的研究越来越多。针对于d t n 网络高 延迟、高误码率、低投递率及网络开销大等特点，人们对其研究的重点可以归结 为以下几点： ( 1 ) 路由算法研究。任何网络性能的好坏，与其自身路由有着巨大的关系，由 于d t n 网络连接不确定的特性，造成该网络的路由也很难确定，所以路由算法 研究成为d t n 网络研究的难点和热点。总结以往人们对各种路由算法的研究成 果，大多数人研究的路由归于：蔓延路由及其改进、散发等待路由及其改进、概 率路由及其改进。 ( 2 ) 网络节能和拥塞控制。由于d t n 网络中，移动节点的能量有限，而与传统 网络节点不同，移动节点在运动过程和报文传递过程都需要消耗大量的能量，所 以要在有限能量的前提下将报文成功传递出去，就务必需要考虑如何节能问题。 同时d t n 网络采用存储转发策略进行报文传递，而节点的缓存有限，通常转发 节点在空间和时间上都需要等待与下一个节点相遇，且这种等待时间无法预测， 这时如果又有新的报文需要该节点转发，则就可能需要考虑节点自身缓存大小是 否满足要求。所以在有限能量和缓存大小前提下，要成功转发报文，就需要考虑 网络的节能和拥塞控制问题。 ( 3 ) 网络应用。由于d t n 网络具有能够容忍延迟巨大的特点，所以关于d t n 网络的应用也是人们研究的热点之一，其主要应用包括：军事、交通、海洋监测、 偏远地区通信、野生动物跟踪以及卫星通信等。 在d t n 网络中，有一类网络是人们近来研究的热点，即社会网络。社会网 络是一种特殊的d t n 网络，主要是由人、汽车及其他交通工具携带的移动设备 组成，通信是利用这些设备的短距离无线电进行的。在城市中，这样的社会网络 随处可见。同时d t n 网络的另外一个重要性质是网络有多个间断区域组成，即 多区域性。在多区域网络中，每个区域内和区域问都有大量运动的节点构成，这 些节点自身也有其特殊属性，即节点所处位置、节点运动方向和速度、节点运动 路径、节点与周围节点关系、节点经过区域多少以及在某固定区域内停留时间长 短等。所以要在这样多区域社会网络中，研究如何提高网络性能就必须先要去研 究网络中这些节点的性能，并且通过建立种合理的数学公式去衡量节点的性 1 0 第一章绪论 能。 本文将d t n 网络的两大特性：多区域性和社会性相结合，研究节点在网络 中的活跃程度，研究内容包括： ( 1 ) 首先考虑网络中节点运动方式存在着巨大差异，一些节点活跃度很强，能 够在多个区域之间运动，而有的节点活跃程度一般，只能够在很少的几个区域问 运动，还有一些节点活跃程度最弱，只能在某个区域内运动。报文将根据节点运 动区域的多少以及在某个固定区域内停留时间长短，建立节点活跃度的数学公 式。 ( 2 ) 其次本文从计算出的节点活跃度出发，建立一种合适的路由模型，以适应 于多区域转发模型。拟将报文的转发分为在区域内和区域之间转发两种情况。 ( 3 ) 最后通过建立仿真平台，来模拟所提出的路由模型。 1 3 本文的工作及结构 d t n 网络所具有的特殊结构，必然使其在未来应用中大有可为。对于d t n 网络的研究主要包括路由算法、拥塞控制以及应用等方面。本文从d t n 网络所 具有的社会性和多区域性着手，考虑在多区域环境下，节点运动活跃性的不同， 建立一种合适的路由机制，使在多区域环境下，报文能够更好更准确的传递出去。 本文分为五个部分，分别是： 第一章，绪论。首先介绍了在d t n 网络产生之前，传统计算机网络发展的 几个阶段。接着介绍了d t n 网络产生的背景、结构与特点、d t n 网络所特有的 聚束层、d t n 网络应用。再接着介绍了衡量d t n 网络特性的几个指标。最后是 本文的选题及研究意义。 第二章，d t n 网络路由概述。主要介绍了人们当前所研究的几种热点路由 算法，包括：蔓延路由、散发等待路由、概率路由以及其他路由。 第三章，多区域社会网络。主要将d t n 网络的社会性和多区域性进行结合， 介绍了社会网络研究背景、多区域网络模型、在多区域网络中所存在的路由算法。 第四章，基于多区域社会网络的路由研究。主要介绍了该路由算法的思想、 社会活跃度的计算方法、根据所提思想所建立的仿真平台、实验结果。 第五章，结束语。主要是对本文进行总结。 基于多区域社会网络的d t n 路由研究 1 4 本章小结 本章首先从传统的计算机网络开始介绍，给出了计算机网络发展的阶段以及 传统网络所具有的特征，接着介绍了在当前情况下，d t n 网络产生的背景、d t n 网络所具有的特殊结构以及应用。同时为了后面的仿真参数建立，还介绍了衡量 网络性能的一部参数指标。最后给出了本文的选题和研究意义。 1 2 第二章d t n 网络路由概述 2 1 概述 第二章d t n 网络路由概述 最近，随着人们对d t n 网络的深入研究，关于d t n 网络的应用越来越多， 如人群网络、军事网络、海洋勘测、星际网络、偏远地区通信等。但是由于网络 自身所存在的特点，即网络延迟巨大、投递率低、非对称数据率以及网络开销大 等特性，制约了d t n 网络的进一步发展应用。同时d t n 网络中网络连接的不 确定性、节点动态变化以及节点缓存和能量有限等缺陷，也是d t n 网络发展的 另外一个重要瓶颈。对于网络中路由的研究一直是各种网络研究的热点和难点， 这是因为合适的路由方法对于网络来说，不但能够提高网络性能，还使网络更容 易实现。同理，要在众多挑战环境下，使d t n 网络能够实现的唯一方法就是提 高d t n 网络的性能，即减少传输延迟、增加投递率、减小网络开销，所以对d t n 网络的路由设计就成为关键的研究问题。 对于d t n 网络的路由设计，首先考虑的是提高网络的投递率，因为对于任 何网络来说，消息能够顺利的传输出去并能够顺利接收到才是最重要的。由于在 d t n 网络中，存在着众多不可预测或不可靠的设备，所以网络投递率一般很低。 为了弥补这种缺陷，很多人设计出多拷贝路由方式来提高投递率，即在报文传递 开始，在所经过节点对报文进行多个拷贝。从实验结果来看，采用多拷贝策略后， 网络的投递率得到提高，但是由于每次都要传输多个拷贝的报文，相应的传输时 间又变得更大了，且网络开销也会增加。所以在考虑路由时，人们设计出了单拷 贝策略，与多拷贝比较，每次投递时只传递一个报文。通过实验结果看，单拷贝 降低了网络开销和延迟，但是投递率也下降明显。所以从实验结果看，单拷贝和 多拷贝传输策略自身都存在着重要的缺陷，只有通过其他的方法来弥补。 当前，人们对d t n 网络的路由研究做了大量的工作，提出了多种不同的路 由算法，总结来说，主要集中在下面几种路由。v a h d a t 和b e c k e r 等人所提出的 蔓延路由【l 引，即当两个节点相遇时，节点问就会彼此交换报文，以此完成报文 传递。蔓延路由与网络中的泛洪机制类似，即网络中所有节点都会成为转发节点， 因而报文的延迟会减少很多。但是由于网络中所有的节点都要参与传递，相应的 1 3 基于多区域社会网络的d t n 路由研究 网络的开销会提高很多，并且占用太多的网络资源。后来，t h r a s y v o u l o s s p y r o p o u l o s 等人提出了一种被称为二分散发等待( b i n a r ys p r a ya n dw a i t r o u t i n g ) 1 9 】的路由算法，是在蔓延和多拷贝基础上建立的一种新的方法，即在 报文传输开始时，将报文复制l 份，当携带l 份的源节点遇到第一个节点时， 会将自身一半的报文传给对方，自身留下剩下的一半。接着携带报文的节点遇到 其他节点，也会将自身携带报文的一半传给相遇节点，自身留下一半，一直到节 点只携带一份报文，这个阶段称为散发阶段。接着在剩下时间里，携带一份报文 的节点在网络中运动，只有当碰到目的节点时，才将自身所携带的报文传递出去， 否则不传递，这个阶段称为等待阶段。散发等待路由算法与蔓延路由相比，由于 只是选择一部分节点参与报文传递，所以大大的降低了网络开销，但是由于只存 在l 份源报文，所以投递率会降低很多，同时，开始时l 份拷贝数确定具有很 大的随机性。a n d e r sl i n d g r e n 等人根据网络中节点和节点相遇次数来计算节点间 的相遇概率【2 0 j ，当携带报文的节点与另外一个节点相遇时，不是立即将自身携 带的报文传给对方，而是先要判断其相遇概率值大小，只有当相遇节点的概率值 比自身大时才会将报文传递。与蔓延路由相比，概率路由也是只选择网络中部分 节点作为转发节点，且这些被选择的节点在网络中与其他节点碰面机会大，所以 概率路由的网络开销要比蔓延路由低很多。但是，由于概率路由也只是选择部分 节点作为转发节点，所以其投递率也没有蔓延路由高。本章将详细介绍这三种路 由算法以及常见的其它几种算法。 2 2 蔓延( e p i d e m i c ) 路由 蔓延路由与传统网络中的泛洪机制相似，其主要思想是当两个节点相遇 时，首先彼此交换对方信息，判断本身所携带报文是否也在对方缓存中，如果一 方没有，则将自身所具有的报文传递给对方，以此类推，直到将报文传递到目的 节点。图2 1 给出蔓延路由的整个过程。 1 4 第二章d t n 网络路由概述 时间t l 时间t 2 t l 节点交换信息 图2 1 蔓延路由过程 如图2 1 所示，源节点s ，中继节点n ，目的节点d ，节点的通信范围为灰 色区域。整个蔓延路由可以分为三个阶段： 在t l 时刻，携带报文的源节点s 在通信范围内遇到节点n l 和n 2 ，s 首先判 断n 1 和n 2 是否已经具有自己所携带的报文，之后将报文传递给节点n l 和n 2 。 在t 2 时刻，节点n l 运动到另外一个节点n 3 附近，在可通信范围内，节点 n l 和节点n 3 交换彼此信息，n l 在确定n 3 没有自己所具有的报文后，将自己所 携带的报文传递给节点n 3 。 在t 3 时刻，节点n 3 与目的节点d 相遇，这时n 3 直接将所携带报文传递给d 。 从蔓延的路由过程看，整个传递阶段可以总结为图2 1 的节点交换信息图， 即节点b 和b l 相遇，b 将所携带报文的摘要向量传给b l ，b l 把收到的摘要向量 与自身所携带的摘要向量进行比较，找到自己所不具备的报文，然后请求b 发 送给报文，b 在收到请求后将该报文发送给b l 。蔓延路由的设计目的主要有下 面几个方面：最小化延迟、最大化的投递率和有效的信息传播。 但是，在用蔓延路由进行报文传递时，我们不得不考虑下面两个问题： l 、资源利用问题。由于蔓延路由在报文传递过程中，几乎使用了网络中所有的 节点进行中继，由于d t n 网络与传统网络不同，d t n 网络中所存在的节点能量 有限，如果使用这些能量有限的节点进行报文传递，势必会造成资源浪费的结果， 固鬻国缘 ：i；曛鞭=：=“霍= ：=：=：、鬈琏” 辩i|甄!；j铥 一黼糕鬻 熬缈纛溯蝴 主 基于多区域社会网络的d t n 路由研究 即网络开销巨大。所以在使用蔓延路由进行报文传递时，虽然在衡量网络性能的 投递率和延迟上会获得好的效果，但在网络开销问题上会造成很大的资源浪费， 这在实际应用中不得不考虑的问题。 2 、性能表现是否真的好。对于传统网络，衡量其好坏标准通常根据投递率大小、 网络延迟、数据率、网络开销等方面。但是为了衡量整个网络好坏，人们通常又 加入了平均传输延迟、平均缓存利用率、节点能量消耗等方面。从实验结果去看， 蔓延路由在新加入的几个网络标准上，结果不尽人意。 2 3 散发等待( s p r a y a n dw a i t ) 路由 散发等待路由算法【1 9 】是在蔓延基础上创建的新路由方法，其主要过程可以 分为散发和等待两个阶段： 散发阶段：在信源节点为每个报文产生l 份拷贝，然后由信源开始对每个 报文拷贝进行传播。当信源节点与某个节点相遇时，会将自身所携带的报文l m 份传给对方，这里的m 是事先设定好的一个定值，信源节点会留下剩下的报文。 接着，携带报文的节点继续在网络中运动，假设自身携带报文拷贝为，份，当该 节点与其他没有携带报文的节点相遇，同样也会将自身所携带报文的i m 传给 对方。以此类推，直到在节点中的报文只剩下一份为止。 等待阶段：当节点携带的报文只剩下一份后，即使这些节点与新的节点相遇， 如果相遇节点不是目的节点，那么也不会将报文传递给对方，所以称这个阶段为 等待阶段。只有当携带报文的节点遇到目的节点时才将自身报文直接传给对方。 散发等待路由算法的过程可以用图2 2 来描述： _ l 个一 图2 2 散发等待路由 1 6 一、，i誓-=i颡罐一 第二章d t n 网络路由概述 在图2 2 中，源节点携带l 份报文m ，经过散发阶段后，整个网络中有不同 的节点携带一份报文，但是所有报文之和仍然是l 份，即在散发阶段网络中蔓 延对报文进行拷贝。当携带一份报文的节点能够与目的节点通信时，会直接将报 文传递给目的节点。 由于在散发阶段，m 值的确定比较困难，所以人们就直接将m 值定义为2 ， 将这种改进后的散发等待路由算法成为二分散发等待( b i n a r ys p r a ya n dw a i t ) 路 由。其过程如图2 3 所示： 图2 3 二分散发等待路由 图2 3 显示，源节点s 携带了l 份报文拷贝，在散发阶段，当s 首先与节点 e 相遇，会将自身所携带报文的一半传给e ，自己留下剩下的一半，即第一次相 遇后，源节点保留l 2 份报文，节点e 拥有l 2 份报文。接着节点s 与a 相遇， 同样交给对方一半拷贝数报文，自己留下一半；节点e 与d 相遇，e 也把自己 刚得到报文的一半拷贝数交给对方，自己留下一半，这时a 、s 、e 、d 节点都 具有l