改进蚁群算法在QoS组播路由中的应用研究

格式：pdf
大小：1.54 MB
文档页数：4

下载文档原格式

基于蚁群算法的QOS组播路由问题研究

叼（，＝１ｃｓ（，）ｉ）／ｏｔｉＪ
（）１
（）：ｅＥ∈Ｒ费用函数ｃｓ（）Ｅ∈Ｒ，ｏｔｅ：。那么存
在如下关系：
式中：（Ｊ为信息素浓度；为信息启发式因子，ｒｉ）
表示轨迹的相对重要性；为期望启发式因子，表
法，一种启发式算法，于解决Ｎ是对Ｐ—Ｃ问题具
有很强优势。本文将蚁群算法用于多约束ＱＳｏ
随着网络流媒体技术的发展，ｎｅｎｔ经从Ｉｔｅ已ｒ单一的数据传送向图像、音、频等多媒体信息语视
（１一
ｓＥｌｗ（］［（川ｒ，叼，）
０，否则
（２）
３基于蚁群优化的Ｑ０组播路由Ｓ
（ｎ—ｃｎ一１若 ∈ ａｌｗ），ｌｏ
算法
３１算法描述．
传统蚁群算法利用蚂蚁留下的信息素搜索可行解。这样的蚁群算法具有分布式计算的特点，以避免算法过早收敛。但是传统蚁群算法可的缺点是，由于利用的是局部最优解，样算法这很容易陷入局部最优，系统出现停滞现象。使模拟退火算法的特点是在搜素最优解的过
ｉｔｏａｏｔｍｕ．Ｇｉｅａｅｗｏｋｏｔｎｍｏｅ，ｇｉｅｔｅｅｅａｔａａｅｅｓｈｓｍｕａｉｎｎｏｌｃｌｐｉｍｖｎｎｔｒｒｕｉｇｄｌｖｎｈｒｌｖｎｐｒｍｔｒｔｅｉｌｔｏ

改进蚁群算法在QoS组播路由中的应用

ＯＳ网络的拓扑结构由加权图Ｇ（Ｅ来表示，中ｏＶ，）其
萎
Ｖ＝｛Ｖ，Ｖ｝网络节点集，Ｅｅ，。… ，是节Ｖ，。 …，是＝｛ｅ，ｅ｝
点的双向链路集。Ｅ【为网络中边的数目。设Ｐ（，）Ｓｉ表ｎ
示从源节点ｓ目的节点ｍ的路径，Ｔ（，表示组播树。至ＳＭ）
（（ＪＩ）＝＞（（），∈Ｊ ’ ｛Ｉ），１Ｐ、，』，
一
，
Ｐ（ｓ
，、（）２
链路带宽崩：只，用来表示链路ｅ的剩余带宽。Ｅ上
对于任意路Ｐｓ１）（，ＩＴ，定义如下：
Ｂ（Ｐ．ｌ）＝ｍｉＢ《７∈Ｊ，Ｉ１）ｎｃ）Ｖ７，ｒ、
法的缺点，提出了一种双向蚁群算法对该问题进行求解，并改进了蚁群算法的信息素更新策略。仿真实验表明，该算法能快速搜索并收敛到全局（似）最优解，且随着网络规模的增大，算法保持了良好的特性。近关键词：组播路由；双向蚁群；ＱＳｏ；蚁群算法
（ｏｇｆＩｏａ￣ｃｎ＆Ｅｇｅｉ，ＳｎｏｏａＵＮｒＺ，Ｊａ．ａｄｎ￣０１．Ｃ：）Ｃ／ｅｏｆｍｔｎＳ／ｃ＠ｎｌｅｎｈｄｎＮｒｌｎｅ／／ｅｎｒｌｅｈｒｇａｇｍｓｙｎｎＳｎｏ５０４／ａｈｇ：ｈ
对于任意路径Ｐｓｉ）（，，定义如下：ｎ
，（（．）＞Ｄ（ＶＪ，ＰｓⅢ）＝．，∈ ）Ｊ

改进的量子蚁群算法求解带约束QoS组播路由

