 69 views
 88 downloads
Efficient Evaluation of Multistate Network Reliability

 Author / Creator
 Bai, Guanghan

In network reliability context, it is often assumed that both the components and the systems can take two possible states, completely working or totally failed. However, in many realworld network systems, the component states and the system state can take more than two values. This multistate phenomenon has to be addressed when specific performance measures such as capacity are taken into consideration. The network must not just be connected but function at a certain performance level. For a twoterminal multistate network with a source node, s, and a sink node, t, the reliability is defined as the probability of successfully sending a required amount of flow, d, from node s to node t, which is the probability that the flow throughput is not less than d. The capacity (state) of each component can take discrete, nonnegative integer values from 0 to its maximum capacity, following a certain probability distribution. The overall objective of multistate network reliability is to provide engineers and managers useful tools to enhance their ability for design and maintenance of such networks. However, despite the increasing complexity of modern networks, the size of the network that can be analyzed by existing methods is still rather modest, given a modest number of states for each component. This is expected since the network reliability analysis problem is NPhard. Consequently, research aimed at improving the efficiency of reliability evaluation is needed. In addition, most reported works focus on one specific demand at a time. However, during the design phase or operation phase, we are often interested in system reliability with respect to multiple possible demand levels, in order to obtain a complete picture of the system capability. Thus, an efficient and systematic method is desirable for network reliability evaluation with respect to all possible d values. This thesis documents research contribution for efficient evaluation of multistate network reliability using the indirect approaches based on minimal path vectors. A dMP refers to a minimal path vector with respect to demand level d. Firstly, an improved backtracking algorithm based on depthfirst search is developed for finding all minimal paths (MPs) for binary networks. These MPs are used as building blocks for generating dMPs for multistate networks. Secondly, given all the MPs, a recursive algorithm to search for all the dMPs for all possible d values is developed based on breadthfirst search. These dMPs are used for reliability evaluation of multistate networks. Thirdly, given all dMPs, ordering heuristics are proposed to improve the efficiency of the Recursive Sum of Disjoint Product (RSDP) method for evaluating multistate network reliability. Fourthly, given all dMPs, an improved State Space Decomposition (SSD) algorithm is developed for evaluating multistate network reliability. Thorough efficiency investigations are conducted to compare the efficiency of the reported direct approaches and indirect methods, including the proposed improved SSD method and the RSDP method with ordering heuristics, for evaluating multistate network reliability. With efficient reliability evaluation algorithms and methods, the research results out of this thesis provide the reliability engineers and facility managers a more powerful tool for the design and maintenance of more complex networks.

 Subjects / Keywords

 Graduation date
 201606

 Type of Item
 Thesis

 Degree
 Doctor of Philosophy

 License
 This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for noncommercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.