Computing Approximate Network Reliability Based On Edge Expansion Diagram

Nowadays the scale of the infrastructure network is successively increasing, and people have a continually higher demand on the network reliability. Network reliability influences the layout and the planning of the infrastructure network construction as a key index. Hence how to calculate the network reliability rapidly and accurately has always been a focus of the trusted computing area.In the network reliability analysis, using edge expansion diagram technique can greatly improve the performance and efficiency. This process mainly includes three steps:ordering the edges, constructing a edge expansion diagram, generating a BDD equivalent to the EED and calculating the reliability. Specifically, first, according to the strategy of BFS, we order the edges of the network, then use edge expansion diagram technique to construct a EED equivalent to the network, finally generate a reliable equivalent BDD and calculate the value of each BDD, and recursively calculate the final reliability value of the BDD. Exact reliability, small and regular network can be calculated quickly, but for large-scale networks, reliability calculation is difficult. Hence, researchers proposed a method of approximate analysis for network reliability. In the analysis of approximate network reliability, the existing methods are mostly based on cutsets or pathsets, but in this thesis, we study aspect based on truncated edge expansion diagrams.The contribution of this thesis aims at truncated edge expansion diagrams research on approximate analysis for network reliability, the specific work includes:Basing on the algorithm proposed by Kuo build approximate algorithm on truncated edge expansion diagrams for computing network reliability. The algorithm of Kuo consists of ordering the edges, constructing a edge expansion diagram, generating a BDD equivalent to the EED and calculating the reliability. In this thesis, the approximate algorithm is based on a given threshold of truncating edge expansion diagram, and then generating the equivalent BDD, finally calculating the network reliability. The performance analysis based on kinds of regular network models and the comparison with the existing approximate algorithm come to the conclusion, the algorithm can greatly reduce the binary decision diagram size and the error of reliability is maintained at a certain range. The result is very important for approximate analysis for network reliability on infrastructure network.The approximate analysis for network reliability on truncated edge expansion diagrams is applied to infrastructure network. The network models are Beijing rail transit network, Henan power network, social network. For each network model, we randomly select 3 different groups of source and terminal, and count performance index of the process of connectivity reliability analysis, such as reliability value,binary decision diagram size and error, then compare them with the result of Kuo. The experimental results showed the superiority of the approximation algorithm we proposed.