On setting-up asynchronous ad hoc wireless networks

Abstract

This paper studies the task of setting up ad hoc wireless networks. In such networks, it is often the case that nodes become active at different times, without coordination or knowledge about network topology. We consider the following tasks: wake-up, clock synchronization, leader election, and multimessage broadcast. We show how to achieve these goals in scalable O(D polylog(n)) time. As a tool we define and give a solution to a quasi-backbone problem, which aims to set up transmission probabilities at nodes in a way that they can be efficiently used to solve other tasks. Our results are obtained by minimalistic algorithms, which do not require power control or carrier sensing capabilities, use very small energy, local computation and memory. Moreover, unlike many previous work, they remain scalable even if the network is not highly connected.