蚁群算法和遗传算法在QoS组播路由上的应用及比较研究

摘要

随着Internet和多媒体业务的飞速发展，传统IP网络所采用的“尽力而为”的转发机制，已经不能满足用户的要求。没有提供QOS保证则是影响IP网络向综合网络发展的主要因素。 QoS组播路由是下一代网络中实现QOS服务的关键技术之一。QoS路由的主要优点是能为接入的业务选择满足服务质量要求的传输路径，同时保证整个网络资源的有效利用。 然而，寻找具有两个独立路径约束的一条单播路由或一棵组播树属于NP完全问题。本文介绍了有关QOS路由的一些基本原理以及国内外对QoS路由问题的研究现状，简单地介绍了遗传算法及其在QoS组播路由问题中的应用，然后主要探讨了蚁群算法在多约束的QOS组播路由选择中的应用问题，对蚁群算法的信息素控制和发送蚂蚁数量的机制作了一些改进。 最后对两种启发式算法作了简单比较。在此基础上，将融合蚁群算法和遗传算法的想法[1]应用到QOS组播路由问题中，即将遗传算法中解空间的交叉操作应用到蚁群算法中，同时加入蚂蚁数量控制，从而使新的蚁群算法能在QoS组播路由问题中既能更快的收敛，又更趋向于得到最优解。 仿真结果表明，融合了交叉因子的蚁群算法性能优于原蚁群算法，而蚂蚁数量控制机制能进一步优化蚁群算法及其改进算法。

目录

文摘

英文文摘

声明

引言

第一章 QOS问题

1.1QoS的概念和需求

1.2QoS问题的由来和发展

1.3QoS的定义

1.4QoS体系结构

第二章 QoS组播路由问题及其路由算法

2.1IP组播技术

2.1.1组播技术发展的背景

2.2QoS路由

2.2.1QoS度量特性

2.2.2加权图模型

2.2.3状态信息

2.2.4QoS路由的基本问题

2.2.5QoS路由策略

2.3QoS组播路由

2.3.1QoS组播路由问题

2.3.2组播路由算法的分类

2.3.3源路由策略下的QoS组播路由算法

2.3.4分布式策略下的QoS组播路由算法

2.3.5NP完全问题

第三章 遗传算法及其在QoS组播问题中的应用

3.1遗传算法的产生和发展

3.2遗传算法的基本思想

3.3遗传算法的主要步骤

3.4遗传算法的基本操作

3.5遗传算法参数的选择

3.6遗传算法的性能评估指标

3.7遗传算法在QoS组播路由问题中的应用

3.8遗传算法的特点及存在的问题

第四章 基于ACS的QoS组播路由算法的改进

4.1蚂蚁算法的基本原理

4.2蚂蚁算法的发展

4.3蚁群算法在QoS组播路由优化问题上的应用

4.3.1QoS动态组播路由问题

4.3.2基于ACS的QoS动态组播路由算法

4.4算法复杂度分析

4.4.1ACS算法复杂度分析

4.4.2信息素更新机制优化ACS算法及复杂度分析

4.4.3每组蚂蚁数量渐减机制优化ACS算法及复杂度分析

4.5仿真平台简介

4.6蚁群算法的仿真设计

4.6.1包格式(蚂蚁)的设计

4.6.2链路设计

4.6.3节点模型和进程模型的设计

4.6.4各个节点种算法的实现

4.7改进的ACS仿真设计

4.7.1基于信息素渐进增加的ACS仿真设计

4.7.2基于每组蚂蚁数渐减的ACS仿真设计

4.8ACS及其改进算法仿真结果分析

4.8.1原ACS算法的仿真

4.8.2信息素更新机制优化的ACS算法的仿真

4.8.3每组蚂蚁数量渐减机制优化的ACS算法的仿真

4.8.4仿真结果分析

4.9小结

第五章 遗传算法与蚁群算法的对比和融合

5.1遗传算法和蚁群算法的简单对比

5.2遗传算法和蚁群算法的融合及其复杂度分析

5.2.1算法的融合

5.2.2加入交叉操作和蚂蚁数控制的蚁群算法复杂度分析

5.2.3算法的仿真及其分析

结束语

致谢

参考文献

作者攻读学位期间已完成的学术论文