（计算机应用技术专业论文）通信网络中qos多播路由算法研究.pdf

醅 一 l 独创性声明 r 删n , , t 7 8 7 7 7 6 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：辈应旌日期：礁蜂巫丝 、关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：雄之趣导师签名：驾姓日期：丝堡垒塑! 卵 。， 护 摘要 摘要 随着i n t e m e t 的发展，多媒体通信和分布式环境下的协同工作等应用促使 了多播通信的发展。多播问题的关键在于多播路由的确定，即寻找简单、高效、 健壮的多播路由算法，多播路由算法主要是用来建立一棵性能良好的多播树， 并使它能够满足各种业务的服务质量( q u a l i t yo f s e r v i c e ，q o s ) 需求，由于q o s 多播路由带有多个q o s 约束参数，而这种多约束条件下的q o s 多播路由问题 属于n p 完全问题。对于q o s 多播路由问题的研究大多都集中在采用启发式 算法求解无约束多播路由问题和时延受限多播路由优化问题，然而由于这些算 法都具有较高的时间复杂度而不能满足实际应用的需要。 本文给出了多约束q o s 多播路由的问题模型，分析论述了多约束q o s 多播 路由优化的约束树算法。重点分析讨论了遗传算法基本原理、实现步骤，算法 的优势和局限性。标准的遗传算法有两个严重缺点，即过早收敛以及在进化后 期搜索效率较低，这使得最终搜索得到的往往不是全局最优解，而是局部最优 解。本文在分析这两个缺点产生原因的基础上，结合模拟退火算法局部搜索能 力强的优点，提出了既能加快进化速度，又能抗早熟的遗传模拟退火算法。该 方法针对遗传算法的局限性，采用基于备选路径集的整数队列编码机制，对适 应度函数进行了调整，改进了交叉和变异操作，结合了模拟退火算法。该算法 充分利用了遗传算法和模拟退火算法的优点，克服了遗传算法在求解多q o s 约 束多播路由问题中的爬山能力差以及不成熟收敛等问题。仿真实验结果表明，该 算法为多q o s 约束多播路由问题的求解提供了一种有效的新途径。最后对q o s 约束的多播路由技术的进一步研究进行了展望。 关键词多播路由；q o s ；遗传模拟退火算法 北京t 业人学t 学硕十学位论文 i i - a b s t r a c t a b s t r a c t w i t ht h e d e v e l o p m e n to fi n t e m e t ，t h er e c e n te m e r g e n c eo fm u l t i m e d i a c o m m u n i c a t i o n sa n dc o o p e r a t i v ew o r k si nd i s t r i b u t e de n v i r o n m e n t sp r o v i d e sa n i n c e n t i v et os y s t e md e s i g n e r s t oi n c l u d em u l t i c a s tc o m m u n i c a t i o ns u p p o r tf o rt h e s e a p p l i c a t i o n s af u n d a m e n t a li s s u ei n m u l t i c a s tc o m m u n i c a t i o ni sh o wt od e t e r m i n ea n e f f i c i e n tm u l t i c a s tr o u t i n g ，n a m e l yi ns e a r c h o fs i m p l e ，e f f e c t i v ea n dr o b u s tm u l t i c a s t r o u t i n ga l g o r i t h m s m u l t i c a s tr o u t i n ga l g o r i t h m sa r e u s e dt oc o m p u t em u l t i c a s tt r e e s t h a ts a t i s f yq u a l i t yo fs e r v i c er e q u i r e m e n t t h ep r o b l e mi n s e a r c ho fm u l t i c a s tr o u t i n g w i t hq o sc o n s t r a i n e di san p - c o m p l e t ep r o b l e m m o s tp r e v i o u sr e s e a r c h e r sh a v e f o c u s e do n d e v e l o p i n g h e u r i s t i c a l g o r i t h m s t o s o l v eu n c o n s t r a i n e da n d d 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 gp r o b l e m h o w e v e r , t h es e h e u r i s t i ca l g o r i t h m s h a v eh i 。g hc o m p u t a t i o nc o m p l e x i t y ，s ot h e ya r en o tf i ti np r a c t i c a l i t y i nt h i sp a p e r , t h ep r o b l e mm o d e lo fq o sm u l t i c a s tr o u t i n gi sp r e s e n t e d ，a n dt h e p a p e rp r e s e n t ss o m et y p i c a lm u l t i c a s tr o u t i n ga l g o r i t h m s t h ep a p e rd i s c u s s e dt h e b a s i cp r i n c i p l e ，r e a l i z a t i o n s t e p ，t h es u p e r i o r i t ya n dt h e l i m i t a t i o no fg e n e t i c a l g o r i t h m t h es t a n d a r dg e n e t i ca l g o r i t h mh a st w oc r i t i c a ld e f e c t s ，n a m e l yp r e m a t u r e r e s t r a i n i n ga sw e l la sl a t e rp e r i o ds e a r c h e st h ee f f i c i e n c yi nt h ee v o l u t i o nt ob el o w , t h i sc a u s e st h er e s u l tt ob eo b t a i n e df i n a l l yi sn o tt h ef u l l s c a l eo p t i m a ls o l u t i o n ，b u t t h ep a r t i a lo p t i m a ls o l u t i o n t h i sa r t i c l e a n a l y z e si nt h er e a s o nf o u n d a t i o nw h i c h t h e s et w os h o r t c o m i n g s ，c o m b i n e st h em e r i ti np a r t i a ls e a r c ha b i l i t yo fs i m u l a t i o n a n n e a l i n ga l g o r i t h m ，p r o p o s e da l g o r i t h ms i m u l a t e da n n e a l i n ga l g o r i t h mw h i c hc a n s p e e du pt h ee v o l u t i o n a r yr a t e ，a n da v o i dt h ea n t i - p r e c o c i t y i nt h ea l g o r i t h m ，a i m i n g a tt h el i m i t a t i o no f g e n e t i ca l g o r i t h m ，i n t e g r a ls e q u e n c ee n c o d i n gm e t h o db a s e do n t h ep r e p a r a t i v ep a t h ss e ti sa d o p t e d ，a n dt h ef i t n e s sf u n c t i o ni sa d j u s t e d t h ec r o s s a n dm u t a t i o nm e t h o di si m p r o v e d ，a n ds i m u l a t e da n n e a l i n ga l g o r i t h mi sc o m b i n e d w i t h t h i sa l g o r i t h mt o o ka d v a n t a g eo fg aa n ds a ，a n do v e r c a m et h es h o r t c o m i n g s o fg ai ns o l v i n gt h em u l t i c a s tr o u t i n gpr o b l e mw i t hm u l t i p l eq o s c o n s t r a i n t s p o o r c l i m b i n ga b i l i t ya n di m m a t u r ec o n v e r - g e n c e t h ep r o p o s e da l g o r i t h me n h a n c e sn o t o n l yg l o b a ls e a r c ha b i l i t yb u ta l s oc o n v e r g e n c es p e e d 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 mi sa ne f f e c t i v ea p pr o a c ht om u l t i c a s tr o u t i n gd e c i s i o nw i t hm u l t i p l e q o sc o n s t r a i n t s f i n a l l y , i tp u t sf o r w a r ds o m es 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 k e y w o r d sm u l t i c a s tr o u t i n g ；q o s ；g e n e t i cs i m u l a t e da n n e a l i n ga l g o r i t h m - i j 北京t 业大学t 学硕上学位论文 i v - 二 ； 目录 目录 摘要。i a b s t r a c t i i i 第1 章绪论。1 1 1 研究背景1 1 2 多播路由算法分类2 1 3 多播路由技术的研究现状3 1 4 主要研究内容和论文结构安排4 第2 章多播树理论基础与算法7 2 1q o s 约束7 2 2q o s 多播路由网络模型定义一8 2 3q o s 多播路由算法9 2 3 1s t e i n e r 问题9 2 3 2 多播路由算法简介9 2 4 随机网络产生模型1 2 2 5 本章小结1 3 第3 章遗传算法分析与改进1 5 3 1 生物进化理论和遗传学的基本知识1 5 3 2 遗传算法介绍1 7 3 2 1 遗传算法的基本思想1 7 3 2 2 遗传算法的特点一1 7 3 3 遗传算法的基本操作1 9 3 3 1 参数编码一1 9 3 3 2 初始群体设定1 9 3 3 3 个体适应度评价1 9 3 3 4 选择算子2 0 3 3 5 交叉算子2 1 3 3 6 变异算子2 3 3 4 遗传算法的实现步骤2 4 3 5 遗传算法的参数选择2 5 3 6 遗传算法的性能评估指标2 6 3 7 遗传算法的问题与不足2 6 3 8 遗传算法的改进2 7 3 9 本章小结2 7 第4 章遗传模拟退火算法在q o s 多播路由中的应用一2 9 4 1 模拟退火算法2 9 4 1 1 模拟退火算法简介2 9 4 1 2 模拟退火算法的特点3 1 4 1 3 模拟退火算法实现的技术问题3 1 4 1 4 模拟退火算法参数实际选择3 1 4 2 遗传算法和模拟退火算法的结合3 2 v 北京t 业大学t 学硕 ：学位论文 4 2 1 遗传算法和模拟退火算法相结合的出发点一3 2 4 2 2 遗传模拟退火算法的特点3 3 4 2 - 3 模拟退火算法的实现步骤3 3 4 2 4 遗传模拟退火算法的实现步骤3 4 4 3 基于遗传模拟退火算法的q o s 多播路由优化3 5 4 3 1 初始群体的构建和编码3 5 4 3 2 适应度函数3 7 4 3 3 遗传参数的设计。3 8 4 3 4 模拟退火参数的设计4 1 4 3 5 算法终止准则4 2 4 4 算法分析和仿真结果4 2 4 4 1 算法分析4 2 4 4 2 实验研究及仿真结果4 3 4 5 本章小结4 5 结论4 7 参考文献4 9 攻读硕士学位期间所发表的学术论文一5 3 致 射5 5 一? 第l 章绪论 1 1 研究背景 第1 章绪论 随着网络技术的发展和i n t e m e t 的迅速普及，网络正以前所未有的速度发 展，网络规模进一步扩大，网络信息流量迅速增加，从而网络将变得更加拥挤， 这将严重影响网络的传输速率。随着网络应用的进一步扩展，各种多媒体业务， 如音频视频会议、远程教学、i p 电话、交互式仿真、网络游戏等，它们都依赖 于从一个主机向多个主机或者从多个主机向多个主机发送同一信息的能力，而在 i n t e m e t 上分发信息的主机的数目可能达数十万台，发送信息需要更高的带宽。 若采用传统的点到点单播通信方式或广播方式己无法满足当前网络信息传输的 要求，不仅浪费大量的网络带宽，而且效率很低。多播( m u l t i c a s t ) 正是针对此类 问题提出的一种新的、高效的网络传输方案，它是面向“组”的介于单播和广播通 信之间的数据传送方式。路f l 了( r o u t i n g ) 是计算机网络核心层的主要功能，也是决 定网络传输性能的主要因素之一。为了准确、有效地将信息送到多播组，必须为 它们确定路由，信息按选择的路由进行传送。因此，作为多播通信的重要组成部 分和鱼待解决的关键问题，寻找简单、高效、健壮的多播路由算法一直是网络界 致力研究但未完全解决的问题。与单播路由不同的是，多播路由的目标是寻找一 系列从源节点出发并最终到达所有目的节点的路径，因此多播路由也比单播路由 复杂许多。目前实现多播通信最有效的一种方式就是构造多播树( m u l t i c a s tt r e e ) 。 多播树就是覆盖所有多播组成员的一棵生成树。所以，多播路由算法就是研究如 何在网络中建立一棵多播树。 网络的快速发展要求当前网络既能传送常规的“尽力传输( b e s t e f f o r t ) ”服务 ( j t l ：e m a i l 、邱等) ，也能传送有一定服务质量( q u a l i t yo fs e r v i e e ，q o s ) 要求的实 时多媒体业务。而传统的尽力传输路由只关心网络的平均性能，各种数据流在网 络中平等地分享网络资源且能沿多条路径传输，仅有这种特性的路由技术不能满 足有q o s 要求的实时多媒体业务传送的需要。因此，q o s 约束的多播路由算法 的研究逐步发展起来。简单地说，基于q o s 约束的多播路由是通过发现具有某 种相关性能约束的最佳多播树，来更好地利用网络资源以支持应用的q o s 需求。 它是以q o s 为中心的网络体系结构中不可缺少的组成部分，己成为网络研究领 域的重要内容和热点问题。 众所周知，在多播路由中提供q o s 保障是很困难的，原因是： 首先，许多分布式的多媒体应用，诸如电视会议、视频点播、i p 电话和基 于w e b 的应用等对时延、时延抖动、带宽以及包丢失率有不同的要求。多个q o s 约束通常使多播路由很难实现。已经证明：存在多个不相关可加度量的q o s 多 北京工业大学t 学硕：t z 学位论文 播路由问题是一个n p 完全问题。n p 完全问题是当前数学界尚未解决的数学难 题，可见q o s 多播路由技术研究的难度。 当路由算法被多播路由协议采纳后，又存在许多实际问题。例如，状念集合 的更新、动态拓扑结构的处理与成员变化、树的维护与可扩展性问题等。所以， q o s 的要求使得协议设计过程更加复杂化。 此外，必须考虑如何用最小的代价收集维护与q o s 相关的状态，如何在集 合的非精确状态信息下构建一棵满足q o s 的路由树，如何维护路由域之间的q o s 在占 号宇。 研究基于i n t e m e t 的q o s 多播路由算法，以获得较好的网络服务质量和高的 网络资源利用率，为将来多播通信服务实施具体应用奠定基础，对于我国计算机 网络技术和其他相关领域的发展具有重要的战略意义。通过追踪世界上网络研究 的前沿领域，开展这一领域的研究工作，将具有一定的理论价值和广泛的应用前 景。 1 2 多播路由算法分类 多播路由算法按其实现方式可分为集中式源路由和分布式路由，它们各有优 缺点： 1 集中式源路由 集中式源路由采用集中处理的方式，因此在发出路由请求时，可以立即获得 预先存在的路由信息，无需在网络的各个节点之间进行信息交换。但它需要在网 络中每个节点上都维持一张有关整个网络全局链路状态的“图”；另外，经过源路 由计算的路径是不含回路的。源路由是一种简单、明了、易于实施、评估、检查 和升级维护的路由计算方法。与设计、解决属于n p 完全问题的分布式路由启发 式算法相比，其实施是非常容易的。但基于源路由的路由算法也存在一些问题， 即：( 1 ) 为维持整个网络通信链路的状态信息，必须进行高频率的状态刷新，给 网络造成了负载；( 2 ) 由于不可避免地存在着刷新延迟，因此存在着状态信息滞 后的问题。 2 分布式路由算法 在分布式路由中，路径计算是激励式的，即当有路由请求时，它不会马上获 得到路由信息，需要一个路径搜索延迟。但是，该类路由选择和优化都是基于局 部状态信息的，不需要像源路由那样为网络所有节点都维持一张链路状态表。因 此，分布式路由算法能够很好地适应网络规模，但计算复杂度比较高。同时，在 多方向上并行搜索多个可行路径，增加了搜索的成功率。但是当链路状态信息、 由于广播延迟而造成不同节点的有关链路状态不一致时，回路就会发生，从而增 加了网络带宽的消耗。 第1 章绪论 多播路由算法按多播组成员是否变化又可分为静态和动态多播路由算法。静 态多播路由算法针对初始多播组成员构造一棵多播树，它不能够根据当前组成员 的加入或离开来调整路由，而是按初始设计好的路径传送，它的路由修改需经过 一定时间的运行后进行；动态多播路由算法可以针对组成员的加入或离开适时的 进行多播树的更新，但若动态算法对路由的频繁修正，将会引起通信的不稳定。 目前q o s 多播路由问题是国内外研究的一个热点问题，由于传统i p 网络最初 是为数据传输而设计的，其通信模式采用点对点方式，是为保证数据可靠传输而 设计的，其采用的传输协议多为点到点的协议，这样就增加了网络发送负载，带 来网络延时，由此也带来了带宽的急剧消耗和网络拥挤问题。 1 3 多播路由技术的研究现状 传统的口网络对各种业务一律平等，不能保证特殊业务的特殊要求，不能 保证服务质量( 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 约束的多播路由选择问题。目前已经证明这些问题都是n p 完全问 题，针对此类问题大多采用启发式算法。 常规的多播源路由算法有最短路径树算法( d i j k s t r a 算法【l j 和b e l l m a n f o r d 算 法【1 l 和最小生成树算法( p r i m 算法) 。最短路径算法使多播树上从源节点到目的 节点的每条路径上链路权重( w e i g h t ) 之和最小。如果所有链路的权重都为1 ，结 果树就是最小跳树。如果权重代表链路时延，则结果树就是一棵最小时延树。p d m 算法求得一棵覆盖所有组成员且树权重最小的树。算法采用的是贪婪策略，因为 在树的增长过程中，每次选择的边都是使树权重增加最少的边。 s t e i n e r 树问题研究使多播树整体代价最小，是n p 完全问题，无约束s t e i n e r 树问题可以解决多播树优化问题，但不能解决点对点的约束问题。s a l a m a 等人 在文献【2 】中对近年来的几种s t e i n e r 树问题解决方案的性能进行了评估和比较。 分布式算法本身要比集中式算法复杂得多，这方面的研究也少得多。典型的 分布式算法有b a u e r 等人提出的s p h 算法 3 1 和k s p h 算法 3 1 ，文献it 是j i a 等人 设计的另一个分布式多播路由算法，能达到近似最优的时延约束多播树。 针对q o s 多播路由问题的复杂性，引入了一些人工智能优化算法寻求最优 解。智能优化算法是解决复杂问题的一个重要途径，具有广阔的发展前景。智能 算法具有并行性、自适应性和自学习性的优点，已经在各个研究领域得到了广泛 北京t 业大学t 学硕l 学位论文 的重视，p r o c e e d i n g so f i e e e 曾多次出版智能计算专刊。目前智能优化算法的研 究主要集中在神经网络、遗传算法、模拟退火算法和禁忌搜索算法。国外有学者 提出利用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 ) 【5 j ，正交遗传算法将正交矩阵的实验设计方 法引入到遗传算法的交叉操作中，要求正交矩阵规模较大，而大的正交矩阵则增 大了计算的复杂度，因此j 下交矩阵的大小决定了算法的性能。 近代科学技术发展的特点之一是生命科学与工程科学的相互交叉、相互渗透 和相互促进。遗传算法是近些年提出的一种新的仿生型优化算法，它被广泛用于 解决各种具有n p 难度的问题。其优点是：具有大范围的全局搜索能力，鲁棒性 强，具有内在的并行性，收敛速度快。其缺点是：不能充分利用系统的反馈信息， 产生大量冗余迭代，过快收敛会陷入局部最优解问题。而一些优化算法如爬山法、 梯度法、模拟退火算法具有很强的局部搜索能力，而另一些含问题相关的启发知 识的启发式算法也有很高的运行效率，将这些优化算法的思想加以合理的融合， 形成一种混合型算法，是一种提高运行效率和求解质量的有效手段。本论文结合 模拟退火算法，对遗传算法进行改进，把优化q o s 多播的路由算法作为研究重 点。 国内也有多所大学及科研部门致力于多播技术研究，如中科院软件研究所、 哈尔滨工业大学、华中科技大学等。提出了树形编码、二进制编码等编码方案， 但仍需作进一步研究。采用智能算法来实现q o s 多播路由问题，在国内外都处 在研究阶段，因此本文的研究有着积极的意义。目前所作的工作还是初步的探讨， 但随着智能算法的不断成熟，智能算法在今后的q o s 多播路由选择以及其它领 域还是有着非常广阔的前景。 1 4 主要研究内容和论文结构安排 用智能算法来实现q o s 多播路由问题，在国内外都处在研究阶段，本文的 主要研究内容是采用遗传算法来实现q o s 多播路由算法问题。本文根据q o s 多播路由选择问题的特点，结合遗传算法的寻优特征，从不同角度对遗传算法进 行改进，旨在提高遗传算法的搜索性能，使之更有效地求解多播路由问题。 围绕这个主题，本文共分为4 章： 第1 章是绪论，介绍了q o s 多播路由问题研究背景，多播路由算法分类， 并介绍了多播路由技术的研究现状。 第2 章介绍了q o s 约束，q o s 多播路由网络模型定义，接着对q o s 多播路 第l 章绪论 由算法进行了简单介绍与分析，并介绍了仿真网络模型的构建。 第3 章讨论了遗传算法的基本思想、特点、算法的优势与劣势，描述了遗传 算法的实现步骤，本章指出了遗传算法的难点和算法存在的问题，即容易发生早 熟收敛现象。提出了结合模拟退火算法对遗传算法改进的思路，为下一章用遗传 模拟退火算法实现q o s 多播路由问题打下了理论基础。 第4 章讨论了用遗传模拟退火算法解决q o s 多播路由优化问题。本章针对 遗传算法存在过早收敛以及在进化后期搜索效率较低的缺点，结合模拟退火算法 局部搜索能力强的优点，将模拟退火与遗传算法相结合，提出了既能加快进化速 度，又能抗早熟的遗传模拟退火算法。该方法采用基于备选路径集的整数队列编 码机制，对适应度函数进行了调整，改进了交叉和变异操作，结合了模拟退火算 法，克服了遗传算法在求解多q o s 约束多播路由问题中的爬山能力差以及不成 熟收敛等问题。仿真实验证明该算法具有操作简单，全局收敛速度快和可靠性高 等优点。 最后，对本文所做的工作做了一个总结，并对q o s 组播通信路由问题的 求解进行了展望。 北京1 = 业人学t 学硕：i 二学位论文 第2 章多播树理论基础与算法 2 1o o s 约束 第2 章多播树理论基础与算法 服务质量( q u a l i t yo f s e r v i c e ，简称q o s ) ，指发送和接收信息的用户之间 以及用户与传输信息的服务网络之间关于信息传输的质量约定。q o s 包括用户 要求和网络服务提供者的行为两个方面。用户要求指用户在i n t e m e t 网络上进 行多媒体通信时所要求的服务类型以及相应的传输性能和质量，所以多媒体应用 对i p 网q o s 的要求同时体现：丢包率、传输时延、时延抖动、网络带宽等参 数描述的分组传输特性。网络要满足用户的质量要求，就必须满足用户要求的 q o s 参数。 1 q o s 主要参数 带宽( b a n d w i d t h ) ：单位时间内传送的i p 包数量。多媒体业务的数据传 输量往往较大，因此需要网络为其分配最小带宽。 延时( d e l a y ) ：指i p 包从发送到接收之问的时间间隔。它包括终端设备 的编码解码时间，口包在传播介质的传播时间，i p 包在交换机或路由器中被处 理的时间，以及口包在交换机或路由器的等待队列中的排队时间。 延时抖动( j i t t e r ) ：即延时变化( d e l a yv a r i a t i o n ) 。当i p 包到达交换设备时， 如果等待队列中没有别的i p 包，则它将以固定延时被转发出去。但是，如果等 待队列中还有别的包，则它可能就需要等待，这时i p 包被交换的延时就等于固 定延时加上在队列中等待的时问。以上两种情况下延时的变化程度就是延时抖 动。 包丢失率( p a c k e tl o s sr a t e ) ：是指特定的时间段丢失的包占传输包的总数 的比例。 丢包主要是由于网络拥塞引起的。 2 q o s 度量 对于路径p = 向色c 矽，用讹矽表示对应链路向砂的度量，则q o s 度 量可以按性质分为以下三类： ( 1 ) 凸性q o s 度量 如果d ( a , g ) = m i n d ( a , b ) ，舱砂d o f , g ) j ，那么度量由传输通道中瓶颈决定， 即此度量定，如时延、时延抖动、费用等。 ( 2 ) 加性q o s 度量 如果嘏砂= 讹矽+ m 砂十俐，那么度量由传输通道中所有链路的特性 共同决定，如时延、时延抖动、费用等。 ( 3 ) 乘性q o s 度量 北京t 业人学工学硕卜学位论文 如果嘏矽= 嘏剀材陋砂木d ( f g ) ，即度量为所有链路对应度量的乘积，如 可靠性等。如取讹缈= 锄磁红叨，则乘性度量就转化为加性度量。 因此，按度量的性质q o s 路由可归结为基本的两大类：路径优化问题，对 应加性q o s 度量；链路优化问题，对应凸性q o s 度量。 2 20 0 s 多播路由网络模型定义 通常将q o s 多播路由问题描述为一个加权图g = e ) ，其中v 表示节点 集，e 表示节点问的通信链路集，l v l 和f 剧分别为节点数和链路数。s ( s 功表示 il 多播的源节点，m 表示目的节点集f ，mcv - 盘。r + 为正实数集，r 为非负实 数集。对于任意的节点，定义3 个q o s 特征值，即v i = ( n 砖t a y , nl o s s , nj i t t e r ) ， 其中nd e l a y ( v o ：v - - , r + 表示节点的延时；n 表示节点的包丢失率；10ss(vo：v-)r+ n j i t t e r ( v o ：v - * r + 表示节点的延时抖动。对于任意的链路岛，定义三个q o s 特征值， 即e i = 以c o s t ，b a n d w i d t h ，z 础l a y ) ，其中，c o s t ( e o ：e 一r + 表示传输费用； ，b a n d w i d t h 忙砂? e _ r + 表示传输带宽；，d e l a y ( e 砂? e _ r + 表示传输延时。 对于给定的源点s k 目的节点集m ，s 和m 组成的多播树矾m ) 存在 关系见式( 2 1 ) 、( 2 2 ) 、( 2 3 ) 、 ( 2 - 4 ) 、 ( 2 5 ) 。 a e t a y ( p ( s , t ) ) ：l _ d e l a y ( e ) + 啦伽俐 ( 2 1 ) e e p ( s , t ) v p ( s , o c o s t ( r ( s , m ) ) = l _ c o s t ( e ) + lc o s t ( n ) ( 2 2 ) e 皂p f s 哟n e p ( s 鹕 b a n d w i d t h o ，( s , 砂) 刊切帅a n d w i d t h ( e ) ，e 向砂)( 2 3 ) 如纫o f 抛，囟向纱：，z j i t t e r ( e ) + 甩一j i t t e r ( n ) ( 2 4 ) e e p ( s ，f )n p ( s ，) p a c k e t l o s s ( p ( s , 缈21 。il ( j 一刀一l o s s ( v )( 2 - 5 ) 其中p ( s , o 为多播树蚴上源节点s 到目的节点f 的路径。 实际上，q o s 多播路由问题就是要寻找一棵多播树确蚴，使之满足式( 2 6 ) 、 ( 2 7 ) 、( 2 - 8 ) 、( 2 9 ) 的q o s 约束，且使c o s t ( t ( s , m ) ) 最小。 延时约束：d e l a y ( p ( s , 圳三d( 2 6 ) 带宽约束：b a n d w i d t h ( p ( s , 圳扭 ( 2 。7 ) 延时抖动约束：d e l a y _ j i t t e r ( p ( s , 圳盟v( 2 8 ) 包丢失率约束：p a c k e t _ l o s s ( p ( s , 圳吼 ( 2 - 9 ) 其中，d 为延时约束，曰为带宽约束，d j 和儿分别为延时抖动和包丢失率 8 第2 章多播树理论基础与算法 约束。在上述q o s 特征值中，延时和延时抖动是可加性的，带宽是极值性的， 包丢失率是乘积性的，它们之间既有联系又有区别。 2 3o o s 多播路由算法 2 3 1s t ein e t 问题 对于多播路由问题，一般要建立费用最小树，而最优s t e i n e r 树的费用是最 小的，因此s t e i n e r 树被认为是实现多播通信的最好办法之一。s t e i n e r 树理论及 其算法也成为求解多播树的基础。 计算机通信网一般用无向图g 形习表示v ( v j ，v 2 ，如，) 是图g 的节 点集，e 为图g 的边集，z = i 吲为图g 的节点数，i e l 为图g 的边数或链路数，每 条链路e ( j 9 的链路费用为c 俐，d = a ，如如，如) 表示目的节点集；s 为 所有可能成为s t e i n e r 节点的节点集，q 对应多播问题的组成员， q n s = q 肛pu s 。s t e i n e r 树多播路由算法定义为从图g 中找出覆盖d 中所有节 点的最小生成树t ，即使得树的费用c 仞= m i ny c 伍廖最小，该最小生成树称为 南昌 s t e i n e r 树。 d = v 情况下，s t e i n e r 问题就简化为求图的最小生成树的问题，其时间复杂 度为o ( n 2 ) 。当l d i = 2 时，s t e i n e r 问题又简化为求两节点间的最短路径问题，也 可以在多项式时问复杂度o ( n 2 ) 内解决。除此之外，求s t e i n e r 树问题是n p 完全 问题。 2 3 2 多播路由算法简介 对s t e i n e r 树问题一般讨论解它的启发式算法。因为精确计算最优多播树需 要使用枚举的方式，其计算量随网络节点的增加而指数增加，在网络规模较大时， 寻找一棵s t e i n e r 树需要很长的时间，因此确定式算法不适用于网络多播应用。 启发式算法并不保证给出最优解，那么如何评价启发式算法的好坏呢? 主要是基 于两个方面的考虑：首先是时间复杂性方面的要求；其次是性能方面的要求， 即希望所求的近似解尽可能“接近”最优解。 下面简单介绍几种最常见的s t e i n e r 树问题的启发式算法。 1 最短路径算法 最短路径算法是由s u n 和l a n g e n d o e r f e r 首先提出的，基本思想是在多播树 上从源节点到目的节点的每条路径上链路权值之和最小，而且满足端到端的延迟 北京t 业大学t 学硕十学位论文 约束。若所有链路的权值均为1 ，则算法所获得的多播树即为最小跳树：若权值代 表链路时延，则算法将获得一棵最小时延树。b e l l m a n f o r d 算法【l 】和d i j k s t r a 算 法【l 】是两个最著名的最短路径算法，其时间复杂度分别为d 神和d 伽刁。最短路 径算法是搜索最短路径的常用算法，如果存在满足约束的多播树，则该算法总可 以发现约束最短路径。 2 最小生成树算法 一棵最小生成树是包含了多播源点和所有多播终点且权值最小的一棵树。最 有名的集中式最小生成树算法是普里姆( p r i m ) 算法【l 】，g a l l a g e r 等提出了一种 分布式算法1 6 1 。普里姆算法的基本思想是：在网络中任选一个节点v 0 作为树根， 从v 0 开始，连接与v o 相连的、边权值最小的节点v 1 ，得到子树乃，再以上述 规则连接乃与网络中不在乃中的节点，如此继续下去，直到所有节点都用到 为止。最小生成树算法可以用来解决树优化问题。 3 s t e i n e r 树算法 所谓s t e i n e r 树，是指给定某个度量空间中的一个点集，求解将这些点互联 的最短网络。斯坦利( s t e i n e r ) 树问题以最小化多播树的总代价为目标，是n p 完全问题【_ 7 】【8 】。如果多播组包含了网络中的所有节点，则斯坦利树问题就简化为 最小生成树问题。不受限斯坦利树算法可以用来解决树优化问题，但不能用来解 决有q o s 约束的树受限问题。w i n t e r l 9 1 和h w a n g 1 0 】对启发式斯坦利树算法进行 了总结。 k o u ，m a r k o w s k i 和b e r m a n 提出了一种求解斯坦利树的启发式算法【l1 1 。 k m b 算法先定义一个距离完全图。所谓距离完全图是包含了网络中所有节点的 完全图，且用每对节点之间的边表示它们之间的最短路径。设从最初的网络拓扑 图g 创建出的距离完全图为矾首先用普里姆最小生成树算法得到日图的最 小生成树u ；再把u 中的每条边用相应的最短路径替换，从而得到连通子图n 然后对v 运用最小生成树算法得到一个生成树丁；最后，反复修剪丁中的非 多播叶子节点，从而得到一棵多播树。此外，t a k a h a s h i 提出了一种启发式算法 【1 2 】，b a u e r 和v e r m a 提出了一种分布式算法来求解斯坦利树问题【1 3 1 。 4 约束s t e i n e r 树算法 在进行树优化的多播路由中加入不同的q o s 约束( 例如带宽、时延、时延抖 动或者它们的组合) ，则s t e i n e r 树问题就扩展为基于q o s 约束的s t e i n e r 树问题。 由于这些问题也是n p 完全问题，目前研究较多的是采用启发式算法。基本的算 法思想为：在集中式或分布式网络模型中采用基于不同最短路径算法计算最小代 价，如d i j k s t r a 、b e l