IDEAS home Printed from https://ideas.repec.org/a/eee/reensy/v131y2014icp83-93.html
   My bibliography  Save this article

Choosing a heuristic and root node for edge ordering in BDD-based network reliability analysis

Author

Listed:
  • Mo, Yuchang
  • Xing, Liudong
  • Zhong, Farong
  • Pan, Zhusheng
  • Chen, Zhongyu

Abstract

In the Binary Decision Diagram (BDD)-based network reliability analysis, heuristics have been widely used to obtain a reasonably good ordering of edge variables. Orderings generated using different heuristics can lead to dramatically different sizes of BDDs, and thus dramatically different running times and memory usages for the analysis of the same network. Unfortunately, due to the nature of the ordering problem (i.e., being an NP-complete problem) no formal guidelines or rules are available for choosing a good heuristic or for choosing a high-performance root node to perform edge searching using a particular heuristic. In this work, we make novel contributions by proposing heuristic and root node selection methods based on the concept of boundary sets for the BDD-based network reliability analysis. Empirical studies show that the proposed selection methods can help to generate high-performance edge ordering for most of studied cases, enabling the efficient BDD-based reliability analysis of large-scale networks. The proposed methods are demonstrated on different types of networks, including square lattice networks, torus lattice networks and de Bruijn networks.

