PaperlayerView exact revision on arXiv

Source-linked AI summary

An Information-Theoretic Approach to PMU Placement in Electric Power Systems

Qiao Li, Tao Cui, Yang Weng, Rohit Negi, Franz Franchetti, Marija D. Ilic

arXiv:1201.2934v1math.OCcs.DScs.ITmath.IT

TL;DR

Topological observability can be too coarse for PMU placement when full system observability is out of reach. This paper uses mutual information between PMU measurements and system states as the placement criterion and proposes a greedy algorithm. The algorithm achieves a (1−1/e) approximation for any PMU budget, and the paper states that better approximation is NP-hard.

  • Problem

    Topological observability is a coarse criterion when installed PMUs are insufficient for full observability, despite correlated system states and the influence of line admittances.

    Source: §I · p. 1

  • Method

    The paper optimizes mutual information between PMU measurements and system states, modeling state uncertainty and probabilistic PMU failures.

    Source: §I · pp. 1–2

  • Results

    The greedy algorithm achieves a (1−1/e) approximation for any PMU budget, and better approximation is NP-hard.

    Source: §I · p. 2

  • Takeaways & Limitations

    The any-budget guarantee makes greedy placement suitable for multi-stage installations under limited utility budgets.

    Source: §I · p. 2

Abstract

from arXiv · show

This paper presents an information-theoretic approach to address the phasor measurement unit (PMU) placement problem in electric power systems. Different from the conventional 'topological observability' based approaches, this paper advocates a much more refined, information-theoretic criterion, namely the mutual information (MI) between the PMU measurements and the power system states. The proposed MI criterion can not only include the full system observability as a special case, but also can rigorously model the remaining uncertainties in the power system states with PMU measurements, so as to generate highly informative PMU configurations. Further, the MI criterion can facilitate robust PMU placement by explicitly modeling probabilistic PMU outages. We propose a greedy PMU placement algorithm, and show that it achieves an approximation ratio of (1-1/e) for any PMU placement budget. We further show that the performance is the best that one can achieve in practice, in the sense that it is NP-hard to achieve any approximation ratio beyond (1-1/e). Such performance guarantee makes the greedy algorithm very attractive in the practical scenario of multi-stage installations for utilities with limited budgets. Finally, simulation results demonstrate near-optimal performance of the proposed PMU placement algorithm.

I. INTRODUCTION

PMU placement should maximize information about power-system states, but topological observability can be too coarse when only a limited number of PMUs are installed. The paper proposes mutual information as a placement criterion and models correlated bus angles under a DC power-flow model.

I. INTRODUCTION

  • Topological observability gives a binary view of state information and can yield suboptimal placements when PMUs are insufficient for full observability.It also overlooks state correlations and transmission-line admittances.Source: §I · p. 1
  • The paper uses mutual information between PMU measurements and system states to select informative configurations, including probabilistic PMU failures.The criterion includes topological observability as a special case.Source: §I · pp. 1–2
  • The greedy placement algorithm achieves a (1−1/e) approximation for any PMU budget, supporting multi-stage installations under limited budgets.The paper states that no polynomial-time algorithm can achieve a better approximation ratio unless P = NP.Source: §I · p. 2

A. GMRF Model for Phasor Angles

  • Under the DC model, non-reference bus angles form a GMRF with mean B−1µ and covariance B−1ΣB−1 when the power system is fully connected.The model assumes Gaussian power-injection uncertainty; independent injections produce GMRF connections between two-hop neighbors.Source: A. GMRF Model for Phasor Angles · p. 2

B. Measurement Model

The measurement model describes conventional measurements under the DC power-flow assumption and provides an equivalent model for PMU measurements.

1) Conventional Measurements:

B. Measurement Model

  • The passage describes measurement noises as Gaussian, with distribution N(0, κconv…).The stated variance expression is truncated in the supplied passage.Source: 1) Conventional Measurements · p. 2
  • A PMU at bus i measures its voltage and selected incident-branch currents, from which adjacent-bus phasor angles can be calculated.Source: 2) PMU Measurements · p. 2

2) PMU Measurements:

The PMU model accounts for channel limits and measurement availability, while the probabilistic graph illustrates how placement affects information gain.

2) PMU Measurements:

  • Channel limits mean a PMU can monitor only a subset of its adjacent branches.The subset of neighbors is denoted P_i.Source: 2) PMU Measurements · p. 2
  • The graphical model distinguishes state variables from measurements and indicates that PMU information gain depends on placement buses.Its shaded region represents the GMRF for non-reference bus angles, with independent power injections assumed.Source: Figure 2 · p. 3, 2) PMU Measurements · p. 3
  • PMU measurement variances reflect sources of uncertainty, and probabilistic failures are modeled through measurement availability.The passage identifies GPS synchronization, instrument transformers, A/D converters, and cable parameters as uncertainty sources.Source: 2) PMU Measurements · p. 3

III. OPTIMAL PMU PLACEMENT

The placement objective is the mutual information between system states and PMU measurements, expressed as a reduction in state uncertainty. Under noiseless, failure-free measurements, maximizing it recovers complete observability.

