Power Water

Location:

Holmdel, NJ

Posted:

February 18, 2013

Contact this candidate

Resume:

**** **** ***** ************* ********* on Spread Spectrum Techniques and Applications

Multiuser Mercury/water lling for Downlink

OFDM with Arbitrary Signal Constellations

Angel Lozano Antonia M. Tulino Sergio Verd

Bell Labs (Lucent Technologies) Universit di Napoli Federico II

a Princeton University

Holmdel, NJ 07733, USA Naples 80125, Italy Princeton, NJ 08544, USA

Email: ****@******.*** Email: *******@**.*********.*** Email: *****@*********.***

each user on its assigned tones, and establishes user priorities

Abstract This paper formulates the power allocation policy

from the nonnegative set {wj }k=1 such that

that maximizes the region of mutual informations achievable

in multiuser downlink OFDM channels. Arbitrary partitioning

of the available tones among users and arbitrary modulation k

wj = 1.

formats, possibly different for every user, are considered. The (1)

policy, derived for slowly fading channels tracked by the base j =1

station, adopts the form of a multiuser mercury/water lling

Denoting by nj the number of tones assigned to user j, the

procedure that generalizes the single-user mercury/water lling

introduced in [1]. input-output relationship on the ith tone of the j th user is

Yi,j = hi,j Xi,j + Wi,j i = 1, . . ., nj j = 1, . . ., k

I. I NTRODUCTION

(2)

There is, of late, great interest in OFDM (orthogonal

where hi,j is a complex gain while the noise Wi,j is a

frequency-division multiplexing) for multiuser wireless down-

zero-mean unit-variance complex Gaussian random variable

links. Although in general suboptimal in the face of instan-

independent of the noise on the other tones. Noting that the

taneous CSIT (channel state information at the transmitter),

tones assigned to a given user may be nonadjacent, we de ne

orthogonal multiplexing techniques are much more robust to

j =

CSIT inaccuracies than nonorthogonal schemes. Furthermore, (3)

OFDM has the added bene t of being naturally well suited

as the fraction of the total bandwidth assigned to user j .

to deal with frequency selectivity [2]. With the continued

The complex signals {Xi,j }, zero-mean and mutually inde-

increase in signal bandwidths, OFDM is poised to be a central

pendent, must satisfy the power constraint

ingredient of most wireless systems to come.

The present paper formulates the optimum power allocation nj k

E Xi,j 2 P

policy for multiuser OFDM downlinks with instantaneous (4)

CSIT. This policy, which maximizes the mutual information i=1 j =1

region, extends to the multiuser realm the single-user mer-

where P is not a function of time. It is convenient to introduce

cury/water lling policy presented in [1] enabling:

normalized unit-power signals

Determination of the region of spectral ef ciencies reli-

Xi,j

ably achievable for any partition of the available tones Si,j =, (5)

E [ Xi,j 2 ]

and any modulation format.

A benchmark against which suboptimal power allocation whose distribution is dictated by the modulation scheme used

policies can be gauged. by the corresponding user, and a normalized power allocation

Assessment of the fundamental advantage of allocating

E Xi,j 2

power on the basis of instantaneous CSIT. pi,j = . (6)

For the sake of brevity, the proofs of the various results are

We can then de ne, for each tone, the channel state

not included in the manuscript.

i,j = P hi,j 2 (7)

II. M ODELS AND D EFINITIONS

which represents the receive signal-to-noise ratio on the ith

A. Multiuser OFDM

tone of the j th user when the power allocation is uniform,

Consider a downlink channel partitioned into n orthogo- i.e., pi,j = 1 i, j . (More generally, the receive signal-to-noise

nal tones, sized such that each experiences (approximately) ratio is pi,j i,j .) With that, (2) under coherent reception is

frequency- at fading. A scalar signal is transmitted on every equivalent to

tone. A scheduler at the base station assigns each tone to one of

Yi,j = i,j pi,j Si,j + Wi,j

k users, determines the signalling constellation to be used by (8)

292

0-7803-9780-0/06/$20.00 2006 IEEE

subject to greatly complicates optimization procedures that entail its

nj k

1 differentiation. Propitiously, a recently unveiled relationship

pi,j 1. (9) [3] af rms that, regardless of the distribution of the signal S,

n i=1 j =1

I = MMSE (16)

B. Fading Channels and CSIT d

{ i,j }i=1

For every user j, the channel states on the tones

where I is in nats/s/Hz and the function MMSE returns

assigned to that user have the same marginal distribution,

the minimum mean-square error in estimating S by observing

determined by the location of that particular user, and are

Y . This minimum mean-square error is achieved by the

known by its receiver. In particular,

conditional-mean estimator

E [ i,j ] = j

i = 1, . . ., nj (10)

