基于QoS约束的组播路由算法研究

摘要

通信网络的快速发展要求当前网络既能传送常规的尽力传输服务，也能传送有一定QoS要求的实时多媒体业务，使得QoS组播路由技术成为网络多媒体信息传输的关键技术之一。QoS组播路由算法主要是用来建立一棵性能良好的组播树，并使它能够满足各种业务的服务质量需求。QoS组播路由带有多个QoS约束参数，这种约束条件下的QoS组播路由问题属于NP完全问题。许多用启发式算法、遗传算法(GA)、蚂蚁算法和模拟退火算法(SA)等求解带QoS组播路由问题的方法相继提出，由于这些算法都具有较高的时间复杂度或存在未成熟收敛和搜索能力差等明显的缺点而不能满足实际应用的需求。 针对现有算法中的不足，提出基于遗传模拟退火算法的QoS组播路由选择方法，将遗传算法与模拟退火算法融合，使GA并行处理、快速度收敛的优点和SA跳出局部最优的能力得以共同保存，提高了算法的效率。采用树型编码节省了编码空间和解空间的转换所需时间。采用嫁接式种群初始化方法，使各初始染色体都是无环路的合理组播树。设计了交叉算子和模拟退火式变异算子，使用自适应的交叉概率有效加快了进化速度。 提出了基于路由重组的QoS动态组播路由方法。包括组播成员从组播树中动态删除及新的组播成员加入的处理。设计了路由重组方法，计算累计损伤并对累计损伤的权值动态调整控制重组规模，使路由重组对其它组播成员通信的影响在可接受范围内，达到树的优化和计算时间、复杂性之间的平衡。 对Salama网络拓扑随机生成算法进行了研究，利用K均值聚类改进网络拓扑随机生成方法。以此算法生成不同规模的随机网络拓扑进行仿真实验，分别对上述QoS组播路由算法进行收敛性能及费用性能进行仿真分析。路由请求成功率对比曲线和费用曲线显示了各算法的收敛性能和不同网络规模下的费用性能。算法能够满足多媒体网络对相应QoS的要求并有较好的性能表现。

目录

文摘

英文文摘

声明

1 绪论

1.1 QoS组播路由研究背景

1.2国内外研究现状

1.3论文研究内容及组织结构

2 QoS组播路由理论基础

2.1 QoS组播路由技术介绍

2.2组播路由算法

2.3 QoS组播路由网络模型

2.4 QoS组播路由仿真环境

2.5本章小结

3基于遗传模拟退火算法的QoS组播路由方法

3.1遗传模拟退火算法简介

3.2编码及适应度函数

3.3嫁接式种群初始化方法

3.4 遗传模拟退火算法的算子设计

3.5算法终止准则及整体描述

3.6仿真实验及分析

3.7本章小结

4基于路由重组的动态QoS组播路由算法

4.1动态组播路由算法简介

4.2组播成员动态变化的处理

4.3算法终止准则及整体描述

4.4仿真实验及性能分析

4.5本章小结

5结论与展望

5.1 结论

5.2展望

参考文献

附录A算法部分程序伪代码

攻读硕士学位期间发表学术论文情况

致 谢