WLC20-1: Topology Control for Constant Rate Mobile Networks

Controlling the topology of a wireless ad hoc network is very important from the point of view of performance. One known technique for controlling the topology is through the assignment of appropriate transmission power levels to the nodes. Such an assignment aims to minimize a specified function of the powers assigned to nodes. While this problem has been widely studied for the case of stationary wireless networks, few reported theoretical results for mobile wireless networks (MANETs). In this paper, we consider the topology control problem for MANETs from a theoretical perspective. We define a topology control problem under the constant rate mobile network model. In this model, all the n nodes in the network may move. Associated with each moving node are its constant moving speed and direction. The goal is to minimize the maximum power used by any network node in producing a connected network. We provide two polynomial algorithms for solving this problem: one for the decision version, the other for the optimization version.