Sensor scheduling and efficient algorithm implementation for target tracking
Antonia Papandreou‐Suppappola, Darryl R. Morrell, Amit S. Chhetri · 2006
Recent advances in sensor technology coupled with embedded systems and wireless networking has made it possible to deploy sensors for numerous applications including target tracking, environmental science, defense information, and security. Sensor scheduling, a process to allocate sensing resources by optimizing a performance metric over a future time-horizon under constraints, is an effective method to improve performance for such problems. This work investigates myopic (one step ahead) and non-myopic (multiple steps ahead) sensor scheduling algorithms for target tracking applications. Two methods of predicting tracker performance are developed that can be used for target tracking applications. The first is covariance-based, and it can be used with covariance-based scheduler costs. The second is unscented transform-based and it can be used with arbitrary scheduler costs. In application, both methods give a significant improvement in tracking performance over the tracking performance without sensor scheduling. The use of non-myopic sensor scheduling is often restricted due to an exponential dependency of computational and memory requirements on the length of prediction horizon. For non-myopic scheduling, two branch-and-bound based optimal pruning algorithms were investigated. Monte Carlo simulations demonstrated that they significantly reduce the computational and memory requirements of non-myopic scheduling without compromising the tracking accuracy. In networks of tiny inexpensive energy-constrained sensors, tracking involves a natural trade-off between performance and energy consumption. Non-myopic scheduling to minimize the network energy consumption subject to maintaining a desired tracking accuracy in the target's position estimate was studied; non-myopic sensor scheduling significantly improved the energy performance of the network compared to myopic scheduling. Using the covariance-based scheduling framework, large sensor scheduling problems involving a trade-off between sensor-usage costs and tracking performance can be posed as binary (0-1) convex programming problems. In some special cases, these problems simplify to 0-1 mixed integer programming problems. The 0-1 convex programming and 0-1 mixed integer programming problems are solved using outer approximation and linear programming relaxation based branch-and-bound algorithms. Simulation results demonstrated that the 0-1 programming allows optimal solution to problems of up to 50-90 sensors typically in the order of seconds.