Topology control in constant rate mobile adhoc networks
Topology control is the problem of assigning power levels to the nodes of an adhoc network so as to create a specified network topology while minimizing the energy consumed by the network nodes. While considerable theoretical attention has been given to the issue of topology control in wireless adhoc networks, all of that prior work has concerned stationary networks. When the nodes are mobile, there is no algorithm that can guarantee a graph property (such as network connectivity) throughout the node movement. In this paper we study topology control in mobile wireless adhoc networks (MANETs). We define a mobility model, namely the constant rate mobile network (CRMN) model, in which we assume that the speed and direction of each moving node are known. The goal of topology control under this model is to minimize the maximum power used by any network node in maintaining a specified monotone graph property. Network connectivity is one of the most fundamental monotone properties. Under the CRMN model, we develop general frameworks for solving both the decision version (i.e. for a given value p>0, will a specified monotone property hold for the network induced by assigning the power value p to every node?) and the optimization version (i.e. find the minimum value p such that the specified monotone property holds for the network induced by assigning the power value p to every node) of the topology control problems. Efficient algorithms for specific monotone properties can be derived from these frameworks. For example, when the monotone property is network connectivity, our algorithms for the decision and optimization versions have running times of O(n 2 log2 n) and O(n 4 log2 n), respectively. Our results represent a step towards the development of efficient and provably good distributed algorithms for topology control problems for MANETs.
topology control monotone properties graph algorithms dynamic graphs power optimization mobile ad hoc networks