DROPS

Document

DOI: 10.4230/LIPIcs.ICALP.2018.145

Resolving SINR Queries in a Dynamic Setting

Authors: Boris Aronov, Gali Bar-On, and Matthew J. Katz

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

We consider a set of transmitters broadcasting simultaneously on the same frequency under the SINR model. Transmission power may vary from one transmitter to another, and a signal's strength decreases (path loss or path attenuation) by some constant power alpha of the distance traveled. Roughly, a receiver at a given location can hear a specific transmitter only if the transmitter's signal is stronger than the signal of all other transmitters, combined. An SINR query is to determine whether a receiver at a given location can hear any transmitter, and if yes, which one. An approximate answer to an SINR query is such that one gets a definite yes or definite no, when the ratio between the strongest signal and all other signals combined is well above or well below the reception threshold, while the answer in the intermediate range is allowed to be either yes or no. We describe several compact data structures that support approximate SINR queries in the plane in a dynamic context, i.e., where both queries and updates (insertion or deletion of a transmitter) can be performed efficiently.

Cite as

Boris Aronov, Gali Bar-On, and Matthew J. Katz. Resolving SINR Queries in a Dynamic Setting. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 145:1-145:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.ICALP.2018.145,
  author =	{Aronov, Boris and Bar-On, Gali and Katz, Matthew J.},
  title =	{{Resolving SINR Queries in a Dynamic Setting}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{145:1--145:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.145},
  URN =		{urn:nbn:de:0030-drops-91495},
  doi =		{10.4230/LIPIcs.ICALP.2018.145},
  annote =	{Keywords: Wireless networks, SINR, dynamic insertion and deletion, interference cancellation, range searching}
}

Search Results

Documents authored by Bar-On, Gali

Resolving SINR Queries in a Dynamic Setting

Abstract

Cite as

Thanks for your feedback!

Could not send message