III. OPTIMAL PMU PLACEMENT

  • The information gain from a PMU configuration is the entropy reduction in system states after observing its measurements.The model uses sufficiently fine quantization to reflect finite meter accuracy.Source: §III · p. 3
  • Mutual information between states and PMU measurements is H(θ) − H(θ|zPMU(S)), with conditional entropy representing remaining uncertainty.The formulation also describes conditional mutual information when conventional measurements are considered.Source: §III · p. 3
  • With no PMU failures or measurement noise, maximum information gain occurs if and only if the system is completely observable from PMU measurements.In that case, conditional state entropy is zero.Source: 2) (State Estimation Error) · p. 3
  • The paper relates the MI criterion to minimizing state-estimation error through conditional entropy.Source: 2) (State Estimation Error) · p. 3

1) (Observability):

The section connects mutual-information placement with state-estimation accuracy and formulates objectives for PMUs alone or with conventional measurements. The PMU-only objective represents time-averaged information gain, while conventional measurements change it to conditional mutual information.

1) (Observability):

IV. GREEDY PMU PLACEMENT

The greedy PMU placement method achieves the stated approximation guarantee, while the hardness result rules out a better polynomial-time ratio unless P = NP. It selects placements by marginal information gain and is described as computationally simple to implement at large scale.

IV. GREEDY PMU PLACEMENT

  • The optimal placement problem is NP-complete, and the proposed greedy algorithm targets the best performance guarantee among polynomial-time methods.Source: §IV · p. 4

A. Hardness Result

  • Unless P = NP, no polynomial-time algorithm can achieve a better-than-(1−1/e) approximation ratio for the optimal placement problem.Source: A. Hardness Result · p. 4

B. Greedy PMU Placement

  • At each step, the algorithm chooses the candidate with the largest marginal information gain, using F1 or F2 depending on whether conventional measurements are included.Source: B. Greedy PMU Placement · p. 4
  • The greedy placement achieves an approximation ratio of (1−1/e) for both objective functions F1 and F2.Source: B. Greedy PMU Placement · p. 4
  • The greedy method is presented as easier to implement in large-scale systems than mixed-integer programming, binary search, or metaheuristics, due to its low computational complexity.Source: 1) Optimality · p. 4

1) Optimality:

The section presents the greedy guarantee as useful when utilities install PMUs over multiple years with limited or uncertain budgets. It then introduces numerical comparisons with literature methods in standard IEEE test systems.

1) Optimality:

  • For multi-stage installations, the greedy method retains a (1−1/e) approximation ratio for any budget K, while fixed plans may lose performance if K changes unexpectedly.Source: 2) Multi-stage Installation · p. 4

2) Multi-stage Installation:

V. NUMERICAL RESULTS

  • The numerical-results section compares the proposed greedy algorithm with PMU placement results in the literature.Source: §V · p. 4

A. System Description

The IEEE 14-bus simulations compare greedy PMU placement with optimal and observability-based configurations under stated measurement and outage assumptions. Greedy placements remain nested across budgets and achieve information gains close to the no-failure upper bound.

A. System Description

  • Simulations assume independent 3% PMU failure probability, 0.02° PMU measurement error, and 0.57° conventional-measurement error.Real power injections are independent across buses, normally distributed, and have standard deviation equal to 10% of their mean.Source: A. System Description · p. 4

1) PMU Measurements Only:

  • For K = 3, greedy placement improves information gain by around 20% over observability-based placement and stays close to the no-failure upper bound.The gain exhibits diminishing marginal returns as more PMUs are installed, consistent with submodularity of the MI objective.Source: Figure 3 · p. 5, 1) PMU Measurements Only · p. 5

B. IEEE 14-Bus System

2) With Conventional Measurements:

On the IEEE 57-bus system, greedy placement yields significant information gain over observability-based results, including when conventional measurements already make the system observable. The conclusion highlights a (1 −1/e) guarantee for any PMU budget and robustness to budget changes.

2) With Conventional Measurements:

C. IEEE 57-Bus System

  • Without conventional measurements, greedy placement provides significant information gain over observability-based criteria on the IEEE 57-bus system.The optimal configuration is computationally infeasible to obtain for large K, and the greedy information-gain curve shows diminishing marginal returns.Source: 1) PMU Measurements Only · p. 6

VI. CONCLUSION

  • The greedy algorithm achieves a (1 −1/e) approximation ratio for any PMU budget K, the best guarantee among polynomial-time algorithms.The conclusion identifies robustness to changes in budget as a reason it is attractive for phased installations.Source: §VI · p. 6

APPENDIX A PROOF OF THEOREM 2

A reduction from max k-cover establishes that PMU placement cannot be approximated beyond (1 −1/e) in polynomial time. The greedy guarantee follows from the MI objective's nondecreasing submodularity and its diminishing returns.

APPENDIX A PROOF OF THEOREM 2

  • A polynomial-time reduction from max k-cover shows that PMU placement is NP-hard to approximate beyond (1 −1/e).The construction uses independent phasor angles with entropy 1 and assumes no PMU failure or measurement noise.Source: Appendix A · pp. 6–7

A. Introduction to Submodular Functions

B. Proof of Theorem 3

The proof establishes that the MI objective is submodular and nondecreasing for PMU placement. The argument extends across time slots and to the case conditioned on conventional measurements.

B. Proof of Theorem 3

  • Without conventional measurements, the MI objective is submodular because conditional independence makes its marginal gain decrease as the selected PMU set grows.The objective is nondecreasing because conditional mutual information is nonnegative.Source: B. Proof of Theorem 3 · p. 7
  • The same properties extend to F1 by summing the inequalities over T time slots and to the conventional-measurement case by conditioning on those measurements.Source: B. Proof of Theorem 3 · p. 7
Loading 1201.2934v1…