An efficient heuristic for placement, scheduling and routing in wireless sensor networks

A wireless sensor network consists of distributed autonomous electronic devices called sensors. Sensors have limited energy and capability for sensing, data processing and communication, but they can act in a collective way to form a network that will monitor a region, and transmit information to gateway nodes or sinks. In most applications, the network must operate for long periods of time, so the energy resources of the sensors must be managed efficiently. In this work, we develop a mixed-integer linear programming model to maximize the network lifetime by optimally determining locations of sensors and sinks, activity schedules of deployed sensors, and sensor-to-sink data flow routes over a finite planning horizon subject to coverage, flow conservation, energy consumption, and budget constraints. Unfortunately, the exact solution of this model is difficult even for small problem instances. Therefore, we propose a heuristic that first finds connected sensor sets with minimum cost satisfying the coverage constraints, and then determines optimal sensor-to-sink data routes with optimal flow quantities. Computational experiments performed on various test instances indicate that the heuristic is very efficient and quite accurate. (C) 2010 Elsevier B.V. All rights reserved.