基于遗传算法的qos组播路由算法研究

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

山东大学硕士学位论文基于遗传算法的QoS组播路由算法研究姓名：孙玲玲申请学位级别：硕士专业：计算机系统结构指导教师：贾智平20080405 山东大学硕士学位论文摘要随着Internet和宽带网络技术的日益发展，传统的以文字和图片为主的服务已不能满足用户的需要，具有视频和音频的多媒体服务成为主流。近几年嵌入式网络数字视频监控系统正在得到广泛应用。由于嵌入式网络数字视频监控系统传输的数据量大而系统资源有限，采用点对点的传输方式会增加服务器的负担，造成网络拥塞。而组播技术可以将相同的数据从嵌入式网络视频服务器同时并行地发送到接收者，大大节省了网络带宽，减少了数据冗余，即使用户数量成倍增加，主干网络带宽也不会随之增加。同时视频监控系统对信息传送的时延和时延抖动有严格的要求，要求传输的数据必须在一定的时延限制内到达所有的接收者，并且接收者之间的延迟差别也需在一定的范围内，即满足一定服务质量(OoS)的要求。因此在嵌入式网络数字视频监控系统中我们需要解决OoS组播路由问题。该问题的目标是寻找一棵满足OoS要求的组播树，使该树覆盖所有的组成员，同时使网络费用达到最小。遗传算法是近几年提出的一种模拟生物界自然选择和遗传机制，具有高度并行，群体寻优的新型最优化搜索算法，近年来已有一些学者采用遗传算法来求解OoS组播路由问题。本文在分析现有遗传算法的基础上，提出了两种改进的遗传算法。第一个改进算法针对遗传算法运行初期易陷入早熟，运行后期收敛缓慢的问题进行了改进，采用初始群体均衡生成法和自适应变异操作可以很好地抑制早熟现象，引入排序对适应度进行拉伸，从而加快了算法的收敛速度。仿真实验结果表明改进后的遗传算法收敛速度快，性能好，可以满足系统资源有限和实时性的要求。第二种改进算法是在分析了遗传算法和蚁群算法各自优缺点的基础上，将两种算法进行融合来求解OoS组播路由问题，算法的前一阶段利用遗传算法的快速性、随机性、全局收敛性产生后一阶段蚁群算法所需要的初始信息素，加快了蚁群算法利用正反馈特性进行搜索的速度。经融合后的算法，在时间效率上优于蚁群算法，在求解效率上优于遗传算法，形成了一种时间效率和求解效率都比较好的启发式算法。 山东大学硕十学位论文本文最后针对现有视频监控系统单播传输存在的问题，将组播技术应用到网络视频监控系统中，可以有效地节省网络资源，降低时延，减少网络堵塞的几率，较好地保证了数字视频传输的实时性和服务质量。关键词：QoS；组播路由；遗传算法；蚁群算法II 山东大学硕士学位论文ABSTRACTWiththedevelopmentofInternetandbroadbandtechnology，traditionalservicesforwordandpicturecannotsatisfytheneedofusers，mediaserviceswithvideoandaudiobecomemainstream．Inrecentyears，embeddednetworkdigitalvideomonitorsystemiswidelyused．Becauseoflargedataandlimitsystemresource，unicastwillenhancetheburdenofserverandleadtocongestion．ButmulticastcantransmitthesamedatafromembeddednetworkvideoservertothereceiversparallellySOthatitcansavebroadbandandreducedataredundancy．Atthesametime，videomonitorsystemhasthestrictrequestfordelayanddelay-jitter．Thetransmitteddatamustreachallreceiversinlimitedtime，andthedelaydifferencebetweenreceiversalsoneedstobeinalimitedrange，thatistosay，satisfythedemandofQoS．ThereforeweneedtosolveQoSmulticastroutingquestioninembeddednetworkdigitalvideomonitorsystem．ThegoalofthequestionistofindamulticasttreesatisfyingthedemandofQoSthatoverlayallgroupnumbersandmakethecostminimum．GeneticalgorithmisanewglobaloptimalalgorithmsimulatingevolutionandwidelyusedtosolveallkindsofNP-hardproblems．InrecentyearssomescholarshaveusedgeneticalgorithmtosolveQoSmulticastroutingquestion．Thisthesisanalysesexistgeneticalgorithmsandprovidestwokindsofimprovedgeneticalgorithm．Thefirstimprovedalgorithmanalysesthatthestandardgeneticalgorithmiseasytogetintoprematurity，andattheendofthealgorithm，itrunsslowly．Inordertoovercomethephenomenon，weadoptinitialpopulationuniformbuildingmethodandself．adaptivemutationtorestrainprematurityandintroduceorderingtoscalefitnesstoimproveconvergencespeed．Simulationshowsthattheimprovedalgorithmisefficientandeffective，andcanfindthebestsolutionquickly．Itcansatisfylimitedresourceandreal-timethesystemrequests．Thesecondimprovedalgorithmmixesthistwoalgorithmsbasedonthestrengthandshortcomingofgeneticalgorithm 山东大学硕十学位论文andant-colonyalgorithmtosolveQoSmulticastroutingquestion．ThefirstphaseofthemixedalgorithmmakesUSeofthequickness，randomandglobalconvergenceofgeneticalgorithmtoproducetheinitialpheromonethatisneededbythesecondphaseofthemixedalgorithmThemixedalgorithmisbetterthanant—colonyalgorithmintimeefficiencyandbetterthangeneticalgorithminsolutionefficiency．Becauseofunicastproblemintheexistingvideomonitorsystem，thispaperappliesmulticasttechnologytonetworkvideomonitorsystem．Bythisway，Wecansavenetworkresourceeffectively，reducedelayanddecreasetheprobabilityofnetworkcongeststoensurereal．timeandqualityofserviceofdigitalvideotransmissionKeyWords：QoS；multicastrouting；geneticalgorithm；ant-colonyalgorithm 原创性声明和关于论文使用授权的说明原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。论文作者签名：刘!壹煎日期：堑!至!墨丝关于学位论文使用授权的声明本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。(保密论文在解密后应遵守此规定)论文作者签名：趟：硷蕴导师签名：El期：二垫印 山东大学硕士学位论文1．1论文的选题背景第一章绪论在传统的Internet中，IP业务主要集中在HTTP、FTP、E-mail等数据业务。然而，随着Internet的网络规模和用户数量的迅速发展，Internet上的业务种类也与日俱增，各种实时和多媒体业务，如：视频点播、视频会议、远程教学、新闻发布、网络电视等业务正在成为信息传送的重要组成部分。现有的Internet采用的是点到点的传送方式即单播方式。在这种方式下，发送方和每一个接收方需要一个单独的数据通道，从一台服务器送出的每个数据包只能传送给一个客户机，如果有另外的用户希望顺路获得这个数据包的拷贝是不可能的。这种方式会极大地加重服务器的负担并浪费大量带宽。解决的办法是构建一种具有组播能力的网络，允许路由器一次将数据包复制到多个通道上。组播发送方只要发送一个信息包而不是很多个，所有目的地将同时收到同一信息包，可以更及时、更同步把信息发送到目的地，减少网络上传输的信息包的总量，网络成本变得相当低廉，达到从未有过的传输能力。实现组播技术要解决的关键问题之一就是组播路由问题。组播是将信息从源节点同时发送到网络中多个目的节点的通信方式。Kompella等在1992年首次提出了一种满足给定端到端延时约束的组播路由算法，并证明此类问题是NP完全问题。对于约束组播路由的求解，多年来提出了许多不同的算法，其中最引人注目的是近几年出现的一种新型优化算法一一遗传算法。遗传算法是模拟自然界自然选择遗传机制进行搜索寻优的方法。遗传算法本质是一个群体迭代过程，从一个随机的初始群体出发，依据优胜劣汰原则，通过竞争、选择、繁殖、变异等遗传优化作用，产生性能更好的下一代群体。使用遗传算法求解科学研究和工程技术中各种组合搜索和优化计算问题的这一基本思想，早在60年代初由美国Michigan大学的J．Holland教授提出，并在80年代中期得到蓬勃发展。但在其发展的同时，遗传算法也暴露出许多不足和缺陷，针对不足，近年来又有许多对基本遗传算法的改进方 山东大学硕士学位论文法出现。本文正是利用改进的遗传算法，对多约束的QoS组播路由问题进行求解。1．2国内外研究现状近年来，在Internet上出现了越来越多的高带宽需求的多媒体应用，如网络音视频点播、多媒体远程教育、远程会议等。而传统网络点对点的通信模式使得网络用户增加时网络发送负载和网络延迟也随之增加，这就带来带宽的急剧消耗和网络拥挤问题。人们提出了各种方案缓解网络瓶颈，其中组播技术由于它的独特优越性而被广泛采用。组播问题的关键在于组播路由的确定，寻找简单、高效、健壮的组播路由算法一直是网络界致力研究的问题。分布式多媒体的应用要求网络能够传送具有QoS要求的实时信息。因此基于OoS约束的组播路由算法研究成为网络研究领域的热点问题。组播的关键是构造组播树，为了构造性能良好效率高的组播树，人们进行了大量的研究，提出了很多算法，大致可以分为三类：(1)求解Steiner树的启发式算法，．女ⅡKMB算法，MPH算法，ADH算法等，但这类算法没有考虑QoS约束，不能满足多媒体实时性的要求。(2)求解QoS约束Steiner树的经典算法，如BSMA算法，KPP算法，CDKS算法等。有研究者对这类经典算法进行了仿真研究，结果表明：这类算法要么太复杂而难于求解，要么太费时而不能实际应用。(3)现代智能优化算法求解OoS组播路由问题，如模拟退火，遗传算法，蚁群算法，神经网络等。其中遗传算法是近几年迅速发展起来的一种新型的随机搜索与优化算法，其基本思想源于达尔文的进化论和孟德尔的遗传学说。该算法创建于1975年，此后引起了国内外学者的关注。自1985年以来国际上已召开了多次遗传算法的学术会议和研讨会为研究和应用遗传算法提供了国际交流的机会。遗传算法具有高度并行、随机、自适应和全局寻优的特点，已广泛应用于解决各种NP-hard问题。’2 山东大学硕士学位论文1．3论文的主要工作本文共分为六章，各章的主要内容如下：(1)第一章介绍了选题背景，国内外研究现状及论文的主要工作。(2)第二章对OoS组播路由问题进行综述，介绍了QoS的主要参数和度量，组播工作原理、实现方式以及组播路由算法。(3)第三章建立了QoS组播路由问题的数学模型，针对现有遗传算法运行初期易陷入早熟，运行后期收敛缓慢的不足，提出了一种改进的遗传算法，经实验验证该算法收敛速度快，实现了全局寻优。(4)第四章在分析了遗传算法和蚁群算法各自优缺点的基础上，将两种算法进行融合来求解OoS组播路由问题，算法的前一阶段利用遗传算法的快速性、随机性、全局收敛性产生后一阶段蚁群算法所需要的初始信息素，加快了蚁群算法利用正反馈特性进行搜索的速度。经融合后的算法，在时间效率上优于蚁群算法，在求解效率上优于遗传算法，形成了一种时间效率和求解效率都比较好的启发式算法。(5)第五章针对现有视频监控系统单播传输存在的问题，将组播技术应用到网络视频监控系统中，较好地保证了数字视频传输的实时性和服务质量。(6)第六章对全文进行总结，并对今后的工作提出了展望。 山东大学硕士学位论文2．1QoS概述第二章QoS组播路由问题服务质量【ll(QualityofService，简称QoS)，指发送和接收信息的用户之间以及用户与传输信息的服务网络之间关于信息传输的质量约定。QoS包括用户需求和网络服务提供者的行为两个方面。用户要求指用户在Internet网络上进行多媒体通信时所要求的服务类型以及相应的传输性能和质量，所以多媒体应用对IP网QoS的要求同时体现：丢包率、传输时延、时延抖动、网络带宽等参数描述的分组传输特性。网络要满足用户的质量要求，就必须满足用户要求的QoS参数。2．1．1OoS主要参数带宽(bandwidth)：单位时间内传送的IP包数量。多媒体业务的数据传数量往往较大，因此需要网络为其分配最小带宽。如标准电话为64kbit／s，压缩过的HDTV为25～34Mbit／s，视频会议为0．1～2Mbit／s。延时(delay)：指IP包从发送到接收之间的时间间隔。它包括终端设备的编码／解码时间，IP包在传输介质的传播时间，IP包在交换机或路由器中被处理的时间，以及IP包在交换机或路由器的等待队列中的排队时间。实时业务往往是对延时敏感的，比如在虚拟现实应用中，由于语音输入的响应时间被限制在lOOms之内，所以端到端延时应在40ms左右。而有些非实时业务如e．mail等，却是对延时不敏感的，因此网络不需要对这类业务提供延时保证。延时抖动(delay-jitter)：当IP包到达交换设备时，如果等待队列中没有别的IP包，则它将以固定延时被转发出去。但是，如果等待队列中还有别的包，则它可能就需要等待，这是IP包被交换的延时就等于固定延时加上在队列中等待的时间。以上两种情况下延时的变化程度就是延时抖动。丢包率(packetlossrate)：是指特定的时间段丢失的包占传输包的总数4 山东大学硕士学位论文的比例。丢包主要是由于网络拥塞引起的。某些应用程序在丢包后无法正常工作，因此要求网络提供传输保证，这方面的典型例子就是TCP。而某些多媒体业务如IP电话，个别包的丢失虽然会影响视频的质量，但用户往往可以容忍这种质量的暂时下降。因此，只要包丢失率在一定的范围内，就不会影响业务的正常进行。2．1．200S度量对于路径P=(a，b，c，⋯，f,g)，用d(a，b)表示对应链路(a，b)的度量，则QoS度量可以按性质分为以下三类‘2】：(1)凹性QoS度量如果d(a，g)=min{d(a，b)，d(b，c)，⋯，d(f，g))，那么度量由传输通道中瓶颈决定，即此度量仅与路径上的某个瓶颈链路的QoS度量有关，如剩余带宽、剩余缓存空间、链路速度等。(2)加性QoS度量如果d(a，g)=d(a，b)+d(b，c)+⋯+d(Cg)，那么度量由传输通道中所有链路的特性共同决定，如时延、时延抖动、费用等。(3)乘性QoS度量如果d(a，g)=d(a，b)·d(b，c)·⋯宰d(Cg)，即度量为所有链路对应度量的乘积，如可靠性等。因此，按度量的性质QoS路由可归结为基本的两大类：路径优化问题，对应加性QoS度量；链路优化问题，对应凹性QoS度量。2．2组播概述随着宽带多媒体网络的不断发展，各种宽带网络应用层出不穷。视频会议数据和资料分发、网络音频应用、多媒体远程教育等宽带应用都对现有带宽多媒体网络的承载能力提出了挑战。采用单播技术构建的传统网络已经无法满足新兴宽带网络应用在带宽和网络服务质量方面的要求，因为服务器必须为每一个接收者提供一个相同内容的IP报文拷贝，同时网络上也重复地 山东大学硕士学位论文—■曹I————————————I皇—■■量曼曼曼曼曼鼍曼曼曼詈量传输相同内容的报文，占用了大量资源。虽然IP广播允许一个主机把一个一个IP报文发送给同一个网络的所有主机，但是由于不是所有的主机都需要这些报文，因而浪费了网络资源随之而来的是网络延时、数据丢失等等问题。在这种情况下组播(multicast)应运而生，它的出现解决了一个主机向特定的多个接收者发送消息的方法。组播网络中，即使组播用户数量成倍增长，骨干网络中网络带宽也无需增加，从而最大限度的解决目前宽带应用对带宽和网络服务质量的要求。2．2．1组播的工作原理组播是一种从一个发送者同时向多个接收者或者多个发送者向多个接收者传送数据包的通信过程。组播源把数据包发送到特定组播组，而只有属于该组播组的地址才能接收到此数据包。组播以最佳的方式将数据传输给所有的主机。组的成员可以是动态的，即成员可以在任何时间加入一个组或者离开一个组，组的大小和位置没有限制，一个主机可以是多个组的成员。组播可以大大的节省网络带宽，提高数据传送效率，减少主干网出现拥塞的可能性。为了满足多媒体实时应用等的要求，很有必要寻求网络层对组播通信的支持，使组播技术满足此类应用的要求，为此就有了实现组播的方式，也就是建立组播树(multicasttree)。组播树是覆盖源节点和所有目的节点的一棵生成树，建立组播树有以下优点：信息可以沿着树的分枝并行传到各个目的节点，这可以降低信息传输的时延；信息只是在树的分枝处进行复制，从而使复制的份数尽量少，这样做可以节省带宽，提高资源利用率，并且能减少阻塞的发生。除了组播通信方式，计算机网络中常用的通信方式还有单播通信方式和广播通信方式。单播(unicast)：在发送者和每一接收者之间需要单独的数据信道。如果一台主机同时给很少量的接收者传输数据，一般没有什么问题。但如果有大量主机希望获得数据包的同一份拷贝时却很难实现，因为这将导致发送者负担沉重、延时增加以及造成网络拥塞，而且为了保证一定的服务质量还需要增加硬件和带宽。6 山东大学硕士学位论文广播(broadcast)：在整个IP子网内广播数据包，所有子网内部的主机都将收到这些数据包。广播意味着网络向子网主机都投递一份数据包，不论这些主机是否乐于接收。然而广播的使用范围非常小，只在本地子网内有效，因为路由器会封锁广播通信；同时广播增加非接收者的开销。组播传输可在数据链路层和网络层实现，支持的媒体类型包括以太网、FDDI和ATM。大多数路由器提供商支持IP组播，不支持IP组播的网络通过组播隧道技术传输逐波信息包。2．2．2组播实现方式目前网络对组播的支持主要是通过建立一棵连接源节点和多个目的节点的组播树来实现的，信息以并行方式沿树枝发送到不同目的节点，降低了传输时延；而且信息只需在树的分叉处进行复制，节省了网络资源。组播树有两种基本类型【8】：有源树和共享树。有源树有两种形式：一种是最短路径树，它以最短路径贯穿网络，即从源节点到所有目的节点都是通过最短路，因此被称为最短路径树(SPT：ShortestPathTree)。最短路径树保证了从源节点到每个目的节点为最短路，但是全树的费用并不一定是最优的，这里树的费用是指树中边的费用之和。为了达到全树的费用最优，因此有第二种形式的有源树，即覆盖所有组播成员的一棵最优Steiner树，Steiner树问题是从图论中引申出来的一个优化问题：在一个连通图中，给定一个节点子集，要求在图中找到一棵覆盖给定节点子集的费用最小的生成树。Steiner树的总费用最小，但是从源节点到每个目的节点不一定是最短路。如果组中有多个组播源，则必须为每个组播源构造一棵组播树。由于不同组播源发出的数据包被分散到各自分离的组播树上，因此采用有源树有利于网络中数据流量的均衡。缺点是要为每个组播源构造各自的分布树，当数据流量不大时，构造开销相对较大。一共享树也称为RP树，是指为每个组播组选定一个共用根(汇合点RP或核心)，以RP为根建立组播树。同一组播组的组播源将所要组播的数据单播到RP，再由RP向其他成员转发。共享树在路由器所需存储的状态信息的数量和路由树的总代价两个方面具有较好的性能。当组的规模较大，而每个成员的数据发送率较低时，使用共享树比较合适。但当通信量大时，使用共7 山东大学硕士学位论文曼舅Mm●曼量曼曼—曼皇曼曼曼曼皇曼喜曼—■■—寞享树将导致流量集中及根(RP)附近的瓶颈。2．2．3组播应用自从1992年3月第一次建立组播主干网MBone，且IETF利用它成功地举行第一次网络会议以来，组播引起了更为广泛的重视，并取得很大的发展，许多专家学者对其各个方面进行了深入研究。组播应用大致可以分为三类：点对多点应用，多点对多点应用，多点对点应用。点对多点应用：是指一个发送者，多个接收者的应用形式，这是最常用的组播应用形式。典型的应用包括：媒体广播、媒体推送、信息缓存、事件通知和状态监视等。多点对多点应用：是指多个发送者和多个接收者的应用形式。通常，每个接收者可以接收多个发送者发送的数据，同时，每个发送者可以把数据发送给多个接收者。典型应用包括：多点会议、资源同步、并行处理、协同处理、远程学习和讨论组等。多点对点应用：是指多个发送者，一个接收者的应用形式。典型应用包括：资源查找、数据收集、网络竞拍和信息询问等。2．3组播路由算法为进行有效的组播通信，确定组播路由是非常关键的，组播路由算法就是用来确定组播树的。组播树是通过在每个路由器设置路由表来建立的，路由表上给出为使信息送到组播组成员，此路由器应该选择哪个邻接节点的信息。由于网络的动态变化，每个路由器的路由表也需要定期更新，此外路由表的设置还要保证不能有回路产生。2．3．1组播路由算法分类1．静态和动态组播路由算法组播路由算法按照是否允许网络成员随时加入或离开组播组，可以分为 山东大学硕士学位论文静态路由算法和动态路由算法两类。静态组播路由算法针对初始的组播组成员构造一棵组播树，这时候组播组成员和组播树固定下来，它不能根据当前实际传输量和拓扑结构的变化来做拓扑选择，而是按照先前构造好的组播路由进行传输，它的路由修改需经过一定时间的运行后才能进行。但是真实网络中存在许多动态的变化，例如网络拓扑结构的变化，组播组成员的变化等，所以动态组播路由算法显得非常的重要，它允许组播组成员可以动态加入或者离开。构造适应组成员变化的算法有三种方式：一种是构造一棵性能优化的初始组播树，组播组成员变化之后对树采取最小的变化，例如成员的加入通过建立节点到组播树的最短路由来完成，成员离开时仅删除该节点，如果删除产生一个非成员的叶子节点，则删除该非成员的叶子节点，重复该步骤，直到不存在非成员的叶子节点为止。第二种方式是组播组成员发生变更后，对整个组播组重新计算组播路由，也可以采用一种改进的方法，首先节点加入和离开仿照第一种方式实现，但是在树的局部范围内，考察节点的加入和离开对树的累计损伤，当这种累计损伤超过一定的门限时，在局部范围内重新优化路由，可以通过改变门限值来达到树的优化、计算时间和复杂性之间的平衡。第三种是构造一棵富于弹性变化的次优树，即最短路径树，每个组成员之间互相独立的选择最短路由，因此树的性能不受组成员动态变化的影响。2．集中式和分布式组播路由算法组播路由算法按照其实现方式，又可分为集中式和分布式算法。集中式路由算法是由节点在掌握了整个网络的拓扑结构后确定组播路由，集中式组播路由算法一般都是源路由算法，即源节点通过某个链路协议获得完整的网络拓扑信息，进行路由计算。而分布式算法【3l贝0不需要每个成员掌握整个网络拓扑信息，每个组成员在只具有局部信息的条件下就可参与路由的确定。这两种算法各有其优缺点，集中式算法往往简单快速，但是由于一个节点需要维护整个网络的状态，其开销比较大，而分布式算法相对于集中式算法较复杂并且速度较慢，但是它有一个显著的优点，就是任何节点都不需要维持整个网络的状态。3．无约束和有约束组播路由算法按照是否有QoS约束，组播路由算法可以分为无约束组播路由算法和有约束组播路由算法，许多现有的算法是为非实时网络设计的无约束组播路9 山东大学硕士学位论文由算法，它们往往只试图优化树的费用，但是实时和多媒体应用对QoS提出了更高的要求，有约束的组播路由算法通常是在给定QoS约束的条件下使组播树的费用最小。2．8．2组播路由算法简介1．基于最短路径树的算法最短路径树算法求解从组播源点到组播终点各成员的路径并使路径总权值之和最小。如果使用单位权值，则得到的组播树就是最小跳树，即从源点到终点所经过的节点最少的组播树。如果权值表示链路时延，则所得到的组播树就是最小时延树。Bellman．Ford算法和Dijkstra算法是最有名的两个最短路径算法，两个算法都是多项式时间复杂度。2．基于最小生成树的算法一棵最小生成树是包含了组播源点和所有组播终点且权值最小的一棵树。最有名的集中式最小生成树算法是Prim算法，基本思想是：在网络中任选一个节点V。作为树根，从V。．开始，连接与V。相连的、边权值最小的节点V"得到子树Tl’再以上述规则连接Tl与网络中不在T1中的节点，如此继续下去，直到所有节点都用到为止。3．相关启发式算法1)KPP算法【5】是较早提出的时延受限组播路由算法，它由Kompella、Pasquale、Polyzos提出，故称为KPP算法。该算法借鉴了KⅧ算法141的思想，用于在一定时延约束下优化网络费用。算法的基本步骤如下g步骤1：构造一个只包含源节点和目的节点的完全图，这个完全图中的每条边对应原图中两个节点之间满足时延约束费用最小路径。步骤2：从完全图中生成一个时延受限生成树，生成算法与Prim算法相似，每次将费用最小的边加入到生成树。步骤3：将生成树的边用原图中的时延受限．最小费用路径来代替，并去掉产生的回路。KPP算法的缺点在于有时当解存在时，它有可能找不到解。2)BSMA算法[6,11】，它采用先找到问题的可行解，然后对可行解进行改进，使其性能更加接近于最优解的方法。这一算法的主要特点是：对不同的10 山东大学硕士学位论文—一IIll●—曹●——|—皇●●量曼曼■|■|■|●■■—皇吕皇曼■量—置鼍—鼍邑舅曼曼曼曼曼曼曼|舅—量罾皇—■●——■—|皇鼍量舅—舅—鲁量皇曼曼喜●目的地，其时延约束边界值可以不同；与KPP算法相比，其链路费用值、链路时延值可以是任意实数；与以往算法一次性通过不同，BSMA算法可以重复执行以使树的费用最小。算法的基本思想如下：(1)通过LD算法生成组播树；(2)用费用更小但满足时延要求的超边来替代生成的组播树中费用较大的超边，这个步骤一直反复进行，直到整个生成树的费用不能再减小为止。该算法在替换费用高的超边时，用到了求k条最短路径算法。BSMA算法虽然求得的组播树的费用较小，但其复杂度太高。3)CDKS算法CDKS算法【401是在LD算法和BSMA算法之间的一个折中。其基本思想为：(1)计算一个LC(Least．Cost)树，即用Dijkstra算法计算从源节点到各目的节点的费用最短路径，然后合并相同链路所构成的树；(2)将从源节点到各目点节点的路径中不满足时延要求的路径用LD(Least．Delay)路径替换，从而得到需要的时延受限组播树。CDKS算法是一个综合性能比较均衡的算法，一方面，它的时间复杂度不太高，另一方面，它的解质量基本还可以接受，但是由于存在合并的过程，使其难于在分布式环境下部署。有学者对这些启发式算法进行了仿真研究，结果表明：当前提到的启发式算法要么太复杂而难于求解，要么太费时而不能实际应用。4．智能优化算法随着近年来遗传算法、蚁群算法、模拟退火算法等的兴起，科学工作者对这些算法的模型、理论和应用技术等一系列的问题进行了深入的研究，这些算法被称为现代优化算法，其主要应用对象是优化问题中的NP问题，由于QoS组播路由问题是NP完全问题，为此近年来许多学者用这些现代优化算法来求解该问题。其中遗传算法是一种新型的智能优化算法，具有群体并行搜索，全局优化，鲁棒性强等优点，非常适合求解QoS组播路由问题。2。400S组播路由问题对于QoS组播路由问题，一般有两种QoS要求，即最优化(optimization) 山东大学硕+学位论文和满足给定的约束条件(constraint)。这些要求的组合就形成了用户对网络提出的各种QoS要求。组播路由问题中研究最多的是受限组播树，其中包括时延受限最小代价组播树问题‘11。13】，带宽受限组播树问题[14-151，时延抖动受限问题【l3】等。QoS组播路由问题已被证明是NP完全问题，具有较高的复杂性，因而遗传算法被应用到该问题的求解中。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法，适合在复杂而庞大的搜索空间中寻找最优解，它原理简单，鲁棒性强，易于并行分布处理，惯犯用于求解各种NP完全问题。因此，遗传算法为QoS组播路由问题的求解提供了新的途径。文献[17．19]应用遗传算法求解无约束的Steiner树问题，文献[20—29]应用遗传算法求解时延受限的组播路由问题，文献[301应用遗传算法求解时延抖动受限的组播路由问题，文献【31】应用遗传算法求解带度约束的组播路由问题，文献【32．331应用遗传算法求解带综合QoS约束的组播路由问题，包括带宽、时延、时延抖动、丢包率等多个QoS约束的组合。2．5本章小结本章对计算机网络的组播通信进行综述，首先介绍了QoS的基本概念、主要参数和QoS度量；接着介绍了组播的工作原理、实现方式及其应用，然后对组播路由算法从不同的角度进行分类，并简单介绍了现有的组播路由算法，最后分析了QoS组播路由问题。12 山东大学硕士学位论文第三章一种改进遗传算法求解OoS组播路由问题3．1遗传算法遗传算法【9】(GeneticAlgorithm，GA)是近几年提出的一种新型优化算法，它具有并行搜索、群体寻优的特点，已广泛用于解决各种具有NP难度的问题。遗传算法是由美国Michigan大学的JohnHolland与其同事、学生们研究形成的一个较完整的理论和方法。随后经过20余年的发展，取得了丰硕的应用成果和理论研究的进展，特别是近年来世界范围形成的进化计算热潮，计算智能已成为人工智能研究的一个主要方向，以及后来的人工生命研究兴起，使遗传算法得到广泛的关注。3．1．1遗传算法的基本思想遗传算法的基本思想来源于遗传进化，主要借助于生物进化机制与遗传学原理，按照自然选择和适者生存的原则，利用简单的编码技术和繁殖机制，模拟自然界生物群体优胜劣汰的进化过程，实现对复杂问题的求解。遗传算法是从代表问题可能潜在解集的一个种群开始的，而一个种群则由经过基因编码(coding)的一定数目的个体组成。每个个体(individual)实际上是染色体带有特征的实体。染色体(chromosome)作为遗传物质的主要载体，即多个基因(gene)的集合，其内部表现是某种基因组合，它决定了个体形状的外部表现。因此，在一开始需要实现从表现型到基因型的映射即编码工作。初始种群(population)产生之后，按照适者生存和优胜劣汰的原理，逐代(generation)演化产生出越来越好的近似解。在每一代，根据问题域中个体适应度大小挑选(selection)个体，并借助遗传算子进行交X(crossover)和变异(mutation)，产生出代表新解集的种群。这个过程将导致种群更加适应环境，末代种群中的最优个体经过解码(decoding)，可以作为问题近似最优解。其中，在遗传算之中，复制是从一个旧群体中选择生命力强的个体产生新群体的过程，体现自然界优胜劣汰的规律；交叉是按较大概率从种群中随机选择两个个体进行 山东大学硕士学位论文IIII——曼曼曼曼曼曼量曼■—●罾皇曼量量曼置皇—■—曼曼曼—皇●■|曼皇皇—■鼍曼量曼曼曼皇量皇曼鲁曼曼曼量—■—曼曼曼——皇曼曼蔓鲁曼昌曼曼皇操作，以产生新的基因组合；变异则以一定概率改变群体中某些个体的位，目的在于防止寻优过程中过早收敛。复制和交叉完成遗传算法的大部分搜索功能。而变异增加了遗传算法找到最优解的能力。3．1．2遗传算法的设计基本步骤在设计遗传算法时，通常按以下的基本步骤进行：(1)确定编码方案：遗传算法求解问题不是直接作用在问题的解空间上，而是利用解的某种编码表示。选择何种编码表示有时将对算法的性能、效率等产生很大的影响。(2)确定适应函数：适应值是对解的质量的一种度量，它通常依赖于解的行为与环境的关系。一般以目标函数或费用函数的形式来表示。解的适应值是遗传过程中进行选择的唯一依据。(3)选择策略的确定：优胜劣汰的选择机制使得适应值大的解有较高的存活概率，这是遗传算法与一般搜索算法的主要区别之一。不同的选择策略对算法的性能也有较大的影响。(4)控制参数的选择：包括种群规模、算法执行的最大遗传代数、执行不同遗传操作的概率以及其它一些辅助性的控制参数。(5)遗传算子的设计：包括选择、杂交、变异算子。遗传算子的设计和编码方案是同步考虑的。(6)确定算法的终止准则。3。1．3遗传算法流程遗传算法的一般流程：第1步：随机产生初始种群，染色体的基因编码；第2步：计算个体的适应度，出最优解，否则转向第3步：由一定数目的个体组成，每个个体表示为并判断是否符合停止准则，若符合，则输第3步：依据适应度选择再生个体，适应度高的个体被选中的概率高，14 山东大学硕+学位论文适应度低的个体可能被淘汰；第4步：按照一定的交叉概率和交叉方法，生成新的个体；第5步：按照一定的变异概率和变异方法，生成新的个体；第6步：由交叉和变异产生新一代的种群，返回到第2步。遗传算法中的停止准则，一般依据问题的不同有不同的确定方式。例如，可以采用以下的准则之一作为判断条件：种群中个体的最大适应度超过预先设定值；种群中个体的平均适应度超过预先设定值；迭代次数超过预先设定值。3．1．4遗传算法的特点遗传算法与传统的算法具有很多不同之处，但主要的特点如下所述：(1)智能性：遗传算法的智能性包括自组织、自适应和自学习等。应用遗传算法求解问题时，在确定了编码方案、适应度函数及遗传算子后，算法将利用计算过程中获得的信息自行组织搜索。由于基于自然的选择策略：适者生存、不适者淘汰，通常适应度值大的个体具有与环境更适应的基因结构，再通过杂交和基因突变特征同时也赋予了它具有能根据环境的变化自动发现环境的特征和规律的能力。自然选择消除了算法设计中的一个最大障碍：即需要事先描述问题的全部特点，并说明针对问题不同特点算法应该采取的措施。于是利用遗传算法可以解决那些结构尚无人能理解的复杂问题。(2)本质并行性：遗传算法的本质并行性表现在两个方面：一是遗传算法是内在并行的，可以让多台计算机各自进行独立种群的计算，等到运算结束时才进行比较，选取最佳个体。二是遗传算法的内涵并行性，由于遗传算法采用种群的方式组织搜索，从而它可以同时搜索解空间的多个区域，这使得遗传算法能够以较小的计算获得较大的收益。(3)过程性：遗传算法通过自然选择和遗传操作等自组织行为来增强群体的适应性，算法模拟的是一个过程。在这个过程中，算法本身无法判定个体处在解空间的位置，因此需要人为干预才能终止。(4)多解性：遗传算法是采用群体的方式组织搜索。它从多个点出发，通过这些点内部结构的调整和重组来形成新的点。因而每次都将提供多个近 山东大学硕士学位论文似解，这对多目标搜索或有需要多个近似解作为参照的情况下是非常有用的。(5)不确定性：遗传算法的不确定性是伴随其随机性而来的。遗传算法的主要步骤都含有随机因素。从而在算法的演化过程中，事件的繁盛与否带有很大的不确定性。(6)非定向性：自然选择和生物繁殖这种非定向机制是遗传算法的关键。他没有确定的迭代方向也不依靠梯度下降法似的爬山策略，而是用调整群体的内部结构的方法来增强其对环境的适应度，以解决问题。(7)全局优化：传统优化方法一般都是梯度下降的爬山策略，从而使得多峰函数容易陷入局部最优。而遗传算法能同时在解空间的多个区域内进行搜索，并能以较大的概率跳出局部最优，以找到全局最优。3．1．5遗传算法的应用遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面是遗传算法的一些主要应用领域：1．函数优化：是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。很多人构造了各种各样的复杂形式的测试函数，有连续函数也有离散函数，有凸函数也有凹函数，有低维函数也有高维函数，有确定函数也有随机函数，有单峰函数也有多峰函数等，人们用这些几何特性各异的函数来评价遗传算法的性能。而对于一些非线性、多目标的函数优化问题，用其他优化方法较难求解，遗传算法却可以方便的得到较好的结果。2．组合优化：随着问题规模的扩大，组合优化问题的搜索空间急剧扩大，有时在目前的计算机上用枚举法很难或者甚至不可能得到其精确最优解。对于这类复杂问题，人们已意识到应把精力放在寻求其满意解上，而遗传算法则是寻求这种满意解得最佳工具。实践证明，遗传算法对于组合优化中的NP完全问题非常有效。例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分等方面得到成功的应用。3．生产调度问题：遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面都得 山东大学硕十学位论文到了有效应用。4．自动控制：在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已在其中得到了初步的应用，并显示出了良好的效果。例如用遗传算法进行航空控制系统的优化、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识等。5．图像处理：在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会存在～些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在这些图像处理中的优化计算方面找到了用武之地，目前已在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。6．人工生命：自组织能力和自学习能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工。生命现象的重要基础理论虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。7．机器学习：学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。3．2OoS组播路由的数学模型网络表示成一个带权图G=(V，E)，其中y代表节点集合，E代表节点的链路集合。并假定在网络中一对节点之间最多只有一条链路。关联每条链路e∈E的参数是该链路的QoS度量。假设组播会话的源节点为s∈V，目的节点集M∈V一和)，也称为组播组，M中的每个节点meM称为组成员。组播树丁是G的子图，是根为J并包含目的节点集合膨的一棵树，用T=(巧，B)表示。丁中存在由源节点s到每个目的节点m的一条路径，用p(s，朋)表示。考虑到嵌入式视频监控系统的实时性，假定每一条链路关联代价、时延、时延抖动3个QoS参数，则组播树丁存在下列关系：(1)delay(p(s，聊))=∑delay(e)，VmEM17 山东大学硕士学位论文(2)cost(T(s，M))=∑cost(e)eeT(s，时)(”aetay—jitter(p(s，聊))=∑沈细一jitter(e)，Vm∈Meep(s，rn)定义QoS组播路由问题就是找到一棵组播树T(s，M)满足：(1)延迟约束：delay(p(s，m，))≤Di：(2)延迟抖动约束：沈协一jitter(p(s，m1))≤Jl；并使得组播树的费用COSt(T(s，M))最小。其中D，表示第i个目的节点的延迟约束，，；表示延迟抖动。本算法中每个目的节点的延迟和延迟抖动可以不相同，大大增加了本算法的应用范围。3．3改进的遗传算法3．3．1引言随着Internet和宽带网络技术的日益发展，传统的以文字和图片为主的服务已不能满足用户的需要，具有视频和音频的多媒体服务成为主流。近几年嵌入式网络数字视频监控系统正在得到广泛应用。不同于以往的模拟视频监控系统，该系统使用现有的网络，采用嵌入式网络视频服务器，实现从监控点前端、监控中心、监控工作站的数字化处理，具有权限的用户可以轻而易举地进行远程视频监控，实现监控现场的无人值守。由于嵌入式网络数字视频监控系统传输的数据量大而系统资源有限，采用点对点的传输方式会增加服务器的负担，造成网络拥塞。而组播技术可以将相同的数据从嵌入式网络视频服务器同时并行地发送到接收者，大大节省了网络带宽，减少了数据冗余，即使用户数量成倍增加，主干网络带宽也不会随之增加。同时视频监控系统对信息传送的时延和时延抖动有严格的要求，要求传输的数据必须在一定的时延限制内到达所有的接收者，并且接收者之间的延迟差别也需在一定的范围内，即满足一定服务质量(QoS)的要求。因此在嵌入式网络数字视频监控系统中我们需要解决QoS组播路由问题。该问题的目标是寻找一棵满足QoS要求的组播树，使该树覆盖所有的组成员，同时使网络费用达到最小。 山东大学硕士学位论文该问题已被证明是NP．hard。求解该问题可采用启发式算法，如KPP，BSMA等，仿真研究表明当前提出的启发式算法要么太复杂而难于求解，要么太费时而不能实际应用。于是人们开始探讨研究使用智能优化算法[34-361来求解该问题，而遗传算法是近几年提出的一种模拟生物界自然选择和遗传机制，具有高度并行，群体寻优的新型最优化搜索算法，已经广泛用于解决各种具有NP．hard的问题。对于QoS组播路由问题，近年来已有一些学者采用遗传算法[37-39]来解决。文献[7】中的遗传算法采用树型编码，每条染色体代表一棵组播树，既减少了编码空间，也省略了解码操作。适应度函数的定义中采用罚函数，对不满足约束条件的个体施行惩罚。选择操作采用最佳个体保存和轮盘赌相结合的策略。选择父代中相同链路，将其直接遗传到子代，并连接零散子树实现交叉操作，变异采用指导性的操作过程。该算法的性能比较好，但对于遗传算法运行初期易陷入早熟，运行后期收敛缓慢的问题，文献[7】中没有采取措施抑制。本文算法在文献【7】算法的基础上进行了改进，改进后的算法收敛速度快，较好的抑制了早熟，实现全局优化。3．3．2算法描述3．3．2．1树型编码编码是遗传算法求解问题的关键。本文采用树型结构编码，具体步骤如下：首先从源节点出发随机搜索一条到任意一个组播目的节点的路由路径，把该节点标记为已访问。然后从一个未被访问的组播目的节点出发随机搜索，直到某个节点在先前组建的子树中。重复上面的步骤直到所有的组播目的节点都被访问过。这样就生成了一棵组播树，但需要指出这样生成的组播树，可能不满足QoS约束。可通过罚函数来处理不满足约束的组播树。3．3．2．2初始种群的选取假设种群的规模为Np，其值根据具体情况由系统设定。现有遗传算法19 山东大学硕+学位论文直接随机生成Ⅳ。个染色体，组成初始种群。这种随机性导致个体分布不均匀，通常会产生一些超常个体，这些个体因竞争力太突出而控制了选择过程，易陷入未成熟收敛，使遗传算法所求的解停留在某一局部最优点上，影响算法的全局性。为了克服这种现象，本文进行了改进，提出一种初始种群均衡生成法，即：先随机生成2N。个染色体，根据适应度值进行降序排列，选取中间的肋个组成初始种群。这种方法使得个体分布相对均匀，既避免了超常个体的出现，又淘汰了适应度很差的个体，使算法从第一代开始就在较好的搜索空间中搜索，从而加快了算法的收敛速度。3．3．2．3适应度函数适应度函数是遗传算法用来判断个体好坏的标准。本算法中个体是一棵覆盖源节点和目的节点的组播树，其费用越小，表明树的性能越好，性能好(满足QoS约束且费用较小)的个体适应度大，性能差(不满足QoS约束或费用较大)的个体适应度小。本算法的适应度函数定义为：f(T(s，M))=正(矾+耽)‘其中工2忑赢而，六2恩九(比lay(p(训一刚，厶=兀如(dday—jitter(p(s，m，)-J，))①。cz，={三，Zz<>0。，①李cz，={二二专％口是正实数，A，B分别为厶，厶的正加权系数，表示时延、时延抖动在适应度函数中所占的比重，值由系统根据具体应用设定。①d(Z)是时延度量的惩罚函数，当个体满足时延约束时其值为1，否则为rd(0<屹<1)：①西(z)是延时抖动度量的惩罚函数，当个体满足延时抖动约束时，其值为l，否则为饧(0<～<1)。白，白决定惩罚的程度。3．3．2．4选择操作采用保留最优解与轮盘赌相结合的方法。在群体交叉前，先选出最佳个 山东大学硕+学位论文体，直接遗传到子代群体中，其余个体采用比例选择法。各个个体的选择概率和其适应度成比例，个体适应度越大，其被选择的概率就高。设群体的规模为Ⅳ。，个体f被选择的概率P。为：。：』盟／-'i∑竺朋)经过若干次迭代，在遗传算法运行的后期阶段，群体中所有个体的平均适应度可能会接近于群体中最佳个体的适应度。也就是说大部分个体的适应度和最优个体的适应度差异不大，都会以相近的概率被遗传到下一代，导致无法对某些重点区域进行重点搜索，从而影响算法的运行效率。为了克服这种现象，本文在算法运行后期阶段引入了排序选择方法对个体的适应度进行拉伸，拉大最优个体与其他个体适应度之间的差异，以提高个体间的竞争性。排序选择方法的主要思想是对群体中的所有个体按其适应度大小进行排序，基于这个排序来分配各个个体被选中的概率。该方法需根据具体其情况预先设计一个概率分配表。3．3．2．5交叉操作交叉操作从当代群体中随机选择两个父代个体，以概率1交叉产生一个子代个体。交叉规则是首先选择父代中相同的链路，直接遗传到子代个体，接下来是连接这些零散子树构成一棵完整的组播树。采用启发式的连接方法：如果所选的父代个体在延时或延时抖动约束上只有一项不满足，则在子树间采用使该项约束最小的最短路径连接；若父代个体QoS约束全不满足或各满足一个或全满足，则子树间随机用“最短延时路径’’、“最小延时抖动路径”和“最小费用路径"连接。经过这种交叉方式产生的子代个体是一棵没有回路的组播树。3．3．2．6变异操作交叉完成后，子代个体以概率已进行变异。变异规则如下：从子代个体中随机选一些中间节点，删除连接这些节点的路径形成零散子树，然后按照与交叉操作相似的．连接方法连接。现有遗传算法通常采用反复实验来确定21 山东大学硕士学位论文己，很难找到适应于每个问题的最佳值。为此本文采用自适应的变异操作，即匕能够随适应度自动改变。对于适应度高于群体平均适应度的个体，相对应于较低的己，使该解得以保护进入下一代；而低于平均适应度的个体，相对应于较高的匕，使该解被淘汰掉。采用如下的公式进行调整：p—j掣，f>-f嘴已={厶。一厶’Ik：，f<厶其中，厶。表示当代群体中最大的适应度，厶表示当代群体中平均适应度，厂表示要变异个体的适应度。采用这种自适应的变异操作既可以保证群体的多样性，跳出局部最小，实现全局寻优；又可以保护较优解的基因不被破坏，加快收敛速度。3．3．2．7算法具体描述输入：网络拓扑图，源节点，目的节点集，QoS约束条件种群大小Ⅳ。，最大遗传代数MAXGEN输出：一棵满足约束条件代价最小的组播树，遗传代数步骤1．采用3．3．2．1中的编码方式随机生成2Ⅳ。个染色体，并计算其适应度值；步骤2．根据适应度大小进行排序，选取中间的N，个染色体组成初始种群；步骤3．记录当前代的最优个体currentbest和群体的平均适应度current·average-fitness。if(next-average—fitness--current-average-fimess)<占{引入排序方法，按适应度进行排序，根据系统设定的分配表进行概率分配以拉伸适应度。}·将最优个体直接放入交配池，余下个体采用轮盘赌方法选择放入交配池；步骤4．如，i_1tON，从交配池中随机选择两个父代个体，按概率1进行交叉操作； 山东大学硕+学位论文步骤5．对交叉生成的Ⅳ。个子代个体采用自适应己进行变异操作；步骤6．用保存的最优个体替换经交叉变异后得到的群体中适应度较小的个体，生成新一代群体，计算其平均适应度next．average．fitness；步骤7．判断终止条件，如果N。