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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> mk), where n is the dimension of the measurement space. The complexity of the algorithm is further reduced to O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> 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.