1

Distribution System Outage Detection using Consumer
Load and Line Flow Measurements
Raffi Sevlian∗ , Yue Zhao∗‡ , Ram Rajagopal† , Andrea Goldsmith∗ , H. Vincent Poor‡
∗ Department of Electrical Engineering, Stanford University † Department of Civil and Environmental Engineering,
Stanford University ‡ Department of Electrical Engineering, Princeton University

arXiv:1503.08244v2 [cs.SY] 17 Nov 2016

Abstract—An outage detection framework for power distribution
networks is proposed. Given the tree structure of the distribution
system, a method is developed combining the use of real-time power
flow measurements on edges of the tree with load forecasts at
the nodes of the tree. A maximum a posteriori detector (MAP)
is formulated for arbitrary number and location of outages on trees
which is shown to have an efficient detector. A framework relying
on the maximum missed detection probability is used for optimal
sensor placement and is solved for tree networks. Finally, a set of case
studies is considered using feeder data from the Pacific Northwest
National Laboratories. We show that a 10% loss in mean detection
reliability network wide reduces the required sensor density by 60
% for a typical feeder if efficient use of measurements is performed.

I. I NTRODUCTION

Outage detection and management has been a long-standing
problem in power distribution networks. Outages are caused by
protective devices closing off a part of the network to automatically isolate faults. Usually, a short circuit fault will trigger this
protective operation. We employ the term outage detection to
denote the task of finding the status of the protective devices, and
the term fault detection to denote finding the faults that caused
the resulting outage situation.
Many methods for outage and fault detection based on artificial intelligence have been developed. Outage detection is
often performed prior to fault detection and can greatly improve
the accuracy of fault diagnosis. For outage detection, fuzzy set
approaches have been proposed based on customer calls and
human inspection [14], and based on real-time measurement
with a single sensor at the substation [1]. In networks where
supervisory control and data acquisition (SCADA) systems are
available, a subset of the protective devices’ status can be obtained
via direct monitoring. When two-way communications from the
operator and the smart meters are available, AMI polling has
been proposed to enhance outage detection [8]. There have also
been knowledge based systems that combine different kinds of
information (customer calls, SCADA, AMI polling) [6]. For fault
detection, using only a single digital transient recording device
at the substation, fault location and diagnosis systems have been
developed based on fault distance computation using impedance
information in the distribution system [15]. Using only the outage
detection results, i.e., the status of the protective relays, expert
systems have been applied to locate the underlying faults [4].
Incorporating voltage measurements in the distribution system
This research was supported in part by the DTRA under Grant HDTRA1-081-0010, in part by the Tomkat Center, in part by Powell Foundation Fellowship,
in part by the National Science Foundation award CIF1116377, in part by the Air
Force Office of Scientific Research under MURI Grant FA9550-09-1-0643, and
in part by the Office of Naval Research, under Grant N00014-12-1-0767.

with the outage detection results, fault detection methods based
on knowledge based systems have been proposed [2]. Fault
detection that uses fault voltage-sag measurements and matching
has been proposed in [9], [5]. Fault diagnosis based on fuzzy
systems and neural networks have also been proposed that can
resolve multiple fault detection decisions [13]. Existing outage
and fault detection methods based on artificial intelligence do
not provide an analytical performance metric, so it is in general
hard to examine their optimality. Their performance can however
be evaluated numerically and in simulation studies. Moreover,
because of this lack of an analytical metric, while some of
the existing approaches depend on near real-time sensing (e.g.
SCADA), they do not provide guidance on where to deploy the
limited sensing resources within the distribution system.
A major alternative to these mechanism is the so called last
gasp, where area’s in outage will notify, via distress signal that
they are out of power. These provide a duplicate method of outage
detection which can be combined with the proposed methods here.
In fact, combining both of these methods can further reduce the
time to outage in practical scenarios.
The proposed sensing and feedback framework exploits the
combination of real-time sensing and feedback from a limited
number of power flow sensors and the infrequent load updates
from AMI or forecasting mechanisms. This can is practically
possible since there is a growing number of deployments of
distribution system line measurements [7], which can measure
line current with high precision.
II. P ROBLEM F ORMULATION AND M AIN C ONTRIBUTIONS
Consider a power distribution network that has a tree structure.
Power is supplied from the feeder at the root, and is drawn by all
the downstream loads. An outage is a protective device isolating
a faulted area. When this occurs, the loads downstream of the
faulted area will be in outage. We investigate the optimal design
and performance of automatic outage detection systems with the
use of the following two types of measurements:
Noisy Nodal Consumption typically in the form of forecasts
which have forecast errors that must be taken into account.
Error Free Edge Flows which typically come from realtime SCADA measurements of the power flows on a fraction
of the lines.
The issue of noisy and error free measurement comes from the
fact that loads come from delayed information which needs to be
forecasted, while SCADA systems have real time communication
potential. This work assumes lossless power flow, but can also be
applied in the case of current measurements on the line and load
level. This can be done, since practical distribution line sensing

2

is accurate in terms of current measurements, and smart meter
interval data provides power and voltage information, making
current inference possible.
The main contributions of this work are the following:
Outage Detection We formulate the problem of detecting
any number of possible outages via nodal and edge measurements as a general hypothesis testing problem where the
number and locations of outages are unknown. We show that
this general formulation results in a computationally efficient
decentralized hypothesis detector.
Sensor Placement We use the decentralized nature of the
detector provide a optimal sensor placement with respect to
the maximum missed detection error for all hypotheses.
III. S YSTEM M ODEL AND N OTATION
0
1

s0

3

7

where the set Vi (H) indicate the set of vertices to be summed
over under any particular hypothesis.
A general representation of the observed flow is the following.
The set of full flow observations s, given a particular hypothesis
H ∈ H k , we can represent the observations as:

9
10

s1

(4)

where ΓH ∈ {0, 1}|M|×|V | . Here ΓH is generated for each
hypothesis and we assume the forecast error covariance Σ can
be estimated from the load forecasting process.

8

5
6

v∈Vi (H)

s = ΓH x ∀H ∈ Hk ,

2
4

Measurement Model: For any edge e, denote by s the power flow
on it towards all active downstream loads. The measured flow
depends on the network topology, outage situation and the true
loads. The sensor placement is denoted as M with M ⊂ E. The
vector of all measurements is s ∈ R|M| .
Given a tree T assume hypothesis H corresponds to the outage
of any number of disconnected edges. The measured power
consumption of the ith sensor measurement under hypothesis
H ∈ Hk is
X
si (H) =
x(v),
(3)

11

IV. G ENERAL O UTAGE D ETECTION

12
13
14

16
17
18

15

Fig. 1. Example tree T1 used to illustrate various properties. Each node in the
network is numbered. Node vn is connected to it’s parent via edge en consuming
x(v) power at each node. Two flow measurement sensors s0 , s1 along with load
pseudo measurements x̂(v).

Topology of the Distribution System: The vertices in the distribution network are indexed by V = {v0 , v1 , . . . , vN }, with bus
v0 denoting the root of the tree. We index by en the line that
connects bus vn and its parent node.
Outage Hypothesis Model: Outages are modeled as disconnected
edges corresponding to protective devices disconnecting loads on
a network. For example, consider single line outages in a tree
with N edges: In this situation, there will exist N single edge
outage hypotheses and a single non-outage situation. Let H1 =
{e1 , . . . , eN ∪ ∅} be the set of all single outage hypotheses for a
tree T .
We consider a more general case of an unknown number and
location of potential outages. We define the set of up to k edge
outages Hk as the set of k edge hypothesis. This set follows:
Hk = H1 × H1 . . . H1 .
|
{z
}

(1)

k times

Load Model: Each node v in the graph has a consumption load
x(v). The forecast of each load is x̂(v) with error (v) =
x(v) − x̂(v). We assume errors are mutually independent random
variables that follow (v) ∼ N (0, σ(v)2 ). Given the forecasts we
treat the true load, which is unknown to us, as a random variable
x(v) ∼ N (x̂(v), σ 2 (v)). In the vector case, we have
x̂ ∼ N (x, Σ)
where we can assume Σ is a diagonal covariance matrix.

(2)

Consider the general outage detector. Given the vector of load
forecasts, x̂, nominal forecast error Σ and real time load flows s
along a set of branches, the detector must determine the correct
?
number and location of each edge in outage H ∈ Hk .
These are single snapshot values of load forecast and line flow.
A multi period detection framework can be analyzed in a similar
fashion. We first construct a simple but naive multiple hypothesis
detector relying on a maximum likelihood estimator. Consider the
flow model in eq. (4), relating the true load at each node to the
observed flow on the network.
Given the forecast model in eq. (2) and the hypothesis model
in eq. (4), the Maximum a Posteriori detector is the following:
{k ? , Ĥ} ∈ arg max Pr (s | x̂, H)

(5)

H∈Hk

See Appendix B, for details.
The flow likelihood can be computed as follows:
s|{x̂, H} = ΓH x
= ΓH (x̂ + )
∼ N ΓH x̂, ΓH ΣΓTH