S (y, ) = E [S S + W = y ; ] (17)

where j is a measure of the local-average signal-to-noise ratio

which is, in general, a nonlinear function of the observation

at the location of user j . The { i,j }i=1 are independent if

y . (It becomes linear if S is Gaussian.) Therefore,

the frequency separation of the corresponding tones exceeds

nj 2

some nite coherence bandwidth. Moreover, { i,j }i=1 are MMSE =E S S ( S + W, ) (18)

independent from their counterparts for all other users.

We shall consider slowly fading channels where { i,j } do with expectation over both S and W . Since S is unit power,

not change appreciably during each codeword. The transmitter MMSE [0, 1]. The inverse of MMSE with respect to the

composition of functions is denoted by MMSE 1 [0, ).

can then track the fading states. (Precisely, the formulation

only requires that the amplitudes { i,j } be tracked). For a Gaussian signal, (17) becomes

In the case of Rayleigh fading, which shall be invoked in

(y, ) =

many of our examples, every i,j has an exponential density S y (19)

e / j

MMSE = 1/(1 + ) and, in turn, to

f i,j = i = 1, . . ., nj . leading to

(11)

1 = 1. (20)

III. M UTUAL I NFORMATION AND MMSE MMSE

Our measure of performance is the mutual information, For discrete constellations, (17) yields

which speci es the maximum spectral ef ciency achievable

y s 2

=1 q s e

with arbitrary reliability for a given modulation format. Given

S (y, ) = (21)

a scalar Gaussian-noise channel of the form Y = S + W, m y s 2

=1 q e

we denote its mutual information by

from which the MMSE follows via (18), which can be easily

I = I (S ; S + W ) (12) implemented as a low-pass lter driven by the estimation error

S S 2 . Alternatively, the MMSE can be tabulated and stored

which is maximized when S is Gaussian, for which I =

in memory for each of the constellations in use.

log(1+ ) where the base of the logarithm determines the infor-

IV. M ULTIUSER M ERCURY / WATERFILLING

mation units. While ideal, Gaussian signals cannot be realized

in practice because of their continuous and unbounded support. Since { i,j } are known by the transmitter, the power

Rather, signals usually conform to discrete constellations with allocation is a function thereof. Every realization of { i,j }

limited peak-to-average ratios. For a discrete constellation (m- thus gives rise to a k -dimensional region containing all of the

QAM, m-PSK, etc) consisting of m points, {s }m 1, taken feasible k -tuples {R1, . . ., Rk } where

with probabilities {q }m 1 such that =1 q = 1,

= nj

Rj (p1,j, . . ., pnj,j ) = Ij (pi,j i,j ) (22)

I = log( e) fm (y, ) log fm (y, ) dy (13) nj i=1

is the mutual information attained by user j on its as-

where the integration extends to the complex plane while

signed tones with the function Ij re ecting the signalling

s 2

q e y scheme used by that user. The boundary of this region can

fm (y, ) = . (14)

be fully characterized by means of the weighted function

=1 k

j =1 wj Rj for all priorities {wj }j =1 satisfying (1). We

A de ning feature of any discrete constellation is the minimum

thus seek the power allocation {pi,j } that solves

distance between any two of its points, which we indicate by

1 wj

d = min sk s . (15) {pi,j } = arg max Ij (pi,j i,j ).

pi,j 1 n j

{pi,j }: n

k= j =1 i=1

i,j

(23)

The fact that, for non-Gaussian signals, the mutual in-

yielding the optimum boundary {R1, . . ., Rk }.

formation cannot in general be expressed in closed form

293

old, ( j /wj ), that is directly proportional to the bandwidth

fraction of the corresponding user and inversely proportional

to its priority. Active tones, in turn, are allocated the exact

amount of power needed to render i,j MMSEj (pi,j i,j ) equal

to the threshold of their respective users.

w1 w1 w1 w1

Computationally, Theorem 1 boils down to solving a single

1 1 1 1 w2 w2 w2

nonlinear equation on, from which {pi,j } are then simply

w3 w3

2 2 2

3 3

mapped via (24) and (25).

In order to provide a graphical interpretation, let us de ne

1/ i,j the auxiliary function

1/ MMSE 1 [0, 1]

Gj = (26)

User j =1 User j =2 User j=3

1 >1

(a)

which, for a Gaussian signal, reduces to Gj = 1.

Theorem 1 is tantamount to the following multiuser mer-

H2 0 cury/water lling procedure (cf. Fig. 1):

(a) For each of the n tones, set up a vessel of base (wj / j )

1, solid up to a height 1/ i,j .

(b) Choose . Pour mercury onto each of the vessels until its

height (including the solid) reaches wj i,j Gj ( wj j i,j ).

the water level reaches 1/ .

