基于离散概率模型的二端网络可靠性分析

摘要

在经济生活日益依赖于通信网的今天，网络故障不仅会带来巨大的数据损失，甚至会导致灾难性后果。利用网络可靠性分析，工程人员可以增强网络可靠性，减少故障时损失。尽管网络可靠性分析已经取得了大量成果，但如下方面还需要开展进一步研究： 第一，网络结点不可靠时的可靠性分析。传统的网络可靠性分析通常假设结点可靠，这在一些新的网络研究领域是不成立的，譬如自组织网络、灾难环境网络。而且，当网络结点众多时，可靠性分析中的计算量将变得非常庞大。 第二，网络部件故障非统计独立时的可靠性分析。传统的网络可靠性分析通常假设部件故障统计独立，这会给某些网络的可靠度评估带来很大的偏差，譬如极端环境下的网络。另外，当非统计独立故障较多且网络规模较大时，可靠性分析将变得非常困难。 第三，网络部件重要性分析。传统的网络可靠性分析主要讨论可靠度计算，不能从部件故障角度全面了解网络可靠性，缺乏高效的计算方法。 第四，网络运行时可靠性分析。传统的网络可靠性分析主要研究可靠性设计指标，其成果不能很好地反映运行时的网络可靠性。 通信网有着庞大的规模和动态复杂性，经典的故障分布函数很难描述网络的故障特性。为降低复杂性，解决一般性问题，本文采用了主流的网络可靠性模型——时间独立的离散概率模型。另外，本文只讨论了二端网络的可靠性问题，但其成果可以推广到K端网络和全端网络。 针对网络可靠性分析中存在的上述问题，本文从四个方面开展了研究工作： (1)研究了结点不可靠网络的可靠性分析，提出了基于标记因子划分的网络可靠度评估算法——MFP(MarkedFactorPartition)和基于特征识别的street网络可靠度评估算法——SNR(StreetNetworkReliability)，解决了部分规模较大而结点不可靠的网络可靠度评估问题。最后，针对无线传感网的众多不可靠结点，提出了能有效评估可靠度的算法——EF(EnhancedFactoring)。 1)MFP改进了基于有序二叉判定图(OBDD，OrderedBinaryDecisionDiagram)的可靠性分析方法。在创建OBDD过程中，利用边替代(ER，EdgeReplacement)运算处理网络中的不可靠结点。同时，从两个方面减少了计算量：分解网络时，根据子网的标记因子划分来识别同构子网，避免分解同构子网带来的重复计算；利用OBDD来存储网络结点和边的状态，减少了冗余状态。 2)SNR是专门针对street网络的方法，其基本原理与MFP相同。SNR利用源端位置信息作为子网特征，识别street网络分解过程中出现的同构子网，从而减少重复计算。 3)增强因子分解算法在网络分解过程中采用hash表来存储同构子网的可靠度，提高了计算效率。 (2)研究了一类常见的非统计独立故障——共因失效，提出了分析共因失效网络可靠性的算法——CNR(Common-cause-failureNetworkReliability)和无线传感网可靠性的算法——WR(Wireless-sensor-networksReliability)。解决了部分共因事件较多且规模较大网络的可靠度评估问题，讨论了有共因失效的无线传感网可靠度评估问题。 1)CNR改进了基于OBDD的共因失效可靠性分析方法。为降低分析复杂性，CNR算法未考虑结点不可靠的情况。由于CNR方法只需要递归创建一个OBDD结构，在共因事件较多、网络规模较大时，这种方法可节省大量计算开销。关于如何创建共因失效网络的OBDD，本文又提出了两种方法：基于布尔运算的方法和基于共因变量集的方法。第一种方式比较灵活，第二种方式有较高的存储效率。 2)WR算法充分考虑了无线传感网中的大量共因事件和不可靠结点，借用了CNR创建共因失效网络OBDD的思路，利用结点扩张法来处理无线传感网中的不可靠结点。 (3)研究了网络部件重要性分析。讨论利用Birnbaum测度、关键重要度和风险增长区间等部件重要性指标来描述网络可靠性，提出了基于Birnbaum测度的链路重要性评估算法——BIL(BirnbaumImportanceofLink)和基于风险增长区间的网络可靠性评估算法——RI(RiskIncrement)。BIL充分利用OBDD结构来高效计算Birnbaum测度、关键重要度和风险增长，发现网络薄弱环节，确定引发故障的最可能部件。而RI能够对部件故障时的网络稳定度进行分析，为网路抗毁性提供了又一个参考指标。另外，针对无线传感网中不可靠结点，提出了基于风险增长的结点重要性评估算法——WNI(WirelessNodeImportance)。 (4)针对网络运行时可靠性分析，提出了两个可靠性测度：基于故障检测的指标——容错MPLS网络的可靠性测度；基于可用带宽测量的指标——自愈IP网络可靠性测度。最后，为分析容错MPLS网络运行时可靠性，设计并实现了一个开销较低速度较快的故障检测方法——自适应的LSP故障检测机制。

