Abstract
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.
Original language | English (US) |
---|---|
Title of host publication | 43rd Annual Allerton Conference on Communication, Control and Computing 2005 |
Publisher | University of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering |
Pages | 896-905 |
Number of pages | 10 |
ISBN (Electronic) | 9781604234916 |
State | Published - 2005 |
Event | 43rd Annual Allerton Conference on Communication, Control and Computing 2005 - Monticello, United States Duration: Sep 28 2005 → Sep 30 2005 |
Publication series
Name | 43rd Annual Allerton Conference on Communication, Control and Computing 2005 |
---|---|
Volume | 2 |
Conference
Conference | 43rd Annual Allerton Conference on Communication, Control and Computing 2005 |
---|---|
Country/Territory | United States |
City | Monticello |
Period | 9/28/05 → 9/30/05 |
Bibliographical note
Funding Information:Ritesh Madan and Sanjay Lall were partially supported by the Stanford URI Architectures for Secure and Robust Distributed Infrastructures, AFOSR DoD award number 49620-01-1-0365. Ritesh Madan was also partially supported by a Sequoia Capital Stanford Graduate Fellowship. Zhi-Quan Luo was partially supported by the National Science Foundation under grant DMS-0312416.
Keywords
- Distributed algorithms
- Lifetime
- Linear convergence
- Routing
- Wardrop equilibrium
- Wireless sensor networks