Resolving SINR Queries in a Dynamic Setting

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



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.145.pdf
  • Filesize: 0.6 MB
  • 13 pages

Document Identifiers

Author Details

Boris Aronov
  • Department of Computer Science and Engineering, Tandon School of Engineering, New York University, Brooklyn, NY 11201, USA
Gali Bar-On
  • Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel
Matthew J. Katz
  • Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel

Cite AsGet 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)
    0
    PDF Downloads

References

  1. 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.
  2. Boris Aronov, Gali Bar-On, and Matthew J. Katz. Resolving SINR queries in a dynamic setting. arXiv:1804.10654. Google Scholar
  3. 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. Google Scholar
  4. 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.
  5. 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.
  6. 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.
  7. B. Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput., 17(3):427-462, 1988. Google Scholar
  8. 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/.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. J. Matoušek. Efficient partition trees. Discrete Comput. Geom., 8:315-334, 1992. Google Scholar
  14. M. H. Overmars. The Design of Dynamic Data Structures, volume 156 of Lecture Notes in Computer Science. Springer-Verlag, Heidelberg, West Germany, 1983. Google Scholar
  15. 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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail