On the complexity of clustering multi-hop wireless networks

A Distributed Clustering Algorithm (DCA) is presented that partitions the nodes of a fully mobile network (multi-hop network) into clusters, thus giving the network a hierarchical organization. Nodes are grouped by following a new weight-based criterium that allows the choice of the nodes that coordinate the clustering process based on node mobility-related parameters. The DCA time complexity is proven to be bounded by a network parameter Db that depends on the possibly changing topology of the network rather than on its size, i.e., the invariant number of the network nodes. Simulation results are given which demonstrate that in a mobile scenario Db-and thus the DCA time complexity-is logarithmic in the size of the network. This result improves exponentially a previously known upper bound on the time complexity of distributed clustering for multi-hop wireless networks.