WSN16-3: Topology Control for Simple Mobile Networks

Topology control is the problem of assigning power levels to the nodes of an ad hoc network so as to create a specified network topology while minimizing the energy consumption of the network nodes. While considerable theoretical attention has been given to the issue of topology control in wireless ad hoc networks, all of that work has concerned stationary networks. In this paper we carry out a theoretical study of a topology control problem in mobile wireless ad hoc networks (MANETs). For MANETs, we define a topology control problem under the Simple Mobile Network model, where there is one moving node and n stationary nodes. The goal is to minimize the maximum power used by any node in producing a connected network. We provide three polynomial algorithms for solving this problem. Surprisingly, the fastest algorithm runs as fast as the best known algorithm for stationary networks.