Abstract
The SINR (Signal to Interference plus Noise Ratio) model for the quality of wireless connections has been the subject of extensive recent study. It attempts to predict whether a particular transmitter is heard at a specific location, in a setting consisting of n simultaneous transmitters and background noise. The SINR model gives rise to a natural geometric object, the SINR diagram, which partitions the space into n regions where each of the transmitters can be heard and the remaining space where no transmitter can be heard.
Efficient point location in the SINR diagram, i.e., being able to build a data structure that facilitates determining, for a query point, whether any transmitter is heard there, and if so, which one, has been recently investigated in several articles. These planar data structures are constructed in time at least quadratic in n and support logarithmic-time approximate queries. Moreover, the performance of some of the proposed structures depends strongly not only on the number n of transmitters and on the approximation parameter ε, but also on some geometric parameters that cannot be bounded a priori as a function of n or ε.
In this article, we address the question of batched point location queries, i.e., answering many queries simultaneously. Specifically, in one dimension, we can answer n queries exactly in amortized polylogarithmic time per query, while in the plane we can do it approximately.
In another result, we show how to answer n2 queries exactly in amortized polylogarithmic time per query, assuming the queries are located on a possibly non-uniform n × n grid.
All these results can handle arbitrary power assignments to the transmitters. Moreover, the amortized query time in these results depends only on n and ε.
We also show how to speed up the preprocessing in a previously proposed point-location structure in SINR diagram for uniform-power sites, by almost a full order of magnitude. For this, we obtain results on the sensitivity of the reception regions to slight changes in the reception threshold, which are of independent interest.
Finally, these results demonstrate the (so far underutilized) power of combining algebraic tools with those of computational geometry and other fields.
- Deepak Ajwani, Saurabh Ray, Raimund Seidel, and Hans Raj Tiwary. 2007. On computing the centroid of the vertices of an arrangement and related problems. In Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS’07). 519--528. Google ScholarDigital Library
- M. Andrews and M. Dinitz. 2009. Maximizing capacity in arbitrary wireless networks in the SINR model: Complexity and game theory. In Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM’09). 1332--1340.Google Scholar
- Boris Aronov and Matthew J. Katz. 2015. Batched point location in SINR diagrams via algebraic tools. In Proceedings of Automata, Languages, and Programming—42nd International Colloquium (ICALP’15), Part I. 65--77. See also arXiv:1412.0962 {cs.CG}, 2014.Google Scholar
- Rom Aschner, Gui Citovsky, and Matthew J. Katz. 2014. Exploiting geometry in the SINRk model. In Proceedings of Algorithms for Sensor Systems—10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS’14). 125--135.Google Scholar
- Franz Aurenhammer. 1986. The one-dimensional weighted Voronoi diagram. Inform. Process. Lett. 22, 3 (1986), 119--123. Google ScholarDigital Library
- Franz Aurenhammer and Herbert Edelsbrunner. 1984. An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Patt. Recog. 17, 2 (1984), 251--257.Google ScholarCross Ref
- Franz Aurenhammer, Rolf Klein, and D.-T. Lee. 2013. Voronoi Diagrams and Delaunay Triangulations. World Scientific. http://www.worldscientific.com/worldscibooks/10.1142/8685. Google ScholarDigital Library
- Chen Avin, Asaf Cohen, Yoram Haddad, Erez Kantor, Zvi Lotker, Merav Parter, and David Peleg. 2017. SINR diagram with interference cancellation. Ad Hoc Netw. 54 (2017), 1--16. Google ScholarDigital Library
- Chen Avin, Yuval Emek, Erez Kantor, Zvi Lotker, David Peleg, and Liam Roditty. 2012. SINR diagrams: Convexity and its applications in wireless networks. J. ACM 59, 4, Article 18 (2012), 34 pages. Google ScholarDigital Library
- Dario Bini and Victor Y. Pan. 1994. Polynomial and Matrix Computations, Vol. 1: Fundamental Algorithms. Birkhäuser. Google ScholarDigital Library
- M. de Berg, O. Cheong, M. van Kreveld, and M. H. Overmars. 2008. Computational Geometry: Algorithms and Applications (3rd ed.). Springer-Verlag, Berlin. http://www.cs.ruu.nl/geobook. Google ScholarDigital Library
- H. Edelsbrunner and R. Seidel. 1986. Voronoi diagrams and arrangements. Discrete Comput. Geom. 1 (1986), 25--44. Google ScholarDigital Library
- O. Goussevskaia, M. M. Halldórsson, R. Wattenhofer, and E. Welzl. 2009. Capacity of arbitrary wireless networks. In Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM’09). 1872--1880.Google Scholar
- O. Goussevskaia, Y. A. Oswald, and R. Wattenhofer. 2007. Complexity in geometric SINR. In Proceedings of the 8th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc’07). 100--109. Google ScholarDigital Library
- P. Gupta and P. R. Kumar. 2000. The capacity of wireless networks. IEEE Trans. Inform. Theor. 46, 2 (2000), 388--404. Google ScholarDigital Library
- M. M. Halldórsson. 2012. Wireless scheduling with power control. ACM Trans. Algorithms 9, 1 (2012), 7:1--7:20. Google ScholarDigital Library
- M. M. Halldórsson and P. Mitra. 2011. Wireless capacity with oblivious power in general metrics. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA’11). 1538--1548. Google ScholarDigital Library
- M. M. Halldórsson and R. Wattenhofer. 2009. Wireless communication is in APX. In Proceedings Automata, Languages and Programming—36th International Colloquium (ICALP’09), Part I. 525--536. Google ScholarDigital Library
- Sariel Har-Peled and Nirman Kumar. 2015. Approximating minimization diagrams and generalized proximity search. SIAM J. Comput. 44, 4 (2015), 944--974.Google ScholarDigital Library
- Erez Kantor, Zvi Lotker, Merav Parter, and David Peleg. 2011. The topology of wireless communication. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC’11). 383--392. Google ScholarDigital Library
- T. Kesselheim. 2011. A constant-factor approximation for wireless capacity maximization with power control in the SINR model. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA’11). 1549--1559. Google ScholarDigital Library
- Zvi Lotker and David Peleg. 2010. Structure and algorithms in the SINR wireless model. SIGACT News 41, 2 (2010), 74--84. Google ScholarDigital Library
- Guillaume Moroz and Boris Aronov. 2016. Computing the distance between piecewise-linear bivariate functions. ACM Trans. Algorithms 12, 1 (2016), 3:1--3:13. Google ScholarDigital Library
- T. Moscibroda and R. Wattenhofer. 2006. The complexity of connectivity in wireless networks. In Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM’06). 25--37.Google Scholar
- Michael Nüsken and Martin Ziegler. 2004. Fast multipoint evaluation of bivariate polynomials. In Proceedins 12th European Symposium on Algorithms (ESA’04). 544--555.Google ScholarCross Ref
- Victor Y. Pan. 1994. Simple multivariate polynomial multiplication. J. Symb. Comput. 18, 3 (1994), 183--186. Google ScholarDigital Library
- M. Sharir and P. K. Agarwal. 1995. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York. http://us.cambridge.org/titles/catalogue.asp?isbn=0521470250. Google ScholarDigital Library
- Joachim von zur Gathen. 1999. Modern Computer Algebra. Cambridge University Press, Cambridge. Google ScholarDigital Library
- P.-J. Wan, X. Jia, and F. F. Yao. 2009. Maximum independent set of links under physical interference model. In Proceedings of the 4th International Conference on Wireless Algorithms, Systems, and Applications (WASA’09). 169--178. Google ScholarDigital Library
- Martin Ziegler. 2003. Fast relative approximation of potential fields. In Proceedings of the 8th International Workshop on Algorithms and Data Structures (WADS’03). 140--149.Google ScholarCross Ref
Index Terms
- Batched Point Location in SINR Diagrams via Algebraic Tools
Recommendations
Resolving SINR Queries in a Dynamic Setting
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 ...
Partially overlapping channel assignment for WLANs using SINR interference model
The use of multiple channels in 802.11 wireless local area networks can improve network performance. Many efforts have been done to better exploit multiple non-overlapped channels. However, the number of orthogonal channels in the Institute of ...
Transmit selection diversity with maximal-ratio combining for multicarrier DS-CDMA wireless networks over Nakagami-m fading channels
We propose the scheme to integrate transmit selection diversity/maximal-ratio combining (TSD/MRC) with multicarrier (MC) direct-sequence code-division multiple access (DS-CDMA) for various wireless networks. Applying this TSD/MRC-based scheme, the ...
Comments