- 309 views
- 394 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 real-world network systems, the component states and the system state can take more than two values. This multi-state 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 two-terminal 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, non-negative 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 NP-hard. 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 d-MP refers to a minimal path vector with respect to demand level d. Firstly, an improved backtracking algorithm based on depth-first search is developed for finding all minimal paths (MPs) for binary networks. These MPs are used as building blocks for generating d-MPs for multistate networks. Secondly, given all the MPs, a recursive algorithm to search for all the d-MPs for all possible d values is developed based on breadth-first search. These d-MPs are used for reliability evaluation of multistate networks. Thirdly, given all d-MPs, 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 d-MPs, 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
- Spring 2016
-
- 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 non-commercial 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.