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

《基于克隆策略的QoS选播路由算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于克隆策略的QoS选播路由算法张园园1，张英2，余镇危1（1．中国矿业大学（北京），北京，100083；2.中国科学院，计算技术研究所，北京，100190）文献标识码A；中文分类号：TP393摘要：在分析选播通信模型的基础上，提出一种基于克隆策略的QoS选播路由算法，在保证带宽和时延的条件下对目标函数进行优化，对带时延约束的QoS选播路由问题作了深入研究。既保留了遗传算法较强的全局搜索能力，又避免了局部搜索性能差和早熟现象，实验结果表明与基于遗传算法的选播路由算法相比,此算法是有效可行的。关键词：选播；路由

2、算法；QoS参数；时延约束；克隆策略AnycastQoSRoutingBasedonCloneStrategiesZhangYuanyuan1,YuZhenwei1(ChinaUniversityofMining&Technology,Beijing,100083)Email:yuanyuanzhang@163.comPhn:13693570131Abstract:Basedonstudyinganycastservice,ananycastQoSroutingalgorithmbasedonCloneStr

3、ategiesispresentedinthispaper.Withthebandwidthanddelayconstraints,thealgorithmoptimizesobjectivefunction,theproblemofdelay-constrainedQoSanycastroutingislubricated.Itreservessuperiorsearchabilityforglobalsearchingenerationalgorithm,andavoidspoorperformanceo

4、flocalsearchandprecociousphenomenon.Simulationresultsshowthatcomparedwiththosebasedongeneticalgorithm,thealgorithmisfeasibleandeffective.Keywords:anycast;routingalgorithm;QoSparameters;delayconstraint;cloneStrategies1引言随着Internet分布式计算的迅速发展,大量用户通过WWW来实现信息共享和

5、查询，一些流行的站点可能因为访问用户过多而发生阻塞。为了增强服务的可用性和改善网络的流量分布，选播作为一种新型网络通信方式在RFC2460定义为，一个选播地址对应多个网络接口，如果一个报文要求被传送到一个选播地址，则根据路由选择协议距离度量方式，它将被传送到由该地址标识的一组接口中最近的一个。图1给出选播服务的范例，三个服务器具有相同的选播地址，这里采用最小跳数路由，则A向用户1提供服务，而用户2的服务由C提供。随着音频、视频等流媒体业务的广泛应用，目前这种“尽力而为”的选播服务在提高网络的服务质量方面存在严

6、重不足，因此研究选播流的QoS具有可行性和现实意义。图1选播通信服务示意图基于多个不相关可加度量的QoS路由问题是一个NP完全问题，在现有的相关研究中，基金项目：网络系统性能测试及智能优化平台创新基金项目（BT2008-22）(theFoundationofInnovationProjectofnetworksystemperformancetestingandintelligentoptimizationplatform)张园园（1983-），女，河北保定人，博士研究生，主要研究方向：网络体系结构，路由协议

7、，选播；张英(1951-)，女，研究员，主要研究方向：计算机网络及性能评价;余镇危（1942-）,男，上海人，博士生导师，主要研究方向：网络体系结构，覆盖网，下一代互联网。多数采用的是遗传算法（GA），它具有鲁棒性强、并行搜索、群体寻优等特点，传统的GA通过交叉算子来产生繁衍新的个体，如果在算法收敛于全局最优解之前个体失去了多样性，遗传迭代无法进行下去，产生了所谓“早熟收敛”现象。针对这些问题，提出了克隆策略（CloneAlgorithm），其基本思想是以克隆选择算子和克隆变异算子代替遗传算法中的选择和变异算

8、子，引入反馈机制，对退化算子进行删除，并补充新的抗体，使寻找最优解的过程变得更有“目的”性，从而提高了收敛速度，并避免了遗传策略中的早熟、退化现象[1]。2选播QoS路由优化问题描述选播路由服务的基本模型可以从图论的角度抽象为有向加权图G=(V,E),其中V={v1,v2,…vn}是网络中的有限节点集，E={ei,j

9、}是网络中有限链路集合，设

10、V

11、=n,

12、E

13、=m分别为网络中节点数和链路数，每条边