∀H ∈ Hk

(6)

Eq. (6) allows us to evaluate a likelihood under each possible
hypothesis. Therefore, a naive detector will enumerate every possible outage, evaluate it’s likelihood, and choose the maximum.
This is difficult for the following reasons:

k
1) The set Hk is of size |E|
k , so computing the set H
can be very expensive. Enumerating
the
 entire maximum
P
likelihood detector requires k=1 |E|
evaluations.
k
2) Many of the potential hypotheses map to the same observed
flows, therefore the detector output is not unique. This
occurs when one edge is a descendant of another.
3) Missed detection errors in a multivariate hypothesis testing
framework can only be evaluated via monte carlo testing.
There is no insight in optimizing placement.

3

V. D ECOUPLED M AXIMUM L IKELIHOOD D ETECTION

0

We show that the issues regarding the general maximum likelihood detector can be overcome by decoupling the hypotheses and
the observations, given the tree structure of the outage detection
problem. This leads to a simple decentralized detector which is
equivalent to eq. (5), where each decision is a scalar hypothesis
test. This leads to an efficient hypothesis enumeration, detection
and error evaluation.
In the following sections, we show the following:
1) The original search space Hk can be replaced by a set Hu
of uniquely detected outages, due to the tree structure of
the network.
2) Processing zero/positive flow information reduces the
search space from Hu to Hu+ . which decouples
a
V into
product set of local hypotheses: Hu+ =
Hu+ (A).
A∈A+

Where, A indicates a local area with it’s own hypothesis
set.
3) The joint likelihood function Pr(s | x̂, H) decouples along
each area.
Combining these results leads to a decentralized detector which
can be solved easily.
A. Unique Outages
Maximizing the likelihood of observations over the k outage
set can lead to a non-unique solution. An alternative is to only
consider uniquely detectable outages, where no possible outage
event is downstream of any other.
Define the set of outage hypotheses Hu (u is for unique) as
follows:
Hu ={H ∈ H for some k, s.t no two edges
(7)

This definition is not constructive, but useful. Consider tree T2
shown in Figure 2(c). Here Hu can be enumerated by simple
observation.
Hu = {∅, e1 , e2 , e3 , e4 , e5 , (e3 × e5 ), (e4 × e5 )}

2

b3

b2
b4

b3

b2

3

b5
b5

b4

(a)

(8)

There is a single non-outage hypothesis ∅, and 5 single outage
hypotheses, and 2 double outage hypotheses.
For a more general case (Figure 1), enumerating this set for a
tree can be performed recursively. The set Hu can be enumerated
using a ’branch-network’ based on the original tree. The tree
in Figure 1 is depicted in Figure 2(a) with nodes and edges
removed which highlights the various branches of the graph. Each
set of branches are aggregated as a node to be traversed, in the
hypothesis enumeration procedure.
Consider a set function E(b) = {e ∈ E : e is along branch bi }
to enumerate the set of edges on a branch. Given the two
examples, we have the following branch-edges:
• T1 : E(b1 ) = {e1 , e2 , e3 }, E(b2 ) = {e4 , e5 , e6 , e7 }, E(b3 ) =
{e8 , e9 , e10 , e11 , e12 }, E(b4 ) = {e13 , e14 , e15 } and E(b5 ) =
{e16 , e17 , e18 }.
• T2 : E(b1 ) = {e1 , e2 }, E(b2 ) = {e3 , e4 }, E(b3 ) = {e5 }.
Using this definition, we propose the following recursive definition of the set Hu (b), which indicates the set of hypotheses
formed from branch b and all descendants. From this definition,

s

1

b1

b1

5

4

(b)

b3

b2

(c)

(d)

Fig. 2. 2(a) Branches of tree T1 . 2(b) Branch network for tree T1 . 2(c) Simple
tree network T2 . 2(d) Branch graph for T2 .

it is clear that Hu ≡ Hu (b1 ), since this is the root branch of the
tree.

!
[
^
Hu (b) = E(b) ∪ 
(9)
Hu (b) 
b∈b

b∈P(child(b))

Here b is the current node, and child(b) is the set of children of b
in the branch tree. The set P(child(b)) is the power set of all the
child branches, where any element of the power set is b. Note that
if a branch has no descendants, we merely evaluate E(b), since
the remaining terms are null. Eq. (9) is quite unwieldy, but can
be interpreted easily. For tree T2 in Figure 2(c) the child branches
are child(b1 ) = {b2 , b3 } while the power set is:
P({b2 , b3 }) = { {∅} , {b2 }, {b3 }, {b2 , b3 }}.
|{z} |{z} |{z} | {z }
b0

b1

b2

(10)

b3

Evaluating (9), we arrive at the following:

 

^
^
Hu (b1 ) = E(b1 ) ∪ 
Hu (b) ∪ 
Hu (b)
b∈{b2 }

b∈{∅}



k

are descendant of each other.}

b1


^

∪



Hu (b) ∪ 

b∈{b3 }


^

Hu (b)

(11)

b∈{b2 ,b3 }

We rely on the following definitions:
V
D1 Base case:
Hu (b) = ∅.
b∈{∅}

D2 Hypotheses double counting: ei ∪ ei = ei , including the
empty set ∅ ∪ ∅ = ∅.
D3 Cross product reduction: ∅ × ei = ei , which implies E(b) ×
∅ = E(b).
For example, eq. (9) is applied to T2 as follows: For b1 , we have
that
Hu (b1 ) = {E(b1 ) ∪ Hu (b2 ) ∪ Hu (b3 ) ∪ Hu (b2 ) × Hu (b3 )}.
(12)
For the branches b2 and b3 we use eq. (9) and D1 resulting in
Hu (b2 ) = {E(b2 ) ∪ ∅} and Hu (b3 ) = {E(b3 ) ∪ ∅}. Using D2
and D3, we have the following: This results in:
Hu (b1 ) = {E(b1 ) ∪ {∅} ∪ {E(b2 ) ∪ ∅} ∪ {E(b3 ) ∪ ∅}
∪ {E(b2 ) ∪ ∅} × {E(b3 ) ∪ ∅}}
= {∅ ∪ E(b1 ) ∪ {E(b2 ) ∪ E(b2 ) ∪ E(b3 ) ∪ (E(b2 ) × E(b3 ))}
= {∅, e1 , e2 , e3 , e4 , e5 , (e3 × e5 ), (e4 × e5 )}
Which is identical to simple enumeration. At this point, we have
reduced the maximum likelihood detector to the following form:
Ĥ = arg max Pr (s | x̂, H)
H∈Hu

(13)

4

Note the equality in the maximization since the restriction of
the search space allows us to find a unique solution. Notice that
this procedure will automatically enumerate all possible number
of outages as well as their positions in the graph. Under the
general model of any number of edge outages, this is the complete
enumeration of the hypothesis set which has a high computational
burden.
In the following sections we show that (1) the search space decouples to a product space of local hypotheses given binary flow
indicators and (2) the likelihood function decouples along these
local ’areas’, thereby reducing to a decoupled scalar hypothesis
test for each local area.
B. Reducing Hypotheses from binary flow information

A1, H+u(A1)

A1 b
1

s1
s2

b2

A2 H+u(A2)

s1

s1
b u3
A2
b4

(a)

bl

s2

H1

s2
3

H2

b5

(b)

(c)

Fig. 3.
3(a) The branch network for network T1 with associated sensors s1 ,
+
+
s2 and area hypotheses Hu
(A1 ) and Hu
(A2 ). 3(b) Each area will keep the
local branches. Branch b3 is split between two areas and processed as different
u
vertices in branch-network (bu
3 and b3 . 3(c) The network can be modeled by a
directed graphical model indicating observations (shaded) and variables that must
be maximized over.

The detection problem will encounter a set of positive flows as
well as zero’s when a sensor is downstream of an edge outage.
The ML detection observations and search space can be reduced
as:
Ĥ = arg max Pr ({sz s+ } | x̂, H)

(14)

∀H∈Hu

= arg max Pr ({s+ } | x̂, H)

(15)

∀H∈H+
u

By processing the flow information we reduce the set of hypothesis in the detector from the set Hu to the reduced set
Hu+ . More importantly, we show that Hu+ does not require a
recursive enumeration, but actually decouples as a product space
of local hypotheses. This is first shown in an example, then the
general form is stated. Consider T1 with branch network with flow
measurements in Figure 3(b). In this example, all branches are
unchanged except b3 , which is split into bu3 and bl3 and is separated
by flow measurement s1 . In the case of splitting branch nodes,
the upper branch will take the edge with the measurements so
E(bu3 ) = {e8 , e9 , e10 } and E(bl3 ) = {e11 , e12 }.
The following illustrative example highlights a general decoupling principle of the hypothesis set Hu+ . Let’s consider the two
cases separately (s1 , s2 > 0 and s1 > 0, s2 = 0) which provides
the intuition for the general case.
1) Case 1: (s1 > 0, s2 > 0) This implies that there cannot
be any outage with edges in b1 or b3 , else s2 = 0. A brute force
enumeration of Hu+ (b1 ) is done by enumerating H(b1 ) according
to Figure 2(b), then removing any terms with E(b1 ) and E(b3 )

outages. It can be shown that:
Hu (b1 ) = {∅ ∪ E(b1 ) ∪ E(b2 ) ∪ (E(bu3 ) ∪ Hu (bl3 ))
∪ E(b2 ) × (E(bu3 ) ∪ Hu (bl3 ))}
Removing the possible outages due to the positive flow information (i.e. any tuple with edges in E(bu3 ), or E(b1 )) , we have:

Hu+ (b1 ) = {∅ ∪ E(b2 ) ∪ Hu+ (bl3 ) ∪ E(b2 ) × Hu+ (bl3 ) }
= {∅1 ∪ E(b2 )} × {∅2 ∪ Hu+ (bl3 )}
= Hu+ (A1 ) × Hu+ (A2 )
We use A1 and A2 to define a local area. An area is a partition
of the original tree, which will decouple the set of all hypotheses
into a product space of ’area hypotheses’. Each area will contain
a root sensor (ex. A1 contains s1 ) and a set of descendent sensors
(ex. child(s1 ) = {s2 }).
Within a local area, a set of unique outage hypotheses are evaluated Hu+ (A1 ) which satisfy the binary observations of whether
any flow is observed along the downstream sensors child(s1 ) > 0.
The local hypotheses of each area are later combined to form
any possible hypothesis from the original enumeration of unique
outages. Appendix C contains a more detailed discussion.
2) Case 2: (s1 > 0, s2 = 0) This implies that all possible
outages must contain b1 or bu3 , else s2 > 0. First we enumerate
Hu (b1 ) then keep only those elements which lead to s2 = 0 (i.e.
every tuple with edges in E(bu3 ), or E(b1 )) , we have:
Hu+ (b1 ) = {∅ ∪ E(b1 ) ∪ E(bu3 ) ∪ E(b2 ) × E(bu3 )}
= {Hu+ (A1 )}
Note that in this case, Hu+ (A2 ) is never evaluated since s2 = 0.
Different positive and zero flow patterns lead to changes in the
local hypothesis set Hu+ (A).
3) General Hypothesis Decoupling: A complete description of
the set should be Hu+ (A, f ), where f = I{child(si )>0} , since this
set depends on the binary flow information of the child sensors.
For example Case 2 is Hu+ = Hu+ (A1 , {1 0}) and Case 2 is
Hu+ = Hu+ (A1 , {1 1}) × Hu+ (A2 , {1 1}). For any arbitrary tree
and flow sensors, the unique hypothesis set conditional on binary
flows Hu+ will decouple according to:
^
Hu+ =
Hu+ (A).
(16)
A∈A+
+

