基于遗传算法的QoS多组播路由问题研究

论文摘要

随着Internet的发展,涌现出了许多新的通信需求,如视频点播、多媒体会议、远程教学等,这类应用促进了多组播通信的发展。多组播路由问题是在一个给定的通信网络中找到一个总代价最小且满足带宽-时延约束的多个源点到多个目的点的路由集合。这是一个比单个源点到多个目的点的组播路由问题更加复杂的问题,是一个NP-hard问题。QoS多组播路由问题的求解方法主要包括启发式算法和遗传算法,本文主要研究了遗传算法在多组播路由问题中的应用。遗传算法是一种全局随机优化算法,它具有并行搜索,全局寻优的特点,已广泛应用于解决各种具有NP难度的问题。因此遗传算法为QoS多组播路由问题的求解提供了新的解决途径。本文应用遗传算法的基本思想,将求解问题分解成两个目标,一个是求解满足时延约束组播树的多个优秀解,另一个是求解满足带宽约束和时延约束组播树的最优组合,提出一种求解满足带宽-时延约束多组播路径问题的两层遗传算法。在算法中设计了一种基于节点连接路径的具有树状结构的染色体表示方法及可以实现树状染色体交叉和变异的算子。数值实验结果表明,文中提出的算法可以有效找到多组播路由问题的优化解。

论文目录

• 摘要
• Abstract
• 1. 绪论
• 1.1 问题的提出
• 1.2 国内外研究现状
• 1.3 课题的意义
• 1.4 本文研究内容
• 1.5 本章小结
• 2 QoS组播路由问题
• 2.1 QoS组播通信
• 2.2 组播通信的工作原理
• 2.3 组播路由
• 2.3.1 组播路由协议的分类
• 2.3.2 组播路由协议
• 2.4 组播路由算法的分类
• 2.5 QoS组播的关键指标
• 2.6 本章小结
• 3. 多组播路由问题的遗传算法
• 3.1 遗传算法简介
• 3.1.1 遗传算法的运算流程
• 3.1.2 遗传算法的特点
• 3.2 基于遗传算法的QoS多组播路由问题
• 3.2.1 问题描述
• 3.2.2 染色体编码
• 3.2.3 求解最优组播树的遗传算法模块
• 3.2.4 求组播树最优组合的遗传算法模块
• 3.3 本章小结
• 4 仿真实验
• 4.1 QoS多组播路由问题的遗传算法有效性验证
• 4.2 本章小结
• 5 结束语
• 致谢
• 参考文献
• 研究生期间发表的论文