Distributed broadcast in unknown radio networks

ABSTRACT

We consider the problem of broadcasting in an unknown radio network modeled as a directed graph G = (V, E), where |V| = n. In unknown networks, every node knows only its own label, while it is unaware of any other parameter of the network, included its neighborhood and even any upper bound on the number of nodes. We show an O(n log n log log n) upper bound on the time complexity of deterministic broadcasting improving upon the time complexity of the currently best known algorithms [6, 12].

REFERENCES

• 1: Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, A lower bound for radio broadcast, Journal of Computer and System Sciences, v.43 n.2, p.290-298, Oct. 1991 [doi>10.1016/0022-0000(91)90015-W]
• 2: N. Alon and J. Spencer. The Probabilistic Method. John Wiley, 1992.
• 3: Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, On the time-complexity of broadcast in radio networks: an exponential gap between determinism randomization, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.98-108, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41849]
• 4: Bogdan S. Chlebus , Leszek Gąsieniec , Alan Gibbons , Andrzej Pelc , Wojciech Rytter, Deterministic broadcasting in unknown radio networks, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.861-870, January 09-11, 2000, San Francisco, California, United States
• 5: Bogdan S. Chlebus , Leszek Gasieniec , Anna Östlin , John Michael Robson, Deterministic Radio Broadcasting, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.717-728, July 09-15, 2000
• 6: M. Chrobak , L. Gasieniec , W. Rytter, Fast broadcasting and gossiping in radio networks, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.575, November 12-14, 2000
• 7: Andrea E. F. Clementi , Angelo Monti , Riccardo Silvestri, Distributed broadcast in radio networks of unknown topology, Theoretical Computer Science, v.302 n.1-3, p.337-364, 13 June 2003 [doi>10.1016/S0304-3975(02)00851-4]
• 8: Artur Czumaj , Wojciech Rytter, Broadcasting Algorithms in Radio Networks with Unknown Topology, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.492, October 11-14, 2003
• 9: Gianluca De Marco , Andrzej Pelc, Faster broadcasting in unknown radio networks, Information Processing Letters, v.79 n.2, p.53-56, June 30, 2001 [doi>10.1016/S0020-0190(00)00178-2]
• 10: Piotr Indyk, Explicit constructions of selectors and related combinatorial structures, with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.697-704, January 06-08, 2002, San Francisco, California
• 11: Dariusz R. Kowalski , Andrzej Pelc, Deterministic Broadcasting Time in Radio Networks of Unknown Topology, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.63-72, November 16-19, 2002
• 12: Dariusz R. Kowalski , Andrzej Pelc, Faster Deterministic Broadcasting in Ad Hoc Radio Networks, SIAM Journal on Discrete Mathematics, v.18 n.2, p.332-346, 2005 [doi>10.1137/S089548010342464X]
• 13: D. R. Kowalski and A. Pelc. Optimal deterministic broadcasting in known topology radio networks. Distributed Computing, 19(3):185--195, 2007.
• 14: Eyal Kushilevitz , Yishay Mansour, An Ω(D log(N/D)) lower bound for broadcast in radio networks, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.65-74, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164059]
• 15: Andrzej Pelc, Broadcasting in radio networks, Handbook of wireless networks and mobile computing, John Wiley & Sons, Inc., New York, NY, 2002
• 16: D. Peleg. Deterministic radio broadcast with no topological knowledge. Manuscript, 2000.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms
      G.2.3 Applications

General Terms:
Algorithms, Design, Theory