Abstract
In Nature, the primary goal of any network is to survive. This is less obvious for engineering networks (electric power, gas, water, transportation systems, etc.) that are expected to operate under normal conditions most of the time. As a result, the ability of a network to withstand massive sudden damage caused by adverse events (or survivability) has not been among traditional goals in systems design. Reality, however, calls for the adjustment of design priorities. As modern networks develop toward increasing their size, complexity, and integration, the likelihood of adverse events also increases due to technological development, climate change, and activities in the political arena, among other factors. Under such circumstances, a network failure has an unprecedented effect on lives and economy. To mitigate the impact of adverse events on network operability, the survivability analysis must be conducted at an early stage in network design. Such analysis requires the development of new analytical and computational tools. A computational analysis of network survivability is an exponential time problem that makes the analysis computationally unfeasible for large-scale networks. The current paper describes a new algorithm in which reduction of the computational cost is achieved by mapping an initial network topology with multiple sources and sinks onto a set of simpler smaller topologies with multiple sources and a single sink. Steps for further reducing the time and space expenses of computations are also discussed.
Similar content being viewed by others
Notes
Initially, the algorithm was presented in the conference paper (Poroseva 2010b) with application to a power system. The current paper, however, is an independent work for the most part.
References
Committee on the societal and economic impacts of severe space weather events: a workshop, national research council (2008) Severe space weather events—understanding societal and economic impacts: a workshop report (2008). The National Academies Press. http://books.nap.edu/openbook.php?record_id=12507&page=1
Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, 2nd edn. MIT Press/McGraw-Hill, Cambridge/New York, pp 540–549
Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco
Goldreich O (2008) Computational complexity: a conceptual perspective. Cambridge University Press, Cambridge
Hill J (2005) Survivable architectures for vital systems. In: Proceedings of the ASNE reconfiguration and survivability symposium, Jacksonville, FL, USA, February
IEEE (2010) Recommended practice for 1 to 35 kV medium voltage DC power systems on ships. IEEE P1709/Draft D0.8.2, New York, NY, Jan 2010
Lancaster J (2000) Engineering catastrophes: causes and effects of major accidents. CRC Press, Boca Raton
Neumayr D, Poroseva SV (2011) On development of computational tools for evaluating system survivability due to its topology. In: Proceedings of the 52nd AIAA/ASME/ASCE/AHS/ASC structures, structural dynamics and materials conference, Denver, USA, April. AIAA-2011-1818
Newman M, Barabasi A-L, Watts DJ (2006) The structure and dynamics of networks. Princeton University Press, Princeton
North American Electric Reliability Corporation (2007) Results of the 2007 Survey of Reliability Issues. http://www.nerc.com/files/Reliability_Issue_Survey_Final_Report_Rev.1.pdf
Oliveto FE (1998) System efficiency/merit. In: Proceedings of the IEEE 1998 NAECON, Dayton, OH, USA, July, pp 51–59
Papadimitriou CH (1994) Computational complexity. Addison-Wesley, Reading
Poroseva SV (2010a) Computational analysis of network survivability with application to power systems. Phys Procedia 4:113–117
Poroseva SV (2010b) Designing power system topologies of enhanced survivability. In: Proceedings of the 51st AIAA/ASME/ASCE/AHS/ASC structures, structural dynamics, and materials conference, Orlando, FL, USA, April. AIAA-2010-2572
Poroseva SV, Woodruff SL, Hussaini MY (2005) Topology of the generator bus in a warship integrated power system. In: Proceedings of the IEEE electric ship technologies symposium, Philadelphia, PA, USA, July, pp 141–148
Poroseva SV, Lay N, Hussaini MY (2009) Algorithm development for evaluating the IPS survivability due to its topology. In: Proceedings of the IEEE electric ship technologies symposium, Baltimore, MD, USA, April, pp 253–260
President’s commission on critical infrastructure protection, critical foundations (1997) Protecting Americas infrastructures. http://www.fas.org/sgp/library/pccip.pdf
Saleh AJH, Castet J-F (2011) Spacecraft reliability and multi-state failures. Wiley, New York. Chap 8.2
The NextGen Energy Council Management Information Services, Inc. (2008) Lights out in 2009? http://www.oe.energy.gov/DocumentsandMedia/Attachment_1_Nextgen_Energy_Council_Lights_Out_Study.pdf.pdf
U.S. DOE (2002) Transmission grid. http://www.ferc.gov/industries/electric/gen-info/transmission-grid.pdf
U.S. DOE (2005) Overview of the electric grid. http://www.energetics.com/gridworks/grid.html
Acknowledgements
The author would like to thank anonymous reviewer #1 for the thorough review and helpful suggestions.
Author information
Authors and Affiliations
Corresponding author
Appendices
Appendix A
Let us show that indeed \(\sum_{j = 1,\ldots,\mathit{VB}} M_{j} 2^{M_{j}} \le \mathit{VB}\max [M_{j}]2^{\max [M_{j}]} < M2^{M}\). To prove it is to show that \(\mathit{VB}\max [M_{j}]2^{\max [M_{j}]} < M2^{M}\), when 1<VB≤M−1, M≥3, and max[M j ]≤M−1. The values of VB and max[M j ] are not independent from one another. The relation between them is given by the following expression: max[M j ]≤M−VB+1. That gives us
The next step is to show that VB⋅(M−VB+1)2M−VB+1<M2M. Dividing both sides of this expression by M2M results in
Substitution of x=VB−1 into this expression gives
Function (x+1)/2x is monotonically decreasing from 1 to (M−1)/2M−2 with x increasing from 1 to M−2. Because M is never less than 3, the value of this function is 1 or less.
The value of x is always less than M, therefore expression (1−x/M) is always less than 1.
Thus, the product of (x+1)/2x and (1−x/M) is always less than 1, that is, indeed
Appendix B
To prove that (4) holds true is to show that
We will use an approach similar to the one in Appendix A. That is, let us first make a substitution of max[M j ] with max[M j ]≤M−VB+1:
After dividing both sides of this expression by 2M
and moving 1 from the left side to the right, one has to prove that
After two substitutions, such as, x=VB−1 and a=M−1, the final expression takes the following form
Dividing both sides of this expression by a gives
It was shown in Appendix A that function (x+1)/2x is monotonically decreasing from 1 to (M−1)/2M−2 with x increasing from 1 to M−2. Because M is never less than 3, the value of this function is 1, when M=3, or less than 1 when M>3.
Let us discuss the behavior of term (1−x)/a. This term is equal to zero when x is equal to 1 and becomes negative with x increasing. Therefore, term (1+(1−x)/a) is equal to 1 at M=3 (VB=2) and is less than 1 for all other values of x.
Combining the properties of both terms—(x+1)/2x and (1+(1−x)/a)—, one can conclude that the product of both terms is equal to 1 when M=3 or less than 1 for M>3.
Thus, expressions (5) and (4) are satisfied when M>3. Clearly, the case of M=3 (one source with two adjacent VB-links) is not of importance in designing engineering networks. Therefore, we conclude that expression (4) holds true for the purposes of the survivability analysis of engineering networks.
Rights and permissions
About this article
Cite this article
Poroseva, S.V. “Selfish” algorithm for reducing the computational cost of the network survivability analysis. Optim Eng 15, 381–400 (2014). https://doi.org/10.1007/s11081-012-9207-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11081-012-9207-1