（信号与信息处理专业论文）机会网络路由协议研究.pdf

重庆邮电大学硕士论文 摘要 摘要 机会网络作为一种新型无线互联网络，可以广泛应用于外太空网络、陆地移动 网络和军事自组织网络等。它具有链路间断连接、高时延、低数据率、节点资源有 限等特点。由于机会网络的无线链路具有随机间断特性，网络中的通信终端之间无 法建立可靠的端到端路径，因此现有的t c p 协议并不能很好地运行在机会网络 上。目前，人们已经开展了各种适用于机会网络的新技术研究，其中路由协议是研 究的重点。 本文首先简要介绍了机会网络的概念、关键技术、特点和应用，并对机会网络 的路由问题以及现有的几种典型路由协议进行了分析研究。然后针对传染路由协议 盲目选择中继节点，对数据副本转发没有限制的缺点，提出一种改进协议e p i h t 。 e p i h t 将节点间的历史相遇次数和平均相遇时间间隔等历史信息引入传染路由，并 通过计算来估计节点间的接近程度，将数据副本转发给更靠近于目标节点活动的中 继节点，以达到减少副本转发次数的目的。最后本文在消息摆渡路由的基础上，针 对在无线社会网络中由于普通节点的长距离通信距离有限而无法与消息摆渡节点通 信的问题，提出了一种适用于无线社会网络的路由协议f i m f c n 。f i m f c n 将社 会网络的研究成果应用到无线社会网络的路由设计中去，通过网络中的中心性节点 对数据的中继转发来提高网络性能。 本文选用n s 2 仿真平台对e p i h t 和f i m f c n 方法进行了仿真分析。仿真结 果表明，e p i - h t 和f i m f c n 在提高数据交付率和降低传输时延方面具有良好性能。 关键词：机会网络，传染路由，历史信息，消息摆渡，中心节点 重庆邮电大学硕士论文 摘要 a b s t r a c t a san e ww i r e l e s si n t e r c o n n e c t i o nn e t w o r k ，o p p o r t u n i s t i cn e t w o r kc a nb ew i d e l y u s e di ni n t e r p l a n e t , l a n dm o b i l en e t w o r k sa n dm i l i t a r ya dh o cn e t w o r k s i th a st h e c h a r a c t e r i s t i c so fd i s c o n t i n u o u sl i n kc o n n e c t i o n ，h i g hl a t e n c y , l o wd a t ar a t ea n dl i m i t e d n o d er e s o u r c e s b e c a u s et h ew i r e l e s sl i n kh a st h ef e a t u r eo fr a n d o md i s c o n t i n u i t ya n dt h e c o m m u n i c a t i o nt e r m i n a l sc o u l dn o te s t a b l i s har e l i a b l ee n d - t o - e n dp a t h ，t h et c p i p p r o t o c o lc a l l tw o r ks m o o t h l yo no p p o r t t m i s t i cn e t w o r k a tp r e s e n t ，n e wt e c h n o l o g i e s s u i t a b l ef o rt h eo p p o r t u n i s t i cn e t w o r ka r eo nt h ew a yo fr e s e a r c h , a n dt h er e s e a r c ho f r o u t ep r o t o c o lp l a y sa nq u i t ei m p o r t a n tr o l e t h i sp a p e rw i l lf i r s t l yi n t r o d u c et h ec o n c e p t ，k e yt e c h n o l o g i e s ，c h a r a c t e r i s t i c sa n d a p p l i c a t i o n so fo p p o r t u n i s t i cn e t w o r k , a n dt h e nm a k ead e 印a n a l y s i so fs e v e r a lt y p i c a l r o u t ep r o t o c o l s s e c o n d l y , t oa d d r e s st h ed e f e c t so fe p i d e m i cr o u t ep r o t o c o lb l i n d l y c h o o s i n gr e l a yn o d e sa n dn ol i m i t a t i o no nt r a n s f e r r i n go fd a t ad u p l i c a t e s ，w ep r o p o s ea n e wp r o t o c o lc a l l e d “e p i - h t ”w h i c hc a l c u l a t e sa n de s t i m a t e st h em o t i o na r e ao ft a r g e t n o d eb yt h eh i s t o r i ce n c o u n t e rt i m e sa m o n gn o d e sa n dt h e i ra v e r a g ee n c o u n t e ri n t e r v a l s ， t h e ns e n d sc o p i e so fd a t at ot h ec l o s e rr e l a yn o d eo ft h et a r g e tn o d ei no r d e rt or e d u c et h e t r a n s f e r r i n gn u m b e ro fd u p l i c a t e s a tl a s t ，w ep r o p o s ea n o t h e rr o u t ep r o t o c o lc a l l e d “f i m f - c n w h i c hi ss u i t a b l ef o rw i r e l e s ss o c i a ln e t w o r k t oa d d r e s st h ep r o b l e mo ft h e c o m m u n i c a t i o nf a i l u r eb e t w e e no r d i n a r yn o d ei nt h ew i r e l e s ss o c i a ln e t w o r ka n dt h e m e s s a g ef e r r yw h e nt h et r a n s s m i s s i o nr a n g eo ft h eo r d i n a r yn o d ei sl i m i t e d ，f i m f c n a p p l i c a t i o n st h es t u d i e so fs o c i a ln e t w o r kt ot h ed e s i g no fr o u t i n ga n di m p r o v e st h e p e r f o r m a n c eo f t h en e t w o r kb yt h ec e n t r a ln o d e sr e l a y i n go ft h ed a t a i nt h i sp a p e r , w ec h o s en s - 2a ss i m u l a t i o nt o o lt om a k es i m u l a t i o na n dp e r f o r m a n c e a n a l y s i s f o re p i - h tp r o t o c o la n df i m f c np r o t o c 0 1 s i m u l a t i o nr e s u l t ss h o wt h a t ， e p i h ta n df i m f - c nb o mh a v eag o o dp e r f o r m a n c eo ni m p r o v i n gd a t ad e l i v e r yr a t e a n dr e d u c i n gt r a n s m i s s i o nd e l a y k e y w o r d s ：o p p o r t u n i s t i cn e t w o r k s ，e p i d e m i cr o u t i n g ，h i s t o r i c a li n f o r m a t i o n , m e s s a g e f e r r y , c e n t r a ln o d e7 i i 重庆邮电大学硕士论文第一章绪论 1 1 课题背景 第一章绪论 近年来，以无线方式实现移动终端之间的无线多跳连接的无线互联网络，包括 无线传感器网络( w s n ：w i r e l e s ss e n s o r n e t w o r k s ) l l j 、移动自组织网络( m a n e t ： m o b i l ea dh o en e t w o r k s ) 2 1 、无线局域网( w l a n ) 、星际网络( i p n ：i n t e r p l a n e t ) 【3 】等，已成为无线通信领域的研究热点。与传统的移动通信系统( 如g s m ) 相比， 无线互联网络的通信终端设备既可以产生和处理信息，又可以作为中间设备转发信 息，它的一个重要特征是能够以无线多跳方式实现通信设备间的互联。 近年的研究表明，与传统的有线网络不同，无线互联网络由于拓扑动态变化， 链路带宽有限，节点资源受限等原因，节点间的无线链路连接具有随机间断特性， 这导致网络中的通信终端间无法建立可靠的端到端路径。由于节点间只有在间断连 接的通信时间内才有通信机会，因此我们将这种存在时间离散的通信机会的无线互 联网络称为机会互联网络，或机会网络( o p p o r t u n i s t i cn e t w o r k s ) 。同传统网络相比， 机会网络通信机会的间断性直接影响了网络终端间不能建立可靠的端到端路径。然 而，现在已有的通信体系、路由技术以及拥塞差错控制技术等提出的前提均是“终 端之间存在稳定可靠的端到端路径”这一假设，因此现有的通信协议、机制无法适 用于机会网络。为此，迫切需要研究适用于机会网络的新的关键技术。 在实际的无线网络应用环境中，现有的无线网络也大多存在机会网络的特性， 如节点的移动、障碍的阻挡和电磁干扰、为了达到节能目的的节点周期性休眠等， 都会造成节点间无线链路的随机中断。同时，一些新的应用，如广告信息投放、火 灾预警、偏远地区的移动数据业务等，都可以使用机会网络的通信模式来实现，从 而降低对固有网络设备的依赖性。相信随着机会网络研究的逐渐成熟，机会网络将 会拥有更加广泛的应用，并且有更多项目可以得益于它的发展，我们的生活最终会 与之密不可分。因此，研究适合机会网络的通信协议和机制不仅能够推动无线互联 网络的研究和应用，同时对整个无线通信领域和人类生活都会产生积极影响。 在机会网络的研究领域，机会网络的特点决定了路由问题是研究中的一个关键 问题，本课题基于国家自然科学基金项目( 间断连接无线互联网通信体系及关键技 术研究) 的支持，对适用于机会网络的路由协议展开研究。 重庆邮电大学硕士论文 第一章绪论 1 2 机会网络的概念和连接统计特性 1 2 1 机会网络的概念 机会网络的部分概念来源于早期的延迟容忍网络d t n ( d e l a yt o l e r a n tn e t w o r k ) n 研究，它的一个描述性定义【5 1 是：机会网络是一种不需要源节点和目标节点之间存 在完整链路，利用节点移动带来的相遇机会实现通信的自组织网络。图1 1 是一个机 会网络示意图，t l 时刻源节点蹄望将数据传输给目标节点d ，但s 和d 位于不同的 连通域而没有通信路径，因此，s 首先将数据打包成消息发送给邻居节点3 ，由于3 并没有合适的机会转发下一跳节点，它将消息在本地存储并等待砖输机会，经过一 段时间到达t 2 时刻，节点3 运动到节点4 的通信范围并转发给节点4 ，在t 3 时刻，节点4 将消息传输给目标节点d ，完成数据传输。 ； ! ；! m | 尸一；一i 尸i i 一 i i ； 豸 ；k 图1 1 机会网络不慈图 1 2 2 机会网络的连接统计特性 机会网络的端到端之间不存在完整的链路，我们用“接触( c t ：c o n t a c t ) ”这一 概念来描述机会网络的这种间断连接特性。c t 是指网络中两个节点彼此进入对方 通信半径时的通信机会，它用一个五元组表示，即c t = ( s ，r ，t ，瓦，c ) ，其中s 表示 链路的源节点，r 表述链路的接收节点，互、乏均是时间f 的函数，即正= 乃( t ) ， = t ( f ) ，分别表示s 和r 接触的起始时间和结束时间，c 表示s 到r 在一次接触 中的数据发送速率。 a e 叵堕互二臣堕珥二工i 亟匠工 iiiii b t = 0 i ” 秘通信范围内 在a 通信范围内枷信范围内 卜乙( 捍卜卜乃( 玎) _卜l ( 玎+ 1 ) - 乃( n + 1 ) 瓦( 行) - 个， 、。 、 c 、_ r 1 ， 7 乙( 玎一1 ) ( 疗) 乞( ，z )( 刀+ 1 ) 乞( 刀+ 1 ) f 图1 2 连接时间统计特性图 2 重庆邮电大学硕士论文 第一章绪论 图1 2 对机会网络的连接统计特性作了更详细的描述。其中乃( 以) 表示节点第玎 次接触所持续的时间，即第玎次接触的起始时刻( n ) 和第刀次接触的结束时亥t j t , ( 丹) 的间隔时间，由式( 1 1 ) 表示。 乃( n ) = t e ( n ) - t s ( n ) 刀= 1 ，2 ，3 式( 1 1 ) 瓦f n ) 表示节点实现第n 次接触所需要等待的时间，即第刀一1 次接触的结束时 刻乙( ，l 1 ) 和第门次接触的起始时刻气( 刀) 的间隔时间，由式( 1 2 ) 表示。 瓦( 甩) = ( 以) 一乞( n - i ) 刀= 1 ，2 ，3 式( 1 2 ) z ( ，z ) 表示两节点第疗次接触周期，即两节点第n - 1 次接触结束的时亥t j t , ( n - 1 ) 与第疗次接触结束的时刻乞( ，z ) 的间隔时间。可以推出互( 刀) 也是接触持续时间乃( 以) 和接触等待时间瓦( ，z ) 之和，由式( 1 3 ) 表示。 瓦( 厅) = t e ( n ) - t , ( n - 1 ) = 乃( ，z ) + 瓦( 疗) 聆= 1 ，2 ，3 式( 1 3 ) 综上所述，机会网络的连接统计特性可由式( 1 4 ) 表示。 f 乃( 甩) = ，p ( 刀) 一( 疗) ， 瓦( ，z ) = ( n ) - t , ( n - 1 ) 甩= 1 ，2 ，3 式( 1 4 ) 【乃( 甩) = 乙( 刀) 一乙( n - 1 ) = 乃( ，z ) + 瓦( n ) 1 3 机会网络体系结构 跟机会网络相关的研究是星际网络( i p n ：i n t e r p l a n e t ) ，t f 下属的研究小组 d t n r g 针对星际网络无线链路周期间断性的特点，在2 0 0 3 年提出一种机会网络体 系结构【6 】，如图1 3 所示： 应用层应用层 传输层 网络层 链路层 物理层 区域1 传输层 网络层 链路层 物理层 区域2 传输层 网络层 链路层 物理层 区域3 传输层 网络层 链路层 物理层 区域4 图1 3 基于b u n d l e 层的机会网络体系结构 与传统的t c p i p 通信体系不同的是，这种新型通信体系增加了一个新的协议层 b u n d l e 层。b u n d l e 层位于传输层之上，应用层之下，该层的协议数据单元( p d u ： p r o t o c o ld a t a 嘣t ) 可以是任意长的消息( 也称为b u n d l e ) 。b u n d l e 采用面向异步消 息传输模式，允许消息长期储存在中间节点的永久介质中，直到被投递到目的节点。 这种基于“存储转发 的体系结构，在每个特定区域网络都能够使用已有的全 3 重庆邮电大学硕士论文 第章绪论 部协议以达到最优的性能，b u n d l e 层提供了一种新的标准方式使得两种不同协议可 以在特定区域网络环境的边界上进行转换，并有效地实现了一个可以通用的应用层 网关架构，为任意数量的应用程序服务。b u n d l e 层与特定区域的底层协议相互配合， 如现有因特网协议等，使得应用程序可以在多个区域之间进行通信 在机会网络体系结构中，b u n d l e 层依靠下层协议的支撑扮演着端到端之间的代 理角色，并且具有重传机制，帮助妥善处理间断性的连接，并在路由到达时为数据 包作最新的保管绑定。同时，b u n d l e 层为数据包提供了保管传输、传输优先级、保 管传输通告、认证、转发数据通告和返回收条6 种服务。 新的机会网络体系结构是对i n t e m e t 的一个根本改变，它采用了全新的设计理念： 用消息代替分组、以可靠安全的h o p - b y - h o p 通信取代了e n d t o e n d 通信、用基于名 称的路由取代基于地址的路由以及用局部连接网络代替全网连接网络。机会网络体 系结构可以很容易地与i n t e r a c t 保持兼容并覆盖子其上。 1 4 机会网络的关键技术及相关研究成果 影响机会网络正常运行的关键技术有很多，目前包括路由、传输协议、节点移 动模型、安全等技术都是学术界主要关注的热点，在这些方面的研究虽然时间较短， 但是发展很快，近年来已经形成了一些研究成果，可为进一步的研究作参考和借鉴。 ( 1 ) 路由技术j 任何组网技术的首要问题都是路由，现有的a dh o e 网络路由协议的前提假设是 端到端之间存在至少一条稳定可靠的通信路径，因此在机会网络中无法运行现有的 路由协议。为了在间断连接的网络中实现通信，机会网络采用了“存储携带转发” 的路由模式，即当去往目的节点的下一跳节点在路由表中不存在时，当前节点将消 息暂存在自己的缓存中，并在当前节点的移动过程中等待适合转发的下一跳节点。 从以上可以看到，设计有效的机会网络路由的关键是为每个消息选择最合适的转发 时机和最优的下一跳转发节点。 在2 0 0 4 年的a c ms i g c o m m 年会中，j a i n 等人首先提出了机会网络的路由问 题【8 1 ，z h a n g 9 帐据机会网络链路间断特性将现有的机会网络路由方法分为两大类： 一类为确知性路由，它假定节点的移动和节点间的连接是已知的，或者是可以预测 的，例如卫星的绕轨运行和节点的周期性休眠。现有的确知性路由主要有：1 ) 修 正的最短路径路由【引，2 ) 基于树的路由【1 0 1 ，3 ) 时空路由【1 1 】。 另一类为随机性路由，它假定网络的链路间断性是随机的尸不可预知的，而目前 大多数机会网络都是随机性间断连接网络，因此随机性路由是机会网络路由研究的 重点。已有的随机性路由主要有：1 ) 扩散路由【1 2 1 ；2 ) 基于节点主动移动路由【1 3 】； 3 ) 基于历史转发消息路由f 1 4 1 ；4 ) 基于模型路由【1 5 】；5 ) 基于编码路由【1 6 1 。 4 重庆邮电大学硕士论文第一章绪论 ( 2 ) 传输协议【7 j 机会网络体系结构中的b u n d l e 层为了有效处理受限网络中链路频繁中断、高延 时和异构性等问题，采用保管传递方法来增强端到端的可靠性传递。保管传递协议 最初由c e r f 等人提出旧，f a l l 等人在文献 1 8 】中进一步描述了保管传递的实施方法 和基本结构，并指出保管传递不同于数据库。消息的的大小、优先级、剩余生存时 间以及节点当前的资源、路由情况、安全情况等是消息是否被接受并保管的决定因 素。 保管传递的目的是能够从一个节点将消息的可靠传递责任转移给另一节点，当 网络拥塞时，机会网络采用转移已保管消息给另一保管人，并丢弃未接受保管或超 时的消息的方法来解决。消息的当前保管人显示在机会网络协议的头字段中，当消 息转移给其他保管人后，该字段被更新。 ( 3 ) 节点移动模型 传统的m a n e t 由于假设网络是全连通的，因此在分析移动模型对网络协议性 能的影响时多是从网络拓扑的角度去考虑，如节点连通度、拓扑连通率等。但是机 会网络要依靠节点移动带来的相遇机会来完成数据传输，而节点的移动模型决定了 节点间的相遇时间分布和相遇概率，因此描述了节点间相遇特征的移动模型对机会 网络研究至关重要。 目前，三个经典的独立同分布移动模型：r a n d o mw a yp o i n t ( g w v ) 1 1 9 】，r a n d o m d i r e c t i o n ( r d ) 和r a n d o mw a 墩1 2 0 正在被许多学者广泛研究，它们都是以相遇 时间( m e e t i n gt i m e ) 和相遇间隔时间( i n t e rm e e t i n gt i m e ) 两个参数来描述节点的相遇特 征。 除了理论模型，一些学者还利用统计的方法研究实际移动模型。麻省理工学院 的r e a l i t ym i n i n g 项目 2 1 】记录了校园中1 0 0 个携带蓝牙手机的职工和学生为期9 个月 的相遇数据和移动轨迹；剑桥大学的h a g g l e 项目 2 2 】通过一些带有蓝牙接口的设备收 集了校园相遇情况；加州大学的w i r e l e s st o p o l o g yd i s c o v e r y 2 3 1 则记录了1 l 周内3 0 0 多个无线p d a 与w i - f i 接入点的相遇数据。研究人员通过在小规模区域内收集节点的 移动轨迹，提出了新的移动模型，但是由于采集数据区域的局限性，这些新模型能 否真实描述节点的移动特征，还需要更多验证。 ( 4 ) 安全和隐私 机会网络只有在节点间出现相遇机会时才能通信，这使得网络节点更加难以控 制，对数据和用户的安全性、隐私性带来更大的挑战。为了解决这一问题，文献 2 4 】 提出了一种可扩展的基于公共密钥技术的保护方案：当一个用户想要使用网络服 务，就被要求用证书注册公共密钥，然后用户会收到一个公共密钥拷贝和一个基本 信用拷贝，它们都是被证书认证标记的。基本信用准许使用一些网络服务，并有一 重庆邮电大学硕士论文 第一章绪论 个期满时间。 1 5 机会网络的特点及应用 1 5 1 机会网络的特点 机会网络端到端之间的链路的不可靠性使得其不同于传统网络，它主要有以下 特征【7 】： 1 ) 高延迟、低数据率 端到端延迟是指端到端传输路径上每一跳的延迟之和。每一跳上的延迟包括通 过相关链路时的传播时间、传输时间、处理时间和排队等待时间。对于机会网络来 说，由于链路间断性连接，等待连接时间往往较长，造成高延迟。同时，机会网络 大多是受限网络，传输速率可能较小，延迟可能较大，且数据率在很大程度上可能 是不对称的。 2 ) 网络分割 在机会网络中，端到端之间的链路间断频繁，网络拓扑经常变化。造成机会网 络间断连接的原因主要两种：确定性事件和随机性事件。例如卫星的按轨道周期性 运动造成的网络断开是可以预测的，而对于节点的随机性移动造成的节点间的断开 与连接，则具有不可预测性。 3 ) 长排队延迟 在机会网络中，排队时间可能是相当大的。这是因为机会网络链路断开频繁， 当节点长期不能与合适的下一跳节点有通信机会时，已经做出的下一跳节点选择可 能无效，消息必须在中间节点储存相当长的时间，或者节点重新选择合适的下一跳 节点以便更好地传输消息。 4 ) 端系统寿命和资源有限 在某些特定的机会网络( 如军事网络和紧急反应网络等) 中，终端节点可能被 放置在敌对或恶劣环境中。在这种情况下，由于环境恶劣和临时性用途，设计者可 能并不期望这些节点拥有较长寿命以及较高的缓存和处理能力。 5 ) 端系统低占空比操作 由于端系统在当初的设计中并不拥有较长的寿命，当它们被放置在缺乏供电系 统的地区时，为了延长整个网络的寿命，必须通过限制占空比去努力节约能量。在 一些情况下，占空比甚至维持在1 。这样的设备定期收集数据，并以一定的低速 率进行数据汇报。 6 重庆邮电大学硕士论文 第一章绪论 1 5 2 机会网络的应用 随着机会网络研究工作的不断深入，机会网络的实用化也取得了较大的进展。 除了空间方面的i p n 等应用之外，研究者还将其尝试用于诸如灾害恢复网络【2 5 】、生 态环境监测网络【2 6 】【2 7 】和普适计算等形形色色的应用项目，可以说机会网络已经开始 走入我们的生活。下面仅列举一些典型的应用： 1 ) 车载网络 配备了短距离无线通信接口的车辆构成的车载机会网络可以广泛应用于路况收 集、交通事故预警、拥堵预报和车辆诊断等，除此之外，利用与路边接入点的通信 机会，车辆可以方便访问因特网和商业应用。麻省理工学院开发的c a r t e l 2 8 】采用 w i f i 或b l u e t o o t h 等通信技术用于车辆收集和发布信息，安装在车辆上的c a r t e l 节点 在两车相遇时可以直接互换数据，同时，也可以通过道路边的接入点将数据传送到 因特网上。 2 ) 手持设备组网 剑桥大学提出的p s n ( p o c k e ts w i t c h e dn e t w o r k ) e 2 9 1 是一种由个人携带的手持设备 组成的机会网络，每个节点既可以通过w i - f i 或g p r s 等接入因特网来进行全局转发 数据，也可以通过人与人的相遇进行局部通信。p s n 研究的目的在于充分利用手持 设备资源和带宽，为用户提供透明的各种连接方式的网络服务。 3 ) 偏远地区网络接入 机会网络技术能够为网络基础设施不够完善的偏远地区提供低廉的非即时可用 的网络服务。d a k n e t o o j 是部署在印度偏远地区的机会网络，它包括：部署在村庄里 的k i o s k 设备、公交车辆上的移动接入设备( m a p ) 以及城镇中已连接互联网的a p 设备。这些设备之间通过w i f i 接口通信。村民通过手持设备与k i o s k 交换数据， k i o s k 设备在公交车经过时再与其上的m a p 交换数据，最后当公交车到达城镇后， m a p 通过a p 连接n i n t e m e t 上传或下载数据。 4 ) 野生动物监测 z e b r a n e t t 3 1 】是由普林斯顿大学设计的追踪草原斑马的机会网络。该系统通过安 装在斑马脖子上的传感器收集斑马的迁徙数据，并在斑马相遇时交换数据。s w i m e 3 2 是一个监视鲸鱼海底活动的机会网络。镶嵌在鲸鱼身上的特殊t a g 周期性地采集数 据，当两头鲸鱼相遇时，它们通过t a g 相互交换数据，因此数据通过鲸鱼的移动被 复制到不同的鲸鱼上，直至到达部署在水面上的基站。从以上可以看出，在大范围 的野生动物监测中，机会网络比传统的静态传感器网络更具优势。 5 ) 战地自组网络 这类网络的节点被部署在战场收集情报，但是由于节点移动，战场恶劣的自然 7 重庆邮电大学硕士论文 第一章绪论 环境或者敌人故意的人为干扰等因素，节点间的通信链路会随时断开，造成网络分 裂。 1 6 本文工作 本课题基于国家自然科学基金项目的支持，对机会网络路由协议进行研究。本 文共分五章，各章的内容安排如下： 第一章：介绍了本课题的背景，机会网络的概念、连接统计特性、体系结构、 关键技术、特点和相关应用； 第二章：分析机会网络路由协议设计中的关键问题，并对几种具有代表性的路 由协议作了重点介绍； 第三章：通过对机会网络路由协议的深入分析，在传染路由协议的基础上，提 出了一种改进协议e p i - h t ，并通过n s 2 仿真软件对改进协议进行性能仿真，验证 其优越性； 第四章：针对机会网络的一种新型应用一无线社会网络，将社会网络的一些研 究成果应用到无线社会网络的路由设计中去，提出f i m f c n 路由，并通过仿真验 证其性能； 第五章：总结本文所做工作，提出下一步的研究方向。 8 重庆邮电大学硕士论文第二章机会网络中的路由协议研究 第二章机会网络中的路由协议研究 传统的因特网路由( 如肿、o s p f ) 和移动自组网路由( 如d s r 、a o d v ) 等 路由协议都是在“端到端之间存在至少一条可靠路径 这一前提下才能实现的，但 是机会网络的高延迟、网络分割和端系统能力低下等特点决定了它无法满足上述前 提条件，传统的路由协议已无法适用于机会网络。因此解决机会网络中的路由问题 是现阶段的迫切任务，对整个机会网络的研究工作也有着极为重要的意义。同时， 机会网络的路由研究尚处于起步阶段，未来将前景十分广阔。 在2 0 0 4 年的a c ms i g c o m m 年会中，j a i n s 】等人首次提出了机会网络中的路由 问题，并指出机会网络路由就是确定在一个动态地随时间变化的连通图里，如何使 信息完成端到端地穿越。由于机会网络中节点间的连接时间是离散分布的，这就要 求在研究机会网络路由时需同时考虑节点之间在空间和时间上的连接关系，因此， 机会网络路由传输的目的并不再是选择最小跳数或者最短路径，而是以最小的网络 消耗、最低的网络延迟实现最大化的消息传输的可能性。 2 1 机会网络路由设计的关键问题 从现有的机会网络应用项目可以看出，与传统网络路由协议不同，机会网络的 路由协议需要考虑的问题主要有以下几个【3 3 】： 1 ) 网络节点信息的不确定性 由于网络分割，机会网络中的数据的发送端很难获知网络中其它节点的位置、 移动方向、移动速度等信息。因此，机会网络路由协议需要解决的一个关键问题是： 机会网络中的节点如何在不知道任何目的节点的信息或者不存在到达目的节点的路 径的情况下，选择最合适做下一跳路由节点。比如说：可以根据两节点最近通信的 时间或者节点的历史相遇次数来制定规则。 2 ) 网络开销 与传统的路由协议不同，机会网络路由协议的设计者们往往希望在机会网络的 不同节点中，可以存在一个数据的多个复本( c o p i e so f m e s s a g e ) ，以提高数据传输的 交付率、减少传输时延。但是当节点保存有多个数据的复本时，节点的缓存和网络 带宽的消耗都需要增大。所以，在设计机会网络路由协议时，需要权衡好数据交付 最大化和网络开销最小化之间的矛盾。 3 ) 协议性能的评价 对于机会网络路由协议性能的评价，通常有三个主要参数：数据交付率、平均 9 重庆邮电大学硕士论文第二章机会网络中的路由协议研究 时延和网络开销。其中数据交付率是首要评价参数，在链路连接状态很不稳定的机 会网络中，数据分组传输失败的概率往往高于传统网络，因而，数据交付率是衡量 机会网络路由协议性能最重要的指标。同时，尽管机会网络由于间断连接特性，可 以允许消息有一定的延迟，但是在路由设计时，仍然要求尽可能地降低平均延时。 而以低网络开销实现高效率同样是任何路由设计的追求。除了上述三个参数以外， 路由协议的健壮性、聚敛性和适用性等也是评价其性能好坏的衡量标准。 协议的安全性 在机会网络中，数据从源节点传递到目的节点的路径往往是不固定的，具有随 意性。而对于比较机密的信息来说，需要路由协议可以保证数据安全可靠地传输， 因此，除了经典的加密算法，机会网络路由最好能在数据传输的过程中记录下其所 经过的节点，使上层应用程序和网络中的可信任节点可以借此来判断数据是否经历 了不可信节点，并调整路由表，删除不可信节点。 2 2 现有的机会网络路由协议 机会网络路由协议的研究虽然尚处于起步阶段，但是国内外的研究人员已经提 出了一些适合于不同机会网络应用场景的路由协议。按照协议原理的不同，文献 【5 1 1 3 4 3 5 等对现有的机会网络路由做了不同种类的划分，如先验知识路由、基于模 型的路由、基于复制的路由、基础设施辅助路由和编码路由等。需要指出的是，由 于各个类型之间会有交叉存在，这种协议类型的界定并不需要十分严格。本文根据 需要，将机会网络路由大致分为以下两类：一类是主动路由，另一类是被动路由。 2 2 1 主动路由 在主动路由机制中，路由的设计者在网络中增加了特殊的受控节点，并让它们 主动移动来为其它普通节点提供通信服务。主动路由最有代表性的；黾a m m a r m 等人 所提出的消息摆渡( m f ，m e s s a g ef e r r y i n g ) 【3 6 】网路由。m f 路由为网络增加了一种 特殊的移动节点f e r r y ，称为消息渡船，它被安排在网络中按照固定轨迹运动，并负 责在节点之间的数据传输。m f 方法的实质是在大量随机移动的节点( 普通节点) 中 部署非随机运动的节点( f e r r y 节点) ，通过f e r r y 节点的非随机性移动来更有效地传递 信息。在灾后营救、战场等需要部署稀疏自组网的场景中，该方法可以被很好地应 用。例如，当地震严重摧毁基础通信设施时，搭建临时的自组网络可以及时获取灾 情信息。这时，装备有短距离通信设备的车辆可以用作f e r r y 节点，负责在消息中断 的不同受灾地区采集信息，而先期进入灾区的搜救人员是普通节点，他们可以通过 手机、p d a 等小型通信设备向f e 珂及时传递当地灾情。 1 0 重庆邮电大学硕士论文 第二章机会网络中的路由协议研究 在文献 3 6 】中，a m m a r m 等在网路中的普通节点是固定的情况下对m f 路由进行 了研究，指出f e 邺，节点路由线路的选择决定了网络的吞吐量和时延，并给出一种有 效的计算f 删路的方法。而当普通节点可移动时，作者在文献 3 7 1 q b 提出了两种 m f 路由方法，分别是节点主导的消息摆渡唧，n 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 珊t 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 ) ，下文将介绍它们的 工作过程： 1 ) 节点主导的消息摆渡 在节点主导的消息摆渡( n i m f ) 方法中，f e r r y 节点被设定沿着一条固定的路 由路径移动，并且网络中所有普通节点都知道f e r r y 当前的坐标位置和它的路由路 径。f e r r y 的当前位置可由f e n y 周期性的广播来实现。而f e r r y 的路由路径则既可由 f e r r y - 播给网络中的普通节点，也可以在网络部署时就告知给普通节点。普通节点 在知道 f e r r y 的坐标位置和路由路径后，便可以采取主动移动的方式与v e r r y 接触以 传递信息。图2 1 对n l v l f 的工作过程作了简单介绍。在图2 1 ( a ) 中，f e r r y 沿着一个 固定的路径( 虚线所示) 运动，当源节点s 有消息要传递给目的节点r 时，它从白色圆 圈位置开始移动，到达黑色圆圈位置时与f e r r y 接触，把消息传递给f e r r y 。在图2 1 ( b ) 中，消息的目的节点r 从白色圆圈位置向f c r 巧移动，并在黑色圆圈位置与f e r r y 接触， 这样，通刘- f e r r y 节点的中继，即使在s 和r 之间不存在直接相连的物理链路，来自节 点s 的消息仍然可以被传递给节点r 。 j n 3 n 4j 口 ， 篡罨v 一n 6 n 1s e 钿x e c 掣h a n g e eo ， ， o n 2 。o ( a ) n 5 一 f e r r yr o u t e - 。_ n o d em o v e m e n t 。 r a d i ot r a n s m i s s i o n _ - f e r r y 口n o d e o b e f o r em o v e m e n t口o a f t e rm o v e m e n t 图2 1n i m f 工作过程图 以上介绍了节点主导的消息摆渡方法，但是从中也可以看到这种方法存在的缺 陷：节点工作效率和信息交付率的冲突。在机会网络中，信息的交付率是衡量路由 性能的重要参数，为了成功交付数据信息，n i m f 路由要求普通节点必须离开工作区 域，主动向f e 哪，节点运动，才能完成信息传输。但是在离开的工作区域的这段时间， 普通节点无法完成分配的工作任务，这在一定程度上会降低节点的工作的效率。特 重庆邮电大学硕士论文第二章机会网络中的路由协议研究 别是对于信息采集网来说，这种影响可能是无法忍受的。对于节点工作效率和信息 交付率之间的冲突，虽然可以采取一些方式使之取得一定的平衡，但还是无法从根 本上解决。 2 ) 渡船主导的消息摆渡 在渡船主导的消息摆渡( f i m f ) 方法中，主动移动的节点换成 f e r r y 节点，它 通过向普通节点主动移动来与其交换信息，并假设f e r r y 的可控移动速度比普通节点 快，而普通节点具有传送通信控制信息的长距离通信的能力。 图2 2 描述了f i m f 路由的工作过程。初始时f e r r y 沿着一条固定路径移动并通过 长距离通信广播自己的位置。当普通节点s 通过广播发现f e r r y 在附近并且想与其交 换信息时，它会通过长距离通信发送一个服务请求( s e r v i c er e q u e s t ) 消息给f e r r y ，此 服务请求消息里包含有普通节点自己的坐标位置，如图2 2 ( a ) 所示。当f e r r y 接收到普 通节点的服务请求信息时，它会根据请求信息里的坐标位置改变自己的移动路线去 与普通节点接触。为了正确引导f e r r y 节点移动，节点s 会不时地将自己的新位置通 过位置更新( l o c a t i o nu p d a t e ) 信息来告知f e r r y ，如图2 2 ( b ) 所示。当节点s 和f e r r y , ； 近时，它们会通过无线短距离通信交换信息，如图2 2 ( c ) 。当f e r r y 和节点通信完毕后， f e r r y 会返回原来的路由路径，如图2 。2 ( d ) 。 d r 。u e ：口 。，- 。 7 v l p o d c a a t t e i o 。n i n 2 n 。- o s r o u t e f ， 一 、+ 0 r f - 警 n 2 1 百 n s f r t 、 f e r r yr o b t e -。-“。 m o v e m e n t - r a d i ot r a n s m i s s i o n - - - - - + f e r r y 一口n o d e 0 b e f o r em o v e m e n t口o a f t e rm o v e m e n t 图2 2f i m f i 作过程图 f m i f 和n n 伍的主要区别在于主动移动的不是普通节点而是f e r r y ，以及普通节 点用长距离通信来发送控制消息。但是，由于能量限制或节点本身设计等原因，普 通节点的长距离无线通信可能受到限制而无法覆盖整个网络，因此，只有处于f e n y 1 2 重庆邮电大学硕士论文第二章机会网络中的路由协议研究 附近一定范围内的普通节点才能发送请求服务信息给f e r r y ，这也是f i m f 路由的不足 之处。 除了上述单f e r r y 系统外，文献 3 8 】又提出使用多个f e r r y 节点的路由情况以提高 网络的可靠性和传输效率。但是由于f e r r y 节点之间可能会产生相互影响，所以多 f e r r y 路由设计将更加的复杂。 2 2 2 被动路由 在被动路由机制中，节点不再为了实现与其它节点的通信而主动运动，它们的 通信时机就是节点随机运动时的相遇时刻。由于不再严格要求节点可控，这种路由 机制具有更广阔的应用空间。下文将介绍几种典型的被动路由。 1 ) 传染路由 最初的传染路由( e p i d e m i cr o u t i n g ) 1 3 9 】算法是v a h d a t 等人提出的。传染路由 要求每个节点都维护一个缓存队列，当节点相遇时，交换对方没有保存的信息。它 实质上是一种洪泛算法，通过节点向所有相遇的邻居节点的转发，最终使相关信息 被网络中的全部节点保存，包括信息的目的节点。因此，在资源不受限的情况下， 传染路由在任何机会网络场景下都有最优的路由性能。 传染路由的基本思想 网络中的每一个节点的缓存队列中储存有要发送的数据( m e s s a g e s ) ， s v ( s u m m a r yv e c t o r ) 是这些数据集合的摘要向量，当两个节点相遇( 彼此进入对方的通信 范围) 时