loading...
A Local Voronoi Diagram-Based Approximate Algorithm for Minimum Disc Cover Problem
Adelaide, Australia December 03-December 06
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/PDCAT.2007.38Eighth International Conference on Pa ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
KeZhong Lu, XiaoHui Lin, FengXia Ding, "A Local Voronoi Diagram-Based Approximate Algorithm for Minimum Disc Cover Problem," Parallel and Distributed Computing Applications and Technologies, International Conference on, pp. 421-425, Eighth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2007), 2007.
 
 
BibTex
x
 
@article{ 10.1109/PDCAT.2007.38,
author = {KeZhong Lu and XiaoHui Lin and FengXia Ding},
title = {A Local Voronoi Diagram-Based Approximate Algorithm for Minimum Disc Cover Problem},
journal ={Parallel and Distributed Computing Applications and Technologies, International Conference on},
volume = {0},
year = {2007},
isbn = {0-7695-3049-4},
pages = {421-425},
doi = {http://doi.ieeecomputersociety.org/10.1109/PDCAT.2007.38},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel and Distributed Computing Applications and Technologies, International Conference on
TI - A Local Voronoi Diagram-Based Approximate Algorithm for Minimum Disc Cover Problem
SN - 0-7695-3049-4
SP421
EP425
A1 - KeZhong Lu,
A1 - XiaoHui Lin,
A1 - FengXia Ding,
PY - 2007
VL - 0
JA - Parallel and Distributed Computing Applications and Technologies, International Conference on
ER -
 
Minimum disc cover problem which is NP-hard is kernel of node scheduling protocol in wireless sensor networks. Size of disc cover set obtained by approximate algorithm determines performance of node scheduling protocol. But the approximation ratios of present approximate algorithms aren't good. This paper proposes a local Voronoi diagrams-based approximate algorithm which can obtain a minimal disc cover set. Theoretical analyses show that the approximation ratio of this algorithm is less than 3. Experiments show that the size of disc cover set obtained by this algorithm is less than 43% of present algorithms and the average coverage degree is around 2.11 which are 1.7 times of optimal. Key words: wireless sensor network; node scheduling; minimum disc cover problem; disc cover set; average coverage degree
Citation:
KeZhong Lu, XiaoHui Lin, FengXia Ding, "A Local Voronoi Diagram-Based Approximate Algorithm for Minimum Disc Cover Problem," pdcat, pp.421-425, Eighth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2007), 2007
Usage of this product signifies your acceptance of the Terms of Use.