Optimal placement, scheduling, and routing to maximize lifetime in sensor networks

A wireless sensor network is a network consisting of distributed autonomous electronic devices called sensors. Sensors have limited energy and capability for sensing, data processing, and communicating, but they can collectively behave to provide an effective network that monitors an area and transmit information to gateway nodes or sinks, either directly or through other sensor nodes. In most applications the network must operate for long periods of time, so the available energy resources of the sensors must be managed efficiently. In this paper, we first develop a mixed integer linear programming model to maximize network lifetime by optimally determining locations of sensors and sinks, activity schedules of deployed sensors, and data flow routes from sensors to sinks over a finite planning horizon subject to coverage, flow conservation, energy consumption, and budget constraints. Unfortunately, it is difficult to solve this model exactly even for small instances. Therefore, we propose two approximate solution methods: a Lagrangean heuristic and a two-stage heuristic in which sensors are deployed and an activity schedule is found in the first stage, whereas sinks are located and sensor-to-sink data flow routes are determined in the second stage. Computational experiments performed on various test instances indicate that the Lagrangean heuristic is both efficient and accurate and also outperforms the two-stage heuristic.