A Distributed Algorithm with Linear Convergence for Maximum Lifetime Routing in Wireless Networks

A wireless sensor network of nodes with limited energy is considered. The problem of computing a routing flow that maximizes the network lifetime is formulated as a linear program. We consider a convex optimization problem with a separable objective function that computes an approximate solution to this linear program. Approximation bounds are given for the solution to this convex problem. A distributed algorithm with linear convergence is proposed to solve the approximate optimization problem. The approximation can be chosen such that the lifetime given by the approximate problem is arbitrarily close to the optimal lifetime given by the linear program. The main step of the algorithm can be implemented using the Bellman-Ford algorithm for computing the shortest path in a graph.