SIZE AND HOP RESTRICTED CLUSTER FORMATION IN MOBILE AD-HOCNETWORKS

摘要

Clustering has been employed as a means to tackle thescalability issues in mobile ad-hoc networks. Clusteringhelps in hierarchical organization of nodes in the network,thereby easing the management of large number of nodes.This paper proposes a distributed, size and hop limited initialcluster formation that can be used in large mobile ad-hocnetworks. The distributed cluster formation algorithm is atwo-constrained tree-partitioning algorithm with number ofhops (K) and number of nodes per cluster (S) as metrics forcluster formation. The ad-hoc network is modeled as a unitdisk graph. This graph is reduced to a spanning tree rooted atan arbitrary vertex r using a distributed implementation ofMinimum Connected Dominated Set (MCDS) technique.The distributed tree partitioning method proposed in thepaper will then partition the MCDS spanning tree into subtreesof bounded diameter and size. The proposed initialcluster formation technique has a message and timecomplexity of O(n).