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

论文摘要

在计算机网络中,多播是指从源节点将同一份信息传送到多个目的节点的技术。多播路由是网络层具备的功能,多播问题的关键在于多播路径的确定。实现多播的一般方式是建立多播树,多播树是根为源节点,且覆盖所有多播成员的一棵生成树。多播树的优点在于,首先信息以并行方式发送到不同的多播成员,从而降低了信息传递的时延;其次信息的复制只在树杈上进行,能够节省网络带宽资源,减少拥塞。多播路由算法主要用来建立一棵性能好的多播树,并使得它满足各种业务的服务质量需求。目前,多播路由算法的研究大多都针对无约束多播路由问题和时延受限多播路由问题,多采用启发式等方法。本论文研究如何将遗传算法这一新型优化算法应用到多约束QoS多播路由算法中,利用该算法的并行搜索、种群优化的特点,为解决QOS多播路由问题寻找新的途径。首先,对计算机网络的多播通信进行了综述。主要介绍多播的概念、分类、基本特点与应用;研究了多播技术及应用、多播路由技术、多播路由协议,还介绍了OoS的基本概念。其次,研究QoS多播路由问题。主要介绍了QoS多播路由的基本概念、描述参数、网络模型、优化准则和多播协议;分析了多播路由算法的研究现状;研究了几个实用的多播路由算法,给出其执行过程。再次,介绍遗传算法的基本思想、特点和应用;详细分析了遗传算法的基本要素、遗传算法存在的问题;分析了遗传算法求解多播路由问题的现状及发展趋势,对遗传算法的改进方法进行总结。最后根据Qos多播路由的特点,结合遗传算法的寻优特性,提出了一种改进的Dijkstra算法和一种基于改进遗传算法的多约束QoS多播路由算法,并对改进的多播路由算法进行了收敛性分析和仿真验证。与相关算法进行多次比较实验证明,算法对解决多约束QoS多播路由选择优化问题有一定改进,尤其在网络规模较大的情况下,搜索速度较快。本文提出的算法是可行的、有效的。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 多播技术
• 1.1.1 多播的基本概念
• 1.1.2 多播树的分类
• 1.1.3 多播技术的基本特点与应用
• 1.2 多播路由技术
• 1.2.1 多播路由产生背景
• 1.2.2 多播路由协议的基本类型
• 1.2.3 多播路由协议介绍
• 1.3 QoS的基本概念
• 1.3.1 赋权图模型
• 1.3.2 状态信息
• 1.3.3 QoS的度量
• 1.3.4 QoS设计的基本原则
• 1.3.5 QoS的研究范围
• 1.4 遗传算法求解QoS多播路由的研究现状及发展趋势
• 1.4.1 国内外研究历史及现状
• 1.4.2 发展趋势
• 1.5 本文的主要工作
• 第2章 QoS多播路由算法研究
• 2.1 QoS约束多播路由的概念
• 2.1.1 QoS的描述
• 2.1.2 QoS的保证策略
• 2.2 QoS多播网络模型
• 2.2.1 多播路由算法的数学模型
• 2.2.2 QoS多播路由问题的网络模型
• 2.3 多播树的优化准则
• 2.4 QoS多播路由算法研究现状
• 2.5 实用多播路由算法
• 2.5.1 最短路径树算法
• 2.5.2 最小生成树及Prim算法
• 2.5.3 Steiner树问题及KMB、MPH算法
• 2.5.4 受约束的Steiner树问题
• 2.6 本章小结
• 第3章 遗传算法
• 3.1 遗传算法的基本思想
• 3.2 遗传算法的特点与应用
• 3.2.1 遗传算法的特点
• 3.2.2 遗传算法的应用
• 3.3 标准遗传算法的基本要素
• 3.3.1 编码策略
• 3.3.2 种群初始化
• 3.3.3 适应度函数
• 3.3.4 选择算子
• 3.3.5 交叉算子
• 3.3.6 变异算子
• 3.3.7 控制参数
• 3.4 遗传算法的改进方法
• 3.5 本章小结
• 第4章 遗传算法在QoS多播路由问题中的应用
• 4.1 一种改进的Dijkstra算法
• 4.2 一种基于遗传算法的多约束QoS多播路由算法
• 4.2.1 多播路由问题的编码
• 4.2.2 种群的初始化
• 4.2.3 适应度函数
• 4.2.4 选择操作
• 4.2.5 交叉操作
• 4.2.6 变异操作
• 4.2.7 维护操作
• 4.3 算法分析和仿真实验
• 4.3.1 收敛性分析
• 4.3.2 时间复杂度分析
• 4.3.3 仿真研究
• 4.4 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的论文和取得的科研成果
• 致谢
• 个人简历