Maximal independent sets in radio networks

T Moscibroda, R Wattenhofer - Proceedings of the twenty-fourth annual …, 2005 - dl.acm.org
T Moscibroda, R Wattenhofer
Proceedings of the twenty-fourth annual ACM symposium on Principles of …, 2005dl.acm.org
We study the distributed complexity of computing a maximal independent set (MIS) in radio
networks with completely unknown topology, asynchronous wake-up, and no collision
detection mechanism available. Specifically, we propose a novel randomized algorithm that
computes a MIS in time O (log2! n) with high probability, where n is the number of nodes in
the network. This significantly improving on the best previously known solutions. A lower
bound of Ω (log2! n/log log n) given in [11] implies that our algorithm's running time is close …
We study the distributed complexity of computing a maximal independent set (MIS) in radio networks with completely unknown topology, asynchronous wake-up, and no collision detection mechanism available. Specifically, we propose a novel randomized algorithm that computes a MIS in time O(log2! n) with high probability, where n is the number of nodes in the network. This significantly improving on the best previously known solutions. A lower bound of Ω(log2!n / log log n) given in [11] implies that our algorithm's running time is close to optimal. Our result shows that the harsh radio network model imposes merely an additional O(log n) factor compared to Luby's MIS algorithm in the message passing model. This has important implications in the context of ad hoc and sensor networks whose characteristics are closely captured by the radio network model.
ACM Digital Library