Minimum energy target tracking with coverage guarantee in wireless sensor networks

Wireless Sensor Networks (WSN) are composed of low-cost sensors designed to monitor targets inside their sensing range. The sensors are randomly dispatched in a region and have a limited battery capacity. The targets are moving and their trajectory are subject to uncertainty. A way to save energy of the WSN is to activate subsets of sensors covering all the targets. The challenge of this paper is to preserve and balance the residual capacities of the sensors in order to perform further target tracking missions using the same WSN. A two-step exact method is proposed. First, the input data is processed in order to design a mathematical formulation. Second, a column generation algorithm, combined with a GRASP metaheuristic, assigns activation time to sensors.