Where the set A indicates the areas which have a root measurements si > 0. Finally, Hu+ (A) is the local conditional
hypothesis, which can be computed in the general case. Any
given Hi ∈ Hu+ can be represented by a product of area
hypotheses Hi = H1,i(1) × . . . × HM,i(M ) , where for the k th area
Hk,i(k) ∈ Hu+ (Ak ). Index i(k) is the particular index into the k th
hypothesis set corresponding to global hypothesis Hi . Appendix
D presents a general algorithm generate the set Hu+ (A, f ), for
arbitrary binary flow information.
C. Decoupling the Joint Likelihood:
Due to the model of noiseless flow and forecasted nodal
measurements joint likelihood of all observations, given x̂, and
H ∈ Hu+ , decouple across the areas. In general we have:
Y
Pr (s+ | x̂, H) =
Pr (si | child(si ), x̂, Hi ) (17)
i:Ai ∈A+

5

The tree T1 is presented here as an example, while the general
case can be easily shown as an extension of the example.
Consider again the sub-graph in Figure 3(a), where we have already reduced the hypotheses using binary flow information (both
s0 , s1 > 0). As discussed in Section V-B3, a unique hypothesis
Hi ∈ Hu+ can be represented as Hi = H1,i(1) × H2,i(2) . Where
H1,i(1) ∈ H(A1 ) and H2,i(2) ∈ H(A2 ).
From eq. (3) the observed flow s1 , can be computed as follows:
X
s1 |{x̂, Hi } =
x(v)
(18)

D. Decoupled Maximum Likelihood Function:
We can combine the results shown so far to a decoupled
likelihood function.
{k ? , Ĥ} ∈ arg max Pr (s|x̂, H)
= arg max Pr ({s+ sz }|x̂, H)

X

x(v) +

v∈V (H1,i(1) ×H2,∅ )\V (H2,∅ )

X

= arg max Pr (s+ |x̂, H)

X

=
x(v)
=

Pr (s+ |x̂, H1 . . . HM )
Y

arg max
∀A∈A+ ∀Hi ∈H+ (A)

Pr (si |child(si ), x̂, Hi )
(26)

^

=

Where:
• Eq. (18) is the summation of true loads. By decoupling of
the hypotheses across areas, we represent Hi as the product
of the two local hypotheses H1,i(1) and H2,i(2) .
• In (19), this can be separated as the sum of parts
1) V (H1,i(1) × H2,∅ ) \ V (H2,∅ ) are the vertices in the
summation in A1 independent of what is happening
of downstream areas. H2,∅ indicates the non-outage
hypothesis in area 2.
2) V (H2,i(2) ) is the set of vertices in the summation
for
P area Area 2. Although H2,i(2) is unknown, s2 =
v∈V (H2,i(2) ) x(v), the the unknown hypothesis can
be eliminated.
• Eq. (20), replaces the second summation with the observed
flow, since they are equivalent. Therefore, if we condition on
the remaining flow observation, child(s1 ), the flow decouple
between different areas.
Finally, since x(v), is not known, a likelihood function for the
net flow in the area can be constructed given the load forecasts.
The first term in eq. (20) is modeled with the following:
(21)

Evaluating µ(x̂, H), and σ(Σ, H) can be computed easily and
is described in Section VI-B.
Similarly, s2 is decoupled from any hypothesis in Hu+ (A1 ),
since the measurement depends only on downstream hypotheses
(assuming s2 has some positive flow to begin with). In this
example we can decouple the likelihood function as follows.
Pr (s1 s2 | x̂, H1 , H2 ) = Pr (s2 | x̂, H2 ) Pr (s1 |s2 x̂, H1 )
In this example, this decoupling can be represented as a simple
graphical model as shown in Figure 3(c), where each local
hypothesis is an unknown variable that must be determined via
likelihood maximization. Conditioning on the the only observations s1 , s2 , the two hypotheses variables are independent. This
graphical model formulation is used to show the general case
where there may be noise in the flow measurements. In such
a case, the decoupling would not work, but a message passing
algorithm can be used. The graphical model formulation can also
be applied in different sensor types. To show the general case, eq
(18)-(20), can be extended to a general area network with multiple
downstream sensors.

(25)

i:Ai ∈A+

(20)

v∈V (H1,i(1) )\V (H2,∅ )

s1 − s2 |{s2 x̂, H} ∼ N (µ(x̂, H), σ(x̂, H)).

arg max
∀A∈A+ ∀Hi ∈H+ (A)

v∈V (H2,i(2) )

x(v) + s2

(24)

∀H∈H+
u

(19)
=

(23)

∀H∈Hu

v∈V (H1,i(1) ×Hi,i(2) )

=

(22)

∀k,∀H∈Hk

i:Ai ∈A+

arg max Pr (si |child(si ), x̂, Hi ) (27)
∀Hi ∈H+ (Ai )

Here eq. (22) is the original maximum likelihood hypothesis test
over all Hk outages. This is reduced to a search space over Hu
in eq. (23). This further reduces to an even smaller search space
Hu+ due to processing of binary flow information in eq. (24). Eq.
(25) decouples Hu+ to a product space of local search hypotheses.
Eq. (26) decouples the likelihood functions by conditioning on
the set of observations. This likelihood function is a product
of terms which only depend on the local hypotheses. Therefore
maximizing this product is equivalent to maximizing each term
separately, as in eq. (27). The decoupling of the centralized likeAlgorithm 1: Maximum Likelihood Hypothesis Detector.
Result: Maximum Likelihood Hypothesis Detector
Input: [1] Load Forecast/Nominal Statistics: x̂, Σ
[2] Real Time Load: s = {s+ , sz }
+
1 A ← prune − areas(A, s)
+
2 for Ai ∈ A do
3
// Generate Local Hypothesis set.
4
Hu+ (Ai ) ← local − hypotheses(T , si , d(si ))
5
// Local MAP Detector
6
Ĥi ← arg max Pr (si |d(si ), x̂, Hi )
∀Hi ∈H+ (Ai )
7
8
9

end
// Combine Local Hypotheses
V
Ĥ ←
Ĥi
Ai ∈A+

