27卷 第8期2010年8月

微电子学与计算机

MICROELECTRONICS&COMPUTER

Vol.27 No.8August2010

基于蚁群优化算法的多QoS选播路由算法研究

李陶深,肖 猛,葛志辉,赵志刚

(广西大学计算机与电子信息学院,广西南宁530004)

摘 要:提出一种基于蚁群优化算法的多QoS选播路由算法.算法设计了合理的路径评价方法,从平衡网络负载的角度出发,寻找适当的选播路由路径.通过对迭代最优解路径上的信息素的调整和算法重启的策略,算法有效地避免了陷入局部最优的缺陷,扩大了算法的搜索范围.实验结果表明,该算法能找到满足QoS约束的全局最优解,并在资源预留的基础上较好地满足用户对于带宽、时延的要求.关键词:蚁群算法;选播路由;QoS约束;负载平衡

中图分类号:TP391 文献标识码:A 文章编号:1000-7180(2010)08-0091-05

ResearchonMultipleQoSAnycastRoutingAlgorithm

BasedonAntColonyAlgorithm

LITao-shen,XIAOMeng,GEZh-ihui,ZHAOZh-igang

(SchoolofComputer,ElectronicsandInformation,GuangxiUniversity,Nanning530004,China)

Abstract:AnewQoSanycastroutingalgorithmbasedonanantcolonyalgorithmisproposedinthispaper.Inordertosearchareasonableanycastroutingpath,afelicitousestimatemethodoftheoptimizationpathisdesignedandtheloadba-lanceisconsidered.Byadjustingthepheromoneintheiteration-bestpathandre-initializingthealgorithm,theproposeda-lgorithmcanefficientlyavoidfallingintolocaloptimalanditcanenlargeglobalsearching.Theresultsofthesimulatingex-perimentshowthatthealgorithmcaneffectivelyfindthegloba-lbestsolutionthatsatisfiedtheQoSconstraintandbalancetheloadofnetworks,andalsocanbeutilizedtosatisfytheneedoftheclientsforbandwidth,delayandcostonthebasisofresourcereservation.

Keywords:AntColonyAlgorithm;anycastrouting;ServiceofQuality(QoS)constraint;loadbalance

1 引言

选播(Anycast)是Partridge等于1993年首次提

出,并在IPv6中被规定为一种标准的通信服务模型.选播的实现很大程度上取决于对路由的选择.研究表明[2],基于多个不相关可加度量的QoS路由问题是一个NP完全问题,目前采用的方法多为启发式算法.蚁群优化算法是受到自然界蚁群行为的研究启发而提出的一种用于求解组合优化问题的新型启发式随机搜索算法.它采用正反馈机制实现分布式全局优化,通过信息素的不断累积和更新最终达到收敛于最优路径的目的,算法的特征

收稿日期:2009-06-01;修回日期:2010-07-01

[3-4]

[1]

与网络路由优化问题的一些特征是可以互相匹配

的.因此,随着对蚁群优化算法研究的不断深入,蚁群优化算法逐渐被成功运用于解决网络由问题.文献[5]提出了基于蚁群算法的分布式QoS路由调度方法,文献[6]提出一种基于蚁群系统原理的QoS单播路由算法,文献[7]介绍了蚁群算法在QoS组播路由问题中应用.在选播路由方面,文献[8]提出了一种具有正反馈作用的分布式多蚁群算法,通过相互协调来调整单个蚂蚁的行为,使蚁群行为具有智能,且仅需要局部信息就能找到最优解.文献[9]提出了一种基于改进蚁群优化算法的选播路由算法

基金项目:国家自然科学基金项目(60963022);广西自然科学基金项目(桂科自0640026)