On the Balance of Meter Deployment Cost and NILM Accuracy

1 Introduction

Real-time monitoring on/off states of electrical appliances in buildings is a crucial component for smart control systems. Deploying smart meters on every appliance guarantees highfidelity appliance state monitoring [Jiang et al., 2009], but the cost is unbearably high especially in the case of modern commercial buildings with a huge number of appliances.

An alternative approach is Non-Intrusive Load Monitoring (NILM) [Hart, 1992]: at the electrical feed of the appliances, a meter is deployed to disaggregate their on/off states by pattern analysis in temporal or frequency domain. Early works on NILM took advantage of steady-state power changes [Sultanem, 1991; Marceau and Zmeureanu, 2000]. The key idea is to detect jumps in active/reactive power patterns specific to individual appliances, therefore it is more suitable for steady, finite-state appliances. Harmonic analysis was used to identify continuously variable appliances [Laughman et al., 2003; Lee et al., 2005; Berges et al., 2009]. Latest machine learning techniques like support vector machine [Patel et al., 2007], neural networks [Roos et al., 1994], sparse coding [Wang et al., 2014], pattern recognition [Farinaccio and Zmeureanu, 1999] and a number of unsupervised learning methods [Shao et al., 2013; Kolter and Jaakkola, 2012; Parson et al., 2012] all found applications in the field of NILM.

∗This work was supported in part by the National Basic Research Program of China Grant 2011CBA00300, 2011CBA00301, the National Natural Science Foundation of China Grant 61033001, 61361136003.

†This work was prepared or accomplished by Bangsheng Tang in his personal capacity.

While most aforementioned papers strive for better NILM algorithms for accuracy and efficiency, scalability remains a major limitation of NILM. In a single-meter NILM system, monitoring error increases as the power system scales up. Multiple NILM meters are required in a complex power system. Considering the cost of the meters including deployment and maintenance, it is desirable to use as few meters as possible while attaining a satisfactory monitoring accuracy. In contrast to the extensively investigated NILM algorithms, the problem of balancing deployment cost and monitoring accuracy lies greatly unexplored. Only few prior works studied this problem (cf. [Jung and Savvides, 2010; Hao et al., 2012; Bellala et al., 2012]). In this paper, we investigate the quantitative tradeoff between the meter deployment cost and the NILM state monitoring accuracy. In particular, we propose:

• Clearness function For any power load tree with a meter located at the root, a clearness function takes values in [0, 1], where higher value indicates higher monitoring accuracy. This notation induces a quantitative criteria for monitoring accuracy.
• Smart meter deployment problem (SMDP) That is, finding a meter deployment satisfying the quantitative monitoring accuracy requirement with minimum number of meters. We show that SMDP is NP-hard and then present a PTAS to approximately solve SMDP, which is highly efficient for practice use.
• A framework for tradeoff The tradeoff problem could be decomposed into two subproblems: 1) design a clearness function for the underlying power model; 2) solve the SMDP given the clearness function. This framework

is generic in that it can easily incorporate with various NILMmethods, and algorithmic results and quantitative relations will carry over naturally.

2 A Framework for Accuracy-Cost Tradeoff

This section devotes to the high-level idea of our framework for tradeoff. We assume that the power network structure is a priori knowledge, which is for example obtainable from the blueprints [Jung and Savvides, 2010; Shao et al., 2013]. Following [Parson et al., 2012], we assume access to some basic prior information of an appliance's power pattern. However, the on/off correlation between the appliances is unknown since it is closely related to user behaviors.

2.1 Power Load Tree

Power network in a commercial building typically has a treelike structure, which is called power load tree (PLT) [Jung and Savvides, 2010] and denoted by T (V,E). The root of a PLT is the power entrance of a building. Each internal node corresponds to a power break or an outlet, and each leaf node corresponds to an electrical appliance. There is an edge ei,j ∈ E, if power flows through an internal node vi ∈ V to another node vj ∈ V . Let ne be the total number of leaves (namely, electrical appliances) and n = |V | be the number of nodes in T (V,E). State monitoring is to track the on/off states of the n appliances in real-time, i.e., a vector sv ∈ {0, 1}ne . NILM methods have been employed in the task of tracking sv accurately with multiple meters placed on nodes in PLT.

2.2 Multi-meter NILM

