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

Newport, Calvin ; Zheng, Chaodong

Approximate Neighbor Counting in Radio Networks

pdf-format:
LIPIcs-OPODIS-2018-26.pdf (0.4 MB)

Abstract

For many distributed algorithms, neighborhood size is an important parameter. In radio networks, however, obtaining this information can be difficult due to ad hoc deployments and communication that occurs on a collision-prone shared channel. This paper conducts a comprehensive survey of the approximate neighbor counting problem, which requires nodes to obtain a constant factor approximation of the size of their network neighborhood. We produce new lower and upper bounds for three main variations of this problem in the radio network model: (a) the network is single-hop and every node must obtain an estimate of its neighborhood size; (b) the network is multi-hop and only a designated node must obtain an estimate of its neighborhood size; and (c) the network is multi-hop and every node must obtain an estimate of its neighborhood size. In studying these problem variations, we consider solutions with and without collision detection, and with both constant and high success probability. Some of our results are extensions of existing strategies, while others require technical innovations. We argue this collection of results provides insight into the nature of this well-motivated problem (including how it differs from related symmetry breaking tasks in radio networks), and provides a useful toolbox for algorithm designers tackling higher level problems that might benefit from neighborhood size estimates.

BibTeX - Entry

@InProceedings{newport_et_al:LIPIcs:2018:10086,
  author =	{Calvin Newport and Chaodong Zheng},
  title =	{{Approximate Neighbor Counting in Radio Networks}},
  booktitle =	{22nd International Conference on Principles of Distributed  Systems (OPODIS 2018)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{125},
  editor =	{Jiannong Cao and Faith Ellen and Luis Rodrigues and Bernardo Ferreira},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10086},
  URN =		{urn:nbn:de:0030-drops-100860},
  doi =		{10.4230/LIPIcs.OPODIS.2018.26},
  annote =	{Keywords: Radio networks, neighborhood size estimation, approximate counting}
}

Keywords: Radio networks, neighborhood size estimation, approximate counting
Collection: 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)
Issue Date: 2018
Date of publication: 15.01.2019

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