Topology Control for Simple Mobile Networks.
Liang Zhao, Errol L. Lloyd, Ravi Samikannu · 2006
Topology control is the problem of assigning power levels to the nodes of an ad hoc network so as to create a specified network topol- ogy while minimizing the energy consumption of the network nodes. While considerable theo- retical 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 polyno- mial algorithms for solving this problem. Sur- prisingly, the fastest algorithm runs as fast as the best known algorithm for stationary networks. I. INTRODUCTION In a mobile wireless ad hoc network (MANET), where nodes move freely and self-organize using communication based on radio propagation with- out pre-existing infrastructure, the network topol- ogy is formed based on the transmission ranges of and the routes followed by the nodes. Each node functions, when necessary, as a relay so as to allow multihop communications. The objective in topology control is to maintain a specified network topology such as connected or biconnected. The desired effect of topology control is to reduce energy consumption and MAC layer interference between adjacent nodes, and to increase the ef- fective network capacity. The primary method of accomplishing topology control is by adjusting the transmission powers of the network nodes. That is, each node is assigned a transmission power level so that the induced graph of the network satisfies the specified prop- erties. Further, the assignment of transmission