TY - JOUR

T1 - Resolving SINR queries in a dynamic setting

AU - Aronov, Boris

AU - Bar-On, Gali

AU - Katz, Matthew J.

N1 - Funding Information:
\ast Received by the editors September 16, 2019; accepted for publication (in revised form) October 8, 2020; published electronically December 14, 2020. An earlier version of this paper (excluding section 3 and section 6 and some of the proofs) was presented in Proceedings of Automata, Languages, and Programming---45th International Colloquium, Part III, 2018, pp. 145:1--145:13. Work on this paper was initiated at the Fifth Workshop on Geometry and Graphs, Bellairs Research Institute, Barbados, 2017. https://doi.org/10.1137/19M128733X Funding: The first and third authors were supported by a joint grant 2014/170 from the US-Israel Binational Science Foundation. The first author was supported by NSF grants CCF-11-17336, CCF-12-18791, and CCF-15-40656. The third author was supported by grant 1884/16 from the Israel Science Foundation.
Funding Information:
The first and third authors were supported by a joint grant 2014/170 from the USIsrael Binational Science Foundation. The first author was supported by NSF grants CCF-11-17336, CCF-12-18791, and CCF-15-40656. The third author was supported by grant 1884/16 from the Israel Science Foundation.
Publisher Copyright:
Copyright © by SIAM.

PY - 2020/12/14

Y1 - 2020/12/14

N2 - We consider a set of transmitters broadcasting simultaneously on the same frequency under the signal to interference plus noise ratio (SINR) model. Transmission power may vary from one transmitter to another, and a transmitter's signal strength at a given point is modeled by the transmitter's power divided by some constant power α of the distance it traveled. Roughly, a receiver at a given location can hear a specific transmitter only if the transmitter's signal is stronger by a specified ratio than the signals 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 compact data structures that support approximate SINR queries in the plane in a dynamic context, i.e., where transmitters may be inserted and deleted over time. We distinguish between two main variants - uniform power and nonuniform power. In both variants the preprocessing time is O(polylogn) and the amortized update time is O(polylogn), while the query time is O(polylogn) for uniform power, and randomized time O(√ n polylogn) with high probability for nonuniform power. Finally, we observe that in the static context the latter data structure can be implemented differently, so that the query time is also O(polylogn), thus significantly improving all previous results for this problem.

AB - We consider a set of transmitters broadcasting simultaneously on the same frequency under the signal to interference plus noise ratio (SINR) model. Transmission power may vary from one transmitter to another, and a transmitter's signal strength at a given point is modeled by the transmitter's power divided by some constant power α of the distance it traveled. Roughly, a receiver at a given location can hear a specific transmitter only if the transmitter's signal is stronger by a specified ratio than the signals 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 compact data structures that support approximate SINR queries in the plane in a dynamic context, i.e., where transmitters may be inserted and deleted over time. We distinguish between two main variants - uniform power and nonuniform power. In both variants the preprocessing time is O(polylogn) and the amortized update time is O(polylogn), while the query time is O(polylogn) for uniform power, and randomized time O(√ n polylogn) with high probability for nonuniform power. Finally, we observe that in the static context the latter data structure can be implemented differently, so that the query time is also O(polylogn), thus significantly improving all previous results for this problem.

KW - Computational geometry

KW - Dynamic data structures

KW - Interference cancellation

KW - SINR

KW - Wireless networks

UR - http://www.scopus.com/inward/record.url?scp=85099304242&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85099304242&partnerID=8YFLogxK

U2 - 10.1137/19M128733X

DO - 10.1137/19M128733X

M3 - Article

AN - SCOPUS:85099304242

VL - 49

SP - 1271

EP - 1290

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 6

ER -