Lifetime approximation schemes allow multicast algorithm with linear message complexity in wireless sensor networks

Mianxiong Dong, Song Guo, Minyi Guo

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

Abstract

We consider an optimization problem in wireless sensor networks (WSNs) that is to find a multicast tree with maximum lifetime. While a recently proposed distributed algorithm for this problem guarantees to obtain optimal solutions, its high message complexity may prevent such contribution from being practically used in resource-constrained WSNs. In this paper, we proposed a new distributed algorithm that achieves a good balance on the algorithm optimality and message complexity. We use a graph theoretical approach, by the first time, to derive the bounds of both approximation ratio and message complexity in an analytical expression for this algorithm. The theoretical analysis on the tradeoff between these two performance metrics is also validated by our simulation studies.
Original languageEnglish
Title of host publicationProceedings - 10th IEEE International Conference on High Performance Computing and Communications, HPCC 2008
Pages532-539
Number of pages8
DOIs
Publication statusPublished - 24 Nov 2008
Externally publishedYes
Event10th IEEE International Conference on High Performance Computing and Communications, HPCC 2008 - Dalian, China
Duration: 25 Sep 200827 Sep 2008

Conference

Conference10th IEEE International Conference on High Performance Computing and Communications, HPCC 2008
CountryChina
CityDalian
Period25/09/0827/09/08

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications
  • Electrical and Electronic Engineering

Cite this