Distributed and mobility-adaptive clustering for ad hoc networks

A distributed algorithm is presented that partitions the nodes of a fully mobile network (ad hoc network) into clusters, thus giving the network a hierarchical organization. The algorithm is proven to be adaptive to changes in the network topology due to nodes' mobility and to nodes addition/removal. A new weight-based mechanism is introduced for the efficient cluster formation/maintenance that allows the cluster organization to be configured for specific applications and adaptive to changes in the network status, not available in previous solutions. Simulation results are provided that demonstrate up to an 85% reduction on the communication overhead associated with the cluster maintenance with respect to clustering algorithms previously proposed.