Algorithm for Cluster Establishment(ACE)
In this paper, we introduce ACE (the Algorithm for Cluster Establishment), an emergent cluster formation algorithm. The algorithm consists of two logical parts
Øthe first controls how clusters can spawn (by having a node elect itself to be leader) and
Øthe second controls how clusters migrate dynamically to reduce overlap
Note: In general, clusters are only created when the overlap of the new cluster with existing clusters is small. After creation, clusters will move apart from each other to minimize the amount of mutual overlap, thus yielding a near-optimal packing in very few iterations.
Spawning of new clusters
New clusters are spawned in a self-elective (self employed) process — when a node decides to become a cluster head, it will broadcast a RECRUIT message to its neighbors, who will become followers of the new cluster.
ØA node can be a follower of more than one cluster while the protocol is running (it picks a single cluster for membership only at the end of the protocol).
Migration of existing clusters
Migration of an existing cluster is controlled by the cluster head.
ØEach cluster head will periodically POLL all its followers (i.e., all its neighbors) to determine which is the best candidate to become the new leader of the cluster.
ØThe best candidate is the node which, if it were to become cluster head, would have the greatest number of nodes as followers while minimizing the amount of overlap with existing clusters.
ØOnce the best candidate is determined by the current cluster head,it will PROMOTE the best candidate as the new cluster head and ABDICATE its position as the old cluster head.
Thus, the position of the cluster will appear to migrate in the direction of the new cluster head as some of the former followers of the old cluster- head are no longer part of the cluster, while some new nodes near the new cluster head become new followers of the cluster.