| Abstract |
|
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
|
 Additional Information
|
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
|