(d) The volume of water in the (i, j )th vessel gives pi,j .

G ( /w ) As in single-user mercury/water lling, the mercury regu-

j j j j i,j

w j i,j

1/ i,j lates the water admitted by each vessel thereby accounting

for the respective signalling constellations. The new feature

in multiuser mercury/water lling is the variability in vessel

(b)

widths, which also regulates the water admission but in

relation with the user priorities and assigned bandwidths.

Since no mercury is poured onto vessels whose signal is

Gaussian, multiuser mercury/water lling reverts to a multiuser

p i,j

water lling whenever all of the signals are Gaussian:

= 0 i,j

pi,j (27)

1/ G ( /w ) 1

wj / j j

j j w j j i,j pi,j i,j > (28)

i,j wj

1/ i,j j i,j

In this case, we can in fact clear the parameter and obtain

an alternative xed-point form for the solution.

(c)

Corollary 1: With Gaussian signals,

Fig. 1. Multiuser mercury/water lling with k = 3 users and with adjacent

pi,j = 0 i,j

tones assigned to each user for clarity. (a) On vessels of base (wj / j ) 1

solid up to 1/ i,j, pour mercury as shown. (b) Water ll until the water levels

reach 1/ . (c) The volume of water in the (i, j )th vessel gives pi,j . wj

j 1 MMSEj (pi,j i,j )

pi,j = i,j >

k n

1 MMSE (p )

=1 =1,

Theorem 1: The unique power allocation that solves (23) is

Although in principle less appealing than (27) (28), the

=0 i,j

pi,j (24) xed-point characterization in Corollary 1 has the advantage

of generalizing to nonorthogonal parallel channels [4].

1 j j

pi,j i,j > (25)

MMSEj

V. L OW-P OWER AND H IGH -P OWER R EGIMES

i,j wj i,j wj

In the low-power regime, multiuser mercury/water ling

with such that (9) is met with strict equality.

behaves as follows for quadrature-symmetric signals, a class

The strategy spelled by Theorem 1 is as follows. No power that encompasses ideal Gaussian signals as well as discrete

constellations such as m-QAM and m-PSK [5].

is allocated to tones whose channel state is below a thresh-

294

Proposition 1: For P 0, multiuser mercury/water lling 2

Discrete Constellations

allocates power only to the tone(s) with the largest factor

Gaussian

wj i,j / j . If several tones share the largest such factor, then

power is uniformly distributed thereon.

1.5

In contrast with the low-power regime, where optimality

in terms of mutual information boils down to quadrature

p 1=2-p 2

symmetry only, in the high-power regime the nonidealities of .

discrete constellations become overtly manifest.

1=5 dB

Proposition 2: If the signals are Gaussian, then for P SK

pi,j = + O i = 1, . . ., nj AM

0.5 =5 dB

(29) 2

-Q

j P 16

whereas, if the signals conform to discrete constellations with

minimum distance dj for user j, then 0

log P

0 0.2 0.4 0.6 0.8 1

= + O pi,j (30)

hi,j j

2 d2 P w 1=1-w 2

with

= Fig. 2. Average power allocation as function of w1, for k = 2 users having

. (31)

k n

1 1

1 dB = 2 dB = 5. Both channels are frequency- at Rayleigh-faded with

=1 h, 2 d2

bandwidth partitioning 1 = 2 = 1/2.

Notice the discrepancy between the leading terms in the

high-power expansion with ideal Gaussian signals and with

With the average conditions in Example 1, the channel states

discrete constellations. With the former, the power allocated

are frequently in a range where 16-QAM is rich enough to

to a tone is dominated by the priority and bandwidth fraction

resemble an ideal Gaussian signal whereas QPSK is not.

of the respective user. With the latter, in contrast, the user

priority and bandwidth fraction become immaterial for large Example 2: Consider the same scenario of Example 1,

except with 1 dB = 10 and 2 dB = 0. The average multiuser

P . Only the channel states and the constellation minimum

distances are of essence, with more power allocated to tones mercury/water lling power allocation and the ergodic mutual

whose users are employing richer constellations but with less information region boundaries are shown in Figs. 4 and 5,

power on tones with stronger channel states. respectively.

In Example 2, the various signalling constellations behave

VI. E RGODIC C HARACTERIZATION

similarly whenever user j = 2 is prioritized because it is often

The optimum power allocation {pi,j } and the corresponding

in low-power conditions. When user j = 1 is favored, however,

user mutual informations {Rj }k=1 can be regarded as random

j there is a large disparity between the power allocation and

variables whose distributions are induced by the channel

mutual informations for the several signalling formats.

states, { i,j }. For delay-tolerant applications, nonetheless, the

Another instance in which, notwithstanding the delay toler-

time averages of the mutual informations acquire operational

