A heuristic method for clustering a large-scale sensor network
A heuristic method for clustering a large-scale sensor network
复制标题
DOI：
10.1109/wts.2007.4563330
复制
发表时间：
2007-04
期刊：
影响因子：
--
通讯作者：
T. Furuta;H. Miyazawa;F. Ishizaki;Mihiro Sasaki;Atsuo Suzuki
中科院分区：
文献类型：
--
作者：
T. Furuta;H. Miyazawa;F. Ishizaki;Mihiro Sasaki;Atsuo Suzuki
针对传感器网络的分簇问题，提出了一种新的启发式算法。启发式方法是使用无容量限制的设施选址问题的传感器网络的分簇问题的提法。它是一种基于Voronoi图的迭代方法。我们还提出了一个并行版本的算法，以减少获得解决方案的时间。所提出的算法进行了调查，其近似解的质量和计算时间，以获得它们。通过对100个传感器算例的近似解与精确解的比较，发现近似解的质量与精确解的质量几乎相同。近似解的计算时间是精确解的千分之一。以一万个传感器为例，通过顺序算法获得解的计算时间约为9.1秒，通过我们的六台计算机并行算法获得解的计算时间约为6.0秒。
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.