（计算机软件与理论专业论文）基于遗传粒子群算法的选播qos路由算法的研究.pdf

基于遗传粒子群算法的选播q o s 路由算法的研究摘要随着i n t e m e t 技术的不断发展，各种多媒体服务对网络服务质量提出了更高的要求。为了增强网络服务质量和提供网络负载均衡，人们提出了“选播 通信模型，而保证选播通信服务的关键问题是选播q o s 路由问题。本文在对网络选播路由的基本概念和技术进行深入分析和研究的基础上，提出了基于遗传粒子群算法的选播q o s 路由算法，以求解选播路由选择问题。概括而言，本文的研究工作如下：( 1 ) 将遗传算法、粒子群算法与选播q o s 路由技术相结合，探索利用遗传算法和粒子群算法两者优点来求解选播q o s 路由优化问题。( 2 ) 提出基于遗传粒子群算法的选播路由算法。该算法基于遗传算法和粒子群算法的思想，对粒子群算法和遗传算法进行改进；提出一个更新算子操作，让路径之间相互学习，使得整个种群不断地趋于最优路径。( 3 ) 将所提出的选播路由算法应用于求解时延约束和多约束的选播路由问题，并通过实验证明遗传粒子群算法在求解时延约束和多约束问题时的可行性和有效性。同时，将本文算法与基于遗传算法的选播路由算法和基于粒子群算法的选播路由算法进行性能分析比较，结果表明，基于遗传粒子群算法的选播路由算法具有一定的优越性。( 4 ) 以n s 2 为仿真工具并对其进行扩展。通过更改和添 j i n s 2 底层代码，重新编译，建立仿真平台，对本文提出的算法进行仿真。综上所述，本文的研究不仅在遗传粒子群融合算法优化方面具有良好的理论意义，而且在选播q o s 路由问题上具有良好的工程应用价值。关键词：选播路由；遗传算法；粒子群算法；q o s 约束；n s 2 仿真；更新算子i ir e s e a r c ho na n y c a s tq o sr o u t i n ga l g o r i t h mb a s e do ng e n e t i ca l g o r i t h ma n dp a r t i c l es w a r mo p t i m i z a t i o na l g o i u t h ma b s t r a c tw i t ht h er a p i dd e v e l o p m e n to ft h ei n t e m e tt e c h n o l o g y , m u l t i m e d i as e r v i c e sp u tf o r w a r dh i g h e rr e q u i r e m e n t st ot h eq u a l i t yo fs e r v i c e ( q o s ) i no r d e rt oi m p r o v eq o sa n ds u p p o r tt h el o a db a l a n c i n go ft h en e t w o r k , t h ea n y c a s tm o d e lh a sb e e np r o p o s e d t h ek e yp r o b l e mo fe n s u r i n ga n y c a s tc o m m u n i c a t i o ns e r v i c e si sa n y c a s tq o sr o u t i n gp r o b l e m o nt h eb a s eo ft h ea b u n d a n ta n a l y s i sa n ds t u d yo ft h eb a s i cc o n c e p ta n dt e c h n o l o g yo fn e t w o r ka n y c a s tr o u t i n g ，t h i st h e s i sp r o p o s e st h ea n y c a s tq o sr o u t i n ga l g o r i t h mb a s e do ng e n e t i ca l g o r i t h ma n dp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h mt os o l v et h ep r o b l e mo f a n y c a s tr o u t i n g 功em a i nw o r ka n dc o n t r i b u t i o n so ft h i st h e s i sa r ea sf o l l o w s ：( 1 ) c o m b i n et h ea d v a n t a g e so fg e n e t i ca l g o r i t h ma n dp s oa l g o r i t h ma n de x p l o r e st h ec o n v e r g e da l g o r i t h mt os o l v ea n y c a s tq o sr o u t i n gp r o b l e m ( 2 ) a na n y c a s tr o u t i n ga l g o r i t h mb a s e do ng aa n dp s oa l g o r i t h mi sp r o p o s e d t h i sa l g o r i t h mi sb a s e do ng e n e t i ca l g o r i t h m sa n dp a r t i c l es w a r ma l g o r i t h m t h et h e s i si m p r o v e st h eb a s i co p e r a t i o na n dp r o p o s e sa nu p d a t eo p e r a t o r , w h i c hm a k e sr o u t i n gp a t h sl e a r nf r o me a c ho t h e ra n df i n dt h eb e s tp a t hf i n a l l y i i i( 3 ) t h ea n y c a s tr o u t i n ga l g o r i t h mb a s e do ng aa n dp s oi sa p p l i e dt os o l v et h ep r o b l e m sw i t hm u l t i c o n s t r a i n t sa n dd e l a yc o n s t r a i n t t h en o v e la l g o r i t h mp r o v e dt ob ef e a s i b l ea n de f f e c t i v eb ye x p e r i m e n t m o r e o v e r ，t h en o v e la l g o r i t h mp r o v e da l s ot oh a v eb e r e rp e r f o r m a n c et h a na n y c a s tq o sr o u t i n ga l g o r i t h mb a s e do ng ao rp s or e s p e c t i v e l yb ye x p e r i m e n t ( 4 ) n s 2i se x t e n d e da n da p p l i e dt os i m u l a t et h ea l g o r i t h mi nt h et h e s i s t h eb o t t o mc o d e o fn s 2i sm o d i f i e da n dt h e nr e c o m p i l e d t a k e na sac o l l e c t i o n ，t h i st h e s i sn o to n l yd e s e r v e sg o o dr e s e a r c hi nt h ea r e ao ft h eh y b r i da l g o r i t h mb a s e do ng aa n dp s o ，b u ta l s oh a sb e t t e ra p p l i c a t i o nv a l u e sf o ra n y c a s tq o sr o u t i n g k e y w o r d ：a n y c a s tr o u t i n g ；g e n e t i ca l g o r i t h m ；p a r t i c l es w a r mo p t i m i z a t i o n ；q o sc o n s t r a i n s ；n s 2s i m u l a t i o n ；u p d a t eo p e r a t o ri v广西大学学位论文原创性声明和学位论文使用授权说明学位论文原创性声明本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相关知识产权属广西大学所有。除已注明部分外，论文中不包含其他人已经发表过的研究成果，也不包含本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮助的个人和集体，均已在论文中明确说明并致谢。论文作者签名：系、秀学位论文使用授权说明j 吵年6 月矽日本人完全了解广西大学关于收集、保存、使用学位论文的规定，即：本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容；按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。请选择发布时间：口即时发布口解密后发布( 保密论文需注明，并在解密后遵守此规定)论文作者答名：篦秀导师签名锏洙1 年6月jy 日基于遗传粒子群算法的选播q o s 路由算法的研究1 1 课题研究的背景及意义第一章绪论如今，网络技术的发展是日新月异，技术带动应用，不同领域的开发商都充分利用着不断成熟的技术，所以，网络应用领域也越来越广泛。网络服务已从以前的简单的文本信息传输发展到视频点播、视频会议、网站镜像、负载均衡、并行计算、网络游戏等不同的方式。此时，传统的点到点的通信方式已经不能满足各种应用的需要，多种不同的网络通信方式应对于不同的应用而出现。目前，网络的通信方式主要包括：单播( 删c a s t ) 、广播( b r o a d c a s t ) 、组播( m u l i c a s t ) 、选播( a n y c a s t ) 等。如今单播、广播和组播通信方式的研究已经比较成熟，而选播相对来说则是一种较新的通信方式。1 9 9 3 年因特网工程任务组( i n t e m e te n g i n e e r i n gt a s kf o r c e ，i e t f ) 提出了a 1 1 y c a 5 t 的概念【1 1 ，1 9 9 8 年在r f c 2 3 7 3 1 2 中将选播定义为i p v 6 的一种标准服务模型。选播的定义是通过对一组提供相同服务的主机赋予相同的选播地址，使得客户可以从中选择离它最近( 或最好) 的服务主机的通信方式。由此看出选播虽然也是一种点到点的网络通信服务，但是相对于传统的单播和组播，它的配置相对简单，能提供一种弹性服务，节约路由和链路资源，能够保证服务的可靠性，并且有利于网络的负载均衡。基于上述特点使选播具有广阔的应用前景。路由是影响单播、组播通信质量的重要因素，对选播也不例外。网络服务质量要得到保证，就必须在客户端和服务器之间建立了一条可行的、优化的数据传输通道。而传统的路由协议只能提供一种尽力而为的服务，不能满足不同用户群体对网络流量、带宽要求、传输延时以及服务安全性等方面服务质量( q u a l i t yo f s e r v i c e ，简称q o s ) 的不同要求。随着i n t e m e t 技术的不断发展，各种实时网络服务要求的q o s 也越来越高，针对这种现状，人们提出了几种q o s 体系结构，例如集成服务、区分服务和多协议标识交换等不同的体系结构。如何选择q o s 路由，即满足q o s 约束的路径是提供q o s 保证的关键问题之一。研究表明，对于具有多个不相关度量的q o s 路由问题这样的n p 完全问题来说，目前大部分学者都采用启发式算法来求解。但是由于现有的启发式算法比较复杂、难以求解等问题，所以还不能应用于实际。经过分析表明，q o s 路由之所以难以解决，就是因为网络中各种实时的服务会对网络时延、时延抖动、丢包率、带宽、路由器缓冲空间以及c p u 处理周期等诸多q o s 参数提出各种各样的要求。在一些情况下，多种约束会同时附加在路由生成的过程中，从而导致q o s 路由问题难解 4 1 。所以如何解决选播通信方面的路由问题，目前仍然没有一种非常有效的路由算法，许多关键技术仍在研究之中。至今为止，人们对单播和组播路由的q o s i b - j 题的研究较为深入，取得许多有益的研究成果并付诸实际工程应用，但是对选播q o s 的研究相对较少。基于选播通信服务的优点及q o s 路由的重要性，选播q o s 路由问题具有重要的研究价值和实用价值，也是一项广西大学硕士学位论文基于遗传粒子群算法的选播q o s 路由算法的研究富有挑战性的课题。目前，许多研究人员利用遗传算法对选播q o s 路由进行研究，并取得了较好的效果。也有一些学者把改进的粒子群算法运用到组播q o s 路由优化和a dh o c网络，但是把粒子群算法运用到选播q o s 路由上的研究还比较少。研究表明，粒子群优化算法和遗传算法各有自己的优缺点，有互补之处，如粒子群优化算法收敛速度快，但是后期容易陷入局部最优；遗传算法的交叉和变异操作则可以改变粒子，扩大搜索范围，使得粒子跳出局部最优。基于两类算法的特点，本文大胆融合粒子群算法和遗传算法的优点，提出了基于遗传粒子群算法的选播q o s 路由算法，希望通过路由优化来实现网络资源充分利用、网络负载均衡，从而为将来选播通信服务实施具体的应用奠定研究基础。作为粒子群算法在离散优化问题中的一个新的应用方向，本文的研究是一次有益的尝试。选播通信服务及其q o s 路由问题具有较高的研究价值和应用价值，所以本文的研究不仅在遗传粒子群融合算法优化方面具有良好的理论意义，而且在选播q o s 路由问题上具有良好的工程应用价值，对于我国计算机网络技术和其它相关领域的发展也具有一定的研究意义和现实意义。1 2 国内外研究现状1 2 1 选播通信服务及选播q o s 路由由于选播通信服务具有良好的研究价值和广泛的应用前景，越来越多的研究人员投入到该领域，使得该领域的研究发展迅速。选播技术目前主要有两个发展方向：基于应用层的选播服务和基于网络层的选播服务。基于应用层的选播服务是利用选播路由技术等来实现选播服务、提高网络通信业务的效率和服务和网络等的负载均衡1 5 儿6 j ，基于网络层的选播服务则是通过目标服务器的选择去实现选播服务、优化网络应用等方面【7 儿8 】【9 】。对于应用层选播来说，目标服务器的选择标准一般是依赖于服务器或是应用的不同尺度来决定，如可以获得的容量、可以测到的相应时间、可以激活的连接的数量等，也就是说，选择服务器比较依赖外部的实体。而在网络层选播中，目标服务器的选择标准有所不同，有的依赖于网络的拓扑，如路由最小的跳数、最小的花费，有的依赖路由器选择的算法，也就是说依赖于网络自身来选择服务器。有前面可知，路由的选择能很大程度上决定网络层选播的实现，所以路由算法的研究与实现尤为重要。目前，国内外研究人员关于选播理论与技术的研究已经取得许多有意义的研究成果，特别是在i p v 6 越来越体现出巨大重要性之后。在国外，对选播的相关研究进展较为丰富。其中，选播在面向应用层上的工作主要研究其作为服务定位和主机自动配置的解决方法等等【5 j ，在网络层选播的工作主要是在路由协议、无状态服务问题、组管理协议、地址结构、安全问题以及可扩展性等不同方面【1 0 】【l l 】【1 2 】。还有一些研究人员对选播的容错和负载均衡也进行了较为深入的研究【l 引。在国内，对选播的相关研究主要侧重于选播路由算法、选播的应用等问题。例如，北京大学张丽等人通过对觚y c a s t 服务特性的分析以及对i p v 6 协议栈相关协议的分析，提出在网络层对a n y c a s t 数据包进行路由的吸收协2基于遗传粒子群算法的选播0 0 s 路由算法的研究议【1 4 】和一个使用特殊复合距离的选播路由算、法【”j ；中南大学王建新等人设计实现了一种移动自组网络中的选播路由协议【1 6 1 ，提出了一种基于选播策略的路由恢复方法【1 7 1 ；广西大学李陶深、陈燕等人将遗传算法、随机方法与网络选播路由技术结合起来，设计实现了一组基于遗传算法的选播路由算法【1 8 】【1 9 1 2 0 1 。选播一经提出，其特殊语义为q o s 的研究提出了挑战，选播的q o s i h - j 题随即引起了研究者的兴趣。国外有些研究人员对选播路由算法进行研究【2 1 】【2 2 】【2 3 1 ，提出适合于选播通信服务模型的路由算法，适当考虑了带宽约束等条件【2 3 】，而较少全面考虑业务的q o s需求。国内在q o s 选播路由算法的研究方面起步较晚，但是较全面的考虑了业务的q o s需求，提出的算法中不仅包含单个约束，还综合考虑包括时延、带宽、时延抖动等几个约束条件【2 4 】，甚至把网络和服务器的负载问题考虑在内，以寻找出一个更满足用户需求的路径，取得了很多研究成果。例如，文献【2 5 】提出了一种保证服务数据流q o s 的选播路由算法，文献【3 l 】提出了基于网络链路空闲率的q o s 选播路由算法。近年来，研究人员受到智能优化算法( 例如，遗传算法【2 6 1 、粒子群算法【2 7 1 1 2 矾、蚁群算法【2 9 1 、模拟退火算法【3 0 1 等) 的启发，将其应用于选播q o s 路由问题求解，并取得较好的效果。例如，广西大学陈燕等先后提出并实现了一种带多个q o s 参数约束的选播路由算法1 2 4 、一种延时受限的选播q o s 路由算法【3 2 j 和一种基于遗传算法的选播q o s 路由算法【2 6 ；文献【3 0 】提出了一种基于模拟退火算法和遗传算法的选播路由算法。目前将粒子群算法应用于选播q o s 路由问题的研究还较少见，其中文献 2 7 【2 8 】基于粒子群算法的思想，改进了粒子群算法，提出了特殊相加算子和随机扰动算子，在粒子群算法运用于选播q o s 路由算法的研究上迈开一大步，为本文的研究做出了重要的铺垫。1 2 2 遗传算法和粒子群算法的结合从网络选播q o s 路由算法的研究进展来看，利用智能优化算法来研究选播q o s 路由算法也存在一些问题。例如，各种智能算法本身存在一定的优缺点，在应用到选播q o s路由领域中时也存在算法耦合性问题。而研究表明，把不同的智能进化算法有效融合，能够提高算法的性能。就本文研究的粒子群算法和遗传算法来说，遗传算法进化速度缓慢，而粒子群算法容易陷入局部最优。许多学者从算法优化、组合优化的角度，分析两种算法的优缺点，将粒子群算法与遗传算法进行结合，即利用遗传算法遗传算子来解决粒子群算法陷入局部最优的问题，并应用于许多领域，取得了较多的研究成果。1 9 9 8 年，e b e r h a r t 和a n g e l i n e 各自在比较了遗传算法和p s o 算法的优缺点的基础上，提出混合式g a p s o 模型，并证明融合算法较前两者具有更优的性能【3 3 】【3 4 】。文献 3 5 】引入选择算子，选择每次迭代后的较好粒子复制到下一代，以保证每次迭代的粒子群都具有就较好的性能，这种算法对某些单峰函数效果良好。文献 3 6 】分别提出了自己的变异算法，基本思路均是希望通过引入变异算子跳出局部极值点的吸引，从而提高算法的全局搜索能力，得到较高的搜索成功率。文献 3 7 】结合p s o 算法的快速收敛能力和遗传算法的全局优化能力，提出一种解决多q o s 约束的组播路由问题的算法。文献 3 8 1 总结了3广西大学硕士掌位论文基于遗传粒子群算法的选播q o s 路由算法的研究将遗传算法、粒子群算法及其融合算法应用于多目标优化问题求解的研究。文献 3 9 1 在线性递减权重粒子群算法的基础上提出了一种新的准粒子群优化算法，它借鉴了遗传算法中交叉的思想并采用了对偶算法模型改善了算法的优化速度和收敛特性。文献 4 0 】提出了一种新的基于群体适应度方差自适应变异的粒子群优化算法。文献 4 1 1 提出了带变异算子的p s o 算法，在算法搜索的后期引入变异算子，使算法摆脱后期易于陷入局部极优点的束缚，同时又保持前期搜索速度快的特性。因此，关于遗传算法和粒子群算法结合的应用已有许多研究成果，但将其应用于选播路由的研究还很少。鉴于遗传粒子群算法的有效性和选播q o s 路由研究的重要意义，将遗传粒子群算法应用于选播q o s 路由领域，并对原有算法进行改进以提高选播路由的性能，是一项十分值得研究和具有挑战性的工作。1 3 本文的研究内容本文针对网络选播路由的特点，运用遗传算法的交叉操作和变异操作、粒子群算法的基本思想，提出一种基于遗传粒子群算法的网络选播q o s 路由算法，使之能够用于求解选播q o s 路由问题。本课题的研究内容主要有以下几方面：( 1 ) 研究选播的背景及其通信服务技术，其中重点分析选播路由的发展0 现状及实现技术，并指出今后解决的问题。( 2 ) 定义选播q o s 路由网络模型，根据具体的情况和对选播不同的q o s 要求来定义不同的优化目标函数。( 3 ) 根据遗传算法的交叉操作和变异操作、粒子群算法的基本思想的优缺点，融合两种算法，改进两种算法的操作，设计实现一种基于遗传粒子群算法的网络选播q o s 路由算法。( 4 ) 鉴于网络中用户的不同需求，改进目标函数，将所提出的算法应用于求解有时延约束的选播q o s 路由优化问题和多参数的选播q o s 路由优化问题。( 5 ) 在n s 2 中进行仿真，对本文提出的算法进行了仿真实验和性能分析评价。1 4 本文的组织结构本文的结构安排如下：第一章绪论。分析选播及其q o s 路由的研究背景及国内外研究现状，阐述论文的研究内容，最后简述论文的总体结构。第二章相关理论知识介绍。对本文研究所涉及的选播通信服务、粒子群优化算法、遗传算法、i pq o s 作简单的介绍，分析选播服务的网络模型及其路由问题。第三章基于遗传粒子群算法的选播q o s 路由算法的设计。提出结合遗传算法和粒子4基于遗传粒子群算法的选播q o s 路由算法的研究群算法的原因、策略，介绍一种更新算子操作，以及遗传算法的交叉操作和变异操作的改进，提出一种基于遗传粒子群算法的选播q o s 路由算法。第四章选播q o s 路由算法仿真实验。描述分别在单源点和多源点请求服务的情况下的基于遗传算法和粒子群优化算法的有时延约束和多个参数约束的选播q o s 路由问题。介绍算法的仿真实验，对算法的有效性和可行性进行分析。通过实验分析基于遗传粒子群算法的选播q o s 路由算法的优越性。第五章总结与展望。简单叙述所设计的基于遗传粒子群优化算法的选播q o s 路由算法的作用和取得的成果，指出我们现有工作的局限性以及下一步研究的工作。5广西大学硕士学位论文基于遗传粒子群算法的选播q o s 路由算法的研究第二章相关理论知识介绍本章主要介绍选播通信服务、q o s 路由、粒子群算法、遗传算法等与研究内容相关的基础理论。2 1 选播通信服务2 1 1 选播的定义选播是一种新型的网络服务，其定义为：选播是通过对一组提供相同服务的主机赋予相同的选播地址，使得客户可以从中选择离它最近( 或最好) 的服务主机的通信方式。选播的定义中暗含了一种思想，即一个客户端发送一个数据包到具有一个选播地址的一组服务机中，但是它并不在意这个数据包被投递到这组机子的哪个服务器。当一个客户端要发送一个数据包到选播服务器时，由于一组服务器是由一个选播地址来标志的，所以通过更改包头的选播地址来完成，然后路由器把这些数据包投递到最匹配这个选播地址的服务器上。选播是这样的通信方式是一种点到多点中任一点的方式。根据选播的特点，使用选播服务可以大大简化一些应用。比如，选播队列可用来从一组可行服务器中找出合适的一个服务器，以提高多传送队列的有效性。特别地，多镜像网址可共享单个的选播地址，这样，用户只需要发送一个请求就可取得所需的信息。图2 1 给出了选播服务的示意图，服务器a 、服务器b 、服务器c 具有相同的选播地址，客户机a 、客户机b 要确定用服务器a 、b 、c 中的哪一个服务器提供服务。在该图中，采用最少跳数的策略，客户机a 选择服务器a 提供服务，而客户机b 贝, w j 选择服务器c 提供服务。6广西大学硕士掌位论文基于遗传粒子群算法的选播q o s 路由算法的研究图2 1 选播服务示意图f i g 2 - 1f i g u r eo fa n y c a s ts e r v i c e2 1 2 选播技术的应用选播从提出至今，相关技术得到很大的发展，选播技术的应用主要有以下方面【3 】：( 1 ) 最优服务器选择从选播的定义可以看出，选播的基本功能是在一组服务器中为用户选择一个“最优”的服务器，这也是提出选播的最初的目的。从应用的方面看，这种服务器可以简单地被分为两类：一类是复制服务器，另一类是具有相同、相似属性的节点。例如，同一个子网内的所有路由器。目前提高网络服务性能和服务效率的一种常用手段是复制服务器。目前使用复制服务器的应用例子在网络等领域有很多，各个开发商可以使用分散服务器到不同的地理位置的方式来提高服务能力，平衡服务器和网络的负载。用户应用程序是根据某个地址来连接的，所以对于一组服务器来说，用一个选播地址来表示，用户却不用分辨具体的服务器，就可以得到性能最好的服务器。这样不仅方便了用户的使用，而且又提高了服务的性能，并且能避免用户盲目参与选择所带来的损失。( 2 ) 支持主机自动配置除了复制服务器外，支持主机的自动配置也是选播服务被提出的另一个动机。这个应用主要针对d n s 及类似的服务。在有了选播服务之后，用户在进行d n s 解析时，根据选播服务的概念，只需要向全球唯一的某个代表d n s 服务的知名选播地址发送查询请求即可得到地址解析的结果。这样主机就不必依赖特定的网络，即使主机移动到一个新的网络也不需要重新配置本地d n s 服务器地址。7广西大学硕士掌位论文基于遗传粒子群算法的选播q o s 路由算法的研究( 3 ) 其它应用领域选播能有效地分摊网络中不同链路的负载。这个特性可以被其它服务利用，例如，有许多学者将选播作为组播的基础，文献【1 1 】中选播使p i m s m 能够支持多个组播树拥有多个汇聚路由器，而文献 1 2 q h 选播运用在域内组播路由协议的设计中，以便减少带宽的开销，减轻流量的汇聚。在移动组播服务中，选播路由技术被用来支持移动节点和外地本地代理之间的m u l t i c a s t 通信。以此提高m u l t i c a s t 的效率，移动主机用选播连接最近的、可用的本地或者外地代理，代理通过一条至l j m u l t i c a s t 路由器的选播路由来转发m u l t i c a s t 消息，以便减少端到端的时延。2 2q o s 技术q o s 在m t f 中的定义为“as e to f s e r v i c er e q u i r e m e n t st ob em e tb yt h en e t w o r kw h i l et r a n s p o r t i n gaf l o w ，即网络在传输数据流时要满足的一系列服务要求，具体可以量化为传输时延、抖动、丢失率、带宽要求等指标。而路由包含两个基本功能：一是搜集并不断更新网络的状态信息；二是根据搜集的信息计算可行路径。q o s 路由( q o sr o u t i n g ) 的基本任务是为一次连接寻找一条有足够资源的并能满足q o s 要求的可行路径。q o s 路由与尽力而为的路由之所以不同，是因为q o s 路由通常是面向连接、有资源预留功能，并且能够提供有质量保证的服务；而尽力而为的路由有可能是面向连接的，也可能是面向无连接的，根据当前可获得的资源的不同，服务质量方面也有所不同。2 2 1q o s 定义q o s 在i 江c 2 3 8 6 【4 2 】中描述为：q o s 是网络在传输数据流时要求满足的一系列服务请求，可以量化为时延抖动、丢失率、带宽、时延、吞吐量等性能指标。此处的服务具体是指数据包经过若干所接受的传输服务，强调端到端( e n dt oe n d ) 或网络边界到边界的整体性。q o s 反映了网络元素在保证信息传输和满足服务要求方面的能力。q o s 朔- - 种描述【4 3 】为：q o s 是指发送和接受信息的用户之间，以及用户与传输信息的综合服务网络之间的关于信息传输的质量约定。这个约定可以看成是服务提供者承担支持用户的给定的服务质量的一个契约，当且仅当用户按照约定的信息流特征产生数据。换言之，服务质量是用户与服务提供者两方面主客观标准的统一，因为它不仅包括用户的要求，而且包括网络服务提供者的行为。用户对所要求的服务类型和相应的传输性能和质量等要求较高，所以i n t e m e t 上进行媒体通信服务时，在这方面要满足用户。网络服务提供者的行为则指满足用户的要求而达至l j i n t e m e t 针对某一类服务所能提供和达到的性能与质量。2 2 2i pq o s 的体系结构在不影响当前i p 协议相关特性的情况下，在其基础上通过修改i p 协议或补充其它机制在网络层实现q o s 就是i p q o s l 4 4 j 。i p q o s 的目的是不仅为因特网应用提供不同的服务质8广西大学页士学位论文基于遗传粒子群算法的选播q o s 路由算法的研究量，而且须根据应用要求保证服务性能。为实现i p q o s ，目前i e t f 提出了多种i p q o s 体系结构，主要包括：集成服务体系结构( i n t s e r v ) 、区分服务体系结构( d i f f s e r v ) 、多协议标签交换( m p l s ) ，下面就简单介绍下集中体系结构：( 1 ) 集成服务体系结构( i n t s e r v )i n t s e r v 体系结构是在流的等级上预约资源。i n t s e r v 模型为了保证严格的服务性能，是工作在端到端的资源预留( r s v p ) 机制下，。i n t s e r v 的主要缺点是所有的操作都是基于单个流的，造成了路由器尤其是核心路由器处理和存储大量的流信息，同时，协议开销大，在具体的实现中还存在可扩展性较差。( 2 ) 区分服务体系结构( d i f f s e r v )为解决i n t s e r v 协议存在的开销大和可扩展性差的缺点，研究者提出了区分服务体系结构。在d i f f s e r v 中，旨在定义一种既能实施i pq o s 又能更容易扩展的方式，按类区分服务，因而不需要基于流的端到端的资源预约机制，实现起来简单，可用于大规模网络。但是预防拥塞能力比较脆弱是d i f f s e r v 的缺点。( 3 ) 多协议标签交换( m p l s )m p l s 能提供较之传统i p 路由更精确的网络状态信息，所以更有利于路由的计算，实质上是一个转发机制。m p l s 网络中的q o s 路由的目的就是把流量主干看作是被路由的对象，从而实现负载均匀分布。为了防止拥塞，可以通过q o s 路由为已经存在的标签交换路径重新选路。可以看出，q o s 路由与i p 网络体系结构相结合的优点就是，能够进一步优化网络资源的利用，并能更好的为业务流提供q o s 保证，使得网络通信服务更有效率，同时也更能满足用户的不同需求。2 2 3q o s 路由中的参数度量在选择路径的时候，一般通过多个参数度量来描述各种业务需求的特性，如带宽、时延、抖动、丢包率以及费用等。根据对整个路径q o s 特性影响的不同，可以把q o s 度量分为三类：可加度量、可乘度量和凹性度型45 。通常把网络表示为有向连通图g = ( v ，e ) ，其中哟节点集合，e 为图中连接两个节点的链路集合，每条链路p 化纠印和上述某些q o s 度量相关。例如，可以定义一个时延函数为：d ? e o r + ，其中r + 为正实数集，函数值c 俐是链路p 亿砂钮考虑了队列的费用代价。同样可以类似地定义其它度量参数的函数值。这些与链路相关的度量参数合起来称为链路状态。同样地，对于每个网络节点，也有一些q o s 度量参数与之相关，这些参数合称为节点状态。链路状态和节点状态合为网络状态。根据运算规则，这些参数度量可以分为加性参数度量、乘性参数度量和凹性参数度量。设所似砂为链路p “砂e 的某一参数度量，对于任意路径尸似砂= “u ，七谚，各种参数度量的特性如下：加性参数度量：如果度量m 满足所以砂- - - m 以矽+ 脚俐+ + 聊传砂，则称m 是加性的。9广西大学硕士学位论文基于遗传粒子群算法的选播q o s 路由算法的研究例如：时延，时延抖动和费用等。乘性参数度量：如果度量m 满足肌以砂= _ 7 ，z 化砂锄俐母锄传砂，则称m 是乘性的。例如：包丢失率。凹性参数度量：如果度量m 满足删亿v ) = r a i n r e ( u , 妒，聊俐，m ( g w ，则称m 是凹性的。例如：带宽。满足业务流q o s 需求的路径并不一定是传统意义上的最短路径w i ，而是满足条件的认为是最好的路径。通过研究表明，不同的q o s 度量的数目多少都会对路由算法的复杂性造成很大影响。其中对于凹性度量，把对网络拓扑进行剪枝操作这样的步骤假如算法的设计中，剪除不满足约束的链路【4 8 1 。可乘度量可以转换为可加度量。2 2 4q o s 路由策略q o s 路由算法是实现q o s 路由的核心研究部分，对q o s 路由算法可以用以下几方面进行评价：第一，计算的复杂度要低，与传统的路由算法相比不应有过多的计算开销；第二，扩展性高，能适合大规模网络下的要求；第三，能适合于“尽力而为”的i p 网络的结构。根据路由的状态信息的维护机制和路径计算方法的不同，q o s 路由算法可以分为三类：源路i 扫( s o u r c er o u t i n g ) 、层次结构路( h i e r a r c h i c a lr o u t i n g ) 、分布式路由( d i s t r i b u t e dr o u t i n g ) 1 4 6 1 。( 1 ) 源路由算法源路由算法，即源端节点根据全局信息计算可行路径。每个节点都持有整个网络状态信息，包括网络的拓扑结构和每个链路的状态。基于这些信息，路径的选择在本地源节点进行。源节点维护全局网络状态的同时进行本地计算整个路由，这样不仅能够避免分布式算法带来的很多不便，同时又能够确保无环路由。算法的可扩展行较差是源路由算法面临的最大问题，因为每个节点必须维护全局的网络状态信息，而这些信息又是动态的、实时更新的。对于大型的网络来说，频繁的信息更新会造成很大的网络负载。此外，q o s 路由协议提供的网络状态信息的不精确性对源路由算法的影响相对较大，导致算法得到的路径最终不能满足业务需求。( 2 ) 层次结构路由算法层次结构路由算法，即网络中的节点形成一个多级的层次结构，分层递归选路。组中选择出一个能代表本组的物理节点作为逻辑节点，该逻辑节点维护更高一层的网络状态信息。由算法的特点可知算法有较好的扩展性，网络节点只需要维护部分全局状态的信息业是其优点之一。此外，层次结构路由算法不仅继承了源路由算法的简洁性又避免了源路由算法扩展性差的问题，还继承了分布式算法的一些优点。但是网络状态的汇聚导致状态信息不精确这样的缺点也不容忽视，这使得算法必须具有在一定程度上容忍不精确状态信息的能力。( 3 ) 分布式路由算法1 0基于遗传粒子群算法的选播q o s 路由算法的研究分布式路由算法，即每一节点通过距离矢量计算每一跳路由。这类算法是通过分布式计算来选择路径，算法需要在节点之间交换一些各节点掌握的控制信息，每个节点把持有的网络状态信息共同来用于整个路径的搜索。只在源节点和目的节点间进行路由计算的分布式算法，则存在着较好的可扩展性和较快的响应时间这样的优点，另外多条路径可以同时并行计算的特点使其算法成功的概率有所增大。缺点是，基于全局状态的分布式路由算法也存在扩展性差的问题，并需要发送更多的消息。2 3 粒子群算法群居昆虫以集体力量觅食、御敌、筑巢，单个个体只能完成简单的任务，而由单个个体组成的群体却能完成复杂的任务，这种群体所表现出来的“智能”称为群智能( s w a r mi n t e l l i g e n c e ，s 1 ) h 9 】，如蜜蜂采蜜、筑巢，蚂蚁觅食、筑巢等。从群居昆虫互相合作进行工作得到启迪，研究其中的原理，以此设计的新的算法被称为群智算法【5 0 j 。粒子群算法【5 1 1 ( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 是由e b e r h a r t 和k e n e d y 于19 9 5 年共同提出的，源于对鸟群扑食行为的研究。由于粒子群算法具有计算速度快、概念简明、依赖的经验参数较少，实现方便等特点，它己成功应用于诸多领域的求解。粒子群算法首先应用于神经网络训练【5 l l 中，随着粒子群算法的不断发展，逐渐在各个领域都得到了广泛的应用，诸如多目标优化问题方面【5 2 1 、电力系统方面【5 3 1 、移动通信方面刚等等。下面将介绍基本粒子群算法及几种改进算法。2 3 1 基本粒子群算法“群”( s w a r m ) 的概念来自于人工生命，满足人工生命的五个基本原则【56 。p s o 算法通过多鸟群觅食的行为而研究出来的。研究者发现鸟群在飞行过程中，虽然每只鸟在飞行的过程中会有许多不可预测的行为，但是整个鸟群总保持一致性，每只鸟彼此间也保持着最适宜的距离。通过研究表明，发现诸如鸟群、蚁群等生物群体中存在着一种社会信息共享机制，这种机制可以为群体的进化提供了一种优势，而p s o 算法形成的基础就是这个。通过文献【5 5 】的描述，我们可以想象这样一个场景：在一个空间中只有一块食物，一群鸟在随机搜索食物，所有的鸟都不知道食物在什么地方。但是却又知道它们所在的位置离食物有多远。怎么去找这个食物呢? 搜寻目前离食物最近的鸟的附近区域【5 5 】就是一个较好的方法。如果把一个优化问题看作是在空中找食的一个鸟群的话，那空中飞行的觅食的鸟就可以当作是p s o 算法中在解空间中进行搜索的一个“粒子”( p a r t i c l e ) 。“食物”就是优化问题的最优解。速度和加速度是粒子用于本身状态的调整，没有质量和体积，所以它的概念是一个折衷的选择。因此p s o 算法也可看作是对简化了的社会模型的模拟，社会群体中的信息共享是推动算法的主要机制。在p s o 算法中，每个粒子都要随时根据自己的飞行经验和其他粒子的飞行经验来调1 1广西大掌硕士g 啦论文基于遗传粒子群算法的选播q o s 路由算法的研究整自己的方向，每个粒子在飞行过程所经历过的最好位置，就是粒子找到的本身的最优解，这个叫做个体极值( p b e s t ) 。那整个群体所经历过的最好位置，就是整个群体目前找到的最优解这个叫做全局极值( g b e s t ) 。每个粒子都要通过这两个极值来不断变化自己，从而产生新一代群体。实际操作中通过由优化问题所决定的适应度函数值( f i m e s sv a l u e )来评价粒子的“优劣”程度。显然，每个粒子的行为就是根据当前迭代过程的最优粒子在解空间中进行搜索。在p s o 算法中，当前的每个粒子具有速度和位置，且对应一个可行解，粒子根据速度通过不断调整自己的位置来搜索新解，且都能记住自己搜索到的最好解，记作只，以及整个粒子群经历过的最好位置，即目前搜索到的最优解，记作只。每个粒子都有一个速度蹄位置丘设：z ，= g n ，而：，工椭) 为粒子i 的当前位置。v i = n 。，b 2 ，) 为粒子i 的当前飞行速度。只= 0 儿，p 脚，p 加) 为粒子i 所经历的最好位置，也就是粒子i 所经历过的具有最好适应值的位置，称为个体最好位置。对于最小化问题，目标函数值越小，对应的粒子的适应值就越好。名= p g l 以：，p 印) 为整个粒子群所经历的最好位置，也称为全局极值。粒子根据下面两个公式来更新自己的速度和位置：屹( t + 1 ) = v u ( ，) + q ，i ji o ( p o ( ，) 一( f ) ) + c ：吒，( r ) ( ( ，) 一而( f ) )( 2 1 )( ，+ 1 ) = ( ，) + 屹( t + 1 )( 2 2 )其中：下标丁表示粒子的第，维，“，表示粒子f ，f 表示第，代，五和厂2 为均匀分布于【o ，1 】之间的随机数，q 和c ，为加速度限定因子。从上面的公式可以看出是又三部分组成：第一部分是粒子目前的速度，说明了粒子目前的状态；第二部分是认知部分( c o g n i t i o nm o d a l ) ，表示粒子本身需要进行的改变；第三部分为社会部分( s o c i a lm o d a l ) 。三个部分共同决定了每个粒子的空间搜索能力。第一部分起到了平衡全局和局部搜索的能力，第二部分使粒子有了足够强的全局搜索能力，避免局部极小，第三部分体现了粒子间的信息共享。在这三部份的共同作用下粒子才能有效的到达最好位置。算法中粒子不仅要根据速度调整自己的位置，还要受到设定的最大速度v m a x 和最小速度v m i n 的限制。如果k 超过最大速度时时将被限定为v m a x ，当k 小于最小速度时将被限定为v m i n 。v m a x 的选择不应超过的粒子宽度范围，因为如果v m a x 太大，1 2基于遗传粒子群算法的选播q o s 路由算法的研究粒子可能飞过最优解的位置；如果v m a x 太小，可能降低粒子的全局搜索能力。2 3 2 带惯性权重的粒子群算法为了提高算法的收敛性能，s h i 和e b e r h a r t 于1 9 9 8 年对p s o 算法的速度项引入了惯性权重w 【5 7 1 ，并提出在进化过