Approximation algorithms for longest-lived directional multicast communications in WANETs

Song Guo, Oliver Yang, Victor Leung

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

13 Citations (Scopus)

Abstract

Several centralized and distributed algorithms have been recently proposed to maximize the multicast lifetime for directional communications in wireless ad-hoc networks. Their performance has been studied by simulations; however, their theoretical performance in terms of approximation ratio is still unknown. In this paper, we use the graph theoretic approach, by the first time, to derive the upper bound of the approximation ratio in an analytical expression for these algorithms. We have also discovered that these upper bounds are finite numbers. Based on this analysis and some key observations, we present a new distributed constant-factor approximation algorithm in order to achieve a higher performance. This effort is validated by our simulation studies.
Original languageEnglish
Title of host publicationMobiHoc'07
Subtitle of host publicationProceedings of the Eighth ACM International Symposium on Mobile Ad Hoc Networking and Computing
Pages190-198
Number of pages9
DOIs
Publication statusPublished - 1 Dec 2007
Externally publishedYes
EventMobiHoc'07: 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing - Montreal, QC, Canada
Duration: 9 Sep 200714 Sep 2007

Conference

ConferenceMobiHoc'07: 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing
Country/TerritoryCanada
CityMontreal, QC
Period9/09/0714/09/07

Keywords

  • Approximation algorithm
  • Directional antenna
  • Maximum-lifetime routing
  • Multicast tree
  • Wireless ad hoc networks

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this