A message complexity oriented design of distributed algorithm for long-lived multicasting in wireless sensor networks

Xiaofei Liu, Song Guo, Abdulmotaleb El Saddik

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 rooted at the source node and including all the destination nodes such that the lifetime of the tree is maximized. While a recently proposed distributed algorithm for this problem guarantees to obtain optimal solutions, we show that its high message complexity may prevent such contribution from being practically used in resource-constrained WSNs. In this paper, we proposed a new distributed suboptimal algorithm that achieves a good balance on the algorithm-optimality and message complexity. In particular, we prove that it has a linear-message complexity. The tradeoff between algorithm sub-optimality and message complexity is also studied by simulations.
Original languageEnglish
Title of host publication2008 Proceedings of 17th International Conference on Computer Communications and Networks, ICCCN 2008
Pages771-776
Number of pages6
DOIs
Publication statusPublished - 26 Dec 2008
Externally publishedYes
Event17th International Conference on Computer Communications and Networks, ICCCN 2008 - St. Thomas, Virgin Islands, U.S.
Duration: 3 Aug 20087 Aug 2008

Conference

Conference17th International Conference on Computer Communications and Networks, ICCCN 2008
CountryVirgin Islands, U.S.
CitySt. Thomas
Period3/08/087/08/08

Keywords

  • Communication complexity
  • Distributed algorithm
  • Energy efficiency
  • Multicasting
  • Wireless sensor network

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Software

Cite this