ＫｅｒｓＱＡ；ＱＳｒｕｉｇｄｎｍｉ；ｓａｅｙｒｖｌｉｇｇｔｙｗｏｄ：ＡＣｏｔ；ｙａｃｔｔ；ｅｏｎａｅｏｎｒｇｖ
０引言
随着网络规模的不断扩大，业务也在快速增长，服务ＩＰ且
ＺＵＯｉｇｌｎ．ＹＵｉｌｎＪｎ —ｏｇＧｕ —ａ
（ｏｌｅｆｏｐｔｄＥｅｔｎｃｅｈｏｏｙＣｌｇｍｕｅａｌｒｉＩｆｒｔｎｕｎｄｎｖｓｙｆｅｏｈｍｉｃｎｌｇ，ｅｏＣｒｎｃｏｉＵｎｅｉＰｒａＴＭａｍｉｇ２００Ｃｉａｏｎ５０，ｈｎ）５
ｕｄｔｅｎｈｒｍｏｅｙｈｕｎｍｔｉｎｇｔ．Ｆｒｅｒ，ａｙａｃｄｕｔｎｔｉｎａｇｅｔｔｇｕｒｒｄｐａｓｈｔｅｅｔａｐｏｎｅａｔｒａｏａｅｕｔｒｅｎｍｉａｊｓｂｔｑｕｏｔｈｍｏｄｍｅｔｏａｏｎｌｓａｅｙｉｐｔｏｗａｄｒｔｒｓｆｎａ
摘要：了快速求解在带宽、为延迟等约束下的最小代价组播路由树，避免求解过程陷于局部最优，并对量子蚁群算法进行
了改进。改进算法采用量子旋转门对信息素进行更新，出了一种动态调整旋转角的策略，从理论上对其进行了证明。提并在
ｏｈｒｓｅｔ，ａｄｍｅｎｉｖｉｅｎａｐｄｉｃｌｐｉｍ，ａｒｖｄｔｅｑａｔｍｎｏｏｙａｇｒｔｍｒｐｓｄｗｈｃｔｅｐｃｓｎａｗｈｌａｏｄｂｉｇｔｐｅｌａｔａｅｒｎｏｏｍｕｎｉｍｐｏｅｕｕａｔｌｎｌｏｉｈｎｃｈｉｐｏｏｅ，ｓｉｈ

基于改进的蚁群算法的组播路由问题的研究

基于改进的蚁群算法的组播路由问题的研究俞慧;吴巍;黄潇;宫婧;孙知信【期刊名称】《计算机技术与发展》【年(卷),期】2012(22)1【摘要】目前,蚁群算法在路由协议上已有广泛应用.通过研究蚁群算法的特性和目前在路由协议上的应用,发现其在加快运行时间、局部最优解等问题上还有改进的空间.为此文中提出一种蚁群优化算法,使蚁群算法更好地应用在路由协议上.针对蚁群算法容易出现局部最优解的问题,文中提出一种链表随机选择法,该方法能有效地减小蚁群算法出现局部最优解的几率.同时为了减少蚁群算法在选择路径上的时间,提高运行速率,文中还提出了一种雅克比迭代收敛准则,此方法很好地减短了算法时间.%Currently,the ant colony algorithm has been widely used in routing protocols. By researching the ant colony algorithmic characteristic and application of routing,it finds that there is the room of improvement in speeding up the running time,reducing the rate of causing local optimization problems and so on. In order to make better application of ant colony algorithm in routing protocol,it proposes a kind of ant colony optimized algorithm to improve its performance. Because ant colony algorithm is easy to cause local optimization problems, it proposes a random selection method using chain table. This method can effectively reduce the possibility of local optimization problems in ant algorithm. Meanwhile,in order to reduce the time of choosing a path and increase therunning rate.it puts forward new convergence criteria according to Jacobi iterative thoughts. It is very good to cut down the cost of time.【总页数】4页(P107-110)【作者】俞慧;吴巍;黄潇;宫婧;孙知信【作者单位】南京邮电大学理学院,江苏南京 210003;南京邮电大学理学院,江苏南京 210003;南京邮电大学理学院,江苏南京 210003;南京邮电大学理学院,江苏南京 210003;南京邮电大学物联网学院,江苏南京 210003【正文语种】中文【中图分类】TP301.6【相关文献】1.基于改进蚁群算法的组播路由算法研究 [J], 柴井坤;魏圆圆;曲立国2.蚁群算法行为属性的改进解决QoS组播路由优化问题 [J], 曾宇恒;宋留静;白嘉豪3.基于一种新的蚁群算法的QoS组播路由问题的研究 [J], 张凌;毛力4.基于改进信息素的蚁群算法在QoS组播路由中的研究 [J], 陈暄;万志平;许方恒;龙丹5.基于蚁群算法的QoS组播路由问题研究 [J], 杨晓敏;王春红;李萍因版权原因，仅展示原文概要，查看原文内容请购买。

