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