The Study On Two-terminal Network Reliability

With the current development of economy, computer networks, communicationnetworks, electricity supply network, water supply network, gas supply networks andtransportation networks etc. have become an increasingly important part in the nationaleconomy. The reliability of network is more and more important related to thedevelopment of the national economy. In this thesis, the reliability of two-terminalnetwork under two states and multi-state components have been studied, the mail worksare as follows:Because the two-terminal network reliability is a NP hard problem, any exactalgorithm for large network can not get the desired results. Under the assumption thatall links in the network has only two states and the probability of failure state is smallenough, the result that the probability of the numbers of network failure links less thantwo is more than 2.5/e is proved. Using the idea of state-space truncation method, thetruncated network states are analyzed based on the Markov model. Finally, the lowerbound of the two states network reliability can be obtained.For the flow network, it also has the degraded states besides work and failure state.The multi-state model is used. In this thesis, the related concepts and the algorithms ofmulti-state two-terminal network reliability are introduced. Then the algorithm based onRamire-Marquez is improved through optimizing the information sharing mechanism,proposed the algorithm is based on the sort of minimum cut set method. It is found that,for small-scale network, this improvement is not meaningful, but it can greatly reducethe computation cost in the calculation of minimal cut sets to larger network throughanalyzing the example.Through analyzing the multi-state network state space, it is found that, theprobability of a considerable portion of the system states that occur is very small, andthe probability of a certain system states that occur may occupy almost the entirenetwork system state space. In this thesis, the ORDER-M algorithm is improved,whichfinds the K states that most likely happened in the multi-state network, and ensures theprobability of resulting K states that occur is large enough. The K network system statescan be considered as the actual network states that occur. And then, the multi-statetwo-terminal network reliability is obtained by analyzing the K system states withmaximum flow algorithm.