目录

文摘

英文文摘

声明

第1章 绪论

1.1本课题的研究背景

1.2本文的研究内容和意义

1.3本文的结构和安排

1.4本章参考文献

第2章二端网络的离散概率模型与网络可靠性分析综述

2.1符号表示

2.2二端网络的离散概率模型

2.3网络可靠性指标

2.3.1 网络可靠度

2.3.2 网络部件重要度

2.3.3 其它指标

2.4网络可靠性分析现状与挑战

2.4.1 网络可靠性分析的现状

2.4.2 网络可靠性分析的挑战

2.5本章小结

2.6本章参考文献

第3章结点不可靠网络的可靠性分析

3.1引言

3.2符号表示

3.3 OBDD基本原理和运算

3.3.1 OBDD的基本原理

3.3.2 OBDD的运算

3.3.3 OBDD与可靠度布尔函数

3.4基于OBDD的可靠度评估算法

3.4.1 因子分解创建OBDD

3.4.2 边扩张创建OBDD

3.4.3 递归方法计算可靠度

3.4.4 子网同构问题

3.5基于标记因子划分的网络可靠度评估

3.5.1 标记因子划分原理

3.5.2 应用标记因子划分原理改进OBDD算法

3.5.3 实验

3.6基于特征识别的street网络可靠度评估

3.6.1 street网络与子网同构

3.6.2 应用s-hash改进OBDD算法

3.6.3 实验

3.7增强因子分解法评估无线传感网可靠度

3.7.1 无线传感网的二端图

3.7.2 结点的因子分解

3.7.3 算法步骤与伪码

3.7.4 实验

3.8本章小结

3.9本章参考文献

第4章共因失效网络的可靠性分析

4.1引言

4.2共因失效模型

4.2.1 符号表示

4.2.2 考虑共因因素的可靠度计算

4.3改进的OBDD算法评估共因失效网络可靠度

4.3.1 基于布尔运算的失效网络OBDD创建方法

4.3.2 基于共因变量集的共因失效网络分析法

4.4应用共因失效模型评估无线传感网可靠度

4.4.1 算法设计

4.4.2 算例分析

4.4.3 实验

4.5本章小结

4.6本章参考文献

第5章网络部件重要性分析

5.1引言

5.2符号表示

5.3重要性指标

5.3.1 Bimbaum测度

5.3.2 关键重要度

5.3.3 险增长区间

5.4基于Birnbaum测度的链路重要性评估

5.4.1 可靠度模型

5.4.2 算法设计

5.4.3 算例分析

5.5基于风险增长的网络可靠性稳定度评估

5.5.1 可靠度模型

5.5.2 算法设计

5.5.3 实验

5.6基于风险增长的无线传感网结点重要性评估

5.6.1 可靠度模型

5.6.2 算法设计

5.6.3 实验

5.7本章小结

5.8本章参考文献

第6章基于网络测量的可靠性分析

6.1引言

6.2基于网络测量的网络可靠性测度

6.2.1. 容错MPLS网络的可靠性测度

6.2.2 自愈IP网络可靠性测度

6.3自适应的LSP故障检测机制

6.3.1 MPLS故障检测

6.3.2 MPLS环回OAM架构

6.3.3 自适应故障检测的理论模型

6.3.4 简化的自适应故障检测模型

6.3.5 自适应的故障检测算法

6.3.6 实验

6.4本章小结

6.5本章参考文献

结束语

致 谢

个人简历及参加的科研工作

在攻博期间发表的文章