Wireless Link Capacity under Shadowing and Fading

arXiv:1706.05269v1 [cs.IT] 16 Jun 2017

Magnús M. Halldórsson

Tigran Tonoyan

ICE-TCS, School of Computer Science
Reykjavik University
mmh@ru.is,ttonoyan@gmail.com
June 19, 2017

Abstract
We consider the following basic link capacity (a.k.a., one-shot scheduling) problem in wireless
networks: Given a set of communication links, find a maximum subset of links that can successfully transmit simultaneously. Good performance guarantees are known only for deterministic
models, such as the physical model with geometric (log-distance) pathloss. We treat this problem under stochastic shadowing under general distributions, bound the effects of shadowing
on optimal capacity, and derive constant approximation algorithms. We also consider temporal fading under Rayleigh distribution, and show that it affects non-fading solutions only by a
constant-factor. These can be combined into a constant approximation link capacity algorithm
under both time-invariant shadowing and temporal fading.

1

Introduction

Efficient use of networks requires attention to the scheduling of the communication. Successful
reception of the intended signal requires attention to the interference from other simultaneous
transmissions, and both are affected crucially by the vagaries in the propagation of signals through
media. We aim to understand the fundamental capacity question of how much communication can
coexist, and the related algorithmic aspect of how to select large sets of successfully coexisting links.
The hope is to capture the reality of signal propagation, while maintaining the fullest generality:
arbitrary instances, and minimal distributional assumptions.
The basic property of radio-wave signals is that they attenuate as they travel. In free space, the
attenuation (or “pathloss”) grows with the square of the distance. In any other setting, there are
obstacles, walls, ceilings and/or the ground, in which the waves can go through complex transforms:
reflection, refraction (or shadowing), scattering, and diffraction. The signal received by a receiver is
generally a combination of the multiple paths that it can travel, that are phase-shifted, resulting in
patterns of constructive and destructive interference. The general term for variation of the received
strength of the signal from the free-space expectation is fading.
The fading of signals can be a function of time, location, frequency and other parameters, of
which we primarily focus on the first two. A distinction is often made between large-scale fading, the
effects of larger objects like buildings and trees, and the small-scale fading at the wavelength scale
caused by multiple signal-paths. We primarily distinguish between temporal fading, that varies
randomly within the time frame of communication, and shadowing, that is viewed as invariant
within the time horizon of consideration. Temporal fading is typically experienced at the smallscale as a combination of multi-path propagation and movement or other environment changes.
The most common way of modeling true fading is stochastic fading. To each point in space-time,
we associate a random variable drawn from a distribution. Typically, this is given by a distribution
in the logarithmic dBm scale, so on an absolute scale the distributions are exponential. There is a
general understanding that log-normal shadowing (LNS), which is Gaussian on the dBm scale, is
the most faithful approximation known of medium-large scale fading or even all atemporal fading
[46, 8, 11]. Empirical models often add variations depending on the environment, the heights of
the sender/receiver from the ground, and whether there is a line-of-sight (e.g., [30]). The most
prominent among the many models proposed for small-scale and temporal fading are the ones of
Rayleigh and Rice [39], with the former (latter) best suited when there is (is no) line-of-sight,
respectively. The Rayleigh distribution mathematically captures the case when the signal is highly
scattered and equally likely to arrive at any angle. Though probabilistic models are known to be far
from perfect, they are generally understood to be highly useful for providing insight into wireless
systems, and certainly more so than the free-space model alone.
Stochastic fading is the norm in generational models, such as for simulation purposes. For
instance, LNS is built into the popular NS-3 simulator. It is also commonly featured in stochastic
analysis, e.g. [29]. Worst-case analysis of algorithms has, however, nearly always involved deterministic models, either the geometric free-space model, or extensions to more general metric spaces,
e.g., (cite various). One might expect such analysis to treat similarly arbitrary or “any-case” fading,
but that quickly invokes the ugly specter of computational intractability [16].
Problems and setting. In the Link Capacity problem, we are given a set L of links, each of
which is a sender-receiver pair of nodes on the plane. We seek a maximum feasible subset of links
in L, where a set is feasible in the physical (or SINR) model if, for each link, the strength of the
signal at the receiver is β times larger than total strengths of the interferences from the other links.
We consider arbitrary/any-case positions of links, aiming for algorithms with good performance
guarantees, as well as characterizations of optimal solutions.
1

We treat Link Capacity in extensions of the standard physical model to stochastic fading. We
separate the fading into temporal and atemporal (or time-invariant) aspects, which we refer to as
temporal fading and shadowing, respectively. We generally assume independence across space in
time-invariant distributions and across time in the temporal distributions. This is a simplification,
aimed to tackle most pronounced aspects; where possible, we relax the independence assumptions,
sometimes allowing for arbitrary (worst-case) values. Observe that the two forms can be arbitrarily
correlated: the temporal results hold under arbitrary time-invariant fading.
Our results. We give a comprehensive treatment of link capacity under stochastic fading models.
We give constant-factor approximation algorithms for both time-invariant and temporal stochastic
models. These are complementary and can be multiplexed into algorithms for both types of fading.
For (time-invariant) shadowing, we allow for essentially any reasonable stochastic distribution.
We show that shadowing never decreases the optimal link capacity (up to a constant factor), but can
significantly increase it, where the prototypical case is that of co-located links. We give algorithms
for general instances, that achieve a constant factor approximation, assuming length diversity is
constant.
For temporal fading, we treat arbitrary instances that can have arbitrary pathloss/shadowing.
We show that algorithms that ignore the temporal fading given by Rayleigh distribution achieve a
constant factor approximation. The links can additionally involve weights and can be of arbitrary
length distribution.
Besides the specific results obtained, our study leaves us with a few implications that may be
of general utility for algorithm and protocol designers. One such lesson is that to achieve good
performance for shadowing,
algorithms can concentrate on the signal strengths of the links,
and can largely ignore the strength of the interference between the links. Another useful lesson is
that
algorithms can base decisions on time-invariant shadowing alone,
since the temporal fading will even out.
These appear to be the first any-case analysis of scheduling problems in general stochastic
models. In particular, ours appears to be the first treatment of approximation algorithm for
scheduling problems under shadowing or time-invariant fading.
Related Work. Gupta and Kumar [18] introduced the physical model, which corresponds to
our setting with no fading. Their work spawned off a large number of studies on “scaling laws”
regarding throughput capacity in instances with stochastic input distributions. First algorithms
with performance guarantees in the physical model were given by Moscibroda and Wattenhofer
[31]. Constant approximation for the Link Capacity problem were given for uniform power [16],
linear power [14, 38], fixed power assignments [21], and arbitrary power control [24]. This was
extended to a distributed setting [12, 2], admission control in cognitive radio [22], link rates [25],
multiple channels [6, 41], spectrum auction [23], changing spectrum availability [9], and MIMO
[43]. NP-hardness was established in [17]. Numerous works on heuristics are known, as well as
exponential time exact algorithms (e.g., [35]).
The Link Capacity problem has been fundamental to various other scheduling problems, appearing as a key subroutine for shortest link schedule [42, 16, 20], maximum multiflow [40, 4],
weighted link capacity [42, 25], and capacity region stability [3, 26].
Numerous experimental results have indicated that simplistic range-based models of wireless
reception are insufficient, e.g., [15, 28, 46]. Significant experimental literature exists that lends
2

support for stochastic models [33], especially log-normal shadowing, e.g., [46, 8, 11]. Analytic
results on stochastic fading are generally coupled with stochastic assumptions on the inputs, such
as point processes in stochastic geometry [29, 19, 44]. Most stochastic fading models though do
not lend themselves to closed-form formulation; Rayleigh fading is a rare exception [7]. Log-normal
shadowing has been shown to result in better connectivity [37, 32] and throughput capacity [36],
but this may be artifact of the i.i.d. assumption [1].
The only work on Link Capacity with any-case instances in fading models is by Dams et al.
[10], who showed that temporal Rayleigh fading does not significantly affect the performance of
LinkCapacity algorithms, incurring only a O(log∗ n)-factor increase in performance for link capacity algorithms. We improve this here to a constant factor. Rayleigh fading has also been
considered in distributed algorithms for local broadcast [45].
The non-geometric aspects of signal propagation have been modeled non-stochastically in various ways. One simple mechanism is to vary the pathloss constant α [18]. A more general approach
is to view the variation as deforming the plane into a general metric space [13, 21]. Also, the
pairwise pathlosses can be obtained directly from measurements, inducing a quasi-metric space
[6]. All of these, however, lead to very weak performance guarantees in the presence of the huge
signal propagation variations that are seen in practice (although some of that can be ameliorated
by identifying parameters with better behavior, like “inductive independence” [23]).

2
2.1

Models and Formulations
Communication Model

The main object of our consideration is a set L of communication links, numbered from 1 to n = |L|.
Each link i ∈ L represents a unit-demand communication request between a sender node si and a
receiver node ri , both point-size wireless nodes located on the plane.
We assume the links all work in the same channel, and all (sender) nodes use the same transmission power level P (unless stated otherwise). We consider the following basic question, which
is called the LinkCapacity problem: what is the maximum number of links in L that can successfully communicate in a single time slot? We will refer to a set of links that can successfully
communicate in a single time slot as feasible.
When a subset S of links transmit at the same time, a given link i will succeed if its signal
(the power of the transmission of si when measured at ri ) is larger than β times the total (sum)
interference from other transmissions, where β ≥ 1 is a threshold parameter, and the interference
of link j on link i is the power of transmission of sj when measured at ri . We will denote by Si the
received signal power of link i and by Iji the interference of link j on link i. In this notation, link
i transmits successfully if1
Si
> β.
(1)
SIR(S, i) = P
j∈S\i Iji

2.2

Geometric Path-Loss

The Geometric Path-Loss model or GPL for short, defines the received signal strength between
nodes u and v as P/d(u, v)α , where P is the power used by the sender u, α > 2 is the path-loss
exponent and d denotes the Euclidean distance. In particular, the signal strength/power of a link
1
In general, there should also be a Gaussian noise term in the success condition, which is omitted for simplicity of
exposition. It may be noted that in expectation, the success of only a fraction of links will be affected by the noise.

3

i and the interference of a link j on link i are, respectively,
G
SiG = P/liα and Iji
= P/d(sj , ri )α ,

where li = d(si , ri ) denotes the length of link i and d(sj , ri ) is the distance from the sender node of
link j to the receiver node of link i.
If the links in a set S transmit simultaneously, the formula determining the success of the
transmission on link i is similar to (1), but we will use the slightly modified notation SIRG (S, i) > β
to indicate that GPL model is considered.

2.3

Shadowing

One of the effects that GPL ignores (or models only by appropriate change of the exponent α), is
signal obstruction by objects, or shadowing. In generic networks shadowing is often modeled by a
Stochastic Shadowing model, or SS for short, such as the Log-Normal Shadowing model, or LNS for
short. In this case, there is a parametrized probability distribution D, such that the signal strength
SiD of a link i at ri is assumed to have been sampled from the distribution D and E[SiD ] = SiG ,
D is sampled from D and E[I D ] = I G . We
and similarly, for any two links i, j, the interference Iij
ij
ij
assume that signals and interferences do not change in time (due to shadowing), at least during
the time period when LinkCapacity needs to be solved. In this model too, signal reception is
characterized by the signal to interference ratio, but we will use the notation SIRD (S, i) > β to
indicate that SS model is considered.
We shall be assuming independence among the random variables. This may lead to artifacts
that are contrary to experience. It is nevertheless valuable to examine closely this case that might
be considered the most extreme.

2.4

Temporal Fading

Another effect that is not described by the models above is the temporal variations in the signal,
due to a combination of movement (of either transceivers or people/objects in the environment)
and the scattered multipath components of the signal. We will concentrate on Rayleigh fading,
where the signal power SiF is distributed according to an exponential distribution with mean Si ,
F is distributed according to an exponential
i.e. E[SiF ] = Si , and similarly, the interference power Iij
F ] = I , where S and I are the signal and interference values,
distribution with mean Iij , i.e., E[Iij
ij
i
ij
not necessarily from SS or GPL. Again, the success of transmission is described by the signal to
interference ratio. Note, however, that in this case the success is probabilistic: the same set of links
can be feasible in one time slot and non-feasible in another.

2.5

Computational Aspects

There is a striking difference between GPL and shadowing on one side, and temporal fading on the
other side, from the computational point of view. This difference stems from the spatial nature
of GPL and shadowing, and the time-variant nature of temporal fading. In the former case, an
algorithm can be assumed to have access to, e.g., the signal strengths of links, which could be
obtained by measurements. This, however, is impossible or impractical under temporal fading,
which forces the algorithms to be probabilistic and base the actions solely on the expected values
of signal strengths (w.r.t. fading distribution), and the performance ratio of algorithms is measured
accordingly (see Sec. 5 for details).

4

2.6

Technical Preliminaries

Throughout this text, by “constants” we will mean fixed values, independent of the network size
and topology (e.g. distances). Some examples are parameters α, β, and the constants under big O
notation.
Affectance. In order to describe feasibility of a set of links with arbitrary signal and interference
values, we will use the notion of affectance, which is more convenient than (but equivalent to) the
I
1
= Sijj and extend this definition to
signal to noise ratio. For two links i, j we let ai (j) = SIR(i,j)
P
P
subsets: If S ⊆ L is a set of links, then aS (j) = i∈S\j ai (j) and ai (S) = j∈S\i ai (j). Then, a
set S of links is feasible if and only if aS (j) < 1/β holds for every link j ∈ S. When considering
a particular SS distribution D or GPL we will use superscripts D and G respectively, as before.
We will use the following result of [5], which shows that feasibility is robust with respect to the
threshold value β.
Lemma 1. If a set S of links and number β ′ > 0 are such that aS (i) ≤ 1/β ′ for each link i ∈ S,
then S can be partitioned into at most ⌈2β/β ′ ⌉ feasible subsets.
Smooth Shadowing Distributions. We will use quantiles of an SS distribution. Consider an
SS distribution D and assume links use uniform power assignment. For a probability p ∈ (0, 1) and
a link i with E[SiD ] = SiG , let S̄ip denote the 1 − p-quantile, i.e., a value x such that Pr[SiD > x] = p.
For a given number p ∈ (0, 1), the distribution D is called p-smooth, if there is a constant c > 0 such
that S̄ip ≥ c · SiG holds for each link i. Note that all major distributions used to model stochastic
shadowing satisfy such a smoothness condition.

3

Comparing Shadowing to GPL

We start by comparing the optimal solutions of LinkCapacity under SS and GPL for any given
set L of links. However, a particular instance drawn from an SS distribution D is arguably not
informative and can be hard to solve. Instead, we will be more interested in the gap between GPL
optimum and a “typical” SS optimum, in the sense of expectation.
We denote by OP T G (L) the size (number of links) of the optimal solution to LinkCapacity
for a set L of links under GPL. Similarly, we denote by OP T D (L) the size of the optimal solution to
LinkCapacity under SS model with distribution D. We assume that for every link i, the variables
D (for all j) are independent, unless specified otherwise.
SiD and Iij
We will compare the expected value E[OP T D (L)] with OP T G (L), for a given set L of links,
D for all links i, j. In
where the expectation is over the distributions of random variables SiD and Iji
particular, we prove that the expected SS optimum is never worse than a constant factor of the
GPL optimum. On the other hand, due to the presence of links with high signal strength that can
appear as a result of shadowing, the capacity can considerably increase.

3.1

SS Does not Decrease Capacity

First, we show that E[OP T D (L)] = Ω(OP T G (L)), i.e., a typical optimum under SS is not worse
than the optimum under GPL.
Theorem 1. Let D be a p-smooth SS distribution with a constant p > 0, and let L be any set of
links. Then E[OP T D (L)] = Ω(OP T G (L)).
5

Proof. Let S be a maximum cardinality subset of L that is feasible under
P GPL,G and let
P us fixD a
G
D
link i ∈ S. Recall that Si = E[Si ] and, by additivity of expectation, j∈S Iji = E[ j∈S Iji ].
Also, by smoothness assumption, there are constants c > 0 and p ∈ (0, 1) such that S̄ip ≥ c · SiG and
Pr[SiD > S̄ip ] = p. On the other hand, by Markov’s inequality,


X
X
D
G
Iji
≤2
Iji
≥ 1/2.
Pr 
j∈S\i

j∈S\i

D for each i, j ∈ L. Thus,
Recall that we assumed that the random variable SiD is independent from Iji
P
P
p
G
D ≤ 2
we have that with probability at least p/2, both SiD > S̄i > cSiG and j∈S\i Iji
j∈S\i Iji
P
D
hold, implying that SiD > βc
j∈S\i Iji . By additivity of expectation, it follows that the expected
2
P
p
D
size of a subset S ′′ of S with SiD > βc
j∈S\i Iji for each link i is at least 2 · |S|. On the other
2
hand, such a set S ′′ can be partitioned into at most 4/c feasible (under SS) subsets, by Lemma 1.
G
This implies that E[OP T D (L)] ≥ pc
8 · OP T (L).

In the particular case of Log-Normal Shadowing, even independence is not necessary for the
result above to hold, as shown in th next theorem. We use the standard notation X ∼ ln N (µ, σ 2 )
and Y ∼ N (µ, σ 2 ) to denote log-normally and normally distributed random variables, respectively.
In Log-Normal Shadowing model, we assume that for all links i, j, Si ∼ ln N (µi , σ 2 ) and Iij ∼
ln N (µij , σ 2 ) for appropriate positive values µi , µij and σ. In particular, the second parameter σ is
constant.
A log-normally distributed variable X ∼ ln N (µ, σ 2 ) can be seen as X = eZ , where Z ∼ N (µ, σ 2 )
2
is a normal random variable. We will use the fact that E[X] = eµ+σ /2 . We will also use the following
basic fact.
Fact 1. If X ∼ N (µ1 , σ 2 ) and Y ∼ N (µ2 , σ 2 ) are normal random variables, then E[eX−Y ] ≤
2
eµ1 −µ2 +2σ .
Proof. By Cauchy-Schwartz,
X−Y

E[e

X

−Y

] = E[e · e

]≤

q

E[e2X ]E[e−2Y ].

Since 2X ∼ N (2µ1 , 4σ 2 ) and −2Y ∼ N (−2µ2 , 4σ 2 ), using the formula for the expectation of a
log-normal variable gives
p
2
E[eX−Y ] ≤ e2µ1 +2σ2 · e−2µ2 +2σ2 = eµ1 −µ2 +2σ .
Theorem 2. For any set L of links under Log-Normal shadowing D, E[OP T D (L)] = Ω(OP T G (L)),
even if the signal and interference distributions are arbitrarily correlated.
Proof. Let S ⊆ L be a feasible subset of L under GPL. It is enough to show that the expected
size of an optimal feasible subset of S under LNS is Ω(|S|). Consider an arbitrary link i ∈ S. The
affectance of i under LNS is:
aD
S (i)

=

D
X Iji

j∈S\{i}

SiD
6

=

X eZji
,
eZi

j∈S\{i}

where log-normal random variables eZi and eZji represent the signal of link i and interference caused
G
by link j, respectively. Recall that Iji
= E[eZji ] and SiG = E[eZi ]. Let us denote µi = E[Zi ] and
µji = E[Zji ] and note that the variables Zi , Zji have variance σ 2 . Hence, using the expectation
2
2
G
formula for log-normal variables, we can observe that SiG = eµi +σ /2 and Iji
= eµji +σ /2 . Using
this observation together with Fact 1, we obtain that for every pair i, j,
2

E[aD
j (i)]

Zji −Zi

= E[e
=

G
Iji

SiG

2

µji −µi +2σ2

]≤e

2
eµji +σ /2
= µ +σ2 /2 · e2σ
i
e

2

· e2σ = e2σ aGj (i).

Using the fact that S is feasible, and linearity of expectation, we have, for every i ∈ S, that
2σ2 · aG (i) ≤ e2σ2 /β. Thus, using Markov’s inequality, we obtain that
E[aD
S (i)] ≤ e
S
2

2

2σ
2σ
< 1/2.
/β] < β · E[aD
P[aD
S (i)]/2e
S (i) > 2e
2

2σ /β is less than |S|/2.
The latter implies that the expected number of links i ∈ S with aD
S (i) > 2e
2
It remains to note that by Lemma 1, a 1/(4e2σ )-th fraction of the remaining set of links will be
feasible under LNS, i.e., we will have that aD
S (i) < 1/β for those links i.

3.2

SS Can Increase Capacity

Next we show that, perhaps surprisingly, there are instances L for which E[OP T D (L)] ≫ OP T G (L):
the typical optima under SS can be much better than the optimum under GPL. The intuition is
that shadowing will create many links with higher signal strength than the expectation, which will
be the main contributors to the increase in capacity.
In the remainder of this section we consider a set L of links of the same length li = ℓ, and assume
that all sender nodes are located at one point (for all) and all receivers are located at another point.
We call such links co-located. Note that under GPL, any feasible subset of co-located links contains
a single link. We show below that under SS, the capacity can significantly increase. Let us fix a
p-smooth shadowing distribution D for a constant p > 0. Since L is a set of co-located links of
G
G
length ℓ, we have that for each i, j ∈ L, SiG = SjG = Iij
= Iji
= ℓPα which we denote S̄ for short.
In a dense or co-located set of links, the only hope for an increase in capacity are links of signal
strength higher than S̄. Intuitively, if there is a feasible subset S ⊆ L made of links of strength kS̄,
then |S| = O(k), since the total interference on each link is likely to be k S̄. The following definition
essentially captures the maximum size of such a set of strong links there can be in L.
For each link i, denote f (t) = Pr[SiD > tS̄] the probability that link i has signal strength at
′
least t times
i is expected. For each integer n > 0, there is a maximal value gn ≥ 0 such that
h ′ what
′
f (gn′ ) ∈ gnn , 2gnn , because f (t) is a non-increasing function of t, and f (t) → 0 when t → ∞. We

will use the following slightly
different definition: gn = max{1, gn′ }. For the case of log-normal
√
distribution, gn = Θ(e2σ ln n ), as shown in Cor. 1 below.
The following lemma (Lemma 2) gives an upper bound on the SS optimum, when the signal
strengths of links are fixed and there are few links with “strong signal”. Essentially, it indicates
that the main contribution to the capacity is by links with strong signal, and interestingly, using
power control cannot change this.
We will use the following result from linear algebra.
P √
Fact 2. [34, 27] Let A = (aij ) be an n × n non-negative real matrix. Then r(A) ≥ n1 i,j aij aji ,
where r(A) is the largest eigenvalue of A.
7

Lemma 2. Let L be a set of co-located links. Assume that the signal strengths Si are fixed, but
D are drawn from a p-smooth SS distribution D, for a number p > 0. For a number
interferences Iij
n}
for
s > 0, assume that there are at most m links i ∈ S with Si ≥ s · S̄, where m > C max{s,log
p2
D
a large enough constant C > 0. Then OP T (L) < 4m holds w.h.p. with respect to interference
distributions, even when links use power control.

Proof. Let m′ = 4m. Let E∃f eas denote the event that L contains a feasible (under SS) subset of
size m′ . Let ESf eas denote the event that a set S is feasible. By the union bound, we have that

 ′
P
en m
Pr[E∃f eas ] ≤ S⊆L,|S|=m′ Pr[ESf eas ]. The sum is over mn′ ≤ m
subsets, so it is enough to
′
′
′
−m
.
prove that for each subset S ⊆ L of size m , Pr[ESf eas ] < (en)
′
Let us fix a subset S of size m = 4m for the rest of the proof. Note that S contains a subset S ′
D are identically
of t = 3m links such that Si < s · S̄. Since D is a p-smooth distribution and all Iji
D > S̄ p ] = p for every
distributed, there is a constant c > 0 s.t. S̄ p ≥ cS¯ where S̄ p is such that Pr[Iij
′
pair i, j ∈ L. For each pair of links i, j ∈ S , let Bij denote the binary random variable that is 1 iff
D , I D } > S̄ p . Note that B are i.i.d. variables and Pr[B = 1] = p2 > 0. Consider the sum
min{Iij
ij
ij
P ji
X = i,j∈S ′ Bij . We have that E[X] = p2 · t(t − 1)/2. By a standard Chernoff bound, we have
2
that Pr[X < p2 · t(t − 1)/6] < e−p ·t(t−1)/9 . Recall that p is constant. We choose the constant C so
· log(en), which gives Pr[X < p2 · t(t − 1)/4] < (en)−m .
as to have t ≥ 3m ≥ 1 + 12
p2
It remains to prove that if X ≥ p2 · t(t − 1)/6, then the set S is not feasible with any power
assignment. Let A = (aij ) denote the normalized gain matrix of the set S ′ , where for any pair of
D /S and a = 1. As shown in [47], the largest SIR ratio that
links i, j ∈ S ′ we denote aij = Iij
j
ii
1
can be achieved with power control is r(A)−1
, where r(A) is the largest eigenvalue2 of A. Thus,
if we show that r(A) > 1/β + 1, then the set S is not feasible
P √even with power control. To that
end, we will use the bound given in Fact 2: r(A) > 1t i,j aij aji . We restrict our attention
only to the terms with Bij = 1, as those will have sufficient contribution to the sum. Indeed,
D , I D } > S̄ p ≥ cS̄. Since it also holds
recall that for each pair i, j with Bij = 1, we have min{Iij
ji
q
√
(S¯p )2
′
for each link i ∈ S , that Si < s · S̄, we have:
≥ c/s. Since we also have
aij aji >
(sS̄)2
|{i, j ∈ S ′ : Bij = 1}| > p2 t(t − 1)/6, we obtain the bound:
r(A) >

1
c
cp2 (t − 1)
· |{i, j ∈ S ′ : Bij = 1}| · ≥
.
t
s
6s

Hence, for any fixed β, we choose the constant C so as to have t ≥ 3m > 1 +
case r(A) > 1/β + 1 and the set S is infeasible. This completes the proof.

6s(1/β+1)
,
cp2

in which

Theorem 3. Let L be a set of co-located links under a p-smooth SS distribution D with associated
sequence {gn }. There are constants c1 , c2 > 0, such that
c1 gn < E[OP T D (L)] < c2 (gn + log n),
where the expectation is taken w.r.t. interference and signal strength distributions. In particular, if
gn = Ω(log n), then E[OP T D (L)] = Θ(gn ). The upper bound holds even if power control is used.
Proof. We begin by showing the first inequality. Note that the case gn = 1 trivially holds, so we
assume gn > 1.
2

It is important here that we defined the normalized gain matrix in terms of interferences and signal strengths
D
with respect to uniform power assignment (i.e., the power level P is “cancelled” in the ratio Iij
/Sj , leaving the gain
ratio, since links i and j use the same power level).

8

Let us call a link strong if SiD > gn S̄. By the definition of values gn and since gn > 1, the
probability that any fixed link i is strong is at least gn /n and at most 2gn /n. Let S be the
subset of strong links. The observation above readily implies, by the linearity of expectation, that
gn ≤ E[|S|] ≤ 2gn .
D ] = S̄ for all links i, j ∈ L. Thus, the expected affectance on each link i ∈ S is
Recall that E[Iji



D
X
X Iji
S̄ · E[|S|]
D
 ≤ 1 E
≤ 2,
Iji
E
=
Si
gn S̄
gn S̄


j∈S\{i}

j∈S\{i}

D . Thus, using Markov’s
where the expectation is taken over the distribution of interferences Iji
inequality, we get that the expected number of links in S with aD
S (i) ≤ 4 is Ω(|S|). This, together
with Lemma 1 and the fact that E[|S|] ≥ gn , proves that E[OP T D (L)] = Ω(gn ).
Now, let us demonstrate the second inequality of the claim. Let us assume that power control
is allowed, and, as before, let Si denote the signal strength of link i and Iij denote the interference
n
′
from link i to link j when all links use uniform power P . Denote c = c′ · (1 + log
gn ), where c > 8
is a large enough constant. We will show that E[OP T D (L)] = O(cgn ). Let Estr be the event that
there are at least cgn /4 strong links. Recall that the expected number of strong links is at most
2gn . Since c′ > 8, applying standard Chernoff bound gives Pr[Estr ] < e− log(2n) < 1/n, i.e., with
high probability, Estr holds: There are at most cgn /4 strong links.
Given that Estr holds, Lemma 2, applied with m = cgn /4 and s = gn (assuming the constant c′ is
suitably large), tells us that gives that with high probability, OP T D (L) = O(cgn ). This completes
the proof.

Corollary 1. For a set L of n co-located equal length links with Log-Normal Shadowing distribution
D,
√
E[OP T D (L)] = Θ(e2σ ln n ).
Proof. First, let us estimate gn . Let µ and σ be the parameters associated with the LNS distribution
of each link i. Since the links have equal lengths, those parameters are the same across all links
2
in L. Recall that S̄ = E[SiD ] = eµ+σ /2 for each link i ∈ L. We will use the fact that the tail


,
probability of a log-normal variable X with parameters µ, σ is as follows: P [X > t] = Q ln t−µ
σ
2
R ∞ −x2 /2
−x /2
where Q(x) = x e
dx is the tail probability of the standard normal distribution φ(x) = e √2π .
There is no closed form expression for Q(x), but it can be approximated as follows for all x > 0:
x
· φ(x) < Q(x) < x1 · φ(x).
x2 +1
Using these formulas, we obtain: f (t) = P[SiD > tS̄] = Q(ln t/σ + σ/2). Denote x = gn /σ + σ/2
 −x2 /2 
for some n > 1. Then, by the definition of gn , we must have that f (gn ) = Q(x) = Θ e x
=
√

Θ(gn /n). A simplification gives gn = Θ(e2σ ln n ). It remains to show that LNS is a smooth
distribution, i.e., for some constant p, S̄ p = Ω(S̄). To this end, note that the mean of a log normal
2
variable X with parameters σ, µ is eµ+σ /2 and the median is eµ , so assuming σ is fixed, we can
take p = 1/2.

Remark. Theorem 3 can be extended in two ways. First, we can assume that the sender nodes
and receiver nodes are not in exactly the same location, but are within a region of diameter smaller
compared to the link length. Second, we can assume that the links do not have exactly equal
lengths, but the lengths differ by small constant factors. These modifications incur only changes
9

in constant factors. This follows from Lemma 1. That is, the theorem predicts increased capacity
due to shadowing not only for co-located sets of links, but also sets that contain dense parts, i.e.,
have subsets that are “almost co-located”.
The results above assert that under SS, the main contributor to the capacity increase in a
co-located set of links are the “strong” links. The following result demonstrates that significant
capacity increase (though not as dramatic as above) can happen even when all links have signal
strength fixed to the GPL value. This phenomenon is due to interference distributions.
Theorem 4. Let L be a set of co-located links, all of length ℓ. Assume that the signal strengths are
fixed and equal to Si = SiG = S̄ but the interferences are drawn from Log-Normal shadowing model
D. Then,

p
log n/ log log n .
E[OP T D (L)] = Ω
Proof. Assume, for simplicity, that β = 1. Consider any fixed subset S ⊆ L of size |S| = t > eσ
for a fixed t to be specified later, and let i, j ∈ S. From the definition of LNS we have,
!
2
ln(eµ+σ /2 /t) − µ
D
Pr[Iij < S̄/t] = 1 − Q
σ
 2

σ /2 − ln t
=1−Q
σ


2
ln t − σ /2
=Q
σ

2

≥ exp(− ln2 t/2σ 2 + ln t/2 − ln ln t + c),

for a constant c, where we used the fact that Q(x) = 1 − Q(−x). Denote φ(t) = − ln2 t/2σ 2 +
D < S̄/t holds for all pairs i, j ∈ S, is et(t−1)φ(t) .
ln t/2 − ln ln t + c. Thus, the probability that Iji
Note that if the latter event happens then S is a feasible set. Let us partition L into ⌊n/t⌋ subsets
of size t. From the discussion above we have that each of those subsets is feasible with probability
at least et(t−1)φ(t) . Since those subsets are disjoint, the probability that none of them is feasible is
at most (1 − e−t(t−1)φ(t) )n/t < exp(− nt · e−t(t−1)φ(t) ). In order to have the latter probability smaller
q

log n
than 1/2, it is sufficient to set n/t > e−t(t−1)φ(t) , which holds when t = O
log log n
The following result demonstrates the limitations of Thm. 3. Namely, it shows that the O(log n)
slack in the upper bound cannot be replaced with constant in general: We show that there is an SS
distribution
with gn = O(1), such that the gap between SS and GPL capacities is at least a factor
p
of Ω( log n/ log log log n) for co-located equal length links. It also shows that gn = Ω(log n) is not
necessary for increase in capacity compared to GPL.
Theorem
5. There
is an SS distribution D with gn = O(1) for each n, such that E[OP T D (L)] =

q
log n
Ω
log log log n holds for a set L of n co-located links.

Proof. Let S denote the expected signal strength of each link, as before. Consider the following
6
discrete SS distribution D, where for each link i and t ≥ 1, Pr[SiD = cS
2t ] = π 2 t2 , where c =
−1
 P
1
6
. It is easy to show that E[SiD ] = S and gn = O(1) for each n. Consider an
t≥1 t2 2t
π2

arbitrary subset S of size m and fix a link i ∈ S. It follows from the definition of D, that Pr[SiD ≥
1
D ] = S and Pr[I D < S ] ≥
S] ≥ 1/2. For each link j ∈ S \ {i}, E[Iji
= 2 log12 m . Thus, by
ij
β·m
2β log2 m
10

m−1

P
1
D < S ] ≥ Pr[I D < S , for all j ∈ S \ i] ≥
independence of interferences, Pr[ j∈S\i Iji
ji
β
βm
2 log2 m
and



m
X
1
S D
D
D
D


.
Pr[aS (i) < 1/β] ≥ Pr
Iji < |Si ≥ S · Pr[Si ≥ S] ≥
β
2 log2 m
j∈S\i

m2

. Split L into n/m disjoint subsets
Thus, set S is feasible with probability at least 2 log12 m
S1 , S2 , . . . , Sn/m of size m and let Et denote the event that St is feasible. Note that the events Et

m2
are independent, and Pr[Et ] ≥ 2 log12 m
. By the union bound and independence, Pr[∃t, Et ] ≥
q

m2
log n
n
1
·
.
Thus,
in
order
to
have
Pr[∃t,
E
]
≥
1/2,
it
suffices
to
take
m
≥
t
m
3 log log log n .
2 log2 m

4

Computing Capacity under Shadowing

In this section we study the algorithmic aspect of LinkCapacity under SS. Namely, our aim
is to design algorithms that perform well in expectation under SS, compared with the expected
optimum under SS. In the first part, we handle (nearly) co-located links, while the second part
discusses the more general case when the links are arbitrarily placed on the plane. In both cases,
we obtain constant factor approximations for links of bounded length diversity, under general SS
distributions satisfying weak technical assumptions. This holds against an optimum that can use
arbitrary power control.
Let us start with several definitions. For any set L of links, let ∆ = ∆(L) = maxi,j∈L {li /lj }
denote the max/min link length ratio in L. A set L is called equilength if ∆(L) < 2.
An equilength set S of links is called cluster if there is a square of side length ℓ/2 that contains
the sender nodes of all links in S, where ℓ = mini∈S {li }.

4.1

Clusters

Consider a cluster L of links with minimum length ℓ. The algorithm is based on Thm. 3, which
suggests that choosing only the strong links is sufficient for a constant factor approximation to the
expected optimum. We prove that a similar result holds in a more general setting, where the signal
strengths Si of links i ∈ L are fixed and arbitrary, while interferences are drawn from a p-smooth
SS distribution D for a constant p > 0. The algorithm is as follows.
Algorithm. Let set S be constructed by iterating over the set L in a decreasing order of link
¯ Output the set
strength, and adding each link i to S if its strength Si satisfies Si > 2β|S|S.
1
D
ALG = {i ∈ S : aS (i) < β } of successful links in S.
The theorem below shows that this strategy results in only additive O(log n) expected error,
and yields a fully constant factor approximation when signal strengths are drawn from an SS
distribution with gn = Ω(log n), such as LNS.
Theorem 6. Let L be a cluster of n links. Assume that the signal strengths of links are fixed and
arbitrary, but interferences are drawn from a p-smooth SS distribution D for a constant p > 0.
Then,
Eint [OP T D (L)] = O(Eint [|ALG|] + log n),

11

where the expectation is taken only w.r.t. interference distributions. When the signal strengths are
also drawn from D and we further have gn = Ω(log n), then
E[|ALG|] = Θ(E[OP T D (L)]),
where expectation is taken w.r.t. signal and interference distributions.
Proof. P
First, let us note that E[|ALG|] ≥ |S|/2. Indeed, take a linkP
i ∈ S. We have that Si > 2β S̄|S|
D ] ≤ |S|S̄. Thus, with probability at least 1/2,
D
and E[ j∈S\i Iji
j∈S\i Iji ≤ 2S̄|S| < Si /β, i.e.,
i ∈ ALG. By additivity of expectation, this implies that E[|ALG|] ≥ |S|/2. It remains to show
that E[OP T D (L)] = O(|S| + log n). But this simply follows from Lemma 2 with s = 2β|S| and an
appropriate value m = O(max{|S|, log n}). The second part of the theorem follows from Thm. 3,
which asserts that E[|S|] = Θ(gn ) = Ω(log n).

4.2

General Equilength Sets

The algorithm presented in the previous section can be extended to general sets of equilength
links, which are not necessarily clusters. The essential idea is to partition such a set into clusters,
solve each cluster separately, then combine the solutions. This, however, requires some technical
elaboration.
Let L be an arbitrary equilength set. First, we partition L into a constant number of wellseparated subsets, where an equilength set S is called well-separated if S is a disjoint union of
subsets S1 , S2 , . . . such that for each t, St is a cluster and for each s 6= t and links i ∈ Ss and j ∈ St ,
min{d(si , rj ), d(sj , ri )} > ℓ, where ℓ = mini∈S {li }.
Proposition 1. Any equilength set L on the plane can be split into a constant number of wellseparated subsets.
Proof. Let ℓ = mini∈L li . Partition the plane into squares of side ℓ/2 with horizontal and vertical
lines. Consider only the squares intersecting the bounding rectangle of links L. Assign the squares
integer coordinates (x, y) in the following way: if two squares with coordinates (x, y) and (x′ , y ′ )
share a vertical (horizontal) edge then y = y ′ and |x − x′ | = 1 (x = x′ and |y − y ′ | = 1, resp.). Then
split L into 49 subsets Lks , k, s = 0, 1, . . . , 6, where Lk,s = {i ∈ L : si is in a square with (x, y) =
(k, s) mod 7}. Let us fix R = Lk,s for some arbitrary indices s, k and let i, j ∈ R be any links. It
remains to note that if the sender nodes of i and j are in different squares, then d(si , sj ) ≥ 6ℓ/2 = 3ℓ,
which via the triangle inequality (and using the assumption that L is equilength) implies that
d(si , rj ), d(sj , ri ) > ℓ.
Algorithm. Partition L into well-separated subsets, solve the capacity problem for each subset
separately (as described below) and output the best solution obtained.
To process a well-separated subset L′ , observe first that L′ is a disjoint union of clusters
L1 , L2 , . . . , Lm , by definition. Run the algorithm from Sec. 4.1 on each cluster Lt separately,
obtaining a subset St . Denote S = ∪m
t=1 St . Let c > 0 be a constant, as indicated in the proof of
Thm. 7, and let R be the set of all links j in S such that aD
S (j) < 2c. Partition R into at most 2cβ
feasible subsets (under SS) using Lemma 1 and let ALG be the largest of those.
Theorem 7. Let L be a set of n equilength links (arbitrarily placed on the plane) under a p-smooth
SS distribution D, for a constant p > 0, with gn = Ω(log n). Then,
E[|ALG|] = Θ(E[OP T D (L)]).
12

Proof. First, note that performing the step of partitioning into well-separated subsets and selecting
the best one, we lose at most a constant factor against the optimum. So we concentrate on a
well-separated set L′ , consisting of clusters L1 , L2 , . . . Lm . Recall that S1 , S2 , . . . , Sm be the subsets
obtained by the algorithms on the clusters and S = ∪m
t=1 St .
We first show that the expected number of links the algorithm chooses from S is Ω(|S|), where
the expectation is only w.r.t. interference distributions. To that end we show that the out-affectance
from any link in S to all the other links is constant under GPL. That means that the expected
affectance on a link in S, even under D, is constant, which yields the claim after some sparsification
of S.
For any two indices s, t ∈ {1, . . . , m}, s 6= t, define the representative affectance a(s, t) by set Ss
on set St as the largest GPL affectance by a link in Ss on a link in St : a(s, t) = maxi∈Ss ,j∈St aGi (j).
It follows from the definition of the GPL affectance and the assumption that all links have length at
most 2ℓ, that a(s, t) = O(1) · (ℓ/dst )α , where dst = mini∈Ss ,j∈St {d(si , rj )} ≥ ℓ (by well-separation).
P
Claim 1. For every s, m
t=1,t6=s a(s, t) = O(1).

Sketch. This can be shown by an area argument that uses the fact that α > 2. Take any link i ∈ Ss .
Partition the space around the sender node si into concentric rings of width ℓ. By well-separation,
there are no other links within distance ℓ from si . Number the rings starting from si . Let ar
denote the total contribution of sets St that intersect the ring number r. It is easy to see that
ar = O(1/r α ) · zr , where zr is the number of such sets. Since each set St occupies an area O(ℓ2 )
(it is a cluster) and different
P∞ a simple area argument gives that zr = O(r), so
Pm sets are disjoint,
α−2
ar = O(1/r
). Thus, t=1,t6=s a(s, t) = r=1 ar = O(1), because α > 2 and thus the last sum
converges.
Now, fix an index s and a link i ∈ Ss . Let j ∈ St , for t 6= s. Recall, from the definition
P
IG
IG
of St , that Sj = Ω(|St |)SjG . Thus, Sijj = O(1/|St |) · aGi (j) = O(1/|St |) · a(s, t) and j∈St Sijj =
O(1/|St |) · a(s, t) · |St | = O(a(s, t)). A similar argument applied to the links j ∈ Ss gives that
G
G
P
Iij
Iij
G
=
O(1/|S
|)
·
a
(j)
=
O(1/|S
|),
so
s
s
j∈S
\i
i
Sj
Sj = O(1).
s
Summing over all links and using Claim 1, we obtain that
G
X Iij

j∈S\i

Sj

=

G
X Iij

j∈Ss \i

Sj

+

G
X X Iij
t6=s j∈St

= O(1) + O(1) ·
Summing over all links i ∈ S, we obtain

P

X

Sj

a(s, t) = O(1).

t6=s

G
Iij
i,j∈S Sj

= O(|S|). By the pigeonhole principle, there
P
IG
is a subset S ′ ⊆ S with |S ′ | ≥ |S|/2, such that for each link j ∈ S ′ , i∈S Sijj ≤ c for a constant


G
D
P
P
Iij
Iij
=
c > 0. Thus, for each link j ∈ S ′ , Eint
i∈S Sj < c. The latter implies that
i∈S Sj
′
D
Pr[aD
S (j) < 2c] > 1/2 and the expected number of links j ∈ S with aS (j) < 2c is at least
′
|S |/2 ≥ |S|/4. This is exactly the set R (or Rr , for a particular index set Ir ) we are looking for.
Thus, by Lemma 1, R can be split into at most 2βc feasible subsets. The largest of them, which is
output by the algorithm, has expected cardinality at least |S|/(8βc).

It now only remains to bound OP T D (L) in terms of |S|. Recall that OP T D (L) = O(OP T D (L′ )).
We know from Thm. 6 that E[|St |] = Θ(E[OP T D (Lt )]) for t = 1, 2, . . . , m. Combining those
13

observations, we obtain the desired bound:
E[OP T D (L)] = E[OP T D (L′ )] = O

m
X

OP T D (Lt )

t=1

=O

m
X
t=1

4.3

!

(E[|St |])

!

= O (E[|S|]) .

General Sets

Any set of links can be partitioned into at most ⌈log ∆⌉ equilength subsets. Thus, we can solve the
problem for each of the subsets using the algorithm from the previous section and take the largest
solution obtained. That will give us, e.g., O(log ∆) approximation for general sets of links under
LNS. This holds even against an optimum that can use arbitrary power control.

5

The Effect of Temporal Fading

In Rayleigh fading model, due to the temporal variability of signals, it is natural to define a ”typical
optimum” as follows. For a set L of n links (numbered, as before), we consider a transmission
probability vector p̄ = (p1 , p2 , . . . , pn ), representing that link i transmits with probability pi ∈ [0, 1].
Let Qp̄ (i) denote the probability that link i succeeds when all links transmit according to the
vector p̄ (as defined by theP
signal to interference ratio). Then, the expected number of successful
transmissions is w(L, p̄) = i∈L Qp̄ (i). Finally, we define the optimum capacity as the maximum
expected number of successful transmissions with any transmission probability vector p̄; namely,
OP T F (L) = maxp̄ w(L, p̄).
Here we denote the non-fading values of signals and interferences as Si and Iij and assume that
they can take arbitrary positive values. Also, OP T (L) denotes the size of the optimal solution to
LinkCapacity with respect to those values. We will show that OP T (L) and OP T F (L) are only
constant factor apart from each other, namely, the effect of temporal fading is at most a (small)
constant factor.
In fact, we can prove a more general result. Assume that each link i has a positive weight
wi . The weighted variant
Pof LinkCapacity requires to find a feasible subset S ⊂ L of links with
maximum total weight i∈S wi . We let W OP T (L) denote the weight of an optimal solution in
the non-fading setting. Similarly, given a transmission probability vector p̄, let
Pus re-define the
expected weight of the set of successful transmissions when using p̄ as w(L, p̄) = i∈L wi Qp̄ (i) and
let W OP T F (L) = maxp̄ w(L, p̄). Then we have the following result. We assume that for every link
F (for all j) are independent.
i, the variables SiF and Iij
Theorem 8. For any set L of links, W OP T (L) = Θ(W OP T F (L)).
Dams et al. [10] have already shown that W OP T (L) = O(W OP T F (L)). Specifically, given a
feasible set S, if we form the vector p̄ by pi = 1 if li ∈ S and pi = 0 otherwise, then w(L, p̄) ≥ |S|/e.
Thus, it remains to show that W OP T (L) = Ω(W OP T F (L)).
Proof. Let q̄ be the probability
vector corresponding to W OP T F (L), namely, q̄ is such that
P
W OP T F (L) = w(L, q̄) = i∈L wi Qq̄ (i).
Note thatP
within the confines of the argument, q̄ is a deterministic vector, not a random variable.
Let Aq̄ (j) = i∈L qi · ai (j) denote the expected affectance on link j.
14

Dams et al. [10, Lemma 2] applied a characterization of Li and Haenggi [29] to obtain that for
each link i,
qi e−Aq̄ (i) ≤ Qq̄ (i)) ≤ qi e−Aq̄ (i)/2 .
(2)
The idea of our proof is to consider only nodes with small expected affectance under q̄; they
can be sparsified to a feasible set of large size. The key observation is that much of the weight in
the optimal solution with fading is centered on those low-affectance nodes; otherwise, one could
obtain a larger solution by uniformly reducing the probabilities.
Let k = 4 · ln 11/2 = 4(ln 4 + ln 11/8) ∼ 6.819. Let H = {i ∈ L : Aq̄ (i) ≤ k} be the links of
small weighted affectance and let H ′ = L \ H.

Claim 2. w(H, q̄) ≥ 23 w(L, q̄) = 23 W OP T F (L).

Proof. Suppose otherwise, so w(H ′ , q̄) > 23 w(L, q̄). Form a new probability vector p̄ = q̄/4, i.e.,
pi = qi /4, for all i ∈ L. Then, Ap̄ (i) = Aq̄ (i)/4, for all i ∈ L. For i ∈ H ′ , since Aq̄ (i) > k, it holds
from the definition of k that
−

Aq̄ (i)
Aq̄ (i)
− ln 4 ≥ −
+ ln 11/8 .
4
2

(3)

Thus, for i ∈ H ′ ,
qi −Ap̄ (i)
e
= qi e−Aq̄ (i)/4−ln 4
4
11
11 −Aq̄ (i)/2
qi e
≥ Qq̄ (i) ,
≥ qi e−Aq̄ (i)/2+ln 11/8 =
8
8

Qp̄ (i) ≥

using (2), the definition of p̄, (3), rearrangement, and again (2). Thus, w(H ′ , p̄) ≥
follows that
w(L, p̄) = w(H, p̄) + w(H ′ , p̄) ≥

11
′
8 w(H , q̄).

It

11
1
w(H, q̄) + w(H ′ , q̄)
4
8

1
9
= w(L, q̄) + w(H ′ , q̄) > w(L, q̄),
4
8

where the strict inequality uses the supposition. This contradicts the choice of q̄. Hence, the claim
follows.
We continue with the proof of Theorem 8. We use the probabilistic method to show that there
is a feasible subset of H of weight at least W OP T F (L)/(6k).
Let X be a random set of links from H, where link i ∈ H is added to X with probability qi /(2k).
Consider a link t ∈ H and let Yt = aX (t) be the random variable whose value is the affectance of
set X on link t. By definition of H, Aq̄ (t) ≤ k. Observe that
X
E[Yt ] = E[aX (t)] =
Pr[j ∈ X] · aj (t)
j∈H

Aq̄ (t)
1 X
1
=
qj · aj (t) ≤
≤ ,
2k
2k
2
j∈H

using the linearity of expectation and the definition of Aq̄ . Thus, by Markov’s inequality,
Pr[Yt ≤ 1] ≥ Pr[Yt ≤ 2 · E[Yt ]] ≥
15

1
.
2

(4)

Observe that the value of Yt is independent of the event that link t was selected into X. Let
SX = {i ∈ X : aX (i) ≤ 1} be the subset of feasible links in X. It follows that
X
X
E[
wi ] =
wi Pr[i ∈ X and Yi ≤ 1]
i∈SX

i∈L

≥
≥
≥

X

wi Pr[i ∈ X] · Pr[Yi ≤ 1]

X

wi ·

i∈H

i∈H

qi 1
·
2k 2

(Independence)
((4) and defn. of X)

1 X
wi Qq̄ (i)
4k

((2))

i∈H

w(H, q̄)
4k
W OP T F (L)
≥
6k

(Defn. of w)

=

(Claim 2) .

As per the probabilistic method, this implies there exists a feasible set of size Ω(W OP T F (L)).

6

Conclusions

We have compared link capacity in instances with and without stochastic shadowing, as well as
with and without temporal fading. We have also obtained constant-factor approximations in both
cases. Numerous open problems and directions still remain.
There is room to strengthen and generalize our results. This includes extending the approximations for shadowing to links of unbounded length diversity, and extending the temporal fading
analysis to other stochastic models.
Modeling correlations and analyzing its effect on link capacity would be valuable, and the same
holds for analyzing other scheduling problems, including weighted link capacity and shortest length
schedules.
Acknowledgements. This work was supported by grants 152679-05 and 174484-05 from the
Icelandic Research Fund. We thank Michael Neely for pointing out an error in an earlier version
of the paper.

References
[1] P. Agrawal and N. Patwari. Correlated link shadow fading in multi-hop wireless networks.
IEEE Trans. Wireless Commun., 8(8):4024–4036, 2009.
[2] E. Ásgeirsson and P. Mitra. On a game theoretic approach to capacity maximization in wireless
networks. In INFOCOM, 2011.
[3] E. I. Asgeirsson, M. M. Halldórsson, and P. Mitra. A fully distributed algorithm for throughput
performance in wireless networks. In CISS, pages 1–5, 2012.
[4] E. I. Ásgeirsson, M. M. Halldórsson, and P. Mitra. Maximum MIMO flow in wireless networks
under the SINR model. In WiOpt, pages 295–302, 2014.

16

[5] J. Bang-Jensen and M. M. Halldórsson. Vertex coloring edge-weighted digraphs. Inf. Process.
Lett., 115(10):791–796, 2015.
[6] M. Bodlaender and M. M. Halldórsson. Beyond geometry: Towards fully realistic wireless
models. In PODC, 2014.
[7] P. Cardieri. Modeling interference in wireless ad hoc networks. IEEE Commun. Surveys Tuts.,
12(4):551–572, 2010.
[8] Y. Chen and A. Terzis. On the implications of the log-normal path loss model: an efficient
method to deploy and move sensor motes. In SenSys, pages 26–39. ACM, 2011.
[9] J. Dams, M. Hoefer, and T. Kesselheim. Sleeping experts in wireless networks. In Distributed
Computing, DISC, pages 344–357. Springer, 2013.
[10] J. Dams, M. Hoefer, and T. Kesselheim. Scheduling in wireless networks with Rayleigh-fading
interference. IEEE Trans. Mobile Comput., 14(7):1503–1514, 2015.
[11] B. Dezfouli, M. Radi, S. A. Razak, T. Hwee-Pink, and K. A. Bakar. Modeling low-power
wireless communications. J Netw. Comput. Appl., 51:102–126, 2015.
[12] M. Dinitz. Distributed algorithms for approximating wireless network capacity. In INFOCOM,
pages 1–9. IEEE, 2010.
[13] A. Fanghänel, T. Kesselheim, H. Räcke, and B. Vöcking. Oblivious interference scheduling. In
PODC, pages 220–229, August 2009.
[14] A. Fanghänel, T. Kesselheim, and B. Vöcking. Improved algorithms for latency minimization
in wireless networks. In ICALP, pages 447–458, 2000.
[15] D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker. Complex
behavior at scale: An experimental study of low-power wireless sensor networks. Technical
report, UCLA/CSD-TR 02, 2002.
[16] O. Goussevskaia, M. M. Halldórsson, and R. Wattenhofer. Algorithms for wireless capacity.
IEEE/ACM Trans. Netw., 22(3):745–755, 2014.
[17] O. Goussevskaia, Y.-A. Oswald, and R. Wattenhofer. Complexity in geometric SINR. In
MobiHoc, pages 100–109, 2007.
[18] P. Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Trans. Inf. Theory,
46(2):388–404, 2000.
[19] M. Haenggi, J. G. Andrews, F. Baccelli, O. Dousse, and M. Franceschetti. Stochastic geometry
and random graphs for the analysis and design of wireless networks. IEEE J. Sel. Areas
Commun., 27(7):1029–1046, 2009.
[20] M. M. Halldórsson. Wireless scheduling with power control. ACM TALG, 9(1):7, 2012.
[21] M. M. Halldórsson and P. Mitra. Wireless Capacity with Oblivious Power in General Metrics.
In SODA, 2011.
[22] M. M. Halldórsson and P. Mitra. Wireless connectivity and capacity. In SODA, pages 516–526,
2012.
17

[23] M. Hoefer and T. Kesselheim. Secondary spectrum auctions for symmetric and submodular
bidders. ACM TEAC, 3(2):9, 2015.
[24] T. Kesselheim. A constant-factor approximation for wireless capacity maximization with power
control in the SINR model. In SODA, pages 1549–1559, 2011.
[25] T. Kesselheim. Approximation algorithms for wireless link scheduling with flexible data rates.
In ESA, pages 659–670, 2012.
[26] T. Kesselheim. Dynamic packet scheduling in wireless networks. In PODC, pages 281–290,
2012.
[27] L. Y. Kolotilina. Lower bounds for the Perron root of a nonnegative matrix. Linear Algebra
Appl., 180:133–151, 1993.
[28] D. Kotz, C. Newport, R. S. Gray, J. Liu, Y. Yuan, and C. Elliott. Experimental evaluation of
wireless simulation assumptions. In MSWiM, pages 78–82. ACM, 2004.
[29] X. Liu and M. Haenggi. Throughput analysis of fading sensor networks with regular and
random topologies. EURASIP J. Wirel. Commun. Netw., 2005(4):554–564, 2005.
[30] B. Mondal, T. A. Thomas, E. Visotsky, F. W. Vook, A. Ghosh, Y.-H. Nam, Y. Li, J. Zhang,
M. Zhang, Q. Luo, et al. 3d channel model in 3gpp. IEEE Commun. Mag., 53(3):16–23, 2015.
[31] T. Moscibroda and R. Wattenhofer. The complexity of connectivity in wireless networks. In
INFOCOM, pages 1–13, 2006.
[32] T. Muetze, P. Stuedi, F. Kuhn, and G. Alonso. Understanding radio irregularity in wireless
networks. In SECOND, pages 82–90. IEEE, 2008.
[33] H. Nikookar and H. Hashemi. Statistical modeling of signal amplitude fading of indoor radio
propagation channels. In Proc. 2nd IEEE International Conference on Universal Personal
Communications, volume 1, pages 84–88, 1993.
[34] A. J. Schwenk. Tight bounds on the spectral radius of asymmetric nonnegative matrices.
Linear Algebra Appl., 75:257–265, 1986.
[35] Y. Shi, Y. T. Hou, S. Kompella, and H. D. Sherali. Maximizing capacity in multihop cognitive
radio networks under the SINR model. IEEE Trans. Mobile Comput., 10(7):954–967, 2011.
[36] P. Stuedi and G. Alonso. Log-normal shadowing meets SINR: A numerical study of capacity
in wireless networks. In SECON, pages 550–559, 2007.
[37] P. Stuedi, O. Chinellato, and G. Alonso. Connectivity in the presence of shadowing in 802.11
ad hoc networks. In WCNC, volume 4, pages 2225–2230. IEEE, 2005.
[38] T. Tonoyan. On the capacity of oblivious powers. In ALGOSENSORS, volume 7111 of Lecture
Notes in Comput. Sci., pages 225–237. Springer, 2011.
[39] D. Tse and P. Viswanath. Fundamentals of wireless communication. Cambridge University
Press, 2005.
[40] P. Wan. Multiflows in multihop wireless networks. In MobiHoc, pages 85–94, 2009.

18

[41] P.-J. Wan. Joint selection and transmission scheduling of point-to-point communication requests in multi-channel wireless networks. In MobiHoc, pages 231–240, 2016.
[42] P.-J. Wan, O. Frieder, X. Jia, F. Yao, X. Xu, and S. Tang. Wireless link scheduling under
physical interference model. In INFOCOM, pages 838–845. IEEE, 2011.
[43] P.-J. Wan, B. Xu, O. Frieder, S. Ji, B. Wang, and X. Xu. Capacity maximization in wireless
mimo networks with receiver-side interference suppression. In MobiHoc, pages 145–154, 2014.
[44] L. Wang, P. Wan, and W. Washington. Connectivity of multihop wireless networks with
log-normal shadowing. Wireless Networks, 21(7):2279–2292, 2015.
[45] Y. Wang, D. Yu, Q. Liu, and F. C. Lau. Inductive coloring: Implementing basic communication
primitives with Rayleigh-fading interference. In INFOCOM, pages 1–9. IEEE, 2016.
[46] M. Z. Zamalloa and B. Krishnamachari. An analysis of unreliability and asymmetry in lowpower wireless links. ACM TOSN, 3(2):7, 2007.
[47] J. Zander. Performance of optimum transmitter power control in cellular radio systems. IEEE
Trans. Veh. Technol, 41(1):57–62, 1992.

19

