On the stability of paths, Steiner trees and connected dominating sets in mobile ad hoc networks

We propose algorithms that use the complete knowledge of future topology changes to set up benchmarks for the minimum number of times a communication structure (like paths, trees, connected dominating sets, etc.) should change in the presence of a dynamically changing topology. We first present an efficient algorithm called Opt Path Trans that operates on a simple greedy principle: whenever a new source-destination (s-d) path is required at time instant t, choose the longest-living s-d path from time t. The above strategy when repeated over the duration of the s-d session yields a sequence of long-lived stable paths such that number of path transitions is the global minimum. We then propose algorithms to determine the sequence of stable Steiner trees and the sequence of stable connected dominating sets to illustrate that the principle behind Opt Path Trans is very general and can be used to find the stable sequence of any communication structure as long as there is a heuristic or algorithm to determine that particular communication structure in a given network graph. We study the performance of the three algorithms in the presence of complete knowledge of future topology changes as well as using models that predict the future locations of nodes. Performance results indicate that the stability of the communication structures could be considerably improved by making use of the knowledge about locations of nodes in the near future. (C) 2007 Elsevier B.V. All rights reserved.