基于改进信息素的蚁群算法在QoS组播路由中的研究

基于改进信息素的蚁群算法在QoS组播路由中的研究陈暄;万志平;许方恒;龙丹【期刊名称】《计算机应用研究》【年(卷),期】2012(029)011【摘要】QoS multicast routing problem has been widely used for solving complex optimization problems in various engineering and science fields. In order to solve the time or stagnant problems in large-scale traveling salesman problem by using ant colony algorithm, this paper proposed an ant colony algorithm based on the improved pheromone. The improved algorithm made the pheromone after searching reflect solution better and better. The results of simulation experiments show that, based on the pheromone adjustment improved ant colony optimization algorithm can obtain better solution than the basic ant colony algorithm , and increases the stability of the algorithm.%针对传统的蚁群算法在求解大规模旅行商问题时容易导致搜索时间过长或陷入停滞的问题,提出了一种基于改进信息素的蚁群算法.通过蚁群算法的改进,使得每轮搜索之后的信息素都能更好地反映解的质量.实验仿真结果表明,改进后的蚁群算法能获得比传统的蚁群算法更优的解,同时具有更快的收敛速度和较好的稳定性.【总页数】4页(P4296-4299)【作者】陈暄;万志平;许方恒;龙丹【作者单位】浙江工业职业技术学院,浙江绍兴312000;浙江工业职业技术学院,浙江绍兴312000;浙江工业职业技术学院,浙江绍兴312000;浙江大学,杭州310058【正文语种】中文【中图分类】TP393【相关文献】1.改进的蚁群算法与网络QoS组播路由研究 [J], 王文国;樊丽娟;刘洋2.改进的蚁群算法在QoS网络路由中的应用 [J], 胡琼琼;雷秀娟;张兰3.基于改进的量子粒子群算法在QoS组播路由中的研究 [J], 万振凯;曾蕾4.改进蚁群算法在QoS组播路由中的应用 [J], 孙倩;王新华;许经彩5.改进蚁群算法在QoS组播路由中的应用研究 [J], 魏勇;赵开新;张松青;王东署;孙新领因版权原因，仅展示原文概要，查看原文内容请购买。

一种新的混沌蚁群算法及其在QoS组播路由优化问题中的应用

ｔｏｌｏｉｍｏｄｎｍｉａｌｅｅｔｐｒｍｅｅｓｏｈｎｏｏｙａｇｒｔｍｎｍｐｏｅｌｂａｅｒｈｎｎｏ－ｉｎａｇｒｔｈｔｙａｃｌｙｓｌｃａａｔｒｆｔｅａｔｃｌｎｌｏｈａｄｉｒｖｓｇｏｌｓａｃｉｇａｄｃｎｉｖｒｅｃｂｌｔｅ．Ｓｍｕａｉｎｒｓｌｈｗｈａｈｓｃａｔｃａｔｃｌｎｐｉｚｔｏｌｏｉｈｐｒｏｍｓｂｔｒｔａｅｇｎｅａｉｉｓｉｌｔｏｅｕｔｓｏｔｔｔｉｈｏｉｎｏｏｙｏｔｍｉａｉｎａｇｒｔｍｅｆｒｅｔｈｎｉｓｅ
种新的混沌蚁群算法及其在ＱＳ组播路由优化问题中的应用ｏ
一
孔
笋，陈增强
（开大学信息技术科学学院，津３０７）南天００１
摘
要：基于ＱＳ的组播路由问题是通过发现具有某种相关性能约束的最佳组播树，更好地利用网络资源以支持ｏ来
ｒｑｉｅｎｓｂｅｒｈｎｏｈｐｉｌｍｕｉａｔｔｅｔｏｅｏｍａｅｃｎｔａｎｓｅｕｒｍｅｔｙｓａｃｉｇｆｒｔｅｏｔｍａｈｃｓｒｅｗｉｓｍｅｐｒｒｎｃｏｓｒｉｔ．Ｔｈｓｐｏｌｍ，ｗｈｃｓｈｆｉｒｂｅｉｈｉ
ｔｅｇｎｔｌｒｈｎｎｃｌｙｏｔｉｔｎｍｅｔｎｄｈｒｒｏｉｏｕｉｓｒｕｉｇｐｏｌｍｗｔｈｅｅｉａｏｉｍａｄａｔｏｎｐｉｚｉｎｉｅｅｅｆｌｎａＱＳｍｈｃｔｏｔｒｂｅｉｃｇｔｏｍａｏｏｏｓｖｇａｎｈ

