基于改进蚁群优化的组播路由算法研究

论文摘要

随着网络技术的飞速发展,网络通信带宽和处理能力的不断提高,各种宽带网络多媒体应用层出不穷,如视频点播、视频会议、网络电话、交互式游戏、远程教育、分布式多媒体数据库等,这些应用对带宽、延时、延时抖动、丢包率、费用等较为敏感,需要QoS(服务质量)的保证。当前Internet发展迅速,节点数成指数级增长,而且网络传输正在向大容量、高速化、多媒体化方向发展,传统的“尽力而为”的服务已经不能满足这些新兴业务提出的要求。组播是一种有效的支持多点通信的机制,可以将同一信息从源节点传送到网络中多个目的节点(不一定是网络中所有结点)。由于组播树中路由器的复制和转发,相对于单播传输方式,组播发送数据流到一组目的节点源节点只需产生发送一份数据流,因而组播技术具有缓解网络传输瓶颈和减轻主机处理压力的特点,有效提高传输效率,得到了广泛的应用。组播问题的关键是确定组播路由,QoS组播路由就是寻找一棵满足特定QoS约束的组播树,这已被证明是一个NP完全问题,用常规的方法难以求解,因而需要应用到启发式算法。蚁群算法作为一种新型的模拟进化算法,具有稳健性、正反馈、本质上的并行性、易于与其他算法相结合等特点,是解决多QoS约束组播路由问题的一种较好的启发式算法。本文首先列举了现有的组播路由协议及算法的分类,分析了几种经典QoS路由算法,提出组播路由研究中仍存在的问题。接着介绍了蚁群算法的基本原理和算法的数学模型,通过对Oliver30城市的TSP问题实验分析了蚁群算法中各参数对算法性能的影响。针对蚁群算法收敛速度慢和容易局部收敛的问题,对蚁群算法进行了优化,提出参数按算法迭代结果自适应调整；修改基本蚁群算法中信息素的更新规则,使得每轮搜索后信息素的增量能更好地反映解的质量以加快收敛；对所选的下一节点进行判定,防止源节点到目的节点子图中形成环路；考虑到蚁群种类差异和行为差异,引入具有多行为的混合蚂蚁来扩大解搜索空间等改进策略。最后将改进蚁群算法应用于QoS组播路由问题,并对其进行仿真实验,结果表明算法的可行性和有效性。

论文目录

• 摘要
• Abstract
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 选题背景及意义
• 1.2 QoS组播路由研究现状
• 1.3 研究目的和意义
• 1.4 论文研究内容和组织结构
• 第2章 QoS组播路由技术
• 2.1 组播路由的基本概念
• 2.2 组播路由协议
• 2.3 组播路由算法
• 2.4 QoS组播路由概述
• 2.4.1 QoS的定义
• 2.4.2 QoS的主要参数
• 2.4.3 QoS组播路由算法
• 2.5 小结
• 第3章 蚁群算法
• 3.1 蚁群算法原理
• 3.2 蚁群算法模型
• 3.3 蚁群算法的参数对蚁群算法性能的影响
• 3.3.1 信息素强度对蚁群算法性能的影响
• 3.3.2 启发式因子对蚁群算法性能的影响
• 3.3.3 信息素挥发系数对蚁群算法性能的影响
• 3.4 蚁群算法的特点
• 3.5 小结
• 第4章 基于改进蚁群算法的QoS组播路由选择
• 4.1 QoS组播路由问题的建模
• 4.2 算法的改进
• 4.2.1 参数动态自适应调整
• 4.2.2 信息素更新规则
• 4.2.3 蚁群混合行为
• 4.2.4 删除到达目的节点路径间的环路
• 4.3 算法的实现步骤
• 4.4 算法仿真实验
• 4.5 小结
• 第5章 仿真实验和分析
• 5.1 随机网络拓扑生成
• 5.2 算法仿真结果分析
• 5.2.1 收敛性能分析
• 5.2.2 网络代价性能分析
• 5.3 小结
• 结论
• 参考文献
• 附录A （攻读硕士期间参加的项目）
• 致谢