基于服务质量的组播路由算法研究

论文摘要

随着网络技术的发展及其应用领域的不断扩大,当前的网络能支持越来越多的实时多媒体应用,为了支持这些多媒体应用,组播通信网络也正在逐渐广泛应用。同时,许多多媒体业务对时延、时延抖动、带宽以及网络代价等也提出了越来越高的要求,需要当前的网络具有QoS(服务质量)支持能力。时延与代价是组播研究中一对非常重要又相互矛盾的QoS参数,追求到每个目的节点的最小时延不利于优化组播路由树的总体代价,而优化组播树总的代价又很难满足每个目的节点到源都有满足时延约束的路径。个好的组播算法通常要在组播树的总体代价与信息源到各目的节点时延之间做出权衡。论文针对受时延约束组播路由问题设计了三种简单、快速、易于实现且满足用户QoS需求的组播路由算法。论文首先分析了受时延约束的组播路由问题及相关算法,基于网络模型提出了一种受时延约束的组播路由算法DCMRA,该算法每次将到达组播树的代价较小,且满足端到端时延约束的成员节点及其相应路径加入到组播树,直到所有的成员加入到组播树上为止。在寻找路径的过程中使用了新提出的NDUR算法,该算法在保证满足时延约束的同时尽量减小对最小代价路径的破坏,达到了优化代价的目的。然后将禁忌搜索算法引入到组播路由问题中来,利用该方法灵活、简单、搜索能力强的特点,提出了一种基于中继节点变换的禁忌搜索算法TSNSMRA来解决时延约束组播路由问题。本算法提出了节点重要度的概念,使得通过变换中继节点得到的邻域解集规模适中同时质量较高,进行迭代后可以得到高质量的解。最后,由于在实际组播应用中,通常面临着组播成员的动态变化的问题,论文借鉴了贪婪算法的思想,提出一个基于K条最短路径算法的时延约束动态组播路由算法DDMP。算法为申请加入的节点寻找一条满足时延约束,同时使当前树新增代价较小的路径。算法中共享费用的提出,给予了包含树上节点的路径一定的优先权,这样可以在保证时延的条件下实现更多链路的共享,优化组播树的代价。

论文目录

• 中文摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究的背景及意义
• 1.2 组播路由技术介绍
• 1.2.1 网络数据传输方式
• 1.2.2 组播路由的基本概念
• 1.3 组播路由技术的发展现状
• 1.4 论文研究内容和组织结构
• 1.4.1 论文研究内容
• 1.4.2 论文的组织结构
• 第二章 QoS组播路由研究基础
• 2.1 概述
• 2.2 服务质量的定义及其约束
• 2.2.1 服务质量的定义
• 2.2.2 组播路由问题的QoS约束
• 2.3 QoS组播路由的网络模型
• 2.4 现有组播路由算法
• 2.4.1 组播路由算法的分类
• 2.4.2 组播路由典型算法
• 2.5 QoS约束组播路由算法研究难点和几个亟待解决的问题
• 2.5.1 QoS路由中研究的主要难点
• 2.5.2 QOS组播路由算法研究中几个亟待解决的问题
• 2.6 NP问题介绍
• 2.7 本章小结
• 第三章 一种时延约束组播路由算法
• 3.1 时延约束组播路由问题描述
• 3.2 相关算法介绍
• 3.3 时延约束组播路由算法DCMRA
• 3.3.1 算法基本思想
• 3.3.2 DCMRA算法实现需要解决的问题
• 3.3.3 DCMRA算法的具体描述
• 3.4 算法分析
• 3.4.1 算法正确性分析
• 3.4.2 算法复杂度分析
• 3.5 仿真实验及结果
• 3.6 本章小结
• 第四章 基于禁忌搜索的时延约束组播路由算法
• 4.1 禁忌搜索算法
• 4.2 已有的基于禁忌搜索算法解决组播路由问题的算法
• 4.3 中继节点变换的禁忌搜索算法
• 4.3.1 算法的基本思想
• 4.3.2 初始解的生成
• 4.3.3 邻域解集的生成
• 4.3.4 候选节点的选取
• 4.3.5 参数K的确定
• 4.3.6 禁忌表与禁忌长度
• 4.3.7 解禁准则
• 4.3.8 终止规则
• 4.4 算法伪代码
• 4.5 算法分析
• 4.6 仿真实验及结果
• 4.7 本章小结
• 第五章 有时延约束的动态组播路由算法
• 5.1 动态组播路由算法的分类
• 5.1.1 不重组的动态组播路由算法
• 5.1.2 重组的动态组播路由算法
• 5.2 已有的动态组播路由算法
• 5.3 有时延约束的动态最小代价组播路由问题
• 5.4 时延约束动态组播路由算法DDMP
• 5.4.1 算法基本思想
• 5.4.2 算法中用到的几个概念
• 5.4.3 算法过程描述
• 5.5 算法分析
• 5.5.1 算法正确性分析
• 5.5.2 算法复杂度分析
• 5.6 本章小结
• 第六章 结束语
• 6.1 论文的主要工作
• 6.2 论文的不足和未来的研究方向
• 参考文献
• 致谢