求解QoS路由优化的蚁群算法研究的开题报告

求解QoS路由优化的蚁群算法研究的开题报告开题报告：基于蚁群算法的 QoS 路由优化研究一、研究背景在Internet中，QoS（Quality of Service）在网络传输过程中的重要性与日俱增。

QoS在不同的应用场景中具有不同的表现，如低延迟、高可靠性和高带宽等。

QoS是通过选择最优路径、优化网络拓扑结构等方法来提高网络质量的。

而QoS路由是保证网络性能的一种重要方法，尤其对于对服务质量和网络性能要求高的业务，QoS路由不仅能提高网络服务可靠性和质量，同时避免传输浪费和减少时延。

因此研究如何优化QoS路由算法，已经成为网络研究的热点之一。

二、研究内容本文研究基于蚁群算法的QoS路由优化算法，并将其应用于Internet网络中。

蚁群算法是一种基于群体智能思想的优化算法，它的优化策略是基于模拟真实的蚂蚁行为。

我们将基于蚁群算法的QoS路由优化算法设计为重要的优化方案，以优化QoS 路由算法的性能。

我们的研究主要包括以下几个方面：1. 首先，我们将研究和分析现有的QoS路由算法，确定优化方案的需求及具体优化目标，为后续的研究提供方向。

2. 然后，我们将基于蚁群算法的优化方案进行设计和实现，从而提高QoS路由算法的可靠性和性能。

我们将选择蚁群算法作为优化算法，通过仿真的运行结果来分析、测试、验证QoS路由算法。

3. 最后，我们将在真实网络环境下对我们的优化算法进行实际应用，对其性能进行测试，同时与现有的其他优化算法进行对比。

三、研究方法本文主要采用以下研究方法：1. 文献综述方法：通过收集网络研究领域内的相关文献和论文，研究分析已有的QoS路由算法及其研究结果，为我们的优化方案设计提供理论支持。

2. 算法设计方法：我们将基于蚁群算法的优化方案进行设计和实现，并结合多个实验来验证改进算法的有效性。

3. 实验仿真方法：我们将使用NS2仿真器来进行实验仿真，以验证我们的算法优化方案在QoS路由中的有效性。

基于蚁群算法的+Ad+Hoc+网络+QoS+组播路由研究

分类号：____________密级：______________ ＵＤＣ：____________ 单位代码：______________硕士学位论文论文题目：基于蚁群算法的Ad Hoc 网络QoS 组播路由研究学号：_________________________作者：_________________________专业名称：_________________________2011 年06月17日李浩磊公开 1 0 1 2 7 计算机应用技术 200802053 TP393内蒙古科技大学硕士学位论文论文题目：作者：_________________________指导教师：单位：协助指导教师：单位：单位：论文提交日期：2011年 06月 17日学位授予单位：内蒙古科技大学谭跃生教授内蒙古科技大学基于蚁群算法的Ad Hoc 网络QoS 组播路由研究李浩磊基于蚁群算法的Ad Hoc网络QoS组播路由研究Research on Ad Hoc Network QOS Multicast Routing Based on Ant Colony Algorithm研究生姓名：李浩磊指导教师姓名：谭跃生内蒙古科技大学信息工程学院包头014010，中国Candidate：LiHao-leiSupervisor：TanYue-shengSchool of InformationEngineeringInner Mongolia University of Science and TechnologyBaotou 014010，P.R.CHINA独创性说明本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工作及取得研究成果。

尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得内蒙古科技大学或其他教育机构的学位或证书所使用过的材料。

基于改进的蚁群系统的多QoS约束组播路由算法

