More Web Proxy on the site http://driver.im/

article

Deterministic broadcasting in ad hoc radio networks

Authors:

Bogdan S. Chlebus,

Leszek Gasieniec,

Wojciech RytterAuthors Info & Claims

Distributed Computing, Volume 15, Issue 1

Pages 27 - 38

https://doi.org/10.1007/s446-002-8028-1

Published: 01 January 2002 Publication History

Abstract

We consider the problem of distributed deterministic broadcasting in radio networks of unknown topology and size. The network is synchronous. If a node u can be reached from two nodes which send messages in the same round, none of the messages is received by u. Such messages block each other and node u either hears the noise of interference of messages, enabling it to detect a collision, or does not hear anything at all, depending on the model. We assume that nodes know neither the topology nor the size of the network, nor even their immediate neighborhood. The initial knowledge of every node is limited to its own label. Such networks are called ad hoc multi-hop networks. We study the time of deterministic broadcasting under this scenario.For the model without collision detection, we develop a linear-time broadcasting algorithm for symmetric graphs, which is optimal, and an algorithm for arbitrary n-node graphs, working in time O(n^11/6). Next we show that broadcasting with acknowledgement is not possible in this model at all.For the model with collision detection, we develop efficient algorithms for broadcasting and for acknowledged broadcasting in strongly connected graphs.

References

[1]

1. N. Alon, A. Bar-Noy, N. Linial, D. Peleg: A lower bound for radio broadcast, J Comput Syst Sci 43, 290-298 (1991)]]

Digital Library

[2]

2. B. Awerbuch: A new distributed depth-first-search algorithm, Inform Process Lett 20, 147-150 (1985)]]

[3]

3. B. Awerbuch, O. Goldreich, D. Peleg, R. Vainish: A tradeoff between information and communication in broadcast protocols, Journal of the ACM 37, 238-256 (1990)]]

Digital Library

[4]

4. R. Bar-Yehuda, O. Goldreich, A. Itai: On the time complexity of broadcast in radio networks: an exponential gap between determinism and randomization, J Comput Syst Sci 45, 104-126 (1992)]]

Digital Library

[5]

5. R. Bar-Yehuda, A. Israeli, A. Itai: Multiple communication in multihop radio networks, SIAM J Comput 22, 875-887 (1993)]]

Digital Library

[6]

6. S. Basagni, D. Bruschi, I. Chlamtac: A mobility-transparent deterministic broadcast mechanism for ad hoc networks, IEEE/ACM Trans Netw 7, 799-807 (1999)]]

Digital Library

[7]

7. S. Basagni, A.D. Myers, V.R. Syrotiuk: Mobility-independent flooding for real-time multimedia applications in ad hoc networks, Proc. 1999 IEEE Emerging Technologies Symposium on Wireless Communications & Systems, Richardson, TX]]

[8]

8. D. Bruschi, M. Del Pinto: Lower bounds for the broadcast problem in mobile radio networks, Distrib Comput 10, 129-135 (1997)]]

Digital Library

[9]

9. I. Chlamtac, A. Faragó: Making transmission schedule immune to topology changes in multi-hop packet radio networks, IEEE/ACM Trans Netw 2, 23-29 (1994)]]

Digital Library

[10]

10. I. Chlamtac, A. Faragó, H. Zhang: Time-spread multiple access (TSMA) protocols for multihop mobile radio networks, IEEE/ACM Trans Netw 5, 804-812 (1997)]]

Digital Library

[11]

11. I. Chlamtac, S. Kutten: On broadcasting in radio networks - problem analysis and protocol design, IEEE Trans Commun 33, 1240-1246 (1985)]]

[12]

12. I. Chlamtac, S. Kutten: Tree-based broadcasting in multihop radio networks, IEEE Trans Comput 36, 1209-1223 (1987)]]

Digital Library

[13]

13. I. Chlamtac, O. Weinstein: The wave expansion approach to broadcasting in multihop radio networks, IEEE Trans Commun 39, 426-433 (1991)]]

[14]

14. B.S. Chlebus, L. Gasieniec, A. Gibbons, A. Pelc, W. Rytter: Deterministic broadcasting in unknown radio networks, Proc. 11th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA'2000), pp 861-870]]

