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

高可靠性的容错组播路由算法研究

作　者: 王肖楠
导　师: 程东年
学　校: 解放军信息工程大学
专　业: 通信与信息系统
关键词: 组播容错故障恢复全局可靠性蚁群优化弱段可用性马尔可夫链
分类号: TN915.02
类　型: 硕士论文
年　份: 2010年
下　载: 30次
引　用: 0次
阅　读: 论文下载

内容摘要

组播通信具有树状路由结构的特点,网络中的单一故障即可造成组播路由结构的严重破坏,因此,提高组播路由的容错能力是一个重要课题。容错组播路由算法分为反应式和先应式两类。根据所构建的组播树结构不同,故障恢复速度快速的先应式算法又分为不相交双树和相交双树两种。对于现有的容错组播路由算法,主要存在以下两个问题:(1)不相交双树所需网络拓扑的连通性条件过于苛刻;(2)缺乏对组播路由树的时变结构特性以及全局容错能力的考虑。鉴于此,本文针对网络发生故障的情况下,能够提供较高的容错能力的组播路由算法展开了专门研究。本文首先提出了能够刻画时变树结构下组播路由容错能力的度量——组播路由全局可靠性,对不同路由结构的容错能力进行了分析,在结论的指导下,研究了高可靠性的容错组播路由算法和快速故障恢复方法。主要工作包括:1、建立了路由全局可靠性模型现有度量无法有效地反映组播路由在数据传输过程中的整体容错能力,本文提出了路由全局可靠性来刻画时变树结构下的组播路由容错能力,并建立模型分析了不相交双树和相交双树两种路由结构的全局可靠性,为高可靠性的容错组播路由算法的设计提供了理论依据。通过模型在冗余双树选择问题上的应用,发现建立相交双树结构的组播路由、优化相交双树中“弱段”数目以及尽量构造“辫状”冗余路由能够提高组播路由的可靠性。这些结论指导了后续的容错组播路由算法的设计。2、提出了一种弱段最小化的容错组播路由算法为了构建符合约束条件且可靠性最大的相交双树,提出了一种弱段最小化的容错组播路由算法(VOMRA),算法基于蚁群算法强大的全局优化能力,采用组成员节点驱动和生成配对蚂蚁的方式搜索相交双树,采用重置方式的信息素单体更新和扬优抑劣的信息素整体更新规则,使得算法倾向于“弱段值”较小且为“辫状”结构的冗余路由。仿真结果表明故障模式下,算法的平均传输时延比PAS和IDFP算法分别低了2.37%和4.83%.3、提出了一种面向弱段的快速故障恢复方法VOMRA算法基于相交双树的路由结构,对于弱段处的故障无能为力。本文提出了一种面向弱段的快速故障恢复方法来解决这个问题。方法计算故障点至原组播树的最短恢复路径,快速地将故障造成的“孤立子树”重新加入到组播树中。针对节点故障造成数个“孤立子树”的情况,采用设定唯一上下游关系的方法,使各子树按顺序依次加入而避免了环路的产生。方法既采用了本地恢复的方式,又使用最短恢复路径进行故障恢复。方法可以和VOMRA结合为FR-VOMRA算法,仿真结果显示FR-VOMRA算法缩短了故障恢复时间。本文以路由全局可靠性模型为指导,以弱段最小化的容错组播路由算法为主体,以面向弱段的快速故障恢复方法为补充,以仿真系统的性能对比为验证,对高可靠性的容错组播路由算法进行了研究,研究成果提升了组播通信的容错能力。

全文目录

表目录  7-8
图目录  8-10
摘要  10-12
ABSTRACT  12-14
第一章绪论  14-23
  1.1 研究背景  14-15
  1.2 组播通信中的容错路由技术  15-19
    1.2.1 反应式容错组播路由技术  15-17
    1.2.2 先应式容错组播路由技术  17-19
  1.3 问题的提出  19-21
    1.3.1 不相交双树所需网络拓扑的连通性条件过于苛刻  19-20
    1.3.2 缺乏对组播路由树的时变结构特性以及全局容错能力的考虑  20-21
  1.4 论文的主要工作和章节安排  21-23
    1.4.1 论文的主要工作  21-22
    1.4.2 章节安排  22-23
第二章路由全局可靠性模型  23-34
  2.1 引言  23
  2.2 组播路由容错能力的度量  23-25
  2.3 全局可靠性模型  25-30
    2.3.1 系统可靠性模型简介  25-27
    2.3.2 单树可靠性模型  27-28
    2.3.3 不相交双树可靠性模型  28
    2.3.4 相交双树可靠性模型  28-30
  2.4 模型在冗余双树选择中的应用和结论  30-33
  2.5 本章小结  33-34
第三章弱段最小化的容错组播路由算法  34-44
  3.1 引言  34
  3.2 路由可靠性优化问题描述  34-35
  3.3 蚁群优化算法(ACO)介绍  35-36
    3.3.1 基本原理  35
    3.3.2 基本模型  35-36
  3.4 弱段最小化的容错组播路由算法(VOMRA)  36-40
    3.4.1 算法概述  36-37
    3.4.2 信息素的更新  37-38
    3.4.3 参数的设置  38-39
    3.4.4 算法实现步骤  39-40
  3.5 非弱段处的故障恢复方法  40-41
  3.6 VOMRA 算法的正确性分析及验证  41-43
    3.6.1 正确性分析  41-42
    3.6.2 仿真验证  42-43
  3.7 本章小结  43-44
第四章面向弱段的快速故障恢复方法  44-51
  4.1 引言  44
  4.2 组播路由的故障恢复时间和方式分析  44-45
    4.2.1 故障恢复时间分析  44-45
    4.2.2 故障恢复方式研究  45
  4.3 组播路由的快速故障恢复模型  45-47
  4.4 基于最短恢复路径的故障恢复方法  47-50
    4.4.1 方法概述  47-48
    4.4.2 最短恢复路径算法  48-49
    4.4.3 恢复路径激活算法  49-50
  4.5 本章小结  50-51
第五章 FR-VOMRA 算法性能分析及仿真对比  51-62
  5.1 FR-VOMRA 算法  51-52
  5.2 算法性能分析  52-53
  5.3 NS2 中组播路由算法仿真设计  53-57
    5.3.1 NS2 中组播路由算法的添加  54-56
    5.3.2 仿真系统的体系结构  56-57
  5.4 仿真测试与结果分析  57-61
    5.4.1 仿真环境设定  57-58
    5.4.2 传输性能对比与分析  58-60
    5.4.3 容错性能对比与分析  60-61
    5.4.4 结论  61
  5.5 本章小结  61-62
结束语  62-64
参考文献  64-68
作者简历攻读硕士学位期间完成的主要工作  68-69
致谢  69

高可靠性的容错组播路由算法研究

内容摘要

全文目录

相似论文