A Randomized Greedy Algorithm for Near-Optimal Sensor Scheduling in Large-Scale Sensor Networks
For practitioners in sensor networks and control systems, this work offers a computationally efficient method for sensor selection with theoretical guarantees, though it is an incremental improvement over existing greedy approaches.
This paper tackles sensor scheduling in large-scale networks for state estimation, proposing a randomized greedy algorithm that is significantly faster than existing methods. The algorithm achieves near-optimal mean square error, with bounds derived in terms of curvature and submodularity.
We study the problem of scheduling sensors in a resource-constrained linear dynamical system, where the objective is to select a small subset of sensors from a large network to perform the state estimation task. We formulate this problem as the maximization of a monotone set function under a matroid constraint. We propose a randomized greedy algorithm that is significantly faster than state-of-the-art methods. By introducing the notion of curvature which quantifies how close a function is to being submodular, we analyze the performance of the proposed algorithm and find a bound on the expected mean square error (MSE) of the estimator that uses the selected sensors in terms of the optimal MSE. Moreover, we derive a probabilistic bound on the curvature for the scenario where{\color{black}{ the measurements are i.i.d. random vectors with bounded $\ell_2$ norm.}} Simulation results demonstrate efficacy of the randomized greedy algorithm in a comparison with greedy and semidefinite programming relaxation methods.