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

Song Guo, Minyi Guo, Victor C.M. Leung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)


We consider an optimisation 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 maximised. 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 sub-optimal 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 trade-off between algorithm sub-optimality and message complexity is also studied by simulations.
Original languageEnglish
Pages (from-to)180-190
Number of pages11
JournalInternational Journal of Sensor Networks
Issue number3-4
Publication statusPublished - 1 Dec 2009
Externally publishedYes


  • Communication complexity
  • Distributed algorithm
  • Energy efficiency
  • Multicasting
  • Wireless Sensor Network
  • WSN

ASJC Scopus subject areas

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

Cite this