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.