@prefix vivo: . @prefix edm: . @prefix ns0: . @prefix dcterms: . @prefix dc: . @prefix skos: . vivo:departmentOrSchool "Applied Science, Faculty of"@en, "Electrical and Computer Engineering, Department of"@en ; edm:dataProvider "DSpace"@en ; ns0:degreeCampus "UBCV"@en ; dcterms:creator "Mao, DeTao"@en ; dcterms:issued "2009-08-17T15:50:45Z"@en, "2009"@en ; vivo:relatedDegree "Master of Applied Science - MASc"@en ; ns0:degreeGrantor "University of British Columbia"@en ; dcterms:description """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 service(s) 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 effective. 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 effectiveness during the response stage and the recovery stage of the emergency management cycle are demonstrated. (II) Identification 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 effects 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. (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 modeling 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)."""@en ; edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/12268?expand=metadata"@en ; dcterms:extent "1894904 bytes"@en ; dc:format "application/pdf"@en ; skos:note """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 interde- pendent. The complexity of these interdependencies has created a new di- mension of vulnerability, making the whole system very fragile under unex- pected events. To make the whole system more resilient during disasters, the Joint Infrastructure Interdependencies Research Program (JIIRP), aimed at de- veloping 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 vul- nerabilities would be intractable, an interdependencies control strat- egy, 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 infras- tructure networks. By computation of GAM, decision making for ICS can be made more effective. Moreover, measures for improving surviv- ability of the system are proposed. ICS application to a case study at the UBC campus is detailed in Chapter 3, its effectiveness during the response stage and the recovery stage of the emergency management cycle are demonstrated. • (II) Identification 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 infeasi- ble. 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 effects of a changed climate, the causalities and their consequences are illus- trated 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 emer- gencies (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.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3.1 Work on Infrastructure Interdependency Modelling . . 3 1.3.2 Work Based on Graph theory . . . . . . . . . . . . . 4 1.3.3 Work on Vulnerability Analysis and Risk Assessment . 4 1.4 Research Objectives . . . . . . . . . . . . . . . . . . . . . . . 5 1.5 Outline of the Thesis . . . . . . . . . . . . . . . . . . . . . . . 6 1.6 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Interdependencies Control Strategy . . . . . . . . . . . . . . 12 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 Representation of Multi-arc Directed Physical Independencies by the Generalized Adjacency Matrix (GAM) . . . . . . . . . 15 2.2.1 Algebraic Operation and Logic Rules for GAM . . . . 15 2.2.2 Further Information Abstraction Based on GAMCom- putation . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2.3 Advantages of Interdependency Analysis Based on GAM 18 iv Table of Contents 2.3 Interdependencies Control Based on GAM . . . . . . . . . . . 18 2.3.1 Brief Introduction to Emergency Management . . . . 19 2.3.2 Survivability Index of an Island (SII) . . . . . . . . . . 20 2.3.3 Description of Interdependencies Control Strategy . . 20 2.3.4 Measures for Improving SII in Emergency Management 22 2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.5 Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.6 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3 Survival from Disaster by Interdependencies Management 27 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2 Representation of Modellable Physical Independencies by the Generalized Adjacency Matrix (GAM) . . . . . . . . . . . . . 28 3.2.1 Operation Rules for GAM . . . . . . . . . . . . . . . . 28 3.2.2 System Information Abstracted by GAM Computation 30 3.2.3 Advantages of GAM-based Interdependency Analysis . 35 3.3 Interdependencies Control Strategy (ICS) Based on GAM . . 36 3.3.1 Basic Introduction to Emergency Management . . . . 36 3.3.2 Survivability Index of an Island (SII) . . . . . . . . . . 37 3.3.3 Interdependencies Control Strategy . . . . . . . . . . . 38 3.3.4 Measures for Improving SII . . . . . . . . . . . . . . . 39 3.4 Application of ICS on the UBC Campus Case . . . . . . . . . 40 3.4.1 Scenario Description . . . . . . . . . . . . . . . . . . . 41 3.4.2 ICS-based Decision Making Activity during Emergency and Recovery State . . . . . . . . . . . . . . . . . . . . 43 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.6 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4 Identifying Cascading Pathways for Power Outage Mitiga- tion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.2 Investigation on Vancouver’s 2006 Snow-Caused Power Outage 51 4.2.1 Several Root Causes Introduced by Changed Climate 52 4.2.2 Unchanged Policies of Vegetation Management by BC Hydro . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.2.3 Related Weather Factors Affecting Ice Accretion on Overhead Wires . . . . . . . . . . . . . . . . . . . . . 54 4.2.4 Impacted Critical Infrastructure Networks . . . . . . . 55 4.2.5 Dependency Network Representation for the Power Outage in Vancouver 2006 . . . . . . . . . . . . . . . . 55 v Table of Contents C Matlab Code for the Library on the Operators of GAM . 88 C.1 A Library of Functions for GAM Operation . . . . . . . . . . 88 C.1.1 Generalized “And” . . . . . . . . . . . . . . . . . . . . 89 C.1.2 Generalized “Multiply” for Matrixes . . . . . . . . . . 89 C.1.3 Generalized “Multiply” for Vectors . . . . . . . . . . . 90 C.1.4 SCC Checking and Detecting . . . . . . . . . . . . . . 90 C.1.5 Diagonal Elements Resetting . . . . . . . . . . . . . . 91 C.1.6 Compressing SCCs . . . . . . . . . . . . . . . . . . . . 92 C.1.7 Substraction between SCCs . . . . . . . . . . . . . . . 92 C.1.8 GAM Matrix Checking . . . . . . . . . . . . . . . . . 93 C.1.9 Subset Detection of a SCCs . . . . . . . . . . . . . . . 94 C.1.10 Find Subsets of SCCs . . . . . . . . . . . . . . . . . . 95 C.1.11 Display SCCs . . . . . . . . . . . . . . . . . . . . . . . 96 C.1.12 Compressed GAM Verification . . . . . . . . . . . . . 97 C.1.13 Find Out All Pathways . . . . . . . . . . . . . . . . . 98 C.1.14 Display All Pathways . . . . . . . . . . . . . . . . . . 99 C.1.15 Main Function . . . . . . . . . . . . . . . . . . . . . . 100 C.1.16 GAM Converter . . . . . . . . . . . . . . . . . . . . . 102 C.1.17 Pathway Number . . . . . . . . . . . . . . . . . . . . . 103 C.1.18 Cell’s Domain . . . . . . . . . . . . . . . . . . . . . . . 103 C.1.19 Channel’s Domain . . . . . . . . . . . . . . . . . . . . 104 D Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 vii List of Tables 2.1 Number of Weather Related Global Disasters at Each Decade (1950-1999) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.1 Data on Vancouver ’s Snow Dates (1997-2007) . . . . . . . . 52 C.1 Library of Functions for GAM Operation . . . . . . . . . . . 88 viii List of Figures 1.1 The number weather related natural disasters around the world at each decade [1950-1999] is roughly ruled by a Fi- bonacci sequence. . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.1 Power loss caused by all events together vs. power loss caused by weather related events (NERC data, 1984-2006). . . . . . 14 2.2 UBC campus model with strong coupled components/cells(SCCs). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3 The time line for emergency management. The five levels of human needs imply the priority of these critical infrastructure networks during emergency states. . . . . . . . . . . . . . . . 20 2.4 Decision making flow chart for interdependencies control strat- egy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.1 UBC campus model with strong coupled cells(SCCs). . . . . . 29 3.2 Graph characteristic of external resource (left) and critical service (right). . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.3 First order influence domain {7} and second order influence domain {6, 7, 8, 10} of cell 3 (cell GVRD). . . . . . . . . . . . 31 3.4 nth order influence domain of a damaged channel. . . . . . . 32 3.5 The infrastructure networks in the UBC campus before (a) and after an earthquake (b). . . . . . . . . . . . . . . . . . . . 33 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 identified: {1, 2, 5, 6}, {3, 7} and {, 4, 8, 9, 10} . . . . . . . . . . . . . . . . 35 3.7 The time line for emergency management. The five levels of human needs imply the priority of these critical infrastructure networks during emergency states. . . . . . . . . . . . . . . . 37 3.8 Decision making flow chart for Interdependencies Control Strat- egy (ICS). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 ix List of Figures 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. . . . . . . . . . . . . . . . . . . 41 3.10 Cells on UBC campus. Where the cross “X” in the figure represents the topologicallocation of an event. . . . . . . . . . 42 3.11 Decision making tree for the recovery phase without ICS op- erations. Where Era (E r b , E r c ) refers to the recovery actions of Ea (Eb, Ec). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.12 ICS operations (represented by circled cross “⊗”) of redis- tributing scarce resources during emergency stage. . . . . . . 45 3.13 Decision making tree for the recovery phase after ICS oper- ations. Where Era (E r b , E r c ) refers to the recovery actions of Ea (Eb, Ec). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.1 Synthesized effect of delayed deciduous time, extended grow- ing season and unchanged policies on vegetation management upon the collapse probability of trees and branches. . . . . . 53 4.2 The temperature curve (upper figure) and wind speed curve (lower figure) during Nov 22th to Dec 4th 2006 in Vancouver area . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.3 Dependency network for these cascading pathways unfolded during the power outage in Nov, 2006 at Vancouver area (B.C., Canada). . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.4 Decision making process for artificial precipitation stimula- tion(APS) action. . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.5 Active suppression of the development process of atmospheric icing by artificial precipitation stimulation. Where t0 denotes present time, t′0 denotes the APS action time, t1 denotes the beginning time of ice accretion, (t1, t2) denotes the ice accre- tion duration after APS, while (t1, t3) denotes the estimated ice accretion duration without APS. . . . . . . . . . . . . . . 59 4.6 Vulnerable geographical locations under snow storm along the transmission lines in Northern British Columbia. . . . . . . . 60 A.1 Instance of cells, channels, reserve, external source, aggrega- tors and distributors by UBC campus case. . . . . . . . . . . 69 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.. . . 70 x List of Figures A.3 I2Sim demo illustrated by PC cluster. . . . . . . . . . . . . . 70 A.4 Topological structure of the 16-PC cluster at UBC power lab. 70 A.5 UBC 5 cell cluster demo integrated into one single machine by global memory synchronization. . . . . . . . . . . . . . . . 71 A.6 A typical channel model with delay. . . . . . . . . . . . . . . 71 A.7 Overview of the channel model with time-varying delay. . . . 72 A.8 Detailed internal structure of the channel model by MATLAB Simulink. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 B.1 The ideal multi-dimension fitting function in a 2-D subspace viewed from different angles. . . . . . . . . . . . . . . . . . . 76 B.2 Flowchart on data processing from I2DB to I2Sim. . . . . . 77 B.3 For the multi-dimension function abstracted from the HRT data of UBC hospital, (a) is the fitted function projected on the nurse dimension; (b) is its projection on the doctor dimension. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 B.4 Infrastructure interdependencies among those critical infras- tructure networks. . . . . . . . . . . . . . . . . . . . . . . . . 80 B.5 EMIP: Study space of infrastructure Interdependency Analy- sis. Which includes four layers: Energy transmission, Matter transportation, Information communication, Policy manage- ment. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 B.6 UBC campus five cell model. . . . . . . . . . . . . . . . . . . 81 B.7 Instances of self-loop or rings. . . . . . . . . . . . . . . . . . 82 B.8 Graph with strongly connected components (SCCs) marked. . 84 B.9 Flowchart on the searching and compressing algorithm for SCCs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 B.10 Strongly connected components (SCCs) identified by GAM computing algorithm. . . . . . . . . . . . . . . . . . . . . . . 85 B.11 SCCs and pathways found between vertex 1 and vertex 12 in Fig. B.10. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 xi Acronyms AIMS Agent-Based Infrastructure Modelling & Simulation APS Artificial 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 first, 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 affected 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 first 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 affected by his passion on this field 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 benefited 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, Hafiz 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 Chap- ter 3 and the paper in Chapter 4 are identification 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 finance 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 affected by some specific 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 Content Natural disasters Earthquake, floods, landslides, tsunamis, wild-fires, volcanic activities etc. [7]. Adverse weather Extreme winds, snow, sleet, ice storm etc.[8][9]. Technical failures Design faults etc. Managerial factor Inadequate maintenance etc.[10]. Investment factor Unskilled workers, aging infrastructure, aging workforce, excessively prolonged service etc.[10]. Human factors 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 justified 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 different 1 Chapter 1. Introduction 13 16 29 44 74 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 inter- dependent 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 net- works, 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 re- action, 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 inter- dependencies is extremely important and has significant challenges. These challenges are greatly magnified by the wide breadth and high complexity of our critical national infrastructures. Moreover, a broad range of inter- related 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 interde- pendencies 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 financially 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), Depart- ment of Energy (DOE), Department of the Air Force (DAF),Defense Ad- vanced 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 differences 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 agent- based system to simulate and model interdependencies and survivabil- ity 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]: de- veloped by Idaho National Laboratory (INL), is a modelling and sim- ulation framework that combines geo-spatial information and a four dimensional (4D) environment (time-based) to support ’what if’ anal- ysis. 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 inter- dependent 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 identification 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 fluid 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 In- frastructure 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 juris- dictions 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 Vul- nerability 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 avail- ability 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 hu- man activity is not modelled, and only the electrical infrastructure is considered. • Multi-Network Interdependent Critical Infrastructure Pro- gram for Analysis of Lifelines (MUNICIPAL) [40]: Designed at Rensselaer Polytechnic Institute (RPI), is a geographic informa- tion system (GIS) user interface. It is built on a formal, mathematical representation of a set of civil infrastructure systems that explicitly in- corporates 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 net- work 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 fre- quency of failures. But compared with the objective of preventing large cas- cading 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-sufficient islands” to prevent cascading failures. In this thesis, all my research investigations (cell modelling and represen- tation, interdependency modelling and analysis by graph theory, interdepen- dencies 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 effective 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 specified 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 al- gorithms for vulnerability assessment, bottleneck detection and islands identification. • Further development of the GAM-based interdependencies control strat- egy, 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. • Identification of the cascading pathways, as well as modelling the cas- cading 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 adja- cency 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, de- cision making processes with/without ICS are demonstrated with different scenarios. Chapter 4 is on mitigating snow-caused blackouts along cascading path- ways. Based on our investigation of the Vancouver’s snow-caused power outage in November 2006, a dependency network has been built to rep- resent the causalities among these root conditions and the related con- sequences. 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 Hu- man 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, un- derstanding, 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 im- proving 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 con- cepts 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 mecha- nism 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 Administra- tion 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, Com- modity 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 re- port, North American Electric Reliability Cooperation, Oct 24, 2007. [12] R. Billinton and C. Wu, “Predictive reliability assessment of distribu- tion systems including extreme adverse weather”, In CCECE, http:// ieeex- plore.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 ad- verse weather: modelling in transmission and distribution system reliability evaluation”, In Generation, Transmission and Distribution, IEE Proceed- ings, 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 secu- rity”, 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”, Spe- cial issue of the IEEE Computer Magazine on Security and Privacy, sup- plement to computer, pp.8-10, April 2002. [22] A. Massoud and P. F.Schewe, “Preventing blackouts. Scientific Ameri- can”, www.Sciam.com, May, pp.60-67, 2007. [23] J. A. Hollman, J. R. Marti, Juri Jatskevich, and K.D. Srivastava, “Dy- namic islanding of critical infrastructures: a suitable strategy to survive and mitigate extreme events”, International Journal of Emergency Man- agement(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 Com- puter 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, De- cember 2005. [27] S. Marsh, “Critical infrastructure interdependencies”, http://iit- iti.nrc- cnrc.gc.ca/colloq/0405/04-11-04-e.html, November 4 2004. [28] D. D. Dudenhoeffer, M. R. Permann and R. L. Boring, “Decision con- sequence in complex environments: Visualizing decision impact”, In Pro- 9 Chapter 1. Introduction ceeding of Sharing Solutions for Emergencies and Hazardous Environments, American Nuclear Society Joint Topical Meeting: 9th Emergency Prepared- ness and Response/11th Robotics and Remote Systems for Hazardous Envi- ronments, 2006. [29] D. D. Dudenhoeffer, M. R. Permann and E.M. Sussman, “A parallel sim- ulation framework for infrastructure modeling and analysis”, In Proceedings of the 2002 Winter Simulation Conference, Piscataway, New Jersey: Insti- tute of Electrical and Electronics Engineers., 2002. [30] D. D Dudenhoeffer, 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 mod- eling at LANL”, Technical report, LALP-03-027,LA-UR-03-0658., 2003. [33] G. Apostolakas and D. Lemon, “A screening methodology for the identi- fication 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 ele- ments 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 infrastruc- tures”, 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”, Tech- nical 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 elec- trical networks, transportation networks, communications networks, water (oil and gas) networks, banking and finance service networks, food distri- bution 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 efficient use of limited resources; the availability of these resources are also guaranteed by their diversity. Therefore these interdependencies are mak- ing the infrastructure networks so robust that it can handle most local dis- turbances or stochastic fluctuations. On the other hand, this “system of systems” is becoming more fragile. Through cascading effects, 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 at- tacks 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. 1A version of this chapter has been accepted for publication. DeTao Mao, Mandana Sotoodeh, Kafui Monu, Jose R. Marti and K. D. Srivastava (2009), Interdependencies Con- trol: 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 Number of Event(s) Fitting Value 1950-1959 14 13 1960-1969 16 18 1970-1979 29 28 1980-1989 44 44 1990-1999 74 71 2000-2009 114 1 Under a changing climate, scientists believe that extreme adverse weather disasters will be more frequent [4]. This opinion can also be justified by the data [3] in Table 2.1 above. With these data, we find 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: Z(n) = 2.29 ( √ 5− 1 2 )n + 10.3 ( √ 5− 1 2 )−n (2.1) 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 find 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 coefficient between {xi} and {yi} is: R(xi, yi) = Cov(xi, yi)√ Cov(xi, xi)Cov(yi, yi) = 0.8732 (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 coefficient R(xi, yi) indicates the degree of linear dependence between xi and yi. A high value of R(xi, yi) implies 1Predicted 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 affected 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 disas- ters, 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. There- fore, 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 vulner- ability of our infrastructure networks is briefly introduced, and the impact of climate change on critical infrastructures (NCIs) is justified based on our research results. In Section 3.2, the concept of the adjacency matrix is gen- eralized to represent multi-arc directed physical interdependencies among critical infrastructures. Related logic rules and operations are also defined. 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 nec- essary to represent the topology, dependency direction, and interacting de- gree(s). Physical interdependencies between two components in various in- frastructure 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 vari- ables {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 = ⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣ 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 i 0 0 0 0 1 0 i 1 0 i 0 0 i 0 i 2i 0 0 0 i 0 0 1 0 1 2i 0 0 0 i 1 2 i 0 2i 0 0 0 0 i 0 2 2 0 ⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦ 2.2.1 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 redefined the multiply operator ⊗ for GAM as follows: B = A2 = A⊗A bij = n∑ k=1 aik ∩ akj 15 Chapter 2. Interdependencies Control Strategy Sub- Station 5 Hospital 6 Water Station 7 Steam Station 8 Power House 9 power power power power oil oil water water gas steam UBC CampusBCHydro 1 power GVRD 3 water gas TERASEN GAS_2 4 gas steam TERASEN GAS_1 2 Figure 2.2: UBC campus model with strong coupled compo- nents/cells(SCCs). 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 definition 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 non- negative integers. 2.2.2 Further Information Abstraction Based on GAM Computation With the physical interdependencies at the same hierarchical level repre- sented 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 identified 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 identified primarily by detecting those el- ements owning no outgoing degrees, i.e., the real parts of all the complex numbers representing interdependencies between this element and other el- ements are zeroes. nth order Influence Domains of a Cell Influence Domain of a cell refers to elements that will be affected 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 influence domain, a 2nd order influence domain, · · · , and (at most) a m− 1th order influence domain. nth order Influence Domains of a Channel Influence domains of a channel refers to the n−1th order influence domains of the downstream cells connected to this channel. The 1st order influence domain of a channel refers to the downstream cells connected to this channel. The 2nd order influence domain refers to the union of the 1st order influence domain of the downstream cells connected to this channel. Similarly, the nth order influence domain of a channel refers to the union of the n − 1th order influence 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 figure, to demonstrate the existence of SCC, the broken line is added artificially. 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 efficiently. Critical Level of External Resources or internal Cells For instance, by GAM computation, we can get that the impacting domain or influence 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 : TerasenGAS1 is {6}; the impacting domain of cell 3 : GV RD is {6, 7, 8}; the impacting domain of cell 4 : TerasenGAS1 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 offers the following advantages: • By finding 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 influence domains for any element in the graph. Therefore it is an exhaustive analysis instead of a ‘what if’ analysis; • The order of the influence domain implies that the impact index from one element to the others, which may give both essential information on where to buffer 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, crit- ical components can be detected, and a vulnerability assessment can be obtained. Furthermore, by SCC identification, interdependencies control strategies (ICS) are more rational and effective. 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 de- graded. The purpose for proposing the concept of interdependencies control in this paper is to try to reduce the sensitivities of critical services on un- expected fluctuations 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 pro- posed 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 briefly 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 different stages [6]: • Mitigation: Long before the disaster. This refers to the sustained ac- tions 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 emer- gency. • 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 efforts taken to repair and restore communities after an emergency. Based on Maslow’s theory of human motivation [16], humans have differ- ent 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 infor- mation on prioritizing the different infrastructure lifelines during emergency states. 19 Chapter 2. Interdependencies Control Strategy Maslow’s Hierarchy of Huam Needs Self-actualization Esteem Love/Belonging Safety Pysiological Normal EmergencyAlert Recovery Analysis Planning Monitoring Coordination Coordination Figure 2.3: The time line for emergency management. The five 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 disas- ter. The survivability index of each island can be briefly expressed as how long this island can survive before its linkages are re-established. Mathe- matically, 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 defined as: SII D k = min(ti) max(Tj) (i ∈ [0,m], j ∈ [1, n], ti ∈ R, Tj ∈ R+.) (2.4) The objective of interdependencies control during a disaster D̃ is to main- tain SII Dk 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 emer- gency 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 Interdependency Control according the priority of missions under current disaster D Further Information abstraction based on GAM computation Yes No Online monitoring by early warning system (EWS) No Yes Recovery Methods Improving SII Physical interdependencies representation by generalized adjacency matrix (GAM) New disaster D Emerges? Warning Broadcast Recovery-oriented Responses Under D SII • 1 ? Figure 2.4: Decision making flow chart for interdependencies control strat- egy. 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 is- landing 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 difference 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 out- going 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 con- trol strategy (see Fig.3.8) is briefly 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 util- ities for these critical services with higher priority and sections with vulner- abilities, 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 finally 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. Other- wise, 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 dura- tion; (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 char- acteristics, etc. Preparedness Stage • Early warning capability by monitoring possible disasters online, pre- solutions 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 avail- ability”, which is very similar to a rolling blackout during power out- age, but instead of losing services totally, it can keep the system op- erated 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 net- works, 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 adja- cency 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 infras- tructure networks, according to a risk analysis under the disaster context, and therefore prevent failures from spreading. The proposed strategy is an effective 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 is- land’s SII according to the local event spectrum. • Identification of complicated cascading patterns by data mining [18]. 23 Chapter 2. Interdependencies Control Strategy • Detecting time-dependent hidden interdependencies with the help of formal verification 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, “Iden- tifying, understanding, and analyzing critical infrastructure interdependen- cies”, IEEE Control Systems Magazine, vol.21, pp.11-25, Dec, 2001. [2] R. Little, “Toward more robust infrastructure: observations on improv- ing 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 Meet- ing 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 eval- uation”, 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 is- landing 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”, Inter- national 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 interdepen- dencies 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.552- 557. [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 Manage- 25 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, pre- sentation. [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 con- trolled 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 informa- tion 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 net- works”, Science, vol.286(5439), pp.509-512, 15 October 1999. [20] S. H.Strogatz, “Exploring complex networks”, Nature, vol. 410, pp.268- 276, 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 reliabil- ity of the critical infrastructure networks, which include electrical networks, transportation networks, communications networks, water (oil and gas) net- works, banking and finance 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 efficient use of lim- ited 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 stochas- tic fluctuations. On the other hand, this “system of systems” is becoming more fragile. Through cascading effects, 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 earth- quakes, 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 interdependen- cies. 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 1A 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 disas- ters, 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. There- fore, 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 neces- sary to represent their topology, dependency direction, and interacting de- gree(s). Modellable physical interdependencies between two components in various infrastructure networks can be seen as directed linkages in graph the- ory. 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: GAMubc = ⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣ 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 i 0 0 0 0 1 0 i 1 0 0 i 0 0 i 0 i 2i 0 0 0 0 i 0 0 1 0 1 2i 1 0 0 0 i 1 2 i 0 2i 1 0 0 0 0 i 0 2 2 0 1 0 0 0 0 0 0 i i i 0 ⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦ 3.2.1 Operation Rules for GAM Since the logic rules for matrix operations on semi-certain adjacency matri- ces (SAM) cannot be adopted here directly, we have redefined the multiply 28 Chapter 3. Survival from Disaster by Interdependencies Management Hospital 6 Water Station 7 Steam Station 8 Power House 9 power power power power oil oil water water gas steam UBC Campus BC Hydro 1 power GVRD 3 water gas TERASEN GAS_2 4 gas TERASEN GAS_1 2 power Non- critical Cells 10 water steam Sub- Station 5 steam Figure 3.1: UBC campus model with strong coupled cells(SCCs). operator ⊗ for GAM as follows: B = A2 = A⊗A bij = n∑ k=1 aik ∩ akj 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 definition 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 non- negative integers. 29 Chapter 3. Survival from Disaster by Interdependencies Management source Critical service Figure 3.2: Graph characteristic of external resource (left) and critical ser- vice (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 identified 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 identified primarily by de- tecting 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 Influence Domains of a Cell Influence Domain refers to elements that will be affected 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 influence domain, 2nd order influence domain · · · , and at most m− 1th order influence domain of a channel. For instance, in Fig.3.3, for element 3 (GVRD), its first order influence domain is {7} (water station), its second order influence domain is {6, 8} (hospital and steam station). For instance, in Fig.3.4, the 1st order influence domain of this broken channel is {a}, the 2nd order influence domain is {b, c}, the 3rd order influence domain is {d, e, g, f}. 30 Chapter 3. Survival from Disaster by Interdependencies Management Figure 3.3: First order influence domain {7} and second order influence domain {6, 7, 8, 10} of cell 3 (cell GVRD). nth order Influence Domains of a Channel which refers to the n−1th order Influence Domains of the downstream cells connected to this channel. For example, the 1st order influence domain of a channel refers to the downstream cells connected to this channel; The 2nd order influence domain of a channel refers to the union of the 1st order influ- ence domain of the downstream cells connected to this channel. Similarly, the nth order influence domain of a channel refers to the union of the n-1th order influence 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 figure, to demonstrate the existence of SCC, the broken line is added artificially. In the real world, the steam pipe from the Steam Station to the Substation does 31 Chapter 3. Survival from Disaster by Interdependencies Management a b ced i h g f x Figure 3.4: nth order influence 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 efficiently. Critical Level of External Resources or internal Cells For instance, by GAM computation, we can get that the impacting domain or influence domain of cell BCHydro : 1 in Figure 3.1 is {1, 5, 6, 7, 8, 9}; while the impacting domain of cell 2 : TerasenGAS1 is {6}; the impacting domain of cell 3 : GV RD is {6, 7, 8, 10}; the impacting domain of cell 4 : TerasenGAS2 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 field of graph theory the Laplacian matrix [18], some- times called admittance matrix or Kirchhoff matrix, is a matrix representa- tion 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 5 6 7 8 9 1 3 4 2 5 6 7 8 9 1 3 4 2 (a) (b) 10 10 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 defined as i,j := ⎧⎪⎨⎪⎩ deg(vi) if i = j −1 if i = j and vi is adjacent to vj 0 otherwise. (3.2) That is, it is the difference 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-semidefinite (∀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 i,j := {∑n j=1 ||sign(gij)|| if i = j and gij = 0 −1 if i = j and gij = 0 (3.3) For instance, UBC’s five 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 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 3 −1 0 0 −1 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 −1 0 −1 −1 4 −1 0 0 0 0 0 0 −1 −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 cam- pus 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). LM islandsubc = ⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣ 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 ⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦ The eigenvalues of LM islandsubc are {0, 0, 0, 0.5858, 1, 2, 2, 3, 3.42, 4}, there 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 identified: {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 con- trol is based on computations on the generalized adjacency matrix (GAM). This approach offers the following advantages: • By finding 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 influence domains for any element in the graph. Therefore, it is an exhaustive analysis instead of a ’what if’ analysis. • The order of the influence domain determines the impact index from one element to the others. Thus it may give both essential information on where to buffer 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, crit- ical components can be detected, and a vulnerability assessment can be obtained. Furthermore, by SCC identification, interdependencies control strategies (ICS) are more rational and effective. 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 avail- able simultaneously and running at full capacity. For instance, to maintain the normal operability of a hospital, the simultaneous availability of electric- ity, water, steam, natural gas, medicine, nurses, doctors, foods, communica- tion, 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 fluctuations 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 pa- per, 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 con- venient and necessary to briefly review the conceptual framework for emer- gency 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 different stages [2]: • Mitigation: Long before the disaster. This refers to the sustained ac- tions 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 emer- gency. • 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 Maslow’s Hierarchy of Huam Needs Self-actualization Esteem Love/Belonging Safety Pysiological Normal EmergencyAlert Recovery Analysis Planning Monitoring Coordination Coordination Figure 3.7: The time line for emergency management. The five 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 efforts taken to repair and restore communities after an emergency. Based on Maslow’s theory of human motivation [13], humans have differ- ent 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 different 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 briefly 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 defined as: SII D k = ⎧⎪⎨⎪⎩ min(ti) max(E(Tj)) (max(E(Tj)) > 0) min(ti) (max(E(Tj)) = 0) The objective of interdependencies control during a disaster D̃ is to maintain SII D k 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 elec- trical 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 inter- dependencies 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 protec- tion strategy aimed at preventing a system-wide blackout as a result of the cascading of low probability events [4]. The difference 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 availabil- ity of scarce resources, or isolating failures (e.g. epidemics), within a certain limited area. This decision making process for the GAM-based interdependencies con- trol strategy (see Fig.3.8) is briefly explained as fellows: Step 1: Identify all modellable physical interdependencies, and repre- sent 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 finally 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 Further Information abstraction based on GAM computation Yes No Online monitoring by early warning system (EWS) No Yes Recovery Physical interdependencies representation by generalized adjacency matrix (GAM) New disaster D Emerges? Warning Broadcast Recovery-oriented Responses SII • 0? Interdependencies Control to redistribute limited resources etc. ICS-based Decision Making Figure 3.8: Decision making flow chart for Interdependencies Control Strat- egy (ICS). not less than 0 after the expected duration of restoration, its recovery pro- cesses 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 dura- tion; (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 char- acteristics, etc. Preparedness Stage • Early warning capability by monitoring possible disasters online, pre- solutions 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 avail- ability”, which is very similar to a rolling blackout during power out- age, but instead of losing services totally, it can keep the system op- erated 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 win- ter of 2006, which affected 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 28/ 11 / 2006 15 : 00 PM 29/ 11 / 2006 1 : 00 AM 15 : 00 24 :00 3 : 20 Fuel Pipe Restored 3 : 20 Water Pipe Fixed ( Sending water to Hospital ) 27/ 11/ 2006 1 : 00 AM 27/ 11 / 2006 3 : 00 AM 02: 00 01 :20 Power Outage from BC_Hydro 01 :40 Water Pipe Broken ( Sending water to Hospital ) 02: 10 Fuel Pipe Out of Work ( Sending oil from power house to steam station) 23:00 PM Power Restored 28//11/2006 3:20 AM PM PM 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 Van- couver, 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 descrip- tion 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 transmis- sion 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 Sub- Station 5 Hospital 6 Water Station 7 Steam Station 8 Power House 9 power power power power oil oil water water gas steam UBC CampusBCHydro 1 power GVRD 3 water gas TERASEN GAS_2 4 gas TERASEN GAS_1 2 power Non- critical Cells 10 water steam Ea Eb Ec Figure 3.10: Cells on UBC campus. Where the cross “X” in the figure 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 After ICS Before ICS 48 hours (with steam) t6ele backup electricity in cell 6 32 hours ( no steam) 24 hours t6wat reserved water in cell 6 24 hours 24 hours t7wat reserved water in cell 7 24 hours 12 hours t9oil reserved oil in cell 9 24 hours 12 hours The expected recovery duration of these events are in the following Table 1Due 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 Normal 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 Duration Normal 1 hours ICS 2 hours 3.4.2 ICS-based Decision Making Activity during Emergency and Recovery State The purpose is to prevent the functionality of the whole campus from col- lapsing, and especially, to keep the critical service(s) survive during this constructed scenario. With limited restoration resources, aided by GAM- based 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 identified. (since our research objective of JIIRP is to save as many lives as possi- ble 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 identified; Step 2: No strong coupled cells (SCCs) are identified in this case; Step 3: Identified by GAM calculation, the influence 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 identified by GAM compu- tation: 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 identified: 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 Normal Ea Eb Ec Eb Ec Ea Ec Ea Eb Ec Eb Ec Ea Eb Ea Event(s) SII= 23 44 SII= -1 20 SII= 16.5 32 SII= 15 36 SII= -13 8 SII= -9 12 SII= -7.5 8 SII= 8.5 24 SII= -9 12 SII= 3 24 SII= -21 SII= -21 SII= -15.5 SII= 24 45 SII= -15.5 SII= -21SII= -21 Recovery Phase Emergency Phase r r rr rrrrr r r r r r r Figure 3.11: Decision making tree for the recovery phase without ICS oper- ations. Where Era (E r b , E r c ) refers to the recovery actions of Ea (Eb, Ec). self-sufficient duration tinti and the external self-sufficient duration t ext i of one utility. The external self-sufficient duration of one lifeline can be cal- culated along its upstream pathway identified 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 opera- tions, 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 final 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 Sub- Station 5 Hospital 6 Water Station 7 Steam Station 8 Power House 9 power power power power oil oil water water gas steam UBC Campus BC Hydro 1 power GVRD3 water gas TERASEN GAS_2 4 gas TERASEN GAS_1 2 power Non- critical Cells 10 water steam Ea Eb Ec EICS2 EICS1 Figure 3.12: ICS operations (represented by circled cross “⊗”) of redistribut- ing scarce resources during emergency stage. after the final restoration. According to the obtained results in Step 3, the order of the size of the influence domain of these events is Ea > Ec > Eb, therefore the decision branch with the restoration order Era → Erc → Erb 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 ICS Ea Eb Ec Eb Ec Ea Ec Ea Eb Ec Eb Ec Ea Eb Ea Event(s) SII= 34 44 SII= 22 20 SII= 33 32 SII= 26 36 SII= 10 8 SII= 14 12 SII= 9 8 SII= 25 24 SII= 2 12 SII= 14 24 SII= 2 SII= 1 SII= 24 46 SII= 2 SII= 1 SII= -10 SII= -10 Recovery Phase Emergency Phase r r r rrrr r r rrr r r r Figure 3.13: Decision making tree for the recovery phase after ICS opera- tions. Where Era (E r b , E r c ) 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 infras- tructure networks, according to a risk analysis under the disaster context, and, therefore, prevents failures from spreading. The proposed strategy is an effective 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; • identification 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 improv- ing 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 is- landing 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”, Inter- national 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 interdepen- dencies 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 Manage- ment. 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 con- trolled 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 informa- tion 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 net- 48 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.268- 276, 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 HYDROWinter 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 Trans- actions 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]. Affected by climate change, not only the damage degree of these storms were unbelievably higher than before, but their spatio-temporal pat- terns 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. Scien- tists 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 de- icing 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 different aspects in power outages, have not been systemized or standardized 1A 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-effect-based de- icing and anti-icing methods, which have been applied in many countries before, to our modern large-scale power networks [11]. Different to these methods stated above, we propose a systematic ap- proach 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 effects 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 ar- tificial 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 effect, 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 first snow dates and the first 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 first snow and the first heavy snow (lasting over three days) happened at the same time in 2006. This early heavy snow brought forth some negative effects 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 Annual Heaviest Snow Interval Dec 18, 1997 (1 day) Jan 1, 1998 (4 days) 14 Dec 21, 1998 (3 days) Dec 21, 1998 (3 days) 0 Dec 14, 1999 (1 day) Dec 31, 1999 (2 days) 17 Dec 14, 2000 (3 days) Dec 14, 2000 (3 days) 0 Nov 29, 2001 (3 days) Jan 17, 2002 (3 days) 49 Dec 24, 2002 (1 day) Mar 7, 2003 (3 days) 102 Nov 22, 2003 (1 day) Dec 30, 2003 (4 days) 38 Dec 6, 2004 (1 day) Jan 6, 2005 (3 days) 31 Nov 28, 2005 (5 days) Nov 28, 2005 (5 days) 0 Nov 25, 2006 (5 days) Nov 25, 2006 (5 days) 0 Nov.26, 2007 (1 day) Jan 7, 2008 (4 days) 41 52 Chapter 4. Identifying Cascading Pathways for Power Outage Mitigation More branches or trees might fall upon overhead T- Lines, bus cables, telephone lines and roads etc Climate Change/ Greenhouse Effect Temperature under Freezing Point Low Wind Speed Moister in trees making them fragile when frozen Extended Growing Season Overgrown Trees More Snow/Ice accumulated on trees Heavy and Early Wet Snow Non-updated Policies On Vegetation Management Deciduous time delayed Figure 4.1: Synthesized effect 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 Effect of Greenhouse Another factor that had worsened the effect of falling trees, was trees’ de- ciduous 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 effect has delayed the decidu- ous 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 freez- ing 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 significantly advanced in spring bud break and similarly sig- nificantly 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 difference 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 figure) and wind speed curve (lower figure) 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 modified 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 effect 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 effects 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 quantified and considered [16]. 4.2.3 Related Weather Factors Affecting 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 effected 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 cus- tomers turn on their air-conditioning equipment simultaneously, which im- pacted the power systems heavily. In some situations, power systems with- out 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 final 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 disas- ter, 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 affected events or objects, and finally reaching their com- mon destination: “the blackout of Vancouver”. The manageability of each pathway has been analyzed, classified 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 finding of countermeasures that will be discussed below. 55 Chapter 4. Identifying Cascading Pathways for Power Outage Mitigation Affected Communication Branches or trees fell down on T- Lines, Bus cables, Telephone lines and roads More snow/ice accumulated on Trees Snow/ice accumulated on Roads Load Impacts T-Line Fault Events Power Outage Snow/ice accumulated on T-lines Delayed Recovery Processes System Integrity Broken Snow/ice accumulated on Bus cables Snow/ice accumulated on Teleph-Lines Degraded Traffic 2 (a) 3 (a) 3 (c) 2 (b) 6 (a) 5 (a)4 (a) 5 (b) 6 (b) 4 (b) 4 (c) Manageable Pathway Un-Manageable Pathway Concurrent Processes 3 (b) Greenhouse Effect/ Climate Change Extended Growing Season Early and Heavy Wet-Snow Temperature under Freezing Point Low Wind Speed Non-updated Policies On Vegetation Management Delayed Deciduous Time 1 Overgrown Trees Internal moisture making trees fragile when frozen Figure 4.3: Dependency network for these cascading pathways unfolded dur- ing 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 de- icing 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 sys- tematic 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 un- certainties in CC science and predictions, which warrant that investment in adaptation measures to manage climate risks may prove to be more certain and tangible benefits rather than just reducing CO2[23]. According to Fig.4.3, meteorological factors globally affect all down- stream 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 es- pecially based on the feasibility studies of forecasting heavy snow storms[23][24], we propose some meteorology modification methods, such as artificial pre- cipitation stimulation (APS). The effect of artificial 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 Will it snow/rain in t0? No All other preconditions are satisfied? Snowing time > t1? Yes Yes No No Anticipated Responses Based on the current ice accretion pattern, to calculate the threshold duration t1 Yes Forecasting processes Forecasting process Warning Artificial Precipitation Stimulation Online Weather Monitoring Figure 4.4: Decision making process for artificial precipitation stimula- tion(APS) action. mass of accreted snow per unit length of wire can be expressed as W = 4.5 e−6(T/T0−0.32)2 V 0.2N Pnt (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 effective pathways, in which benefit of any feasible mitigation and/or countermeasure generally 58 Chapter 4. Identifying Cascading Pathways for Power Outage Mitigation t0 t1 t2 Wind Speed Temperature Humidity Ice Accretion Durationafter APS Estimated Ice Accretion Duration Snowing process without APSSnowing process after APS t0' Time window for APS t3 Figure 4.5: Active suppression of the development process of atmospheric icing by artificial precipitation stimulation. Where t0 denotes present time, t′0 denotes the APS action time, t1 denotes the beginning time of ice ac- cretion, (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 cascad- ing pathway (uMCP). In Fig.4.3, except pathway 1, there are in total 10 manageable cascading pathways left. Besides anti-icing and de-icing meth- ods 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 sig- nificantly by the geographical location of the transmission lines. During snow storms (or flood, 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 trans- mission line at one of these locations is Po during a snow storm, then the probability of transmission failure is: P ss1 = 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 P ss2 , 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: P ss2 P ss1 = 1− (1− Pu)3n 1− (1− Po)3n ( Pu Po )3n (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 relia- bility. 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 fibers. 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 affected by weather factors, to reduce the load impacts under similar situation, previous plan for reserved gener- ation 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, espe- cially to keep these critical services or essential missions survive during ad- verse 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 in- vestigated the power outage in the Vancouver area in November 2006, and discovered that climate change seriously affected this power outage. By con- sidering 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 Trans- actions of the Royal Society, vol.358, pp.2941-2970, 2000. [10] CIGRE Task Force 33.04.09, “Influence of ice and snow on the flashover performance of outdoor insulators, part I: effects of snow”, Electra, vol.188, pp.55-69, 2000. [11] M. Farzaneh, Atmospheric Icing of Power Networks, Springer Nether- lands, 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 Struc- tures (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 manage- ment”, 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 re- sponse 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 senes- cence”, Global Change Biology, vol.14(2), pp.264-275, February 2008. [20] A. Menzel and P. Fabian, “Growing season extended in Europe”, Na- ture, 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 Geophys- ical Research, vol.106, pp.20069-20083, 2001. [22] TELUS Communications Company, “Telecom decision CRTC 2007- 72”, 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 ap- plication 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, Oc- tober 2000. [26] D. O. Koval, B. Shen, S. Shen, and A. A. Chowdhury, “Modeling severe weather related high voltage transmission line forced outages”, in Trans- mission and Distribution Conference and Exhibition, 2005/2006 IEEE PES, 21-24 May 2006, pp.788-793. [27] unknown, “Important factors affecting underground placement of trans- mission”, 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, identification and analysis of interdependencies among critical infrastructures was drawn in- creasing attention. Affected by a changing global climate, as well as by the advancements and changes in technologies, economics and policies, the orga- nizational 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 effort should be devoted in studying the important role that interdependencies play in a changing environment, on the continuity and reliability aspects of infrastructure op- eration 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 net- works 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 cur- rent stage, tracking all such interdependencies is too complex, the price of preventing all possible failures may be extremely high, investing on the sur- vival of critical services is more feasible than preventing all large cascading failures. With the physical interdependencies represented by the general- ized 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 man- age the interdependencies among the critical infrastructure networks, and, therefore, can improve the survivability of any critical service as well as pre- vent potential large cascading failures. The proposed strategy is an effective means to reduce the inherent vulnerability of interconnected critical infras- tructure 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 probabil- ity 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 decid- uous time (all climate change related variables) had played an important role in affecting 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 de- veloped 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 interdependen- cies research. But because of the strong nonlinearity and high complexity introduced by the connectivity among the infrastructure networks, interde- pendencies are still a very difficult 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 specified 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 interde- pendencies of local infrastructures; • Identification of complicated cascading patterns by data mining [4]; • Detecting time-dependent hidden interdependencies with the help of formal verification 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 Manage- ment (IJEM), vol.4(1), pp.45-58, 2007. [2] Jose R. Marti, Jorge A. Hollman, C. Ventura and J. Jatskevich, “Dy- namic 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 Proceed- ings 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 in- formation creating tool”, OCLC Systems and Services, vol.15(2), pp.81-90, 1999. 66  67    Appendices Appendix A Introduction on I2Sim A.1 Conceptual Framework of I2Sim One of the goals of JIIRP is to build a simulator on interdependent in- frastructures (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 solu- tion 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 different 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 flow 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 com- ponents of the physical layer, tokens, cells, channels, external sources, re- serves, 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 first layer is the cell’s functional- ity, where specific amounts of input tokens are needed to produce specific amounts of output tokens, and this functionality is abstracted from human readable table (HRT, which will be explained in detail in Chapter B). An- other layer is the physical (inter)dependencies layer among different 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 satisfied. 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 quantified and represented. A.2 Clustered I2Sim Integrated into a Single Machine The previous version of I2Sim was implemented by the five PCs of the 16- machine PC-cluster at UBC power lab, whose topological structure can be seen in Fig.A.4. However, instead of using SCI communication in the pc- cluster distributed model [2](Fig.A.3), here a top system is created at the highest level, which includes the five cells as subsystems, data store memories [3] for global variables are applied to synchronize the five subsystems, and thus integrate the five 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 xxx xxx xxx xxx xxx xxx xxx xxx xxx y y yy y y y y y y y y y y y y y p1 p2 p3 r1 r2 r3w1 w2 w3 w1 w2 w3 r1 r2 r3 p1 p2 p3 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 tx itx i 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 different events created by human activities, the impacts and effects 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 flow-type delay, since in most cases, this type channel’s capacity is defined as the volume of flow. Thus for the flow 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 τ = Lτ0 τ τ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 chan- 72 Appendix A. Introduction on I2Sim nel; the “varying delay” block refers to the real time delay for the channel, but emphasis on the delay affected 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 traffic flow; the “Availability coefficient 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, “Dy- namic 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 infras- tructure 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] Hafiz 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 Continuous Function Representation for Complicated Cells Based on Human Readable Tables (HRT) Method B.1.1 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 different infrastructure networks , in most situations, the interactions among these inputs cannot be modelled in an explicit way, also it is difficult 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 fitting 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 combina- tion of their different 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 y xx y Figure B.1: The ideal multi-dimension fitting function in a 2-D subspace viewed from different 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 effect). But because of these physical constraints, such as system scale and other hardware bottle necks (saturation effect), the final operability cannot be infinite, it can be seen as a set of equilibria, which demonstrates the com- promised competition between two effects: Matthew effect and saturation effect. 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 f(x, α0,K1, x0) = α0 α0 + (1− α0) · e−K1·(x−x0) (B.1) (0% < x,α0, x0, x− x0 < 100%). When projected in a 2D subspace, this multi-Dimension fitting 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 off- 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 fixed, thus it can easily be recovered by 76 Appendix B. Introduction on HRT Method and GAM Representation HRT Data in Per Unit System Function F(x i, Į i ) represented by key parameters { Į i } Multi-Dimension Nonlinear Continuous Function in Normal Form F(x i, Į i ) i Abstract Subroutines For each single-D by LSE. Synthesis these single-D Subroutines Calculation on the upper and low boundaries. Searching the linear interpolation parameter(s) between the boundaries by LSE. 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 efficiency greatly. B.1.4 Multi-dimension Function to Approximately Represent the Operability of Cells Based on HRT the Multi-dimension efficiency function of hospital in a view of optimism Usually a convex metric need to be constructed to synthesis these in- putting utilities, but in this case, it is obvious that the hospital’s efficiency 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 fitted 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 fitting 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 vari- ables with the similar characteristics will be fused together, therefore this method can reconstruct the multi-dimension function with incom- plete information. 78 Appendix B. Introduction on HRT Method and GAM Representation B.2 Infrastructure Interdependencies and Their Representation by the Generalized Adjacency Matrix (GAM) B.2.1 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 di- rected 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 field, where logic rules and algebraic operations are also redefined. In this thesis, all related interdependency anal- ysis 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 efficiently. Based on the cal- culated results of the SCC, critical components, vulnerability assessment, sensitivity analysis can also be obtained. By SCCs identification, 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 influences 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 effects on infrastructure agents. In the sections that follow, four principal classes of interdependencies: physical, cybertical, geographic and policy, will be defined. Although each has distinct characteristics, these classes of interdependencies are not mutually exclusive. • Physical Interdependency: Two infrastructures are physically interde- pendent 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 Tele-Com Water Banking & Finance Transportation Emergency Service Gov’t Service Fuel supply Compressor Station T-lines Electric Power Power PlantSubstation Traffic Light Transport Fire Hall Call Centre Ambulence Hospital Treasury DepartLegislative Offices Military Installation Pension Servie/ Payment End Office Switching Office Reservior WaterStation ATM Check Processing Centre Federal Reserve Bank Figure B.4: Infrastructure interdependencies among those critical infras- tructure networks. the other. • Geographic Interdependency: Infrastructures are geographically inter- dependent if a local environmental event can create state changes in all of them. • Cyber Interdependency: An infrastructure has a cyber interdepen- dency if its state depends on information transmitted through the information infrastructure. • Logical Interdependency: Two infrastructures are logically interde- pendent 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 effect 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 five 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 Redefined Operation Rules In Fig.B.6, five cells on UBC campus can be seen as an instance of Infras- tructure 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. AGAM = ⎡⎢⎢⎢⎢⎣ 0 1 0 0 1 i 0 2 2 0 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 sig- nificant, it is not permitted here, for instance, for order n = 1, by definition, 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 defined the multiply operator ⊗ of generalized SAM, B = A2 = A⊗A bij = n∑ k=1 aik ∩ akj here bij is the element of B, and ∑ is algebraic “sum” in regular sense. ∩ is logic “and” (&) but has a generalized definition 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 different orders of matrix will become simple, and the interdependency relationship between different 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 finding all these pathways between any pair of components or vertices, GAM can identify or detect the whole possible correlated or affected 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 in- 83 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 buffer the cascading failures with the minimum cost. Also for a detailed local interdependencies model, GAM can tell us all these unexpected weak- nesses. 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 flow 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) identified 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.337- 358, 2007. [3] Steven M. Rinaldi, James P. Peerenboom, and K. Kelly Terrence, “Iden- tifying, understanding, and analyzing critical infrastructure interdependen- cies”, IEEE Control Systems Magazine, vol.21, pp.11-25, Dec, 2001. [4] De Tao Mao, “Modelling hospital: Construction and fitting the multi- dimension I/O function with incomplete information”, Technical report, Uni- versity of British Columbia, 14 September 2007. [5] Lu Liu, “Prototyping and cells modelling of the infrastructure interdepen- dencies 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-definited GAM matrix operation, a library of functions coded in MATLAB has been developed. Table C.1: Library of Functions for GAM Operation Function Name Description gc and.m Generalized “and ” for two scalar variables. gc multiply.m Generalized “multiply” for two matrixes. gc RC.m Generalized “multiply” for a two vectors. Check SCC.m Check the existence and identify the SCCs. setdiagonal.m Set the diagonal elements to zeroes. SCC Compress.m Compress SCC after calculating them out. Set Minus.m Subtraction between two SCCs and theri subsets. checkGAM.m Check whether a matrix is a GAM. findout SubSet.m Find a subsets of SCCs. Get subset SCC.m Find out all the subsets of SCCs. Display SCC.m Display the subsets of SCCs. check GAMcomp.m Verify the compressed GAM. Pathway Finder.m Find out all the pathways between two elements. Display Paths.m Display all the pathways between two elements. mainSCC.m Main program for finding, compressing and displaying both SCC and pathways. GAM2Lap.m To convert GAM into Laplacian matrix. Number of Paths.m To find out how many paths in one connectivity. InfDomain of Cell.m To find out whole influence domain of a cell. InfDomain of Link.m To find out whole influence 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 definited 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 definited 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 definited 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 vari- able!’); 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=find(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 finding them out. Code: function y=SCC Compress(A,SCC) SCC=SCC(1:end-2); index=find(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=find(y1==1); A(position B)=0; [v,w]=find(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]=find(y∼=0); if length(n1)*length(n2)==0 y sym=1; else y sym=0; end; realA=real(A); imagA=imag(A); [n1,n2]=find(realA<0); [n3,n4]=find(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=findout 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=find(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(find(y==SCC(i))); [n2,m2]=size(find(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: find 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=findout 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=find(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=find(sub SCC m =0); subSCCm=sub SCC m(index nonzero); str=[’Except subset: [’,num2str(subSCCm),’],There is no other sub- sets 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 Verification 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(find(RB>0)); [irb,icb]=size(find(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: find 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=find(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=find(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 find, compress and display SCCs and path- ways. 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(find(RB>0)); [irb,icb]=size(find(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=find(x(i,:) =0); y(i,c)=-1; y(i,i)=length(c); end; end; C.1.17 Pathway Number Description: find 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: find out the influence 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=find(A =0); cell set=union(cell set,c); end; C.1.19 Channel’s Domain Description: find out the influence 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=find(A =0); cell set=union(cell set,c); end; 104 Appendix D Publications [1]Detao Mao, Peng Zhang, Hafiz 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]Hafiz Abdur Rahman, Mazana Armstrong, DeTao Mao, and Jose R. Marti, “I2Sim: A Matrix-partition based Framework for Critical Infras- tructure 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 Snow- caused 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 Dis- aster by Interdependencies Management”, International Journal of Emer- gency Management (to be submitted) 105"""@en ; edm:hasType "Thesis/Dissertation"@en ; vivo:dateIssued "2009-11"@en ; edm:isShownAt "10.14288/1.0067512"@en ; dcterms:language "eng"@en ; ns0:degreeDiscipline "Electrical and Computer Engineering"@en ; edm:provider "Vancouver : University of British Columbia Library"@en ; dcterms:publisher "University of British Columbia"@en ; dcterms:rights "Attribution-NonCommercial-NoDerivatives 4.0 International"@en ; ns0:rightsURI "http://creativecommons.org/licenses/by-nc-nd/4.0/"@en ; ns0:scholarLevel "Graduate"@en ; dcterms:title "Survival from disaster : interdependencies management in critical infrastructure networks"@en ; dcterms:type "Text"@en ; ns0:identifierURI "http://hdl.handle.net/2429/12268"@en .