Greedy Sensor Selection under Channel Uncertainty


Estimation in resource constrained sensor networks where the fusion center selects a fixed-size subset from a pool of available sensors observing the states of a linear dynamical system is considered. With some probability, the communication between a selected sensor and the fusion center may fail. It is shown that when the fusion center employs a Kalman filter and desires to minimize a function of the error covariance matrix, sensor selection under communication uncertainty can be cast as the maximization of a submodular function over uniform matroids. We propose a computationally efficient greedy sensor selection scheme achieving performance within (1 -1/ e ) of the optimal non-adaptive policy. Additionally, we propose an efficient adaptive greedy algorithm which achieves (1-1/e) of the optimal adaptive policy. Structural features of the problem are exploited to reduce the complexity of the greedy selection algorithms. We analyze the complexity and present simulation studies which demonstrate efficacy of the proposed techniques.

IEEE Wireless Communications Letters
Siddhartha Banerjee
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.