On the multicast lifetime of WANETs with multibeam antennas: Formulation, algorithms, and analysis

Song Guo, Minyi Guo, Victor C.M. Leung, Shui Yu, Yong Xiang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 Citations (Scopus)

Abstract

We explore the multicast lifetime capacity of energy-limited wireless ad hoc networks using directional multibeam antennas by formulating and solving the corresponding optimization problem. In such networks, each node is equipped with a practical smart antenna array that can be configured to support multiple beams with adjustable orientation and beamwidth. The special case of this optimization problem in networks with single beams have been extensively studied and shown to be NP-hard. In this paper, we provide a globally optimal solution to this problem by developing a general MILP formulation that can apply to various configurable antenna models, many of which are not supported by the existing formulations. In order to study the multicast lifetime capacity of large-scale networks, we also propose an efficient heuristic algorithm with guaranteed theoretical performance. In particular, we provide a sufficient condition to determine if its performance reaches optimum based on the analysis of its approximation ratio. These results are validated by experiments as well. The multicast lifetime capacity is then quantitatively studied by evaluating the proposed exact and heuristic algorithms using simulations. The experimental results also show that using two-beam antennas can exploit most lifetime capacity of the networks for multicast communications.
Original languageEnglish
Article number6487492
Pages (from-to)1988-2001
Number of pages14
JournalIEEE Transactions on Computers
Volume63
Issue number8
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes

Keywords

  • approximation algorithm
  • directional multibeam antenna
  • multicast
  • Wireless ad hoc networks

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this