Distributed Spatial Clustering in Sensor Networks
Distributed Spatial Clustering in Sensor Networks
复制标题
DOI：
10.1007/11687238_57
复制
发表时间：
2006-03
期刊：
影响因子：
--
通讯作者：
Anand Meka;Ambuj K. Singh
中科院分区：
文献类型：
--
作者：
Anand Meka;Ambuj K. Singh
传感器网络监测大地理区域的物理现象。如果科学家了解潜在的数据分布，他们可以对这些现象获得有价值的见解。通过空间聚类可以有效地提取这些数据特征，空间聚类将网络划分为一组具有相似观测的空间区域。本文的目标是执行这样的空间聚类，特别是δ-聚类，其中簇内任何两个节点之间的数据相异性最多为δ。本文提出了一个网内聚类算法ELink，它在时间和消息复杂度上都能为同步和异步网络生成良好的δ-聚类，其中N表示网络规模。在真实的数据集和合成数据集上的实验结果表明，ELink的聚类质量与集中式算法相当，并且上级优于其他分布式算法.此外，在通信成本方面，ELink的性能比集中式算法好10倍，比分布式算法好3-4倍。我们还开发了一个分布式索引结构，使用生成的集群，可用于回答范围查询和路径查询。查询算法将空间搜索定向到相关的聚类，从而使性能增益达到竞争技术的5倍。
Sensor networks monitor physical phenomena over large geographic regions. Scientists can gain valuable insight into these phenomena, if they understand the underlying data distribution. Such data characteristics can be efficiently extracted throughspatial clustering, which partitions the network into a set of spatial regions with similar observations. The goal of this paper is to perform such a spatial clustering, specificallyδ-clustering, where the data dissimilarity between any two nodes inside a cluster is at mostδ. We present anin-networkclustering algorithmELinkthat generates goodδ-clusterings for both synchronous and asynchronous networks intime and inO(N) message complexity, whereNdenotes the network size. Experimental results on both real world and synthetic data sets show that ELink’s clustering quality is comparable to that of a centralized algorithm, and is superior to other alternative distributed techniques. Furthermore, ELink performs 10 times better than the centralized algorithm, and 3-4 times better than the distributed alternatives in communication costs. We also develop a distributed index structure using the generated clusters that can be used for answering range queries and path queries. The query algorithms direct the spatial search to relevant clusters, leading to performance gains of up to a factor of 5 over competing techniques.