Design and Analysis of a Fast Local Clustering Service for Wireless Sensor Networks

The authors present a fast local clustering service, FLOC, that partitions a multi-hop wireless network into non-overlapping and approximately equal-sized clusters. Each cluster has a cluster-head such that all nodes within unit distance of the cluster-head belong to the cluster but no node beyond distance m from the cluster-head belongs to the cluster. By taking unit distance to be the reliable communication radius and m to be the maximum communication radius, FLOC exploits the double-band nature of wireless radio-model and achieves clustering in constant time regardless of the network size.