一种基于蚁群系统的多约束Qos路由算法

《一种基于蚁群系统的多约束Qos路由算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一种基于蚁群系统的多约束Oos路由算法冉敏高随祥徐葆（中国科学院研究生院，北京100039）E-maii：ranmin@sOhu.cOm摘要该文研究了多约束路由OOs问题，其中约束主要包括时延、带宽、延时抖动、成本等。给出了多约束OOs路由的数学模型，并提出了一种基于蚁群系统原理来解决多约束OOs路由问题的算法。仿真实验证明该算法能很好地优化网络资源。关键词多约束OOs网络路由蚁群算法文章编号1002-8331-（2005）07-0142-03文献标识码A中图分类号TP301.6AnAlgorithmBase

2、donthePrincipleofAntSystemforMultipleConstrainedOosRoutingRanMinGaoSuixiangXuBao（GraduateSchOOiOftheChineseAcademyOfSciences，Beijing100039）Abstract：ThispaperdiscussestheMuitipieCOnstrainedOOsROutingprObiem，thesecOnstrainscOnciudedeiay，bandwidth，deiay-jitter

3、，cOstandsOOn.ThispagergivesamathematicaimOdeiOfmuitipiecOnstrainedOOsrOutingprObiemandprOpOsesanaigOrithmbasedOntheprincipieOfantcOiOnysystem.SimuiatiOnresuitsdemOnstratethatthisaigOrithmcanOptimizethenetwOrkresOurces，andcancOnvergetOasatisfiedsOiutiOn.Keyw

4、ords：muitipiecOnstrainedOOs，netwOrkrOuting，antaigOrithm1前言图1举例说明了蚁群算法的原理。设一群蚂蚁从A到B随着网络技术的高速发展，一些多媒体业务应运而生。传觅食，初始阶段，由于路径上没有该激素，一群蚂蚁从A点随统internet所提供的尽力而为的服务方式已无法满足用户的机运动，一些到达C，再由C到B，另一些蚂蚁直接由A向C需求，对网络服务质量（OOs）的要求也越来越严格，例如对带移动，到达B后又沿BCA或BA返回A，由于AC+CB>AB，在宽、延迟、网

5、络资源及丢包率都有了一定的要求。现有的很多算蚂蚁运动速度不变的情况下，经过一段时间，在AB上经过的法只是针对一个或两个约束条件产生的（如最小带宽或最小时蚂蚁数就会多于ACB上经过的蚂蚁数，从而AB上的信息浓延等），在多种OOs约束下，这些算法具有一定的局限性。如何度就会高于ACB上的信息浓度。以后的蚂蚁根据路径上的信解决多约束OOs路由问题，如何在满足业务要求的同时，尽量息浓度来选择路径，当然越短的路径，就会有越多的蚂蚁选择。减少资源消耗，合理分配网络的流量负荷，减少阻塞率，成为大家关注的热点。该文采用的蚁群

6、算法，是近几年提出的一种新的优化方法。该算法不依赖于具体问题的数学描述，具有很强的全局优化能力和本质上的并行性，是解决NP-完全问题的有效方法。图1蚁群算法图例蚁群算法是1992年由意大利学者M.DOrigO等人首先提出的，它是对自然界蚂蚁寻径进行模拟而得出的一种模拟进化算法。然而，基本的蚁群算法在计算过程中容易造成大量无效搜蚂蚁个体之间通过一种称为外激素（pherOmOne）的物质来传递索或陷入局部最优问题。该文通过对基本蚁群算法进行改进，信息。蚂蚁所通过的路径上会留下这种激素，而蚂蚁本身又会在信息素的增加

7、方面只对当前最优路径上的信息素增加，且其通过这种信息的强弱来选择路径，从而互相协作，完成复杂任增量也因每段链路的重要程度而有所不同。这些改进使信息素务。该物质在不断挥发，距离越短的路径上相对走过的蚂蚁数的浓度与解的最优性成正比，避免了大量无效搜索，利于全局就会越多，该物质的强度就会越大。由于蚂蚁在运动中感知这优化。种物质，并倾向于选择向该物质强度高的方向移动。这就形成该文通过对多种约束条件的分析，利用蚁群算法的正反馈了一种信息正反馈现象，即某条路径上走过的蚂蚁越多，则后性和协同性，提出一种基于蚁群系统的多约束

8、OOs路由算法，来的蚂蚁选择这条路径的概率就越大。运用到路由寻路上，则很好地解决了多约束OOs路由优化的问题。路径越短的，后来的蚂蚁选择该路径的概率越大。该文的结构如下：第2节描述了多约束OOs的数学模型；基金项目：国家自然科学基金资助（编号：10171095）作者简介：冉敏（1973-），女，硕士生，主要研究方向为算法设计。高随祥（1962-），男，教授，主要研究方向为组合最优化。徐葆，女，硕士生