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

论文摘要

随着Internet的发展,涌现了许多新型的通信需求,如视频点播、多媒体会议、远程教学等,这类应用促使了多播通信的发展。多播是将同一信息从源节点传送到网络中多个目的节点。多播问题的关键在于多播路径的确定。通常实现多播的方式是建立多播树,多播树是以根为源节点,且覆盖所有多播成员的一棵生成树。因此,多播路由算法主要是用来建立一棵性能良好的多播树,并使得它满足各种业务的服务质量(QoS: Quality of Service)需求。QoS多播路由问题的求解方法包括启发式算法和遗传算法,本文主要研究了遗传算法在多播路由问题中的应用。遗传算法是一种全局随机优化算法,它具有并行搜索、群体寻优的特点,已广泛运用于解决各种具有NP难度的问题。因此,遗传算法为QoS多播路由问题的求解提供了新的途径。针对时延受限多播路由问题,本文设计了一种模拟退火遗传算法,将模拟退火算法的思想引入到遗传算法中,提高了算法的全局收敛能力和收敛速度。算法采用基于路径的编码方式,简化了遗传算子的操作过程,并对可能出现的环路问题进行分析解决。仿真试验表明,该算法能够以较少的遗传代数获得满足时延约束的代价较低的多播树,具有较好的代价性能和时间性能,能够满足实际应用的要求。对于求解含有多个QoS参数的QoS多播路由问题,本文首先分析了单目标路由优化算法的不足,这类算法通常是将多个QoS约束组合成一个单目标标量函数进行求解,以致进化结果对权重敏感且为单一解。本文在上述分析的基础上提出了一种多目标优化的遗传算法,该算法同样采用基于路径的编码方式,通过运用Pareto优于关系来同时优化多个QoS参数,产生一组有效的非劣多播树解,由此克服了单目标路由优化的缺陷。在进化过程中,该算法引入了小生境的思想,以保持多目标遗传算法的群体多样性,防止算法由于过高的选择压力导致早熟收敛以及群体缺乏多样性而使进化结果收敛至单个解。最后通过仿真实验证明了算法的有效性。

论文目录

• 第一章 绪论
• 1.1 引言
• 1.2 多播路由技术的发展背景
• 1.3 多播路由算法研究现状
• 1.3.1 Steiner 树算法和CBT 算法
• 1.3.2 静态路由算法和动态路由算法
• 1.3.3 集中式算法和分布式算法
• 1.3.4 分层多播路由算法
• 1.3.5 QoS 多播路由算法
• 1.4 本文的主要研究工作
• 1.5 论文的组织
• 第二章 QOS 多播路由问题
• 2.1 QOS 多播路由的基本概念
• 2.1.1 赋权图模型
• 2.1.2 状态信息
• 2.1.3 QoS 的度量
• 2.2 QOS 多播路由的数学模型
• 2.3 QOS 多播路由问题分类
• 2.3.1 最小生成树
• 2.3.2 最短路径树
• 2.3.3 Steiner 树
• 2.3.4 受约束的 Steiner 树
• 2.4 QOS 多播路由算法发展现状
• 第三章 遗传算法
• 3.1 遗传算法的基本原理
• 3.1.1 遗传算法的目的
• 3.1.2 遗传算法的基本原理
• 3.2 遗传算法的基本步骤
• 3.2.1 初始化群体
• 3.2.2 终止循环的条件
• 3.2.3 选择
• 3.2.4 交叉
• 3.2.5 变异
• 3.3 遗传算法的特点与应用关键
• 3.3.1 遗传算法的特点
• 3.3.2 遗传算法的应用关键
• 3.4 遗传算法求解多播路由的研究现状及发展趋势
• 3.4.1 遗传算法求解QoS 多播路由问题的难点
• 3.4.2 国内外研究历史及现状
• 3.4.3 发展趋势
• 第四章 基于模拟退火遗传算法的时延受限多播路由优化
• 4.1 引言
• 4.2 时延受限多播路由问题的数学描述
• 4.3 相关算法介绍
• 4.4 模拟退火遗传算法的设计
• 4.4.1 模拟退火算法概述
• 4.4.2 模拟退火遗传算法主要思想
• 4.4.3 算法流程
• 4.5 算法描述
• 4.5.1 编码
• 4.5.2 适应度函数
• 4.5.3 选择算子
• 4.5.4 交叉算子
• 4.5.5 变异算子
• 4.5.6 修复函数
• 4.5.7 算法终止准则
• 4.6 算法性能分析
• 4.7 仿真实验结果和分析
• 4.8 小结
• 第五章 基于多目标遗传算法的QOS 多播路由优化
• 5.1 引言
• 5.2 QOS 多播路由问题的数学描述
• 5.3 多目标优化问题
• 5.4 小生境简介
• 5.4.1 小生境与遗传算法
• 5.4.2 遗传算法中小生境的实现方法
• 5.5 基于多目标遗传算法的多播路由优化
• 5.5.1 算法主要思想
• 5.5.2 算法流程
• 5.6 算法描述
• 5.6.1 编码
• 5.6.2 适应度函数
• 5.6.3 选择策略
• 5.6.4 交叉算子
• 5.6.5 变异算子
• 5.6.6 算法终止准则
• 5.7 算法性能分析
• 5.8 实验仿真结果和分析
• 5.9 小结
• 结束语
• 1. 本文的主要贡献
• 2. 对未来工作的展望
• 参考文献
• 致谢
• 个人简历、在校期间的研究成果及发表的学术论文