of 5
Failure Localization in Power Systems via Tree Partitions
Linqi Guo, Chen Liang, Alessandro Zocca, Steven H. Low, and Adam Wierman
Computing and Mathematical Sciences, California Institute of Technology
1200 E. California Blvd, Pasadena, CA, 91125, USA
Email:
{
lguo, cliang2, azocca, slow, adamw
}
@caltech.edu
.
ABSTRACT
Cascading failures in power systems propagate non-locally,
making the control and mitigation of outages extremely hard.
In this work, we use the emerging concept of the
tree parti-
tion
of transmission networks to provide an analytical char-
acterization of line failure localizability in transmission sys-
tems. Our results rigorously establish the well perceived in-
tuition in power community that failures cannot cross bridges,
and reveal a finer-grained concept that encodes more precise
information on failure propagations within tree-partition re-
gions. Specifically, when a non-bridge line is tripped, the
impact of this failure only propagates within well-defined
components, which we refer to as
cells
, of the tree par-
tition defined by the bridges. In contrast, when a bridge
line is tripped, the impact of this failure propagates
globally
across the network, a
ecting the power flow on all remain-
ing transmission lines. This characterization suggests that it
is possible to improve the system robustness by
temporarily
switching o
certain transmission lines, so as to create more,
smaller components in the tree partition; thus spatially lo-
calizing line failures and making the grid less vulnerable to
large-scale outages. We illustrate this approach using the
IEEE 118-bus test system and demonstrate that switching
o
a negligible portion of transmission lines allows the im-
pact of line failures to be significantly more localized without
substantial changes in line congestion.
1. INTRODUCTION
Power system reliability is a crucial component in the
development of sustainable modern power infrastructure.
Recent blackouts, especially the 2003 and 2012 blackouts
in Northwestern U.S. [1] and India [2], demonstrated the
devastating economic impact a grid failure can cause. In
even worse cases, where facilities like hospitals are involved,
blackouts pose direct threat to people’s health and lives.
Because of the intricate interactions among power sys-
tem components, outages may cascade and propagate in a
very complicated, non-local manner [3–5], exhibiting very
This work has been supported by Resnick Fellowship,
Linde Institute Research Award, NWO Rubicon grant
680.50.1529., NSF grants through PFI:AIR-TT award
1602119, EPCN 1619352, CNS 1545096, CCF 1637598,
ECCS 1619352, CNS 1518941, CPS 154471, AitF 1637598,
ARPA-E grant through award DE-AR0000699 (NODES)
and GRID DATA, DTRA through grant HDTRA 1-15-1-
0003 and Skoltech through collaboration agreement 1075-
MRA.
Copyright is held by author/owner(s).
di
erent patterns for di
erent networks [6]. Such complex-
ity originates from the interplay between network topology
and power flow physics, and is aggravated by possible hid-
den failures [7] and human errors [8]. This complexity is the
key challenge for research into the modeling, control, and
mitigation of cascading failures in power systems.
There are three traditional approaches for characterizing
the behavior of cascades in the literature: (i) using sim-
ulation models [9] that rely on Monte-Carlo approaches to
account for the steady state power flow redistribution on DC
[5,8,10,11] or AC [12,13] models; (b) studying purely topo-
logical models that impose certain assumptions on the cas-
cading dynamics (e.g., failures propagate to adjacent lines
with high probability) and infer component failure propa-
gation patterns from graph-theoretic properties [14–16]; (c)
investigating simplified or statistical cascading failure dy-
namics [3,17–19]. In each of these approaches, it is typically
challenging to make general inferences across di
erent sce-
narios due to the lack of structural understanding of power
redistribution after line failures.
A new approach has emerged in recent years, which seeks
to use spectral properties of the network graph in order to
derive precise structural properties of the power system dy-
namics, e.g., [20–22]. The spectral view is powerful as it of-
ten reveals surprisingly simple characterizations of the com-
plicated system behaviors. In the cascading failure context,
a key result from this approach is about the
line outage
distribution factor
[6, 23]. Specifically, it is shown in [21]
that the line outage distribution factor is closely related to
transmission graph spanning forests.
While this literature has yet to yield a precise characteri-
zation of cascades, it has suggested a new structural repre-
sentation of the transmission graph called the
tree partition
,
which is particularly promising. For example, [21] shows
that line failures in a transmission system cannot propagate
across di
erent regions of the tree partition (for more back-
ground on the tree partition, see Section 2).
Contributions of this paper:
We prove that the tree
partition proposed in [21] can be used to provide an analyti-
cal characterization of line failure localizability, under a DC
power flow model, and we show how to use this characteriza-
tion to mitigate failure cascades by temporarily switching o
asmallnumberoftransmissionlines.
Our results rigorously
establish the well perceived intuition in power community
that failures cannot cross bridges, and reveal a finer-grained
concept that encodes more precise information on failure
propagations within tree-partition regions. This work builds
on the recent work focused on the line outage distribution
factor, e.g., [6, 21, 24], and shows that the tree partition is
a particularly useful representation of this factor, one that
Performance
Evaluation
Review,
Vol.
46,
No.
2, September
2018
57
captures many aspects of how line failures can cascade.
Our formal characterization of localizability is given in
Theorem 3. It shows that the impact of tripping a non-
bridge line only propagates within well-defined components,
which we refer to as cells, inside the tree partition regions.
In constrast, the failure of bridge lines, in normal operating
conditions, propagate globally across the network and im-
pact the power flow on all transmission lines. In order to
prove these results, we depend on properties of the tree par-
tition proved in [21] as well as some novel properties derived
in [25]. Further, we make use of the block decomposition
of tree partition regions to completely eliminate the graph
spanning forests among distinct cells, which in the spectral
view means failure localization [21]. Lastly, we apply classi-
cal techniques from algebraic geometry to address potential
pathological system specifications and establish our results.
The characterization we provide in Theorem 3 yields many
interesting insights for the planning and management of
power systems and, further, suggests a new approach for
mitigating the impact of cascading failures. Specifically, our
characterization highlights that switching o
certain trans-
mission lines
temporarily
in responds to the real-time injec-
tion profile can lead to more, smaller regions/cells, which
localize line failures, thus making the grid less vulnerable
against line outages. In Section 4, we illustrate this approach
using the IEEE 118-bus test system. We demonstrate that
switching o
only a negligible portion of transmission lines
can lead to significantly better control of cascading failures.
Further, we highlight that this happens without significant
increases in line congestion across the network.
2. PRELIMINARIES
We use the graph
G
=(
N
,
E
) to describe a power trans-
mission network, where
N
=
{
1
,...,n
}
is the set of buses
and
E
N
N
is the set of transmission lines. The terms
bus/vertex and line/edge are used interchangeably. An edge
in
E
between vertices
i
and
j
is denoted either as
e
or (
i, j
).
We assume
G
is connected and simple, and assign an arbi-
trary orientation over
E
so that if (
i, j
)
2
E
then (
j, i
)
/
2
E
.
The line susceptance of
e
is denoted as
B
e
and the branch
flow on
e
is denoted as
P
e
. The susceptance matrix is defined
to be the diagonal matrix
B
=diag(
B
e
:
e
2
E
).
We denote the power injection and phase angle at bus
i
as
p
i
and
i
,anduse
n
and
m
to denote the number of
buses and transmission lines in
G
. The vertex-edge incidence
matrix of
G
is the
n
m
matrix
C
defined as
C
ie
=
8
>
<
>
:
1 if vertex
i
is the source of
e
1 if vertex
i
is the target of
e
0 otherwise.
With the above notation, the DC power flow model can be
written as
p
=
CP
(1a)
P
=
BC
T
,
(1b)
where (1a) is the flow conservation constraint and (1b) is
Kirchho
’s and Ohm’s Laws. The slack bus phase angle in
is typically set to 0 as a reference to other buses. With
this convention, the DC model (1) has a unique solution
and
P
for each injection vector
p
such that
P
j
2
N
p
j
=0.
When a line
e
is tripped, the power flow redistributes
according to the DC model (1) on the newly formed graph
G
0
=(
N
,
E\{
e
}
). If
G
0
is still connected, then the branch
Figure 1: The construction of
G
P
from
P
.
flow change on a line ˆ
e
is given as
P
ˆ
e
=
P
e
K
e
ˆ
e
,
where
K
e
ˆ
e
is the
line outage distribution factor
[23] from
e
to ˆ
e
. It is known that this distribution factor is independent
of the original power injection
p
and can be computed from
the matrices
B
and
C
[23].
If the new graph
G
0
is disconnected, then it is possible that
the original injection
p
is no longer balanced in the connected
components of
G
0
. Thus, to compute the new power flow, a
certain power balance rule
B
needs to be applied. Several
such rules have been proposed and evaluated in literature
based on load shedding or generator response [5,6,26–28]. In
this work, we do not specialize to any such rule and instead
opt to identify the key properties of these rules that allow
our results to hold. With this more abstract approach, we
can characterize the power flow redistribution under a class
of power balance rules.
For a power network
G
=(
N
,
E
), a collection
P
=
{N
1
,
N
2
,
···
,
N
k
}
of subsets of
N
is said to form a
partition
of
G
if
N
i
\
N
j
=
;
for
i
6
=
j
and
[
k
i
=1
N
i
=
N
. For any partition, we can define
a reduced multi-graph
G
P
from
G
as follows. First, we reduce
each subset
N
i
to a super node (see Figure 1). The collection
of all super nodes forms the node set for
G
P
.Second,weadd
an undirected edge connecting the super nodes
N
i
and
N
j
for each pair of
n
i
,n
j
2
N
with the property that
n
i
2
N
i
,
n
j
2
N
j
and
n
i
and
n
j
are connected in
G
.Notethat
multiple ledges are added when multiple pairs of such
n
i
,n
j
exist. Unlike the graph
G
to which we assign an arbitrary
orientation (and thus is a directed graph), the reduced multi-
graph
G
P
is undirected.
Definition 1.
A partition
P
=
{N
1
,
N
2
,
···
,
N
k
}
of
G
is
said to be a
tree partition
if the reduced graph
G
P
forms a
tree.
Definition 2.
Given a tree partition
P
=
{N
1
,
N
2
,
···
,
N
k
}
,
the sets
N
i
are called the
regions
of
P
.Anedge
e
=(
w, z
)
with both endpoints inside
N
i
is said to be
within
N
i
.If
e
is not within
N
i
for any
i
,thenwesay
e
forms a
bridge
.
In [25], we derived a set of results regarding the reducibil-
ity, uniqueness, and computational complexity of tree par-
titions. In particular, it is shown that each graph
G
has a
unique irreducible tree partition and this particular parti-
tion can be computed in linear time. Thus, to simplify the
terminology, whenever we say the tree partition of
G
in the
sequel, we always refer to its irreducible partition.
3. SUMMARY OF RESULTS
Our main result applies in contexts where the system is
operating under
normal
conditions, i.e., when the following
58
Performance
Evaluation
Review,
Vol.
46,
No.
2, September
2018
Figure 2: Non-zero entries of the
K
e
ˆ
e
matrix (as
represented by the dark blocks) for a graph with
tree partition
{N
1
,
N
2
,
···
,
N
k
}
and bridge set
E
b
.The
small blocks represent cells inside the regions.
two assumptions are satisfied: (a) the injection is
island-
free
; and (b) the grid is
participating
with respect to its
power balance rule. Moreover, to address certain patholog-
ical cases, we add a perturbation drawn from certain prob-
ability measure
μ
to the line susceptances and assume
μ
is
absolutely continuous with respect to the Lebesgue measure
L
m
on
R
m
. We redirect the readers to our online report [25]
for formal definitions of these terminologies and proof of our
result.
Theorem 3.
For a power network operating under normal
conditions,
K
e
ˆ
e
6
=0
almost surely in
μ
if and only if:
1.
e,
ˆ
e
are within a common tree partition region and
e,
ˆ
e
belong to the same cell; or
2.
e
is a bridge.
This result highlights that, for a practical system, the
tree partition encodes rich information on how the failure
of a line propagates through the network. We emphasize
that: (i) the condition that
μ
is absolutely continuous with
respect to
L
m
is satisfied by almost all practical probabil-
ity models for such perturbations; and (ii) the conditions
that the injection is island-free and the grid is participat-
ing are satisfied in typical operating scenarios. Therefore,
the conditions posed in Theorem 3 are satisfied in practical
settings.
Figure 2 shows how the tree partition is linked to the spar-
sity of the
K
e
ˆ
e
matrix through Theorem 3. It suggests that,
compared to a full mesh transmission network consisting of
single region/cell, it can be beneficial to
temporarily
switch
o
certain lines so that more regions/cells are created and
the impact of a line failure is localized within the cell in
which the failure occurs. We study this network planning
and design opportunity in Section 4.
4. LOCALIZING CASCADING FAILURES
Our findings highlight a new approach for improving the
robustness of the network. More specifically, Theorem 3
suggest that it is possible to localize failure propagation by
temporarily
switching o
certain transmission lines. This
creates more, smaller areas where failure cascades can be
contained. We remark that the lines that are switched o
are still part of the system. In cases where the newly created
bridges are tripped, some of these lines should be switched
on so the system are still connected. The examples presented
below are preliminary and we are still investigating how to
optimally tradeo
the increased robustness from localized
failures and the yet also increased vulnerability from having
more bridges.
(a)
(b)
Figure 3: (a) A double-ring network.
G
is the gen-
erator bus and
L
is the load bus. Arrows represent
the original power flow. (b) The new network after
removing an edge. Arrows represent the new power
flow.
It is reasonable to expect that such an action may in-
crease the stress on the remaining lines and, in this way,
worsen the network congestion. In fact, one may expect
that improved system robustness obtained by switching o
lines
always
comes at the price of increased congestion lev-
els. In this section, we argue that this is not necessarily the
case, and show that if the lines to switch o
are selected
properly, it is possible to
improve the system robustness and
reduce the congestion simultaneously.
We corroborate this
claim by considering first a small stylized example and then
an IEEE test system.
4.1 Double-Ring Network
Consider the double-ring network in Figure 3(a), which
contains exactly one generator and one load bus. The origi-
nal power flow on this network is also shown in Figure 3(a).
Suppose we switch o
the upper tie-line. The new network
and the redistributed power flow are shown in Figure 3(b).
In this example, by switching o
one transmission line, the
circulating flows inside the hexgons are removed and the
overall network congestion is decreased. In fact, it is easy
to show that the topology in Figure 3(b) minimizes the sum
of (absolute) branch flows over all possible topologies.
4.2 IEEE test system
In the simple example above, removing a line provides
improvements in both robustness and congestion. Now, we
move to the case of a more realistic network, the IEEE 118-
bus test system. In this case, we also see that line removals
can improve robustness without more than minor increase
in congestion.
In our experiments, the system parameters are taken from
the Matpower Simulation Package [29] and we plot the in-
fluence graphs among the transmission lines to demonstrate
how a line failure propagates in this network
1
. More specif-
ically, in the influence graph we plot, two edges
e
and ˆ
e
are
connected if the impact of tripping
e
on ˆ
e
is not negligi-
ble (we use
|
K
e
ˆ
e
|
0
.
005 as a threshold). In Figure 4(a),
we plot the influence graph of the original network. It can
be seen that this influence graph is very dense and connects
many edges that are topologically far away, showing the non-
local propagation of line failures within this network.
Next, we switch o
three edges (indicated as
e
1
,
e
2
and
e
3
in Figure 4(b)) to obtain a new topology that has a
bridge and whose tree partition now consists of two regions
of comparable size. The new influence graph is shown in
1
The original IEEE 118-bus network has some trivial “dan-
gling” bridges that we remove (collapsing their injections
to the nearest bus) to obtain a more transparent influence
graph.
Performance
Evaluation
Review,
Vol.
46,
No.
2, September
2018
59
(a) Original influence graph.
(b) The influence graph after switching o
e
1
,
e
2
and
e
3
.Theblackdashedline
indicates the failure propagation boundary defined by the tree partition.
Figure 4: Influence graphs on the IEEE 118-bus network before and after switching o
lines
e
1
,
e
2
and
e
3
.
Blue edges represent physical transmission lines and grey edges represent connections in the influence graph.
Figure 4(b). One can see that, compared to the original in-
fluence graph in Figure 4(a), the new influence graph is much
less dense and, in particular, there are no edges connecting
transmission lines that belong to di
erent tree partition re-
gions.
It is also of interest to see how the network congestion
is impacted by switching o
these lines. To do so, we col-
lect statistics on the di
erence between the branch flows in
Figure 4(b) and those in 4(a). In Figure 5(a), we plot the
histogram of such branch flow di
erences normalized by the
original branch flow in Figure 4(a). It shows that roughly
half (the exact percentage is 47
.
41%) of the transmission
lines have higher congestion yet the majority of these branch
flow increases are negligible. To more clearly see how much
the congestion becomes worse on these lines, we plot the
cumulative distribution function of the normalized positive
branch flow changes, which is shown in Figure 5(b). One
can see from the figure that 90% of the the branch flows
increase by no more than 10%.
(a)
(b)
Figure 5: (a) Histogram of the normalized branch
flow changes. (b) Cumulative distribution func-
tion of the positive normalized branch flow changes.
Note that the curve intercepts the
y
-axis since
52
.
59%
of the branch flows decrease.
60
Performance
Evaluation
Review,
Vol.
46,
No.
2, September
2018
5. CONCLUSION
This work can be extended in several directions. First, we
provide an analytical characterization of power flow redis-
tribution when a line fails, and our results are generalizable
to bus failures. It is of interest to understand how these
two types of failures interact. Second, we demonstrate in
our case studies that by switching o
certain transmission
lines, grid robustness can potentially be improved. It would
be useful if the selection of such lines can be optimized for
a certain objective function, such as the sparsity of the in-
fluence graph or the total load loss when some critical lines
are tripped. Third, to fully capture the cascading failure
dynamics, both the power flow redistribution and the line
capacities are relevant. It is important to investigate how
line capacities can be incorporated to our framework.
6. REFERENCES
[1] “U.S.-Canada power system outage task force. report
on the August 14, 2003 blackout in the United States
and Canada: Causes and recom- mendation,” 2004.
[2] “Report of the enquiry committee on grid disturbance
in Northern region on 30th July 2012 and in Northern,
Eastern and North-Eastern region on 31st July 2012,”
Aug 2012.
[3] P. D. Hines, I. Dobson, and P. Rezaei, “Cascading
power outages propagate locally in an influence graph
that is not the actual grid topology,”
IEEE TPS
,
vol. 32, no. 2, pp. 958–967, 2017.
[4] I. Dobson, B. A. Carreras, D. E. Newman, and J. M.
Reynolds-Barredo, “Obtaining statistics of cascading
line outages spreading in an electric transmission
network from standard utility data,”
IEEE TPS
,
vol. 31, no. 6, pp. 4831–4841, Nov 2016.
[5] A. Bernstein, D. Bienstock, D. Hay, M. Uzunoglu, and
G. Zussman, “Power grid vulnerability to
geographically correlated failures: Analysis and
control implications,” in
IEEE INFOCOM
,2014,pp.
2634–2642.
[6] S. Soltan, D. Mazauric, and G. Zussman, “Analysis of
failures in power grids,”
IEEE TCNS
,no.99,2015.
[7] J. Chen, J. S. Thorp, and I. Dobson, “Cascading
dynamics and mitigation assessment in power system
disturbances via a hidden failure model,”
International Journal of Electrical Power & Energy
Systems
,vol.27,no.4,pp.318–326,2005.
[8] B. A. Carreras, V. E. Lynch, I. Dobson, and D. E.
Newman, “Critical points and transitions in an
electric power transmission model for cascading failure
blackouts,”
Chaos: An interdisciplinary journal of
nonlinear science
,vol.12,no.4,pp.985–994,2002.
[9] I. Dobson, B. A. Carreras, V. E. Lynch, and D. E.
Newman, “Complex systems analysis of series of
blackouts: cascading failure, critical points, and
self-organization,”
Chaos: An Interdisciplinary
Journal of Nonlinear Science
,vol.17,no.2,p.026103,
2007.
[10]
M. Anghel, K. A. Werley, and A. E. Motter,
“Stochastic model for power grid dynamics,” in
HICSS
.IEEE,2007,pp.113–113.
[11]
J. Yan, Y. Tang, H. He, and Y. Sun, “Cascading
failure analysis with DC power flow model and
transient stability analysis,”
IEEE TPS
,vol.30,no.1,
pp. 285–297, 2015.
[12]
D. P. Nedic, I. Dobson, D. S. Kirschen, B. A.
Carreras, and V. E. Lynch, “Criticality in a cascading
failure blackout model,”
International Journal of
Electrical Power & Energy Systems
,vol.28,no.9,pp.
627–633, 2006.
[13]
J. Song, E. Cotilla-Sanchez, G. Ghanavati, and P. D.
Hines, “Dynamic modeling of cascading failure in
power systems,”
IEEE TPS
,vol.31,no.3,pp.
2085–2095, 2016.
[14]
A. E. Motter and Y.-C. Lai, “Cascade-based attacks
on complex networks,”
Phys Rev E
, Dec. 2002.
[15]
C. D. Brummitt, R. M. DSouza, and E. A. Leicht,
“Suppressing cascades of load in interdependent
networks,”
Proceedings of the National Academy of
Sciences
,vol.109,no.12,pp.E680–E689,2012.
[16]
Z. Kong and E. M. Yeh, “Resilience to
degree-dependent and cascading node failures in
random geometric networks,”
IEEE TIT
,vol.56,
no. 11, pp. 5533–5546, Nov 2010.
[17]
C. L. DeMarco, “A phase transition model for
cascading network failure,”
IEEE Control Systems
,
vol. 21, no. 6, pp. 40–51, Dec 2001.
[18]
I. Dobson, B. A. Carreras, and D. E. Newman, “A
loading-dependent model of probabilistic cascading
failure,”
Probab. Eng. Inf. Sci.
,vol.19,no.1,pp.
15–32, Jan. 2005.
[19]
Z. Wang, A. Scaglione, and R. J. Thomas, “A
markov-transition model for cascading failures in
power grids,” in
HICSS
.IEEE,2012,pp.2115–2124.
[20]
L. Guo and S. H. Low, “Spectral characterization of
controllability and observability for frequency
regulation dynamics,” in
CDC
.IEEE,2017,pp.
6313–6320.
[21]
L. Guo, C. Liang, and S. H. Low, “Monotonicity
properties and spectral characterization of power
redistribution in cascading failures,”
55th Annual
Allerton Conference
,2017.
[22]
L. Guo, C. Zhao, and S. H. Low, “Graph laplacian
spectrum and primary frequency regulation,”
arXiv
preprint arXiv:1803.03905
,2018.
[23]
A. Wood and B. Wollenberg,
Power Generation,
Operation, and Control
. Wiley-Interscience, 1996.
[24]
C. Lai and S. H. Low, “The redistribution of power
flow in cascading failures,” in
51st Annual Allerton
Conference
,Oct2013,pp.1037–1044.
[25]
L. Guo, C. Liang, A. Zocca, S. H. Low, and
A. Wierman, “Failure localization in power systems
via tree partitions,”
arXiv preprint arXiv:1803.08551
.
[26]
D. Bienstock and A. Verma, “The
n
k
problem in
power grids: New models, formulations, and numerical
experiments,”
SIAM Journal on Optimization
,vol.20,
no. 5, pp. 2352–2380, 2010.
[27]
D. Bienstock, “Optimal control of cascading power
grid failures,” in
CDC
, Dec 2011, pp. 2166–2173.
[28]
A. Bernstein, D. Bienstock, D. Hay, M. Uzunoglu, and
G. Zussman, “Power grid vulnerability to
geographically correlated failures 2014: analysis and
control implications,” in
IEEE INFOCOM
, April
2014, pp. 2634–2642.
[29]
R. D. Zimmerman, C. E. Murillo-S ́anchez, and R. J.
Thomas, “Matpower: Steady-state operations,
planning, and analysis tools for power systems
research and education,”
IEEE TPS
,vol.26,no.1,
pp. 12–19, 2011.
Performance
Evaluation
Review,
Vol.
46,
No.
2, September
2018
61