学位论文 > 优秀研究生学位论文题录展示

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

作 者: 贡玫
导 师: 郑连伟
学 校: 东北大学
专 业: 运筹学与控制论
关键词: 组播路由 服务质量 时延约束 最小代价 禁忌搜索 动态路由
分类号: TP393.09
类 型: 硕士论文
年 份: 2008年
下 载: 12次
引 用: 0次
阅 读: 论文下载
 

内容摘要


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

全文目录


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

相似论文

  1. 面向业务过程的服务动态组合方法研究,TP393.09
  2. 面向信息物理系统的IEEE802.15.4MAC协议分析及优化,TP212.9
  3. IP网络QoS技术研究,TP393.09
  4. 我国信用卡感知服务质量实证研究,F832.2
  5. 基于顾客满意视角的移动通信业服务质量管理研究,F626;F224
  6. 完全垄断型技术服务外包企业的服务质量提升策略研究,F719
  7. 大学生信用卡顾客忠诚度影响因素的实证研究,F832.2
  8. 基于炼油厂CSTR生产的循环调度与优化问题研究,F273
  9. 保险公估服务质量满意度问题研究,F842
  10. 冶金企业生产与物流作业管理决策支持系统,F426.32
  11. 基于QoS的无线Mesh网络路由协议及相关技术的研究,TN929.5
  12. 基于GMPLS的光突发交换光网络及其关键技术的研究,TN929.1
  13. 多域多层光网络生存性关键技术研究,TN929.1
  14. 基于Linux的流量控制系统的研究与实现,TP393.06
  15. 基于网络编码的无线传输优化算法,TN911.22
  16. 基于QoS感知的Web服务组合,TP393.09
  17. IP网络的QoS技术研究,TN915.09
  18. 基于区分服务模型的IP QoS技术研究,TN915.09
  19. 河南省乡镇卫生院医疗服务质量监管现状及对策研究,R197.6
  20. 基于多节点模式的DTN组播路由算法,TN929.5
  21. 网络电话服务质量保证机制的研究,TP393.02

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 计算机网络 > 一般性问题 > 计算机网络应用程序
© 2012 www.xueweilunwen.com