（计算机软件与理论专业论文）基于遗传算法的qos组播路由问题研究.pdf

北京交通大学硕士学位论文 y 5 8 8 2 1 8 摘要 随着 i n t e rn e t 的飞速发展，涌现出许多新型的通信需求，如视频 点播、多媒体会议、远程教学等。这类应用一般涉及多个用户，需 要网 络提供组播 ( m u tt ic as t ) 支持， 并且 保证服务质 量( q o s : q u a l it y o f s e r v i c e ) . q o s组播路由 是实现这类应用的关键技术之一，因而成为 研究热点，其目 标是寻找一棵连接源节点和多个目的节点的组播 树，使得树的代价最小并且满足各种q o s 需求。 q o s 组 播路由 问 题的 求 解 方 法 包括 启 发 式 算 法和 遗 传算 法 ( g a , g e n e t i c a l g o r i t h m ) ， 本文主 要 研究了 遗传算 法在组播路由问 题中的 应 用。遗传算法是一种全局寻优技术，适合于在复杂而庞大的搜索空 间中寻找最优解， 它原理简单，易于并行，广泛用于许多 n p难题 求解的领域。因 此，遗传算法为 q o s组播路由问 题的求解提供了新 的途径。 针对时延受限的组播路由问 题，本文提出了一种基于路径编码 的改进的遗传算法。设定了有效的指数定标技术和自 适应的变异策 略，克服了早熟收敛。仿真试验表明，改进的遗传算法能够以较少 的遗传代数获得代价较低且满足时延约束的组播树，具有较好的费 用性能和时间性能.能够满足实际应用的要求。 本文还将正交试验设计方法与遗传算法相结合，提出了一种求 解时延受限组播路由问题的正交遗传算法。正交遗传算法的优点在 于利用正交表的均匀分散性合理安排交叉方案，使得交叉算子在遗 传空间内执行的搜索更具有代表性，更容易发现性能优良的个体， 从而提高收敛速度。仿真试验对正交遗传算法和改进的遗传算法进 行了比较，发现采用两种算法求得的最优组播树的性能十分接近， 但正交遗传算法需要的遗传进化代数更少，试验表明，正交遗传算 法性能稳定，具有较快的收敛速度。 最后，对全文进行总结，并对下一步研究工作提出了 展望。 关锐词 组播 q o s 组播路由 s t e i n e r 树 时延约束 遗传算法 北京交通大学硕士学位论文 ab s t r a c t t h e d e v e l o p m e n t o f i n t e r n e t h a s g i v e n r i s e t o m a n y n e w c o m m u n i c a t i o n s e r v i c e s s u c h a s v i d e o b r o a d c a s t i n g , m u l t i m e d i a c o n f e r e n c e , re m o t e e d u c a t i o n. i n g e n e r a l , t h e s e a p p l i c a t i o n s re q u i r e t h e n e t w o r k t o p r o v i d e m u lt i c as t s u p p o rt a n d g u a r a n t e e t h e q u a l it y o f s e r v i c e s ( q o s ) . q o s m u l t i c a s t r o u t i n g i s t h e k e y t e c h n o l o g y i n t h e s e a p p l i c a t i o n s a n d b e c o m e t h e f o c u s o f r e s e a r c h . t h e g o a l o f t h e p r o b l e m i s t o f i n d a m u lt i c a s t t r e e c o n n e c t i n g t h e s o u r c e n o d e a n d m u l t i p l e d e s t i n a t i o n n o d e s w h i c h h a s g o o d p e r f o r m a n c e a n d s a t i s f i e s d i ff e r e n t q o s re q u i r e m e n t s t h e c u r re n t a p p r o a c h e s f o r m u l t i c a s t r o u t i n g p r o b l e m i n c l u d e h e u r i s t i c a l g o r i t h m s a n d g e n e t i c a l g o r i t h m . i n t h i s th e s i s , t h e a p p l i c a t i o n o f g e n e t i c a l g o r i t h m i n t h e q o s m u l t i c a s t p r o b l e m i s s t u d i e d . t h e g e n e t i c a l g o r i t h m i s a g l o b a l o p t i m i z a t i o n m e t h o d w h i c h c a n p e r f o r m s e a r c h i n c o m p l e x a n d l a r g e s p a c e . d u e t o i t s a d v a n t a g e s o f s i m p le i m p l e m e n t a t i o n a n d p a r a l l e l i z a t i o n , g e n e t i c a l g o ri t h m h as b e e n a p p l i e d s u c c e s s f u l l y i n m a n y f i e l d s o f n p c o m p l e t e p r o b l e m s . t h e r e f o r e , g e n e t i c a l g o r it h m p ro v i d e s a n e w d i r e c t i o n f o r t h e q o s m u lt i c as t p r o b l e m . a n i m p r o v e d g e n e t i c a lg o ri t h m b a s e d o n p a t h e n c o d i n g i s p r o p o s e d f o r d e l a y - c o n s t r a i n e d m u l t i c as t r o u t i n g p r o b l e m ( d c m r ) . b y u s i n g e ff e c t i v e e x p o n e n t s c a l i n g t e c h n i q u e a n d s e l f - a d a p t m u t a t i o n o p e r a t i o n , t h e i m p r o v e d a l g o r i t h m h as o v e r c o m e p r e m a t u r it y s u c c e s s f u l l y s i m u l a t i o n s s h o w t h e p r o p o s e d a l g o ri t h m c a n g e t l o w c o s t m u l t i c a s t t r e e w i t h o u t v i o l a t i n g t h e d e l a y c o n s t r a i n t i n f e w e r g e n e r a t i o n s . wi t h b e tt e r c o s t a n d c o n v e r g e n c e p e r f o r m a n c e , t h e p r o p o s e d a l g o r it h m c a n m e e t t h e d e m a n d s o f p r a c t i c a l a p p l i c a t io n s a n o rt h o g o n a l g e n e t i c a l g o ri t h m i s p r e s e n t e d w h i c h i n c o r p o r a t e o r th o g o n a l e x p e r im e n t d e s i g n m e t h o d i n t o t h e c r o s s o v e r o p e r a t i o n . t h e c r o s s o v e r i s a r r a n g e d a c c o r d i n g t o o r th o g o n a l t a b l e . t h e o rt h o g o n a l c r o s s o v e r p e r f o r m s r e p r e s e n t a t i v e s e a r c h i n t h e g e n e t i c s p a c e , s o i t c a n f i n d e x c e l le n t i n d i v i d u a l m o r e q u i c k l y . i n s i m u l a t i o n s , t h e i m p r o v e d a l g o ri t h m a n d t h e o rt h o g o n a l a l g o ri t h m a r e c o m p a r e d , b o t h c a n f i n d m u lt i c as t t r e e w i t h g o o d p e r f o r m a n c e , b u t t h e l a tt e r n e e d l e s s e v o l u t i o n s t e p s . i t s h o w s t h a t t h e o rt h o g o n a l a l g o ri t h m i s s t a b l e a n d h a s f a s t e r c o n v e r g e n c e s p e e d i n t h e l as t , t h e t h e s i s i s s u m m a r i z e d a n d t h e n e x t r e s e a r c h w o r k i s p r o s p e c t e d . k e y w o r d s mu l t i c ast q o s m u l t i c a s t r o u t i n g s t e i n e r t r e e d e la y - c o n s t r a i n e d g e n e t i c a l g o ri t h m 北京交通大学硕士学位论文 第1 章 绪论 光纤通信和交换技术的进步大大提高了计算机网络的传输速 率，许多新型的通信业务大量涌现，如电视会议、视频点播、邮件 群发、网络游戏、远程教学等。这类业务一般涉及多个用户，并且 对带宽等网络资源的消耗极大。组播( m u l t i c a s t ) 作为优化带宽的一种 重要手段而受到越来越多的关注。本章首先介绍了组播的工作原理 及实现方式，然后分析组播路由算法的研究现状，最后阐述本文主 要研究问题及章节安排。 1 . 1 组播的工作原理 组播( m u l t i c a s t ) 是一种允许一个或多个发送者( 源节点 ) 同时向 多 个接收者( 目 的节点 ) 传输同 一份数据包的 通信方式。 组播源点把数据 包发送到特定的组播组，只有属于该组播组的地址才能接收到数据 包。因为无论有多少个目标地址，在整个网络的任何一条链路上只 传送单一的数据包，所以组播提高了数据传输速率，极大的节省了 网络带宽。 常用的通信方式还有另外两种:单播和广播。图 1 . 1 为基于三种 通信方式的网络结构和数据传递过程。 单播( u n i c a s t ) 是指传统的点到点通信方式， 在发送者和每一个接 收者之间都需要单独的数据通道。如果一台主机同时给少量的接收 者传输数据，一般没什么问题，但如果有大量的主机希望获得数据 包的同一份拷贝时却很难实现，这将导致发送者负担过重、延迟 长、网络拥塞，而且为了保证一定的服务质量还需要增加硬件和带 宽。 广播旧r o a d c a s t ) 是指在 i p子网内 广播数据包， 所有在子网内的 主机都将收到这些数据包。广播意味着网络向子网主机都投递一份 数据包，不论这些主机是否乐于接收该数据包。然而广播的使用范 围非常小，只在本地子网内有效，因为路由器会封锁广播通信;同 时广播传输增加非接收者的开销，即判断是否为自己 所需数据包花 北京交通大学硕士学位论文 费的时间等等。 目的主机 目的主机 单播 目的主机 目的主机 组播 源主机非目 的主 机目 的主机非目 的主机 广播 图1 . 1三种通信方式数据传递过程比较 1 . 2 组播实现方式 目前网络对组播的支持主要是通过建立是一棵连接源节点和多 个目的节点的组播树来实现的，信息以并行方式沿树枝发送到不同 目的节点，降低了传输时延;而且信息只需在树的分叉处进行复 北京交通大学硕士学位论文 制，这样网络中需要传送的复制信息最少，节省了网络资源。组播 树有 两种基 本类型 1 i : 有源树和共享 树。 1 . 2 . 1 有源树 有源树是组播树最简单的一种形式，有源树的根是组播信息流 的来源，有源树的分支形成了通过网络到达接收站点的分布树( 如图 1 .2 . 1 - 1 、1 .2 . 1 - 2 ) . 有源树也有两种形式:一种是最短路径树，它以最短路径贯穿 网络，即从源节点到所有目的节点都是通过最短路，因此被称为最 短路径树( s p t : s h o rt e s t p a t h t re e ) 。 最短路径树保证了 从源节点到每 个目的节点为最短路，但是全树的费用并不一定是最优的，这里树 的费用是指树中边的费用( c o s t :这里的费用是一个广义上的费用，它 可以根据距离、信道带宽、平均通信量、通信开销、队列平均长 度、 测量到的时 延和其他一些因 素的函 数而计算出 来的 ) 之和。 为达到全树的费用最优，因此有第二种形式的有源树，即覆盖 所有组播成员的一棵最优 s t e in e : 树，s t e in e r 树问 题是从图论中引申 出来的一个优化问 题:在一个连通图中，给定一个节点子集，要求 在图中找到一棵覆盖给定节点子集的费用最小的生成树。s t e i n e r树 的总费用最小，但是从源节点到每个目的节点不一定是最短路。在 网络中的每个节点( 实际是路由 器) 都具有组播功能时， 求解费用最小 的组播树问 题与 s t e i n e r 树问题是等价的。如果组中有多个节点存在 组播需求，需要为每个节点分别建立一棵以该节点为根的组播树， 这会增加网络管理的开销。 1 .2 .2 共享树 组播 树的另一 种形式 是 共享树( c b t : c o r e - b a s e d t re e ) 。 这里， 每 个组只计算一棵生成树，其树根 ( 核心)靠近组播组的中间部位， 要发一个组播消息，主机先将它发往核心，再由核心沿着生成树发 送消息( 如图 1 .2 . 2 ) 。 采用这种方式，只需要为组播组维护一棵生成 树，能够降低存储开销，但付出的代价是生成的组播树对某些组播 源来说可能不是最优的，从而导致延时增加。还有，共享树可能会 北京交通大学硕士学位论文 将来自 多个组播源的流量聚集在靠近核的部分链路上，造成网络拥 塞，降低服务质量。 主机s主机c 图1 .2 . 1 一 1 主机a的 有源树 接收器 _ 上 机d主机c 图1 .2 . 1 - 2主机b的有源树 一一一一一一一一鉴冬里途翌过 图1 .2 .2共享树 1 .3 组播路由算法研究现状 为了进行有效的组播通信，确定组播路由是非常关键的。组播 路由 算法就是用来确定组播树。组播树是通过在每个路由器设置路 由 表建立的，路由表上给出了为使信息传送到组成员，此路由 器应 该选择那个邻接节点。由于网络的动态变化，每个路由器的路由表 也需要定期更新。此外路由表的设置要保证不能有回路的产生。下 面对组播路由算法进行介绍。 1 .3 . 1 s t e i n e r 树算法和c b t算法 根据组播树构造方式的不同，组播路由 算法可分为两种:s t e i n e r 树算法和 c b t算法。在构造组播树时， 一般以 树的“ 费用”作为评 价组播树性能的标准。组播树的费用是指树中所有链路费用的总 和。这里链路的费用是一个广义的费用，它可以指链路上的时延、 可用资源、带宽、价格等等。在实际应用中，一般要求确定的路由 要有效利用网络资源，为此要求组播树的费用最小。前面提到，在 网络中寻找覆盖给定节点集合的费用最小的生成树问题在数学上被 称为 s t e i n e r 树问题，这是一个 n p完全问 题，即一般来说，最优算 北京交通大学硕士学位论文 法无法在多项式时间内完成。因此，需要寻求有效的启发式算法， 降低算法难度，在性能上逼近理论算法。目 前，s t e i n e r 树问题的启 发式算法很多lz - s l ， 它们都可 用来 求解代价最小组播树， 是组播路由 算法的一个重要研究方向。 中心树算法是近年来提出的构造组播树的一种新方法，它首先 由w a l l提出 阁 ， 以 选定中 心为 树 根， 其 他 组 成 员按 照最 短路 的原 则与中心建立连接，构造成为一棵由所有发送节点共享的树， c b t 不具备广播特性，即数据只发向明确发出加入组请求的节点，避免 了广播式算法运行时大量无效分组的扩散。由于构造和管理多中心 c b 丁的复杂性，该方法目 前还没有成熟的结论。 1 . 3 . 2 静态路由算法和动态路由算法 根据组播树是否随着网络拓扑变化，组播路由算法有静态和动 态之分。静态组播路由算法针对初始组播成员构造一棵组播树，它 不能根据当前实际传输量和拓扑变化来做拓扑选择，而是按初始设 计好的路由传送。但真实网络中存在许多动态变化，如网络拓扑结 构的变化，组成员的变化等。因此动态组播路由算法显得非常重 要。构造适应组成员动态变化的算法有三种方式:一种是构造一棵 性能优化的初始组播树，成员变化之后对树采取最小的变化，如文 献 7 中 的 算法， 成员的 加入通过建立节点到 树的 最短路由 完成; 成 员的离开仅删除树叶节点，如果删除产生一个非成员树叶，该算法 删除该节点，直到不存在非成员树叶。另一种是成员变更后，对整 个组重新进行路由确定，这将对组中原来成员通信产生干扰，当成 员的 变换剧烈时， 这种方法是不实 用的。 文献 8 l 给出了 一种改 进算 法，首先节点的加入和离开仿照前面第一种方式实现，但在树的局 部范围内，考察节点的加入和离开对树的累计损伤，当这种累计损 伤超过一定限制条件时，在局部范围内重新优化路由，通过改变限 制条件达到树的优化和计算时间、复杂性之间的平衡。第三种是构 造一棵富于弹性变化的次优树，即最短路径树，每个组成员之间相 互独立选择最短路由，因此树的性能不受组动态变化的影响。 北京交通大学硕士学位论文 1 .3 .3 集中式算法和分布式算法 根据组播树的实现方式，组播路由算法又可分为集中式路由 和 集中式算路由。集中式组播路由在掌握整个网络的拓扑结构后，确 定组播路由。集中式组播路由一般都是源路由算法( s o u r c e - b a s e d r o u t i n g ) ，即源节点通过某个链路协议获得完整的网络拓扑结构信 息，进行路由的计算。分布式路由不需要每个组成员掌握整个网络 的拓扑，每个组成员在只具有局部信息条件下就可参与路由的确 定， 1 . 3 . 这对大型网络的组播路由是十分有利的。 4 q o s 组播路由算法 随着网络技术的迅速发展，视频点播、多媒体会议、远程教 学、网络游戏等己经开始应用。这些应用涉及到网络的服务质量 ( q u a l i t y o f s e r v i c e ， 简称q o s ) 问 题。 服务质量( q u a l i t y o f s e r v i c e ， 简称q o s ) 是网络在传输业务流时， 业务流对网络服务的需求的集合，其中业务流是指与特定q o s相关 的从源到目 的地的分组流。也就是说，q o s是应用业务对网络传输 服务提出的一组可度量的要求，主要包括带宽， 端到端延迟、分组 丢失率、抖动、花费等。网络在传输相应的数据业务时，必须满足 这组要求。其中，端到端时延是实时通信应用中很基本的一个方 面。对于实时通信来说，如果时延过长，就会引起用户视觉和听觉 上的不适，甚至引起语意的无法理解。而对于视频点播来说，则要 保证一定的图像质量，网络必须提供足够的带宽和可以接受的数据 丢失率。 对于 q o s组播路由问题，一般有两种 q o s要求，即最优化 ( o p t im iz a t io n ) 和 满足 给定的 约 束条 件 ( c o n s t r a in t ) 。 这 些要求的 组合就 形成了 用户对网络提出的 各种 q o s要求。 如要求组播树中 源节点到 各目的节点的时延不高于某个限制值，但组播树的费用要求最小， 这就是组播的时延受限和组播树优化的组合。组播路由问题中研究 最多的是受限 组播树( c o n s t r a i n e d m u l t i c a s t t r e e ) ， 其中 包括时延受限 最 小 代 价组 播 树问 题 9 - 13 ， 带宽 受限 组 播 树问 题 14 -1 5 ， 时 延 抖动 受限问 北京交通大学硕士学位论文 题 13 等。 q o s组播路由问 题已 被证明是 n p完全问 题，具有较高的复杂 性，因而遗传算法被应用到该问题的求解中。遗传算法是模拟生物 在 自 然环境中的遗传和进化过程而形成的一种 自 适应全局优化概率 搜索算法 1 6 ， 适合于在复杂而庞大的 搜索空间中 寻找最优解， 它 原理简单，鲁棒性强，易于并行分布处理，广泛用于求解各种 n p完 全问题。因 此，遗传算法为 q o s组播路由问 题的求解提供了新的途 径。 文献 1 7 - 1 9 ) 应用遗传算法求解无约束代的 s t e i n e : 树问 题， 文献 2 0 - 2 9 应用 遗传算 法求解时 延受限的 组播路由问 题， 文献 3 0 应用遗 传算法求解时延抖动受限的组播路由问 题， 文献 3 1 应用遗传算法求 解带度约束的组播路由问 题，文献 3 2 - 3 4 应用遗传算法求解带综合 q o s约束的组播路由问题，包括带宽、时延、时延抖动、包丢失率 等多 个q o s 约束的 组 合。 1 . 4 本文主要研究问傲及章节安排 本文主要研究遗传算法在 q o s组播路由问 题中的 应用。 首先介 绍了 q o s组播路由问 题的 基本概念和相关理论，归纳评价了 求解该 问题的启发式算法和遗传算法。然后，将求解组播路由问题的遗传 算法按照编码方式进行归类，比较不同遗传算法的优缺点。针对时 延受限的组播路由问题，在文献算法的基础上提出了一种改进的遗 传算法，仿真试验表明改进的算法有效地克服了文献算法的早熟收 敛;本文还将正交试验设计法与遗传算法相结合，提出了一种正交 遗传算法，并通过仿真试验对算法性能进行验证。本文章节安排如 下: 第二章主要阐述q o s 组播路由问 题的 基本概念，定义q o s组播 路由问 题的 数学模型。并按照优化目 标和约束条件对 q o s组播路由 问题进行分类，总结归纳了求解该问题的启发式算法和遗传算法。 第三章重点介绍了时延受限组播路由问题，描述了该问题的网 络模型。分析评价了求解该问题的启发式算法和遗传算法。并按照 组播树编码方式的不同，将求解组播路由问题的遗传算法分为按节 a t 京交通大学硕士学位论文 点编码、按边编码、按路径编码、按树编码四类，并对算法进行了 分析和优缺点比较。 第四章针对时延受限的 q o s组播路由问 题， 提出了 一种改进的 遗传算法。通过设定有效的指数定标技术和自 适应变异策略，克服 了算法的早熟收敛。通过仿真试验对算法性能进行了验证，并分析 不同因素对算法性能的影响。 第五章将正交试验设计与遗传算法相结合，提出了一种正交遗 传算法用于求解时延受限组播路由问题。正交遗传算法采用正交表 安排设计交叉方案。仿真试验将正交遗传算法与第四章提出的改进 算法进行了对比，结果表明正交遗传算法性能稳定，具有更快的收 敛速度。 第六章对全文内容进行总结归纳，对进一步研究工作进行展 望。 北京交 通大学硕士学位论文 第2 章 q o s 组播路由问题 目前广泛发展的新型通信业务如视频点播、电视会议、远程教 学等一般涉及多个用户，且对服务质量有着较高要求。 q o s组播路 由问题主要研究在满足服务质量需求的情况下怎样更好地实现组播 功能， 成为研究的热点。本章首先介绍 q o s组播路由问 题的基本概 念，然后描述该问 题数学模型定义， 根据 q o s约束条件对组播路由 问题进行分类， 最后对求解 q o s组播路由 算法的 几种启发式和遗传 算法进行了归纳和评价。 2 . 1 q a s 组播路由的基本概念 q o s组播路由 就是根据给定的 q o s度量参数，选择有足够网络 资源的链路来传送组播数据。路由有两方面的基本内容:一是收集 网络状态信息并不断更新信息，另一是根据已有信息来为新的连接 请求选择一条合适的路由。一个路由 算法的性能极大的取决于信息 收集的好坏。 2 . 1 . 1 斌权圈模型 网 络的拓扑结构和资源容量可以抽象为一个赋权图( v , e ) ，其中 节点( 吟代表网络中的交换设备，边( e ) 代表传输链路。对于大多数 实际网络而言，传输链路一般都是不对称的，这里为了简化问题， 假设链路对称，因此赋权图的边是无向的。每一条链路都有一个对 应于相关 q o s度量的 状态， 每一个节点也有相应的状态，节点的 状 态信息可以单独表示出来，或者也可以折算到与节点相连的链路状 态中去。 2 . 1 .2 状态信息 1 )本地信息 每一个节点都必须保持其最新的本地信息，包括链路传输时 延、排队时延、输出链路的剩余带宽及其他网络资源的可用信息。 北京交通大学硕士学位论文 2 )全局 信息 所有节点本地信息的总和就构成了全局信息。每一个节点可以 用链路状态协议或者距离一向量协议来发布、取得全局信息。链路 状态协议通过让各节点广播其本地信息来确定网络的拓扑结构和各 链路的状态。距离一向量协议通过相邻节点定期交换其距离向量来 取得并扩散全局信息。每一个节点保持的全局信息，总是对现有网 络状态的一种近似。这是由于信息传输时延造成的。而时延的不可 避免性表明这种不确定性会随着网络规模的增加而不断扩大。 3 )状态信息的聚合 因为任何物理设备的存储资源和处理能力都是有限的，所以对 全局信息的精确保存，会带来扩展性问题，于是降低全局信息的规 模就变得十分重要。这可以通过把一个具有层次性结构的大型网络 的局部信息进行聚合来完成，即把包含几个物理节点的组抽象为一 个逻辑节点，而逻辑节点又可以进一步聚合成更高一级的逻辑节 点，如此反复下去。在聚合过程中，必须把下层节点的网络度量性 能聚集为本层逻辑节点的度量特性。这种过程是复杂的，而不同的 聚集方法对状态信息的影响也是一个开放性的问题。 2 . 1 .3 q o s 度量 在q o s 组 播路由 中， 路 径p r ( u , v ) = ( u , i, j , 二 ， k , v ) ， 用d ( u , v ) 表示对 应链路( u , v ) 的 度量，则q o s 度量可以 按性质分为以 下三类: 1 )最小性q o s 度量 如果d ( u , v ) = m in ( d ( u , i ) , d ( i , j ) , - . , d ( k , v ) ) ，那么度量由传输路径中 的瓶颈决定，即此度量仅与路径上的某个瓶颈链路的 q o s度量有 关，如剩余带宽、缓冲空间等。 2 )可加性q o s 度量 如果d ( u , v ) = d ( u , i ) + d ( i , j ) 十 + d ( k , v ) ，那么度量由传输路由中所 有链路的特性共同决定，如时延、时延抖动、费用等。 3 )可乘性q o s 度量 如果d ( u , v ) = d ( u , i ) x d ( i , j ) x - . - x d 伏 ， ， ) ，那么度量为所有链路 北京交通大学硕士学位论文 对应度量的乘积，如包丢失率等。 2 .2 q o s 组播路由的 数学 模型 q o s 组播路由 是一种基于数据流q o s 请求和网络可用资源进行组 播路由的机制，在其路径选择标准里可能包含可用带宽、链路和端 到端路径利用率、资源消费量、时延、跳数以 及抖动等q o s参数。 其主要目标包括两点:( 1 )为每一个接纳的q o s业务连接请求，找 到满足其q o s要求的 组播路由 : ( 2 ) 优化全局资 源利 用率， 平衡网 络 负载，从而最大化网 络接受其他q o s 请求的能力。该问 题数学模型定 义如下: 定义 1 - 1计算机网 络通常可以 表示为无向 赋权图g ( v , e ) ， 其中 v是节点集，可以表示交换机、路由器和主机，也可以是子网:e 是边集， 代表通信链路，n= 1 v 1 , l = 1 e 1 ， 边。 e e，s e v 为组播 源点，dc_ v - ( s ) 为 组播目 的 节点 集合，r , 表示正实数 集，r 表 示非负实数集。 定义1 - 2对于任一条链路e e e，定义四种度量: 1 )时 延函 数 d e l a y ( e ) : e - * r , ; 2 )代 价函 数c o s t ( e ) : e 峥r 十 ; 3 )带宽 函 数 b a n d w id th ( e ) : e - * r ,; 4 )时 延 抖动函 数 d e l a y - j i t t e r ( e ) : e - + r . 定义1 - 3对于任一网络节点， ( = v，也定义四种度量: 1 )时 延函 数 d e l a y ( v ) : v - * r , ; 2 )代价 函 数 c o s t( v ) : v -4 r ,; 3 )包丢失率函 数 p a c k e t - l o s s ( v ) : v - i r ,; 4 )时延抖动函 数 d e l a y - j i t te r ( v ) : v -4 r + . 定义 1 - 4对于给定的源点、 e v ，目的节点集合d, s 和d组成 的 组播树t ( s , d ) 存在下列关系: 北京交通大学硕士学位论文 1 ) d e la y (p t (s ,d ,) 一 y eep (s,d ,) d e lay (e ) + 艺 ，。 。 ，。 ) d e lay (v ) ， 2 ) c o s t(t (s ,d ) 一 l r e.t (s,d ) c o s 1(e ) + y- ,et (s,d ) c o s t(v ) ， 3 ) b a n d w i d th ( p t ( s , d ; ) ) = m i n b a n d w id t h ( e ) , e e p t ( s , d) ; 4 ) d e la y 一 、 itte r ( p t (s , d ; ) =艺d e la y 一 ， itte r (e ) +艺d e la y 一 ， itte r (v ) e e 矜( s , q) v e 丹( s , 口) 5 ) p a c k e ， 一 lo s s ( p ., (s , d ; ) 一 ， 一1 1 (， 一 、k e 一 lo s s (v ) v e p ( , , d , ) 其中，p 1 . ( s , d , ) 为组播树t ( s , d ) 上源节点， 到目 的节点d ， 的路 径。 本模型只考虑网络节点的包丢失率 ( 因缓冲溢出) ，而忽略链路 的包丢失率，这与实际情况相符。 定义 1 - 5 q o s组播路由问 题可定义为:网 络图g ( v , e ) ， 组播 源点、 e v，组播 目的节点集合 dc v - ( s ) i ，延时函数 d e l a y ( ) e r , ，延时抖动函数d e l a y _ j i tt e r ( .) e r + ，代价函数 c o s t ( ) e r ,，带宽函数b a n d w id th ( .) e r ， 和包丢失率函数 p a c k e t _ l o s s ( -) 。 r + ， 寻 找 一 棵 组 播 树t ( s , d ) 满 足: 1 ) 延时 约 束: d e la y ( p t ( s , d , ) ) !g d t , ; 2 ) 带 宽 约 束:b a n d w id th ( p t ( s , d , ) ) 2 b ; 3 ) 延时 抖动 约束:d e l a y _ j it t e r ( p t ( s , d , ) ) 00, if f (x )+ c ,; _ 0 式中，c ,o o 为 一 个 适当的 相对 较小的 数。 b ) 求最小值问题，作下述转换: f (x ) c .一 a x ),: f ( x 卜c m - 1 ( x) ac ox 式中，c o x 是一个适当的 相对较大的数。 可取为迄今为止进化过 程中刀 x ) 的最大值。 2 ) 适应值函 数定标 在遗传算法的实际应用过程中，可能会出现两种不利情况:一 是早熟收敛，即在遗传进化的初期少数适应值较高个体的出现导致 这些个体在群体中占有较大比例;使得产生新个体的交叉算子不能 发挥作用，导致群体多样性降低，发生早熟收敛。二是随机漫游， 北京交通大学硕士学位论文 即群体的平均适应值已接近最佳个体适应值，最佳个体和其他大多 数个体在选择过程中有几乎相等的选择机会，从而使目标的优化过 程趋向无目标的随机优化过程。 为了避免出现这两种情况，可对适应值进行定标。主要方法有 以下几种:线性定标、乘幂定标、指数定标。 a )线性定标 f =a f+b 式中，f是原适应值，f是定标后的新适应值，a 和b 是系数。 对于系数的选取一般需要满足以下两个条件: 条 件一: 定 标 后 全 部 个 体的 新 适 应 值f o x 要 等 于 其原 适 应 值平 均 值f vg ， 即f ,x 二 f s 条 件二: 定 标后群体中 新的 最大适应值凡 队 要等于原平均适应值 f , 的 指 定 倍 数， 即f . . = c . f . 8 。 式中 ， c 为 最 佳 个 体的 期 望 复 制 数量，对于群体规模大小为 5 0 -1 0 0个个体的情况，一般取 c=1 . 2一2。 b )乘幂定标。 乘幂定标的公式为: f =f k 即新的适应值是原有适应值的某个指定乘幂。幂指数k 与所求的 问题有关。 c )指数定标。指数定标的公式为: f = e x p ( 一 迎) 即新的适应值是原有适应值的某个指数。式中系数9决定了选 择的强制性，q 越小，原有适应值较高的 个体的新适应值就越与其 他个体的新适应值相差较大，越增加了 选择该个体的强制性。 3 ) 惩罚函数法 惩罚函数法的表达方法主要针对带约束问题。在运用遗传算法 对有约束问题求解的过程中，需要考虑每一代种群中的个体是否满 足约束条件。惩罚函数法的目的就是设法对个体违背约束条件的情 况给予惩罚，并将惩罚体现在适应值函数设计中，把一个约束优化 北京交通大学硕士学位论文 问题转换为一个附带考虑代价或惩罚的非约束化问题。 令 选择算子 选择是从群体中选取优胜的个体，淘汰劣质个体的的操作。选 择建立在对个体的适应值进行评价的基础上。选择的主要目的是避 免有用遗传信息的丧失，提高全局收敛性，其操作策略与编码方式 无关，主要的选择算子有以下几类: 1 )适应值比 例选择法 又称为轮赌法，最基本最常用的选择方法，个体的选择概率与 其适应值成比例。 2 )最佳个体保留法 该方法是将群体中适应值最高的个体不进行配对交叉而直接复 制到下一代。这种方法的优点是进化过程中某一代的最优个体可以 不被交叉和变异操作破坏。最佳个体保留法可视为选择操作的一部 分。是遗传算法收敛性的一个重要保证条件。 但另一方面，也容易 使得某个局部最优个体不易被淘汰反而快速扩散，从而使得算法的 全局搜索能力不强。所以该法一般要与其他一些选择操作方法配合 起来使用，才可获得良 好效果。 3 )期望值选择方法 期望值选择方法的思想如下: a )计算群体中 每个个体在下一代生存的期望数目 : m= f ! f; b )若某个体被选中并要参与配对和交叉，则它在下一代中的生 存数目 减去 0 .5 ;若不参与配对和交叉，则该个体的生存期 望数目 减1 ; c )在 b ) 的 两 种情况下， 若一个个体的 期 望值小 于零时则 该个体 不参与选择。 4 ) 排序选择方法 排序选择方法是指在计算每个个体的适应值后，根据适应值大 小顺序对群体中个体排序，然后按照事先设计好的概率表顺序分配 给个体，作为各自的选择概率。 北京交通大学硕士学位论文 5 ) 联赛选择方法 该方法的操作思想是:从群体中任意选择一定数目的个体 ( 联 赛规模) ，其中适应值最高的个体保存到下一代。这一过程反复执 行，直到保存到下一代的个体数达到预先设定的数目 为止。 6 )排挤方法 d e j o n g 提出的排挤选择方法是新生成的子代将代替或排挤相似 的父代个体，提高群体的多样性。 今 交叉算子 交叉算子是遗传算法产生新个体的主要方法，在遗传算法中起 着关键作用。交叉算子设计和实现与具体问题密切相关，并要和编 码设计一同考虑，主要包括交叉点的位置和如何交换部分基因。基 本的交叉算子有以下几种: 1 )一点交叉: 在个体串中随机设定一个交叉点，实行交叉时， 该点前或后的两个个体的部分结构进行互换，并生成两个新 个体; 2 )两点交叉:设置两个交叉点，其余与一点交叉类似; 3 )多点交叉:此法较少采用，因为多点交叉不能有效的保存重 要的模式; 4 )均匀交叉:是指两个配对个体的每一个基因座上的基因都以 相同的交叉概率进行交换，从而形成两个新的个体; 5 算术交叉:是指由两个个体的线性组合而产生两个新的个 体。为了 能够进行线性组合运算， 算术交叉的 操作对象一般 是由 浮点数编码所组成的个体。 6 )启发式交叉:需要涉及应用领域知识。 . 变异算子 变异算子是遗传算法产生新个体的另一种方式，引入变异算子 的目 的之一是加强遗传算法的局部搜索能力，当遗传算法通过交叉 算子已 接近最优解领域时，利用变异算子的局部随机搜索能力可以 加速向 最优解收敛;二是使遗传算法维持群体多样性，以防止未成 熟收敛。 常用的变异算子有如下几 种: 一一一一一j掣 * v t * 9 * 3 l 一一一 1 ) 基 本 变 异 算 子 : 对 群 体中 的 个 体 码串 随 机 挑 选 一 个 或 多 个 基 因座并对这些基因座的值作变动: 2 )自 适 应 变 异 算 子 : 该 算子 与 基 本 变 异 算 子 的 操 作内 容 类 似， 唯一不同的是变异概率不是固定不变，而是随群体中个体的 多样性程度而自 适应调节; 3 )均匀 变 异: 是指 分 别 用 符 合 某一 范 围内 均匀 分布 的随 机 数， 以某一较小的概率来替换个体编码串中各个基因座上的原有 基因值; 4 )非 均匀 变异:由j a n i l o w和 m i c h a l e w i c z 提出，目 的 是改 进 遗传算法对重点搜索区域的局部搜索性能。非均匀变异算子 有两种方式，一种是变异范围与演化代数相关联，随着演化 代数的增加，变异范围越来越小;另一种是变异范围与个体 解的质量相关，适应值大的个体在较小范围内搜索，适应值 小的个体在较大范围内搜索。 令 控制参数的确定 遗传算法中需要确定的控制参数主要有个体编码串长度l 、群体 大小m、交叉概率p : 、 变异概率p , 、进化代数t 等。 这些参数对遗 传算法的运行性能影响较大，需要认真选取。 1 )编码串长度1 。 使用二进制编码来表示个体时，编码串 长度l 的选 取与问题所要求的求解精度有关;使用浮点数编码来表示个体 时，编码串长度i 与决策变量的个数。 相等;使用符号编码来表 示个体时，编