Discrete Mobile Centers
Discrete Mobile Centers
复制标题
DOI：
10.1007/s00454-003-2925-6
复制
发表时间：
2003-05
影响因子：
0.8
通讯作者：
Jie Gao;L. Guibas;J. Hershberger;Li Zhang;An Zhu
中科院分区：
文献类型：
--
作者：
Jie Gao;L. Guibas;J. Hershberger;Li Zhang;An Zhu
\emph{我们提出了一种新的随机化算法，用于在平面上的移动节点之间维护一组c个聚类。给定一个特定的簇半径，我们的算法选择并维护一个可变的节点子集作为簇中心。该子集具有以下属性：(1)以选定节点为中心的给定半径的球覆盖所有其他节点；(2)所选中心的数量是最小可能的常数因子近近值。随着节点的移动，基于事件的动态数据结构会根据需要更新集群。这种动态数据结构具有响应快、高效、局部化和紧凑的特点。从某种意义上说，生产的覆盖也很光滑，避免了批发集群的重新安排。如果每个节点都能够感知到自己与其他节点之间的距离，直至集群半径，则该算法可以在不知道节点位置的情况下实现。这种动态集群可以用于许多应用程序中，这些应用程序必须将移动设备连接到一个ad-hoc网络中以协同执行某些任务。}
\emph{We propose a new randomized algorithm for maintaining a set of c lusters among moving nodes in the plane. Given a specified cluster radius, our algorithm selects and maintains a variable subset of the nodes as cluster centers. This subset has the property that (1) balls of the given radius centered at the chosen nodes cover all the others and (2) the number of centers selected is a constant-factor approximation of the minimum possible. As the nodes move, an event-based kinetic data structure updates the clustering as necessary. This kinetic data structure is shown to be responsive, efficient, local, and compact. The produced cover is also smooth, in the sense that wholesale cluster re-arrangements are avoided. The algorithm can be implemented without exact knowledge of the node positions, if each node is able to sense its distance to other nodes up to the cluster radius. Such a kinetic clustering can be used in numerous applications where mobile devices must be interconnected into an ad-hoc network to collaboratively perform some task.}