Greedy Sensor Selection: Leveraging Submodularity

Abstract

We consider the problem of sensor selection in resource constrained sensor networks. The fusion center selects a subset of k sensors from an available pool of m sensors according to the maximum a posteriori or the maximum likelihood rule. We cast the sensor selection problem as the maximization of a submodular function over uniform matroids, and demonstrate that a greedy sensor selection algorithm achieves performance within $(1 - 1/e )$ of the optimal solution. The greedy algorithm has a complexity of $O(n^3 mk)$, where n is the dimension of the measurement space. The complexity of the algorithm is further reduced to $O(n^2 mk)$ by exploiting certain structural features of the problem. An application to the sensor selection in linear dynamical systems where the fusion center employs Kalman filtering for state estimation is considered. Simulation results demonstrate the superior performance of the greedy sensor selection algorithm over competing techniques based on convex relaxation.

Type
Publication
49th IEEE Conference on Decision and Control (CDC)
Siddhartha Banerjee
Associate Professor

Sid Banerjee is an associate professor in the School of Operations Research at Cornell, working on topics at the intersection of data-driven decision-making, market design, and algorithms for large-scale networks.