On the use of binary programming for sensor scheduling

In this paper, we propose two myopic sensor scheduling algorithms for target tracking scenarios in which there is a tradeoff between tracking performance and sensor-usage costs. Specifically, we consider the problem of activating the lowest cost combination of at most L sensors that maintains a desired squared-error accuracy in the target's position estimate. For sensors that provide position information only, we develop a binary (01) mixed integer programming formulation for the scheduling problem and solve it using a linear programming relaxation-based branch-and-bound technique. For sensors that provide both position and velocity information, we pose the scheduling problem as a binary convex programming problem and solve it using the outer approximation algorithm. We apply our scheduling procedures in a network of sensors where the sensor-usage costs correspond to network energy consumption. Our simulation results demonstrate that scheduling using binary programming allows us to obtain optimal solutions to scheduling involving up to 5070 sensors typically in the order of seconds.