（计算机应用技术专业论文）qos多播路由算法及仿真研究.pdf

武汉理工大学硕士学位论文 摘要 当前通信网络带宽和处理能力的提高使网络能提供更多的多媒体业务， 其中许多业务都要求网络具有多播( m u l t i c a s t ) 能, 力，例如音频视频会议、交 互式仿真、多人游戏、分布式数据库等。在多播通信中，若对每个信宿单独 发送数据包，则将大大浪费网络资源，增加节点的处理负担，严重时会加剧 网络的拥塞。因此往往首先建立一棵多播树，信源发出的数据包沿着多播树 进行转发，这棵多播树由多播路由算法决定。因此研究构造多播树的多播路 由算法就非常重要。 本文首先介绍多播通信的背景知识和分析要实现多播尚需解决的问题， 并介绍了典型的多播路由算法。描述了s t e i n e r 树的理论和相关算法。重点对 遗传算法和蚂蚁算法进行了较为仔细的研究。在此基础一l - _ 将两者有机结合， 提出了一一种混合蚂蚁算法( g a a a ：c o m b i n a t i o no fg e n e t i ca l g o r i t h ma n da n t a l g o r i t h m ) ，并用c + + 语言实现了该算法，仿真结果证明该算法收敛快，费用 小，是一种有效的算法。 本文总共分为6 章。其内容如下： 第1 章介绍了多播路由的发展背景、研究现状及课题来源，介绍了主要 的几种多播路由算法和q o s 的相关知识。并介绍了本课题的来源及研究的意 义。 第2 章介绍了s t e i n e r 树问题及目前几种主要的多播路由启发式算法，分 析了其局限性。介绍了w a x m a n 随机网络模型。 第3 章介绍了遗传算法的产生和发展、特点、优缺点和应用，还介绍了 遗传算法的基本步骤，混合遗传算法，包括在遗传算法中用于解决约束优化 问题的常用方法。 第4 章介绍了蚂蚁算法的产生、发展、基本原理和具体步骤，介绍了蚁 群优化算法和最值蚂蚁算法。 第5 章是本文工作的重点，在这章中我们提出r 一种混合蚂蚁算法，并 将其应用于时延受限q o s 多播，仿真说明，该算法性能优于传统的遗传算法。 第6 章是本文的总结，并对下一步的工作作出了展望。 本文得到了国家自然科学基金项目( 批准号：6 0 1 7 2 0 3 5 ) 的资助。 关键词：q o s 多播路由，s t e i n e r 树，遗传算法，蚂蚁算法，g a a a 算法 - i 武汉理i ：火学硕士学位论文 a b s t r a c t t h er e c e n ta d v a n c e sl nt h e h i g h - s p e e d e o m m u n i c a t i o nn e t w o r k sh a v ee n a b l e dt h c n e t w o r kt op r o v i d em o r ea n dm o r em u l t i - m e d i a a p p l i c a t i o n s ，s u c ha sa u d i o v i d e oc o n f e r e n c e ， d i s t r i b u t e ds i m u l a t i o n ，m u l t i u s e rg a m e ，d i s t r i b u t e dd a t a b a s e e t c ，w h i c hh a v em a d et h e m u l t i c a s tan e c e s s i t y h o w e v e r , t h ep r o b l e mi st h a ti fm u l t i c a s ti sr e a l i z e do n l yb ys e n d i n g p a c k e tc o p i e st ot h ed e s t i n a t i o n sr e s p e c t i v e l y , t h en e t w o r kr e s o u r c e sw i l lb ew a s t e dg r e a t l y w h i l et h ep r o c e s s i n ga b i l i t yo fn e t w o r kn o d e sw i l lb ea f f e c t e dd r a m a t i c a l l y , m a k i n gn e t w o r k c o n g e s t i o nm o r es e r i o u s t h e r e f o r e ，s e t t i n gu pa ne f f i c i e n tm u l r i c a s tm u t i n ga l g o r i t h mi s e s s e n t i a lt ot h er e a l i z a t i o no fm u l t i c a s tc o m m u n i c a t i o ni nt h a ti ti st h ea l g o r i t h m sd e t e r m i n e s t h eo o n s t m c t i o no fm u l t i c a s tt r e e ，a l o n gw h i c ht h ep a c k e t sc o u l db et r a n s m i t t e dw i t hh i g h s p e e d t h e p r e s e n ts t u d yi sd e s i g n e dt oi n v e s t i g a t et h em u l t i c a s tr o u t i n ga n dt h eo t h e rr e l e v a n t k e yp r o b l e m s f o l l o w i n g t h ei n t r o d u c t i o nt os o m eb a s i c k n o w l e d g e o fm u l t i c a s t c o m m u n i c a t i o na n di t s p r a c t i c a lp r o b l e m sr e m a i n e dt ob es o l v e d ，t h ep a p e rp r e s e n t ss o m e t y p i c a la l g o r i t h m ss u c ha st h em u l t i c a s tm u t i n ga l g o r i t h m ，t h es t e i n e rt r e et h e o r ya n di t s r e l e v a n ta l g o r i t h m ，t h eg e n e t i ca l g o r i t h ma sw e l la st h ea n ta l g o r i t h m b a s e do nt h ed e t a i l e d d i s c u s s i o na b o u tt w o k e ya l g o r i t h m s ，t h eg e n e t i ca l g o r i t h m a n dt h ea n t a l g o r i t h m ， c o m b i n a t i o no f g e n e t i ca l g o r i t h ma n da n ta l g o r i t h m ( g a a a ) ，i sf i n a l l ys e tu pa n dr e a l i z e db y a d o p t i n gc + + l a n g u a g e t h es i m u l a t i o n r e s u l t ss u g g e s tt h a tt h en e wa l g o r i t h mi sm o r e e f f i c i e n ta n dm o r ee c o n o m i c a lt h a nt h eg e n e t i ca l g o r i t h ma n dt h ea n ta l g o r i t h m t h i st h e s i sc o n s i s t so f s i xm a i n c h a r p t e t s ： c h a r p t e r1b r i e f l yd e m o n s t r a t e st h ed e v e l o p m e n to fm u l t i c a s tr o u t i n g ，t h e p r e s e n t s i t u a t i o n so ft h er e l a t e ds t u d i e s ，t h eo b j e c t i v e s ，s i g n i i i c a n c e sa n ds o u r c e so f t h es t u d y , s o m e t y p i c a lr o u t i n ga l g o r i t h m sa sw e l la ss o m ek n o w l e d g ea b o u tq o s ，a l s oi n t r o d u c 访gt h es o l l r e e a n d m e a n i n g f o rt h i sa r t i c l e c h a r p t e r2s t u d i e so o sc o n s t r a i n e ds t e i n e rt r e ep r o b l e m i n t r o d u c i n gs e r v a l m a i n l y h e u r i s t i c a l g o r i t h m s , d i s c u s s i n g m u l t i c a s tt h e o r yt h a ts u p p o r t i n go o s c l m r p t e r3r e c o m m e n d st h ed e v e l o p m e n th i s t o r yo fg e n e r i ca l g o r i t h m ，a n di n c l u d i n g c h a r a c t e r i s t i c ，a d v a n t a g ea n dd i s a d v a n t a g e w ea l s og i v et h eb a s i cs t e p ，i n t r o d u c eh y b r i d i i 武汉理1 。大学硕十学位论文 g e n e t i ca l g o r i t h m ，s o m ed e t a i l sh a v ey e tt ob ed i s c u s s e da b o u ts o l u t i n gt h ec o n s t r a i n to o s w i t h g e n e t i ca l g o r i t h m c h a r p t e r 4d e m o n s t r a t e st h eo d l 如，d e v e l o p m e n t ，b a s i c p r i n c i p l e sa n dp r o c e d u r e so f a j l t a l g o r i t h m a n ta l g o r i t h mi sag e n e r a lp u r p o s ea l g o r i t h mi n s p i r e db y t h e s t u d yo f t h eb e h a v i o r o fa n tc o l o n i e s t h i sp a r tt h e ni ts t u d i e st w ot y p i c a la c o s ，n a m e l ya c oa n dm m a x ， c a r e f u l l y c h a r p t e r5i s t h ek e yp a r to ft h ew h o l ep a p e r i t p u t s f o r w a r dg a a a a l g o r i t h m ，a c o m b i n a t i o no fg e n e t i ca l g o r i t h ma n da n t a l g o r i t h mf o ro o sm u l t i c a s tr o u t i n g i ta d o p t s g e n e t i ca l g o r i t h mt os o l v ea n d t og i v ei n f o r m a t i o np h e r o m o n et od i s t r i b u t ea n dm a k e u s eo f i t sa b i l i t yo f q u i c k n e s sa n ds t o c h a s t i co nag l o b a l l ys e a r c h i n g , a tt h es a l t l et i m e ，i tg i v e st h e w e l ls o l u t i o nm a k eu s eo ft h ec h a r a c t e r i s t i c so fa n ta l g o r i t h mc o n v e r g e so n o p t i m i z a t i o np a s s i n f o r m a t i o n p h e r o mo n ea c c u m u l a t i o n a n dr e n e w t h es i m u l a t i o nr e s u l ts h o wt h a tt h e a l g o r i t h m i sv a l i da n de f f e c t i v e c h a r p t e r 6s u m m a r i z e st h em a j o r f i n d i n g s ，p r e s e n t st h el i m i t a t i o n so f t h ep r e s e n t s t u d y a n d p u t sf o r w a r d s o m e s u g g e s t i o n sf o rt h ef u t u r es t u d i e s t h i sp a p e ri s s u p p o r t e db yn a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o no fc h i n a ( p r o j e c t n o ，6 0 1 7 2 0 3 5 ) k e y w o r d s ：o o sm n i t i c a s tr o u d n g ，s t e i n e r - t r e e ，a n ta l g o r i t h m ，g e n e t i ca l g o r i t h m g a a a a l g o r i t h m 耍堡些! ：叁兰堕主堂垡堡奎一 1 。1 路由算法概述 第1 章绪论 路由算法的主要功能是指引分组通过通信予网到达正确的目的节点。它 包括两个方面的功能： 1 ) 为不同的源节点和目的节点对选择一条传输路径； 2 ) 在路由选好以后，将用户的消息正确的送到目的节点a 路由算法是网络层具有的协议，路由算法既要试图使网络的通过量最 大，又要试图使网络的平均分组时延最小。路由算法通常很复杂，这主要表 现存： 1 ) 路由算法要求子网中所有节点相互协调，而不像链路层和高层那样 仪涉及对对等模块之间的协调。 2 ) 路由算法必须处理链路和节点的故障，要求对业务进行重新定向和 对系统维持的数据库进行更新。 3 ) 必须达到高的性能。当网络部分区域拥塞时，路由算法必须能够修 币路由。 对于一个理想的路由算法应具有如下的特点川： 1 ) 算法必须是正确的和完整的，即每一个节点( 交换机和路由器) 中 的路由表，必须都给出到所有可能的目的节点的下一站应怎样走，并且所给 出的走法应是f 确的。这里正确的含义是：沿着各节点( 交换机或路由器) 中路由表所指引的路由，分组一定能够到达目的节点。并且分组到达目的节 点后不会在向其它节点转发该分组。 2 ) 算法在计算上应简单。由于每个节点上都要进行路由选择的计算， 因此必然要增加分组的时延。此外路由算法的计算不应使网络的通信量增加 太多的额外开销。若为计算合适的路由必须使用网络的其它节点发来的大量 状态信息，额外开销就会增大。 3 ) 算法应能适应通信量和网络拓扑的变换。这就是况要有自适应性。 当网络中的通信量发生变化时，算法能自适应的改变路出，以均衡各链路的 武汉理1 大学硕e 学位论文 负载。 4 ) 当某个或某些节点链路发生故障不能工作时，算法也能及时的改变 路f 白。有时称这种自适应性为“稳健性”或“鲁棒性”。 5 ) 算法应是公平的。算法应对所有用户( 除对少数高级的用户外) 都 是平等的。例如，若使某一对用户的端到端时延为最小，但却不考虑其它的 用户，这就明显的不符合公平性的要求。 6 ) 算法应是最佳的。这里的“最佳”通常是指以最低的费用( 成本) 米实现路由算法。这里特别需要注意的是，在研究路由算法时，“费用”并不 一定就是“钱”。每条链路的费用通常由链路容量、节点缓冲区被占用的程度、 链路的差错率情况等因素综合决定。可以根据用户的具体情况来设置每一条 链路的“费用”。 7 ) 个实际的路由算法，应尽可能的接近于理想的算法。在不同的应 用条件下，对以上提出的六个方面也可有不同的侧重。 路由算法在何时执行，取决于网络中采用的路由方式。如果采用数据撤 方式，则对每一个分组都要进行一次选路。因此相同源和目的节点的分组可 能会经过1 i 同的路径。如果采用虚电路方式，则在虚电路建立时要进行路山 选择。 1 2 多播技术发展的背景 如今计算机网络飞速发展，网络功能日益强大。网络的作用从简单的信 息传送发展到远程教学、视频会议、数据分发和网络游戏等。用户的数据要 从一个终端发送到另一个终端，首先要确定传输路由，不同的通信方式，其 确定路由的方式也不同。如今网络的通信方式主要有以下几种： 单播( u n i c a s t ：p o i n tt op o i n t ) ，点到点的通信方式。 多播( m u l t i c a s t ：p o i n tt om u l t i p o i n t ) ，点到多点的通信方式。 汇播( c o n c a s t ：m u l t i p o i n tt o p o i n t ) ，多点到点的通信方式。 群播( m u l t i p o i n tt om u l t i p o i n t ) ，多点到多点的通信方式。 广播( b r o a d c a s t ：p o i n tt oa l lp o i n t ) ，点到所有节点的通信方式。 任播( a n y c a s t ：p o i n tt oa n yp o i n o ，一点到一个或多个网络接口( 通常属于 不同的结点) 的通信。如果数据包发向任播地址，它会被路由到有这个地址 的最近接口处，至于什么是最近的接口要看路由协议的规定t 1 2 , 3 1 。 2 武汉理【i 人学硕十学位论文 单播的实现般采用d i j k s t r a 提出的最短路算法( s h o r t e s tp a t h a i g o r i t h j m ) 4 l 或b e l l m a n f o r d 算法来建立点到点的路由。当只有两个终 端参与同进程时，一般采用单播方式。广播是网络中常用的通信方式，其 是节点向网络中所有节点发送信息的通信方式，广播通信方式在局域网中 应用很广。而多播是一源节点向多个目的节点发送信息( 但不是所有节点) 的 通信方式，涉及多播技术的应用很多，如多媒体会议、远程教育、数据分发 等。多媒体会议是多播应用的一一个典型例子，数据分发是多播应用的另个 领域，这项技术允许公司每天夜里向他们的远程商店发布新的信息，比如价 格和产品信息，以便在下一个营业日有更新的信息。多播应用的普及也导致 了多播主干网f m b o n e ) 的快速发展。汇播私多播有相同之处，多播是一点到多 点的通信，而汇播是多点到多点的通信方式，例如远程数据采集就是采用的 汇播方式。至于群播的典型应用是网络即时游戏，在多方游戏中，需要将各 自的状态互相同步发送。在多播、汇播和群播中，多播是目前研究得最多， 也是应用最。的网络连接方式。 在多播通信中，若对每个目的节点单独发送数据包，则将大大浪费网络 资源，增加源节点的处理负担，严重时会加剧网络的拥塞。因此，有必要寻 求网络层对多播通信的支持，使多播技术满足多媒体实时应用的要求。从而 出现了以多播树( m u l t i c a s t i n gt r e e ) 实现多播的方式多播树是覆盖所有多播 组成员的棵生成树，多播树有以下两个优点：1 ) 信息以并行的方式沿着树 枝发送到不同的组成员，降低了信息传递的时延：2 ) 网络中需要传送的复制 信息最少，而且信息的复制只在树权处进行，这样能够节省网络带宽资源， 提高每次多播通信时的资源利用率，并能减少拥塞，降低网络负载。而这棵 多播树的生成是由多播路由算法决定。 一般要求多播服务的业务对带宽和实时性要求较高，涉及用户较多，占 用的资源也多，因此有必要优化多播路由。多播路出算法就是要寻求最优多 播树，理想有效的路由算法将设计一棵仅覆盖多播组成员的树，并体现如下 特征：1 ) 树随着组成员变化动态更新；2 ) 最小化节点需要保存的状态信息 量；3 ) 避免链路和节点的流量集中；4 ) 根据费用函数优化路由。 1 3 多播路由技术的研究现状 3 武汉理b 尺学颂：k 学位论文 1 3 1 多播路由算法的分类 多播路由算法按其实现方式可分为集中式源路由和分布式路由1 6 1 ，它们 各有优缺点： 1 ) 源路由采用集中处理的方式，因此在发出路由请求时，可以立即获 得预先存在的路由信息，无需在网络的各个节点之间进行信息交换。但它需 要在网络中每个节点上都维持一张有关整个网络全局链路状态的“图”；另 外，经过源路由计算的路径是不含回路的。源路由是一种简单、明了、易于 实施、评估、检查和升级维护的路由计算方法。与设计、解决属于n f 一完 全问题的分布式路由启发式算法相比，其实施是非常容易的。但基于源路由 的路出算法也存在一些问题，即：( 1 ) 为维持整个网络通信链路的状态信息 必须进行高频率的状态刷新，给网络造成了负载；( 2 ) 由于不可避免地存在 着刷新延迟，因此存在着状态信息滞后的问题。 2 ) 分布式路由算法 在分布式路由中，路径计算是激励式的，即当有路由请求时，它不会马 上获得到路由信息，需要一个路径搜索延迟。但是，该类路由选择和优化都 足基 二局部状态信息的，不需要像源路由那样为网络所有节点部维持一张键 路状态表。因此，分布式路由算法能够很好地适应网络规模，但计算复杂度 比较高。同时，在多方向上并行搜索多个可行路径，增加了搜索的成功率。 但是当链路状态信息由于广播延迟而造成不同节点的有关链路状态不一致 时，回路就会发生，从而增加了网络带宽的消耗。 多播路由算法按多播组成员是否变化又可分为静态和动态多播路由算 法【6 j ：静态多播路由算法针对仞始多播组成员构造一棵多播树，它不能够根 据当前组成员的加入或离开来调整路由，而是按初始设计好的路径传送，它 的路由修改需经过定时问的运行后进行；动态多播路由算法可以针对组成 员的加入或离开适时的进行多播树的更新，但若动态算法对路由的频繁修j f ， 将会引起通信的不稳定。 1 3 2 多播路由算法简介 目前，针对不同的基于q o s 约束的多播路由问题，已提出许多相应的 路由算法。 4 武汉理l ：大学硕十学位论文 1 ) 最短路径算法 最短路径算法使多播树上从源节点到目的节点的每条路径j 二链路权值 之和最小。若所有链路的权值均为1 ，则算法所获得的多播树即为最小跳树； 若权值代表链路时延，则算法将获得一棵最小时延树。b e l l m a n f o r d 算法 和d i j k s t r a 算法是两个最著名的最短路径算法，其时间复杂度分别为o ( n 3 ) 和o ( n 2 ) 。最短路径算法是搜索最短路径的常用算法。 2 ) 最小生成树算法 最小生成树是一棵覆盖图中所有节点并且树权重最小的树。著名的集中 式最小生成树算法是p r i m 算法f 6 】。而g a l l a g e r 等学者则提出了解决最小 生成树问题的一个分布式算法【7 】 2 5 】。在p r i m 算法中，从任意一个根节点开 始构建整棵树，直到其扩展到网络中所有节点。在每一步中，连接已选择节 点与末选择节点的权重最小的边被加入到树中。算法采用了贪婪策略，在树 的增长过程中，每次选择的边都是使树权重增加最少的边。最小生成树算法 可用来解决树的最优化问题。 3 ) 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 树算法( 8 j 可用来解决树最优化问题，但对于有约束的应用该 类算法却很难满足其端到端的约束条件。w i n t e r 9 】和h w a n g l l 0 1 分别深入研 究了启发式s t e i n e r 树算法。s a l a m a 和r e e v e s 等学者通过对已有的启发式 算法的大量仿真指出由k o u ，m a r k o w s k i 和b e r m a n 提出的k m b i “】算法具 有较好性能，是一个较为有效的算法，其所获得的多播树的平均费用仅高于 s t e i n e r 树费用的5 ，而其算法的时间复杂度为o ( 1 g i i v l 2 ) 4 ) 基于q o s 约束的s t e i n e r 树算法 在进行树优化的多播路由中加入不同的q o s 约束( 例如带宽、时延、 时延抖动或者它们的组合) ，则s t e i n e r 树问题就扩展为基于o o s 约束的 s t e i n e r 树问题。由于这些问题也是n p 完全问题，目前研究较多的是采用 启发式算法。 ( 1 ) 基于源路由的启发式算法 在基于源路由的算法中具有代表性的是k o m p e l l a 等提出了种基于时 延约束的启发式算法一k p p ”】及z h u 等也提出了一种基于时延约束的启发 式算法一b s m a i 】3j 。 在k p p 算法中假设链路( 1 1 ，v ) 的时延d ( u ，v ) 及时延约束均为整数，链 5 武汉理1 人学硕十学位论文 路( u ，v ) 的费用c ( u ，v ) 为j e 实数。给定源节点s 和多播组d ，k p p 首先得到 一个覆盖 s 1ud 的满足时延约束完全图g + ；然后利用p r i m 算法从源节点 丌始，一次增加条选定的边，直到整棵树包含所有接收节点从而得到一个 满足时延约束的最小生成树；最后用图中的路径替换最小生成树中的边。在 k p p 中提出了两种选择函数：一是链路费用；另一个则强调最小费用与最小 时延之间的平衡。k p p 算法的时间复杂度为o ( a i v l 3 ) 。 在b s m a 算法中，算法茸先构建一棵以给定源节点为根节点并且覆盖 所有组成员的最小时延树；然后在不违反时延约束的前提f ，反复用不在树 上的费用更小的路径替换树中的超边，直到再也找不出费用更小的路径。算 法利用第k 短路径算法寻找费用更小的路径。如果可行解存在的话，b s m a 总能找到一个满足时延约束的多播树，因为它起始于一棵最小时延树。b s m a 算法的时间复杂度为o ( k l v l 3 l o g l v i ) 。 ( 2 ) 分布式启发式算法 k o m p e l l a 等提出了一种分布式启发算法来构建时延约束的s t e i n e r 树 算法。算法要求网络中每个节点维护一个到其它所有节点的最小时延距离欠 带。它所构建的树最初只包括源节点，然后向树中每次增加一个接收节点， 直到该树包含了所有接收节点。算法使用以下方法选择每次增加的接收节点。 源节点向已构建的部分多播树上节点以多播形式发送一个f i n d 消息。树上 节点收到f i n d 消息后，各自确定连接其与非树上的接收节点的发送路径， 该路径不违反时延约束条件并且使选择函数最小。接着，树上节点向源节点 回送一个r e s p o n s e 消息，它包含了候选路径的标识。当源节点收到所有的 r e s p o n s e 消息后，节点s 将选择一条使选择函数最小的最好路径，并把该链 路加入到树中。该算法要求控制信息可多播传送。 j i a 等也提出一个基于时延约束的分布式算法| 1 4 1 ，并假设任意两节点间 的最小费用路径即是最小时延路径( 但这通常是不现实的) ( 3 ) 采用遗传算法解决基于q o s 约束的s t e i n e r 树问题 自1 9 9 5 年h e s b e n s e n 应用遗传算法【1 5 】( g a ：g e n e t i c a l g o r i t h m s ) 有效解决s t e i n e r 问题以来，遗传算法逐渐成为一种求解q o s 组播路由问题 的研究手段。遗传算法作为一种新型的模拟生物进化过程的随机化搜索优化 算法，以在解决诸多典型组合优化问题中显示了良好的性能和效果。 r a v i k u m a r 等卜邮针对时延约束费用最小多播路由问题提出一种遗传算 法。王征应等提出一种启发式遗传算法求解基于带宽、时延等约束的s l e i n e r 树1 。算法以树型结构作为染色体的编码，并构建一较为复杂的适应度函数 ，6 武汉理r 人学硕十学位论文 并在交叉策略上采用了启发式方法。x i a n g i ”j 等提出一种通用的遗传算法， 算法采用n n 的一维二进制编码机制( 其中n 为网络节点数) 。 ( 4 ) 其他算法 在文献 1 9 】中作者针对端到端时延和时延抖动约束的多播路由问题提 出了基于h o p f i e l d 神经网络的多播路由优化算法。在文献 2 0 1 中基于蚂蚁 算法( a n t a l g o r i t h m ) 提出了一种解决多播路由问题的分布式算法。 对于q o s 多播路由问题，研究得最多的是受限多播树f c o n s t r a i n e d m u l t i c a s t i n gt r e e ) ，其中包括时延受限最小费用多播树，带宽受限多播树问题。 另外，时延抖动受限问题也是研究的重点。由于q o s 路由问题的复杂性，引 入人工智能方法是很合理的，目前提出的算法有两种，一种是基于遗传算法、 神经网络技术的多播路由算法；另一种是基于模糊理论的模糊寻径。近些年 来，人们在对大自然中动物的一些行为特性研究后提出了“仿生型”算法的 概念，其中蚂蚁算法以其本身良好的性能受到了人们的广泛关注，在q o s 路 由问题的研究中也得到了广泛的应用。 以数据报方式传输的分组网络不易提供实时通信的服务保证，在这种情 况下，一般需要在分组流进行传输前建立会话虚连接。在建立会话虚连接时， 应用j j j 以指定q o s 要求；基于所需的o o s 和网络资源，可以通过路由、资 源预留和接入控制等模块选择合适的路由并预留资源；当分组流经过选定的 网络元素( n e ) 时，通过分类、缓存和凋度等资源管理模块完成对分组流的服 务处理。由此可见提供q o s 保证是个很复杂的过程，需要网络和终端系统 的一系列软件、硬件支持。一般会同时由以下多个系统组成部分的共同参与： o o s 路由、实时传输层协议、分组调度机制、资源预约以及实时操作系统和 多媒体设备，这些功能之间必须紧密合作。 网络路由功能主要划分为两个部分：路由协议和路由算法。路由算法将 根据会话需求完成选定连接一个会话中的信源到各信宿的路由工作：对于 q o s 多播来说，路由算法是构造一棵以发送节点为根的树，要求覆盖所有接 收节点，并巳从发送节点到每一个接收节点的树上路径和链路满足边界条件。 本文将在第二章中研究。而路由铷议则描述了如何在具体网络中实现路由算 法，路由协议必须是健壮而且容错的。 1 3 。3q o s 约束 常用的几种q o s 约束【2 1j 主要包括带宽、端到端时延、分组丢失率、抖 7 武汉理工大学硕 = 学位论文 动和费用，不同的约束具有不同的性质。按照这些性质，o o s 约束可以分为 可加性约束、可乘性约束和最小性约束3 类。 1 ) 可加性约束 包括时延、时延抖动、费_ 3 、转发跳数( h o pc o u n t ) 等。例如，一条路径 的叫延为从源到目的地的所有链路时延与结点时延的总和。 2 ) 可乘性约束 包括分组丢失率为可加乘约束，其中链路丢失率为0 与1 之问的实数。 在求解有关可乘性约束的过程中，可以类比参照可加性约束的有关求解方法。 3 ) 最小性约束 例如，带宽为最小性约束，即路径带宽为路径上瓶颈链路的带宽。 求解单个q o s 约束以及多个组合的q o s 约束，其计算的代价是不同的。 例如，求解多重最小性约束的组合可以在多项式时问内完成，而多重可加性 约束的组合通常不能在多项式时间内完成。在q o s 路由选择参数中，带宽与 时延是最常用的参数。 1 3 4 服务质量路由( q o s r ) 的目标 可行q o s 路径是网络中从源点到目的结点的一条满足特定的q o s 需求 的路径，为了提供q o s 保证，数据传输前通常要先计算可行路径，然后按照 此路径传播。个可行的解决方案应达到以下目标： 1 ) 动态确定可行路径。 2 ) 优化全局资源利用率，平衡网络负载。 3 ) 对性能的影响尽可能小。 根据这个目标，路由选择问题应该由以下三部分组成： 1 ) 获得满足应用请求所必需的路由计算信息。 2 ) 建立一条满足q o s 请求的路径。 3 ) 维护已建立的路径。 1 。3 5 服务质量路由( q o s r ) 问题难解决的原因 q o s r 很难完全解决的原因有： 1 ) 寻找同时满足两个以上条件约束的可行路径是一个n p 问题： 2 ) 为了提高可扩展性所使用的层次化模型，带来了多种参数如何聚集 ，8 武汉理j 大学硕士学位论文 的问题； 3 ) 网络状态信息的陈旧性极大影响了q o s r 算法的性能； 4 ) 目前的网络体系和结构对q o s 支持性不强，而且如果将q o s r 融入 到当前这种“尽力而为”的路由体系中，原有的业务将受到巨大打击。 1 4 本文的课题来源和意义 在q o s 的早期研究中，许多q o s 的研究着眼于调度，拥塞控制，资源 顸留，而对q o s 路由研究得不多。近几年得研究表明网络q o s 多播路由的 算法对保证服务质量起到关键的作用。研究基于i n t e r n e t 的q o s 路由算法， 以获得较好的网络服务质量和高的网络资源利用率具有十分重要的研究意 义。 一般来蜕，求解q o s 多播路出问题是非常困难的。首先，分布式多媒体 数据传输的q o s 要求很苛刻。其次，网络的状态是动态变化的，最后，网络 规模的日益扩大和无线链路的接入增加了网络状态的不确定性。从而降低了， 多播算法的寻径能力。因此，目前主要采用各种启发式算法来求解。如遗传 算法、模拟退火算法和神经计算等。 遗传算法是近些年提出的一种新的仿生型优化算法，它被广泛用于解决 各种具有n p 难度的问题。其优点是：具有大范围的全局搜索能力，鲁棒性 强，具有内在的并行性，收敛速度快。其缺点是：不能充分利用系统的反馈 信息，产生大量冗余迭代，过快收敛会陷入局部最优解问题【2 2 】。随着人们研 究的深入，人们发现一些优化算法如爬山法、梯度法、模拟退火算法具有很 强的局部搜索能力，而另一些含问题相关的启发知识的启发式算法也有很高 的运行效率，将这些优化算法的思想加以合理的融合，形成一种混合型算法， 是一种提高运行效率和求解质量的有效手段。 蚂蚁算法是一种仿生类算法。其优点是：具有全局优化能力和本质上的 并行性，同时具有天然的随机性、自适应性和分布式等特点，适合并行计算 和求精确解。其缺点是：初始信息素匮乏，求解速度慢【2 3 】。 基于遗传算法的快速全局搜索能力和蚂蚁算法的正反馈收敛机制，本文 提出一种混合蚂蚁g a a a 算法，初期采用遗传算法过程生成信息素分布，后 期利用蚂蚁算法正反馈求精确解，优势互补。 本文得到了国家自然科学基金项目( 批准号：6 0 1 7 2 0 3 5 ) 的资助。 武汉理1 人学硕士学能沦文 第2 章多播树理论基础和算法 2 1 s t e i n e r 树问题 对于多播路出问题，一般要建立费用最小树，而最优s t e i n e r 树【2 5 j 的 费用是最小的，因此s t e i n e r 树被认为是实现多播通信的最好办法之一。s t e i n e r 树理论及其算法也成为求解多播树的基础。 计算机通信网一般用无向图g ( v ，e ) 表示，v ( v l ，v ! ，v3 ，v n ) 是图g 的节点 集，e 为图g 的边集，n = v l 为图g 的节点数，i e | 为图g 的边数或链路数， 每条链路e ( j ，j ) 的链路费用为c 0 , j ) ，d = d l ，d ! ，d 3 ，d m 表示目的节点集；s 为 所有可能成为s t e i n e r 节点的节点集，q 对应多播问题的组成员，q n s = 中， v = q us 。s t e i n e r 树多播路由算法定义为从图g 中找出覆盖d 中所有节点的 最小生成树t ，即使得树的费用c ( t ) = m i nf c ( i ，j ) 最小，该最小生成树称为 ( ，l 白 s t e i n e r 树。 d = v 情况下，s t e i n e rf j 题就简化为求图的最小生成树的问题，其时削复 杂度为o ( n 2 ) ；当l d l - 2 时，s t e i n e rf j 题又简化为求两节点间的最短路径问题， 也可以在多项式时问复杂度o ( n 2 1 内解决。除此之外，求s t e i n e r 树问题是n p 完全问题。 2 。2 s t e i n e r 树的启发式算法 对s t e i n e r 树问题一般讨论解它的启发式算法。因为精确计算最优多播树 需要使用枚举的方式，其计算量随网络节点的增加而指数增加，在网络规模 较大时，寻找。棵s t e i n e r 树需要很长的时间，因此确定式算法不适用于网络 多播应用。启发式算法并不保证给出最优解，那么如何评价启发式算法的好 坏呢? 主要是基于两个方面的考虑：首先是时间复杂性方面的要求；其次是性 能方面的要求，即希望所求的近似解尽可能“接近”最优解。 l o 武汉理 。大。学硕十学位论文 在描述问题之前，首先给出了几个定义和符号。 定义2 1g = f v ，e ) 表示无向连通图，v 为节点集合，e 为边的集合，s 为所有可能成为s t e i n e r 节点的节点集，d 对应多播问题的组成员，o ns = 中， v = o u s 。 定义2 2 t = ( v t ，e v ) 表示覆盖节点集合d 的棵生成树，d v t v ， e t e 。 定义2 3 c i j 表示边( i ，j ) e e 的费用，c o e r + ，v ( i ，j ) e e 。 定义2 4 d i ，表示节点i 到节点j 的最短路费用，即节点i 到节点j 距离。 定义2 5 d ( i ，t ) = m i n d j ：j c v t 表示树t 外节点i 到树t = ( v t ，e t ) 的距离， 称节点i 为树t 中距离节点i 最近的节点，如果节点j 满足下面条件，对树 中任意节点k 有不等式d i sd + 成立。 定义2 ，6c t 表示在求解s t e i n e r 树问题时，用启发式算法得到的树t 的 费用，c 。，表示对应的最优树的费用。 下i 面简单介绍几种最常见的s t e i n e r 树问题的启发式算法 2 2 1k m b 算法 k m b 算法”在有些文献中又被称为d n h 算法，它是有关s t e i n e r 树最 著名的1 个算法。它用到了距离完全图和最小生成树算法。 1 ) 构造图g 的距离完全图g s = ( q ，e * ) ，其中v ( u ，v ) e e 是图g 中二肖 点u 到节点v 的最短路径，即边( u ，v ) e e + 的费用等于g 中节点u 到节点v 的最短路的费用； 2 ) 构造图g 的最小生成树t ； 3 ) 将t 中的边再转换为g 中的最短路径，形成子图g 。； 4 ) 求出g 。的最小生成树t s ； 5 ) 删除t ；中非基本节点的叶子节点，最后得到所求的树t ： k m b 算法的复杂度为o ( i q l l v l 2 ) ，平均性能较好，为最优解费用的1 0 5 。 2 2 2m p h ( s h o r t e s tp a t hh e u r i s t i c ) m p t f 算法”6 1 的基本思想是选择树外所有目的节点中选择距离树最近的 那个目的节点通过最短