AN IMPROVED ALGORITHM FOR K-TERMINAL PROBABILISTIC NETWORK RELIABILITY ANALYSIS
Keywords:
Minimal Path Set, Binary Decision Diagram, Ordered Binary Decision Diagram, Reduced Ordered Binary Decision Diagram, Variable Ordering Heuristics, Breadth First Search TraversalAbstract
An optimal variable ordering technique for Reduced Ordered Binary Decision Diagram (ROBDD) has been proposed to solve the network reliability analysis problem for complex communication networks. Several approaches have been proposed in the literature using the static and dynamic variable ordering techniques to solve the terminal network reliability problems. In this paper, the Minimal path set enumeration of the networks using Breadth first search traversal and ROBDD based Sift-reordering technique on manipulating the reliability evaluation is presented. The experimental results are compared with the previous approaches in computational time and number of ROBDD nodes to evaluate the K-terminal network reliability analysis.
Downloads
References
Akers, S.B. (1978). Binary decision diagrams, IEEE Transactions on
computers, 100(6), p. 509-516.
Al-Ghanim, A.M. (1999). A heuristic technique for generating minimal path
and cutsets of a 24 general network, Computers & Industrial Engineering, 36
(1), p. 45-55.
Bollig, B. and Wegener, I. (1996). Improving the variable ordering of OBDDs
is NP-complete, IEEE Transactions on computers, 45 (9), p. 993-1002.
Bryant, R.E. (1986). Graph-based algorithms for boolean function
manipulation, IEEE Transactions on Computers, 100 (8), p. 677-691.
Colbourn, C. (1987). The Combinatorics of Network Reliability, Oxford
University Press, New York, USA.
Gertsbakh, I. and Shpungin, Y. (2008). Network reliability importance
measures: combinatorics and monte carlo based computations, WSEAS
Transactions on Computers, 7 (4), p. 216-227.
Hardy, G., Lucet, C. and Limnios, N. (2007). K-terminal network reliability
measures with binary decision diagrams, IEEE Transactions on Reliability, 56
(3), p. 506-515.
Hui, K.P. (2007). Monte Carlo network reliability ranking estimation, IEEE
Transactions on Reliability, 56 (1), p. 50-57.
Kim, Y. and Kang, W.H. (2013). Network reliability analysis of complex
systems using a non-simulation-based method, Reliability Engineering &
System Safety, 110, p. 80-88.
Kobayashi, K. and Yamamoto, H. (1999). A new algorithm in enumerating all
minimal paths in a sparse network, Reliability Engineering & System Safety,
(1), p. 11-15.
Kuo, S.Y., Lu, S.K. and Yeh, F.M. (1999). Determining terminal-pair
reliability based on edge expansion diagrams using OBDD, IEEE Transactions
on Reliability, 48 (3), p. 234-246.
Kuo, S.Y., Yeh, F.M. and Lin, H.Y. (2007). Efficient and exact reliability
evaluation for networks with imperfect vertices, IEEE Transactions on
Reliability, 56 (2), p. 288-300.
Lee, C.Y. (1959). Representation of Switching Circuits by Binary-Decision
Programs, Bell Labs Technical Journal, 38 (4), p. 985-999.
Li, J. and He, J. (2002). A recursive decomposition algorithm for network
seismic reliability evaluation, Earthquake Engineering & Structural
Dynamics, 31 (8), p. 1525-1539.
Mishra, R. and Chaturvedi, S.K. (2009). A cutsets-based unified framework to
evaluate network reliability measures, IEEE Transactions on Reliability, 58
(4), p. 658-666.
Rauzy, A. (2003). A new methodology to handle Boolean models with loops,
IEEE Transactions on Reliability, 52 (1), p. 96-105.
Rudell, R. (1993). Dynamic variable ordering for ordered binary decision
diagrams, Proceeding of the IEEE/ACM International conference on
Computer-aided design, p. 42-47.
Satyanarayana, A. and Chang, M.K. (1983). Network reliability and the
factoring theorem, Networks, 13 (1), p. 107-120.
Sekine, K. (1999). Computational investigations of all-terminal network
reliability via BDDs, IEICE Transactions on Fundamentals of Electronics,
Communications and Computer Sciences, 82 (5), p. 714-721.
Shen, Y. (1995). A new simple algorithm for enumerating all minimal paths
and cuts of a graph, Microelectronics Reliability, 35 (6), p. 973-976.
Soh, S. and Rai, S. (1993). Experimental results on preprocessing of path/cut
terms in sum of disjoint products technique, IEEE Transactions on Reliability,
(1), p. 24-33.
Somenzi, F. (2012). CUDD-2.5.0, http://vlsi.colorado.edu.
Xing, L. (2008). An efficient binary decision diagram based approach for
network reliability and sensitivity analysis, IEEE Transactions on Systems,
Man, and Cybernetics-Part A: Systems and Humans, 38 (1), p. 105-115.
Yeh, F.M., Lu, S.K. and Kuo, S.Y. (2002). OBDD-based evaluation of k-
terminal network reliability, IEEE Transactions on Reliability, 51 (4), p. 443-
Yeh, W.C. (2007). An improved sum of disjoint products technique for the
symbolic network reliability analysis with known minimal paths, Reliability
Engineering & System Safety, 92 (2), p. 260-268.
Yeh, W.C. (2008). A greedy branch and bound inclusion-exclusion algorithm
for calculating the exact multi-state network reliability, IEEE Transactions on
Reliability, 57 (1), p. 88-93.
Zang, X. Sun, N. and Trivedi, K.S. (1999). A BDD-based algorithm for
reliability analysis of phased-mission systems, IEEE Transactions on
Reliability, 48 (1), p. 50-60.
