  Clustering is a standard approach for achieving efficient and scalable
performance in wireless sensor networks. Traditionally, clustering algorithms
aim at generating a number of disjoint clusters that satisfy some criteria. In
this paper, we formulate a novel clustering problem that aims at generating
overlapping multi-hop clusters. Overlapping clusters are useful in many sensor
network applications, including inter-cluster routing, node localization, and
time synchronization protocols. We also propose a randomized, distributed
multi-hop clustering algorithm (KOCA) for solving the overlapping clustering
problem. KOCA aims at generating connected overlapping clusters that cover the
entire sensor network with a specific average overlapping degree. Through
analysis and simulation experiments we show how to select the different values
of the parameters to achieve the clustering process objectives. Moreover, the
results show that KOCA produces approximately equal-sized clusters, which
allows distributing the load evenly over different clusters. In addition, KOCA
is scalable; the clustering formation terminates in a constant time regardless
of the network size.
