Clustering in mobile ad hoc networks through neighborhood stability-based mobility prediction

Clustering for mobile ad hoc networks (MANETs) offers a kind of hierarchical organization by partitioning mobile hosts into disjoint groups of hosts (clusters). However, the problem of changing topology is recurring and the main challenge in this technique is to build stable clusters despite the host mobility. In this paper, we present a novel clustering algorithm, which guarantees longer lifetime of the clustering structure in comparison to other techniques proposed in the literature. The basis of our algorithm is a scheme that accurately predicts the mobility of each mobile host based on the stability of its neighborhood (i.e., how different is its neighborhood over time). This information is then used for creating each cluster from hosts that will remain neighbors for sufficiently long time, ensuring the formation of clusters that are highly resistant to host mobility. For estimating the future host mobility, we use provably good information theoretic techniques, which allow on-line learning of a reliable probabilistic model for the existing host mobility.