Adapting d-hop dominating sets to topology changes in ad hoc networks

By grouping neighboring stations into clusters, a clustering architecture could provide a good infrastructure for efficient channel access and packet routing. Unfortunately, existing cluster formation algorithms to construct minimal sets of clusters have to be rerun on the entire network even if there is a small change in the topology. This wastes communication bandwidth and delays user data transmission. In graph-theory terminology, a minimum set of clusterheads in an ad hoc network is precisely a minimum dominating set. In this paper, we show that the problem of adapting a minimum d-hop dominating set to a simple topology change in ad hoc networks is NP-complete. We then propose a heuristic to adapt a given dominating set in an ad hoc network to a simple topology change by looking only at a small local area around the change. We perform some experiments to show that the proposed heuristic performs consistently almost as well as the rerun approach. We also discuss an efficient distributed implementation of our heuristic