基于群智能优化算法的qos组播路由算法研究

《基于群智能优化算法的qos组播路由算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

论文题目：基于群智能优化算法的QoS组播路由算法研究专业：通信与信息系统硕士生：杨原（签名）___________指导教师：王亚民（签名）___________摘要近年来，伴随互联网技术的快速发展，越来越多新型通信需求随之出现，尤其是日益兴起的视频会议、在线教育、IP电话等多媒体实时业务。此类的应用往往会对网络的通信能力提出更高的要求，同时要求计算机在支持多媒体业务时，使用更好的组播通信方式。多媒体实时业务对延时、带宽、费用、丢包率等QoS参数有不同的需求，多约束QoS组播路由算法已经成为互联网技术研究领域的热点问题之一。本文在研究多约束QoS组播路由算法现状的基础上，构建了QoS组播路由问题的数学模型，并提出了一种将遗传算法和蚁群算法有效的结合起来的新型算法—遗传蚁群混合优化算法(CGAACA，theCombinationofGeneticAlgorithmandAntColonyAlgorithm)。算法前期利用遗传算法生成若干组优化解；算法中期，为了确保遗传算法和蚁群算法在适当时机能够融合，本文在这里设置了一个遗传算法进化程度函数，通过遗传算法的进化程度，动态地控制两种算法的最佳融合时机；算法后期，把遗传算法的若干优化解转换为蚁群算法里的信息素初值，利用蚁群算法得到满足一定QoS约束条件的最优解。此外，本文在算法前期和后期加入了邻近搜索的概念，采用了最大差异性交叉策略、保优选择策略和双重信息素更新策略。这些新策略使该算法既克服了遗传算法后期进化缓慢和蚁群算法前期信息素缺乏等缺点，又保留了遗传算法的并行性和蚁群算法正反馈等优点。本文将遗传蚁群混合优化算法应用于QoS组播路由问题，使用Matlab进行仿真。实验证明，相比较于基本遗传算法和基本蚁群算法，本文算法不仅具有可行性、有效性，而且具有更好的全局收敛性，实现了对网络资源的有效优化，对未来网络的发展提供了理论依据。关键词：服务质量；组播路由；遗传算法；蚁群算法研究类型：理论研究型万方数据 万方数据 Subject:ResearchonQoSMulticastRoutingAlgorithmbasedonSwarmIntelligenceOptimizationAlgorithmSpecialty:CommunicationandInformationSystemName:Yangyuan(Signature)Instructor:Wangyamin(Signature)ABSTRACTWiththerapiddevelopmentofcomputernetworktechnology,moreandmorecommunicationdemandsappear,especiallytheriseofdistancelearning,videoconference,IPTV,networkgameandsoon.Theseapplicationshaveproposedhigherandmoreurgentrequirementsonthebearingcapacityofexistingnetwork,atthesametime,thecomputerisrequiredtouseabetterwayofcommunicationnamelythemulticastcommunicationwhenitsupportsmultimediabusiness.Multimediareal-timebusinesshasdifferentrequirementsonQoSparameters,suchastimedelay,bandwidth,cost,packetlossrate.Multi-constraintsQoSmulticastroutingalgorithmhasbecameoneofhotissuesinthefieldofcomputernetworkresearch.Onthebasisofmulti-constraintsQoSmulticastroutingalgorithm,thepaperbuiltthemathematicalmodelofQoSmulticastrouting,andproposedanewalgorithmnamedtheCombinationofGeneticAlgorithmandAntColonyAlgorithm(CGAACA),whichcombinedgeneticalgorithmandantcolonyalgorithmeffectively.Ontheearlystageofalgorithm,afewgroupsofoptimizationsolutionsweregenerated;onthemiddlestage,inordertoensurethefusionofgeneticalgorithmandantcolonyalgorithmatthebesttime,thegeneticalgorithmevolutiondegreefunctionwasgiventocontrolthebestfusiontimeofthetwoalgorithms;onthelatestage,someoptimizationsolutionsofgeneticalgorithmwereconvertedintopheromoneinitialvalueofantcolonyalgorithm,andthenusedantcolonyalgorithmtogettheoptimalsolutionwhichmeetQoSconstraints.Inaddition,thepaperaddedtheconceptofneighborhoodsearchontheearlyandlatestageofalgorithm,andusedthemaximumdifferencecrossoverstrategy,optimalchoicestrategyanddualpheromoneupdatestrategy.Becauseofthesenewstrategies,thealgorithmnotonlyovercameshortcomingsoftheslowevolutionofgeneticalgorithm’slatestageandthelackpheromoneofantcolonyalgorithm’searlystage,butalsoremainedadvantagesofparallelismofgeneticalgorithmandpositivefeedbackofantcolonyalgorithm.万方数据 ThepaperappliedtheCombinationofGeneticAlgorithmandAntColonyAlgorithmtoQoSmulticastrouting,andusedMatlabtosimulate.Theresultshaveshowedthatthisalgorithmnotonlyhasfeasibilityandeffectivenessbutalsohasbetterglobalconvergencecomparingwiththegeneticalgorithmandantcolonyalgorithm.Atthesametime,itachieveseffectiveoptimizationofnetworkresourcesandoffersacertaintheoreticalsupportonthefuturedevelopmentofnetwork.Keywords:QoS;Multicastrouting;Geneticalgorithm;AntcolonyalgorithmThesis:ApplicationResearch万方数据 目录目录1绪论........................................................................................................................................11.1选题背景及研究意义..................................................................................................11.1.1选题背景............................................................................................................................11.1.2研究意义............................................................................................................................21.2国内外现状..................................................................................................................21.3论文的主要内容和章节安排......................................................................................32QoS组播路由技术.................................................................................................................52.1组播路由技术..............................................................................................................52.1.1组播的原理........................................................................................................................52.1.2组播路由协议...................................................................................................................72.1.3组播路由算法分类..........................................................................................................82.2QoS参数.......................................................................................................................92.2.1QoS概述............................................................................................................................92.2.2QoS主要参数...................................................................................................................92.2.3QoS度量..........................................................................................................................112.3QoS组播路由.............................................................................................................112.3.1QoS组播原理.................................................................................................................112.3.2QoS组播路由经典算法研究......................................................................................132.4本章小结....................................................................................................................143遗传算法和蚁群算法..........................................................................................................153.1遗传算法....................................................................................................................153.1.1遗传算法简介................................................................................................................153.1.2遗传算法的基本概念..................................................................................................153.1.3遗传算法流程................................................................................................................183.1.4遗传算法特点................................................................................................................183.2蚁群算法....................................................................................................................193.2.1蚁群算法简介................................................................................................................193.2.2蚁群算法基本原理.......................................................................................................193.2.3蚁群算法的数学模型..................................................................................................203.2.4蚁群算法流程................................................................................................................213.2.5蚁群算法的特点............................................................................................................223.3本章小结....................................................................................................................23I万方数据 目录4基于遗传算法和蚁群算法融合的混合优化算法..............................................................244.1QoS组播路由问题的数学模型.................................................................................244.2混合算法的背景描述.................................................................................................254.3CGAACA算法设计思想及总体框架.......................................................................264.4CGAACA算法具体设计方案...................................................................................264.4.1遗传算法部分................................................................................................................264.4.2遗传算法和蚁群算法相融合部分............................................................................314.4.3蚁群算法部分................................................................................................................314.5CGAACA算法的描述...............................................................................................324.6本章小结....................................................................................................................335CGAACA算法的QoS组播路由仿真实验及分析............................................................345.1开发工具介绍............................................................................................................345.2网络拓扑随机生成算法............................................................................................345.3仿真实验参数............................................................................................................355.4实验仿真与结果分析................................................................................................365.4.1算法可行性分析............................................................................................................365.4.2算法有效性分析............................................................................................................395.4.3算法的网络代价性能分析.........................................................................................435.5本章小结......................................................................................................................................456总结与展望..........................................................................................................................466.1总结..............................................................................................................................................466.2展望..............................................................................................................................................46致谢..........................................................................................................................................48参考文献..................................................................................................................................49II万方数据 1绪论1绪论1.1选题背景及研究意义1.1.1选题背景近年来，随着互联网应用的不断发展壮大，网络应用范围也越来越广。对于网络而言，用户需求越来越丰富，相应的对相关的技术的要求也越来越高。传统的网络主要提供服务HTTP、FTP、E-mail等单纯的数据业务，而现在人们对视频、音频等多样化实时传输有了更多的需求。这些业务的竟相出现，使传统的单播和广播的通信方式不能满足网络信息传输的要求，所以组播技术应运而。组播技术是一种介于单播技术和广播技术之间的数据传输方式，可以有效地减少整个网络的带宽需求，降低服务器和网络的负载，使信息传输准确高效。因此，组播通信方式是更适合多媒体网络传输需求的新一代实时通信方式。QoS(QualityofServices，服务质量)指反映网络性能好坏的一系列参数。它主要表达了用户对服务的质量满意程度。这一系列的参数主要包括带宽、端到端时延、吞吐量、[1]链路带宽约束、源节点到不同目的节点之间的时延抖动和丢包率等。这些参数通常也用于评价一个网络服务性能的优劣。网络应用把各种具体QoS参数值提供给网络，网络根据提出的参数要求而提供不同的通信服务。对于传统的简单网络应用，尽力而为的传输服务模式已经可以到达需求。但是现代的多媒体网络应用增加了很多实时性的高要求，就必须要求网络支持具有不同QoS要求的多媒体实时业务。QoS保证机制的构建是网络高速运转的重要部分，对网络服务提供者和用户来说是必须且急迫的部分。提高QoS服务质量的关键点中的一个就是对QoS组播路由算法。QoS保证机制通过对不同级别的数据包高效合理的安排，加快了网络传输的过程，更好的管理网络资源的分配，从而实现对网络资源的优化。网络路由算法是当今计算机网络性能表现的一个决定性的条件。越优化的算法使得网络具有更低的网络时延、更大的网络带宽和更小的丢包率。QoS组播路由指的是在最大能力满足QoS参数约束的情况下，组建一个包含源节点和目的节点的组播树。这颗组播树不仅仅满足信息发送和接受要求，还能最大化的满足用户对QoS的要求。这就要求现代网络同时有组播技术和QoS保证机制来实现。关于这个问题，很多学者提出了相应的路由算法，但是都有一定的缺陷。如何组建多约束QoS条件下的最优组播树，即多约束QoS组播路由问题成为计算机网络技术领域的一个难点和热点。对此问题的研究不仅会使网络应用和网络与更快速的发展，还会为将来通信服务的具体应用提供基础理论。1万方数据 西安科技大学硕士学位论文智能优化算法又称为现代启发式算法，是通过模拟或者揭示某种自然现象或过程发展而来的。该类算法易于理解，具有全局化性能、通用性强、且适合于并行处理。因此，群智能优化算法得到广泛的研究和应用。近年来，随着智能优化算法的兴起和发展，将智能优化算法应用到传统算法难于解决的多约束QoS组播路由问题上，成为了该领域的研究热点。1.1.2研究意义单播、广播需要做的就是把数据包从一个指定的源节点，经过传输到达一个或者是多个目的节点。针对该问题，产生了一种更快速的新的技术方案—组播技术。组播技术在获取网络拓扑信息以及数据约束信息的基础上，建立一个包含源节点以及目的节点的[2]组播树。建立组播树的目的是让不同的目的节点间可以使用一些共用的路径，因而节约了很多的网络资源，在实际意义上实现了网络优化。组建QoS多约束最优组播树是一个难点，它主要体现在这两点上：(1)NP完全问题：新兴多媒体实时业务对QoS，即费用、带宽、丢包率等，有着不[3][4]同的要求。求解同时有多个相对独立的参数的QoS组播的路由，属于NP完全问题。该类问题很难解决；(2)实际条件的复杂性：QoS组播路由算法是路由协议的关键点之一。因此计算路由算法的时候就必须考虑到复杂的实际条件。组播成员的加入或退出引起的网络拓扑结构的变化、节点之间的变化、组播树的扩展和维护等，这些实际条件也是QoS组播路由算法复杂的原因之一。QoS组播路由问题的复杂性，使得最优组播树的最优解的搜索范围也不断扩大。传统的枚举法几乎不能求出最优解，即使求出也花费过多时间代价。如此类NP完全问题，现在人们越来越偏向求出相对最满意解。国内外学者根据实际情况研究了很多种求解最优解的算法。这些算法在求解最优解时取得一定的成就，但是不能更好地适应复杂的网络环境，其中成就最为突出的是智能算法。智能算法指的是一些模拟自然过程或者揭示自然现象的算法，智能算法在解决一些复杂的问题上有很好的效果。智能算法具有高效的并行性、很好的鲁棒性和非常广泛的通用性。这些特性使得智能算法越来越多的受到关注，利用不同的智能算法解决复杂的路由问题已经成为QoS组播路由问题的主要趋势和研究方向。1.2国内外现状近年来，在人们日益意识到网络QoS的重要性和必要性的同时加大了QoS方面的考察和研究。一些网络运行商和网络提供者在一定程度上实现了网络的QoS技术支持，随着下一代网络的兴起，更多的多媒体实时业务向网络提出更高的QoS要求，但是现阶段2万方数据 1绪论已有的研究还不够成熟，不足以完全支撑所有的多媒体业务。路由算法指的是数据包从发送端到接收端所经过的路由路径的选择，路由算法通常有下列设计目标的一个或者多个：优化、简单、低耗、稳定、灵活。QoS组播路由指的是在复杂的网络条件下，例如网络拓扑图的变化和资源的重分配，组建满足实际需求的代价最小最优组播树。QoS组播路由属于NP完全问题，即没有算法能得到组播树最优解，只能得到相对最优解。组播路由算法的重要组成部分是组建一棵包含源节点和所有目的节点的代价最小的组播树，将数据包传递到目的节点。学者们围绕如何组建高性能，高效率的组播树进行了大量的分析研究。现在该领域的算法分类为：(1)针对Steiner的启发式算法。此类比较突出的算法有PMST算法、ADH算法和MPH算法。然而这些算法所应用到的网络小而且简单，当今的网络规模日益扩大，实际条件日益复杂，所以此类算法几乎不能满足未来多媒体实时业务对下一代网络的多变的要求。①(2)针对QoS约束Steiner的经典算法。此类比较突出的算法有BSMA算法和KPP算法。然而这些算法结合实际情况后，具有极其复杂的公式和极大的运算量使得人们越来越少的应用到实际网络中去。[5][6](3)现代智能算法。此类算法中突出算法包括遗传算法、蚁群算法、模拟退火算[7][8][9]法、禁忌搜索算法和神经网络等智能优化算法。近年来，随着网络规模的不断扩大，智能算法在QoS组播路由上的应用研究越来越深入。智能算法能很好地被应用在路由算法领域，但是也有一定的缺陷。智能算法其中[10]一个最重要的算法是遗传算法。遗传算法最明显的缺点就是早收敛问题，蚁群算法最明显的缺陷是早期的收敛速度很慢。其他的智能算法也都有一定的缺陷限制算法的发展应用。相当一部分学者用智能算法在组播路由领域取得了很好的成绩。郑振华在蜂群算[11]法的基础上提出了一种基于人工蜂群算法的智能优化算法；ESbensen把经典的智能算[12]法—遗传算法应用在了组播树的组建上，得到了很好的效果；Xiang.F改进了基本遗[13]传算法，并应用在了QoS路由领域上；王新红则研究了和改进了免疫遗传算法在最优[14][15]组播树上的应用；刘芳把免疫算法应用在了QoS组播路由上；同时也存在不少的学者研究两种智能算法的融合算法，也取得很好的成绩。综上所述，智能算法在多约束QoS[16]组播路由算法的应用已经成为了网络路由优化的主要研究方向和发展趋势。1.3论文的主要内容和章节安排本文首先研究和分析了QoS组播路由技术的相关知识，主要包括组播的基本原理、组播路由协议、QoS主要参数和现有的QoS组播路由的经典算法；其次研究了群智能优化算法中的遗传算法和蚁群算法的关键技术，包括算法的基本原理、主要特点和具体实3万方数据 西安科技大学硕士学位论文现步骤；之后结合理论知识提出了QoS组播路由问题的数学模型，并在对遗传算法和蚁群算法的研究基础上提出了一种新的QoS组播路由算法。该算法不仅更好的融合了两种算法，并且加入了一些创新策略：邻近搜索概念、最大差异性交叉策略、保优选择策略和双重信息素更新策略；最后在Matlab上对算法应用在QoS组播路由问题上进行了仿真实验，结果证明了该算法应用在QoS组播路由问题上的可行性和有效性，并研究分析了本文算法和传统算法的网络代价性能对比。第一章介绍和分析了QoS组播路由算法的产生背景和国内外研究现状，论证了QoS组播路由问题具有现实意义。并给出论文的工作内容和章节安排。第二章介绍了组播技术的原理、优点和组播相关算法的分类，从各方面详细描述了QoS参数的相关知识，并对目前经典QoS组播路由算法进行介绍。第三章研究了目前热门智能算法中遗传算法和蚁群算法的基本理论、实现步骤、算法的特点以及其他关键技术。第四章在网络模型的基础上，给出QoS组播路由问题的数学模型，并在此基础上提出一种新型智能化算法应用在QoS组播路由问题上。新算法所采用的的创新策略为：采用最大差异交叉策略和双重信息素更新策略，并两次加入了邻近搜索的限制。本章详细描述了新型算法的基本理论、整体框架和具体实现步骤。第五章对本文提出的新算法进行仿真实验，随机生成随机网络，并在此基础上研究了新算法在QoS组播路由中的可行性和有效性以及网络代价性，证明了新算法在该领域的可行性和有效性。第六章总结了本文的工作内容，并指出了QoS组播路由问题未来的研究方向。4万方数据 2QoS组播路由技术2QoS组播路由技术随着互联网以及相关技术的发展，QoS组播路由作为QoS和组播路由两个重要研究课题的融合，已经成为当前和下一代互联网亟待解决的难题之一。本章将分别对组播路由技术和QoS参数的相关知识进行分析，并对各种QoS组播路由算法进行对比分析。2.1组播路由技术2.1.1组播的原理数据包从源节点传输到目的节点，必须先确定传输路径。不同的传输方式，具有不同的方式来决定其路由路径。当今网络数据包的传输方式主要有三种：(1)单播(Unicast)，单点对单点的通信方式。在发送者和每个接收者之间都是一个单独的通信信道。若大量的接收者想要获得同一种数据包，必须为每一个接收者复制并发送一份相同的数据包。其工作原理如图2.1所示。(2)广播(Broadcast)，单点对所有点的通信方式。在整个子网内广播数据包，子网中的每一个主机都能够收到数据包，不管这些主机是否需要接收这些数据包。其工作原理如图2.2所示。(3)组播(Multicast)，单点对多点的通信方式。从一个或多个发送者向多个接收者发送数据包的过程。组播源把数据包发送到特定的组播组，而只有属于该组播组成员的地址才能接收该数据包。其工作原理如图2.3所示。服务器ba路由器aaa路由器b路由器aba路由器a路由器b客户端C客户端A客户端B图2.1单播数据流5万方数据 西安科技大学硕士学位论文在图2.1中给出了三个客户端，服务器根据每个客户端的需求，分别发送三个数据包，三个客户端分别接受对应的数据包。即使客户端A和客户端C同时请求同一份数据包，服务器也会重复发送数据包a，导致服务器负担沉重、延迟变长、网络出现拥塞。服务器a路由器aa路由器路由器aaa路由器a路由器a接收端接收端非接收端图2.2广播数据流在图2.2中显示了三个不同的接收点，广播的工作方式是每次发送一个数据包，无论需求与否，组内成员都会接受统一的数据包。从这个图可以看粗，此种方式产生了很大的无效的信息，并且还花费了很大的代价。组播传输方式与它们有很大的差别。组播每次都是先收集需要信息的一些点，然后按照不同的需求传输数据包，即按需传递数据包的方式。服务器a路由器aa路由器路由器aa路由器a路由器接收端接收端非接收端图2.3组播数据流6万方数据 2QoS组播路由技术如图2.3的展示方式，不是所有的接收端都是需要该数据报的。在传输之前，组播技术先按照自己的方式收集相关的信息，得知需要传输的接收端。然后在此基础上把同一份数据包传输给需要的点。这种方式在很大的程度上降低了很大一部分的费用代价。并且在一定程度上，对于网络或者是服务器都是降低了工作量。则为很受欢迎的一种传输方式。2.1.2组播路由协议组播路由协议的任务是收集和维护相关的网络状态信息，比如网络拓扑图结构、链路负载程度、路由器和链路的连接状况和路由器的类型等。收集好信息之后，路由算法根据收集的信息来选择路由。在此依据组播成员在网络中分布的密集程度，分成两类。一是密集模式组播路由协议，二是稀疏模式组播路由协议。密集模式组播路由协议，指的是组播成员密集的分布在全网络中，即协议中需求很多的接收端，且有较大带宽。因此它主要采用广播技术来实现传输。稀疏模式组播路由协议，指的是组播成员零散的分布在全网络中，即协议中需求较少的接收端，且带宽有限。因此它主要采用路由选择技术来实现传输。(1)密集模式路由协议①距离向量组播协议(DistanceVectorMulticastRoutingProtocol，DVMRP)DVMRP是第一个支持组播的路由协议，也是现在应用中常见协议的一种。它的开发是基于单播中的RIP协议。DVMRP保留了RIP算法中的一些特性和TRPB算法。采用RPF算法组建传播组播树，并据此传输数据包。DVMRP利用“洪泛和剪除”的方式来维护组播树，因此该协议会浪费大量带宽。②开放式组播最短路径优先协议(MulticastOpenShortestPathFirst，MOSPF)MOSPF是在单播中的OSPF协议的基础上的改进协议。它通过利用是链路状态数据库中的网络图，组建组播成员之间的关系。MOSPF网络中的所有路由器都共享链路信息，实时了解全网络的拓扑结构变化。组播树也随着网络拓扑的变化而变化。MOSPF的缺点是网络中成员数量的的不断增加，CPU资源的消耗随之增大。③协议无关组(ProtocolIndependentMulticast，PIM)PIM-DM类似于DVMRP协议，它也是采用RPF算法组建传播组播树，不同的地方是DVMRP基于距离向量算法，而PIM-DM则不受此限制，可采用多种单播协议。相对于前两种协议，PIM-DM更简单，更独立，且具有最小花费。它的缺点就是扩散和剪除组播树的同时对网络有一定的性能影响。(2)稀疏模式组播路由协议①有核树组播路由协议(CoreBasedTree，CBT)CBT协议是以一个中心路由器为源组建一个共享树。所有组播中的数据包都要经过7万方数据 西安科技大学硕士学位论文此核心路由器。它的主要任务是降低网路中的相关路由器的组播状态，以此在一定程度上增加了可扩展性。它的缺点是在中心路由器周围的数据包过于集中，而导致网络整体性能的下降。②稀疏模式独立组播协议(ProtocolIndependentMulticast-SparseMode，PIM-SM)PIM-SM类似于CBT协议。它采用的也是以一个中心路由器为根，为所有组播组共享一个共享树。不同的是PIM-SM具有更好的灵活性。PIM-SM从共享树开始，不经过RP转发就可以到达最短路径树，组建从源节点到接受节点之间的最短路径树，在很大程度上增加了转发准确率和效率，同时也提高了网络性能。2.1.3组播路由算法分类组播路由算法是确保有效通信的基础，算法的主要目的是组建组播树。组播树的产生是建立在路由器的路由表上的，路由表上收集了路由器相互之间的关系。每个路由器[17]上路由表都是随着网络的动态变化而变化。依据不同的准则，把组播路由算法分为不同的分类。(l)静态和动态路由算法这组分类的依据是允许不允许网络中成员随时加入或者离开组播范围。静态组播路由算法的原理是建立在初始的组播组中的成员上，组建一个初始组播树。算法过程中，组播成员和组播树都不在动态变化，处于静态。算法组建的组播树不会随着网络拓扑的变化而变化。这类算法不会根据实时做出修改。动态组播路由算法因允许组播中成员随时的加入或离开而具有实时性，该类算法的原理是根据网络拓扑结构发生变化而变化。两类算法中后者更能具有实际应用性，(2)集中式、分布式算法这组分类的依据是不同的实现方式。集中式组播路由算法的原理是网络中的每个节点保存整个网络的状态。比如网络拓扑结构等。在获得全网络的信息后再根据具体步骤组建出对应的组播树。这类算法具有简单性和快速性，但具有较大代价。分布式组播路由算法就不要求每个节点都掌握所有的状态信息。每个节点只需要掌握部分相关信息便可以确定自己的路由状态。相对于集中式，该类算法代价小但是计算复杂，速度较慢。(3)无约束、有约束算法这组分类的依据是需不需要考虑QoS约束。无QoS约束的原理是不考虑QoS的相关参数，这类算法主要任务是资源的平均分配的基础上使组播树代价最低。这类算法因无QoS约束而不具有实时性。有QoS约束的原理是考虑QoS的相关参数，这类算法根据多媒体实时业务的要求，8万方数据 2QoS组播路由技术更加合理的选择路由，更加合理的分配现有的资源。在保证实时性的基础上，使得组播树代价最小。这类算法具有实时性。依据不同的分类标准进行相应对比，如表2.1所示：表2.1算法主要分类及特点算法分类主要特点静态路由算法组播组成员固定，组播成员和路由树不发生改变1动态路由算法允许组成员动态加入或离开，组播树会发生改变集中式路由算法节点掌握整个网络拓扑结构，简单，快速2分布式路由算法每个节点掌握局部网络信息，复杂，速度慢有QoS约束要求在给定QoS的条件下使树的费用最小3无QoS约束只优化树的费用，无QoS要求2.2QoS参数2.2.1QoS概述QoS（QualityofService)，服务质量，指的是发送端和用户接收端之间或者是指用户端和信息传输网络之间，传输信息的质量。简单来讲zhikuquan20150721QoS是衡量网络传输质量的指标。的QoS主要是指两个方向：用户的要求和网络提供者的动作。用户要求方面是要求网络给出多媒体实时业务的所需要的服务状态、传输性能和一定的质量保证，多媒体实时业务的QoS需求主要是传输信息的时延、时延抖动、带宽、丢包率等相关的参数。2.2.2QoS主要参数现代网络中的QoS的参数有很多，这里主要考虑的参数指标有如下几种：(1)带宽(Bandwidth)带宽是指单位时间内，网络传输的有效数据包的数量。因多媒体实时业务传输较大的数据，对带宽的要求较高，保证其最小带宽即是保证业务的正常传输。(2)延时(Delay)延时是指发送端发送数据包到接收点的时间的间隔。影响时延的主要原因有转发延时、传输时延、排队延时和路由算法等。对于网络中的非实时业务而言，对延时要求不高，但是对网络中多媒体实时业务来说，对时延的要求较高。在各种时延的原因中，传输时延对实时业务影响最大。时延是难以控制的，但是因它对网络性能有较高的影响力而变得重要。(3)延时抖动(DelayJitter)9万方数据 西安科技大学硕士学位论文延时抖动是指同一个发送源，通过相同的路由路径传输到目的节点的延时差异。当数据包到达路由器时，若无其他等待传输数据包则立即转发出去。若有其他数据包占用路由器，则需等待空闲后传输。如一个数据包从发送源到目的节点耗时80ms，发送另一个数据则耗时95ms，即抖动是15ms。如图2.4，表现的是网络数据包的典型时延。概率密度最小时延最大时延时间抖动图2.4时延抖动示意图(4)丢包率(PacketLossRate)丢包率是指在一定的时间内，由于各种原因丢失的数据包占总数据包的比率。这种丢失现象是不可避免的，只能尽量降到最低。丢包的原因有数据包长度、数据发送频率zhikuquan20150721和网络拥塞等。该参数主要用来测试网络路由的稳定程度。一些多媒体业务的应用能接受丢包率的暂时上升，对正常业务几乎影响。(5)通信代价(CommunicationCost)代价是指在网络中，数据包传输过程的花费代价。一般的网络传输质量评价标准是网络性能和花费的综合评价，即越好的性能同时代价越小，则表示网络传输质量越好越好。[18]不同的业务则有不同的QoS要求，表2.2展现了几种常见的业务对QoS的需求。表2.2常见业务的QoS需求业务带宽时延时延抖动丢包率语音（电话）低高高高视频点播高低高高视频会议高高高高文件传输中低低低电子邮件低低低低Web访问中中低低10万方数据 2QoS组播路由技术2.2.3QoS度量P(a,b,e,,f,g)D(a,b)测量的QoS度量来实现QoS要求。本文用表示路径，用表示对应链路ba),的度量。按性质，(QoS度量分成三类[19]：(1)凹性QoS度量即：(min{(,D,),)aD(ga,b),D,bD(ef,g)}，表示QoS度量取决于链路中的所有度量值的最小值，比如带宽、链路速率等。(2)加性QoS度量即：D(a,g)D(a,b)D(b,e)D(f,g)，表示QoS度量取决于所有链路的QoS度量值得总和，比如时延、时延抖动等。(3)乘性QoS度量即：(,(D),aD)gaD(bbD,(e)f,g)，表示QoS度量取决于所有链路的QoS度量值的乘积，如丢包率等。2.3QoS组播路由zhikuquan201507212.3.1QoS组播原理[20]多媒体实时业务采用组播传播方式时对QoS要求较高，，QoS组播路由和非QoS组播路由所组建的组播树有所差别。例如网络拓扑结构如图2.2所示。服务器R1R4R3R2R5客户端2客户端3客户端1图2.5无QoS约束组播路由11万方数据 西安科技大学硕士学位论文[21]图2.5中非QoS组播路由算法不考虑QoS约束，只考虑最短路径和代价等因素。在此情况下，如图2.5中所示，组建一个包含源节点和目的节点（客户端1，2，3）的组播树。图2.7（a）是此算法生成的组播树。服务器QoS参数（带宽，延时）R1（3，6）（1，4）（3，5）R4R3（1，3）（3，5）R2（5，6）（3，3）（2，4）R5客户端2客户端3客户端1图2.6QoS约束组播路由图2.6QoS组播路由算法不仅考虑到最短路径和代价等因素，还加入了QoS约束。在此情况下，如图zhi2.6所示，组建一个包含源节点和目的节点的组播树。此时，设置kuquan20150721QoS需求为（2.5,11.5），即带宽约束是2.5，时延约束是11.5。图2.7(b)是此类算法的组播树。QoS约束和没有QoS约束两种情况组播树的比较如图2.7所示。这就表明，虽是同一个网络，组播树因有无QoS约束而不同。R1R2R2R3R4R4R5R5(a)无QoS要求的组播树(b)满足QoS要求的组播树图2.7有无QoS要求的组播树12万方数据 2QoS组播路由技术2.3.2QoS组播路由经典算法研究[22]目前的国内外学者对这个领域已经提出许多算法。以下是几种经典算法：(1)最短路径树算法此算法求解所得的组播树，该组播树的特点是从源节点到目的节点链路值最小。若该值指的是时延，则该组播树就是最小时延树。最短路径求解的组播树是树约束的最优[23][24]树。在该算法中，最典型算法是Dijkstra以及Belman-Ford算法。(2)最小生成树算法最小生成树算法是指所组建的组播树的所有链路权重和最小。该算法中典型的算法[25]是Prim算法。Prim算法是自网络一个节点上开始组建组播树，发展到所有的节点。每次发展，算法都会选择链路权重最小的路径。(3)有关Steiner树算法Steiner树指最小总代价。该类算法是组播路由算法的难点和重点。解决Steiner树是NP完全问题。以下算法是具有QoS约束的该类算法。①最短路径思想的启发类的算法此类算法的基础是最短路径算法，并在原算法上有细微改动。初始的状态中，自一个源节点开始组建树，并用最短路径算法依次加入目的节点。zhikuquan20150721②最小生成树思想的启发类的算法此类算法的基础就是在于组建最小生成树的相关算法。该算法用最小生成树算法组建树，之后再根据需求删除不需要的节点。③启发式源路由算法[26][27][28]启发式源路由算法中，经典的是KMB算法，KPP算法以及BSMA算法。KMB算法是Steiner树中最权威的算法。它的基础是先求解出距离完全图和最小生成[29]树，把树的枝干变为最短路径产生子图，最后求解出组播树。KPP算法的前提是算法之前必须满足时延的相关参数约束。它先求解其中两个节点间，并且在此基础上找出能满足时延约束的同时的最小代价路径。在此基础上，求出包含所有节点的完全封闭图。图中的边就是满足延时约束，组建最小生成树。BSMA算法是先把代价作为求解的有效参数，把简单路径当树的超边。该算法通过找k条最短途径取代代价高的路径，降低总代价。该算法是现代时延约束启发式算法中，复杂性最高，代价性能最好。④智能优化算法近年来，智能优化算法日益发展，不少学者把它应用在QoS组播领域中，取得了不[30][31]少成就。智能优化算法主要有遗传算法、禁忌搜索算法、蚁群算法和人工神经网络[32]等。表2.3是经典算法的复杂性对比。13万方数据 西安科技大学硕士学位论文表2.3组播路由经典算法及其复杂性比较路由算法算法关键字典型算法时间复杂度2Dijkstra算法n）（最短路径算每个节点法最短路径3Belman-Ford算法n）（最小生成树2权重和最小Prim算法n）（算法2路径最短基于最短路径的Steiner树算法n）（2剪枝最小生成树基于最小生成树的Steiner树算法n）（2KMB算法nD）（基于QoS的Steiner树算启发式源路由KPP算法（n）法zhikuquan201507213BSMA算法(njlogn)SPH算法、K-SPH算法、启发式分布路由-DMCTC算法、DMCTCD算法遗传算法、模拟退火算法、智能优化算法-蚁群算法等其中，n表示网络中的总节点数，是端到端时延上限。2.4本章小结本章主要介绍了QoS组播路由的相关技术，重点讨论了组播路由的基本概念、组播路由协议、组播算法的分类、QoS主要参数的定义，以及QoS组播路由的几种经典算法。这些基础知识为下文的研究提供了思路和理论依据。14万方数据 3遗传算法和蚁群算法3遗传算法和蚁群算法智能优化算法是一种新兴的起源于对简单社会系统的模拟的演化计算技术，群智能算法的通用性和自适应性等特点，使它广泛的被应用于各个相对复杂的研究领域。目前，在QoS组播路由算法这个领域中也取得了优异的成就。本章主要介绍群智能优化算法中遗传算法和蚁群算法的原理、算法步骤等相关技术，为后面新算法的提出做出理论铺垫。3.1遗传算法3.1.1遗传算法简介遗传算法(GeneticAlgorithm,GA)是一种模拟自然生活进化，具有高效性、并行性的智能算法。1975年，根据“适者生存，优胜劣汰”规律美国JohnHolland首次提出遗传算法的概念。GA把计算机科学和生物进化论原理融合在一起，该算法能在搜索过程中自适应的收集搜索空间的信息，逐渐靠近最优解。由于GA是全局搜索策略，所有具有广泛的应用范围。特别是传统搜索算法解决不了的非线性问题。zhiGA算法具有简单性，通用性和较好的健壮性。kuquan201507213.1.2遗传算法的基本概念GA的基础是生物学中的自然选择和遗传学。它模拟的是这样一个进化过程：一个种群存在着随机初始解集，通过“优胜劣汰”的选择后，再对种群进行遗传操作，实现了种群中的个体重组的过程。每次重组都会出现一组解集，并由适应度函数计算适应值。一直循环整个过程，直到收敛到一定程度。[33]GA中的一些基本概念如下所示：(1)编码(Coding)实际问题中的相关参数，不能被GA算法直接接受。编码是指把相关参数翻译成遗传搜索空间中的展现方式。这种展现方式包括按一定规则构成的个体或者染色体。遗传的编码方式确定了个体重组的规则。将问题的参数翻译成对应的编码染色体是GA的关键点和难点。(2)染色体(Chromosome)染色体即个体，在GA中用一个基因串(或向量)来表示。Xxxx(3.1)12l其中x是串X中的基本单元，l称为基因个数。通常，一个基因组和一个实际问题l15万方数据 西安科技大学硕士学位论文的解相对应。在GA中，不同的编码方式，所产生的个体的表现形式也随之不同。常见的表示形式有二进制和实数。(3)种群(Population)以及种群规模(Pop_Size)个体的集合就是种群。当GA解决实际问题的时候，在随机产生的初始解集里，有目的的全局搜索。随机初始解集合和每次算法产生的新解集都称作种群。每个个体对应实际问题中的一个解，一个种群就对应实际问题的解的集合。种群规模指种群中个体的数量总和。取值过小，即使加快了算法的计算速度，却同时降低了种群多样性，使得算法极易早熟现象。取值过大，确保了种群的多样性，却同时降低了运行速度。故具体问题具体分析。通常情况下，取值范围是在50到150之间(4)遗传算子遗传算子是模拟进化过程的关键点，是GA中最重要的部分。基本遗传算子有：①选择算子(SelectionOperator)根据具体问题和个体的适应度值的大小，选择初始种群中可以保留的染色体。该算子的任务是依据一些的选择准则，选择出上一代种群中较大适应值的个体，复制到下一代种群中，进行算法其他步骤。选择算子的原理是随机选择，但是这个随机并不是完全随机，这个随机选择是建立在个体的适应值上。越高的适应值，复制到下一代的概率越大，越低的适应值，复制的概率越小。目前轮盘选择策略是选择策略中最常见的。zhikuquan20150721②交叉算子(CrossoverOperator)基因重组是生物进化的核心。在GA中，交叉算子是算法的核心。交叉是指种群中内的个体随机组成一对，并且该对染色体上的部分基因以一定的概率交换彼此的位置，最后产生新的个体。一般使用的交叉方式有：1)单点交叉在个体的基因串中，随机选一个交叉点，两个对应的个体在这个点交换彼此的一部分基因串。AABB图3.1单点交叉示意图2)两点交叉在个体的基因串中，随机选两个交叉点，两个对应的个体按照交叉点位置交换交叉点内的部分基因串。16万方数据 3遗传算法和蚁群算法AABB图3.2两点交叉示意图3)均匀交叉两个对应的个体中，每个基因都根据一定的概率交换。AABB图3.3均匀交叉示意图交叉操作是GA产生新个体的主要方法。通过交叉操作，GA的搜索能力能得到快速地提高。③变异算子(MutationOperator)基因突变是生物进化中不可或缺的部分。变异算子同样也是GA中不可缺少的一部分。变异操作是指随机地改变一些个体中的部分基因值，从而产生新的个体，也因此模拟了演化的过程。变异算子不仅仅在一定程度上增加了GA的随机搜索性能，即加快了搜索速度，并且增加了GA种群中的个体多样性，即多样性的增加有效的预防早熟现象的产生。过小的取值，不能体现变异算子的优势，过大的取值，不能有效保留最优解。该算子的取值是根据实际问题，具体分析。表3.1列举了常用的变异算子及其特点。表3.1常用变异算子及特点变异算子名称各自特点适用的编码方式基本位变异标准遗传算法成员符号均匀变异每一个实数以相同概率在域内变动实数高斯近似突变提高对重要搜索区域的局部搜索能力实数(5)适应度(Fitness)适应值是指种群中个体对问题的适应的优劣程度。适应值是GA中选择算子的重要依据。适应值是由适应度函数得出的，无论怎么计算都不产生负值是对于适应度函数的最大要求。一般情况下，越大的适应值，对应的解越接近最优解，最大适应值也就是对应最优解。不同的具体问题，所选取不同的适应值函数，适应值函数直接影响GA的性能。17万方数据 西安科技大学硕士学位论文由于算法后期用到适应值来确定概率，所以一般选取的适应度函数所得到的适应值越大效果越是明显。(6)迭代代数(MaxGen)预设迭代次数是GA中最常用、最简答的结束算法的方法之一。选取值过小，则到不到最优解便结束；选取值过大，则增加计算负载，浪费时间和资源。3.1.3遗传算法流程运用GA解决实际问题时，GA的基本处理流程如图3.4所示：结束确定问题的适应值函数确定问题的GA参数集生成初始种群计算适应值是否满足收敛准则YN输出结果种群p(t)à选择种群P(t+1)结束交叉变异图3.4遗传算法的基本处理流程3.1.4遗传算法特点GA不同与许多传统的算法，主要优点如下：(1)智能性：GA在算法过程中，根据不同的编码策略，遗传算子等步骤来收集最优解的相关信息，根据相关信息自适应的向最优解靠近。(2)并行性：GA的计算方式是并行计算，即同时在多区域搜索最优解。(3)多解性：传统算法是从一个解开始计算，GA是从一个解集开始进行搜索计算。18万方数据 3遗传算法和蚁群算法(4)不确定性：GA中的遗传算子中包含随机的因素，因而在算法进化过程中，解的优化具有不确定性(5)全局优化：GA在搜索过程中比其他算法有更低的陷入局部最优解的可能性。GA的并行性保证了算法的全局搜索能力，从而达到全局最优化，找出整体最优解。3.2蚁群算法3.2.1蚁群算法简介蚁群算法(AntColonyAlgorithm,ACA)，这个算法是一种常用的智能算法。它模拟的是自然界中生物状态－蚂蚁觅食的情况。1992年，意大利学者ColorniA等人根据蚂蚁在觅食中选取路径的行为首次提出的。经过十几年的研究，说明ACA在求解实际的复杂类优化问题中表现了很好的性能。它的原理简单来说是群体中的个个体间的相互影响和作用的同时优化问题。现在ACA的应用广泛，如典型的旅行商问题（TSP）、车间调度问题等。算法在通信方面，如通信负载等，也展现了较强的适应力。3.2.2蚁群算法基本原理研究证明：蚂蚁在搜索食物的过程中，不管外界条件的如何变化，一段时间后，肯[34]定能找到从蚁巢到食物的最短路径。这种现象的产生得助于一种信息素的物质。一般情况下，蚂蚁会产生一定数量的信息素在走过的路径上。信息素具有挥发性和累加性。路径的长短决定信息素的产量：路径长的信息素低。信息素的产生量和路径长度成反比。[35]著名的双桥实验就是蚂蚁的觅食过程的研究。巢穴A巢穴A蚂蚁CCD障碍物ED障碍物EFF食物B食物B(a)开始觅食时(b)找到最短路径时图3.5蚁群觅食示意图19万方数据 西安科技大学硕士学位论文如图3.5所示，有两条路可以从蚁穴A走到食物B，一是蚁穴ACDF食物B；二是蚁穴ACEF食物B。路径一的长度明显小于路径二。3.5（a）是开始觅食，没有信息素在CD、DF、FE、CE上，则蚂蚁会随机选择一或者二。即有50%的蚂蚁选择CD、DF到达食物，50%选择CE、EF到达食物。由于路径的长短不一样，较短路径的蚂蚁会产生更多的信息素在路径上。当第二批蚂蚁从蚁穴A点到食物B，这时，两条路径上都有上一批蚂蚁的信息素残留。路径一上的信息素量高于路径二，此刻会有比例较大的蚂蚁选择CD路径。随着次数的增加，选择较短路径的概率会越变越大。最终，几乎所有蚂蚁都选择路径一。如图3.5（b）所示最终确定一条目前最优的路径。3.2.3蚁群算法的数学模型[36]本文借助TSP问题来描述ACA的数学模型。TSP是典型的组合优化问题，即商旅者从起点的城市开始，经过所有的城市，再回到出发城市，在此基础上寻求一条代价最小的路径。N表示需要经过的城市个数，C表示需要经过城市集合，m表示蚂蚁的总数，di,j1,2,,n表示城市i和城市j间的对应距离。0表示在开始时，信息素在所ijij0有路径连接路径上具有的相同值。t代表的是城市i与j间在时刻t时的路径上的信息素ij大小。开始时，把m只蚂蚁依次放到n个随机城市中，蚂蚁kk1,2,,m根据城市间路径k的信息素的浓度决定所选择得下一个城市。t时刻，蚂蚁k从城市i到j的转移概率为P(t)，ij其计算公式为：ttijijsallowkktt(3.2)Pijtisissallowk0sallowk1ijt是启发函数，ijt代表的是该蚂蚁从城市i期望走到j的值大小；表示dij信息素重要程度，越大表示信息素在转移过程中的作用越大；表示启发函数重要程度，越大表示下一个路径的吸引力在转移中的作用越大；allowk1,2,,m表示需要访问k的城市集合。tatuCallow表示禁忌表，即k用来记录蚂蚁k从开始到现在所有走kk过的城市。信息素具有挥发性，目的是避免过度的信息素而忽视启发信息的选择问题。个体在20万方数据 3遗传算法和蚁群算法遍历完城市后，需要更新对应的信息素。01表示信息素挥发的系数。ijt11ijtijn(3.3)kijijk1k代表第k只蚂蚁在城市i到j的路径产生的信息素；表示蚁群在城市i和j间路ijij径上产生的信息素浓度的和。更新信息素的模型有三种：(1)Antcyclesystem模型k在这个模型中，的公式为：ijQk第k只蚂蚁从城市i访问城市jijLk(3.4)0其他未访问路径Q是常量，指蚂蚁在遍历所有的城市过程中，产生信息素的总和；L代表第k只蚂k蚁此次运算过程中路径的总和。没有访问的路径不增加信息素。(2)Antquantitysystem模型k在这个模型中，的公式为：ijQk第k只蚂蚁从城市i访问城市jijdij(3.5)0其他未访问路径其中，d为代表城市i到j的路径长度；Q为常量。ij(3)Antdensitysystem模型k在这个模型中，的公式为：ijkQ第k只蚂蚁从城市i访问城市jij(3.6)0其他未访问路径其中，Q为一个常量。该模型中，城市间的距离不影响信息素的增加，遍历过的路径具有相同的增量。L表示蚂蚁k此次搜索过程中，经过的所有的路径的总和。搜索完成，蚁群便会进k行下次的搜索。当搜索次数是预先设定的值时，结束整个算法。得到最短路径是LminLl1,2,,NC。minkminl21万方数据 西安科技大学硕士学位论文3.2.4蚁群算法流程其基本算法流程如下图3.6所示。开始M个蚂蚁被置在不同的节点上，时间t=o,初始信息素为常数，最大循环次数，循环次数为NC=0，迭代次数NC=NC+1初始化禁忌表蚂蚁数量k=k+1按照状态转移概率公式选择下一次节点修改禁忌表N集合C中的元素是否遍历完Y信息素的更新N是否满足约束条件Y输出计算结果结束图3.6基本蚁群算法流程图3.2.5蚁群算法的特点ACA的优点：①(1)并行分布式计算。ACA算法同时在多个区域进行搜索最优解故具有并行性。算法中每个蚂蚁依据不同的情况独立的构造不同的解，故具有分布式特性。22万方数据 3遗传算法和蚁群算法(2)较强的鲁棒性。即停止部分蚂蚁的工作，整个系统依然能正常运转。(3)全局搜索。随机的路径选择，路径的不确定性，增大最优解的寻找可能性。(4)易结合性。ACA求解过程是分步进行的，在分步过程中随时可以融合其他算法来更好的解决实际问题。3.3本章小结遗传算法是一种模拟自然界生物遗传进化过程的仿生智能优化算法。蚁群算法是一种新型的仿生智能优化算法，它通过模拟蚁群的觅食行为，以求解比较困难的组合优化问题。本章介绍了蚁群算法和遗传算法的相关知识，详细说明了两种算法的基本原理，具体实现步骤和各自的特点。为提出新算法求解QoS组播路由问题打好理论基础。23万方数据 西安科技大学硕士学位论文4基于遗传算法和蚁群算法融合的混合优化算法QoS组播路由问题的研究是建立在真实网络的基础上，具有现实意义。本章在现实网络基础上，得出了QoS组播路由问题的数学模型。并在第三章遗传算法和蚁群算法的研究基础上提出了一种新的QoS组播路由算法—遗传蚁群混合优化算法。该算法不仅仅把遗传算法和蚁群算法用一种更好的方式结合在一起，而且还在此基础上，采用了最大差异性交叉策略，保优选择策略，双重信息素的更新策略和加入了邻近搜索限制的概念。本章详细的阐述了新算法的设计思想和具体步骤。4.1QoS组播路由问题的数学模型[37]组播路由问题从本质上来讲，属于Steiner树问题。本文用一个无向赋权图G(V,E)表示网路结构。图中顶点V{v1,v2,,vn}代表网络中的节点集（主机、路由器等），n为网络节点总个数。图中的边E{e,e,e}指代的是网络中的基本链路集。12n结合实际情况，设网路节点间链路个数为1或者0。p(s,d)代表从节点s到目的节点d的存在路径之和，N为网络中的目标节点集，则组播树记为T(s,N)。QoS组播路由问题的约束条件有带宽（Bandwidth）、时延（Delay）、丢包率（Packet_loss）、时延抖动（Delay_jitter）和代价（Cost）等。在此，R为非负实数集。针对于链路eE，在此定义：时延函数Delay(e)：ER，带宽函数Bandwidth(e)：ER，代价函数Cost(e)：ER，时延抖动函数Delay_jitter(e)：ER，丢包率函数Packet_loss(e)：ER；对网络中的节点nV，定义的五种度量为：时延函数delay(n)：VR，代价函数cost(n)：VR，时延抖动函数Delay_jitter(n)：VR。(1)时延：Delay(p(s,d))Delay(e)Delay(n)(4.1)ep(s,d)np(s,d)(2)瓶颈带宽：Bandwidth(T(s,N))min{Bandwidth(e)}(4.2)(3)费用：Cost(T(s,N))Cost(e)Cost(n)(4.3)eT(s,N)nT(s,N)(4)时延抖动：Delayjitter(p(s,d))Delayjitter(e)Delayjitter(n)(4.4)ep(s,d)np(s,d)24万方数据 4基于遗传算法和蚁群算法融合的混合优化算法(5)丢包率：Packet_loss1(1p_loss(e))(4.5)ep(s,d)QoS组播路由求解一棵满足约束条件同时最小代价的树T，约束条件有：(1)时延约束：Delay(p(s,d))D，D为时延约束；pp(2)带宽约束：Bandwidth(T(s,N))B，B为带宽约束；pp(3)时延抖动约束：Delayjitter(p(s,N))J，J为时延抖动约束；pp(4)丢包率约束：Packet_loss(p(s,d))L，L为包丢失率约束；pp(5)费用约束：在满足以上约束条件的组播树中，Cost(T(s,N))为最小。4.2混合算法的背景描述遗传算法和蚁群算法是目前解决非线性问题的两种智能算法。这两种算法都是模拟某些现象，得到启示后优化问题求最优解。这两种算法都容易实现，很广的应用范围。在QoS组播路由领域，算法具有各自的缺点：GA具有很强的全局搜索能力，但没有利用反馈信息，当求解到一定程度时，算法具有大量的数据冗余，导致较低的后期搜索效率。ACA因初始阶段信息的缺少，导致算法前期的搜索速度很慢。算法在求解过程中的速度[38]-时间图如图4.1所示。vdb蚁群算法aVace遗传算法t0tdtbtatctet图4.1蚁群算法和遗传算法速度-时间曲线GA在算法初期(t~t时间段)有较高的收敛速度，在t时出现下降趋势，在t时求0aba效率更降低。ACA在算法初期(t~t时间段)缺乏相关信息，搜索速度很慢，当信息素0a增加到一定的值时(t时刻之后)，收敛速度明显增快。b本章结合QoS组播路由的实际性，针对GA与ACA的优缺点，设计了一种将两种算法融合的混合优化算法(CGAACA,theCombinationofGeneticAlgorithmandAntCofonyAlgorithm)。该算法既把两种算法的缺陷降到最低，又把他们的优势发挥到最高，结合后的算法有更好的实际效果。25万方数据 西安科技大学硕士学位论文4.3CGAACA算法设计思想及总体框架CGAACA算法的基本思想是前期用遗传算法生成若干最优解，中期把最优解转化成后期信息素的初值，后期利用蚁群算法迭代求解最优解。算法的主要框架：(1)前期处理部分该部分主要有两步：一是根据实际情况简化，把链路上的QoS参数和节点上的QoS参数相加，全部作为链路上的QoS参数。二简化网络拓扑图，前期处理时便删除不满足带宽约束的路径，得到的新拓扑图全部链路都满足QoS带宽约束，简化了问题。(2)GA部分该部分利用GA的全局搜索能力，产生若干组的优化解，取优化组的最好几组姐作为后期ACA算法的初始信息素。给后期的ACA算法的搜索性做铺垫。(3)过度部分该部分是两种算法的过度部分。根据实际情况，设计了适用于QoS组播路由问题的方法来解决两种算法的融合入适当时机，即何时跳出遗传算法，进入蚁群算法。具体步[34]骤如下：CTl1l1定义一个过度控制函数C，CT为GA第l次迭代后，得到的种群的GPlCTll1代价平均值，1lN，N是GA迭代的次数，p是常数。本文的算法通过C的值GGG动态地控制两种算法融合时机。(4)ACA部分该部分发挥ACA算法的正反馈的优势，利用算法前期得到的初始信息素，高效准确的求解最优解。4.4CGAACA算法具体设计方案4.4.1遗传算法部分(1)编码方式遗传算法的编码特征决定着交叉策略和变异策略。遗传算法的编码方式有很多种，在采用遗传算法来求解组播路由问题时，组播树的编码表示要满足以下这些特征：编码表示出的只能是树，而不能是图或者其它的结构；编码必须能表示出所有可能的树；要设计出易于实现的编码方式与解码方式；要便于实现交叉和变异等遗传操作。本文的创新算法中所采用的编码方式是一种基于路径表示、保持树型结构的编码方26万方数据 4基于遗传算法和蚁群算法融合的混合优化算法式。即该编码方式使每一条染色体分别代表一棵组播树，且同时包含源节点和所有的目的节点。在组播路由中。设源节点为s和目的节点集为Md,d,d，则本文算法的12m染色体是长度为m的数组构成，则用编码表示一棵组播树为：g1g2gigm图4.2组播树的染色体编码1jk其中，g1表示从源节点s到目的节点di的备选路径集Pi,,Pi,,Pi中的一条路[39]j径，该表示方法最早是为了解决单播路由问题中。备选路径集的其中一条路径P，i表示从源节点s到目的节点d的路径上的依次经过的节点数组。图4.3展示了他们之间i的关系：g1g2gigmg1i源节点s到目的节点di满足带宽、延时、丢包率约束的路径集路径号路径1s-di2s-…-di…...ks-……-di图4.3染色体、基因和路径关系该编码策略不仅仅可以更方便的进行有效的其他遗传操作，并且不会出现不合格的染色体。(2)种群初始化产生备选路径集是种群初始化的重点。Dijkstra算法是常用的生成备选路径集的方法，即求解出所有从源节点到目的节点的所有最短路径的集合。种群初始化策略是CGAACA算法的一个创新设计点。传统算法在种群初始化中选择路径上的下一个节点时，完全随机选择。这样选择最大的缺点是，容易产生并不相连的无效路径，降低了算法的搜索速度和搜索的有效性。与传统算法不同的是本文在算法的此部分中加入了邻近限制的禁忌搜索概念，邻近限制的禁忌搜索指的是采用节点邻近约束的搜索方案。具体是指当选择路径的下一个节点时，不随机选择，而是从之前收集的邻近节点矩阵中，选择与当前节点相连的节点中的一个。如此有目的的进行选择，可以27万方数据 西安科技大学硕士学位论文保证有链路的两个节点才能形成路径，减少了不必要的无效路径，提高了搜索速度和搜索准确度。使用的产生方法：Step1：初始化相关参数。选择源节点和目的节点集Md,d,d，把源节点s12m作为第一个节点；Step2：循环次数为p，从目的节点d开始，一直循环到d；1mStep3：判断：若p