Since NILMmeters measure power profiles, like current and voltage, which are linearly additive. By assuming the meters are reliable and accurate, a PLT with a (partial) deployment D ⊆ V could be decomposed into several mono-meter trees. Each mono-meter tree contains exactly one meter deployed at its root. Also each appliance in the original PLT is assigned to a mono-meter tree rooted at a closest meter-monitored node. Let T (u) = (V (u),E(u)) be the subtree of T rooted at u. For a meter deployed at u ∈ D, the mono-meter tree generated from this meter is Tm(u) = (Vm(u),Em(u)), where Vm(u) = V (u) \ {w | w ∈ V (v), v ∈ D ∩ V (u) \ {u}}, Em(u) = {(v,w) | (v,w) ∈ E, v ∈ Vm(u),w ∈ Vm(u)}. Fig 1 gives an example of mono-meter tree decomposition.

Since the correlation between appliances is unknown, the on/off appliance states on mono-meter trees are decoded independently. By such a decomposition, the original multi-meter on/off decoding process is separated into several independent single-meter on/off decoding process. Apparently, the multimeter decoding is acceptable only if the decoding accuracy on each mono-meter tree is good enough.

2.3 Tradeoff Framework

The tradeoff between monitoring cost and monitoring accuracy can be easily seen from the mono-meter tree decomposition. Deploying more meters at appropriate positions will reduce the size of each meter's appliance set. It also reduces the probability of state ambiguity, which helps improve state decoding accuracy. To balance accuracy and cost, we propose a tradeoff framework consisting of two parts, as in Fig 2 - clearness function design and meter deployment.

Clearness Function Design Clearness function is a quantitative indicator of decoding quality of mono-meter trees. It depends on the underlying NILM model, including power patterns of the appliances, decoding algorithm and accuracy requirements (Fig 2). For a given mono-meter tree, the clearness function takes values in [0, 1], and a higher value indicates a higher chance of correct decoding. For any deployment scheme, monitoring quality could be measured by computing the clearness function for all mono-meter trees.

Meter Deployment Given the clearness function as a black box, accuracy requirement can be stated as clearness function on every mono-meter tree evaluates to a large enough value. For any given accuracy requirement, Smart Meter Deployment Problem(SMDP) is the problem of finding a deployment scheme with minimum number of meters while satisfying the requirement. Later in this paper, we formalize this problem and propose an efficient and effective solution.

3 Clearness Function Design

Construction of clearness function varies in different NILM models. Many previous approaches on NILM [Leeb et al.,

1995; Parson et al., 2012] assumed specific power patterns and proposed decoding algorithms accordingly. In this case the clearness function for each mono-meter tree could be calculated by off-line simulations. However it is more common that the NILM model, specially the decoding algorithm, is not well-defined beforehand, whereby the design of clearness function would be radically different.

For a mono-meter tree Tm(v), denote the set of appliances in it as A(v). Let sv = {0, 1}|A(v)| be the appliance state vector of Tm(v). For a fixed state sv , Rv (sv ) is the set of all possible readings on a single meter. Mathematically, we say a reading Rv is ambiguous if there exist some sv1 ̸= sv2 , s.t. Rv ∈ Rv (s1 v ) ∩Rv (s2 v ), i.e., more than one state maps to a same reading. Otherwise, if Rv has a unique pre-image sv , we say Rv is clear.

In a mono-meter tree Tm(v), only clear readings could be decoded correctly. Clearness function fc(Tm(v)) is defined in a way such that its value is proportional to the probability of seeing clear readings. i.e.

Next, we showcase constructions of clearness function for two basic power patterns without specifying NILM decoding algorithm. And we will evaluate the performance of our tradeoff framework for these two models.

Example 1: Interval Power Pattern Model

In this model, power pattern is characterized as an interval containing the majority of the probability mass. Specifically, power pattern of the ith appliance is represented by a tuple (pi, θi), where pi is its expected power consumption, and θi is the deviation. θi is minimized such that the real-time power consumption takes values in [(1-θi)pi, (1+θi)pi] with overwhelming probability, e.g. 95%. For electrical appliances like lights, computers and televisions, real-time power consumptions are concentrated on their rated values. This model precisely describes the appliance with concentrated power consumption. However, for those appliances with constantly changing power consumption, the deviation is large and it is harder to decode their on/off states from an aggregated power measurement.

