Irrigating ad hoc networks in constant time

We propose very simple randomized algorithms to compute sparse overlay networks for geometric random graphs modelling wireless communication networks. The algorithms generate in constant time a sparse overlay network that, with high probability, is connected and spans the whole network. Moreover, by making use of the "power of choice" paradigm, the maximum degree can be made as small as O(log log n), where n is the size of the network. We show the usefulness of this kind of overlays by giving a new protocol for the classical broadcast problem, where a source is to send a message to the whole network. Our experimental evaluation shows that our approach outperforms the well-known gossiping approach in all situations where the cost of a message can be charged to the pair (sender, receiver), i.e. to the edge connecting the two. This includes sensor networks. Copyright 2005 ACM.