Title :
A heuristic method for clustering a large-scale sensor network
Author :
Furuta, Takehiro ; Miyazawa, H. ; Ishizaki, F. ; Sasaki, Motoharu ; Suzuki, A.
Author_Institution :
Fac. of Math. Sci. & Inf. Eng., Nanzan Univ., Aichi
Abstract :
We present a new heuristic method for a clustering problem of sensor networks. The heuristic method is using the uncapacitated facility location problem formulation for the clustering problem of sensor networks. It is an iterative method based on the Voronoi diagram. We also propose a parallel version of the heuristics to reduce the time to obtain a solution. The proposed algorithms are investigated for the quality of their approximate solutions and computational time to obtain them. By comparing the approximate solutions to the exact solutions for examples of one hundred sensors, we found that the quality of the approximate solutions is almost the same as that of the exact ones. The computational time to obtain the approximate solutions is a thousandth of that of obtaining the exact solution. For examples of ten thousand sensors, the computational time to obtain a solution is about 9.1 seconds by the sequential algorithm and about 6.0 seconds by our parallel algorithm with six computers.
Keywords :
computational geometry; iterative methods; wireless sensor networks; Voronoi diagram; clustering problem; computational time; heuristic method; iterative method; large-scale sensor network; parallel algorithm; sequential algorithm; uncapacitated facility location; Batteries; Capacitive sensors; Clustering algorithms; Clustering methods; Concurrent computing; Energy efficiency; Iterative algorithms; Iterative methods; Large-scale systems; Wireless sensor networks;
Conference_Titel :
Wireless Telecommunications Symposium, 2007. WTS 2007
Conference_Location :
Pomona, CA
Print_ISBN :
978-1-4244-0696-8
Electronic_ISBN :
1934-5070
DOI :
10.1109/WTS.2007.4563330