For a mono-meter tree Tm(v) with nv appliances, the expected observation value and deviation for state vector sv are

Ideally, all real-time power consumptions should fall into their corresponding intervals, and the observed value for state vector sv should fall into the observation interval Int(sv ) = [(1 - θ(sv ))E(sv ), (1 + θ(sv ))E(sv )]. Therefore, the total power consumption for Tm(v) must fall into one of the observation intervals. However, if some interval overlaps with another, there is no guarantee that every value can be correctly decoded to a state vector - ambiguity happens. Let Pr[Rv = x] be the probability of reading x, estimated by exploiting prior knowledge. The clearness function for interval power pattern model is defined as:

In the case that Pr[Rv = x] is not given in closed form, the clearness function is

The na¨ıve way to calculate fc(Tm(v)) is to enumerate all possible range segments and scan each of them to get the lengths of ambiguous part and clear part. This will not scale well since for each Tm(v) with nv appliances, there are 2nv possible segments. The exhaustive enumeration can be circumvented by dynamic programming, resembling the algorithm for knapsack. The key idea is to map the observation intervals to integers in [0, B], preserving order and B being the maximum meter range; and then calculate how many times each integer is mapped from those observation intervals. This algorithm runs in O(B · nv + B2 ) time and O(B) space.

Example 2: Distributional Power Pattern Model

In reality, many appliance have multiple power consumption states and each of the state have a certain probability to be on. Appliance's power consumption may follow a certain distribution on those states. Here we introduce the distributional power pattern model where each appliance's consumption distributes over a set of discrete values. Given a mono-meter tree Tm(v) with nv appliances, let pv1 , . . . , pvnv be the power patterns of appliances indexed by 1, . . . , nv. For appliance i in Tm(v), pvi := {〈wv i,0 , qv i,0 〉, 〈wv i,1 , qv i,2 〉, ..., 〈wv i,mvi , qv i,mvi 〉} where wi,j is a power consumption value for appliance i and qi,j is the corresponding probability. wi,0 = 0 is the power consumption when the appliance is off.

To construct clearness function for distributional power pattern model, we use the notation of entropy from information theory, which is the average amount of information for a random event. Summation of power consumptions can be viewed as compression of the binary state vector svi . The more information available from the readings, the easier it is to achieve high monitoring accuracy. In light of the intuition, the clearness function can be defined as the ratio of monitoring entropy and on/off state entropy.

For Tm(v), the total entropy of appliance states is:

Let {rv 1 , rv 2 , . . . , rvMv} be the set of distinct meter readings, each corresponds to at least one combination of appliance states in Tm(v). ∀i ∈ {1, 2, ...,M v }, let K(i) be the set of tuples (k1, k2, . . . , knv ) such that ∑nv j=1 wj,kj = rv i . Since all the appliances take readings i.i.d. , it holds that

where Rv is the reading at root v and nv is the number of appliances in Tm(v). The entropy of the smart meter is then defined as:

Note that Hd(v) < Hs(v) implies that there are two different states with the same aggregate power consumption. This ambiguity prevents extracting exact states. Therefore, error-free monitoring can be viewed as lossless compression. Namely, fc(Tm(v)) = 1 if and only if Hd(v) = Hs(v)

However, requiring error-free monitoring is impractical because of inevitable noise and measurement errors. Here we relax the condition from error-free to low-error, and we define the clearness function as

In network science, entropy usually plays the role of a metric in deployment schemes for data gathering system (cf. [Guestrin et al., 2005; Bellala et al., 2012]). Instead of maximizing monitoring entropy, we seek to minimize the number of deployed meters subject to the accuracy criteria that the monitoring entropy remaining larger than a given threshold.

3.1 Clear Deployment Condition

In our setting, clearness indicates high accuracy monitoring for each mono-meter tree. Because of the presence of noise in practice, instead of requiring perfect state decoding, we set a threshold τ ∈ [0, 1] for decoding error, which we call clear ratio. Quantitatively, for a mono-meter tree Tm(v), if fc(Tn(v)) is larger than a predefined τ, we say that Tm(v) is clear; otherwise, it is ambiguous.

Similar to each mono-meter tree, the clearness of the PLT indicates all appliances are monitored as accurately as required. Based on the mono-meter decomposition, we quantify monitoring accuracy by the following,