lihood function in (26), leads to a simple decentralized detector
in Algorithm 1. The input is (1) the set of load forecasts x̂ with
their nominal statistics Σ, (2) and the real time load information
s. The function prune-areas simply discards areas with zero flow.
The function local-hypotheses performs the generation of local
hypothesis set Hu+ (Ai ) as described in section D.
Finally the local MAP detector is simple to evaluate as a multihypothesis test involving scalar gaussian of known means and
variances as follows: For a local area, since H+ (A) is enumerated,
we determine:
!2
P
si − s∈child(si ) s − µ(x̂, H)
Ĥ = arg max
σ(Σ, H)
H∈H+ (A)

6

Algorithm 2: Solution to optimization (OPT-3) for tree
network.
Result: Placement for a Tree Network
Input: [1] Tree network T
s∈child(si )
[2] Nominal loads statistics x̂, Σ
[3] Subproblem Ordering Vprocess
for each local area. Computation of the means and variance are
[4] Target error P target
discussed in Section VI-B.
1 // Generate node process ordering
2 Eprocess ← generate-edge-order(T )
VI. S ENSOR P LACEMENT P ROBLEM
3 // initialize sensor placement as empty
In evaluating a placement, we use the maximum missed de- 4 Mg ← ∅
tection probability over all hypotheses. This is a useful metric 5 for et ∈ Eprocess do
A ← construct-area(et , Mg )
since we are considering a very large number of alternative 6
// Evaluate the current subtree maximum missed
hypotheses. First consider the maximum error PE (H, M) = 7
if PEmax (A) ≤ P target then
Pr(Ĥ 6= H; placement M), where Ĥ is the optimal solution 8
9
// continue to next node
of the outage detection.
10
else
This can be used for sensor placement evaluation.
11
if |child(vt )| == 1 then
M? = arg min max PE (H, M)
(OPT-1) 12
Mg ← line-action(A, Mg )
|M|=M H∈Hu
13
else if |child(vt )| > 1 then
This is difficult to do outside of a combinatorial enumeration of 14
Mg ← tree-action(A, Mg )
sensor locations and hypotheses. A suitable proxy we optimize 15
instead is the following:
16
end
17
end
M? = arg min max PE (A)
(OPT-2)
g
18 return M
|M|=M A∈A
Therefore each decision only depends on an effective measurement
X
∆si , si −
s
(28)

Where PEmax (A) = maxf,H∈Hu+ (A,f ) PE (H, M), that is we only
search over the hypothesis in the local area. This second optimization very closely approximates an upper bound to (OPT-1)
(see appendix F for details). Optimization OPT-2 is solved via a
bisection method on the following feasibility problem:
M? = find

M

|M|≤M
s.t. PEmax (A)

(OPT-3)
≤ P target

So the minimum P target is determined which yields a solution
of size |M| = M . This can be solved very efficiently, with the
algorithm that follows.
A. Feasibility Placement Algorithm
The intuition for the greedy placement algorithm is the following. Starting from the bottom of a tree, we successively
maintain a temporary local area with root sensor in et . The root
sensor is iteratively moved closer to the root edge e1 , while
maintaining that the maximum error of all areas is less than
P target . This is done by maintaining that the local area has
error less than P target . If this is true we move closer to the
root, if not, we place a sensor and start a new area. Since the
objective function decouples across areas, we can maintain that
the feasibility problem is always satisfied. Finally, if the number
of sensors are less than M , M? is returned. This framework
can be realized in Algorithm 2. The inputs to the method are
the tree network T and the set of nominal load forecasts x̂ and
forecast variance Σ. To have the effect of starting at the leaf of
the network and move our way up to the root, the algorithm will
process a sequence of edges Eprocess . For example in Figure 1,
Eprocess = {E(b4 ) E(b5 ) E(b3 ) E(b2 ) E(b1 )}. We generate the
list Eprocess in line 2 with function generate-edge-order. The
function takes the tree T and traverses via breadth first search
keeping track of the depth of each vertex/edge. Reversing this

list of depths yields a list of nodes to process, the parent edge
being e ∈ Eprocess .
The greedy solution Mg must first be initialized as empty. In
line 5 we iterate over the current root node et and current sensor
placement M. In line 6 we construct the current area network A.
We then evaluate PEmax (A) in line 8; If PEmax (A) > P target we
perform a placement action line-action or tree-action depending
on the number of child nodes of vt (downstream of et ). Each sub
function is described in more detail as follows.
1) construct-area: For each iteration, the temporary node et
is visited and the area network A is constructed with et and the
previous solution Mg . The current edge et is the temporary root
sensors of the area st . The terminal sensors of the area are any
sensors in Mg that are children of st . Note that this may be
empty at the start of the algorithm.
2) line-action: Given that our current subproblem satisfies
PEmax (A) < P target , if the next subproblem does not satisfy the
condition, our only option is place a sensor at child (vt ). So
Mg ← Mg ∪ et .
3) tree-action: Given that the algorithm up to now has placed
sensors on the two disjoint trees with roots with v1 and v2 We
must move as far up to the root as possible before we are forced to
place a measurement. This leads to two different types of actions:
a greedy strategy that is easy to implement and the optimal
strategy. The greedy strategy is implemented in practice and is
almost always equal to the optimal strategy, which is discussed
in Appendix H.
The greedy strategy chooses the area network with the smallest
PEmax (A). For example, in Figure 4, first assume PEmax (A0 ) and
PEmax (A00 ) < P target and PEmax (A1 ) > P target . In moving et
closer to the root, we must choose either A2 or A3 based on
the placement which has the smallest error.

7

outage detector with greedy placement is extremely efficient (only
O(|E|2 ) complexity).

…

For the remaining case studies only single area outages are
considered.

…

A3

…

…

…

…

A2

…

…

…

A1

…

…

…

A0

…

…

…

A '0

…

VII. D ISTRIBUTION S YSTEM C ASE S TUDY

A. PNNL Case Study

Fig. 4. (greedy-tree-action) Correct node traversal in the tree network assumes
max (A ) < P target and P max (A0 ) < P target . If P max (A ) < P target we
that PE
0
1
0
E
E
do nothing. Else, we generate and evaluate the error one of the 2|child(vt )|−1
0
00
area networks that can be constructed for example A1 and A1 .

R1−12.47−1
R2−12.47−3
R5−12.47−1
R5−12.47−4
R5−25.00−1

0.6

is computed as follows. For each
local hypothesis H ∈ H (Ai , f ), the conditional distribution
∆s| x̂ H ∼ N (µ(x̂, H), Σ(x̂, H)) is computed.
µ
PTo compute this, we introduce the following W (k) =
load forecast of
v∈desc(v) x̂(v) which computes the cumulative
P
all descendent vertices. Similarly W σ (v) = v∈desc(v) σ 2 (v) for
the forecast variances. For a given area, we evaluate the ∆si under
hypothesis H, assuming the root si and child sensor locations
child(si ) for a particular observed flow.
X
X
µ(x̂, H) = W µ (si ) −
W µ (e) −
W µ (e) (29)
e∈V (H)

e∈child(si )

Note that this is computed for a particular binary flow pattern.
Therefore, no outage edge upstream from the child sensors that
we consider. Likewise σ(x̂, H) is computed via W σ .
Finally, given the scalar distribution for ∆si |{x̂ H}, the
probability of missed detection for a scalar maximum likelihood
detector can be computed.
C. Optimality and Complexity
This discussion concerns only optimal-tree-action since it
guarantees optimality, although the greedy strategy output is
almost always identical.
Theorem 1. The bottom up placement solution Mg relying on
optimal-tree-action traversal solves OPT-3.
Complexity of evaluating the detector and the objective as well
as the placement algorithm is discussed in Appendix E. The main
results are summarized as follows:
• The worst case complexity of evaluating the detector for an
area and it’s missed detection PEmax (A) for an area of size
|E| is O(4|E| ). Evaluating only outages of size k is O(|E|k ).
max
• Given a fixed size to evaluating PE
(A) the greedy placement algorithm is of O(|E|) complexity while the optimal
strategy is of O(4log |E| ) complexity.
The detector and placement complexity in the worst case is
quite poor. However in any practice, this cost is averted using a
detector fixed hypothesis size. The outage model was of each
edge having some finite prior likelihood of outage. Therefore
a multi-edge outage of large size is much less likely. For this
reason, all k outages do not need to be enumerated. In practical
a single edge outage per area may be sufficient. Using a single

0.5
Sensor Density

B. Evaluating PEmax (A)
The objective PEmax (Ai )
+

0.4
0.3
0.2
0.1
0

0.1

0.3

0.5
0.7
Misdetection Error

0.9

Fig. 5. Outage detection performance for selected PNNL feeders. Square marker
denotes specified error target for optimization. Circular marker denotes empirical
mean missed detection error for hypothesis set.

We perform outage detection using a subset of the Pacific
Northwest National Laboratory test feeders [11]. Table I gives
overview of the feeders chosen for the simulation study. The
primary applications of the feeders, are heavy to light urban
networks, as well as suburban and rural networks. The climate
zones refer to (1) temperate (2) hot/arid (3) cold (4) hot/cold (5)
hot/humid according to [11].
TABLE I
PNNL T EST FEEDERS USED IN CASE STUDY
Network

Voltage

Climate Zone

Type

Size

