多QoS约束的组播路由优化算法研究

摘要

进入21世纪以来，计算机网络技术得到了更快的发展，这些发展源自于许多新的通信需求的涌现，特别是远程教学、视频会议、IPTV、网络游戏等。这些应用对现有网络的承载能力提出了更高，更迫切的要求，进一步迫使计算机网络在支持多媒体业务时，必须使用更好的组播通信方式。深入研究发现，这些多媒体应用对时延、带宽、代价、丢包率等，即QoS，有不同的需求。现有的计算机网络并不能够完全满足传输带有QoS指标的实时多媒体信息的需要，所以多约束QoS组播路由算法已经成为计算机网络研究领域的热点问题之一。
　　 本研究针对多约束QoS组播路由算法的现状进行了考察。以此为基础针对QoS中的时延、带宽和丢包率等指标的最小代价问题，进行了研究，进而提出了一种高效的组播路由优化算法。主要内容包括：⑴对组播路由技术的相关背景进行考查，简单介绍了国内外现状，熟悉了QoS路由的基本概念和网络模型，指出目前已有算法的优缺点，为本研究找到了方向；⑵提出了一种将遗传算法与蚁群算法相融合的混合优化算法(GAACA，thecombination of Genetic Algorithm and Ant Colony Algorithm)。该算法首先利用遗传算法生成若干组优化解，然后转换为蚁群算法里的信息素初值，以便利用蚁群算法编制程序得到满足一定QoS约束条件的最优解。为了确保遗传算法和蚁群算法在适当时机能够融合，这里设置了一个遗传算法控制函数。该算法既克服了遗传算法和蚁群算法的缺点，又保留了它们各自的优点；⑶为了有效使用Salama随机网络拓扑生成算法，对其进行研究并提出了新的改进算法。对改进后算法使用MATLAB进行了仿真，并与传统算法就收敛性和迭代次数进行比较。MATLAB运行结果说明了算法的可行性和有效性，说明了算法能够针对目前的网络需求做到代价低且快速收敛。

目录

文摘

英文文摘

1 绪论

1.1 课题研究的目的和意义

1.2 国内外研究现状

1.3 本文的研究内容

1.4 本文的组织结构

2 组播路由技术

2.1 组播的工作原理

2.2 组播通信的方式

2.3 组播路由协议

2.3.1 密集模式路由协议

2.3.2 稀疏模式组播路由协议

2.4 组播路由算法分类

2.5 组播路由典型算法

3 QoS组播路由模型

3.1 QoS概述

3.2 QoS路由

3.3 QoS组播路由问题的数学模型

3.4 QoS约束组播路由算法的设计理论

3.4.1 算法设计的复杂性分析

3.4.2 QoS约束组播路由算法的设计原则

3.4.3 QoS约束组播路由算法性能指标

4 遗传算法与蚁群算法

4.1 遗传算法

4.1.1 遗传算法的基本概念

4.1.2 遗传算法的基本流程

4.1.3 遗传算法的特点及其应用

4.2 蚁群算法

4.2.1 蚁群算法的原理

4.2.2 蚁群算法的发展

4.2.3 蚁群算法的优点与不足

5 基于遗传算法与蚁群算法融合的QoS组播路由算法

5.1 算法背景

5.2 GAACA算法设计思想及总体框架

5.3 遗传算法部分

5.3.1 染色体编码

5.3.2 种群初始化

5.3.3 适应值函数

5.3.4 选择算子

5.3.5 交叉算子

5.3.6 变异算子

5.3.7 遗传算法结束条件

5.4 遗传算法与蚁群算法相融合部分

5.4.1 算法融合时机的设置

5.4.2 蚁群算法信息素初值的设置

5.5 蚁群算法部分

5.5.1 路径选择规则

5.5.2 信息素强度调整规则

5.5.3 蚁群算法部分结束条件

5.6 GAACA算法的描述

5.7 仿真实验及分析

5.7.1 开发工具的选择

5.7.2 改进的网络拓扑随机生成算法设计

5.7.3 仿真实验参数

5.7.4 算法收敛性能分析

5.7.5 算法代价的性能分析

6 结论

6.1 研究成果

6.2 未来的工作

参考文献

攻读硕士学位期间发表的论文

致谢