Performance Bounds on Sensor Placement Algorithms and Online Outlier Detection in the Power Grid

Abstract

Accurate real-time estimation of the states is of critical importance in the operation of the power grid. The quality of the state estimates is essentially dependent on ensuring the collection of measurement data that provide maximal information about the states and ensuring the integrity of the collected data. This thesis addresses the problem of ensuring quality of the suboptimal solutions to the optimal sensor placement problem and also presents algorithms for detecting outliers or malicious data in the power grid. In the sensor placement problem, the number of sensors that can be deployed is often limited by costs and other resource constraints. Finding the best subset of sensor locations in a large network is pro- hibitively complex, forcing us to look for suboptimal algorithms. In this thesis we obtain numerical bounds on the suboptimal algorithms to assess the performance of these algo- rithms in the absence of the optimal solution. Given noisy measurements and knowledge of the state correlation matrix, we use the linear minimum mean squared error estimator as the state estimator to formulate the sensor placement problem as an integer programming problem. We develop a set of approximate algorithms and derive a set of analytical nes-ted performance upper bounds to the optimal solution based on the structure of the data correlation matrix. The second part of the thesis investigates algorithms to ensure data integrity by detecting outliers in the sensor data. We study the detection of gross measurement errors and hidden data attacks in the power system as an online outlier detection problem. An online probability density based technique is presented to identify bad measurements within a sensor data stream in a decentralized manner using only the data from the neighboring buses and a one- hop communication system. Analyzing the spatial and temporal dependency between the measurements, the proposed algorithm identifies the bad data. To develop an online outlier detection algorithm with lower complexity, a sparse online least-squares one-class support vector machine classification algorithm is developed to provide real-time quality information, before the data is fed into the computationally expensive state estimator. An approximate linear dependence cost criteria is used to obtain a sparse solution by sequentially processing each data point only once, keeping with the requirement of data processing over data stream. The performances of the proposed algorithms are then verified through simulations on IEEE benchmark test systems.