Topology Stability Analysis and Its Application in Hierarchical Mobile Ad Hoc Networks

The hierarchical architecture has been proven effective for solving the scalability problems in large-scale ad hoc networks. The stability of the hierarchical architecture is a key factor in determining the network performance. Although many solutions have been proposed to construct stable clusters, the maximum stability achievable in mobile environments is still unknown. In this paper, we define three metrics for measuring network stability: (1) the cluster lifetime;(2) the intercluster link lifetime; and (3) the end-to-end path lifetime. We model and analyze the maximum of these lifetimes under the constraint of random node mobility. Analytical results provide the fundamental understanding of the bounds on network stability. Inspired by this understanding, we propose a clustering algorithm and a hierarchical routing protocol that work together to achieve the maximum network stability. The analytical results are verified by simulations.