基于路径函数和BDD的网络可靠度分析

Computing Network Reliability Based on Path-Function and BDD

现有的二终端网络可靠度评估方法,多数基于不交积和,由于没有充分利用普遍存在的同构子网特性,导致存在大量冗余计算,无法适用于大型网络.为此,本文提出了一种基于路径函数和BDD的网络可靠度分析方法,利用图Hash技术识别同构子网,从而简化路径函数的构建,再利用BDD高效地操纵路径函数计算网络可靠度.实验结果表明,该方法性能稳定且高效,适用于更大规模的网络可靠性分析.

For computing network reliability, most published algorithms are based on the sum of disjoint products. However they lack the capability to avoid redundant computation due to isomorphic sub-problems which are common in the network,and can not be applied to larger networks. To overcome these problems, we present an efficient method which is based on path function and BDD （binary decision diagram）. First, the success path function of a given network is constructed by traversing the network. In this process, the sub-graph isomorphism is efficiently identified. Then in order to further improve performance, we efficiently manipulate the path function using BDD and calculate the reliability measures. The results of experiment show that our method is stable and efficient and can be applied to a number of large-scale networks.