Lifetime optimization for reliable broadcast and multicast in wireless ad hoc networks

Peng Li, Song Guo, Jiankun Hu, Ruhul Sarker

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)

Abstract

In this paper, we consider the reliable broadcast and multicast lifetime maximization problems in energy-constrained wireless ad hoc networks, such as wireless sensor networks for environment monitoring and wireless ad hoc networks consisting of laptops or PDAs with limited battery capacities. In packet loss-free networks, the optimal solution of lifetime maximization problem can be easily obtained by tree-based algorithms. In unreliable networks, we formulate them as min-max tree problems and prove them NP-complete by a reduction from a well-known minimum degree spanning tree problem. A link quality-aware heuristic algorithm called Maximum Lifetime Reliable Broadcast Tree (MLRBT) is proposed to build a broadcast tree that maximizes the network lifetime. The reliable multicast lifetime maximization problem can be solved as well by pruning the broadcast tree produced by the MLRBT algorithm. The time complexity analysis of both algorithms is also provided. Simulation results show that the proposed algorithms can significantly increase the network lifetime compared with the traditional algorithms under various distributions of error probability on lossy wireless links.
Original languageEnglish
Pages (from-to)221-231
Number of pages11
JournalWireless Communications and Mobile Computing
Volume14
Issue number2
DOIs
Publication statusPublished - 10 Feb 2014
Externally publishedYes

Keywords

  • energy efficiency
  • error control
  • multicast
  • NP-complete
  • wireless ad hoc network

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Cite this