Bdd-Based Network Reliability Analysis Methods Research

With the development of human civilization, network has been a very important part in our daily lives and industrical production. Due to the Big Data techniques, network systems become larger and more complex. Thus, the reliability analysis of networks becomes more and more important.Using Binary Decision Diagram (BDD) technique to analyze the reliability of network can greatly improve the performance and efficiency. The BDD-based method consists of three steps:find out a network variable ordering with good performance, construct a BDD encoding the original network, and calculate the reliability measures of the network by analyzing the generated BDD. Choosing a powerful ordering heuristic to generate a good ordering of network edges and nodes can greatly improve the performance of BDD-based reliability analysis algorithm. According to the obtained variable ordering, use the network deconstruction to construct a equivalent BDD for the target network. Calculate the probability relating to each BDD node based on a recursive method, and calculate the final reliability measures of the network. The time and space complexity are considered for our algorithm, the complexity indices are measured by the path length and the nodes number of BDD. Therefore, in order to improve the algorithm performance when we choose the edge ordering or calculate the final reliability measures, we should try to minimize the number of BDD nodes and shorten the length of the BDD path.The improvement of the performance of BDD-based network reliability analysis algorithm is currently a hot topic. This paper has made some efforts to improve performance, the noval research work of this paper mainly includes:(1) Based on the bottom-up BDD construction algorithm proposed by Sy-Yen Kuo which uses edge expansion technique, we proposed some algorithm improvements on two aspects:Firstly, we presented a more concise and efficient isomorphism check method named "Kernel" method to determine whether the subnets appear in the network deconstruction process are isomorphic. The second is about redundancy elimination, we proposed the concept of s-t disconnect expansion path and redundant node expansion path, and then we show how to delete these two types of invalid expansion path.(2) We improved the top-down algorithm proposed by Gary Hardy, which uses the edge expansion and edge deletion technique. The main idea of our improvement is "Partition", and we use boundary partition to identify a network. This method makes subnets isomorphism check easier and it also makes the storage of network information more convenient. In detail, our improvement includes two aspects:based on the theorem "two subnets in the same layer are isomorphic if their boundary partitions are equal", we developed a top-down BDD construction algorithm with redundancy elimination for K-terminal network reliability analysis. Using Hash operations in the process of BDD construction can greatly enhance the performance of the algorithm.(3) After using the techniques of isomorphic subnets elimination, redundancy elimination and subgraph sharing, the performance of BDD construction algorithm has been improved greatly, and the obtained BDD size becomes smaller, but it is still very large for some complex networks. The BDD size heavily relies on the edge ordering, and BDD edge ordering problem is a NP-hard problem. In this work, we use the Breadth First Search heuristic, and we study the edge ordering problem and find our the distribution patterns of the best performance start node and the worst performance start node in rule network and nearest neighbor network. Our findings on the influence of network ordering start node to the performance of BDD algorithm are very important for the performance improvement of network reliability analysis.In summary, this paper focused on the BDD-based network reliability analysis methods. Based on the Kuo and Hardy algorithm, we show how to improve their performance. Based on the breadth-first edge ordering, we analyze the influence of start node to the analysis performance. We also show how to select the optimal variable ordering, and create a BDD with less computation time and less storage space. Based on the bottom-up and top-down algorithms, we proposed an isomorphic subgraphs check method and a redundant sub-graph elimination method. Empirical results show that our improvement methods can offer lower computational complexity as well as a simpler model construction and improved evaluation algorithms over Kuo and Hardy algorithms.