SINR diagrams: towards algorithmically usable SINR models of wireless networks

ABSTRACT

The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model. For a collection of simultaneously transmitting stations in the plane, it is possible to identify a reception zone for each station, consisting of the points where its transmission is received correctly. The resulting SINR diagram partitions the plane into a reception zone per station and the remaining plane where no station can be heard.

SINR diagrams appear to be fundamental to understanding the behavior of wireless networks, and may play a key role in the development of suitable algorithms for such networks, analogous perhaps to the role played by Voronoi diagrams in the study of proximity queries and related issues in computational geometry. So far, however, the properties of SINR diagrams have not been studied systematically, and most algorithmic studies in wireless networking rely on simplified graph-based models such as the unit disk graph (UDG) model, which conveniently abstract away interference-related complications, and make it easier to handle algorithmic issues, but consequently fail to capture accurately some important aspects of wireless networks.

The current paper focuses on obtaining some basic understanding of SINR diagrams, their properties and their usability in algorithmic applications. Specifically, based on some algebraic properties of the polynomials defining the reception zones we show that assuming uniform power transmissions, the reception zones are convex and relatively well-rounded. These results are then used to develop an efficient approximation algorithm for a fundamental point location problem in wireless networks.

REFERENCES

• 1: P.K. Agarwal and J. Erickson. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry, pages 1--56. American Mathematical Society, 1999.
• 2: A. Aggarwal , M. Hansen , T. Leighton, Solving query-retrieval problems by compacting Voronoi diagrams, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.331-340, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100260]
• 3: Saugata Basu , Richard Pollack , Marie-Françoise Roy, Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 4: Uyless Black, Mobile and wireless networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 5: Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, Theoretical Computer Science, v.84 n.1, p.77-105, July 22, 1991 [doi>10.1016/0304-3975(91)90261-Y]
• 6: Brent N. Clark , Charles J. Colbourn , David S. Johnson, Unit disk graphs, Discrete Mathematics, v.86 n.1-3, p.165-177, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90358-O]
• 7: Mark de Berg , Otfried Cheong , Marc van Kreveld , Mark Overmars, Computational Geometry: Algorithms and Applications, Springer-Verlag TELOS, Santa Clara, CA, 2008
• 8: Olga Goussevskaia , Yvonne Anne Oswald , Roger Wattenhofer, Complexity in geometric SINR, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1288107.1288122]
• 9: P. Gupta and P.R. Kumar. The capacity of wireless networks. IEEE Trans. Information Theory, 46(2):388--404, 2000.
• 10: Fabian Kuhn , Aaron Zollinger, Ad-hoc networks beyond unit disk graphs, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.69-78, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941089]
• 11: Thomas Moscibroda, The worst-case capacity of wireless sensor networks, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA [doi>10.1145/1236360.1236362]
• 12: T. Moscibroda, R. Wattenhofer, and Y. Weber. Protocol design beyond graph-based models. In Proc. 5th Workshop on Hot Topics in Networks (Hotnets), 2006.
• 13: Thomas Moscibroda , Roger Wattenhofer , Aaron Zollinger, Topology control meets SINR: the scheduling complexity of arbitrary topologies, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132939]
• 14: Kaveh Pahlavan , Allen H. Levesque, Wireless information networks, Wiley-Interscience, New York, NY, 1995
• 15: Theodore S. Rappaport, Wireless Communications: Principles and Practice, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 16: Pascal von Rickenbach , Stefan Schmid , Roger Wattenhofer , Aaron Zollinger, A Robust Interference Model for Wireless Ad-Hoc Networks, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 12, p.239.1, April 04-08, 2005 [doi>10.1109/IPDPS.2005.65]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms

Keywords:
SINR, reception zone, wireless networks