基于蚂蚁优化的QoS约束分布式多播路由算法研究与实现

论文摘要

随着因特网通信业务量的不断膨胀,如何有效地在QoS约束下寻找具有最小网络费用的多播路由树成为研究的热点。论文主要研究基于蚂蚁优化算法的具有QoS约束的分布式多播路由算法问题,解决了已有算法在多播规模增大时路由选择时间长,全局优化性能差,容易产生回路的问题。论文在研究分布式网络、QoS约束,多播路由的基础上,建立了分布式QoS多播路由的数学模型,包括网络模型、QoS度量及特征和多播路由模型。发现已有算法当多播规模增大时,蚂蚁死亡率较高,容易产生回路。提出了一种带回路检测的分布式度约束算法,首先建立初始多播路由树,多播路由树的寻找和建立可以在同时完成;提出一种改进的蚂蚁优化算法,定义两种类型的蚂蚁代理:向前蚂蚁和向后蚂蚁,两种蚂蚁互相协作,共同发现满足带宽和延迟约束的最小代价路径,蚂蚁一边前进一边对已经建立的初始多播路由树进行优化,充分利用了分布节点的局部信息,能够降低蚂蚁死亡率,改善解的质量,降低了产生回路的可能。论文改进了算法收敛规则,通过信息素强度变参数控制,残留信息素数量限幅控制和挥发系数动态自适应调节,增加了算法收敛速度,提高了算法的全局收敛性。通过与BSMA和KMB算法进行网络规模影响,多播规模与时延限制影响等仿真实验结果比较分析,表明本算法适应大规模的网络和多播要求,路由选择时间较短,全局优化能力较好和收敛时间适当。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.2.1 国内外研究现状
• 1.2.2 QoS多播路由算法存在着的问题与不足
• 1.3 本文的工作与组织结构
• 第二章 相关理论和技术
• 2.1 QoS约束的多播路由
• 2.1.1 QoS约束
• 2.1.2 QoS多播路由概念
• 2.1.3 QoS多播路由分类
• 2.1.4 QoS多播路由研究的主要难点
• 2.2 蚂蚁优化算法
• 2.2.1 蚂蚁算法概述
• 2.2.2 传统蚂蚁算法的优点
• 2.2.3 传统蚂蚁算法求解QoS多播路由
• 2.2.4 传统蚂蚁算法的不足
• 2.3 本章小结
• 第三章 DQMRACO算法的设计
• 3.1 数学模型
• 3.1.1 网络模型
• 3.1.2 QoS度量及特征
• 3.1.3 分布式多播路由模型
• 3.2 分布式QoS多播路由算法
• 3.2.1 蚂蚁代理定义
• 3.2.2 算法的原理
• 3.2.3 算法的步骤
• 3.2.4 算法的改进
• 3.3 收敛规则与蚂蚁数
• 3.3.1 收敛规则
• 3.3.2 蚂蚁数的计算
• 3.4 本章小结
• 第四章 DQMRACO算法的分析
• 4.1 DQMRACO算法规则分析
• 4.1.1 路径选择
• 4.1.2 局部更新
• 4.1.3 全局更新
• 4.2 DQMRACO算法性能分析
• 4.2.1 算法正确性证明和复杂性分析
• 4.2.2 回路检测算法性能分析
• 4.2.3 算法收敛性分析
• 4.3 本章小结
• 第五章 仿真实验与结果分析
• 5.1 仿真实验环境的建立
• 5.2 仿真实验
• 5.2.1 改进收敛规则实验
• 5.2.2 超边替换实验
• 5.2.3 网络规模影响实验
• 5.2.4 多播规模与时延限制影响实验
• 5.3 实验结果分析
• 5.4 本章小结
• 第六章 总结和展望
• 6.1 论文总结
• 6.2 进一步的研究方向
• 参考文献
• 致谢
• 攻读学位期间主要的研究成果