An ad hoc network is a collection of wireless mobile hosts forming a temporary network without the aid of any fixed infrastructure. Indeed, an important task of an ad hoc network is to determine an appropriate topology over which high-level routing protocols are implemented. Furthermore, since the underlying topology may change with time, we need to design routing algorithms that effectively react to dynamically changing network conditions.
The aim of this paper is to explore the limits of communication in wireless mobile networks, concentrating on local-control algorithms for topology control and routing. We analyze the performance of the algorithms under three measures: throughput, which is the rate at which packets can be delivered, space overhead, i.e. the space necessary to buffer packets, and the total energy consumed due to packet transmissions. Energy consumption is an important performance measure for ad hoc networks since the battery power of mobile nodes is usually limited.
We show that for any distribution of nodes in the 2-dimensional Euclidean plane, a simple local algorithm allows to establish and maintain a connected constant degree overlay network that contains energy-efficient paths between every pair of nodes. We also present a local routing algorithm that works for arbitrary overlay networks. We show that for any sequence of network changes and packet injections the algorithm is within a constant factor of the optimal, with respect to both throughput and energy, when compared to what a best possible routing schedule can achieve under the same sequence of network changes and injections. We also extend our algorithms and analyses for both topology control and routing to account for transmission interference, an important performance-limiting aspect of wireless communication.