LIPIcs.ICALP.2018.145.pdf
- Filesize: 0.6 MB
- 13 pages
Document
Resolving SINR Queries in a Dynamic Setting
Authors
-
Part of:
Volume:
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-07-04
Cite As Get BibTex
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)
https://doi.org/10.4230/LIPIcs.ICALP.2018.145
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
- Networks → Network algorithms
Keywords
- Wireless networks
- SINR
- dynamic insertion and deletion
- interference cancellation
- range searching
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Pankaj K. Agarwal. Range searching. In Handbook of Discrete and Computational Geometry, Second Edition, pages 809-837. CRC Press LLC, 2004. URL: http://dx.doi.org/10.1201/9781420035315.ch36.
-
Boris Aronov, Gali Bar-On, and Matthew J. Katz. Resolving SINR queries in a dynamic setting. arXiv:1804.10654.
-
Boris Aronov and Matthew J. Katz. Batched point location in SINR diagrams via algebraic tools. ACM Transactions on Algorithms, 2018. Accepted for publication; see also arXiv:1412.0962.
- Chen Avin, Asaf Cohen, Yoram Haddad, Erez Kantor, Zvi Lotker, Merav Parter, and David Peleg. SINR diagram with interference cancellation. Ad Hoc Networks, 54:1-16, 2017. URL: http://dx.doi.org/10.1016/j.adhoc.2016.08.003.
- Chen Avin, Yuval Emek, Erez Kantor, Zvi Lotker, David Peleg, and Liam Roditty. SINR diagrams: Convexity and its applications in wireless networks. J. ACM, 59(4):18:1-18:34, 2012. URL: http://dx.doi.org/10.1145/2339123.2339125.
- Timothy M. Chan. A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries. J. ACM, 57(3):16:1-16:15, 2010. URL: http://dx.doi.org/10.1145/1706591.1706596.
-
B. Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput., 17(3):427-462, 1988.
- M. de Berg, O. Cheong, M. van Kreveld, and M. H. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, 3rd edition, 2008. URL: http://www.cs.ruu.nl/geobook/.
- Meng He and J. Ian Munro. Space efficient data structures for dynamic orthogonal range counting. Comput. Geom., 47(2):268-281, 2014. URL: http://dx.doi.org/10.1016/j.comgeo.2013.08.007.
- Erez Kantor, Zvi Lotker, Merav Parter, and David Peleg. The topology of wireless communication. In Proceedings 43rd ACM Symposium on Theory of Computing, STOC 2011, pages 383-392, 2011. URL: http://dx.doi.org/10.1145/1993636.1993688.
- Erez Kantor, Zvi Lotker, Merav Parter, and David Peleg. Nonuniform SINR+Voroni diagrams are effectively uniform. In Proceedings 29th International Symposium on Distributed Computing, DISC 2015, pages 588-601, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48653-5_39.
- Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir. Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. In Proceedings 28th ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 2495-2504, 2017. See also arXiv:1604.03654. URL: http://dx.doi.org/10.1137/1.9781611974782.165.
-
J. Matoušek. Efficient partition trees. Discrete Comput. Geom., 8:315-334, 1992.
-
M. H. Overmars. The Design of Dynamic Data Structures, volume 156 of Lecture Notes in Computer Science. Springer-Verlag, Heidelberg, West Germany, 1983.
- D. E. Willard and G. S. Lueker. Adding range restriction capability to dynamic data structures. J. ACM, 32:597-617, 1985. URL: http://dx.doi.org/10.1145/3828.3839.