text: where λ ; i = 1, 2, ..., n are the eigenvalues of CΣ | CT i x y z with C deﬁn(cid:88)ed in (7), and λ satisfying the(cid:0)follow(cid:1)ing constraint: Fig. 1. Block diagram of the remote source coding problem nx − min (λ, λ ) = n D tr Σ | . (12) i x x yz i=1 B. Applications Related to our problem is also another problem considered One possible application of the formulated problem is in in [1], where the constraint (4) is replaced by a mutual wireless acoustic sensor networks which is a set of wireless mi- information constraint deﬁned as: crophones equipped with communication and signal processing units. The microphones are randomly distributed in an envi- | ≥ ronment, sampling the sound ﬁeld. The measurements made I (x; u z) R , (13) I by each microphone should be delivered at a fusion center possibly via a sequence of transmissions through neighboring (cid:18) (cid:19) nodes. It is desirable to compute the local RDF at each node of where R is a given rate. The rate-rate function for this such a network. This can be used for computing the network I | | spuromb-lreamte,wbiythwahdicishtoornteiocnacnofnosrtmrauinlatte(ea.gs.udmis-troartteiomniantimthiezaﬁtinoanl problem for 0 ≤(cid:88)RI ≤12 lo(cid:34)g(cid:18) |ΣΣxx||yzz|(cid:19) is then given(cid:35) by: destination). As suggested in [2], this can be used for optimal   routing in the network. When sending a message from a node 1 nx 1 − µ − − − −1 to a neighboring node, the measurement of the sound at the R (R ) = log µ − i (1 µ ) , latter node can be used as side information, thus ﬁtting our I 2 i 1 γ i i=1 distributed source coding framework. (14) Another application is in relay networks as discussed in [r1el]a.yI,natnhdisrceacseeiv, enrxa,nnteyn, naansd. nz are the number of transmitter, wΣh1e/|2reCTµΣi−, |1Ci Σ1=/|2, an1d, .γ..,∈n[x0, 1a)resatisthﬁees tehiegefnovllaolwueisng:of y z x z y z (cid:18) (cid:19) (cid:88) C. Related Work In the special case where nx = ny = nz = 1, the RDF for −1 nx 1 − µ − the above-(cid:40)mentione(cid:16)d problem i(cid:17)s given by [3]: 2 log 1 − γi = RI. (15) i=1 − ≤ 1 log Σx|−z Σx|yz , if Σ | < D Σ | In general, it is not straightforward to generalize the above R(D) = 02, D Σx|yz if Dx>yzΣ | x z results to the case of covariance matrix distortion constraints. x z (9) Indeed, due to the matrix form of the distortion constraint, it does not appear as it is possible to reduce the problem to an equivalent problem of parallel scalar sources. where D is the scalar distortion constraint, and Σ | and Σ | are conditional variances of scalar random variabxlez x. x yz In [4], the RDF for (4) was recently found for the somewhat restrictive case where n = n = n , and C in (7) is invertible, For the vector case, the authors in [1] solved the prob- and the distortion consxtraintysatisﬁzes Σ | ≺ D (cid:22) Σ | . lem for the mean-squared error distortion constraint; i.e. for Under these assumptions, th(cid:32)e R(cid:12) DF was sxhoywz(cid:12)n(cid:33)to be: x z (cid:16) (cid:104) (cid:105)(cid:17) (cid:12) (cid:12) problem (3) with the distortion constraint (4) replaced by: (cid:12) (cid:12) (cid:12) (cid:12) − tr E (x − xˆ) (x − xˆ)T ≤ n D. (10) R (D) = 1 log Σx|z− Σx|yz . (16) x 2 D Σ | x yz This is similar to a case where in (4), only the sum of the Although under the above assumptions the problem is diagonal elements of the distortion and error matrices are manageable to solve, it is a quite restricted case. In this paper, ≺ of interest. Thus, in this particular case, the vector Gaussian we consider the most general case with Σ | D and x yz problem can be treated as parallel scalar problems, leading without the above assumptions, and establish a lower bound to well-known water-ﬁlling interpretations. The RDF for this and an upper bound on the RDF, which in general do not ≤ ≤ problem when tr(Σ | ) n D tr(Σ | ) was shown in [1] coincide. Then we consider some special cases for which the x yz x x z to be: (cid:18) (cid:19) two bounds coincide, giving the exact RDF. We will show that (cid:88) (9) and (11) could be derived as special cases of our results. In R(D) = 1 nx log λi +, (11) axddwiittihona,didnittihveeswpehcitiealncoaissee,th(a1t4y) caonudldz aalrseonboeisdyevrievresdionfrsoomf 2 λ our results. We will also generalize (16) to the case that no i=1 ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: where

text: λ

text: i

text: n

text: are

text: the

text: eigenvalues

text: of

text: CΣ

text: CT

text: i

text: x

text: y

text: z

text: with

text: C

text: in

text: and

text: λ

text: satisfying

text: constraint:

text: Fig.

text: Block

label: caption

text: diagram

text: of

text: the

text: remote

text: source

text: coding

text: problem

text: nx

text: min

text: (λ,

text: λ

text: n

text: D

text: tr

text: Σ

text: i

text: x

text: x

text: yz

text: B.

text: Applications

text: Related

text: to

text: our

text: problem

text: is

text: also

text: another

text: problem

text: considered

text: One

text: possible

text: application

text: of

text: the

text: formulated

text: problem

text: is

text: in

text: in

text: where

text: the

text: constraint

text: is

text: replaced

text: by

text: a

text: mutual

text: wireless

text: acoustic

text: sensor

text: networks

text: which

text: is

text: a

text: set

text: of

text: wireless

text: mi-

text: information

text: constraint

text: deﬁned

text: as:

text: crophones

text: equipped

text: with

text: communication

text: and

text: signal

text: processing

text: units.

text: The

text: microphones

text: are

text: randomly

text: distributed

text: in

text: an

text: envi-

text: ronment,

text: sampling

text: the

text: sound

text: ﬁeld.

text: The

text: measurements

text: made

text: I

text: (x;

text: u

text: z)

text: R

text: I

text: by

text: each

text: microphone

text: should

text: be

text: delivered

text: at

text: a

text: fusion

text: center

text: possibly

text: via

text: a

text: sequence

text: of

text: transmissions

text: through

text: neighboring

text: nodes.

text: It

text: is

text: desirable

text: to

text: compute

text: the

text: local

text: RDF

text: at

text: each

text: node

text: of

text: where

text: R

text: is

text: a

text: given

text: rate.

text: The

text: rate-rate

text: function

text: for

text: this

text: such

text: a

text: network.

text: This

text: can

text: be

text: used

text: for

text: computing

text: the

text: network

text: I

text: problem

text: for

text: ≤12

text: is

text: then

text: by:

text: destination).

text: As

text: suggested

text: in

text: this

text: can

text: be

text: used

text: for

text: optimal

text: routing

text: in

text: the

text: network.

text: When

text: sending

text: a

text: message

text: from

text: a

text: node

text: nx

text: µ

text: −1

text: to

text: a

text: neighboring

text: node,

text: the

text: measurement

text: of

text: the

text: sound

text: at

text: the

text: R

