Survival from Disaster: Interdependencies Management in Critical Infrastructure Networks by DeTao Mao Ele. Eng., Xi'an Jiaotong University, 1998 M.E.E., Tsinghua University, 2001 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in The Faculty of Graduate Studies (Electrical and Computer Engineering) The University of British Columbia (Vancouver) August 2009 © DeTao Mao 2009 Abstract Today’s critical infrastructure networks are becoming increasingly interdependent. The complexity of these interdependencies has created a new dimension of vulnerability, making the whole system very fragile under unexpected events. To make the whole system more resilient during disasters, the Joint Infrastructure Interdependencies Research Program (JIIRP), aimed at developing methods for reducing its vulnerabilities. As part of the research work in JIIRP, this thesis mainly consists of three sections: • (I) Interdependencies Control Strategy (ICS): Since to prevent all vulnerabilities would be intractable, an interdependencies control strategy, which can help to maintain the survival of the critical services is proposed in Chapter 2. A generalized adjacency matrix (GAM) is proposed to represent the physical interdependencies among infrastructure networks. By computation of GAM, decision making for ICS can be made more eﬀective. Moreover, measures for improving survivability of the system are proposed. ICS application to a case study at the UBC campus is detailed in Chapter 3, its eﬀectiveness during the response stage and the recovery stage of the emergency management cycle are demonstrated. • (II) Identiﬁcation of Cascading Pathways for Mitigating Snow-Caused Power Outages : Since most of the present de-icing and anti-icing methods are not fully developed for industrial applications, building a power network that can tolerate any snow storm would be infeasible. In Chapter 4, based on investigation of Vancouver’s power outage in November 2006, a dependency network has been built to represent how the cascading pathways unfolded during this disaster. The eﬀects of a changed climate, the causalities and their consequences are illustrated by this model. Through analyses of the dependency network, we propose a systematic strategy to mitigate the impacts of a snow storm to power systems. ii Abstract • (III) Contributions to I2Sim: I2Sim is a simulator which was developed to simulate disasters and to develop strategies for dealing with emergencies (Appendix A). The author’s contributions to I2Sim are: (a) the modelling and implementation of methods to represent complex cells with multi-input and multi-output (Appendix B); (b)integration of the cluster demon into one single machine; (c) development of a library of functions on GAM operations(Appendix C). iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv Co-authorship Statement . . . . . . . . . . . . . . . . . . . . . . . xv 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Literature Review . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Work on Infrastructure Interdependency Modelling . 1.3.2 Work Based on Graph theory . . . . . . . . . . . . 1.3.3 Work on Vulnerability Analysis and Risk Assessment 1.4 Research Objectives . . . . . . . . . . . . . . . . . . . . . . 1.5 Outline of the Thesis . . . . . . . . . . . . . . . . . . . . . . 1.6 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Interdependencies Control Strategy . . . . . . . . . . . . . . 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Representation of Multi-arc Directed Physical Independencies by the Generalized Adjacency Matrix (GAM) . . . . . . . . . 2.2.1 Algebraic Operation and Logic Rules for GAM . . . . 2.2.2 Further Information Abstraction Based on GAM Computation . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 Advantages of Interdependency Analysis Based on GAM iv 1 1 2 3 3 4 4 5 6 8 12 12 15 15 16 18 Table of Contents 2.3 Interdependencies Control Based on GAM . . . . . . . . . . . 2.3.1 Brief Introduction to Emergency Management . . . . 2.3.2 Survivability Index of an Island (SII) . . . . . . . . . . 2.3.3 Description of Interdependencies Control Strategy . . 2.3.4 Measures for Improving SII in Emergency Management Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . . Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 19 20 20 22 23 24 25 3 Survival from Disaster by Interdependencies Management 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Representation of Modellable Physical Independencies by the Generalized Adjacency Matrix (GAM) . . . . . . . . . . . . . 3.2.1 Operation Rules for GAM . . . . . . . . . . . . . . . . 3.2.2 System Information Abstracted by GAM Computation 3.2.3 Advantages of GAM-based Interdependency Analysis . 3.3 Interdependencies Control Strategy (ICS) Based on GAM . . 3.3.1 Basic Introduction to Emergency Management . . . . 3.3.2 Survivability Index of an Island (SII) . . . . . . . . . . 3.3.3 Interdependencies Control Strategy . . . . . . . . . . . 3.3.4 Measures for Improving SII . . . . . . . . . . . . . . . 3.4 Application of ICS on the UBC Campus Case . . . . . . . . . 3.4.1 Scenario Description . . . . . . . . . . . . . . . . . . . 3.4.2 ICS-based Decision Making Activity during Emergency and Recovery State . . . . . . . . . . . . . . . . . . . . 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 27 2.4 2.5 2.6 4 Identifying Cascading Pathways for Power Outage Mitigation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Investigation on Vancouver’s 2006 Snow-Caused Power Outage 4.2.1 Several Root Causes Introduced by Changed Climate 4.2.2 Unchanged Policies of Vegetation Management by BC Hydro . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.3 Related Weather Factors Aﬀecting Ice Accretion on Overhead Wires . . . . . . . . . . . . . . . . . . . . . 4.2.4 Impacted Critical Infrastructure Networks . . . . . . . 4.2.5 Dependency Network Representation for the Power Outage in Vancouver 2006 . . . . . . . . . . . . . . . . v 28 28 30 35 36 36 37 38 39 40 41 43 46 48 50 50 51 52 54 54 55 55 Table of Contents C Matlab Code for the Library on the Operators of C.1 A Library of Functions for GAM Operation . . . . C.1.1 Generalized “And” . . . . . . . . . . . . . . C.1.2 Generalized “Multiply” for Matrixes . . . . C.1.3 Generalized “Multiply” for Vectors . . . . . C.1.4 SCC Checking and Detecting . . . . . . . . C.1.5 Diagonal Elements Resetting . . . . . . . . C.1.6 Compressing SCCs . . . . . . . . . . . . . . C.1.7 Substraction between SCCs . . . . . . . . . C.1.8 GAM Matrix Checking . . . . . . . . . . . C.1.9 Subset Detection of a SCCs . . . . . . . . . C.1.10 Find Subsets of SCCs . . . . . . . . . . . . C.1.11 Display SCCs . . . . . . . . . . . . . . . . . C.1.12 Compressed GAM Veriﬁcation . . . . . . . C.1.13 Find Out All Pathways . . . . . . . . . . . C.1.14 Display All Pathways . . . . . . . . . . . . C.1.15 Main Function . . . . . . . . . . . . . . . . C.1.16 GAM Converter . . . . . . . . . . . . . . . C.1.17 Pathway Number . . . . . . . . . . . . . . . C.1.18 Cell’s Domain . . . . . . . . . . . . . . . . . C.1.19 Channel’s Domain . . . . . . . . . . . . . . GAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 88 89 89 90 90 91 92 92 93 94 95 96 97 98 99 100 102 103 103 104 D Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 vii List of Tables 2.1 Number of Weather Related Global Disasters at Each Decade (1950-1999) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Data on Vancouver ’s Snow Dates (1997-2007) . . . . . . . . 52 C.1 Library of Functions for GAM Operation . . . . . . . . . . . 88 4.1 viii List of Figures 1.1 2.1 2.2 2.3 2.4 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 The number weather related natural disasters around the world at each decade [1950-1999] is roughly ruled by a Fibonacci sequence. . . . . . . . . . . . . . . . . . . . . . . . . . 2 Power loss caused by all events together vs. power loss caused by weather related events (NERC data, 1984-2006). . . . . . 14 UBC campus model with strong coupled components/cells(SCCs). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 The time line for emergency management. The ﬁve levels of human needs imply the priority of these critical infrastructure networks during emergency states. . . . . . . . . . . . . . . . 20 Decision making ﬂow chart for interdependencies control strategy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 UBC campus model with strong coupled cells(SCCs). . . . . . Graph characteristic of external resource (left) and critical service (right). . . . . . . . . . . . . . . . . . . . . . . . . . . First order inﬂuence domain {7} and second order inﬂuence domain {6, 7, 8, 10} of cell 3 (cell GVRD). . . . . . . . . . . . nth order inﬂuence domain of a damaged channel. . . . . . . The infrastructure networks in the UBC campus before (a) and after an earthquake (b). . . . . . . . . . . . . . . . . . . . (a) Visualized sparsity matrix of the UBC campus case before re-ordering the cell numbers; (b) Visualized sparsity matrix after re-ordering the cell numbers {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} → {2, 6, 5, 1, 7, 3, 4, 8, 10, 9}. The three islands can be identiﬁed: {1, 2, 5, 6}, {3, 7} and {, 4, 8, 9, 10} . . . . . . . . . . . . . . . . The time line for emergency management. The ﬁve levels of human needs imply the priority of these critical infrastructure networks during emergency states. . . . . . . . . . . . . . . . Decision making ﬂow chart for Interdependencies Control Strategy (ICS). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix 29 30 31 32 33 35 37 39 List of Figures 3.9 3.10 3.11 3.12 3.13 4.1 4.2 4.3 4.4 4.5 4.6 Time line of the events at UBC campus triggered by the 2006 winter snow storm and their restoration processes optimized by GAM-based ICS strategy. . . . . . . . . . . . . . . . . . . Cells on UBC campus. Where the cross “X” in the ﬁgure represents the topologicallocation of an event. . . . . . . . . . Decision making tree for the recovery phase without ICS operations. Where Ear (Ebr , Ecr ) refers to the recovery actions of Ea (Eb , Ec ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . ICS operations (represented by circled cross “⊗”) of redistributing scarce resources during emergency stage. . . . . . . Decision making tree for the recovery phase after ICS operations. Where Ear (Ebr , Ecr ) refers to the recovery actions of Ea (Eb , Ec ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . Synthesized eﬀect of delayed deciduous time, extended growing season and unchanged policies on vegetation management upon the collapse probability of trees and branches. . . . . . The temperature curve (upper ﬁgure) and wind speed curve (lower ﬁgure) during Nov 22th to Dec 4th 2006 in Vancouver area . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dependency network for these cascading pathways unfolded during the power outage in Nov, 2006 at Vancouver area (B.C., Canada). . . . . . . . . . . . . . . . . . . . . . . . . . . Decision making process for artiﬁcial precipitation stimulation(APS) action. . . . . . . . . . . . . . . . . . . . . . . . . . Active suppression of the development process of atmospheric icing by artiﬁcial precipitation stimulation. Where t0 denotes present time, t0 denotes the APS action time, t1 denotes the beginning time of ice accretion, (t1 , t2 ) denotes the ice accretion duration after APS, while (t1 , t3 ) denotes the estimated ice accretion duration without APS. . . . . . . . . . . . . . . Vulnerable geographical locations under snow storm along the transmission lines in Northern British Columbia. . . . . . . . A.1 Instance of cells, channels, reserve, external source, aggregators and distributors by UBC campus case. . . . . . . . . . . A.2 An instance of transportation matrix. Here x refers internal transmission link; y refers interdependency link; pi (wi , ri ) refers power (water, road) token value node i; Spi (Swi ,Sri ) refers power (water, road) source value node i, i = 1, 2, 3.. . . x 41 42 44 45 46 53 54 56 58 59 60 69 70 List of Figures A.3 I2Sim demo illustrated by PC cluster. . . . . . . . . . . . . . A.4 Topological structure of the 16-PC cluster at UBC power lab. A.5 UBC 5 cell cluster demo integrated into one single machine by global memory synchronization. . . . . . . . . . . . . . . . A.6 A typical channel model with delay. . . . . . . . . . . . . . . A.7 Overview of the channel model with time-varying delay. . . . A.8 Detailed internal structure of the channel model by MATLAB Simulink. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.1 The ideal multi-dimension ﬁtting function in a 2-D subspace viewed from diﬀerent angles. . . . . . . . . . . . . . . . . . . B.2 Flowchart on data processing from I2DB to I2Sim. . . . . . B.3 For the multi-dimension function abstracted from the HRT data of UBC hospital, (a) is the ﬁtted function projected on the nurse dimension; (b) is its projection on the doctor dimension. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.4 Infrastructure interdependencies among those critical infrastructure networks. . . . . . . . . . . . . . . . . . . . . . . . . B.5 EMIP: Study space of infrastructure Interdependency Analysis. Which includes four layers: Energy transmission, Matter transportation, Information communication, Policy management. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.6 UBC campus ﬁve cell model. . . . . . . . . . . . . . . . . . . B.7 Instances of self-loop or rings. . . . . . . . . . . . . . . . . . B.8 Graph with strongly connected components (SCCs) marked. . B.9 Flowchart on the searching and compressing algorithm for SCCs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.10 Strongly connected components (SCCs) identiﬁed by GAM computing algorithm. . . . . . . . . . . . . . . . . . . . . . . B.11 SCCs and pathways found between vertex 1 and vertex 12 in Fig. B.10. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi 70 70 71 71 72 72 76 77 78 80 81 81 82 84 85 85 86 Acronyms AIMS Agent-Based Infrastructure Modelling & Simulation APS Artiﬁcial Precipitation Stimulation CC Climate Change CIMS Critical Infrastructure Modelling System CIP Critical Infrastructure Protection DEW Distributed Engineering Workstation EMTDC Transients Simulation Software by Manitoba HVDC Research Centre EMTP Electromagnetic Transients Program EMIP Energy, Matter, Information, Policy. EWS Early Warning System GAM Generalized Adjacency Matrix GUI Graphical User Interface HRT Human Readable Table ICS Interdependencies Control Strategy IEISS Interdependent Energy Infrastructure Simulation System I2Sim Infrastructures Interdependencies Simulator I2DB Infrastructures Interdependencies DataBase IPCC International Panel of Climate Change JIIRP Joint Infrastructure Interdependencies Research Project LSE least square error MATE Multi Area Thevenin Equivalent MCP Manageable Cascading Pathway MDG multi-arc di-rected graphs MIMO multi-input and multi-output xii Acronyms MUNICIPAL Multi-Network Interdependent Critical Infrastructure Program for Analysis of Lifelines NCIs National Critical Infrastructures NERC North American Electric Reliability Council NSRAM Network Security Risk Assessment Model OVNI Object Virtual Network Integrator PSC Public Safety Canada SAM semi-certain Adjacency Matrix SCC Strongly Correlated/Coupled Cells/Components SII Survivability Index of Island UMCP UnManageable Cascading Pathway xiii Acknowledgements I owe a great debt of gratitude to many people who helped me to make the completion of this thesis possible. I would like to thank my supervisor Dr. Marti at ﬁrst, for giving me support to work in this amazing area and for his creative thoughts, inspiring ideas throughout this study. His patience in instructing students, his enthusiasm in his research activities, has deeply aﬀected me, and will always encourage me as invaluable spiritual wealth in my future career. I would also like to thank the people whom I have had the opportunity to learn from and who inspired me so much. The ﬁrst of these is Dr. Hermann Dommel. It was an extreme pleasure to audit his lectures of power systems, because of his deep understanding of power system concepts and wonderful ability to explain them, and I was greatly aﬀected by his passion on this ﬁeld of power system research. I would next like to thank Dr. Ebrahim Vaahedi, whose suggestions in my research, clear explanations as a teacher gave me an appreciation for optimal models that has beneﬁted me throughout my research. I would also like to thank Dr. Wenyuan Li. His informative suggestions in my power system research, and his enthusiasm and eagerness to study original problems was always part of my inspiration in this area. and I would also like to extend my thanks to these people who gave me nice suggestions during my study, including Dr. K.D. Srivastava, Dr. Wilsun Xu, Dr. Khosravi, Mr. Kip Morrison, Dr. Juri Jatskevich, Mr. Steven Pai, and Mr. Bao Lixin et al. It is very important to mention my labmates, friends and co-workers who helped and supported me in my research. These include Dr. Peng Zhang, Dr. Mike Wrinch, Haﬁz Abdur Rahman, Hugon Juarez, Alejandro Cervantes, Jian Xu, Dr. Jorge Hollman, Dr. Arvind Singh, Tom De Rybel, Amir Rasuli, Dr. Weidong Xiao, Leon Max Vargas, Nathan Ozog, Mandana Sotoodeh, and Kafui Monu et al. They have all played larger roles in this undertaking than they probably realize. Finally, I would like to thank Gina Chang for her devoted support. xiv Co-authorship Statement Dr. Marti’s contributions to the paper in Chapter 2, the paper in Chapter 3 and the paper in Chapter 4 are identiﬁcation and design of research programs, and manuscript preparations. Dr. Srivastava’s contributions to the paper in Chapter 2, the paper in Chapter 3, and the paper in Chapter 4 are manuscript preparations. Mandana Sotoodeh’s contribution to the paper in Chapter 2 is manuscript preparation. Kafui Monu’s contribution to the paper in Chapter 2 is manuscript preparation. xv Chapter 1 Introduction 1.1 Background In modern society, our living quality is determined by the reliability of the national critical infrastructure networks (NCIs), which include electrical networks, transportation networks, communications networks, water (oil and gas) networks, banking and ﬁnance service networks, food distribution networks, health and emergency services networks etc. [1][2]. Since none of them can be independent from the others, as a whole, this multi-layer network can be seen as a “system of systems”. Since the multiple layers of this system of systems are interweaved with each other today, it is very robust to most disturbances, but aﬀected by some speciﬁc factors, it can be very fragile [3][4]. For instance, Table I lists factors that can make this multi-layer system collapse [5][6]. Table I: Catastrophic Factors on Infrastructure Networks Factor Natural disasters Adverse weather Technical failures Managerial factor Investment factor Human factors Content Earthquake, ﬂoods, landslides, tsunamis, wild-ﬁres, volcanic activities etc. [7]. Extreme winds, snow, sleet, ice storm etc.[8][9]. Design faults etc. Inadequate maintenance etc.[10]. Unskilled workers, aging infrastructure, aging workforce, excessively prolonged service etc.[10]. Mis-operation, sabotage, terrorism, and war etc. Also in a background of changed climate , scientists believe in that factors like extreme adverse weather conditions have a high probability to be more frequent [11-13]. This opinion can also be justiﬁed by the data [14] in Fig.1.1. To protect our critical infrastructure networks against various disastrous factors, especially to mitigate or prevent cascading events that may lead to a system collapse, a better understanding on the behavior of each component in the network, the internal interaction mechanisms among them in diﬀerent 1 Chapter 1. Introduction 74 44 29 13 16 Figure 1.1: The number weather related natural disasters around the world at each decade [1950-1999] is roughly ruled by a Fibonacci sequence. layers of the critical infrastructure networks are required. Since related historical data is rare and usually incomplete, and the cost of real-world physical experiments is extremely high, analysis by network modelling and computer simulation will be more practical and feasible. 1.2 Motivation Generally speaking, the more complex a system is, the more fragile it will be. A system with higher complexity usually has more subsystems, more uncontrollable parameters, more possible interference sources, more interdependent interfaces among the internal subsystems and with the external environment, and thus it has more unpredictable behaviors. In this sense, for today’s increasingly interconnected infrastructure networks, the probability of system failures will increase after inter-connections [8][9][15]. For instance, the scale of disturbance that two electrical networks can tolerate together is usually larger than the tolerance of each individual network. But, because of deregulation and market competition [16], shared spare capacity is usually used to its limit. Therefore by interconnection, the whole system’s risk of collapse might be increased instead of decreased. In some extreme situations, when all these components in one layer of this multi-layer network are simultaneously in critical states, which is usually induced by a global adverse condition, similar to the process of chain reaction, a small local disturbance can easily develop into a large cascading failure during its propagation. This is consistent with the small world model 2 Chapter 1. Introduction [17] where the interdependent interfaces can seriously impact other layers [18][19][20][21]. Research work on identifying, understanding and analyzing these interdependencies is extremely important and has signiﬁcant challenges. These challenges are greatly magniﬁed by the wide breadth and high complexity of our critical national infrastructures. Moreover, a broad range of interrelated factors and system conditions complicated this challenge. These include the technical, economic, business, social/political, legal/regulatory, public policy, health and safety, and security concerns etc.. These interdependencies can be physical, cyber, related to geographic location, or logical in nature. The interdependencies and the resultant infrastructure topologies can create subtle mechanisms that often lead to unexpected behaviors and consequences during disruptions. Most recent studies in this area are concentrated on qualitative and local analysis [5][19][21][25], although these works articulate the inherent dangers of uncontrolled interdependencies, they do not provide a methodology for thinking about or analyzing this phenomenon. For large-scale multi-layers network, such as our NCIs, tractable methodology as well as a framework of interdependency analysis at systems level is greatly required. 1.3 Literature Review After 9/11, mainly ﬁnancially supported by the U.S.A, the E.U and Canada, many organizations, institutes and universities have focused their research directions onto critical infrastructure networks. Some of these supporting organizations include the Department of Homeland Security (DHS), Department of Energy (DOE), Department of the Air Force (DAF),Defense Advanced Research Projects Agency (DARPA) etc. Here, we give an overview on the work on infrastructure interdependency modelling, simulation and vulnerability assessment done in recent years. Their diﬀerences from our current simulator are also mentioned here. 1.3.1 Work on Infrastructure Interdependency Modelling • Agent-Based Infrastructure Modelling & Simulation (AIMS) [26]: developed at the University of New Brunswick, AIMS is an agentbased system to simulate and model interdependencies and survivability of Critical Infrastructures in Canada. However, as opposed to the methodologies in our simulator, risk assessment and vulnerability analysis are not considered in this project. 3 Chapter 1. Introduction • Critical Infrastructures Modelling System (CIMS)[27-29]: developed by Idaho National Laboratory (INL), is a modelling and simulation framework that combines geo-spatial information and a four dimensional (4D) environment (time-based) to support ’what if’ analysis. In our I2Sim team, exhaustive analysis can be done by the tool using the generalized adjacency matrix developed in this thesis. • Interdependent Energy Infrastructure Simulation System (IEISS) [30-31]: developed by Los Alamos National Laboratory, is an actor-based infrastructure modelling, simulation, and analysis tool designed to assist individuals in analyzing and understanding interdependent energy infrastructures. As opposed to our simulator, the human layer is not considered in IEISS. 1.3.2 Work Based on Graph theory • MIT Screening Methodology[32][33]: This research proposes a methodology for the identiﬁcation and prioritization of vulnerabilities in infrastructures. But this method only considers terrorism factors. • Distributed Engineering Workstation (DEW) [34-35]: DEW is being used to identify and analyze interdependencies in large scale electrical power systems and ﬂuid systems of aircraft carriers. But here the human decision layer and risk assessment are not considered. 1.3.3 Work on Vulnerability Analysis and Risk Assessment • CARVER [37-39]: Designed by Infrastructure Expertise Critical Infrastructure Library, CARVER2 is a simple software program that provides a quick and easy way to prioritize potential terrorist targets. It compares and rates critical infrastructures and key assets in jurisdictions by producing a mathematical score for each potential target. But in CARVER human activity is not modelled and terrorist attacks are considered as the only disaster factors. • Knowledge Management and Visualization in Support of Vulnerability Assessment of Electricity Production: This work is being done by Carnegie Mellon University to analyze vulnerabilities associated with delivery of fuel. It is designed to help ensure availability of supply and to visualize the impacts for decision support. 4 Chapter 1. Introduction The project has focused on coal deliveries to power plants. But human activity is not modelled, and only the electrical infrastructure is considered. • Multi-Network Interdependent Critical Infrastructure Program for Analysis of Lifelines (MUNICIPAL) [40]: Designed at Rensselaer Polytechnic Institute (RPI), is a geographic information system (GIS) user interface. It is built on a formal, mathematical representation of a set of civil infrastructure systems that explicitly incorporates the interdependencies among them. But vulnerability and risk assessments are not considered. • Network Security Risk Assessment Model (NSRAM) Tool for Critical Infrastructure Protection (CIP) Project [41][42]: developed by James Madison University (JMU), it is a complex network system simulation modelling tool that emphasizes the analysis (including risk analysis) of large interconnected multi-infrastructure models. However, interdependencies among critical infrastructures are not modelled. 1.4 Research Objectives For a system of systems, various measures can be taken to reduce the frequency of failures. But compared with the objective of preventing large cascading failures, the survival of essential critical services is a more tractable issue. As Dr. Marti et al. suggested in [22][23], a practical approach is to dynamically segment the system, according to related risk analyses of the disaster context, into several “self-suﬃcient islands” to prevent cascading failures. In this thesis, all my research investigations (cell modelling and representation, interdependency modelling and analysis by graph theory, interdependencies control strategy, mitigating snow-caused blackout along cascading pathways etc.) are developed under the environment of our I2Sim team. The team’s research goal is to better understand, model, analyze, and simulate critical infrastructure interdependencies in the context of various disasters [43][44], to develop eﬀective decision-making tools, which can help policy makers and infrastructure service providers to save a maximum number of human lives, to keep a maximum time of reliable service, to minimize the down time and restoration process as well as monetary loss during natural or man made disasters. 5 Chapter 1. Introduction To achieve such a goal, the research objectives in this thesis are speciﬁed as follows: • Development of an interdependencies control strategy (ICS) based on computation of the generalized adjacency matrix (GAM) and based on our results on dynamic islanding methods; development of related algorithms for vulnerability assessment, bottleneck detection and islands identiﬁcation. • Further development of the GAM-based interdependencies control strategy, which will help the decision making activity in the four phases of the emergency management cycle, as well as to maintain the survival of the critical services and to minimize the system’s loss during a disaster. An index to measure the survivability of a system is also proposed. • Identiﬁcation of the cascading pathways, as well as modelling the cascading mechanism, which can help prevent large disasters in critical infrastructure networks, particulary in electrical power networks. 1.5 Outline of the Thesis The outline of this thesis is organized as follows: Chapter 1 introduces the research background, motivation, related work and the objectives of this research. Chapter 2 is on managing interdependencies among NCIs. where adjacency matrix (GAM) is generalized, based on which an interdependencies control strategy (ICS) is proposed, which can help keep the survival of the most critical services. The application of ICS on the UBC test case is described in Chapter 3, where based on the 2006 snow-caused power outage of Vancouver, decision making processes with/without ICS are demonstrated with diﬀerent scenarios. Chapter 4 is on mitigating snow-caused blackouts along cascading pathways. Based on our investigation of the Vancouver’s snow-caused power outage in November 2006, a dependency network has been built to represent the causalities among these root conditions and the related consequences. Through analysis on this causal dependency network, related countermeasures to inhibit the development of a wet-snow disaster, as well as to strengthen the vulnerabilities are described. In Chapter 5, conclusions are given and future work is proposed. 6 Chapter 1. Introduction The theoretic foundation for this study can be found in the Appendix sections. Appendix A introduces the I2Sim (Infrastructure Interdependency Simulator) simulator. Appendix B includes two sections: one is on the Human Readable Table (HRT) method and its application in I2Sim. Another section is on graph representation of modellable interdependencies among critical infrastructures. A library of functions for operations on GAM was developed in Appendix C. 7 Chapter 1. Introduction 1.6 Bibliography [1] S. M. Rinaldi, J. P. Peerenboom and K. K. Terrence, “Identifying, understanding, and analyzing critical infrastructure interdependencies”, IEEE Control Systems Magazine, vol.21, pp.11-25, Dec, 2001. [2] R. G. Little, “Toward more robust infrastructure: observations on improving the resilience and reliability of critical systems”, In Proceedings of the 36th Annual Hawaii International Conference, 6-9 Jan. 2003. [3] J. P. Peerenboom, “Infrastructure interdependencies: overview of concepts and terminology,” paper from Pacific North-West Economic Region security site http://www.pnwer.org/pris/. [4] J. M. Carlson and John Doyle, “Complexity and robustness”, Proc. Natl. Acad. Sci., USA, vol.99, pp.2538-2545, 2002, Suppl.1. [5] J. M. Carlson and John Doyle,“Highly optimized tolerance: A mechanism for power laws in designed systems”, Phys. Rev. E., vol.60, No 2, pp.1412-1427, Aug 1999. [6] A. J. Holmgren, “Quantitative Vulnerability Analysis of Electric Power Networks”, Doctoral thesis in safety analysis, Royal Institute of Technology, Sweden, Division of Safety Analysis, Dept of Transport and Economics, RIT. SE-100 44 Stockholm, Sweden., April 2006. [7] D. McEntire, “Status of emergency management theory”, In the FEMA Higher Education Conference, Emmitsburg, MD., Emergency Administration and Planning Program, University of North Texas, Denton,TX., June 8, 2004. [8] J. L. Magin and Maria Newman, “Earthquake hits Hawaii and causes blackouts”, International Herald Tribune-American, October 16, 2006. [9] J. McCready, “Ice storm 1998: Lessons learned”, In Kelowna, editor, 6th Canadian Urban Forest Conference, October 19-23, 2004. British Columbia, Meteorological Service of Canada, 2004. [10] P. Sandene, “Massive snowstorms hit China”, Technical report, Commodity Intelligence Report by Foreign Agricultural Service in USDA (United States Department of Agriculture), Feb, 1st, 2008. [11] NERC, “Results of the 2007 survey of reliability issues”, Technical report, North American Electric Reliability Cooperation, Oct 24, 2007. [12] R. Billinton and C. Wu, “Predictive reliability assessment of distribution systems including extreme adverse weather”, In CCECE, http:// ieeexplore.ieee.org/iel5/7425/20197/00933530.pdf, May 2001. [13] R. Billinton and G. D. Sing, “Reliability assessment of transmission and distribution systems considering repair in adverse weather conditions”, In Proceedings of the 2002 IEEE Canadian Conference on on Electrical & 8 Chapter 1. Introduction Computer EQineering, 2002. [14] R. Billinton and G. Singh, “Application of adverse and extreme adverse weather: modelling in transmission and distribution system reliability evaluation”, In Generation, Transmission and Distribution, IEE Proceedings, vol.153, pp.115-120, 2006. [15] P. Hoeppe, and G. Berz, “Risks of climate change - the perspective of the (re) insurance industry”, In Power Engineering Society General Meeting 2005, IEEE, vol.2, pp.2023-2026, Munich Re, Munich, Germany, 2005. [16] CBC News, “Snowstorm blankets B.C.’s Southern coast”, CBC News, Sunday, 11:25 PM EST, November, 26 2006. [17] Arthur R. Bergen and Vijay Vittal, Power Systems Analysis (Second Edition). Prentice Hall, 2000. [18] D. J. Watts, Small Worlds: The Dynamics of Networks Between Order and Randomness, Princeton Univ. Press, Princeton, N.J., 1999. [19] Y. Y. Haimes, “Infrastructure interdependencies and homeland security”, J. Infrastruct. Syst., vol.11, pp.65-66, 2005. [20] A. Massoud and B. F. Wollenberg, “Toward a smart grid”, IEEE Power and Energy Magazine, vol.3, No 5, pp.34-38, Sept/Oct. 2005. [21] A. Massoud, “Security challenges for the electricity infrastructure”, Special issue of the IEEE Computer Magazine on Security and Privacy, supplement to computer, pp.8-10, April 2002. [22] A. Massoud and P. F.Schewe, “Preventing blackouts. Scientiﬁc American”, www.Sciam.com, May, pp.60-67, 2007. [23] J. A. Hollman, J. R. Marti, Juri Jatskevich, and K.D. Srivastava, “Dynamic islanding of critical infrastructures: a suitable strategy to survive and mitigate extreme events”, International Journal of Emergency Management(IJEM), vol.4(1), pp.45-58, 2007. [24] J. R. Marti, J. A. Hollman, C. Ventura, and J. Jatskevich, “Design for survival: Real-time infrastructure coordination”. In International Workshop on Complex Network and Infrastructure Protection, Rome, 2006. CNIP. [25] A. Massoud, “Toward self-healing infrastructure systems”, IEEE Computer Magazine, vol. 33, No. 8, pp.44-53, Aug. 2000. [26] L. Augusto Dueas-Osorio, “Interdependent Response of Net- worked Systems to Natural Hazards and Intentional Disruptions”, PhD thesis, School of Civil and Environmental Engineering Georgia Institute of Technology, December 2005. [27] S. Marsh, “Critical infrastructure interdependencies”, http://iit- iti.nrccnrc.gc.ca/colloq/0405/04-11-04-e.html, November 4 2004. [28] D. D. Dudenhoeﬀer, M. R. Permann and R. L. Boring, “Decision consequence in complex environments: Visualizing decision impact”, In Pro9 Chapter 1. Introduction ceeding of Sharing Solutions for Emergencies and Hazardous Environments, American Nuclear Society Joint Topical Meeting: 9th Emergency Preparedness and Response/11th Robotics and Remote Systems for Hazardous Environments, 2006. [29] D. D. Dudenhoeﬀer, M. R. Permann and E.M. Sussman, “A parallel simulation framework for infrastructure modeling and analysis”, In Proceedings of the 2002 Winter Simulation Conference, Piscataway, New Jersey: Institute of Electrical and Electronics Engineers., 2002. [30] D. D Dudenhoeﬀer, M. R. Permann and M. Manic. Cims, “ A framework for infrastructure interdependency modeling and analysis”, In Proceedings of the 2006 Winter Simulation Conference, Piscataway, New Jersey:Institute of Electrical and Electronics Engineers, 2006. [31] Los Alamos National Laboratory (LANL), “Nisac energy sector:IEISS”, Technical report, NISAC Capabilities Workshop, LA-UR-03-1159, Portland, Oregon, 26-27 March 2003. [32] Los Alamos National Laboratory (LANL), “Energy infrastructure modeling at LANL”, Technical report, LALP-03-027,LA-UR-03-0658., 2003. [33] G. Apostolakas and D. Lemon, “A screening methodology for the identiﬁcation and ranking of infrastructure vulnerabilities due to terrorism”, Risk Analysis, vol.25(2), pp.361-376, 2005. [34] D. Michaud and G.E.Apostolakis, “A methodology for ranking the elements of water-supply networks”, Journal of Infrastructure Systems , vol.12, pp.230-242, 2006. [35] R. Broadwater, “Power engineering”, http://www.ecpe.vt.edu/news /ar04/power2004.pdf, 2004. [36]Sam Six Products: DEW, http://www.samsix.com/dew.htm, 2006. [37] T. Kwa Sur and R. Broadwater, Virginia tech presentation, http://www.eng.vt.edu/research/dom pres/Tam-Broadwatertion.pdf, July 3 2006. [38] NI2 Center, Ni2 center for infrastructure expertise critical infrastructure library. http://www. ni2ciel.org/, 2006. [39] National Infrastructure Institute, National infrastructure institute home page, http://www.ni2.org/default.asp, 2006. [40] National Infrastructure Institute, Carver2 project home page, http://www.ni2cie.org/CARVER2.asp, 2006. [41] E. E. Lee, “Decision technologies for protection of critical infrastructures”, http://www.rpi.edu/ mitchj/papers/decisiontechnologies.pdf, 2006. [42] J. McManus, “Network security risk assessment model (NSRRAM) tool for critical infrastructure protection project”, http://www.jmu.edu/iiia/ webdocs/ppt /NSRAM Tool.ppt, July 12 2006. 10 Chapter 1. Introduction [43] S. Redwine. “Network security risk assessment model tool”, http://www. jmu.edu/cisat/frd/abstracts04/redwine sam.html, April 3 2006. [44] JIIRP Group, “Infrastructure interdependencies simulation team”, Technical report, University of British Columbia, 2005. http://www.jiirp.ca. 11 Chapter 2 Interdependencies Control Strategy 2.1 Introduction In modern societies, the standard of living is determined by the reliability of the national critical infrastructure networks (NCIs), which include electrical networks, transportation networks, communications networks, water (oil and gas) networks, banking and ﬁnance service networks, food distribution networks, health and emergency services networks, etc. [1][2]. Since as a whole, none of them can be fully independent from the others, this multi-layer network can be seen as a “system of systems”. By sharing larger reserve capacity, today’s inter-connected infrastructure networks can make eﬃcient use of limited resources; the availability of these resources are also guaranteed by their diversity. Therefore these interdependencies are making the infrastructure networks so robust that it can handle most local disturbances or stochastic ﬂuctuations. On the other hand, this “system of systems” is becoming more fragile. Through cascading eﬀects, an event which may have collapsed one single layer of the networks before, now due to the inter-connection, may cause catastrophe in all possible layers of the critical infrastructure networks. In some extreme situations, those global disturbances, such as earthquakes, adverse weather conditions, terrorist attacks etc., can trigger many events simultaneously, either making the whole system devolve into a critical state, or revealing many unexpected hidden and detrimental interdependencies. In this paper, this “robust yet fragile” duality is treated as the inherent vulnerability of our critical infrastructure networks, which will become more vulnerable due to climate change. 1 A version of this chapter has been accepted for publication. DeTao Mao, Mandana Sotoodeh, Kafui Monu, Jose R. Marti and K. D. Srivastava (2009), Interdependencies Control: Compensation Strategies against the Inherent Vulnerability of Critical Infrastructure Networks, IEEE Canada, the 2nd Climate Change Technologies Conference (CCTC 2009), McMaster, Hamilton, Canada, May, 2009. 12 Chapter 2. Interdependencies Control Strategy Table 2.1: Number of Weather Related Global Disasters at Each Decade (1950-1999) Decade Interval 1950-1959 1960-1969 1970-1979 1980-1989 1990-1999 2000-2009 Number of Event(s) 14 16 29 44 74 Fitting Value 13 18 28 44 71 114 1 Under a changing climate, scientists believe that extreme adverse weather disasters will be more frequent [4]. This opinion can also be justiﬁed by the data [3] in Table 2.1 above. With these data, we ﬁnd that, in each decade from 1950 to 1999, the number of weather related natural disasters around the world is roughly ruled by a Fibonacci sequence: √ √ 5−1 n 5 − 1 −n Z(n) = 2.29 ( ) + 10.3 ( ) (2.1) 2 2 with n ∈ N . According to formula 2.1, this ten years (2000-2009), weather related disaster will be more frequent than before. Moreover, based on the power outage data (1984-2006) from the North American Electric Reliability Council (NERC) [5], we ﬁnd that these weather related power outages are strongly correlated with all power outages. In this analysis, the annual power loss caused both by all the events together: {xi }(i ∈ [1, 12]) and by weather related events separately: {yi }(i ∈ [1, 12]) have been accumulated for each month. The curves are displayed in Fig.2.1. The correlation coeﬃcient between {xi } and {yi } is: Cov(xi , yi ) = 0.8732 R(xi , yi ) = Cov(xi , xi ) Cov(yi , yi ) (2.2) where the covariance of variable{xi }(i ∈ [1, 12]) and {yi }(i ∈ [1, 12]) is cov(xi , yi ) = E[(xi − μxi )(yi − μyi )]. E is the mathematical expectation, μxi = E(xi ), μyi = E(yi ). The coeﬃcient R(xi , yi ) indicates the degree of linear dependence between xi and yi . A high value of R(xi , yi ) implies 1 Predicted value by formula 2.1 13 Chapter 2. Interdependencies Control Strategy Figure 2.1: Power loss caused by all events together vs. power loss caused by weather related events (NERC data, 1984-2006). that most of those power outage events during 1984 to 2006 were directly or indirectly aﬀected by weather. Based on Eqn.2.1 and Eqn.2.2, we can conclude that critical infrastructure networks, especially electric networks, will be more unreliable in the future. As the climate patterns are changing, many of the previous assumptions related to system planning, reliability standards, and anticipated responses during emergencies, may no longer be tenable. During recent severe disasters, such as the 1998’s winter ice storm in eastern Canada, and hurricane Katrina, it proved impossible to either prevent the disasters or keep the system’s integrity. As we have stated before, the vulnerability of NCIs is mainly caused by the complicated interdependencies among them. Therefore, during an emergency, to assure the continuation of critical services by controlling the interdependencies will be a more tractable problem. This paper is organized as follows. In Section 2.1, the inherent vulnerability of our infrastructure networks is brieﬂy introduced, and the impact of climate change on critical infrastructures (NCIs) is justiﬁed based on our research results. In Section 3.2, the concept of the adjacency matrix is generalized to represent multi-arc directed physical interdependencies among critical infrastructures. Related logic rules and operations are also deﬁned. In Section 3.3, based on the generalized adjacency matrix (GAM) as well as our research results [6][7][8], an interdependencies control strategy (ICS) is proposed. By either controlling the interdependencies among NCIs, or splitting the network into several autonomic islands, it can keep essential activities survival during a disaster. Related methods on how to improve 14 Chapter 2. Interdependencies Control Strategy the survivability index of the island are also described here. We conclude our study in Section 2.4. 2.2 Representation of Multi-arc Directed Physical Independencies by the Generalized Adjacency Matrix (GAM) To control the interdependencies among critical infrastructures, it is necessary to represent the topology, dependency direction, and interacting degree(s). Physical interdependencies between two components in various infrastructure networks can be seen as directed linkages in graph theory. In this chapter, the concept of the semi-certain adjacency matrix (SAM) [21], which is usually employed to represent undirected graphs by Boolean variables {0, 1}, is generalized to represent multi-arc directed graphs with loops by using a complex matrix. For instance, in Fig.3.1, the UBC campus case in [9] can be represented by GAM with the following matrix: ⎡ GAMubc 2.2.1 ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ =⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 0 0 0 0 i 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 i 0 1 0 0 0 0 i 0 1 i 0 1 0 0 1 0 1 2 0 ⎤ 0 0 0 0 0 0 ⎥ ⎥ 1 0 0 ⎥ ⎥ 0 1 0 ⎥ ⎥ 0 i 1 ⎥ ⎥ i 2i 0 ⎥ ⎥ 0 1 2i ⎥ ⎥ i 0 2i ⎦ 2 2 0 Algebraic Operation and Logic Rules for GAM Since the logic rules for matrix operations on semi-certain adjacency matrix (SAM) cannot be adopted here directly, we have redeﬁned the multiply operator ⊗ for GAM as follows: B = A2 = A ⊗ A n aik ∩ akj bij = k=1 15 Chapter 2. Interdependencies Control Strategy TERASEN GAS_1 2 gas BC Hydro 1 UBC Campus Hospital 6 power gas steam oil Power House 9 water oil power Steam Station 8 gas campus GVRD 3 Water Station 7 power steam power Figure 2.2: UBC nents/cells(SCCs). water water power SubStation 5 model TERASEN GAS_2 4 with strong coupled compo- where bij denotes the element of matrix B, aij or ajk denotes the element of matrix A, and denotes algebraic “sum” in the regular sense. ∩ denotes the logical “and” (&), but with a generalized deﬁnition as fellows: x ∩ y = re(x) · re(y) + i · img(x) · img(y) (2.3) here re(x) represents the real part of variable x, and img(x) represents the imaginary part of variable x (the same for re(y) and img(y)). Variables x and y are complex numbers whose real parts and imaginary parts represent the incoming and outgoing degree(s), respectively. Hence, both are all nonnegative integers. 2.2.2 Further Information Abstraction Based on GAM Computation With the physical interdependencies at the same hierarchical level represented by GAM, further information of NCIs can be abstracted from related computations on GAM, such as the following properties: External Sources In GAM, external sources can be identiﬁed by detecting those elements owning no incoming degrees, i.e., the imaginary parts of all complex numbers representing interdependencies between this element and other elements are zeroes. 16 Chapter 2. Interdependencies Control Strategy Critical Services In GAM, critical services can be identiﬁed primarily by detecting those elements owning no outgoing degrees, i.e., the real parts of all the complex numbers representing interdependencies between this element and other elements are zeroes. nth order Inﬂuence Domains of a Cell Inﬂuence Domain of a cell refers to elements that will be aﬀected by the deletion of a cell from the graph. For a graph with m elements, according to their graph distance [11], there exist a 1st order inﬂuence domain, a 2nd order inﬂuence domain, · · · , and (at most) a m − 1th order inﬂuence domain. nth order Inﬂuence Domains of a Channel Inﬂuence domains of a channel refers to the n − 1th order inﬂuence domains of the downstream cells connected to this channel. The 1st order inﬂuence domain of a channel refers to the downstream cells connected to this channel. The 2nd order inﬂuence domain refers to the union of the 1st order inﬂuence domain of the downstream cells connected to this channel. Similarly, the nth order inﬂuence domain of a channel refers to the union of the n − 1th order inﬂuence domain of the downstream cells connected to this channel. Strongly Coupled Components as typical Critical Components A directed graph is called strongly coupled/connected, if for every pair of vertices {u, v}, there is a path from u to v and a path from v to u [12]. The strongly connected components (SCCs) of a directed graph are its maximal strongly connected subgraphs that form a partition of the graph (Shadow area of the UBC campus cells [9] in Fig.3.1. Note that, in this ﬁgure, to demonstrate the existence of SCC, the broken line is added artiﬁcially. In the real world, the steam pipe from the Steam Station to the Substation does not exist). By introducing the concept of Strongly Coupled Components (SCCs), further topological knowledge about the multi-arc directed graph can be calculated explicitly and eﬃciently. Critical Level of External Resources or internal Cells For instance, by GAM computation, we can get that the impacting domain or inﬂuence domain of cell BCHydro : 1 in Fig.3.1 is {1, 5, 6, 7, 8, 9}; while 17 Chapter 2. Interdependencies Control Strategy the impacting domain of cell 2 : T erasenGAS1 is {6}; the impacting domain of cell 3 : GV RD is {6, 7, 8}; the impacting domain of cell 4 : T erasenGAS1 is {6, 8}. Therefore, roughly, we can know that the importance of critical level of each external cells. Considering both the backup cost and the restoration cost of the utility supplied by each external cell, we can precisely evaluate the important level of each of them. 2.2.3 Advantages of Interdependency Analysis Based on GAM In this paper, all interdependency analysis during interdependencies control is based on computations on the generalized adjacency matrix (GAM), this approach oﬀers the following advantages: • By ﬁnding all the pathways between any pair of elements (vertices), GAM can detect the existence of interdependencies between any pair of elements, and identify all the nth order inﬂuence domains for any element in the graph. Therefore it is an exhaustive analysis instead of a ‘what if’ analysis; • The order of the inﬂuence domain implies that the impact index from one element to the others, which may give both essential information on where to buﬀer the cascading failures with minimum cost and the priority of these elements under a given disaster context; • Since the vulnerability of strongly coupled components is determined by its weakest section, based on the calculated results of the SCC, critical components can be detected, and a vulnerability assessment can be obtained. Furthermore, by SCC identiﬁcation, interdependencies control strategies (ICS) are more rational and eﬀective. 2.3 Interdependencies Control Based on GAM For critical services in the NCIs to work, many utilities need to be available simultaneously and running at full capacity. For instance, to maintain the normal operability of a hospital, the simultaneous availability of electricity, water, steam, natural gas, medicine, nurses, doctors, foods, communication, and transportation must be assured. This full capacity state is more fragile than any other state, for in this state, a number of requirements must hold simultaneously. According to the theory on “the fragility of goodness”[13], 18 Chapter 2. Interdependencies Control Strategy once one of them fails, the functionality of the hospital will be greatly degraded. The purpose for proposing the concept of interdependencies control in this paper is to try to reduce the sensitivities of critical services on unexpected ﬂuctuations of external resources. This can be implemented by adjusting the interdependency degree by either splitting the network into several islands or just shutting down the related physical connectivity. Based on computation of GAM and a reliability assessment of the utilities, as proposed in this paper, interdependencies control strategy can help to assign limited resources to the most critical services, while avoiding the propagation of cascading failures to other infrastructure layers. Since the interdependencies control strategy (ICS) is mainly focusing at the response stage of the four phases of emergency management, it is convenient and necessary to brieﬂy review the conceptual framework for emergency management as follows. 2.3.1 Brief Introduction to Emergency Management Emergency management is the discipline of dealing with and avoiding risks [14]. As Fig.3.7 illustrates, it generally includes four diﬀerent stages [6]: • Mitigation: Long before the disaster. This refers to the sustained actions to reduce or eliminate the long-term impacts and risks associated with disasters. • Preparedness: Long and shortly before the disaster. This refers to the policies, procedures and plans for how to best manage an emergency. • Response: During and shortly after the disaster. This refers to the actions taken during or directly after an emergency occurs. • Recovery: Shortly and long after the disaster. This refers to the eﬀorts taken to repair and restore communities after an emergency. Based on Maslow’s theory of human motivation [16], humans have diﬀerent levels of needs constrained by their socio-economic background factors. A connection has been established between human motivation theory and emergency management due to the dynamic characteristics of emergency conditions [6]( as shown in Fig.3.7). The connection can give helpful information on prioritizing the diﬀerent infrastructure lifelines during emergency states. 19 Chapter 2. Interdependencies Control Strategy Analysis Planning Normal Coordination Monitoring Emergency Alert Coordination Recovery Self-actualization Esteem Love/Belonging Safety Pysiological Maslow’s Hierarchy of Huam Needs Figure 2.3: The time line for emergency management. The ﬁve levels of human needs imply the priority of these critical infrastructure networks during emergency states. 2.3.2 Survivability Index of an Island (SII) By applying the GAM-based interdependencies control strategy (ICS), the infrastructure networks can be divided into several islands during a disaster. The survivability index of each island can be brieﬂy expressed as how long this island can survive before its linkages are re-established. Mathematically, for an island with m internal backup resources, and n linkages connected with external resources, assume the availability duration of the backup resource i is ti , here ti ≤ 0 indicates that utility i has been used up for ti (time units). The estimated recovery time under a certain disaster context D for linkage j is Tj . The survivability index of island k can then be deﬁned as: SIIkD = min(ti ) (i ∈ [0, m], j ∈ [1, n], ti ∈ R, Tj ∈ R+ .) max(Tj ) (2.4) The objective of interdependencies control during a disaster D is to maintain SIIkD not less than 1. The details on ICS will be discussed in Section 2.3.3, the related measures to improve SII during the four phases of emergency management cycle will be addressed in Section 3.3.4. 2.3.3 Description of Interdependencies Control Strategy Among our modern infrastructure networks, the electrical network is the most fundamental and important infrastructure. Since it is in the lowest 20 Chapter 2. Interdependencies Control Strategy Physical interdependencies representation by generalized adjacency matrix (GAM) Further Information abstraction based on GAM computation Online monitoring by early warning system (EWS) No New disaster D Emerges? Yes Interdependency Control according the priority of missions under current disaster D Under D Warning Broadcast Yes SII 1 ? Recovery-oriented Responses No Methods Improving SII Recovery Figure 2.4: Decision making ﬂow chart for interdependencies control strategy. layer of our infrastructures pyramid, it supports the operation of most other infrastructures. The concept of interdependencies control is based on our previous work [6][7][8], and it also has been inspired by the controlled islanding strategy of power networks. It is well known that in power systems, controlled islanding is a special protection strategy aimed at preventing a system-wide blackout as a result of the cascading of low probability events [17]. The diﬀerence between controlled islanding strategy and ICS is that, in ICS, it is usually not necessary to split the network into several islands. In most cases, interdependencies control means shutting down several outgoing linkages, thus ensuring the availability of scarce resources, or isolating failures (e.g. epidemics), to a certain limited area. The decision making process for the GAM-based interdependencies control strategy (see Fig.3.8) is brieﬂy explained as fellows: 21 Chapter 2. Interdependencies Control Strategy Step 1: Identify all these modelable physical interdependencies, and represent them with the generalized adjacency matrix (GAM); Step 2: Based on the calculation of GAM, identify the supporting utilities for these critical services with higher priority and sections with vulnerabilities, such as strongly coupled components (SCCs); Step 3: Monitor the possibility of new disasters online with an early warning system (EWS). If a disaster happens, broadcast warning, carry out the anticipated recovery-oriented actions, and ﬁnally perform ICS according to the priority of the essential missions; Step 4: After interdependencies control, if the SII for each island is not less than 1, the recovery processes will receive the highest priority. Otherwise, there are many measures to maintain the critical service survival as long as possible. The detailed content on improving SII will be described in the next section. 2.3.4 Measures for Improving SII in Emergency Management As the survivability index of island (SII) is mainly determined by (1) the scarce resource, or the backup lifeline with the minimum supporting duration; (2) the recovery time; hence to improve SIS of each island, various measures at the four phases of emergency management cycle are described below. Mitigation Stage • Infrastructure design taking the following properties in consideration: risk-decentralized redundancy, multi-functionality, adaptivity to the statistic patterns of local events, maintenance/recovery-oriented characteristics, etc. Preparedness Stage • Early warning capability by monitoring possible disasters online, presolutions based on historical experiences, etc. Response Stage • Redistribute the limited resources from other external resources, or redirect them from other islands whose SII is less than 1. 22 Chapter 2. Interdependencies Control Strategy • Degrade the operability capacity of the island. • Supply critical missions in the island with “synchronized rolling availability”, which is very similar to a rolling blackout during power outage, but instead of losing services totally, it can keep the system operated at a low quality of service. • Mobilized lifelines/resources, such as mobile generators, etc. • Make use of convertible utilities, as well as multi-functional resources. As there exists overlap of these utilities’ functionality, it is possible to move from one to the other during a disaster state, like switching between gas, oil, steam, or electricity for heating. Recovery Stage • Personnel training, prioritization of critical infrastructures under all possible scenarios; Optimization of the restoration time by dynamic programming etc. 2.4 Conclusion For a system of systems, such as interdependent critical infrastructure networks, various measures can be taken to reduce the frequency of failures; however, tracking all such interdependencies is too complex. The survival of critical missions is more tractable than preventing all large cascading failures. With multi-interdependencies represented by the generalized adjacency matrix (GAM), also based on our previous results [6][7][8], we have proposed a more practical approach to respond to a large disaster. This approach helps to control the interdependencies among the critical infrastructure networks, according to a risk analysis under the disaster context, and therefore prevent failures from spreading. The proposed strategy is an eﬀective means to reduce the inherent vulnerability, as well as to increase the resiliency of critical infrastructure networks. Future work can be on: • Developing methods for optimizing the survivability index of an island’s SII according to the local event spectrum. • Identiﬁcation of complicated cascading patterns by data mining [18]. 23 Chapter 2. Interdependencies Control Strategy • Detecting time-dependent hidden interdependencies with the help of formal veriﬁcation methods, or further analysis with complex network theory [19][20]. • Building a database for all those hidden interdependencies experienced under certain disaster contexts. 2.5 Acknowledgment The authors gratefully acknowledge the contributions of J. A. Hollman, J. Jatskevich, and C. Ventura for their inspiring work on this topic. We also deeply give our thanks to Tom De. Rybel, for his suggestions in manuscript preparation of this paper. 24 Chapter 2. Interdependencies Control Strategy 2.6 Bibliography [1] Steven M. Rinaldi, James P. Peerenboom, and K. Kelly Terrence, “Identifying, understanding, and analyzing critical infrastructure interdependencies”, IEEE Control Systems Magazine, vol.21, pp.11-25, Dec, 2001. [2] R. Little, “Toward more robust infrastructure: observations on improving the resilience and reliability of critical systems”, in Proceedings of the 36th Annual Hawaii International Conference, pp.6-9 Jan. 2003. [3] P. Hoeppe and G. Berz, “Risks of climate change -the perspective of the (re) insurance industry”, in Power Engineering Society General Meeting 2005 IEEE, vol. 2, Munich Re, Munich, Germany, pp. 2023- 2026. [4] R. Billinton and G. Singh, “Application of adverse and extreme adverse weather: modelling in transmission and distribution system reliability evaluation”, in Generation, Transmission and Distribution, IEE Proceedings-, vol.153, no.1, 2006, pp.115-120. [5] NERC, “Nerc power outage database”, online, disturbances Analysis Working Group. [Online] Available: http://www.nerc.com/ dawg/database.html [6] J. A.Hollman, J. R. Marti, J. Jatskevich, and K. Srivastava,“Dynamic islanding of critical infrastructures: a suitable strategy to survive and mitigate extreme events”, International Journal of Emergency Management (IJEM), vol. 4(1),pp. 45-58, 2007. [7] J. R. Marti, J. A. Hollman, C. Ventura, and J. Jatskevich, “Dynamic recovery of critical infrastructures: real-time temporal coordination”, International Journal of Critical Infrastructures, vol. 4(1), pp. 17-31, 2008. [8] J. R. Marti, K. Srivastava, J. A. Hollman, and J. Jatskevich, “Design for survival: Real-time infrastructures coordination”, in Proceedings of the International Workshop on Complex Network and Infrastructure Protection (CNIP2006), Rome,Italy, 2006. [9] L. Liu, “Prototyping and cells modeling of the infrastructure interdependencies simulator i2sim”, Master’s thesis, University of British Columbia, 2007. [10] C. Godsil and G. Royle, Algebraic Graph Theory, Springer, 2001. [11] R. Diestel, Graph Theory, New York: Springer-Verlag, 1997. [12] T. H. Cormen, C. E. R. Leiserson, L. Rivest, and C. Stein, Introduction to Algorithms, Second Edition., MIT Press and McGraw-Hill, 2001. pp.552557. [13] L. Levantovskii, “singularities of the boundary of the stability domain”, Jour. Funkts. Anal. Prilozh., vol. 16, pp. 44-48, 1982. [14] G. D. Haddow and J. A. Bullock, Introduction to Emergency Manage25 Chapter 2. Interdependencies Control Strategy ment, Amsterdam: Butterworth-Heinemann., 2004. [15] J. R. Marti, “Simulation of infrastructure interdependencies dynamics for disaster response coordination”, JIIRP UBC Workshop, Feb 2007, presentation. [16] A. H. Maslow, “A theory of human motivation.” Psychological Review, vol. 50, pp. 370-396, 1943. [17] N. Senroy and G. T. Heydt, “A conceptual framework for the controlled islanding of interconnected power systems”, IEEE Transaction on Power Systems, vol. 21(2), pp.1005-1006, 2006. [18] M. L. Gargano and B. G. Raggad, “Data mining - a powerful information creating tool”, OCLC Systems and Services, vol. 15(2), pp.81-90, 1999. [19] A. L. Barabsi and R. Albert, “Emergence of scaling in random networks”, Science, vol.286(5439), pp.509-512, 15 October 1999. [20] S. H.Strogatz, “Exploring complex networks”, Nature, vol. 410, pp.268276, 2001. [21] C. Godsil, and G. Royle, “Algebraic Graph Theory”, Springer, 2001. 26 Chapter 3 Survival from Disaster by Interdependencies Management 3.1 Introduction In modern societies, the standard of living is determined by the reliability of the critical infrastructure networks, which include electrical networks, transportation networks, communications networks, water (oil and gas) networks, banking and ﬁnance service networks, food distribution networks, health and emergency services networks etc. [1]. Since as a whole, none of them can be fully independent from the others, this multi-layer network can be seen as a “system of systems”. By sharing larger reserve capacity, today’s inter-connected infrastructure networks can make eﬃcient use of limited resources; the availability of these resources is also guaranteed by their diversity. Therefore these interdependencies are making the infrastructure networks so robust that it can handle most local disturbances or stochastic ﬂuctuations. On the other hand, this “system of systems” is becoming more fragile. Through cascading eﬀects, an event which may have collapsed one single layer of the networks before, now due to the inter-connection, may cause catastrophe in all possible layers of the critical infrastructure networks. In some extreme situations or global disturbances, such as earthquakes, adverse weather conditions, terrorist attacks, etc., can trigger many events simultaneously, either making the whole system devolve into a critical state, or revealing many unexpected hidden and detrimental interdependencies. In this paper, this “robust yet fragile” duality is treated as the inherent vulnerability of our critical infrastructure networks, which will become more vulnerable due to climate change. As the climate patterns are changing, many of the previous assumptions 1 A version of this chapter is to be submitted for publication. DeTao Mao, Jose R. Marti and K. D. Srivastava, Survival from Disaster by Interdependencies Management. 27 Chapter 3. Survival from Disaster by Interdependencies Management related to system planning, reliability standards, and anticipated responses during emergencies, may no longer be tenable. During recent severe disasters, such as the winter 1998 ice storm in eastern Canada, and hurricane Katrina, it proved impossible to either prevent the disasters or keep the system’s integrity. As we have stated before, the vulnerability of NCIs is mainly caused by the complicated interdependencies among them. Therefore, during an emergency, to assure the continuation of critical services by controlling the interdependencies will be a more tractable problem. 3.2 Representation of Modellable Physical Independencies by the Generalized Adjacency Matrix (GAM) To control the interdependencies among critical infrastructures, it is necessary to represent their topology, dependency direction, and interacting degree(s). Modellable physical interdependencies between two components in various infrastructure networks can be seen as directed linkages in graph theory. In this paper, the concept of the semi-certain adjacency matrix (SAM) [6], which is usually employed to represent undirected graphs by Boolean variables {0, 1}, is generalized to represent multi-arc directed graphs with loops by using a complex matrix. For instance, in Fig.3.1, the UBC campus case in [5] can be represented by GAM with the following matrix: ⎡ 0 0 0 0 i 0 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 0 i 0 0 1 0 0 0 0 i 0 1 i 0 GAMubc ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ =⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 3.2.1 Operation Rules for GAM 0 1 0 0 1 0 1 2 0 0 0 0 1 0 0 i 0 i 2 i 0 0 0 1 i 2i 1 0 2 i 0 0 0 0 1 0 2i 2i 0 i 0 0 0 0 0 0 1 1 1 0 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ Since the logic rules for matrix operations on semi-certain adjacency matrices (SAM) cannot be adopted here directly, we have redeﬁned the multiply 28 Chapter 3. Survival from Disaster by Interdependencies Management TERASEN GAS_1 2 gas BC Hydro 1 power UBC Campus Hospital 6 power water water SubStation 5 steam gas Water Station 7 power steam GVRD 3 oil power water Power House 9 oil power Steam Station 8 water steam power gas Noncritical Cells 10 TERASEN GAS_2 4 Figure 3.1: UBC campus model with strong coupled cells(SCCs). operator ⊗ for GAM as follows: B = A2 = A ⊗ A n aik ∩ akj bij = k=1 where bij denotes the element of matrix B, aij or ajk denotes the element of matrix A, and denotes the algebraic “sum” in the regular sense. ∩ denotes the logical “and” (&), but with a generalized deﬁnition as fellows: x ∩ y = re(x) · re(y) + i · img(x) · img(y) (3.1) here re(x) represents the real part of variable x, and img(x) represents the imaginary part of variable x (the same for re(y) and img(y)). Variables x and y are complex numbers whose real part and imaginary part represent the incoming and outgoing degree(s), respectively. Hence, both are all nonnegative integers. 29 Chapter 3. Survival from Disaster by Interdependencies Management source Critical service Figure 3.2: Graph characteristic of external resource (left) and critical service (right). 3.2.2 System Information Abstracted by GAM Computation With the modellable physical interdependencies at the same hierarchical level represented by GAM, system information of NCIs can be abstracted from related computations on GAM, such as the following properties: External Sources In GAM, external sources (as in Fig.3.2) can be identiﬁed by detecting those elements owning no incoming degrees, i.e., the imaginary parts of all complex numbers representing interdependencies between this element and other elements are zeroes. Critical Services In GAM, critical services (as in Fig.3.2) can be identiﬁed primarily by detecting those elements owning no outgoing degrees, i.e., the real parts of all the complex numbers representing interdependencies between this element and other elements are zeroes. nth order Inﬂuence Domains of a Cell Inﬂuence Domain refers to elements that will be aﬀected by the deletion of an element from the graph. For a graph with m elements, according to their graph distance [8], there exist 1st order inﬂuence domain, 2nd order inﬂuence domain · · · , and at most m − 1th order inﬂuence domain of a channel. For instance, in Fig.3.3, for element 3 (GVRD), its ﬁrst order inﬂuence domain is {7} (water station), its second order inﬂuence domain is {6, 8} (hospital and steam station). For instance, in Fig.3.4, the 1st order inﬂuence domain of this broken channel is {a}, the 2nd order inﬂuence domain is {b, c}, the 3rd order inﬂuence domain is {d, e, g, f }. 30 Chapter 3. Survival from Disaster by Interdependencies Management Figure 3.3: First order inﬂuence domain {7} and second order inﬂuence domain {6, 7, 8, 10} of cell 3 (cell GVRD). nth order Inﬂuence Domains of a Channel which refers to the n − 1th order Inﬂuence Domains of the downstream cells connected to this channel. For example, the 1st order inﬂuence domain of a channel refers to the downstream cells connected to this channel; The 2nd order inﬂuence domain of a channel refers to the union of the 1st order inﬂuence domain of the downstream cells connected to this channel. Similarly, the nth order inﬂuence domain of a channel refers to the union of the n-1th order inﬂuence domains of the downstream cells connected to this channel. Strongly Coupled Components as typical Critical Components A directed graph is called strongly coupled/connected, if for every pair of vertices {u, v}, there is a path from u to v and a path from v to u [9]. The strongly connected components (SCCs) of a directed graph are its maximal strongly connected subgraphs that form a partition of the graph (Shadow area of the UBC campus cells [5] in Figure 3.1. Note that, in this ﬁgure, to demonstrate the existence of SCC, the broken line is added artiﬁcially. In the real world, the steam pipe from the Steam Station to the Substation does 31 Chapter 3. Survival from Disaster by Interdependencies Management x a b d i c e h g f Figure 3.4: nth order inﬂuence domain of a damaged channel. not exist). By introducing the concept of Strongly Coupled Components (SCCs), further topological knowledge about the multi-arc directed graph can be calculated explicitly and eﬃciently. Critical Level of External Resources or internal Cells For instance, by GAM computation, we can get that the impacting domain or inﬂuence domain of cell BCHydro : 1 in Figure 3.1 is {1, 5, 6, 7, 8, 9}; while the impacting domain of cell 2 : T erasenGAS1 is {6}; the impacting domain of cell 3 : GV RD is {6, 7, 8, 10}; the impacting domain of cell 4 : T erasenGAS2 is {8}. Therefore, roughly, we can know that the importance of critical level of each external cells. With considering both the backup cost and the restoration cost of the utility supplied by each external cell, we can precisely evaluate the important level of each of them. Number of Islands Detected by Eigenvalue Calculation of the Laplacian Matrix In the mathematical ﬁeld of graph theory the Laplacian matrix [18], sometimes called admittance matrix or Kirchhoﬀ matrix, is a matrix representation of a graph. Given a graph G with n vertices (without loops or multiple edges), its 32 Chapter 3. Survival from Disaster by Interdependencies Management 2 2 1 6 1 3 5 7 9 10 8 3 5 7 9 6 10 8 4 4 (a) (b) Figure 3.5: The infrastructure networks in the UBC campus before (a) and after an earthquake (b). Laplacian matrix L := (i,j )n×n is deﬁned as i,j ⎧ ⎪ ⎨deg(vi ) := −1 ⎪ ⎩ 0 if i = j if i = j and vi is adjacent to vj otherwise. (3.2) That is, it is the diﬀerence of the degree matrix and the adjacency matrix of the graph. In the case of directed graphs, either the in-degree or the out-degree might be used, depending on the application. For a graph G and its Laplacian matrix L with eigenvalues λ0 ≤ λ1 ≤ · · · ≤ λn−1 : • L is always positive-semideﬁnite (∀i, λi ≥ 0). • The number of times 0 appears as an eigenvalue in the Laplacian is the number of connected components (isolated islands) in the graph. • λ0 is always 0. • λ1 is called the algebraic connectivity. • The smallest non-trivial eigenvalue of L is called the spectral gap. The rules to covert from the generalized adjacency matrix (GAM) to the Laplacian Matrix can be described as follows. Assume Gn×n is a generalized adjacency matrix, its element is gij , Ln×n is a converted Laplacian matrix, 33 Chapter 3. Survival from Disaster by Interdependencies Management its element is i,j , then the rule from the GAM to the Laplacian matrix is n j=1 ||sign(gij )|| if i = j and gij = 0 (3.3) i,j := −1 if i = j and gij = 0 For instance, UBC’s ﬁve cells case in Fig.3.1 can be represented as a labelled graph in Fig.3.5, and its Laplacian matrix is : ⎡ LMubc ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ =⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 1 0 0 0 −1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 −1 0 0 0 3 0 −1 0 0 −1 0 0 −1 0 0 0 0 0 −1 0 0 0 0 0 −1 0 0 0 0 0 0 −1 0 0 −1 4 −1 −1 0 0 0 0 −1 0 0 −1 5 −1 −1 −1 0 0 0 −1 0 −1 −1 5 −1 −1 ⎤ 0 0 0 0 ⎥ ⎥ 0 0 ⎥ ⎥ 0 0 ⎥ ⎥ −1 0 ⎥ ⎥ 0 0 ⎥ ⎥ −1 −1 ⎥ ⎥ −1 −1 ⎥ ⎥ 4 −1 ⎦ −1 3 Assume channels CH5−9 , CH6−7 , CH6−8 , CH7−8 , CH7−9 and CH7−10 are broken after an earthquake, the infrastructure networks in the UBC campus are isolated into several subnetworks as shown in Fig.3.5 (here channel CHi−j refers to the channel that connects cell i and cell j). ⎡ islands LMubc ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ =⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 1 0 0 0 −1 0 0 0 0 0 0 1 0 0 0 −1 0 0 0 0 0 0 1 0 0 0 −1 0 0 0 0 0 0 1 0 0 0 −1 0 0 −1 0 0 0 2 −1 0 0 0 0 0 −1 0 0 −1 2 0 0 0 0 0 0 −1 0 0 0 1 0 0 0 0 0 0 −1 0 0 0 3 −1 −1 0 0 0 0 0 0 0 −1 2 −1 0 0 0 0 0 0 0 −1 −1 2 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ islands are {0, 0, 0, 0.5858, 1, 2, 2, 3, 3.42, 4}, there The eigenvalues of LMubc are three zeroes in them, corresponding to three subnetworks or islands. After reordering the cell numbers, the islands can be visualized in Fig.3.6 (b), where the cells represented by the number can be seen in Fig.3.3. 34 Chapter 3. Survival from Disaster by Interdependencies Management Figure 3.6: (a) Visualized sparsity matrix of the UBC campus case before re-ordering the cell numbers; (b) Visualized sparsity matrix after re-ordering the cell numbers {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} → {2, 6, 5, 1, 7, 3, 4, 8, 10, 9}. The three islands can be identiﬁed: {1, 2, 5, 6}, {3, 7} and {, 4, 8, 9, 10} . 3.2.3 Advantages of GAM-based Interdependency Analysis In this paper, all interdependency analysis during interdependencies control is based on computations on the generalized adjacency matrix (GAM). This approach oﬀers the following advantages: • By ﬁnding all the pathways between any pair of elements (vertices), GAM can detect the existence of interdependencies between any pair of elements, and identify all the nth order inﬂuence domains for any element in the graph. Therefore, it is an exhaustive analysis instead of a ’what if’ analysis. • The order of the inﬂuence domain determines the impact index from one element to the others. Thus it may give both essential information on where to buﬀer the cascading failures with minimum cost and the priority of these elements under a given disaster context; • Since the vulnerability of strongly coupled components is determined by its weakest section, based on the calculated results of the SCC, critical components can be detected, and a vulnerability assessment can be obtained. Furthermore, by SCC identiﬁcation, interdependencies control strategies (ICS) are more rational and eﬀective. 35 Chapter 3. Survival from Disaster by Interdependencies Management 3.3 Interdependencies Control Strategy (ICS) Based on GAM For critical services in the NCIs to work, multiple utilities need to be available simultaneously and running at full capacity. For instance, to maintain the normal operability of a hospital, the simultaneous availability of electricity, water, steam, natural gas, medicine, nurses, doctors, foods, communication, and transportation must be assured. This full capacity state is more fragile than any other state, for in this state, a number of requirements must hold simultaneously. According to the theory on “the fragility of goodness” [10], once one of them fails, the functionality of the hospital will be greatly degraded. The purpose of proposing the concept of interdependencies control in this paper is to try to reduce the sensitivities of critical services on unexpected ﬂuctuations of external resources. This can be implemented by adjusting the interdependency degree by either splitting the network into several islands or just shutting down the related physical connectivity. Based on computation of GAM and a reliability assessment of the utilities, as proposed in this paper, interdependencies control strategy can help to assign limited resources to the most critical services, while avoiding the propagation of cascading failures to other infrastructure layers. Since the interdependencies control strategy (ICS) is mainly focused on the response stage in the four phases of emergency management, it is convenient and necessary to brieﬂy review the conceptual framework for emergency management as follows. 3.3.1 Basic Introduction to Emergency Management Emergency management is the discipline of dealing with and avoiding risks [11]. As Figure 3.7 illustrates, it generally includes four diﬀerent stages [2]: • Mitigation: Long before the disaster. This refers to the sustained actions to reduce or eliminate the long-term impacts and risks associated with disasters. • Preparedness: Long and shortly before the disaster. This refers to the policies, procedures and plans for how to best manage an emergency. • Response: During and shortly after the disaster. This refers to the actions taken during or directly after an emergency occurs. 36 Chapter 3. Survival from Disaster by Interdependencies Management Analysis Planning Normal Coordination Monitoring Coordination Emergency Alert Recovery Self-actualization Esteem Love/Belonging Safety Pysiological Maslow’s Hierarchy of Huam Needs Figure 3.7: The time line for emergency management. The ﬁve levels of human needs imply the priority of these critical infrastructure networks during emergency states. • Recovery: Shortly and long after the disaster. This refers to the eﬀorts taken to repair and restore communities after an emergency. Based on Maslow’s theory of human motivation [13], humans have diﬀerent levels of needs constrained by their socio-economic background factors. A connection has been established between human motivation theory and emergency management due to the dynamic characteristics of emergency conditions [2] (see Fig.3.7). The convection can give helpful information on prioritizing the diﬀerent infrastructure lifelines during emergency states. 3.3.2 Survivability Index of an Island (SII) By applying the GAM-based interdependencies control strategy (ICS), our infrastructure networks can be divided into several islands during a disaster. The survivability index of an island can be brieﬂy expressed as how long this island can survive before its linkages are re-established. Mathematically, for an island with m internal backup resources, and n linkages connected with external resources, assume the availability duration of the backup resource i is ti (i ∈ [1, m]), here ti ≤ 0 indicates that utility i has been used up for ti (time units). The estimated recovery time under a certain disaster context 37 Chapter 3. Survival from Disaster by Interdependencies Management D for linkage j is E(Tj ) (j ∈ [1, n]). The survivability index of island k can then be deﬁned as: ⎧ min(t ) ⎪ ⎨ max(E(Ti j )) (max(E(Tj )) > 0) SIIkD = ⎪ ⎩ min(t ) (max(E(T )) = 0) i j The objective of interdependencies control during a disaster D is to maintain SIIkD not less than 1. The details on ICS will be discussed in Section 3.3.3, the related measures to improve SII during the four phases of emergency management cycle will be addressed in Section 3.3.4. 3.3.3 Interdependencies Control Strategy It is well-known that among our modern infrastructure networks, the electrical network is the most fundamental and important infrastructure. Since it is in the lowest layer of our infrastructures pyramid, it supports and thus assures the operation of most other infrastructures. The concept of interdependencies control is based on our previous work [2][3][4], and it also has been inspired by the controlled islanding strategy of power networks. It is well known that in power systems, controlled islanding is a special protection strategy aimed at preventing a system-wide blackout as a result of the cascading of low probability events [4]. The diﬀerence between controlled islanding strategy and ICS is that, in ICS, it is usually not necessary to split the network into several islands. In most cases, interdependencies control means shutting down several outgoing linkages, thus ensuring the availability of scarce resources, or isolating failures (e.g. epidemics), within a certain limited area. This decision making process for the GAM-based interdependencies control strategy (see Fig.3.8) is brieﬂy explained as fellows: Step 1: Identify all modellable physical interdependencies, and represent them with the generalized adjacency matrix (GAM); Step 2: Based on the calculations of GAM, identify the supporting utilities for these critical services with higher priority and sections with vulnerabilities, such as strongly coupled components (SCCs); Step 3: Monitor the possibility of new disasters online with an early warning system (EWS). If a disaster happens, broadcast warnings, carry out the anticipated recovery-oriented actions, and ﬁnally perform ICS according to the priority of the essential missions; Step 4: After interdependencies control, if the SII for each island is 38 Chapter 3. Survival from Disaster by Interdependencies Management Physical interdependencies representation by generalized adjacency matrix (GAM) Further Information abstraction based on GAM computation Online monitoring by early warning system (EWS) No New disaster D Emerges? Yes SII 0? Yes No Warning Broadcast Interdependencies Control to redistribute limited resources etc. Recovery-oriented Responses ICS-based Decision Making Recovery Figure 3.8: Decision making ﬂow chart for Interdependencies Control Strategy (ICS). not less than 0 after the expected duration of restoration, its recovery processes will receive the highest priority. Otherwise, there are many measures to maintain the critical service survival as long as possible. The detailed content on improving SII will be described in the next section. 3.3.4 Measures for Improving SII As the survivability index of island (SII) is mainly determined by (1) the scarce resource, or the backup lifeline with the minimum supporting duration; (2) the recovery time; hence to improve SIS of each island, various measures at the four phases of emergency management cycle are described below. Mitigation Stage • Infrastructure design taking the following properties in consideration: risk-decentralized redundancy, multi-functionality, adaptivity to the 39 Chapter 3. Survival from Disaster by Interdependencies Management statistic patterns of local events, maintenance/recovery-oriented characteristics, etc. Preparedness Stage • Early warning capability by monitoring possible disasters online, presolutions based on historical experiences, etc. Response Stage • Redistribute the limited resources from other external resources, or redirect them from other islands whose SII is less than 1. • Degrade the operability capacity of the island. • Supply critical missions in the island with “synchronized rolling availability”, which is very similar to a rolling blackout during power outage, but instead of losing services totally, it can keep the system operated with a low service quality. • Mobilized lifelines/resources, such as mobile generators etc. • Make use of convertible utilities, as well as multi-functional resources. As there exists overlap of these utilities’ functionality, it is possible to move from one to the other during a disaster state, like switching between gas, oil, steam, or electricity for heating. Recovery Stage • Personnel training, prioritization of critical infrastructures under all possible scenarios; Optimization of the restoration time by dynamic programming etc. 3.4 Application of ICS on the UBC Campus Case In this section, based the snow-caused power outage of Vancouver in the winter of 2006, which aﬀected the utilities in the campus of UBC, comparisons of survivability of the isolated critical service(s) with and without ICS is presented. Decision making processes aided by GAM calculation during the mitigation, response and recovery phases of emergency management cycle are also presented. 40 Chapter 3. Survival from Disaster by Interdependencies Management 01 :20 02: 10 Power Outage from BC_Hydro Fuel Pipe Out of Work ( Sending oil from power house to steam station) 3 : 20 Power Restored 3 : 20 PM 15 : 00 PM 02: 00 27/ 11/ 2006 1 : 00 AM Water Pipe Fixed ( Sending water to Hospital ) 27/ 11 / 2006 3 : 00 AM 28//11/2006 3:20 AM 24 :00 28/ 11/ 2006 15 : 00 PM 29/ 11/ 2006 1 : 00 AM Fuel Pipe Restored Water Pipe Broken ( Sending water to Hospital ) 23:00 PM 01 :40 Figure 3.9: Time line of the events at UBC campus triggered by the 2006 winter snow storm and their restoration processes optimized by GAM-based ICS strategy. 3.4.1 Scenario Description On November 26, 2006, 20-40 cm of heavy snow fell across Greater Vancouver, Victoria, and the rest of the South Coast. The weight of the heavy snow brought branches and trees down on power lines [19][20]. Because of the snow and the resulting power outage at the UBC-Point Grey campus, the whole campus was closed on November 27, 2006, following the No.68 university policy. The campus power outage lasted for about 24 hours [5]. Time-line of the scenario The time line for this scenario can be seen in Fig.3.9. The detailed description for the triggering events in this scenario is as follows: • Initial state: t = t0 , the whole campus runs normally; • t2 = t0 +21(min), Event Ea : Fallen trees brought down the transmission lines sending power to the UBC Substation ; • t3 = t0 +40(min), Event Ec : The water pipe linking the water station to UBC hospital burst; • t3 = t0 +70(min), Event Eb : The fuel pipe linking the power house to the steam station is out of work. The topological locations of the events: Ea , Eb and Ec of the UBC case can be found in Fig.3.10. 41 Chapter 3. Survival from Disaster by Interdependencies Management TERASEN GAS_1 2 gas BC Hydro 1 power Ea UBC Campus Hospital 6 SubStation 5 steam gas power power Power House 9 Ec water water power GVRD 3 Water Station 7 oil water oil Steam Station steam Eb power 8 power gas water Noncritical Cells 10 TERASEN GAS_2 4 Figure 3.10: Cells on UBC campus. Where the cross “X” in the ﬁgure represents the topologicallocation of an event. Related Parameters and Data To calculate the survivability index of a component in the UBC case, related parameters of the cell on UBC campus can be seen in the following Table 4-A [5]1 . Table 4-A: Duration of Reserved Resources in Cells Reserved Resources in Cells t6ele backup electricity in cell 6 t6wat reserved water in cell 6 t7wat reserved water in cell 7 t9oil reserved oil in cell 9 48 32 24 24 24 After ICS hours (with steam) hours ( no steam) hours hours hours Before ICS 24 24 12 12 hours hours hours hours The expected recovery duration of these events are in the following Table 1 Due to information privacy, part of the data were estimated by Lucy from her interview meetings with the utility guys of UBC. 42 Chapter 3. Survival from Disaster by Interdependencies Management 4-B. Table 4-B: Expected Recovery Duration of Event Event Restoration Duration Ea 24 hours Eb 12 hours Ec 8 hours The duration of emergence response operations can be seen in Table 4-C, where N ormal refers to normal response action, and ICS refers to response action of Interdependencies Control Strategy. Table 4-C: Duration of Emergence Response Operations Response Action N ormal ICS 3.4.2 Duration 1 hours 2 hours ICS-based Decision Making Activity during Emergency and Recovery State The purpose is to prevent the functionality of the whole campus from collapsing, and especially, to keep the critical service(s) survive during this constructed scenario. With limited restoration resources, aided by GAMbased calculation, the Emergency Operation Center (EOC) will take the following steps to make decision: Step 1: With the represented topological relationship in Fig.3.10, after GAM-based calculation, a critical service : the UBC hospital is identiﬁed. (since our research objective of JIIRP is to save as many lives as possible during a disaster). External sources or external cells, such as cell {1} (BC Hydro), cell {3} (GVRD), cell {2} (TERASEN GAS1) and cell {4} (TERASEN GAS2) are identiﬁed; Step 2: No strong coupled cells (SCCs) are identiﬁed in this case; Step 3: Identiﬁed by GAM calculation, the inﬂuence domain of these events through the impacted channels. Cells impacted by the T-line fault event Ea is {5, 6, 7, 8, 9, 10}; Cells impacted by the fuel pipe fault event Eb is a set of cells {6, 8, 10}; Cells impacted by the water pipe fault event Ec is a set of cells {6, 7, 8, 10}. Without applying ICS, there are three islands identiﬁed by GAM computation: island {1}, island {3} and island {2, 4, 5, 6, 7, 8, 9, 10}. After applying ICS method to shed these non-critical loads: cell {10}, there are four islands identiﬁed: island {1}, island {3} , island {10} and island {2, 4, 5, 6, 7, 8, 9} . Step 4: SII Computation: which requires computing both the internal 43 Chapter 3. Survival from Disaster by Interdependencies Management Event(s) Normal SII= -1 20 r Ear Eb 24 45 SII= 23 44 SII= SII= Emergency Phase 16.5 32 r Ec 15 36 SII= Recovery Phase r Eb Ecr Ear -13 SII= 8 -9 SII= 12 Ecr Eb SII= -21 r SII= -21 SII= Ecr Ecr Ear -7.5 8.5 SII= 8 24 Ear SII= -15.5 SII= -15.5 SII= -9 12 Ebr SII= 3 24 Ebr Ear SII= -21 SII= -21 Figure 3.11: Decision making tree for the recovery phase without ICS operations. Where Ear (Ebr , Ecr ) refers to the recovery actions of Ea (Eb , Ec ). self-suﬃcient duration tint and the external self-suﬃcient duration text of i i one utility. The external self-suﬃcient duration of one lifeline can be calculated along its upstream pathway identiﬁed by GAM computation. The restoration duration of each event can be estimated by their expectation value from historical records. Step 5: Decision making for restoration order of multiple events based on SII value. Due to limited recovery and maintenance resources, we assume that the restoration actions for these events have to be executed one by one. Case I: During Step 3 to Step 5, the restoration process without ICS operations can be seen in Fig.3.11. Here we can see that without ICS operations, the critical service (UBC hospital) can not survive during this disaster. Since by this decision making tree, non-option has a SII greater than zero after the ﬁnal restoration. Case II: During Step 3 to Step 5, with ICS operations can be seen in Fig.3.12, where represented by “⊗”, event EICS1 (EICS2 ) refers to shedding the non-critical loads on UBC campus. The restoration process based on ICS can be seen in Fig.3.13, were we can see that after ICS operations, the critical service (UBC hospital) can survive in this disaster. Due to this decision making tree in Fig.3.13, there are four options with a SII greater than zero 44 Chapter 3. Survival from Disaster by Interdependencies Management TERASEN GAS_1 2 gas BC Hydro 1 UBC Campus Hospital 6 power Ea SubStation 5 Ec steam gas power oil water oil EICS2 water Steam Station Eb power 8 EICS1 steam power GVRD 3 Water Station 7 power Power House 9 water water power gas Noncritical Cells 10 TERASEN GAS_2 4 Figure 3.12: ICS operations (represented by circled cross “⊗”) of redistributing scarce resources during emergency stage. after the ﬁnal restoration. According to the obtained results in Step 3, the order of the size of the inﬂuence domain of these events is Ea > Ec > Eb , therefore the decision branch with the restoration order Ear → Ecr → Ebr is picked. By comparing the above two processes, we can see that without ICS operations, the critical service on UBC campus can not survive during this diaster; While with ICS operations, its survivability can be assured. If ICS operations are taken during emergency response phase, even the recovery actions are executed randomly, there is a 66% probability that the critical cells will survive in this snow disaster. 45 Chapter 3. Survival from Disaster by Interdependencies Management Event(s) SII= 24 46 Emergency Phase ICS SII= 22 20 Ebr Ear 34 44 SII= 33 32 SII= Ecr 26 36 SII= Recovery Phase Ebr Ear 14 12 SII= Ecr Ebr Ecr SII= 2 SII= 2 SII= 10 8 Ecr SII= SII= 1 Ecr 9 8 SII= Ear 25 24 SII= Ear Eb 2 12 r SII= 1 SII= -10 Ebr SII= 14 24 Ear SII= -10 Figure 3.13: Decision making tree for the recovery phase after ICS operations. Where Ear (Ebr , Ecr ) refers to the recovery actions of Ea (Eb , Ec ). 3.5 Conclusion For a system of systems, such as the interdependent critical infrastructure networks, various measures can be taken to reduce the frequency of failures. However, tracking all such interdependencies is too complex, the survival of critical missions is more tractable than preventing all large cascading failures. With the multi-interdependencies represented by the generalized adjacency matrix (GAM), also based on our previous results [2][3][4], we have proposed a more practical approach to respond to a large disaster. This approach helps control the interdependencies among the critical infrastructure networks, according to a risk analysis under the disaster context, and, therefore, prevents failures from spreading. The proposed strategy is an eﬀective means to reduce the inherent vulnerability, as well as to increase the resiliency of critical infrastructure networks. Future work can be on • developing methods for optimizing the survivability index of an island (SII) according to the local event spectrum; • identiﬁcation of complicated cascading patterns by data mining [15]; 46 Chapter 3. Survival from Disaster by Interdependencies Management • further analysis with complex network theory [16, 17]; • building a database of all these hidden interdependencies experienced under certain disaster contexts; • application of queueing theory in GAM-based decision making process against multiple events. Acknowledgements The authors gratefully acknowledge the contributions of J. A. Hollman, J. Jatskevich, and C. Ventura for their inspiring work on this topic. We also deeply give our thanks to Alejandro Cervantes and Tom De. Rybel, for his discussion and suggestions in writing this paper. 47 Chapter 3. Survival from Disaster by Interdependencies Management 3.6 Bibliography [1] R. Little, “Toward more robust infrastructure: observations on improving the resilience and reliability of critical systems”, in Proceedings of the 36th Annual Hawaii International Conference, 6-9 Jan, 2003. [2] J. A. Hollman, J. R. Marti, J. Jatskevich, and K. Srivastava, “Dynamic islanding of critical infrastructures: a suitable strategy to survive and mitigate extreme events”, International Journal of Emergency Management (IJEM), vol.4(1), pp.45-58, 2007. [3] J. R. Marti, J. A. Hollman, C. Ventura, and J. Jatskevich, “Dynamic recovery of critical infrastructures: real-time temporal coordination”, International Journal of Critical Infrastructures, vol.4(1), pp.17-31, 2008. [4] J. R. Marti, K. Srivastava, J. A. Hollman, and J. Jatskevich, “Design for survival: Real-time infrastructures coordination”, in Proceedings of the International Workshop on Complex Network and Infrastructure Protection (CNIP2006), Rome, Italy, 2006. [5] L. Liu,“Prototyping and cells modeling of the infrastructure interdependencies simulator i2sim”, Master’s thesis, University of British Columbia,2007. [6] C. Godsil and G. Royle, Algebraic Graph Theory, Springer, 2001. [7] C. Perrow, Normal Accidents: Living with High-Risk Technologies New York: Basic Books, pp.89-100, 1984. [8] R. Diestel, Graph Theory. New York: Springer-Verlag, 1997. [9] T. H. Cormen, C. E. R. Leiserson, L. Rivest, and C. Stein, Introduction to Algorithms, Second Edition. (pp.552-557.). MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.5. [10] L. Levantovskii,“singularities of the boundary of the stability domain”, jour Funkts. Anal. Prilozh., vol. 16, pp. 44-48, 1982. [11] G. D. Haddow and J. A. Bullock, Introduction to Emergency Management. Amsterdam: Butterworth-Heinemann, 2004. [12] J. R. Marti, “Simulation of infrastructure interdependencies dynamics for disaster response coordination”, JIIRP UBC Workshop, presentation, 2007. [13] A. H. Maslow, “A theory of human motivation”, Psychological Review, vol. 50, pp.370-396, 1943. [14] N. Senroy and G. T. Heydt, “A conceptual framework for the controlled islanding of interconnected power systems”, IEEE Transaction on Power Systems, vol. 21(2), pp.1005-1006, 2006. [15] M. L. Gargano and B. G. Raggad, “Data mining — a powerful information creating tool”, OCLC Systems and Services, vol.15(2), pp.81-90, 1999. [16] A. L. Barabasi and R. Albert, “Emergence of scaling in random net48 Chapter 3. Survival from Disaster by Interdependencies Management works”, Science, vol.286, pp.509-512, 1999. [17] S. H. Strogatz,“Exploring complex networks”, Nature, vol.410, pp.268276, 2001. [18] D. M. Cvetkovic, M. Doob, and H. Sachs, Spectra of Graphs: Theory and Applications, 3rd ed, New York: Wiley, pp.2-14, 1998. [19] BC HYDRO, “BC HYDRO Winter Storm Report October 2006-January 2007”, Island BC HYDRO, pp.79-88, 2007. [20] Minsitry of Public Safety & Solicitor General , “Preparedness is Key in Cold Weather and Power Outages”, (2006 PSSG 0060-001436 ) 2006. [21] M. O. Ball, “ Computational complexity of network reliability analysis: an overview”, IEEE Transactions on Reliability, Vol.35, pp.230-239, 1986. [22] H. J. Vermculen, J. M.Strauss, and V.Shikoana, “Online estimation of synchronous generator parameters using PRBS perturbations”, IEEE Transactions on Power Systems, Vol.17, pp.694-700, 2002. [23] H. J. Garcia, “Multi hazard risk assessment of critical infrastructure: an interdependency approach”, PhD Proposal, University of British Columbia, March. 2009. 49 Chapter 4 Identifying Cascading Pathways for Power Outage Mitigation 4.1 Introduction During the past several decades, as a result of heavy ice/wet-snow storms, many countries experienced large-scale power blackouts with huge monetary loss, for example, Western Canada-Northeast USA in Jan. 1998 [2], B.C. Canada in Nov. 2006 [3], Southern and Central China in Feb. 2008 [4], Northeast USA in Dec. 2008 [5], and Southern and Eastern USA in Jan. 2009 [6]. Aﬀected by climate change, not only the damage degree of these storms were unbelievably higher than before, but their spatio-temporal patterns were becoming uncertain, for instance, Southern and Central China (2008) [4] and Southern USA (2009)[6], which have not experienced such severe ice/wet-snow storms for many years, were seriously impacted. Scientists believe that, as a result of climate change, similar events will be more frequent, more severe, and longer lasting in the near future [7][8]. To protect our power network, especially overhead transmission lines, from damage caused by ice/wet-snow storms, currently there are several research options, such as studies on the ice accretion mechanisms [9], failure mechanisms of iced outdoor insulation equipments [10], anti-icing and deicing methods [11], on-line monitoring and diagnosis of icing [12], online evaluation, prediction and decision making of icing [13][14], establishment of an emergency response system against ice-snow disaster [15] etc. But up to now, most of these prevention and treatment methods focusing on diﬀerent aspects in power outages, have not been systemized or standardized 1 A version of this chapter has been accepted for publication. DeTao Mao, Jose R. Marti and K. D. Srivastava (2009), Mitigation Snow-Caused Power Outage along Cascading Pathways, the 2009 IEEE International Conference on Technologies for Homeland Security (HST’09), Waltham, MA, USA, May 11-12, 2009. 50 Chapter 4. Identifying Cascading Pathways for Power Outage Mitigation for industry applications, For instance, it will be challenging to adapt these Joule-eﬀect-based deicing and anti-icing methods, which have been applied in many countries before, to our modern large-scale power networks [11]. Diﬀerent to these methods stated above, we propose a systematic approach to inhibit the development of similar disaster as well as to mitigate its propagation along these cascading pathways. This approach is based on our investigation of the 2006 power outage caused by a snow storm in Vancouver area (BC, Canada), where by analyzing the evolution processes and considering the changed climate, the root causes of this disaster and possible chain-reaction pathways have been carefully studied. The content of this paper is organized as following. In Section 4.1, we give a short introduction on the background and a brief review of current research related to atmospheric icing issue in power systems. In Section 4.2, the power outage caused by the snow storm in Nov. 2006 at Vancouver is investigated. The root causes of this blackout and the eﬀects of climate change are described, followed by an analysis on the dependency network containing these cascading pathways. In Section 4.3, based on analyzing the emergence mechanism of the disaster, systematic countermeasures for blocking these manageable cascading pathways, such as building an early warning system against snow storm and inhibiting wet-snow storm by artiﬁcial precipitation stimulation (APS) etc., are summarized. Finally, our study is concluded in Section 4.4. 4.2 Investigation on Vancouver’s 2006 Snow-Caused Power Outage On Nov. 27th, 2006, an unexpected heavy snow storm in the Vancouver area, including: Vancouver, North Vancouver, Lions Bay, Bowen Island, Surrey, Burnaby and Maple Ridge etc., resulted in a sustained power outage. It was reported that this power outage, was mainly caused by falling trees and snow-damaged power lines [3]. Contrast to the conclusion in [16], which states that this is a typical snow-caused power outage. By analyzing the development process of this disaster, especially the root conditions leading to the cascading failures, we discovered that climate change had played an importance role in this disaster. 51 Chapter 4. Identifying Cascading Pathways for Power Outage Mitigation 4.2.1 Several Root Causes Introduced by Changed Climate Compared to snow-caused large blackouts under normal circumstances, the Vancouver 2006 outage, caused by climate change as well the greenhouse eﬀect, has some special characteristics, which can be summarized as follows: The First Heavy Snow Date Was Early at Vancouver in 2006 Based on the data from [17], both the ﬁrst snow dates and the ﬁrst heavy snow dates in Vancouver B.C. from 1997 to 2007, are listed in Table 4.1. According to this table, it was about 10 days earlier than the average date. Moreover, the ﬁrst snow and the ﬁrst heavy snow (lasting over three days) happened at the same time in 2006. This early heavy snow brought forth some negative eﬀects on local power networks. For instance, electrical load impacts, the falling probability of trees over transmission line; Otherwise, if it snowed several weeks later, these preconditions that had induced the power outage might become very rare, the reserved margin capacity in power systems would have been better prepared for winter load peak, and with less moisture and less foliage, the trees would be more resilient during this storm. Table 4.1: Data on Vancouver ’s Snow Dates (1997-2007) First Snow Dates Dec 18, 1997 (1 day) Dec 21, 1998 (3 days) Dec 14, 1999 (1 day) Dec 14, 2000 (3 days) Nov 29, 2001 (3 days) Dec 24, 2002 (1 day) Nov 22, 2003 (1 day) Dec 6, 2004 (1 day) Nov 28, 2005 (5 days) Nov 25, 2006 (5 days) Nov.26, 2007 (1 day) Annual Heaviest Snow Jan 1, 1998 (4 days) Dec 21, 1998 (3 days) Dec 31, 1999 (2 days) Dec 14, 2000 (3 days) Jan 17, 2002 (3 days) Mar 7, 2003 (3 days) Dec 30, 2003 (4 days) Jan 6, 2005 (3 days) Nov 28, 2005 (5 days) Nov 25, 2006 (5 days) Jan 7, 2008 (4 days) 52 Interval 14 0 17 0 49 102 38 31 0 0 41 Chapter 4. Identifying Cascading Pathways for Power Outage Mitigation Climate Change/ Greenhouse Effect Non-updated Policies On Vegetation Management Temperature under Freezing Point Extended Growing Season Overgrown Trees Moister in trees making them fragile when frozen Deciduous time delayed Heavy and Early Wet Snow Low Wind Speed More Snow/Ice accumulated on trees More branches or trees might fall upon overhead T- Lines, bus cables, telephone lines and roads etc Figure 4.1: Synthesized eﬀect of delayed deciduous time, extended growing season and unchanged policies on vegetation management upon the collapse probability of trees and branches. The Deciduous Time Delayed by the Eﬀect of Greenhouse Another factor that had worsened the eﬀect of falling trees, was trees’ deciduous time. Since a tree with more leaves and larger canopy could catch more wet snow, and internal moisture might make trees much fragile when frozen. According to [18][19], the greenhouse eﬀect has delayed the deciduous time of trees. Based on data collected across Europe, they found during the last 30 years, autumnal senescence has been delayed by 1.3 to 1.8 days per decade. During an early and long lasting wet snow, this may highly increase the collapse probability of tree, especially when the temperature is below freezing point. The causal relationship/dependencies between climate change, temperature, and the collapse probability of trees is displayed in Fig.4.1. The Growing Season of Tress has been Extended Due to climate change, many woody and herbaceous plants in mid to upper latitudes are signiﬁcantly advanced in spring bud break and similarly signiﬁcantly delayed in autumn with leaf color change and leaf fall, resulting in an extension of the growing season. Remote sensing of vegetation using the normalized diﬀerence vegetation index shows a 12-day extension of the growing season in North America between 1982 and 1999 [21]. Thus for 53 Chapter 4. Identifying Cascading Pathways for Power Outage Mitigation Figure 4.2: The temperature curve (upper ﬁgure) and wind speed curve (lower ﬁgure) during Nov 22th to Dec 4th 2006 in Vancouver area . trees along essential transmission line and key roads, our previous frequency for pruning trees, usually once 4 − 8 years [16], should be modiﬁed with the above facts in consideration. 4.2.2 Unchanged Policies of Vegetation Management by BC Hydro According to [16], before 2006, factors such as climate change and greenhouse eﬀect etc. are not considered by BC Hydro in its vegetation management. After the 2006 power outage, BC Hydro planned to invest more in vegetation management, but evaluation on eﬀects such as extended growing season, new growing patterns and delayed deciduous time etc., which have been introduced by changed climate, were still not mentioned, let alone quantiﬁed and considered [16]. 4.2.3 Related Weather Factors Aﬀecting Ice Accretion on Overhead Wires The snow storm lasted from Nov 25 until Nov 30, during which, the tendency of related weather factors are displayed in Fig.4.2. The maximum wind speed was less than 40km per hour, and averaged less than 24km per hour, and the local temperature was below the freezing point of water. Based on the conclusions in [9], these factors have induced and positively eﬀected ice accretion on overhead wires. With snow accumulated on overhead lines, falling trees would highly increase the probability of snow-caused line fault. 54 Chapter 4. Identifying Cascading Pathways for Power Outage Mitigation 4.2.4 Impacted Critical Infrastructure Networks Low temperature following this unexpected early snow had made the customers turn on their air-conditioning equipment simultaneously, which impacted the power systems heavily. In some situations, power systems without enough reserved capacity, after such an impact maybe pushed beyond their stability margin. Except the electric network, during this storm, there were several other related critical infrastructures that had contributed to the ﬁnal blackout, such as the transportation network and the communication network, since their un-availabilities would hinder recovery from a power outage. The transportation network was slowed down because of the slippery road surface caused by wet snow and freezing rain. Driving on roads became very dangerous, especially on curves and slopes. Bus-cable failures due to fallen trees or branches made situation worse. Since many buses were out of work, more private cars might jam the road. As to the communication network, according to [22], quite a number of telephone lines were damaged by the fallen trees and atmospheric icing. 4.2.5 Dependency Network Representation for the Power Outage in Vancouver 2006 According to the above analysis in Section 4.2.3 and Section 4.2.1, as well as considering these hidden interdependencies unfolded during this disaster, a sequential diagram has been built to represent the causal relationship among these elements, in which each cascading pathway starts from the root causes, passing by aﬀected events or objects, and ﬁnally reaching their common destination: “the blackout of Vancouver”. The manageability of each pathway has been analyzed, classiﬁed and labelled. Mitigation treatments or prevention methods are only permitted along these manageable pathways. The whole dependency network structure leading to this power outage can be seen in Fig.4.3, in which the related elements (in boxes) are connected by cascading pathways (solid or broken lines). These concurrent processes or preconditions are represented, which pinpoints the mechanism of this power outage and facilitates the ﬁnding of countermeasures that will be discussed below. 55 Chapter 4. Identifying Cascading Pathways for Power Outage Mitigation Greenhouse Effect/ Climate Change Extended Growing Season Non-updated Policies On Vegetation Management Delayed Deciduous Time Low Wind Speed Early and Heavy Wet-Snow Temperature under Freezing Point 1 Overgrown Trees Snow/ice accumulated on T-lines Internal moisture making trees fragile when frozen More snow/ice accumulated on Trees Snow/ice accumulated on Roads 2 (a) Snow/ice accumulated on Bus cables Snow/ice accumulated on Teleph-Lines 5 (a) 4 (a) Branches or trees fell down on T- Lines, Bus cables, Telephone lines and roads Load Impacts 6 (a) 3 (c) 3 (a) 3 (b) Degraded Traffic T-Line Fault Events 2 (b) 4 (b) System Integrity Broken 6 (b) Affected Communication 5 (b) Delayed Recovery Processes 4 (c) Concurrent Processes Manageable Pathway Power Outage Un-Manageable Pathway Figure 4.3: Dependency network for these cascading pathways unfolded during the power outage in Nov, 2006 at Vancouver area (B.C., Canada). 4.3 Countermeasures against Snow-Caused Power System Failure In this section, we aim to develop a mitigation strategy or countermeasure along manageable cascading pathways (dotted lines in Fig.4.3) in order to isolate related events in a limited range, or mitigate the overall impact of 56 Chapter 4. Identifying Cascading Pathways for Power Outage Mitigation snow storm to a certain degree, thus reducing the probability and risk of power system failure. According to our best knowledge, most of the current anti-icing and deicing methods at power industry are not available for wide application, while the cost of building a transmission network which may tolerate any degree of snow storm would be extremely high. Based on our previous analysis of the Vancouver case, particularly the sequential diagram in Fig.4.3, a systematic solution against snow-caused blackout is proposed and described in two aspects: • actively inhibit the development of ice/wet-snow storms; • block cascading along manageable cascading pathways. the detailed content will of them be explained below respectively. 4.3.1 Active Suppression on the Development Process of Atmospheric Icing Much attention on Climate Change (CC) is directed towards mitigation measures for reducing greenhouse gas; However, the complexities and uncertainties in CC science and predictions, which warrant that investment in adaptation measures to manage climate risks may prove to be more certain and tangible beneﬁts rather than just reducing CO2 [23]. According to Fig.4.3, meteorological factors globally aﬀect all downstream events and objects. Once these meteorological processes emerge concurrently, atmospheric icing will come into being. Longer duration of precipitation of wet-snow, will result in more ice accumulating on trees, transmission lines, bus cables, roads, telephone lines etc., and increase the probability of a power system failure. Corresponding to the manageable cascading pathway 1 in Fig.4.3, an intuitive idea is to reduce its duration or at least inhibit the coexistence of preconditions that have induced the ice accretion process. Based on the advancement of modern meteorological technologies and especially based on the feasibility studies of forecasting heavy snow storms[23][24], we propose some meteorology modiﬁcation methods, such as artiﬁcial precipitation stimulation (APS). The eﬀect of artiﬁcial precipitation stimulation (APS) can be seen in Fig.4.5. The decision making process for APS can be seen in Fig.4.4. Here the time threshold value t1 can be calculated by the snow accretion model in [9][13]. As in[9], a formulae for determining the 57 Chapter 4. Identifying Cascading Pathways for Power Outage Mitigation Online Weather Monitoring Forecasting process No Will it snow/rain in t0? Yes Forecasting processes All other preconditions are satisfied? No Yes Based on the current ice accretion pattern, to calculate the threshold duration t1 No Snowing time > t1? Yes Warning Artificial Precipitation Stimulation Anticipated Responses Figure 4.4: Decision making process for artiﬁcial precipitation stimulation(APS) action. mass of accreted snow per unit length of wire can be expressed as 2 W = 4.5 e−6(T /T0 −0.32) Pn t VN0.2 (4.1) where T denotes the surrounding temperature (◦ C), T0 is a threshold value for determining whether it is raining or snowing, VN denotes wind speed (ms−1 ), Pn is the amount of snow passing around the wire per unit time (gt−1 ), t denotes time (s). Other countermeasures along cascading pathway 1 includes building an early warning system (EWS) for adverse weather, this would give critical infrastructure networks more time for preparation, possibly improving the survivability of essential services as well as reducing the monetary losses. 4.3.2 Blocking the Propagation of Disaster along the Manageable Cascading Pathways A manageable cascading pathway (MCP) refers a cost eﬀective pathways, in which beneﬁt of any feasible mitigation and/or countermeasure generally 58 Chapter 4. Identifying Cascading Pathways for Power Outage Mitigation Snowing process after APS Temperature Snowing process without APS Wind Speed Estimated Ice Accretion Duration Time window for APS Ice Accretion Duration after APS Humidity t0 t0' t1 t2 t3 Figure 4.5: Active suppression of the development process of atmospheric icing by artiﬁcial precipitation stimulation. Where t0 denotes present time, t0 denotes the APS action time, t1 denotes the beginning time of ice accretion, (t1 , t2 ) denotes the ice accretion duration after APS, while (t1 , t3 ) denotes the estimated ice accretion duration without APS. prevails the associated costs, otherwise it is called an unmanageable cascading pathway (uMCP). In Fig.4.3, except pathway 1, there are in total 10 manageable cascading pathways left. Besides anti-icing and de-icing methods in [11], other related countermeasures or mitigation strategies will be discussed in the following subsections. MCP 2(a) and 2(b) As shown in [26], the frequency of snow-caused outage is determined signiﬁcantly by the geographical location of the transmission lines. During snow storms (or ﬂood, hurricane and other adverse weathers), underground cable is more reliable than overhead cable, but it will be extremely costly to replace all these overhead lines [27]; Hence only locations with a higher frequency of line fault after a snow storm, and areas become inaccessible after the storm, should transmit electrical energy underground. Also as the reliability of a transmission line is mainly determined by its most vulnerable segment or weakest linkage, the load limits of these transmission-lines and supporting towers should also be evaluated, the weakest segments should be strengthened [28]. For instance, assume in Fig.4.6, there are n locations A1 , · · · , An which are vulnerable to snow storm, and the failure rate of an overhead transmission line at one of these locations is Po during a snow storm, then the probability of transmission failure is: P1ss = 1 − (1 − Po )3n (4.2) after replacing the overhead line with underground cable, assume the failure rate becomes Pu , the probability of transmission line after upgrade is P2ss , 59 Chapter 4. Identifying Cascading Pathways for Power Outage Mitigation Figure 4.6: Vulnerable geographical locations under snow storm along the transmission lines in Northern British Columbia. then the reliability comparison between the two cases is: 1 − (1 − Pu )3n P2ss = P1ss 1 − (1 − Po )3n ( Pu 3n ) Po (4.3) MCP 3(a),3(b) and 3(c) Each species of trees should be evaluated in terms of growing speed, falling probability, falling direction and possible falling range. According to [2], robust tree species should be planted beside roads and overhead lines instead of tree species which prone to fall under adverse weather condition. Typically, very tall or fast-growing vegetation, such as hackberry or ash trees, should be removed from the right-of-way to ensure safety and reliability. MCP 4(a),4(b) and 4(c) For snow/ice accumulated on roads, instead of traditional methods, such as anti-icing by spreading salt, de-icing by snow removal program, priority for the transportation networks before, during and after snow etc. should be systemically considered and carried out according to the latest forecasting information[24]25]. MCP 5(a) and 5(b) For overhead telephone lines prone to snow-induced failure, 4.3.2 can be taken, for instance, they can be replaced by underground optical ﬁbers. The communication infrastructure can also be strengthened by the installation of more wireless stations. 60 Chapter 4. Identifying Cascading Pathways for Power Outage Mitigation MCP 6(a) Since a large part of electrical load is aﬀected by weather factors, to reduce the load impacts under similar situation, previous plan for reserved generation capacity, maintenance schedule, transmission reliability analysis [26] etc. should be adaptive to new climate patterns [23], especially to these unexpected adverse weathers induced by climate change. MCP 6(b) Since these power outages were mainly and directly caused by faults on transmission lines, to keep the integrity of the whole power system, especially to keep these critical services or essential missions survive during adverse weathers caused by climate change, besides splitting strategy against cascading failures, risk de-centralizing generation options, such as mobility generators, distributed generation etc. should be considered in long term sense under the background of climate change. 4.4 Conclusion As a result of climate change, adverse weather will be more frequent and more severe. In order to prevent snow caused power outages, we have investigated the power outage in the Vancouver area in November 2006, and discovered that climate change seriously aﬀected this power outage. By considering all the related cascading processes during this disaster, a systematic solution has been proposed to suppress the development of the disaster as well as to block its propagation along cascading pathways. For similar future snow storms, we believe that, the probability of large-scale power outage can be highly reduced based on our solution. 4.5 Acknowledgment The authors deeply give our thanks to Arvind Singh, for his nice suggestions in the manuscript preparation of this paper. 61 Chapter 4. Identifying Cascading Pathways for Power Outage Mitigation 4.6 Bibliography [1] Government of Canada, “Joint infrastructure interdependencies research program (JIIRP)”, Online http://www.nserc.ca/programs/jiirp-e.htm, 2004. [2] J. McCready, “Ice storm 1998:lessons learned”, in 6th Canadian Urban Forest Conference, Kelowna, B.C., October 19-23, 2004. [3] CBC News, “Snowstorm blankets B.C.’s southern coast”, CBC News, Sunday, November 26, 2006 11:25 PM ET, November, 26 2006. [4] P. Sandene, “Massive snowstorms hit China”, Commodity Intelligence Report by Foreign Agricultural Service in USDA (United States Department of Agriculture), Tech. Rep., Feb, 1st, 2008. [5] SKY News, “U.S. storm leaves millions in dark”, http://news.sky.com, Dec 2008. [6] D. Shea, “Blackouts and deaths blamed on ice and snow storm warnings from Texas to Maine”, http://www.newser.com, Jan. 27 2009. [7] P. Hoeppe and G. Berz, “Risks of climate change - the perspective of the (re)insurance industry”, in Power Engineering Society General Meeting 2005, IEEE, vol.2, Munich Re, Munich, Germany, 2005, pp.2023-2026. [8] R. Billinton and C. Wu, “Predictive reliability assessment of distribution systems including extreme adverse weather”, in CCECE [online] http:// ieeexplore.ieee.org/iel5/7425/20197/00933530.pdf, May 2001. [9] Y. Sakamoto, “Snow accretion on overhead wires”, Philosophical Transactions of the Royal Society, vol.358, pp.2941-2970, 2000. [10] CIGRE Task Force 33.04.09, “Inﬂuence of ice and snow on the ﬂashover performance of outdoor insulators, part I: eﬀects of snow”, Electra, vol.188, pp.55-69, 2000. [11] M. Farzaneh, Atmospheric Icing of Power Networks, Springer Netherlands, 2008, “Ch. 6th:Anti-icing and De-icing Techniques for Overhead Lines”, pp.229-268. [12] K. Oura, K. Kanemaru and R. Matsubara, “Application of a power line maintenance information system using OPGW to the Nishi-Gunma UHV line”, IEEE Trans on Power Delivery, vol.10(1), pp.511-517, 1995. [13] A. Veal and A. Skea, “Method of forecasting icing load by meteorology model”, in the 11th International Workshop on Atmospheric Icing of Structures (IWAIS), 2005. [14] J. D. Mozer and A. M. D. Gioia et al., “Predicting ice and snow loads for transmission line”, in Proceedings of the First IWAIS, 1983. [15] D. Lubkeman and D. E. Julian, “Large scale storm outage management”, in Power Engineering Society General Meeting, 2004. IEEE, vol.1, pp.16-22, June 2004. 62 Chapter 4. Identifying Cascading Pathways for Power Outage Mitigation [16] BC Hydro, “BC hydro winter storm report (October 2006- January 2007)”, BC Hydro and BCUC (B.C. Utilities Commission), Tech. Rep., 2007. [17] Vancouver Weather Website: http://www.wunderground.com/history/airport/ CYVR/2006/11/2/MonthlyHistory.html [18] A. Menzel, T. H. Sparks and N. Estrella, “European phenological response to climate change matches the warming pattern”, Global Change Biology, vol.12, pp.18, 2006. [19] G. Taylor, “Future atmospheric CO2 leads to delayed autumnal senescence”, Global Change Biology, vol.14(2), pp.264-275, February 2008. [20] A. Menzel and P. Fabian, “Growing season extended in Europe”, Nature, vol.397, p.659, 1999. [21] L. Zhou et al., “Variations in northern vegetation activity inferred from satellite data of vegetation index during 1981 to 1999”, Journal of Geophysical Research, vol.106, pp.20069-20083, 2001. [22] TELUS Communications Company, “Telecom decision CRTC 200772”, Canadian Radio-television and Telecommunications Commission, Tech. Rep., 2007. [23] J. McConnach, “How the power industry is adapting to climate change”, in 2008 IEEE PES General Meeting, July 20-24, Pittsburgh, PA, USA, 2008. [24] H. Cheng, Chad. Auld, G. Li, J. Klaassen, B. Tugwood and Q. Li, “ An automated synoptic typing procedure to predict freezing rain: An application to Ottawa, Ontario, Canada”, Weather and Forecasting, vol.19(4), pp.751-768, August 2004. [25] J. J. Cortinas, “A climatology of freezing rain in the great lakes region of north America”, Monthly Weather Review, vol.128(10), pp.3574-3588, October 2000. [26] D. O. Koval, B. Shen, S. Shen, and A. A. Chowdhury, “Modeling severe weather related high voltage transmission line forced outages”, in Transmission and Distribution Conference and Exhibition, 2005/2006 IEEE PES, 21-24 May 2006, pp.788-793. [27] unknown, “Important factors aﬀecting underground placement of transmission”, American Electric Power, Tech. Rep., 2000. [Online]. Available: www.aep.com/about/i765project/docs/UGvsOVHDPaper.pdf [28] R. W. Caswell and X. Andrews, “Foundation stability of wood-pole H frame structures for transmission lines”, Power Apparatus and Systems, Part III. Transactions of the American Institute of Electrical Engineers, vol.73(1), pp.245-255, Jan. 1954. 63 Chapter 5 Conclusions After the September 11th New York attacks, modelling, identiﬁcation and analysis of interdependencies among critical infrastructures was drawn increasing attention. Aﬀected by a changing global climate, as well as by the advancements and changes in technologies, economics and policies, the organizational structure and relationship of infrastructures are greatly changing. Furthermore, the revolution in information technology has resulted in more interconnected infrastructure networks, with greater centralized instead of distributed control. In fact, the trend towards higher degree of infrastructure interdependency has accelerated these years. More eﬀort should be devoted in studying the important role that interdependencies play in a changing environment, on the continuity and reliability aspects of infrastructure operation as well as on the increased security concerns and risks that might emerge given these hidden interdependencies. As a system of systems, our interdependent critical infrastructure networks are facing many unexpected events, which may cascade to a large-scale disaster through those interdependency pathways. Various measures can be taken to reduce the frequency of such kind of failures. However, in our current stage, tracking all such interdependencies is too complex, the price of preventing all possible failures may be extremely high, investing on the survival of critical services is more feasible than preventing all large cascading failures. With the physical interdependencies represented by the generalized adjacency matrix (GAM), also based on our previous results [1][2][3], we have proposed a more practical approach—Interdependencies Control Strategy—to respond to a large disaster. This approach can help to manage the interdependencies among the critical infrastructure networks, and, therefore, can improve the survivability of any critical service as well as prevent potential large cascading failures. The proposed strategy is an eﬀective means to reduce the inherent vulnerability of interconnected critical infrastructure networks and to increase their resiliency. For further research in this topic (accurately identifying, modelling and analyzing the complicated interdependencies of our critical infrastructures), information privacy will become the main bottleneck. 64 Chapter 5. Conclusions Also, as a result of climate change, adverse weather has a high probability to be more frequent, more severe and longer lasting. In order to prevent snow-caused power outages, we have investigated the power outage in the Vancouver area in November 2006 caused by a snow storm and discovered that unusual snow storm date, extended growing season and delayed deciduous time (all climate change related variables) had played an important role in aﬀecting this power outage. By identifying the related cascading processes during this snow storm, a systematic solution has been proposed to stop the development of the disaster, as well as to block its propagation along cascading pathways. For similar future snow-caused power outages, we believe that the probability of large-scale power outage can be highly reduced by our proposed solution. Moreover, the analytical technique developed in this study can also be extended to analyze the 2003 blackout in North America. The JIRRP team at UBC has taken an initial step in this direction by proposing an ontology and a simulator—I2Sim—to facilitate interdependencies research. But because of the strong nonlinearity and high complexity introduced by the connectivity among the infrastructure networks, interdependencies are still a very diﬃcult problem to analyze. In the real world, many factors, such as interdependencies type, varying environment, coupling degree, response behavior, event type, and system operation state etc. may create complicated challenges to any solution under a speciﬁed context. For future study, these directions can be undertaken: • Developing methods for optimizing the survivability index of an island (SII) according to both the global event spectrum and the interdependencies of local infrastructures; • Identiﬁcation of complicated cascading patterns by data mining [4]; • Detecting time-dependent hidden interdependencies with the help of formal veriﬁcation methods. 65 Chapter 5. Conclusions 5.1 Bibliography [1] Jorge A. Hollman, Jose R. Marti, Juri Jatskevich and K.D. Srivastava, “Dynamic islanding of critical infrastructures: a suitable strategy to survive and mitigate extreme events”, International Journal of Emergency Management (IJEM), vol.4(1), pp.45-58, 2007. [2] Jose R. Marti, Jorge A. Hollman, C. Ventura and J. Jatskevich, “Dynamic recovery of critical infrastructures: real-time temporal coordination”, International Journal of Critical Infrastructures, vol.4(1), pp.17-31, 2008. [3] Jose R. Marti, K.D. Srivastava, Jorge A. Hollman and J. Jatskevich, “Design for survival: Real-time infrastructures coordination”, In Proceedings of the International Workshop on Complex Network and Infrastructure Protection (CNIP2006), Rome, Italy, 2006. [4] Michael L. Gargano and Bel G. Raggad, “Data mining — a powerful information creating tool”, OCLC Systems and Services, vol.15(2), pp.81-90, 1999. 66 Appendices 67 Appendix A Introduction on I2Sim A.1 Conceptual Framework of I2Sim One of the goals of JIIRP is to build a simulator on interdependent infrastructures (I2Sim), which is capable of capturing the complex dynamics occurring in a system of multiple infrastructures as cascading events develop during large disaster situations. In which the system modelling and solution approach implemented is based on a time-sensitive coordination of the delivery of tokens (these vital goods and services) required to maximize as well as to keep human survivability. I2Sim models the network of diﬀerent infrastructures simultaneously. I2Sim simulator consists of several basic components [1][4], which can be listed as follows: • Tokens: Tokens are goods or services that are provided by some entity (e.g., manufacturer or distributor) to another entity that uses them. • Cells: A cell is an entity that performs a function. • External Sources: Resources brought into the system from outside the system. • Reserves: Resources available at the cells location. • channels: Channels are the means by which tokens ﬂow from a resource cell(node) to a consuming cell(node). • Distributor: A distributor divides the output of a cell to send it to other cells according to distribution factor. • Aggregator: An aggregator adds up external inputs and internal inputs to produce a total input. In our multiple infrastructures interdependency simulator (I2Sim), the components of the physical layer, tokens, cells, channels, external sources, reserves, distributors and aggregators etc. are integrated together by two 68 Appendix A. Introduction on I2Sim Figure A.1: Instance of cells, channels, reserve, external source, aggregators and distributors by UBC campus case. layers of operating relationships. The ﬁrst layer is the cell’s functionality, where speciﬁc amounts of input tokens are needed to produce speciﬁc amounts of output tokens, and this functionality is abstracted from human readable table (HRT, which will be explained in detail in Chapter B). Another layer is the physical (inter)dependencies layer among diﬀerent cells, since the tokens are delivered through channels from supplying cells and/or external sources to the consuming ones, the topological relationships and the channel characteristics (channel capacity and time delay) will give another set of conditions that must be satisﬁed. These two layers of functionality can deduce the matrix of transportation (Fig.A.2), where both the cell’s operability equation and the global physical linkages are well quantiﬁed and represented. A.2 Clustered I2Sim Integrated into a Single Machine The previous version of I2Sim was implemented by the ﬁve PCs of the 16machine PC-cluster at UBC power lab, whose topological structure can be seen in Fig.A.4. However, instead of using SCI communication in the pccluster distributed model [2](Fig.A.3), here a top system is created at the highest level, which includes the ﬁve cells as subsystems, data store memories [3] for global variables are applied to synchronize the ﬁve subsystems, and thus integrate the ﬁve cells into one single machine (Fig.A.5). This single machine prototype preserve the same properties and dynamical behavior as 69 Appendix A. Introduction on I2Sim p1 p2 p3 w1 w2 w3 r1 r2 r3 p1 x x x x x x y p2 p3 x x x y w1 y w2 y y y y x x x x x x y w3 x x x r1 r2 y r3 y y y y y y y y x x x x x x x x x Figure A.2: An instance of transportation matrix. Here x refers internal transmission link; y refers interdependency link; pi (wi , ri ) refers power (water, road) token value node i; Spi (Swi ,Sri ) refers power (water, road) source value node i, i = 1, 2, 3.. Figure A.3: I2Sim demo illustrated by PC cluster. Figure A.4: Topological structure of the 16-PC cluster at UBC power lab. 70 Appendix A. Introduction on I2Sim Legend Data Communication Figure A.5: UBC 5 cell cluster demo integrated into one single machine by global memory synchronization. i xi t xi t i Figure A.6: A typical channel model with delay. the cluster one, but the HRT table for hospital cell has been replaced by the abstracted function from it. This single machine prototype can conveniently display the design scenarios, with an interactive GUI added, human decision process and related activities can also be integrated in to the system, driven by diﬀerent events created by human activities, the impacts and eﬀects of human layer on these infrastructures will be unfolded dynamically. A.3 Modelling Channels with Time-varying Delay Mathematical Description for the Flow-type Channel: The equation for a typical channel with delay (Fig.A.6) can be expressed as x(t) = Cx(t − τ ), usually C = 1. But for a ﬂow-type delay, since in most cases, this type channel’s capacity is deﬁned as the volume of ﬂow. Thus for the ﬂow type 71 Appendix A. Introduction on I2Sim Figure A.7: Overview of the channel model with time-varying delay. Figure A.8: Detailed internal structure of the channel model by MATLAB Simulink. channel, the capacity under threshold is proportional to its speed, hence C(τ ) = r.v = r L τ0 Lτ0 = τ = C(τ0 ) τ τ τ0 (A.1) then its transportation equation can be expressed as x(t) = C(τ )x(t − τ ) = C(τ ) τ0 x(t − τ ) τ (A.2) Where τ0 is the minimum delay for the channel, as in usual situation c(τ0 ) = 1 , therefore x(t) = τ0 x(t − τ ) τ (A.3) This channel model with time-varying delay has been implemented by Simulink in MATLAB, the top-level block can be illustrated in Fig.A.7, and detailed subsystem block can be illustrated in Fig.A.8. Where in Fig. A.7, the “Varying Input” block refers to the real time input for the chan72 Appendix A. Introduction on I2Sim nel; the “varying delay” block refers to the real time delay for the channel, but emphasis on the delay aﬀected by global event, for instance snow storm that worsen the roads situation. the “Channel Capacity” block refers to the real-time capability of the channel, for instance, in transportation channel case, it refers to the volume of traﬃc ﬂow; the “Availability coeﬃcient after Disaster” block refers to the left capability of the channel after a damage or a disaster. 73 Appendix A. Introduction on I2Sim A.4 Bibliography [1] Jose R. Marti, Jorge A. Hollman, C. Ventura, and J. Jatskevich, “Dynamic recovery of critical infrastructures: real-time temporal coordination”, International Journal of Critical Infrastructures, vol.4(1), pp.17-31,2008. [2] Siva Prasad Rao Singupuram, “Pc-cluster simulator for joint infrastructure interdependencies studies”, Master thesis, University of British Columbia, 2007. [3] The Mathworks Inc, MATLAB 7.3.0 HELP:Simulink:work with data stores, 2006. [4] Haﬁz Abdur Rahman, Mazana Armstrong, DeTao Mao and Jos R. Marti, “I2Sim: A Matrix-partition based Framework for Critical Infrastructure Interdependencies Simulation”, Electric Power Conference, 2008. EPEC 2008. IEEE Canada, Vancouver, B.C., Canada, Oct, 2008. ( http://ieeexplore.ieee.org) 74 Appendix B Introduction on HRT Method and GAM Representation B.1 B.1.1 Continuous Function Representation for Complicated Cells Based on Human Readable Tables (HRT) Method Introduction For information privacy and security, for instance, to hide a cell’s internal sensitive information that are not publicly accessible, or to protect its critical elements, Dr. Marti proposed the idea of human read tables (HRT) to model a cells’ operability. But for a complicated cell with multi-inputs from diﬀerent infrastructure networks , in most situations, the interactions among these inputs cannot be modelled in an explicit way, also it is diﬃcult to get enough data to construct a complete HRT. To get the cell’s output for any continuously varying input, traditional linear interpolation methods are not applicable, as the data sample in the multi-dimension space is too sparse. To solve these problems, based on theoretical assumptions, I derived a multi-variable nonlinear function to represent the cell’s functionality. This function is constructed from the HRT with limited information and it can approximate the cell’s I/O behavior within an acceptable ﬁtting gap. B.1.2 Basic Assumptions and the Derived Formulae In [1], Adam Smith observed that, without labor division, each pin-maker could make at most 20 pins a day, but with a proper division and combination of their diﬀerent operations, ten pin-makers could make four thousand eight hundred pins in a day. For these cells with complicated internal struc- 75 Appendix B. Introduction on HRT Method and GAM Representation z x y y x Figure B.1: The ideal multi-dimension ﬁtting function in a 2-D subspace viewed from diﬀerent angles. ture and I/O relationship, such as hospital, the hospital cell can be seen as a pipeline from patients to healthy people, with many subsystems as division of labors, similar to the pin-making process, the hospital cell’s operability will be improved exponentially as availability of utilities increases (Matthew eﬀect). But because of these physical constraints, such as system scale and other hardware bottle necks (saturation eﬀect), the ﬁnal operability cannot be inﬁnite, it can be seen as a set of equilibria, which demonstrates the compromised competition between two eﬀects: Matthew eﬀect and saturation eﬀect. Based on the above analysis, a nonlinear continuous function has been derived to represent the cell’s I/O behavior, this function projected on one single dimension in the multi-dimension space can be expressed as α0 α0 + (1 − α0 ) · e−K1 ·(x−x0 ) (0% < x, α0 , x0 , x − x0 < 100%). f (x, α0 , K1 , x0 ) = (B.1) When projected in a 2D subspace, this multi-Dimension ﬁtting function can be seen in Fig. B.1. Where {x, y} are inputs, z is the operability of a cell. For more information, the derivation details can be found in [5]. B.1.3 From HRT Data in I2DB to Represent Functions in I2Sim. As shown in Fig.B.2, this multi-dimension function can be abstracted oﬀline from HRT data, both the HRT data and the abstracted parameters are stored in I2DB, these parameters will be quarried online by the I2Sim simulator, as the function’s form is ﬁxed, thus it can easily be recovered by 76 Appendix B. Introduction on HRT Method and GAM Representation HRT Data in Per Unit System Abstract Subroutines For each single-D by LSE. Synthesis these single-D Subroutines Multi-Dimension Nonlinear Continuous Function in Normal Form F(x i, Į i ) Function F(x i, Į i ) represented by key parameters {Įi} Calculation on the upper and low boundaries. Searching the linear interpolation parameter(s) between the boundaries by LSE. i Figure B.2: Flowchart on data processing from I2DB to I2Sim. the parameters. The simulator and the HRT data that has physical world information are totally isolate, which guarantees a high level of information security, and also improves the computing eﬃciency greatly. B.1.4 Multi-dimension Function to Approximately Represent the Operability of Cells Based on HRT the Multi-dimension eﬃciency function of hospital in a view of optimism Usually a convex metric need to be constructed to synthesis these inputting utilities, but in this case, it is obvious that the hospital’s eﬃciency is at least limited by the minimum value of these seven single-dimension functions: Eopt = min{E(x0doc ), E(x0gas ), E(x0med ), E(x0ele ), E(x0wat ), E(x0stm ), E(x0nurs )} That’s to say, in an optimism view, we can see Eopt = Emin as a metric of the multi-dimension function of Ui , (0 ≤ i ≤ 7). 77 Appendix B. Introduction on HRT Method and GAM Representation Figure B.3: For the multi-dimension function abstracted from the HRT data of UBC hospital, (a) is the ﬁtted function projected on the nurse dimension; (b) is its projection on the doctor dimension. B.1.5 Fitting Results for HRT Data from the UBC Hospital Based on the HRT constructed by L.Liu in [1], a multi-dimension function is abstracted, its ﬁtting results can be seen in Fig.B.3. B.1.6 Other Aspects about Cell Modelling Based on HRT • Based on HRT, the more data we get, the more accurate the model and the representing function will be, since these principal parameters can be adjusted in least square error (LSE) sense. But comparing with neural network method, our modelling method doesn’t need a large volume of data and thus there is no training process required.( but it requires a minimum support set of data.) • Assessments over the priority of these inputting utilities are evaluated in the HRT modelling process, it can supply us local vulnerability information for late global analysis. • By variable reduction and dimension fusion, the dimensions or variables with the similar characteristics will be fused together, therefore this method can reconstruct the multi-dimension function with incomplete information. 78 Appendix B. Introduction on HRT Method and GAM Representation B.2 B.2.1 Infrastructure Interdependencies and Their Representation by the Generalized Adjacency Matrix (GAM) Introduction and Overview To represent inter/intra interaction relationship through physical interface among these cells in the multi-layer infrastructure networks, so as to do some interdependency related analysis, such as vulnerability assessment and risk assessment etc., in this section, the conception of Semi-certain Adjacency Matrix (SAM), which is usually to represent undirected graph by Boolean variables {0, 1} in graph theory, is generalized to represent multi-arc directed graphs (MDG) with loops(feedback graph) by a complex matrix. A physical interdependency or interaction between two cells can be seen as a link in graph theory, with this generalized SAM matrix, interaction can be represented by numbers in the complex ﬁeld, where logic rules and algebraic operations are also redeﬁned. In this thesis, all related interdependency analysis is based on this matrix representation. By introducing the concept of Strongly Coupled Components (SCC), further topological knowledge about MDG graph, can be calculated explicitly and eﬃciently. Based on the calculated results of the SCC, critical components, vulnerability assessment, sensitivity analysis can also be obtained. By SCCs identiﬁcation, splitting strategies among these critical infrastructure networks can therefor be more convincible. Other possible applications based on GAM are also remarked. B.2.2 Introduction on Interdependency Types Dependency refers to a linkage or connection between two infrastructures, through which the state of one infrastructure inuences or is correlated to the state of the other. Interdependency refers to a bidirectional relationship between two infrastructures through which the state of each infrastructure inﬂuences or is correlated to the state of the other. More generally, two infrastructures are interdependent when each is dependent on the other[3]. Interdependencies vary widely, and each has its own characteristics and eﬀects on infrastructure agents. In the sections that follow, four principal classes of interdependencies: physical, cybertical, geographic and policy, will be deﬁned. Although each has distinct characteristics, these classes of interdependencies are not mutually exclusive. • Physical Interdependency: Two infrastructures are physically interdependent if the state of each is dependent on the material output(s) of 79 Appendix B. Introduction on HRT Method and GAM Representation Oil/Natural Gas Fuel supply Compressor Station Electric Power T-lines Switching Office Tele-Com Power Plant Substation Transportation Traffic Light End Office Transport WaterStation Water Emergency Service Hospital Call Centre Reservior Banking & Finance Check Processing Centre Bank ATM Ambulence Fire Hall Military Installation Federal Reserve Legislative Offices Pension Servie/ Payment Gov’t Service Treasury Depart Figure B.4: Infrastructure interdependencies among those critical infrastructure networks. the other. • Geographic Interdependency: Infrastructures are geographically interdependent if a local environmental event can create state changes in all of them. • Cyber Interdependency: An infrastructure has a cyber interdependency if its state depends on information transmitted through the information infrastructure. • Logical Interdependency: Two infrastructures are logically interdependent if the state of each depends on the state of the other via a mechanism that is not a physical, cyber, or geographic connection. • Policy/Procedural Interdependency: An interdependency that exists due to policy or procedure that relates a state or event change in one infrastructure sector component to a subsequent eﬀect on another component. 80 Appendix B. Introduction on HRT Method and GAM Representation ܥ Ȁ ܧ ܥ Ȁ ܧ ܥ Ȁܧ Ȁܧ ܥ ܥ Ȁ ܧ ܥ Ȁ ܧ ܥ Ȁ ܧ ܥ Ȁ ܧ Figure B.5: EMIP: Study space of infrastructure Interdependency Analysis. Which includes four layers: Energy transmission, Matter transportation, Information communication, Policy management. Figure B.6: UBC campus ﬁve cell model. 81 Appendix B. Introduction on HRT Method and GAM Representation i i Figure B.7: Instances of self-loop or rings. B.2.3 Multi-Arc Directed Graph Represented by GAM with Redeﬁned Operation Rules In Fig.B.6, ﬁve cells on UBC campus can be seen as an instance of Infrastructure Interdependency, which is also represented by the following matrix AGAM . GAM Representation In a generalized SAM , the connectivity information between vertexes is represented by a complex number, with exiting degree as its real part and entering degree as imaginary part, thus a GAM matrix AGAM is capable to imply that physical interdependency information among infrastructure components. ⎡ ⎤ 0 1 0 0 1 ⎢ i 0 2 2 0 ⎥ ⎢ ⎥ ⎥ AGAM = ⎢ ⎢ 0 2i 0 i 2 ⎥ ⎣ 0 2i 1 0 1 ⎦ i 0 2i i 0 Though it can be presented mathematically by the corresponding diagonal element, self-loop(s) (as in Fig. B.7) of each elements is not practically signiﬁcant, it is not permitted here, for instance, for order n = 1, by deﬁnition, diagonal elements of matrix A should be zero, aii = 0(i = 1, · · · , n). 82 Appendix B. Introduction on HRT Method and GAM Representation Algebraic operation and logic rules for GAMs Since the logic rules for the operation on SAM cannot be adopted here directly, I have deﬁned the multiply operator ⊗ of generalized SAM, B = A2 = A ⊗ A n aik ∩ akj bij = k=1 here bij is the element of B, and is algebraic “sum” in regular sense. ∩ is logic “and” (&) but has a generalized deﬁnition as fellows: x ∩ y = re(x) · re(y) + i · img(x) · img(y) (B.2) here re(x) denotes the real part of variable x, and img(x) the imaginary part of x. variables like x and y are complex numbers whose real part and imaginary part are all non-negative integers. Flow chart of the algorithm for searching and compressing SCCs A directed graph is called strongly connected if for every pair of vertices {u, v}, there is a path from u to v and a path from v to u. The strongly connected components (SCCs) of a directed graph are its maximal strongly connected subgraphs, that form a partition of the graph B.8. The reason we introduce the conception of SCC here is to reduce the computing complexity of directed graph with pathway cycles in it. When all these cycles are reduced to SCCs, the structure of these diﬀerent orders of matrix will become simple, and the interdependency relationship between diﬀerent components or vertices can be more clear and obvious. Otherwise, for the graph with pathway cycles in it, the number representing the length of the pathway can become very large, since the loop in the pathway can repeat itself for arbitrary times. By ﬁnding all these pathways between any pair of components or vertices, GAM can identify or detect the whole possible correlated or aﬀected domain for any components in the system, since all these types of interdependencies can be modelled into GAM. And it is also an exhaustive analysis method instead of a “what if” analysis depended on a certain set of preconditions, theoretically it can supply us more reliable, global and complete results. By analysis with GAM, for a disaster triggered by a certain type of event, for these infrastructure components that have a higher priority of protection, the index of cascading impact can tell us all the relationship to other in83 Appendix B. Introduction on HRT Method and GAM Representation Figure B.8: Graph with strongly connected components (SCCs) marked. frastructure components, which may give us essential information on where to buﬀer the cascading failures with the minimum cost. Also for a detailed local interdependencies model, GAM can tell us all these unexpected weaknesses. For instance, during the ice storm in 1998 at NW Canada, a GAM model on this multi-layer infrastructure networks may inform the decision makers the locations of these most vulnerable vertices or which linkage has the highest probability of collapse[2]. The ﬂow chart for the algorithms on searching and compressing SCCs is described in Fig. B.9. An instance for previous algorithms will be displayed in Fig.B.10and B.11. 84 Appendix B. Introduction on HRT Method and GAM Representation Figure B.9: Flowchart on the searching and compressing algorithm for SCCs. Figure B.10: Strongly connected components (SCCs) identiﬁed by GAM computing algorithm. 85 Appendix B. Introduction on HRT Method and GAM Representation Figure B.11: SCCs and pathways found between vertex 1 and vertex 12 in Fig. B.10. 86 Appendix B. Introduction on HRT Method and GAM Representation B.3 Bibliography [1] Adam Smith, Wealth of Nations, chapter I: Of the Division of Labour. Chapman and Hall, 1969. [2] Stephanie E. Chang, Timothy L. McDaniels, Joey Mikawoz and Krista Peterson, “Infrastructure failure interdependencies in extreme events: power outage consequences in the 1998 ice storm”, Nat. Hazards, vol.41, pp.337358, 2007. [3] Steven M. Rinaldi, James P. Peerenboom, and K. Kelly Terrence, “Identifying, understanding, and analyzing critical infrastructure interdependencies”, IEEE Control Systems Magazine, vol.21, pp.11-25, Dec, 2001. [4] De Tao Mao, “Modelling hospital: Construction and ﬁtting the multidimension I/O function with incomplete information”, Technical report, University of British Columbia, 14 September 2007. [5] Lu Liu, “Prototyping and cells modelling of the infrastructure interdependencies simulator i2sim”, Master’s thesis, University of British Columbia, 2007. 87 Appendix C Matlab Code for the Library on the Operators of GAM C.1 A Library of Functions for GAM Operation Based on the new-deﬁnited GAM matrix operation, a library of functions coded in MATLAB has been developed. Table C.1: Library of Functions for GAM Operation Function Name gc and.m gc multiply.m gc RC.m Check SCC.m setdiagonal.m SCC Compress.m Set Minus.m checkGAM.m ﬁndout SubSet.m Get subset SCC.m Display SCC.m check GAMcomp.m Pathway Finder.m Display Paths.m mainSCC.m GAM2Lap.m Number of Paths.m InfDomain of Cell.m InfDomain of Link.m Description Generalized “and ” for two scalar variables. Generalized “multiply” for two matrixes. Generalized “multiply” for a two vectors. Check the existence and identify the SCCs. Set the diagonal elements to zeroes. Compress SCC after calculating them out. Subtraction between two SCCs and theri subsets. Check whether a matrix is a GAM. Find a subsets of SCCs. Find out all the subsets of SCCs. Display the subsets of SCCs. Verify the compressed GAM. Find out all the pathways between two elements. Display all the pathways between two elements. Main program for ﬁnding, compressing and displaying both SCC and pathways. To convert GAM into Laplacian matrix. To ﬁnd out how many paths in one connectivity. To ﬁnd out whole inﬂuence domain of a cell. To ﬁnd out whole inﬂuence domain of a channel. 88 Appendix C. Matlab Code for the Library on the Operators of GAM C.1.1 Generalized “And” Description: Generalized “and” for two scalar variables. Code: function y = gc and(x1,x2); if nargin ∼ = 2; error(’Wrong number of input arguments!’); end; if((round(real(x1)) =real(x1))—(round(real(x2))∼=real(x2))); error(’Error with X1 or X2,one or both of the real parts are not integer,out of deﬁnited value range!’); end; if((round(imag(x1))∼=imag(x1))—(round(imag(x2))∼=imag(x2))); error(’Error with X1 or X2, one or both of the imag parts are not integer, out of deﬁnited value range!’); end; if (real(x1)<0) | (real(x2)<0) | (imag(x1)<0) | (imag(x2) < 0); error(’Error with X1 or X2,one or both of the real parts are not integer,out of deﬁnited value range!’); end; y=real(x1)*real(x2)+i*imag(x1)*imag(x2); C.1.2 Generalized “Multiply” for Matrixes Description: generalized multiply for two matrixes. Code: function y=gc multiply(A,B); [na,ma]=size(A); [nb,mb]=size(B); 89 Appendix C. Matlab Code for the Library on the Operators of GAM if (na∼=ma)|(nb∼=mb)|(na∼=nb) error(’The matrixs are not square!’); end; for i=1:1:na; for j=1:1:nb; y(i,j)=gc RC(A(i,:),B(:,j)); end; end; C.1.3 Generalized “Multiply” for Vectors Description: generalized multiply for two vectors. Code: function y=gc RC(z1,z2); if nargin ∼= 2; error(’Wrong number of input arguments’); end; if (length(z1)∼=length(z2))|(length(z1)==0); error(’Error, they are not equal length column and row!,or null variable!’); end; y=0; for i=1:1:length(z1); y=y+gc and(z1(i),z2(i)); end; C.1.4 SCC Checking and Detecting Description: Check the existence and identify the SCCs. Code: function [exist SCC,SCC]=Check SCC(A); 90 Appendix C. Matlab Code for the Library on the Operators of GAM [na,ma]=size(A); if (na∼=ma)|na==1 error(’The matrixs are not square!’); end; SCC=[ ]; Diag A=diag(A); SCC=ﬁnd(Diag A); [na,nb]=size(SCC); if na>nb SCC=SCC’; end; [na,nb]=size(SCC); if (na==1)&(nb>1); exist SCC=1; else exist SCC=0; end; C.1.5 Diagonal Elements Resetting Description: set the diagonal elements to zeroes. Code: function y=setdiagonal(X); if nargin ∼=1; error(’Wrong number of input arguments’); end; [m,n]=size(X); if (m∼=m); error(’Error with X, it is not a square matrix!’); end; 91 Appendix C. Matlab Code for the Library on the Operators of GAM for i=1:m; X(i,i)=0; end; y=X; C.1.6 Compressing SCCs Description: compress SCC after ﬁnding them out. Code: function y=SCC Compress(A,SCC) SCC=SCC(1:end-2); index=ﬁnd(SCC∼=0); SCC=SCC(index); n=length(SCC); for i=2:n; A(:,SCC(1))=A(:,SCC(1))+A(:,SCC(i)); A(SCC(1),:)=A(SCC(1),:)+A(SCC(i),:); A(:,SCC(i))=0; A(SCC(i),:)=0; end; A(SCC(1),SCC(1))=0; y=A; C.1.7 Substraction between SCCs Description: substraction between two SCCs and their subsets. Code: function y=Set Minus(A,B); 92 Appendix C. Matlab Code for the Library on the Operators of GAM [x1,y1]=wcommon(B,A); if sum(x1)∼=length(x1) error(’B is not a subset of A.’); end; position B=ﬁnd(y1==1); A(position B)=0; [v,w]=ﬁnd(A∼=0); y=A(w); C.1.8 GAM Matrix Checking Description: Check whether a matrix is a GAM. Code: function [y, size A ]=checkGAM(A); [row, column]=size(A); if row∼=column y=0; else size A=row; y=A-i.*A’; [n1,n2]=ﬁnd(y∼=0); if length(n1)*length(n2)==0 y sym=1; else y sym=0; end; realA=real(A); imagA=imag(A); [n1,n2]=ﬁnd(realA<0); [n3,n4]=ﬁnd(imagA<0); 93 Appendix C. Matlab Code for the Library on the Operators of GAM if length(n1) ∗ length(n2) > 0 | length(n3) ∗ length(n4) > 0 y degree=0; else y degree=1; end; if y sym*y degree==0; y=0; else y=1; end; end; C.1.9 Subset Detection of a SCCs Description: detect a subset of a SCC. Code: function y=ﬁndout SubSet(SCC,path length,G); [na,nb]=size(SCC); if (na =1)&(nb =1) error(’this is not a SCC.’); end; if na>nb SCC=SCC’; end; index nonzero=ﬁnd(SCC =0); SCC=SCC(index nonzero); y=SCC(1); length SCC=length(SCC); for j=1:length SCC; for i=1:length SCC; [n1,m1]=size(ﬁnd(y==SCC(i))); [n2,m2]=size(ﬁnd(y==SCC(j))); if (i =j)&(Circle Check(SCC(j),SCC(i),path length,G))& · · · 94 Appendix C. Matlab Code for the Library on the Operators of GAM (Circle Check(SCC(i),SCC(j),path length,G)) &(m1==0)&(m2>0) y=[y,SCC(i)]; end; end; end; [nr,nc]=size(y); if nr>nc y=y’; end; C.1.10 Find Subsets of SCCs Description: ﬁnd out all subsets of a SCC. Code: function [number SCC,SCCM]=get subset SCC(SCC,path length,G); [na,nb]=size(SCC); if na>nb SCC=SCC’; end; lengthSCC=length(SCC); if length(SCC)==path length; SCCM=[SCC,0,path length]; else i=0; while length(SCC)>2; i=i+1; subSCC=ﬁndout SubSet(SCC,path length,G); z=[ ]; l=lengthSCC-length(subSCC); z(1:l-1)=0; SCCM(i,:)=[subSCC,z,0,path length]; SCC=Set Minus(SCC,subSCC); 95 Appendix C. Matlab Code for the Library on the Operators of GAM number SCC=i; end; end; C.1.11 Display SCCs Description: display all subsets of a SCC. Code: function Display SCC(SCC cell); Length SCC cell=length(SCC cell); for k=1:Length SCC cell; SCC Matrix=SCC cellk; last bit=SCC Matrix(1,end); SCC Matrix=SCC Matrix(:,1:1:end-2); [rn,cn]=size(SCC Matrix); if rn>1; str=[’There are ’,num2str(rn), ’ subsets in SCC cell’,num2str(k),’.’]; disp(str); for m=1:1:rn; sub SCC m=SCC Matrix(m,:); index nonzero=ﬁnd(sub SCC m =0); subSCCm=sub SCC m(index nonzero); str=[’The No.’,num2str(m) ,’ Subset of SCC cell’,num2str(k),’ is: [’,num2str(subSCCm),’].’]; disp(str); str=[’This subset of SCC will be compressed as element ’,num2str(subSCCm(1)),’.’]; disp(str); end; else sub SCC m=SCC Matrix; index nonzero=ﬁnd(sub SCC m =0); subSCCm=sub SCC m(index nonzero); str=[’Except subset: [’,num2str(subSCCm),’],There is no other subsets in SCC cell’,num2str(k),’.’]; disp(str); str=[’This SCC will be compressed as element ’,num2str(subSCCm(1)),’.’]; 96 Appendix C. Matlab Code for the Library on the Operators of GAM disp(str); end; end; sprintf(’\n’); C.1.12 Compressed GAM Veriﬁcation Description: verify the compressed GAM. Code: function [no ring,G,G pages]=check GAMcomp(GAM comp); run=1; path length=0; G(:,:,1)=GAM comp; A=GAM comp; while(run==1); B=gc multiply(A,GAM comp); path length=path length+1; G(:,:,path length+1)=B; [exist SCC,SCC]=Check SCC(B); if exist SCC>0; run=0; no ring=0; else run=1; no ring=1; end; RB=real(B); IB=imag(B); [rrb,rcb]=size(ﬁnd(RB>0)); [irb,icb]=size(ﬁnd(IB>0)); if (rcb*rrb)==0 & (icb*irb)==0; run=0; end; 97 Appendix C. Matlab Code for the Library on the Operators of GAM A=B; end; G pages=path length; C.1.13 Find Out All Pathways Description: ﬁnd out all the pathways between two elements. Code: function [exist path, paths]=Pathway Finder(element i,element j,path length,GAM record); [cn,rn,pn]=size(GAM record); exist path=real(GAM record(element i,element j,path length)); if exist path==0| path length<0 | path length>pn ; exist path=0; paths=[ ]; disp([’There are no pathways between element ’,num2str(element i),... ’ and element ’,num2str(element j),’ with length ’,num2str(path length),’.’]); else exist path=1; disp([’There exists pathway(s) between element ’,num2str(element i),... ’ and element ’,num2str(element j),’ with length ’,num2str(path length),’ as below:’]); end; if path length==1 exist path=real(GAM record(element i,element j,path length)); path=[element i,element j]; end; while (path length>1); Ics=ﬁnd(real(GAM record(element i,:,path length-1))>0); element j temp=[]; [rn1, cn1]=size(element j); if rn1*cn1>0; [rn,cn]=size(element j(:,1)); 98 Appendix C. Matlab Code for the Library on the Operators of GAM end; if (rn1*cn1>0)&(rn*cn>0); for k=1:1:rn; Jcs k=ﬁnd(real(GAM record(:,element j(k,1),1))>0); Jcs k=Jcs k’; if length(Jcs k)>0; common element position=wcommon(Ics,Jcs k); common elements=Ics(common element position); z=[ ]; for l=1:length(common elements); z=[z; common elements(l),element j(k,1:end)]; end; element j temp=[element j temp; z]; end; end; element j=element j temp; end; path length=path length-1; end; [rn,cn]=size(element j); element ii=ones(1,rn)*element i; paths=[element ii; element j’]’; C.1.14 Display All Pathways Description: display all the pathways between two elements. Code: function Display Paths(paths,GAM); [rn,cn]=size(paths); str=[ ]; for i=1:rn; for j=1:cn if j==1; 99 Appendix C. Matlab Code for the Library on the Operators of GAM head=([’Path ’,num2str(i),’: ’,num2str(paths(i,j))]); str=[str,head]; else if j==cn; str=[str,’–>’,num2str(paths(i,j)),’, ’]; else str=[str,[’–>’,num2str(paths(i,j))]]; end; end; end; numb path=Number of Paths(paths(i,:),GAM); str=[str,’totally ’, num2str(numb path), ’ paths.’]; disp(str); sprintf(’\ n’); str=[ ]; sprintf(’\n’); sprintf(’\n’); end; sprintf(’\n’); C.1.15 Main Function Description: Main program to ﬁnd, compress and display SCCs and pathways. Code: tic; clear; clc; format rat; global GAM; GAM= [0,1,0, 0,0,0, 1,0,0, 0,0; j,0,1, 0,j,0, 0,0,0, 0,0; 0,j,0, 1+j,0,0, 0,0,0, 0,0; 0,0,1+j, 0,1,1, 0,0,0, 0,0; 0,1,0, j,0,0, 0,0,0, 0,0; 0,0,0, j,0,0, 0,j,0, 1,0; j,0,0, 0,0,0, 0,1+j,1, 0,0; 0,0,0, 0,0,1, 1+j,0,1+j, 0,0; 0,0,0, 0,0,0, j,1+j,0 0,0; 0,0,0, 0,0,j, 0,0,0, 0,1; 100 Appendix C. Matlab Code for the Library on the Operators of GAM 0,0,0, 0,0,0, 0,0,0, j,0;]; [GAM criteria,sizeA]=checkGAM(GAM); if GAM criteria==0; error(’The matrix is Not a GAM!’); end; run=1; element number=sizeA; path length=1; A=GAM; a=GAM; GAM comp=A; G(:,:,1)=a; SCC counter=0; while (run==1)&(path length¡element number); B=gc multiply(A,a); path length=path length+1; G(:,:,path length)=B; RB=real(B); IB=imag(B); [rrb,rcb]=size(ﬁnd(RB>0)); [irb,icb]=size(ﬁnd(IB>0)); if (rcb*rrb)==0 & (icb*irb)==0; run=0; end; [exist SCC,SCC]=Check SCC(B); if exist SCC>0; SCC counter=SCC counter+1; [number SCC SubSet, SCCM]=get subset SCC(SCC, path length,G); SCC cellSCC counter=SCCM; SCCM subset no=0; while number SCC SubSet>=1; SCCM subset no=SCCM subset no+1; GAM comp=SCC Compress(GAM comp,SCCM(SCCM subset no,:)); number SCC SubSet=number SCC SubSet-1; 101 Appendix C. Matlab Code for the Library on the Operators of GAM end; a=GAM comp; A=GAM comp; path length=1; G=[ ]; G(:,:,1)=GAM comp; else A=B; end; end; Display SCC(SCC cell); [no ring,GAM record,path length]=check GAMcomp(GAM comp); for p=1:path length; [exist path, paths]=Pathway Finder(1,11,p,GAM record); if exist path; Display Paths(paths); end; end; toc; C.1.16 GAM Converter Description: covert GAM matrix to Laplacian matrix. Code: function y=GAM2Lap(x); [isGAM,size A]=checkGAM(x); if isGAM error(’The matrixs is not a GAM!’); end; y=x; 102 Appendix C. Matlab Code for the Library on the Operators of GAM for i=1:1:size A; for j=1:1:size A; c=ﬁnd(x(i,:) =0); y(i,c)=-1; y(i,i)=length(c); end; end; C.1.17 Pathway Number Description: ﬁnd out how many paths in one connectivity. Code: function y=Number of Paths(path,GAM); if length(path)<2; y=0; else if length(path)==2; y=GAM(path(1),path(2)); y=abs(y); else if length(path)>2; la=path(1:1:end-1); lb=path(2:1:end); y=1; for i=1:1:length(la); y=y*GAM(la(i),lb(i)); end; y=abs(y); end; end; end; C.1.18 Cell’s Domain Description: ﬁnd out the inﬂuence domain of a cell. Code: function cell set=InfDomain of Cell(cell i,GAM record); 103 Appendix C. Matlab Code for the Library on the Operators of GAM [rn,cn,page]=size(GAM record); cell set=[ ]; for i=1:1:page; A=GAM record(cell i,:,i); c=ﬁnd(A =0); cell set=union(cell set,c); end; C.1.19 Channel’s Domain Description: ﬁnd out the inﬂuence domain of a channel. Code: function cell set=InfDomain of Link(cell i, cell j, GAM record); link=GAM record(cell i,cell j,i); if real(link)>0 cell i=cell j; end [rn,cn,page]=size(GAM record); cell set=[ ]; for i=1:1:page; A=GAM record(cell i,:,i); c=ﬁnd(A =0); cell set=union(cell set,c); end; 104 Appendix D Publications [1]Detao Mao, Peng Zhang, Haﬁz Abdur Rahman, and Jose R. Marti, “Nonlinear Oscillations Caused by Periodic Disturbance between Inter-area Power Systems”, Electric Power Conference, 2008. EPEC 2008. IEEE Canada, Vancouver, B.C., Canada, Oct, 2008. (http://ieeexplore.ieee.org) [2]Haﬁz Abdur Rahman, Mazana Armstrong, DeTao Mao, and Jose R. Marti, “I2Sim: A Matrix-partition based Framework for Critical Infrastructure Interdependencies Simulation”, Electric Power Conference, 2008. EPEC 2008. IEEE Canada, Vancouver, B.C., Canada, Oct, 2008. ( http://ieeexplore.ieee.org) [3]DeTao Mao, Mandana Sotoodeh, Kafui Monu, Jose R. Marti, and K. D. Srivastava, “Interdependencies Control—Compensation Strategies on the Inherent Vulnerability of Critical Infrastructures ”, the IEEE 2nd Climate Change Technology Conference (CCTC 2009), CANADA. (accepted) [4]DeTao Mao, Jose R. Marti, and K. D. Srivastava, “Mitigating Snowcaused Blackouts on the Cascading Pathways”, 2009 IEEE International Conference on Technologies for Homeland Security (HST ’09) (accepted) [5]DeTao Mao, Jose R. Marti, and K. D. Srivastava, “Survival from Disaster by Interdependencies Management”, International Journal of Emergency Management (to be submitted) 105