Resolving SINR Queries in a Dynamic Setting

DOI10.1137/19M128733XzbMATH Open1497.68135arXiv1804.10654MaRDI QIDQ3387759FDOQ3387759

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

Publication date: 13 January 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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 transmitter's signal strength at a given point is modeled by the transmitter's power divided by some constant power $alpha$ 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 non-uniform power. In both variants the preprocessing time is $O(nmathopextrmpolylogn)$ and the amortized update time is $O(mathopextrmpolylogn)$, while the query time is $O(mathopextrmpolylogn)$ for uniform power, and randomized time $O(sqrtnmathopextrmpolylogn)$ with high probability for non-uniform 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(mathopextrmpolylogn)$, thus significantly improving all previous results for this problem.

Full work available at URL: https://arxiv.org/abs/1804.10654

Recommendations

• Resolving SINR queries in a dynamic setting
• Enabling dynamic querying over distributed hash tables
• Dynamic query interpretation in relational databases
• Dynamic query optimization under access limitations and dependencies
• Querying sensor networks by using dynamic task sets
• scientific article; zbMATH DE number 2086275
• scientific article; zbMATH DE number 1487621

zbMATH Keywords

computational geometrywireless networksdynamic data structuresinterference cancellationSINR

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Communication theory (94A05) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Efficient partition trees
• Computational geometry. Algorithms and applications.
• The design of dynamic data structures
• Adding range restriction capability to dynamic data structures
• Worst-case optimal insertion and deletion methods for decomposable searching problems
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Space efficient data structures for dynamic orthogonal range counting
• The topology of wireless communication
• Approximating Minimization Diagrams and Generalized Proximity Search
• On approximate range counting and depth
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
• Nonuniform SINR+Voroni diagrams are effectively uniform
• SINR diagrams, convexity and its applications in wireless networks
• Title not available (Why is that?)
• Approximate Nearest Neighbor Searching with Non-Euclidean and Weighted Distances
• SINR diagram with interference cancellation

Cited In (2)

• Resolving SINR queries in a dynamic setting
• Dynamic approximate multiplicatively-weighted nearest neighbors

This page was built for publication: Resolving SINR Queries in a Dynamic Setting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3387759)