Document Open Access Logo

Broadcasting in an Unreliable SINR Model

Authors Fabian Kuhn, Philipp Schneider

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2017.3.pdf
  • Filesize: 0.62 MB
  • 21 pages

Document Identifiers

Author Details

Fabian Kuhn
Philipp Schneider

Cite AsGet BibTex

Fabian Kuhn and Philipp Schneider. Broadcasting in an Unreliable SINR Model. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 3:1-3:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.OPODIS.2017.3

Abstract

We investigate distributed algorithms for broadcasting in unreliable wireless networks. Our basic setting is the signal to noise and interference ratio (SINR) model, which captures the physical key characteristics of wireless communication. We consider a dynamic variant of this model in which an adversary can adaptively control the model parameters for each individual transmission. Moreover, we assume that the network devices have no information about the geometry or the topology of the network and do neither know the exact model parameters nor do they have any control over them. Our model is intended to capture the inherently unstable and unreliable nature of real wireless transmission, where signal quality and reception depends on many different aspects that are often hard to measure or predict. We show that with moderate adaptations, the broadcast algorithm of Daum et al. [DISC 13] also works in such an adversarial, much more dynamic setting. The algorithm allows to broadcast a single message in a network of size n in time O(D·polylog(n+R)), where D is the diameter and R describes the granularity of the communication graph.
Keywords
  • radio networks
  • wireless networks
  • broadcast
  • SINR model
  • unreliable communication
  • dynamic networks

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. L. Anantharamu, B. S. Chlebus, D. R. Kowalski, and M. A. Rokicki. Medium access control for adversarial channels with jamming. In Proceedings of the 18th International Conference on Structural Information and Communication Complexity, SIROCCO quotesingle11, 2011. Google Scholar
  2. Baruch Awerbuch, Andréa W. Richa, and Christian Scheideler. A jamming-resistant MAC protocol for single-hop wireless networks. In Rida A. Bazzi and Boaz Patt-Shamir, editors, Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC 2008, Toronto, Canada, August 18-21, 2008, pages 45-54. ACM, 2008. URL: http://dx.doi.org/10.1145/1400751.1400759.
  3. Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy A. Lynch, and Calvin C. Newport. Structuring unreliable radio networks. Distributed Computing, 27(1):1-19, 2014. URL: http://dx.doi.org/10.1007/s00446-013-0198-8.
  4. Sebastian Daum, Seth Gilbert, Fabian Kuhn, and Calvin C. Newport. Broadcast in the ad hoc SINR model. In Yehuda Afek, editor, Distributed Computing - 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14-18, 2013. Proceedings, volume 8205 of Lecture Notes in Computer Science, pages 358-372. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-41527-2_25.
  5. Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, and Calvin C. Newport. Secure communication over radio channels. In Rida A. Bazzi and Boaz Patt-Shamir, editors, Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC 2008, Toronto, Canada, August 18-21, 2008, pages 105-114. ACM, 2008. URL: http://dx.doi.org/10.1145/1400751.1400767.
  6. P. Erdös, P. Frankl, and Z. Füredi. Families of finite sets in which no set is covered by the union of r others. Israel Journal of Mathematics, 51(1), 1985. URL: http://dx.doi.org/10.1007/BF02772959.
  7. Mohsen Ghaffari, Erez Kantor, Nancy A. Lynch, and Calvin C. Newport. Multi-message broadcast with abstract MAC layers and unreliable links. In Magnús M. Halldórsson and Shlomi Dolev, editors, ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15-18, 2014, pages 56-65. ACM, 2014. URL: http://dx.doi.org/10.1145/2611462.2611492.
  8. Mohsen Ghaffari, Nancy A. Lynch, and Calvin C. Newport. The cost of radio network broadcast for different models of unreliable links. In Panagiota Fatourou and Gadi Taubenfeld, editors, ACM Symposium on Principles of Distributed Computing, PODC '13, Montreal, QC, Canada, July 22-24, 2013, pages 345-354. ACM, 2013. URL: http://dx.doi.org/10.1145/2484239.2484259.
  9. Seth Gilbert, Rachid Guerraoui, and Calvin C. Newport. Of malicious motes and suspicious sensors: On the efficiency of malicious interference in wireless networks. In Alexander A. Shvartsman, editor, Principles of Distributed Systems, 10th International Conference, OPODIS 2006, Bordeaux, France, December 12-15, 2006, Proceedings, volume 4305 of Lecture Notes in Computer Science, pages 215-229. Springer, 2006. URL: http://dx.doi.org/10.1007/11945529_16.
  10. Olga Goussevskaia, Thomas Moscibroda, and Roger Wattenhofer. Local broadcasting in the physical interference model. In Michael Segal and Alexander Kesselman, editors, Proceedings of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing, Toronto, Canada, August 18-21, 2008, pages 35-44. ACM, 2008. URL: http://dx.doi.org/10.1145/1400863.1400873.
  11. Magnús M. Halldórsson, Stephan Holzer, and Nancy A. Lynch. A local broadcast layer for the SINR network model. In Chryssis Georgiou and Paul G. Spirakis, editors, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015, pages 129-138. ACM, 2015. URL: http://dx.doi.org/10.1145/2767386.2767432.
  12. Magnús M. Halldórsson and Pradipta Mitra. Towards tight bounds for local broadcasting. In Fabian Kuhn and Calvin C. Newport, editors, FOMC'12, The Eighth ACM International Workshop on Foundations of Mobile Computing (part of PODC 2012), Funchal, Portugal, July 19, 2012, Proceedings, page 2. ACM, 2012. URL: http://dx.doi.org/10.1145/2335470.2335472.
  13. Tomasz Jurdzinski and Dariusz R. Kowalski. Distributed backbone structure for algorithms in the SINR model of wireless networks. In Marcos K. Aguilera, editor, Distributed Computing - 26th International Symposium, DISC 2012, Salvador, Brazil, October 16-18, 2012. Proceedings, volume 7611 of Lecture Notes in Computer Science, pages 106-120. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33651-5_8.
  14. Tomasz Jurdzinski and Dariusz R. Kowalski. Distributed randomized broadcasting in wireless networks under the SINR model. In Encyclopedia of Algorithms, pages 577-580. Springer, 2016. URL: http://dx.doi.org/10.1007/978-1-4939-2864-4_604.
  15. Tomasz Jurdzinski, Dariusz R. Kowalski, Michal Rozanski, and Grzegorz Stachowiak. On the impact of geometry on ad hoc communication in wireless networks. In Magnús M. Halldórsson and Shlomi Dolev, editors, ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15-18, 2014, pages 357-366. ACM, 2014. URL: http://dx.doi.org/10.1145/2611462.2611487.
  16. Fabian Kuhn, Nancy A. Lynch, and Calvin C. Newport. The abstract MAC layer. Distributed Computing, 24(3-4):187-206, 2011. URL: http://dx.doi.org/10.1007/s00446-010-0118-0.
  17. Fabian Kuhn, Nancy A. Lynch, Calvin C. Newport, Rotem Oshman, and Andréa W. Richa. Broadcasting in unreliable radio networks. In Andréa W. Richa and Rachid Guerraoui, editors, Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, PODC 2010, Zurich, Switzerland, July 25-28, 2010, pages 336-345. ACM, 2010. URL: http://dx.doi.org/10.1145/1835698.1835779.
  18. Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193-201, 1992. URL: http://dx.doi.org/10.1137/0221015.
  19. Nancy A. Lynch and Calvin Newport. A (truly) local broadcast layer for unreliable radio networks. In Chryssis Georgiou and Paul G. Spirakis, editors, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015, pages 109-118. ACM, 2015. URL: http://dx.doi.org/10.1145/2767386.2767411.
  20. Dominic Meier, Yvonne Anne Pignolet, Stefan Schmid, and Roger Wattenhofer. Speed dating despite jammers. In Bhaskar Krishnamachari, Subhash Suri, Wendi Rabiner Heinzelman, and Urbashi Mitra, editors, Distributed Computing in Sensor Systems, 5th IEEE International Conference, DCOSS 2009, Marina del Rey, CA, USA, June 8-10, 2009. Proceedings, volume 5516 of Lecture Notes in Computer Science, pages 1-14. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-02085-8_1.
  21. T. Moscibroda, R. Wattenhofer, and Y. Weber. Protocol design beyond graph-based models. In Proceedings of the ACM Workshop on Hot Topics in Networks (HotNets-V), 2006. Google Scholar
  22. Calvin C. Newport, David Kotz, Yougu Yuan, Robert S. Gray, Jason Liu, and Chip Elliott. Experimental evaluation of wireless simulation assumptions. Simulation, 83(9):643-661, 2007. URL: http://dx.doi.org/10.1177/0037549707085632.
  23. Adrian Ogierman, Andréa W. Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. Competitive MAC under adversarial SINR. In 2014 IEEE Conference on Computer Communications, INFOCOM 2014, Toronto, Canada, April 27 - May 2, 2014, pages 2751-2759. IEEE, 2014. URL: http://dx.doi.org/10.1109/INFOCOM.2014.6848224.
  24. A. Richa, Ch. Scheideler, S. Schmid, and J. Zhang. A jamming-resistant MAC protocol for multi-hop wireless networks. In Proceedings of the 24th International Conference on Distributed Computing, DISC quotesingle10. Springer-Verlag, 2010. Google Scholar
  25. D. Yu, Q. Hua, Y. Wang, and F. C. M. Lau. An O(log n) distributed approximation algorithm for local broadcasting in unstructured wireless networks. In IEEE 8th International Conference on Distributed Computing in Sensor Systems, ICDCS quotesingle12. IEEE, 2012. URL: http://dx.doi.org/10.1109/dcoss.2012.39.
  26. Dongxiao Yu, Qiang-Sheng Hua, Yuexuan Wang, Haisheng Tan, and Francis C. M. Lau. Distributed multiple-message broadcast in wireless ad hoc networks under the SINR model. Theor. Comput. Sci., 610:182-191, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2014.06.043.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact