随着网络技术的飞速发展,当前通信网络带宽和处理能力的提高使网络能够提供更多的多媒体业务,也使得支持“点到多点”或“多点到多点”的组播通信方式成为网络支持多媒体业务的必要形式。组播路由是网络层具备的功能,组播问题的关键在于组播路由的确定,寻找简单、高效、健壮的组播路由算法一直是网络界致力研究但未完全解决的问题。另一方面,许多分布式的多媒体应用对时延、时延抖动、带宽以及包丢失率有不同的要求,这需要当前网络能够传送具有这些QoS要求的实时多媒体信息。因此,作为QoS为中心的网络体系结构中不可缺少的组成部分,基于IP网络的QoS约束组播路由算法的研究成为网络研究领域的重要内容和热点问题。 本文系统的研究了IP QoS的体系结构、典型服务模型和机制,并对相关的关键技术进行了介绍;阐述了IP QoS组播路由原理;并将现有QoS约束组播路由算法的研究成果进行了归纳、分类,其中详细分析了IP QoS约束的Steiner树算法;重点介绍了时延约束最小代价组播路由问题及其相关算法。 本文工作重心在于:分析总结了传统遗传算法、禁忌搜索算法和模拟退火算法各自的优缺点,并在此基础上结合禁忌搜索算法和模拟退火算法各自的优点,提出了一种改进的混合遗传算法TSSAGMA。该算法的适应度函数采用模拟退火算法的思想来确保在后期快速收敛,同时引入禁忌搜索算法的交叉和变异算子,来防止算法早熟。通过仿真实验表明,TSSAGMA混合遗传算法在解决时延约束最小代价组播路由的问题上优于传统算法,能够在较小的代价下搜索到较好的解。另外,本文还引入了边交换和路径交换的概念,提出了两种改进模拟退火算法:基于边交换的退火组播路由算法(SAESMA)和基于路径交换的退火组播路由算法(SAPSMA),并分别对它们的时间复杂度进行了证明。