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 language | English |
|---|---|
| Article number | 4724345 |
| Pages (from-to) | 399-406 |
| Number of pages | 8 |
| Journal | Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS |
| DOIs | |
| Publication status | Published - 1 Dec 2008 |
| Event | 2008 14th IEEE International Conference on Parallel and Distributed Systems, ICPADS'08 - Melbourne, VIC, Australia Duration: 8 Dec 2008 → 10 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