Sleeping schedule aware minimum transmission broadcast in wireless ad hoc networks

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

Research output: Journal article publicationConference articleAcademic researchpeer-review

8 Citations (Scopus)

Abstract

As a fundamental operation of wireless ad hoc networks (WANET), broadcast has been widely studied in the past ten years. However, most existing broadcasting strategies assumed non-sleeping wireless devices. Little attention has been paid to broadcast in WANETs with sleeping schedule, which is a promising power-saving method in wireless networks. In this paper we study the sleeping schedule aware minimum transmission broadcast problem in WANETs (MTB-SA problem) and prove its NP-hardness. Both centralized and distributed approximation algorithms are presented to solve the problem. The centralized algorithm SchmM-Cent has an approximation ratio of 3(ln Δ+1) and time complexity of O(n3). The distributed algorithm SchmM-Dist has a constant approximation ratio of at most 20, while time and message complexity are both O(n). In addition, we provide theoretical analysis and simulations to evaluate the performance of the approximation algorithms.
Original languageEnglish
Article number4724345
Pages (from-to)399-406
Number of pages8
JournalProceedings of the International Conference on Parallel and Distributed Systems - ICPADS
DOIs
Publication statusPublished - 1 Dec 2008
Event2008 14th IEEE International Conference on Parallel and Distributed Systems, ICPADS'08 - Melbourne, VIC, Australia
Duration: 8 Dec 200810 Dec 2008

Keywords

  • Approximation algorithm
  • Minimum transmission broadcast
  • NP-hard problem
  • Sleeping schedule
  • Wireless ad hoc network (WANET)

ASJC Scopus subject areas

  • Hardware and Architecture

Cite this