（通信与信息系统专业论文）基于多约束qos的ip组播路由算法研究.pdf

武汉理工大学硕士学位论文 摘要 进入2 1 世纪以来，计算机网络技术得到了飞速发展，各种宽带网络应用层 出不穷。p t v 、视频会议、远程教学、网络游戏、数据资料分发等宽带应用都 对现有网络的承载能力提出了挑战，这就使得组播通信方式成为网络支持多媒 体业务的必要形式。与此同时，这些分布式的多媒体应用对带宽、时延、时延 抖动以及丢包率有不同的要求，这需要当前网络能够传送具有这些q o s 要求的 实时多媒体信息。因此，基于多约束q o s 的组播路由算法的研究成为计算机网 络研究领域的重要内容和热点问题。 本文主要研究基于多约束q o s 的组播路由算法，针对带宽、延迟、抖动和 丢包率等约束的最小代价组播路由问题，提出了一种高效、实用的组播路由算 法。主要研究工作和取得的成果如下： ( 1 ) 在介绍组播路由技术相关背景知识的基础上，研究了q o s 路由的基本 概念和网络模型，归纳分析了当今主要的相关算法以及各自优缺点； ( 2 ) 提出了一种将蚁群算法和遗传模拟退火算法相结合的混合优化算法 ( a c o g s a ，a n tc o l o n y o p t i m i z a t i o n a n dg e n e t i cs i m u l a t e d a n n e a l i n g a l g o r i t h m ) ，采用基于蚁群算法创建的备选路径集编码方式，大大提高了编码效 率；在组播路由算法设计中将遗传算法与模拟退火方法相结合，克服了遗传算 法“过早收敛”问题和模拟退火算法优化时间性能较差的缺点，并引入变异退 火算子和含浓度均衡措施的选择复制算子，使得算法性能进一步增强； ( 3 ) 改进了s a l a r n a 网络拓扑生成器，对提出的算法进行仿真，并与传统算 法就收敛性和运行时间上进行比较，仿真结果表明算法的可行性、有效性和稳 定性，并验证了算法具有代价低、收敛迅速的特点。 关键词：q o s 组播路由；蚁群算法；遗传模拟退火；备选路径集编码 武汉理工大学硕士学位论文 a b s t r a c t s i n c ee n t e r i n gt h e21s tc e n t u r y ，c o m p u t e rn e t w o r kt e c h n o l o g yh a se n j o y e d r a p i d d e v e l o p m e n ta n d t h ea p p l i c a t i o no fa v a r i e t yo fn e t w o r k se m e r g e do n eb yo n e p t v ，v i d e oc o n f e r e n c i n g ，d i s t a n c el e a r n i n g ，o n l i n eg a m e s ，s u c ha sb r o a d b a n d d a t aa p p l i c a t i o n sp o s eac h a l l e n g eo nt h ec a r r y i n gc a p a c i t yo fe x i s t i n gn e t w o r k s ， m a k i n gm u l f i c a s tc o m m u n i c a t i o nn e t w o r kt os u p p o r tm u l t i m e d i as e r v i c e sb e c o m e n e c e s s a r yf o r m s a tt h es a m et i m e ，t h ed i s t r i b u t e dm u l t i m e d i aa p p l i c a t i o n so n b a n d w i d t h ，d e l a y ，d e l a yj i t t e ra n dp a c k e tl o s sr a t eh a sd i f f e r e n tr e q u i r e m e n t s ，w h i c h n e e dt h ec u r r e n tn e t w o r kb ea b l et os e n dt h e s er e a l t i m em u l t i m e d i ai n f o r m a t i o n m e e t t i n gt h er e q u i r m e n to fq o s t h e r e f o r e ，b a s e do nt h em u l t i c o n s t r a i n e dm u l t i c a s t q o sr o u t i n ga l g o r i t h mf o rc o m p u t e rn e t w o r k sb e c o m ea ni m p o r t a n tf i e l do fr e s e a r c h a n dh o tt o p i c s i nt h i sp a p e r , b a s e do nt h em u l t i c o n s 仃a i n e dm u l t i c a s tq o s r o u t i n ga l g o r i t h mf o r b a n d w i d t h ，d e l a y ，j i t t e ra n dp a c k e tl o s sr a t eb o u n do ft h em i n i m u mc o s tm u l t i c a s t r o u t i n gp r o b l e m ，ah i g h l ye f f i c i e n ta n dp r a c t i c a la l g o r i t h mf o rm u l t i c a s tr o u t i n g t h e m a i nr e s e a r c hw o r ka n dr e s u l t sa c h i e v e da r ea sf o l l o w s ： ( 1 ) i n t r o d u c em u l t i c a s tr o u t i n gt e c h n o l o g yo nt h eb a s i so fb a c k g r o u n d k n o w l e d g et os t u d yt h eb a s i cc o n c e p t so fq o sr o u t i n ga n dn e t w o r km o d e l ，i n t oa n a n a l y s i so ft h er e l e v a n c eo ft o d a y sm a j o ra l g o r i t h ma n dt h e i rr e s p e c t i v ea d v a n t a g e s a n dd i s a d v a n t a g e s ( 2 ) a na n tc o l o n ya l g o r i t h mt os i m u l a t e da n n e a l i n ga n dg e n e t i ca l g o r i t h m o p t i m i z a t i o na l g o r i t h mt h a tc o m b i n e s ( a c o g s a ) ，a n tc o l o n ya l g o r i t h mb a s e do nt h e p a t ht oc r e a t eb a c k u p p a t h # s e t , g r e a t l yi m p r o v et h ec o d i n ge f f i c i e n c y ；a tm u l t i c a s t r o u t i n ga l g o r i t h md e s i g nw i l lb es i m u l a t e da n n e a l i n ga n dg e n e t i ca l g o r i t h mm e t h o d o fc o m b i n i n gt h e g e n e t i ca l g o r i t h mt oo v e r c o m et h e ”p r e m a t u r ec o n v e r g e n c e ” p r o b l e ma n dt h es i m u l a t e da n n e a l i n ga l g o r i t h mt oo p t i m i z et h ep e r f o r m a n c eo fl e s s t i m ed i s a d v a n t a g e ，a n dt h ei n t r o d u c t i o no fm u t a t i o no p e r a t o r sa n dw i t ha n n e a l i n gt h e 武汉理工大学硕士学位论文 c o n c e n t r a t i o no fb a l a n c e dm e a s u r e st os e l e c tt h ec o p yc o u n ts o n ，m a k i n gf u r t h e r e n h a n c et h ea l g o r i t h mp e r f o r m a n c e ( 3 ) i m p r o v e dn e t w o r kt o p o l o g yg e n e r a t o rs a l a m a , t h ep r o p o s e ds i m u l a t i o n a l g o r i t h m ，a n d 谢mt h et r a d i t i o n a la l g o r i t h mo nt h ec o n v e r g e n c ea n dc o m p a r i s o no n r u n n i n gt i m e ，s i m u l a t i o nr e s u l t ss h o wt h ef e a s i b i l i t yo fa l g o r i t h m s ，t h ee f f e c t i v e n e s s a n ds t a b i l i t ya n ds h o wt h a tt h e a l g o r i t h m 谢t hl o wc o s t ，r a p i dc o n v e r g e n c e c h a r a c t e r i s t i c s k e yw o r d s ：q o s ；m u t i c a s tr o u t i n g ；a n tc o l o n yo p t i m i z a t i o n ； g e n e t i ca 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 m ；b a c k u pp a t hs e te n c o d i n g 一 i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名： 日期：啦 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生c 签鼽乇r 喃导师c 签孙 日期 p 。s 。 f 武汉理工大学硕士学位论文 第1 章绪论 1 1 课题研究的目的和意义 近年来，随着个人计算机的普及和计算机网络的高速发展，上网已经成 为人们日常生活中不可缺少的组成部分，各个企业及大多数家庭都建立了先 进的网络，人们能够方便地在网络上畅游，利用计算机网络进行通信或者获 取自己需要的信息资源。网络也成为了人们获取信息最便捷的途径，有时我 们工作中所需要的重要信息在网上能够很快地找到，这也大大提高了工作效 率。在家中我们可以足不出户就与远方的亲戚朋友聊天、玩网络游戏、看在 线电影甚至购物。可见，无论在工作中和生活中计算机网络都扮演着至关重 要的角色。 因特网是全世界最大的公用网络，连接全世界各个大学、企业、组织、 政府机关以及亿万个家庭。而随着宽带技术的发展，诸如交互性网络游戏、 在线音频视频电播、网络视频会议、远程教学等新兴的宽带网络应用越来越 受欢迎，有时甚至很必需。这些应用涉及到点对点或者点对多点的通信。随 着这些应用的迅速发展、网络规模的不断大，网络信息流量迅速增加，网络 也将变得更加拥挤，这将严重影响网络的传输效率。虽然可以采用传统的点 到点单播通信实现点对多点通信，但效率极低。因为随着接收者的增多，需 要发送的数据包呈线性增长，对于n 个接受者需要发送同一个数据包的n 份 拷贝，这样通信量会成倍增加，也会占用网络的许多带宽，有时会引起网络 堵塞。而采用广播方式，因为组播组的成员在不断变化，同样会浪费大量带 宽，无法满足其实时性。可见，传统的单播和广播通信方式都无法满足这些 实时应用的信息传输要求。因此，针对此问题提出了一种新的、高效的传输 方案，这就是组播【l j 。 一个组播组就是一个或者多个希望接收特定数据流的接受者或者路由器 的节点。这个组没有物理或者地理的边界，组内的主机可以位于互联网的任 意地点。组播组的每一个节点被称为组播组成员。 路由( r o u t i n g ) 是t c p i p 协议中网络层的的主要功能，主要作用是将信 武汉理工大学硕士学位论文 息按照一定的路径从源送到目的端。组播路由就是将信息准确、高效地从发 送者传送到各个组播组的成员，即接受者。寻找简单、高效、健壮的组播路 由算法是组播通信的重要组成部分，也一直是网络界致力研究但仍未完全解 决的问题。 组播路由相比单播路由要复杂许多，单播路由是寻找从源到目的端最优 的一条路径，而组播路由的目的是寻找一系列从源节点出发并最终到达所有 目的节点的路径。目前实现组播通信最有效的一种方式就是构造组播树。组 播树就是覆盖所有组播组成员的一棵生成树。因此，组播路由算法研究就是 研究如何在网络中建立一棵最优组播树。 宽带多媒体应用不仅要求交互性，而且对实时性提出了很高的要求。例 如，视频会议、交互性网络游戏等往往要求所有成员在时间上达到同步。这 就要求网络既能传送常规的“尽力而为 的服务，也能传送有一定服务质量 ( q u a l i t yo fs e r v i c e ，q o s ) 要求的实时多媒体业务【2 】。网络环境复杂多变， 如何寻找满足一定q o s 约束的最优组播树，以更好的利用网络资源以支持应 用的q o s 需求，就是基于q o s 约束的组播路由问题，这也逐渐成为了网络研 究领域的热点问题。 要寻找满足所有q o s 约束的最优组播树并不简单，原因如下： ( 1 ) 实时多媒体业务对带宽、时延、时延抖动、包丢失率、吞吐量、可靠 性和传输费用等有不同的需求，这样的具有多个不相关度量的q o s 组播路由问 题是一个n p 完全问题； ( 2 ) 路由算法最终要成为组播路由协议的一部分，因此需要考虑一些实际 的因素，如链路状态的收集与更新、网络拓扑结构和成员的变化、组播树的维 护和扩展等，最后还要加上q o s 约束，会使协议的设计变得更加复杂。 ( 3 ) 应考虑如何以最小的代价来收集或维护与q o s 相关的状态、如何利用 非精确的状态信息来构造一棵满足q o s 的组播树等等； 综上所述，对满足q o s 约束的组播路由算法的研究对网络理论和应用的发展 都有着重大的推动作用。因此，对此领域的研究有很强的理论意义和应用价值。 1 2 国内外研究现状 网络q o s 已经引起了越来越多的研究人员的兴趣，不仅如此，工业界对 2 武汉理工大学硕士学位论文 q o s 研究进展的关注程度也日益提高，有影响力的网络运行商和网络设备提 供商都提供了一定程度的q o s 支持。而新型的网络应用对q o s 的需求也日益 迫切，这些都使得q o s 正成为研究热点。总体上来说，i pq o s 的研究还没成 熟，还没有成为一个统一的标准。 路由选择算法是网络层软件的一部分，负责确定所收到数据包的输出路 径。在数据包交换网络中，路由器对收到的每个数据包都要重新做路由选择， 因为对每个数据包来说，上次到达的最佳路由可能已经改变了。路由算法必 须具有正确性、简单性、健壮性、稳定性、公平性、最佳性。q o s 路由选择 算法就是要在考虑网络拓扑、流的要求、链路资源以及网络管理员设定的策 略的情况下达到高网络吞吐率。 实现i pq o s 组播路由最普遍的方法是构造树形路由结构，寻找连接源节 点和一组目的节点的一棵树，信息可沿这棵树决定的路径进行发送。基于树 实现组播路由，信息以并行方式沿树枝发送到组成员，减少了信息传递的延 时，同时由于网络中需要传送的复制分组最少，信息的复制只在树叉处进行， 可以节省网络带宽资源，提高组播通信时的资源利用率，减少拥塞，降低网 络负载。 组播路由是一个权衡各种因素以寻找最优解的过程。已经证明，找到满 足多个约束条件的q o s 路径优化是n p 完全问题【8 1 ，n p 完全问题是当前数学 界尚未解决的数学难题，这就意味着无法在多项式的计算级别上找到最优解。 到目前为止，已有不少学者在该领域做过研究，也提出了许多组播路由算法。 因为研究的侧重点和解决的问题不同，国内外提出的组播路由算法各种各样。 组播路由算法可以根据不同的角度、不同的准则来分类。如按照是否允许网 络成员随时加入或离开组播组可以分为静态路由算法和动态路由算法，按是 否有q o s 约束可以分为无约束算法和有约束算法等等。 近年来，很多启发式智能算法已广泛应用于求解q o s 组播路由问题，例 如遗传算法、模拟退火算法等。但它们都各有优缺点。因此，不少学者将多 种算法相结合以弥补各自的不足。这类算法已成为多约束q o s 组播路由问题 的最主要的研究方向和发展趋势。 武汉理工大学硕士学位论文 1 3 本文的研究内容和组织结构 1 3 1 论文的研究内容 本文主要研究具有多q o s 约束的组播路由算法，在介绍组播路由技术背 景知识的基础上将现有的传统算法进行归纳分类，分析了当前主流的智能算 法，提出了一种基于遗传算法的混合优化算法( a c o g s a ，a n tc o l o n y o p t i m i z a t i o na n d 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 ) ，并对其进行仿真。 论文的主要研究内容为： ( 1 ) 在介绍组播路由技术背景知识的基础上，研究了q o s 组播路由的网 络模型和q o s 度量的定义，分析了当今相关经典算法特性及优缺点； ( 2 ) 研究了遗传、模拟退火和蚁群算法等在q o s 组播路由中的应用，针 对具有带宽、延时、抖动及丢包率约束的组播路由问题，提出了一种改进的 基于遗传算法的混合优化算法( a c o g s a ) ，采用备选路径集编码方式，并首次 将具有高并行性和高搜索效率的蚁群算法用于备选路径集的创建。在组播路由 算法设计中将遗传算法和模拟退火算法相结合，克服了各自的缺点，并改进变 异和选择复制算子，使算法性能进一步增强； ( 3 ) 改进了s a l a m a 拓扑生成算法，使得仿真环境更接近现实情况。研究了 m a t l a b 仿真软件，对算法进行仿真实验。仿真结果表明，本算法与传统遗传 算法相比，时间性能好，网络代价低、更为稳定可靠。 1 3 2 论文的组织结构 全文共5 章，具体内容安排如下： 第l 章，讨论组播路由技术的引入及发展背景，简要归纳总结当前国内外 组播路由算法和协议的研究成果，列出本文的主要研究内容和组织结构； 第2 章，谈论多约束q o s 组播路由的基本概念、网络模型及算法设计基 本理论，分析当前经典算法的原理、特点以及优缺点，最后介绍了几种智能 算法及在q o s 组播路由中的应用； 第3 章，全文的重点部分。提出一种基于遗传算法的混合优化算法 ( a c o g s a ) ，详细描述该算法的基本原理、设计思想和算法优越性； 第4 章，对第3 章提出的算法进行仿真实验，验证算法的收敛性，并就 编码的时间性能和算法代价性能与传统遗传算法进行比较，仿真结果表明该 4 武汉理工大学硕士学位论文 算法稳定可行，具有运行时间短、收敛快、网络代价低等特点； 第5 章，总结与展望。对论文所做的工作进行了总结，指出目前的工作中 存在的优势与不足，并对下一步的工作方向作出展望。 武汉理工大学硕士学位论文 第2 章q o s 组播路由算法概述 2 1 服务质量路由 2 1 1 服务质量概述 服务质量( q o s ，q u a l i t yo fs e r v i c e ) 的最初定义由c c i t t 给出：“q o s 是 一个综合指标，用于衡量一个服务的满意度”。q o s 是网络的一种安全机制， 是用来解决网络延迟和阻塞等问题的一种技术，其目的是向用户提供端到 端的服务质量保证。 在正常情况下，如果网络只用于特定的无时间限制的应用系统，并不需要 q o s ，比如w e b 应用，或e m a i l 设置等。但是对关键应用和多媒体应用就十分 必要。当网络过载或拥塞时，q o s 能确保重要业务量不受延迟或丢弃，同时保 证网络的高效运行。， q o s 直接表现为口数据流通过网络时的性能，可以用以下一系列可度量的 参数来描述【l o 】： ( 1 ) 带宽( b a n d w i d t h ) 带宽是网络发送数据能力的一种度量。通常在带宽足够的情况下，数据包 在网络转发设备中由于排队引起的时延会比较小。在网络中引入q o s 并不能创 造带宽，只是能够根据应用程序的需求以及网络状况来管理带宽。 ( 2 ) 延时( d e l a y ) 延时( 又称时延) 即两个参照点之间发送和接收数据包的时间间隔。包括 固定延时和可变延时。前者主要是指数据包转发和在传输链路上传播的延时， 后者主要是数据包在网络节点的队列中等待引起的延时。 ( 3 ) 抖动( j i t t e r y ) 延迟的变化称为抖动，即相邻两个数据包到达接受者的时间间隔与发送者 发送这两个数据包的时间间隔之间的差异。 ( 4 ) 丢包率( p a c k e tl o s sr a t e ) 丢包率是指在网络中传输数据包时丢弃数据包与全部数据包之比。丢包网 络中一个很严重的问题，最主要原因是节点输出队列已满，输出队列中填满了 6 武汉理工大学硕士学位论文 等待传输的数据包，没有更多空间来存储入站数据包。此外，传输错误也可能 引起数据包的丢失。 i p 网络中有两种q o s 体系结构：集成服务( i n t s e r v ) 模型和区分服务 ( d i f f s e r v ) 模型。集成服务又称为硬q o s ，是一种严格的预定服务，意味着 所有中间系统和资源都显式地为流提供预定的服务。区分服务又称为软q o s ， 它以类别为基础，将数据流进行分类，然后将它们加入到效率不同的队列中。 区分服务使用统计优先，不像集成服务那样提供严格的保证，但能够提供满 足不同q o s 需求的多种服务等级【1 1 1 。 2 1 2 服务质量路由 服务质量路由【l z j ( q o s r ，q o sr o u t i n g ) 是一种基于数据流q o s 请求和 网络可用资源进行路由的机制，它是一种动态路由协议，并且在其路径选择 标准里考虑网络可用带宽、链路和端到端路径利用率、延迟、抖动、代价等 q o s 参数。其目标是动态确定可行路径，优化资源选用并且对网络性能的影 响尽可能小。q o s 组播路由的目的是找到一棵有足够资源的可以满足应用的 q o s 需求的组播树。根据这个目标，在组播路由选择时应首先获得满足所有 应用请求所必须的路由计算信息，然后建立一条满足q o s 要求的可行路径， 即建立一棵组播树，并且维护组播树。 服务质量选路不仅关心源到宿的连通性，而且关心路由是否能够满足业 务所提出的各种服务质量要求( 比如时延约束、带宽约束、可靠性要求等) 。因 此，服务质量选路需要同时考虑业务需求和网络当前的可用资源状况，这包 括两个方面：一是网络状态信息( 比如可用资源) 的管理，涉及到选择哪些网络 状态信息来表述网络以方便于服务质量选路，如何保证网络结点保留信息的 准确性( 信息的准确性影响着服务质量选路算法的有效性) 以及状态信息的更 新等；二是利用获得的网络状态信息，使用选路算法计算相应的路由。 相对于传统的“尽力而为”的路由，服务质量路由更加复杂，它的基本 问题是在满足两个或两个以上的约束条件的基础上对某个参数或多个参数进 行优化。服务质量路由问题很难完全解决：寻找同时满足两个或两个以上的 路径约束的可行路径已被证明是一个n p c o m p l e t e 问题。此外，多种参数如 何聚集优化以及将服务质量路由融入到当前“尽力而为”的路由体系结构都 具有较大的难度。 7 武汉理工大学硕士学位论文 2 2q o s 组播路由问题的数学模型 组播路由问题从本质上讲，属于图论里的s t e i n e r 树问题【1 5 】。s t e i n e r 树是总 代价最小的分布树。这里的总代价是指树中所有边的代价之和，这里的代价是 一个广义上的代价，它可以根据距离、信道带宽、平均通信量、通信开销、队 列平均长度和其它一些因素的函数而计算出来的。s t e i n e r 树问题是从图论中引 申出来的一个优化问题，就是在网络中建立一棵以源节点为根，覆盖所有目的 节点的代价最小的生成树问题。带时延约束的组播路由问题，就是源节点到目 的节点的时延不能超过某一个时延限制的s t e i n e r 树问题。含q o s 约束的组播路 由问题，就是在s t e i n e r 树问题的基础上增加若干q o s 约束，其数学模型可以表 述如下： 把通信网看成一个有向连通图g ( v ，日，其中y 是节点的集合，e 是链路的 集合。在不改变问题本质的前提下，把节点的延时和延时抖动全部归并到它的 前趋链路中，则可以使用五个关于链路的矩阵来完整地描述通信网的参数，这 五个矩阵分别是：c o s t ( c o a ，费用) ，b ( b a n dw i d t h ，带宽) ，d ( d e l a y ， 延时) ，j ( d e l a y j i t t e r ，延时抖动) ，p ( p a c k e tl o s s ，丢包率) 。q o s 组播路由 的目的就是寻找一棵组播树，使得组播树的代价最小，同时满足以下q o s 约束： 己( 表示从源点s 到目的t 的路径) 的可用带宽不小于v 的带宽要求既； 的延迟不大于v ，的延迟要求现；己的延迟抖动不大于e 的延迟抖动要求 ；己的丢包率不大于v f 的丢包率要求。 m i n m r 鲥i n f 2 丕( p ) 吖m 。i ，n 。 b o b r , q 岛 勺6 易 厶 勺6 昂 1 一n ( 1 一弓) 8 ( 2 1 ) ( 2 2 ) ( 2 3 ) ( 2 4 ) ( 2 5 ) 武汉理工大学硕士学位论文 2 3q o s 约束组播路由算法的设计理论 2 3 1 算法设计的复杂性分析 q o s 约束组播路由的设计、实现和部署是一个复杂性问题。网络中的带宽、 延时、抖动、网络代价、丢包率等都是作为服务质量约束组播路由算法和协议 设计中要考虑的。满足两个或多个可加性和可乘性量度以及两种量度的任意组 合都可能是n p 完全问题。其复杂性主要表现在以下几个方面： ( 1 ) 由于路由器需要将数据流在多个端口上转发，因此路由器在转发前必 须检查多个端口，这就需要存储组播路由表； ( 2 ) 对于一个群组，它的每个成员都有可能是源端，因此组播路由表的大 小将正比于网络中的网络数与群组数的乘积，而单播路由表只正比于网络数。 ( 3 ) 相对单播，组播路由是一个更加动态化的问题，不仅网络拓扑结构发 生变化或者设备出现故障时路由会改变，更频繁的是节点加入或者退出一个组 播组都会引起路由信息的变化。如何设计一个有效算法以适应这种动态性是组 播路由问题面临的严峻挑战。 此外，当j 个路由算法作为一个组播路由协议的一部分合成时，有许多实 际问题需要考虑，包括：网络路由信息收集与更新、组播树的计算代价和模式、 算法与协议的健壮性、规模伸缩性以及异构服务质量请求问题等。 2 3 2q o s 约束组播路由算法的设计原则 针对q o s 约束组播路由问题的复杂性，我们在设计组播路由算法和协议时 要尽可能考虑下述因烈1 7 j ： ( 1 ) 尽可能降低和平衡网络的负载，避免出现环路以及数据量在某条链路 或子网上的过度集中。因为组播通信的数据在路由过程中要进行复制，如果不 注意这个问题会很容易引起数据在网络上的泛滥，导致拥塞。 ( 2 ) 在结点之间提供可靠的路由。如果组成员是动态变化的，组成员加入 组或退出组引起的路由改变不能影响该组其他成员的通信性能，或影响很小直 至可以忽略。 ( 3 ) 路由协议和算法应根据应用的性质对网络资源( 如带宽、存储量、状 态信息等) 、代价( 如链路代价、复制代价、路由计算代价、状态管理代价、额 外开销代价) 以及性能( 如端到端时延及每个接收者之间的时延抖动、可靠性、 9 武汉理工大学硕士学位论文 扩展性等) 进行协调。 ( 4 ) 组播通信中有多个参与者，每个参与者性能、需求差异以及参与者之 间子网的能力、流量负载等的不同都会给组播路由造成影响。要在路由中完全 解决这些问题是不可能的。组播通信一个有吸引力的特点是扩展性好，即发送 者和网络带宽的消耗不会随着接收者的增加而线性增长，这种良好的扩展性实 际是以牺牲接收者的个性为代价的，即把接收者看作几乎是一样的。我们需要 做的也是在扩展性和接收者差异之间取折衷。 2 4q o s 约束组播路由算法介绍与评价 q o s 约束组播路由算法已成为计算机网络领域研究的热点问题，许多国内 外学者根据不同的问题、原则和角度开发出了许多解决此类问题的算法。在本 节中首先对q o s 约束组播路由算法进行分类，然后介绍几种经典的约束s t e i n e r 树算法，并对其进行评析。 2 4 1q o s 约束组播路由算法的分类 组播路由算法可以根据不同的角度、不同的准则来分类。事实上一种算法 可以同时属于一种或几种分类方法。下面对各种算法进行归纳总结如下： ( 1 ) 静态路由算法和动态路由算法 按照是否允许网络成员随时加入或离开组播组可以分为静态路由算法和动 态路由算法。静态组播是指在通信开始之前指定组播成员。在通信过程中成员 是相对固定的，不发生变化，直至整个组播通信进程被撤销。静态组播路由算 法不能根据当前组成员的实际变化情况做出选择，信息只能够按照设计好的路 径传送，不适用于动态环境。动态路由允许成员能够随时加入或者离开组播组， 但是动态路由算法要处理成员加入和离开后组播树的更新问题。 ( 2 ) 无约束算法和有约束算法 按是否有q o s 约束可以分为无约束算法和有约束算法。许多现有算法是为 非实时网络设计的无约束组播路由算法，它们往往只试图优化树的费用，没有 考虑到有q o s 需求的情况，这使得这些算法的应用范围有限。有约束算法通常 是在给定q o s 约束的条件下使树的费用最小。 ( 3 ) 集中式算法和分布式算法 1 0 武汉理工大学硕士学位论文 根据组播树生成的方式可分为集中式源路由算法和分布式算法。集中式路 由算法也称显式路由或源路由算法，其特点是源节点通过某个链路协议获得整 个网络的拓扑信息，进行路由计算。集中式算法算法简单、易于实施。采用集 中处理的方式，可以立即获取预先存在的路由信息，无需在各个网络节点之间 进行信息交换。缺点是结点在确定路由之前要获取整个网络的拓扑信息，易造 成链路拥塞，有一定的延时；而且节点要定期更新拓扑信息，以保证不产生回 路。p i m d m 1 8 】( p r o t o c a li n d e p e n d e n tm u l t i c a s 卜- d e n s em o d e ) 协议所采用的就 是集中式算法。 在分布式路由算法中，每个组成员仅在局部信息条件下就可参与路由的确 定，而不需要掌握整个网络的拓扑信息，有利于实现大规模的组播路由。分布 式算法的优点是算法执行只限于组成员结点；每个组成员结点仅用到局部的信 息，网络中不需要存储整个网络拓扑信息的中心结点；算法执行过程中所需的 通信费用较小，有利于在大规模网络中确定组播路由。但是分布式路由算法也 存在一些问题，比如当有路由请求时，它不会马上获得路由信息而需要一个路 径搜索延迟；此外，当链路状态信息由于广播延迟而造成不同结点的有关链路 状态不一致时，就会产生回路，从而增加网络带宽的消耗。 ( 4 ) 确定性算法、近似算法与启发式算法 确定性算法是指在一定条件下以确定计算步骤求解问题的算法。这类算法 简单，但不提供回溯能力，且往往具有较高的时间复杂度。由于q o s 组播路由 问题是n p 完全问题，所以很少采用确定性算法的组播路由方法。 近似算法是指以多项式时间解决优化问题并保证能够得到接近最优近似解 的算法。这类算法以k m b 1 9 1 算法为代表，但k m b 算法的代价性能比s t e i n e rt r e e 平均多出5 ，并且k m b 不是和动态群组和大规模网络环境。 启发式算法是近年来研究最多的一个算法。它采用某个启发式函数或规则 对计算步骤进行限制。它不一定能够找到可用解，但是一个设计较好的启发式 算法往往能够得到接近最优的解，同时具有相对低的时间复杂度。q o s 组播路 由问题是n p 完全问题，因此大部分这类问题都采用启发式算法。 2 4 2 约束s t e i n e r 树算法评析 ( 1 ) k p p 算法 k p p 算n t 2 1 】是较早提出的一个时延约束的组播算法。它扩展了寻找近似 武汉理工大学硕士学位论文 s t e i n e r 的k m b 算法。算法先构建满足时延约束的连通图，然后运用p r i m 算法 求出连通图的最小生成树。这个算法的时间复杂度为o ( a l v l 3 ) ，其中是端到端 时延上限。k p p 算法的缺点在于当解存在时，它可能会找不到解。 ( 2 ) b s m a 算法 b s m a 算法【矧由m e h r d a dp a r s a 等人提出。它采用一个切实可行的搜索优化 方法。首先用d i j k s t r a 最短路算法求出从源到各目的节点的延时最段路径构成组 播树，通过替换树中代价较高的边，不断降低树的总代价。b s m a 算法的时间 复杂度为o ( k f 3l o g l v l ) ，其中k 为迭代次数。b s m a 在替换边时采用的第k 条 最短路算法，虽然求得的组播树代价较小，但其时间复杂度比较高。尤其在大 型网络中，k 值往往较大，将大大增加计算时间。虽然调节参数k 可以降低时间 复杂度，但这势必会增加树的代价。 ( 3 ) d v m a 算法 d v m a 算法1 2 3 j 是一种满足延时和抖动约束的多约束组播路由算法，由 r o u s k a s 和b a l d i n e 提出。它以从源节点到最远节点的k 条最短路径中的一条作 为初始组播树，然后通过一定规则对初始树进行扩充，直至组播树包括所有目 的节点。该算法时间复杂度为o ( k z l u l l v l 4 ) ，算法复杂度很高，在大规模网络环 境下时间问题尤为突出。为此文献 2 4 j 提出了一种改进的l cd v m a 算法，其主 要思想是每次通过最短代价路径或最短延时路径连到树上的任一节点，再通过 比较找出最理想的路径并添加到树上，该算法的时间复杂度为o ( i m i i v l 2 ) 。 ( 4 ) c d k s 算法【2 习 该算法首先计算一个从源到各个目的的最小代价树，然后合并相同链路所 构成的树，再将所有路径中不满足延时约束的路径用最小延时路径替换。该算 法理论上总能找到符合约束条件的组播树，其时i b - 复杂度为o ( i v l 2 ) 。 ( 5 ) d d v c t 算法 s h e u 基于c b t ( c o r eb a s e dt r e e s ) 【2 6 】和最小延迟路径算法提出t d d v c t t 2 b ， 设计该算法的出发点在于：( 1 ) d i j k s t m 算法能够快速找到最小延迟路径； ( 2 ) 在两个节点的最小延迟路径上很容易满足延迟变化约束。算法的难点在于核心 的选择，选择核心节点的步骤是：( 1 ) 计算每一个目的节点和网络中其它节点 的最小延迟；( 2 ) 为每一个节点计算该节点到不同目的节点的延迟变化； ( 3 ) 选择具有最小延迟变化的节点作为核心节点；( 4 ) 目的节点连接到该核心节点。 直到找到个满足条件的核心节点为止。 武汉理工大学硕士学位论文 除了以上介绍的几种算法外，还有许多s t e i n e r 树算法，如c s p t 2 8 1 、 c r m a 2 9 、d p c t 【3 0 1 、q d m r t 3 1 】、d d v b m r a 3 2 1 、d d m m r p 3 3 】等等。这些算法 都考虑了一种或一种以上q o s 约束。 2 5 基于智能算法的q o s 约束组播路由算法 传统的约束组播树算法是在基于特殊数学模型的基础上，使用严格逻辑推 理的确定性的研究方法解决问题的。然而实际的网络是不确定的，不能简单地 用数学模型的方法来分析和解决如此复杂的问题。对于2 个以上目标和准则， 虽然有许多启发式算法通过减少搜索空间来发现可以接受的解，但这些算法仍 然是不切实际的和不可靠的。近年来，以智能算法为代表的智能优化技术发展 迅速，受到人们的普遍关注，取得了一些有意义的成果。这些算法在运用到组 合优化问题中有独到的优势，许多学者都将其引入q o s 约束组播路由问题中来， 开发出了许多基于智能算法的q o s 约束组播路由算法。 2 5 1 遗传算法 遗传算法m 1 ( g a ，g e n e t i ca l g o r i t h m ) 最早由h o l l a n d 等人提出。近年来，遗 传算法以其解多目标优化问题的潜力而受到了较大的重视。作为一种自适应全 局优化概率搜索算法，遗传算法以其简单通用、健壮性强、适于并行处理以及 高效、实用等显著特点，己在组合优化、模式识别、神经网络、经济预测等领 域广泛应用。遗传算法的基本思想来源于遗传进化，主要是借助于生物进化机 制与遗传学原理，按照自然选择和适者生存的原则，利用简单的编码技术和繁 殖机制，模拟自然界生物群体优胜劣汰的进化过程，实现对复杂问题的求解。 遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编 码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传 操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制 参数设定五个要素组成了遗传算法的核心内容。 应用遗传算法进行问题求解时要解决3 个方面的问题，即：首先将待研究 问题的解用某种编码方式( 如二进制等) 表示成染色体，并随机生成初始群体， 然后是适应值函数的设计，即以群体中个体的适应值为依据，淘汰部分后代， 适应值高的染色体被选中的概率高，最后是对个体执行选择、交叉和变异三种 武汉理工大学硕士学位论文 基本遗传算子操作以及控制参数的设定，使群体中的个体( 问题的解) 不断进 化并逐渐逼近问题的最优解。 图2 1 为一种典型的遗传算法流程图。图中有几个重要的环节： ( 1 ) 编码和初始群体的生成：g a 在进行搜索之前先将解空间的解数据表 示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同 的点。然后随机产生n 个初始串结构数据，每个串结构数据称为一个个体，n 个体构成了一个群体。g a 以这n 个串结构数据作为初始点开始迭代。编码方式 依赖于问题怎样描述比较好解决。初始群体也应该选取适当，如果选取的过小 则杂交优势不明显，算法性能很差，群体选取太大则计算量太大。 ( 2 ) 检查算法收敛准则是否满足，控制算法是否结束。可以采用判断与最 优解的适配度或者定一个迭代次数来达到。 ( 3 ) 计算个体适应值：适应性函数表明个体或解的优劣性，在开始也应该 评价适应性，以便和以后的做比较。不同的问题，适应性函数的定义方式也不 同。根据适应性的好坏，进行选择。选择的目的是为了从当前群体中选出优良 的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体 现这一思想，进行选择的原则是适应性强的个体为下一代贡献后代的概率大。 ( 4 ) 交叉：按照交叉概率进行杂交。杂交操作是遗传算法中最主要的遗传 操作。通过杂交操作可以得到新一代个体，新个体组合了其父辈个体的特性。 杂交体现了信息交换的思想。可以选定一个点对染色体串进行互换、插入、逆 序等杂交，也可以随机选取几个点杂交。杂交概率如果太大，种群更新快，但 是高适应性的个体很容易被淹没，概率小了搜索会停滞。 ( 5 ) 变异：按照变异概率进行变异