An Improved Algorithm Of Communication Network Reliability Based On Minimal Pathsets

The algorithms of network reliability based on minimal pathsets play an important role in the calculation of network reliability. The most common used mtheods include sum of disjoint method and binary decision diagram method. And these methods are more efficient than those ever.However, they are difficult to implement and not conducive to the survey of some other features of the network. At the same time, the efficiency of these methods is still to be improved for the calculation of the NP-hard network reliability.This paper studies the algorithm of network reliability based on pathset matrix and boolean operation. It’s easy to use and program. In addition it simplified the calculation of network reliability and the important reliability, all of which makes this method an useful tool in network reliability calculation, however, there exists a serious combinatorial explosion problem.And the operation time grows almost exponentially with the number of minimal paths.Our paper keeps the advantages of the previous algorithm. Firstly the special pathsets are preprocessed to reduce the number of minimal paths that invole in the following calculation. Secondly the bit vector is used to store the pathset matrix and the matrixes generated in the calculation. Thirdly improve the algorithm to reduce the redundancy and the time complexity of tha algorithm. The result shows that for different networks the efficiency of the improved algorithm increases with different degrees compared with the previous algorithm, which relieves the combinatorial explosion problem and widens the application of the algorithm in some degree.Finally, the improved algorithm is applied to the fact network reliability and efficiency calculations.First of all, the reliability and efficiency of the components are obtained, and then the minimal pathsets between each terminal node and the center node are generated. Finally the reliability and efficiency are obtained by the improved algorithm, which provides valuable reference for the the design of network reliability and evaluation.