System Reliability Evaluation for Imperfect Networks Using Polygon-to-Chain Reduction — Oak Academic Publishing
Research ArticleOpen AccessGoogle Scholar indexed
System Reliability Evaluation for Imperfect Networks Using Polygon-to-Chain Reduction
Department of Mechanical Engineering/Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, Laval University, Quebec, Canada
,
Department of Mechanical Engineering/Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, Laval University, Quebec, Canada
1 Department of Mechanical Engineering/Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, Laval University, Quebec, Canada
2 Department of Mechanical Engineering/Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, Laval University, Quebec, Canada
The purpose of this paper is to propose a computational technique for evaluating the reliability of networks subject to stochastic failures. In this computation, a mathematical model is provided using a technique which incorporates the effect of the factoring decomposition theorem using polygon-to-chain and series-parallel reductions. The algorithm proceeds by identifying iteratively one of seven polygons and when it is discovered, the polygon is immediately removed and replaced by a simple chain after having changed the individual values of the reliability of each edge and each node of the polygon. Theoretically, the mathematical development follows the results presented by Satyanarayana & Wood and Theologou & Carlier. The computation process is recursively performed and less constrained in term of execution time and memory space, and generates an exact value of the reliability.
Institute of Electrical and Electronics Engineers (1990) IEEE Standard Computer Dictionary: A Compilation of IEEE Standard Computer Glossaries. IEEE Std 610, 1-217.
Deo, N. and Medidi, M. (1992) Parallel Algorithms for Terminal-Pair Reliability. IEEE Transactions on Reliability, 41, 201-209. https://doi.org/10.1109/24.257782
Dotson, W.P. and Gobien, J. (1979) A New Analysis Technique for Probabilistic Graphs. IEEE Transactions Circuits and Systems, 26, 855-865. https://doi.org/10.1109/TCS.1979.1084573
Fratta, L. and Montanari, U.G. (1973) A Boolean Algebra Method for Computing the Terminal Reliability in a Communication Network. IEEE Transactions on Circuit Theory, 20, 203-211. https://doi.org/10.1109/TCT.1973.1083657
Heidtmann, K.D. (1989) Smaller Sums of Disjoint Products by Subproduct Inversion. IEEE Transactions on Reliability, 38, 305-311. https://doi.org/10.1109/24.44172
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, 288-298. https://doi.org/10.1109/TR.2007.896770
Lin, H.Y., Kuo, S.Y. and Yeh, F.M. (2003) Minimal Cutset Enumeration and Network Reliability Evaluation by Recursive Merge and BDD. Proceedings of the 8th IEEE International Symposium on Computers and Communication, 2, 1530-1346.
Liu, H.H., Yang, W.T. and Liu, C.C. (1993) An Improved Minimizing Algorithm for the Summation of Disjoint Products by Shannon’s Expansion. Microelectronic Reliability, 33, 599-613.
Misra, K.B. (1970) An Algorithm for the Reliability Evaluation of Redundant Networks. Transactions on Reliability, R-9, 146-151. https://doi.org/10.1109/TR.1970.5216434
Tarjan, R.E. (1972) Depth First Search and Linear Graph Algorithms. SIAM Journal of Computing, 1, 146-160. https://doi.org/10.1137/0201010
Yan, L. and Taha, H.A. (1994) A Recursive Approach for Enumerating Minimal Cutsets in a Network. IEEE Transaction on Reliability, 43, 383-388. https://doi.org/10.1109/24.326430
Yoo, Y.B. and Deo, N. (1988) A Comparison of Algorithms for Terminal-Pair Reliability. IEEE Transactions on Reliability, 37, 210-215. https://doi.org/10.1109/24.3743
Locks, M.O. and Wilson, J.M. (1992) Note on Disjoint Products Algorithms. IEEE Transactions on Reliability, 41, 81-84. https://doi.org/10.1109/24.126676
Simard, C. (1996) Contribution au problèmed’évaluation de la fiabilité des réseaux. Master Thesis, Laval University, Quebec, Canada, TJ-7.5-UL-1996.
Moskowitz, F. (1958) The Analysis of Redundancy Networks. Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics, 77, 627-632.
Page, L.B. and Perry, J.E. (1988) A Practical Implementation of the Factoring Theorem for Network Reliability. IEEE Transactions on Reliability, 37, 259-267. https://doi.org/10.1109/24.3752
Page, L.B. and Perry, J.E. (1989) Reliability of Directed Network Using the Factoring Theorem. IEEE Transactions on Reliability, 38, 556-562. https://doi.org/10.1109/24.46479
Rebaiaia M.L. (2011) A Contribution to the Evaluation and Optimization of Networks Reliability. PhD Thesis, Laval University, Canada.
Resende, M.G.C. (1986) A Program for Reliability Evaluation of Undirected Networks via Polygon-to-Chain Reductions. IEEE Transaction on Reliability, 35, 24-29. https://doi.org/10.1109/TR.1986.4335334
Satyanarayana. A. and Chang M. (1983) Network Reliability and the Factoring Theorems. Networks, 13, 107-120. https://doi.org/10.1002/net.3230130107
Satyanarayana, A. and Wood, R.K. (1985) A Linear-Time Algorithm for Computing K-Terminal Reliability in Series-Parallel Networks. SIAM Journal on Computing, 14, 818-832. https://doi.org/10.1137/0214057
Theologou, R. and Carlier, J.G. (1991) Factoring & Reduction for Networks with Imperfect Vertices. IEEE Transactions on Reliability, 40, 210-217. https://doi.org/10.1109/24.87131
Hardy, G., Lucet, C. and Limnios, N. (2007) K-Terminal Network Reliability Measures with Binary Decision Diagrams. IEEE Transaction on Reliability, 56, 506-515. https://doi.org/10.1109/TR.2007.898572
Rudell, R. (1993) Dynamic Variable Ordering for Ordered Binary Decision Diagrams. Proceedings of the IEEE International Conference on Computer Aided Design, Santa Clara, CA, 7-11 November 1993, 42-47.
Nakazawa, H. (1976) Bayesian Decomposition Method for Computing Reliability of Oriented Network. IEEE Transactions on Reliability, R-25, 77-80. https://doi.org/10.1109/TR.1976.5214983
Kubat, B. (1989) Estimation of Reliability for Communication/Computer Networks-Simulation/Analytic Approach. IEEE Transactions on Reliability, 37, 927-933. https://doi.org/10.1109/26.35372
Rebaiaia, M.-L. and Ait-Kadi, D. (2015) Reliability Evaluation of Imperfect K-Terminal Stochastic Networks Using Polygon-to-Chain and Series-Parallel Reductions. Proceedings of the 11th ACM Symposium on QoS and Security for Wireless and Mobile Networks, Cancun, Mexico, 2-6 November 2015, 115-122.
Valian, L.G. (1979) The Complexity of Enumerating and Reliability Problems. SIAM Journal of Computing, 8, 410-421. https://doi.org/10.1137/0208032
Ball, M.O. (1986) Computational Complexity of Network Reliability Analysis: An Overview. IEEE Transactions on Reliability, 35, 230-239. https://doi.org/10.1109/TR.1986.4335422
Rosenthal, A. (1974) Computing Reliability of Complex Systems. PhD Thesis, University of California, Berkeley.
Wood, R.K. (1986) Factoring Algorithms for Computing K-Terminal Network Reliability. IEEE Transactions on Reliability, 35, 269-278. https://doi.org/10.1109/TR.1986.4335431
Barlow, E.B. and Proschan, F. (1975) Statistical Theory of Reliability and Life Testing: Probability Models (International Series in Decision Processes), (Ed.) Rinehart & Winston, Holt.
Moore, E.F. and Shannon, C.E. (1956) Reliable Circuits Using Less Reliable Relay. Journal of the Franklin Institute, 262, 281-297.
Murchland, J. (1973) Calculating the Probability That a Graph Is Disconnected. Working Paper No. 18.
Wang, S.-D. and Sun, C.-H. (1996) Transformations of Star-Delta and Delta-Star Reliability Networks. IEEE Transactions on Reliability, 45, 120-126. https://doi.org/10.1109/24.488927
Choi, M.S and Jun, C-H. (1995) Some Variants of Polygon-to-Chain in Evaluating Reliability of Undirected Networks. Microelectronics Reliability, 35, 1-11. https://doi.org/10.1016/0026-2714(94)P1833-X