（电子科学与技术专业论文）计算机网络中的组播路由算法研究.pdf

硕一i j 学位论文 a bs t r a c t w i t ht h er a p i dp o p u l a r i z a t i o no fi n t e r n e ta n dt h er a p i dd e v e l o p m e n to fs o m e h i g h b a n d w i d t ha p p l i c a t i o n s ，t h e r eh a v eb e e nm a n yn e wc o m m u n i c a t i o ns e r v i c e s ，s u c h a sv i d e oo nd e m a n d ，e - m a i lb l a s t s ，o n l i n eg a m e s ，d i s t a n c el e a r n i n g ，v i d e oc o n f e r e n c e a n ds oo n s u c ha p p l i c a t i o n sc o n s u m ea m o u n t so fn e t w o r kr e s o u r c e ss i g n i f i c a n t l y , a n d h a v eah i g h e rq u a l i t yo fs e r v i c er e q u i r e m e n t sb ym u l t i p l eu s e r s m u l t i c a s ti sa ne f f e c t i v e w a yt or e d u c en e t w o r kb a n d w i d t hc o n s u m p t i o na n di n c r e a s e d a t at r a n s m i s s i o ne f f i c i e n c yo f c o m m u n i c a t i o nw h i c hi ns u c ha p p l i c a t i o n sh a sb e e nw i d e l yu s e d t h ep r o b l e m so fq o s m u l t i c a s tr o u t i n gw h i c hr e s e a r c hh o wt ob e t t e rr e a l i z et h em u l t i c a s tf u n c t i o nu n d e rm e e tt h e d e m a n do fs e r v i c eq u a li t yb e c o m ear e s e a r c hh o t s p o t t h i sp a p e rr e s e a r c h e sa n da n a l y z e sav a r i e t yo fm u l t i c a s tr o u t i n ga l g o r i t h m ， o b t a i n e dt h e a d v a n t a g e sa n dd i s a d v a n t a g e s o fv a r i o u sa l g o r i t h m s ，a n a l y s i so f a l g o r i t h mb a s e do na n tc o l o n ya l g o r i t h ma n dd e l a y - c o n s t r a i n e dm u l t i c a s tr o u t i n ga n d a l g o r i t h mb a s e do nc l o n ea l g o r i t h mf o rd e l a y - c o n s t r a i n e dm u l t i c a s tr o u t i n g o nt h e b a s i so ft h e m ，t h i st o p i ch a sd e s i g n e dac l o n a lc e l e c t i o na l g o r i t h mw i t hr e c e p t o r e d i t i n ga n da no v e r a l lo p t i m i z er o u t i n ga l g o r i t h mb a s e do nc l o n i n gs t r a t e g yi m p r o v e d t h ec l o n a ls e l e c t i o na l g o r i t h mw i t hr e c e p t o re d i t i n gi sb e t t e rt h a nt h eu s u a lc l o n a l s e l e c t i o na l g o r i t h m t h eg o o dg e n es e g m e n ti nt h ei m m a t u r i t ys u b p o p u l a t i o nw a s a d o p t e da n dr e c e p t o re d i t i n gw a sc o n d u c t e db a s e do nt h ep r i n c i p l eo fm i n i m u mc o s t a n dd e l a yc o n s t r a i ns e p a r a t e l y r e s u l t ss h o wt h a tr e c s ac a ns e a r c hp r o m p t l yf o r o p t i m u ms o l u t i o nw i t h o u tap r e p a r e dr o u t i n gs e t t h ep r o c e s si sa l s of e a t u r e dl o w e r c o m p u t a t i o n a lc o m p l e x i t ya n dh i g h e rs t a b i l i t y t h i sp a p r eh a sa l s ob e e nu s e dr e c s a t ot h es o l u t i o no ft h eq o sp r o b l e m si nm u l t i c a s tr o u t i n g ，p r o p o s e dao v e r a l lo p t i m i z e m u l t i c a s tr o u t i n ga l g o r i t h mb a s e do ni m p r o v e dc l o n i n gs t r a t e g y a f t e rf u l f i l l i n gt h e c o n d i t i o no ft h et i m ed e l a yr e s t r a i n t ，ap a r a m e t e rq ，w h i c hc o n s i d e r st h eb a l a n c et h e t h r e ep e r f o r m a n c ei n c l u d i n gt i m ed e l a y ，b a n dw i d t ha n dt h ee x p e n s e ，i sd e f i n e da n d i n t r o d u c e dt om e a s u r et h eo v e r a l lp e r f o r m a n c e ，m a i n t a i n i n gt h ec o m p r o m i s ea n d b a l a n c ea m o n gt h et h r e ei n d i e s t h i so v e r c o m e st h ep r o b l e mi nt r a d i t i o n a ls o l u t i o n st o m u l t ic a s tr o u t i n g ，n a m e l yt h ei m p r o v e m e n to fap e r f o r m a n c ep a r a m e t e rr e s u l t e di n s e r i o u sd e g e n e r a t i o no fo t h e rp a r a m e t e r s t h er e s u l t so fs i m u l a t i o nt e s t si n d i c a t ei t s h i g hs e a r c h i n ge f f i c i e n c y ，c a p a b l eo fa d j u s t i n gt h ew h o l ep e r f o r m a n c eo ft h em u l t i c a s t r o u t i n ga n di m p r o v e ds e r v i c eq u a l i t yo ft h eq o s s oi t c a nb ea p p l i e dt om u l t i c a s t a r e a ss u c ha sv i d e o o n d e m a n d i l i k e yw o r d s ：m u l t i c a s tr o u t i n g ；c l o n a ls t r a t e g i e s ；q u a l i t yo fs e r v i c e ；c o m p r e h e n s i v e p e r f o r m a n c e ；g e n e t i co p t i m i z a t i o n i v 硕i ：学位论文 1 1 课题背景及意义 第1 章绪论 1 选题依据 现代社会，随着i n t e r n e t 迅速普及，出现了许多新型通信业务，网络的作用己 从简单信息传送发展到远程教学、视频会议、数据分发和网络游戏等业务功能( ， 渗入到人们日常工作和生活的每个角落。由于网络功能的多样性和复杂化，它们 对网络的服务质量( q u a l i t yo f s e r v i c e ，q o s ) 的要求越来越高。服务质量是指发送 和接收信息的用户之间以及用户与传输信息的服务网络之间关于信息传输的质量 约定。它包括网络中端到端时延、带宽、代价、丢包率等多方面的因素。其中， 端到端时延是实时通信应用中的一个基本方面，如果网络传输延时过长，用户视 觉和听觉上的效果就会不好，严重时可能引起语义的无法理解或者误解；特别是 对于视频点播，网络必须提供足够的带宽和可以接受的丢包率以保证可靠的视频 质量1 2 j 。而传统的单播和广播通信方式，数据的发送只提供“尽力而为( b e s t e f f o r t ) 服务，已经不能满足这些服务质量的要求，一种有效的解决办法就是组播技术。 因此，研究q o s 组播路由算法来提高网络资源利用率，降低网络成本，达到较好 的服务质量是很有必要的。 用户希望的服务质量主要是：延时小，延时抖动小，带宽大，丢包率小，代 价小。而这些指标都是相互制约，一些指标的提高通常是以另一些指标的下降为 代价的，不可能同时满足用户所有的要求，因此这类组播通信没有精确的解决方 案，它是网络中的n p c o m p l e t e 问题，这类问题没有最优解，只有次优解或者满 意解，目前大多采用启发式算法来解决；对于q o s 组播路由问题，通常要根据特 定的网络技术应用提出特定的服务质量要求。 2 课题意义 近年来，组播支持的网络多媒体应用日益增多，并且这些应用对服务质量要 求很高，这正是目前组播技术面临的挑战，即组播路由对服务质量的支持1 2 j 。组播 路由算法的目的是确定组播树，并且一般用树的“费用 来衡量组播树的质量， 组播树费用是指树中所有链路费用的总和，在实际应用中，有效利用网络资源是 非常重要的，因此要求组播树的费用最小。针对目前q o s 组播路由算法中存在的 缺点，如算法复杂收敛速度慢、算法稳定不好，容易过早陷入早熟、对组播路由 整体性能把握不均衡等。我们提出一种基于改进克隆策略的整体优化组播路由算 计算机m 络中的组播路由算法研究 法，该算法在满足延时约束的条件下，综合考虑延时、带宽、代价这三个性能指 标，并使之均衡，引入了一个综合性能指标q 作为适应度函数，使得这棵组播树 的代价和延时较小，带宽较大，提高了组播的服务质量，同时对个体进行了基因 优化操作，收敛速度快且算法稳定可靠。该方法不仅对组播路由的理论研究具有 重要意义，而且对组播的现实应用领域的研究也具有广阔的实际应用价值。 1 2 组播技术的介绍和发展趋势 组播是一种允许一个或多个发送者( 组播源) 发送单一的数据包到多个接收 者( 一次的，伺时的) 的网络技术。因此它是多方通信方式，也称多点播送或多 路广播，它有助于减少主机的工作量，控制网络的传输流量，提高数据传送效率， 避免网络拥堵，是一种优化网络使用带宽的传输新技术。目前，许多网络业务包 括远程会议、邮件群发、网络电话、网络游戏等应用都对组播提出了需求。组播 业务可以在o s i 参考模型的网络层或者应用层实现，下面对这两种实现体制分别进 行介绍。 1 2 1 i p 组播 1 9 8 8 年d e e r i n g 提出了将组播的功能机制增加到数据网i p 层的组播实现体系 结构，这种体系结构称为i p 组播( i pm u l t i c a s t ) 。经过2 2 年的发展和应用，i p 组 播形成了比较完整的组播协议体系，包括组播地址管理协议、组播主机和网络的 交互协议、组播路由协议等。目前i g m p 协议和p i m s m 组播路由协议在面向内 部网络的路由器都得到实现，可以维护主机和网络设备之间的组员关系。i g m p 是 互联网组管理协议，是主机和路由器之间建立和维护组播组成员关系的协议；而 p i m s m 是稀疏模式的协议无关组播协议。在内部网络中，i p 组播已经得到一些 应用，从开始的标准i p 组播业务模型到后来s s m 业务模型【3 j ，但是由于对组播业 务的管理还缺乏有效的解决方案，路由器的组播功能往往没有开放。i p 组播在网 络中的运用仍是零散有限的，并没有取得预期的成功。一方面，因特网中的网络 极少开放i p 组播业务，至今还没有全因特网范围的组播业务；另一方面，基于i p 组播的上层应用也屈指可数，相对于w w w 等新的体系结构，i p 组播的发展十分 缓慢【4 1 。 从因特网发展的过程和i p 网络的体系结构看，阻碍i p 组播业务发展的主要因 素利5 】： ( 1 ) i p 组播体系结构可扩展性差。路由器需要为每个活动的组播组维护路由状 态信息，随着网络中并发的组数量增加，网络中大量的活动组将需要路由器巨大 的存储和处理开销。此外，组播组成员的动态使网络必须动态维护路由状态，更 增加了组播路由器的处理开销，并且转发组播数据报文需要更长的处理时间。 硕l j 学位论文 ( 2 ) 开放的i p 组播模型在开放的因特网环境中难以支持有效的管理和控制机 制。为了保证数据的传输安全，组播要求只有注册的发送者才可以向组发送数据： 而且只有注册的接收者才可以接收组播数据，然而i p 组播业务模型很难保证这一 点。它是一种任何源、任何接收者的开放模型，在这种模型下，接入控制、组管 理、组地址的协调机制一直没有种有效的解决方案。 ( 3 ) 组播数据流的计费方式难以确定，网络运营商之间的利益取向不同。目前 要打破了传统的计费模式，当前的组播的服务模式没有支持组播的付费，要在当 前的服务模式和协议体系结构下普遍化和商业化，i p 组播会遇到很多困难【6 1 。 1 2 2 应用层组播 因为各种因素阻碍了i p 组播在因特网中的配置，一些研究者开始反思在网络 层实现组播服务是否是最为合适的选择，提出了将复杂的组播功能从路由器转移 到终端系统实现的新思想，即在应用层实现组播服务，称为应用层组播( a p p l i c a t i o n l a y e rm u l t i e a s t ) ，又称端系统组播。应用层组播网的节点是组播成员主机，数据路 由、复制、转发功能都由成员主机来完成，成员主机之间建立一个叠加在i p 网络 之上的、实现组播业务逻辑的功能性网络，称为叠加网( o v e r l a yn e t w o r k ，又称为 覆盖网络) ，主机基于自组织算法建立和维护叠加网。i p 组播的数据沿着物理链路 复制和转发，而应用层组播的数据则在主机实现复制和转发，数据报沿着逻辑链 路转发，多跳逻辑链路可能经过同一条物理链路【7 1 。 自组织算法是端系统组网的核心功能和机制，自组织算法的主要功能包括： 周期性地交换节点状态信息，通报组成员状态；周期性地收集网络逻辑连接的带 宽、时延等动态参数；动态地调整叠加网拓扑。 应用层实现组播功能可以避开网络层实现组播功能的许多难题：一是应用层 组播的状态在主机系统中维护，不需要路由器保持组的状态，解决了业务的扩展 性问题，网络可以支持大量的组播组。二是组播应用可以随时部署，不需要网络 设备的升级和功能扩展，应用层组播可以根据所承载的不同业务的需求建立不同 的叠加网。三是可以简化组播的控制、可靠等功能的实现，建立在网络连接之上 的应用层组播可以使用t c p 、u d p 服务，如可以利用t c p 的可靠和拥塞控制简化 组播的可靠和拥塞控制。所以应用层组播思想提出后的几年里，取得了飞速的发 展，多个研究机构对应用层组播进行研究，提出了许多应用层组体系结构，如： e s m ( e n ds y s t e mm u l t i c a s t ) ，y o i d ，s c a t t e r c a s t ，o v e r c a s t ，a l m i ，h m ( h o s tm u l t i c a s t ) 笙【6 l 寸。 当然，应用层组播也有许多的局限：一是主机对i p 网络的拓扑结构不了解， 只能以启发式的方式，根据延时和带宽等参数来建立叠加网，这种逻辑链路不能 充分地利用底层网络资源，叠加网的多条链路可能经过同一条物理链路；二是端 计算机m 络巾的组播路f i 算法研究 系统对i p 网络的了解有限，节点在加入组网时，也只能通过外在的网络性能参数， 例如延时、带宽等，选取的逻辑链路难以优化；三是相对于路由器而言，端系统 稳定性较差，主机性能不高，复制和转发工作由应用层通过软件实现，效率较低【s j 。 尽管应用层组播的效率比i p 组播低，但是在i p 组播服务没有广泛提供的前提 下，应用层组播还是值得研究和应用的。 1 2 3 组播技术的发展趋势 由于组播技术具有“一次发送，多点传输 、节省带宽以及按组播组接收数据 的优点和特性，因此组播技术在计算机网络有着十分广泛的应用，虽然现在大规 模的组播应用还有许多难题要克服，但组播应用的前景仍比较乐观，尤其是在多 媒体业务日益增多的情况下，组播有着巨大的市场潜力。在中国，各运营商在宽 带网络建设中都投入了大量的资金进行“圈地运动，但是对于如何利用这些网络， 如何把前期投入变成产出，仍然缺乏有效的手段。而组播技术正是解决这一问题 的有效手段，其意义不仅在于减少网络资源的占用，提高扩展性，还在于利用网 络的组播特性方便地提供一些新的业务【9 l 。随着网络中多媒体业务的日渐增多，组 播的优越性和重要性越来越明显。 虽然i p 组播在公众网中的运用前景并不乐观，但是，i p 组播作为一种高效率 的组播通信实现体系结构，可以根据自身的优势，在专门网络中进行运用，或者 作为公众网络中一种受限的业务提供给特定的用户。在以后i p 组播体系结构的进 一步发展和完善，也可以在公众网络中对特定用户开放i p 组播业务1 6 j 。 而应用层组播，目前还处于起步研究阶段，虽然提出很多应用层组播体系结 构，但这些结构都是针对某种特殊应用的解决方案，如果在网络中应用，由于网 络的组播应用的多样性，需要部署多种不同的应用层组播协议，这太过于复杂， 因此，建立一个可以复用、可灵活配置的支持多种业务的应用层组播服务层是将 来的一个主要发展方向。同时从目前的研究成果看，以中间件的形式实现应用层 组播业务是一种可行的结构。通过定义应用层组播业务模型，明确应用层组播的 各个功能机制并建立一个标准化的框架，可以建立一个以中间件形式存在的、标 准的、可配置和复用的、灵活的应用层组播基础设施1 6 j 。 总之目前网络发展的总体趋势是：网络业务呈现多层次发展，核心网只提供 i p 单播业务，是为了保持i p 网络核心简单高效的优点。而其它在网络核心中难以 实现的功能迁移到网络的边缘或者网络端系统。这种叠加网层将成为未来网络体 系结构中一个重要的业务实现层次，而将来的网络也将有可能通过提供某些基本 的业务，比如向上层提供组成逻辑链路的物理链路信息或者网络的拓扑信息，专 门支持叠加网业务的实现。随着应用层组播研究的深入，最终将通过叠加网层实 现一个功能强大的，支持多种组播应用的组播业务。 顾1 j 学位论文 1 3q o s 组播路由的研究现状和发展趋势 随着组播技术在计算机网络中应用不断的发展，网络组播技术应用呈现出多 样性和复杂化，人们对这些特殊的网络应用有特殊的要求，例如实时通信，对端 到端的时延波动要求很高；视频会议，要求各地的与会者同时听到发言者讲话， 对传输的时延要求很高。这些特殊要求就是网络的服务质量( q o s ) 问题，传统计 算机网络，对各种业务一律平等，不能保证特殊业务的特殊要求，不能保证服务 质量。所以q o s 组播路由问题成为目前国内外研究的一个热点问题。 最早，人们提出了单一度量标准的最小跳数路由和最短延迟路由j ，而后自 适应路由( a d a p t i v er o u t i n g ) 又成为人们研究的重点。到2 0 世纪9 0 年代后期， q o s 组播路由逐渐被人们重视，从理论到具体实现都进行了大量的研究工作【l 列， 主要研究有：流量控制，通过对各种具有不同q o s 要求的业务流进行适当的路由 选择、路由优化和采取多种高效的流量管理和控制手段，但是仍然很难在组播路 由中提供q o s 支持，因为不同的网络应用对延时、延时抖动、丢包率和带宽都有 不同的要求。路由问题的实质是最优控制问题，根据业务要求、网络资源的现状 来找出源和目的间的路径树，使时延和时延抖动最小，同时提高网络的吞吐量i l3 1 。 与此同时国外出现许多经典的q o s 组播路由算法，如斯坦利树( s t e i n e rt r e e ) 是 使整个组播树的费用最小。而时延受限斯坦利树( d e l a yc o n s t r a i n e ds t e i n e rt r e e ) 是寻找满足时延受限要求同时费用为最小的组播树。但这类启发式算法的求解复 杂，不能很好地解决q o s 组播路由问题。 后来，人们引入了智能优化算法。智能优化算法是解决复杂问题的一个重要 途径，目前研究的人工智能优化方法主要有遗传算法、神经网络、蚁群算法、免 疫算法、免疫克隆选择算法等。在国外，有学者提出利用h o p f i e l d 神经网络来解决 q o s 路由选择问题，通过引入能量函数来使神经网络达到平衡状态，该方法可在限 定的时间内求出最优解，但仍然有可能陷入局部的极小值，并且在具体实现上存 在着困难。q z h a n g 等人提出了正交遗传算法( o r t h o g o n a lg e n e t i ca l g o r i t h m ) ，将 正交矩阵的实验设计方法引入到遗传算法的交叉操作中，来提高算法的性能，但 该算法比较复杂【1 4 l 。在国内，也有多所大学及科研部门致力于组播技术研究，如 浙江工业大学的黄德才、张洁等人将生物进化论的遗传算法引入组播路由问题， 提出一个混合遗传算法，改进了编码、交叉操作和变异操作，来解决q o s 约束的组 播路由问题，但该算法容易出现早熟，陷入局部最优i l 引。南京大学的王汝传、孙 力娟等人将将遗传算法和蚁群算法两种算法融合，提出了一种遗传蚁群算法 ( g a a c s ) ，扩大了系统对解空间的搜索，采用优化得到的参数组合能更好、更快 地引导蚁群系统找到全局最优解来求解q o s 组播路由问题【i6 1 。西安电子科技大学 计算机m 络中的纽播路l | 】算法研究 的刘芳、杨海潮等人引入克隆策略，将克隆选择算子和克隆变异算子代替遗传策 略中的选择和变异算子，引入反馈机制，使寻找最优解的过程变得更有“目的” 性，从而提高算法收敛速度【17 1 。但是q o s 组播路由问题仍需作进一步研究，目前 对支持q o s i 拘组播路由涉及的比较少，还没有形成一套完整成熟的理论方法，因此 对支持q o s 的组播路由作进一步的研究就很有必要。 1 4 本文主要研究内容 本文的主要研究内容： 第l 章绪论。通过分析组播技术的研究现状和发展趋势，指出了组播路由算 法的优越性及本课题的研究意义。 第2 章计算机网络组播通信的相关理论。对计算机网络的组播通信进行了全 面的综述，详细介绍了目前几个实际应用中的组播路由协议，分析它们的优缺点 和适用范围，叙述了组播路由算法的研究现状和组播树相关的一些理论基础，包 括了网络中的数据包传输方式，组播树的概念，服务质量q o s 的要求，影响组播 通信的一些主要的指标，给出了研究q o s 组播路由的数学模型。 第3 章详细介绍了基于蚁群算法时延受限组播路由算法。简单介绍了k p p 算法、b s m a 算法、l d t 算法；研究了基于蚁群算法时延受限组播路由算法，对 该算法原理和实现步骤进行阐述运用m a t l a b 软件开发了该算法的实验仿真程序， 进行实验仿真，并和基于启发式遗传算法的组播路由算法进行了比较。 第4 章详细介绍了基于克隆算法时延受限组播路由算法和带受体编辑的克隆 选择时延受限组播路由算法，对该二种算法原理和实现步骤进行阐述，并进行实验 仿真，和基于蚁群算法时延受限组播路由算法及基于启发式遗传算法的组播路由 算法进行对比。带受体编辑的克隆选择时延受限组播路由算法在没有备选路径集 的情况下，直接进行基因操作选出满足延时、代价好的优良基因并保存下来，大 大的提高了收敛速度，降低了算法的复杂度。 第5 章针对目前组播路由算法只是在满足延时，带宽约束的前提下使组播树的 代价最小，这类算法代价的优化是以延时和带宽的性能下降作为代价的，过于厚此 薄彼，提出一种基于改进克隆策略的整体优化组播路由算法，这种算法继承克隆 算法的优点，并加以改进，引入了一个综合性能指标q 来衡量组播树的性能，同时 对个体进行了基因优化操作，通过实验仿真，验证了该算法优越性。 最后，对本文研究工作进行总结与展望。 硕j ：学位论文 第2 章计算机网络组播通信的相关理论 随着网络功能的日益强大，如何保证计算机网络中的通信畅通、信息完整等 服务质量尤其重要，关键在于确定支持服务质量的组播路由。q o s 组播路由算法 是本文的研究重点，用它来确定支持服务质量的组播路由。如何实现q o s 组播路 由算法，是在收集网络中相关状态信息的基础上完成。网络的状态信息由网络的 拓扑结构、链路和路由器的负载程度、链路和路由器的失效和有效、网络中路由 器的类别( 是否具有组播功能) 等因素构成。这些信息的收集是靠组播路由协议 ( m u l t i e a s tr o u t i n gp r o t o e 0 1 ) 来完成的。本章简要介绍几个实际应用中的组播路由协 议和组播路由算法的研究现状以及组播树韵相关概念。 2 1 网络中的数据包传输方式 数据包在网络中传输一般有三种方式：单播、组播、广播。人们在网络传输 上提出各种解决网络拥挤的方案，而组播正是其中比较有优势的一项技术，以下 是这三种传输方式的原理图。 图2 1 单播原理图 图2 2 广播原理图 接收者 计算移【网络中的组播路由算法研究 = = = = = = = = = ! = = = ! = = = = = = = = ! = i 二= i i 二m = lm = = ! = = = = = = = = = = = ! = = = = = = = = = = = = ! = = = = = = = ! = 竺! = = 图2 3 组播原理图 1 单播 ，b a n d w i d t h ( 2 7 ) m a x ( d e l a y ( p r ( s , t ) ) ) k d e l a y ( 2 8 ) m a x ( d e l a y _ j i t t e r ，n ( s , t ) ) ) 弋d e l a y _ _ j i t t e r ( 2 9 ) m a x ( p a c k e t l o s s ( p r ( s , t ) ) ) p a c k e t l o s s ( 2 1 0 ) 计算机m 络中的i l i 播路巾算法研究 其中，b a n d w i d t h 、d e l a y 、d e l a y _ j i t t e r 、p a c k e t l o s s 分别是带宽、延时、延时 抖动、丢包率约束。 2 6 本章小结 本章主要对计算机网络组播通信的相关理论进行了全面的综述，详细介绍了 目前几个实际应用中的组播路由协议，分析它们的优缺点和适用范围，叙述了组 播路由算法的研究现状和组播树相关的一些理论基础，包括了网络中的数据包传 输方式，组播树的概念，服务质量q o s 的要求，影响组播通信的一些主要的指标， 给出了研究q o s 组播路由的数学模型。 硕f j 学位论文 第3 章基于蚁群算法的时延受限组播路由算法 3 1 时延受限组播问题的数学描述 设g = ( ，k e 夕表示网络，其中y 表示节点集，e 表示节点间的链路集，j v 为 组播源节点，m 矿一 s ) 为组播目的节点集。r + 表示正实数集，r + 表示非负实 数集。对于任一链路e e ，有该链路对应的两个正实数加权值d e l a y 俐和 c o s t 俐，分别表示该链路的延时和代价。对于矿中的任何两个节点亿6 ) ，p 亿 表示两个节点伍之间的路径，则路径p 向的延时函数和代价函数计算如下： d e a y ( a ，b ) = 芝：d e l a y ( e ) ( 3 1 ) c o s t ( a ，6 ) = c o s t ( e ) e e p ( a ，6 ) ( 3 2 ) 在多媒体实时业务的q o s 传输中，基于时延受限的组播路由优化问题可以描述 为：给定网络延g = ( ，k e a 寻找从源节点s 到所有目的节点的组播树t = ( e r ) ， 丁g ，弓( s ，) 表示组播树t 上源节点s 到目的节点t 的路由路径，组播树t 满足如下条 件： m a x ( d e l a y ( p r ( s ，f ) ) ) d e l a y( 3 3 ) c o s t ( t ) = m i n ( c o s t ( e ) ) ( 3 4 ) e e f r 其中公式3 3 中，d e l a y 为实时业务允许时延的上限值，因此，时延受限组播 路由问题的实质就是在满足时延约束条件下，寻找一棵从源节点到多个目的节点 的最小代价的组播树。 3 2 传统时延受限组播路由算法介绍 国内外已有不少学者对时延受限组播路由算法进行研究，提出了许多经典的算 法。但大都采用启发式算法来解决，如k p p 算法【3 7 】是一种满足端到端时延约束的组 播路由启发式算法，b s m a ( b o u n d e ds h o r t e s tm u l t i c a s ta l g o r i t h m ) 算法【3 8 j 是构 造受限s t e i n e r 树的信源路由启发式算法，l d t 算法则是满足最小时延树的组播路 由启发式算法，下面对这三种最具代表性的算法进行详细阐述。 1 k p p 算法 k p p 算法是由k o m p e l l a 、p a s q u a l e 和p o l y z o s 提出，因而称为k p p 算法。该 计弦机网络中的鲋l 播路由算法f j f 究 算法借鉴了k m b 算法的思想，假定链路时延和时延约束都是正整数。在介绍具 体算法之前，首先介绍约束的最小代价路径的概念。 约束的最小代价路径指节点矿和w 之间满足时延约束的代价最小的那条路径， 用p c ( v ，w ) 表示这条路径的代价。记o ( 矿，w ) 是节点v 和w 之间时延正好等于d 的 最小代价路径的代价，已( y ，w ) 可以通过类似f l o y d 算法的方法求得： ( _ ( 矿，w ) = m i n c d d e t a y ( ”，w ) ( v ，”) + c o s t ( u ，叻) ，z ，1 ，( 3 5 ) 尸c ( 矿，形) = m i n ( c a ( 矿，形) ) ，d a( 3 6 ) k p p 算法的步骤如下【3 7 i ： s t e p l 以集合s u m 的所有节点为顶点构造完全封闭图g ， 对之间的约束最小代价路径，边的代价是这条路径的代价。 s t e p 2 在时延约束下求g 的生成树t 。与p r i m 算法相似， 边加入到生成树，但各边代价按以下规则之一取值： g 的边是这些节点 每次将代价最小的 j 仲，w ) 。i 鬲c o s 丽t ( v , w ) 肭) + 撕“嗍锄 ( 3 7 ) i f c o ( v ，叻= o t h e r w & e l 乒( v ，w ) = c o s t ( v ，w ) f ( p ( v ) + d e t a y ( v ，w ) ) a i乒( v ，w ) = o 。 。比刑妇 ( 3 舟) 其中，p ( v ) 是生成树上从源节点到节点v 的时延，c o s t ( v ，w ) 是完全图g 中 链路( v ，w ) 的代价，d e l a y ( v ，w ) 是完全图g 中链路( v ，w ) 的时延。 s t e p 3 把生成树的边还原成约束的最小代价路径。 s t e p 4扩展后的路由树不定是真正的路由树，因为它可能含有环。k p p 算 法在扩展后的路由树上求出目的节点时延最优路由树，并将其作为最终的路由树。 k p p 算法的缺点在于当解存在时，它可能会找不到解。另外，该算法可能会出 现环路，并给出了检查环路和去除环路的算法，从而完善了k p p 算法【3 7 1 。 2 b s m a 算法 b s m a 算法【3 8 j 是由z h u 等人提出的，采用先找到问题的可行解，然后对可行解 进行改进，使其性能更加接近最优解的方法。该算法求得的组播树的代价较小， 平均性能仅与最优解相差7 ，是当时所有时延约束静态组播启发算法中代价性能 较好的一个。b s m a 算法的主要特点是：( 1 ) 对不同目的节点，其时延约束边界值可 以不同；( 2 ) 与k p p 算法相比，其链路代价值和链路时延值可以是任意实数；( 3 ) 与以往算法一次性通过不同，b s m a 算法可以重复执行以使树的代价最小。 b s m a 算法也是一种源路由算法，即源节点掌握网络中所有链路的情况。b s m a 算法包括两个基本步骤： 硕 ：学位论文 s t e p l 利用d i j k s t r a 算法求出以源节点s 为根的最短路径树，若此时不满足 时延约束条件，则需与目的节点协商；若满足，则继续下一步。 s t e p 2 在保证不违反目的节点的时延约束条件下，不断用代价更低的路径替 代树上的代价最高的超边。 这里假定第i 次循环前的树为t i ，循环后的树为t i + l 。所谓树中超边即t i 中的 一条路径，路径的头尾节点可以任选，但除了头尾节点以外路径上所有中继节点 必须是非组播节点，而且这些中继节点必须只连接两条链路。实际上，去掉超边 后的t i 分裂为两棵子树t i l 和t i 2 0 在b s m a 算法中，求子树t i l 和t i 2 间的时延约束 的最小代价路径。这里利用求第k 条最短路径算法，k 的值预先不确定，由算法运 行结果决定。当出现以下两种情况时，求k 条最短路径算法就终止：1 ) 找到的路 径违反时延约束条件；2 ) 找到的路径与删除的超边长度一样。最后从k 条路径中 选出剩余时延最多的路径作为替代超边的路径。但b s m a 算法的复杂度很高，不适 于求解大型网络。 3 l d t 算法 l d t 算法( l e a s t d e l a yt r e e ) 是指由s a l a m a 提出的最小时延树算法。该算法使 用d i j k s t r a 最短路径算法计算从源节点到各个目的节点的时延最短路径，然后合并 相同的链路，就求得时延约束的组播树。由于l d 算法使用d i j k s t r a 最短路径算 法，因此时间复杂度为酬iy 1 2 ) 。该算法得到的组播树代价较大，因为它只考虑端 到端的时延，而没有考虑边的代价。l d 算法适合于对实时性要求很高的业务，因 为算法得到的组播树，从源节点到目的节点的时延是最短的。用该算法求得的组 播树，称为最小时延树( l e a s td e l a yt r e e ，l d t ) 。在许多组播路由算法中，常常首 。 先使用最小时延树来判断是否有解存在。 由于这类启发式算法效率不高，时间复杂度高，不适应现代化的大型网络，近 年来，一些学者引入人工智能方法来优化生成树，现在研究的人工智能方法主要 有遗传算法、神经网络、蚁群算法、免疫算法、免疫克隆选择算法等，例如r a v i k u m a r 等人针对延时约束费用最小的组播路由问题，提出一种基于遗传算法的路由算法， 孙力娟等人将遗传算法和蚁群算法融合，提出了一种用遗传蚁群算法( g a a c s ) 求 解q o s 组播路由问题，但其收敛速度都不尽人意【l6 1 。由于人工免疫算法比遗传算 法具有更好的全局寻优能力，这点在函数优化问题中得到了很好体现，刘芳等人 针对带时延约束的组播路由问题，提出一种基于克隆策略的路由算法【1 7 】等。随着 智能算法的不断成熟，智能算法在今后的q o s 组播路由选择有着非常广阔的前景。 本文就蚁群算法和克隆选择算法的组播路由算法进行详细的介绍，并运用m a t l a b 软件编程进行仿真实验，对该二种算法性能进行分析比较。 计算机网络中的f l l 播路山算法研究 3 3 蚁群算法介绍 3 3 1 蚁群算法的基本原理 蚁群算法( a c a ) 是人们通过对自然界中蚁群群体行为的研究的基础上，由意 大利学者m o o r i g o 首先提出的一种基于种群的模拟进化算法【3 9 1 。该算法通过模拟 蚂蚁搜索食物的过程来求解一些实际问题。蚁群能够在没有任何提示的情况下找 出蚁穴到食物源的最短路径，并且能随着环境的变化而变化，然后搜索新的路径， 产生新的选择。蚂蚁寻找到从巢穴到食物源的最短路径是通过一种正反馈的机制 来实现，单个蚂蚁在自己走过的道路上留下一些挥发性分泌物，称之为信息素， 这些物质能被同一蚁群中后来的蚂蚁感受到，并作为一种信号影响后到者的行走 路径，具体表现在后到的蚂蚁选择有这些物质的路径的可能性比选择没有这些物 质的路径的可能性大得多，而后到者留下的信息素会对原有的信息素进行加强， 并如此循环下去。这样，经过蚂蚁越多的路径，在后到蚂蚁的选择中被选中的可 能性就越大，这是因为残留的信息素浓度较大的缘故。由于在一定的时间内越 短的路径会被越多的蚂蚁访问，因而积累的信息素也就越多，在下一个时间内被 其他的蚂蚁选中的可能性也就越大，这个过程会一直持续到所有的蚂蚁都走最短 的那一条路径为止【4 0 1 。 3 3 2 蚁群算法描述实现过程 s t e p l 初始化各路径上的信息强度和蚂蚁数； s t e p 2 计算各路径上的适应度； s t e p 3 每个蚂蚁同时从源点出发，通过赌轮规则选择路径，并进行分泌物强 度调整，直到找到目的节点，再判断是否大部分蚂蚁都收敛于某一条路径，如果 是，则输出结果，退出程序；否则，转s t e p 4 执行； s t e p 4 所有蚂蚁返回源点，再转s t e p 2 执行【4 。 3 3 3 蚁群算法的优缺点 蚁群算法的优点r 4 2 】： 1 较强的鲁棒性。对该算法模型稍加修改，便可以应用于其它问题。蚂蚁算 法对初始路线要求不高，即蚂蚁算法的求解结果不依赖于初始路线的选择，而且 在搜索过程中不需要进行人工的调整。其次，蚂蚁算法的参数数目少，设置简单， 易于蚂蚁算法应用到其它组合优化问题的求解。 2 分布式计算。该算法是一种基于种群的拟生态系统算法，具有本质并行性， 易于并行实现。 3 易于与其它方法结合。该算法很容易与多种启发式算法结合，以改善算法 的性能。 硕l j 学位论文 4 蚁群算法是一种本质上并行的算法。每只蚂蚁搜索的过程彼此独立，仅通 过信息激素进行通信。它在问题空间的多点同时开始进行独立的解搜索，不仅增 加了算法的可靠性，也使得算法具有较强的全局搜索能力1 4 3 1 。 蚁群算法的缺点h 纠： 1 需要较长的计算时间，容易出现停滞现象。蚂蚁中各个体的运动是随机的， 虽然通过信息激素交换能够向着最优路径进化，但是当群体规模较大时，很难在 较短时间内从大量杂乱无章的路径中找到一条较好的路径。这是因为在进化的初 期，各个路径上的信息激素差别不大，通过信息正反馈，使得较好路径上的信息 激素逐渐增大，经过较长一段时间，才能使得较好路径上的信息激素明显高于其 它路径，随着这一过程的进行，差别越来越明显，从而最终收敛，这一过程一般需 要较长的时间。 2 所有通过路段的搜索路径对应