On the Use of Binary Programming for Sensor Scheduling

Abstract

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 (0-1) 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 50-70 sensors typically in the order of seconds