工程网络可靠性分析研究

摘要

随着工程网络建设规模的不断增大，各行各业对其网络可靠性的要求也在不断的提高。网络可靠性作为工程网络建设的一项重要指标，时刻影响着其布局与规划。如何快速、精确地计算工程网络可靠性，始终是可信计算领域里的一个核心问题。
　　本论文根据工程网络的特点，分别针对边失效型工程网络模型和节点失效型这两类工程网络模型，进行可靠性分析研究。针对边失效型的工程网络模型，提出了一个冗余子网删除定理，然后，基于这个定理，提出了一种网络简化技术。这种简化技术首先利用Tarjan算法找到网络的关节点，然后根据K点的分布情况，按照一定规则逐个在关节点上进行边删除和K点连通边添回操作。这种网络简化技术以非常小的时间代价，事先对工程网络进行冗余子网识别与删除，从而有效缓解了直接利用网络可靠性分析方法在规模庞大、结构复杂的工程网络上直接进行计算，容易引发的内存溢出和组合爆炸等问题。本文选取了多个工程网络进行实验，实验结果表明，这种预处理技术，可以明显提高可靠性分析算法在工程网络上的工作效率。
　　针对节点失效型的工程网络模型，本文注意到一个节点失效则对应多条边失效这一网络特性。同时，我们还参考Kuo和Hardy的边失效型网络模型的网络可靠性BDD(Binary Decision Diagram)构建算法，提出了一个节点块的概念，并分别制定了节点块选择规则以及节点块中节点的选择规则，为节点失效型二端工程网络的网络可靠性等价BDD构建，提供了一种动态节点排序方法;此外，在节点失效型网络等价BDD的生成过程中，又利用BDD节点对应的网络结构，提出了一个同构BDD节点识别定理。这种基于节点动态排序的网络可靠性等价BDD构建方法，可以快速判断节点失效型二端网络中st点的连通情况，再结合同构BDD识别定理，再次降低等价BDD构建过程中计算机内存的压力，提高节点失效型的二端工程网络可靠性分析的性能和效率。

目录

摘要

1 绪论

1．1 研究背景和意义

1．2 工程网络可靠性的研究现状

1．2．1 网络可靠性相关的概念

1．2．2 网络可靠性分析的研究现状

1．2．3 常见的工程网络可靠性分析应用

1．3 本文主要工作和组织结构

1．3．1 本文的主要工作

1．3．2 本文的结构安排

1．4 本章小结

2 工程网络可靠性分析基础

2．1 引言

2．2 网络模型

2．2．1 网络的基本概念

2．2．2 规则网络模型

2．2．3 随机网络模型

2．2．4 工程网络模型

2．3 BDD相关知识和操作

2．4 本章小结

3 工程网络可靠性分析的网络简化方法

3．1 引言

3．2 问题分析

3．3 算法描述

3．3．1 关节点定义

3．3．2 冗余消除定理

3．3．3 算法实现

3．4 算法应用

3．4．1 在工程网络的应用

3．4．2 在社交网络的应用

3．4．3 性能分析

3．5 本章小结

4 一种二端节点失效型工程网络可靠性分析方法

4．1 引言

4．2 问题描述

4．3 算法描述

4．4 同构识别

4．5 算法性能测试

4．6 本章小结

5 工作总结与展望

5．1 工作总结

5．2 工作展望

参考文献

攻读硕士学位期间取得的成果

致谢

声明