Distributed approximation algorithms for longest-lived multicast in WANETs with directional antennas

Song Guo, Victor Leung, Xiaohong Jiang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 Citations (Scopus)

Abstract

We consider the lifetime optimization problem for multicasting in wireless ad hoc networks, in which each node is equipped with a directional antenna and has limited energy supplies. Several distributed algorithms proposed recently are especially beneficial to a resource-constrained wireless ad hoc network. In this paper, we propose a new distributed algorithm and investigate its theoretical performance compared to existing distributed algorithms. We use a graph theoretic approach to obtain the upper bound of the approximation ratio for a group of distributed algorithms. In particular, the derived upper bound in a closed form for each algorithm provides a sufficient condition to determine if the obtained solutions can reach optimum. Both theoretical and experimental performance analysis show that the new algorithm outperforms other proposals in terms of providing long-lived multicast tree.
Original languageEnglish
Article number5508974
Pages (from-to)2227-2237
Number of pages11
JournalIEEE Transactions on Wireless Communications
Volume9
Issue number7
DOIs
Publication statusPublished - 1 Jul 2010
Externally publishedYes

Keywords

  • approximation algorithm
  • directional antenna
  • multicast
  • Wireless ad hoc network

ASJC Scopus subject areas

  • Computer Science Applications
  • Applied Mathematics
  • Electrical and Electronic Engineering

Cite this