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

摘要移动网络是一种移动通信和计算机网络相结合的网络，网络中的每个节点都兼有路由器和主机两种功能。它具有以下四点特征：( 1 ) 动态变化的网络拓扑结构，( 2 ) 有限的资源，( 3 ) 多跳通信，( 4 ) 较低的安全性。在移动网络中提供服务质量q o s ( q u a l i t yo fs e r v i c e ) 面临许多挑战，q o s 已成为移动网络研究的热点问题。q o s 移动组播路由选择的目的是在满足每个路由的q o s 需求时生成一棵包括所有组播组成员的最小组播生成树。针对移动网络的特点，在z r p 协议中考虑q o s 参数，获取当前能够满足q o s 要求的最大网络拓扑图；探讨了蚁群算法在多约束q o s 路由问题中求解最优组播树的问题。改进后的算法在获取网络拓扑时，在每个区域选择一个区域代理转发数据，并为该区域内的节点提供服务。选择本区域内移动频率最小的节点作为区域代理，构造出网络模型。改进的蚁群算法结合正交实验统计方法，根据要搜索路径的规模，选择合适的正交表，确定各q o s 参数影响度的大小。各q o s 参数的影响度决定信息素的挥发度，使得多数蚂蚁趋向于选择影响度大的路由；而且在搜索过程中，采用概率选择的方法，两组蚂蚁分别进行搜索，每搜索完一次进行信息素的交互，避免搜索过程中陷入局部最小解。结合多个q o s 约束，从选择的两组路径中选出一条最优路径。每只蚂蚁在选择下一节点时引入该路径上次被搜索时的选择概率，加快搜索速度。实验证明，该算法具有更好的性能，能够快速有效的建立q o s 组播树，较快的收敛到全局最优解，且有效减少了因节点移动而造成的组播树重构频率。关键词：移动网络q o s 蚁群算法组播r e s e a r c h0 uq o sm o b i l em u l t i c a s tr o u t i n ga l g o r i t h mt i a nj i n g ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y )d i r e c t e db ya s s o c i a t ep r o f w e id o n g p i n ga s s o c i a t ep r o f l ik e w e na b s t r a c tm o b i l en e t w o r ki sac o m b i n a t i o nn e t w o r ko fm o b i l ec o r n m u n i c a t i o n sa n dc o m p u t e rn e t w o r k s e a c hn o d eh a st h ef u n c t i o no fr o u t e r sa n dh o s t s i th a st h ef o u rc h a r a c t e r i s t i c sa sf o l l o w s ：( 1 ) t h ed y n a m i cc h a n g e so fn e t w o r kt o p o l o g y , ( 2 ) l i m i t e dr e s o u r c e s ，( 3 ) m u l t i h o pc o m m u n i c a t i o n s ，( 4 ) t h el o w e rs e c u r i t y i tm e e t sm a n yc h a l l e n g e sf o rp r o v i d i n gq o s ( q u a l i t yo fs e r v i c e ) i nm o b i l en e t w o r k q o sr e s e a r c hh a sb e c o m eah o ti s s u ei nm o b i l en e t w o r k m o b i l em u l t i c a s tq o sr o u t i n gi sd e s i g n e dt om e e tt h en e e d so fe a c hr o u t i n gq o sa n ds i m u l t a n e o u s l yg e n e r a t et h em i n i m u ms p a n n i n gm u l t i c a s tt r e ew h i c hi n c l u d e sa l lm e m b e r so ft h em u l t i c a s tg r o u p a i m i n ga tt h ec h a r a c t e r i s t i c so fm o b i l en e t w o r k ，t h eq o sp a r a m e t e r sa r et a k e ni n t oa c c o u n ta tz r pp r o t o c o lt oo b t a i nt h el a r g e s tn e t w o r kt o p o l o g yw h i c hm e e t st h eq o sr e q u i r e m e n t s a n dt h ea n tc o l o n ya l g o r i t h mi se x p l o r e dt os o l v et h eo p t i m a lm u l t i c a s tt r e ei nt h em u l t i c o n s t r a i n e dq o sr o u t i n gp r o b l e m w h e ng e t t i n gt h en e t w o r kt o p o l o g y , t h ei m p r o v e da l g o r i t h mc a r lc h o o s ear e g i o n a la g e n tf r o me a c hr e g i o nt ot r a n s m i td a t a , a n dp r o v i d es e r v i c e sf o rt l l en o d e so ft h er e g i o n t h em o b i l en o d ew h i c hh a st h es m a l l e s tf r e q u e n c yf r o mt h er e g i o ni ss e l e c t e da st h er e g i o n a la g e n tt oc o n s t r u c tn e t w o r km o d e l a c c o r d i n gt ot h es i z eo ft h es e a r c hp a t h , t h ei m p r o v e da n tc o l o n ya l g o r i t h mc o m b i n i n gw i t ht h eo r t h o g o n a ls t a t i s t i c a lm e t h o d s ，c h o o s et h es u i t a b l eo r t h o g o n a lt a b l ew h i c hd e t e r m i n e st h ei m p a c to fv a r i o u sd e g r e e so fq o sp a r a m e t e r st od e t e r m i n ep h e r o m o n ev o l a t i l i t y t h ei m p a c to fv a r i o u sd e g r e e so fq o sp a r a m e t e r sm a k e sm o s to fa n t st e n dt os e l e c tt h ei m p a c to fd e g r e er o u t i n g f u r t h e r m o r e ，i nt h es e a r c hp r o c e s s ，t h ep r o b a b i l i t yo fs e l e c t i o nm e t h o d si su s e d t w og r o u p so fa n t ss e a r c hs e p a r a t e l ya n di n t e r a c tp h e r o m o n ea f t e re a c hs e a r c ht oa v o i dt h es e a r c hp r o c e s si n t ot h el o c a lm i n i m u ms o l u t i o n c o m b i n e dw i t hm u l t i p l eq o sc o n s t r a i n t s ，t h eo p t i m a lp a t hi ss e l e c t e df r o mt h et w os e l e c t e dp a t h s w h e nc h o o s i n gt h en e x tn o d e ，e a c ha n ti m p o r t st h ep r o b a b i l i t yo fs e l e c t i o nt h a th a sb e e ni n t r o d u c e di nt h el a s tt oa c c e l e r a t et h es e a r c hs p e e d e x p e r i m e n t ss h o wt h a tt h ea l g o r i t h mh a sb e t t e rp e r f o r m a n c e i tc a ns e tu pt 1 1 eq o sm u l t i c a s tt r e eq u i c k l ya n de f f i c i e n t l y , c o n v e r g e n c et ot h eg l o b a lo p t i m a ls o l u t i o nf a s t ，a n dr e d u c et h er e c o n f i g u r a t i o nf r e q u e n c yo fm u l t i c a s tt r e ed u et on o d em o b i l i t ye f f e c t i v e l y k e yw o r d s ：a dh o e ，q o s ，a n tc o l o n ya l g o r i t h m ，m u l t i c a s t关于学位论文的独创性声明本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外，本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志对研究所做的任何贡献均已在论文中作出了明确的说明。若有不实之处，本人愿意承担相关法律责任。学位论文作者签名：固输日期：刀彳年岁月) 日学位论文使用授权书本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构)送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他复制手段保存学位论文。保密学位论文在解密后的使用授权同上。学位论文作者签名：、矽蔼争指导教师签名：乏墓型l 咎日期：研年参月2 2 - 日e t 期：力力刁年岁月z 日中国石油大学( 华东) 硕士学位论文第一章前言1 1 课题背景及意义随着因特网的发展，越来越多具有q o s ( q u a l i t yo f s e r v i c e ) 要求的业务接入因特网。在网络上传输实时多媒体数据已成为可能，由此产生了大量的实时多媒体应用，如视频会议、远程教育等，这些分布式的实时应用要求网络有多播能力外，还要求有服务质量( q u a l i t yo f s e r v i c e ) 【l 巧】。服务质量体现的是消费者对服务者所提供服务的满意程度，是对服务者服务水平的一种度量和评价。同样，现代计算机网络作为计算和信息等服务的提供者，同样面临着q o s 的问题。q o s 是应用业务对网络传输服务所提出的一组可度量的要求，主要包括带宽、端到端延迟、分组丢失率、抖动、花费的代价等，网络传输相应的数据业务时，必须满足这组要求。q o s 组播路由旨在找到一个满足q o s 约束的组播树以满足q o s 应用的需求。组播是一种优化使用网络带宽的路由技术，采用组播技术，避免了不必要的数据包复制，减少了骨干网络的数据流量。随着无线技术的成熟，有越来越多的人通过无线设备连接至r j i n t e m e t a z t 6 。7 】，希望能够随时随地地对网络进行访问。支持移动成为i n t e m e t 发展的必然要求。i e t f ( i n t e m e te n g i n e e r i n gt a s kf o r c e ) m o b i l ep 工作组的移动i p ( m o b i l ei p ) 及其相关技术是主要研究内容，占据着主导地位，并取得了显著的研究成果。移动和组播的结合给两者都带来了新的挑战。在移动环境中，组播不仅要管理动态组播组成员、建立和维护组播树，还需要解决成员位置动态变化的问题。但现在i n t e r a c t中使用的组播协议，如d v m r p l 8 ，c b t 9 1 ，m o s p f 1 0 】，p i m 1 1 _ 1 3 增，通常都假设其成员是静态的，而没有考虑成员位置动态变化的情况。如果每次节点移动后都当作一个新加入的成员，则会给组播组的管理和组播树的维护带来过多的开销，增加网络的负担。另一方面，移动碑协议主要对单播进行了研究，对于组播只提出了两种基本的解决方案，但都存在着比较严重的缺陷，而在此基础上的改进方案也都还存在着比较大的缺陷。例如，非最优路由、隧道聚集、切换时延、丢包等。因此如何把i p 组播和移动相结合，为移动节点提供组播应用，是一个值得深入研究的问题。网络中的节点状态信息决定了网络能支持怎样i 拘q o s 要求，为了能够满足业务所需要的服务质量要求，须控制选择使用网络中单节点状态的有效信息，在此基础上选择相应的网络机制，例如接纳控制机制、调度机制、路由选择机制、节点状态控制机制等，从而满足使整个网络的传输过程实现某种q o s 意义上的最优。所以，对于网络中的单个第一章前言节点，通过对相应业务q 0 8 要求的信息搜索，找到最适合所用网络机制的最优节点状态，使之能够根据业务可容忍的延时、抖动和丢包率的严格要求对业务加以区分，并为业务提供确定服务质量保证【1 4 1 或者统计服务质量保证【1 5 】。移动组播中对服务质量的规范和管理非常困难。首先带宽受紧邻链路的传输活动的影响；再次，移动主机可以随时随地加入、离开或重新加入网络。例如在线观看电影时对传输带宽有一定的要求，则支持q o s 的组播路由系统就会从一组服务器中选择带宽和距离综合性能最优的组播服务器。移动组播环境中选择满足q o s 要求的最优路径成为研究的热点。基于多个不相关可加度量的q o s 路由问题是n p 完全问题【1 6 1 。现有的启发式算法，女n b s m a t l 7 1 ，d v m a 1 钔，m r p m q 1 9 】等，不是过于复杂，就是计算复杂度太高。针对这些问题，目前一般采用蚁群算法来求解。蚁群系统不依赖于具体问题的数学描述，具有很强的全局优化能力和本质上的并行性：同时，具有更强的鲁棒性、求解时间短、易于计算机实现等优点。基于蚁群系统设计动态多约束路由模型能够更好地适应新的网络应用，动态满足多约束q o s 服务需求，克服服务单一性、网络可扩展性的不足，更好地实现网络的稳定性，同时降低计算开销，提高路由效率。基于约束i 约q o s 路由模型中引入蚁群智能，将蚁群算法应用在路由计算中。主要的计算工作由源端和终端节点完成。源端接收业务请求后，根据不同的应用确定q o s 约束的尺度，并确定路由规则；而终端负责对网络蚂蚁搜索的路由进行评价，获取当前的满足q o s 的最优路由。网络蚂蚁负责从源端到目的端的路由搜索，根据各网络节点的状态信息选择路由。根据蚂蚁所选择的路由进行路径上信息素的更新，提高收敛速度，减小陷入局部极值的可能性，获得满足q o s 要求的路径吸引了众多的学者。1 2 国内外研究现状近年来，研究人员提出了一些a dh o c 网络环境下的组播路由协议，移动自组网的组播协议，根据节点的组织结构主要分为基于树状的和基于网状的。基于树状的结构简单，数据传输效率高，但是稳健性与扩展性差，如a m r o u t e 基于网状的结构支持多条路径，稳健性好，但容易引起节点冲突，且在网格内泛洪数据会引起很高的开销，如o d m r p 、r o m r 。协议按其路由策略可分为主动式和反应式。主动式又称源路由，节点通过周期性交互信息得到所有到达其他节点的路由，女l l a m r o u t e ；反应式又称按需路由，节点只查找和维护自己需要使用的路由，避免了维护无用路由信息所造成的资源浪费，如o d m r p 。移动组播依赖于移动和组播的特性使得提供q o s 变得非常困难。2中国石油大学( 华东) 硕士学位论文目前，在i n t e r n e d 2 支持q o s 的体系结构主要有两种：i n t s e r v 2 0 1 和d i f f s e r v t 2 1 1 。针对无线a dh o c 网络，文献【2 2 】的作者提出了一种称为灵活q o s 模型( f q m m ：f l e x i b l eq o sm o d e lf o rm a n e t s ) 的体系结构。f q m m 是第一个针对无线a dh o c 网络的q o s 模型，它的主要优点是根据网络状态的变化，作自适应的业务量调节( c o n d i t i o n i n g ) ，并对q o s 作定性保证，但它同时存在如下缺点：1 ) 实现复杂。由于网络中的节点既要支持i n t s e r v 的基于流的资源分配，又要支持d i f f s e r v 的基于类的资源分配，同时每个节点既可能是边缘节点又可能是核心节点，因此，要求每个节点均实现i n t s e r v 和d i f f s e r v 的相关功能。2 ) 对于混合的资源分配策略，存在高优先级的流和低优先级的流各应占多大比例的问题；对低优先级的流，由于采用d i f f s e r v 的基于类的资源分配策略，因此，在a dh o e域内，仍存在与d i f f s e r v 相似的资源分配问题。德国通讯网络学院在探讨移动i p v 6 与密集模式协议独立组播( p i m d m ，p r o t o c o li n d e p e n d e n t m u l t i c a s td e n s em o d e ) 的互操作性时，提出的远程加入( m i p r s ) 和双向隧道( m p b t ) 。h r i s h i k e s hg o s s a i n , 贝1 主要针对组播组的源是移动节点的情况提出了解决方案。在该方案中，当一个移动节点既是组播组的接收者也是发送者的时候，它通过从移动节点当前所在处向其家乡代理的单向隧道转发组播数据，由家乡代理真正的以组播的方式再将组播包发送出去，对于组播数据的接收直接采用远程加入的方式。中国科学院的孙利民提出了结合家乡签署h s ( h o m es u b s c r i p t i o n ) 和远程签署r s ( r e m o t es u b s c r i p t i o n ) 两种基本算法，采用组播区域代理作为参与互联网组播路由的组播路由器，为整个区域的移动主机提供组播服务。在当前m s a ( m u l t i c a s ts u b n e ta g e n t )和p m s a ( p r e v i o u sm s a ) 之间建立隧道。同时，当前m s a 申请加入组播组，减少了组播服务中断的时间，也优化了组播数据的传输路径：在互联网级，组播路由器通过组播路由协议交换组信息，通过建立组播树传输组播数据。局域网的组播路由器是本地主机到组播骨干网的接入点。通过采用区域的层次型的路由结构，减少组播树重构的开销。北京交通大学的沈波提出移动网络组播方法d m a d y n a m i cm u l t i c a s ta g e n t ) 。引入路径度量值：定义不小于l a d 与l d s l 匕值的最小整数为路径度量值，其中l a d 表示移动网络当前附着的接入路由器a r 与d m a 间的拓扑距离，l d s 表示d m a 与组播源间的拓扑距离。移动网络经过的子网的路径度量值之和小于给定门限时，重新选择d m a ，即进入另个区域。第一章前言j l s o b r i n h o ，a s k r i s h n a k u m a r 从m a c 层考虑在m a n e t 中对q o s 的支持。采用这种方式，主机实时的利用优先级来竞争使用无线电频道。移动主机的优先级是由这台主机等待无线电频道空闲下来的时间决定的。这种优先级方式给予了实时传输比较高的优先级并且它能够保证实时数据包能够进行无冲突的传输。c r l i n ，j s l i u 提出了一种可以保证一条具有多跳的路径的q o s 机制。在这里假定了一个基于c d m a 的t d m a 模型。为了避免冲突给邻居主机分配不同的传输代码。每一个传输代码是一个时帧。每一帧由标号为1 到n 的n 个时间片组成。共同相邻于一台主机的两台主机不能用相同的传输代码同时向这台相邻的主机发送数据，否则就会产生冲突。但是如果他们的传输代码是不一样的，那么数据传输的状况就会得到改善。s m u r t h y ，j j g a r c i 吐上u n a - a c e v e s 提出了一种基于表的协议来支持q o s 路由。这个协议在每一个节点尽可能为每一个目的节点提供端到端的状态信息。这种状态信息被d s d v 协议定期的更新。国防科技大学的陈岩提出一种再励学习蚁群路由算法对多q o s 约束问题进行求解，算法通过对蚂蚁搜索路径进行评价产生再励信号，并根据再励信号采取了不同的信息更新策略，提高算法寻优能力和收敛速度。南京邮电大学的谢铎针对通信网络中存在的服务质量问题提出了满足q o s 约束的最优路由选择算法一蚁群算法。通过动态地调整信息素的挥发度和采用最优、最差路径信息素全局更新策略来较快地收敛到全局最优解。北京交通大学的卢苇针对a dh o e 网络q o s 路由存在的局限性提出了一种基于免疫蚁群算法的q o s 路由算法。该算法前过程利用人工免疫算法( a r t i f i c i a li m m l m ea l g o r i t h m ，剐队) 快速寻求较优的可行解，在此基础上算法后过程采用蚁群算法( a n tc o l o n ya l g o r i t h m ，a c a ) ，利用前过程中人工免疫算法获得的较优可行解，进一步提高求解效率。1 3 本课题研究内容本课题主要讨论如何根据节点的移动计算满足q o s 要求的组播树，节点移动时尽量减少重新计算和建立组播树的开销。利用蚁群算法的基本原理，研究了多约束q o s 组播路由算法。构造多约束q o s 组播路由模型，结合正交实验方法，分析各q o s 参数影响度的大小，影响度较大的路径拥有较高的优先级。搜索过程中，两组蚂蚁分别进行，每只蚂蚁参考该路径上次被选择的概率，加快搜索时间，而且避免陷入局部最小解。4中国石油大学( 华东) 硕士学位论文本课题的研究主要包括以下几个方面：( 1 ) 基于q o s 的移动组播树建立的研究节点的移动往往使组播树进行重新计算和建立，引入过多的处理开销和协议开销，引发组播路由协议的收敛性问题，影响组播转发的稳定性。如果保持组播转发树不变则又会带来路径非最优、路由冗余等问题。根据节点的移动，建立组播路由模型；在保证路径较优的前提下，对组播树的构造进行研究，尽量的减少根据q o s 信息建立的组播树的重建开销，提出一种减少组播树重建频率的构造方法。( 2 ) 蚁群算法在基于q o s 的移动组播路由算法中的应用蚁群算法采用分布式控制，改良型的全局搜索方法求解全局最优解；具有潜在的并行性，搜索时从多个点进行。本课题将对其进行深入的研究，根据每条链路上的q o s约束进行路径选择，提高对较优解的构造能力。在搜索过程中，两组蚂蚁分别进行搜索，每搜索完一次进行信息素的交互，避免搜索过程中陷入局部最小解。结合多个q o s 约束，从选择的两组路径中选出一条最优路径。每只蚂蚁在选择下一节点时引入该路径上次被搜索时的选择概率，加快搜索速度。( 3 ) 仿真实现利用网络模型对本课题提出的算法和已有的相关算法进行仿真实验，得出实验数据并对不同算法的实验结果进行比较，最后得出实验结论。实验证明，本文算法在一定程度上减少了组播树的重构开销，加快了蚂蚁的搜索时间。1 4 论文的组织结构本文的组织结构安排如下：第一章为前言，介绍课题产生的背景及意义、国内外q o s 组播路由的研究现状，给出课题研究的主要内容及研究方法。第二章首先阐述了移动组播技术的概念、评价标准、几种典型的移动组播算法及移动环境中口组播面临的新问题。接着介绍了q o s 路由的相关概念、q o s 网络模型及度量标准。第三章介绍了蚁群算法的相关理论基础知识。包括蚁群算法的原理、特点、模型、应用及优缺点。第四章讨论了如何在满足q o s 的基础上，尽量减少因节点的移动而重建组播树的开销。在z r p 协议中考虑q o s 因素，获取最大网络拓扑图，每个区域选择一个区域代理5第一章前言转发数据，选择本区域内移动频率最小的节点作为区域代理。第五章分析了蚁群算法在q o s 路由问题中的应用，采用正交实验方法研究各q o s参数影响度，确定多约束q o s 组播路由模型。采用两组蚂蚁分别进行搜索，在搜索过程中，每次搜索都借鉴上次搜索的概率，避免陷入局部最小解。最后对本文所做工作进行总结，并指出下一步的研究方向。6中国石油大学( 华东) 硕士学位论文第二章q o s 移动组播技术基础2 1 移动组播技术2 1 1 组播的概念和定义1 9 8 5 年，s d e e r i n g 和d c h e r i t o n 发表了“h o s t gr o u p s ：am u l t i c a s t e xt e n s i o nt oi n t e m e tp r o t o c o l ，这可以说是在i n t e m e t 中加入组播支持的第一步。s d e e r i n g 又在1 9 8 9 年8 月发表了“h o s te x t e n s i o n s f o ri pm u l t i c a s t i n g ( r f c l11 2 ) ，这个提案最终取代了i 强c 9 9 6 并成为口组播的官方标准。网络数据传输主要有单播，组播和广播技术三种方式：单播( u n i c a s t ) 传输：在发送者和每一接收者之间实现点对点网络连接。如果一台发送者同时给多个接收者传输相同的数据，也必须相应的复制多份相同的数据包。如果有大量主机希望获得数据包的同一份拷贝时，将导致发送者负担沉重、延迟长、网络拥塞，为保证一定的服务质量需增加硬件和带宽。组播( m u l t i c a s t ) 传输：在发送者和每一接收者之间实现点对多点网络连接。如果一个发送者同时给多个接收者传输相同的数据，只需复制一份相同的数据包。它提高了数据传送效率。减少了骨干网络出现拥塞的可能性。主要用于视频会议等应用场合，这种应用需要将一份数据同时发送给多个用户。而组播技术具有带宽利用率高、减轻主机路由器的负担、避免目的地址不明确所引起的麻烦等优点，从而满足这种应用。广播( b r o a d c a s 0 传输：是指在p 子网内广播数据包，所有在子网内部的主机都将收到这些数据包。广播意味着网络向子网每一个主机都投递一份数据包，不论这些主机是否乐于接收该数据包。所以广播的主要缺点就是每个广播都要发送数据至所有机器，消耗了所有机器上的资源，即使数据要被网络中大多数机器所丢弃。而且使用范围非常小，只在本地子网内有效，通过路由器和交换机网络设备控制广播传输。组播可以大大的节省网络带宽，因为无论有多少个目标地址，在整个网络的任何一条链路上只传送单一的数据包。如图2 1 所示，组播的网络结构和数据传递过程。7第二章q o s 移动组播技术基础接收者l凄收者2接收者3接收者4接收者5凄收者6图2 - 1 组播数据传递过程f i 9 2 - 1t h em u l t i c a s td a t at r a n s f e rp r o c e s s2 1 2 移动组播算法的评价标准在移动环境中，由于移动节点常常使用无线链路，因此网络资源非常有限，其中最明显的特征就是受限的链路带宽和较高的错误率。而且一般情况下移动节点的体积往往比较小，因此它拥有的能量供应、处理器能力，以及存储能力等都比较低。在这种情况下，m 组播所具有的高效使用资源的优点对于移动节点来说尤为重要。定义1 ( 移动组播( m o b i l em u l t i e a s t ) ) 。组播和移动相结合、在移动环境中进行i p 组播的机制称为移动组播。相应地，可以定义移动组播算法、移动组播协议等相关内容。移动组播算法和协议的评价标准【冽主要包括以下内容：可扩展性：当组播组成员中移动节点的数量增多时，不会使组播的性能发生严重下降。高效：不会由于支持移动而给i p 组播的应用引入过多的开销。这些开销主要包括组播组管理的开销、组播转发树维护的开销以及防止切换时丢包的开销。鲁棒性：组播应用不会由于节点的移动而受到影响( 例如发生中断) ，或者影响很小。8中国石油大学( 华东) 硕士学位论文与具体路由算法无关：应尽量做到与具体的组播路由算法无关。简单：应尽可能地简单，从而能够通过引入尽可能少的修改实现与现有i n t e m e t协议和机制的互操作。可靠性：移动节点发生切换时，特别是快速切换时，不会引入组播包的丢失。2 1 3 几种典型的移动组播算法1 、双向隧道( h i d i r e c t i o n a lt u n n e l 。简称m 口b t )在该算法中，移动节点及其家乡代理之间需要建立双向隧道，移动节点通过双向隧道加入退出组播组，并且通过该隧道发送和接收组播包。因此，这里要求移动节点的家乡代理同时也是一个组播路由器。当移动节点作为组播接收者的时候，它通过隧道向家乡代理发送i g m p 报文，请求加入，当家乡代理接收到i 咖报文以后，将该移动节点加入到组播组中，然后组播路由协议建立到家乡网络的组播转发树。在真正转发组播包时，组播包首先被转发到家乡网络，由家乡代理再将组播包通过隧道以单播的方式发送给移动节点。当移动节点作为组播发送者的时候，移动节点首先通过隧道将组播包发送给家乡代理，然后由家乡代理负责通过组播转发树以组播的形式发送该组播包。该算法的优点是将节点的移动性隐藏了起来，移动对于组播协议来说是透明的，不会给组播带来额外的负担。特别是对于源树方式的组播路由协议( 如d v m r p ，p i m d m ，m o s p f ) ，在组播发送者移动的情况下，不需要重新计算组播树，减少了计算和通信负担。但是，双向隧道算法同时也存在着比较严重的缺陷：( 1 ) 该算法使用的是三角路由，远非最优路由，因此链路开销较大。特别是当移动节点远离家乡网络且加入到外地链路的本地组播组时，该算法引入的额外开销将非常显著，并且对于像视频会议这种对链路带宽要求较高的组播应用，可能会由于外地网络与本地网络之间的链路质量问题而无法应用于移动节点。( 2 ) 在该算法中，家乡代理以单播的形式通过隧道为每个移动节点转发组播包。这样，当家乡代理有多个对应的移动节点在同一个外地链路时，每个移动节点都会通过家乡代理得到组播包的一个拷贝。这样，外地代理将从不同的隧道接收多个重复的拷贝，因而导致“隧道聚集问题 2 3 】。外地代理f a 通过多个隧道接收同一个组播包的多个拷贝，并且在外地链路中以单播的形式递交给每个移动节点。显然，这种方式的效率很低，9第二章q o s 移动组播技术基础链路带宽的浪费也很严重。( 3 ) 可以对双向隧道算法加以改进，家乡代理根据外地代理建立组播隧道，并且外地代理以链路级组播的方式转发组播包。这样就解决了同一个家乡代理向外地代理建立多个隧道转发相同组播包的问题，同时也提高了链路的利用率。但是即使改进后，当外地链路中有多个移动节点属于相同的组播组，并且这些移动节点来自不同家乡网络的时候，还是会出现多个家乡代理分别通过隧道向外地代理传送相同组播包的情况以及外地代理向移动节点组播重复数据的问题。( 4 ) 家乡代理成为“失效集中点( c e n t r a lp o i n to f f a i l u r e ) 【2 4 1 。家乡代理的处理任务以及负载会随着它所服务的移动节点数量的增多而显著增加，导致组播转发效率降低，并且增加了错误发生的概率。特别是当家乡链路中同时有多个组播源，并且组播转发树采用源树方式时，由于这些组播树都是以家乡代理为根节点，因此家乡代理的出错将导致多个组播应用的中断，家乡代理因此成为失效集中点。( 5 ) 在这种算法中。组播在某种程度上已经演变成了单播的形式。2 、远程加入( r e m o t es u b s c r i p t i o n 简称m i p - r s )在该算法中，移动节点改变所在网络以后，每次都是重新加入到组播组中，并重新计算与之对应的组播树。移动节点即使是在外地链路，其组播应用的工作方式也都与固定的节点相同。该算法最大的优点在于它非常简单，可以直接使用现有的组播协议，无须建立任何隧道，组播数据也无须进行任何封装和解封装，因此不会有隧道聚集问题。它的另一个显著的优点在于，组播包能够沿着最优路径进行转发，不存在三角路由问题。但是，该算法同样存在着很多不足之处：( 1 ) 当移动节点作为组播源时，该算法只适合于共享树。因为对于有源树，由于需要重新计算和建立整个组播转发树，因此会引入过多的协议开销，同时还会引发组播路由协议的收敛性问题以及组播转发的稳定性问题。( 2 ) 当移动节点作为组播接收者并发生切换时，由于存在组播组的重新加入过程以及组播转发树的更新过程，因此切换时延相对较大，从而会导致较多的组播包丢失，影响了组播应用的可靠性。特别是在节点快速移动、频繁切换的情况下，组播组的管理以及组播转发树的维护都将有过多的开销和负担。( 3 ) 即使切换可以做到非常迅速，切换时延几乎为0 ，但是由于网络的动态性，各个子网接收组播包的时延不同，因此仍然产生移动环境中特有的“同步丢失”( o u t o f - s y n c h1 0中国石油大学( 华东) 硕士学位论文p r o b l e m ) t 2 5 】问题，所以会导致包丢失问题的产生。( 4 ) 当移动节点同时是多个组播组的成员时，移动切换过程中需要对它所加入的每个组播组进行剪枝、重新加入，这将极大地消耗移动节点的能量( 如电池) ，限制了移动节点的组播应用。因此，远程加入算法适合于节点移动的速率相对较低、能够保持较长静止状态的情况。3 、m o m ( m o b i l em u l t i c a s tp r o t o c 0 1 )m o m 2 6 1 算法以双向隧道算法为基础，主要是针对隧道聚集问题提出了改进。算法引入了“代表组播服务提供者 ( d e s i g n a t e dm u l t i c a s ts e r v i c ep r o v i d e r ，简称d m s p ) 的概念，目的在于避免通过隧道向同一个外地代理转发重复的组播包。外地代理为每个组播组从一组家乡代理中选择一个作为d m s p ，只有d m s p 与外地代理之间建立隧道并转发组播包。这样，对于每个组播包，外地代理只会接收到它的一个拷贝。相对于双向隧道算法，m o m 提高了移动组播应用的可扩展性，并且随着移动组播成员的增多，其性能有明显的提高。但是，由于d m s p 是移动节点家乡代理的代表，因此m o m 也存在着三角路由问题。另外，当因节点移动而改变外地代理以后，新、旧外地代理都需要重新计算d m s p ，以确定是否需要重新进行选择，这给网络增加了处理开销。而且一旦需要重新选择d m s p ，就又会带来d m s p 切换问题【2 7 】。d m s p 切换主要发生在两种情况：一种情况是新的移动节点加入到外地链路中，并且它的家乡代理更加适合作为d m s p ：另一种情况是d m s p作为家乡代理所对应的所有移动节点都离开了该外地链路。当移动节点发生切换时，它的家乡代理一般都能很快地知道新的外地代理，从而得到新的d m s p 的信息，然而原外地代理却要等到超时发生之后才知道移动节点发生了切换，然后再重新选择d m s p 。在选择得到新的d m s p 之前，没有家乡代理向它转发组播包。这样，在切换过程中，外地链路中属于该组播组的所有移动节点都将丢失组播包。因此，m o m 在双向隧道算法的基础上又引入了切换丢包问题。而且，d m s p 的切换不仅影响了它自己对应的移动节点，原外地链路中那些由它服务但属于其他家乡代理的移动节点也都会出现组播包丢失的问题。特别是在组播组成员比较少的情况下，d m s p 切换发生的频率会更高。4 、r b m o m ( r a n g e - b a s e dm o m )该方案【2 8 1 在m o m 的基础上进行了改进，其中心思想在于寻求最短转发路径和频繁重建组播树之间的折衷，使得组播包总是能够以“接近 最优的路径进行转发，并且无第二章q o s 移动组播技术基础须为维护组播树花费过多的开销。r b m o m 为每个移动节点选择一个组播家乡代理( m u l t i c a s th o m ea g e n t ，简称m h a ) ，由它负责通过隧道把组播包转发给移动节点的外地代理。每个移动节点只能有一个m h a 。r b m o m 将“服务范围 引入至i j m h a 中，m h a 只能为那些在其服务范围内的外地链路中的移动节点服务，一旦移动节点离开了这个服务范围就需要重新选择m h a ，即进行m h a 切换。因此，m h a 会随着移动节点位置的变化而动态地变化。最初的时候，m h a 就是家乡代理。m h a 切换的具体方式如下：移动节点的家乡代理记录了该节点当前m h a 的信息，当节点移动到一个新的外地链路时，新的外地代理从家乡代理处获得m h a 的信息，然后依此计算出它与m h a 之间的距离。如果距离大于m h a 的服务范围，则需要重新选择m h a 。比较简单的方式是直接指定新的外地代理作为新的m h a 。新的m h a 需要加入到组播组中，相应地更新组播转发树，同时通知移动节点的家乡代理更新m h a 的信息。如果移动节点仍然在m h a 的服务范围之内则不需要作任何改动，新的外地代理只需与m h a 建立联系即可。m o m 和远程加入算法实际上是r b m o m 方式的两种极端情况：当服务范围无穷大时，r b m o m 实际上是m o m ，此时m h a 就是移动节点的家乡代理，并保持不变；而当服务范围为0 时，r b m o m 演变为远程加入算法，此时m h a 就是移动节点的外地代理，移动节点改变外地链路后，其m h a 也需要相应地改变。由于是一种折衷算法，r b m o m 相对于远程加入算法，减少了组播转发树更新的频率，从而降低了组播树的维护开销；同时，它的组播转发路径是接近最优的，与双向隧道算法相比有了较大改进。因此具有较好的协议性能，而且在r b m o m 方式中，m h a 的服务范围可以根据移动节点的数量和移动特性( 如移动速率) 进行相应的控制，增强了对网络的适应性。但是，r b m o m 中仍然存在m h a 的切换问题以及切换丢包问题。另一方面，为m h a引入服务范围虽然带来了灵活性，但是并没有提出如何根据网络情况选择服务范围，从而使移动组播应用的性能达到最优的方案。如果服务范围选择不当，r b m o m 可能退化为m o m 或远程加入算法。最后为了动态地选择服务范围，m h a 和外地代理还需要记录节点移动的有关特性。5 、m o b i c a s t该方案【2 7 】适用于小型无线蜂窝网络。由于规模比较小，因此具有节省移动设备收发器的能源、数据吞吐率较高、能够获得移动节点更准确的位置信息以及更加有效地使用1 2中国石油大学( 华东) 硕士学位论文无线频率等优点。每个无线蜂窝网络有一个基站( b a s es t a t i o n ，简称b s ) ，它作为移动节点的网关为移动节点提供连接i n t e r n e t 的服务。m o b i c a s t 中最明显的特点就是引入了分层的移动管理，把节点的移动性与主要的组播转发树相分离。这一点和m i c r 0 m o b i l i t y l 2 9 。0 1 的思想类似，即把网络对移动的支持方式分为m a c r o 和m i c r o 两级，在m a c r o 中采用移动i p 机制，而在m i c r o 层则采用m i c r o m o b i l i t y的有关机制。m o b i c a s t 把物理上相邻的多个无线蜂窝网组成一个区域，并提出了区域外地代理( d o m a i nf o r e i g na g e n t ，简称d f a ) 的概念。每个区域对应于一个d f a ，由它负责移动节点组播包的发送和接收。例如，校园网络。该网络中可以只有一个d f a ，它为校园网中所有的移动节点提供组播服务。当移动到一个新的外地区域以后，移动节点首先向该区域