G. Venkataraman and S. Emmanuel (Singapore)
Ad-hoc Networks, Cluster formation, Clustering algorithm, Distributed tree partitioning, Two constrained partitioning.
Clustering has been employed as a means to tackle the scalability issues in mobile ad-hoc networks. Clustering helps 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 initial cluster formation that can be used in large mobile ad-hoc networks. The distributed cluster formation algorithm is a two-constrained tree-partitioning algorithm with number of hops (K) and number of nodes per cluster (S) as metrics for cluster formation. The ad-hoc network is modeled as a unit disk graph. This graph is reduced to a spanning tree rooted at an arbitrary vertex r using a distributed implementation of Minimum Connected Dominated Set (MCDS) technique. The distributed tree partitioning method proposed in the paper will then partition the MCDS spanning tree into sub trees of bounded diameter and size. The proposed initial cluster formation technique has a message and time complexity of O(n).
Important Links:
Go Back
