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

Abstract

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.

Keywords:

• sensor networks
• heuristics
• integer programming
• telecommunications

Acknowledgements

We thank two anonymous referees for their helpful comments and suggestions that significantly improved the quality and exposition of the paper. We also gratefully acknowledge the support of TÜBİTAK (The Scientific and Technological Research Council of Turkey) under grant no. 107M250.