能优化算法求解带QoS 组播路由向题的文章
已发表了许多，但是存在易于陷人早熟收敛和
成一个无向带权连通图G=(V,E)，其中V为网
络节点集合，为网络双向链路的集合， E 并记
局部求精能力不足等明缺点。因此本文显的提出了一种基于改进蚁群优化算法的QoS 组
e=(u,v)表示从节点u 到节点v 的边。源节点 ‘ 目节点集M, delay , del ay - jitte r , . 的 bandwidth ,degree,packet- loss 分别表示给
，引言
组播路由是一种源节点可以同时向多个
目的节点发送信息的通信方式。带Qas 约束
组播路由问题的N标是寻求一裸满足QoS 要
正反馈现象:某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。虽然单个蚂蚁的选路能力有限，但是通过个体之间的信
C (T二 ot(v 护 )最 .A ，氛Ce )+票 t(e 小，
息交流，整个蚁群之间不断组成员包括发送者与者，使网接收同时络满足QoS 要求. 这等价
于求解带约束的最小Steiner 树问题。已经证
明，求解带约束的最小Steiner 树是NP- C问
题，因而用近似求解方法解决。
3 多OoS约束组播路由问题的建模
2)从s 到d 〔 M的延迟抖动满足:
息素，希望实现既加强算法的全局搜索能力又
加快收敛速度。为达此目的，信息素分期调
D dayhtta}s,d)二艺D elay)itte.(v)+ 艺DdaylM a
(e) s A dds，夕e. 一t
2 蚁群优化算法原理
蚊群算法是对自然界蚂蚁的寻径方式进

基于蚁群算法的QoS组播路由研究的开题报告

基于蚁群算法的QoS组播路由研究的开题报告一、选题背景和意义随着互联网的高速发展，网络应用的规模和复杂性也不断增加，需要提供稳定、高质量的服务，因此QoS（Quality of Service）作为网络应用的基础，逐渐受到人们的关注。

组播路由是在满足QoS的前提下，实现组播数据的广播。

QoS组播路由是指在组播播放的过程中，通过网络节点的数据缓冲、调度和队列管理技术，为组播数据流提供优质的服务质量，避免网络拥塞、流量控制过度等问题，提高网络的数据传输性能。

蚁群算法（Ant Colony Algorithm）是一种基于自然界中蚂蚁觅食行为的启发式优化算法，其优点在于简单、易于实现、鲁棒性强等。

利用蚁群算法来解决QoS组播路由问题，可以提高网络的性能和稳定性，降低网络成本，具有重要的研究和应用价值。

二、主要研究内容和目标本论文的研究内容和目标是基于蚁群算法的QoS组播路由。

具体来说，本研究将从以下几个方面进行探讨：1. 分析组播路由中涉及的QoS参数、组播树选取机制等关键问题，确定适合基于蚁群算法的QoS组播路由模型。

2. 通过实验模拟和理论分析，研究蚁群算法在QoS组播路由中的应用，并与其他优化算法进行比较。

3. 针对QoS组播路由中的时延、带宽、丢包等QoS参数，提出一种基于蚁群算法的优化策略，并进行实验验证和性能评估。

4. 分析蚁群算法在QoS组播路由中存在的问题和不足，并提出优化和改进方案，提高其应用效率和性能。

三、研究方法本文的研究方法主要包括以下几种：1. 文献综述：对QoS组播路由和蚁群算法进行系统性的研究和分析，收集和整理相关文献。

2. 算法设计：根据蚁群算法的特点和QoS组播路由的需求，设计适合的蚁群算法模型，并对其进行改进和优化。

3. 实验仿真：通过仿真实验和性能测试，验证蚁群算法在QoS组播路由中的优化效果和性能表现。

4. 总结分析：分析实验结果，总结改进方案，并提出未来研究的方向和建议。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

改进蚁群算法在QoS 组播路由中的应用研究魏勇1，赵开新1，张松青1，王东署2，孙新领1（1.河南工学院，河南新乡453002；2.郑州大学电气工程学院，郑州450001）摘要：基本蚁群算法直接应用在QoS 组播路由时，容易产生局部最优路径，并且收敛速度较慢，本文对基本蚁群算法的状态转移规则和信息素的更新方式进行改进，并把改进的蚁群算法应用到QoS 组播路由中，提出了基于改进蚁群算法的QoS 组播路由方案，仿真实验表明，改进后蚁群算法的性能明显优于基本蚁群算法。

