Application of Binary Decision Diagrams in Time-Dependent Reliability Analysis
DOI:
https://doi.org/10.47839/ijc.23.3.3654Keywords:
binary decision diagram, GiNaC, probabilistic decision diagram, structure function, symbolic expression, TeDDy, time-dependent reliabilityAbstract
Binary Decision Diagrams (BDDs) are often used in specific types of reliability analysis known as topological (or structure) analysis and time-independent analysis. The previous focuses only on the analysis of system topology, which is defined by structure function. The latter takes into account the structure function together with the time-independent reliabilities of components that the system is composed of. However, the most interesting type of reliability analysis is time-dependent analysis in which reliabilities of the components are time-dependent functions. In this paper, we first present the development of a mathematical model of a non-repairable system composed of independent non-repairable components and explain the properties of this model from the point of view of time-dependent, time-independent, and topological reliability analysis. In the second part of the paper, we present and experimentally compare two methods for time-dependent reliability analysis of the considered mathematical model. The first method is based on the direct application of BDDs and we label it as a basic approach. The second, symbolic approach, combines BDDs with expression trees. The experimental comparison implemented using opensource C++ libraries TeDDy and GiNaC shows that the first method based on the basic approach is much faster than the second method using expression trees.
References
Y. Crama and P. Hammer, Boolean Functions: Theory, Algorithms, and Applications. Cambridge University Press, 2011.
R. Bryant, “Graph-based algorithms for boolean function manipulation,” IEEE Transactions on Computers, vol. C-35, no. 8, pp. 677–691, 1986.
C. Meinel and T. Theobald, Algorithms and Data Structures in VLSI Design. Berlin, Heidelberg, DE: Springer Berlin Heidelberg, 1998.
A. Deb, R. Wille, O. Keszöcze, S. Shirinzadeh, and R. Drechsler, “Synthesis of optical circuits using binary decision diagrams,” Integration, vol. 59, pp. 42–51, sep 2017.
T. Hadžic and J. N. Hooker, “Cost-bounded binary decision diagrams for ´ 0-1 programming,” in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, P. Van Hentenryck and L. Wolsey, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 84–98.
A. Rauzy, “Binary decision diagrams for reliability studies,” in Handbook of Performability Engineering, K. B. Misra, Ed. London, UK: Springer London, 2008, pp. 381–396.
E. Zaitseva, V. Levashenko, and J. Kostolny, “Importance analysis based on logical differential calculus and binary decision diagram,” Reliability Engineering & System Safety, vol. 138, pp. 135–144, jun 2015.
F. Somenzi, “Cudd: Cu decision diagram package,” https://github.com/ vscosta/cudd, 2005, accessed: 2023-07-20.
J. Lind-Nielsen, “Buddy – a binary decision diagram package,” https:// github.com/jgcoded/BuDDy, 2014, accessed: 2023-07-20.
M. Mrena, M. Kvassay, and E. Zaitseva, “Teddy: Templated decision diagram library,” SoftwareX, vol. 26, p. 101715, 2024.
A. K. Das and T. K. Roy, “Fractional order EOQ model with linear trend of time-dependent demand,” International Journal of Intelligent Systems and Applications, vol. 7, no. 3, pp. 44–53, feb 2015.
V. Kharchenko, Y. Ponochovnyi, A.-S. M. Q. Abdulmunem, and A. Boyarchuk, “Security and availability models for smart building automation systems,” International Journal of Computing, vol. 16, no. 4, pp. 194–202, dec 2017.
Rakhi and G. L.Pahuja, “Component Importance Measures based Risk and Reliability Analysis of Vehicular Ad Hoc Networks,” International Journal of Computer Network and Information Security, vol. 10, no. 10, pp. 38–45, oct 2018.
L. Ozirkovskyy, B. Volochiy, O. Shkiliuk, M. Zmysnyi, and P. Kazan, “Functional safety analysis of safety-critical system using state transition diagram,” Radioelectronic and Computer Systems, no. 2, pp. 145–158, may 2022.
T. Nakagawa, Stochastic Processes, ser. Springer Series in Reliability Engineering. London, UK: Springer London, 2011.
C. Bauer, A. Frink, and R. Kreckel, “Introduction to the ginac framework for symbolic computation within the c++ programming language,” Journal of Symbolic Computation, vol. 33, no. 1, pp. 1–12, 2002.
E. Babeshko, V. Kharchenko, K. Leontiiev, and E. Ruchkov, “Practical aspects of operating and analytical reliability assessment of FPGA-based I&C systems,” Radioelectronic and Computer Systems, no. 3, pp. 75–83, sep 2020.
H. Fesenko, V. Kharchenko, A. Sachenko, R. Hiromoto, and V. Kochan, “An internet of drone-based multi-version post-severe accident monitoring system: Structures and reliability,” in Dependable IoT for Human and Industry, V. Kharchenko, A. L. Kor, and A. Rucinski, Eds. New York: River Publishers, sep 2022, pp. 197–217.
Y. Sun, H. Fesenko, V. Kharchenko, L. Zhong, I. Kliushnikov, O. Illiashenko, O. Morozova, and A. Sachenko, “UAV and IoT-based systems for the monitoring of industrial facilities using digital twins: Methodology, reliability models, and application,” Sensors, vol. 22, no. 17, p. 6444, aug 2022.
E. Zio, “Reliability engineering: Old problems and new challenges,” Reliability Engineering & System Safety, vol. 94, no. 2, pp. 125–141, feb 2009.
M. Rausand and A. Høyland, System Reliability Theory, 2nd ed. John Wiley & Sons, Inc., 2004.
A. Lisnianski, I. Frenkel, and Y. Ding, Multi-state System Reliability Analysis and Optimization for Engineers and Industrial Managers. London, UK: Springer-Verlag London Ltd., 2010.
B. Natvig, Multistate Systems Reliability Theory with Applications, ser. Wiley Series in Probability and Statistics. Chichester, UK: John Wiley & Sons, Ltd, jan 2011.
W. Kuo and X. Zhu, Importance Measures in Reliability, Risk, and Optimization: Principles and Applications, 1st ed. Wiley Publishing, 2012.
M. Kvassay and E. Zaitseva, “Topological analysis of multi-state systems based on direct partial logic derivatives,” in Recent Advances in Multistate Systems Reliability, ser. Springer Series in Reliability Engineering, A. Lisnianski, I. Frenkel, and A. Karagrigoriou, Eds. Cham, CH: Springer International Publishing, 2018, pp. 265–281.
J. Newton and D. Verna, “A theoretical and numerical analysis of the worst-case size of reduced ordered binary decision diagrams,” ACM Trans. Comput. Logic, vol. 20, no. 1, jan 2019.
A. Srinivasan, T. Ham, S. Malik, and R. Brayton, “Algorithms for discrete function manipulation,” in 1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers, 1990, pp. 92–95.
S. Yanushkevich, D. Miller, V. Shmerko, and R. Stankovic, Decision Diagram Techniques for Micro- and Nanoelectronic Design Handbook. CRC Press, 2006.
S. Nagayama, A. Mishchenko, T. Sasao, and J. T. Butler, “Exact and heuristic minimization of the average path length in decision diagrams,” J. Multiple Valued Log. Soft Comput., vol. 11, pp. 437–465, 2005.
Y. Mo, L. Xing, and S. V. Amari, “A multiple-valued decision diagram based method for efficient reliability analysis of non-repairable phasedmission systems,” IEEE Transactions on Reliability, vol. 63, no. 1, pp. 320–330, 2014.
P. Rusnak, J. Rabcan, M. Kvassay, and V. G. Levashenko, “Timedependent reliability analysis based on structure function and logic differential calculus,” in International Conference on Dependability of Computer Systems, 2018.
S. Du, R. Kang, Z. Zeng, and E. Zio, “Time-dependent reliability assessment of a distributed generation system based on multi-valued decision diagrams and markov processes,” in Safety and Reliability – Theory and Applications. CRC Press, Jun. 2017.
T. van Dijk, Sylvan: multi-core decision diagrams. University of Twente, 7 2016.
K. Brace, R. Rudell, and R. Bryant, “Efficient implementation of a bdd package,” in 27th ACM/IEEE Design Automation Conference, 1990, pp. 40–45.
K. McElvain, “Iwls’93 benchmark set: Version 4.0,” Tech. Rep., May 1993.
E. Zaitseva and V. Levashenko, “Importance analysis by logical differential calculus,” Automation and Remote Control, vol. 74, 2013.
W.-C. Yeh, “A new algorithm for generating minimal cut sets in k-out-ofn networks,” Reliability Engineering & System Safety, vol. 91, no. 1, pp. 36–43, jan 2006.
W.-C. Yeh, “An improved algorithm for searching all minimal cuts in modified networks,” Reliability Engineering & System Safety, vol. 93, no. 7, pp. 1018–1024, jul 2008.
M. Forghani-elahabad and N. Kagan, “An approximate approach for reliability evaluation of a multistate flow network in terms of minimal cuts,” Journal of Computational Science, vol. 33, pp. 61–67, 2019.
M. Mrena, M. Kvassay, and S. Czapp, “Single and series of multi-valued decision diagrams in representation of structure function,” in Lecture Notes in Networks and Systems, vol. 484 LNNS, 2022, pp. 176–185.
P. Fišer, “Collection of digital design benchmarks,” https://ddd.fit.cvut.cz/ www/prj/Benchmarks/, 1991, accessed: 2023-10-31.
M. Kvassay, E. Zaitseva, V. Levashenko, and J. Kostolny, “Reliability analysis of multiple-outputs logic circuits based on structure function approach,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 36, no. 3, pp. 398–411, 2017.
A. Shrestha, L. Xing, and Y. Dai, “Decision diagram based methods and complexity analysis for multi-state systems,” IEEE Transactions on Reliability, vol. 59, no. 1, pp. 145–161, mar 2010.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
