arXiv:2005.10199v3 [eess.SY] 26 May 2020
Localization & Mitigation of Cascading Failures in Power Sy
stems,
Part I: Spectral Representation & Tree Partition
Linqi Guo, Chen Liang, Alessandro Zocca, Steven H. Low, and A
dam Wierman
Abstract
— Cascading failures in power systems propagate
non-locally, making the control of outages extremely diffic
ult.
In this work, we propose a new framework that offers strong
analytical guarantees on both the localization and mitigat
ion
of cascading failures in power systems. The key component of
this framework leverages the concept of
tree partition
, which
characterizes regions of a power network inside which line
failures are automatically localized. In Part I of this pape
r
we establish a mathematical theory that underlies all the
performance guarantees of tree partition as well as its fail
ure
localization properties. This theory consists of a set of to
ols
developed using the Laplacian matrix of the transmission ne
t-
work and reveals a novel perspective that precisely capture
s the
Kirchhoff’s Law in terms of topological structures. Our res
ults
show that the distribution of different families of subtree
s of
the transmission network plays a critical role on the patter
ns
of power redistribution, and motivates tree partitioning o
f the
network as a strategy to eliminate long-distance propagati
on of
disturbances. These results are used in Parts II and III of th
is
paper to design strategies to localize and mitigate line fai
lures.
I. I
NTRODUCTION
Cascading failures in power systems propagate non-
locally, making their analysis and mitigation difficult. Th
is
fact is illustrated by the sequence of events leading to the
1996 Western US blackout (as summarized in Fig. 1 from
[1], [2]), in which successive failures happened hundreds o
f
kilometers away from each other (e.g. from stage
3
to stage
4
and from stage
7
to stage
8
). Non-local propagation
makes it challenging to design distributed controllers tha
t
reliably prevent and mitigate cascades in power systems. In
fact, such control is often considered impossible, even whe
n
centralized coordination is available [3], [4].
Current industry practice for mitigating cascading fail-
ures mostly relies on simulation-based contingency analys
is,
which focuses on a small set of most likely initial failures
[5]. Moreover, the size of the contingency set which is teste
d
(and thus the level of security guarantee) is often constrai
ned
by computational power, undermining its effectiveness in
view of the enormous number of components in power
networks. After a blackout event, a detailed study typicall
y
leads to a redesign of such contingency sets, potentially
together with physical network upgrades and revision of
system management policies and regulations [4].
The limitations of the current practice have motivated a
large body of research on cascading failure; see e.g. [6]
for a recent review with extensive references. In particula
r,
This work has been supported by Resnick Fellowship, Linde In
stitute
Research Award, NWO Rubicon grant 680.50.1529, NSF through
grants
CCF 1637598, ECCS 1619352, ECCS 1931662, CNS 1545096, CNS
1518941, CPS ECCS 1739355, CPS 154471.
LG, CL, SHL, AW are with the Department of Computing and Mathe
-
matical Sciences, California Institute of Technology, Pas
adena, CA, 91125,
USA. Email:
{
lguo, cliang2, slow, adamw
}
@caltech.edu
.
AZ is with the Department of Mathematics of the Vrije Univers
iteit
Amsterdam, 1081HV, The Netherlands. Email:
a.zocca@vu.nl
.
Fig. 1: The sequence of events, indexed by the circled number
s, that lead
to the Western US blackout in 1996 from [1], [2].
the literature on analytical properties of cascading failu
re
can be roughly categorized as follows: (a) applying Monte-
Carlo methods to analytical models that account for the
steady state power redistribution using DC [7]–[10] or AC
[11]–[13] power flow models; (b) studying pure topological
models built upon simplifying assumptions on the propa-
gation dynamics (e.g., failures propagate to adjacent line
s
with high probability) and inferring component failure pro
p-
agation patterns from graph-theoretic properties [14]–[1
6];
(c) investigating simplified or statistical cascading fail
ure
dynamics [2], [17]–[19].
In all these approaches, it is often difficult to make general
inferences about failure patterns. For example, power flow
over a specific transmission line can increase, decrease and
even reverse direction as cascading failure unfolds [20]. T
he
failure of a line can cause another line that is arbitrarily
far away to trip [21]. Load shedding instead of mitigating a
cascading failure, can actually increase the congestion on
certain lines [22]. This lack of structural properties is a
key challenge in the modeling, control, and mitigation of
cascading failures in power systems.
In this work, we take a different approach that leverages
the spectral representation of transmission network topol
ogy
to establish several structural properties. The spectral v
iew
is powerful as it reveals surprisingly simple characteriza
tions
of complex system behaviors, e.g., on controllability and
observability of power system dynamics [23], on dynamic
properties of frequency control [24], [25], and on mono-
tonicity properties and power flow redistribution [26]. In
the context of cascading failures, our spectral approach [2
6]
motivates the use of the network
tree partition
to eliminate
long-distance propagation of disturbances, and allows us t
o
develop a new control framework that offers strong analytic
al
guarantees in both the mitigation and localization of casca
d-
ing failures.
Contributions of Part I of this paper:
We establish a
mathematical theory that underlies the performance guar-
antees of the tree partition of a transmission network and
the failure localization properties that tree partitions b
ring
to the proposed control framework.
This theory starts from
the Laplacian matrix of a transmission network and unveils
a close connection between power redistribution patterns
and the distribution of different families of (sub)trees of
the power network topology. This connection uncovers new
topological structures of several important and well-stud
ied
quantities in power system contingency analysis, such as
the generation shift sensitivity factor and the line outage
redistribution factor. Further, in contrast to pure graphi
cal
models such as those in [14], [15], [27], such topological
interpretations capture Kirchhoff’s Law in a precise way an
d
do not rely on any assumptions or simplifications on the
failure propagation dynamics.
The key result that relates the power redistribution to
graphical structures is given in Proposition 4, which state
s
that the distribution of different families of subtrees of
the transmission network fully determines the system state
under a given set of injections. In Section III, we establish
a new set of graphical representations of generation shift
sensitivity factors and line outage distribution factors i
n
contingency analysis. This novel graph-theoretical viewp
oint
enables us to derive precise algebraic properties of power
redistribution using purely graphical arguments, and show
s
that disturbances propagate through “subtrees” in a power
network. Using this framework, in Section III-E we derive
the
Simple Loop Criterion
that fully determines whether the
failure of one line can impact another line in a given network
topology.
In order to prove these results, we exploit the celebrated
Kirchhoff Matrix Tree Theorem as well as its generalization
known as the All Minors Matrix Tree Theorem. Further, we
make use of some novel properties of the Laplacian matrix
derived in the context of DC power flow and characterize
certain quantities of interest by different families of spa
nning
forests in the transmission network.
Our graphical interpretation of power redistribution natu
-
rally suggests that we can eliminate long-distance propaga
-
tion of system disturbances by refining the (possibly trivia
l)
tree partition of a transmission network. In Section IV, we
formally define the notion tree partition and show that the
“finest” tree partition of a general graph is unique and can
be computed in linear time. In Section V, we demonstrate
how tree partitioning localizes the impacts of a line failur
e
to the region of the network where the failure happens. The
rigorous proof of such localization properties and how they
can be leveraged to provide analytical guarantees for failu
re
mitigation are presented in Part II and Part III of this paper
,
respectively.
II. P
RELIMINARIES
In this section, we present the DC power flow model,
explain its network Laplacian matrix, and introduce some of
its basic properties that will be used throughout this paper
.
A. Power network and DC power flow
We describe a transmission network using a graph
G
=
(
N
,
E
)
, whose node set
N
=
{
1
, . . . , n
}
models the
n
=
|N|
buses and whose edge set
E ⊆ N × N
models the
m
=
|E|
transmission lines. We without loss of generality
assume the graph is simple and use the terms bus/node and
line/edge are used interchangeably. An edge in
E
between
node
i
and
j
is denoted either as
e
or
(
i, j
)
. We assign
an arbitrary orientation over
E
so that if
(
i, j
)
∈ E
then
(
j, i
)
/
∈ E
. The line susceptance (weighted by nodal voltage
magnitudes [28]) of line
e
= (
i, j
)
is denoted as
B
e
=
B
ij
and the susceptance matrix is the
m
×
m
diagonal matrix
B
:= diag(
B
e
:
e
∈ E
)
. Let
f
be the
m
-dimensional vector
consisting of all branch flows, with
f
e
denoting the branch
flow on line
e
. The node-edge incidence matrix of
G
is the
n
×
m
matrix
C
defined as
C
ie
=
1
if node
i
is the source of
e,
−
1
if node
i
is the target of
e,
0
otherwise.
We introduce the
n
-dimensional vectors
p
and
θ
, where
p
i
and
θ
i
are the power injection and voltage phase angle at
bus
i
, respectively. With the above notation, the DC power
flow model can be written as
p
=
Cf
(1a)
f
=
BC
T
θ,
(1b)
where (1a) is the flow conservation (Kirchhoff’s) law and
(1b) is the Ohm’s laws. Given an injection vector
p
that is
balanced over the network
P
j
∈N
p
j
= 0
, the DC model (1)
has a solution
(
θ, f
)
where
θ
is unique up to an arbitrary
reference angle. Without loss of generality, we choose node
n
as a reference node and set
θ
n
= 0
. With this convention,
the solution
(
θ, f
)
is unique.
When a line
e
is tripped, the power redistributes according
to the DC model (1) on the newly formed graph
G
′
:=
(
N
,
E\ {
e
}
)
. If
G
′
is still connected, then the flow change
on a line
ˆ
e
with the same power injection
p
can be given in
terms of the
line outage distribution factor
K
ˆ
ee
from
e
to
ˆ
e
as
∆
f
ˆ
e
=
K
ˆ
ee
f
e
.
It is known that these distribution factors depend solely on
the network topology, in the sense that they are independent
of the power injections
p
and can be computed directly from
the matrices
B
and
C
[29]. In Section III-D, we derive a new
formula for
K
ˆ
ee
that precisely captures how the Kirchhoff’s
law redistributes branch flows along subtrees of
G
and that is
the foundation for our results on the localization properti
es
of network tree partitions.
B. Laplacian matrix
The DC power flow equations (1) imply that
p
=
CBC
T
θ.
In other words, the phase angles
θ
are determined from the
power injection
p
via the matrix
CBC
T
. This matrix, which
we denote as
L
=
CBC
T
, is known as the Laplacian matrix
of
G
and plays a central role in our analysis. Since for any
v
∈
R
n
we have that
v
T
Lv
=
X
(
i,j
)
∈E
B
ij
(
v
i
−
v
j
)
2
≥
0
,
(2)
the matrix
L
is positive semidefinite. Moreover, equality is
attained in (2) if and only if
v
i
=
v
j
for every
(
i, j
)
∈ E
.
Fig. 2: An example element in
T
(
N
1
,
N
2
)
, where circles correspond to
elements in
N
1
and squares correspond to elements in
N
2
. The two trees
containing
N
1
and
N
2
are highlighted as solid lines.
Thus the Laplacian matrix
L
is singular and the eigenspace
of
L
corresponding to
0
, i.e., the kernel of
L
, consists of
vectors that take the same value on each of the connected
components of
G
. The following well-known result summa-
rizes a special case.
Lemma 1.
If the graph
G
is connected, then the kernel of
L
is
span (
1
)
, the set of vectors with uniform entries.
This result implies that the Laplacian matrix
L
of a
connected graph has rank
n
−
1
and, hence, contains an
invertible submatrix of size
(
n
−
1)
×
(
n
−
1)
. Consider
the submatrix
L
obtained from
L
deleting the last row and
the last column (i.e., those corresponding to the reference
node
n
). The Kirchhoff’s Matrix Tree Theorem (stated below,
see [30] for more details) relates the determinant of
L
to a
weighted sum of spanning trees of
G
.
Proposition 2.
If the graph
G
is connected, the determinant
of
L
is given by
det(
L
) =
X
E
∈T
E
Y
e
∈
E
B
e
,
where
T
E
is the set of all spanning trees of
G
.
This result implies, in particular, that
L
is invertible since
the set of spanning trees
T
E
is non-empty for a connected
graph and
B
e
>
0
for all
e
. Define the
n
×
n
matrix
A
as
follows:
A
=