The Algorithm Research On Stochastic-flow Network Reliability Analysis Based On MDD

As a multi-state discrete probability model, the stochastic-flow network is used to describe computer networks, transportation networks, communication networks. Reliability analysis is an important indicator for network performance evaluation. With the increasing expansion of the network scale, the terms of the inclusion-exclusion principle will be grew exponentially, leading to inefficiencies for evaluating network reliability. Due to the basic characters of compact and disjoint features, multi-valued decision diagram is used to implicitly represent and search the state space or the combination of variables, therefore, the state space explosion problem can be reduced by MDD method. Based on two assumptions of networks with imperfect edges and networks with imperfect edges and nodes, multi-valued decision diagram theory for algorithms research of stochastic-flow network reliability analyses is introduced. The main achievements are as follows:(1) Base on the assumption of networks with imperfect edges, a formal model of stochastic-flow network reliability under time threshold and budget constraint is constructed. Secondly, the complexity of Lin’s algorithm for evaluating stochastic-flow network reliability is analyzed. Thirdly, an algorithm named BTSFN_MDD is presented for evaluating stochastic-flow network reliability under time threshold and budget constraint. Compared with Lin’s algorithm, experiment shows BTSFN_MDD algorithm is running with high efficiency.(2) Base on the assumption of networks with imperfect nodes and edges, a formal model of computer network reliability under time threshold and error rate constraint is constructed. Secondly, the complexity of Lin’s algorithm for evaluating computer network reliability is analyzed. Thirdly, an algorithm named RTSCN_MDD is presented for evaluating computer network reliability under time threshold and error rate constraint. The effectiveness of the RTSCN_MDD algorithm is verified by several experiments.(3) Base on the assumption of networks with two-state nodes and edges, a formal model of networks with binary state nodes and edges is constructed, and a novel network reliability analysis algorithm named NEF_MDD is proposed. Any node and its adjacent non-visited edges’ combination states are enumerated to merge isomorphic sub-networks. Then, a MDD variable is used to represent the reduced state vector and corresponding probability vector. Finally, the MDD representing for the network is constructed by a custom operation. Experiment shows the level and size of decision diagram generated by the proposed algorithm are less than the corresponding binary decision diagram.