Definition 1 (Clear Deployment Condition). Given a PLT T (V,E) and a clear ratio τ, clear deployment condition for a meter deployment scheme D = {v1, v2, . . . , vm} is that ∀v ∈ D, fc(Tm(v)) ≥ τ .

We would require deployments to satisfy clear deployment condition, and to verify clear deployment condition it suffices to evaluate fc(·) on each mono-meter tree. When fc(·) is given, finding a minimum-cost deployment is independent of the underlying power pattern model. Thus, our framework can be extended to various NILM models.

4 Smart Meter Deployment

The clearness function quantifies state monitoring accuracy of each mono-meter tree. Armed with this, our objective is to find a deployment scheme with minimum number of meters, such that all the mono-meter trees satisfy clear deployment condition with respect to the clearness function. Formally, we solve the following:

Problem 1. (Smart Meter Deployment Problem (SMDP))

• INPUT A PLT T (V,E), a clearness function fc(·), a clear ratio τ and a set of power patterns to compute clearness function.
• OUTPUT A set D ⊆ V , referred to as a deployment scheme, indicating where meters are deployed, such that |D| is minimized while satisfying clear deployment condition.

Algorithm 1 A PTAS for SMDP: ASMDP

1: INPUT : PLT T (V,E) with power patterns, clearness function fc(·) and monitoring accuracy threshold τ 2: OUTPUT: A smart meter deployment D ⊆ V 3: Let v1, . . . , vn be the vertices in V in postorder 4: T 0 ← T , D← ∅, I ← ∅ 5: for i ← 1 to n-1 do 6: opt(T i-1 (vi)) ←OPTDEPLOYMENT(T i-1 (vi)) 7: if opt(T i-1 (vi)) ≥ 1 + ⌈1/ϵ⌉ then 8: T i ← T i-1 \ T i-1 (vi) 9: D←D∪ opt(T i-1 (vi)) 10: I ← I ∪ {i} 11: else 12: T i ← T i-1 13: end if 14: end for 15: D(vn) ←OPTDEPLOYMENT(T n-1 ) 16: D←D∪ opt(T i-1 (vi)) 17: return D

In practice, PLTs usually have special structures that can be exploited to design good deployment algorithms. In particular, we make a mild assumption that each node in the PLT has degree upper bounded by a constant d. Consider MultiCut, a variant of the unweighted multicut problem on trees [C˘alinescu et al., 2003], that is, given an unweighted tree, and some forbidden sets of leaves, find a set of edges of minimum size, whose removal separates at least one node pair from each forbidden set. It can be shown that each instance of MultiCut can be efficiently translated to an SMDP instance with a clearness function exactly characterizing the forbidden sets. This enables us to show the NP-hardness of SMDP, since MultiCut can be reduced from Exact-3SAT: let n be the number of variables, and m the number of clauses; for each variable x, construct a tree with leaves corresponding to x and ¯x, and a forbidden set containing the two leaves; for each clause, construct a tree with three leaves corresponding to its literals, and also three forbidden sets each containing two of the leaves; all these trees are connected at the bottom layer of a full binary tree with at least n+m leaves. It can be proved that the Exact-3SAT instance is satisfiable if and only if the constructed MultiCut instance has optimal value n + 4m.

Suppose there exists an algorithm to compute fc(·) in O(1) time 1 . Next we turn to present ASMDP, a polynomial-time approximation scheme (PTAS). Let opt(T ) be an optimal solution for SMDP on tree T = (V,E). The algorithm iterates over the nodes of T in postorder. Let vi be the node visited in ith iteration and T i be the PLT after ith iteration. When visiting vi, if |opt(T i-1 (vi))| ≥ 1+⌈1/ϵ⌉, we deploy meters on opt(T i-1 (vi)) ∪ {vi} and cut subtree T i-1 (vi) from T i-1 . Otherwise directly visit next node vi+1. Postorder traversal ensures that all the descendants of vi have been visited before vi, so |opt(T i-1 (u))| < 1 + ⌈1/ϵ⌉, ∀u ∈ C(vi), where C(vi) is the set of vi's children. OPTDEPLOYMENT(·) returns an optimal deployment for a given tree.

