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

摘费摘要近年来，多媒体通信和分布式环境中的协同工作等应用的出现促进了组播通信的发展，同时，多种应用需要提供服务质量( q u a l i t yo f s e r v i c e ，q o s ) 保证，因此研究在多媒体通信中，如何保证服务质量要求以及实现多媒体数据的组播通信是发展的方向。目前有很多智能优化算法用于解决q o s 组播路由问题，但都存在不足，因此探索研究新的启发式智能优化算法，对目前现有算法进行改进，使之能够更盘了地应用十求解q o s 组播路由问题是一个重要课题。r j i 常用的用于解决q o s 组播路由的算法有很多种，遗传算： 上是近几年提出的一利l 新犁优化算法，它具有并行搜索、群体寻优的特点，已经广泛应用于各种具自in p 复杂度的问题中。但是遗传算法存在易陷入局部收敛等缺陷，凼此如何找到一种新型的、改进遗传算法不足之处的智能优化算法是面临的重要问题。量子遗传算法是量子计算与遗传算法结合的产物，目前的研究表明量了遗传算法能够有效地改进常规遗传算法的不足。由于对量子遗传算法的研究还刚川：始，应用范围还相当有限。本文研究了将智能优化算法用于解决q o s 组播路由问题，提出了一种应用鲑j i 遗传算法解决q o s 组播路由问题的方案。关键词：组播路山，q o s ，遗传算法，量子遗传算法型堕型型塑兰兰垡堡塞一竺! 坠里a b s t r a c ta st h ed e m a n d sf o rq u a l i t yo fs e r v i c e ( q o s ) b ym u l t i s e r v i c ei ni n t e r n 。a r er a p i d l yi n c r e a s i n g ，e f f e c t i v ea n de f f i c i e n tq o ss u p p o r th a sb e c o m i n gm o r ea n d ”o 。i m p o r t a n t t h er o u t i n gt e c h n o l o g yi so n eo ft h ek e yr o l e st og u a r a n t e eq o s ，s ot h er o u t i n gm e c h a n i s ma n dq o sm u s tb eb e c o m et o g e t h e ra sa l lo ft h ep r e s e n a l g o r i t h m st os o l v eq o sm u k i c a s tr o u t i n gp r o b l e m sh a v es e v e r a ll a c k s ，i t sas e r i o u sp r o b l e mt oi m p r o v et h eo p t i m i z i n ga l g o r i t h m st h e r e ，r ek i n d so fa l g o r i t h m st os o l v eq o sn m l t i c a s tr o u t i n gp r o b l e m ，a b o v ea i i , g e n e t i ca 1 9 0 r i t h mi san e wo p t i m i z i n go n e ，a n dh a v eb e e nu s i n gt os o l v et h en p cd r o b l e ma tt h es a m et i m e ，i th a ss o m el i m i t a t i o n s s o ，h o wt of i n dan e w ，b e t t e rt i m i z i n ga l g o r i t h mi sas e r i o u sm a t t e r , q u a n t u mg e n e t i ca l g o r i t h i st h 。c 。m b i n a t i o no fq u a n t u mc o m p u t a t i o na n dg e n e t i ca l g o r i t h m - p r e s e n tr e s e a r c h e sh a v es h o w nt h a tq g ac a ne f f i c i e n t l yr e m e d yt h el a c ko fc g ab u tt h er e s e a r c ho fq o a j u s tb e g i n ，a n ds t i l lh a si t sl o c a l i z a t i o n 1 h i sp a p e rf o c u so nu s i n go p t i m i z i n ga l g o r i t h mt os o l v eq o sm u t i c a s tr o u t i n g口r o b l m n a n dp u tf o r w a r dap r o j e c tw i t hq u a n t u mg e n e t i ca l g o r i t h mk e y w o r d s ：m u l t i c a s tr o u t i n g ，q o s ，g e n e t i ca l g o r i t h m ，q u a n t u mg e n e t i ca l g o r i t h m- i i 南京邮电学院学位论文独创性声明y7 6 5 2 1 0本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电学院或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。研究生签名：葺纽生日期：0 2 咝生壁南京邮电学院学位论文使用授权声明南京邮电学院、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权南京邮电学院研究生部办理。研究生签名：阜! 益一一导师签名：妊生4 日期：曼生：竺! 多南京邮电学院硕士研究生学位论文引言引言课题背景：q o s 路由算法是支撑网络传输的关键技术，是随着网络的出现而诞生，随着网络规模的扩大而发展起来的。性能出色的路由算法为数据准确及时的传递、新业务的应用和服务质量的保证提供了必要的保障。目前常用的用于解决q o s 组播路由的算法有很多种，遗传算法是近几年提出的一种新型优化算法它具有并行搜索、群体寻优的特点，已经广泛应用于各种具有n p 复杂度的问题中。但是遗传算法存在易陷入局部收敛等缺陷，因此如何找到一种新型的、改进遗传算法不足之处的智能优化算法是面临的重要问题。量子遗传算法是量子计算与遗传算法结合的产物，目前的实验表明，量子遗传算法能够有效的改进常规遗传算法的不足。本人i 作：量子遗传算法的研究尚处于起步阶段，因而其应用也是有限的。从理论上说，凡是可以采用遗传算法进行优化求解的领域都是量子遗传算法的应用对蒙。在整个课题的研究期间，本人对该课题所涉及的相关背景、国内外研究现状和方案的可行性进行了一定深度的研究，提出了将量子遗传算法应用于求解q o s 组播路由问题，并进行了仿真实验。通过将结果与常规的遗传算法进行比较，得出了量子遗传算法比常规的遗传算法更有效的结论。本文组织：全文共分五个章节，内容组织如下：第一章是组播路由问题的概述，首先对计算机网络的单播、组播通信进行了综述，主要介绍了i p 组播的发展历史、工作原理、实现方案。第二章是q o s 组播路由问题及其算法的综述，主要包括以下几个部分：组播问题的概念、原理，提出了服务质量要求的概念，并且对q o s 组播路由中的分类、控制模型等做了介绍，最后分析了现有解决q o s 组播路由问题的各种算法，介绍了遗传算法及其在q o s 组播路由中的应用。第三章论述了一种新型的智能优化算法量子遗传算法，包括概念、原南京邮电学院硕士研究生学位论文引言理、算法流程以及目前对量子遗传算法的研究动态。第四章提出了一种基于量子遗传算法求解q o s 组播路由问题的算法方案，并对算法进行了仿真，实验结果表明，与遗传算法等求解q o s 组播路由的算法相比，基于量子遗传算法的q o s 组播路由算法有效性好，并说明了它的可行性。第五章总结，并对本课题的进一步研究方向进行了展望。- 2 南京邮电学院硕士研究生学位论文第一章组播通信概述1 1 引言第一章组播通信概述现代社会中，协同合作几乎是解决问题不可缺少的要素。然而目前人们大多居住比较分散，如何让人们超越地理位置的局限去协同合作是通信网络要解决的问题。计算机通信网络上的组播通信方式就是解决这一问题的手段之一。组播通信是指多个参与者之间的通信。它的特征是源节点发送信息，多个接受者接收。在日常生活中，多媒体教学、视频会议等都是组播通信的典型应用。人们对计算机网络的组播通信应用的要求很早就有。当时由于分组交换网的网络层缺乏对组播通信的支持，组播通信的应用是用多个点到点通信来实现。多地址电子邮件、多点的文件分配以及i n t e m e t 的新闻发布等等都是这种方法实现的。然而，很多场合的组播通信应用不能靠点到点的通信来支持，例如，人们希望能通过分组交换网来传输音频和视频信息，因为这种通信方式比文本自然、直观，为了提高通信的效率和通用性，一般倾向于采用易扩展的组播通信方式。高保真音频和视频需要较大的带宽和严格的实时性，此时若还用点对点通信来实现组播通信，其性能和效率将极为低下。男外还有很多场合如网络会议、远程教育、医疗、分布式交互计算与仿真、计算机支持的协同工作( c s c w )等，都需要高效的组播通信来支持。因此对组播通信的研究具有重要意义。1 2 网络数据传输方式计算机网络中常用的通信方式有单播、组播和广播三种。单播( u n i c a s t ) 传输：在发送者和每接收者之间需要单独的数据通信。如果一台主机同时给很少量的接收者传输数据，一般没有问题。但如果有大量主机希望获得数据包的同份拷贝时就很难实现，因为这将导致发送者负担沉重、延迟过长以及网络拥塞，而且为了保证一定的服务质量还需要增加硬件和带宽。组播( m u l t i c a s t ) 传输：提高了数据传送效率，减少了主干网的带宽要求南京邮电学院硕士研究生学位论文第一章组播通信概述以及主干网出现拥塞的可能性。组播组中的主机可以是在同一个物理网络中，也可以来自不同的物理网络( 如果不同网络之间的路由器支持组播通信方式的话) 。广播( b r o a d c a s t ) 传输：是指在整个i p 子网内广播数据包，所有在子网内的主机都将收到这些数据包。广播意味着网络向子网主机都投递一份数据包而不论这些主机是否乐于接收该数据包。然而广播的使用范围非常小。，只在本地子网内有效，因为路由器会封锁广播通信；伺时广播传输增加非接收者的开销，如判断是否为所需信息包所需的时间等。1 3 组播通信概述1 3 1 组播工作原理组播是一种允许一个或多个发送者( 组播源) 发送单一的数据包到多个接收者( 一次的，同时的) 的网络技术。组播源把数据包发送到特定组播组，而只有属于该组播组的地址才能接收到数据包。组播可以大大节省网纠带宽，因为无论有多少个目标地址，在整个网络的任何1 条链路上只传送单一的数据包。1 3 2 组播通信的实现方案在单播模型中，数据包通过网络沿着单路径从源主机向目标主机传递，但在组播模型中，组播源向某一组地址传递数据包，而这一地址却代表一个主机组。为了向所有接收者传递数据，一般采用组播分布树描述i p 组播在网络里经过的路径。组播分布树有四种基本类型：泛洪法、有源树、有核树和s t e i n e r 树。1 泛洪法( f l o o d i n g )这是最简单的向前传送组播路由算法，并不构造所谓的分布树。其基本原理如下：当组播路由器收到发往某个组播地址的数据包后，首先判断是否是首次收到该数据包，如果是首次收到，那么将其转发到所有接1 ：3 上，以确保其最终能到达所有接收者；如果不是首次收到，则抛弃该数据包。泛洪法的实现关键是“首次收到”的检测。这需要维护一个最近通过的数南京邮电学院硕士研究生学位论文第一章利播通信概述据包列表，但无需维护路由表。它适合于对组播需求比较高的场合，并且能做到即使传输出现错误，只要还存在一条到接收者的链路则所有接收者都能接收到组播数据包。然而，泛洪法不适合用于i n t e m e t ，因为它不考虑链路状态，并产生大量的拷贝数据包。此外，对于高速网络而言，“首次收到”列表将会很长，占用相当大的内存；尽管它能保证不对相同的数据包进行二次转发，但不能保证对相同数据包只接收一次。2 有源树有源树也称为基于信源的树或最短路径树( 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 的缺点是：要为每个缎播源构造各自的分布树，这样的话，当数据流量不大时，构造s p t 的开销相对较大。3 共享树共享树也称r p 树( r p t ) ，是指为每个组播选定一个共用根( 汇合点r p或核心) ，以r p 为根建立的组播树。同一组播组的组播源将所要组播的数据单播到r 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 ) 中特定组的成员所需的链路数目最少。若考虑资源总量被大量的组使用的情况，那么使用资源较少最终就会减少产生拥塞的风险。s t e i n e r 树相当不稳定，树的形状随组中成员关系的改变而改变，且对大型网络缺少通用的解决方案。所以s t e i n e r 树只是一种理论模型，而非实用工具。目前，出现了许多s t e i n e r 树的次优启发式生成算法。有核树是由根到所有组成员的最短路径合并恧成的树。a b a l l a r d i f e 在1 9 9 7年9 月的基于核的组播路由体系结构( c o r 3b a s e dt r e e s ( c b t ) m u l t i c a s tr o u t i n ga r c h i t e c t u r e ) ( r f c 2 1 8 9 蛇1 和r f c 2 2 0 1 ) 中介绍了有核树。南京邮电学院硕士研究生学位论史第一章纽播通信概述共享树在路由器所需存储的状态信息的数量和路由树的总代价两个方面具有较好的性能。当组的规模较大，而每个成员的数据发送效率较低时，使用共享树比较合适。但当通信量大时，使用共享树将导致流量集中及根( r p ) 附近的瓶颈。1 3 3 组播地址分配组播通信中，我们需要两种地址：个i p 组播地址和一个e t h e m e t 组播地址。其中，i p 组播地址标识个组播树，同时由于所有i p 数据包都封装在e t h e m e t帧中，所以还需要一个组播树e t h e m e t 地址。为了使组播正常工作，主机应该能够同时接收单播和组播数据，这意味着主机需要多个不同i p 和e m e m e t 地址。i p 地址方案专门为组播划出一个地址范围，在i p v 4 中为d 类地址，范围是2 2 4 0 0 0 到2 3 9 2 5 5 2 5 5 2 5 5 ，并将d 类地址划分为局部链接组播地址、预留组播地址、管理权限组播地址：同时在i p v 6 中为组播地址提供了许多新的标识功能，表1 1 为i p v 4 和i p v 6 的组播地址格式，其中i p v 6 协议中特殊域的定义见表1 2 。表1 1i p v 4 和i p v 6 的组播地址格式 p v 4 组搔地址格式| ol2343 11lo组标志符m v 6 组播地址格式o781 11 21 51 61 2 71 1 1 1 1 1 1 1f l a g ss c o p e组标志符局部链接地址：2 2 4 0 0 0 2 2 4 0 0 2 5 5 ，用于局域网，路由器不转发属于此范围的i p 包。预留组播地址：2 2 4 0 1 0 2 3 8 2 5 5 2 5 5 ，2 5 5 ，用于全球范围或网络协议。管理权限地址：2 3 9 0 0 0 2 3 9 2 5 5 ，2 5 5 2 5 5 ，组织内部使用，用于限制组播范围。- 6 南京邮电学院硕士研究生学位论文第一章组播通信概述表1 2i p v 6 中特殊域的定义域值含义f l a g s0 0 0 0永久组播地址0 0 0 1动态组播地址s c o p e0 0 0 1本地结点0 0 1 0本地链路0 1 0 1本地网点1 0 0 0本地组织1 1 1 0全局组播地址其它保留或未指定1 4 本章小结本章主要讨论了i p 组播的发展历史和体系结构，对多媒体通信中的组播通信问题进行了分析和归纳，重点是介绍组播通信的工作原理和实现方案。与此同时简要介绍了单播通信和广播通信。为了满足多媒体通信对网络服务质量的要求，研究如何在无连接的l p 网中进行组播通信时引入面向连接的q o s 路由机制是目前研究的热点问题。下一章将介绍q o s 组播路由。南京邮电学院硕士研究生学位论文第二章q o s 组播路由及算法2 1 引言第二章q o s 组播路由及算法当前的高速网络需要支持一个大范围的、通信集中的、实时的多媒体应用。这种要求对网络提出了许多新的挑战。其中最关键的一个问题就是服务质量路由( t h eq u a n l i t y o f - s e r v i c e ( q o s ) r o u t i n g ) ，即通过所要求的q o s 参数选择网络路由。2 2q o s 组播路由2 2 ，1 组播路由文献“1 指出，通信网络的路由功能可分为两个方面：一是在连接建立阶段为通信会话选择一个路由：二是确保该会话的分组沿指定的路由转发。面向连接的通信进程执行完整的路由功能，而面向无连接的通信进程并不那么严格的执行路由功能，有时是收到分组后再为它计算路由，有时则是用软状态来设置路由通道。组播路由比较复杂。首先，组播通信地址不具有层次性，不含有组成员位置或标识的任何信息；在多个节点之间计算路由，本身也增加了计算的复杂性；另外参加组播通信的用户可以动态更新，组成员的更新和网络拓扑的变化等给组播路由的建立和维护带来困难。2 2 2 服务质量要求一i p 网络的服务质量1 概述：服务质量( q u a l i t yo f s e r v i c e ，q o s ) 是种抽象概念，用于说明网络服务的“良好”程度。在“r f c 2 3 8 6 州卯中定义为：服务质量是“网络在传输流数据时必须满足的一系列服务需求”。这里，数据流指的是从源地址到目的地址南京邮电学院硕士研究生学位论文第二章q o s 组播路由及算法以一定的服务质量进行传输( 单播和组播) 的数据流”。在不同应用系统中，q o s 参数集的定义方法可能是不同的，经常使用吞吐量、差错率、端到端延时、延时抖动等网络性能参数来定义q o s 。在早期的计算机网络及分组交换网络中，网络一般只为业务提供“尽力而为”( b e s t e f f o r t ) 的服务，在这样的网络系统中，所有业务共享并抢占网络资源，业务之间并没有明确的区分，随着技术的发展，人们发现单一的服务类型并不能满足未来业务的发展需要，于是提出了服务质量( 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 的严格程度来分类：i 确定型( d e t e r m i n i s t i c ) q o s 承诺i i 统计型( s t a t i s t i c a l ) q o s 承诺i i i 尽全力型( b e s t e f f o r t ) q o s 承诺从服务质量的实现层次来分类：应用层应用层q o s 参数是面向端用户的，应当采用直观、形象的表达方式来描述不同的q o s ，供端用户选择。传输层传输层协议主要提供端到端的、面向连接的数据传输服务。通常，这种面向连接的服务能够保证数据传输的正确性和顺序性，但以较大的网络带宽和延迟开销为代价。传输层q o s 参数主要有：吞吐量、端到端延迟、端到端延迟抖动、分组差错率和传输优先级等等。网络层网络层协议主要提供路由选择和数据报转发服务。通常，这种服务是无连接的，通过中间点( 路由器) 的“存储一转发”机制来实现。在数据报转发南京邮电学院硕士研究生学位论文第二章q o s 组播路由及算法过程中，路由器将会产生延迟( 如排队等待转发) 、延迟抖动( 选择不同的路由) 、分组丢失及差错等。数据链路层数据链路层协议主要实现对物理介质的访问控制功能，也就是解决如何利用介质传输数据问题，与网络类型密切相关，并不是所有网络都支持q o s ，即使支持q o s 其支持程度也不尽相同。3 q o s 的控制模型咖：i e t f 建立了数种q o s 服务解决方案，主要有：综合服务( i n t - - s e r v ) r s v p1 7 1 1 5 ，区分服务( d i f f - - s e r v ) 们n 叭m ，多标签标记交换( m p l s ) 1 m 。综合服务模型的主要特征就是资源预留。区分服务通过给分组打上不同的标记，把分组分成不同类别，对不同类别的分组给予不同的服务。m p l s 是种转发方案，分组在进入m p l s 域时被赋予个标记，以后就根据这个标记对分组流进行分类、转发、服务。二q o s 组播路由基本概念q o s 组播路由就是根据给定的q o s 参数，避择有足够网络资源的链路来传送组播数据。路由有两方面的基本内容：一是收集网络状态信息并不断更新，另一方面是根据已有信息来为新的连接请求选择一条合适的路由。一个路由算法的性能极大地取决于信息收集的好坏。1 - 加权图模型：网络的拓扑结构和资源容量可以抽象为一个加权图( v ，e ) 。其中节点( v ) 代表网络中的交换设备，边( e ) 代表传输线路。如果传输线路是对称的，则对应的边是无向的。对于大多数实际网络雨言，其链路一般都是非对称的，因而其每一条链路对应于模型中，就是两条有向的加权边。每一条链路都有一个对应于相关q o s 度量的状态。而每一个节点出有相应的状态，它可以单独表示出来，也可以把它折算到与节点相连的链路状态中去。2 状态信息：包括本地信息、全局信息以及状态信息的聚合。3 q o s 度量对于路径p = ( a ，b ，c ，f ，g ) ，用d ( a ，b ) 表示对应链路( 咖) 的度量，则南京邮电学院硕士研究生学位论文第二章q o s 组播路由及算法q o s 度量可以按照性质分为以下三类：凸性q o s 度量如果d ( a ，g ) = m i n d ( a ，b ) ，d ( b ，c b ，d ( f ，g ) ，那么度量由传输通道中的瓶颈决定，即此度量仅与路径上的某个瓶颈链路的q o s 度量有关，如剩余带宽、剩余缓存空间、链路速率等。可加性q o s 度量如果d ( a ，g ) ；d ( a ，b ) + d ( b ，c ) + + d ( e g ) ，那么度量由传输通道中所有链路的特性共同决定，如时延、时延抖动、费用等。可乘性度量如果d ( a ，曲= d ( a ，b ) x d ( b ，c ) x x d ( f , g ) ，即度量为所有链路对应度量的乘积，如可靠性等。如取d ( a ，b ) = l n d ( a ，b ) 】，则乘性度量就转换为加性度量。4 路由策略根据网络信息如何保存，以及可行路径如何实现，路由策略可分为三种：源路由、分布式路由和分层路由。源路由中，每个节点都保存全局网络信息，包括网络拓扑信息和每条链路的状态信息。根据该全局信息，源节点在本地计算出条合适的路由。然后，在选择的路由上传送一个控制包，通知路由上的每个节点，说明其前继者和后继者为谁。每个节点的信息更新由链路协议完成。在分布式机制中，可行路径在一个h o p b y h o p 基础上通过分布式方法得到，路径上的各节点通常拥有个距离矢量，通过交互控制消息，并结合各节点所存储的状态信息，来完成路由选择的计算。分层路由是用来解决大型网络中源路由的升级问题。在分层路由中，节点聚集成为节点群，该群进一步递归的聚集成为更高层次的节点群，成为个多层结构。使用源路由算法进行路由选择。三q o s 组播路由的数学模型定义上边主要研究了一些q o s 组播路由问题的基本概念，下边我们讨论建立q o s 组播路由问题的数学模型所需的些重要定义。定义2 1 有向图g = ( v ，e ) ，其中v 是节点集，可以表示交换机、路由器和主机，或者子网；e 是边集，代表通信链路，n - - ivl ，m = lei ，边e i南京邮电学院硕士研究生学位论文第二章q o s 组播路由及算法e ，标识为e i j ：( v i ，v j ) ，表示从结点v i 到之间的条直通的链路，i j t l 2 ，n ，v 。，v j v ，s v 为组播源节点，m e v - s 为组播终点集，r 十表示正实数集，r + o 表示非负实数集。定义2 - 2 边e 4 有三个属性：长度l e ( k m ) ，媒体传播速度t r ( k 耐s ) 和误码e r o定义2 - 3 结点v 的属性：d 3 h i 表示每个结点v i 的入度，即咀v i 为尾的边数；d o u t t 表示为每个结点v i 的出度，即以v - 为头的边数：d i = ( di n i + d _ o u t 0 董m为每个结点的度数：v i 的服务速率为s r ( b i t s ) ，v j = f p t jj ，p b 2 ，p t i k ，k = d i ，i = l 2 ，n ) ，p t i k 表示v i 连接第k 个边的端口，端口有两个属性：端口吞吐率t p ( b i t s ) ，端口缓冲空间b f ( b y t e ) 。定义2 4 每条边有4 个函数：延迟函数d e l a y ( e ) ：e - * r + ；代价函数c o s t ( 曲：e r + ；可利用的剩余带宽函数：b a n d w i d t h ( e ) ：e r + ；延时抖动函数d e l a y i i t t e r ( e ) ：e r + o定义2 - 5 对于任一网络结点n v ，也定义了4 个函数：延时函数d e l a y ( n ) ：v r + ；代价函数c o s t ( n ) ：v r + ；结点分组丢失率p a c k e t _ l o s s ( n ) ：v r + o ：与调度机制相关的结点延迟抖动d e l a y _ j i t t e r ( n ) ：v r o定义2 - 6 根据以上定义，对于给定的源节点s v 。，终点集m ，s 和m 组成的组播树t ( s ，m ) 存在下列关系：d e l a y ( p ，( s ，f ) ) ；= 办j 掣( p ) + 斑? 缈( 帕托一( ，”吨 ( 砟)c o s t ( t ( s ，埘) ) = c 吲( g ) + c f ( 一)f ( 竹“，)t f n ( ，( 2 。1 )( 2 - 2 )b a n d w i d t h ( p r 0 ，r ) ) ；m i n ( b a n d ，i d l h ( e ) ，p p r ( s ，l ”( 2 3 )d e l a y f i u e r ( p r ( s 。，) ) = 如母一j i t t e ，o ) + 咖姆一j i t t e r ( ，i ) ( 2 - 4 )_ p f ，) t j ， i np a e l t e t t o s s ( p t q ，f ) ) = l n n p a c k e t l o b s ( n ) ) ( 2 - s )o t p tc j 0其中，p t ( s ，t ) 为组播树t ( s ，m ) 上源节点s 到终点t 的路由路径。可见本模型只考虑网络结点的包丢失率( 因缓冲溢出) ，而忽略链路的包丢失犁，这与实南京邮电学i 皖硕士研究生学位论文第二章q o s 组播路由及算法际情况相符。定义2 7 q o s 组播路由问题可以定义为：给定有权图g = ( v ，e ) ，定义了边函数和节点函数，源节点s ，目的节点集d ，节点之间存在通路，求有权图中的一个子图，包含所有的组播节点( 包括源节点和目的节点) ，并且满足边函数和节点函数的约束。2 3q o s 组播路由算法2 3 ，l 引言为进行有效的组播通信，确定组播路由是非常关键的。组播路由问题的目标是找到一种算法和策略，在给定的网络和组播需求的情况下，找到一种链路连接方式，使得网络资源能够得到有效利用。这类问题不可能用最优方案来解决。我们所寻求的只是一种次优化韵、在实际中可以接受的方案。组播路由算法就是用来确定组播树的。组播树是通过在每介路由器设置路由表建立的。路由表上给出了为使信息传送到组成员，此路由器应选择哪个邻接节点。由于网络的动态变化，每个路由器的路由表也要定期更新。此外路由表的设置要保证不能有回路的产生。近年来，各国学者在这方面进行探索，提出了一些快速有效的算法。2 3 2 组播路由算法及其分类大多数现有的组播路由主要关注以下几个问题：带宽受限的组播路由，延迟受限的组播路由延迟受限的最小花费组播路由( 即受限的s t e i n e r t r 6 e 问题) ，以及延迟和延迟抖动受限的组播路由。算法分为以下几类：1 组播源路由算法：源路由算法要求每个节点保存一个全局状态信息。大多数解决n p 复杂度组播路由问题的优化算法都是基于特定的选择尺度，通过每次在树中添加节点来构成一棵受限树。如延迟和延迟抖动的受限组播树问题( r b 算法) ：首先用d i j k a s t r a s 算法构造以延迟为关键字的最短路径树。如果该树不满足延迟抖动的限制，算法就从最短路径树中找最大延迟的路径，再从该路径开始生成一棵可行树。每次从此树中的一个节点到树外的一个目的南京邮电学院硕士研究生学位论文第二章q o s 组播路由及算法节点的“好”路径被添加到树中。注意，路径必须完全脱离树，并且不使树违背约束。重复以上过程直到所有目的节点都包含在树中。2 组播分布式路由算法：文献4 1 提出了一种遗传算法在分布式路由中的应用。每个节点只保留一个局部状态。用分布式计算方法在每个节点收集最新局部状态信息来寻找路径。运用遗传算法形成个前向环境，以及计算探测等待时间的计算公式。、3 分层路由算法：文献5 1 提出了一种针对基于p n n i ( p r i v a t e _ n e t w o r k- n e t w o r ki n t e r f a c e ) 分层网络的q o s 路由算法。算法中关键的一点是针对p n n l分层网络结构的拓扑集，考虑不精确信息的能力。2 4 遗传算法应用于q o s 组播路由问题2 4 1 引言遗传算法是近年来发展起来的种搜索寻优技术，由于其出色的搜索寻优性能，目前已被广泛的应用于各个领域。它是模仿生物进化过程中的生物染色体的交叉：选择，变异的原理，利用达尔文“优胜劣汰，适者生存”伪思想，对实际应用领域的一些问题进行搜索寻优的技术。，2 4 2 遗传算法简介遗传算法的操作流程包括编码、初始种群的生成、选择、交换、变异等过程。下边分别介绍如下：( 1 ) 编码：g a 在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据这些串结构数据的不同组合便构成了不同的点。( 2 ) 初始群体的生成：随机产生n 个初始串结构数据，每个串结构数据称为一个个体，n 个个体构成了一个群体。g a 以这n 个串结构数据作为初始点开始迭代。( 3 ) 适应性值评估检测：适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。( 4 ) 选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机南京邮电学院硕士研究生学位论文第二章q o s 组播路由及算法会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。( 5 ) 交换：交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。( 6 ) 变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，g a 中变异发生的概率很低，通常取值在o 0 0 1 0 0 1 之间。变异为新个体的产生提供了机会。第四章将讨论遗传算法的具体操作。2 4 3 遗传算法应用于q o s 组播路由1 时延受限组播路由算法文献6 提出一种通用的遗传算法，但该算法采用n x n 的维二进制编码机制( 其中n 为网络节点数) ，这种编码方式的算法编码、解码过程复杂，并且算法的搜索空间随网络规模的增大而急剧增大，算法效率低。文献7 1 也提出了一种时延受限组播遗传算法，但该算法容易陷入未成熟收敛，算法的精度不好。文献“”提出了一种求解时延受限组播路由问题的混合遗传算法( h g a ：h y b r i dg e n e t i ca l g o r i t h m ) ，采用树型编码，每个染色体就是覆盖源节点和目的节点集合的一棵子树，遗传操作直接作用与这介个体，节省了编码和解码的时间。2 有时延和时延抖动约束的组播路由算法文献“”设计了一种基于动态惩罚函数的遗传算法。惩罚函数的形式采用不可微精确惩罚函数。由于遗传算法对问题的可微性没有限制，因此克服了基于梯度算法不能处理不可微函数的缺陷，从而能够有效的求得可行的极值点。文献2 0 设计的遗传算法采用了受限斯坦利最小树( c m s t ) 算法。在m c m s t算法的基础上，提出了一种适合延时与延时抖动要求的组播路由遗传算法模型，并进行了实验分析。结果表明，与其他方法相比，该方法具有搜索速度快、效率高等特点，避免了采用启发式搜索技术对问题知识的要求，具有较强的通用南京邮电学院硕士研究生学位论文第二章q o s 组播路由及算法性和鲁棒性，能够满足多媒体应用对延时和延时抖动的要求。3 带宽约束的组播路由算法带宽约束的组播路由问题可归结为带宽约束的s t e i n e r 树算法。求满足约束的最优s t e i n e r 树，是个n p 复杂度问题。文献t 2 1 1 提出了一种采用遗传算法来进行s t e i n e r 节点搜索的方法。2 5 本章小结本章主要讨论了q o s 组播路由的概念、原理，现有的q o s 组播路由算法及其分类，介绍了遗传算法在q o s 组播路由中的应用研究。南京邮电学院硕士研究生学位论文第三章量子遗传算法3 1 引言第三章量子遗传算法量子遗传算法是量子计算与遗传算法相结合的产物。目前这一领域的研究主要集中在两类模型上：一类是基于量子多宇宙特征的多宇宙量子衍生遗传算法( q u a n t u mi n s p i r e dg e n e t i ca l g o r i t h m ) 1 2 2 1 , 另一类是基于量子比特和量子态叠加特性的遗传量子算法( o e n e t i cq u a n t u m a l g o r i t h m ，g q a ) 1 2 3 1量子遗传算法( q g a ) 是对上述两类模型进行的改进，采用了多状态基因量子比特编码方式和通用的量子旋转门操作，引入静态和动态调整旋转角机制和量子变异，使得量子遗传算法更具有通用性，且效率更高。下面将讨论量子遗传算法及其研究现状。3 2 量子遗传算法3 2 1 。量子信息论量子信息是信息科学和量子力学相结合的新兴交叉科学。诺贝尔物理奖学金获得者f e y n m a n 曾指出：量子力学的精妙之处在于引人了几率幅( 量子态)的概念t 2 4 1 0 量子信息科学采用这个奇妙的量子态作为信息单元( 量子比特) 。一旦用量子态来表示信息，就实现了信息的量子化。于是，信息的传输、处理和提取的过程必须服从量子物理原理。信息的传输就是量子态在通道中的传送，信息处理就是对信息实施变换，而信息的提取就是对信息系统进行量子测量。3 2 2 量子计算基本原理量子世界的奇妙特性( 如叠加态、相干性和纠缠性) 使得量子信息系统突破经典信息系统的极限。如量子计算机能轻易敏破现有的密码体系，量子密码能提供绝对安全的保密体系等。量子信息领域的权威b e n n e t t 和d i v i n c e n z o 在自然杂志中对量子信息做了总结性评价：从经典信息到量子信息的推广就像从实数到复数的推广一样。量子计算正是利用了量子理论中的有关量子态的堕塞墅皇兰堕堡圭旦茎竺兰堡望兰第三章量子遗传算法叠加、纠缠和干涉等特性，通过量子并行计算有可能解决经典计算中的n p 复杂度问题。尤其是1 9 9 4 年s h o r 提出第一个量子算法，用来求解大数质因子分解的经典计算难题，该算法可用于公开密钥系统r s a 。1 9 9 6 年g r o v e r 提出随机数据库搜索的量子算法，在量子计算机上可实现对未加整理数据库根号n 量极的加速搜索。从此，量子计算以其独特的计算性能引起了广泛瞩目，迅速成为研究的热点。国内在量子计算领域也作了一定的工作，尤其是中国科技大学在量子神经网络等领域，国防科技大学在量子算法模拟系统领域都作了卓有成效的工作。3 2 3 量子遗传算法的基本原理在引言中所述的两类模型中，第一类算法中的多宇宙是通过分别产生多个种群获得的，并没有利用量子态，因此仍属于常规遗传算法；第二类算法主要用来解决o 一1 背包问题，编码方案和量子旋转门的演化策略不具有通用性。因此文2 2 1 提出了量子遗传算法( q g a ) 的概念。量子遗传算法建立在量子的态矢量表述基础上，7 将量子比特的几率幅表示应用于染色体的编码，使得一条染色体可以表达多个态的叠加，并利用量子旋转门和量子非门实现染色体的更新操作，从而实现了目标的优化求解。1 量子比特编码在量子计算机中充当信息存储单元的物理介质是一个双态量子系统，称为量子比特。量子位与经典位不同就在于它可以向时处在两个量子态的叠加态中。比如：i 妒 = a 1 0 + 1 1 ( 3 1 )( a ，) 是两个复常数，满足t 2 l2 + lpj 2 _ 1( 3 2 )其中口l o 和夕i l 分别表示自旋向下和自旋向上态。所以一个量子比特可同时包含态i o 和ll 的信息。在量子遗传算法中，采用量子比特存储和表达一个基因。该基因可以为一，个“0 ”态或“l ”态，或它们的任意叠加态。即该基因所表达的不在是某一确南京邮电学院硕士研究生学位论文第三章量子遗传算法定的信息，而是包含所有可能的信息，对该基因的任一操作也会同时作用于所有可能的信息。采用遗传算法中的二进制编码，对存在多态的问题进行量子比特编码，如两态用一个量子比特进行编码，四态用两个量子比特进行编码。该方法的优点是通用性好，而且实现简单。采用多量子比特来编码多状态基因如下所示，f 耐。：哌磋，畋嚷吒畋咄1、劬。i 屏。尾尻属。压：尾尾。尾：属。j妈一3 其中g ：代表第t 代、第j 个个体的染色体，k 为编码每一个基因的量子比特数，m 为染色体的基因个数。采用量子比特编码使得一个染色体可以表达多个态的叠加，并使量子遗传算法比经典遗传算l 法拥有更好的多样性特征。采用量子比特编码可以获得较好的收敛性，随着1 口12 ，1p12 趋于0 或1 ，量子比特编码的染色体将收敛到一个单一态。2 量子遗传算法流程量子遗传算法的算法流程具体如下：( 1 )初始化种群q ( b ) ；( 2 )对初始化种群中的各个体实施一次测量，得到组状态p ( t 0 ) ；( 3 )对各状态进行适应度评估：( 4 )记录下最佳个体状态及其适应度值：( 5 )w h i l e 非结束状态d ob e g i nt 文+ l ：量子旋转门调整和量子非门调整；对种群q ( t ) 实施一次测量，得到一组状态p ( t ) ；对各状态进行适应度评估；记录下最佳个体状态及其适应度值。算法的第一步是初始化种群q ( t o ) ，种群中全部染色体的所有基因g 0 )南京邮电学院硕士研究生学位论文第三章量子遗传算法被初始化为【击，击 ，这意味着个染色体所表达的是其全部可能状态的等概率叠加：旧广2 若赤卜户( 3 - - 4 )其中，乩为该染色体的地k 种状态，表现形式为一长度为m 的二进制串( x i ，x 2 ，x 。) ，其中x ( i _ l ，2 ，3 ，m ) 要么为0 ，要么为1 。算法的第二步是对初始种群中的个体进行一次测量，以获得一组确定的解p o ) = p ：，p ：t ，或 ，其中，p ：为第t 种群中第j 个解( 第j 个个体的测量值) ，表现形式为长度为m 的二进制串，其中每一位为0 或1 是根据量子比特的概率( i 口：1 2 或i 麒1 2 ，i 一1 ，2 ，m ) 选择得到的。其中测量过程为：随机产生一个 0 ，1 数，若大于概率幅的平方，则测量结果取值为1 ，否则取值为0 。然后对这一组解进行适应度评估，记录下最佳适应度个体作为下一步演化的目标值。随后，算法进入循环迭代阶段，随着迭代的进行，种群的解逐渐向最优解收敛。在每一次迭代中，首先对种群q ( t ) 的测量，以获得一组确定的解p ( t ) ，然后计算每一个解的适