APSIPA Transactions on Signal and Information Processing > Vol 3 > Issue 1

Nested performance bounds and approximate solutions for the sensor placement problem

Muhammad Sharif Uddin, University of Hawaii at Manoa, USA, uddin@hawaii.edu , Anthony Kuh, University of Hawaii at Manoa, USA, Aleksandar Kavcic, University of Hawaii at Manoa, USA, Toshihisa Tanaka, Tokyo University of Agriculture and Technology, Japan
 
Suggested Citation
Muhammad Sharif Uddin, Anthony Kuh, Aleksandar Kavcic and Toshihisa Tanaka (2014), "Nested performance bounds and approximate solutions for the sensor placement problem", APSIPA Transactions on Signal and Information Processing: Vol. 3: No. 1, e4. http://dx.doi.org/10.1017/ATSIP.2014.3

Publication Date: 17 Mar 2014
© 2014 Muhammad Sharif Uddin, Anthony Kuh, Aleksandar Kavcic and Toshihisa Tanaka
 
Subjects
 
Keywords
sensor placementgreedy algorithmgeneralized eigenvectors
 

Share

Open Access

This is published under the terms of the Creative Commons Attribution licence.

Downloaded: 546 times

In this article:
I. INTRODUCTION 
II. PROBLEM STATEMENT 
III. EFFICACY-BASED APPROXIMATE SOLUTIONS 
IV. UPPER BOUNDS ON THE OPTIMAL EFFICACY 
V. PROJECTION-BASED APPROXIMATE SOLUTIONS 
VI. SIMULATION RESULTS 
VII. SUMMARY AND FURTHER DIRECTIONS 

Abstract

This paper considers the placement of m sensors at n > m possible locations. Given noisy observations, knowledge of the state correlation matrix, and a mean-square error criterion (equivalently maximizing an efficacy cost criterion), the problem is formulated as an integer programming problem. Computing the solution for large m and n is infeasible, requiring us to look at approximate algorithms and bounding optimal performance. Approximate algorithms include greedy algorithms and variations based on examining the efficacy cost function and projection-based methods that all run in polynomial time of m and n. A sequence of nested bounds are found that upper bound the optimal performance (with analysis based on using matrix pencils and generalized eigenvectors). Finally, we show through simulations that the approximate algorithms perform well and provide tight implementable lower bounds to optimal performance and the nested bounds provide upper bounds to optimal performance with tighter bounds achieved with increasing complexity. The sensor placement problem has many energy applications where we are often confronted with limited resources. Some examples include where to place environmental sensors for an area in which there are many distributed solar photovoltaic generators and where to place grid monitors on an electrical distribution microgrid.

DOI:10.1017/ATSIP.2014.3