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

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