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.