Speaker: Yuval Emek School of Electrical Engineering, Tel Aviv University
Title: SINR Diagrams: Towards Algorithmically Usable SINR Models of Wireless Networks.
The rules governing the availability and quality of connections in a wireless network are described by \emph{physical} models such as the \emph{signaltointerference \& noise ratio (SINR)} model. For a collection of simultaneously transmitting stations in the plane, it is possible to identify a \emph{reception zone} for each station, consisting of the points where its transmission is received correctly. The resulting \emph{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. So far, however, the properties of SINR diagrams have not been studied systematically, and most algorithmic studies in wireless networking rely on simplified \emph{graphbased} models such as the \emph{unit disk graph} model, which fail to capture accurately some important aspects of wireless networks.
This work focuses on obtaining some basic understanding of SINR diagrams. 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 wellrounded. These results are then used to develop an efficient approximation algorithm for a fundamental point location problem in wireless networks.
Joint work with Chen Avin, Erez Kantor, Zvi Lotker, David Peleg, and Liam Roditty.
