（计算机应用技术专业论文）基于移动预测的移动组播算法研究.pdf

硕士论文基于移动预测的移动组播算法研究 摘要 i n t e r n e t 已经深入到我们生活的方方面面，成为人们日常活动中不可缺少的一部 分，但目前大都采用的固定接入的方式使用i n t e r n e t ，这在很多方面限制了它的进一 步应用。同时，伴随着无线通信技术的迅速发展，移动设备大量增加，人们迫切希望这 些移动设备在移动过程中能够随时地通过无线方式从i n t e r n e t 上获取信息，但移动用 户在网络中的频繁切换和无线带宽的限制成为移动通信发展的瓶颈。由于组播通信能够 利用链路级共享，采用组播传输方式后只需要少量业务数据流即可给大量用户提供服 务，能够有效地节省网络带宽，减少网络通信延迟，提高传输的效率，对诸如远程教学、 视频会议、i n t e r n e t 电视等新兴的i n t e r n e t 应用非常有用。移动和组播的结合扩大了 移动和组播的应用范围，为两者的应用带来了更广泛的发展空间，达到了优势互补的效 果，同时也给两者都带来了新的挑战，因而移动组播技术也已经成为移动i p 技术科研 领域中的一个研究热点。 本文对现有的几种移动组播算法进行了分析研究，并重点研究了几种层次化移动组 播算法。在此基础上，针对远程加入中存在的两个缺陷：( 1 ) 组播树重构频率随着移动 节点的切换次数的增加而增大；( 2 ) 移动节点发生切换时，组播服务中断时间较长。结 合层次型的移动管理模型，并根据移动节点在运动时所表现出的规律性，提出一种基于 移动预测的移动组播算法。算法的基本思想是采用移动预测的方法预测移动节点未来要 进入的新子网，提前将组播分组转发至预测的新子网，从而降低组播分组的丢失率，缩 短组播服务的中断时间，提高移动组播服务的性能。同时，在组播服务中引入层次化的 移动管理方案，将移动节点在区域内的移动屏蔽起来，减少了由于节点移动而导致的组 播树重构频率过高的问题。对该方法的仿真结果显示，基于移动预测的移动组播算法具 有组播树重构频率低、组播分组丢失率小、传输延迟小、组播服务中断时间短等优点， 是一种高效的移动组播算法。 关键词：移动组播，移动预测，远程加入，层次结构，o m n e t 仿真 a b s t r a c t 硕士论文 a b s t r a c t i n t e r n e th a sg o n ed e e pi n t oe a c ha s p e c to fo u rl i f e ，a n db e c o m ea ni n d i s p e n s a b l ep a r to f p e o p l e sd a i l ya c t i v i t i e s ，b u tn o w t h ea d o p t e dw a yo fa c c e s s i n gi n t e m e ti sf i x e da c e s s ，i tl i m i t s t h ef u r t h e ra p p l i c a t i o no fi n t e r n e ta c c e s si nm a n yw a y st of u r t h e rl i m i tt h ea p p l i c a t i o no ft h e i n t e r n e t w i t ht h er a p i d l yi n c r e a s i n gn u m b e ro fw i r e l e s sc o m m u n i c a t i o n se q u i p m e n t ，p e o p l e f e r v e n t l yh o p e t oa c q u i r et h en e e d e di n f o r m a t i o nb yt h e s ew i r e l e s sc o m m u n i c a t i o n s e q u i p m e n ti nw i r e l e s sw a yw h i l em o v i n g b u tm o v i n gf r e q u e n t l yo fam o b i l en o d ea n d s a v i n gs c a r c eb a n d w i d t h i nw i r e l e s se n v i r o n m e n ti sab o t t l e n e c kp r o b l e mi nt h ed e v e l o p m e n t o fm o b i l ec o m m u n i c a t i o n a sm u l t i c a s tc o m m u n i c a t i o nc a nm a k eu s eo fl i n k s h a r i n g ， a d o p t i n gm u l t i c a s tt r a n s m i s s i o no n l yn e e d s as m a l la m o u n to ft r a f f i cf l o wt op r o v i d es e r v i c e s t oal a r g en u m b e ro fu s e r sa n di tw i l le f f e c t i v e l ys a v en e t w o r kb a n d w i d t h , r e d u c en e t w o r k c o m m u n i c a t i o nd e l a ya n di m p r o v et h ee f f i c i e n c yo ft r a n s m i s s i o n s om u l t i c a s t i n gi sv e r y u s e f u lf o rs o m en e we m e r g i n gi n t e r a c ta p p l i c a t i o n s ，s u c ha sd i s t a n c el e a r n i n g ，v i d e o c o n f e r e n c i n g , i n t e r n e t ，t e l e v i s i o n ，a n ds oo n t h ec o m b i n a t i o no fm o b i l ei pa n dm u l t i c a s th a s e x p a n d e dt h ea p p l i c a t i o no fm o b i l ei p a n dm u l t i c a s t ，b r o u g h tab r o a d e rs p a c ea n dh a s a c h i e v e dac o m p l e m e n t a r ye f f e c t i th a sa l s ob r o u g h tan e wc h a l l e n g et ot h e s et w o t e c h n o l o g i e s t h u sm o b i l em u l t i c a s tt e c h n o l o g yh a s b e c o m eah o tf i e l do fm o b i l ei p t e c h n o l o g yr e s e a r c h i nt h i st h e s i s ，s o m ee x i s t i n gm o b i l em u l t i c a s tp r o t o c o l sw e r ea n a l y z e da n dr e s e a r c h e d f i r s t l y , a n df o u rh i e r a r c h i c a lm o b i l em u l t i c a s tp r o t o c o l s w e r er e s e a r c h e de s p e c i a l l y b a s e do i l t h e s ew o r k s ，t h i sp a p e rp r o p o s e dan o v e lh i e r a r c h i c a lm o b h em u l t i c a s tp r o t o c o lb a s e do i l m o b i l i t yp r e d i c t i o n i tu s e sah i e r a r c h i c a lm o b i l em u l t i c a s ta r c h i t e c t u r et oi s o l a t et h el o c a l m o v e m e n tf r o mo u t s i d e ，a n di m p r o v e st h es t a b i l i t yo ft h em a i nm u l t i c a s td e h v e r yt r e e a c c o r d i n gt ot h em o b i l en o d em o v e m e n tv e l o c i t ya n dr e l a t e di n f o r m a t i o no fi t sn e i g h b o r i n g s u b n e t ，i tp r e d i c t st h es u b n e to ft h em o b i l en o d ef o rf a t h e r l a n dt h e nf o r w a r d st h em u l t i c a s t p a c k e tt ot h ep r e d i c t e ds u b n e ta h e a di no r d e rt or e d u c em u l t i c a s tp a c k e tl o s sr a t e ，s h o r t e nt h e m u l t i c a s ts e r v i c ed i s r u p t i o nt i m ea n di m p r o v et h ep e r f o r m a n c eo fm o b i l em u l t i c a s ts e r v i c e s s i m u l a t i o nr e s u l t sd e m o n s t r a t et h a tt h i ss c h e m ei se f f e c t i v e 、机t hl o wm u l t i c a s tt r e er e b u i l d f r e q u e n c y , l i t t l ep a c k e tl o s sr a t ea n ds h o r tt r a n s f e rd e l a y k e y w o r d s ：m o b i l em u l t i c a s t ，m o b i l i t yp r e d i c t i o n ，r e m o t es u b s c r i p t i o n , h i e r a r c h i c a ls t r u c t u r e 0 m n e ts i i n u l a t i o n 硕士论文基于移动预测的移动组播算法研究 图表目录 图2 1 1 源树和共享树8 图2 2 2 1 移动i p v 6 的双向隧道路由方式1 1 图2 2 2 2 移动i p v 6 的优化路由方式1 2 图2 2 2 3 移动i p v 6 的路由方式转换1 2 图2 2 2 4 返回路径可达过程1 3 图2 2 3 1 p v 6 的注册过程1 5 图2 3 2 1 移动i p v 6 中的双向隧道操作1 8 图2 3 2 2 双向隧道算法18 图2 3 2 3 移动i p v 6 中的远程加入操作1 9 图2 3 2 4 远程加入方法2 0 图2 3 2 5f h s r 协议的操作过程2 l 图3 2 1 组播代理协议的三级层次结构。2 4 图3 3 1m o b i c a s t 的层次结构2 5 图3 4 1 基于s s m 的层次型结构2 7 图3 5 1 移动节点的组播数据流的路由示意图2 8 表3 6 1 几种移动组播算法的性能对比一2 9 图4 2 1m p h m m 的分层组播结构3 2 图4 2 2 公共服务区3 3 图4 2 3 临界区域3 4 图4 - 3 1 1 移动预测3 6 图4 3 2 1 相关消息扩展3 8 图4 4 2 1m p h m m 的数据结构4 5 图5 2 2 1o m n e t + + 仿真程序的体系结构5 3 图5 3 1 14 * 4 的m e s h 网络中m p h m m 算法仿真场景5 4 表5 3 1 1 主要参数设置5 5 图5 3 2 1 组播树的重构频率5 5 图5 3 2 2 平均组播分组丢失率5 6 图5 3 2 3 平均传输延迟5 7 图5 3 2 4 组播服务的平均加入延迟5 8 v 声明尸明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：啦 力矿扫多年月喃 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：缉 工咕年月自 硕士论文 基于移动预测的移动组播算法研究 1 绪论 1 1 课题的研究背景 i n t e r n e t 已经深入到我们生活的各个方面，成为人们日常生活中不可缺少的组成部 分。目前采用固定接入方式使用i n t e r n e t ，这在很多方面限制了i n t e r n e t 的进一步应 用。而随着网络技术和无线通信设备的迅速发展，手机、掌上电脑、笔记本电脑等便携 式或移动设备大量应用，人们迫切希望能够随时地利用这些移动设备通过无线网络从 i n t e r n e t 上获取信息，但原来的i p 协议对网络节点的移动性支持不够，针对这种情况， i e t f 工作组于1 9 9 6 年开始制定支持移动i n t e r n e t 的协议，即移动i p 协议。移动i p 作为支持移动节点无缝接入i n t e r n e t 的i p 协议扩展，i e t f 基于i p v 4 协议提出 r f c 2 0 0 3 3 2 2 0 支持移动i p 的标准，并在i p v 6 的基础上，提出了相关的移动i p v 6 的r f c 方案，移动i p 也已经成为i p v 6 协议的不可缺少的组成部分。 同时，诸如远程教学、视频会议、i n t e r n e t 电视等新兴的i n t e r n e t 应用都涉及点到 多点和多点到多点通信，这些应用可能只有少数几个源，但存在大量的信息接收者，因 而传统的单播和广播两种数据传输方式已经不能适应迅猛增长的数据传输业务，组播传 输方式应运而生。组播通信能够利用链路级共享，采用组播传输方式后只需要少量业务 数据流即可给大量用户提供服务，能够有效地节省网络带宽，减少网络通信延迟，提高 传输的效率，对很多i n t e r n e t 应用非常有用醢1 。而近年来随着移动技术的迅速发展和移 动设备的大量应用，无线网络技术得到了飞速的发展，越来越多的移动设备用户希望能 在日常生活中通过无线设备随时访问传统i n t e r n e t 上的服务。在移动环境中，由于移动 节点常常使用无线链路，其最明显的特征就是有限的链路带宽和较高的错误率，同时移 动节点的体积通常都比较小，拥有的能量供应、处理器能力以及存储能力等都比较低。 因此，在移动环境下，i p 组播所具有的可扩展性强和高效等特点，对于移动节点来说显 得尤为突出和重要b 1 。移动和组播的结合可以扩大移动和组播的应用范围，为两者的应 用带来更广泛的发展空间，达到优势互补的效果。i p 组播要求有明确的机制去追踪组 成员，这种功能一定程度上体现在主机与负责维护组成员记录的一个或多个组播路由器 上，因此移动与组播的结合也给两者都带来了新的挑战，这主要体现在三个方面睛1 ： 1 移动组播不仅要处理动态的组成员，还要考虑组成员会动态改变位置。 2 在建立组播树的时候，主机可能会发生移动。 3 如果移动节点是组播源，当该主机执行切换操作时会导致发往其他成员的组播流 中断。 一方面移动与组播的结合具有潜在的应用价值和广泛的应用前景，另一方面移动与 组播的结合又面临这些新的挑战，因此移动环境中的组播应用引起了人们越来越多的重 l 1 绪论硕士论文 视，许多专家和学者在该领域进行了大量的研究，提出了很多解决方案，但是这些方案 都只是部分地解决了移动组播所面临的新问题，迄今为止还没有一个全面高效的解决方 案【1 1 1 ，移动组播技术仍然是移动i p 技术科研领域中的一个难点和热点。 1 2 研究现状 1 2 1 移动组播技术 目前在i n t e r n e t 马b 使用的查n c b t 嘲、d v m r p m 、m o s p f 嘲和p i m n 0 1 等组播协议，在构建 组播树时都假设主机的位置是固定的，而没有考虑组成员位置动态变化的情况。在主机 移动的环境下，移动组播协议不仅要处理组播组中动态变化的组成员关系，而且要处理 移动节点位置的动态改变。当组成员移动时，如果重新构建组播树，就意味着增加网络 系统的协议开销，组播服务被间隙性中断；当移动节点快速移动时，可能会因为来不及 重建组播树而使得组播服务一直中断；如果不重构组播树，则会导致组播分组的低效传 输，甚至移动节点根本接收不到组播分组n 。因此，这些协议都不适合组成员移动的环 境。 而随着移动i p 技术的发展，人们开始研究支持主机移动的组播协议，i e t f 工作组在 移动工p 中定义了两种基本的移动组播方法：远程加入r s 和双向隧道b t 。同样，在移动i p v 6 中也给出了这两种支持主机移动的组播机制。但是，这两种方法都存在比较严重的缺陷： 远程加入算法会产生包丢失、组播树重构频率高等问题；而双向隧道算法中则存在“三 角路由和“隧道聚集”等问题。由于这两种组播方法都存在比较严重的缺陷，人们在 这两个组播机制的基础上提出了多个新的方法。 文献 1 3 结合双向隧道和远程加入的优点，提出一种f h s r 方法。在该方法中，家 乡代理代替移动节点一直加入组播组，移动节点移动到外地网络后，首先建立与家乡代 理之间的隧道，通过隧道接收组播数据分组；同时，移动节点在外地网络上申请加入组 播组。当移动节点收到外地网络转发的组播数据分组后，通知家乡代理停止转发组播数 据分组，但家乡代理继续接收组播数据分组，因而这种方法存在家乡代理额外接收组播 数据包、浪费网络资源等问题。文献 1 4 基于双向隧道的思想，提出一种前向网络 p s ( p e r v i o u sn e t w o r ks u b s c r i p t i o n ) 的组播机制，即当移动节点发生移动时，同该节 点上一次访问的子网之间建立双向隧道，由于这样的双向隧道通常要比移动节点与家乡 代理之间的双向隧道短，从而保证移动节点切换到当前子网后，在重新建立组播树之前 就能很快收到组播包。在此基础上作者进而提出一种基于层次型路由结构的先p s 再r s 的移动组播协议。这种方法减少了移动节点切换后重新加入组播组的等待时间，也减轻 了家乡代理的通信负担。但是，与f h s r 方法类似，这种方法存在前向网络代理额外接 收组播数据包，浪费网络资源等问题。文献 1 5 则在远程加入和双向隧道的基础上，根 2 硕士论文 基予移动预测鼬移鹚组播冀法研究 摇霸户移动模式提出了种基于震产移动模式的蠢适应移动缱播算法，移穗节煮穰据移 动模式和当前移动状态自适应地选择双向隧道算法或者远程加入算法完成组播切换。当 移动节点移动速率大时，采用双向隧道的组播机制，避免频繁的组播切换，减小组播树 的重梅代价；蔼当移动节点移动速率小时，茭l j 采用远程加入酌组播杌制，用较小的组播 瓣重梅戗价来实现组援数据麴傀纯传输。这种方法相对鞭s r 窝黔豁来说，综合性巍更 好，尤其在组播源移动时，但该方法的性能好坏在一定程度上依赖于不同的移动模式。 文献 1 6 3 则对m l d 作了扩展，并在引入组播传输代理节点m d a 的基础上，提出了一 释基予溉d 支持源移动的组播算法。文献疆7 】 王8 】孳 入移动缀播两关m m g 解决7 双离隧 道载隧道聚集翘题，但存在单一节点失效阀题，也就是说存在组撩数据丢失匏可能。文 献 1 9 则引入域组播代理d m a 和予网组播代理s m a 的概念，d m a 代表移动节点加入组播 缢，并采用多级分层的d m a 结构，由合适的d 漱通过隧道向s m a 传输组播数据，再由 s 激将组播数据发送绘在该予鄹的移动苇点。这些方法郭萼l 入了新戆实体，这使得这些 方法在实现时比较复杂。 文献 2 0 根据移动节点的移动速度提出一种层次组播协议，通过移动节点在前一个 子网逶留的时瓣来选择一个合适的淞p 作为该主枫的组播代理，降低了缀播橱重构酌开 销。文熬 2 羔】和文献 2 2 提出了一种基于分层m a p 的移动组播冀法，遥过肉m a p 睾请 利用隧道接收组播数据，同时也在本地申请加入组播组。当移动节点进入异地m a p 域后， 向当地m a p 注册本地转交地址，获得在线转交地址，同时向前一个m a p 注册，同前一个 m a p 建耄隧道，并在凝浆m a p 域牵请加入缎接缓。然矮，异缝潋p 域的m r a 代表移动繁 点加入组接组成功后，通过m s a 囱移动节点发送组播数据。在移动节点接收到当地网络 上组播路由器转发的组播分组前，组播分组由前一个m a p 域通过隧道转发。这种方法的 路由遥钕最优，加入延迟较低，餐是m a p 一矗接收数据，这是对两络资源的浪费。 文献_ 莲5 】掇撼移动节点在一定范孱蠹的萋复性移动定义了一个本缝组豹概念，本地 组指的是移动节点最近曾经访问过的子网的集合，始终保留属于本地组内的子网的组播 树，这样，当移动节点再次移动该子网时，就不需要重建组播树。而在文献 1 2 中则把 奉地缓定义为在一定时闻闯隔at 蠹移动节点访阚过的子嬲翡集合，如果一个子网处予 组播路由上则称它是活动的，否则就是菲活动的，并定义所蠢在本地缀内的予网在移动 节点离开后的t 时间范围内都是活动的，活动的子网由其本地代理继续接收组播数据。 所有活动的子网中，在时间t 肉，如粟组播组的任一成员重新迸入本地组内的予网， 鄂么该子翳将被激滔，垂本逑代理嚣移动节点转发缀播数据；否则当蠡专耗尽，该子阕 的本地移动代理向本地组播路虫器发送离开消息，并将该予网从本地组巾被剔除。这些 方法可以减少组播树剪枝次数和移动节点重新加入组播树的次数，但它们对资源的浪费 情况都较为严重。 这些方法或者是缝合双蠢隧道和远程加入嚣种方法鲢优点改善协议性麓，或者透过 3 1 绪论 硕士论文 引入新的实体来改善协议性能，或者将分层移动管理的方法引入组播来改善协议性能， 或者是利用移动节点的移动特性来改善协议性能。这些方法各有优缺点，相对而言，在 移动组播算法中引入层次化的管理机制能带来较好的协议性能，也方便进行层次化的管 理。因此，在移动组播算法中引入分层机制将是一个比较重要的发展方向幢1 。 1 2 2 移动预测技术 虽然近年来无线通信网络发展迅速，但是目前的应用大部分还局限于简单的数据传 输服务，如w e b 浏览、收发电子邮件等，一方面这是由于无线链路固有的缺陷，另一 方面是因为无线通信网络本身缺乏对服务质量的支持【4 3 】。为了提高无线通信网络服务的 服务质量，可以通过移动预测技术来预测移动节点的运动路径，预测出移动节点未来要 进入的新的目标子网，从而可以为移动节点在进入预测目标子网时实现提前切换，减少 实际切换时的工作量，达到减小切换延迟的目的【z 5 j 。同时，根据预测结果也可以提前为 移动节点进行资源预留协商，为移动节点进入预测目标子网后预留足够的资源，保证移 动节点进入预测目标子网后的服务质量 2 6 o 通过移动预测也可以改进无线通信网络在组 播通信方面的综合性能【2 ”。因此，移动预测对于无线通信网络的发展和应用具有重要的 作用。 目前的移动预测方法大体可以分为两类：基于人工神经网络的方法和基于概率统计 模型的方法【3 0 1 。第一类要借助于g p s 设备m 】，根据移动节点当前所在子网的位置信息、 预测子网的位置信息以及移动节点当前的位置、速率和运动方向等信息，建立预测目标 子网与当前子网间的数学模型，根据移动节点的运动趋势预测移动节点未来要进入的子 网。如在文献 2 8 】中首先获得当前子网无线接入点的位置以及当前子网各相邻子网的无 线接入点的位置，然后间隔一段时间获得移动节点的位置，计算移动节点距离哪个子网 的无线接入点距离最近，距离最近的子网就是预测的目标子网。在文献【2 9 】中则根据移 动节点的运动方向来预测移动节点要进入的下一个子网，首先移动节点在当前子网向基 站汇报它的位置和它的运动方向，基站根据它的位置计算移动节点与其相邻子网的两个 切线方向，用两个角度表示，如果移动节点运动方向的角度在这个两个切线方向之间， 那么该相邻子网就是目标预测子网。这一类预测方法的优点是预测方法简单，但是并非 所有的移动设备都具有g p s 装置，这也使得这一类预测方法具有一定的局限性。 第二类预测方法是与g p s 无关的【4 3 】，通常用统计的方法从移动节点的运动轨迹中 发现移动的运动模式，利用发现的运动模式来预测移动节点移动的目标子网。比如文献 【2 5 通过切换日志事件数据库来计算不同接入点之间单位时间内的切换率，然后建立由 各相邻无线接入点构成的带权双向图，权值就是计算所得的切换率，再根据用户服务的 级别设置权值的范围，建立一个选择算法，预测出移动节点未来可能要到达子网的无线 接入点。而文献 3 0 贝j j 提出了一种基于隐马尔可夫的移动预测模型，在该方法中将无线 4 硕士论文基于移动预测的移动组播算法研究 接入点所覆盖的区域分为多个区域，并记录下移动节点在这些区域移动过程中的各个状 态，无线接入点再根据观察数据训练与其相邻的各子网对应的h m m 参数，从而建立模 型。通过训练观察规整判别的过程来预测移动节点运动的目标子网。这一类方法不依 赖于g p s 这样的设备，具有更广阔的应用空间。 1 3 论文的主要研究内容 本文主要讨论了移动环境下的组播技术，特别是对移动i p v 6 网络中的层次型组播 算法和协议进行了重点的研究，并结合层次化的移动管理方案和移动预测机制设计了一 种移动组播算法，以提高移动环境下组播服务的性能，即：减少由于节点移动而导致的 组播树重建频率，降低组播数据分组丢失率。具体体现在以下几个方面： ( 1 ) 对现有的移动组播算法进行了详细的研究分析，并重点研究了结合分层管理机 制的移动组播方案。 ( 2 ) 在现有的层次型移动组播算法的基础上，提出了一种基于移动预测的层次型移 动组播算法，通过层次化的移动管理方案来减少由于节点移动而导致的组播树重构频率 过高问题，这种算法通过移动预测算法预测移动节点未来要进入的外地子网，提前将组 播分组转发到该子网，从而降低组播分组的丢失率，缩短组播服务的中断时间，提高移 动组播服务的性能。 ( 3 ) 对提出的移动组播方法进行了模拟仿真，分析了该方法的性能。 如 1 4 论文的组织结构 本文共分六章，主要包括如下几部分内容： 第一章介绍了课题的研究背景以及国内外研究现状，阐述了本文的主要研究工作， 明确了研究方向。 第二章介绍了相关的理论背景，包括三个部分：首先简单介绍了i p 组播的基本原 理，然后介绍了移动i p 的常用术语以及层次化的移动管理模型，紧接着对移动环境下 的组播技术进行了分析，介绍了在移动环境下组播面临的问题以及目前人们对移动组播 算法的评价标准，并对远程加入和双向隧道这两种传统的移动组播算法以及综合二者优 点的f h s r 算法进行了分析。 第三章介绍了四种典型的层次型移动组播算法，并对这四种组播算法进行了详细的 分析，指出它们的优点与存在的不足，在与两种传统的组播算法比较的基础上总结了在 移动组播中引入分层管理机制的好处。 第四章在现有层次型移动组播算法的基础上提出了一种基于移动预测的层次型移 动组播算法，通过分层机制减少组播树的重构频率，通过移动预测缩短组播服务的中断 时间、降低组播分组丢失率。 5 l 绪论硕士论文 第五章利用仿真软件o m n e t + + 对提出的方法进行了仿真模拟，从组播树重构频率、 组播服务中断时间、组播分组丢失率等方面与远程加入、双向隧道这两种方法进行了对 比分析，实验结果表明基于移动预测的分层移动组播算法具有更好的性能。 第六章是对本文所做研究工作的总结与展望，分析目前的研究工作中还有待于进一 步完善的地方，以及今后要深入研究的内容和方向。 6 硕士论文基于移动预测的移动组播算法研究 2 相关理论背景 2 1i p 组播 传统的单播和广播通信方式在传递信息时只局限于特定主机或网络的所有主机，不 能适应动态的通信。组播技术则是一种允许一个或者多个发送者发送同一数据到多个接 收者的网络技术。它通过组的概念将用户划分为不同的组播组，组播组中的成员可以是 同一个子网的，也可以是不同子网，组播源发送组播分组给某个的组播组，只有该组的 成员能收到这些组播分组。与单播通信相比，在一对多的组播通信中，组播源同时向任 意数目的接收者通过组播树传输组播分组，并且只在扇出点复制组播分组，使得每个组 播分组在每条链路上最多出现一次，能够提高网络资源的利用效率。特别是当组播组的 成员数很大时，采用组播方式可以明显地减轻网络中各种资源的消耗。i p 组播模型由 s t e p h e nd e e r i n g 最早提出，作为i p 点到点单播传输模型的扩展。i n t e r n e t 中i p 组播 模型主要包括三个方面f l j ： ( 1 ) i p 类型的风格：组播源可以在任何时候发送组播分组，组播通信基于无连接u d p 协议，组播分组采用尽力传输的服务策略，不需要可靠或拥塞控制机制。 ( 2 ) 组的开放性：发送者只需要知道组播地址，不需要知道组成员关系和组成员个 数，一个组可以有任意个组播源。 ( 3 ) 组的动态性：组成员可以按照自己的意愿在任何时间加入或者离开组播组，没 有必要向组管理中心进行注册、同步或者协商。 如果主机希望加入或离开某个组播组，需要通过组管理协议i g m p ( i n t e r n e tg r o u p m a n a g e m e n tp r o t o c 0 1 ) 或者组播侦听发现m l d ( m u l t i c a s tl i s t e nd i s c o v e r y ) 协议， 向本地组播路由器申请加入或者离开某个组播组，并及时响应组播路由器的查询信息。 而本地组播路由器则记录本地局域网中存在的组成员信息，通过i g m p 或m l d 协议来管 理组成员的状态。为了将组播数据分组传送给所有的组成员，组播路由器之间需要建立 和维护组播树。建立组播树的典型算法有：洪泛算法、生成树算法、反向路径转发和核 心树等。而根据组播树根节点选择方式的不同，组播树可以粗略地分为两类【2 4 】：源树和 共享树。源树又称为最短路径树( s p t ，s h o r t e g tp a t ht r e e ) ，它以发送者为根在网络 中建立生成树，到达每个组成员；而共享树则是在网络中选择某一点作为公共的根节点 来建立组播树。图2 1 1 显示了源树与共享树的不同瞰1 。 7 2 相关理论背景硕士论文 澎l l ( a ) 源树 2 2 移动i p 技术 ( b ) 共事树 巨2 1 1 源树和共享树 过去几年中，因特网得到了惊人的发展，人们也越来越依赖于网络计算。同时，伴 随着无线通信技术的迅速发展，大量的移动设备进入到入镌能毅常生活中，越来越多静 人芷成为移动办公的一分子，人们急切地希望通过移动设备从因特网上获取自己所需的 数据。这些因素共同推动着将移动主机与其他主机相连的需求，包括固定主机与移动主 机。但是传统的礤协议对主机移动性的支持不够，因此因特网工程组制定了一个为移 动主枫传送信息的解决方案移动p 。移动球与移动主机通信时所采髑的物理媒介 硕士论文 基于移幼预测的移动缎播算法研究 无关，它允许主机在不中断逶信和重薪启动应用程序豹情况下改变地理位置。本节将以 移动i p v 6 为例，介绍移动d 的常用术语和基本操作【1 1 。 2 2 1 移动i p v 6 的常用术语 1 移动i p v 6 的功能实体 ( 1 ) 移动节点( m o b i l en o d e ) ：是指从个网络或子网链路上切换到另一个网络或子 嬲的主机或路毒器。移动节点可以改变它的网络接入点，并且还可以使用原来的王p 地 址与其他节点通信。 ( 2 ) 通信对端( c o r r e s p o n d e n tn o d e ) ：指所有与移动节点通信的节点，通信对端可 以是静止或移动的。， 3 家乡代理( h o m ea g e n t ) ：指移动节点家乡链路上的一个路由器，允许移动节点 向其注册当前的转交地址，并且当移动节点离开家乡时，截取其家乡链路上目的地址是 移动节点家乡地址的分组，通过隧道转发到移动节点注册的转交地址。 移动节点、通信对端和家乡代理是移动i p v 6 中最重要的三个功麓实体。这种分类 只是概念上的，它们只是存在予i p v 6 节点上的功能实体，并非对i p v 6 节点的分类定义。 比如，移动节点同时可能是其他节点的通信对端，家乡代理也可能是移动节点的通信对 端等。 2 其他术语 1 ) 家乡地址( h o m ea d d r e s s ) ：指分配给移动节点的王p 地址。它属于移动节点的家 乡链路，标准的i p 路由机制会把转发给移动节点家乡地址的分组发送到其家乡链路。 ( 2 ) 转交地址( c a r e - o fa d d r e s s ) ：指移动节点访问外地链路时获得的i p 地址。这 个i p 地址的子网前缀是外地子网前缀。移动节点同时可获得多个转交地址，其中注舫 到家乡代理的转交地址称力主转交地址( p r i m a r yc a r eo fa d d r e s s ) 。 ( 3 ) 移动( m o v e m e n t ) ：指移动节点改变其到i n t e r n e t 连接点的行为。如果移动节点 当前不在它的家乡链路上，则称为离开家乡。 ( 垂) 家乡予网前缀( h o m es u b n e tp r e f i x ) ：指对应于移动节点家乡地址的王p 子网前 缀。 ( 5 ) 家乡链路( h o m el i n k ) ：对应于移动节点家乡子网前缀的链路。标准i p 跷由机制 会把目的地址是移动节点家多地址的分组转发到移动节点的家乡链路。 鳓井缝子网前缀( f o r e i g ns u b n e tp r e f i x ) ：对于一个移动节点而畜，指除了其家 乡子网前缀之外的任何i p 子网前缀。 ( 7 ) 外地链路( f o r e i g nl i n k ) ：对于一个移动节点而言，指除了其家乡链路之外的 任何链路。 8 ) 绑定( b i n d i n g ) ：指移动节点家乡地址和转交地址之间的关联。家乡代理通过这 9 2 相关理论背景 硕士论文 种关联把发到家乡链路的属于移动节点的分组转发到其当前位置，通信对端通过这种关 联也可以知道移动节点的当前接入点，从而实现通信的路由优化。 ( 9 ) 绑定过程( b i n d i n gp r o c e d u r e ) ：由移动节点发起，通知通信对端或者家乡代理 关于本节点当前绑定的过程。 绑定授权( b i n d i n ga u t h o r i z a ti o n ) ：绑定过程需要授权，使得接收者相信发送 者有权指定新的绑定。 2 2 2 移动i p v 6 的基本操作 2 2 2 1 移动绑定 当移动节点移动到外地链路上时，要通过i p v 6 邻居发现机制( 通常通过无状态的 地址自动配置方式) 获得一个或多个转交地址，转交地址的子网前缀与移动节点访问的 外地链路的子网前缀相同。移动节点在获得转交地址后，需要把一个转交地址注册到它 的家乡代理上，通过向家乡代理发送“绑定更新”消息，以及接收家乡代理应答的“绑 定确认消息完成注册。移动节点可以同时拥有多个转交地址，注册到家乡代理的转交 地址称为主转交地址。 移动节点在任何时候都可以给通信对端发送绑定更新，使通信对端获知移动节点当 前使用的转交地址。考虑到移动节点的连续移动，移动节点在新的链路上获得了新的转 交地址后，可能希望正在发往前一个转交地址的分组也可以到达移动节点，减少分组重 传带来的延迟。为了精确建立这类临时的隧道，隧道的源端必须是移动节点的前一个转 交地址，类似于从移动节点家乡地址到移动节点当前转交地址的隧道。为此，移动节点 需要向前一个所在链路的家乡代理发送绑定更新以建立绑定。 移动节点维护一个绑定更新列表，记录它所发送的每个尚未超时的绑定更新的相关 信息，其中包括移动节点发往家乡代理、通信对端以及前一个转交地址所在链路的家乡 代理的所有绑定更新。如果某个绑定更新表项快要超时，移动节点重新发送绑定更新消 息，以确定是否需要继续维护当前的绑定。 2 2 2 2 分组路由 家乡代理获得移动节点的转交地址并完成绑定后，在移动节点的家乡链路上使用代 理邻居发现机制，在家乡链路上截获目的地址是移动节点家乡地址的i p 俩分组，然后 通过隧道将它们转发到移动节点的主转交地址。家乡代理对分组使用i p v 6 封装，外层 i p v 6 报头中目的地址是移动节点的主转交地址。 通信对端和移动节点之间有两种可能的通信方式。第一种方式称为双向隧道( 如图 2 2 2 1 ) ，这种方式不要求通信对端提供移动i p v 6 的支持，也不要求移动节点在通信 对端上注册绑定。通信对端发送的分组路由至i j 家乡代理，家乡代理通过隧道转发给移动 l o 硕士论文基于移动预测的移动组播算法研究 节点；移动节点发送给通信对端的分组首先通过反向隧道发送到家乡代理，然后从家乡 网络正常路由到通信对端。 图2 2 2 1 移动i p v 6 的双向隧道路由方式 第二种方式是优化路由( 如图2 2 2 2 所示) 。要求移动节点在通信对端上注册它 的当前绑定，通信对端到移动节点的分组直接发送给移动节点的转交地址。当发送任何 i p v 6 分组时，通信对端根据分组的目的i p 地址查询它的绑定缓存，如果在绑定缓存中 蒋在匹配，通信对端使用第二类路由头，将分组的目的地址换成查询获得的转交地址， 第二类路由头中的地址是移动节点的家乡地址。移动节点发送分组给通信对端时，在目 的地扩展报头中使用家乡地址选项，设置分组的源地址为移动节点的当前转交地址，家 乡地址选项中的地址是移动节点家乡地址。这种优化路由机制缩短了通信的路径，也消 除了家乡代理和家乡链路上可能的流量冲突，减小了家乡代理、家乡链路上的故障对移 动节点与通信对端的影响。 通信对端在发送分组时，如果在缓存中没有找到分组的目的地址，就按照常规分组 的规则发送，即使移动节点的家乡地址作为分组的目的地址。移动节点的家乡代理收到 分组后，通过隧道转发分组给移动节点。移动节点收到家乡代理通过隧道发来的分组， 认为通信对端没有与它建立绑定，就向通信对端发送绑定更新消息来建立绑定，以形成 优化路由，如图2 2 2 3 所示。 2 相关理论背景 硕士论文 圈2 2 2 2 移动i p v 6 的优化路由方式 圈2 2 2 3 移动i p v 6 的路凌方式转换 2 2 2 3 返回路径可达过程 - 移动i p v 6 提供很多安全特性，包括移动节点到家乡代理或通信对端绑定更新的保 护，对隧道、家乡地址信息和分组中路由指令的保护。移动节点和家乡代理通过建立安 全关联，使用a h ( a u t h e n t i c a t i o nh