1 This is just for convenience sake, as long as it can be computed in polynomial time, the later results will carry through.

Since ⋃u∈C(vi) opt(T i-1 (u))∪{vi} is feasible for T i-1 (vi), it holds that |opt(T i-1 )(vi)| ≤ ∑u∈C(vi) |opt(T i-1 (u))| + 1 ≤ d(1 + ⌈1/ϵ⌉) + 1. Thus OPTDEPLOYMENT(T i-1 (vi)) takes the following steps,

STEP 1 Enumerate all possible meter deployment schemes of size no larger than d⌈1/ϵ⌉ + d + 1.

STEP 2 Filter out the schemes not satisfying clear deployment condition.

STEP 3 Choose the scheme with minimum size.

Based on the discussion above, we summarize ASMDP in Algorithm 1. We also establish a series of lemmas to show correctness and efficiency of ASMDP.

Lemma 1. D is a feasible solution to SMDP for T .

Proof. Let Si be the set of mono-meter trees generated from opt(T i-1 (vi)) on subtree T i-1 (vi). All mono-meter trees in Si are clear. The mono-meter trees generated from D on PLT T is the union of Si, ∀i ∈ I. Therefore, clear deployment condition is satisfied, which implies D is a feasible solution.

Proof. Observe that for any subtree T (v), (opt(T )∩T (v))∪ {v} is a feasible solution for T (v), namely |opt(T )∩T (v)|+ 1 ≥ |opt(T (v))|. Then,

Lemma 3. ∀i ∈ I, OPTDEPLOYMENT(T i-1 (vi)) returns in polynomial time.

Proof. There are O(nd⌈1/ϵ⌉+d+1 ) possible deployment schemes. For each scheme, there are at most d⌈1/ϵ⌉ + d + 1 corresponding mono-meter trees, so it takes O(d⌈1/ϵ⌉+d+1) time to test clear deployment condition for each of them. In total, OPTDEPLOYMENT(T i-1 (vi)) returns within time O((d⌈1/ϵ⌉ + d + 1)nd⌈1/ϵ⌉+d+1 ).

Lemma 4. ASMDP is a polynomial-time algorithm.

Proof. Running time of each iteration is dominated by OPTDEPLOYMENT(·). Combining Lemma 3, ASMDP runs in O((d⌈1/ϵ⌉ + d + 1)nd⌈1/ϵ⌉+d+2 ) time, which is polynomial in n for ϵ > 0.

Theorem 5. For any fixed ϵ > 0, ASMDP is a polynomialtime algorithm that outputs an (1 + ϵ)-optimal solution.

Proof. Correctness, approximation ratio and efficiency follow from Lemma 1, Lemma 2 and Lemma 4 respectively.

The output of ASMDP goes arbitrarily close to optimal by shrinking ϵ, but the running time goes up rapidly at the same time. In our later evaluation, we set ϵ = 1, a balance in approximation ratio and running time.

5 Evaluation

We carry out experiments using simulated and real data to evaluate the effectiveness of clearness function and ASMDP's performance, through comparison with three baselines:

Dense deployment deploy meters at all appliances

Random deployment deploy meters uniformly randomly

Following the electrons (FE) a greedy algorithm proposed in [Bellala et al., 2012] to maximize information acquired with a given number of meters.

5.1 Experiments on PowerNet Dataset

The first experiments are conducted on real-world data from PowerNet 2 . PowerNet provides per-device energy and usage statistics of an office building in Stanford University. More specifically, we use data collected from 126 different appliances in Sept. 2011. Sampling rate is basically 1Hz. To neutralize noise, each appliance's consumption is smoothened by taking the average consumption of intervals of 30 seconds as data points. Fig. 3 shows the real-time power measurements of three appliances on Sept. 25, 2011.

Power Pattern Analysis

We first investigate the concentration property of each appliance's power consumption. An appliance is said having power consumption concentrated on pm at level θ, if there exists a pm, such that 95% of the readings of the appliance's consumption are in the interval [pm(1 - θ), pm(1 + θ)]. In our data set, 73%, 77% and 89% of all the appliances have concentrated power consumption at levels 3%, 5%, and 10% accordingly. This justifies the interval power pattern model. Further, Fig. 4 shows the histogram of the concentrated powers of all the appliances at level 5%. One may observe that the majority of the appliances have concentrated power consumption less than 50W; the distribution is fairly flat in the interval between 50W and 250W. 2 appliances with power consumption far more than 500W are omitted in the figure.