R1-12.47-1
R2-12.47-3
R5-12.47-1
R5-12.47-4
R5-25.00-1

12.5 kV
12.47 kV
13.8 kV
12.47 kV
22.9 kV

1
2
5
5
5

suburban
urban
urban
commercial
suburban

613
52
265
643
946

1) Outage Model: For the PNNL feeders, outages are simulated by fuses and switches disconnected the downstream loads
from the substation feeders. For each network, all fuses and
switches are reduced to edges in the general tree network. The set
of loads which are disconnected by a fuse or switch disconnecting
are lumped to aggregate loads. For these loads, the mean load of
each group of fuses can vary.

8

B. General Line and Tree Network Sensitivity

κ = 0.01
κ = 0.1
κ = 0.2
κ = 0.3

Sensor Density

0.8
0.6
0.4
0.2
0

1

Sensor Density

1

κ = 0.01
κ = 0.1
κ = 0.2
κ = 0.3

0.8

0.3
0.5
0.7
Error Target Probability

0.9

(a)

Err−Mean: κ = 0.01
ErrTarget: κ = 0.01
Err−Mean: κ = 0.25
ErrTarget: κ = 0.25

0.8

0.4

Sensor Density

0.5
Mean Misdetection Error

0.3
0.2

0.4
0.2

0.1
0
0

0.6

0.05
0.1
0.15
Empirical Misdetection Error

0.2

0.1

(a)

0.3
0.5
0.7
Misdetection Error

0.9

(b)

Fig. 7. Hypothesis missed detection analysis: 7(a) error histogram for P target =
0.2; 7(b) tree network reduction to mean error.

record the value of each hypothesis error. The empirical maximum
error is close to the target 0.2. This makes sense because in
successively solving the feasibility problem, we will expand the
area network until the maximum error surpasses P target . However,
we see that in fact almost all of the missed detection probabilities
are less than the target. For this example in particular 34% of the
hypothesis are less than 1e−3 therefore essentially zero.
In comparing the mean and maximum errors for the range of
achievable values of κ and P target . The mean error is in on average
25% of the P target . The maximum error in the network and P target
very closely, therefore the optimization yields a very tight result.

0.6

VIII. C ONCLUSION

0.4
0.2

0.1

0.6

Empirical Count

2) Forecast Error Model: In [12] the authors present a rule of
thumb model for day ahead load forecasting at various aggregation levels based on smart meter data. The day ahead forecast
coefficient of variation, κ = σ/µ is shown to be dependent
on the mean load of the group. Many studies make simplified
assumptions on the relative forecast error. However, at the level
of small aggregates, the forecast κ can vary greatly on the size of
the aggregate and must beqtaken into account. A Reasonable fit
shown in [12] is κ(W ) = 3562
W + 41.9. This formula is used to
show that each set of islanded loads will have a different value
of κ(W ).
Figure 5 shows the application of the sensor placement algorithm for each network. Even though each networks represents a
different applications, they show somewhat similar performance
in terms of placement density. Averaged over each of the network
configurations, attaining 10% mean missed detection error is
possible by having 30% sensor density. Seen another way, we can
reduce the realtime monitoring of each fuse by 70% by tolerating
a small amount of error in the outage decision.

0

0.1

0.3
0.5
0.7
Error Target Probability

0.9

(b)

Fig. 6. The effect of optimization error target P target and relative forecast error
κ on both line (6(a)) and tree (6(b)) networks.

Figure 6 shows the sensitivity of the line and tree networks
under different simulation parameters. Both networks are of
length 100 nodes, the tree was generated using the method
in [10]. In an ideal line network with extremely high forecast
accuracy (κ = 1%), 1 or 2 sensors are required for extremely low
missed detection errors. This extreme situation does not occur in
practice, but serves as a baseline for realistic networks. From
Figure 6(a) we see that the required sensor density decreases
quite quickly vs. P target . The relation between sensor density and
P target is smoothly decaying.In comparison, randomly generated
tree networks require on average 2 − 3 times as many sensors to
achieve the same error target.
C. Missed Detection Error
Optimization (OPT-2) is meant to minimize the maximum
missed detection error among all possible hypothesis. This is
clearly can be too conservative of a requirement. Therefore it
is useful to understand the nature of the actual hypothesis missed
detection values that arise from a given sensor placement.
Figure 7(a) shows the distribution of missed detection probabilities for a tree network. Setting P target = 0.2, and κ = 0.3 we

We propose an outage detection framework combining power
flow measurements on edges of the distribution system along with
consumption forecasts at nodes of the network. We formulate
the detection problem and provide an optimal placement for the
maximum missed detection error metric. Finally, relying on feeder
information from the pacific northwest national labs as well as a
forecast error scaling law derived from Pacific Gas and Electric
smart meter data, we demonstrate our formulation.
R EFERENCES
[1] J.R. Aguero and A. Vargas. Inference of operative configuration of
distribution networks using fuzzy logic techniques - part i: real-time model.
IEEE Transactions on Power Systems, 20(3):1551– 1561, 2005.
[2] R. Balakrishnan and A. Pahwa. A computer assisted intelligent storm outage
evaluator for power distribution systems. IEEE Transactions on Power
Delivery, 5(3):1591–1597, 1990.
[3] Christopher M Bishop et al. Pattern recognition and machine learning,
volume 1. Springer New York, 2006.
[4] C. Fukui and J. Kawakami. An expert system for fault section estimation
using information from protective relays and circuit breakers. IEEE
Transactions on Power Delivery, 1(4):83–90, 1986.
[5] M. Kezunovic. Smart fault location for smart grids. IEEE Transactions on
Smart Grid, 2(1):11–22, 2011.
[6] Y. Liu and N.N. Schulz. Knowledge-based system for distribution system
outage locating using comprehensive information. IEEE Transactions on
Power Systems, 17(2):451–456, 2002.
[7] Sentient Energy LLC. Mm3 intelligent sensor, 2016.
[8] S.T. Mak and N. Farah. Synchronizing scada and smart meters operation for
advanced smart distribution grid applications. Proc. IEEE PES Innovative
Smart Grid Technologies (ISGT), pages 1–7, 2012.
[9] R.A.F. Pereira, L.G.W. da Silva, M. Kezunovic, and J.R.S. Mantovani.
Improved fault location on distribution feeders based on matching duringfault voltage sags. IEEE Transactions on Power Delivery, 24(2):852–862,
2009.
[10] Alexey Rodionov and Hyunseung Choo. On generating random network
structures: Trees. In Computational Science?ICCS 2003, pages 879–887.
Springer, 2003.

9

[11] Kevin Schneider, Yousu Chen, David Chassin, Robert Pratt, David Engel,
and Sandra Thompson. Modern grid initiative distribution taxonomy final
report. arXiv preprint arXiv:1404.0058, 2008.
[12] Raffi Sevlian, Patel Siddarth, and Ram Rajagopal. Day ahead electricity load
forecasting on varying levels of aggregation. Power Engineering Letters,
2014.
[13] D. Srinivasan, R.L. Cheu, Y.P. Poh, and A.K.C. Ng. Automated fault
detection in power distribution networks using a hybrid fuzzy–genetic algorithm approach. Elsevier Engineering Applications of Artificial Intelligence,
13(4):407–418, 2000.
[14] Z. Sumic and R. Vidyanand. Fuzzy set theory based outage determination.
Proc. of 1996 International Conference on Intelligent Systems Applications
to Power Systems, pages 204–208, 1996.
[15] J. Zhu, D.L. Lubkeman, and A.A. Girgis. Automated fault location and
diagnosis on electric power distribution feeders. IEEE Transactions on
Power Delivery, 12(2):801–809, 1997.

A PPENDIX
A. Nomenclature Table
T

Tree network representation of a distribution
feeder
(V, E)
Vertex and edge set of tree T
V (H)
Set of vertices that are connected to root under
outage hypothesis H.
desc(v)
Descendants of vertex v.
child(v)
Children of vertex v.
xn , x
Scalar load and forecast value at vertex v
n , 
Forecast residual for load l(v)
σn2 , Σ
Forecast residual variance and covariance matrix.
H1
Single outage hypothesis and element and set.
Hk
k-outage hypothesis.
Hu
Unique hypothesis where no edges are downstream of any others.
A, A, A+
Local area network A ∈ A; Pruned areas under
binary flow processing.
Set of local area hypotheses post binary flow
Hu+ (Ak , f )
processing.
Hk,i(k)
i(k)th hypothesis in area Ak . Used to reconstruct global hypothesis Hi .
M
Sensor placement (M ⊂ E)
s
Set of observations on edges of network
rij
Acceptance region for pairwise test of hypotheses: Hi and Hj
RH (H)
Acceptance region of hypothesis H over all
alternatives in H.
PE,C (H, M), Probability of error (E) and correct detection
(C) for hypothesis H, under placement M.
PEmax (A)
Maximum probability of incorrect detection
over all hypothesis error in area A.
PCmin (A)
Minimum probability of correct detection over
all hypothesis error in area A.
B. MAP Detection for Outage Hyptheses
Here we show how the general MAP detector rule can be
evaluated for where we combine edge flows s, load forecasts x̂
and candidate outages H.
Ĥ = arg max Pr (H | s, x̂)

