Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/31831
Title: Sleeping schedule aware minimum transmission broadcast in wireless ad hoc networks
Authors: Hong, J
Li, W
Lu, S
Cao, J 
Chen, D
Keywords: Approximation algorithm
Minimum transmission broadcast
NP-hard problem
Sleeping schedule
Wireless ad hoc network (WANET)
Issue Date: 2008
Source: Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS, 2008, 4724345, p. 399-406 How to cite?
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.
Description: 2008 14th IEEE International Conference on Parallel and Distributed Systems, ICPADS'08, Melbourne, VIC, 8-10 December 2008
URI: http://hdl.handle.net/10397/31831
ISSN: 1521-9097
DOI: 10.1109/ICPADS.2008.16
Appears in Collections:Conference Paper

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

6
Last Week
0
Last month
0
Citations as of Aug 19, 2017

WEB OF SCIENCETM
Citations

3
Last Week
0
Last month
0
Citations as of Aug 15, 2017

Page view(s)

26
Last Week
3
Last month
Checked on Aug 14, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.