Cost-saving Performance

Since PowerNet does not provide the PLT explicitly, we simulate the power network with randomly generated PLTs and put 126 appliances at leave nodes. We evaluate the costsaving performance of ASMDP on random PLTs with average degrees of 2, 4, 6 and 8. We define cost ratio as the number of deployed meters divided by the number of appliances. Intuitively, a smaller cost ratio is preferable. As an extreme example, in a dense deployment where every appliance is monitored by a meter, the cost ratio is always 1.

Cost ratio for each generated PLT is calculated and depicted in Fig. 5. It can be observed that the number of meters needed and the topology of the underlying PLT are closely related. Larger average degrees generally imply more meters. Moreover, the number of required meters increases with the clear ratio τ . For each value of τ , we run ASMDP on 20 randomly generated trees. The error bar is the standard deviation of 20 runs. As shown in Fig. 5, even in the worst case, the cost ratio of ASMDP is about 0.7, outperforming dense deployment (cost ration = 1) by 30%.

2 PowerNet: http://powernet.stanford.edu/

Monitoring Accuracy Performance

To evaluate state monitoring accuracy, we run Viterbi-based state decoding in each meter's subtree based on [Wang et al., 2012]. State decoding experiments are conducted on randomly generated PLTs with average degrees 4 and 6. Table 1 presents the relation between state decoding accuracy and clear ratio, which are, as expected, positively correlated. This result justifies clear ratio as a reasonable metric for state decoding during meter deployment.

5.2 Simulations

There are only limited types of appliance power patterns in PowerNet. For comprehensiveness, we evaluate ASMDP's performance on simulated data with diverse power patterns.

Impact of Power Consumption Distribution

We generate datasets from three different power patterns: uniform distribution U(0, 1000), normal distribution N(500, 1672 ) and exponential distribution with λ = 0.002. Here we assume all appliances have concentrated power with θ = 0. Fig. 6 shows the cost-saving performance for clear ratio τ = 1. For different sizes and structures of PLTs, ASMDP always achieves cost ratios less than 0.3. Cost ratios for exponential and uniform power distributions are close. In contrast, the cost ratio for normal distribution is significantly higher. The intuition behind is that, the power levels of appliances are more concentrated in the normal distribution, thus more smart meters are required to disambiguate the states of those appliances with similar power patterns.

Comparison of Accuracy

We further compare ASMDP with random meter deployment and FE in terms of accuracy aspect. Distinct from previous evaluations, here distributional power pattern model is used. Entropy ratio is defined as re = minv∈D fc(v), which works as a metric for monitoring accuracy. As shown in Table 1, a larger re indicates a higher monitoring accuracy at the worst monitored appliance, and hence a better monitoring performance. We compare entropy ratios of different deployments at the same deployment cost.

The simulation is conducted on a PLT with 200 nodes, including about 120 appliances. Power consumption of each appliance is uniformly randomly sampled from a distribution shaped resembling the histogram in Fig. 4 with mean 50 watts. The results are summarized in Fig. 7. The entropy ratio increases as the number of meters increases for all three algorithms. Both ASMDP and FE beat random deployment easily. ASMDP always outperforms FE when cost ratio is < 0.2. For example, at entropy ratio re = 0.8, ASMDP costs 40% less than FE. As cost ratio approaches 0.2, both ASMDP and FE already achieves entropy ratio 1, which is the theoretical limit. This is also achievable by a random or dense deployment, but at a much higher cost.

6 Conclusion and FutureWork

This paper presented an extensible framework to investigate the tradeoff between meter deployment cost and appliance state monitoring accuracy. We answered two questions: 1) how to evaluate the quality of a deployment; and 2) how to find a good deployment. In particular, we proposed clear deployment condition to characterize when a deployment satisfies the monitoring accuracy requirements. Based on it, an efficient and effective deployment optimization algorithm was developed. The validity and effectiveness of our approach was then verified both theoretically and experimentally. There are multiple ways that our work can be extended. For example, our framework could be applied in monitoring appliances with multi-mode, dynamic power patterns. Another possible direction to further reduce the number of smart meters is by identifying and tracking only major energy consumers.