Adaptive multi-hop clustering in mobile networks
Matthias R. Brust, Hannes Frey, Steffen Rothkugel · 2007
Clustering algorithms form hierarchical structures of an otherwise homogeneous ad hoc or sensor network. Efficient clustering is a challenging task since the process should be completely self-organized and makes use of incomplete environmental information. As result of these requirements many clustering algorithms use local information and support 1-hop sized clusters. The contribution of this paper is to show how k-hop sized clusters can be formed and maintained by solely using local neighborhood information. k-hop sized clusters are clusters where nodes are at most k-hops away from the clusterhead, i.e. with a cluster diameter of at most 2k. The presented k-hop clustering algorithm takes advantage of nodes' mobility in order to form and maintain k-hop sized clusters. The paper concludes that mobility is a key force for supporting self-organization of clusters. The algorithm described works locally, asynchronously, and fully distributed.