《移动ad hoc网络中文件广播分发算法的研究与实现》由会员分享，可在线阅读，更多相关《移动ad hoc网络中文件广播分发算法的研究与实现（80页珍藏版）》请在金锄头文库上搜索。
1、杭州电子科技大学硕士学位论文 移动A dh o c 网络中文件广 播分发算法的研究与实现 研究生：朱韬 指导教师：陈勤教授 D i s s e r t a t i o nS u b m i t t e dt oH a n g z h o uD i a n z iU n i v e r s i t y f o r t h eD e g r e eo fM a s t e r A S t u d y o nt h e A p p l i c a t i o no f B r o a d c a s t i n g D i s t r i b u t i o nI nt h eA dh o c N
2、e t w o r k s C a n d i d a t e ：T a oZ h u S u P r o f C h e nQ i n s u p e r v i s o r ：P r o C h e n D e c e m b e r ，2 0 1 0 杭州电子科技大学 学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人 或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。 申请学位论文与资料若有不实之处，本人
3、承担一切相关责任。 论文作者签名： 央格日期：匆t1 年1 月串日 学位论文使用授权说明 本人完全了解杭州电子科技大学关于保留和使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属杭州电子科技大学。本人保证 毕业离校后，发表论文或使用论文工作成果时署名单位仍然为杭卅I 电子科技大 学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文 的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密 论文在解密后遵守此规定) 论文作者签名：身 广播技术。影响M A N E T 路由性能的重要原因之一就是缺少简单高效的 广播算法【1 0 1 。主流的路
4、由协议【1 4 1 岳1 8 】可以被分成3 类：主动望d ( p r o a c t i v e ) 、被动 型( r e a c t i v e ) 和混合型。 5 杭州电子科技大学硕士学位论文 主动型路由协议需要每个节点维护全局的拓扑信息，才能保证只要有路由请 求就准备好需要的路径。但是这一类的路由协议也有明显的缺点，比如可扩展性 较低和协议开销较高。 被动型路由协议按照需要计算路径，即每个节点只在需要的时候为了特定的 目的地计算路径。只要拓扑变化没有影响到有效路由，将不会引发路由维护，因 此通信开销比主动型的路由协议低。 第三种类型，只有一部分节点维护局部的拓扑信息，而且路由决策既不是
5、主 动型的也不是被动型的。 但是以上三种路由协议，都不能避免洪泛广播带来的混乱。例如，主动型的 路由协议依靠洪泛广播来转发拓扑更新分组，而被动型路由协议依靠洪泛广播进 行路由发现。 因此不论是基于主动式的路由算法，还是基于被动式的，都需要使用广播的 方式来进行路由选择和节点更新过期的路由信息。除此之外，更重要的是广播技 术也是很多具体应用进行文件广播分发的常用选择，例如将公钥基础设施( P K I ， P u b l i cK e yI n f r a s t r u c t u r e ) 体系【1 9 - 2 1 1 应用于M A N E T 的关键就是如何高效的分发证 书吊销列表( C
6、R L ，C e r t i f i c a t eR e v o c a t i o nL i s t ) 。但是直接简单的泛洪广播将导致广 播风暴( B r o a d c a s ts t o r mp r o b l e m ) 2 2 , 2 3 的产生，直接影响到M A N E T 通信的性能。 为此国外学者提出了通过采用最小连通支配集算法构造虚拟骨干网络的方式一 一虚拟骨干网由属于连通支配集的节点构成，将路由节点的数目减少到虚拟骨干 网中的节点数目。在文件广播分发的过程中，只让处于虚拟骨干网中的节点进行 文件广播分发，大大缓解了广播风暴。 ( 2 ) 动态网络拓扑使得网络需要更加
7、完备的网络管理技术。M A N E T 中节点可 以在一定的区域内自由移动，使得全局网络的拓扑结构随着时间不断的变化，这 给M A N E T 的网络协议设计带来了极大的难度。要求M A N E T 的网络协议需要 对网络的移动特性具有良好的适应能力，还要随着移动节点的加入、离开做出快 速的动态变化，而且在规模较大的网络中，控制开销不能随着网络规模的不断扩 大而剧烈的增长。 1 3 本文主要研究目的和内容 本文的主要研究目的是通过对M A N E T 中的广播问题进行研究，设计一种移 动环境下高效、可靠且可行的文件广播分发协议。 本文的主要工作如下： 1 ) 深入分析了多个现有的最小连通支配集
8、算法，然后针对在规模较大且移动 较频繁的M A N E T 中，构建树形最小支配集缓慢且网络开销大的问题，设计了一 6 杭州电子科技大学硕士学位论文 种基于域的分布式最小连通支配集启发式算法( Z B C D S ) 。 2 ) 针对Z B C D S 算法所构建的虚拟骨干网，在M A N E T 环境中稳定性不强、 链路极易断开和维护代价过高的问题，设计了一个新的基于移动变化率的最小支 配集启发式算法( M S Z C D S ) 。 3 ) 设计一个分布式文件广播分发协议。协议中最重要的广播算法采用本文提 出的基于移动变化率的最小支配集启发式算法，另外在虚拟链路的维护方面，由 于虚拟骨干网
9、建立中或是建立后，节点的随机移动性、信号的衰减和干扰，使得 节点之间的链路随时可能中断，或者在虚拟骨干网已经构建完成之后，由于有新 的节点需要加入，必须对原始的虚拟骨干网进行扩充，因此设计了一种虚拟骨干 网移动管理机制来保证虚拟骨干网的性能，该移动管理机制主要针对M B Z C D S 算法而设计。最后通过N S 2 网络模拟器，对算法在不同的环境下进行了性能模 拟，为今后的工作提供了重要的理论支持。 1 4论文的结构安排 论文安排如下： 第一章绪论。简要介绍M A N E T 和主要的研究方向。 第二章M A N E T 中的广播以及相关最小支配集算法概述。先介绍了M A N E T 中的广
10、播和广播风暴问题，然后分析了几种比较常见的最小连通支配集算法。 第三章提出了一个新的基于域的分布式最小连通支配集启发式算法 ( Z B C D S ) ，实验分析表明Z B C D S 算法的性能能够满足在大规模的网络环境中构 建虚拟骨干网的需要。 第四章针对M A N E T 的移动特性，在Z B C D S 基础上引入相对移动率概念， 使得所设计的算法能够适应移动环境中多变的移动情况。 第五章设计基于相对移动率的文件广播分发协议。并通过模拟器N S 2 对设 计的协议进行了仿真与性能评估。 第六章总结与展望。总结了本文研究的主要内容和研究成果，阐述了需要 进一步研究的问题。 7 杭州电子科
11、技大学硕士学位论文 第二章M A N E T 中的广播和最小支配集广播算法概述 2 1M A N E T 中的广播 M A N E T 是由一系列在彼此通信范围内且可以相互通信的移动节点组成。在 M A N E T 中没有预设的基站支持，每个移动节点既可以直接通信，也可以间接地 与其它移动节点进行通信。如果是间接通信，那么就需要使用多跳路由的方案。 从源节点发出的数据分组，经过一系列的中间转发节点，最终到达目的节点。广 播问题具有以下一些特征。 1 ) 任何移动节点可以随时随意地发送广播分组。但由于节点的移动和难以同步 等原因，使得获取任何类型的全局网络拓扑信息是不切合实际( 事实上这和广 播
12、问题一样的困难) 。 2 ) 广播的不可靠性，没有采用应答机制。I E E E8 0 2 1 1 M A C E 2 4 技术标准中没有 要求终端在接收到广播分组之后需要作出应答。但是，可以使用最小代价树 将广播分组分发到网络中尽可能多的移动节点上。做出这个假设的目的是： ( 1 ) 一个移动节点暂时地与网络发生分割，或者经历长时间的碰撞，将会丢失 广播分组；( 2 ) 应答可能使得在发送方周围产生严重的竞争，也就是产生了广 播风暴问题；( 3 ) 在很多应用中，1 0 0 可靠的广播是不必要的。而可靠广播 的目的是确保网络中的每个移动节点都能够接收到广播分组，可以通过移动 节点之间相互交换高
13、层应答来实现，也就是说通常可以在应用层实现可靠的 广播协议。 3 ) 为了防止在M A N E T 中，同一条广播分组被无休止的重复广播，需要假定移 动节点具有检测广播分组是否重复接收的能力。例如在A O D V 等协议中， 为了防止接收重复的广播分组，为每一个广播消息设置一个数组，即源节点 识别I D 、序列号等l - 2 J 。 2 2广播风暴问题及解决方案 通过泛洪实现广播的直接转发。一个移动节点第一次接收到一条广播消息后 必须重发这条消息。显然，网络中如果有n 个移动节点，那么就需要将同一条广 播消息广播n 次。 洪泛广播即是一种简单的网络路由策略也是一种简单的文件广播分发方式， 8
14、杭州电子科技大学硕士学位论文 每个节点只要接收到数据分组，就将该分组转发给每个邻居节点，这样就带来了 严重的广播风暴问题 2 2 1 。文献【2 2 】提出了广播风暴问题的以下三个主要的方面： ( i ) 冗余转发( i i ) 大量节点同时转发相同的数据分组所引发的竞争( i i i ) 由于缺少 R T S C I s - D a t e - A C K 交换机制所引发的碰撞。这些导致了较高的协议开销和通信 干扰。 通过构建连通支配集( C D S 卜一连通支配集( C D S ) 中节点形成虚拟骨干网 使得网络中的节点被组织成分层结构，全局网络被分成许多个较小的C D S 子网络，不论是
15、用来为主动型路由协议发送路由更新数据包或者为被动型路由协 议发送路由请求还是广播发送分发文件，与洪泛广播相比较，由于只需要虚拟骨 干网中的节点维持路由信息或转发需要分发的文件，虚拟骨干网能够显著减少通 信开销，缓解洪泛广播引起的广播风暴。除此之外，还能使路由更简单并能快速 适应拓扑变化。只要在由C D S 生成的子网中没有拓扑变化，就不需要重新计算 路由表，从而减少了节点的存储空间和消息复杂度。 2 3 最小连通支配集广播算法 广播定义为将数据分组传输到网络中所有移动节点的行为。广播是常见的网 络行为，用于解决很多问题，例如分布式计算问题。广播也被广泛的用于解决许 多网络层问题。尤其在M A
16、N E T 中，由于节点的频繁移动，所以需要更为频繁的 使用广播( 例如，寻呼某个特定的节点、发送告警信号、寻找到达某个特定节点 得路由) 。例如，路由协议( D S R , Z R P , A O D V ) 依靠广播一个称为路由请求( R o u t e R e q u e s t ) 的U D P 分组来搜索从源节点到目的节点的路由。而在本文的重点是通过 广播的方式来进行文件的分发。 广播问题描述为【2 5 , 2 6 t 在给定网络环境下，如何能最有效地将源节点的消 息传送给网络中的所有节点。在不考虑单向链路的情况下，计算机通信网络可以 抽象为图论中的简单无向图。通常用一个连通的简单无向图G = 代E ) 来表示移动 A dH o e 网络，其中：V 是节点的集合，每个节点代表一个无线移动主机；E 是 节点之间边的集合，每条边e ：( 叩) EE ( 其中“，yEV ) 表示主机U 和主机v 彼此 都在对方的无线发射范围内。若将网络节点分为支配节点和普通节点，其中只有 支配节点才在收到的广播消息之后，将其转发给它
