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.OPODIS.2017.3
URN: urn:nbn:de:0030-drops-86247
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8624/
Go to the corresponding LIPIcs Volume Portal

Kuhn, Fabian ; Schneider, Philipp

Broadcasting in an Unreliable SINR Model

pdf-format:
LIPIcs-OPODIS-2017-3.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{kuhn_et_al:LIPIcs:2018:8624,
  author =	{Fabian Kuhn and Philipp Schneider},
  title =	{{Broadcasting in an Unreliable SINR Model}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{3:1--3:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{James Aspnes and Alysson Bessani and Pascal Felber and Jo{\~a}o Leit{\~a}o},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8624},
  URN =		{urn:nbn:de:0030-drops-86247},
  doi =		{10.4230/LIPIcs.OPODIS.2017.3},
  annote =	{Keywords: radio networks, wireless networks, broadcast, SINR model, unreliable communication, dynamic networks}
}

Keywords: radio networks, wireless networks, broadcast, SINR model, unreliable communication, dynamic networks
Collection: 21st International Conference on Principles of Distributed Systems (OPODIS 2017)
Issue Date: 2018
Date of publication: 28.03.2018

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