A Distributed Algorithm for Maximum Lifetime Routing in Sensor Networks with Mobile Sink

We consider a noise-limited wireless sensor network that consists of battery-operated nodes which can route information to a mobile sink in a multi-hop fashion. The problem of maximizing the network´s lifetime, defined as the period of time during which the network can route a feasible flow to each sink location subject to power/energy constraints, is cast into a linear program, reduced into a simpler equivalent form and solved via dual decomposition. The unknowns are the sink sojourn times and the routing flow vector for each sink location. The presence of a mobile sink presents new challenges but the problem structure can still be exploited to find the optimal solution. A distributed algorithm based on the subgradient method and using the sink as leader is proposed and its performance is evaluated through simulation for random networks. The algorithm´s requirements in memory are also provided.