（计算机应用技术专业论文）遗传算法在qos组播路由优化中的应用研究.pdf

遗传算法在q o s 组播路由优化中的应用研究 摘要 随着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 需求 由于q o s 组播路由带有多个q o s 约柬参 数 而这种多约束条件f 的q o s 组播路由问题属于n p 完全问题 这使得它与传统的路 由过程不同 难以用经典的最短路径优先算法 如b e l l m a n f o r d 和d i j k s t r a 算法 求解 对于o o s 组播路由问题的研究大多都集中在采用启发式算法求解无约束组播路由问题 和时延受限组播路由优化问题 然而由于这些算法都具有较高的时间复杂度而不能满足 实际应用的需要 本文利用遗传算法作为求解q o s 组播路由优化的算法 主要研究了四 类典型的q o s 组播路由问题 首先 根据组播路由问题的特点 建立了候选路由表 采用了等长节点序列串的编 码方式 针对标准遗传算法的缺点 引入模拟退火思想 该算法既提高了算法的全局收 敛能力也提高了收敛速度 其次 针对目前的单约束 或无约束 组播路由问题的局限 性 用遗传算法实现了一种通用的多约束q o s 组播路由问题 采用基于路径的树结构编 码方式 遗传算子操作过程简单 算法体现了遗传算法较强的搜索能力 再次 通过分 析遗传算法和组播路由问题的特点 提出一种双种群遗传算法 通过嫁接种群来指导种 群的进化方向 大大提高了算法的收敛速度 最后提出一种双染色体遗传算法来求解时 延 带宽约束组播路由问题 同时在产生初始群体时 引入了求解组播路由问题的经 典启发式算法思想 设计遗传算子时 采用了双变异率算子 而交叉算子是在两种染色 体之间进行的 通过仿真结果验证了该算法的有效性 关键词 遗传算法 组播路由 模拟退火算法 s t e i n e r 树 d i j k s t r a 算法 中北大学学位沦文 s t u d yo nq o s m u l t i c a s t r o u t i n go p t i m i z a t i o n b a s e do n g e n e t i c a l g o r i t h m p o s t g r a d u a t e l im e i l i a n t u t o r p r o f e s s o r z e a gj i a o e h a o p r o f e s s o rc h e nl i e h a o a b s t r a c t w i t ht h ed e v e l o p m e n to f i n t e m e t t h er e c e n te m e r g e n c eo f m u l t i m e d i ac o m m u n i c a t i o n s a 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 r ti 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 ea 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 ne 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 n l t i c a s tr 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 st 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 gw 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 s ot h ep r o b l e m c a nn o tb es o l v e du s i n gt h ec l a s s i c a ls h o r t e s tp a t hf i r s ta l g o r i t h m ss u c ha sb e l l m a n f o r da n d d o k s t r a t h u s m o s tp r e v i o u sr e s e a r c h e r sh a v ef o c u s e do nd e v e l o p i n gh e u r i s t i ca l g o r i t h m st 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 d m u l t i c a s t m u t i n gp r o b l e m h o w e v e r t h e s e h e u r i s t i ca l g o r i t l u n sh a v eh i 曲c o m p u t a t i o nc o m p l e x i t ys ot h e ya r en o tf i ti np r a c t i c a l i t y 1 1 1 t h ep a p e r g e n e t i ca l g o r i t h mi su s e dt ot h eq o sm u l t i c a s tm u t i n gp r o b l e ma n df o u rt y p i c a l r e s p e c t so f r e s e a r c hh a v eb e e np u tf o r w a r d f i r s to fa l l c a n d i d a t er o u t i n gt a b l e sa r e d e s i g n e db a s e d o nt h ec h a r a c t e r i s t i co fm u l t i c a s t r o u t i n gp r o b l e ma n dt h ee n c o d i n gm e t h o do fn o d e ss t r i n gw i t he q u a ll e n g t hi su s e d d u et o t h ed i s a d v a n t a g eo fs t a n d a r dg e n e t i ca l g o r i t h m s i m u l a t e da n n e a l i n gi si n t r o d u c e dt og e n e t i c o p e r a t o r s t h ep r o p o s e da l g o r i t h m e n h a n c e sn o t o n l yg l o b a l s e a r c h a b i l i t y b u ta l s o c o n v e r g e n c es p e e d s e c o n d l n i n a l l u s i o nt ot h e t i m i t a t i o no f s i n g l e c o n s t r a i n to r u n c o n s t r n n e dm u l t i c a s tr o u t i n g p r o b l e m ac o m m o n m u l f i c o n s t r a i n e dm u l t i c a s tr o u t i n gb a s e d o ng e n e t i ca l g o r i t h mi sr e a l i z e d t h e r o u t i n ge n c o d i n gm e t h o di su s e d s ot h eg e n e t i c i i 中北火学学位论文 o p e r a t o r sc a nb eo p e r a t e dc o m p a r a t i v e l ye a s i l y t h ea l g o r i t h r n m a n i f e s t sb e t t e rs e a r c ha b i l i t y o f g e n e t i ca l g o r i t h m m o r e o v e r a n a l y z i n gt h ec h a r a c t e r i s t i co fm u l t i c a s tr o u t i n ga n dg e n e t i c a l g o r i t h m ad u a l p o p u l a t i o n sg e n e t i ca l g o r i t h mi sd e s i g n e d i nt h ep r o c e s so f e v o l u t i o n t h e g r a f t e dp o p u l a t i o ni n s t r u c t st h ee v o l u t i o nd i r e c t i o n o ft h ee v o l u t i v ep o p u l a t i o n t oag r e a t e x t e n t t h 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 mi si m p r o v e df i n a l l y t h eg e n e t i ca l g o r i t h m b a s e do nt w oc h r o m o s o m e ss o l v e sb a n d w i d t h d e l a y c o n s t r a i n e dl e a s t c o s tm u l t i c a s tr o u t i n g p r o b l e m w h e n t h ei n i t i a l p o p u l a t i o n i s p r o d u c e d t h e t r a d i t i o n a lh e u r i s t i c a l g o r i t h m i s i n t r o d u c e dt ot h ei m p r o v e dg e n e t i ca l g o r i t h m d u a lm u t a t i o no p e r a t o ri su s e d a n dc r o s s o v e r o p e r a t o r i s o p e r a t e db e t w e e nt w oc h r o m o s o m e s s i m u l a t i o nr e s u l t s s h o wt h i s a l g o r i t h mi s e f f e c t i v e k e y w o r d s g e n e t i ca l g o r i t h m m u l t i c a s tr o u t i n g s i m u l a t e d a n n e a l i n g s t e i n e r t r e e d i j k s t r a i i i 中北大学学位论文 本人声明 我声明 本论文及其研究工作是由本人在导师指导下独立完成的 在完 成论文时所利用的一切资料已在参考文献中列出 作者 签字 幸关龟 日期 中北大学学位论文 1 绪论 现代计算机网络包括i n t e r n e t 都是分组交换网 在进行分组交换阿设计时 网络的 路由选择是需要考虑的重要因素 一个好的路由选择可以使网络的平均时延较低 提高 网络的吞吐量 同列 路由选择是 个非常复杂的问题 这是因为 路由选择是网络中 的所有节点共同协调工作的结果 其次 路由选择的环境往往是在变化的 而这种变化 有时无法事先知道 此外 当网络发生拥塞时 就特别需要有能缓解这种拥塞的路由选 择策略 但恰好在这种条件下 很难从网络中的各节点获得所需的路由选择信息 可见 路由选择在当前乃至于在可预见的未来 都是分组交换网的重要组成部分 其性能的好 坏将直接影响到网络整体性能的好坏 近代科学技术发展的特点之 是生命科学与工程科学的相互交叉 相互渗透和相互 促进 遗传算法的发展正体现了科学发展的这一特征和趋势 由于遗传算法的整体搜索 策略和优化计算是不依赖于梯度信息 所以它的应用范围非常广泛 尤其适合于处理传 统搜索方法难以解决的高度复杂的非线性问题 遗传算法是2 l 世纪智能计算的关键技 术之一 j 路由选择实际上是一个优化问题 传统的启发式算法难以求解并且计算复杂 度高 特别适合使用遗传算法来求解 近年来 随着网络通讯技术的快速发展以及i n t e r n e t 的普及 出现了许多新的网 络应用系统 如视频点播 远程教学 远程医疗及网上拍卖等 而这些系统对网络服务 质量的要求较高 组播是从一个发送者同时向特定多个接收者传送数据的通信过程 由 于组播通信是建立树状路由 数据只在树的分枝处复制 能够节约带宽 降低服务器负 载 降低网络负载和减少拥塞 在国外 组播得到了很广泛的应用 微软公司每个月都 要用组播技术传播多媒体数据流 c i s c o 公司已经用i p 厂r v 来进行实时视频流组播 用 于公司内部的会议和培训 美国田纳西州的p r o m u s 饭店已经使用s t a r b u r s t 通信公司 的软件 通过卫星链路向所属分店分发软件升级和数据更新信息 m c i 公司以及b b n p l a n e t 公司等一些i n t e m e t 服务提供商 h a t e m e ts e r v i c ep r o v i d e r i s p 正在有限的基础 中北大学学位论文 上进行组播试验 包括u l 州e t t e c h n o l o g i e s 在内的供应商已经开始向客户提供组播服 务 d i g i t a lx p r e s s 公百j 通过卫旱经销组播眼务 2 1 组播是一项非常实用的技术 为了推动它的发展 由全球主要的网络设备厂商 电 信运营公司和i s p s 成立了 个 沧坛型的组织 i p 组播倡议组织 i p m i 许多大公 司 包括a t t i b m a l c a t e l c i s c o m i c r o s o f t 和3c o r n 等都支持i p 组播技术 并且成为了i p m i 的成员 i p m i 的目的是与网络工程部i e t f i n t e r n e t e n g i n e e r i n gt a s k f o r c e 中的组播工作组一起制定i p 组播标准 并加速这些标准的采用 随着组播技术 的进 步完善 以及更多高效 实用的组播应用程序被开发出来 组播将获得更加广泛 的应用 组播通信的关键是组播路由的选择 也就是如何构建一棵组播分布树 用以在 转发数据时能保证用户服务质量的需求 因此 找出既能满足应用服务质量需求 又具 有最小代价的组播路由对保证组播应用系统的正常高效运行具有很重要的意义 1 2 网络路由选择问题 1 2 1 路由技术 路由是在最宏观的层次上对网络资源进行管理的手段 它是交换机或者路由器不可 缺少的基本配置之 路由技术也是因特网中最复杂和要求最严格的内容之一 路由有 两方面的基本内容 收集网络状态信息并不断更新信息 根据已有信息来为新的连接请 求选择 条合适的路由 一个路由算法的好坏极大地取决于信息收集的好坏 比如信息 更新的频度 最终信息的准确度 这些问题和实际协议实现方法关联程度更大 通信网 络路由功能可以分为两个方面 一是在连接建立阶段为通信会话选择一个路由 二是确 保该会话的分组沿指定的路由转发 面向连接的通信进程执行完整的路由功能 而面向 无连接的通信进程并不是这么严格地执行路由功能 有时候是收到分组后再为它计算路 由 有时候是用软状态来设置路由通道 1 2 2 基本分类 根据应用范围 路由选择问题一般可分为两大类 单播路由选择和组播路由选择 具体定义如下 2 中北大学学位论文 可行路径 可行树 可行路径 可行树 是网络中从源节点到 所有 目的节点 的一条路径 组播杠j 并且该路径 树 具有足够的尚未分配的资源 能够满足特定 的q o s 需求 单播路由选择问题可定义如下 给定一源节点s 一目的节点t 组服务质量约 束c 以及可能的最佳化目标 寻找从s 到t 满足c 的最可行路径 组播路由选择问题定义如下 给定一源节点s 一组目的节点集r 一组约束c 以 及可能的鼹佳化目标 寻找从s 出发覆盖r 中所有节点日标满足c 的最可行的树 1 3q o s 组播路由选择方法 1 3 1 组播通信概述 f 1 组播的 作原理 组播是一种从一个发送者同时向多个接收者或者多个发送者向多个接收者传送数 据包的通信过程 组播源把数据包发送到特定组播组 而只有属于该组播组的地址才能 接收到此数据包 组播以最佳的方式将数据传输给所有的主机 组的成员可以是动态的 即成员可阱在任何时间加入一个组或离开一个组 组的大小和位置没有限制 一个主机 可以是多个组的成员 组播可以大大的节省网络带宽 提高数据传送效率 减少主干网 出现拥塞的刈 能性 因为无论有多少个1 7 i 标地址 在整个网络的任何一条链路上只传送 单一的数据包 组播组中的主机可以是在同一物理网络 也可以来自不同的物理网络 如 果有组播路由器的支持 为了满足多媒体实时应用等的需求 很有必要寻求网络层对组播通信的支持 使组 播技术满足此类应用的要求 为此就有了实现组播的方式 也就是建立组播树 m u l t i c a s t i n gt r e e 组播树是覆盖源节点和所有目的节点的一棵生成树 建立组播树有 以下优点 信息可以沿着树的分支并行的传到各个目的节点 这可以降低信息传递的 时延 信息只在树的分支处进行复制 从而使复制的份数尽量少 这样做可以节省大 量的带宽资源 提高资源的利用率 并且能减少拥塞的发生 除了组播通信方式 计算机网络中常用的通信方式还有单播通信方式和广播通信方 式 从图1 1 可以看出组播通信和单播通信的区别 3 中北大学学位论文 单播t u n i c a s t 传输 在发送者和每一接收者之间需要单独的数据信道 如果一台 主机同时给很少量的接收者传输数据 一般没有什么问题 但如果有大量主机希望获得 数据包的同一份拷贝时却很难实现 因为这犒导致发送者负担沉重 时延增加以及造成 网络拥塞 而且为了保证一定的服务质量还需要增加硬件和带宽 广播 b r o a d c a s t 传输 是指在整个i p 子网内广播数据包 所有在子网内部的主 机都将收到这些数据包 广播意味着网络向子网主机都投递一份数据包 不论这些主机 是否乐于接收该数据包 然而广播的使用范围非常小 只在本地子网内有效 因为路由 器会封锁 播通信 同时广播传输增加非接收者的开销 a 牲艟j 煎倍方式 接收释3 庐耘蹴 弋尹嘎 滴鬈鹫 组播传输可在数据链路层 第二层 和网络层 第三层 实现 支持的媒体类型包 括以太网 f d d i 和a t m 大多数路由器提供商支持i p 组播 不支持i p 组播的网络通 过组播隧道技术传输组播信息包 2 组播通信的实现方案 在单播模型中 数据包通过网络沿着单一路径从源主机向目标主机传递 但在组播 4 中北大学学位论文 模型中 绀播源向某一组地址传递数据包 而这一地址却代表一个主机组 为了向所有 接收者传递数据 一般采用组播分布树描述i p 组播在网络罩经过的路径 组播分布树有三种基本类型 洪泛法 有源树 共享树 有核树和s t e i n e r 树 洪泛法 这是最简单的向前传送组播路由算法 并不构造所谓的分布树 其基本原理如下 当组播路由器收到发往某个组播地址的数据包后 首先判断是否是首次收到该数据包 如果是首次收到 那么将其转发到所有接口上 以确保其最终能到达所有接收者 如果 不是首次收到 则抛弃该数据包 洪泛法的实现关键是 首次收到 的检测 这需要维护一个最近通过的数据包列 表 但无需维护路由表 它适合于对组播需求比较高的场合 并且能做到即使传输出现 错误 只要还存在一条到接收者的链路 则所有接收者都能接收到组播数据包 然而 洪泛法不适合用于i n t e r n e t 因为它不考虑链路状态 并产生大量的拷贝数据包 此外 对于高速网络而言 首次收到 列表将会很长 占用相当大的内存 尽管它能保证不 对相同的数据包进行二次转发 但不能保证对相同数据包只接收一次 有源树 有源树也称为基于信源的树或最短路径树 s h o r t e s tp a t ht r e e s p t 它是以组播 源为根构造的从根到所有接收者路径部最短的分布树 如果组中有多个组播源 则必须 为每个组播源构造一棵组播树 由于不同组播源发出的数据包被分散到各自分离的组播 树上 因此采用s p t 有利于网络中数据流量的均衡 同时 因为从组播源到每个接收者 的路径最短 所以端到端 e n d t o e n d 的时延性能较好 有利于流量大 时延性能要 求较高的实时媒体应用 s p t 的缺点是 要为每个组播源构造各自的分布树 当数据流 4 孱 7 i i x j 构造s p t 的开销相对较大 共享树 共享树也称r p 树 r p t 是指为每个组播组选定一个共用根 汇合点r p 或核心 以r p 为根建立的组播树 同一组播组的组播源将所要组播的数据单播到r i p 再由r p 向其它成员转发 目前 讨论最多同时也是最具代表性的两种共享树是s t e i n e r 树和有 核树 c b t s t e i n e r 树是总代价最小的分布树 它使连接特定图 g r a p h 中的特定组成员所需 5 中北大学学位沦文 的链路数最少 若考虑资源总量被大量的组使用的情况 那么使用资源较少最终就会减 少产牛搠塞的风脸 s t e j n e r 树相当不稳定 树的形状随组中成员关系的改变而改变 且 对大型网络缺少通用的解决方案 所以s t e i n e r 树只是一种理论模型 而非实用工具 目前 出现了许多s t e i n e r 树的次优启发式生成算法 有核树 c b t 是由根到所有组成员的最短路径合并两成的树 c b t 以选定中心为 根 其他组成员按照最短路的原则与中心建立连接 构造成为一棵由所有发送节点共享 的树 a b a l l a r d i e 在1 9 9 7 年9 月的 基于核的组播路由体系结构 c o f eb a s e dt r e e s c b t m u l f i c a s t r o u t i n g a r c h i t e c t u r e 中介绍了有核树 共享树在路由器所需存储的状态信息的数量和路由树的总代价两个方面具有较好 的性能 当组的规模较大 而每个成员的数据发送率较低时 使用共享树比较适合 但 当通信量大时 使用共享树将导致流量集中及根 r p 附近的瓶颈 3 组播的应用 自从1 9 9 2 年3 月第一次建立组播主干网 m b o n e m u l t i c a s tb o n e 且i e t f i m e m e t e n g i n e e r i n gt a s kf o r c e i n t e m e t 工程任务组 利用它成功地举行第一次网络会议以来f 3 1 组播引起了更为广泛的重视 并取得很大的发展 许多专家学者对其各个方面进行了深 入的研究 4 6 组播应用大致可以分为三类 点对多点应用 多点对多点应用和多点对 点应用 点对多点的应用 点对多点应用是指一个发送者 多个接收者的应用形式 这是最常见的组播应用形 式 典型的应用包括 媒体广播 媒体推送 信息缓存 事件通知和状态监视等 多点对多点的应用 多点对多点应用是指多个发送者和多个接收者的应用形式 通常 每个接收者可以 接收多个发送者发送的数据 同时 每个发送者可以把数据发送给多个接收者 典型应 用包括 多点会议 资源同步 并行处理 协同处理 远程学习和讨论组等 多点对点的应用 多点对点应用是指多个发送者 一个接收者的应用形式 通常是双向请求响应应用 任何 端 多点或点 都有可能发起请求 典型应用包括 资源查找 数据收集 网络竞 拍 信息询问和j u k e b o x 等 6 中北大学学位沦文 1 3 2 服务质量要求 服务质量 q u a l i t yo f s e r v i c e 简称q o s 指发送和接收信息的用户之间以及用户 与传输信息的服务网络之间关于信息传输的质量约定 q o s 包括用户要求和网络服务提 供者的行为两个方面 用户要求指用户在i r t t e r n 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 包在传播介质的传播时间 i p 包在交换机或路由器中被处理的时间 以及 i p 包在交换机或路由器的等待队列中的排队时间 延时抖动 j i t t e r 即延时变j l p 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 a b c f g 用d a b 表示对应链路 a 山 的度量 则q o s 度量可以按性 质分为以下三类 a 凸性q o s 度量 如果d a g m i n d a b d b c d g g 那么度量由传输通道中瓶颈决定 即此度量 仅与路径上的某个瓶颈链路的q o s 度量有关 如剩余带宽 剩余缓存空间 链路速度等 b 加性q o s 度量 如果d a g d a b d b e d c g 那么度量由传输通道中所有链路的特性共同决 7 中北大学学位论文 定 如时延 时延抖动 费用等 c 乘性q o s 度量 如果d a g 2 d a b d b e d f g 即度量为所有链路对应度量的乘积 如可靠性等 如耿d a b l n d a b 则乘性度量就转化为加性度量 因此 按度量的性质q o s 路由可归结为基本的两大类 路径优化问题 对应加性 q o s 度量 链路优化问题 对应凸性q o s 度量 1 3 3q o s 组播路由 因为目前广泛发展的多媒体通信业务的需要 多媒体服务往往在采用组播的同时带 有q o s 要求 越来越多的研究人员关注研究满足多媒体通信的需求及其发展方向 其中 q o s 组播路由问题主要是研究在满足服务质量需求的情况下怎样更好地实现组播功能 q o s 路由问题又称为受限路由问题 其约束条件包含了两个或两个以上的加法型度量 如延迟 代价等 或者包含加法型度量和乘法型度量 如丢失率 的组合 是n p 完全 问题 1 组播路由问题的阐述 组播路由选择问题定义如下 给定一源节点s 一组目的节点集r 一组约束c 以 及可能的最佳化目标 寻找从s 出发覆盖r 中所有节点目标满足c 的最可行的树 为简单起见 分析多点路由问题时 将网络看成无向带权连通图g v e 其中v 是网络中所有交换节点组成的集合 e 是图g 中所有边的集合 每一条边表示两节点间 的一条通信链路 源节点s 目的节点集d 每一条边e e 的代价函数c e e r r o 其中财表示代价的值域范围为包括0 在内的正整数 典型的代价函数包括 链路上的延 迟 可用资源 带宽和价格 图1 2 为带q o s 参数的网络拓扑图 在组播应用中 给定顶点集合d v 寻找g 中一棵覆盖d 的子树t v t e t 信 息从源节点出发 经组播树t v t e t 到达各目的节点 其中v t c v e t c e 并使t 的代价最小 即使 e e t c e 最小 组播树的费用是指树中所有链路费用的总和 这里 链路的费用是一个广义的费用 它可以指链路上的延迟 可用资源 带宽和价格等 在 实际应用中 一般要求确定的路由要有效利用网络资源 为此要求组播树的费用最小 8 中北大学学位论文 图1 2 带q o s 参数的网络拓扑图 2 q o s 组播路由算法的研究现状及发展趋势 f 1 研究现状 求解带q o s 约束的组播生成树问题称为带约束的s t e i n e r 树问题 该问题同样是一 个n p 完全问题 迄今为止 树建立实际上还使用一些基本的启发式算法 其中针对最 短路径问题提出d i j k s t r a 算法 b e l l m a n f o r d 算法 f l o y d 算法 动态规划方法 它们 是寻找节点阳j 最短路径的基本算法 贪心算法 p r i m 算法 破圈法 k r u s k a l 算法是基 本的最小生成树算法 p m s t 算法 k m b 算法是基于最小生成树算法 经剪枝生成 s t e i n e r 树的启发式算法 n a i v e 算法 s p h 算法 s p h z 算法 k s p h 算法 a d h 算 法 7 1 是利用最短路径算法生成s t e i n e r 树的启发式算法 然而采用启发式算法 随着网 络节点和链路数量的增加 其计算时间代价会急剧的增加 目前q o s 组播路由问题中研 究最多的就是延时受限组播树 即只包含1 个约束条件 对于多个约束条件的情况 国 内外现在主要用的方法有遗传算法 8 1 1 1 蚂蚁算法 模拟退火算法 t a b u 算法等 分别 提出了基于这些智能算法的组播路由算法 另外还提出人工神经网络技术 幢 1 3 群集智 能技术 免疫算法等智能算法来解决该问题 目前q o s 组播路由问题是国内外研究 的热点 近年来 随着对遗传算法的研究不断深入 发现采用该算法来求解n p 难问题能取 9 中北大学学位论文 得较好的效果 i 复方式同样适合于求解q o s 组播路由问题 因此人们的注意力越来越集 中在基于g a 的q o s 组播路由算法的研究上 2 组播路由选择算法正在向以下趋势发展 通用性 多媒体应用具有各种q o s 需求 如带宽 时延 时延抖动 代价等 从 组播路由发展来看 应该开发 种通用的路由算法 来取代对不同类型的q o s 需求开 发的不同路由算法 因此 应对多种q o s 参数需求下的组播路由问题进行研究 简单性 在逻辑上简单的组播路由算法 有助于提高运行效率 减少调试和改进 的时间 也将使得算法易于理解 实现 维护和升级 开发简单而有效的组播路由算法 具有重要的现实意义 外延性 随着网络体系结构的改变以及容量的增加 将会出现各种各样新的组播 应用 因此需要路由算法具有自适应性 柬满足各种新出现的服务类型 层次型路由 随着网络和组播组的增大 就会带来可扩展性问题 解决可扩展性 问题的方式就是采用层次型路由 层次型路由较难用于q o s 路由 a 状态信息不精确 b 对于一个节点而言 其网络拓扑信息和链路状态信息都是局部的 因此很难确定q o s 路由 还有待于进一步进行层次型路由的理论研究 不精确状态信息下的路由 大多数现存组播路由算法都假定能得到精确的网络状 态信息 然而在层次型路由环境中 精确的状态信息通常难以得到 因此 在大型网络 中应设计状态信息不精确时的路由算法 目前该问题尚处在理论研究阶段 1 4 组播路由选择算法 q o s 组播路由的q o s 约束包括带宽 或者成本 跳数 吞吐量 延迟 抖动和丢 失率等等 组播路由算法即是选择优化一个或多个q o s 约束的组播路由 1 4 1 组播路由算法分类 从不同的角度 组播路由算法可以有多种分类的方法 i 集中式与分布式 集中式算法要求计算节点知道所有的网络状态信息 而分布 式算法则只要求计算节点知道部分信息 可以看出 在广域网上布署一个集中式算法是 1 0 中北大学学位论文 有困难的 因此 寻求分布式的求解算法是非常重要的 2 静态型与动态型 所谓的静忿型是指在组插树生成以后就不再发生变化了 显 然这对于大部分应用来说是不适合的 而动态型则与此相反 在会话阶段 它允许节点 动态地加入或者离开 这符合实际的需求 但同时也给算法带来了新的问题 3 源基树与共享树型 解决组撩路由问题的算法大致可分两类 类算法称为源 基树算法 该算法为组中每一个发送者建立一棵以发送者所在子网为根的组播树 源基 树算法只适用于广播业务 另一类算法则为组内所有发送者与接收者建立一棵共享树 这类算法适用于会议型业务 如计算机会议 会议型业务具有以下特征 既有1 一t o n 型传输 也有m t o n 型传输 对信息传送的时延有严格要求 数据量大 且媒体 多样要求不同的处理 在改变发言者时要求进行快速的路由切换 1 4 2 组播路由算法 1 基f 最短路径树的算法 最短路径树算法求解从组播源点到组播终点各成员的路径并使路径总权值之和最 小 如果使用单位枞值 则得到的组播树就是最小跳 h o p 树 即从源点到终点所经 过的节点最少的组播树 如果权值表示链路时延 则所得到的组播树就是最小时延树 b e l l m a n f o r d 算法 和d i j k s t r a 算法 1 6 1 是最有名的两个最短路径算法 两个算法都是多 项式时间复杂度 最短路径算法可以用来解决时延受限问题 2 基于最小生成树的算法 一棵最小生成树是包含了组播源点和所有组播终点且权值最小的一棵树 最有名的 集中式最小生成树算法是普里姆 p r i m 算法 g a l l a g e r 等提出了一种分布式算法 1 7 普里姆算法的基本思想是 在网络中任选一个节点v o 作为树根 从v o 开始 连接与v o 相连的 边权值最小的节点v l 得到子树t l 再以上述规则连接t 1 与网络中不在t l 中的节点 如此继续下去 直到所有节点都用到为止 最小生成树算法可以用来解决树 优化问题 3 基于最大带宽树的算法 s h a c h a m 墉1 提出了一个用于处理分布式层次型编码数据的最大带宽树 首先使用迪 杰斯特拉算法得到从组播源点到每个组播终点的最大带宽路径 然后将这些最短路径进 中北大学学位论文 行合并 消除环路等处理 最终得到最大带宽树 最大带宽树可以解决链路优化问题 4 基于斯坦利树的算法 所谓s t e i n e r 树 是指给定某个度量空阃中的一个点集 求解将这些点互联的最短 网络 斯坦利 s t e i n e r 树问题以最小化组播树的总代价为目标 是n p 完全问题 1 9 2 0 l 如果组播组包含了网络中的所有节点 则斯坦利树问题就简化为最小生成树问题 不受 限斯坦利树算法可以用来解决树优化问题 但不能用来解决有q o s 约束的树受限问题 w i n t e r 1 9 和h w a n g 2 0 对启发式斯坦利树算法进行了总结 k o u m a r k o w s k i 和b e r m a n 提出了一种求解斯坦利树的启发式算法1 2 i k m b 算 法先定义个距离完全图 所谓距离完全图是包含了网络中所有节点的完全图 且用每 对节点之间的边表示它们之间的最短路径 设从最初的网络拓扑图g 创建出的距离完 全图为h 首先用普里姆最小生成树算法得到h 图的最小生成树u 再把u 中的每条 边用相应的最短路径替换 从而得到连通子图v 然后对v 运用最小生成树算法得到 一个生成树t 最后 反复修剪t 中的非组播叶子节点 从而得到一棵组播树 此外 t a k a h a s h i 提出了 种启发式算法f 2 2 1 b a u e r 和v e r m a 2 剐提出了一种分布式 算法来求解斯坦利树问题 f 5 1 基于受限斯坦利树的算法 对斯坦利树问题加上其它附加条件 如时延 时延抖动等 就成为受限斯坦利树问 题 该类问题也是n p 完全的 目前已有一些启发式算法被提出 z h u p a r s a 和g a r c i a l u n a a c e v e s 提出了一种称为有界最短组播算法 b o u n d e d s h o r t e s tm u l t i c a s ta l g o r i t h m b s m a 用来解决时延受限树优化问题 该算法定义链路 代价作为链路使用函数 同时定义树的超边 s u p e r e d g e 所谓超边就是一个最长简单 路径 它的节点 包括端点 都是非组播点 称为中继点 r e l a yn o d e 算法先以组播 终点集为叶子节点 以时延为权值生成一棵最小生成树 然后在不违反时延约束时 以 时延更小的超边来取代最小时延树中的超边 直到树的代价不能更低 超边由第k 最 短路径算法生成 由于b s m a 算法以最小时延生成树开始 因此 只要时延受限组播 树存在 就一定能够找到它 k o m p e l l a p a s q u a l e 和p o l y z o p 9 1 提出了一个称为k p p 的启发式算法 他们假定链 路 u v 的时延为d u v 时延约束d 是一个整数 而代价c u v 是任一正实数 定义 1 2 l j 北大学学位论文 了受限最小代价路径和节点集n 的封闭图g 受限最小代价路径为u 和v 之间的最小 代价路径 从u 到v 的时延小于d 而节点集n 的封闭图g 为节点集n 的完全 图 且节点v 到w 的边的权值与从v 到w 的受限最小代价路径的权值相同 同时还给 出了两个选择函数 一个是链路代价函数 另一个是平衡代价和时延的函数 首先构建 一个基于组播源点和组播终点集的封闭图g 然后从组播源点s 开始 用普早姆算法 构造一个最小生成树 构造最小生成树时每条边按以下规则选取 连接树节点与非树 节点 不违反时延约束条件 使选择函数的值最小 最后用受限最小代价路径代替 最小生成树中的相应边 同时消除可能存在的环路 从而得到一棵组播榭 浚算法存在 时间复杂度大 准确度低等问题 h a b e r m a n 等 25 提出了 种求解时延和时延抖动约束的斯坦利树问题的算法 首先 构造 棵参考树t r 它的路径是从组播源点s 到所有终点的最小代价路径 对每一个组 播终点d 都构造一棵树t i 这棵树初始化为t r 中从s 到d i 的路径 通过添加树中 节点到非树组播终点的满足时延和时延抖动约束的路径来扩展树t 直到所有组播终点 都被包括进去 如果最后得到的树不止一棵 刚选取代价最小的那棵作为最终的组播树 k o m p e l l a 2 6 提出了一个构建时延约束斯坦利树的分布式算法 该算法要求每个节点 维持 个到网络中其它节点的最小时延距离向量 首先初始化为包含组播源点的一棵 树 然后每次向树中添加一个组播终点 直到所有的组播终点都添加完为止 所要添加 的组播终点按如下方法选择 组播源点发出一个f i n d 报文 当某点收到此报史后 就确定一个连接非树组播终点的路径 该路径满足时延约束 并且代价函数最小 该 点发送一个包含候选路径标识的r e s p o n s e 报文给组播源点 当组播源点收到所有的 响应报文后 就从候选路径中选取一条最佳路径 添加到树中 多次重复上述过程直 至建立起一棵组播树 w i d y o n o 2 7 1 采用受限b e l l m a n f o r d c b f 算法求解受限斯坦利树 性能较优 但计 算时间随着网络规模的增大而里指数增长 般用作评价解决同类问题的参考模型 f 6 智能化算法 随着近年来遗传算法 人工神经网络算法等的兴起 科学工作者对这些算法的模型 理论和应用技术等一系列问题进行了深入的研究 这些算法被称为现代优化算法 其主 要应用对象是优化问题中的n p 问题 由于s t e i n e r 树问题是n p 完全问题 为此近年 1 3 巾北大学学位论文 来许多学者崩这些算法来解决这个问题 文献 2 8 和 2 9 提出了基于神经网络的路由选 择方案 研究了基于s t e i n c r 树或受限于部分q o s 参数的s t c i n e r 树的路由选择问题 但未考虑受限于多个q o s 参数的路由选择问题 而在基于遗传算法的组播路由算法中 目盼采用标准遗传算法 而标准遗传算法存在过早收敛和进化后期搜索效率低的不足 1 5 本文的主要研究内容 本文根据q o s 组播路由选择问题的特点 结合遗传算法的寻优特征 从不同角度对 遗传算法进行改进 旨