text: (R

text: log

text: µ

text: i

text: µ

text: latter

text: node

text: can

text: be

text: used

text: as

text: side

text: information,

text: thus

text: ﬁtting

text: our

text: I

text: i

text: γ

text: i

text: distributed

text: source

text: coding

text: framework.

text: Another

text: application

text: is

text: in

text: relay

text: networks

text: as

text: discussed

text: in

text: enrxa,nnteyn,

text: naansd.

text: nz

text: are

text: the

text: number

text: of

text: transmitter,

text: tehiegefnovllaolwueisng:of

text: y

text: z

text: x

text: z

text: y

text: z

text: C.

text: Related

text: Work

text: In

text: the

text: special

text: case

text: where

text: nx

text: ny

text: nz

text: the

text: RDF

text: for

text: −1

text: nx

text: µ

text: the

text: problem

text: given

text: by

text: log

text: γi

text: RI.

text: log

text: Σx|−z

text: Σx|yz

text: if

text: Σ

text: D

text: Σ

text: In

text: general,

text: it

text: is

text: not

text: straightforward

text: to

text: generalize

text: the

text: above

text: R(D)

text: D

text: Σx|yz

text: if

text: Dx>yzΣ

text: x

text: z

text: results

text: to

text: the

text: case

text: of

text: covariance

text: matrix

text: distortion

text: constraints.

text: x

text: z

text: Indeed,

text: due

text: to

text: the

text: matrix

text: form

text: of

text: the

text: distortion

text: constraint,

text: it

text: does

text: not

text: appear

text: as

text: it

text: is

text: possible

text: to

text: reduce

text: the

text: problem

text: to

text: an

text: equivalent

text: problem

text: of

text: parallel

text: scalar

text: sources.

text: where

text: D

text: is

text: the

text: scalar

text: distortion

text: constraint,

text: and

text: Σ

text: and

text: Σ

text: are

text: conditional

text: variances

text: of

text: scalar

text: random

text: variabxlez

text: x.

text: x

text: yz

text: In

text: the

text: RDF

text: for

text: was

text: recently

text: found

text: for

text: the

text: somewhat

text: restrictive

text: case

text: where

text: n

text: n

text: n

text: and

text: C

text: in

text: is

text: invertible,

text: For

text: the

text: vector

text: case,

text: the

text: authors

text: in

text: solved

text: the

text: prob-

text: and

text: the

text: distortion

text: consxtraintysatisﬁzes

text: Σ

text: D

text: Σ

text: lem

text: for

text: the

text: mean-squared

text: error

text: distortion

text: constraint;

text: i.e.

text: for

text: Under

text: these

text: assumptions,

text: DF

text: was

text: be:

text: x

text: z

text: problem

text: with

text: the

text: distortion

text: constraint

text: replaced

text: by:

text: tr

text: E

text: (x

text: xˆ)

text: (x

text: xˆ)T

text: n

text: D.

text: R

text: (D)

text: log

text: Σx|z−

text: Σx|yz

text: x

text: D

text: Σ

text: x

text: yz

text: This

text: is

text: similar

text: to

text: a

text: case

text: where

text: in

text: only

text: the

text: sum

text: of

text: the

text: Although

text: under

text: the

text: above

text: assumptions

text: the

text: problem

text: is

text: diagonal

text: elements

text: of

text: the

text: distortion

text: and

text: error

text: matrices

text: are

text: manageable

text: to

text: solve,

text: it

text: is

text: a

text: quite

text: restricted

text: case.

text: In

text: this

text: paper,

text: of

text: interest.

text: Thus,

text: in

text: this

text: particular

text: case,

text: the

text: vector

text: Gaussian

text: we

text: consider

text: the

text: most

text: general

text: case

text: with

text: Σ

text: D

text: and

text: x

text: yz

text: problem

text: can

text: be

text: treated

text: as

text: parallel

text: scalar

text: problems,

text: leading

text: without

text: the

text: above

text: assumptions,

text: and

text: establish

text: a

text: lower

text: bound

text: to

text: well-known

text: water-ﬁlling

text: interpretations.

text: The

text: RDF

text: for

text: this

text: and

text: an

text: upper

text: bound

text: on

text: the

text: RDF,

text: which

text: in

text: general

text: do

text: not

text: problem

text: when

text: tr(Σ

text: n

text: D

text: tr(Σ

text: was

text: shown

text: in

text: coincide.

text: Then

text: we

text: consider

text: some

text: special

text: cases

text: for

text: which

text: the

text: x

text: yz

text: x

text: x

text: z

text: to

text: be:

text: two

text: bounds

text: coincide,

text: giving

text: the

text: exact

text: RDF.

text: We

text: will

text: show

text: that

text: and

text: could

text: be

text: derived

text: as

text: special

text: cases

text: of

text: our

text: results.

text: In

text: R(D)

text: nx

text: log

text: λi

text: caonudldz

text: aalrseonboeisdyevrievresdionfrsoomf

text: λ

text: our

text: results.

text: We

text: will

text: also

text: generalize

text: to

text: the

text: case

text: that

text: no

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: THE DENSITY OF SETS AVOIDING DISTANCE 1 IN EUCLIDEAN SPACE 15 obtained by adding a non negativity constraint on the matrix variables, see Remark 5.1) represents an easy way to tighten it. Indeed, one can see that ϑ(J(n, w, i)) = (cid:48) ϑ (J(n, w, i)) only if (20) Z (i) = min Z (j) k0 ∈ k0 j [w] where k satisﬁes Z (i) = min ∈ Z (i). It turns out that (20) is not always 0 k0 (cid:48) k [w] k fulﬁlled and in these cases ϑ (J(n, w, i)) < ϑ(J(n, w, i)). A more serious improvement is provided by semideﬁnite programming follow- ing [27, (67)] where constant weight codes with given minimal distance are con- sidered. In order to apply this framework to our setting, we only need to change the range of avoided Hamming distances in [27, (65-iv)]. Table 1 displays the numerical values of the three bounds for certain parame- ters (n, w, i), selected either because they allow for Frankl and Wilson bound, or R because they give the best upper bound for m ( n) that we could achieve. For 1 most of these parameters, the semideﬁnite programming bound turns to be the best one and is signiﬁcantly better than the theta number. It would be of course very interesting to understand the asymptotic behavior of this bound when n grows to ∞ + , unfortunately this problem seems to be out of reach to date. The computation of the semideﬁnite programming bound was performed on the NEOS website (http://www.neos-server.org/neos/) with the solver SDPA [34] and double checked with SDPT3 version 4.0-beta [32]. The 600-cell is a regular polytope of dimension 4 with 120 vertices: the six- ± ± ± ± ± teen points ( 1/2, 1/2, 1/2, 1/2), the eight permutations of ( 1, 0, 0, 0) and ± ± ± the 96 poin√ts that are even permutations of (0, 1/(2φ), 1/2, φ/2), where φ = (1 + 5)/2.√If d is the dis√tance between two non antipodal vertices, we ∈ { ± ± } have d2 (5 5)/2, 3, (3 5)/2, 2, 1 . Each value of d gives raise to a graph connecting the vertices that are at distance d apart; these graphs, after rescal- ing so that the edges have length 1, lie on the sphere of radius r = 1/d. Their independence numbers ar√e respect√ively equal to: 39, 26, 24, 26, 20. We note that → − applying the conjugation 5 5 will obviously not change the independence number. Among these g√raphs, the best result in dimension 4, recorded in Table 2, was obtained with d = 3. It turned out that the same graph gave the best result we could achieve in dimensions 5 and 6. R ± The root system E is the following set of 240 points in 8: the points (( 1)2, 06) 8 ± and all their permutations, and the points (( 1/2)8) with an even number of minus signs.√The d√istances between two non antipodal points take three different values: (cid:112) d = 2, 2, 6. The u√nit distance subgraph associated to a value of d lies on a sphere of radius r = 2/d and has an independence number equal respectively to 16, 16, 36. The one with the smallest radius r = 1/3 gives the best bound in dimension 8 as well as in dimensions 9, 10, and 11 (in these dimensions we have compared with Johnson graphs). ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: THE

label: paragraph

text: DENSITY

text: OF

text: SETS

text: AVOIDING

text: DISTANCE

text: IN

text: EUCLIDEAN

text: SPACE

text: obtained

text: by

text: adding

text: a

text: non

text: negativity

text: constraint

text: on

text: the

text: matrix

text: variables,

text: see

text: Remark

text: represents

text: an

text: easy

text: way

text: to

text: tighten

text: it.

text: Indeed,

text: one

text: can

text: see

text: that

text: ϑ(J(n,

text: w,

text: i))

text: ϑ

text: (J(n,

text: w,

text: i))

text: only

text: if

label: equation

text: Z

text: (i)

text: min

text: Z

text: (j)

text: j

text: [w]

text: where

text: k

text: satisﬁes

text: Z

text: (i)

text: min

text: Z

text: (i).

text: It

text: turns

text: out

text: that

text: is

text: not

text: always

text: k

text: [w]

text: k

text: fulﬁlled

text: and

text: in

text: these

text: cases

text: ϑ

text: (J(n,

text: w,

text: i))

text: ϑ(J(n,

text: w,

text: i)).

text: A

text: more

text: serious

text: improvement

text: is

text: provided

text: by

text: semideﬁnite

text: programming

text: follow-

text: ing

text: where

text: constant

text: weight

text: codes

text: with

text: given

text: minimal

text: distance

text: are

text: con-

text: sidered.

text: In

text: order

text: to

text: apply

text: this

text: framework

text: to

text: our

text: setting,

text: we

text: only

text: need

text: to

text: change

text: the

text: range

text: of

text: avoided

text: Hamming

text: distances

text: in

text: Table

text: displays

text: the

text: numerical

text: values

text: of

text: the

text: three

text: bounds

text: for

text: certain

text: parame-

text: ters

text: (n,

text: w,

text: i),

text: selected

text: either

text: because

text: they

text: allow

text: for

text: Frankl

text: and

text: Wilson

text: bound,

text: or

text: R

text: because

text: they

text: give

text: the

text: best

text: upper

text: bound

text: for

text: m

text: n)

text: that

text: we

text: could

text: achieve.

text: For

text: most

text: of

text: these

text: parameters,

text: the

text: semideﬁnite

text: programming

text: bound

text: turns

text: to

text: be

text: the

text: best

text: one

text: and

text: is

text: signiﬁcantly

text: better

text: than

text: the

text: theta

text: number.

text: It

text: would

text: be

text: of

text: course

text: very

text: interesting

text: to

text: understand

text: the

text: asymptotic

text: behavior

text: of

text: this

text: bound

text: when

text: n

text: grows

text: to

text: unfortunately

text: this

text: problem

text: seems

text: to

text: be

text: out

text: of

text: reach

text: to

text: date.

text: The

text: computation

text: of

text: the

text: semideﬁnite

text: programming

text: bound

text: was

text: performed

text: on

text: the

text: NEOS

text: website

text: with

text: the

text: solver

text: SDPA

text: and

text: double

text: checked

text: with

text: version

text: The

text: is

text: a

text: regular

text: polytope

text: of

text: dimension

text: with

text: vertices:

text: the

text: six-

text: teen

text: points

text: the

text: eight

text: permutations

text: of

text: and

text: the

text: poin√ts

text: that

text: are

text: even

text: permutations

text: of

text: where

text: φ

text: d

text: is

text: the

text: dis√tance

text: between

text: two

text: non

text: antipodal

text: vertices,

text: we

text: have

text: Each

text: value

text: of

text: d

text: gives

text: raise

text: to

text: a

text: graph

text: connecting

text: the

text: vertices

text: that

text: are

text: at

text: distance

text: d

text: apart;

text: these

text: graphs,

text: after

text: rescal-

text: ing

text: so

text: that

text: the

text: edges

text: have

text: length

text: lie

text: on

text: the

text: sphere

text: of

text: radius

text: r

text: Their

text: independence

text: numbers

text: ar√e

text: respect√ively

text: equal

text: to:

text: We

text: note

text: that

text: applying

text: the

text: conjugation

text: will

text: obviously

text: not

text: change

text: the

text: independence

text: number.

text: Among

text: these

text: g√raphs,

text: the

text: best

text: result

text: in

text: dimension

text: recorded

text: in

text: Table

text: was

text: obtained

text: with

text: d

text: It

text: turned

text: out

text: that

text: the

text: same

text: graph

text: gave

text: the

text: best

text: result

text: we

text: could

text: achieve

text: in

text: dimensions

text: and

text: R

text: The

text: root

text: system

text: E

text: is

text: the

text: following

text: set

text: of

text: points

text: in

text: the

text: points

text: and

text: all

text: their

text: permutations,

text: and

text: the

text: points

text: with

text: an

text: even

text: number

text: of

text: minus

text: signs.√The

text: d√istances

text: between

text: two

text: non

text: antipodal

text: points

text: take

text: three

text: different

text: values:

text: d

text: The

text: u√nit

text: distance

text: subgraph

text: associated

text: to

text: a

text: value

text: of

text: d

text: lies

text: on

text: a

text: sphere

text: of

text: radius

text: r

text: and

text: has

text: an

text: independence

text: number

text: equal

text: respectively

text: to

text: The

text: one

text: with

text: the

text: smallest

text: radius

text: r

text: gives

text: the

text: best

text: bound

text: in

text: dimension

text: as

text: well

text: as

text: in

text: dimensions

text: and

text: (in

text: these

text: dimensions

text: we

text: have

text: compared

text: with

text: Johnson

text: graphs).

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: THE DENSITY OF SETS AVOIDING DISTANCE 1 IN EUCLIDEAN SPACE 21 (cid:8) (cid:82) G ∈ C ∈ ϑ ( ) = sup f(x)dx : f (X), f(γx) = f(x) (γ Γ ), G X (cid:23) p f 0, (cid:82) (cid:9) (22) f(p) = 1, { } ∈ f(x) = 0 ( x, p E) ≤ f(v)dλ(v) α (G) . V λ G Assuming α ( ) > 0, we have X G ≤ G α ( ) ϑ ( ). X G ⊂ (cid:90) Proof. Let A X be a Borel measurable independent set of positive measure. We introduce 1 f (x) := 1 (γx)1 (γp)dγ. A A A vol (A) X Γ ∈ R This function f X will play the role of the matrix S that occurred in the A G ≤ G A proof of the inequality α( ) ϑ( ) for ﬁnite graphs. We claim that f satisﬁes G A the constraints required by the program deﬁning ϑ ( ). Indeed, being the convo- G lution over Γ of two bounded functions, f is continuous (see [21, (2.39)]). The A other conditions (numbered (i) to (v) in order of appearance in (22)) are easily ob- tained, applying Fubini’s theorem to swap integrals and the invariance by left and right multiplication of the Haar measure on Γ. We skip the details for (i) and (iii). { } ∈ { } ∈ Condition (iv) holds because on one hand, if x, p E, also γx, γp E, and G on the other hand, A is an independent set of , so 1 (γx)1 (γp) = 0. (cid:23) A A Let us check (ii), i.e. f 0: thanks to(cid:90) the right invariance of the Haar measure, A we have − 1 (cid:90) − f (γ 1γ p) = 1 (γγ 1γ p)1 (γp)dγ A j i vol (A) A j i A X Γ 1 = 1 (γγ p)1 (γγ p)dγ. A i A j vol (A) X Γ − ∈ So, the matrix with coefﬁcients f (γ 1γ p) is symmetric. Moreover, for (x , . . . , x ) Rk, (cid:88) A j i (cid:90) (cid:16) (cid:88) (cid:17) 1 k k − 1 2 ≥ x x f (γ 1γ p) = x 1 (γγ p) dγ 0. ≤ ≤ i j A j i volX(A) Γ i A i 1 i,j k i=1 In order to veri(cid:90)fy (v), we remark that − ∩ ≤ (23) 1 (γv)dλ(v) = λ((γ 1A) V ) α (G). A λ V ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: THE

text: DENSITY

text: OF

text: SETS

text: AVOIDING

text: DISTANCE

text: IN

text: EUCLIDEAN

text: SPACE

text: G

text: C

text: ϑ

text: sup

text: f(x)dx

text: f

text: (X),

text: f(γx)

text: f(x)

text: (γ

text: Γ

text: G

text: X

text: p

text: f

text: f(p)

text: f(x)

text: x,

text: p

text: E)

text: f(v)dλ(v)

text: α

text: (G)

text: V

text: λ

text: G

text: Assuming

text: α

text: we

text: have

text: X

text: G

text: G

text: α

text: ϑ

text: X

text: G

text: Proof.

text: Let

text: A

text: X

text: be

text: a

text: Borel

text: measurable

text: independent

text: set

text: of

text: positive

text: measure.

text: We

text: introduce

text: f

text: (x)

text: (γp)dγ.

text: A

text: A

text: A

text: vol

text: (A)

text: X

text: Γ

text: R

text: This

text: function

text: f

text: X

text: will

text: play

text: the

text: role

text: of

text: the

text: matrix

text: S

text: that

text: occurred

text: in

text: the

text: A

text: G

text: G

text: A

text: proof

text: of

text: the

text: inequality

text: α(

text: ϑ(

text: for

text: ﬁnite

text: graphs.

text: We

text: claim

text: that

text: f

text: satisﬁes

text: G

text: A

text: the

text: constraints

text: required

text: by

text: the

text: program

text: deﬁning

text: ϑ

text: Indeed,

text: being

text: the

text: convo-

text: G

text: lution

text: over

text: Γ

text: of

text: two

text: bounded

text: functions,

text: f

text: is

text: continuous

text: (see

text: The

text: A

text: other

text: conditions

text: (numbered

text: (i)

text: to

text: (v)

text: in

text: order

text: of

text: appearance

text: in

text: are

text: easily

text: ob-

text: tained,

text: applying

text: Fubini’s

text: theorem

text: to

text: swap

text: integrals

text: and

text: the

text: invariance

text: by

text: left

text: and

text: right

text: multiplication

text: of

text: the

text: Haar

text: measure

text: on

text: Γ.

text: We

text: skip

text: the

text: details

text: for

text: (i)

text: and

text: (iii).

text: Condition

text: (iv)

text: holds

text: because

text: on

text: one

text: hand,

text: if

text: x,

text: p

text: E,

text: also

text: γx,

text: γp

text: E,

text: and

text: G

text: on

text: the

text: other

text: hand,

text: A

text: is

text: an

text: independent

text: set

text: of

text: so

text: (γp)

text: A

text: A

text: Let

text: us

text: check

text: (ii),

text: i.e.

text: f

text: thanks

text: the

text: right

text: invariance

text: of

text: the

text: Haar

text: measure,

text: A

text: we

text: have

text: f

text: (γ

text: 1γ

text: p)

text: (γγ

text: 1γ

text: (γp)dγ

text: A

text: j

text: i

text: vol

text: (A)

text: A

text: j

text: i

text: A

text: X

text: Γ

text: (γγ

text: (γγ

text: p)dγ.

text: A

text: i

text: A

text: j

text: vol

text: (A)

text: X

text: Γ

text: So,

text: the

text: matrix

text: with

text: coefﬁcients

text: f

text: (γ

text: 1γ

text: p)

text: is

text: symmetric.

text: Moreover,

text: for

text: (x

text: x

text: Rk,

text: A

text: j

text: i

text: k

text: k

text: x

text: x

text: f

text: (γ

text: 1γ

text: p)

text: x

text: (γγ

text: p)

text: dγ

text: i

text: j

text: A

text: j

text: i

text: volX(A)

text: Γ

text: i

text: A

text: i

text: i,j

text: k

text: In

text: order

text: to

text: (v),

text: we

text: remark

text: that

text: (γv)dλ(v)

text: λ((γ

text: V

text: α

text: (G).

text: A

text: λ

text: V

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: THE DENSITY OF SETS AVOIDING DISTANCE 1 IN EUCLIDEAN SPACE 23 G R Our notations suggest an analogy between ϑ ( ) as deﬁned in (22) and ϑ ( n) G G as introduced in Theorem 2.2. This analogy will be more transparent from the G expression of the dual program of ϑ ( ). Here we apply the duality theory of G conic linear programs in locally convex topological vector spaces for which we C refer to [7, Chapter IV]. The dual space of the space (X) of real valued continuous C functions on X, i.e. the space of continuous linear forms on (X) equipped with M (cid:82) the topology deﬁned by the supremum norm, is the space (X) of signed regular measures on X (it follows from Riesz representation theorem, see [24, Theorem ∈ M (cid:23) ≥ 6.19]). For µ (X), the notation µ 0 (µ positive deﬁnite) stands for fdµ ∈ C 0 for all f (X), f being positive deﬁnite. The support of µ is denoted by G supp(µ)(cid:8). The dual program of ϑ ( ) in the sense of [7, Chapter 4, section 6] G becomes: α (G) ∈ M ⊂ { ∈(cid:9) { } ∈ } inf z + z λ : µ (X), supp(µ) x X : x, p E 0 2 λ(V ) ≥ z 0 2 − (cid:23) z δ + µ + z λ dx 0 0 p 2 λ(V ) G We recall that weak duality holds, i.e. that ϑ ( ) is upper bounded by the optimal G value of its dual program (see [7, Theorem 6.2]). Let us go back to the inequality (23). If we integrate it over Γ, and then take the G supremum over the independent sets of , we obtain G ≤ α (G) λ α ( ) . X λ(V ) G In particular, if is a ﬁnite graph and λ is the counting measure, the above inequal- ity becomes G α( ) ≤ α(G) (24) | | | | . X V We recover a standard inequality that has proved to be useful in several in- stances, in particular if one has a special hint on G. For example, in coding theory it is applied to relate the sizes of codes in Hamming and Johnson spaces respec- tively, following Elias and Bassalygo principle (see e.g. [18]). Also, Larman and Rogers inequality (2) can be seen as an analogue of (24) for the unit distance graph. 6. OPEN PROBLEMS We present here a few questions that we believe would be worth to look at. Some of them have already been mentioned previously. (1) There are several possible variants in the way we apply Theorem 2.2 to ﬁnd R upper bounds for m ( n). There is no reason to restrict to graphs that em- 1 bed in a sphere centered at 0n as we do, and also several subgraphs could ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: THE

text: DENSITY

text: OF

text: SETS

text: AVOIDING

text: DISTANCE

text: IN

text: EUCLIDEAN

text: SPACE

text: G

text: R

text: Our

text: notations

text: suggest

text: an

text: analogy

text: between

text: ϑ

text: as

text: deﬁned

text: in

text: and

text: ϑ

text: n)

text: G

text: G

text: as

text: introduced

text: in

text: Theorem

text: This

text: analogy

text: will

text: be

text: more

text: transparent

text: from

text: the

text: G

text: expression

text: of

text: the

text: dual

text: program

text: of

text: ϑ

text: Here

text: we

text: apply

text: the

text: duality

text: theory

text: of

text: G

text: conic

text: linear

text: programs

text: in

text: locally

text: convex

text: topological

text: vector

text: spaces

text: for

text: which

text: we

text: C

text: refer

text: to

text: Chapter

text: IV].

text: The

text: dual

text: space

text: of

text: the

text: space

text: (X)

text: of

text: real

text: valued

text: continuous

text: C

text: functions

text: on

text: X,

text: i.e.

text: the

text: space

text: of

text: continuous

text: linear

text: forms

text: on

text: (X)

text: equipped

text: with

text: M

text: the

text: topology

text: deﬁned

text: by

text: the

text: supremum

text: norm,

text: is

text: the

text: space

text: (X)

text: of

text: signed

text: regular

text: measures

text: on

text: X

text: (it

text: follows

text: from

text: Riesz

text: representation

text: theorem,

text: see

text: Theorem

text: M

text: For

text: µ

text: (X),

text: the

text: notation

text: µ

text: (µ

text: positive

text: deﬁnite)

text: stands

text: for

text: fdµ

text: C

text: for

text: all

text: f

text: (X),

text: f

text: being

text: positive

text: deﬁnite.

text: The

text: support

text: of

text: µ

text: is

text: denoted

text: by

text: G

text: The

text: dual

text: program

text: of

text: ϑ

text: in

text: the

text: sense

text: of

text: Chapter

text: section

text: G

text: becomes:

text: α

text: (G)

text: M

text: inf

text: z

text: z

text: λ

text: µ

text: (X),

text: supp(µ)

text: x

text: X

text: x,

text: p

text: E

text: λ(V

text: z

text: z

text: δ

text: µ

text: z

text: λ

text: dx

text: p

text: λ(V

text: G

text: We

text: recall

text: that

text: weak

text: duality

text: holds,

text: i.e.

text: that

text: ϑ

text: is

text: upper

text: bounded

text: by

text: the

text: optimal

text: G

text: value

text: of

text: its

text: dual

text: program

text: (see

text: Theorem

text: Let

text: us

text: go

text: back

text: to

text: the

text: inequality

text: If

text: we

text: integrate

text: it

text: over

text: Γ,

text: and

text: then

text: take

text: the

text: G

text: supremum

text: over

text: the

text: independent

text: sets

text: of

text: we

text: obtain

text: G

text: α

text: (G)

text: λ

text: α

text: X

text: λ(V

text: G

text: In

text: particular,

text: if

text: is

text: a

text: ﬁnite

text: graph

text: and

text: λ

text: is

text: the

text: counting

text: measure,

text: the

text: above

text: inequal-

text: ity

text: becomes

text: G

text: α(

text: α(G)

text: X

text: V

text: We

text: recover

text: a

text: standard

text: inequality

text: that

text: has

text: proved

text: to

text: be

text: useful

text: in

text: several

text: in-

text: stances,

text: in

text: particular

text: if

text: one

text: has

text: a

text: special

text: hint

text: on

text: G.

text: For

text: example,

text: in

text: coding

text: theory

text: it

text: is

text: applied

text: to

text: relate

text: the

text: sizes

text: of

text: codes

text: in

text: Hamming

text: and

text: Johnson

text: spaces

text: respec-

text: tively,

text: following

text: Elias

text: and

text: Bassalygo

text: principle

text: (see

text: e.g.

text: Also,

text: Larman

text: and

text: Rogers

text: inequality

text: can

text: be

text: seen

text: as

text: an

text: analogue

text: of

text: for

text: the

text: unit

text: distance

text: graph.

text: OPEN

text: PROBLEMS

text: We

text: present

text: here

text: a

text: few

text: questions

text: that

text: we

text: believe

text: would

text: be

text: worth

text: to

text: look

text: at.

text: Some

text: of

text: them

text: have

text: already

text: been

text: mentioned

text: previously.

text: There

text: are

text: several

text: possible

text: variants

text: in

text: the

text: way

text: we

text: apply

text: Theorem

text: to

text: ﬁnd

text: R

text: upper

text: bounds

text: for

text: m

text: n).

text: There

text: is

text: no

text: reason

text: to

text: restrict

text: to

text: graphs

text: that

text: em-

text: bed

text: in

text: a

text: sphere

text: centered

text: at

text: as

text: we

text: do,

text: and

text: also

text: several

text: subgraphs

text: could

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: theshock.Thismeansthereare4wtpairswithone≤particleinsidetheshock.Intotal,for0<t∆/2w

text: (cid:105)(cid:104)(cid:0)(cid:1)−2n2n2nu(t)=(2w)(∆2wt)/L+w4wt/L−−−−2n2(n1)2n1=(4w/L)2∆21wt.(5)

text: (cid:28)For∆/2w<tTallpairswithparticlesonLbothsidesoftheshockhavedisappeared,whilethe

text: particlesinsidetheshockhavetheirpartnersata

text: distancesmallerorequalto∆fromtheshock.Thus

text: thedominantcontributioncomesfrom2∆pairsthat||2n2nhaveu=wwhichgivesu(t)=w2∆/L.

text: ofpairswithashockbetweenthemisthesameas

text: Theﬁnalstepistoaverageoverw=s/2,denoting

text: theprobabilitydensityfunctionfortheshockheight

text: t<0,whilefort>0(cid:28)(cid:29)(cid:90)(cid:0)(cid:1)∆/t2n−−−du(t)12n2n+1=ρ12sP(s)ds.dt0

text: Thisrevealsthenewtypeofanomalyatt=0:(cid:10)(cid:11)(cid:0)(cid:1)(cid:10)(cid:11)−−(cid:0)(cid:1)2n12n2n+1limdu(t)/dt=ρ21s→+t0(cid:10)(cid:11)−−4(2n+1)12n−=21¯(cid:15),(6)n2n1

text: diﬀerentfromthepreviouslysuggested(3).There

text: isnodissipationfort<0;theLagrangianevolution

text: istrulyinviscidwhenviewedbackwardintime.

text: Thefootprintofthisanomalycanalsobeseen(cid:10)(cid:11)inthetwo-particleconservationlawsintheinviscid

text: limit.Following[19],considerconservationlawsof2ntheformuf(∆(t)/∆),where∆(t)isthesep-narationbetweenparticlesattimet.Backwardin

text: Toexploretheanomaliesaroundt=0itisenough(cid:28)≡toconsidertL/vT.Atsuchtimes,rmsLthemaincontributiontothevelocitydiﬀerenceu(t)

text: comesfrompairswhicheitherhaveashockbetween

text: themorhaveonemarkerparticleinsidetheshock.

text: Thesepairshaveavelocitydiﬀerenceoftheorderof(cid:39)v,whiletherestofthepairshaveuv∆/L.rmsrmsWecanthusrestrictouranalysistothevicinityof

text: agenericshock,performingaspatialaverageover

text: pairsfollowedbyanaverageovertheparametersof

text: theshock[15].Webeginwithasingleshockwith

text: prescribedparametersandcalculatethespatialav-

text: 2neragewhichwedenotebyu(t).Sincethemoments

text: ofthevelocitydiﬀerenceareGalileaninvariant,we

text: maychoosethesymmetricEulerianvelocityproﬁle

text: thatisastandingshock:

text: tersarethengivenbythemeanshockdensityρ=

text: domvariablewhosedistributionisinprinciplede-

text: Notethat(4)iskeptstationarybyaninﬂuxofpar-

text: ticlesfromtheboundarieswhileintheoriginalprob-

text: lemstationarityofenergyisinsuredbytherandom

text: forcing,actingateachpoint.However,theforcing

text: fortheoriginalproblemhasanonnegligibleeﬀecton

text: thevelocitydiﬀerenceonlyforpairsthatreachsep-

text: arationscomparabletoL.Therearenosuchpairs

text: atthetimesweareconsideringsotheeﬀectofthe

text: forcingcanbeignored.→Inthelimitν0,(4)turnsintoastepfunction−withv=wforx>0andv=wforx<0.Only

text: 2ntwogroupsofpairscontributesigniﬁcantlytou(t)

text: inthislimit:i)thepairswiththeshockinbetween,||whichhaveu=2w,andii)pairswithonepar-

text: ticleinsideandtheotheroutsidetheshock,which||haveu=w.Wethusneedtocountthenumberof

text: eachtypeofpairsattimet,giventhatattimezero

text: pairswerehomogeneouslydistributed.Thetempo-

text: 2nralbehaviorofu(t)canbedividedintoregimes

text: belongingtothreediﬀerenttimeintervals.Attimes

text: shock,allofwhichbelongedtoapairwithparticles

text: onbothsidesoftheshockatt=0.Thus,thenum-−berofsuchpairsisreducedto∆2wt.Then,every

text: particleinsidetheshockattimetbelongstotwo

text: pairs,bothhavingthesecondparticlestilloutside

text: ##LTLine##

font: default

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 1 On Stochastic Geometry Modeling of Cellular Uplink Transmission with Truncated Channel Inversion Power Control Hesham ElSawy and Ekram Hossain Abstract— Using stochastic geometry, we develop a tractable been proven to provide pessimistic bounds on the performance uplink modeling paradigm for outage probability and spectral metrics (e.g., the outage probability and the mean rate) that efﬁciency in both single and multi-tier cellular wireless networks. are as tight as the optimistic bounds provided by the idealized The analysis accounts for per user equipment (UE) power grid-based model for actual cellular networks [1], [2]. Further control as well as the maximum power limitations for UEs. More speciﬁcally, for interference mitigation and robust uplink validations of stochastic geometry-based modeling of cellular communication, each UE is required to control its transmit power networks via PPP can be found in [5]–[7]. such that the average received signal power at its serving base There have been signiﬁcant developments in the stochastic station (BS) is equal to a certain threshold ρo. Due to the limited geometry modeling of cellular wireless networks. However, transmit power, the UEs employ a truncated channel inversion most of the available literature focus on modeling and analysis power control policy with a cutoff threshold of ρ . We show that there exists a transfer point in the uplink systeom performance of downlink transmissions due to its relative simplicity. In that depends on the tuple: BS intensity (λ), maximum transmit a multi-tier cellular network, if the users associate to the power of UEs (P ), and ρ . That is, when P is a tight operational BSs in the downlink based on their average received signal u o u constraint with respect to [w.r.t.] λ and ρo, the uplink outage strength, the average useful signal power received at each probability and spectral efﬁciency highly depend on the values user equipment (UE) from its corresponding BS will be of λ and ρ . In this case, there exists an optimal cutoff threshold ρ∗, which odepends on the system parameters, that minimizes strictly greater than the average interference power from any o the outage probability. On the other hand, when P is not a individual interfering BS. Therefore, power control is not u binding operational constraint w.r.t. λ and ρ , the uplink outage crucial1 for the network operation, and hence, power control o probability and spectral efﬁciency become independent of λ and is ignored in most of the stochastic geometry models on ρ . We obtain approximate yet accurate simple expressions for o downlink cellular networks and it is generally assumed that outage probability and spectral efﬁciency which reduce to closed- forms in some special cases. all the BSs in the same tier transmit with equal power [1]–[3], Keywords:- Multi-tier cellular networks, uplink communi- [9]–[14]. In contrast, uplink analysis is quite more involved cation, power control, truncated channel inversion, stochastic due to the following reasons: geometry. • Per user power control: in the uplink, due to the random cell sizes, an interfering UE in a neighboring I. INTRODUCTION cell can be much closer to a BS than its tagged UE (cf. Fig. 1). Therefore, power control per UE is crucial Due to the variations of the capacity demand across the for basic uplink operation in order to mitigate the inter- service areas (e.g., downtowns, residential and suburbans cell interference. As will be shown later, per UE power areas, etc.) as well as the deployment of multi-tier cellular control introduces a new source of randomness to the networks (i.e., cellular networks consisting of different types uplink system model which makes the uplink analysis of base stations [BSs] such as macro, micro, pico, and femto more involved. BSs), the practical cellular infrastructure deviates from the • Correlation among interferers: orthogonal channel as- well-known regular grid topology. Instead, it is better modeled signment per BS ensures no channel reuse in the same by a randomized topology with uncertainties in the locations of Voronoi2 cell. That is, given that a UE is transmitting in the BSs [1], [2]. Therefore, modeling and analysis of cellular the uplink on a certain channel, this channel cannot be networks based on stochastic geometry has recently received reused within the coverage of its serving BS, and hence, much attention due to its tractability and accuracy [3]. Stochas- the locations of the UEs using the same uplink channel tic geometry is a very powerful tool to deal with networks with are correlated. random topologies. Stochastic geometry abstracts the cellular network topology to a convenient point process to facilitate its Compared to the downlink, only few efforts were invested modeling and analysis. The Poisson point process (PPP) is an to understand and model the uplink transmissions in cellular appealing abstraction for the cellular network topology due to its simplicity and tractability [3], [4]. Furthermore, the PPP has 1Indeed power control is important in downlink to enhance the network performance (see [8]) but not crucial for the basic network operation due to The authors are with the Department of Electrical and Computer the inherent interference protection introduced by the association criterion. Engineering, University of Manitoba, Winnipeg, Canada (emails: umel- 2A Voronoi tessellation is the planar graph constructed by perpendicular sawy@cc.umanitoba.ca, Ekram.Hossain@umanitoba.ca). This work was sup- lines bisecting the distances between the points of a point process. The ported in part by an NSERC Strategic Grant (STPGP 430285), and in part by Voronoi cells constructed from a point process representing the BS locations a scholarship from TRTech, Winnipeg, Manitoba, Canada. correspond to the coverage regions of the BSs.

text: On

label: title

text: Stochastic

text: Geometry

text: Modeling

text: of

text: Cellular

text: Uplink

text: Transmission

text: with

text: Truncated

text: Channel

text: Inversion

text: Power

text: Control

text: Hesham

label: author

text: ElSawy

text: and

text: Ekram

text: Hossain

text: Abstract—

text: Using

label: abstract

text: stochastic

text: geometry,

text: we

text: develop

text: a

text: tractable

text: been

text: proven

text: to

text: provide

text: pessimistic

text: bounds

text: on

text: the

text: performance

text: uplink

text: modeling

text: paradigm

text: for

text: outage

text: probability

text: and

text: spectral

text: metrics

text: (e.g.,

text: the

text: outage

text: probability

text: and

text: the

text: mean

text: rate)

text: that

text: efﬁciency

text: in

text: both

text: single

text: and

text: multi-tier

text: cellular

text: wireless

text: networks.

text: are

text: as

text: tight

text: as

text: the

text: optimistic

text: bounds

text: provided

text: by

text: the

text: idealized

text: The

text: analysis

text: accounts

text: for

text: per

text: user

text: equipment

text: (UE)

text: power

text: grid-based

text: model

text: for

text: actual

text: cellular

text: networks

text: Further

text: control

text: as

text: well

text: as

text: the

text: maximum

text: power

text: limitations

text: for

text: UEs.

text: More

text: speciﬁcally,

text: for

text: interference

text: mitigation

text: and

text: robust

text: uplink

text: validations

text: of

text: stochastic

text: geometry-based

text: modeling

text: of

text: cellular

text: communication,

text: each

text: UE

text: is

text: required

text: to

text: control

text: its

text: transmit

text: power

text: networks

text: via

text: PPP

text: can

text: be

text: found

text: in

text: such

text: that

text: the

text: average

text: received

text: signal

text: power

text: at

text: its

text: serving

text: base

text: There

text: have

text: been

text: signiﬁcant

text: developments

text: in

text: the

text: stochastic

text: station

text: (BS)

text: is

text: equal

text: to

text: a

text: certain

text: threshold

text: ρo.

text: Due

text: to

text: the

text: limited

text: geometry

text: modeling

text: of

text: cellular

text: wireless

text: networks.

text: However,

text: transmit

text: power,

text: the

text: UEs

text: employ

text: a

text: truncated

text: channel

text: inversion

text: most

text: of

text: the

text: available

text: literature

text: focus

text: on

text: modeling

text: and

text: analysis

text: power

text: control

text: policy

text: with

text: a

text: cutoff

text: threshold

text: of

text: ρ

text: We

text: show

text: that

text: there

text: exists

text: a

text: transfer

text: point

text: in

text: the

text: uplink

text: systeom

text: performance

text: of

text: downlink

text: transmissions

text: due

text: to

text: its

text: relative

text: simplicity.

text: In

text: that

text: depends

text: on

text: the

text: tuple:

text: BS

text: intensity

text: (λ),

text: maximum

text: transmit

text: a

text: multi-tier

text: cellular

text: network,

text: if

text: the

text: users

text: associate

text: to

text: the

text: power

text: of

text: UEs

text: (P

text: and

text: ρ

text: That

text: is,

text: when

text: P

text: is

text: a

text: tight

text: operational

text: BSs

text: in

text: the

text: downlink

text: based

text: on

text: their

text: average

text: received

text: signal

text: u

text: o

text: u

text: constraint

text: with

text: respect

text: to

text: [w.r.t.]

text: λ

text: and

text: ρo,

text: the

text: uplink

text: outage

text: strength,

text: the

text: average

text: useful

text: signal

text: power

text: received

text: at

text: each

text: probability

text: and

text: spectral

text: efﬁciency

text: highly

text: depend

text: on

text: the

text: values

text: user

text: equipment

text: (UE)

text: from

text: its

text: corresponding

text: BS

text: will

text: be

text: of

text: λ

text: and

text: ρ

text: In

text: this

text: case,

text: there

text: exists

text: an

text: optimal

text: cutoff

text: threshold

text: ρ∗,

text: which

text: odepends

text: on

text: the

text: system

text: parameters,

text: that

text: minimizes

text: strictly

text: greater

text: than

text: the

text: average

text: interference

text: power

text: from

text: any

text: o

text: the

text: outage

text: probability.

text: On

text: the

text: other

text: hand,

text: when

text: P

text: is

text: not

text: a

text: individual

text: interfering

text: BS.

text: Therefore,

text: power

text: control

text: is

text: not

text: u

text: binding

text: operational

text: constraint

text: w.r.t.

text: λ

text: and

text: ρ

text: the

text: uplink

text: outage

text: for

text: the

text: network

text: operation,

text: and

text: hence,

text: power

text: control

text: o

text: probability

text: and

text: spectral

text: efﬁciency

text: become

text: independent

text: of

text: λ

text: and

text: is

text: ignored

text: in

text: most

text: of

text: the

text: stochastic

text: geometry

text: models

text: on

text: ρ

text: We

text: obtain

text: approximate

text: yet

text: accurate

text: simple

text: expressions

text: for

text: o

text: downlink

text: cellular

text: networks

text: and

text: it

text: is

text: generally

text: assumed

text: that

text: outage

text: probability

text: and

text: spectral

text: efﬁciency

text: which

text: reduce

text: to

text: closed-

text: forms

text: in

text: some

text: special

text: cases.

text: all

text: the

text: BSs

text: in

text: the

text: same

text: tier

text: transmit

text: with

text: equal

text: power

text: Keywords:-

text: Multi-tier

text: cellular

text: networks,

text: uplink

text: communi-

text: In

text: contrast,

text: uplink

text: analysis

text: is

text: quite

text: more

text: involved

text: cation,

text: power

text: control,

text: truncated

text: channel

text: inversion,

text: stochastic

text: due

text: to

text: the

text: following

text: reasons:

text: geometry.

text: Per

text: user

text: power

text: control:

text: in

text: the

text: uplink,

text: due

text: to

text: the

text: random

text: cell

text: sizes,

text: an

text: interfering

text: UE

text: in

text: a

text: neighboring

text: I.

text: INTRODUCTION

text: cell

text: can

text: be

text: much

text: closer

text: to

text: a

text: BS

text: than

text: its

text: tagged

text: UE

text: (cf.

text: Fig.

text: Therefore,

text: power

text: control

text: per

text: UE

text: is

text: crucial

text: Due

text: to

text: the

text: variations

text: of

text: the

text: capacity

text: demand

text: across

text: the

text: for

text: basic

text: uplink

text: operation

text: in

text: order

text: to

text: mitigate

text: the

text: inter-

text: service

text: areas

text: (e.g.,

text: downtowns,

text: residential

text: and

text: suburbans

text: cell

text: interference.

text: As

text: will

text: be

text: shown

text: later,

text: per

text: UE

text: power

text: areas,

text: etc.)

text: as

text: well

text: as

text: the

text: deployment

text: of

text: multi-tier

text: cellular

text: control

text: introduces

text: a

text: new

text: source

text: of

text: randomness

text: to

text: the

text: networks

text: (i.e.,

text: cellular

text: networks

text: consisting

text: of

text: different

text: types

text: uplink

text: system

text: model

text: which

text: makes

text: the

text: uplink

text: analysis

text: of

text: base

text: stations

text: [BSs]

text: such

text: as

text: macro,

text: micro,

text: pico,

text: and

text: femto

text: more

text: involved.

text: BSs),

text: the

text: practical

text: cellular

text: infrastructure

text: deviates

text: from

text: the

text: Correlation

text: among

text: interferers:

text: orthogonal

text: channel

text: as-

text: well-known

text: regular

text: grid

text: topology.

text: Instead,

text: it

text: is

text: better

text: modeled

text: signment

text: per

text: BS

text: ensures

text: no

text: channel

text: reuse

text: in

text: the

text: same

text: by

text: a

text: randomized

text: topology

text: with

text: uncertainties

text: in

text: the

text: locations

text: of

text: cell.

text: That

text: is,

text: given

text: that

text: a

text: UE

text: is

text: transmitting

text: in

text: the

text: BSs

text: Therefore,

text: modeling

text: and

text: analysis

text: of

text: cellular

text: the

text: uplink

text: on

text: a

text: certain

text: channel,

text: this

text: channel

text: cannot

text: be

text: networks

text: based

text: on

text: stochastic

text: geometry

text: has

text: recently

text: received

text: reused

text: within

text: the

text: coverage

text: of

text: its

text: serving

text: BS,

text: and

text: hence,

text: much

text: attention

text: due

text: to

text: its

text: tractability

text: and

text: accuracy

text: Stochas-

text: the

text: locations

text: of

text: the

text: UEs

text: using

text: the

text: same

text: uplink

text: channel

text: tic

text: geometry

text: is

text: a

text: very

text: powerful

text: tool

text: to

text: deal

text: with

text: networks

text: with

text: are

text: correlated.

text: random

text: topologies.

text: Stochastic

text: geometry

text: abstracts

text: the

text: cellular

text: network

text: topology

text: to

text: a

text: convenient

text: point

text: process

text: to

text: facilitate

text: its

text: Compared

text: to

text: the

text: downlink,

text: only

text: few

text: efforts

text: were

text: invested

text: modeling

text: and

text: analysis.

text: The

text: Poisson

text: point

text: process

text: (PPP)

text: is

text: an

text: to

text: understand

text: and

text: model

text: the

text: uplink

text: transmissions

text: in

text: cellular

text: appealing

text: abstraction

text: for

text: the

text: cellular

text: network

text: topology

text: due

text: to

text: its

text: simplicity

text: and

text: tractability

text: Furthermore,

text: the

text: PPP

text: has

text: power

text: control

text: is

text: important

text: in

text: downlink

text: to

text: enhance

text: the

text: network

text: performance

text: (see

text: but

text: not

text: crucial

text: for

text: the

text: basic

text: network

text: operation

text: due

text: to

text: The

text: authors

text: are

text: with

text: the

text: Department

text: of

text: Electrical

text: and

text: Computer

text: the

text: inherent

text: interference

text: protection

text: introduced

text: by

text: the

text: association

text: criterion.

text: Engineering,

text: University

text: of

text: Manitoba,

text: Winnipeg,

text: Canada

text: (emails:

text: umel-

text: Voronoi

text: tessellation

text: is

text: the

text: planar

text: graph

text: constructed

text: by

text: perpendicular

text: sawy@cc.umanitoba.ca,

text: Ekram.Hossain@umanitoba.ca).

text: This

text: work

text: was

text: sup-

text: lines

text: bisecting

text: the

text: distances

text: between

text: the

text: points

text: of

text: a

text: point

text: process.

text: The

text: ported

text: in

text: part

text: by

text: an

text: NSERC

text: Strategic

text: Grant

text: (STPGP

text: and

text: in

text: part

text: by

text: Voronoi

text: cells

text: constructed

text: from

text: a

text: point

text: process

text: representing

text: the

text: BS

text: locations

text: a

text: scholarship

text: from

text: TRTech,

text: Winnipeg,

text: Manitoba,

text: Canada.

text: correspond

text: to

text: the

text: coverage

text: regions

text: of

text: the

text: BSs.


text: 11 1 1 λ=1 0.9 0.9 λ=10 λ=100 0.8 0.8 Outage probability 0000000.......−012345679 0λ=1 −80 −70λ=10−60 −5ρo0 (λd=B1m−04)00 −30STTSTTSTTrororoIIIuuuNNNtttaaannnRRRlllccc −oooaaaooouuuttt2uuuiiioootttttt0aaaaaannngggggg oooeeeeeeuuu λλλ λλλttt aaa=== −===ggg 111 1eee11100 0λλλ000 0=== 1110000 Effective spectral efficiency 0000000−.......123456709 0 −80 −70 −60 −50ρo (dBm−4)0 −30 −20 −10 0 − | | Fig. 6. Total outage probability for σ2 = 110 dBm, θ = 1, and S = 1. − U Fig. 8. Effective spectral efﬁciency for σ2 = 110 dBm, = 50, and |S| = 1. λ 1 λ=1 0.9 λ=10 λ=100 0.8 0.35 0.7 Effective spectral efficiency 000000......123456 Expected transmit power (W) 00..00012...55123 −09 0 −80 −70 −60 −50 −40 −30 −20 −10 0 ρo (dBm) 0.05 λλ == 11000 − | | −09 0 −80 −70 −60 −50 −40 −30 −20 −1λ0 = 1 0 Fig. 7. Effective spectral efﬁciency σ2 = 90 dBm and S = 1. ρo (dBm) − ≤ ≤ − of 70 ρ 55 dBm because P induces a non-binding Fig. 9. Expected transmit power in the uplink. o u constraint and the noise power is negligible w.r.t. the value of ρ (case #3 in Section ). On the other hand, when P o u becomes a binding constraint, the effective spectral efﬁciency and differences between the uplink and downlink transmission depends on both the BS intensity and cutoff threshold. This performances. The criticality of the power control is the ﬁrst ﬁgure also shows the existence of an optimal cutoff threshold main difference between the uplink and downlink transmission ∗ ρo which maximizes the effective spectral efﬁciency. performances. While power control enhances the downlink To show the tradeoff introduced by ρo on the effective transmission performance, it is not crucial for the basic spectral efﬁciency more clearly, we plot Fig. 8 for negligible − network operation due to the inherent interference protection noise power σ2 = 110 dBm. This ﬁgure shows that when provided by the user association policy. On the other hand, Pu induces a non-binding constraint, the effective spectral power control is essential for the case of uplink operation to efﬁciency is completely independent of the BS intensity and mitigate potential severe interference caused by the arbitrary cutoff threshold. On the other hand, when Pu induces a close interfering UEs (cf. Fig. 1). binding constraint, the effective spectral efﬁciency depends on The second difference between the uplink and downlink both the BS intensity and the cutoff threshold. operation is the maximum transmit power constraint for the Fig. 9 shows the average transmit power of the UEs vs. the cutoff threshold ρ . As the cutoff threshold ρ increases, UEs. For a single-tier cellular network, the relative values of λ, the UEs are required too transmit at higher powers too invert the Pu, and ρo may lead to a binding maximum transmit power constraint for the uplink operation. In this case, the uplink path-loss and maintain a high threshold ρ at their serving BSs. o performance is highly affected by the intensity of the BSs as Therefore, the average transmit power is non-decreasing in ρ . E o well as the cutoff threshold for power control. On the other Note that the average transmit power saturates at lim [P] = →∞ ρo hand, when the relative values of λ, Pu, and ρo lead to an Pu . uplink operation under non-binding maximum transmit power 3 constraint, the uplink transmission performance is analogous B. Discussions to the downlink transmission performance. More speciﬁcally, In the light of the proposed uplink framework and the the uplink network can be transformed into an equivalent results provided in [1], [2], we highlight the commonalities network where all UEs have a constant transmit power of ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Outage

text: probability

text: oooeeeeeeuuu

text: λλλ

text: λλλttt

text: aaa===

text: −===ggg

text: Effective

text: spectral

text: efficiency

text: Fig.

text: Total

text: outage

text: probability

text: for

text: σ2

text: dBm,

text: θ

text: and

text: S

text: U

text: Fig.

text: Effective

text: spectral

text: efﬁciency

text: for

text: σ2

text: dBm,

text: and

text: |S|

text: λ

text: Effective

text: spectral

text: efficiency

text: Expected

text: transmit

text: power

text: (W)

text: ρo

text: (dBm)

text: λλ

text: −1λ0

text: Fig.

text: Effective

text: spectral

text: efﬁciency

text: σ2

text: dBm

text: and

text: S

text: ρo

text: (dBm)

text: of

text: ρ

text: dBm

text: because

text: P

text: induces

text: a

text: non-binding

text: Fig.

text: Expected

text: transmit

text: power

text: in

text: the

text: uplink.

text: o

text: u

text: constraint

text: and

text: the

text: noise

text: power

text: is

text: negligible

text: w.r.t.

text: the

text: value

text: of

text: ρ

text: (case

text: in

text: Section

text: On

text: the

text: other

text: hand,

text: when

text: P

text: o

text: u

text: becomes

text: a

text: binding

text: constraint,

text: the

text: effective

text: spectral

text: efﬁciency

text: and

text: differences

text: between

text: the

text: uplink

text: and

text: downlink

text: transmission

text: depends

text: on

text: both

text: the

text: BS

text: intensity

text: and

text: cutoff

text: threshold.

text: This

text: performances.

text: The

text: criticality

text: of

text: the

text: power

text: control

text: is

text: the

text: ﬁrst

text: ﬁgure

text: also

text: shows

text: the

text: existence

text: of

text: an

text: optimal

text: cutoff

text: threshold

text: main

text: difference

text: between

text: the

text: uplink

text: and

text: downlink

text: transmission

text: ρo

text: which

text: maximizes

text: the

text: effective

text: spectral

text: efﬁciency.

text: performances.

text: While

text: power

text: control

text: enhances

text: the

text: downlink

text: To

text: show

text: the

text: tradeoff

text: introduced

text: by

text: ρo

text: on

text: the

text: effective

text: transmission

text: performance,

text: it

text: is

text: not

text: crucial

text: for

text: the

text: basic

text: spectral

text: efﬁciency

text: more

text: clearly,

text: we

text: plot

text: Fig.

text: for

text: negligible

text: network

text: operation

text: due

text: to

text: the

text: inherent

text: interference

text: protection

text: noise

text: power

text: σ2

text: dBm.

text: This

text: ﬁgure

text: shows

text: that

text: when

text: provided

text: by

text: the

text: user

text: association

text: policy.

text: On

text: the

text: other

text: hand,

text: Pu

text: induces

text: a

text: non-binding

text: constraint,

text: the

text: effective

text: spectral

text: power

text: control

text: is

text: essential

text: for

text: the

text: case

text: of

text: uplink

text: operation

text: to

text: efﬁciency

text: is

text: completely

text: independent

text: of

text: the

text: BS

text: intensity

text: and

text: mitigate

text: potential

text: severe

text: interference

text: caused

text: by

text: the

text: arbitrary

text: cutoff

text: threshold.

text: On

text: the

text: other

text: hand,

text: when

text: Pu

text: induces

text: a

text: close

text: interfering

text: UEs

text: (cf.

text: Fig.

text: binding

text: constraint,

text: the

text: effective

text: spectral

text: efﬁciency

text: depends

text: on

text: The

text: second

text: difference

text: between

text: the

text: uplink

text: and

text: downlink

text: both

text: the

text: BS

text: intensity

text: and

text: the

text: cutoff

text: threshold.

text: operation

text: is

text: the

text: maximum

text: transmit

text: power

text: constraint

text: for

text: the

text: Fig.

text: shows

text: the

text: average

text: transmit

text: power

text: of

text: the

text: UEs

text: vs.

text: the

text: cutoff

text: threshold

text: ρ

text: As

text: the

text: cutoff

text: threshold

text: ρ

text: increases,

text: UEs.

text: For

text: a

text: single-tier

text: cellular

text: network,

text: the

text: relative

text: values

text: of

text: λ,

text: the

text: UEs

text: are

text: required

text: too

text: transmit

text: at

text: higher

text: powers

text: too

text: invert

text: the

text: Pu,

text: and

text: ρo

text: may

text: lead

text: to

text: a

text: binding

text: maximum

text: transmit

text: power

text: constraint

text: for

text: the

text: uplink

text: operation.

text: In

text: this

text: case,

text: the

text: uplink

text: path-loss

text: and

text: maintain

text: a

text: high

text: threshold

text: ρ

text: at

text: their

text: serving

text: BSs.

text: o

text: performance

text: is

text: highly

text: affected

text: by

text: the

text: intensity

text: of

text: the

text: BSs

text: as

text: Therefore,

text: the

text: average

text: transmit

text: power

text: is

text: non-decreasing

text: in

text: ρ

text: E

text: o

text: well

text: as

text: the

text: cutoff

text: threshold

text: for

text: power

text: control.

text: On

text: the

text: other

text: Note

text: that

text: the

text: average

text: transmit

text: power

text: saturates

text: at

text: lim

text: [P]

text: ρo

text: hand,

text: when

text: the

text: relative

text: values

text: of

text: λ,

text: Pu,

text: and

text: ρo

text: lead

text: to

text: an

text: Pu

text: uplink

text: operation

text: under

text: non-binding

text: maximum

text: transmit

text: power

text: constraint,

text: the

text: uplink

text: transmission

text: performance

text: is

text: analogous

text: B.

text: Discussions

text: to

text: the

text: downlink

text: transmission

text: performance.

text: More

text: speciﬁcally,

text: In

text: the

text: light

text: of

text: the

text: proposed

text: uplink

text: framework

text: and

text: the

text: the

text: uplink

text: network

text: can

text: be

text: transformed

text: into

text: an

text: equivalent

text: results

text: provided

text: in

text: we

text: highlight

text: the

text: commonalities

text: network

text: where

text: all

text: UEs

text: have

text: a

text: constant

text: transmit

text: power

text: of

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 7 the cutoff threshold ρ(k), the distribution of the transmit power o and the spectral efﬁciency reduces to the following: of the active UEs in the uplink in the jth tier is given by   (cid:18) (cid:19) (cid:16) (cid:113) (cid:17) R = (cid:90) ∞ exp −xρσo2 − √1x−γex2−,+ππλλ(cid:114)1 PρPρouou arctan(√x)dx. (10) fPj(x) = η(cid:80)(ρ(o2jπ))Λη2xη2−11−e−eπ−ΛπΛ(cid:18)ρ(oxjρP)(ouj) (cid:19)η2 η2 , 0 ≤ x ≤ Pu 0 In the interference-limiteId case, ρo is assumed to be large of wahUerEe iΛn t=he jtKkh=t1ieλrkc. aTnhbe(cid:18)emoobmtaeinnetsdoafs(cid:16)the t(cid:17)ran(cid:19)smit power enough such that θσ2 << and hence noise can be ignored. (cid:2) (cid:3) In this case, the SINρoR outage reduces to the following simple  2 closed-form: (cid:110) √ √ (cid:111) E Pα = (ρ(oj))αγ α2η + 1, πΛ(cid:18) ρP(ouj(cid:19)) η . (13) Os = 1 − exp − θ arctan( θ) (11) j (πΛ)α2η 1 − e−πΛ ρP(ouj) η2 and the spectral(cid:90)efﬁciency reduces to √ √ ∞ {− } R exp x arctan( x) Proof Since the UEs associate to the BSs based on the average = dx 0 x + 1 uplink link quality, following the superposition theorem of the = 0.77 nat/sec/Hz. (12) PPP [4], the association regions for the BSs form a Voronoi tessellation for a PPP with intensity Λ. Note that, for the uplink Equation (11) gives a closed-form expression for the outage in a multi-tier network, the association regions form a Voronoi probability in its simplest form and (12) shows that the average tessellation rather than a weighted Voronoi tessellation due to rate reduces to a constant value10 in this special case. These the homogenous transmit powers of the UEs. The rest of the equations clearly show that when P is not a binding constraint proof follows the same steps as in Appendix . u and the interference is much larger than the noise, both the SINR outage and the spectral efﬁciency are independent of the The truncation outage probabil(cid:18)ity at(cid:19)the jth tier is given by cutoff threshold as well as the BS intensity. O −πΛ Pu η2 p(j) = e ρ(oj) . (14) IV. UPLINK MODELING IN MULTI-TIER CELLULAR NETWORKS Without loss of generality, let SINR be the SINR experi- j In this section, we show that the developed baseline model enced by a tagged BS in the jth tier and the BS is located at the origin. By Slivnyak’s theorem, the analysis holds for any for uplink transmission in single-tier cellular networks can be extended for uplink transmission in multi-tier cellular BS in the jth tier. Let each tier has its own SINR threshold networks. First, we present the analysis for multi-tier cel- θk, then, following (4), the SINR outage in the jth tier can be expressed as (cid:34) (cid:40) (cid:32) (cid:33)(cid:41)(cid:35) lular networks with common path-loss exponent. Then, we (cid:88) will show and comment on the case with different path-loss exponents in the different tiers. P {SINRj ≤ θj} = E 1 − e(cid:40)xp −ρθ(jj)(cid:41) (cid:89)σ2 + K(cid:32)Ik (cid:33) A. Common Path-loss Exponent o k=1 The developed model naturally captures multi-tier cellular = 1 − exp − θj σ2 K LI θj nthertewsohrokldsswρ(itkh) fdoirfftehreendtiffienrteenntsittiieerss bλukt waintdh adicfofemremnotncpuatothf-f ρ(oj) k=1 k ρ(oj) (15) o loss exponent η. In this case, the distribution of the transmit I power for the active UEs is obtained from the following where is the aggregate interference from the kth tier, and k lemma. the second line of equation (15) follows from the independence I I ∀ (cid:54) I of and i = k. Note that represents the co-tier inter- k iI (cid:54) j ference and for k = j represents the cross-tier interference. Lemma 2: In a K-tier Poisson cellular network with a com- k As discussed in the single-tier case, the interfering UEs do mon path-loss exponent η and a truncated channel inversion not constitute a PPP and their transmit powers are correlated. power control where each tier has the BS intensity of λ and k However, for analytical tractability, similar to the single-tier case, we approximate the interfering UEs in each tier with 10The correspondence between this result and the result for the downlink case will be discussed in Section. . a PPP and ignore the transmit power correlations. The SINR ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: the

text: cutoff

text: threshold

text: ρ(k),

text: the

text: distribution

text: of

text: the

text: transmit

text: power

text: o

text: and

text: the

text: spectral

text: efﬁciency

text: reduces

text: to

text: the

text: following:

text: of

text: the

text: active

text: UEs

text: in

text: the

text: uplink

text: in

text: the

text: jth

text: tier

text: is

text: given

text: by

text: R

text: exp

text: −xρσo2

text: PρPρouou

text: arctan(√x)dx.

text: fPj(x)

text: η2

text: x

text: Pu

text: In

text: the

text: interference-limiteId

text: case,

text: ρo

text: is

text: assumed

text: to

text: be

text: large

text: of

text: wahUerEe

text: iΛn

text: t=he

text: power

text: enough

text: such

text: that

text: θσ2

text: and

text: hence

text: noise

text: can

text: be

text: ignored.

text: In

text: this

text: case,

text: the

text: SINρoR

text: outage

text: reduces

text: to

text: the

text: following

text: simple

text: 2

text: closed-form:

text: E

text: Pα

text: (ρ(oj))αγ

text: α2η

text: η

text: Os

text: exp

text: θ

text: arctan(

text: θ)

text: j

text: (πΛ)α2η

text: e−πΛ

text: ρP(ouj)

text: η2

text: and

text: the

text: reduces

text: to

text: R

text: exp

text: x

text: arctan(

text: x)

text: Proof

text: Since

text: the

text: UEs

text: associate

text: to

text: the

text: BSs

text: based

text: on

text: the

text: average

text: dx

text: x

text: uplink

text: link

text: quality,

text: following

text: the

text: superposition

text: theorem

text: of

text: the

text: nat/sec/Hz.

text: PPP

text: the

text: association

text: regions

text: for

text: the

text: BSs

text: form

text: a

text: Voronoi

text: tessellation

text: for

text: a

text: PPP

text: with

text: intensity

text: Λ.

text: Note

text: that,

text: for

text: the

text: uplink

text: Equation

text: gives

text: a

text: closed-form

text: expression

text: for

text: the

text: outage

text: in

text: a

text: multi-tier

text: network,

text: the

text: association

text: regions

text: form

text: a

text: Voronoi

text: probability

text: in

text: its

text: simplest

text: form

text: and

text: shows

text: that

text: the

text: average

text: tessellation

text: rather

text: than

text: a

text: weighted

text: Voronoi

text: tessellation

text: due

text: to

text: rate

text: reduces

text: to

text: a

text: constant

text: in

text: this

text: special

text: case.

text: These

text: the

text: homogenous

text: transmit

text: powers

text: of

text: the

text: UEs.

text: The

text: rest

text: of

text: the

text: equations

text: clearly

text: show

text: that

text: when

text: P

text: is

text: not

text: a

text: binding

text: constraint

text: proof

text: follows

text: the

text: same

text: steps

text: as

text: in

text: Appendix

text: u

text: and

text: the

text: interference

text: is

text: much

text: larger

text: than

text: the

text: noise,

text: both

text: the

text: SINR

text: outage

text: and

text: the

text: spectral

text: efﬁciency

text: are

text: independent

text: of

text: the

text: The

text: truncation

text: outage

text: jth

text: tier

text: is

text: given

text: by

text: cutoff

text: threshold

text: as

text: well

text: as

text: the

text: BS

text: intensity.

text: O

text: −πΛ

text: Pu

text: η2

text: p(j)

text: e

text: ρ(oj)

text: IV.

text: UPLINK

text: MODELING

text: IN

text: MULTI-TIER

text: CELLULAR

text: NETWORKS

text: Without

text: loss

text: of

text: generality,

text: let

text: SINR

text: be

text: the

text: SINR

text: experi-

text: j

text: In

text: this

text: section,

text: we

text: show

text: that

text: the

text: developed

text: baseline

text: model

text: enced

text: by

text: a

text: tagged

text: BS

text: in

text: the

text: jth

text: tier

text: and

text: the

text: BS

text: is

text: located

text: at

text: the

text: origin.

text: By

text: Slivnyak’s

text: theorem,

text: the

text: analysis

text: holds

text: for

text: any

text: for

text: uplink

text: transmission

text: in

text: single-tier

text: cellular

text: networks

text: can

text: be

text: extended

text: for

text: uplink

text: transmission

text: in

text: multi-tier

text: cellular

text: BS

text: in

text: the

text: jth

text: tier.

text: Let

text: each

text: tier

text: has

text: its

text: own

text: SINR

text: threshold

text: networks.

text: First,

text: we

text: present

text: the

text: analysis

text: for

text: multi-tier

text: cel-

text: θk,

text: then,

text: following

text: the

text: SINR

text: outage

text: in

text: the

text: jth

text: tier

text: can

text: be

text: expressed

text: as

text: lular

text: networks

text: with

text: common

text: path-loss

text: exponent.

text: Then,

text: we

text: will

text: show

text: and

text: comment

text: on

text: the

text: case

text: with

text: different

text: path-loss

text: exponents

text: in

text: the

text: different

text: tiers.

text: P

text: {SINRj

text: θj}

text: E

text: A.

text: Common

text: Path-loss

text: Exponent

text: o

text: The

text: developed

text: model

text: naturally

text: captures

text: multi-tier

text: cellular

text: exp

text: θj

text: σ2

text: K

text: LI

text: θj

text: nthertewsohrokldsswρ(itkh)

text: bλukt

text: waintdh

text: adicfofemremnotncpuatothf-f

text: ρ(oj)

text: k

text: ρ(oj)

text: o

text: loss

text: exponent

text: η.

text: In

text: this

text: case,

text: the

text: distribution

text: of

text: the

text: transmit

text: I

text: power

text: for

text: the

text: active

text: UEs

text: is

text: obtained

text: from

text: the

text: following

text: where

text: is

text: the

text: aggregate

text: interference

text: from

text: the

text: kth

text: tier,

text: and

text: k

text: lemma.

text: the

text: second

text: line

text: of

text: equation

text: follows

text: from

text: the

text: independence

text: I

text: I

text: I

text: of

text: and

text: i

text: k.

text: Note

text: that

text: represents

text: the

text: co-tier

text: inter-

text: k

text: iI

text: j

text: ference

text: and

text: for

text: k

text: j

text: represents

text: the

text: cross-tier

text: interference.

text: Lemma

text: In

text: a

text: K-tier

text: Poisson

text: cellular

text: network

text: with

text: a

text: com-

text: k

text: As

text: discussed

text: in

text: the

text: single-tier

text: case,

text: the

text: interfering

text: UEs

text: do

text: mon

text: path-loss

text: exponent

text: η

text: and

text: a

text: truncated

text: channel

text: inversion

text: not

text: constitute

text: a

text: PPP

text: and

text: their

text: transmit

text: powers

text: are

text: correlated.

text: power

text: control

text: where

text: each

text: tier

text: has

text: the

text: BS

text: intensity

text: of

text: λ

text: and

text: k

text: However,

text: for

text: analytical

text: tractability,

text: similar

text: to

text: the

text: single-tier

text: case,

text: we

text: approximate

text: the

text: interfering

text: UEs

text: in

text: each

text: tier

text: with

text: correspondence

text: between

text: this

text: result

text: and

text: the

text: result

text: for

text: the

text: downlink

text: case

text: will

text: be

text: discussed

text: in

text: Section.

text: a

text: PPP

text: and

text: ignore

text: the

text: transmit

text: power

text: correlations.

text: The

text: SINR

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##