Title: Energy-aware Routing to Maximize
Lifetime in Wireless Sensor Networks with Mobile Sink
Authors: Ioannis Papadimitriou, Leonidas Georgiadis
Abstract: In this paper we address the problem of maximizing the
lifetime in a wireless sensor network with energy and power constrained sensor
nodes and mobile data collection point (sink). Information generated by the
monitoring sensors needs to be routed efficiently to the location where the sink
is currently located across multiple hops with different transmission energy
requirements. We exploit the capability of the sink to be located in different
places during network operation in order to maximize network lifetime. We
provide a novel linear programming formulation of the problem. We show that
maximum lifetime can be achieved by solving optimally two joint problems: a
scheduling problem that determines the sojourn times of the sink at different
locations, and a routing problem in order to deliver the sensed data to the sink
in an energy-efficient way. Our model provides the optimal solution to both of
these problems and gives the best achievable network lifetime. We evaluate
numerically the performance of our model by comparing it with the case of static
sink and with previously proposed models that focus mainly on the sink movement
patterns and sojourn times, leaving the routing problem outside the linear
programming formulation. Our approach always achieves higher network lifetime,
as expected, leading to a lifetime up to more than twice that obtained with
models previously proposed as the network size increases. It also results in a
fair balancing of the energy depletion among the sensor nodes. The optimal
lifetime provided by the theoretical analysis of our model can be used as a
performance measure in order to test the efficiency of other heuristics that
might be proposed in the future for a practical implementation of a real system.
Our formulation can also be used as a starting point on which new algorithms can
be implemented.