The Topology of Wireless Communication

Details The Topology of Wireless Communication The Topology of Wireless Communication

2011-03-23

arxiv.org/abs/1103.4566v2

Computer Science

Data Structures and Algorithms

64 pages, appeared in STOC'11

Scientific paper

In this paper 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 describe the behavior of a multi-station network, we use the convenient representation of a \emph{reception map}. In the SINR model, the resulting \emph{SINR diagram} partitions the plane into reception zones, one per station, and the complementary region of the plane where no station can be heard. We consider the general 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 point location techniques as well as the theoretical challenge of understanding the geometry of SINR diagrams. We achieve several results in both directions. We establish a form of weaker convexity in the case where stations are aligned on a line. In addition, one of our key results concerns the behavior of a $(d+1)$-dimensional map. Specifically, although the $d$-dimensional map might be highly fractured, drawing the map in one dimension higher "heals" the zones, which become connected. In addition, as a step toward establishing a weaker form of convexity for the $d$-dimensional map, we study the interference function and show that it satisfies the maximum principle. Finally, we turn to consider algorithmic applications, and propose a new variant of approximate point location.

Affiliated with

Also associated with

No associations

Rating

The Topology of Wireless Communication does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Topology of Wireless Communication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Topology of Wireless Communication will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-441577