（计算机应用技术专业论文）基于qos的选播路由算法研究.pdf

摘要 选播是一种新型的网络服务模型，它能够使用户通过一个选播地址访问到该地址所 标示的一组服务器中对用户来说“最近的 一个。选播服务的应用能够增强网络服务的 可用性、提高网络的服务质量。q o s ( q u 觚i t ) r 吣f s e r v i c e ) 路由被认为是保证网络服务质量 的一个不可缺少的路由技术，其目标是寻找满足约束条件的路径同时有效利用网络资 源。选播一经提出，它的q o s 保证即引起了研究者的兴趣。 本文首先介绍了课题的研究背景及意义，详细介绍了选播通信服务的研究现状，然 后阐述了选播通信服务、q o s 路由及遗传算法的相关理论基础知识。在分析国内外现有 q o s 选播路由算法的基础上，针对时延约束代价最小的q o s 选播路由问题，改进了基 于遗传算法有时延约束的q o s 选播路由算法，算法中采用加权深度优先搜索和轮盘赌 相结合的方法来保证初始种群的多样性：算法中设计了一种新的适应度函数，函数的设 计充分考虑了时延和代价的关系，满足时延约束且时延和代价最小的个体适应度值大， 反之适应度值则较小；算法中采用了指导变异的方法，通过指导变异操作加速算法的收 敛速度。为了均衡网络资源的利用、减少网络拥塞的发生，改进了基于随机方法负载均 衡的q o s 选播路由算法，算法中利用网路均衡度和服务器负载这两种度量作为路由选 择的依据，即通过对网路均衡度和服务器负载进行线性加权，进而把这两种度量转化为 一种度量作为选择目的节点的依据，然后通过随机策略实现路由选择和网路资源的均衡 利用。 最后，对算法进行了仿真实验。实验结果表明：第一种算法在较小的进化代数内能 够收敛到全局最优解或次优解；第二种算法所求得路径的时延与a n y c a t - r o u t i n g 算法相 差不多，但它能够较好地平衡网络资源的利用，减少网络拥塞的发生并具有较高的请求 接受率。因此，两种算法都是有效的和可行的。 关键词：选播，q o s 路由，遗传算法，随机方法，负载平衡 r e s e a r c ho nq o s a n y c a s tr o u t i n ga i g o r i t h m f 觚gs h i y i ( c 0 n 咖p u t e fa p p l i c a t i o nt c c h n o l o g y ) d i r e c 钯db ya s s o c i a ：t ep r 0 w e id o i l l ；p i n g a s s o c i a ：t cp r 0 l ik e w e n a b s 仃a c t a n y c a s ti san e wt y p e0 f 饿翻砌r k r v i c c u s e 岱c 趾v i s i tt h e n c a r e 蚶s e n ，c ri na 印u p o fs e r v e r sb ya n 邺，c a s ta d d r e s s 。t h e 髑eo f a 1 1 y c a s tc 被e r 山a l l c e 也ea v a i l a b i l 时o fn e t w 哦 s e r v i c 豁锄di l l l p r o v et l l eq u a l i t y0 fn e t w o r k r v i c 髓a tt h es 锄et i l l 舱，q o s u t i n gi sa l s 0 c 0 璐i d e 砌嬲孤硒p o n a n tr o u t i n gt e c h n o l o 鼢w l l i c hc 趾g u 獭眦e en l eq 谢时o f i c e n e g o a lo fq o sr o u t i n gi st 0f i n d 恤p 柚删c h 咖m e e tm er e 嘶c t i v ec o n d i t i o 姬锄db c e 航c t i v ei nl l s i n gm en e t 、o r k 比s o u r c e s q o s 锄y c a s tr 0 岫l gh 嬲a n r a c t e d 廿1 ei n t e r e s to f r e s e a r c h c r sw h e ni tw 终p i 0 p o s e da tf i i 赋 i n 也i sp a p e r ；w e 痂娥i i i d d i u c et l l eb a c 蜒群衄订a n ds i 鲥f i c a i 雠o ft h i sp r 而e c t ，觚d 血e n m a l ( eap r o f o u n ds 眦ya _ b o u tq o s 锄y c a s tr 0 砸n g a 舭r 也i a t ，w e 蛔d u c et ：h eb 鹤i c t i l e o r e t i c 出k n o w l e d g ea b o u t 觚y c a s t ，( 沁s l i t i l l g 锄dg e l l e t i cm g o r i t i l m b a s e do nt 1 1 e a l l a l y s i s o f e x i s t i n g d o m e s t i ca n d 锄朋枷咖a lq o s 锄y c a s tr o u t i n g a j 9 0 r i 廿l n l ，a d e l a y c o l l s 枷觚dl e a s t - c o s t 觚y c a s tr o u t h l gd 1 9 0 r i t l l i nb a s e do ng e n 舐ca 1 9 0 r i t l l i ni s i m p r 0 v e d h ln l i sa l g o r i t l l i n ，d e p 也f i r s t a r c h 、i n lw e i g h ta n d 坞辩l e c t i o nm e t l l o do f r o u l e t t ea r eu s e dt 0m a l ( e 跚r et l l e 嘶g i n a lc o l o n yd i v e 瑙i 够an e wf i t i l e s s 鼬i o ni s p 即s e d ，i l lw 嫩c h 缸l ef e l a t i o l 毽l 卸b e t 、 雠n 吐l ec o s ta l l d 廿l ed e l a ya r ：et a k e n 血l la c c o 哑t h e p a ：t t lw i l i c hc a l lm e e tt l l ed e l a ya n dt 吼sn l es m a l l e s td e l a y 觚dc 0 s th 嬲m eb i g g e s tf i n 地s s v a l u e a n dc o i l v e r l y h 嬲吐l e 锄a l l e rv 址l 圮t t 蛇m e t i l o do fi i i s 廿i 】c t i o n a la t 嘲n 舳c ei s b r o u 啦f o r v r a r d ，锄dm ec o n 、旧喀e n c em ：t ec a nb ea c c e l e r a t e d l r o u g hi l l s t n l c t i 0 1 1 a la _ b e 撇c e o p e r a t i o n mo r d e rt 0b a l 觚c en 咖0 r k 圮u r c e s 觚d d u c ct h eo c c l l r r e n c eo f 耻：t w o r k c 0 删g e s t i o l l ，al o a db a l a n c e d 锄y c a s tr o u t i i l ga i g o r i t l l mb a s e do nr a n d 唧m 砌丽i si l i l p r o w 洒， i nt h i sa l g o r i m m ，m et v 旧m 鲥c so f m cn 咖r k b a l 甜i c i n gd e g r e e 觚d r v e rl o a da l l s e d 勰 也eb a s i sf o r 也ec h o i c eo f r o u t i n g t h a ti s ，龇m 确cw l l i c hi s9 0 tb y 舢砒gt l l e 赋舰婚r k b a l a i l c i r 喀d e g r e ea r 通s e e rl o a dm t 0o n cn l r o u g hl i n e a rw e i g h t e dw 勰u s e d 弱ab a s i sf o r s e l e c t i o n1 1 0 硕士论文 轻了选播的可扩展性问题，但是这并没有完全解决它。因为全球选播地址仍然必须作为 独立的路由项在互联网中传播，而对某些应用来说全球选播地址是必需的口。目前，还 没有一个根本的办法解决路由表的规模问题。 ( 2 ) 无状态服务问题 无状态服务问题就是将选播数据报投递到最近的服务器，而路由器不依赖于以前的 数据报，这是选播的自然属性，正是这种属性使得选播能够平衡网络的负载【2 7 1 。这种无 状态服务在实际的选播应用中也会引起一些问题，比如，一个用户的数据报在传输过程 中被分为多个数据包，这几个数据报可能被路由到不同的选播服务器上，选播服务器由 于没有得到足够的信息，它将可能拒绝用户的服务请求。 对于无状态服务问题，目前已提出多种方法： 使用i p 包头的流标签。但是，它要求沿途中的每个路由器记住所有数据报的流标签， 如果每个有状态的选播连接都使用流标签，则会增加路由器的开销，造成系统资源的浪 费。 更改现有的传输层协议。用户先用i c m p 6e c h or e q u e s j t i 姊l y 寻找最近的选播服务 器的单播地址，然后利用获得的服务器的单播地址进行有状态的连接，这种方法虽然简 单易于实现，但是每次连接之前进行的服务器查找增加了服务的响应时间【3 2 l 。另外一种 方法是扩展t c p 的三次握手协议为五次握手协议，t c p 客户首先向一选播地址发送s y n 数据报，服务器用其单播地址作为源地址发送一个r s t 应答数据报应答，客户校验应答 数据包并再发送一个s y n 数据报到单播地址进行正常的三次握手通信【3 1 1 。上面两种选择 的通信限制在于初始数据报不能分段，而且更改现有的传输层语义在t c p 等传输协议已 经被广泛应用的今天实施起来非常困难。 ( 3 ) 安全问题 由于选播的特殊语义以及目前提出的一些实现方案，使现有的一些安全技术无法使 用。例如，i p s e c 使用i p v 6 目标地址识别使用的i p s e ck e y ，根据选播语义这种技术将导致 所有的选播成员使用同一个i p s e ck e ) ，【3 孔，因此必将造成安全隐患。动态的口s k e y 交换 ( 如i l 江) 要求两个结点能够持续通信，而这些技术的能否使用则取决于选播无状态连 接问题的解决方案。 ( 4 ) 组管理 如果任意一个实体都可以通告自己为选播组成员，那么，一台恶意主机就可以利用 这个机会向客户提供虚假信息2 7 1 。因此必须有组管理协议来管理成员之间的关系，每个 9 第二章q o s 选播路由的理论基础 选播组成员通过组管理协议向路由系统通知自的身份及状态，在路由之前，成员的合法 性身份应该加以确认，否则，恶意主机有可能通过广播虚假成员地址创造“黑洞 ，其 直接结果是路由到这台假主机的选播请求将会到达一台不能应答的欺骗主机【2 7 l 。选播组 成员的等价复制关系可以提高服务的可用性。但是，这种优势得以实现的前提是要保证 路由系统使用的选播成员表中成员主机的可用性。因此，选播组管理必须保证所提供的 成员表中成员的可用性。 2 2q o s 路由 2 2 1q o s 路由概述 传统i n t e m e t 的主要路由协议都是“b e 妣肋r t 的，路由协议只关注一种网络数据结 构如：带宽、时延、跳数等，相应的数据流称之为b e 办e 硒r t 数据流。路由算法以最短路 径相关的算法或协议为核心，如b e l l m a n f o r d 动态规划算法或d 萄虹扛a 算法，其中最典型 的代表是开放式最短路径优先协议( o l 雒ls h o n e s tp a ：吐lf i f s t o s p f ) 。现在，大规模的实 时数据应用传输已经在局域网或广域网得到应用，如多媒体应用、视频及音频会议及远 程教育等，这些应用对于服务质量( q u a l 毋o f s e r v i c e ，q o s ) 有着严格的要求。 定义l 服务质量服务质量是网络在传输业务流时，业务流对网络服务的需求的集 合，其中业务流是指与特定q o s 相关的从源到目的地的分组流阴。 服务质量是应用业务对网络传输服务提出的一组可度量的要求，主要包括带宽、端 到端延迟、分组丢失率、延时抖动、花费等。各种q o s 需求体现为一系列参数指标( 称 为m e t r i c s ) ，这些m e 仃i c s 对于服务请求者来说是至关重要的，网络在传输相应的数据业 务时，所建立的具体连接必须满足这组账腼c s 。q o s 需求可以通过一个约束集来描述， 包括链路约束、路径约束和树约束f 3 5 1 。链路约束定义了从源到目的地的每一条链路的约 束，如对于一个单播连接请求的带宽约束是指构成该连接路径的所有链路的带宽必须不 小于某个特定数。路径约束定义了从源到目的地的一条路径上端到端q o s 需求，如延迟； 树约束定义了对组播中整个组播树的约束，如对组播树延迟的约束是对树中从源到所有 目的地的路径中最大延迟的约束。一般情况下决策者不仅要求所建立的连接满足某些 q o s 约束，同时要求优化其中某个q o s 参数( m e t r i c s ) ，实际应用过程中把需要优化的q o s 指标称为代价参数，或简称为代价( c 0 s t ) 。 定义2 服务质量路由( q o s r ) 服务质量路由( q o sl b u t i i 唱) 是一种基于数据流q o s 请求和网络可用资源进行路由的机制【硼。或者说q o s r 是一种动态路由协议，并且在其 l o 中国石油大学( 华东) 硕士论文 路径选择标准里可能包含可用带宽、链路和端到端路径利用率、资源消费量、延时、跳 数及延时抖动等q o s 参数阁。 q o s r 路由就是将传统的最短路径变为一条“更好 的路径，其主要目标包括以下 两点【”j ： ( 1 ) 为每一个接纳的q o s 业务连接请求，找到满足其q o s 要求的可行路径。 ( 2 ) 优化全局资源利用率、平衡网络负载，从而最大化网络接受其它q o s 请求的能 力。 q o s r 是一种具备双重目标的路由机制：寻找满足约束条件的连接同时有效利用网 络资源例。实现第一个目标的连接( 一般包括路径或树) 称为可行解，为了实现网络资源 的有效利用，多数q o s 路由算法需要在满足约束条件的同时，优化其中的一个m 丽c 。 链路的代价参数是指一般能用某些经济指标量化的某些链路参数，一个连接的代价是指 由该连接所有链路的代价参数构成自变量的函数，因此称之为代价函数。q o s i 媲化算 法的目标是在所有的可行连接中寻找使代价函数得到优化的连接。 q o s r 问题是难解问题，其主要原因有以下几点：首先，目标节点对数据流的q o s 要求通常是多方面的。如视频会议对带宽、延迟时间及延时抖动都有严格要求，其中的 任何一个约束得不到满足都将影响服务质量，而寻找一条满足两个独立加性q o s 约束的 路径的路由问题就是n p c ( n p - c o i n p l e t e ) 问题，除非其中一个约束条件是跳数。对于多播 q o s 树路由问题，其最简单的情况即不考虑其它q o s 约束而仅优化支撑树的代价函数， 该问题被称为最小代价树或s t e i n e rt r 问题，也是n p c 问题【3 5 1 。其次，如果不仅需要考 虑目标节点的q o s 需求，同时需要考虑所有连接在节点或链路上的q o s 需求口7 l ，问题将 变为结合资源分配的路由问题，从而更加复杂。最后，在现实网络中，网络是高度动态 的，任何连接的建立和释放、链路负载的变动、链路的失效和修复等都会导致网络信息 发生变化。同时，随着网络规模的不断扩大采集实时网络信息将变得越来越困难，网络 状态信息的陈旧性和非精确性将极大地影响q o s 路由算法的性能【3 研。 2 2 2q o s 路由的网络模型和度量 现实中的网络是由交换节点、链路和主机组成，在研究时往往将其抽象为有权图 g ( v ，e ) f 3 9 】。其中哟网络节点集，代表网络中的交换设备，如路由器、交换机等；眯 表传输线路，即双向链路集。对于任意的网络节点珥1 ，如果存在甜到1 ，的链路e = ( u ，v ) ， 第二章q o s 选播路由的理论基础 则一定存在另一条v 到材的链路e = ( v ，u ) 。按照链路的对称性，网络可以分为对称网络和 非对称网络。 定义3 路径在网络g ( v ，e ) 中，如果对i = 1 ，2 ，k l 有( v j ，v j + 1 ) e ，则 p = ( v l ，v 2 ，叱) 为图g 的一条从v l 到v k 的路径，也记作p = 碱川if = 1 ，2 ，七一1 ，p 5 1 。 q o s r 的目标就是选择一条从源节点v ；到目标节点v 。的可行路径p ，使其满足请求业务 的q o s 要求。 q o s r 需要通过可测量的q o s 度量来实现。常用的q o s 度量主要包括以下几种：可用 带宽、端到端时延、分组丢失率、延时抖动和花费。不同的度量具有不同的性质，根据 其性质，q o s 度量可以分为可加性度量、可乘性度量和最小性度量3 类。对于图g ( v ，e ) 中 的路径p = ( v l ，v 2 ，i ) ，若巳川p ( 其中江l ，2 ，七一1 ) ，将色川的莉个属性记为形；+ l ， 整个路御的鳓个属性记为啄，则以上3 类度量的定义如下【3 5 l ： i l 定义4 可加性度量若吖= 形厶，则称路御的射个属性为可加性度量。可加 i i l 性度量包括延迟时间、抖动、花费、跳数等。例如，路柳的时延为从源节点到目的节 点的所有链路延迟时间的总和。 七一l 定义5 可乘性度量若嘭= 兀形；“，则称路径尸的鳓个属性为可乘性度量。例如， f 1 分组丢失率为可乘性度量，其中链路丢失率o 形= ：+ l 。在求解有关可乘性度量的过程 中，可以类比参照可加性度量的有关求解方法，即对其求对数就可以把可乘性度量转化 为可加性度量。 定义6 最小性度量若孵= 晌 形厶 ，则称路径尸的射个属性为最小性度量。 。 l 霉i 一j i 例如，带宽为最小性度量，即路径带宽为路径上瓶颈链路的带宽。对于求解 嘭= ，暴登。( 形；+ ) 的问题可转化为一吖= ，粤n - 。 一形又t ) 问题。对于不同类型的q o s 度量 以及多个q o s 度量的组合，其计算的时间代价是不同的，例如，求解多重最小性度量的 组合可以在多项式时间内完成，而多重可加性度量的组合通常不能在多项式时间内完 成。 1 2 中国石油大学( 华东) i 页士论文 2 2 3q o s 路由算法的分类 ( 1 ) 根据网络信息的存储方式分类 根据网络状态信息在网络中的存储方式，有以下三种路由算法【3 羽m ：源路由算法、 分布式路由算法及分层路由算法。 在源路由算法中，网络中每个路由器都要维护整个网络的状态信息，节点之间可以 通过链路状态协议或距离矢量协议相互交换网络状态信息。链路状态协议对网络中所有 其它节点广播本节点的状态信息使得每个节点都能及时了解网络拓扑结构与链路信息 的变化。距离矢量协议周期性地与相邻节点交换距离矢量，每个矢量包括到每个可能目 标节点的最优路径信息。当业务请求到达时，源节点根据网络状态信息和请求业务的度 量参数约束独立地计算一条可行路径，然后沿着这条路径发送一个控制消息，通知中间 节点相应的前驱和后继节点并进行资源预留。源路由算法简单、灵活，在源节点以集中 方式计算路由可以避免循环( l 0 0 pf r ) 路径的产生，省去了死锁的检测和预防等。但源 路由算法也存在一些缺点，如为了与不断变化的网络参数( 如带宽和时延) 保持一致，节 点的全局状态必须频繁更新，这对大型网络来说开销比较大。因此，源路由算法的扩展 性较差；另外，路由的计算依靠单独的节点，源节点的计算量很大，尤其是在组播和多 约束条件的q o s 路由情况更是如此。 在分布式路由算法中，网络中的路由器同样需要通过链路状态协议或距离矢量协议 向邻近节点传递本节点的相关网络信息。分布式路由选择由多个节点协同完成，路径通 过分布式计算得出：控制信息在节点间交换，保存在每一节点的状态信息被收集起来用 于路径搜索。因此，分布式路由选择的响应时间被缩短、算法更易扩展。一些扩散式算 法不要求保持全局状态，路由计算不要求保持任何全局状态，路由选择的决定和最优化 完全基于局部( 本地) 状态而进行【4 l 】。但是，如果各个节点保留的其它节点的状态信息 不一致或者节点路由信息不准确，就容易出现环路；如果路由节点间不能很好地协同， 对整个网络的性能、路由协议的动态特性及路由结构的扩展性都会有负面影响。 在分层路由算法中，一般是通过某种网络信息的集中从而达到缩减网络规模的目 的，故通常被用在大型网络中。网络被划分为不同的层次，最底层是由若干在距离上比 较接近的实际路由器组成的组构成，有链路与两个或两个以上的组相连的节点称为边界 节点，每组选出一个节点作为该组的代表称为逻辑节点，若干个逻辑组又组成更上一层 的逻辑组。逻辑组在上一层的网络中只以一个逻辑节点表示，而忽略其内部细节，路由 信息在每个逻辑组的边界路由器中进行会聚，这样组内的路由器仅仅知道同一组中的节 第二章q o s 选播路由的理论基础 点的详细信息，而对于其它组，则只了解它们的汇聚信息，这样处理后，每一层的组内 路由节点数被压缩了，相应的路由信息传输量也降低了，扩展性得到了改善。在每一层 的逻辑节点依据汇聚信息直接采用源路由，因而继承了源路由的优点：同时路由计算还 是由路径上的许多节点共同分担，因而也继承了分布路由计算的优点。层次路由对大型 网络而言是最有前途的路由策略，当然，由于汇聚信息引入的非精确性，层次路由在一 些情况下也可能导致选路失败。 在以上三种路由算法中，源路由算法是基础，也是q o s 路由算法研究的理论基础， 它能保证寻找一条无环的路径。对于一些n p c 问题，相对分布式算法和分层路由算法， 源路由算法更易于设计和实现，但采用源路由算法时，每个节点需要保存并广播全网信 息并频繁刷新，对于大型网络来说，由于广播负载过重而难以实现；另外，由于延迟等 一些客观原因，节点所接受的信息只可能是近似的信息，最终将导致在存在可行路径的 情况下算法无法找到可行路径。因此，源路由算法对于大型网络并不适用。分布式路由 算法和分层路由算法常应用于大型网络，每个节点需要保存并传播的信息少于源路由算 法。但是，相对源路由算法，分布式算法难于解决n p c 问题，而且在相邻节点保存的 信息由于传输等问题不一致时，容易导致环路的产生。 ( 2 ) 根据最优化目标分类 根据最优化目标，可以将q o s 路由算法分为两类：单目标最优化和多目标最优化。 最优化目标是指在一个网络环境中，某一个或几个q o s 度量所能达到的极值，所求得的 目标值与极值的接近程度体现了算法的性能。最优化目标不是一种硬性指标，优化目标 与其极值的接近程度对算法的可行性是没有影响的。如：以路径代价作为单一最优化目 标，算法求出代价为2 0 的路径要优于代价为5 0 的路径，但这两条路径在满足约束的条件 下都是可行的。 单目标最优化问题是指仅含有一个目标的最优化问题，在q o s 路由中，它是在牺牲 其它度量的基础上完成某单一目标的最优化，例如把链路利用率、最短路径、最小跳数、 时延等其中一个作为目标函数，其余的需求部分转化为约束条件。根据有无约束条件， 又将单目标最优化路由算法分为无约束单目标最优化路由算法和有约束单目标最优化 路由算法。相对于优化目标而言，约束条件是一种必须严格执行的条件，不满足约束条 件的路径是无效的。现在对q o s 路由算法的研究多是单目标最优化的，这样找到的路径 并不一定能够提供快速、有效的服务，并不一定能满足实际应用的要求，因此需要通过 不断变换目标函数和约束条件多次测试来选择最可行的路径，这样往往需要花费更多的 1 4 中国石油大学( 华东) 硕士论文 网络资源。 多目标最优化是指含有多个目标的最优化问题。而这几个目标又常常是互相冲突 的，在这种情形下的多目标优化问题要比单目标最优化问题复杂得多，是一个n p 完全 问题。现在对多目标最优化路由算法的研究才刚刚起步，通常所采用方法是线性加权法： 根据用户的不同需要，对各个目标加上不同的权系数，最后就将多目标问题转化成单目 标问题。 2 3 遗传算法的基础理论 遗传算法( ( k n e t i ca 1 9 0 r i t h m ，g a ) 是模拟达尔文的遗传选择和自然淘汰的生物进化 过程的计算模型，由美国m i c l l i g 强大学的j h o l l a n d 教授于1 9 7 5 年在其著作自然与人工 系统中的自适用中提出。遗传算法在整体搜索策略和优化计算时不依赖梯度信息，应 用范围非常广泛，因此，获得了广泛的研究，大量的相关文章被发表，并且作为一种优 化工具在实践中也逐渐被推广应用。 2 3 1 遗传算法的基本概念 下面介绍遗传算法中的一些基本概念【4 2 1 【4 3 1 州： ( 1 ) 染色体( c l o m o m e ) 染色体是生物学中的概念，有时也被称为个体。在遗传算法中通常用字母或数字组 成的串来表示，如x = 而x 2 。再，其中薯是染色体x 的基本单元，称为基因( g e n e ) ，称 为基因数。一个或多个基因组成的有效信息段叫做染色体的基因组( g e n e 觚u d ，通常 一个基因组对应于解中的一个优化参数。在遗传算法中根据问题的编码不同，个体的表 现形式也不同。 ( 2 ) 染色体编码承印r e 删i o n ) 遗传算法求解问题不是直接作用在问题的解空间上，而是对被优化的参数进行编 码，并以编码方式运算。因此，如何将问题的解转换为编码串( 染色体) 是利用遗传算 法解决问题的关键。编码方式的不同有时会对算法的性能、效率等产生很大的影响。根 据优化问题的性质不同，所采取的编码方法有着很大的区别，常用的方法有二进制编码、 实数编码和求解组合优化的整数编码等。 ( 3 ) 适用度函数( f i 协豁sf u n c t i o n ) 适应度函数是对解空间中个体对其环境适用程度的一种度量，一般以目标函数或费 第二章q o s 选播路由的理论基础 用函数或其它方法来表示或确定。适应度函数的设计是遗传算法的重要部分，它的设计 直接影响到遗传算法的性能，因此，适应度函数的设计要与具体求解问题的目标相结合。 遗传算法在计算的过程中不依赖外部信息，它进行遗传操作的唯一依据就是个体的适应 度值，通常，适应度函数值越大，个体对应的解越接近问题的最优解。 ( 4 ) 种群( p o p u l a 廿o n ) 和种群规模p o p - s 让狯 种群是指染色体的集合。利用遗传算法求解问题时，从随机选择的多个初始解开始 进行迭代搜索，这多个初始解的集合以及每次迭代生成的一组新解都是一个种群。种群 规模p o p j i z e 是指种群含有的染色体总数，它的取值非常关键，对算法的效率有明显的 影响，当p o p i z e 过小时，尽管可以提高算法的运行速度，但却降低了种群的多样性， 有可能引起遗传算法的早熟现象，难以求出最优解；而当p 0 ps i 笳过大时，又会增长收 敛时间导致算法运行效率的降低。不同问题有各自适合的种群规模p o ps i 瑟，通常建议 种群规模的取值范围为2 旺1 0 0 。 ( 5 ) 遗传操作 遗传算法有3 个基本的操作过程，分别是选择、交叉和变异操作。 选择操作( s e l e c t i o p e 枷o n ) 和选择概率见 选择操作是根据一定的选择策略，以较大的概率从父代群体中选择适应度值较大的 个体将其复制到子代中，实现了达尔文的适者生存的原则。常用的选择方法有：精华选 择、均分选择、轮盘选择、线性排名选择、锦标赛选择等，其中，轮盘选择策略最为常 用。选择是一个重要的过程，如果选择不当就容易失去许多重要的个体，影响算法的收 敛速度。选择操作的基本过程是一样的，即在父代群体中“随机”选择脚一舰阢个个 体，将其作为子代群体的个体。这种“随机 选择并非完全随机，它是基于自然界优胜 劣汰的选择策略，根据个体的适应度值来确定个体被选择的概率，按照一定比例将选择 的个体复制生成新个体加入到下一代种群中。随机选择策略是基于概率的，因此，适应 度值低的个体也有被选择的可能，群体的多样性能够得到维持。同样，适应度值高的个 体也有被淘汰的可能性，造成进化的暂时倒退。为弥补这一不足，可以将父代中适应度 值最大的个体无条件地保留到其子代，这种方法被称为精华保存法。在简单遗传算法中， 采用精华保存法能够保证遗传算法以概率l 收敛到全局最优解。 交叉操作( c 删洛0 v 盯o p 饿瞄饷) 和交叉概率见 1 6 中国石油大学( 华东) 硕士论文 交叉操作以一定的交叉概率见( 霰( o ，l 】) 在种群中随机选择一定数量的个体实施 两两个体之间随机交换信息的一种操作。交叉操作通常是把两个基因串中的某一部分相 互交换，产生两个新的个体。最常用的交叉策略是点式交叉、启发式交叉、顺序交叉、 混合交叉等。点式交叉通常是随机地在两个父体串上选择一个或多个交叉点，然后交换 父体串中对应的子串。交叉操作是遗传算法中产生新个体的主要方法，因此，阢一般应 取较大值。 变异操作( m u t a t i o no p e r a t i o l l ) 变异概率 变异操作是遗传算法用以模拟生物在自然界的遗传环境中由于各种偶然因素引起 基因突变而引入的一种方法。变异操作能够随机改变某个个体的遗传信息，从而避免产 生局部最优值。变异操作通过一定的变异概率以( 砌( o ，1 】) 在种群中随机选择一定数 量的个体实施变异操作。变异操作修改了个体的适应性，使之变成一个新的个体，达到 演化的目的。变异方法一般分为均匀变异、非一致性变异、自适应变异等。 自然界中基因发生变异的概率一般比较小，但在遗传算法中，如果变异概率的取值 过小，就会降低变异操作产生新个体和抑制早熟现象的能力。因此，变异概率值应根据 具体求解问题确定大小。 ( 6 ) 算法运行的终止标准( s t o p p i n gc r i t c r i a ) 在遗传算法中，算法运行直到某个期望的终止标准满足而停止。常用的终止标准是 预先规定一个最大的演化代数或在连续多少代以后所求解的适应度值没有什么明显的 改进时，算法即终止。 2 3 2 遗传算法的基本流程 遗传算法通常有以下几个基本的步骤： ( 1 ) 确定编码方案 编码方案的选取很大程度上依赖于问题的性质，其主要目的是使优化问题解的表现 形式适合于遗传算法中的遗传运算。 ( 2 ) 设计适应度函数 通常，适应度函数设计的依据是优化问题的目标函数。在遗传算法中适应度值函数 是用来衡量个体优劣的标准。适应度函数确定以后，将按照自然界中适者生存的选择规 律决定哪些染色体适应生存，哪些将被淘汰，生存下来的染色体组成新的种群，形成下 1 7 第二章q b s 选播路由的理论基础 一代的群体。 ( 3 ) 生成初始种群 在解空间中，随机选择一定数量的解组成初始种群。产生初始种群时，要尽可能地 保证种群中个体的多样性。 ( 4 ) 遗传操作 基本的遗传操作主要分为三步：首先，按照设计算法时确定的选择策略选择一定数 量的个体，将其作为新的个体加入到下一代群体；然后，以事先给定的交叉概率成和交 叉策略，在选出的个体中任意选择两个个体进行交叉操作，产生两个新的个体，重复该 过程直到所有要求交叉的个体交叉完毕；最后，根据事先给定的变异概率几和一定的 变异策略对选择的个体进行变异操作。 ( 5 ) 终止算法 判断算法是否满足终止条件，若满足则输出求解结果并终止算法，否则继续进行遗 传操作。 遗传算法的基本流程如图2 2 所示： 产生新的种群酏) ，户t + l 图2 2 遗传算法基本流程图 联9 2 2 f l 佣rc h 曩r to f 弘n 鲥c 叠i 印r 妯m 1 8 中国石油大学( 华东) 硕士论文 2 3 3 遗传算法的优点和不足 遗传算法的优点主要表现在以下几个方面【4 2 】m ： ( 1 ) 适用范围广 利用遗传算法解决问题时不需要了解问题的内在性质，对所求问题没有太多的数学 要求，不受搜索空间限制条件( 如可微、连续、单峰) 的约束及不需要其它辅助信息， 它仅是利用某种编码方式将优化问题的决定因素和控制参数编码成适合解决问题的有 限长的串，并且在编码串上进行操作，从中找出高适应度值的串。近年来，遗传算法已 成为国际上众多学科的热门话题，作为一种高效实用的全局优化算法，遗传算法已被广 泛应用于组合优化、自动控制、图像处理、信号处理、机器学习、人工生命、神经网络 等诸多领域【4 5 】。 ( 2 ) 本质并行性 遗传算法的奠基人h o l l 锄d 在最早提出遗传算法的理论和模型时，就已阐述了它所固 有的并行性，即每一代中除了对捍个串的处理外( 以为种群规模) ，遗传算法实际上处理 了大约伏刀3 ) 个模式，从而每代只执行与群体规模成比例的计算量，就能够同时对大约 d ( 刀3 ) 个模式进行有效处理，而且不需要额外的存储空间。此外，在实际应用遗传算法 时，还可以把同一代种群中的个体分布到若干个处理器上，在不同的处理器上完成遗传 操作。 ( 3 ) 智能性 遗传算法的智能性包括自组织、自适应和自学习等。遗传算法在搜索过程中能够自 动地获取和积累搜索空间的相关知识，并自适应地控制搜索过程。在计算过程中，采用 自然界中优胜劣汰的选择策略，适应度值大的个体具有较高的生存概率，进行交叉和变 异等遗传操作时就可能产生与环境更适应的后代，经过群体一代一代地进化，解空间中 越来越多的区域将被搜索到，最终搜索到最优解。 ( 4 ) 鲁棒性强 遗传算法用种群作为基本单位，采用选择、交叉、变异操作对解空间进行搜索，随 着迭代次数的增加和搜索空间的扩大，最终将得到最优解。搜索过程不受初始解的影响， 而且最终获得的解也不会因为初始种群的不同而变化。 ( 5 ) 整体优化 遗传算法在搜索过程中不易陷入局部最优，能同时在解空间的多个区域内进行搜 1 9 第二章q o s 选播路由的理论基础 索。即使在所定义的适应度函数非连续、不规则和伴有噪声的情况下也能以较大的概率 跳出局部最优，找到全局最优解。 随着遗传算法应用范围的不断扩大，人们发现遗传算法求解问题时能够很快地确定 最优解存在的区域，却不能很快地进化至最优解，主要表现为：遗传算法在开始的时候 进化速度很快，有时候能够以指数级的进化速度朝着最优解方向前进，但不久以后，进 化速度就会变慢，临近全局最优解时，则可能是几百代、上千代才会向目标逼近一小步， 有时甚至停滞不前。产生这样现象的主要原因有两个：一是遗传算法较弱的局部搜索能 力：二是是求解复杂的多峰值问题时存在早熟收敛的可能性。在利用遗传算法求解问题 时，种群的规模一般设在几十到几百之间，这与自然界中物种的规模相差甚远。如果种 群中出现了超级个体，即该个体的适应度值z 大大超过种群中个体的平均适应度值 z ，在按照适应度值比例进行选择时，该个体很快就会在群体中占有绝对的比例， 这种现象的极端就是所有个体来自同一祖先。从而导致算法较早的收敛到一个局部最优 点，这种现象被称之为早熟收敛。一旦早熟收敛现象发生，选择和交叉操作就会失效， 而遗传算法本身不具备跳出早熟收敛状态的能力，虽然偶尔也能跳出，但却要花很长时 间。另外，在搜索过程的后期，虽然种群中存在足够的多样性，但群体的平均适应度值 可能会接近群体的最优适应值。在这种情况下，种群中实际上已经不存在竞争，从而搜 索目标也难以得到改善，这种现象被称之为停滞现象。 因此，要提高遗传算法的搜索性能，加快算法的进化速度，必须保证算法在己包含 最优解区域时，具有收敛到最优解的能力( 局部搜索能力) ；当陷入局部极小点时能够开 拓新解区域，跳出早熟收敛的能力。此外，由于陷入早熟收敛状态的原因在于群体的多 样性差，因此，保持进化过程中遗传算法的群体的多样性，可以有效预防早熟收敛的发 生。 中国石油大学( 华东) 硕士论文 3 1 引言 第三章基手遗传算法的q o s 选播路由算法 遗传算法在搜索过程中能够自动获取和积累搜索空间的相关知识，并自适应地控制 搜索过程，从而能够得到最优解或者准最优解，即它能够从任意初始种群出发，通过选 择、交叉和变异等遗传操作，使群体一代代的进化，直至达到最优解空间。遗传算法在 组合优化问题求解、机器学习、规划设计等领域已经展示了其巨大优势，将遗传算法应 用到q o s 选播路由的求解中，能够简化路由算法的求解。 近几年，利用遗传算法解决q o s 选播路由选择问题的相关研究相当活跃。文献【4 6 】 提出了使用遗传算法解决q o s 选播路由问题的最优解方法，该算法首先构造初始路由 表，根据路由表构造初始种群，然后路由计算和遗传操作同时进行，当前节点在演化后， 把路由表传给下一个节点，在一个节点进行路由表的更新，染色体做相应的延伸，然后 继续演化，直到求出最优路由。在网络规模较小时该方法是有效的，但当网络规模较大 时，该方法必将浪费大量的存储空间；同时，由于每选择一个节点，算法都要进行一定 代数的遗传操作，随着网络规模的增加，算法的时间也将是巨大的。文献【4 7 】提出不必 建立候选路由库，直接采用随机深度优先搜索算法生成初始种群，节省了存储空间，但 该算法所采用的随机方法对生成多样性的初始种群并没有太大的帮助，而且算法中采用 的是最基本的遗传操作，没有根据选播路由的特点进行相应的调整。基于此，本章改进 了基于遗传算法有时延约束的q o s 选播路由算法：通过加权深度优先搜索和轮盘赌相结 合的方法来保证初始种群的多样性；设计了新的适用度函数；对基本的变异操作进行改 进，采用了指导变异的方法。 3 2 有时延约束的q o s 选播路由问题描述 选播路由服务的基本模型可以从图论的角度抽象为有向加权图： g = ( y ，e ) 其中：y = ，i ，1 ，2 ) 是一个计算机网络的有限节点集合，e = 积lf 刀，疗 是 网络的链路集合。设ly | = 以，iel - 朋分别为网络中节点数和链路数，每条边e “e 上有 链路带宽色。、链路时延哦。和链路代价q 三个参数。其中：以为链路上可用带宽的度 2 l 第三章基于遗传算法的q i o s 选播路由算法 量，t ，j 为数据包分组通过该链路所经历的时间度量，c u 为链路使用代价的度量，为可 加性度量。从网络的抽象模型可知，网络由节点和链路两大要素组成。严格说，对其进 行分析也应包括节点和链路两大要素，为突出问题的本质，本文对网络模型进行了合理 简化：假设存在一种分配策略，它能将网络节点的q o s 度量合理分配到与其相邻链路的 度量上。 一个q o s 选播路由请求可描述为r = ( s ，彳，b ，d ) ，其中：源节点s 是一组请求服务 的节点，g ( s ) = s l ，s 2 ，毛 表示一组源主机，j l ，s 2 ，西矿，( ， 刀) ；彳作为目的节点的 选播地址，g ( 彳) = 西，d ： 则是一个共享选播地址彳并提供相同服务的选播组， 矾，畋，吒y ，( g 功且而，如，吒仨g ( s ) ；召为业务请求的最小带宽；d 为业务请求 的最大时延。设：p l ，j = l ( 哆，p ) p ，o ( b ，仨p ) ，其中：户为g ( s ) 中某个源节点到 选播组g ( 彳) 中某一成员节点的一条路径，则路径p 的带宽删黝( d 、时延眈劬( d 和代价q 研( 尸) 为别为： 肋砝臃d 纺( 尸) = m i r l ( 6 i ，p j ，j ) f ，歹= l ，2 ，履 ( 3 - 1 ) 一打 眈枷( 一= f 叱易f ，= l ，2 ，刀 ( 3 - 2 ) i 1 1 j t l 一一 q 酣( 尸) = f p u f ，= l ，2 ，j 刀 f l l ，l l ( 3 - 3 ) q o s 选播路由算法的目标是：从g ( s ) 中的某一源节点到目标选播组g ( 彳) 的所有路 径中选择一条满足带宽约束、时延约束且代价最小的路径尸。即路径尸同时满足公式 ( 3 - 4 ) 、( 3 - 5 ) 和( 3 6 ) ： 删黝( p ) 口( 3 - 4 ) 眈坳( d d ( 3 5 ) m i i l c 瓠r ( 尸) ( 3 6 ) 一 中国石油大学( 华东) 硕士论文 3 3 基于遗传算法有时延约束的q o s 选播路由算法 3 3 1 算法描述 ( 1 ) 编码机制 算法中，采用不定长的节点序列编码，一条染色体表示从源节点到选播组成员节点 的一条路径，染色体的基因位由节点的标示表示，其中节点标示是事先给定且在计算过 程中保持不变。这种以节点标示作为基因位的编码方式自然、直观、实用性强，遗传操 作不需要复杂的编码、解码过程；同时能够方便、快速的检测所选路径是否存在环路， 因为只要个体中重复出现某个节点标示就表示该个体对应的路径中存在环路。 ( 2 ) 初始种群的生成 算法首先删除网络中不满足带宽要求的链路，得到一个新的网络拓扑图。通过这个 预处理可以保证生成的所有个体都满足最小带宽的要求，同