Suggested Citation

  • Mo, Yuchang & Xing, Liudong & Zhong, Farong & Pan, Zhusheng & Chen, Zhongyu, 2014. "Choosing a heuristic and root node for edge ordering in BDD-based network reliability analysis," Reliability Engineering and System Safety, Elsevier, vol. 131(C), pages 83-93.
    • Handle: RePEc:eee:reensy:v:131:y:2014:i:c:p:83-93
    DOI: 10.1016/j.ress.2014.06.025
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0951832014001550
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ress.2014.06.025?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Zdravko I. Botev & Pierre L'Ecuyer & Gerardo Rubino & Richard Simard & Bruno Tuffin, 2013. "Static Network Reliability Estimation via Generalized Splitting," INFORMS Journal on Computing, INFORMS, vol. 25(1), pages 56-71, February.
    2. Yeh, Wei-Chang, 2007. "An improved sum-of-disjoint-products technique for the symbolic network reliability analysis with known minimal paths," Reliability Engineering and System Safety, Elsevier, vol. 92(2), pages 260-268.
    3. Xing, Liudong & Levitin, Gregory, 2013. "BDD-based reliability evaluation of phased-mission systems with internal/external common-cause failures," Reliability Engineering and System Safety, Elsevier, vol. 112(C), pages 145-153.
    4. Peng, Rui & Mo, Huadong & Xie, Min & Levitin, Gregory, 2013. "Optimal structure of multi-state systems with multi-fault coverage," Reliability Engineering and System Safety, Elsevier, vol. 119(C), pages 18-25.
    5. Zhusheng Pan & Yuchang Mo & Liudong Xing & Jianmin Han, 2014. "New insights into breadth-first search edge ordering of regular networks for terminal-pair reliability analysis," Journal of Risk and Reliability, , vol. 228(1), pages 83-92, February.
    6. Kang, Won-Hee & Song, Junho & Gardoni, Paolo, 2008. "Matrix-based system reliability method and applications to bridge networks," Reliability Engineering and System Safety, Elsevier, vol. 93(11), pages 1584-1593.
    7. Kim, Youngsuk & Kang, Won-Hee, 2013. "Network reliability analysis of complex systems using a non-simulation-based method," Reliability Engineering and System Safety, Elsevier, vol. 110(C), pages 80-88.
    8. Qingqing Zhai & Rui Peng & Liudong Xing & Jun Yang, 2013. "Binary decision diagram-based reliability evaluation of k-out-of-(n + k) warm standby systems subject to fault-level coverage," Journal of Risk and Reliability, , vol. 227(5), pages 540-548, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Wu, Baichao & Sun, Long, 2024. "A novel layer-by-layer recursive decomposition algorithm for calculation of network reliability," Reliability Engineering and System Safety, Elsevier, vol. 244(C).
    2. Kawahara, Jun & Sonoda, Koki & Inoue, Takeru & Kasahara, Shoji, 2019. "Efficient construction of binary decision diagrams for network reliability with imperfect vertices," Reliability Engineering and System Safety, Elsevier, vol. 188(C), pages 142-154.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Li, Jian & Dueñas-Osorio, Leonardo & Chen, Changkun & Shi, Congling, 2016. "Connectivity reliability and topological controllability of infrastructure networks: A comparative assessment," Reliability Engineering and System Safety, Elsevier, vol. 156(C), pages 24-33.
    2. Kawahara, Jun & Sonoda, Koki & Inoue, Takeru & Kasahara, Shoji, 2019. "Efficient construction of binary decision diagrams for network reliability with imperfect vertices," Reliability Engineering and System Safety, Elsevier, vol. 188(C), pages 142-154.
    3. Bistouni, Fathollah & Jahanshahi, Mohsen, 2014. "Analyzing the reliability of shuffle-exchange networks using reliability block diagrams," Reliability Engineering and System Safety, Elsevier, vol. 132(C), pages 97-106.
    4. Dui, Hongyan & Li, Shumin & Xing, Liudong & Liu, Hanlin, 2019. "System performance-based joint importance analysis guided maintenance for repairable systems," Reliability Engineering and System Safety, Elsevier, vol. 186(C), pages 162-175.
    5. Dehghani, Nariman L. & Zamanian, Soroush & Shafieezadeh, Abdollah, 2021. "Adaptive network reliability analysis: Methodology and applications to power grid," Reliability Engineering and System Safety, Elsevier, vol. 216(C).
    6. Hu, Bin & Seiler, Peter, 2015. "Pivotal decomposition for reliability analysis of fault tolerant control systems on unmanned aerial vehicles," Reliability Engineering and System Safety, Elsevier, vol. 140(C), pages 130-141.
    7. Bistouni, Fathollah & Jahanshahi, Mohsen, 2017. "Remove and contraction: A novel method for calculating the reliability of Ethernet ring mesh networks," Reliability Engineering and System Safety, Elsevier, vol. 167(C), pages 362-375.
    8. Zhang, Chao & Xu, Xin & Dui, Hongyan, 2020. "Analysis of network cascading failure based on the cluster aggregation in cyber-physical systems," Reliability Engineering and System Safety, Elsevier, vol. 202(C).
    9. Vaibhav Gaur & Om Prakash Yadav & Gunjan Soni & Ajay Pal Singh Rathore, 2021. "A literature review on network reliability analysis and its engineering applications," Journal of Risk and Reliability, , vol. 235(2), pages 167-181, April.
    10. Sadoughi, Mohammadkazem & Li, Meng & Hu, Chao, 2018. "Multivariate system reliability analysis considering highly nonlinear and dependent safety events," Reliability Engineering and System Safety, Elsevier, vol. 180(C), pages 189-200.
    11. You Zhou & Chuan He, 2022. "A Review on Reliability of Integrated Electricity-Gas System," Energies, MDPI, vol. 15(18), pages 1-22, September.
    12. Byun, Ji-Eun & Noh, Hee-Min & Song, Junho, 2017. "Reliability growth analysis of k-out-of-N systems using matrix-based system reliability method," Reliability Engineering and System Safety, Elsevier, vol. 165(C), pages 410-421.
    13. Jafary, Bentolhoda & Fiondella, Lance, 2016. "A universal generating function-based multi-state system performance model subject to correlated failures," Reliability Engineering and System Safety, Elsevier, vol. 152(C), pages 16-27.
    14. Thi-Phuong Nguyen, 2021. "Assess the Impacts of Discount Policies on the Reliability of a Stochastic Air Transport Network," Mathematics, MDPI, vol. 9(9), pages 1-13, April.
    15. Peng, Rui & Wu, Di & Xiao, Hui & Xing, Liudong & Gao, Kaiye, 2019. "Redundancy versus protection for a non-reparable phased-mission system subject to external impacts," Reliability Engineering and System Safety, Elsevier, vol. 191(C).
    16. Lin, Yi-Kuei, 2010. "Calculation of minimal capacity vectors through k minimal paths under budget and time constraints," European Journal of Operational Research, Elsevier, vol. 200(1), pages 160-169, January.
    17. Dharmaraja, S. & Vinayak, Resham & Trivedi, Kishor S., 2016. "Reliability and survivability of vehicular ad hoc networks: An analytical approach," Reliability Engineering and System Safety, Elsevier, vol. 153(C), pages 28-38.
    18. Sungsik Yoon & Young-Joo Lee & Hyung-Jo Jung, 2021. "Flow-based seismic risk assessment of a water transmission network employing probabilistic seismic hazard analysis," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 105(2), pages 1231-1254, January.
    19. Kim, Youngsuk & Kang, Won-Hee, 2013. "Network reliability analysis of complex systems using a non-simulation-based method," Reliability Engineering and System Safety, Elsevier, vol. 110(C), pages 80-88.
    20. Monfared, M.A.S. & Rezazadeh, Masoumeh & Alipour, Zohreh, 2022. "Road networks reliability estimations and optimizations: A Bi-directional bottom-up, top-down approach," Reliability Engineering and System Safety, Elsevier, vol. 222(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:reensy:v:131:y:2014:i:c:p:83-93. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/reliability-engineering-and-system-safety .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.