(30)

H∈Hk

Pr (s, x̂ | H) Pr (H)
Pr (s, x̂)

(31)

= arg max Pr (s, x̂ | H) Pr (H)

(32)

= arg max
H∈Hk
H∈Hk

= arg max Pr (s | x̂, H) Pr (x̂ | H) Pr (H)

(33)

H∈Hk

= arg max Pr (s | x̂, H) Pr (x̂) Pr (H)

(34)

H∈Hk

= arg max Pr (s | x̂, H) Pr (H)

(35)

H∈Hk

= arg max Pr (s | x̂, H)

(36)

H∈Hk

Lines (30) - (32) convert the MAP detector to a likelihood
detector with prior weights. Line (33) conditions on the load
forecast x̂. Since x̂ does not depend on the outage hypothesis,
(only s does), the term can be removed leading to (35). In (36),

10

we assume a uniform prior over all hypotheses, however this does
not have to be the case.
Given the assumption of each edge going into outage with some
fixed prior probability, a single edge outage hypothesis should
have Pr (H) = ρ, while a k outage condition should have a
prior of Pr (H) = ρk . This motivates enumerating fewer outage
hypotheses when evaluating Hu in practice.

we have that: H+ ({1 0}) = {E(b1 )}. We see that splitting the
hypotheses based on flow information, conserves the search space,
since Hu+ ({1 1}) ∪ Hu+ ({1 0}) = Hu .
4) Tree T1 : For tree T1 , we have:

C. Extended Discussion of Recursive Evaluation of Hu

D. General Hypothesis Decoupling

s1

s1

b1

(a)
Fig. 8.
3.

b1

b1

s1

b2

b3

b2

(b)

s2

b3

(c)

8(a) Worked example 1. 8(b) Worked example 2. 8(c) Worked example

We present here additional worked out examples, that show
how the recursive definition can enumerate all hypotheses and
focus on some corner cases that must be defined. Recall the
recursive definition:

!
[
^
Hu (b) = E(b) ∪ 
Hu (b) 
b∈P(child(b))

b∈b

1) Example 1 (Figure 8(a)): This is the simplest case to
evaluate and is:
Hu = E(b1 ) ∪ ∅
The null hypothesis set arises from evaluating P(d(b1 )) = ∅, since
b1 has no children.
2) Example 2 (Figure 8(b)): This is the simplest case to
evaluate and is:
Hu = {E(b1 ) ∪ ∅ ∪ Hu (b2 ) ∪ Hu (b3 ) ∪ Hu (b2 ) × Hu (b3 )}
= {E(b1 ) ∪ ∅ ∪ {∅ ∪ E(b2 )} ∪ {∅ ∪ E(b3 )}∪
{∅ ∪ E(b2 )} × {∅ ∪ E(b3 )}}
= {∅ ∪ E(b1 ) ∪ E(b2 ) ∪ E(b3 ) ∪ (E(b2 ) × E(b3 ))}
This example is reduced to it’s final form in eq. (13), in Section V-A. However, the following equalities are omitted in the
enumeration:
∅∪∅=∅

(37)

∅×∅=∅

(38)

∅ × ei = ei

(39)

Hu (b1 ) = {∅ ∪ E(b1 ) ∪ E(b2 ) ∪ Hu (b3 ) ∪ E(b2 ) × Hu (b3 )}
Hu (b3 ) = {∅ ∪ E(b3 ) ∪ E(b4 ) ∪ E(b5 ) ∪ {E(b4 ) × E(b5 )}}

These two cases provide the intuition for a general procedure
which is as follows: Given binary information from flows, all
areas Ak with rooted sensor with sk = 0, are discarded in
generating a local hypothesis. Each node in the branch graph is
assigned a label, l ∈ L L = {P, Z, U } for (P ) positive, (Z) zero,
and (U ) undetermined branches. These are defined as follows:
Positive Branch: Branch is upstream from a sensor measuring positive flow, therefore can never be evaluated in
any outage hypothesis. Also, it’s immediate parent branch
cannot be enumerated either.
Zero Branch: This branch is directly upstream from a
zero measurement therefore it’s edges must always be
enumerated in any outage hypothesis.
Undetermined Branch: This branch has no information,
so is enumerated without any restriction.
This definition leads to the following procedure to enumerate
H+ (Ai , I{child(si )>0} ). First each branch-node is labeled with the
following procedure:
Initialization Branch with descendent sensor (1) s > 0
assigned label P and (2) s = 0 assigned label Z, and (3)
no descendants assigned label U .
Update Given a current branch node b and the set of
children, the node is assigned as follows: (1) If any descendent node is labelled P then it must be labelled P . (2)
If descendants are U and Z, then it must be labeled U .
Once the the branch-nodes are labeled, enumerating
H+ (Ai , I{child(si )>0} ) can be done recursively using the
following rules:
Positive Rule Never enumerate a branch (E(b)) with
positive flow label (P ).
Zero Rule When evaluating the recursive definition H(b)
on an element of the power set. If any descendent is labelled
Z, only evaluate product set elements that contain this
branch.

d+1
b1

The final relation leads to ∅ × E(b) = E(b).
3) Example 3 (Figure 8(c)): Consider the two binary flow
indicators I{s1 ,s2 >0} = {1 1} and {1 0}. In the first case, we
have the following product set:

d
b2

b3

s0

H+ ({1 1}) = {E(b2 ) ∪ ∅1 } × {E(b3 ) ∪ ∅2 }

b4

We use the fact that ∅ × E(b) = E(b) and that the product
∅1 × ∅2 = ∅, which is the global null hypothesis from the naive
enumeration in Example 2. Similarly, enumerating the {1 0} case,

b5
s1

= {E(b2 ) × E(b3 ) ∪ ∅1 × E(b3 ) ∪ E(b2 ) × ∅2 ∪ ∅2 × ∅2 }
= {E(b2 ) × E(b3 ) ∪ E(b2 ) ∪ E(b3 ) ∪ ∅}

1

(a)

2… K

d-1

…
…

…

…

(b)

Fig. 9.
9(a) General network reduced to individual branches. 9(a) Worst case
tree network of depth D and K children for each vertex.

11

TABLE II

F. Proxy Function Optimization

Binary Flow Id(si )>0}

Branch Labels

Hypotheses Branches

0, 0

U , Z, U , U , Z

0, 1
1, 0
1, 1

P , Z, P , U , P
P , P , U, U, Z
P , P , P , U, P

b1 , b2 , b2 × b3 ,
b2 × b5 , b2 × b4 × b5
b2 , b2 × b4
b3 , b5 , b4 × b5
b4

The placement problem OPT-1 will output the optimal sensor locations and minimizing maximum missed detection error
α? (M? ), as:
α? (M? ) = min

max PE (H, M)

|M|=M H∈Hu

An example local area is provided in Figure 9(a). The general
method is applied under each of the binary flow cases, where
the results are shown in Table II. The method is applied to each
binary flow, and the branches to be enumerated are given.

This can be approximated by using the decoupling of hypotheses
in different areas. Recall the solution to OPT-1 repeated above, is
the distributed detector in Algorithm 1 where each area performs
a local hypothesis Ĥ, . . . , ĤM . The complete hypothesis is only
correct if every local detection output is correct. So for any
hypothesis, we have following lower bound:
min P r(Ĥ = H;M)

H∈Hu

E. Complexity Analysis



In analyzing the complexity of various algorithms we assume
the tree in Figure 9(b). Each vertex has K children and is of
depth D. It can be shown that the number of edges is related to
D
−1
.
these quantities by E = KK−1
max
1) Evaluating PE (A): For simplicity, we focus on a binary
tree, so K = 2 and |E| = 2D − 1. The number of possible
hypotheses at each depth C(d) using this network is related
recursively as the following:
K  
X
K
C(d + 1) =
C n (d + 1)
(40)
n
n=1
K

= (C(d) + 1) − 1

(41)

This can be derived directly from (9).
d
In the binary tree case, it’s simple to show that C(d) = 42 −1.
Therefore the number of hypotheses are double exponential in
the depth of the tree. For the entire tree, this leads to the root
D
node value of C(D)
= 42 − 1 which is 4(|E|+1) − 1. Therefore

|Hu | = O 4|E| , exponential in the size of the graph.
This cost may be averted due to the following:
• Fixed multi-hypothesis size. The MAP detector requires a
prior probability of hypotheses. Since multiple edge outages
are less likely, they don’t always have to be enumerated.
For example, considering only single edge outages leads to
|Hu | = O (|E|) complexity for an area.
• Small area sizes, and Binary Flow segmentation. The number
of hypotheses are exponential in |E| for an area. Given many
sensors, this can divide the number of edges for an area
considerably. Additionally, the binary flow information from
downstream sensors will on average divide each H+ (A) by
a factor of 2|d(s)| .
The following analysis is in terms of the evaluation of
PEmax (A) since we assume appropriate approximation of this
function has been performed.
2) Evaluation of Algorithm 2 using greedy strategy: The
greedy strategy will have to evaluate all 2K subproblems at
each vertex, and choose the minimum PEmax (A). The worst case
complexity is therefore O(|E| 2K ), which reduces to O(|E|),
since K is a constant.
3) Evaluation of Algorithm 2 using optimal strategy: The
optimal strategy will expand the problem size by a factor 2K
at each vertex. The number of sub-problems to consider after
a depth of D will be (2K )D which for a binary tree becomes
O(4log |E| ).

