Reliable Broadcasting Without Collision Detection | SpringerLink
Skip to main content
Springer Nature Link
Log in

Reliable Broadcasting Without Collision Detection

Extended Abstract

  • Conference paper
SOFSEM 2006: Theory and Practice of Computer Science (SOFSEM 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3831))

Abstract

We propose a dynamic, ad-hoc communication network consisting of mobile units that can warn about traffic jams on motorways.

Our goal is to provide a practical, low cost solution. Therefore we consider very simple wireless communication hardware, without collision detection, with very small bandwidth and a probabilistic model of link failure.

We provide a complete system architecture. For this purpose we design and analyze solutions for size approximation, leader election and broadcasting. Our algorithms are fine-tuned for fast operation in a practical setting. We provide both a theoretical and experimental evaluation of our solutions.

Our contribution is much different from the previous work, where either pure theoretical models with a pure theoretical analysis are provided or algorithms working in practical models are evaluated only through simulations.

Partially supported by the EU within the 6th Framework Programme under contract 001907 (DELIS).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Helbing, D., Schreckenberg, M.: Cellular Automata Simulating Experimental Properties of Traffic Flow. Physical Review E 59(3) (March 1999)

    Google Scholar 

  2. Jurdak, R., Videira Lopes, C., Baldi, P.: A Survey, Classification and Comparative Analysis of Medium Access Control Protocols for Ad Hoc Networks. IEEE Communications Surveys and Tutorials 6(1), 2–16 (First Quarter 2004)

    Article  Google Scholar 

  3. Jurdziński, T., Kutyłowski, M., Zatopiański, J.: Efficient Algorithms for Leader Election in Radio Networks. In: PODC 2002: Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing, pp. 51–57. ACM Press, New York (2002)

    Chapter  Google Scholar 

  4. Jurdziński, T., Kutyłowski, M., Zatopiański, J.: Energy-Efficient Size Approximation of Radio Networks with no Collision Detection. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol. 2387, pp. 279–289. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  5. Malpani, N., Welch, J.L., Vaidya, N.: Leader Election Algorithms for Mobile Ad Hoc Networks. In: DIALM 2000: Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 96–103. ACM Press, New York (2000)

    Chapter  Google Scholar 

  6. Ramanathan, S., Steenstrup, M.: A Survey of Routing Techniques for Mobile Communications Networks. Mob. Netw. Appl. 1(2), 89–104 (1996)

    Article  Google Scholar 

  7. Vollset, E., Ezhilchelvan, P.: A Survey of Reliable Broadcast Protocols for Mobile Ad-Hoc Networks. Technical Report CS-TR-792, University of Newcastle upon Tyne (2003)

    Google Scholar 

  8. Williams, B., Camp, T.: Comparison of Broadcasting Techniques for Mobile Ad Hoc Networks. In: Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pp. 194–205 (2002)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. International Graduate School of Dynamic Intelligent Systems, University of Paderborn,  

    Jarosław Kutyłowski

  2. Institute of Mathematics and Computer Science, Wrocław University of Technology,  

    Filip Zagórski

Authors
  1. Jarosław Kutyłowski
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Filip Zagórski
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod Vodárenskou věží 2, 182 07, Prague 8, Czech Republic

    Jiří Wiedermann  & Július Štuller  & 

  2. Department of Information and Computer Sciences, University of Utrecht, P.O. Box 80.089, 3508, Utrecht, TB, The Netherlands

    Gerard Tel

  3. Faculty of Mathematics and Physics, Charles University, Prague

    Jaroslav Pokorný

  4. Institute of Informatics and Software Engineering Faculty of Informatics and Information technologies, Slovak University of Technology, Ilkovičova 3, 842 16, Bratislava

    Mária Bieliková

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kutyłowski, J., Zagórski, F. (2006). Reliable Broadcasting Without Collision Detection. In: Wiedermann, J., Tel, G., Pokorný, J., Bieliková, M., Štuller, J. (eds) SOFSEM 2006: Theory and Practice of Computer Science. SOFSEM 2006. Lecture Notes in Computer Science, vol 3831. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11611257_37

Download citation

  • DOI: https://doi.org/10.1007/11611257_37

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-31198-0

  • Online ISBN: 978-3-540-32217-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation