How the Hidden-Terminal Problem Affects Clustering in Ad Hoc and Sensor Networks
Thomas Moscibroda, Fabian Kühn, Roger P. Wattenhofer · Repository for Publications and Research Data (ETH Zurich) · 2004
A newly deployed multi-hop radio network is unstructured and lacks a reliable and efficient communication scheme. In this paper, we de fine a model containing the characteristics of the initialization phase of such networks: asynchronous wake-up, scarce knowledge about the topology of the network graph, unreliable collision detection, and the hidden terminal problem. We show that even for this restricted model, a good clustering can be computed efficiently. We propose a new randomized algorithm for clustering in multi-hop radio net works, such as ad-hoc or sensor networks. The algorithm computes an asymptotically optimal clustering in polylogarithmic time. Addi tionally, our simulation results show the efficiency and practicability of the algorithm in a variety of settings.