Initializing newly deployed ad hoc and sensor networks

• DOI: 10.1145/1023720.1023746
• Publication Date: 2004-10-07T17:39:48Z
• Authors: Fabian Kuhn; Thomas Moscibroda; Rogert Wattenhofer
• Keywords: 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology

A newly deployed multi-hop radio network is unstructured and lacks a reliable and efficient communication scheme. In this paper, we take a step towards analyzing the problems existing during the initialization phase of ad hoc and sensor networks. Particularly, we model the network as a multi-hop quasi unit disk graph and allow nodes to wake up asynchronously at any time. Further, nodes do not feature a reliable collision detection mechanism, and they have only limited knowledge about the network topology. We show that even for this restricted model, a good clustering can be computed efficiently. Our algorithm efficiently computes an asymptotically optimal clustering. Based on this algorithm, we describe a protocol for quickly establishing synchronized sleep and listen schedule between nodes within a cluster. Additionally, we provide simulation results in a variety of settings.