An efficient algorithm for computing exact system and survival signatures of K-terminal network reliability

Reed, Sean; Löfstrand, Magnus; Andrews, John

Abstract

An efficient algorithm is presented for computing exact system and survival signatures of K-terminal reliability in undirected networks with unreliable edges. K-terminal reliability is defined as the probability that a subset K of the network nodes can communicate with each other. Signatures have several advantages over direct reliability calculation such as enabling certain stochastic comparisons of reliability between competing network topology designs, extremely fast repeat computation of network reliability for different edge reliabilities and computation of network reliability when failures of edges are exchangeable but not independent. Existing methods for computation of signatures for K-terminal network reliability require derivation of cut-sets or path-sets which is only feasible for small networks due to the computational expense. The new algorithm utilises binary decision diagrams, boundary set partition sets and simple array operations to efficiently compute signatures through a factorisation of the network edges. The performance and advantages of the algorithm are demonstrated through application to a set of benchmark networks and a sensor network from an underground mine.

Citation

Reed, S., Löfstrand, M., & Andrews, J. (2019). An efficient algorithm for computing exact system and survival signatures of K-terminal network reliability. Reliability Engineering and System Safety, 185, 429-439. https://doi.org/10.1016/j.ress.2019.01.011

• Journal Article Type: Article
• Acceptance Date: Jan 10, 2019
• Online Publication Date: Jan 14, 2019
• Publication Date: May 31, 2019
• Deposit Date: Jan 22, 2019
• Publicly Available Date: Jan 22, 2019
• Journal: Reliability Engineering & System Safety
• Print ISSN: 0951-8320
• Electronic ISSN: 1879-0836
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 185
• Pages: 429-439
• DOI: https://doi.org/10.1016/j.ress.2019.01.011
• Keywords: Industrial and manufacturing engineering; Safety, Risk, Reliability and quality
• Public URL: https://nottingham-repository.worktribe.com/output/1487971
• Publisher URL: https://www.sciencedirect.com/science/article/pii/S0951832018307907
• Additional Information: This article is maintained by: Elsevier; Article Title: An efficient algorithm for computing exact system and survival signatures of K-terminal network reliability; Journal Title: Reliability Engineering & System Safety; CrossRef DOI link to publisher maintained version: https://doi.org/10.1016/j.ress.2019.01.011; Content Type: article; Copyright: © 2019 Elsevier Ltd. All rights reserved.
• Contract Date: Jan 22, 2019