ances, the average mutual informations provide a meaningful

signi cance. Under ergodic fading, these time averages equal

characterization is that of strong frequency selectivity per user,

Rj = E [Rj ]. The corresponding average power allocation,

whereby (22) by itself provides an effective averaging mecha-

pj = E [pi,j ]

i = 1, . . ., nj nism. To gain insight, we consider the limiting regime where

(32)

nj, j = 1, . . ., k.2 From the asymptotic independence

meaningfully conveys how the power is allocated on average. of the channel states for each user, the {Rj } converge in the

Note that this average allocation is common to all the tones mean-square sense to nonrandom limits that depend only on

of a given user because of their identical marginal fading the signalling constellations and fading distributions. Precisely,

distribution and equal signalling constellation.

Example 1: Consider an access point streaming data to Rj Ij f i,j d (33)

MMSE

k = 2 users over respective frequency- at Rayleigh-faded wj

channels with equal bandwidth assigned to each user (i.e.,

with the solution of

1 = 2 = 1/2) and with 1 dB = 2 dB = 5.1 The average

multiuser mercury/water lling power allocation as function of

1 1 j

f i,j d = 1.

the priority w1, is depicted in Fig. 2 parameterized by the j (34)

MMSEj

constellation used by both users. The corresponding ergodic

j =1 wj

mutual information region boundaries are shown in Fig. 3.

2 Note that, by virtue of (9), the total transmit power is also growing without

1 x = 10 log10 x. bound as the system bandwidth increases.

295

3 2

Discrete Constellations Discrete Constellations

Gaussian Gaussian

=5 dB

1.5

=5 dB

R 2 (bits/s/Hz)

-Q

p 1=2-p 2

QPS

=10 dB

0.5

=0 dB

QPSK 16-QAM

0 0.2 0.4 0.6 0.8 1

0 1 2 3

R* w 1=1-w 2

(bits/s/Hz)

Fig. 3. Average mutual information regions for k = 2 users having 1 dB =

Fig. 4. Average power allocation as function of w1, for k = 2 users having

2 dB = 5. Both channels are frequency- at Rayleigh-faded with bandwidth

1 dB = 0 and 2 dB = 10. Both channels are frequency- at Rayleigh-faded

partitioning 1 = 2 = 1/2. with bandwidth partitioning 1 = 2 = 1/2.

The tone powers {pi,j } remain random, but their empirical Discrete Constellations

Gaussian

distributions for the various users converge in probability to

nonrandom limits that can be found from via (24) (25).

Speci cally for Gaussian signals and Rayleigh fading, we =10 dB

can invoke (11) and (20) to obtain more explicit versions of

R 2 (bits/s/Hz)

(34) and (33). Under these conditions

=0 dB

Rj E1 j = 1, . . ., k

(35)

wj j

in nats/s/Hz, with E1 = 1 t 1 e t dt an exponential

integral and with the solution to

wj e wj j

j j

= 1. QPSK 16-QAM

E1 (36) 0

j wj j

j =1

0 1 2 3 4

VII. S UMMARY R* (bits/s/Hz)

We have formulated the multiuser mercury/water lling

power allocation policy for OFDM downlinks with arbitrary

Fig. 5. Average mutual information regions for k = 2 users having 1 dB =

tone partitioning and modulation formats.3 The more general 0 and 2 dB = 10. Both channels are frequency- at Rayleigh-faded with

problem of jointly assigning tones and allocating power could bandwidth partitioning 1 = 2 = 1/2.

also be explored, with the multiuser mercury/water lling pro-

cedure as a building block.

[4] A. M. Tulino, A. Lozano, and S. Verd, Capacity-achieving input co-

R EFERENCES variance for single-user multi-antenna channels, IEEE Trans. on Wireless

Communications, Jan. 2006.

[1] A. Lozano, A. M. Tulino, and S. Verd, Optimum power allocation for

[5] S. Verd, Spectral ef ciency in the wideband regime, IEEE Trans. on

parallel Gaussian channels with arbitrary input distributions, IEEE Trans.

Inform. Theory, vol. 48, no. 6, pp. 1319 1343, June 2002.

on Inform. Theory, vol. 52, no. 7, July 2006.

[2] J. A. C. Bingham, Multicarrier modulation for data transmission: An

idea whose time has come, IEEE Commun. Magazine, vol. 28, no. 5,

pp. 5 14, May 1990.

[3] D. Guo, S. Shamai, and S. Verd, Mutual information and minimum

mean-square error in Gaussian channels, IEEE Trans. on Inform. Theory,

vol. 51, no. 4, pp. 1261 1283, Apr. 2005.

3 Although the modulation format has been considered uniform over the

tones assigned to each user, this restriction can be easily removed.

296

Contact this candidate