(k, r)-Dominating set-based, weighted and adaptive clustering algorithms for mobile ad hoc networks

The creation of stable, scalable and adaptive clusters with good performance, faster convergence rate and with minimal overhead is a challenging task in mobile ad hoc networks (MANETs). This study proposes two clustering techniques for MANETs, which are (k, r)-dominating set-based, weighted and adaptive to changes in the network topology. The set of dominating nodes functions as the clusterheads. The scenario-based clustering algorithm for MANETs (SCAM) is a greedy approximation algorithm, whereas the distributed-SCAM (DSCAM) selects the (k, r)-dominating set through a distributed election mechanism. These algorithms achieve variable degree of clusterhead redundancy through the parameter k which contributes to reliability. Similarly, flexibility in creating variable diameter clusters is achieved with the parameter r. To improve the stability of the created clusters, the affiliation of other nodes with the clusterhead is decided based on the quality of the clusterhead, which is a function of connectivity, stability, residual battery power and transmission range. Mechanisms are available for accounting the group mobility and load balancing. The performance of these algorithms are evaluated through simulation and the results show that these algorithms create stable, scalable and load-balanced clusters with relatively less control overhead in comparison with the existing popular algorithms.