arXiv:2005.11320v2 [eess.SY] 26 May 2020
1
Localization & Mitigation of Cascading Failures in Power Sy
stems,
Part II: Localization
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 and mitigation of outages
hard. In Part II of this paper, we continue the study of
tree partitioning of transmission networks and characteri
ze
analytically line failure localizability. We show that a tr
ee-
partition region can be further decomposed into disjoint ce
lls in
which line failures will be contained. When a non-cut set of l
ines
are tripped simultaneously, its impact is localized within
each
cell that contains a line outage. In contrast, when a bridge l
ine
that connects two tree-partition regions is tripped, its im
pact
propagates globally across the network, affecting the powe
r
flows on all remaining lines. This characterization suggest
s
that it is possible to improve system reliability by switchi
ng
off certain transmission lines to create more, smaller cell
s,
thus localizing line failures and reducing the risk of large
-
scale outages. We demonstrate using the IEEE 118-bus test
system that switching off a negligible portion of lines allo
ws
the impact of line failures to be significantly more localize
d
without substantial changes in line congestion.
I. I
NTRODUCTION
In Part I of this paper [1], we establish the spectral
representation of power redistribution that precisely cap
tures
the Kirchhoff’s Laws in terms of the distribution of differ-
ent families of subtrees in the transmission network. This
new representation motivates a novel approach to localize
cascading failures in power systems.
Contributions of Part II of this paper:
We prove that tree
partitioning proposed in Part I provides a precise analytic
al
characterization of line failure localizability, and we sh
ow
how to use this characterization to mitigate failure cascad
-
ing by switching off a small number of carefully chosen
transmission lines and creating in this way a finer network
tree partition.
Our results not only rigorously establish the
intuition of the community that failures cannot cross bridg
es,
but also reveal a less intuitive finer-grained concept, call
ed
cells (defined by partitioning the network using its cut
vertices, see Section IV) inside each tree-partition regio
n,
that encodes more precise information on failure propagati
on.
In particular, we prove that: (a) a non-cut failure in a cell
will only impact power flows on transmission lines within
that cell, regardless of whether the failure involves a sing
le
line or multiple lines
simultaneously
; and conversely (b) a
non-cut failure in a cell will almost surely impact flows on
every
remaining line within that cell. This is not intuitive
to our best knowledge. Our results also demonstrate how
the impact of cut failures propagate globally in a way that
depends on the design of balancing rules and a network’s
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
.
topological structure. This work builds on the recent work o
n
the line outage distribution factor, e.g., [2], [3], and sho
ws
that tree partitioning is a particularly useful representa
tion
of this factor, one that captures many aspects of how line
failures can cascade.
The formal characterization of localizability in the case
of a single line failure is given in Theorem 2 of Section
III, which summarizes the technical results in Sections IV
and V. In particular, in Section IV, we characterize power
redistribution after the tripping of a single non-bridge li
ne
and show that the impact of such a failure only propagates
within its own cell. In Section V, we consider the failure of
a single bridge line and prove that such a failure propagates
globally across the network and impacts the power flows on
all transmission lines.
In Section VI, we extend Theorem 2 to the case of multiple
simultaneous line failures, and show that the aggregate
impact of such failure consists of two parts: (a) a part from
power redistribution that generalizes the case of a single
non-bridge failure, and such impact can be decomposed in
accordance to the cells where the failures occur; (b) a part
from power balancing rule that generalizes the case of a
single bridge failure and captures how the system handles
disconnected components. These results rely on properties
of
tree partitioning proved in Part I [1]. In particular, we mak
e
use of the block decomposition of tree-partition regions to
completely eliminate simple loops containing edges among
distinct cells. The Simple Loop Criterion in Part I [1] then
guarantees failure localization. Lastly, we apply classic
al
techniques from algebraic geometry to address potential
pathological system specifications for our converse result
s.
The characterizations we provide in Theorem 2 and Sec-
tion VI suggest a new approach for mitigating the impact
of cascading failures by switching off certain transmissio
n
lines to create smaller regions/cells. This better localiz
es
line failures and reduces the risk of large-scale blackouts
.
In Section VII, we illustrate this approach using the IEEE
118-bus test network. We demonstrate that switching off
only a negligible portion of transmission lines can lead to
significantly better control of cascading failures, and mor
e
importantly, without significant increase in line congesti
on
across the grid.
Finally we remark that tree partitioning can be useful for
planning applications. It can also be used as an emergency
measure the same way controlled islanding (see e.g. [4]–[12
])
is used to prevent large-scale blackouts
1
. For instance, tree
partitions can be pre-computed offline for different contin
-
gencies and loading conditions, and implemented as soon as
a contingency is detected using special protection schemes
.
It would be interesting to understand the tradeoffs of post-
contingency corrective tree partitioning and controlled i
s-
landing and how they can be synergistically integrated for
1
We thank Janusz Bialek for suggesting this as a potential app
lication.
2
failure mitigation. In this paper, we focus on proving gener
al
failure localization properties of tree partitioning and l
eave
its application for failure mitigation and network plannin
g
for future work.
II. P
RELIMINARIES
In this section, we present the cascading failure model that
our main technical results build upon. This model extends th
e
DC power flow model presented in Part I to multiple stages,
and is a special case of the integrated failure propagation
model that we introduce in Part III.
Given a power network, we describe the cascading failure
process by keeping track of the set of failed lines at differe
nt
stages indexed by
N
:=
{
1
,
2
,
· · ·
, N
}
. Each stage
n
∈
N
corresponds to a graph
G
(
n
) := (
N
,
E\B
(
n
))
, where
B
(
n
)
is
the set of all tripped lines at stage
n
and is naturally nested:
B
(
n
)
⊂ B
(
n
+ 1)
,
∀
n
∈
N
.
Within each stage
n
, the power flow redistributes over the
network described by
G
(
n
)
according to the DC power
flow model (see Part I for more details). If all the branch
flows are below the corresponding line ratings, then the new
operating point is secure and the cascade stops. Otherwise,
let
F
(
n
)
be the subset of lines whose branch flows exceed
the corresponding line ratings. The lines in
F
(
n
)
are tripped
in stage
n
, i.e.,
B
(
n
+1) =
B
(
n
)
∪F
(
n
)
. This process repeats
for stage
n
+ 1
and so on.
Next, we focus on a fixed stage
n
∈
N
, and describe how
a single line failure impacts the branch flows on remaining
lines. To simplify the notation, we drop the stage index from
symbols such as
G
(
n
)
and simply write them as
G
. Recall that
when a line
e
is tripped from
G
, if the newly formed graph
G
′
:= (
N
,
E\ {
e
}
)
is still connected, then the branch flow
change on a line
ˆ
e
with the same power injections
p
is given
by
∆
f
ˆ
e
=
K
ˆ
ee
f
e
,
where
K
ˆ
ee
is the line outage distribution
factor (LODF) [13] from
e
to
ˆ
e
. In Part I of this paper,
by studying the transmission network Laplacian matrix, we
derive a new formula for
K
ˆ
ee
that precisely captures the
Kirchhoff’s Laws in terms of graphical structures. The new
formula is replicated here for reference:
Theorem 1.
Let
e
= (
i, j
)
,
ˆ
e
= (
w, z
)
∈ E
be edges such
that
G
′
= (
N
,
E\ {
e
}
)
is connected. Then,
K
ˆ
ee
is given by
B
ˆ
e
×
P
E
∈T
(
{
i,w
}
,
{
j,z
}
)
χ
(
E
)
−
P
E
∈T
(
{
i,z
}
,
{
j,w
}
)
χ
(
E
)
P
E
∈T
E\{
(
i,j
)
}
χ
(
E
)
.
Theorem 1 allows us to check algebraic properties of
K
ˆ
ee
by examining the network topology
G
. Recall
K
ˆ
ee
6
= 0
means that the failure of
e
can potentially lead to the failure
of
ˆ
e
. In Part I, we proved a
Simple Loop Criterion
:
K
ˆ
ee
6
= 0
“if” and only if there exists a simple loop containing both
e
and
ˆ
e
in
G
. In particular, for two edges
e
and
ˆ
e
such that
e
is not a bridge, if there is no simple loop containing both
e
and
ˆ
e
, then
K
ˆ
ee
= 0
.
If the post-contingency graph
G
′
is disconnected, then it is
possible that the original injections
p
are no longer balanced
in some connected components of
G
′
. Thus, to compute the
new power flows, a power balancing rule
R
needs to be
applied. Several such rules have been proposed and evaluate
d
in the literature based on load shedding or generator respon
se
[2], [14]–[17]. In this work, we do not specialize to any such
rule but, instead, we identify key properties of these rules
that guarantee our results to hold. For this reason, our more
Fig. 1. Non-zero entries of the
K
ˆ
ee
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 inside
N
1
and
N
2
represent cells inside those regions.
abstract approach allows us to characterize the power flow
redistribution under a broad class of power balancing rules
.
III. S
INGLE
L
INE
F
AILURE
In this section we state our main analytical result in the
case of a single-line failure. This is the critical building
block for characterizing the case of multi-line failures, t
o
be presented in Section VI.
Our result applies to scenarios in which the system is
operating under
normal
conditions, i.e., when the following
two assumptions are satisfied: (a) the injections are
island-
free
(see Definition 7); and (b) the grid is
participating
with
respect to its power balancing rule (see Definition 9). More-
over, to avoid pathological cases, we add a small perturbati
on
to the line susceptances drawn from a probability measure
μ
,
which we assume to be absolutely continuous with respect
to the Lebesgue measure
L
m
on
R
m
(see Section V).
Theorem 2.
For a power network operating under normal
conditions,
K
ˆ
ee
6
= 0
“if” and only if:
1)
e,
ˆ
e
are within the same tree-partition region and
e,
ˆ
e
belong to the same cell; or
2)
e
is a bridge.
The “if” part should be interpreted as an almost sure event
in
μ
(see Definition 6). The conditions stated in Theorem 2
are far from being restrictive, but satisfied in most practic
al
settings. More specifically, we emphasize that: (a)
μ
being
absolutely continuous with respect to
L
m
holds in almost
all relevant stochastic models for such perturbations (see
Section IV); and (b) the conditions that the injections are
island-free and the grid is participating are satisfied in ty
pical
operating scenarios of power systems (see Section V). This
result implies that, for essentially all networks of intere
st, the
tree partition encodes rich information on how the failure o
f
a line propagates through the network.
The findings of Theorem 2 are visualized in Fig. 1, where
it becomes clear how the tree partition is linked to the
sparsity of the
K
ˆ
ee
matrix. It suggests that for a fully meshed
transmission network with a trivial tree partition consist
ing of
a single region/cell, it can be beneficial to switch off certa
in
lines so that more tree-partition regions or cells are creat
ed,
localizing in this way the line failure within the region/ce
ll in
which it occurs. We study this network planning and design
opportunity in Section VII.
The next two sections are devoted to the proof of Theorem
2. We first characterize power redistribution after the trip
ping
3
(a)
(b)
Fig. 2. (a) A butterfly network. (b) The block decomposition o
f the butterfly
network into cells
C
1
and
C
2
.
of a single non-bridge line in Section IV, and then consider
in Section V the failure of a single bridge. In Section VI,
we generalize our single-line failure characterization to
the
case of multi-line failures.
IV. N
ON
-B
RIDGE
F
AILURES ARE
L
OCALIZABLE
In this section, we show that the impacts of a single non-
bridge line failure are localized within a tree-partition r
egion.
Recall from Proposition 10 in Part I that
K
ˆ
ee
is a precise
indicator on whether the failure
e
can potentially lead to the
successive failure of line
ˆ
e
.
A. Impact across Regions
We consider first the case where
ˆ
e
does not belong to the
same region as
e
, that is,
ˆ
e
either belongs to a different region
or
ˆ
e
is a bridge.
Proposition 3.
Consider a power network
G
with a tree
partition
P
=
{N
1
,
N
2
,
· · ·
,
N
k
}
. Let
e,
ˆ
e
∈ E
be two
different edges such that
e
is not a bridge. Then
K
ˆ
ee
= 0
for any
ˆ
e
that is not in the same region containing
e
.
See Appendix I for a proof. This result implies that,
when a non-bridge line
e
fails, any line
ˆ
e
not in the same
tree-partition region as
e
will not be affected, regardless of
whether
ˆ
e
is a bridge. In other words, non-bridge failures
cannot propagate through the boundaries formed by the tree-
partition regions of
G
.
B. Impact within Regions
It is reasonable to expect that the converse to the above
result is also true. That is, if
e,
ˆ
e
belong to the same region
(and thus
e
is not a bridge), we would expect
K
ˆ
ee
6
= 0
. This,
however, might not always be the case for two reasons: 1)
some nodes within a tree-partition region may “block” simpl
e
loops containing both
e
and
ˆ
e
; 2) the graph
G
may be too
symmetric. We elaborate on these two scenarios separately
in the following two subsections.
1) Block Decomposition:
The following example illus-
trates the situation in which nodes inside a tree-partition
region may “block” simple loops containing both
e
and
ˆ
e
.
Example 1.
Consider the butterfly network shown in
Fig. 2(a) and pick
e
= (
i, j
)
and
ˆ
e
= (
w, z
)
. It is not hard
to see that any loop containing
e
and
ˆ
e
must pass through
the central node
c
at least twice and hence is never simple.
The Simple Loop Criterion (Theorem 11 in
[1]
) immediately
yields that
K
ˆ
ee
= 0
.
The underlying issue in this example is that the butterfly
network is not 2-connected, which means that the removal of
a single node (in this case the central node
c
) can disconnect
the original graph. Network nodes with such a property are
referred to as
cut vertices
in graph theory. As in Example 1,
cut vertices prevent the existence of global simple loops.
Fortunately, we can precisely capture such an effect by
decomposing each tree-partition region further through th
e
classical
block decomposition
[18]. Recall that the block
decomposition of a graph is a partition of its edge set
E
such that each partitioned component is 2-connected, see
Fig. 2(b) for an illustration. The block decomposition of a
graph always exists and can be found in linear time [19].
We refer to the components of this decomposition as
cells
to reflect the fact that they are smaller parts within a tree-
partition region. Note that two different cells within the s
ame
tree-partition region may share a common vertex, since the
block decomposition induces a partition only of the network
edges.
Lemma 4.
If
e,
ˆ
e
are two distinct edges within the same tree-
partition region that belong to different cells, then
K
ˆ
ee
= 0
.
Proof.
Let
C
e
and
C
ˆ
e
be the two cells to which
e
and
ˆ
e
respectively belong. It is a well-known result that any path
from a node in
C
e
to a node in
C
ˆ
e
must pass through a
common cut vertex in
C
e
or
C
ˆ
e
[18]. It is then impossible
to find a simple loop containing both
e
and
ˆ
e
and, thus, the
Simple Loop Criterion implies that
K
ˆ
ee
= 0
.
2) Symmetry:
Next, we show how graph symmetries
(more specifically, graph automorphisms) may also block the
propagation of failures. We first illustrate the issue by mea
ns
of an example.
Example 2.
Consider the power network
G
consisting of the
complete graph on
n
vertices (
n
≥
4
) and line susceptances
all equal to
1
. Pick two edges
e
= (
i, j
)
and
ˆ
e
= (
w, z
)
that do not share any common endpoints. By symmetry, it is
easy to see that there is a bijective correspondence between
T
(
{
i, w
}
,
{
j, z
}
)
and
T
(
{
i, z
}
,
{
j, w
}
)
, and thus
X
E
∈T
(
{
i,w
}
,
{
j,z
}
)
χ
(
E
)
−
X
E
∈T
(
{
i,z
}
,
{
j,w
}
)
χ
(
E
) = 0
.
By Theorem 1, we then have
K
ˆ
ee
= 0
.
A complete graph is 2-connected and thus consists of a
single cell. Example 2 shows that even if two edges
e,
ˆ
e
are
within the same cell, when the graph
G
is rich in symmetry,
it is still possible that a failure of line
e
does not impact
another line
ˆ
e
. Nevertheless, this issue is not critical as such a
symmetry almost never happens in practical systems, becaus
e
of heterogeneity in line susceptances. In fact, even if the
power network topology is highly symmetric, an infinitesima
l
change on the line susceptances is enough to break the
symmetry, as we now show.
More specifically, we take the line susceptances to be
average values
B
e
plus random perturbations
ω
= (
ω
e
:
e
∈
E
)
drawn from a probability measure
μ
. Such perturbations
can come from manufacturing error or measurement noise.
The perturbed system
2
shares the same topology (and thus
tree partition) as the original system, yet admits perturbe
d
susceptances
B
+
ω
. The randomness of
ω
implies the factors
K
ˆ
ee
are now random variables. Recall that we assume
μ
to
be
absolutely continuous
with respect to Lebesgue measure
L
m
on
R
m
, which means that for any measurable set
S
such
that
L
m
(
S
) = 0
, we have
μ
(
S
) = 0
.
2
We assume the perturbation ensures
B
e
+
ω
e
>
0
for any
e
∈ E
so
that the new susceptance is physically meaningful.
4
Proposition 5.
Consider a power network
G
with suscep-
tance perturbation
μ
and let
e,
ˆ
e
be two distinct edges within
the same cell. If
μ
is absolutely continuous with respect to
L
m
, then
K
ˆ
ee
6
= 0
μ
-almost surely, i.e.,
μ
(
K
ˆ
ee
6
= 0) = 1
.
See Appendix II for a proof. Note that, by the Radon-
Nikodym Theorem [20], the probability measure
μ
is abso-
lutely continuous with respect to
L
m
if and only if it affords
a probability density function. This essentially amounts t
o
requiring the measure
μ
to not contain Dirac masses. As a
result, we see that for almost all relevant stochastic model
s
on such perturbations (e.g., truncated Gaussian noise with
arbitrary covariance, bounded uniform distribution, trun
cated
Laplace distribution), the assumption applies and, thus,
K
ˆ
ee
6
= 0
for
e,
ˆ
e
within the same cell almost surely, no
matter how small the perturbation is.
3
This perturbation approach is also useful for our results
in the following sections. When we take this approach,
our result often constitutes two directions: (a) an “only if
”
direction that should be interpreted as normal; and (b) an
“if” direction that holds almost surely in
μ
. To simplify
the presentation, we henceforth fix an absolutely continuou
s
perturbation
μ
with respect to
L
m
, and define the following:
Definition 6.
For two predicates
p
and
q
, we say that
p
“if”
and only if
q
when both of the following hold:
p
⇒
q,
q
⇒
μ
(
p
) = 1
.
We say the “if” is in
μ
-sense when we need to emphasize
that the “if” direction only holds almost surely in
μ
.
Proposition 3, Lemma 4, and Proposition 5 prove the first
half of Theorem 2.
V. B
RIDGE
F
AILURES
P
ROPAGATE
The remaining case necessary to prove Theorem 2 is a
characterization of power flow redistribution when a single
bridge is tripped. Here, we show that such failures generall
y
propagate through the entire network.
A. Extended
K
ˆ
ee
and Island-free Operation
When
e
is a bridge, tripping
e
disconnects the power
grid into two islands, and the power in each connected
component may not be balanced. Such power imbalance can
be resolved by a power balancing rule
R
(see [14]–[17] for
examples of such rules), which together with the DC model
uniquely determines the post-contingency branch flows (and
thus the branch flow changes
∆
f
ˆ
e
). For the purpose of
unified notation, we extend the definition of
K
ˆ
ee
through
K
ˆ
ee
:= ∆
f
ˆ
e
/f
e
to the case where
e
is a bridge. Besides
being related to the
B
and
C
matrices, this extended
K
ˆ
ee
factor also depends on the power injections
p
and the power
balance rule
R
. It is only meaningful if
f
e
6
= 0
, which is not
a restriction since when
f
e
= 0
we clearly have
∆
f
ˆ
e
= 0
for all remaining lines.
Definition 7.
For a power network
G
, an injection vector
p
is said to be
island-free
if the resulting branch flow
f
satisfies
f
e
6
= 0
for every bridge
e
.
Intuitively, island-free means that no part of the grid is
self-balanced. That is, the aggregate power injection over
each of the tree-partition regions is non-zero and hence the
re
3
Our results can be readily extended to the case when
μ
contains Dirac
masses. See Appendix X for more discussion.
must be power exchanges among the regions. For an island-
free grid, every bridge carries nonzero branch flow and thus
the extended
K
ˆ
ee
factors are always well-defined.
B. Participating Buses
Suppose a bridge
e
of a power network
G
is tripped and
separates the network into two islands. Consider one of thes
e
islands
D
:= (
N
D
,
E
D
)
and let
u
be the endpoint of
e
that
belongs to
D
. Note
D
may contain multiple tree-partition
regions of the original network. Tripping
e
from the grid
leads to a power imbalance
f
e
(with a sign determined by
the original flow direction on
e
) and the balancing rule
R
distributes such imbalance to a set of
participating
buses
from
D
so that the total power imbalance
f
e
is canceled out.
The rules studied in the literature, e.g., [2], [14]–[17], a
re
typically
linear
in the sense that, for any participating bus
j
,
the injection adjustment dictated by the rule
R
is linear in
f
e
. Given a rule
R
, denote by
N
R
the set of participating
buses in
D
and let
n
r
=
|N
R
|
. The rule
R
can then be
interpreted as a linear transformation from
R
to
R
n
r
given
by
R
(
f
e
) := (
α
j
f
e
:
j
∈ N
R
)
, where
α
j
>
0
,
P
j
α
j
= 1
,
and
f
e
is the total power imbalance in
D
after the bridge
e
failure. Note that
f
e
could be both positive or negative,
depending on whether the island has an excess or a shortfall
of power.
Different rules correspond to different choices of par-
ticipating buses and coefficients
α
j
’s. For instance, if the
generators in
D
are uniformly adjusted to compensate the
imbalance [2], [14], then
N
R
coincides with the set of
generators in
D
and
α
j
= 1
/
|N
R
|
. As another example,
if the imbalance is regulated through Automatic Generation
Control (AGC), then
N
R
is the set of controllable generators
and
α
j
are the normalized generator
participation factors
.
Denote the injection adjustment vector over all buses in
D
(that results from tripping
e
and the power balancing by
R
) by
∆
p
D
. Let
u
be the endpoint of
e
in
D
and denote by
C
D
,
L
D
the incidence and Laplacian matrix of the island
D
,
respectively. Put
B
D
to be the sub-matrix of
B
corresponding
to edges in
D
and let
A
D
be the extended inverse of
L
D
(see
Part I for more details). Then the branch flow changes on the
remaining lines in
D
are given by
∆
f
D
=
B
D
C
T
D
A
D
∆
p
D
.
We now determine when
(∆
f
D
)
ˆ
e
= 0
for a remaining line
ˆ
e
∈ E
D
, which in turn characterizes whether the extended
K
ˆ
ee
is zero or not.
Proposition 8.
For
ˆ
e
∈ E
D
, we have
∆
f
ˆ
e
6
= 0
“if” and only
if there exists
j
∈ N
R
such that there is a simple path in
D
from
u
to
j
containing
ˆ
e
.
The “if” part in this result is in
μ
-sense as discussed in
Section IV. See Appendix III for a proof.
Proposition 8 shows that the positions of participating
buses in
D
play an important role in distributing the power
imbalance across the network. In particular, the power bal-
ancing rule
R
changes the branch flow on every edge that lies
in a path from the failure point
u
to the set of participating
buses. As a result, if
ˆ
e
is a bridge connecting two tree-
partition regions
D
1
and
D
2
in
D
, assuming
u
∈ D
1
, then
∆
f
ˆ
e
6
= 0
“if” and only if
D
2
contains a participating bus
(since a path from
u
to any node in
D
2
must pass through
ˆ
e
). If
ˆ
e
is not a bridge, then we can devise a simple sufficient
5
condition for
∆
f
ˆ
e
6
= 0
using
participating regions
, defined
as follows:
Definition 9.
Consider a power network
G
with tree partition
P
=
{N
1
,
N
2
,
· · ·
,
N
k
}
operating under power balancing
rule
R
with a set
N
R
of participating buses. A region
N
i
with block decomposition
C
i
1
,
C
i
2
,
· · ·
,
C
i
m
i
is said to be a
participating region
if
N
R
∩ C
i
j
contains a non-cut vertex
for
j
= 1
,
2
, . . . , m
i
.
G
is said to be a
participating grid
if
N
i
is participating for
i
= 1
,
2
, . . . , k
.
If a power network does not contain single-point vulnera-
bilities such as cut vertices within each tree-partition re
gion,
then the tree-partition regions are identical with cells. I
n this
case, a region is participating if it contains at least one bu
s
that participates in power balancing and is not the endpoint
of
a bridge, which is often the case. As such, it is reasonable to
assume most tree-partition regions are participating regi
ons
and hence most power grids are participating.
The following result shows that a region being partici-
pating implies all edges in this region are impacted when
the original bridge
e
is tripped (its proof is presented in
Appendix IV).
Lemma 10.
If
N
i
is a participating region and
f
e
6
= 0
, then
∆
f
ˆ
e
6
= 0
μ
-almost surely for any
ˆ
e
∈ N
i
, i.e.,
μ
(∆
f
ˆ
e
6
=
0) = 1
.
Given the above, we now state our main result for bridge
failures.
Proposition 11.
Consider a participating grid
G
with island-
free injections
p
. If
e
is a bridge of
G
, then for any
ˆ
e
6
=
e
,
K
ˆ
ee
6
= 0
μ
-almost surely, i.e.,
μ
(
K
ˆ
ee
6
= 0) = 1
.
This proposition proves the second part of Theorem 2.
VI. M
ULTI
-
LINE
F
AILURES
In this section, we generalize our results in Sections IV and
V to the case of multi-line failures. That is, we characteriz
e
the branch flow changes on remaining lines after a set
E
of
lines are simultaneously removed from service.
Similar to a single-line outage, the impact of tripping a set
E
of lines propagates differently depending on whether the
post-contingency graph
G
′
:= (
N
,
E\
E
)
remains connected.
Definition 12.
A subset of edges
E
⊂ E
is said to be a
cut
set
if the graph
G
′
after removing
E
is not connected, or a
non-cut set
if it is not a cut set.
A. Non-cut Failure
In this subsection, we focus on the case where
E
is a non-
cut set. Partition the column vector
f
= [
f
E
;
f
−
E
]
, where
f
E
and
f
−
E
are the pre-contingency power flows in
E
and
in
E\
E
respectively. Let
ˆ
f
−
E
be the post-contingency line
flows in
E\
E
and
ˆ
θ
be the post-contingency phase angles.
We study the power flow change
∆
f
−
E
:=
ˆ
f
−
E
−
f
−
E
on
the remaining lines in terms of the pre-contingency power
flows
f
E
on the simultaneously outaged lines in
E
. Even
though the DC power flow model is linear, the impacts
∆
f
ˆ
e
on remaining lines
ˆ
e
are generally not the sum of the
impacts from tripping lines in
E
separately
(i.e.,
∆
f
ˆ
e
6
=
P
e
∈
E
K
ˆ
ee
f
e
in general).
Without loss of generality, we partition the matrices
(
B, C
)
into submatrices corresponding to the outaged lines
in
E
and the remaining lines in
E\
E
, i.e.:
B
=
diag
(
B
E
, B
−
E
)
,
C
= [
C
E
, C
−
E
]
.
Then the DC power flow equations that describe the post-
contingency network are given by
p
=
C
−
E
ˆ
f
−
E
(1a)
ˆ
f
−
E
=
B
−
E
C
T
−
E
ˆ
θ.
(1b)
From this, we can rewrite the power flow changes
∆
f
−
E
on
the remaining lines in terms of pre-contingency flows
f
E
on
the outaged lines [21]:
∆
f
−
E
=
B
−
E
C
T
−
E
AC
E
(
I
−
B
E
C
T
E
AC
E
)
−
1
|
{z
}
K
E
f
E
,
(2)
where
A
is defined as in Part I. The
|E\
E
|×|
E
|
matrix
K
E
in (2) is known as the generalized line outage distribution
factor (GLODF),
4
which generalizes the LODF discussed
in previous sections from single-line outages
(
|
E
|
= 1)
to
multi-line outages
(
|
E
| ≥
1)
. More specifically, for each
remaining line
ˆ
e
∈ E \
E
, let
K
ˆ
eE
denote the
ˆ
e
-th
row
of
K
E
, then the power flow change on line
ˆ
e
depends on the
pre-contingency flows on
all
lines
e
∈
E
according to the
ˆ
e
-th row of (2):
∆
f
ˆ
e
=
K
ˆ
eE
f
E
=
X
e
∈
E
K
E
ˆ
ee
f
e
.
(3)
For a single-line failure
E
=
{
e
}
,
K
ˆ
eE
reduces to the
LODF
K
ˆ
ee
. We remark that when
|
E
|
>
1
,
K
E
ˆ
ee
is generally
different from
K
ˆ
ee
(see equation (7) below).
The next result describes the localization property of tree
partition in the case of a multi-line failure.
Theorem 13.
Let
K
E
ˆ
ee
be the
(ˆ
e, e
)
-th entry of the GLODF
K
E
. Then
K
E
ˆ
ee
6
= 0
“if” and only if
e
and
ˆ
e
are within the
same cell.
This result generalizes the non-bridge failure case of
Theorem 2 and shows that such failures are localized within
the corresponding cells (in one stage). In particular, simi
lar to
the single-line failure case, if
ˆ
e
does not share a cell with any
line
e
∈
E
then its line flow will not be impacted. However,
unlike the single-line failure case where
K
ˆ
ee
6
= 0
implies
f
ˆ
e
6
= 0
, we do not necessarily have
∆
f
ˆ
e
6
= 0
even when
ˆ
e
is
in the same cell as some
e
∈
E
. This is because the impact
on
ˆ
e
from different line failures in
E
can potentially cancel
each other. Nevertheless, it can be shown that under mild
conditions on the topology of
G
or by adding a perturbation
to the system injection
p
(similar to how we perturb the line
susceptances
B
with
μ
), such a cancellation almost surely
does not happen. Theorem 13 is illustrated in the following
example.
Example 3.
Consider an
N
−
2
event where lines
e
1
and
e
2
are simultaneously tripped, i.e.,
E
:=
{
e
1
, e
2
}
. The power
flow change on a remaining line
ˆ
e
is
∆
f
ˆ
e
=
K
E
ˆ
ee
1
f
e
1
+
K
E
ˆ
ee
2
f
e
2
,
4
The formula of
K
E
can be derived by considering the pre-contingency
network with changes
∆
p
in power injections that are judiciously chosen
to emulate the effect of simultaneous line outages in
E
. The reference
[21] seems to be the first to introduce the use of matrix invers
ion lemma to
study the impact of network changes on line currents in power
systems. This
method is also used in [22] to derive the GLODF for ranking con
tingencies
in security analysis. The GLODF has also been derived earlie
r, e.g., in [23],
and re-derived recently in [24], [25], without the simplific
ation of the matrix
inversion lemma.
6
where
K
E
ˆ
ee
i
is the
(ˆ
e, e
i
)
-th entry of
K
E
. There are two
cases:
1)
Lines
e
1
, e
2
are in the same cell:
E
⊂ C
. According to
Theorem 13, we have
∆
f
ˆ
e
=
0
,
if
ˆ
e
6∈ C
K
E
ˆ
ee
1
f
e
1
+
K
E
ˆ
ee
2
f
e
2
,
if
ˆ
e
∈ C
, .
2)
Lines
e
1
, e
2
are in different cells:
e
i
∈ C
i
,
C
1
∩ C
2
=
∅
.
Then
∆
f
ˆ
e
=
0
,
if
ˆ
e
6∈ C
1
∪ C
2
,
K
E
ˆ
ee
1
f
e
1
,
if
ˆ
e
∈ C
1
,
K
E
ˆ
ee
2
f
e
2
,
if
ˆ
e
∈ C
2
.
In the rest of this subsection, we look at topological
structures of the transmission network
G
that underlie how
multi-line failures in
E
interact to produce the aggregate
impact
∆
f
−
E
. It also serves as the background for the proof
of Theorem 13 in Appendix VII.
Recall from Part I that
D
ˆ
e,e
represents the generation shift
sensitivity factor from
e
to
ˆ
e
. Let
D
−
E,E
be an
|E\
E
| × |
E
|
matrix whose
(ˆ
e, e
)
-th element is
D
ˆ
e,e
. It is easy to show
that
D
−
E,E
=
B
−
E
C
T
−
E
AC
E
. Then (2) can be rewritten
equivalently as
̃
f
E
= (
I
−
B
E
C
T
E
AC
E
)
−
1
f
E
,
(4a)
∆
f
−
E
=
B
−
E
C
T
−
E
AC
E
̃
f
E
=
D
−
E,E
̃
f
E
.
(4b)
Equations (4) interpret the impact on the remaining lines
of tripping
E
simultaneously as consisting of two steps.
First, the pre-contingency flows
f
E
“mix” into a vector of
flow changes
̃
f
E
, and second, the mixed flow changes
̃
f
E
propagate linearly to the remaining edges via (4b) to produc
e
the post-contingency impact: i.e.,
∆
f
ˆ
e
=
P
e
∈
E
D
ˆ
e,e
̃
f
e
on
each remaining line
ˆ
e
.
Noting that
K
ˆ
ee
=
D
ˆ
e,e
/
(1
−
D
e,e
)
when
e
is not a bridge
[13], we can write the flow change on a remaining line
ˆ
e
as
∆
f
ˆ
e
=
X
e
∈
E
K
ˆ
ee
(1
−
D
e,e
)
̃
f
e
,
(5)
since a non-cut set
E
cannot contain any bridge. Now
consider an outaged line
e
∈
E
and a remaining line
ˆ
e
such
that
e
and
ˆ
e
are not in the same cell. Theorem 2 implies
that
K
ˆ
ee
= 0
and therefore
∆
f
ˆ
e
= 0
if
e
were the
only
line
that has been tripped. This does not, however, automaticall
y
imply that
K
E
ˆ
ee
= 0
for simultaneous line failures
E
. Indeed,
if the tripping of
e
can impact the mixed flow change
̃
f
e
′
on
another line
e
′
∈
E
that is in the same cell as
ˆ
e
(and hence
K
ˆ
ee
′
6
= 0
), then from (5) we see that
∆
f
ˆ
e
can potentially be
nonzero, resulting in a nonzero
K
E
ˆ
ee
. In other words, tripping
e
∈
E
in a different cell from
ˆ
e
can potentially impact
ˆ
e
through a different simultaneously outaged line
e
′
∈
E
that is in the same cell as
ˆ
e
. It is therefore remarkable that
tree partitioning turns out to localize the impact of each
simultaneous
line failure within its own cell: the tripping
of
e
can only impact the mixed flow changes
̃
f
e
′
on lines
e
′
∈
E
that are in the same cell, and therefore
K
ˆ
ee
′
6
= 0
is
not possible. This is made precise in the next result.
We collect edges in
E
based on the cells they belong to
and write
E
=
E
1
∪
E
2
∪· · ·∪
E
k
as its
block decomposition
.
That is,
E
i
⊂ C
i
for some cell
C
i
in
G
, and
C
i
∩ C
j
=
∅
if
i
6
=
j
. This decomposition is well-defined since a non-cut
set
E
does not contain any bridge and thus any edge in
E
must belong to a certain cell.
Proposition 14.
Let
E
=
E
1
∪
E
2
∪ · · · ∪
E
k
be its block
decomposition and set
m
i
=
|
E
i
|
. Then
1) Modulo a permutation of rows and columns, the matrix
(
I
−
B
E
C
T
E
AC
E
)
−
1
in
(4a)
is block-diagonal:
H
1
0
· · ·
0
0
H
2
· · ·
0
.
.
.
.
.
.
.
.
.
.
.
.
0 0
· · ·
H
k
where
H
i
∈
R
m
i
×
m
i
for
i
= 1
,
2
,
· · ·
, k
.
2) Under a line susceptances perturbation
μ
that is abso-
lutely continuous with respect to
L
m
, the submatrix
H
i
consists of strictly nonzero entries
μ
-almost surely, i.e.,
μ
((
H
i
)
e
1
e
2
6
= 0) = 1
,
∀
e
1
, e
2
∈ {
1
,
2
, . . . , m
i
}
.
The proof of this result is presented in Appendix VI.
Proposition 14 allows us to decompose (4) corresponding
to the block decomposition
E
=
E
1
∪
E
2
∪ · · · ∪
E
k
. More
precisely, writing
f
E
= [
f
E
i
;
i
= 1
, . . . , k
]
,
̃
f
E
= [
̃
f
E
i
;
i
=
1
, . . . , k
]
, and
D
ˆ
e,E
= [
D
ˆ
e,E
1
,
· · ·
, D
ˆ
e,E
k
]
, equation (4) can
be rewritten as:
̃
f
E
i
=
H
i
f
E
i
,
i
= 1
, . . . , k
(6a)
∆
f
E
i
ˆ
e
=
D
ˆ
e,E
i
̃
f
E
i
,
ˆ
e
∈ −
E, i
= 1
, . . . , k
(6b)
∆
f
ˆ
e
=
k
X
i
=1
∆
f
E
i
ˆ
e
,
ˆ
e
∈ −
E.
(6c)
Equation (6a) reveals the localization structure of tree pa
r-
titioning for simultaneous line outages. It says that the pr
e-
contingency flows
f
E
i
in cell
C
i
mix to produce the vector
of flow changes
̃
f
E
i
within the
same
cell according to (6a).
Each of these flow changes
̃
f
E
i
impacts the remaining lines
ˆ
e
∈ E \
E
separately
according to (6b). Finally, the total
power flow change on
ˆ
e
is the sum of these changes
∆
f
E
i
ˆ
e
according to (6c).
Since
D
ˆ
e,e
shares the same sign as
K
ˆ
e,e
,
D
ˆ
e,e
is non-zero
“if” and only if
e
and
ˆ
e
are within the same cell by Theorem
2 (recall
e
is not a bridge since
E
is a non-cut set). It is thus
clear that
∆
f
ˆ
e
= 0
for
ˆ
e /
∈ ∪
k
i
=1
C
i
. For
ˆ
e
∈ C
i
, equation (6c)
can be further simplified:
∆
f
ˆ
e
=
D
ˆ
e,E
i
H
i
f
E
i
=
X
e
′
∈
E
i
D
ˆ
e,e
′
X
e
∈
E
i
(
H
i
)
e
′
e
f
e
!
=
X
e
∈
E
i
X
e
′
∈
E
i
K
ˆ
ee
′
(1
−
D
e
′
,e
′
)(
H
i
)
e
′
e
!
f
e
.
Therefore, the GLODF can be computed as:
K
E
ˆ
ee
=
P
e
′
∈
E
i
K
ˆ
ee
′
(1
−
D
e
′
,e
′
)(
H
i
)
e
′
e
ˆ
e
∈ C
i
, e
∈
E
i
,
0
otherwise.
(7)
Note that the summation over
e
′
includes
e
. It suggests
that non-cut failures are localized within the correspondi
ng
cells. In particular, for a fixed cell
C
i
, the flow changes
on remaining lines only come from line failures in
E
i
,
while being independent of any failures from other cells.
A complete proof of Theorem 13 is presented in Appendix
VII.
7
B. Cut Failure
Next we consider the case where
E
forms a cut set,
whose removal disconnects
G
into multiple islands that are
potentially power imbalanced. In this case, the formula (2)
no
longer applies since the matrix
I
−
B
E
C
T
E
AC
E
is not invert-
ible. The power balancing rule
R
then adjusts the injections
of participating buses to cancel out the imbalances in all su
ch
islands. For ease of presentation, let us focus on one island
D
thus created and denote its injection adjustment under
R
by
∆
p
D
. This adjustment
∆
p
D
has non-zero components only
at participating buses or buses that are endpoints of edges i
n
E
that connects
D
and
E\D
.
Given the fixed island
D
, let
E
D
be the set of edges in
E
that have both endpoints within this island. Note that
E
D
is a
non-cut set of
D
since otherwise tripping
E
would disconnect
D
to multiple islands. Let
B
D
, C
D
, A
D
be as introduced
in Section V, which correspond to the post-contingency
topology of island
D
. Let
K
E
D
denote the GLODF of
line failure
E
D
for island
D
. With all these notations, we
characterize how
∆
f
is related to
∆
p
D
,
K
E
D
and
E
D
.
From (4), we know that when multiple lines are tripped
from the grid simultaneously, the aggregate impact in gener
al
is different from the sum of tripping the lines separately.
The impact from balancing rule
R
, though, turns out to be
separable from the rest, as the following result shows (see
Appendix VIII for its proof).
Proposition 15.
Given the injection adjustment
∆
p
D
and
original flow
f
E
D
on
E
D
, we have
∆
f
D
=
B
D
C
T
D
A
D
∆
p
D
+
K
E
D
f
E
D
.
(8)
The first term in (8) captures the impact of power im-
balance, and is characterized by our discussion in Section
V-B. The second term in (8) reduces to the case studied in
Section VI-A since
E
D
is a non-cut set of
D
. We thus see
that a cut set failure impacts the branch flows on remaining
lines in two independent ways: (a) via participating buses
to distribute the power imbalances; (b) via cells to mix and
propagate original flows on the tripped lines. The formula
(8) precisely describes the impact propagation through the
se
two ways, which are fully characterized by our results in
previous sections.
C. Localization Horizon
In this section, we summarize the results from Sections
VI-A and VI-B and show that tree partition localizes the
impact of line failures until the grid is disconnected into
multiple islands. More formally, given a cascading failure
process described by
B
(
n
)
,
n
∈
N
, define
T
:= min
{
n
∈
N
:
F
(
n
)
is a cut set of
G
(
n
)
}
to be the first stage where the grid is disconnected into
multiple islands. Without loss of generality, assume the in
itial
failure
B
(1)
contains only one edge that belongs to the cell
C
. Then we know that (see Appendix IX for a proof):
Proposition 16.
For any
n
≤
T
, we have
F
(
n
)
⊂ C
.
In other words, in a cascading failure process, the
only
way that a non-bridge failure can propagate to edges outside
the cell to which the original failure belongs is to disconne
ct
the grid into multiple islands.
VII. C
ASE
S
TUDIES
Our findings highlight a new approach for improving the
robustness of power grids. More specifically, Theorems 2,
13 and the discussions in Sections IV and VI suggest that it
is possible to localize failure propagation by switching of
f
some transmission lines to create a finer tree partition with
smaller regions where failures can be contained.
It is reasonable to expect that this approach to improve
system robustness
always
comes at the price of increased
line congestion. In this section, we argue that this is not
necessarily the case, and show that if the lines to switch
off are selected properly, it is possible to
improve robustness
and reduce congestion simultaneously.
We corroborate this
claim using the IEEE 118-bus test network according to
two metrics: (a) The
influence graph
is much sparser after
tree partitioning, confirming failure localization; (b) Th
e
congestion level is reduced on 52.59% of the lines and is
increased by less than 10% on 90% of the remaining lines
after tree partitioning.
A. Influence Graph
In our experiments, the system parameters are taken from
the Matpower Simulation Package [26] and we plot the
influence graphs among the transmission lines to demonstrat
e
how a line failure propagates in this network. Our influence
graph is similar in concept to that of [27], [28], but unlike
their influence graph that is based on a probabilistic model,
ours is simply a visualization of the LODF
K
ˆ
ee
that describes
the impact on other lines of tripping a single line
e
. The orig-
inal IEEE 118-bus network is depicted in blue in Fig. 3(a).
5
Its influence graph has these transmission lines (in blue) as
its nodes. Two such blue edges
e
and
ˆ
e
are connected in the
influence graph by a grey edge if
|
K
ˆ
ee
| ≥
0
.
005
. As Fig. 3(a)
shows (), the influence graph of the original network is very
dense and connects many edges that are topologically far
away, showing a high risk of non-local failure propagation
in this network.
We then switch off three transmission lines (indicated
as
e
1
,
e
2
and
e
3
in Fig. 3(b)) to obtain a new network
topology with a tree partition consisting of two regions
of comparable sizes. The corresponding influence graph is
shown in Fig. 3(b). Compared to the original influence graph
in Fig. 3(a), the new one is much less dense and, in particular
,
there are no edges connecting transmission lines that belon
g
to different tree-partition regions, as our theory predict
s. The
network in Fig. 3(b) contains two cut vertices (indicated by
c
1
and
c
2
in the figure, with
c
2
being created when we
switch off the lines). It can be checked that line failures ar
e
“blocked” by these cut vertices, which verifies our results i
n
Section IV.
B. Congestion Level
We have demonstrated using a stylized example in Section
V of Part I that, contrary to conventional wisdom, tree
partitioning can potentially reduce circulating flows in th
e
system and thus decrease the overall line congestion. Here
we evaluate changes in line congestion in the IEEE 118-
bus network before and after our tree partitioning. Specif-
ically, we collect statistics on the difference between the
5
The original IEEE 118-bus network has some trivial “danglin
g” bridges
that we remove (collapsing their injections to the nearest b
us) to obtain a
neater influence graph.
8
(a) Original IEEE 118-bus network (with edges in blue) and it
s influence graph (with edges in grey).
(b) The influence graph after switching off
e
1
,
e
2
and
e
3
. The black dashed line indicates the failure propagation bo
undary defined
by the tree-partition. The vertices
c
1
and
c
2
are cut vertices.
Fig. 3. Influence graphs on the IEEE 118-bus test network befo
re and after switching off lines
e
1
,
e
2
and
e
3
. Blue edges represent physical transmission
lines and grey edges represent connections in the influence g
raph.
branch flows in Fig. 3(b) and those in 3(a), normalized by
the original branch flow in Fig. 3(a). They are plotted in
Fig. 4(a), showing that
52
.
59%
of the transmission lines have
lower congestion. Of the
47
.
41%
of lines that have higher
congestion, the majority of these branch flow increases are
negligible. To visualize more clearly, we plot in Fig. 4(b) t
he
cumulative distribution function of the normalized positi
ve
branch flow changes. It shows that
90%
of the branch flows
increase by no more than
10%
.
VIII. C
ONCLUSION
We make use of the spectral representation of power
redistribution developed in Part I to provide a precise an-
alytical characterization of line failure localizability
through
tree partitioning. We demonstrate that a tree partition can
be
computed in linear time. A case study on the IEEE 118-bus
test network shows that switching off certain transmission
lines can improve grid robustness against line failures wit
h-
out significantly increasing line congestion.
Despite the benefits, refining the tree partition of a given
power grid may not be a satisfactory solution by itself in