Novel direct algorithm for computing simultaneous all-level reliability of multistate flow networks

Wei-Chang Yeh

Reliability Engineering and System Safety, 2022, vol. 225, issue C

Abstract: Different types of networks, such as, Internet of Things, social networks, wireless sensor networks, transportation networks, and 4g/5G serve to benefit and help our daily lives. The multistate flow network (MFN) is used to model the network structures and applications. The level d reliability, Rd, of the MFN is the success probability of sending at least d units of integer flow from the nodes 1 to n and is a popular index for designing, managing, controlling, and evaluating MFNs. The traditional indirect algorithms must have all d-MPs (special connected vectors) or (d-1)-MCs (special disconnected vectors) first, and then use inclusion-exclusion technique (IET) or sum-of-disjoint product (SDP) in terms of found d-MPs or (d-1)-MCs to calculate Rd. The above four procedures are all NP-Hard and #P-Hard and cannot calculate Rd for d = 1, 2, …, dMAX simultaneously, that is, they can only calculate R1, R2, …, and RdMAX sequentially. Thus, in this study a novel algorithm is proposed to calculate the Rd directly for all d simultaneously, eliminating the need of using the above four procedures. The time complexity and demonstration of the proposed algorithm were analyzed with suitable examples. Furthermore, an experiment was conducted on 12 benchmark networks to validate the proposed algorithm.

Keywords: Multistate Flow Network (MFN); Reliability; All-levels; Binary-Addition-Tree Algorithm (BAT); The Maximum-flow algorithm; Inclusion-Exclusion Technique (IET); Sum-of-disjoint Product (SDP); d-MP; d-MC (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0951832022002630
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:reensy:v:225:y:2022:i:c:s0951832022002630

DOI: 10.1016/j.ress.2022.108623

Access Statistics for this article

Reliability Engineering and System Safety is currently edited by Carlos Guedes Soares

More articles in Reliability Engineering and System Safety from Elsevier
Bibliographic data for series maintained by Catherine Liu ().