Minimum-transmission broadcast in uncoordinated duty-cycled wireless Ad Hoc networks

Jue Hong, Jiannong Cao, Wenzhong Li, Sanglu Lu, Daoxu Chen

Research output: Journal article publicationJournal articleAcademic researchpeer-review

47 Citations (Scopus)

Abstract

Broadcast is a fundamental operation of wireless ad hoc networks (WANETs) and has widely been studied over the past few decades. However, most existing broadcasting strategies assume nonsleeping wireless nodes and thus are not suitable for uncoordinated duty-cycled WANETs, in which each node periodically switches on and off to save energy. In this paper, we study the minimum-transmission broadcast problem in uncoordinated duty-cycled WANETs (MTB-UD problem) and prove its NP-hardness. We show that modifications of existing broadcast approaches can only provide a linear approximation ratio of O(n) (where n is the number of nodes in the network). We propose a novel set-cover-based approximation (SCA) scheme with both centralized and distributed approximation algorithms. The centralized SCA (CSCA) algorithm has a logarithmic approximation ratio of 3(ln Δ + 1) and time complexity of O(n3) (Δ is the maximum degree of the network). The distributed SCA (DSCA) algorithm has a constant approximation ratio of at most 20 while keeping both linear time and message complexities. We have conducted both theoretical analysis and simulations to evaluate the performance of the proposed algorithms. Results show that both the CSCA and DSCA algorithms outperform the modified versions of existing broadcast approaches by at least 50%.
Original languageEnglish
Article number5204235
Pages (from-to)307-318
Number of pages12
JournalIEEE Transactions on Vehicular Technology
Volume59
Issue number1
DOIs
Publication statusPublished - 1 Jan 2010

Keywords

  • Approximation algorithm
  • Duty cycle
  • Minimum-transmission broadcast (MTB)
  • NP hard
  • Wireless ad hoc network (WANET)

ASJC Scopus subject areas

  • Automotive Engineering
  • Aerospace Engineering
  • Applied Mathematics
  • Electrical and Electronic Engineering

Cite this