Access Restriction

Author Kantor, Erez ♦ Lotker, Zvi ♦ Parter, Merav ♦ Peleg, David
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2015
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword SINR ♦ Convexity ♦ Networks ♦ Point-location ♦ Weighted voronoi diagram
Abstract This article studies 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 describe the behavior of a multistation network, we use the convenient representation of a reception map, which partitions the plane into reception zones, one per station, and the complementary region of the plane where no station can be heard. SINR diagrams have been studied in Avin et al. [2009] for the specific case where all stations use the same power. It was shown that the reception zones are convex (hence connected) and fat, and this was used to devise an efficient algorithm for the fundamental problem of point location. Here we consider the more general (and common) case where transmission energies are arbitrary (or nonuniform). Under that setting, the reception zones are not necessarily convex or even connected. This poses the algorithmic challenge of designing efficient point location techniques for the nonuniform 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). Our key result exhibits a striking contrast between $\textit{d}-$ and $(\textit{d}+1)-dimensional$ maps for a network embedded in $\textit{d}-dimensional$ space. Specifically, it is shown that whereas the $\textit{d}-dimensional$ map might be highly fractured, drawing the map in one dimension higher “heals” the zones, which become connected (in fact, hyperbolically connected). We also provide bounds for the fatness of reception zones. Subsequently, we consider algorithmic applications and propose a new variant of approximate point location.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2015-11-02
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 62
Issue Number 5
Page Count 32
Starting Page 1
Ending Page 32

Open content in new tab

   Open content in new tab
Source: ACM Digital Library