（电路与系统专业论文）量子进化组播路由算法研究.pdf

摘要 摘要 随着i n t e m e t 的迅速发展，视频会议、网络游戏、在线交易等多媒体通信业 务迅速增长，带宽消耗和网络拥塞问题日益显著。组播技术是将数据从一个源节 点同时传输给大量的目的节点，从而有效的节省了网络带宽占用，减少网络拥塞。 本文针对组播路由问题，主要讨论了求解最小代价的时延约束组播路由算法，主 要研究内容如下： 1 提出了量子进化组播路由算法( q e a ) ，将组播路由问题转化为网络中的边 的组合优化问题，利用量子位对网络中的边进行编码来替代对网络各选路径的编 码，并且改进了量子旋转门策略，加速算法的收敛速度。理论分析和计算机仿真 实验结果都表明，算法复杂度大大降低，且结果稳定，算法收敛速度快，操作简 单。 2 对动态组播问题，结合量子进化组播路由算法的编码优势和组播树的构造 过程，提出了量子进化动态组播路由算法。讨论了网络中组播组成员变化和网络 拓扑结构变化两种情况的动态变化，本算法中引入种群更新算子和个体修复等算 子对动态变化对组播树产生的影响进行修复和补偿。通过仿真测试，验证了算法 对动态组播的有效性和可靠性。 3 针对更大规模的网络组播问题，借鉴中小规模组播问题的解决方式，综合 考虑代价最小和复杂度降低两个因素，提出了基于量子进化计算的大规模网络组 播路由算法，该算法采用基于路径的编码方式，然后采用量子变异算子和量子旋 转门策略对种群进行更新，仿真结果显示，该算法能在组播树性能和计算复杂度 之间的取得折中的结果，且算法实现简单，控制灵活。 本文得到如下基金资助：国家“8 6 3 ”计划：2 0 0 9 a a l 2 2 2 1 0 ；陕西省“1 3 1 1 5 ” 科技创新工程重大科技专项项目：2 0 0 8 z d k g - 3 7 ；国家自然科学基金：( 6 0 7 0 3 1 0 7 和6 0 7 0 3 1 0 8 ) ；陕西省自然科学基金：2 0 0 7 f 3 2 1 中国博士后科学基金特别资助： 2 0 0 8 0 1 4 2 6 1 中国博士后科学基金：2 0 0 8 0 4 3 1 2 2 8 以及中央高校基本科研业务费专 项资金资助：j y l 0 0 0 0 9 0 2 0 4 0 。 关键词：组播路由静态和动态组播量子进化算法量子旋转门策略 i i 摘要 一 垒垒! 堡型 一里一 _ - _ - _ 一 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e m e t ，av a r i e t yo fm u l t i m e d i aa p p l i c a t i o n s ，s u c h a s l u d i oc o r e f e r e n c i n g ，o n l i n eg a m e s ，o n l i n et r a d i n g ，a r ei n c r e a s i n gr a p i d l y , l e a d i n gt o i i m c hm o r ei n t e n s i v eb a n d w i d t hc o n s u m p t i o na n d n e t w o r kc o n g e s t i o n m u l t i c a s t t e c h n o l o g y , w h i c ht r a n s m i t s t h es a m ed a t af r o mas o u r c et oal a r g en u m b e r0 i d e s t i 彻t i o nn o d e ss i m u l t a n e o u s l y , s a v eag r e a td e a lo fb a n d w i d t ha n dr e d u c en e t w o r k c o n g e s t i o n t h ep a p e rc e n t e r so nt h ea l g o r i t h m sw h i c h c 孤c o n s t r u c td e l a y - c o n s t r a i n e d a n dl o w c o s tm u l t i c a s tr o u t i n gt r e e s t h em a i nr e s e a r c hw o r ki s s u m m a r i z e da s f o l l o w s ： 1 q u a n t l 姗i n s p i r e de v a l u a t i o na l g o r i t h m ( q e a ) b a s e d m u l t i c a s tr o u t i n ga l g o r i t h mi s p r o p o s e d i n w h i c ht h em u l t i c a s tr o u t i n gp r o b l e m i st r a n s f o r m e di n t o t h e c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e mo ft h es i d ei nt h en e t w o r k t h ei n d i v i d u a l si n a p o p u l a t i o na r er e p r e s e n t e db yq u a n t u me n c o d i n gb a s e d o nt h es i d ei nt h en e t w o r k t or e p l a c et h ec o d i n go fn e t w o r kc a n d i d a t ep a t hs e t t h eq u a n t u mr o t a t i o ng a t e s t r a t e g yi si m p r o v e dt oa c c e l e r a t ec o n v e r g e n c es p e e do ft h ea l g o r i t h m t h e o r e t i c a l 删y s i sa n dc o m p u t e rs i m u l a t i o n s h o wt h a tt h ec o m p l e x i t yo ft h ep r o p o s e d a l g o 池g r e a t l yr e d u c e d ，a n dt h e r e s u l t sa r es t a b l e t h ea l g o r i t h mc o n v e r g e sf a s t a n de a s yt oo p e r a t e 2 f o rd y n a m i cm u l t i c a s tp r o b l e m ，c o m b i n e dw i t ht h ea d v a n t a g eo fc o d i n ga n dt h e c o n s t r u c t i o np r o c e s s i n go ft h em u l t i c a s tt r e ei nt h eq e a f o rs t a t i cm u l t i c a s tr o u t i n g p r o b l e m q e ab a s e dd y n a m i cm u l t i c a s ta l g o r i t h m i sp r o p o s e d w ed i s c u s s e dt h e d y n a m i c so ft w oc a s e st h a tt h em o d e lo fm u l t i c a s tg r o u pm e m b e r s h i p c h a n g e sa n d t h em o d e lo fn e t w o r kt o p o l o g yc h a n g e s t h ep o p u l a t i o nu p d a t eo p e r a t o ra n d i n d i v i d u a lr e p a i ro p e r a t o ra r ei n t r o d u c e di n t ot h ea l g o r i t h mt oc o m p e n s a t ea n d r e p a i rt h em u l t i c a s tt r e e a f t e rt h ed y n a m i cc h a n g e s s i m u l a t i o n sp r o v e ，t h e p r o p o s e da l g o r i t h m i s v a l i d i t ya n dr e l i a b i l i t y f o rd y n a m i cm u l t i c a s tr o u t i n g p r o b l e m s 3 f o rl a r g e rs c a l en e t w o r km u l t i c a s tr o u t i n gp r o b l e m ，l e a r n i n gf r o ms m a l l 。s c a l e m u l t i c a s tp r o b l e ms o l v i n ga n dc o n s i d e r i n gb o t ht h em i n i m u m c o s to fm u l t i c a s tt r e e a n dt h ec o m p l e x i t yo ft h ea l g o r i t h m ，w ep r o p o s e dt h ed e l a y c o n s t r a i n e dm u l t i c a s t r o 晌ga l g o r i t h mf o rl a r g es c a l en e t w o r kb a s e do nq e a ，i n w h i c ht h ei n d i v i d u a l s i nap o p u l a t i o na 驻r e p r e s e n t e db ym u l t i s t a t eg e n eq u a n t u mb i t sc o d i n gb a s e dt h e p a t h i nt h ei n d i v i d u a l su p d a t i n g ，t h eq u a n t u mr o t a t i o ng a t es t r a t e g y l sa p p l i e dt o i v a b s t r a c t a c c e l e r a t ec o n v e r g e n c e s i m u l a t i o nr e s u l t ss h o wt h a t , t h ea l g o r i t h mc a na c h i e v ea b a l a n c eb e t w e e nt h ep e r f o r m a n c eo fm u l t i c a s tt r e ea n dt h e c o m p l e x i t yo ft h e a l g o r i t h m ，a n dt h ea l g o r i t h mh a st h ep r o p e r t yo fs i m p l er e a l i z a t i o na n df l e x i b l e c o n t r 0 1 1 1 l i sr e s e a r c hi s s u p p o r t e db yt h en a t i o n a lh i 曲t e c h n o l o g yr e s e a r c ha n d d e v e l o p m e n tp r o g r a m ( 8 6 3p r o g r a m ) o fc h i n a ( g r a n tn o 2 0 0 9 a a l2 2 2 10 ) ，t h ek e y s c i e n t i f i ca n dt e c h n o l o g i c a li n n o v m i o ns p e c i a lp r o j e c t so fs h a a n x i “13l15 ”( n o 2 0 0 8 z d k g - 3 7 ) t h en a t i o n a ln a t u r a l s c i e n c ef o u n d a t i o no fc h i n a ( g r a n tn o 6 0 7 0 310 7a n d6 0 7 0 3l0 8 ) t h en a t u r a ls c i e n c eb a s i cr e s e a r c hp l a ni ns h a a n x i p r o v i n c eo fc h i n a ( g r a n tn o 2 0 0 7 f 3 2 ) ，t h ec h i n ap o s t d o c t o r a ls c i e n c ef o u n d a t i o n s p e c i a lf u n d e dp r o j e c t ( n o 2 0 0 8 0 14 2 6 ) ，t h ec h i n ap o s t d o c t o r a ls c i e n c ef o u n d a t i o n f u n d e dp r o j e c t ( n o 2 0 0 8 0 4 312 2 8 ) a n dt h ef u n d a m e n t a lr e s e a r c hf u n d sf o rt h e c e n t r a lu i l i v e r s i t i e s ( n o j y l0 0 0 0 9 0 2 0 4 0 ) k e y w o r d s ：m u l t i c a s tr o u t i n gs t a t i ca n dd y n a m i cm u l t i c a s t q u a n t u m i n s p i r e d e v o l u t i o n a r ya l g o r i t h mq u a n t u mr o t a t i o ng a t es t r a t e g y 第一章绪论 第一章绪论 本章主要介绍组播路由技术以及组播路由算法研究的现状和发展，最后给出 了论文的主要内容和安排。 1 1 论文研究背景介绍 随着i n t e m e t 技术迅速发展，各种多媒体网络业务如视频会议、远程教育、 网络对战游戏、视频点播等也迅速增长，这些业务都将产生的大量的数据信息， 需要消耗大量的网络资源，随着需求量的不断增加，网络用户数量爆炸性增长， 网络拥塞和带宽消耗等问题日益显著。这些业务对网络提出不同的服务质量 ( q u a l i t yo fs e r v i c e ，q o s ) 要求。服务质量是指信息发送和接受用户之间以及用 户与服务网络之间对信息传输质量的要求，主要包括网络中用户到用户间的时延， 带宽，代价等。多媒体通信业务的服务质量中节点到节点之间的时延是最重要的 q o s 要求之一。对于实时通信业务，如在视频会议应用中如果时延过长，用户间 通信将出现延时、中断等问题，使得听觉上和视觉上通信效果差，严重时可能导 致会议双方之间语义无法理解或者误解。而单播或者广播通信方式，数据的发送 仅能提供“尽力而为”服务，无法保证能满足这些服务质量的要求。 1 2 组播技术概述 组播通信方式是实现点到多点或者多点到多点的通信方式，一个或者多个源 节点只需发送一个数据包，每条通信链路上仅有一个数据包拷贝，只有到达下一 个节点时才对数据进行复制，示意图如下图1 1 所示。 服务器 蓉产 图1 1 组播后数据复制方式 也就是说，组播树有以下两大优点：一是信息在发送到不同组播成员时，是 以并行的方式沿着树上的链路进行的，降低了通信链路的时延；二是网络中信息 的复制只发生在链路分叉处进行，组播树上需要传送的复制信息是最少的，这样 大大节省了网络带宽资源，能够有效减少网络拥塞，降低带宽占用，提高资源利 2 量子进化组播路由算法研究 用率。 随着组播支持的网络应用的不断增多，这些应用对服务质量的要求也不断的 提高，因此，组播路由对服务质量的支持是当前组播技术面临的挑战。组播路由 是组播问题的核心，组播路由算法的关键在于确定一棵组播树，一般用组播树的 “代价”来衡量组播树的质量，组播树的代价是指组播树上所有链路代价的总和【l 】。 实际应用中，代价是指通信过程中资源的损耗，因此，要求组播树的代价越小越 好。对实时多媒体业务，还必须满足时延约束条件，因此研究时延受限组播路由 算法可以给多媒体实时通信业务的应用实现和q o s 的保证提供解决方案。 此外，在很多实时多媒体网络应用中，会出现组播组动态变化或者组播网络 动态变化。也就是说，组播过程中，组播成员可能会发生变化，即可能有些组播 成员离开组播组，而另外一些节点则加入组播组；或者是组播通信网络中，有些 链路中断，而另外一些链路连通。这两种情况下，更新组播树以适应组播成员的 变化或者网络拓扑结构变化的问题被称为动态组播路由问题。同样的，将动态组 播路由算法用于实时通信应用时，动态变化后，在更新组播树的同时，仍然要求 新的通信链路满足时延限制条件以及组播树代价越小越好。因此时延受限动态组 播路由算法也具有很高的实用价值。 1 3 组播路由算法的现状和发展 按照不同的分类规则，组播路由算法可以分为不同的类型。本文在讨论组播 路由算法时，主要根据所讨论的网络拓扑结构和状态信息的不同将组播路由算法 分为静态和动态组播路由算法。其中，静态路由算法中认为网络的拓扑结构和状 态信息是确定不变的【2 】【3 】【4 】，动态算法中网络拓扑结构或者组播成员状态信息是动 态变化的。静态路由算法在有节点状态信息发生变化时，之前的组播树就失效了， 需要重新构建组播树。动态组播路由算法则是可以根据网络拓扑结构和状态信息 的改变来动态的构建组播树，对当前通信使用的组播树不产生影响。 此外根据网络拓扑结构和链路状态信息在求解组播树时使用方式的不同，组 播路由算法可以分为集中式组播路由算法和分布式组播路由算法【5 】。集中式组播 路由算法是指在网络中，每个节点都需要掌握整个网络的拓扑结构，然后根据组 播组中的源节点和目的节点构建组播树，根据所得组播树转发组播信息。分布式 算法则不需要每个节点都掌握整个网络的拓扑结构，每个参与组播的节点只需要 掌握局部的网络拓扑信息，各自生成相应的要加入组播树的路径后合并成一棵完 整的组播树【6 j 。 根据算法生成组播树的形式不同，组播路由算法可以分为基于根源树的组播 路由算法和基于共享树的组播路由算法。有源树是以信息源节点为根节点，构造 第一章绪论 的从根到所有以信息的目的节点为叶子节点的最小分布树。有源树根据计算方式 又可以分为两种：一种是最短路径树，即从源节点到目的节点均以最短链路链接， 最常用的算法有d i j k s t r a t 7 1 、b e l l m a n f o r d 8 】以及p r i m 9 1 。显然，由所有最短路径 的总和求得的组播树的总代价并不一定就是最优的。另一种有源树就是最小 s t e i n e r 树，即对给定的网络连通图和组播成员集，要求从图中找出一棵覆盖所有 组播成员的代价最小生成树。共享树又称为核心树，是指为每个组播组选定一个 共有的核心【lo 】，然后以核心为根节点构建组播树，信息发送给核心后，通过核心 向其他成员转发。核心树计算方式减少了计算和存储的开销，但获得的组播代价 比有源树大2 倍以上，如果核心是组播组成员的话，代价会达到有源树的3 倍以 上i l 。本文研究的组播路由算法都是以有源树的形式求得的组播树。 根据k w u 和j h a r m s 的证明，基于两个以上不相关可加度量的q o s 组播路 由问题是n p 完全问题【1 2 1 ，因此组播路由s t e i n e r 树问题是n p 完全问题【1 3 】【1 4 1 。 当前已经有很多启发式算法提出用于求解时延受限组播路由问题，目前常用于解 决组播路由问题的启发式算法有多种【1 5 】，如p a r s a 等人提出的b s m a 算法【1 6 1 ，该 算法能求得较小的组播代价，但算法复杂度为o ( k 1 i v l 3l o g n ) ，其中为网络规模， k 为备选路径集选择的条数，不适用于大型网络的组播路由问题。k o m p e l l a 等人 提出的k p p 算法【1 7 】，但该算法存在有时当可行解存在时，它可能会找不到解的情 况。s u n 等人提出的c d k s 1 8 】，该算法求解时运行时间相对短，获得组播代价介 于b s m a 和k p p 之间。 除了启发式算法外，遗传算法1 1 9 1 、蚁群算法【1 3 】【1 5 l 等智能优化算法也应用于求 解时延受限组播路由问题，但由于这些算法存在收敛速度慢，编码方式的编解码 过程复杂导致复杂度高等缺点，寻找新型的能够快速求解较优解，克服以上缺陷 的启发式智能优化算法是当前求解组播路由问题研究的热点。 量子进化算法( q u a n t u me v o l u t i o n a r ya l g o r i t h m ，q e a ) 2 0 j 【2 4 1 是近年来被广 泛关注的一种新型启发式优化方法。q e a 将量子计算中的原理如叠加性，相干性， 纠缠性，并行性等应用于进化计算中，具有并行计算和群体寻优的特点。本论文 的工作将量子进化计算应用于组播路由求解中，并针对组播路由算法问题，设计 了新的算子。 1 4 论文的主要内容及安排 本文主要研究了量子进化时延受限的组播路由算法，全文共分六个章节，内 容安排如下： 第一章绪论，概述了论文研究的背景，简要介绍了组播技术特点以及组播路 由算法，给出了论文的主要内容和结构安排。 4 量子进化组播路由算法研究 第二章组播路由算法理论基础及基本算法，主要介绍了本文中所涉及到的理 论基础包括组播路由问题的定义以及s t e i n e r 树理论，总结了组播路由问题的智能算 法。最后介绍了本文测试实验所采用的仿真网络模型。 第三章量子进化组播路由算法，给出了量子进化时延受限组播路由算法的建 模，算法描述和算子设计，并进行了仿真实验，并与正交遗传算法进行了比较。 第四章量子进化动态组播路由算法，给出了动态时延受限组播路由算法，分 别讨论了组播成员变化和网络拓扑结构变化两种情况时的动态组播问题，进行了 测试实验，给出了比较结果。 第五章基于量子进化的大规模组播路由，借鉴量子组播路由算法，讨论了大 规模网络的集中式组播路由的实现，并进行了仿真实验，分析讨论了该算法的优 缺点，验证了算法的可行性。 一 第六章总结与展望，对本文工作进行了总结和展望。 第二章组播路由算法理论基础及基本算法5 第二章组播路由算法理论基础及基本算法 求解组播路由问题实际是构建代价最小的组播树，即求解最优s t e i n e r 树。本 章首先给出了s t e i n e r 树问题的定义，然后重点介绍了有关求解最优s t e i n e r 树问 题的理论和相关算法，给出了组播路由问题的数学模型，最后介绍了测试实验时 所使用的仿真网络模型。 2 1s t e i n e r 树问题的定义 在组播路由问题中，构建最优s t e i n e r 树被认为是当前最好的实现方式之一， s t e i n e r 树的基础理论以及算法也成为求解组播路由问题的基础。本文讨论的计算 机通信网络采用的是无向连通图来表示的，因此，我们主要介绍无向连通带权值 图中的s t e i n e r 树的算法以及性能。下面首先给出s t e i n e r 树问题的数学建模定义。 首先将计算机通信网络表示成无向连通图g ( v ，e ) ，其中y 表示网络中的节点 ( 路由器) 的集合，e 表示通信网络中任意两个不同节点x 和y 之间连通的边( 通 信链路) 的集合。对于v ( x ，y ) 在每条边 = ( 工，y ) ) e 上定义权值函数“p ) ： ej 尺+ 表示该边上的代价函数，给定信源节点s 和通信网络中组播成员集合m 其中ms 矿，s m 。求解有源树s t e i n e r 问题就是寻找一棵以s 为根节点覆盖组 播成员集合m 中所有节点，且代价最小的最优s t e i n e r 树。 根据最优s t e i n e r 树的定义，最优s t e i n e r 树的根节点是通信网络中的信源节 点s ，叶子节点是组播组目的节点的集合，即m s 中的节点。一般称m 中的节 一点为基本节点，最优s t e i n e r 树上除基本节以外的其他节点被成为s t e i n e r 节点。 将网络中所有可能成为s t e i n e r 节点的节点集合记为q ，则有m u q = v 且 m n q = o 。其中当m = v 时，求解s t e i n e r 树问题就转化成了求解图g 的最小生 成树问题。当i m l = 2 时，求解s t e i n e r 树问题就转化成了求解集合m 中两节点之 间的最短路径问题，这是s t e i n e r 树问题的两个特例。这两种情况都能在多项式时 间复杂度下求得结果，但一般的s t e i n e r 树是n p 完全问题，不存在多项式时间的 最优解法。 对一般的s t e i n e r 树，一般讨论求解它的启发式算法，使问题能在一个低阶多 项式时间内求得一个近似最优解，即启发式算法无法保证求得的解为最优解。评 价启发式算法的好坏主要考虑两个因素，一是时间复杂度的考量，要求能在多项 式时间界内求解；另一个是解的性能的考量，要求所求得的近似最优解能够尽可 能的接近最优解。因此一般比较启发式算法的性能时可以从以下三种不同的角度 进行评价：一是根据算法运行在最坏情况时所得近似解与最优解的接近程度，近 似解越接近最优解，算法的性能越好；二是根据算法多次运行所得到的近似解计 6 量子进化组播路由算法研究 算算法能够求得最优解的概率，概率越大，算法性能越好；三是根据算法求解局 部最优解的质量，这种方法不能肯定的确定算法的好坏，需要具体实践加以验证。 这三种评价方式中，最坏情况下的性能比较从理论上可以得到一个界定范围，但 是最坏情况下的性能不能完全说明算法的整体性能，平均性能更能体现算法性能 的实际意义，但是很难从理论上进行量化，本文算法的评价我们采用多次仿真实 验来测试算法的平均性能。 2 2 组播路由问题的相关算法 目前常用的求解组播路由问题的算法大致可以分为启发式算法和智能算法两 大类，本节将对这两大类中的一些算法进行介绍，在介绍算法前，首先给出组播 路由算法的数学模型。 2 2 1 组播路由问题的数学模型 在描述问题之前，首先给出几个定义和符号。 一1 ) 无向连通图g ( v ，e ) 表示网络，y 表示网络中节点的集合，e 表示网络中 边的集合，q 表示s t e i n e r 节点的集合，m 表示组播问题的组播成员集合，s 表示 组播问题中的信源节点。其中q u m = v ，q n m - 0 ； 2 ) t = ( 巧，屏) 表示以s 为源节点，且覆盖节点集合m 的一棵生成树， m 巧v ，日e ； 3 ) 对于任意边e e 定义四种度型1 3 1 ( r + 表示非负实数，足表示正实数集) ： 延时函数：d e l a y ( e ) ：e 寸足； 代价函数：c o s t ( e ) ：e 寸疋； 带宽函数：b a n d w i d t h ( e ) ：e 一足； 延时抖动函数：如坳一j i t t e r ( e ) e 专r + ； 4 ) 对于任意节点t iev ，同样的也定义下面四种度量 1 3 】： 延时函数：d e l a y ( n ) ：v - - + 墨； 代价函数：c o s t ( n ) ：v 寸足； 延时抖动函数：d e t a y j i t t e r ( n ) ：y 哼； 带宽函数：p a c k e tl o s s ( n ) ：v 专r + ； 5 ) 勺表示边( ，j ) e 代价，c ：f r + ，v ( i ，) e 。厶表示节点f 到节点的最 短路的代价，即节点f 到节点，的距离，d ( i , t ) = r a i n j , , i j 巧 表示组播树外节 点f 到树t = ( 巧，辱) 的距离，称节点，为树t 中距离节点i 最近的节点，即此时 对树中的任意节点k ，不等式z ，z 。成立； 6 )g 表示求得的近似最优组播树代价，表示对应的最优代价； 7 ) 对于给定网络g ，源节点s ；目的节点集合m ，则由s 和m 组成组播树 第二章组播路由算法理论基础及基本算法 7 r ( s ，m ) 存在f 列关系： d e l a y ( g a s ，x ) ) = d e l a y ( e ) + d e l a y ( n ) ； e e p t ( j ，j )月e p r ( s ，j ) c o s t ( t ( s ，m ) ) = c o s t ( e ) + c o s t ( n ) ； e c t ( s 朋)n e t ( s d d ) b a n d w i d t h ( p r ( s ，x ) ) = m i n b a n d w i d t h ( e ) ，e p r ( s ，x ) ； d e l a y j i t t e r ( p r ( s ，x ) ) = a e t a y j i t t e r ( e ) + 比匆一j i t t e r ( n ) ； e c p r ( j j )e p r ( s , x ) p a c k e t l o s s ( p r ( s ，x ) ) = l ll ( 1 一p a c k e t l o s s ( n ) ) n c p r ( j ，) 其中，p r ( s ，x ) 是组播树t ( s ，m ) 上从源节点s 到目的节点x 的路径。需要特别 说明的是，在上述关系中结合实际通信中的情况，忽略了通信链路的包丢失率， 仅考虑节点的包丢失率。 下面给出组播路由问题的数学模型，假设给定网络g ( v ，e ) ，组播源节点s v ， 组播目的节点集合m 一和 ) ，延时函数a e l a y ( , ) r ，代价函数c o s t ( * ) 墨，延 时抖动函数d e l a y j i t t e r ( * ) r ，带宽函数b a n d w i t h ( * ) r 和包丢失率函数 p a c k e t l o s s ( * ) 足，求解组播路由问题就是寻找一棵组播树t ( s ，m ) 满足： 延时约束：d e t a y ( p r ( s ，x ) ) b ； 延时抖动函数：如伽一j i t t e r ( p r ( s ，x ) ) d j x ； 包丢失率函数：p a c k e t l o s s ( p r ( s ，x ) ) 心； 代价函数：在所有满足条件的组播树中，c o s t ( t ( s ，m ) ) 最小。 其中所( s ，x ) 是组播树r ( s ，m ) 上从源节点s 到目的节点x 的路由路径，b 表示 带宽约束，口表示x 路由路径上的时延约束，d j 表示x 路由路径上的延时抖动x 约束，儿，则表示包丢失率约束。在该模型中，我们假设所有目的节点的带宽约束 都相同，延时，延时抖动和包丢失率约束可以互相不同。在下文中具体讨论时， 我们将延时约束也设定为相同的，进一步简化了组播问题的数学模型，方便讨论 算法的性能。 2 2 2 组播路由问题的启发式算法 下面简单介绍几种最常见的组播路由的启发式算法，首先假设网络中所有的 节点都具有组播的能力，且和本文研究问题相同仅讨论时延受限组播路由的求解。 一、k m b 算法 由b e r m a n 提出的k m b ( d n h ) 算法【2 5 1 是有关s t e i n e r 树最常用的算法之一， 它采用距离完全图和最小生成树算法。首先构造图g 的距离完全图g = ( d ，e 。) ， 对v ( x ，y ) e 是图g 中节点x 到节点y 的最短路径，也就是说边( x ，y ) e 的代价 8 量子进化组播路由算法研究 等于原网络g 中从节点x 到节点y 的最短路径的代价。然后根据构造的图g 的最 小生成树t ；将丁中的边转换回g 中的最短路径，得到子图g t ，再由g 求最小 生成树z ，最后删除生成树z 非基本节点的叶子节点就可以得到所求的组播树丁。 k m b 算法在计算的过程中使用了p r i m 算法，由于p r i m 算法适用于优化对称网络， 所以k m b 算法在对称网络上得到的组播树的代价要比最优s t e i n e r 树高 2 7 1 1 2 引， k m b 算法的复杂度为o d u l l v l 2 ) ，i m 为目的节点的个数，l 吲为网络中节点总数， 算法的平均性能较好。 二、g r e e d y 算法( 贪婪算法) g r e e d y 算法是用于解决组播成员变化，且树结构不可变的动态组播问题的 算法，其基本思想是当有一个节点要加入组播组是，加入节点首先向源节点发送 加入请求，然后计算加入节点到组播树上节点满足时延约束的最小代价路径，并 将最小代价的最短路径与之前的组播树连接，由此得到动态变化后的组播树，这 种情况下算法的时间复杂度为o ( n 2 ) 。当有节点要退出组播组时，如果离开的节点 是组播树的叶子节点，则检查删除树上所有非基本节点的叶子节点；如果退出的 节点不是叶子节点，该节点还有其他目的节点通过它与源节点相连，则不进行删 除操作。 g r e e d y 算法简单可行，构造组播树的过程只使用到了最短路径算法，对原 树的结构影响很小，能够在不改变之前组播树结构的前提下响应动态变化，不会 中断通信，而且对节点的加入和退出操作简单复杂度低，但是随着组播成员的多 次加入退出，树的性能会大大的降低。 三、其他启发式算法 比较著名的启发式算法还有t a k a h a s h i 和m a t s u y a m a 的t m 启发式算法【2 羽， 以及r a y w a r d s m i t h 提出的r s 启发式算法1 2 9 1 。 t m 算法在构造组播树时，首先将单个源节点作为初始树，然后逐次加入组 播组目的节点，每次将形成的组播树与不在树上的目的节点通过树与该节点之间 通过最小代价路径相连，重复上述操作，直到所有的组播成员都加入组播树时算 法结束，t m 算法的时间复杂度与k m b 算法复杂度相同，都为o d m i i z l 2 ) 。 r s 算法以包含不同组播组成员的森林开始，逐步连接距离最近的两棵树，直 到所有的森林合并成一棵树为止。通过仿真实验证明，r s 算法得到的组播树代价 比k m b 算法和t m 算法更接近最优的代价值1 3 0 。但是r s 算法适用于求解无向 网络中的组播路由问题，目前r s 算法还没有应用到有向网络中。 后来j i a n g 等人在k m b 算法和r s 算法基础上提出了改进算法【3 l 】，求得的组 播树代价比改进前的代价要小得多。还有一些其他的启发式算法m p h l 3 2 1 、 a d h l 3 0 l 、b s m a l 3 3 1 、k p p t 3 4 j 以及a r i e s 算法【3 5 j 等可参考相关文献。 第二章组播路由算法理论基础及基本算法9 2 2 3 组播路由问题的智能算法 智能算法是指借用生物界的规律，模仿其原理求解问题的算法。智能算法的 提出为寻找快速算法提供了新的思路，除了启发式算法外，智能算法也被应用于 求解组播路由问题。由于本文中提出的算法与基于遗传算法的组播路由算法进行 了必要，下面先通过介绍遗传算法介绍下组播路由问题的智能算法。 遗传算法( g a ：g e n e t i ca l g o r i t h m ) 是一种基于自然选择和遗传变异理论用于 求解复杂的全局优化问题的随机搜索仿生算法【3 6 1 。遗传算法学习了自然界中生物 进化机制来求解问题，它模拟自然界的进化过程，首先定义了种群即随机的初始 解集合，然后从一个种群开始，通过种群的选择、变异和交叉过程对种群内个体 结构进行重组的迭代过程，使得种群向着搜索空间中适应度越来越好的区域进化， 它对问题的搜索空间没有硬性的要求。 遗传算法已被广泛地应用于各种工程优化问题中，它利用简单的编码技术和 生物进化中的繁殖规律来解决复杂问题，下面介绍遗传算法中的一些概念和主要 步骤。 1 ) 个体( i n d i v i d u a l ) ：遗传算法中用个体也称为染色体( c h r o m o s o m e ) 来定 义问题的一个解，通常用一个串来表示，根据具体问题的不同，这个串通常可以 分为二进制串，实数串，整数串等不同的形式。 2 ) 种群( p o p u l a t i o n ) ：遗传算法中个体的集合，表示求解问题的若干解的集 合，遗传算法在初始化时，随机地选择一定数量的个体构成初始种群。 3 ) 遗传算子：遗传算法过程中用于指导解进化，作用在种群中每个个体的算 子，常用的遗传算子主要有选择算子( s e l e c t i o no p e r a t o r ) 、交叉算子( c r o s s o v e r o p e r a t o r ) 和变异算子( m u t a t i o no p e r a t o r ) 。其中，选择算子的作用是选择种群中 适应性好的个体构成下一代新的种群，选择的方法有很多，最常用的是适应度比 例法，也称轮盘赌选择法，选择过程使种群中适应性好的个体比适应性差的个体 有更多的复制机会。交叉算子主要用于种群中不同个体之间进行信息交流，它作 用在种群中的两个不同个体上，通过个体中部分串的互换产生新的个体，进行交 叉的串部分是随机的，交叉算子也是以一定概率进行操作的，常用的交叉算子有 单点交叉、多点交叉、均匀交叉、算术交叉和线性交叉等。变异算子是模拟生物 进化过程中由于环境等偶然因素引起基因突变产生而新的基因而引入的一种算 子，在二进制串个体中，变异算子是将基因串中某个基因位以一定概率取反，同 样的突变算子是以一定概率起作用的，而且和生物进化过程中一样，突变发生的 概率很小，突变算子操作后也产生新的个体，它能辅助算法搜索到整个解空间的 每一个个体，弥补交叉算子的作用无法实现对整个解空间的搜索的，增加了算法 的全局性。 1 0 量子进化组播路由算法研究 4 ) 适应度函数和适应度( f i t n e s s ) ：适应度表示在遗传空间中，个体对于周 围环境的适应程度，适应度函数是遗传算法中的一个很重要的控制参数，它类似 于优化的目标函数，对于具体的优化问题，构造合适的适应度函数是一个非常重 要的问题，它决定了算法所确定的解决问题方案的好坏。 通过遗传算法来解决某问题时，首先要对问题进行编码，即将问题的解从问 题的搜索空间映射成遗传算法的遗传空间中的个体，然后根据编码和求解问题构 造适应度函数，设计算子，确定算子作用在个体上所得到的新个体仍在遗传空间 内，并尽可能的实现对整个空间的搜索。遗传算法的主要步骤如下： 1 随机地产生一个有确定长度的特征串构成初始种群； 2 计算种群中各个体的适应度值； 3 进行选择、交叉和变异操作产生下一代种群； 4 重复步骤2 和步骤3 至满足停止条件； 5 将适应度最高的个体直接复制到下一代中，指定停止进化那一代出现的最 高适应度值的个体为遗传算法所得到的结果，这个结果就表示优化得到的 问题的一个解。 下面介绍基于遗传算法的组播路由算法，按照编码方式基于遗传算法的组播 路由算法可以分为三类：基于二进制编码、基于树型编码和基于整数编码。 l 、基于二进制编码 基于二进制编码的遗传组播路由算法中，采用o 、1 编码的方式，可以对所有 s t e i n e r 节点进行编码，个体中的每一个基因位代表一个除组播成员节点的中间节 点，若给定网络节点总数为疗，目的节点数为朋，对网络中除了源节点和目的节点 以外的其他节点进行编号：0 ，l ，2 ，刀m 2 ，则遗传算法中二进制编码长度为 甩- m - i 。因此，求解最优s t e i n e r 树的关键就在于确定和组播组节点相连构建组播 树的中间节点。此类算法的重点和难点操作在解码，解码操作对解的质量以及算 法效率起决定性作用，在前面介绍的k m b 算法中已经对解码映射的过程进行过 简单的介绍。x i a n g l 3 7 】等人还提出了一种采用n x n 的一维二进制编码机制的通用 的遗传算法，其中n 为网络中的节点总数，这种编码方式使得算法的编码和解码 过程都非常复杂，而且随着网络规模的增大，解搜索空间剧烈增大，算法效率很 低。根据解码方式的不同，还有很多不同的算法提出，但这些算法都采用二进制 编码和标准的遗传算子。在采用二进制编码方式设计算法时，如何简化解码过程， 提高算法效率是需要解决的关键。 2 、基于树形编码 r a v i k u m a r 等人【3 8 】提出了一种采用树型编码的求解时延受限组播路由问题的 遗传