基于克隆策略的QoS选播路由算法.doc

基于克隆策略的QoS选播路由算法张园园1，张英2，余镇危1（1中国矿业大学（北京），北京，100083；2.中国科学院，计算技术研究所，北京，100190）文献标识码A ；中文分类号：TP393摘要：在分析选播通信模型的基础上，提出一种基于克隆策略的QoS选播路由算法，在保证带宽和时延的条件下对目标函数进行优化，对带时延约束的QoS选播路由问题作了深入研究。既保留了遗传算法较强的全局搜索能力，又避免了局部搜索性能差和早熟现象，实验结果表明与基于遗传算法的选播路由算法相比,此算法是有效可行的。关键词：选播；路由算法；QoS参数；时延约束；克隆策略 Anycast QoS Routing Based on Clone StrategiesZhang Yuanyuan1, Yu Zhenwei1(China University of Mining &Technology, Beijing, 100083)Email: Phnbstract: Based on studying anycast service, an anycast QoS routing algorithm based on Clone Strategies is presented in this paper. With the bandwidth and delay constraints, the algorithm optimizes objective function, the problem of delay-constrained QoS anycast routing is lubricated. It reserves superior search ability for global search in generation algorithm, and avoids poor performance of local search and precocious phenomenon. Simulation results show that compared with those based on genetic algorithm, the algorithm is feasible and effective.Key words: anycast; routing algorithm; QoS parameters; delay constraint; clone Strategies 1 引言 随着Internet分布式计算的迅速发展,大量用户通过WWW来实现信息共享和查询，一些流行的站点可能因为访问用户过多而发生阻塞。为了增强服务的可用性和改善网络的流量分布，选播作为一种新型网络通信方式在RFC2460定义为，一个选播地址对应多个网络接口，如果一个报文要求被传送到一个选播地址，则根据路由选择协议距离度量方式，它将被传送到由该地址标识的一组接口中最近的一个。图1给出选播服务的范例，三个服务器具有相同的选播地址，这里采用最小跳数路由，则A向用户1提供服务，而用户2的服务由C提供。随着音频、视频等流媒体业务的广泛应用，目前这种“尽力而为”的选播服务在提高网络的服务质量方面存在严重不足，因此研究选播流的QoS具有可行性和现实意义。图1 选播通信服务示意图基于多个不相关可加度量的QoS路由问题是一个NP完全问题，在现有的相关研究中，基金项目：网络系统性能测试及智能优化平台创新基金项目（BT2008-22）(the Foundation of Innovation Project of network system performance testing and intelligent optimization platform)张园园（1983-），女，河北保定人，博士研究生，主要研究方向：网络体系结构，路由协议，选播；张英(1951-)，女，研究员，主要研究方向：计算机网络及性能评价;余镇危（1942-）,男，上海人，博士生导师，主要研究方向：网络体系结构，覆盖网，下一代互联网。多数采用的是遗传算法（GA），它具有鲁棒性强、并行搜索、群体寻优等特点，传统的GA通过交叉算子来产生繁衍新的个体，如果在算法收敛于全局最优解之前个体失去了多样性，遗传迭代无法进行下去，产生了所谓“早熟收敛”现象。针对这些问题，提出了克隆策略（CloneAlgorithm），其基本思想是以克隆选择算子和克隆变异算子代替遗传算法中的选择和变异算子，引入反馈机制，对退化算子进行删除，并补充新的抗体，使寻找最优解的过程变得更有“目的”性，从而提高了收敛速度，并避免了遗传策略中的早熟、退化现象1。2 选播QoS路由优化问题描述选播路由服务的基本模型可以从图论的角度抽象为有向加权图G=(V,E),其中V=v1,v2,vn是网络中的有限节点集，E=ei,j|是网络中有限链路集合，设|V|=n,|E|=m分别为网络中节点数和链路数，每条边E上有链路带宽、链路时延,和链路代价三个参数2，其中：, 为链路上可用带宽的度量，为数据包分组通过该链路所经历的时间度量，为链路使用代价的度量。 从网络的抽象模型可知，网络由节点和链路两大要素组成。严格说，对其进行分析也应包括节点和链路两大要素，为突出问题的本质，本文对网络模型进行了合理简化：假设存在一种分配策略，它能将网络节点的QoS度量合理分配到与其相邻链路的度量上。QoS路由的链路度量参数一般分为可加性、可乘性和凹凸性3种，链路带宽属于凹凸性度量参数、链路时延和链路代价属于可加性度量参数3。一个选播QoS路由请求可描述为其中：源节点S是一组请求服务节点，表示一组源主机，作为目标的选播地址，则是一个共享选播地址A并提供相同服务的选播组，为业务请求的最小带宽；为业务请求的最大时延。设，其中，是从源节点到选播组的一个成员节点的一条选播路径。则路径的带宽、时延和代价分别为： 选播QoS路由算法的目标是：从某个源节点到目标选播组的所有路径中选择一条满足带宽约束、时延约束且代价最小的路径同时满足下面公式： 3 基于克隆策略的路由算法设计3.1克隆算法简介 克隆算法与传统的遗传算法相比本质上没有什么区别，在保留原遗传算法的全局搜索能力等优良特性的同时，克隆算法的操作全部是在一个个个体上进行，与种群中的个体多样性无关，因此克隆策略不要求初始种群中的个体具有多样性。在迭代的过程中也不要求初始种群的个体具有多样性，即使种群中的个体全部进化到相同也不影响操作的进行，所以克隆算法不会产生早熟收敛的现象。整个克隆算法(CA, Clone Algorithm)由初始化抗体群、计算抗体亲和度、克隆、克隆交叉、克隆变异和克隆选择等六个功能模块组成。算法步骤如下：1）初始种群生成模块4。定义初始抗体群为A,规模为N,每个抗体的编码长度为L,编码方式可选择二进制编码、序号编码等。随机在解空间生成抗体群，规模为的抗体,为进化代数。2）计算抗体亲和度。建立抗体亲和度函数，计算个体的亲和度。3）克隆。从将第个抗体按公式，克隆个，得到的规模为的克隆后抗体群，其中为克隆系数；4)克隆交叉。对、中的抗体进行克隆交叉，即按照克隆交叉概率随机选取一对抗体,对这对抗体中的一个或多个点进行交叉操作，产生新抗体群。5）克隆变异。对中的抗体按照突变概率进行突变操作,即抗体按照突变概率随机选取抗体中的一个或多个点,并采用高斯变异随机生成的一个或多个基因来取代，形成新的抗体群。6）克隆选择。合并抗体群和，选出亲和度最高且互不相同的抗体组成新抗体群。3.2 基于免疫克隆策略的选播路由算法描述1）抗体编码与初始化抗体群采用不定长的节点序列编码机制，从源节点到选播组成员节点的可行路径上的每一个有效节点就是该条路由解空间的一个抗体。生成初始种群时，针对种群规模M，在其范围内，采用图的广度优先搜索算法来生成：1)首先选择源节点的所有相邻节点，建立一个队列并将这些相邻节点入队列，并做访问标记visited。2)访问下一层相邻节点时每次从队列中压出一个节点，再访问其相邻节点，并类似的将访问到的下层相邻节点压入队列并做访问标记visited。3)重复上述动作直到访问到目标选播组成员节点，或者队列为空。4)记录下所得符合要求的各条路径；若这些路径的数量规模大于种群规模M则随机选择其中仅M数量规模的路径，否则若小于M则全选。5)这些路径的集合即抗体的集合就是初始种群。2）计算抗体亲和度 由于本问题是求解最小值问题，为了研究问题方便，我们转换成极大值并且构造了一个新的亲和度函数，其中为调整参数，为路径上的费用和，为路径上的时延值。通过调整参数可以根据需要选择满足要求的路径。3）克隆对抗体群中每一个抗体按规模克隆得到新的抗体种群。其中为克隆算子，为克隆系数且，用来控制克隆的规模，为取整函数，为亲和度函数，从克隆规模可看出亲和度越高的抗体科龙规模就越大，使得算法在很大程度上使高亲和度抗体中的优秀基因得以更好的保存和发展。4）克隆交叉 按照对中的一对或多对抗体的一点或多点进行克隆交叉，也就是改变选播路径中多个节点的位置，重新生成一条新的选播路径，若在新路径中存在编号重复的节点，则重新进行交叉操作。设为交叉算子，即产生新抗体群。5）克隆变异本文为了操作简单，采用按位变异，即随即选取一个整数按照变异概率取代抗体上原有的值,从而生成新抗体群。若产生的解不满足选播条件,则重新进行克隆变异操作。6）克隆选择对父代抗体群和变异后的克隆抗体群进行克隆选择操作,利用亲和度函数选出亲和度最高且互不相同的个抗体组成新抗体群。7）结束条件 计算中每个抗体的亲和度,若新一代抗体中存在最优个体,则算法终止；否则转到(2)继续操作。3.3 算法性能分析可以看出，克隆算法的实质是在一代进化中,在候选解的附近，根据亲和度的大小产生一个新的子群体，从而扩大了搜索范围,有助于防止进化早熟和搜索陷入局部极小值；多克隆算子还实现了子群之间的信息交换，提高了克隆的多样性；进一步分析可看出，克隆算子是将一个低维空间(维)的问题转化到一个更高维(维)中，从而获得对问题更全面的认识。根据文献5证明5,克隆策略算法的种群序列是有限齐次马尔可夫链6,并且该算法是以概率1收敛的。该算法的时间复杂度与抗体群规模，免疫克隆规模，算法的迭代次数有关，所以算法的复杂度为。4 实验设计及仿真网络拓扑结构采用Waxman提出的方法随机生成，该方法能够随机产生具有实际网络特征的拓扑结构，因此已被许多研究者所采用6。为了方便比较，我们采用文献3随机生成的网络拓扑。假设网络边的延迟代价为一个范围的随机整数，并且每个节点的度约束指定为之间的一个随机整数，采用随机数生成器随机生成各链路上的时延和代价数据，对遗传算法和本文的算法进行比较。图2 网络随机拓扑图 设各算法最大进化代数为，抗体种群规模为30，克隆系数，由计算可得克隆后的群体规模=139，设克隆交叉和变异概率为0.1；对于遗传算法的初始种群规模取（约等于）且它是通过克隆算法生成的群体复制得到，并且设定遗传算法的交叉概率为0.4；变异概率为0.15。假设一个带约束QoS选播请求不妨设，。4.1 算法的有效性分析对于不同的源节点应用本算法,经过网络仿真后得到的从到各成员的最优路径如下，其中斜体表示得到的最优解：从以上的实验数据分析可知,算法能从多个选播组成员中选取综合性能最优的一个为用户提供服务。表1 的路径结果源节点到G(A)的路径时延代价亲和度f(T)99721324135520.476997220271.11399734301233770.935表2 的路径结果源节点到G(A)的路径时延代价亲和度f(T)14141230341324169820.3181414113827245770.84214141221351.6004.2 算法的收敛性分析本文采用NS-2软件作网络协议模拟分析，为了在NS-2中实现对选播QoS路由算法的仿真，在C+与OTCL层次上分别进行了扩展，把网络中若干个选播服务器统一管理，建立一个选播组并分配一个唯一的标识，本实验只考虑带宽、时延和代价三个QoS约束，以时延和代价加权值为度量参数作为选播服务节点的选取机制。由于时延，代价均为QoS可加性度量，仿真中每个数据点的实验为100次，然后统计平均值，利用NS-2的gnuplot 工具，分别针对本算法和遗传算法建立一个了考察中每个源节点的路径时延及代价随进化代数变化的趋势走向。从图3和图4可以看出在迭代初期，遗传算法的时延略优于本算法，原因在于克隆算法的种群多样性即种群维数是逐步提高的，但随着进化代数增加，本算法的收敛速度是比较快的，基本在40代的时候保证时延约束并找到最优路径。表3是克隆算法和遗传算法中代价随代数变化情况。图3 本算法不同源节点时延随进化代数的变化表3 算法性能的比较算法 代数20406080100CA6659504432GA7365585245由此可见，克隆算法较遗传算法能能够很快收敛到最优解，而且在保证带宽，时延约束的同时，使代价开销尽量小。此性能优于遗传算法，尤其是在时延限制放大，候选服务资源增多的情况下，优势明显。本算法适用于在满足实时性要求的基础上，需要对网络资源高效利用的多媒体业务中。图4 遗传算法不同源节点时延随进化代数的变化5.总结选播路由是目前网络研究领域研究的热点问题。本文对网络层QoS选播路由算法进行了研究，给出了问题模型，提出了一种新的选播QoS路由算法，本算法克服了遗传算法中局部收敛性差和“早熟”现象，取得了较好的效果，同时有更快的收敛速度。实验结果证明本算法具有良好的性能，是有效可行的。下一步的研究工作主要包括在多种条件限制下的选播QoS路由算法，及网络状态信息不精确下的选播路由