Broadcasting algorithms in radio networks with unknown topology
- 2 March 2004
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.
Abstract
In this paper we present new randomized and deterministic algorithms for the classical problem of broadcasting in radio networks with unknown topology. We consider directed n-node radio networks with specified eccentricity D (maximum distance from the source node to any other node). Our first main result closes the gap between the lower and upper bound: we describe an optimal randomized broadcasting algorithm whose running time complexity is O(D log(n/D) + log/sup 2/n), with high probability. In particular, we obtain a randomized algorithm that completes broadcasting in any n-node radio network in time O(n), with high probability. The main source of our improvement is a better "selecting sequence" used by the algorithm that brings some stronger property and improves the broadcasting time. Next, we demonstrate how to apply our approach to deterministic broadcasting, and describe a deterministic oblivious algorithm that completes broadcasting in almost optimal time O(n log/sup 2/D). Finally, we show how our randomized broadcasting algorithm can be used to improve the randomized complexity of the gossiping problem.Keywords
This publication has 15 references indexed in Scilit:
- Deterministic broadcasting time in radio networks of unknown topologyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Distributed broadcast in radio networks of unknown topologyTheoretical Computer Science, 2003
- An O(n 1.5 ) Deterministic Gossiping Algorithm for Radio NetworksAlgorithmica, 2003
- Faster Deterministic Broadcasting in Ad Hoc Radio NetworksLecture Notes in Computer Science, 2003
- Centralized broadcast in multihop radio networksJournal of Algorithms, 2003
- An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio NetworksSIAM Journal on Computing, 1998
- Single round simulation on radio networksJournal of Algorithms, 1992
- A lower bound for radio broadcastJournal of Computer and System Sciences, 1991
- Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detectionDistributed Computing, 1991
- A perspective on multiaccess channelsIEEE Transactions on Information Theory, 1985