Sensor Scheduling using a 0-1 Mixed Integer Programming Framework

In this paper, we propose a novel myopic sensor scheduling methodology for tracking a target moving through a network of energy-constrained acoustic sensors. Specifically, we address the problem of activating the minimum-energy combination of sensors in a network that maintains a desired squared-error accuracy in the target's position estimate. We first formulate the scheduling problem as a binary (0-1) nonlinear programming (NLP) problem. Using a linearization technique, we then convert the 0-1 NLP problem into a 0-1 mixed integer programming (MIP) problem. We solve the reformulated 0-1 MIP problem using a linear programming relaxation based branch-and-bound technique. We demonstrate through Monte Carlo simulations that our proposed MIP scheduling method is very computational efficient as we can find optimal solutions to scheduling problems involving 50-60 sensors with processing time in the order of seconds

I. Introduction

An important consideration for tracking a target in a sensor network is the natural trade-off between the cost of sensing resources and the quality of tracking performance [1], [2]. As more sensors are allocated, the tracking quality tends to improve, albeit at an increased sensor-usage cost. For networks where energy is a valuable resource, it is necessary to minimize the network energy consumption subject to constraints on tracking accuracy. Sensor scheduling, a process to allocate future sensing resources by optimizing a scheduler cost under constraints, is a natural solution to such problems.