Irrigating Ad Hoc Networks in Constant Time [Extended Abstract]

We propose very simple randomized algorithms to compute sparse overlay networks for geometric random graphs mod-elling wireless communication networks. The algorithms generate in constant time a sparse overlay network that, with high probability, is connected and spans the whole net-work. 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 pro-tocol 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