אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

We study the topological properties of wireless communication maps and their usability in algorithmic design. We consider the SINR model, which compares the received power of a signal at a receiver against the sum of strengths of other interfering signals plus background noise. To model the reception regions, we use the convenient representation of an \emph{SINR diagram}, introduced in \cite{Avin10journal}, which partitions the plane into $n$ reception zones, one per station, and a complementary region where no station can be heard. The topology and geometry of SINR diagrams was studied in Avin et al. in the relatively simple setting of {\em uniform power}, where all stations transmit with the same power level. It was shown therein that uniform SINR diagrams assume a particularly convenient form: the reception zone of each station is convex, fat and strictly contained inside the corresponding Voronoi cell.

Here we consider the more general (and common) case where transmission energies are arbitrary (or non-uniform). Under that setting, the reception zones are not necessarily convex or even connected. This poses the algorithmic challenge of designing efficient algorithmic techniques for the non-uniform setting, as well as the theoretical challenge of understanding the geometry of SINR diagrams (e.g., the maximal number of connected components they might have). We achieve several results in both directions. One of our key results concerns the behavior of a $(d+1)$-dimensional map, i.e., a map in one dimension higher than the dimension in which stations are embedded.

Specifically, although the $d$-dimensional map might be highly fractured, drawing the map in one dimension higher ``heals'' the zones, which become connected (in fact hyperbolically connected). In addition, we establish the {\em minimum principle} for the SINR function, and utilize it as a discretization technique for solving two-dimensional problems in the SINR model. This approach is shown to be useful for handling optimization problems over two dimensions (e.g., power control, energy minimization); in providing tight bounds on the number of null-cells in the reception map; and in approximating geometrical and topological properties of the wireless reception map (e.g., maximum inscribed sphere). Essentially, the minimum principle allows us to reduce the dimension of the optimization domain \emph{without} losing anything in the accuracy or quality of the solution.

Joint work with Erez Kantor, Zvi Lotker and David Peleg.