A distributed algorithm with linear convergence for maximum lifetime routing in wireless sensor networks

Ritesh Madan, Zhi Quan Luo, Sanjay Lall

Research output: Chapter in Book/Report/Conference proceedingConference contribution

26 Scopus citations

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 languageEnglish (US)
Title of host publication43rd Annual Allerton Conference on Communication, Control and Computing 2005
PublisherUniversity of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering
Pages896-905
Number of pages10
ISBN (Electronic)9781604234916
StatePublished - 2005
Event43rd Annual Allerton Conference on Communication, Control and Computing 2005 - Monticello, United States
Duration: Sep 28 2005Sep 30 2005

Publication series

Name43rd Annual Allerton Conference on Communication, Control and Computing 2005
Volume2

Other

Other43rd Annual Allerton Conference on Communication, Control and Computing 2005
CountryUnited States
CityMonticello
Period9/28/059/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

Fingerprint Dive into the research topics of 'A distributed algorithm with linear convergence for maximum lifetime routing in wireless sensor networks'. Together they form a unique fingerprint.

Cite this