License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2017.25
URN: urn:nbn:de:0030-drops-79898
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7989/
Go to the corresponding LIPIcs Volume Portal

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

An Efficient Communication Abstraction for Dense Wireless Networks

pdf-format:
LIPIcs-DISC-2017-25.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{halldrsson_et_al:LIPIcs:2017:7989,
  author =	{Magn{\'u}s M. Halld{\'o}rsson and Fabian Kuhn and Nancy Lynch and Calvin Newport},
  title =	{{An Efficient Communication Abstraction for Dense Wireless Networks}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{25:1--25:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Andr{\'e}a W. Richa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7989},
  URN =		{urn:nbn:de:0030-drops-79898},
  doi =		{10.4230/LIPIcs.DISC.2017.25},
  annote =	{Keywords: wireless networks, abstractions, SINR, signal fading}
}

Keywords: wireless networks, abstractions, SINR, signal fading
Collection: 31st International Symposium on Distributed Computing (DISC 2017)
Issue Date: 2017
Date of publication: 12.10.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI