- Home
- Documents
*SINR Diagrams: Convexity and its Applications in Wireless ... SINR Diagrams: Convexity and its...*

prev

next

out of 40

View

1Download

0

Embed Size (px)

SINR Diagrams:

Convexity and its Applications in Wireless Networks

Chen Avin∗ Yuval Emek† Erez Kantor‡ Zvi Lotker∗ David Peleg§

Liam Roditty¶

May 8, 2012

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, we have shown that as-

suming 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.

∗Department of Communication Systems Engineering, Ben Gurion University, Beer-Sheva, Israel. E-

mail:{avin,zvilo}@cse.bgu.ac.il. Zvi Lotker was partially supported by a gift from Cisco research center and the Israel Science Foundation (grant no. 894/09). †Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Zurich, Switzerland. E-mail:

yuval.emek@tik.ee.ethz.ch. ‡Department of Electrical Engineering, Technion, Haifa, Israel. E-mail: erez.kantor@ee.technion.ac.il. §Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel. E-

mail: david.peleg@weizmann.ac.il. Supported in part by grants from the Minerva Foundation, the Israel Ministry

of Science and the Israel Science Foundation (grant no. 894/09). ¶Department of Computer Science, Bar Ilan University, Ramat-Gan, Israel. E-mail: liam.roditty@gmail.com.

1 Introduction

1.1 Background

It is commonly accepted that traditional (wired, point-to-point) communication networks are sat-

isfactorily represented using a graph based model. The question of whether a station s is able to

transmit a message to another station s′ depends on a single (necessary and sufficient) condition,

namely, that there be a wire connecting the two stations. This condition is thus independent of

the locations of the two stations, of their other connections and activities, and of the locations,

connections or activities of other nearby stations1.

In contrast, wireless networks are considerably harder to represent faithfully, due to the fact

that deciding whether a transmission by a station s is successfully received by another station s′ is

nontrivial, and depends on the positioning and activities of s and s′, as well as on the positioning

and activities of other nearby stations, which might interfere with the transmission and prevent its

successful reception. Thus such a transmission from s may reach s′ under certain circumstances

but fail to reach it under other circumstances. Moreover, the question is not entirely “binary”, in

the sense that connections can be of varying quality and capacity.

The rules governing the availability and quality of wireless connections can be described by

physical or fading channel models (cf. [21, 6, 22]). Among those, the most commonly studied is

the signal-to-interference & noise ratio (SINR) model. In the SINR model, the energy of a signal

fades with the distance to the power of the path-loss parameter α. If the signal strength received

by a device divided by the interfering strength of other simultaneous transmissions (plus the fixed

background noise N ) is above some reception threshold β, then the receiver successfully receives

the message, otherwise it does not. Formally, denote by dist(p, q) the Euclidean distance between

p and q, and assume that each station si transmits with power ψi. (A uniform power network is

one in which all stations transmit with the same power.) At an arbitrary point p, the transmission

of station si is correctly received if

ψi · dist(p, si)−α N +

∑ j 6=i ψj · dist(p, sj)−α

≥ β .

Hence for a collection S = {s0, . . . , sn−1} of simultaneously transmitting stations in the d- dimensional space, it is possible to identify with each station si a reception zone Hi consisting of the points where the transmission of si is received correctly. The common belief is that the

path-loss parameter falls in the range 2 ≤ α ≤ 4, while the reception threshold is β ≈ 6 (β is always assumed to be greater than 1).

To illustrate how reception depends on the locations and activities of other stations, consider

(the numerically generated) Figure 1. Figure 1(A) depicts uniform stations s1, s2, s3 and their

1 Broadcast domain wired networks such as LANs are an exception, but even most LANs are collections of

point-to-point connections.

1

à

S1

S2

S3

-6 -4 -2 0 2 4 6

-6

-4

-2

0

2

4

6

à

S1

S2

S3

-6 -4 -2 0 2 4 6

-6

-4

-2

0

2

4

6

à

S1

S2

-6 -4 -2 0 2 4 6

-6

-4

-2

0

2

4

6

(A) (B) (C)

Figure 1: An example of SINR diagram with three transmitters s1, s2, s3 and one receiver denoted by

the solid black square. (A) The receiver can hear s2. (B) Station s1 moves and now the receiver cannot

hear any transmission. (C) If, at the same locations as in (B), s3 is silent, then the receiver can hear

s1.

reception zones. Point p (represented as a solid black square) falls insideH2. Figure 1(B) depicts the same stations except station s1 has moved closer, so that now p does not receive any transmission.

Figure 1(C) depicts the stations in the same positions as Figure 1(B), but now s3 is silent, and as

a result, the other two stations have larger reception zones, and p receives the message of s1.

Figure 1 illustrates a concept central to this paper, namely, the SINR diagram. An SINR

diagram is a “reception map” characterizing the reception zones of the stations, namely, partitioning

the plane into n reception zones Hi, 0 ≤ i ≤ n−1, and a zone H∅ where no station can be heard. In many scenarios the diagram changes dynamically with time, as the stations may choose to transmit

or keep silent, adjust their transmission power level, or even change their location from time to

time.

Notice that the SINR diagram adds no new information concerning the locations in which the

stations themselves are positioned, since it follows from the definition (refer to Section 2.2 for a

formal definition) that station si cannot receive the transmission of any station sj , j 6= i, unless the two stations coincide. However, SINR diagrams can be extremely useful for a listening device that

does not belong to S and is located at an arbitrary point p in the plane. Using the SINR diagram,

it is possible to decide which of the stations of S (if any) can be correctly received at the location

p of the listening device.

It is our belief that SINR diagrams are fundamental to understanding the dynamics of wire-

less networks, and will play a key role in the development of suitable (sequential or distributed)

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. Yet, to the best of our

knowledge, SINR diagrams have not been studied systematically so far, from either geometric,

combinatorial, or algorithmic standpoints. In particular, in the SINR model it is not clear what

2

shapes the reception zones may take, and it is not easy to construct an SINR diagram even in a

static setting.

Taking a broader perspective, a closely related concern motivating this paper is that while a

fair amount of research exists on the SINR model and other variants of the physical model, little

has been done in such models in the algorithmic arena. (Some recent exceptions are [10, 11, 12,

13, 14, 15, 17, 19, 20, 23].) The main reason for this is that SINR models are complex and hard

to work with. In these models it is even hard to decide some of the most elementary questions on