= min 
H∈Hu

≥
=

Y

P r(Ĥi = Hi ; M) (42)

∀Ai , Hi

Y
∀A∈A


Y

min P r(Ĥ = H; A)
H∈H(A)

PCmin (A).

(43)
(44)

∀A∈A

Line (42) follows from the decoupling of the decentralized
detector. The overall MAP decision can be correct only if each
local MAP decision is correct. For any H ∈ Hu the probability
of each area making a correct decision is always greater than
the worst case probability of correct decision for each area. We
interchange the sensor placement and area notation since local
areas are constructed from sensor placements. Here PCmin (A) is
the minimum probability of correct detection within a local area
A. This lower bound can be used to first upper bound the optimal
α? . Finally, only an approximate solution to the upper bound is
formulated.
α(M? ) = min

max PE (H, M)

(45)

max (1 − PC (H, M))

(46)

|M|=M H∈Hu

= min

|M|=M H∈Hu

= 1 − max

min PC (H, M)
Y
PCmin (A)

|M|=M H∈Hu

≤ 1 − max

|M|=M

(47)
(48)

∀A∈A

≈ 1 − max

min PCmin (A)

(49)

= 1 − max

max (1 − PEmax (A))

(50)

|M|=M ∀A∈A

=

|M|=M ∀A∈A
min max PEmax (A)
|M|=M ∀A∈A

(51)

Optimization OPT-1 is identical to (46), since the probability of
a single hypothesis error can be exchanged for it’s compliment.
The min-max to max-min change is due to the negative sign
in 47. In line 47, instead of maximizing the minimum correct
probability over all hypotheses we maximize Q
a computationally
tractable lower bound which is the product ∀A∈A PCmin (A).
In 49 we introduce a close approximate solution which is the
following: Instead of maximizing the product of PCmin (A) for
each A, it is sufficient to maximizing the minimum of each
PCmin (A) Experimentally the two solutions have been shown
identical for a large number instances, and only sub-optimal in a
small number of cases where the gap is small.

1

1

0.8

0.8

Lemma 1. An equivalent definition is
\
R(Hi ) =
ri,j .

(55)

j:Hj ∈H

0.6

0.6

0.4

0.4

0.2

0.2

Proof: Using the definition of the right hand side, we have
\
ri,j = {s : s ∈ ri,1 ∩ . . . ∩ s ∈ ri,N }

!

A

P Cm i n(A, M)

12

j∈H

= {s : Pr(s|Hi ) ≥ Pr(s|H1 ) ∩ . . .
0
0

0.5
maxA P Cmin(A, M)

(a)

1

0
0

0.2

0.4
0.6
0.8
maxA P Cmin(A, M)

∩ Pr(s|Hi ) ≥ Pr(s|HN )}

1

= {s : Pr(s|Hi ) ≥ Pr(s|Hj ) ∀Hj ∈ H}

(b)

= RH (Hi ).

Fig. 10.
10(a) Brute force placement evaluation where the two objectives are
identical. 10(b) Brute force placement evaluation where the two objectives differ.

Experimentally the two solutions have been shown identical
for a large number instances, and only sub-optimal in a small
number of cases where the gap is small. Figure 10(a), 10(b),
shows a pair of randomly generated trees with N = 15 nodes
with random loads and a forecast coefficient of variation of 0.02.
In both cases, the bottom up placement was used to determine
Mg , where |Mg | = 5.

15
A brute force enumeration of all
5 placements is evaluated
Q
for max∀A∈A PCmin (A, M) and ∀A∈A PCmin (A, M).
In both cases, there is a strong correlation between the two
solutions. The two solutions are not however equal Figure 10(a),
the solutions are identical, while in 10(b), the two solutions differ
by 7.2%. Intuitively they should intuitively be very close to each
other. Decreasing one area error will increase the other area’s
error due to the monotonic growth of PEmax (A) and the finite
tree size. Therefore, maximizing the product of all the terms tends
to a solution where each area error is as close to each other as
possible. Minimizing the maximum error often leads to such a
solution, since we must trade off one area error for another.

Note, that this statement is for the maximum likelihood classifier. Under an arbitrary classifier, a procedure of constructing
one-to-many classifier will lead to ambiguity. See [3] (pg. 183)
for discussion.
Conjecture 1. Given a ML detection problem with a set of
hypothesis of the form: sk ∼ N (µk , σk2 + ∆) for k = 1, . . . , K.
The missed detection error for each hypothesis will monotonically
increase w.r.t ∆.
This is seen to hold with 200,000 random problem instantiations. We now state Lemma 2.
Definition 2. Two area networks are nested A ⊂ A0 if the vertices
of each area V , V 0 are such that V ⊂ V 0 .
Lemma 2. Given two area networks A and A0 where A ⊂ A0 ,
PEmax (A) ≤ PEmax (A0 ).

G. Proof of Theorem 1
We prove Theorem 1 by showing the following:
1) The objective function PEmax (A) monotonically increases
for nested areas.
2) Algorithm 2, will recover the solution to OPT-3
First we prove propositions 1 and state a conjecture shown to
hold in large scale simulation experiments. These are needed to
prove Lemma 2 which is needed to prove Theorem 1.
First consider the following:
Definition 1. For a single pairwise test, Hi vs Hj we have the
following decision region:
ri,j = {s ∈ RM : Pr(s|Hi ) ≥ Pr(s|Hj )}.

(52)