关键词：蚁群算法；组播路由；信息素；最优路径中图分类号：TP391文献标识码：A文章编号：1001-7119（2017）12-0183-04DOI:10.13774/ki.kjtb.2017.12.040Research of Improved Ant Colony Algorithm in QoS Multicast RoutingWei Yong 1，Zhao Kaixin 1，Zhang Songqing 1，Wang Dongshu 2，Sun Xinling 1（1.Henan Institute of Technology ，Henan Xinxiang ，453003，China ；2.Electrical Engineering School of Zhengzhou University ，Zhengzhou 450001，China ）Abstract ：According to basic ant colony algorithm is easy to fall into local optimum and the defects of slowconvergence speed in solving the QoS multicast routing problem,basic ant colony algorithm pheromone updates and state transition rule is improved,and proposed QoS multicast routing scheme based onimproved ant colony algorithm,and the simulation results shows that improved ant colony algorithm is significantly better than the basic ant colony algorithm.Keywords ：ant colony algorithm ；multicast routing ；pheromone ；optimal path收稿日期：2017-01-12基金项目：国家自然科学基金资助项目（61174085）；河南省高等学校重点科研项目（16A520084）；河南省高等学校教学工程项目（豫教高2012[1099]号）；河南省高等学校教学工程项目（豫教高2012[1185]号）。

作者简介：魏勇（1982-），男，讲师，硕士，研究方向为云计算、计算机网络。

E-mail ：zhaokx_2008@ 。

随着网络的飞速发展，多媒体技术在互联网上的应用越来越广泛，如视频会议、远程教育、视频点播、交互式游戏等，这些应用对带宽、延时、丢包率、费用等较为敏感，需要QoS 的保证，在这种一对多的网络环境中，组播技术被广泛应用[1，2]。

组播路由的产生是实现组播的关键技术之一，组播路由是根据网络当前可用资源和网络业务对服务质量的要求，找出一棵连接源节点和所有目的节点的组播树，并且这棵组播树满足QoS 的约束条件，这已被证明是一个NP 问题，用常规的方法难以求解，蚁群算法是求解组合优化问题的一种新型智能优化算法，本文把改进的蚁群算法引入到组播网络中，来解决QoS 组播路由问题。

1QoS 网络和组播树模型组播可以在一个发送者和多个接收者之间实现点对多点的数据通信，并能将相同的数据分组有效地从源节点传输到多个目的节点。

在组第33卷第12期2017年12月科技通报BULLETIN OF SCIENCE AND TECHNOLOGYVol.33No.12Dec.2017第33卷科技通报播的网络中，源节点只需向网络发送一份数据分组，被传递的数据分组在必要的分叉路口才被开始复制和分发，从而增加了网络带宽的利用率，降低了发生网络拥塞的可能性，提高了数据分组传输效率和网络服务质量[3，4]。

网络模型用一个带权图G=(V,E)表示，其中V={v1,v2,…v i,…,v n}为图中所有网络设备和终端所组成的节点集合，E={e1,e2,…,e i,…,e c}为网络中节点间链路的集合，T(s,M)表示组播树，s为组播树的源节点，p(s,M)为源节点到目的节点的一条路径，其中s为源节点，M为目的节点，ei=<v i,v i+1>∈E，M∈{V-s}为该组播树的目的节点集[5]。

一条链路e具有延迟、费用和带宽三个属性，分别用函数delay(e)，cost(e)，bandwidth(e)来表示，一个节点具有延迟、费用和丢包率三个属性，分别用函数delay(v)，cost(v)，loss_rate(v)来表示，则源节点s∈V，目标节点t∈M所组成的组播树T(s,M)存在如下关系。

