（计算机应用技术专业论文）机会网络中带有确认机制的多副本路由协议的研究与实现.pdf

-tbhfi_孽 d i s s e r t a t i o nf o rm a s t e rd e g r e ei n2 0l l f f | i | i j l | f i f 舢| | f | f | i j i j f j i j 舢嗍 y 18 4 6 5 2 7 s c h o o lc o d e ：1 0 2 6 9 ea s tc h i n an o r m a l u n i v e r s i t y t h er e s e a r c ha n d i m p l e m e n t a t i o no f m u l t i p l e co p yr o u t i n g p r o t o c o lw i t h 。a c k n o 但e d g m e n t m e c h a s i mi no p p o r t u n i s t i c n e t w o r k s d e p a i 之t m e n t ： g q 卫刭巳坠曼! s 堡i 星坠鱼曼鱼垒亟i 叟曼垒塾q ! q g y m a j o r ： q 磐卫坠l 丛p p ! i q 煎i q 塾：曼q 鱼q ! q g y s p e c i a l i t y ： q 望业坠! 丛盟曼! 堕q 然 t u t o r ： 翊：! q 夏堕k 曼s h 曼旦 s t u d e n t ： 里曼盟g 巡坌塾g o c t o b e r ，2 0 l o 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文机会网络中带有确认机制的多副本路由协议的研 究与实现，是在华东师范大学攻读够左博士( 请勾选) 学位期间，在导师的指导下进 行的研究工作及取得的研究成果。除文中已经注明引用的内容外，本论文不包含其他个 人已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文 中作了明确说明并表示谢意。 作者签名： 薹 h 鼍 日期：砷年f1 月歼日 华东师范大学学位论文著作权使用声明 机会网络中带有确认机制的多副本路由协议的研究与实现系本人在华东师范大 学攻读学位期间在导师指导下完成的硒壬博士( 请勾选) 学位论文，本论文的研究成果 归华东师范大学所有。本人同意华东师范大学根据相关规定保留和使用此学位论文，并 向主管部门和相关机构如国家图书馆、中信所和“知网”送交学位论文的印刷版和电子 版；允许学位论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位论 文加入全国博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇 编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于( 请勾选) () 1 经华东师范大学相关部门审查核定的“内部”或“涉密 学位论文宰， 于 年月日解密，解密后适用上述授权。 本人签名圣：墼 如肜年f1 月2 牛日 “涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位 论文( 需附获批的华东师范大学研究生申请学位论文“涉密”审批表方为有效) ，未经上 述部门审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适用 上述授权) 。 王蓬硕士学位论文答辩委员会成员名单 姓名职称单位备注 邵时副教授华东师范大学主席 王能教授华东师范大学 张卫教授华东师范大学 华东师范大学硕士学位论文 摘要 摘要 机会网络是传统移动自组织网络的一种重要的演变，在机会网络中，由于节 点的移动，网络稀疏或者信号衰减等原因，无法保证通信源节点和目的节点之间 存在一条完整的路径。然而应用于传统的移动自组织网络的路由协议要求源节点 和目的节点之间至少存在一条完整的路径，因此这些传统的路由协议无法在机会 网络坏境中工作。对适用于机会网络的路由协议的研究一直是机会网络的研究热 点。 本文首先介绍了机会网络，包括机会网络的概念、发展、目前的研究状况以 及目前的多种实际应用。然后介绍了应用于机会网络单副本路由协议和多副本路 由协议，分别介绍了两类路由协议的概念和特点，并对两类路由协议进行了比较。 本文基于对多副本路由协议的深入分析和研究，指出了当前多副本路由协议存在 的缺陷：缺少对已成功到达目的地的数据报文的确认机制。机会网络的网络特点 决定了网络中的数据报文生存期很长，在原始的多副本路由协议中，当数据报文 成功到达目的节点时，由于缺少确认机制，网络中冗余的数据报文副本会长时间 存在于网络中，这些冗余数据副本会浪费节点的存储空间，并引起节点之间的冗 余的数据交换以及其他一些问题。 针对当前机会网络中的多副本路由协议存在的缺陷，本文提出了带有确认机 制的多副本路由协议。当数据报文成功到达目的节点后，通过确认报文及时清除 网络中存在的其他冗余数据报文副本。带有确认机制的多副本路由协议能够降低 节点存储空间的消耗，降低链路带宽的浪费，提高网络中数据报文成功传输率。 最后，本文通过利用模拟器进行仿真试验，验证确认机制使原始多副本路由协议 性能得到提升。 关键字：移动白组织网络机会网络机会路由路由协议 华东师范大学硕士学位论文 a b s t r a c t a b s t r a c t ， o p p o r t l l n i s 虹cn 酣釉r l 【s a r eo n eo ft h em o s ti m p o r t a i l te v o l u t i 0 船o fm o b i l ea dh o c n 咖o r l 【s h lo 】p p o n u n i s 缸n 神l r o r k s ，d u et on o d a lm o b i l i 够，l o wd 饥s 时，1 0 s s yl i i 此e t c m 锻ei s n og i l a r a n t e et h a ta 血l l yc o n n e c t e dp a t hb 前w e 吼s o u r c e 觚dd e s t i n a t i o ne x i t s h o w e v e r t l l e r o u t i i l gp r o t o c o l su s c di n 仃a d i t i o n a lm o b i l ea dh o cn e t 、o r ! k s 确q u i r ea tl e 弱t0 n ep a t he x i s 恤g 劬ms o u r c et od e s t i n a t i o nn o d e s h ic o n s e q u e i l c e ，t l l e s ep m t o c o l sc 锄n o tw o r ki no l p o r n j n i s t i c n e t w o r k se n “r o n m e n t r e s e a r c h0 nm er o u t i i l gp r o t o c o l s 印p l i e di no p p o r t i m i s t i cn e 似o r l ( si s a l w a y st h eh o ti i l v e s t i g a t i o ni no p p o r t u n i s t i c n e t w o r ：l 【s h lt h i sp a p w ef i r s n yi n 仃o d u c eo p p o n u n i s t i cn e t w o r k s ，i n c l u d i i l gc o n c 印t ，d e v e l o p m e n t ， c u “饥tr e s e a r c hs i m a t i o n 锄dp r a c t i c a la p p l i c a t i o n s a f 锄w a r d s ，、他p r e s 饥tt h es i n g l e - c o p y 锄d m u l t i p l e c o p yr o u t i n gp r o t o c o l st h a ta p p l i e di l lo p p o r h m i s t i cn e 柳o r k s w e i n t r o d u c et h ec o n c e p t 锄dc h a r a c 衄o ft h e 柳oc a t e g o r i e sr e s p e c t i v e l ya i l dm a k eac o m p 撕s o nb e 研e 饥t h e m b a s e do n m ei n t 饥s i v es t l l d ya n da n a l y s i s ，w ei d e n t i 匆t h ed e f e c to ft h e 舢l t i p l e - c o p yr o u t i n gp r o t o c o l s ： l a c ko fa c k n o w l e d 鲫e n tm e c h a n i s mf o r l ed a t a g m mt h a th a sb e e nd e l i v e 化dt om ed e s t i n a t i o n s u c c e s s 如l l y t h ep r o p e n i e so fo p p o 咖n i s t i cn e t w o r k sd e t 锄i n et h a t l et i m et 0 l i v eo ft h e d a t a 黟唧i sq u i t el o n g h lo r i g i n a lm u l t i p l e c o p yr o u t i n gp m t o c o l s ，b e c a u s eo ft h e l a c k o f a c k n o w l e d 舯e n t ，w h e i lad a t a g r a ma r t i v e sa ti t sd e s t i n a t i o n ，m e 坞d u n d a i l tc o p i 销o f t h ed a t a g r a m w i l ls t a yi l lt h en e t w o r kf o ral o n gt i m e t 1 l e s es t a l ec o p i e sw i l l 、a s t et l l eb u f f 酹s p a c eo fn o d e s ； i n c u r 幽d a i l td a t ae xc _ h a i l g ea n do t h c rp 耐b 1 锄s a g a i n s tt h ed r a w b a c ko ft h ec i l r r e n ti n u l t i p l e - c o p yr o u t i n gp r o t o c o l ，i l lt h i sp a p 、p r o p o s e m em u l t i p l e c o p y 嘶t ha c k n o w l e i l g m e n tm e c h a n i s m w h 铋m ed a t a g r a m 硎v e sa tm ed e s t i n a t i o n g u c c 鹤s f i l l l y ，t h eo m e rr e d u n d a n tc o p i e s 、埔ub er e r n o v i e d 矗0 mt h en e 嘲o r ki nt i i i l em r o u g ht h e a c h o w l e d g m e n t s 7 r h ei n u n i p l e - c o p yr o u t i n g “t l la c k i l o w l e d 舯e l l tm e c h 锄i s m 丽u 硎u c et h e c s u m p t i o no fn l eb u f f 瓦d e c r e a s et h ew 邪t co fl i r d ( b 锄d w i d t ha i l di m p r o v et h e s u r c 骼s p r o b a b i l i 够o fd a t a 黟a mt o b ed e l i v e r e d f i n a l l y ，t h r o u g hm es i m u l a t i o n ，w ev e r i 矽m a tt h e a c h o w l e d g m e n tm e c h a n i s me 妇【l l a n c e t h ep e r f o m 锄c eo fm eo r i g i i l a li n u l t i p l e - c o p yr o u t i i l g p r o t o c 0 1 k - e yw o r d ：m o b i l ea dh o cn e 咐o r k ，o p p o m l i l i s t i cn e 咐o r k ，o p p o 咖n i s t i c r o u t i l l 岛r o u t i i l gp r o t o c o l 华东师范大学硕+ 学位论文 目录 目录 第一章绪论1 1 1 研究背景一l 1 1 1 机会网络的提出一l 1 1 2 机会网络的特点一3 1 1 3 机会网络与延时容忍网络4 1 2 机会网络研究现状一5 1 3 研究内容一6 1 4 本文贡献7 1 5 本文结构7 第二章机会网络中的路由协议8 2 1 概j 苤一8 2 1 1 传统i i l t e m e t 中的路由协议8 2 1 2 传统m a n e t 中的路由协议8 2 1 3 机会网络中的路由协议8 2 2 移动模型的介绍9 2 2 1 独立同分布的理论移动模型1 0 2 2 2 基于社区的移动模型1 0 2 2 3 基丁二统计的实际移动模型ll 2 3 单副本路由协议1 2 2 4 多副本路由协议1 4 2 4 1 基丁二泛洪的多副本路由协议1 4 2 4 2 条件泛洪的多副本路由协议( 受限泛洪) 1 5 2 4 3 基于同定数目副本的多副本路由协议1 6 2 5 单副本与多副本路由协议的比较1 6 第三章带有确认机制的多副本路由协议1 8 3 1 缺少确认机制的多副本路由协议一1 8 3 2 确认机制的基本概念和原理1 8 3 2 1 传统h l t e n i e t 中的确认机制1 9 3 2 2 机会网络中的确认机制2 0 3 3 确认机制的实现2 0 3 3 1 综述2 0 3 3 2 确认机制对性能的影响2 6 3 4 协议的具体实现一2 7 3 4 1e p i d 啪i c 协议2 7 3 4 2p r o p h e t 协议2 9 3 4 3s p r a y 锄dw a i t 协议3 0 3 5 三种协议的比较3l 第四章实验与结果3 3 4 1 实验概述。3 3 华东师范大学硕士学位论文 目录 4 2 实验环境描述3 3 4 3 实验性能指标参数3 4 4 4 实验结果3 5 4 4 1 数据报文成功传输概率3 5 4 4 2 链路带宽开销3 6 4 4 3 传输延时3 7 4 4 4 数据报文平均存储时间3 8 4 4 5 能量消耗3 9 4 4 6 存储空间占用4 0 4 7 结论4 0 第五章总结与展望4 2 5 1 研究内容总结4 2 5 2 研究成果总结。4 2 5 3 进一步的上作展望。4 3 攻读硕士学位期间参与的项目及发表的学术论文4 4 参考文献4 5 致谢4 8 2 华东师范大学硕士学位论文第一章序论 1 1 研究背景 1 1 1 机会网络的提出 第一章绪论 传统的i n t c m e t 发展到今天已显示出其强大的生命力，它利用t c p i p 协议 进行网际互连，将世界各地众多的物理网路连接在一起，在各个方面给人们的生 活带来便利。在传统的i n t 锄e t 发展的同时，无线移动通信网络也在迅猛发展， 从第一代移动通信系统到现在的3 g 网络以及处于研究中的4 g 网络，移动通信 系统在提供语音服务的同时，也将提供各种各样的数据通信服务。目前，对于位 于不同城市的两个用户来说，他们之间发送一封电子邮件可以通过以下几种方式 完成( 假设邮件发送方为用户a ，邮件接收方为用户b ) ，我们具体描述用户a 的接入方式，用户b 可以采用这些接入方式中的任何一种。 图卜1 用户接入方式 目前最普遍的方式如图1 1 所示，用户a 可能位于家中、办公室或其他场所， 通过有线连接接入本地i n t 锄e t 服务提供商( i s p ) 提供的有线网络，再通过本地 i s p 的网关连接到i n t e n l e t ，用户a 发出的电子邮件将通过有线网络，逐步被路 由到用户b 。 如图1 1 所示，除了使用有线连接接入本地i s p 提供的有线网络以外，用户 a 也可能是使用带有无线网卡的笔记本利用8 0 2 1 1 无线连接技术，通过本地i s p 提供的无线访问接点( a p ) ，连接到有线网络，继而连接到i n t e m e t ，用户a 发 出的电子邮件将通过无线连接与有线连接的结合最终到达用户b 。 除了使用传统的n e m e t 之外，移动通信系统也能够完成用户a 的要求，如 华东师范人学硕i ：学位论文第一章序论 图1 1 所示，用户a 可以利用自己的手机，通过所在小区的基站接入电信运营商 部署的有线网络，用户a 发出的电子邮件将利用移动通信系统提供的数据通信 服务最终到达用户b 。 在以上的实现方式中，用户a 与用户b 之间的数据通信完全依赖于已部署 的网络基础设施，这些基础设施是进行数据通信的必要条件，然而在一些实际的 情况下，无法为通信双方部署这些网络的基础设施。比如自然灾害使得基础设施 遭到破坏，或者一些经济落后的国家没有财力部署这些基础设施，或者一些偏远 地区由于地理原因而无法部署这些基础设置。在上述几种方式中，缺少网络基础 设施将使得数据通信失败。 大量低成本，具有短距离无线通信能力的智能设备的出现，使得在不具备网 络基础设施的情况下实现数据通信成为可能。用户a 可以通过以下的描述将电 子邮件发送给用户b 。 j 图1 _ 2 机会网络示例图 如图1 2 所示，位于最左边的用户a 位于家中或者办公室，而此时经过的公 交车上的乘客持有能进行无线通信的手持设备，用户a 利用无线连接，首先将 电子邮件发送给公交车上的某个乘客，当公交车上的乘客下车后，电子邮件又被 转发给骑自行车经过的人，如图1 2 所示，该电子邮件相继被转发给其他人，最 终到达位于最右边的用户b 。 在上述的通信方式中，用户a 与用户b 之间始终不存在一条完整的通信链 路，用户a 发送的电子邮件，利用人们的移动形成的相遇机会到达最终目的节 点，这种新兴的通信方式称为机会通信，参与数据通信的节点所组成的网络被称 为机会网络。 目前机会网络还没有一个统一的定义，本文通过综合现有文献分析机会网络 特点，采用文献【l 】给出的描述性定义：机会网络是指利用网络中的节点的移 动带来的相遇机会实现数据通信的自组织网络，网络中不需要源节点和目的节点 之间存在完整的数据链路。机会网络中的节点不是被统一部署的，网络规模和节 2 华东师范大学硕士学位论文第一章序论 点初始位置未进行预先设置，源节点和目的节点之间的路径事先并不能确定是否 存在。图l 一3 描述了机会网络的一般性概念。在第一步中，网络中的节点a 有一 个数据报文要发往目的地节点d ，而源节点a 和目的节点d 不在通信范围之内， 不能进行直接地数据通信。在第二步中，节点a 和节点b 相遇，节点a 将数据 报文转发给节点b ，在第三步中，节点b 和节点c 进入通信范围，节点b 将数 据报文转发给节点c ，最后一步中，节点c 与目的节点d 相遇，数据报文成功 地被转发给目的节点d 。在该示意图中，源节点a 和目的节点d 始终没有相遇， 但由于节点的移动带来的与其他节点的相遇机会，最终数据报文被成功地递交给 目的节点。 1 1 2 机会网络的特点 图卜3 机会网络概念示意图 机会网络被看作是传统的移动自组织网络( m a n e t ) 的一种重要演变，因 此机会网络具有传统m a n e t 的普遍特点，以下是机会网络与传统m a n e t 的 共有的特点。 ( 1 ) 无中心性。网络中所有节点的地位平等，即节点组成的是一个对等式 网络，网络没有严格的控制中心。节点可以随时加入和离开网络，任 何节点的故障不会影响整个网络的运行。 ( 2 )自组织性。网络中的节点可以在任何时刻、任何地点不需要现有信息 3 华东师范大学硕十学位论义第一章序论 基础网络设施的支持，就能够快速构建起一个移动通信网络。 ( 3 ) 多跳路由。网络中的每一个节点扮演着多个角色，具有多种功能，它 们既可以是终端或者服务器，又可以充当路由器。 ( 4 ) 拓扑结构的动态性。网络中的节点以任意速度和任意方向在网络中移 动，同时，由于节点的无线发送装置发送功率的变化、无线信道间的 互相干扰因素、地形等综合因素的影响，节点之间形成的网络拓扑结 构随时可能发生变化，而且变化的方式和速度都是不可预测的。 然而，机会网络又不同于传统的m a n e t ，相对于传统的m a n e t ，机会网 络具有以下独特的特征。 ( 1 ) 无法保证源节点和目的节点之问存在一条完整的通信路径，网络和链 路经常频繁地断开和重新连接。 ( 2 ) 节点之间的通信依赖于节点移动带来的相遇机会。 由于机会网络独特的特征，使得应用于传统m a n e t 中的路由协议无法在机 会网络中正常工作，本文的研究重点就在于应用于机会网络的多副本路由协议， 本文将在第二章详细描述。 1 1 3 机会网络与延时容忍网络 机会网络中的许多概念来源于对延时容忍网络【2 】( d e l a yt o l e r a i l tn 咖o r k ， d t n ) 的研究，延时容忍网络最初是由延时容忍网络研究组提出，主要应用于星 际网络i p n 吲( i n t e r p l a n e t a r yn e 铆o r l ( ) 的通信，其主要目标是实现具有间歇性连 通、延迟大、错误率高等通信特征的不同网络的互联和互操作，如互联i n t c n l e t 和 传感器网络、移动自组织网络等。d t n 架构由多个独立的网络组成，这些独立 的网络称为d t n 域。在每个独立的d t n 域中，使用最适合该域的网络架构， 通信方式，技术手段，通信协议栈等。但d t n 域之间只存在偶然的通信机会， 这些通信机会可以是人为安排的可预知的，也可以是随机的。域间的网关负责不 同域之间的互连通信，因此d t n 中的各个域在网关处分离，即网络的分离点是 可知的。当去往目标d t n 域的链路存在时，网关转发消息，否则，将消息存储 在本地持久存储器中等待可用链路。d t n 的网络架构中，在传统的传输层上添 加了一个束层( b u n d l el a y e r ) ，用来管理不同域之间的端到端的数据传输。 实际上，对于机会网络与延时容忍网络具有明确区分的定义现在还未达成一 致，在一些文献当中可以将这两个概念互换。本文采用文献【4 】的描述，将机 4 华东师范大学硕十学位论文第一章序论 会网络看作是比延时容忍网络更具一般性，并且包含了延时容忍网络的概念。 1 2 机会网络研究现状 机会网络自从出现以来得到了极大的研究关注，目前的研究热点主要集中在 以下几个方面： ( 1 ) 路由协议的研究。路由协议一直是机会网络中的研究重点，网络中的 路由协议要完成将数据报文成功地传输到目的节点的任务，同时，还 要尽可能减小传输延时，减小对网络节点内存的消耗，减小对网络带 宽的消耗。研究人员正在努力研究开发满足上述要求的路由协议并取 得了一定的成果，本文第二章详细介绍机会网络中的路由协议。 ( 2 ) 移动模型的研究【列。移动模型是指网络中的节点移动方式，节点的移 动方式对于网络中的数据通信具有重要的影响。不同的应用环境下， 节点可能具有不同的移动方式，节点的移动可能是随机的，也可能是 具有一定规律的。节点的移动模型对于机会网络中的路由协议的设计 具有一定的指导意义。本文第二章将详细介绍机会网络中节点的移动 模型。 ( 3 ) 安全性研究。安全性的保证是整个网络应用的前提，所以随着机会网 络其他方面的研究发展，以及机会网络的实际部署，安全性方面的研 究得到了逐步关注。目前机会网络中的安全机制研究还处于起步阶 段。 经过近几年的研究发展，机会网络目f i i f 已经有了多种实际的应用，下面是当 前已经部署的机会网络的应用。 ( 1 ) z e b r a n e t 【6 】 z e b r a n e t 是由基站和安装在斑马脖子上的低功耗传感器组成，用来追踪研究 非洲草原斑马的机会网络，该网络由普林斯顿大学设计，并在肯尼亚草原上部署。 在该机会网络中传感器节点收集斑马的移动迁徙数据，并且在与其他斑马相遇 时，传感器节点之间进行数据交换。网络中的基站可以是固定的，当斑马靠近基 站时，传感器节点将数据转发到基站上，数据再通过有线网络到达研究中心。固 定的基站和有线网络带来很高的研究成本，所以网络中可以采用移动基站。每隔 一定的时间研究人员携带移动基站穿越追踪区域进行数据的收集。 ( 2 ) h a g 西e 【7 】 华东师范人学硕匕学位论文 第一章序论 h a g g l e 项目由英国剑桥大学和1 1 1 t e l 研究院共同提出和研究。该项目的研究 重点是被称为p s n 8 】( p o c k e ts w i t c h e dn e t w o r k s ) 的机会网络，该网络是由日常 生活中的手持设备组成，比如手机、p d a 、笔记本电脑等。目前人们随身携带的 手持设备都是通过w i f i 或者g p r s 等接入i i l t e m e t 进行数据交换，而在h a g 酉e 中，手持设备节点也可以利用人们之间的相遇带来的通信机会进行数据交换。 h a g 西e 的研究目标旨在对现有的网络的扩展或者当缺少网络基础设施时作为一 种替代。 ( 3 ) d a k n e t 【9 】 d a k n e t 是由美国麻省理工学院开发，为印度偏远地区提供互联网服务的机 会网络。在该网络中，偏远的村庄部署了大量被称为k i o s k 的设备，村庄的居民 可以利用手持设备与k i o s k 设备交换数据。比较发达的城镇中有用于连接互联网 的a p ( a c c e s sp o i n t ) 设备。同时在偏远的村庄与比较发达的城镇之问有许多公 交车或者其他类型的交通工具往返，这些交通工具上都装有m a p ( m o b i l ea c c e s s p o i n t ) 设备，当交通工具位于偏远的村庄时，m a p 设备能够与k i o s k 设备进行 数据交换，收集村民的数据。当交通工具到达城镇时，m a p 设备能够通过a p 设备与互联网进行数据交换，上传收集到的村民的数据或者按照要求下载数据。 1 3 研究内容 本文研究的机会网络中，网络中的数据报文目的地址是单播地址，许多机会 网络的应用场景符合这个特点。 ( 1 )由移动传感器节点组成的用于野外环境监测或者野生动物研究的机 会网络，每个传感器节点生成的数据报文，目的地址都是最终基站的 地址，网络中采用单播数据报文。 ( 2 )由生活中的手持设备组成的用于实现人们之间电子邮件通信或者文 件共享的机会网络，网络中采用单播数据报文。 本文主要研究具有以上特点的机会网络应用场景中的多副本路由协议的确 认机制，包括e p i d e m i c 协议【1 0 1 ，p r o p h e t 协谢1 1 1 ，s p r a ya i l dw a i t 【1 2 1 协议确认 机制的具体实现，研究加入确认机制后对这些路由协议在各个方面性能的影响。 并且本文将在符合人们日常生活的移动模型中进行仿真实验，比较改进的路由协 议与原路由协议的性能的同时，对三种多副本路由协议进行性能比较，最后对于 在某一具体场景下应该选择何种多副本路由协议给出建议。 6 华东师范大学硕士学位论文第一章序论 1 4 本文贡献 本文实现了应用于机会网络中的多副本路由协议的确认机制，通过引入确认 机制，提高了机会网络中的数据报文成功传输概率，节省了网络中节点的内存消 耗，降低了网络带宽的浪费，并且通过符合人们实际生活轨迹的移动模型下的实 验，分析比较了三种多副本路由协议的性能，并在具体应用场景下应该使用何种 多副本路由协议给出了建议。 1 5 本文结构 本文第二章介绍了应用于机会网络中的路由协议，将路由协议分为单副本路 由协议和多副本路由协议两类，分析了这两类路由协议的特点，并对这两类路由 协议进行了简单比较。 本文第三章首先分析了当前多副本路由协议存在的缺陷，提出了应用于多副 本路由协议中的确认机制。然后介绍了确认机制的具体概念，分析了确认机制在 多副本路由协议中的具体实现，最后分析了引入确认机制在不同方面对性能的影 响。 本文第四章针对改进的多副本路由协议进行仿真实验，本文采用了符合人们 日常生活的移动模型，并从对多个实验参数进行了不同的取值，最后对实验结果 进行了详细的对比分析。 本文第五章对全文进行了总结并提出了未来的研究方向和工作。 7 f 仁东师范火学硕i ：学位论文 第二章机会网络中的路由协议 2 1 概述 第二章机会网络中的路由协议 路由协议的研究是任何组网技术的首要问题。在机会网络中由于网络稀疏， 节点移动和通信范围等因素的影响，有可能会出现网络分裂或节点脱网，源节点 和目的节点之间不一定存在完整的端到端路径，这为路由协议的设计带来巨大的 挑战。 2 1 1 传统i n t e r n e t 中的路由协议 应用于传统的i n t e m e t 中的路由协议，比如选路信息防议( r i p ) ，开放最 短路径优先协议( o s p f ) 和中间系统到中间系统协议( i s i s ) ，这些路由协议 的目的是在每个节点上建议一张稳定的路由表，当数据报文到达时，通过查询路 由表决定如何转发数据报文，所以这些路由协议也被称为表驱动路由协议。在传 统的有线网络中，稳定的节点邻居关系，低链路故障率和低链路数据错误率，使 得这些路由协议能够快速高效地在每个节点建立维护一张稳定的路由表。 2 1 2 传统m a n e t 中的路由协议 传统的移动自组织网络( m o b i l ea d - h o cn e t w o r k s ，m a n e t ) 使用表驱动 路由协议或者按需路由协议。表驱动路由协议如d s d v 【1 3 】( d e s t i n a t i o n - s e q u e n c e d d i s t a l l c e 。v e c t o rr o u t i n g ) ，它类似于有线网络中的路由协议，通过在每个节点建 立和维护一张路由表，当有数据报文要发送时，通过查询路由表决定如何转发数 据报文。按需驱动的路由协议如a o d v 【1 4 】( a dh o co n d 伽a 1 1 dd i s t a n c ev e c t o r r 0 u t i n g ，a o d v ) 和d s r 【1 5 】( d y i l 锄i cs o u r c er o u t i n g ，d s r ) ，在按需驱动的路 由协议中，当某个节点要发送数据报文时，才在网络中发起路由查找过程，找到 相应的路由。 2 1 3 机会网络中的路由协议 机会网络的特点决定了上述传统h l t e m e t 和传统m a n e t 中使用的路由协议 无法在机会网络中应用。首先，机会网络中的网络节点移动频繁，节点甚至有高 华东师范大学硕十学位论文第二章机会网络中的路由协议 移动速度的特点，决定了网络拓扑的频繁改变，如果使用表驱动路由协议，则建 立和维护路由表将带来很大的开销，甚至不具有可行性。其次，机会网络中的节 点由于移动可能会形成多个区域，而各个区域彼此孤立，通信的源节点和目的节 点之间不存在一条完整的通信链路，因此使用按需驱动路由协议，源节点将无法 得到一条到目的节点的路由。 由上面的分析可得，机会网络中必须采用新的路由机制来实现数据通信。目 前机会网络中的路由协议主要采用“存储一携带一转发”机制，即网络中的节点生 成或者接收到一个数据报文，而此时不存在到达目的节点的路径或者不存在合适 的下一跳转发节点，则当前节点将数据报文保存在存储空间中，并随着当前节点 的移动携带着数据报文寻找合适的转发机会。这种机制能够克服网络分裂和端到 端路径不存在的困难，依靠节点的运动和位置改变把数据报文送到目的节点。 在“存储携带转发”机制中，数据报文大部分时间都被缓存在中间节点上， 以等待合适的转发机会，因此，网络中数据传输将经历很大的延时，这要求应用 于机会网络中的应用程序必须具有延时容忍的特征，即为了保证数据报文能够成 功到达目的节点，数据报文要有足够长的生存期( t i m et ol i v e ，t t l ) 。 由以上分析可得，机会网络中设计路由协议的关键问题是针对每个数据报文 确定最好的下一跳转发节点和选择合适的转发时机，使数据报文高效快速地向目 的节点靠近。 2 2 移动模型的介绍 节点的移动模型是指节点的移动路线规律，移动速度，静止时间等特征的变 化模式，移动模型是自组织网络的基础研究之一，并且已经广泛应用于自组织网 络协议性能的分析和评价。传统的m a n e t 一般从网络拓扑角度去分析移动模 型对协议性能的影响，因为传统的m a n e t 假设网络是全连通的，节点的移动对 路由层以上的协议是“屏蔽 的，比如从拓扑连通率、节点连通度等分析移动模 型对性能的影响。而机会网络中的数据传输取决于节点移动带来的相遇机会，而 节点之间的的相遇概率和相遇时间分布是由节点的移动模型决定的，因此机会网 络中的移动模型研究是以刻画节点相遇特征为核心的。相比于传统的m a n e t ， 在机会网络中对移动模型的研究更加重要。在介绍机会网络中的路由协议之前， 本文先介绍机会网络中的节点移动模型。 9 华东师范人学硕 j 学位论文第二章机会网络中的路由协议 2 2 1 独立同分布的理论移动模型 独立同分布移动模型下的节点相遇特征可用两个参数来刻画：相遇时间 ( m e e t i n gt i m e ，简称m t ) 和相遇间隔时间( i n t e rm e e t i n gt i m e ，简称i m t ) 。节点相 遇时间是指两个节点从静止开始到第一次相遇( 进入通信范围) 经过的时间间隔。 节点相遇l 日j 隔时间是指两个节点前后两次相遇的时问间隔。具有代表性的三个独 立同分布移动模型是r a n d o mw a yp o i n t ( r w p ) ，r 锄d o mw a l k ( r w ) 和r a l l d o m d i r e c t i o n 1 7 1 ( r d ) 。文献【1 7 】分别从不同的角度证明了上述三个移动模型的节 点期望相遇时间( e x p e c t e dm e e t i n gt i m e ) 服从指数分布或其尾部服从指数分布， 并基于此分析了多种路由协议的延时性能。文献【1 8 】推导出了r a n d o mw a l k 移动模型下节点期望相遇间隔时问的分布同样服从指数分布。文献【1 9 】推导了 r a n d o md i r e c t i o n 移动模型和r a n d o mw a vp o i n t 移动模型下的节点期望相遇间 隔时间分布，并证明了这两种移动模型下节点相遇时间和相遇间隔时间的尾部分 布具有无记忆性。 2 2 2 基于社区的移动模型 f f 常生活中，由人们所携带的手持设备组成的网络是机会网络的一个主要应 用，对适用于这类场景且便于数学分析的移动模型的研究是机会网络研究的一个 重点。基于社区的移动模型( c o m m u n i t yb a s e dm o d e l ) ，是指由手持设备组成的机 会网络节点的移动具有社区特性。该模型下的节点并不是随机选取移动位置，节 点目的地的选择受以下三种因素影响：1 ) 节点偏好，节点比其他节点更倾向于 去往某个特定位置或遇到特定节点；2 ) 节点异构性，某些节点能够到达所有位 置或者能够遇到所有其他节点；3 ) 行为时变性，节点移动随着时间的推移而发 生变化。m u s o l e s i 等人【2 0 】结合社会网络理论提出了一种基于社区的移动模型。 该模型以节点之间联系的紧密程度为基础，将节点划分在多个在不同区域的社 区，通过计算不同社区对每个节点的吸引力，确定节点是否移动以及朝哪个目标 区域移动。s p y r o p o u l o s 等人提出了时变的社区移动模型。在该模型中每个节 点的工作周期分为正常移动周期和集中移动周期，每个周期内节点随机选择一个 社区作为它的本地社区。每个周期内节点都有两种移动状态：在本地社区内移动 和在其他社区内漫游。节点在本地社区内移动所持续的时间段称为l o c a l 印o c h ， 节点在其他社区内漫游所持续的时间段称为r o 锄i i l g 印o c h 。节点以一定的概率 l o 华东师范大学硕士学位论文第二章机会网络中的路由协议 ( 概率大小由所处的移动周期来确定) 在两个状态之间进行转换，形成一个马尔 可夫链。例如，在集中移动周期内，节点访问本地社区的概率较高。 工作日移动模型【2 2 】( w 0 r k i n gd a ym o v e i i l e n t ，w d m ) 是由芬兰赫尔辛基大 学提出的一种最接近人们日常生活的社区模型。该移动模型主要目的是用来模拟 人们的工作日，人们在一个工作日中可以从事各种各样的活动，所以该模型是由 多个子模型构成的。目前该移动模型实现了三个子模型，描述了日常生活中人们 所处的三种状态：在家中，在上班和晚上下班之后的活动，在三个子模型捕捉了 人们在一个工作日中的大部分行为。在家庭活动子模型中，节点进行短距离的移 动或者静止。在办公活动子模型中，节点首先以一定的速度到达自己的办公桌， 然后静止一段时间，该静止时间服从p a r e t o 分布，静止时间过后，节点在办公 室随机选择一个目的地，移动到该目的地并且再静止一段时间，该时间也服从 p a r e t o 分布，节点重复这样的动作直至下班。在夜晚活动子模型中，节点可能 会在超市购物，可能会在路上行走，或者可能与朋友聚在一起。本文的模拟实验 将采用这种移动模型。 2 2 3 基于统计的实际移动模型 除了对于移动模型的理论研究以外，还可以利用统计方法，通过收集实际环 境中节点的运动轨迹来研究机会网络中节点的移动特征。美