Network Reliability

Sanjay K. Chaturvedi is currently working as an Associate Professor at Reliability Engineering Centre, Indian Institute of Technology, Kharagpur (WB) India. He received his Ph D. degree from Reliability Engineering Centre, IIT Kharagpur (India) in year 2003. He holds a Bachelor's degree in electrical engineering and Master's degree in system engineering and operations research, both from Indian Institute of Technology, Roorkee. He has research interests in the areas of reliability modeling and analysis, network reliability, life-data analysis, maintenance and optimization, and has done several consultancy projects, and delivered lectures in Indian industries in these areas. He has guided several Ph.Ds. and published papers in several international journals.

• Preface xiiiAcknowledgements xvii1 Introduction 11.1 Graph Theory: A Tool for Reliability Evaluation 21.1.1 Undirected Networks 41.1.2 Directed Networks 41.1.3 Mixed Networks 51.2 Large versus Complex System 71.2.1 Large System 71.2.2 Complex System 71.2.3 Large and Complex System 91.3 Network Reliability Measures: Deterministic versus Probabilistic 91.3.1 Terminal-pair Reliability Measure 111.3.2 All-Terminal Reliability Measure 121.3.3 k-terminal Reliability Measure 121.4 Common Assumptions 121.5 Approaches for NSP Network Reliability Evaluation 131.5.1 Non Path or Cut Sets Based Techniques 141.5.1.1 State Enumeration Technique 141.5.1.2 Network Decomposition Technique 181.5.1.3 Probability Transformation Technique 191.5.1.4 Binary Decision Diagram Based Technique 201.5.2 Minimal POC Based Techniques 211.5.2.1 Inclusion-Exclusion Technique 211.5.2.2 Monte-Carlo Simulation Based Technique 221.5.2.3 Domination Theory Based Technique 231.5.2.4 Reliability Bounds Technique 241.5.2.5 Sum-of-disjoint Product Based Technique 25Exercises 26References 272 Reliability Evaluation of General SP-Networks 312.1 Notation and Assumptions 332.2 Unit-Reliability and Failure Models 342.2.1 Constant-Hazard Model 352.2.2 Linear-Hazard Model 352.2.3 Weibull-Hazard Model 352.2.4 Extreme Value-Hazard Model 362.3 Module Representation of Reliability Graphs 362.3.1 Single-Unit Module 362.3.2 Multi-Unit Module 362.3.2.1 Series Model 372.3.2.2 Parallel Model 382.3.2.3 Standby Model 392.3.2.4 k-out-of-m Model 412.4 Misra Matrix Method 442.5 Algorithm 452.6 Implementation and Documentation 552.6.1 Main Module 552.6.2 Function formCmat 562.6.3 Function processCmat 582.6.4 Function systDetail 582.7 Remarks 58Exercises 59References 603 Path Sets Enumeration 633.1 Enumeration of (s, f) Connected Path Sets 643.1.1 Method 1: Using Powers of Connection matrix 653.1.2 Method 2: Traversing Through Connection Matrix 673.1.3 Method 3: Using Incidence Matrix 693.2 Enumeration of All-node Connected Path Sets: Spanning Tree 733.2.1 Method 1: Using the Cartesian Product of the Node Cut Sets 743.2.2 Method 2: Using the Incidence Matrix 753.3 Number of Spanning Trees 843.3.1 Matrix Tree Theorem 843.4 Enumeration of k-node Connected Path Sets: k-Trees 86Appendix 3A.1: Enumeration of Path Sets Algorithm, Illustration and Matlab® Code Notation 88Appendix 3A.2: Sample program I/O for Figure 3A.1 Contents ix 97Exercises 100References 1014 Cut Sets Enumeration 1034.1 (s, f) Cut Sets Enumeration 1044.1.1 Method 1: Using Connection Matrix 1044.1.2 Method 2: Using Minimal Path Sets 1064.1.2.1 Using Set-theoretic Product of Path Sets 1064.1.2.2 Using Path Sets Matrix 1074.1.2.3 Using Path Sets Inversion 1084.2 Global Cut Sets Enumeration 1094.2.1 Testing Connectivity of a Specified Node Set 1104.2.1.1 Node Fusion Technique 1104.2.2 Generation of Node Set Combination from its Lower Order Node-Sets 1124.2.3 Checking Validity of a Node Set 1124.2.4 Formation of Cutset 1134.2.5 General Algorithm to Enumerate Minimal Cutsets for a Reliability Measure 113Appendix 4A.1: Node Fusion Technique and Generation of Node Set Combination 123Appendix 4A.2: Code for Checking Validity of a Node Set and Converting Node-Sets into Link Cutsets 124Appendix 4A.3: Sample Program I/O for Network Graph of Figure 4.3 126Appendix 4A.4: g-Terminal Reliability EvaluationProgram Sample I/O for Example of Figure 4.3 128Appendix 4A.5: Results are provided by the program (output of g-reliability expression for the Figure 4.3for method HM-1 of (Chaturvedi & Misra, 2002). 129Exercises 130References 1315 Reliability Evaluation using MVI Techniques 1335.1 Notation and Assumptions 1345.2 Preliminaries 1355.2.1 Definitions 1355.3 MVI Methods 1375.3.1 Method 1: KDH88 1375.3.2 Method 2: CAREL 1395.3.3 Comparison between KDH88 and CAREL 1445.4 Method 3: Hybrid Methods-HM 1475.4.1 An Alternative Representation of Path or Cut Sets 1475.4.2 Hybrid Methods (HM) 1495.4.2.1 HM-1 1495.4.2.2 HM-2 1495.5 Applying HM-1 and HM-2 1495.5.1 Applying HM-1 1505.5.2 Applying HM-2 1515.5.3 Complete Solution to Example 5.2 1525.6 Global and k-terminal Reliability with SDP Approach 1595.6.1 All-terminal Reliability Evaluation 1615.6.2 Characteristics of a g-reliability Expression 1645.6.3 k-terminal Reliability Evaluation 1645.6.4 Number of k-trees 1675.7 Unreliability with SDP Approach 1695.8 Some Suggested Guidelines 1715.8.1 Directed Network Graph 1715.8.2 Undirected Network Graph 172Appendix 5A.1: Program output of g-reliability expression for the Figure 5.1(b). 173Appendix 5A.2: Program output of k-terminal reliability expression for Figure 5.1(b). 179Appendix 5A.3: Program output of k-terminal reliability expression for Figure 5.1(b). 181Exercises 183References 1856 Unified Framework and Capacitated Network Reliability 1876.1 The Unified Framework 1886.2 Capacitated Reliability Measure: An Introduction 1896.2.1 Some Related Definitions 1916.2.1.1 Minimal Cutset and Subset Cut Group 1916.2.1.2 External Redundant Subset Cut Group 1916.2.1.3 Internal Redundant Subset Cut Group 1926.2.1.4 Invalid Cut Set Cut Group 1926.2.1.5 Description of the Algorithm 1926.3 Algorithm Description 1926.3.1 Equations: The idea 1936.3.2 Is Cut itself a SCG or does it need its Subsets Enumeration? 1946.3.3 What Initial Order? 1946.3.4 Efficient enumeration of particular order SCG of a minimal cut 1976.3.5 External or Both External/ Internal Redundancy Removal 1976.3.6 Internal Redundancy Removal 1996.4 The CRR Evaluation Algorithm 2006.5 A Complete Example 2026.6 Experimental Results, Comparison and Discussion 207References 2127 A LAN and Water Distribution Network: Case Studies 2137.1 Case Study-I: IIT Kharagpur LAN Network 2137.1.1 k-Terminal and global reliability evaluation for hostel area of IIT Kharagpur LAN 2157.1.2 All terminal reliability evaluation for academic area of LAN 2157.1.3 All terminal reliability evaluation for IIT Kharagpur LAN network 2157.2 Case Study-II: Real-Type of Large Size Unsaturated Water Distribution Networks 219References 222Epilogue 223References 225Bibliography 227Index 235