delay(p(s,t))=∑e∈p(s,t))delay(e)+∑v∈p(s,t))delay(v)（1）cos t(T(s,M)=∑e∈T(s,M)cos t(e)+∑v∈T(s,M)cos t(v)（2）bandwi th(p(s,t)=min{bandwi th(e),e∈p(s,t)}（3）loss_rate(p(s,t))=1-∏v∈p(s,t)(1-loss_rate(v))（4）公式中p(s,t)为组播树T(s,M)上源节点s到目标节点t的路由路径[6]。

所找到的QoS路由要满足如下条件：（1）delay(p(s,t))≤D（5）（2）loss_rate(T(s,M)≤PL（6）（3）bandwi th(p(s,t)≥B（7）其中公式中D，PL，B分别代表组播路由对网络延时、丢包率和带宽的限制。

2蚁群算法的改进蚁群算法作为一种新型的模拟进化算法，具有稳健性、正反馈、本质上的并行性、易于与其它算法相结合等特点，是解决多QoS约束组播路由问题的一种较好的启发式算法，但蚁群算法存在着时间复杂度大，容易出现停滞等缺陷，并且在资源搜索的过程中过分依赖信息素浓度，导致过早地生成最优路径，易得出局部最优解，因此基本蚁群算法难以直接应用到QoS的组播路由中[7]。

2.1信息素的更新策略改进通常在蚁群算法中，当所有蚂蚁完成一次搜索后，更新全局最优蚂蚁所在路径上的信息素，就可以保证搜索到的最优路径收敛于当前全局最优，但有可能会忽略迭代解中包含有全局最优解的情况，改进的算法采用迭代最优解与全局最优解混合更新策略，这样可以增强每次迭代搜索最优路径上信息素正反馈的能力，使全局最优解路径上的信息素浓度额外增加。

并且随着迭代数次的增加，在全局最优路径进行信息素更新时动态调整迭代。

全局最优路径和迭代最优路径经过的节点信息素的更新如公式（8）和公式（9）所示。

τij(t+1)=(1-ρ)τij(t)+Δτij(t)（8）Δτij(t)=(m k Ll+n k Lg)×1Nc（9）公式（9）中L l表示当前次迭代最优路径长度，L g表示目前得到的全局最优路径长度，m k与nk之和为Nc，用于调整迭代最优与当前全局最优蚂蚁在信息素更新时所占比重。

2.2蚂蚁状态的转移规则蚂蚁在进行下一节点选择时采用伪随机状态转移规则来确定蚂蚁的移动方向，比基本蚁群算法更好地利用蚂蚁正反馈机制。

位于节点i的蚂蚁根据公式（10）选择下一节点j，其中j为从公式（11）给出的概率分布选出的一个随机变量[8]。

j=ìíîargmaxφij(t)[]τij(t)α[]ηij(t)β,q≤q0j,q>q0（10）p kij(t)=ìíîïïïïταij(t)ηβij(t)∑s∈allowed kταis(t)ηβis(t),j∈allowed k0,j∈o th erwise（11）式（10）中q为（0,1）之间的一个随机数，蚂蚁采用最优转移方式来选择路径的概率为q0，这个移动方式是由信息素浓度和启发式信息决定的，当q≤q0时，由信息素浓度和启发信息共同决定下一个节点的选择，当q>q0时，由基本蚁群算法选择下一个待搜索的节点，引导算法趋向收敛。

q0的大小决定了算法对启发式信息的利用程度和新路径的探索程度。

由上述转移策略可以看出，q0的值决定着确184第12期定性转移和随机性转移被选择的概率。

为了合理搭配两种转移策略，可以在算法中动态调节q0的值：q0=ìíîïïε1q0多数蚂蚁搜索路径相同ε2q0q0≤q minϕ(t)其他（12）ϕ(t)=3.7n2max (n c-0.5n max)2+0.1（13）式中0<ε1<0.5,1<ε2<1.5,n c为迭代次数，n max为最大迭代次数；ϕ(t)为时变函数，其值域为[0.1,0.96]，变化趋势如图1所示。

图1ϕ(t)曲线图Fig.1ϕ(t)Curve graph算法初期，为了以大概率选择确定转移，q0取值较大，加快了局部最优路径的搜索；算法中期q0取较小的值，以增大随机转移概率，防止局部最优产生；算法后期进化方向已基本确定，逐步增大q0取值，以加快算法的收敛，改进的状态转移策略，加大了算法的随机性，扩大了搜索空间，避免了搜索的盲目性。

3基于改进蚁群算法的QoS组播路由算法具有n个节点的网络拓扑结构图中，通过最小带宽约束和改进的蚁群算法,来搜素从源节点到其它目的节点i的候选路由，算法步骤如下：步骤1：定义源节点s和目标节点集U={u1,u2,…,u n-1}，并在源节点处放置m只蚂蚁，设置循环计时器Nc为0，最大循环次数N max，设置网络中每条路径上的初始信息素初始值τ0初始化节点的路由信息表，给出每个节点和链路的QoS特征值以及约束条件。

步骤2：循环次数Nc=Nc+1。

步骤3：将源节点置于禁忌表中的每行中的第一列，行数为m。

步骤4：每只蚂蚁按照公式（10）和（11）根据禁忌表的变化选择节点前进，并根据基本蚁群算法更新局部最优信息素。

步骤5：当所有蚂蚁完成一次循环后根据公式（8）更新全局信息素，并计算路径的费用、延时、丢包率等，获得迭代最优组播树和全局最优组播树，并将全局最优组播树中各边信息素采用全局更新策略更新。