DOI: 10.1007/s00454-003-2925-6Discrete Comput Geom 30:45–63 (2003)Discrete & ComputationalGeometry©2003 Springer-Verlag New York Inc.Discrete Mobile Centers∗Jie Gao,1Leonidas J. Guibas,1John Hershberger,2Li Zhang,3and An Zhu11Department of Computer Science, Stanford University,Stanford, CA 94305, USA{jgao,guibas,anzhu}@cs.stanford.edu2Mentor Graphics, 8005 S.W. Boeckman Road,Wilsonville, OR 97070, USAjohn [email protected] Systems Research Center, 130 Lytton Avenue,Palo Alto, CA 94301, [email protected]. We propose a new randomized algorithm for maintaining a set of clustersamong moving nodes in the plane. Given a specified cluster radius, our algorithm selectsand maintains a variable subset of the nodes as cluster centers. This subset has the propertythat (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 minimumpossible. As the nodes move, an event-based kinetic data structure updates the clustering asnecessary. 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-arrangementsare avoided. This clustering algorithm is distributed in nature and can enable numerousapplications in ad hoc wireless networks, where mobile devices must be interconnected toperform various tasks collaboratively.1. IntroductionCollaborating mobile devices are of interest in diverse applications, from wireless net-working to sensor nets to robot exploration. In these applications there are mobile nodes∗The work of J. Gao, L. Guibas, and A. Zhu was supported in part by NSF Grants CCR-9623851 andCCR-9910633, US Army MURI Grant DAAH04-96-1-0007 and AASERT Grant DAAG55-97-0218, and agrant from the Stanford Networking Research Center. The work of A. Zhu was also supported in part by aGRPW fellowship from Bell Labs, Lucent Technologies.46 J. Gao, L. J. Guibas, J. Hershberger, L. Zhang, and A. Zhuthat need to communicate as they move so as to accomplish the task at hand. These taskscan vary from establishing an ad-hoc multi-hop network infrastructure that allows point-to-point communication, to aggregating and assimilating data collected by distributedsensors, to mapping an unknown environment collaboratively. A challenge common toall these tasks is that communication is usually accomplished using low-power radiolinks or other short-range technologies. As a result only nodes sufficiently close to eachother can communicate directly and therefore the communication topology of the net-work is strongly affected by node motion (as well as obstacle interference, etc.). Themobile networking community has been especially active in studying such problems inthe context of networking protocols allowing the seamless integration of devices such asPDAs, mobile PCs, phones, pagers, etc., that can be mobile as well as switch off and onat arbitrary times. An example of such an effort is the recent Bluetooth specification [12].A principle that has been discussed a number of times for enabling such collaborativetasks is the organization of the mobile nodes into clusters [3], [6], [10], [22]. Clusteringallows hierarchical structures to be built on the mobile nodes and enables more efficientuse of scarce resources, such as bandwidth and power. For example, if the cluster sizecorresponds roughly with the direct communication range of the nodes, much simplerprotocols can be used for routing and broadcasting within a cluster; furthermore, the sametime or frequency division multiplexing can be re-used across non-overlapping clusters.Clustering also allows the health of the network to be monitored and misbehaving nodesto be identified, as some nodes in a cluster can play watchdog roles over other nodes [18].Motivated by these issues, in this paper we study the problem of maintaining a cluster-ing for a set of n moving points or nodes in the plane. There is, of course, a huge literatureon clustering, as the problem in many variations has been studied by several differentcommunities, including operations research, statistics, and computational geometry. Inour setting we assume that all the nodes are identical and each can communicate withina region around itself, which we take to be an Lpball. For most of the paper we focus ona ball in the L∞metric, that is an axis-aligned square whose side is of length r, as thismakes the analysis the simplest. We call two nodes visible to each other if they are withinthe communication range of each other. We seek a minimal subset of the n nodes, thecenters, such that every node is visible to at least one of the centers. In the mobile devicesetting, unlike the general facilities location context, it is appropriate to insist that thecenters are located at the nodes themselves, as these are the only active elements in thesystem; thus we are interested in “discrete center” problems. We survey the literature onthe static version of this problem in Section 2. The problem is known to be NP-completeand most of the work has focused on approximation algorithms.Much less is known, however, about maintaining a clustering on mobile nodes. Therehave been a few papers in the mobile networking community [3], [6], [10], [22] proposingand simulating a number of distributed algorithms for cluster maintenance, but to ourknowledge there has been very little prior work on a theoretical analysis of the problem.In particular, existing algorithms for the static version cannot be adapted to the mobilecase efficiently. Many static algorithms utilize space partition methods, i.e., they partitionspace into smaller sub-regions and solve for each region separately. For instance, onecan design a simple constant approximation algorithm by choosing one center out ofevery pre-fixed grid square of length r/2. Algorithms of such flavor totally ignore theunderlying topology of the node set and, as a result, suffer from many unnecessaryDiscrete Mobile Centers 47solution changes during node motion. For example, if nodes are traveling together withthe same velocity, then in fact there is no need to change the solution. A “good” algorithmshould only undergo solution changes that are necessary. Another desirable property isthat the algorithm can be implemented in a distributed manner on nodes with modestcapabilities, so as to be useful in the mobile ad hoc network setting. As nodes movearound,