Document Open Access Logo

An Efficient Communication Abstraction for Dense Wireless Networks

Authors Magnús M. Halldórsson, Fabian Kuhn, Nancy Lynch, Calvin Newport

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.25.pdf
  • Filesize: 484 kB
  • 16 pages

Document Identifiers

Author Details

Magnús M. Halldórsson
Fabian Kuhn
Nancy Lynch
Calvin Newport

Cite As Get BibTex

Magnús M. Halldórsson, Fabian Kuhn, Nancy Lynch, and Calvin Newport. An Efficient Communication Abstraction for Dense Wireless Networks. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.25

Abstract

In this paper we study the problem of developing efficient distributed algorithms for dense wireless networks. For many problems in this setting, fast solutions must leverage the reality that radio signals fade with distance, which can be exploited to enable concurrent communication among multiple sender/receiver pairs. To simplify the development of these algorithms we describe a new communication abstraction called FadingMAC which exposes the benefits of this concurrent communication, but also hides the details of the underlying low-level radio signal behavior. This approach splits efforts between those who develop useful algorithms that run on the abstraction, and those who implement the abstraction in concrete low-level wireless models, or on real hardware.

After defining FadingMAC, we describe and analyze an efficient implementation of the abstraction in a standard low-level SINR-style network model. We then describe solutions to the following problems that run on the abstraction: max, min, sum, and mean computed over input values; process renaming; consensus and leader election; and optimal packet scheduling. Combining our abstraction implementation with these applications that run on the abstraction, we obtain near-optimal solutions to these problems in our low-level SINR model - significantly advancing the known results for distributed algorithms in this setting. Of equal importance to these concrete bounds, however, is the general idea advanced by this paper: as wireless networks become more dense, both theoreticians and practitioners must explore new communication abstractions that can help tame this density.

Subject Classification

Keywords
  • wireless networks
  • abstractions
  • SINR
  • signal fading

Metrics

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

References

  1. R. Bar-Yehuda, O. Goldreich, and A. Itai. On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. J. Computer and System Sciences, 45(1):104-126, 1992. Google Scholar
  2. Guy E Blelloch. Scans as primitive parallel operations. IEEE Transactions on Computers, 38(11):1526-1538, 1989. Google Scholar
  3. Marijke H.L. Bodlaender, Magnús M. Halldórsson, and Pradipta Mitra. Connectivity and aggregation in multihop wireless networks. In PODC, pages 355-364. ACM, 2013. Google Scholar
  4. K. Censor-Hillel, S. Gilbert, F. Kuhn, N. Lynch, and C. Newport. Structuring unreliable radio networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing, 2011. Google Scholar
  5. Yin Chen and Andreas Terzis. On the mechanisms and effects of calibrating RSSI measurements for 802.15.4 radios. In EWSN, pages 256-271. Springer, 2010. Google Scholar
  6. I. Chlamtac and S. Kutten. On broadcasting in radio networks-problem analysis and protocol design. IEEE Transactions on Communications, 33(12):1240-1246, 1985. Google Scholar
  7. Sebastian Daum, Seth Gilbert, Fabian Kuhn, and Calvin Newport. Broadcast in the ad hoc SINR model. In Proc. 27th Symposium on Distributed Computing (DISC), pages 358-372, 2013. Google Scholar
  8. Jeremy T Fineman, Seth Gilbert, Fabian Kuhn, and Calvin Newport. Contention resolution on a fading channel. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 155-164. ACM, 2016. Google Scholar
  9. A. Goldberg, S. Plotkin, and G. Shannon. Parallel symmetry-breaking in sparse graphs. SIAM J. Discrete Math., 1(4):434-446, 1988. Google Scholar
  10. Magnús M. Halldórsson, Stephan Holzer, and Nancy A. Lynch. A local broadcast layer for the SINR network model. In PODC, pages 129-138, 2015. Google Scholar
  11. Magnús M. Halldórsson and Pradipta Mitra. Distributed connectivity of wireless networks. In PODC, pages 205-214, 2012. Google Scholar
  12. Magnús M. Halldórsson and Pradipta Mitra. Wireless connectivity and capacity. In SODA, pages 516-526, 2012. Google Scholar
  13. Magnús M Halldórsson, Yuexuan Wang, and Dongxiao Yu. Leveraging multiple channels in ad hoc networks. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 431-440. ACM, 2015. Google Scholar
  14. Nathaniel Hobbs, Yuexuan Wang, Qiang-Sheng Hua, Dongxiao Yu, and Francis CM Lau. Deterministic distributed data aggregation under the SINR model. In International Conference on Theory and Applications of Models of Computation, pages 385-399. Springer, 2012. Google Scholar
  15. Fabian Kuhn, Nancy Lynch, and Calvin Newport. The abstract MAC layer. Distributed Computing, 24(3):187-206, 2011. Google Scholar
  16. Fabian Kuhn, Nancy Lynch, Calvin Newport, Rotem Oshman, and Andrea Richa. Broadcasting in unreliable radio networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 336-345. ACM, 2010. Google Scholar
  17. Hongxing Li, Chuan Wu, Qiang-Sheng Hua, and Francis CM Lau. Latency-minimizing data aggregation in wireless sensor networks under physical interference model. Ad Hoc Networks, 12:52-68, 2014. Google Scholar
  18. Thomas Moscibroda. The worst-case capacity of wireless sensor networks. In IPSN, pages 1-10, 2007. Google Scholar
  19. Thomas Moscibroda and Roger Wattenhofer. The complexity of connectivity in wireless networks. In INFOCOM, pages 1-13, 2006. Google Scholar
  20. Thomas Moscibroda, Roger Wattenhofer, and Aaron Zollinger. Topology control meets SINR: the scheduling complexity of arbitrary topologies. In MobiCom, pages 310-321, 2006. Google Scholar
  21. Dongjin Son, Bhaskar Krishnamachari, and John Heidemann. Experimental study of concurrent transmission in wireless sensor networks. In SenSys, pages 237-250. ACM, 2006. 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