Binary Decision Diagrams and Extensions for System Reliability Analysis (eBook)

Liudong Xing, Suprasad V. Amari (Autoren)

eBook Download: EPUB

2015
John Wiley & Sons (Verlag)
9781119178002 (ISBN)

Infos

Recent advances in science and technology have made modern computing and engineering systems more powerful and sophisticated than ever. The increasing complexity and scale imply that system reliability problems not only continue to be a challenge but also require more efficient models and solutions. This is the first book systematically covering the state-of-the-art binary decision diagrams and their extended models, which can provide efficient and exact solutions to reliability analysis of large and complex systems. The book provides both basic concepts and detailed algorithms for modelling and evaluating reliability of a wide range of complex systems, such as multi-state systems, phased-mission systems, fault-tolerant systems with imperfect fault coverage, systems with common-cause failures, systems with disjoint failures, and systems with functional dependent failures. These types of systems abound in safety-critical or mission-critical applications such as aerospace, circuits, power systems, medical systems, telecommunication systems, transmission systems, traffic light systems, data storage systems, and etc. The book provides both small-scale illustrative examples and large-scale benchmark examples to demonstrate broad applications and advantages of different decision diagrams based methods for complex system reliability analysis. Other measures including component importance and failure frequency are also covered. A rich set of references is cited in the book, providing helpful resources for readers to pursue further research and study of the topics. The target audience of the book is reliability and safety engineers or researchers. The book can serve as a textbook on system reliability analysis. It can also serve as a tutorial and reference book on decision diagrams, multi-state systems, phased-mission systems, and imperfect fault coverage models.

Autor

Liudong Xing is a tenured professor in the Department of Electrical and Computer Engineering at the University of Massachusetts (UMass), Dartmouth. She received her PhD degree in Electrical Engineering from the University of Virginia, Charlottesville in 2002. Her current research focuses on reliability modelling and analysis of complex systems and networks. She has authored or co-authored over 190 technical papers. She is the recipient of the Leo M. Sullivan Teacher of the Year Award (2014), Scholar of the Year Award (2010), and Outstanding Women Award (2011) of UMass Dartmouth, as well as the IEEE Region 1 Technological Innovation (Academic) Award (2007). She is also the co-recipient of the Best Paper Award at the IEEE International Conference on Networking, Architecture, and Storage in 2009. She is a senior member of IEEE. Suprasad V. Amari received the M.S. and Ph.D. degrees in Reliability Engineering from the Indian Institute of Technology, Kharagpur, India. He is a senior technical staff member at Relyence Corporation. Prior to joining Relyence, he has served as a Technical Fellow at Parametric Technology Corporation (PTC) for 14 years, where he was responsible for research, design, and development of PTC's reliability modeling and analysis software products. He has authored or coauthored 6 book chapters in Springer Handbooks and about 90 technical papers in the area of reliability engineering. He has been actively involved with Annual Reliability and Maintainability Symposium (RAMS) and currently serving as the Vice General Chair. He has received the 2013 RAMS Best Paper Award from American Society for Quality (ASQ) Reliability Division, the 2009 Stan Oftshun Award from the Society of Reliability Engineers (SRE) and the 2009 William A.J. Golomski Award from the Institute of Industrial Engineers (IIE). He is a senior member of ASQ, IEEE, and IIE. He is a member of ACM, SAE and SRE and an ASQ-certified Reliability Engineer.

Inhalt

Preface xiii

Nomenclature xix

1 Introduction 1

1.1 Historical Developments 1

1.2 Reliability and Safety Applications 4

2 Basic Reliability Theory and Models 7

2.1 Probabiltiy Concepts 7

2.2 Reliability Measures 14

2.3 Fault Tree Analysis 17

3 Fundamentals of Binary Decision Diagrams 33

3.1 Preliminaries 34

3.2 Basic Concepts 34

3.3 BDD Construction 35

3.4 BDD Evaluation 42

3.5 BDD-Based Software Package 44

4 Application of BDD to Binary-State Systems 45

4.1 Network Reliability Analysis 45

4.2 Event Tree Analysis 47

4.3 Failure Frequency Analysis 50

4.4 Importance Measures and Analysis 54

4.5 Modularization Methods 60

4.6 Non-Coherent Systems 60

4.7 Disjoint Failures 65

4.8 Dependent Failures 68

5 Phased-Mission Systems 73

5.1 System Description 74

5.2 Rules of Phase Algebra 75

5.3 BDD-Based Method for PMS Analysis 76

5.4 Mission Performance Analysis 81

6 Multi-State Systems 85

6.1 Assumptions 86

6.2 An Illustrative Example 86

6.3 MSS Representation 87

6.4 Multi-State BDD (MBDD) 90

6.5 Logarithmically-Encoded BDD (LBDD) 94

6.6 Multi-State Multi-Valued Decision Diagrams (MMDD) 98

6.7 Performance Evaluation and Benchmarks 102

6.8 Summary 117

7 Fault Tolerant Systems and Coverage Models 119

7.1 Basic Types 120

7.2 Imperfect Coverage Model 122

7.3 Applications to Binary-State Systems 123

7.4 Applications to Multi-State Systems 129

7.5 Applications to Phased-Mission Systems 133

7.6 Summary 139

8 Shared Decision Diagrams 143

8.1 Multi-Rooted Decision Diagrams 144

8.2 Multi-Terminal Decision Diagrams 148

8.3 Performance Study on Multi-State Systems 151

8.4 Application to Phased-Mission Systems 163

8.5 Application to Multi-State k-out-of-n Systems 168

8.6 Importance Measures 176

8.7 Failure Frequency Based Measures 180

8.8 Summary 183

Conclusions 185

References 187

Index 205

Textauszug

Preface

Recent advances in science and technology have made modern engineering systems more powerful and sophisticated than ever. This decade particularly has witnessed several disruptive technological innovations in distributed and cloud computing, wireless sensor networks, internet of things, big data analytics, autonomous vehicles, space exploration that has pushed the limits of internet and mobile computing technologies beyond our imagination. The increasing level of sophistication and automation in engineering systems not only increases the complexity of these systems, but also increases the dependencies among components within these systems, and as a result, reliability analysis of these systems becomes more challenging than ever. At the same time, an accurate reliability modeling and analysis is crucial to verify whether a system has met desired reliability and availability requirements, as well as to determine optimal cost-effective design policies that maximize system reliability and/or performance.

Reliability of a system depends on reliabilities of its components and the system design configuration that includes the assembly of its components. In general, both the system and its components can have multiple failure modes and performance levels, and they can operate at different environments, stress and demand levels at different phases during their entire mission or life time. As a result, the component failure behavior and system configuration can vary with phases. In most applications, the relationship between a system and its components can be represented using combinatorial models where the system state can be represented using a logic function of its components states. This function that maps the set of component states to the system state is known as a system structure function, which is dependent on the system configuration. Once the system structure function and reliabilities of the system components are determined, traditionally the system reliability was determined using truth-tables, pathsets/cut-sets based on inclusion-exclusion expansion or sum-of-disjoint products representation of the structure function. However, all these traditional reliability evaluation methods are computationally inefficient and are limited to small scale models or problems. To solve large models, bounding and approximating methods have been used. However, finding good bounds and approximations were still considered as a challenging problem for several decades. This situation has changed after the seminal work by Bryant on binary decision diagrams (BDD) in 1986.

BDD is the state-of-the-art data structure, which is primarily based on Shannon’s decomposition theorem, used to encode and manipulate Boolean functions. The full potential for efficient algorithms based on the data structure of BDD is realized by Bryant’s seminal work in 1986. Since then, BDD and its extended formats have been extensively applied in several fields including formal circuit verification and symbolic model checking. The success of BDD in these areas and the important applications of Boolean functions in system reliability analysis have stimulated considerable efforts to adapt BDD and its extended formats to reliability analysis of complex systems since 1993. These efforts have been firstly expended in reliability analysis of binary-state single-phase systems in which both the system and components exhibit only two states: operational or failed and their behaviors do not change throughout the mission. Many studies showed that in most cases, the BDD-based method requires less memory and computational time than other reliability analysis methods. Subsequently, various forms of decision diagrams have become the state-of-the-art combinatorial models for efficient reliability analysis of a wide range of complex systems, such as phased-mission systems, multi-state systems, fault-tolerant systems with imperfect fault coverage, systems with common-cause failures, and systems with functional dependent failures. These types of systems abound in safety-critical or mission-critical applications such as aerospace, circuits, power systems, medical systems, telecommunication systems, transmission systems, traffic light systems, data storage systems, and etc.

The topic of the book “Binary Decision Diagrams and Extensions for System Reliability Analysis” has gained much attention in the reliability and safety community. Several commercial reliability software vendors and research groups have started implementing these methods. Several tutorials on this topic have been presented at various international reliability and system safety conferences. The importance of this topic is also mentioned in the latest handbooks on fault tree analysis, safety and reliability analysis, and performability analysis. Research articles on this subject are continuously being published in peer-reviewed scholarly journals and conference proceedings. With the increased and sustained interest in this subject, it is a right time to bring the first book on this topic.

The purpose of this book is to provide a comprehensive coverage of binary decision diagrams and their extensions in solving complex reliability problems. In the Introduction, the book briefly describes the historical developments of BDD and its extended formats and discusses how they are related to reliability and safety applications. Chapter 2 introduces basic probability concepts that are relevant to the study of reliability, various reliability measures, and fault tree analysis. Chapter 3 discusses fundamentals of BDD including preliminaries, basic concepts, BDD construction, BDD evaluation, and existing software packages. Different strategies for variable orderings and their impact on BDD sizes are also discussed. Chapter 4 discusses the BDD-based binary-state reliability models and analysis with an emphasis on network reliability analysis, event tree analysis, failure frequency analysis, and important measures and analysis. The chapter also presents methods for modularization, non-coherent systems, and systems consisting of disjoint or dependent failures.

Chapter 5 introduces the application of BDD to the reliability analysis of phased-mission systems (PMS), in which multiple non-overlapping phases must be accomplished in sequence. During each phase, a PMS has to accomplish a specified task and may be subject to different stresses and environmental conditions as well as different reliability requirements. Thus, system structure function and component failure behavior may change from phase to phase. This dynamic behavior usually requires a distinct model for each phase of the mission in the reliability analysis. Further complicating the analysis are s-dependencies across the phases for a given component. For example, the state of a component at the beginning of a new phase is identical to its state at the end of the previous phase in a non-repairable PMS. This chapter explains a phase algebra-based BDD method to consider all these dynamics and dependencies in the reliability analysis of PMS.

As another application of decision diagrams in system reliability analysis, Chapter 6 explains multi-state systems (MSS), and their analysis using decision diagrams. MSSs are systems in which both the system and its components may exhibit multiple performance levels (or states) varying from perfect operation to complete failure. As compared to the analysis of binary-state systems, the unique challenge of analyzing MSSs arises from dependencies among different states of the same component, i.e., intra-component state dependencies. This chapter explains three different forms of decision diagrams to address the state dependencies in the MSS analysis: multi-state BDD (MBDD), logarithmically-encoded BDD (LBDD), and multi-state multi-valued decision diagrams (MMDD). Performances of these three methods are also discussed and compared in this chapter.

Chapter 7 presents basic concepts and types of imperfect fault coverage models and fault tolerant systems. Decision diagrams based methods are discussed for considering imperfect fault coverage in reliability analysis of binary-state systems, multi-state systems, and phased-mission systems.

Chapter 8 discusses shared decision diagrams and their advantages in storage requirement, model construction, and model evaluation. Both multi-rooted decision diagrams and multi-terminal decision diagrams are discussed. Applications of these models in solving multi-state systems, phased-mission systems and multi-state k-out-of-n systems with non-identical components are presented. This chapter also presents methods for evaluating multi-state component importance measures as well as failure frequency-based measures of multi-state systems.

Finally, Chapter 9 provides summary and conclusions on binary decision diagrams and their extensions for system reliability analysis.

The book has the following distinct features:

• It is the first book on the topic of reliability analysis using binary decision diagrams and their extensions.
• It provides basic concepts as well as detailed algorithms for reliability analysis of different types of systems using binary decision diagrams and their extended formats.
• It provides a comprehensive treatment on phased-mission systems, multi-state systems, and imperfect fault coverage models.
• It covers several system performance measures including system reliability, failure frequency, and component importance measures.
• It includes both small-scale illustrative examples and large-scale benchmark examples to demonstrate broad applications and advantages of different decision diagrams based methods for complex system reliability analysis.
• It covers recent advances in binary...

Produkt-Details

• Erscheint lt. Verlag: 5.6.2015
• Reihe/Serie: Performability Engineering Series
• Reihe/Serie: Performability Engineering Series
• Reihe/Serie: Performability Engineering Series
• Sprache: englisch
• Themenwelt: Technik ► Elektrotechnik / Energietechnik
• Themenwelt: Technik ► Maschinenbau
• Schlagworte: analysis fundamentals • application • BDD • binary • binarystate • Decision • dependent • Description • Diagrams • Electrical & Electronics Engineering • Elektrotechnik u. Elektronik • Event • failure frequency • Industrial Engineering • Industrial Engineering / Quality Control • Industrielle Verfahrenstechnik • Introduction • Method • Network • package • phasedmission • Qualität • Qualitätssicherung • Qualitätssicherung i. d. Industriellen Verfahrenstechnik • Qualität u. Zuverlässigkeit • Qualität • Qualitätssicherung • Qualitätssicherung i. d. Industriellen Verfahrenstechnik • Qualität u. Zuverlässigkeit • Quality & Reliability • Reliability • safety applications basic • Software • Systems • Systems Engineering & Management • Systemtechnik • Systemtechnik u. -management
• ISBN-13: 9781119178002 / 9781119178002