Exact and performance-guaranteed multicast algorithms for lifetime optimization in WANETs

Song Guo, Victor Leung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

We consider the problem of maximizing the lifetime of a given multicast connection in wireless networks that use directional antennas and have limited energy resources. We provide a globally optimal solution to this problem by developing a general MILP formulation that can apply to many directional antenna models, some of which are not supported by the existing formulations. We also investigate the theoretical performance of a well-known heuristic algorithm for this optimization problem in terms of its approximation ratio. We use a graph theoretic approach, for the first time, to derive an upper bound on its approximation ratio in an analytical expression and discover that it is a constant-factor approximation algorithm.
Original languageEnglish
Pages (from-to)287-297
Number of pages11
JournalNetworks
Volume55
Issue number3
DOIs
Publication statusPublished - 1 May 2010
Externally publishedYes

Keywords

  • Directional antenna
  • Lifetime multicast maximization
  • Mixed integer linear programming
  • Wireless ad hoc networks

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications

Cite this