The observation space is therefore partitioned into two regions.
So the detector is the following:
(
Hi , s ∈ rij
Ĥ =
(53)
Hj , s ∈
/ rij .
For the one-to-many ML test: Hi vs ∀Hj ∈ H, we have an
acceptance region defined as:
RH (Hi ) = {s ∈ RM : Pr(s|Hi ) ≥ Pr(s|Hj ) ∀Hj ∈ H}. (54)

(a)

(b)

Fig. 11. 11(a) Case 1 showing growth by adding new nodes by moving terminal
sensor down. The conditional pdf ∆s|H ∀h ∈ H does not change. However the
acceptance region shrinks from RH to RH∪x . 11(b) Case 2 showing growth by
adding new nodes by moving root sensor up. The conditional pdf ∆s0 |H ∀h ∈ H
0
will change. Again, the acceptance region shrinks from RH to RH∪x
.
max
Proof: Given some α∗ = Perr
(A), which is the maximum
missed detection probability of the local hypothesis in area A
which is evaluated at some hypothesis H ∗ . We aim to show that
for an enlarged area A0 , the error probability for H ? will always
be larger, which is quite intuitive. Therefore the maximum error
PEmax (A0 ) regardless if H ∗ maximizes the missed detection in
the enlarged area.
Expansion of A is analyzed in two cases:
Case 1 Terminal sensors expand downstream (away from
v0 ) shown in Figure 11(a).
Case 2 Root sensor of A moves upstream (closer to v0 )
shown in Figure 11(b).

13

We use the following shorthand: Hypotheses for area A and
A0 : H , H(A), H ∪ xi , H(A0 ). The set xi differ in how the
area is enlarged, where i = 1, 2 for case 1 and case 2. Therefore
under case 1, and 2 we have RH∪x1 (Hi ) and RH∪x2 (Hi ). Now
we show how the effective measurement distribution (as defined
in (28)) and acceptance regions changes under each case.
µ0i

= µi
Case 1 For all hypothesis Hi ∈ H we have that
2
and σ 0 i = σi2 . The
distribution
∆s|H
is
unchanged.
Given
i
T
that RH (Hi ) =T j:Hj ∈H rij , the new acceptance region is
RH∪x1 (Hi ) = j:Hj ∈H∪x1 rij , with rij from the original
alternatives unchanged.
Case 2 For all hypothesis Hi ∈ H we have that µ0i = µe +µi
2
and σ 0 i = σe2 + σi2 . The distribution and acceptance region
change ∆s|Hi → ∆s0 |Hi . The
T new acceptance
T T region is the
0
following: RH∪x2 (Hi ) = { j:Hj ∈H rij
} { j:Hj ∈H rij },
where the acceptance regions under the previous area alternatives are now different.
To see why the distribution ∆s|Hi changes, first recall that:

∆si |Hk ∼ N 


X

µ(v) − µT ,

v∈Vi \Vk

µk , σk2

∼N

X



∀H ∈ H

(57)

The terms µT and σT2 are the sum of loads forecasts and
variances of all terminal sensors. Now moving the root node
upstream leads to:

X

s0i |Hk ∼ N 

X

µ(v) − µT ,

v∈Vi0 \Vk

σ 2 (v) − σT2  (58)

v∈Vi0 \Vk


∼ N µe + µi , σe2 + σi2 ∀H ∈ H.

(59)

Therefore changing the position of si so as to add additional
vertices will increase every original hypothesis mean and variance
by the same amount.
Now consider Case 1 first, where we merely add new alternatives, keeping the distributions of ∆s|H unchanged. Here we
have:
Pr(∆s ∈ RH∪x (H ∗ )|H ∗ true)
\
= Pr(∆s ∈
ri,j | H ∗ true)

(60)
(61)

j:Hj ∈H∪x

= Pr({∆s ∈

\

ri,j } ∩ {

j:Hj ∈H

\

∆s ∈ ri,j }| H ∗ true)

j:Hj ∈x

(62)
≤ Pr(∆s ∈

\

∈ ri,j |H ∗ true)

(63)

Hj ∈H

= Pr(∆s ∈ RH (H ∗ )|H ∗ true).

Pr(∆s0 ∈RH∪x |H ∗ true)
≤ Pr(∆s0 ∈ RH (H ∗ )|H ∗ true)

(65)

= Pr(∆s0 − µe ∈ RH (H ∗ ) − µe |H ∗ true)

(66)

∗

≤ Pr(∆s ∈ RH |H true).

(67)

The inequality in line 65 uses the identical procedure in 61 63. In line 66 we are merely shifting the gaussian ∆s and the
acceptance region by µe using a shorthand notation. This can be
done since the MAP test is scalar. Finally the inequality in line
67, follows from conjecture 1.
We can now prove Theorem 1.
Proof: The bottom up solution Mg moved to the root node
enlarging each area network so that each PEmax (A) < P target but
any further up will violate the target area. Consider some other
method produces a solution M0 which minimizes the number of
sensors the error constraint, where |M0 | < |Mg |. This implies
that some area must increase in size, as compared to the Mg
solution, and from Lemma 2, some area will violate the error
constraint.

σ 2 (v) − σT2  (56)

v∈Vi \Vk



σe2 in mean and variance. This implies that:

(64)

Line 61 defines the area RH (H ∗ ) using proposition 1. This is
split into the the intersection of two separate events using our
definitions of H and H∪x. Next we use the fact that Pr(A∩B) ≤
Pr(A). Therefore if Pr(∆s ∈ RH (H ∗ )|H ∗ true) ≤ Pr(∆s ∈
RH∪x2 (H ∗ )|H ∗ true) then PEmax (A) ≤ PEmax (A0 ).
We next prove Case 2 where not only are more alternatives
considered for H ∗ , but ∆s|H ∗ is translated by fixed amount µe ,

H. Greedy and Optimal Tree Action
optimal-tree-action: The correct action at a node-junction is
to enumerate each 2|child(vr )|−1 possible trees and process them
until only one remains closest to the root. In the example in
Figure 4, we must process to the root node processing both A2
and A3 in parallel as separate problem instances, with its own vt
and M g . This is in contrast to the greedy strategy that chooses
one placement and moves on. Each problem instance is then
processed, until the area objective function violates P target . All
but one problem instance is kept; the one where vt was closest
to the root vertex.
It turns out that the greedy-tree-action and the optimal-treeaction procedures are in practice extremely close as discussed
in Appendix H. Algorithm 2 can only implement this technique,
since we do not grow the search space with multiple bottom up
scenarios.
The bottom up placement using greedy-tree-action relies on
moving the current node as close to root as possible while keeping
the error < P target . At a juncture, recall that the current network
is chosen as the one which minimizes the maximum error, and
continues with that choice. To see why this is sub optimal,
consider Figure 12 shows a typical subtree where we have the
following events:
1) (Figure 12(a)) The bottom up algorithm will evaluate
target
target
PEmax (AL
and PEmax (AR
.
1) < P
1)<P
2) (Figure 12(b)) Move onto evaluating the combined area network with the parent node. Evaluating PEmax (A2 ) > P target ,
we must choose in a greedy manner via greedy-tree-action.
max
3) (Figure 12(c)) Evaluating both PEmax (AL
(AR
3 ),
3 ) and PE
L
max
R
target
max
. The greedy
where PE (A3 ) < PE (A3 ) < P
R
choice will keep AL
3 and discard the A3 .
4) (Figure 12(d)) The optimal choice is in fact AR
4 since
target
max
R
PEmax (AR
)
<
P
<
P
(A
).
4
4
E
The greedy choice will choose AL
3 and be forced to place a
sensor in AL
4 , while the optimal can continue upstream. The
following numerical example will lead to this: µi = 1, ∀i and
σ 2 = {0.0599, 0.0125, 0.0835, 0.0945, 0.0906, 0.0607} with
P target = 0.1923.

4

4

6

4

6

6

14

L
PEmax(A
1 4)

1PE

3

2

3
4

5

3

5
6

3
4

2

5

2

4

1

2

2
3
5

3

5

6

4

6

4

2

4 3

4

4

6

6

PEmax(AL3)

L
PEmax
1 (A 4)

5

3

1

6
PEmax
(AL3)

PEmax(AR3)

4

5

6

PEmax4 (AL1)

PEmax(AR3)

3

2
3

5

5

4

6

R
PEmax
4 (A 1)6

6

3

5

6

4

6

σ2L + ∆
σ2R + ∆

0.1

(d)

5

3

5

3

Ptarget
0.02

1

1

0.04

∆

0.06

0.08

0.1

(a)

2

5

PEmax(AR1)

TABLE III max L
(A 3)STUDYPEmax(AR3)
PNNL T EST FEEDERS USEDPEIN CASE
H+ (A, b)

µk

σk2

max (A)
PE

s2 > 0,
s5 > 0
s2 > 0,
s3 > 0
s1 > 0,
s3 > 0
s1 > 0,
s3 > 0

e3 , e4 , ∅

1, 2, 3

0.0125, 0.1031, 0.1637

0.1083

e5 , e6 , , ∅

1, 2, 3

0.0125, 0.0960, 0.1905

0.0961

e3 , e4 , ∅

2, 3, 4

0.0724, 0.1558, 0.2504

0.1885

e5 , e6 , , ∅

2, 3, 4

0.0724, 0.1630, 0.2236

0.1960

Notice that in the hypothesis means and variances, we have the
following:
L
µk (AL
4 ) = µ(v1 ) + µk (A3 )
R
µk (AR
4 ) = µ(v1 ) + µk (A3 )
L
σ 2 (AL
4 ) = ∆ + σk (A3 )
R
σ 2 (AR
4 ) = ∆ + σk (A3 )

Where µ(v1 ) = 1, and ∆ = σ 2 (v1 ) = 0.0599. The translation
of mean and variance causes the maximum error over an area to
switch from AL to AR . Recall that conjecture 1 stated that the
maximum error in such a case will monotonically increase with
respect to some translation in variances. Regardless, there is no
domination between any pair of triplets, whereby one will always
be greater than another under the same translation.

6

4

6

L ) in Figure
R ) where the maximum hypotheThis can
be (A
seen
13(a)
PEmax
PEmax(A
3
3
sis error between the tuples is shown with respect to translation ∆.
As indicated, any ∆ > 0.02 will cause their ordering to change,
with the counterexample shown to be beyond this point.
However, we should not that although the transition does occur,
the gap is quiet small so any realistic gap will be very small. Since
R
P target is between P (AL
4 ) and P (A4 ) it is very unlikely to occur.
In finding a counterexample 10000 monte carlo runs produced
5 examples. For this reason, the greedy and optimal placement
strategies will have identical outcomes of random instances.

Flow

AR
4

4

4

AL
3

AL
4

5

Fig. 13. The maximum probability of
error over three hypotheses as a function of
5
5
3
3
R
a translation of
each hypothesis variance. At the point ∆ = 0, P (AL
3 ) < P (A3 ),
R
and in point ∆ = 0.0599, P (AL
4 ) > P (A4 )

5

Area

AR
3

2

2

The triplet of scalar hypotheses which cause this are shown in
4III.
6
6
Table
4
6
4
6

PEmax(AL1)

2

0.05
0

PEmax(AR4)

Fig. 12.
12(a) Both areas have maximum error smaller than target error:
max (AL )1 < P target , P max (AR ) < P target . 12(b) The area’s are
PE
1
1
1
E
1
max (A ) > P target
combined, and tested where PE
. 12(c) The greedy choice
2
L
max
L
max
R
will choose A3 as the candidate: PE (A3 ) < PE (A3 ) < P target . 12(d)
2
2
max
max (AR ) < P target
2 (AL ).
2
< PE
The correct choice is AR
4 since PE
3
3
3

0.2
0.15

6

1

5

1

2 1

(c)

3

1

(b)

1

3

5

3

PEmax(AR4)

0.25

3

2 1

1
2

5

5

(a)

PEmax(A2)

2

4

P4 Emax(AR61)

PE4max(AL1)6

2
3

3

5
6

1

1

1

PEmax(A2)

21

21

max(AL )
P0.3
E
4

max(AR )
4

