Document Open Access Logo

Ad-Hoc Affectance-Selective Families for Layer Dissemination

Authors Harshita Kudaravalli, Miguel A. Mosteiro

PDF
Thumbnail PDF

File

LIPIcs.SEA.2017.33.pdf
  • Filesize: 1.28 MB
  • 16 pages

Document Identifiers

Author Details

Harshita Kudaravalli
Miguel A. Mosteiro

Cite As Get BibTex

Harshita Kudaravalli and Miguel A. Mosteiro. Ad-Hoc Affectance-Selective Families for Layer Dissemination. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SEA.2017.33

Abstract

Information dissemination protocols for ad-hoc wireless networks frequently use a minimal subset of the available communication links, defining a rooted "“broadcast"” tree. In this work, we focus on the core challenge of disseminating from one layer to the next one of such tree. We call this problem Layer Dissemination. We study Layer Dissemination under a generalized model of interference, called affectance. The affectance model subsumes previous models, such as Radio Network and Signal to Inteference-plus-Noise Ratio. We present randomized and deterministic protocols for Layer Dissemination. These protocols are based on a combinatorial object that we call Affectance-selective Families. Our approach combines an engineering solution with theoretical guarantees. That is, we provide a method to characterize the network with a global measure of affectance based on measurements of interference in the specific deployment area. Then, our protocols distributedly produce an ad-hoc transmissions schedule for dissemination. In the randomized protocol only the network characterization is needed, whereas the deterministic protocol requires full knowledge of affectance. Our theoretical analysis provides guarantees on schedule length. We also present simulations of a real network-deployment area contrasting the perform- ance of our randomized protocol, which takes into account affectance, against previous work for interference models that ignore some physical constraints. The striking improvement in performance shown by our simulations show the importance of utilizing a more physically-accurate model of interference that takes into account other effects beyond distance to transmitters.

Subject Classification

Keywords
  • Wireless Networks
  • Broadcast Protocols
  • Affectance
  • SINR

Metrics

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

References

  1. Reuven Bar-Yehuda, Oded Goldreich, and Alon Itai. On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. Journal of Computer and System Sciences, 45(1):104-126, 1992. Google Scholar
  2. Imrich Chlamtac and Shay Kutten. Tree-based broadcasting in multihop radio networks. IEEE Trans. Computers, 36(10):1209-1223, 1987. Google Scholar
  3. Bogdan S. Chlebus, Leszek Gasieniec, Alan Gibbons, Andrzej Pelc, and Wojciech Rytter. Deterministic broadcasting in ad hoc radio networks. Distributed Computing, 15(1):27-38, 2002. URL: http://dx.doi.org/10.1007/s446-002-8028-1.
  4. Andrea EF Clementi, Pilu Crescenzi, Angelo Monti, Paolo Penna, and Riccardo Silvestri. On computing ad-hoc selective families. In Proc. of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, volume 2129 of Lecture Notes in Computer Science, pages 211-222, 2001. Google Scholar
  5. Fabio D'Andreagiovanni, Carlo Mannino, and Antonio Sassano. GUB covers and power-indexed formulations for wireless network design. Management Science, 59(1):142-156, 2013. URL: http://dx.doi.org/10.1287/mnsc.1120.1571.
  6. Peter Dely, Fabio D'Andreagiovanni, and Andreas Kassler. Fair optimization of mesh-connected WLAN hotspots. Wireless Communications and Mobile Computing, 15(5):924-946, 2015. URL: http://dx.doi.org/10.1002/wcm.2393.
  7. Mohsen Ghaffari, Bernhard Haeupler, and Majid Khabbazian. The complexity of multi-message broadcast in radio networks with known topology. CoRR, abs/1205.7014, 2012. Google Scholar
  8. Magnús M. Halldórsson and Roger Wattenhofer. Wireless communication is in apx. In Proc. of the 36th International Colloquium on Automata, Languages and Programming, Part I, pages 525-536, 2009. Google Scholar
  9. Tomasz Jurdzinski, Dariusz R. Kowalski, Michal Rozanski, and Grzegorz Stachowiak. Distributed randomized broadcasting in wireless networks under the sinr model. In Yehuda Afek, editor, DISC, volume 8205 of Lecture Notes in Computer Science, pages 373-387. Springer, 2013. Google Scholar
  10. Thomas Kesselheim. Dynamic packet scheduling in wireless networks. In Proc. of the 31st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pages 281-290, 2012. Google Scholar
  11. Thomas Kesselheim and Berthold Vöcking. Distributed contention resolution in wireless networks. In Proc. of the 24th International Symposium on Distributed Computing, volume 6343 of Lecture Notes in Computer Science, pages 163-178. Springer-Verlag, Berlin, 2010. Google Scholar
  12. Majid Khabbazian and Dariusz R. Kowalski. Time-efficient randomized multiple-message broadcast in radio networks. In Cyril Gavoille and Pierre Fraigniaud, editors, PODC, pages 373-380. ACM, 2011. Google Scholar
  13. Dariusz R. Kowalski, Miguel A. Mosteiro, and Tevin Rouse. Dynamic multiple-message broadcast: bounding throughput in the affectance model. In 10th ACM International Workshop on Foundations of Mobile Computing, FOMC 2014, Philadelphia, PA, USA, August 11, 2014, pages 39-46, 2014. Google Scholar
  14. Dariusz R. Kowalski, Miguel A. Mosteiro, and Kevin Zaki. Dynamic multiple-message broadcast: Bounding throughput in the affectance model. CoRR, abs/1512.00540, 2015. URL: http://arxiv.org/abs/1512.00540.
  15. Fredrik Manne and Qin Xin. Optimal gossiping with unit size messages in known topology radio networks. In Workshop on Combinatorial and Algorithmic Aspects of Networking, pages 125-134. Springer, 2006. Google Scholar
  16. Gianluca De Marco and Dariusz R. Kowalski. Towards power-sensitive communication on a multiple-access channel. In 2010 International Conference on Distributed Computing Systems, ICDCS 2010, Genova, Italy, June 21-25, 2010, pages 728-735, 2010. URL: http://dx.doi.org/10.1109/ICDCS.2010.50.
  17. Gianluca De Marco and Dariusz R. Kowalski. Fast nonadaptive deterministic algorithm for conflict resolution in a dynamic multiple-access channel. SIAM J. Comput., 44(3):868-888, 2015. URL: http://dx.doi.org/10.1137/140982763.
  18. Michael Mitzenmacher and Eli Upfal. Probability and Computing. Cambridge University Press, 2005. Google Scholar
  19. Christian Scheideler, Andréa W. Richa, and Paolo Santi. An o(log n) dominating set protocol for wireless ad-hoc networks under the physical interference model. In Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pages 91-100. ACM, 2008. Google Scholar
  20. Mythili Vutukuru, Kyle Jamieson, and Hari Balakrishnan. Harnessing exposed terminals in wireless networks. In Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation, pages 59-72, 2008. Google Scholar
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 About DROPS Imprint Privacy Contact