[15]

15. B.S. Chlebus, L. Gasieniec, A. Östlin, J.M. Robson: Deterministic radio broadcasting, Proc. 27th Int. Coll. on Automata, Languages and Programming, (ICALP'2000), July 2000, Geneva, Switzerland, LNCS 1853, pp 717-728]]

Digital Library

[16]

16. M. Chrobak, L. Gasieniec, W. Rytter: Fast broadcasting and gossiping in radio networks, Proc. 41st Symposium on Foundations of Computer Science (FOCS 2000), Redondo Beach, California, U.S.A., 2000, pp 575-581]]

[17]

17. A.E.F. Clementi, A. Monti, R. Silvestri: Selective families, superimposed codes, and broadcasting on unknown radio networks, Proc. 12th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA'2001), pp 709-718]]

[18]

18. G. De Marco, A. Pelc: Faster broadcasting in unknown radio networks, Information Processing Letters 79, 53-56 (2001)]]

Digital Library

[19]

19. A. Dessmark, A. Pelc: Deterministic radio broadcasting at low cost, Proc. 18th Ann. Symposium on Theoretical Aspects of Computer Science (STACS 2001) February 2001, Dresden, Germany, LNCS 2010, pp 158-169]]

[20]

20. K. Diks, E. Kranakis, D. Krizanc, A. Pelc: The impact of knowledge on broadcasting time in radio networks, Proc. 7th European Symposium on Algorithms, ESA'99, Prague, Czech Republic, July 1999, LNCS 1643, pp 41-52]]

[21]

21. I. Gaber, Y. Mansour: Broadcast in radio networks, Proc. 6th Ann. ACM-SIAM Symp. on Discrete Algorithms, SODA'95, pp 577-585]]

Digital Library

[22]

22. R. Gallager, A perspective on multiaccess channels, IEEE Trans Inf Theory 31, 124-142 (1985)]]

Digital Library

[23]

23. L. Gargano, A. Pelc, S. Pérennes, U. Vaccaro: Efficient communication in unknown networks, Networks, to appear]]

[24]

24. L. Gasieniec, A. Pelc, D. Peleg: The wakeup problem in synchronous broadcast systems, SIAM Journal on Discrete Mathematics 14, 207-222 (2001)]]

Digital Library

[25]

25. F.K. Hwang, The time complexity of deterministic broadcast radio networks, Discrete Appl. Math. 60, 219-222 (1995)]]

Digital Library

[26]

26. E. Kranakis, D. Krizanc, A. Pelc: Fault-tolerant broadcasting in radio networks, Journal of Algorithms 39, 47-67 (2001)]]

Digital Library

[27]

27. E. Kushilevitz, Y. Mansour: An Ω(D log(N/D)) lower bound for broadcast in radio networks, SIAM J Comput 27, 702-712 (1998)]]

Digital Library

[28]

28. E. Kushilevitz, Y. Mansour: Computation in noisy radio networks, Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, SODA'98, pp 236-243]]

[29]

29. E. Pagani, G.P. Rossi: Reliable broadcast in mobile multihop radio networks, Proc. 3rd Annual ACM/IEEE Int. Conf. on Mobile Computing and Networking, (MOBICOM'97), 1997, pp 34-42]]

Digital Library

[30]

30. K. Pahlavan, A. Levesque: Wireless Information Networks, New York: Wiley 1995]]

[31]

31. D. Peleg, Deterministic radio broadcast with no topological knowledge, manuscript 2000]]

[32]

32. A. Sen, M.L. Huson: A new model for scheduling packet radio networks, Proc. 15th Annual Joint Conference of the IEEE Computer and Communication Societies (IEEE INFOCOM'96), 1996, 1116-1124]]

[33]

33. A.S. Tanenbaum: Computer Networks, Englewood Cliffs, NJ: Prentice Hall 1996]]

[34]

34. U. Vishkin, Deterministic sampling - A new technique for fast pattern matching, SIAM J Comput 20, 22-40 (1991)]]

Digital Library

Cited By

Dong LKowalski DKudaravalli HMosteiro M(2022)Information dissemination in wireless ad-hoc networks under the weighted-TIM frameworkTheoretical Computer Science10.1016/j.tcs.2021.11.022901:C(19-34)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1016/j.tcs.2021.11.022
Nanahji K(2022)Exactly Optimal Deterministic Radio Broadcasting with Collision DetectionStructural Information and Communication Complexity10.1007/978-3-031-09993-9_13(234-252)Online publication date: 27-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-09993-9_13
Ellen FGorain BMiller APelc A(2021)Constant-Length Labeling Schemes for Deterministic Radio BroadcastACM Transactions on Parallel Computing10.1145/34706338:3(1-17)Online publication date: 20-Sep-2021
https://dl.acm.org/doi/10.1145/3470633
Show More Cited By

Index Terms

Deterministic broadcasting in ad hoc radio networks

Recommendations

Broadcasting in undirected ad hoc radio networks
Special issue: PODC 02

We consider distributed broadcasting in radio networks, modeled as undirected graphs, whose nodes have no information on the topology of the network, nor even on their immediate neighborhood. For randomized broadcasting, we give an algorithm working in ...
Time of Deterministic Broadcasting in Radio Networks with Local Knowledge

We consider broadcasting in radio networks, modeled as undirected graphs, whose nodes know only their own label and labels of their neighbors. In every step every node acts either as a transmitter or as a receiver. A node acting as a transmitter sends ...
Acknowledged broadcasting and gossiping in ad hoc radio networks

A radio network is a collection of transmitter-receiver devices (referred to as nodes). Acknowledged radio broadcasting (ARB) means transmitting a message from one special node called the source to all other nodes and informing the source about its ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Distributed Computing

Distributed Computing Volume 15, Issue 1

January 2002

63 pages

ISSN:0178-2770

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 January 2002

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

84
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dong LKowalski DKudaravalli HMosteiro M(2022)Information dissemination in wireless ad-hoc networks under the weighted-TIM frameworkTheoretical Computer Science10.1016/j.tcs.2021.11.022901:C(19-34)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1016/j.tcs.2021.11.022
Nanahji K(2022)Exactly Optimal Deterministic Radio Broadcasting with Collision DetectionStructural Information and Communication Complexity10.1007/978-3-031-09993-9_13(234-252)Online publication date: 27-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-09993-9_13
Ellen FGorain BMiller APelc A(2021)Constant-Length Labeling Schemes for Deterministic Radio BroadcastACM Transactions on Parallel Computing10.1145/34706338:3(1-17)Online publication date: 20-Sep-2021
https://dl.acm.org/doi/10.1145/3470633
Hu AChen H(2021)Data Visualization Analysis of Knowledge Graph Application2021 2nd International Conference on Artificial Intelligence and Information Systems10.1145/3469213.3472783(1-10)Online publication date: 28-May-2021
https://dl.acm.org/doi/10.1145/3469213.3472783
Czumaj ADavies P(2021)Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio NetworksJournal of the ACM10.1145/344638368:2(1-22)Online publication date: 28-Jan-2021
https://dl.acm.org/doi/10.1145/3446383
Chrobak MCostello KGąsieniec L(2021)Information gathering in ad-hoc radio networksInformation and Computation10.1016/j.ic.2021.104769281:COnline publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1016/j.ic.2021.104769
Krisko CMiller A(2021)Labeling Schemes for Deterministic Radio Multi-broadcastGraph-Theoretic Concepts in Computer Science10.1007/978-3-030-86838-3_29(374-387)Online publication date: 23-Jun-2021
https://dl.acm.org/doi/10.1007/978-3-030-86838-3_29
Dufoulon FBurman JBeauquier JEmek YCachin C(2020)Can Uncoordinated Beeps tell Stories?Proceedings of the 39th Symposium on Principles of Distributed Computing10.1145/3382734.3405699(408-417)Online publication date: 31-Jul-2020
https://dl.acm.org/doi/10.1145/3382734.3405699
Ellen FGilbert SScheideler CSpear M(2020)Constant-Length Labelling Schemes for Faster Deterministic Radio BroadcastProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400238(213-222)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400238
Ellen FGorain BMiller APelc AScheideler CBerenbrink P(2019)Constant-Length Labeling Schemes for Deterministic Radio BroadcastThe 31st ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3323165.3323194(171-178)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3323165.3323194
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents