Performance analysis of mobility-based d-hop (MobDHop) clustering algorithm for mobile ad hoc networks

Abstract

This paper presents the performance analysis of the mobility-based d-hop (MobDHop) clustering algorithm, which forms variable-diameter clusters based on node mobility patterns in MANETs. Unlike existing clustering algorithms, the diameter of clusters is not restricted by any preset value. Instead, the diameter of clusters is flexible and determined by the stability of clusters. Nodes which have similar moving patterns are grouped into one cluster in order to achieve maximum cluster stability. Unlike existing multihop clustering algorithms, MobDHop only requires 1-hop neighbourhood knowledge instead of multihop neighbourhood knowledge. This makes MobDHop a truly adaptive, distributed and localized algorithm. This paper first presents the empirical results of MobDHop based on a series of extensive NS-2 simulations. The simulation results show that MobDHop forms clusters which are more stable than those formed by Lowest-ID and Max Connectivity Clustering Algorithm in both Random Waypoint and Reference Point Group Mobility Model. Subsequently, the performance of MobDHop is examined from a theoretical perspective where both the time and message complexities are derived. A comparison of MobDHop and four other clustering algorithms is presented. We show that the overhead incurred by multihop clustering has a similar asymptotic bound as 1-hop clustering while being able to reap the benefits of multihop clusters. © 2006 Elsevier B.V. All rights reserved.