Density-aware Probabilistic Clustering in Ad Hoc Networks

Clustering makes an ad hoc network scalable forming easy-to-manage local groups. However, it brings an extra control overhead to create and maintain clustered network topology. In this paper, we propose Probabilistic Clustering Algorithm that is a simple and efficient clustering algorithm with minimal overhead. In this algorithm, cluster heads are determined probabilistically in a distributed fashion. An analytic model is introduced for nodes to compute the probability of declaring themselves as cluster heads. We validate the analytic model by Monte-Carlo simulations. Furthermore, we propose a cross-layer clustered stack and simulate simple applications in stationary and dynamic topologies using OMNeT++. Discrete event simulation results show that Probabilistic Clustering Algorithm eliminates a significant amount of control overhead and the performance of the algorithm is considerably better compared to its opponent, Identity-based Clustering Algorithm.