On the Lambert-W function for constrained resource allocation in cooperative networks

Abstract

In cooperative networks, a variety of resource allocation problems can be formulated as constrained optimization with system-wide objective, e.g., maximizing the total system throughput, capacity or ergodic capacity, subject to constraints from individual users, e.g., minimum data rate, transmit power limit, and from the system, e.g., power budget, total number of subcarriers, availability of the channel state information (CSI). Most constrained resource allocation schemes for cooperative networks require rigorous optimization processes using numerical methods since closed-form solutions are rarely found. In this article, we show that the Lambert-W function can be efficiently used to obtain closed-form solutions for some constrained resource allocation problems. Simulation results are provided to compare the performance of the proposed schemes with other resource allocation schemes.[PUBLICATION ABSTRACT]

Brah et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:19 http://jwcn.eurasipjournals.com/content/2011/1/19

RESEARCH Open Access

On the Lambert-W function for constrained resource allocation in cooperative networks

Flix Brah1*, Abdellatif Zaidi2, Jrme Louveaux1 and Luc Vandendorpe1

AbstractIn cooperative networks, a variety of resource allocation problems can be formulated as constrained optimization with system-wide objective, e.g., maximizing the total system throughput, capacity or ergodic capacity, subject to constraints from individual users, e.g., minimum data rate, transmit power limit, and from the system, e.g., power budget, total number of subcarriers, availability of the channel state information (CSI). Most constrained resource allocation schemes for cooperative networks require rigorous optimization processes using numerical methods since closed-form solutions are rarely found. In this article, we show that the Lambert-W function can be efficiently used to obtain closed-form solutions for some constrained resource allocation problems. Simulation results are provided to compare the performance of the proposed schemes with other resource allocation schemes.

Keywords: Resource allocation, Lambert-W function, cooperative networks, QoS

1 IntroductionCooperative transmissions have attracted much attention over the last few years. It has been demonstrated that the benefits of multi-antenna transmission can be achieved by cooperative transmission without requiring multiple antennas at individual nodes (for example see [1-3]). Cooperation is particularly relevant when the size of mobile devices limits the number of antennas that can be deployed.

Wireless Mesh networks (WMN) and relay networks are among the main networks that use cooperative communication. The main distinguished characteristic of mesh and relay networks is possibility of multi-hop communication. In Mesh networks, traffic can be routed through other mobile stations (MSs) and can also take place through direct links. Nodes are composed of mesh routers and mesh clients and thus routing process is controlled not only by base station (BS) but also by mobile station MS [4]. Each node can forward packets on behalf of other nodes that may not be within direct wireless transmission range of their destination. In case of relay networks, the network infrastructure consists of relay stations (RSs) that are mostly installed, owned, and

controlled by service provider. A RS is not connected directly to wire infrastructure and has the minimum functionality necessary to support multi-hop communication. The important aspect is that traffic always leads from or to BS. The realization of the performance improvement promised by cooperation in wireless mesh and relay networks depends heavily on resource allocation (among other things).

Recently, resource allocation for OFDMA WMN with perfect CSI has been an active research topic. In [5], a fair subcarrier and power allocation scheme to maximize the Nash bargaining fairness has been proposed. Instead of solving a centralized global optimization problem, the authors proposed a distributed hierarchical approach where the mesh router allocates groups of subcarriers to the mesh clients, and each mesh client allocates transmit power among its subcarriers to each of its outgoing links. In [6], an efficient intra-cluster packet-level resource allocation approach taking into account power allocation, subcarrier assignment, packet scheduling, and QoS support has been studied. The authors employ the utility maximization framework to find the joint power-frequency-time resource allocation that maximizes the sum rate of a WMN while satisfying users minimum rate requirements. The benefits of optimal resource allocation in cooperative relay networks with perfect CSI

* Correspondence: mailto:[email protected]

Web End [email protected]

1ICTEAM Institute, Universit Catholique de Louvain, Place du Levant 2, 1348 Louvain-la-Neuve, BelgiumFull list of author information is available at the end of the article

2011 Brah et al; licensee Springer. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0

Web End =http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Brah et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:19 http://jwcn.eurasipjournals.com/content/2011/1/19

Page 2 of 13

has also been investigated by several authors (see, e.g., [7,8], and references therein).

However, when the channel variations are fast, the transmitter may not be able to adapt to the instantaneous channel realization. Hence, CSI-aware resource allocation is not suitable for environments with high mobility. When the channel state can be accurately tracked at the receiver side, the statistical channel model at the transmitter can be based on channel distribution information feedback from the receiver. We refer to knowledge of the channel distribution at the transmitter as CDIT. In [9], CDIT-based constrained resource allocation problem for non-cooperative OFDMA-based networks is studied. The authors derive an optimal power allocation algorithm in closed-form. In [10], a dynamic resource allocation algorithm aiming to maximize the delay-limited capacity of a cooperative communication with statistical channel information is developed. In[11], a power allocation problem for ergodic capacity maximization in relay networks under high SNR regime is solved using numerical methods.

In this article, we present a new result on how the Lambert-W function can be used to efficiently find closed-form solution of constrained resource allocation problems for cooperative networks.

There are two significant benefits from using the Lambert-W function in the context of resource allocation for cooperative networks. Most resource allocation schemes for cooperative networks require rigorous optimization processes using numerical methods since closed-form solutions are rarely found. Using the Lambert-W function, resource allocations can not only be expressed in closed-form but they can also quickly be determined without resorting to complex algorithms since a number of popular mathematical softwares, including Maple and Matlab, contain the Lambert-W function as an optimization component.

The Lambert-W function has several uses in physical and engineering applications [12-15]. In [14], the Lambert-W function is used for the purpose of diode parameters determination in diode I-U curve fitting. Recent work in [15] shows that the Lambert-W function also finds utilization in Astronomy to calculate the position of an orbiting body in a central gravity field.

The remainder of this article is organized as follows. In Sect. 2, we provide a concise introduction to the Lambert-W function. In Sect. 3, we show how the Lambert-W function is applied to a subcarrier allocation problem in WMNs. The use of the Lambert-W function to a power allocation problem in relay networks with statistical channel information is discussed in Sect. 4. In Sect. 5, we show the performance of the proposed resource allocation methods by simulation. Finally, conclusions are drawn in Sect. 6.

2 The Lambert-W FunctionThe Lambert function W(x) is defined to be the multi-valued inverse of the function f(x) = xex [12]. That is, Lambert W(x) can be any function solution of the transcendental equation

W(x)eW(x) = x. (1)

Actually, for some values of x, Equation 1 has more than one root, in which case the different solutions are called branches of W. Since the values of interest in our work are real, we will concentrate on real-value branches of W. If x is real, then for -1/e x < 0, there are two possible real values of W(x) (see Figure 1). The branch satisfying W(x) -1 is denoted by W0(x). The

branch satisfying W(x) -1 is denoted by W(x) and it is referred to as the principal branch of the Lambert-W function.

The nth derivative of the Lambert-W function is given by [12].

dnW(ex)

dxn =

qn(W(ex))

(1 + W(ex))2n1 for n 1 , (2)

in which the polynomials qn, given by

qn(w) =

n1

i=0

n 1

i

(1)iwi+1, (3)

contain coefficients expressed in terms of second-order Eulerian numbers and q1(w) = w.

In (3), the second-order Eulerian number

n m

cor-

responds to the number of permutations of the multiset {1, 1, 2, 2,..., n, n} with m ascents which have the property that for each i, all the numbers appearing between the two occurrences of i in the permutation are greater than i [16].

The application of the Lambert-W function to obtain a closed-form solution for resource allocation problems in wireless mesh and relay networks constitutes the principal contribution of this article.

3 The Lambert-W function for subcarrier allocation in wireless mesh network3.1 Problem formulationWe consider a single cluster OFDMA WMN that consists of one mesh router (MR) and K mesh clients (MC) as illustrated in Figure 2. The MR serves as a gateway for the MCs to the external network (e.g., Internet). The MCs can communicate with the MR and with each other through multi-hop routes via other MCs. We label the MR as node 0 and the MC nodes as k = 1,..., K. A link (k, j) exists between node k and node j when they are within transmission range of each other, i.e., they are neighboring nodes.

Brah et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:19 http://jwcn.eurasipjournals.com/content/2011/1/19

Page 3 of 13

Figure 1 The two real branches of the Lambert-W function.

Figure 2 Illustration of a wireless mesh network.

Brah et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:19 http://jwcn.eurasipjournals.com/content/2011/1/19

Page 4 of 13

There are a total of N subcarriers in the system. Each subcarrier has a bandwidth B. The channel gain of sub-carrier n on link (k, j), which connects MC k to MC j, is denoted by Gnkj and the transmit power of MC k on sub-carrier n is denoted by pnk. MC k has a transmit power limit of pk and a minimal rate requirement of Rk. Let nk

be the number of subcarriers to allocate to MC k, using only information available at the MR, i.e., the average channel gain of all outgoing links at MC k, Gk. Based on Gk and uniform power allocation assumption over all the nk subcarriers (pnk = pk

nk, k), the MR determines an approximated rate for MC k as

rk(nk) = nkB log2

1 + Gk 2n

1 + k nk

subject to:

nkB log2

1 + knk

Rk

K

k=1nk N

K

k=1nkB log2

(5)

pk nk

, (4)

where 2n is the thermal noise power, and is the SNR gap related to the required bit-error-rate (BER).

The main reason that the MR determines an approximated rate instead of the exact rate is that the MR knows only the average channel gain Gk, but not the

complete channel gain Gnkj. In general, exact and complete information needed to determine the exact rate is rarely available at the MR. For practical SNR values (SNR > 5 dB), the gap between the exact rate and its approximate (4) is very small and (4) can be viewed as the rate realized at MC k.

There are various constraints associated with resource allocation in OFDMA-based WMNs. At each node k, the sum of the transmit power on the allocated subcarriers is bounded by a maximum power level pk.

We assume that each subcarrier can only be allocated to one transmission link in a cluster. Different traffic types require different packet transmission rates. For example, voice packets require a constant rate; video traffic has minimum, mean, and maximum rate requirements; while data traffic is usually treated as background traffic whose source rate is dynamic. In our problem formulation, we only take the minimum rate requirement of these three traffic types, if any, into account.

The resources to allocated are defined as a set of subcarriers, and the total transmit power available at each node. We consider a distributed hierarchical resource allocation, where the MR only performs a rough resource allocation with limited information (the average channel gain of all outgoing links at MC or the statistical channel information) and the MCs perform more refined resource allocation with full information that is available locally. In this section, we focus on subcarrier allocation at MR and we assume that each MC k distributes its transmit power limit pk

equally over all its allocated subcarriers. After

subcarrier allocation, the optimal power allocation is performed at each MC k. The optimal power allocation is not developed in this article. Mathematically, the subcarrier allocation problem at MR can be formulated as

max

nk

where k = Gkpk

2n

.

3.2 Solution methodWe propose a solution method based on the Lagrange dual approach and the Lambert-W function. First, we express the Lagrangian of the primal problem (5) as

L(nk, k, ) =

K

k=1nkB log2

1 + k nk

+

(6)

where lk and are the Lagrangian multipliers associated with the minimum rate constraint of MC k and the total subcarrier constraint.

By KKT first optimality condition [17], we take the derivative of (6) with respect to nk for fixed (lk, ) and set the derivative to zero to obtain

ln

1 + k nk

k nk

1 + k

nk

K

k=1k

nkB log2

1 + knk

Rk

K

k=1nk N

= 0. (7)

By solving Equation 7 for nk, for given (lk, ), the optimal value of subcarriers to be allocated to MC k is given by (see Appendix A)

nk =

kW

Bln 2(1 + k)

exp

1

Bln2 (1 + k)

. (8)

The optimal values of and lk still need to be found. They correspond to the ones that satisfy the total sub-carrier constraint with equality and the individual rate constraints. We substitute nk in Equation 6 by nk to form the dual problem

1 + W

exp

1

Bln2 (1 + k)

Brah et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:19 http://jwcn.eurasipjournals.com/content/2011/1/19

Page 5 of 13

k, L(nk, k, ). (9) The optimal k, for fixed , are found using KKT conditions. To derive L(nk, k, ) over lk, we make use of the formula of the nth derivative of the Lambert-W function given by (2). Applying (2) for n = 1, we obtain that the optimal k has to satisfy (see Appendix B)

fm(k)

Rk

k = 0, (10)

where

3.3 Extension to Mesh router with statistical channel informationIn some fading environments, there may not be a feedback link sufficiently fast to convey the full CSI to the MR. The MR may know only the channel distribution information (CDI) and may use the CDI to allocate resource. Following the approach in [9], we can formulate an ergodic rate maximization problem at the mesh router with only CDI as

max

nk E

K

k=1nkB log2

min

1 + knk

subject to:

Ek

nkB log2

1 + knk

Rk

K

k=1nk N

fm(k) =

wk

1 + wk

Bln 2 +

(1 + k)(1 + wk)2

ln (wk)

(15)

+

(1 + k) (1 + wk)

+ 2(1 + k)2(1 + wk)2

with wk = W

exp

1

.

where a = [a1, a2,..., ak,..., aK], and Ea {.} represents the statistical expectation with respect to a.

Using the solution method proposed in 3.2, the optimal subcarrier allocation solution of (15) can be obtained by solving the following equation for nk

Ek

ln

B ln 2

(1+k)

It can be shown that fm is a strictly increasing function of k and fm(k) > 0 for all k 0. Thus, the inverse

function, f 1m,of fm, exists. The optimal k can then be deduced as

k = f 1m

Rk k

1 + k

nk

k

nk

1 + knk

Bln 2 (1 + k)

. (11)

Now we turn to find the optimal *. Substituting lk in

(8) by the optimal value obtained in (11) and using the constraint

Kk=1 nk = N, we obtain

= 0. (16)

To express the left hand side of (16), we need to find the probability density function (pdf) of the random variable

fm (k) = ln

1 + k

nk

k

nk

1 + knk

Bln 2 (1 + k)

. (17)

It can be observed that fm is monotonically nonde

creasing and non-negative with respect to ak. Thus, there exists a unique inverse function, f1m, of fm.

Let Fk(k) and Tk(k) denote the cumulative distri

bution function (cdf) and the pdf of ak. We assume that

Fk(k) and Tk(k) are known at the MR.

First, using the same derivation as in Appendix A where the right hand side of equation (A.1) is fm instead of 0, we can express the inverse function of fm as

k

exp

1

Bln 2 (1 + k)

K

k=1

kW

= N. (12)

1 + W

exp

1

Bln 2 (1 + k)

Let

gm() =

exp

1 B

ln 2 (1 + k)

K

k=1

kW

1 + W

exp

1 B

ln 2 (1 + k)

. (13)

1 + fmBln 2 (1 + k)

Proposition 1 An inverse function for gm, g1m, exists

(see Appendix C. for proof).

Thus

= g1m(N). (14)

fm =

nk

1 + W

exp

. (18)

W

exp

1 + fmBln 2 (1 + k)

Brah et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:19 http://jwcn.eurasipjournals.com/content/2011/1/19

Page 6 of 13

Using expression (18) for the root, we derive the cdf of fm as

Ffm

fm = Fk

fm . (19)

The pdf of fm is then given as the derivative of (19) with respect to fm as

Tfm

k

fm = Tk

k

fm

1 + k

fm 2 Bln 2 (1 + k)

n2k

. (20)

Finally, using (20), the optimal subcarrier assignment

nk is obtained by solving the following equation for nk

0

fm Tfm

fm dfm = 0. (21)

For given multipliers lk and , Equation 21 can be solved numerically.

The optimal values of lk, (k [1, K]) and still need to be found. They correspond to the ones that satisfy the individual rate constraints and the total subcarriers constraint (with equality). If some of the individual rate constraints are exceeded, the corresponding lk is equal to zero. Unlike in the instantaneous allocation where we have derive closed forms for lk and , here it is not easy to obtain a close form. We use an iterative search algorithm to find the optimal set of lk and .

4 The Lambert-W function for CDIT-based power allocation in relay networksIn this section, we show how the Lambert-W Function can be used for constrained resource allocation in relay networks.

4.1 Problem formulationConsider the relay network operating in receiver cooperation mode as illustrated in Figure 3. The transmitter at the source node sends a signal x. Let x1 and y1 denote the transmitted and received signals at the relay node, respectively. We assume that the relay node operates in the full duplex mode, i.e., the relay can receive and transmit simultaneously on the same frequency channel[7]. Thus, the received signals at the relay node and the destination node are given by

y1 = h2x + z1

y = h1x + gh3x1 + z, (22)

where z1 and z are independent identically distributed(i.i.d) zero mean circularly symmetric complex Gaussian (ZMCSCG) additive noise with unit variance.

The capacity cut set bound of the relay network of Figure 3 operating in a full duplex mode with perfect CSI can be expressed as [11]

Cinst = max

0,1

min

log2(1 + P(1 2)(1 + 2)), log2

1 + P1 +

, (23)

where r represents the correlation between the transmit signals of the transmitter and the relay, and gi = |hi|

2.

We assume Rayleigh fading where each channel gain hi, i = 1, 2, 3, is i.i.d. and normalized to have unit variance; hence, the corresponding channel power gain is i.i.d. exponential with unit mean. The average channel power gain between the relay and the receiver is g. We assume that g characterizes only path-loss attenuation, hence g = 1/da, where d is the distance between the relay node and the receiver node and a is the path-loss power attenuation exponent. As in receiver cooperation mode the relay is assumed to be close to the receiver, the scenario of interest is when d is small.

(1 )g + 2

(1 )g

P3

Figure 3 Illustration of a relay network operating in receiver cooperation mode.

Brah et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:19 http://jwcn.eurasipjournals.com/content/2011/1/19

Page 7 of 13

We consider a fast fading environment, where the receiver has CSI to perform coherent detection, but there is no fast feedback link to convey the CSI to the transmitter. Hence, the transmitter only has CDI, but no knowledge of the instantaneous channel realizations. Ergodic capacity is used to characterize the transmission rate of the channel.

We assume the channel has unit bandwidth. We further assume an average network power constraint on the system:

E

|x|2 + |x1|2 P, (24)

where the expectation is taken over repeated channel uses.

The network power constraint model is applicable when the node configuration in the network is not fixed[11]. Note that, when the node configuration is fixed, the individual power constraint model reflects the practical scenarios more than the network model. However, the power allocation problem is, in general, more tractable under network power constraint.

The total power P is optimally allocated between the transmitter and the relay, i.e.,

E

|x|2 P, E

|x1|2 (1 )P, (25)

where b [0,1] is parameter to be optimized based on CDI and node geometry g.

It has been shown in [7] that the capacity upper bound in the asynchronous channel model, i.e., the channel model where the nodes do not have complete CSI, can be found by setting the correlation r to zero.

Since the CDI channel model falls into this case, the ergodic capacity upper bound can be found by taking the expectation of (23) over the channel distribution and setting r = 0. Making use of the high SNR (P 1)

approximation log(1 + xP) log(xP), the ergodic capacity upper bound is then given by

Cerg = max

01

min

4.2 Solution methodTo find the optimal power allocation in closed-form, we propose an approach that uses the Lambert-W function.

First, we need to evaluate the expected value of the capacity expression over the channel fading distribution. For this end, we make use of the following formula for i.i.d. exponential random variables X1, X2 with unit mean:

E[log(a1X1 + a2X2)]

=

a1 loga1 a2 loga2

a1 a2

log e if a1 = a2 log a1 + log e1 if a1 = a2,

(28)

where a1 and a2 are positive scalar constants and g is Eulers constant.

Applying formula (28), the first term and the second term inside the min{.} in expression (26) are given, respectively, by

E [log2(P(1 + 2))] = log2P + log2 + log2e1 , (29)

and

E[log2(P1 + (1 )Pg3)] =log2P

+ g(1 )log2

#g(1 )$ log2g(1 ) log2e . (30)

Expression (29) is an increasing function of b. It is easy to show that expression (30) is a decreasing function of b (for g of interest, i.e., g > 1). Thus the optimal value b* solution of the maximization problem (27) can be found by equating expressions (29) and (30) as

log2P + log2 + log2e1 =log2P

+ g (1 )log2(g (1 )) log2

g (1 )

log2e . (31)

Equation 31 is equivalent to

ln () + 1 = g(1 ) ln (g(1 )) ln ()

g (1 )

E[log2(P(1 + 2))],

E[log2(P1 + (1 )Pg3)]

.

(26)

The problem is to find the optimal power allocation, i.e., the optimal value of b, that gives the capacity upper bound Cerg(b) of (26). Mathematically the power allocation problem can be formulated as

max

01

min

, (32)

where ln(x) is the natural logarithm of x.

After some algebraic manipulations (32) can be rewritten equivalently as

g (1 )

exp

g (1 )

=

1e . (33)

It can be recognized that Equation 33 is in the form of a transcendental Equation 1. Thus we have

W

1 e

=

g (1 )

E[log2(P(1 + 2))],

E[log2(P1 + (1 )Pg3)]

(27)

Problem (27) has been addressed in [11] and a numerical solution has been proposed, but no closed-form expression has been provided. This contrasts with what will be done here.

. (34)

The optimal value b* is deduced from (34) as

= Kg

Kg + 1, (35)

.

Brah et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:19 http://jwcn.eurasipjournals.com/content/2011/1/19

Page 8 of 13

1e = 1.

It is interesting is to observe that the optimal power allocation is obtained in closed-form and depends only on g, i.e., on the distance d between the relay node and the destination node and the path-loss power attenuation exponent a.

4.3 Comparison with CSIT-based power allocationIn order to assess the relevance of the CDIT-based approach, it has to be compared to the allocation scheme based on perfect CSIT. Perfect CSIT is unrealistic, but for the purpose of comparison, let us assume perfect CSIT. Then the power allocation can be formulated to maximize the instantaneous capacity instead of the ergodic capacity. Mathematically, the CSIT-based power allocation can be formulated as

max

0,1

where K = W

min

12log2(1 + P(1 2) (1 + 2)),

1

2log2

1 + P1 +

. (36)

The optimal values of r and b solution of (36) have been found in [11] as

= 1

g2 + 2g + 2, (37)

= g2 + 2g + 2

g2 + 3g + 2. (38)

The instantaneous capacity upper bound for high SNR regime is deduced as

Cinst = log2

P3

(1 ) g + 2

(1 )g

#g + 1

2 $g + 2 P

. (39)

Both CDIT-based and CSIT-based optimal power allocation expressions (35) and (38) are in closed-form and very fast to compute. Thus, the complexity is almost the same. The main difference between the two allocation schemes is the amount of feedback required to perform power allocation. Recall that, for the CSIT-based scheme, the allocation is performed after each symbol period. Let Ns be the number of symbol periods after which the CDIT-based resource allocation is performed. Then a rough estimation tells us that the feedback needed to perform CDIT-based power allocation is

reduced by 1

Ns compared to the perfect CSIT scheme.

5 Simulation resultsIn order to assess the performance of the proposed resource allocation methods, we conduct simulations

and compare the simulation results with other baseline schemes.

5.1 Simulation results for wireless mesh networksWe consider a cluster with four wireless nodes with the scheduling tree topology shown in Figure 4 and 4a total number of subcarriers N = 128 over a 1-MHz band. The relative effective SNR difference between MC 1 (the closest MC to the MR) and MC 2, 3, and 4 are 3, 6, and 10 dB, respectively. The minimum rate requirements are chosen to be the same for all MCs, the maximal power at each MC k is pk = 50 mW, the thermal noise power

is 2n = 1011W.

We assume a Rayleigh fading. Thus, for the CDI-based allocation, the ak follow a c2 distribution with 2Lk degree of freedom, where Lk is the number of outgoing links at MC k. For MC with a single outgoing link, ak is

reduced to an exponential distribution.

We name the proposed scheme with optimal allocation at MR and MCs as full optimal resource allocation (FORA). For comparison, we also implement the following resource allocation schemes:

1. MR-based optimal resource allocation (MORA) where the MR performs the proposed optimal subcarrier assignment, but each MC performs uniform power allocation among its outgoing links.2. Full uniform resource allocation (FURA) where each MC is assigned the same number of subcarriers and transmit power at each MC is uniformly distributed over the assigned subcarriers and the active links.

We evaluate system performance in terms of sum rate, and satisfaction of minimum rate requirements.

In Figure 5, the performance of the proposed FORA is compared to that of the optimal resource allocation at MR under uniform power allocation at MCs (MORA) and the FURA. The result shows that the proposed optimal resource allocation brings significant gain over uniform resource allocation, especially for low SNRs.

Figure 6 shows the users rate for different allocation schemes when the users minimum data rate demands are constrained to Rk = 1 Mbps for all MCs. We observe that under optimal allocation, the need of all users in terms of data rate is satisfied. This is not the case under uniform allocation. With uniform allocation, there is an over-allocation for closer MCs to the MR (MCs 1 and 2) while the rate demand of farer users with bad channel conditions (MCs 3 and 4) are not satisfied.

Brah et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:19 http://jwcn.eurasipjournals.com/content/2011/1/19

Page 9 of 13

5.5

5

4.5

maximized sum rate (Mbps)

4

3.5

3

FORA MORA FURA

2.5

2

1.5

1 0 5 10 15 20 25 30

mean SNR (dB)

Figure 4 Network topology used in the simulations.

1.5

min. rate req. (Rk)

FORA MORA FURA

1

rate per MC (Mbps)

0.5

0

1 2 3 4

MC node ID (k)

Figure 5 Maximized sum rate versus mean SNR for various resource allocation schemes.

Brah et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:19 http://jwcn.eurasipjournals.com/content/2011/1/19

Page 10 of 13

Figure 6 Per mesh client rate for Rk = 1 Mbps.

5.2 Simulation results for relay networksIn all the simulations, we assume a path-loss power attenuation exponent of 2, and hence g = 1/d2. The distance d between the relay node and the receiver node varies from 0.1 to 1.

In Figure 7, the ergodic capacity achieved using the proposed power allocation scheme is compared to the one obtained with uniform power allocation (b = 0.5, d [0.1, 1]). We consider system average network power constraints of P = 10 and P = 100. It can be observed that the achieved capacity using the proposed

optimal power allocation method outperforms the capacity obtained with uniform allocation.

Figure 8 illustrates the achieved capacity using the proposed CDIT-based optimal power allocation (35) in comparison with the capacity of the CSIT-based optimal power allocation (38). The CSIT-based capacity is averaged over the same number of channel realizations Ns over which the distribution is taken to evaluate the ergodic capacity. The result shows that the gap between the average capacity and the ergodic capacity is small. Thus, even with CDIT only, optimal power allocation improves performance of relay networks.

The trade-off between reduced feedback and performance degradation of the proposed CDIT-based optimal power allocation in comparison with the perfect CSIT-based optimal power allocation is shown in Figure 9. We observe that adapting the transmission strategy to the short-term channel statistics, increases the performance but also increases the amount of feedback. However, if the transmission is adapted to the long-term channel statistics, the amount of feedback decreases significantly but with a penalty on the performance. For a CDIT-based allocation with a distribution taken over 16

7.5

7

6.5

6

Capacity (bps)

optimal PA, P=100 uniform PA, P=100 optimal PA, P=10 uniform PA, P=10

5.5

5

4.5

4

3.5

3

2.5 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Distance d

Figure 7 Maximized capacity versus distance d for CDIT-based optimal power allocation and uniform power allocation.

Brah et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:19 http://jwcn.eurasipjournals.com/content/2011/1/19

Page 11 of 13

4.4

CSITbased optimal PA CDITbased optimal PA

4.2

4

3.8

Capacity (bps)

3.6

3.4

3.2

3

2.8 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Distance d

Figure 8 Maximized capacity versus distance d for CDIT-based optimal power allocation and CSIT-based optimal power allocation.

symbol periods, the amount of feedback is reduced by93.75%, while the performance degradation in terms of capacity is less than 12%.

6 ConclusionWe have addressed constrained resource allocation problems for wireless mesh and relay networks. For mesh networks, we have formulated a distributed subcarrier allocation problem to maximize the sum rate while satisfying minimum rate demand. For relay networks, we have formulated power allocation problem to maximize the ergodic capacity under total power constraint. Both cases of perfect and statistical channel knowledge at the transmitter have been considered. We have shown how the Lambert-W function can be use to efficiently find the optimal resource allocation in closed-form. Using the Lambert-W function, resource allocation can quickly be determined since a number of popular mathematical softwares, including Maple and Matlab, contain the Lambert-W function as an optimization component. The Lambert-W function can be combined with the Lagrange dual approach to solve variety of wired and wireless resource allocation

problems without resorting to complex numerical algorithms.

AppendixAppendix A: Derivation of (8) Equation 7 can be rewritten as

ln

nk nk + k

nknk + k + 1 +

Bln 2 (1 + k)

= 0. (A:1)

Equation A.1 can be rewritten equivalently as

nknk + k e

nk nk+k

= exp

1

Bln 2 (1 + k)

(A:2)

Expression (A.2) is in the form of the Lambert-W function W(x), which is the solution to W(x)eW(x) = x.

Thus, from (A.2) we can deduce that

W exp 1

Bln 2 (1 + k)

nknk + k (A:3)

which when then solved for nk gives (8).

=

Brah et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:19 http://jwcn.eurasipjournals.com/content/2011/1/19

Page 12 of 13

30

25

performance degradation (%)

20

15

10

5

0 0 20 40 60 80 100

feedback reduction (%)

Figure 9 Trade-off between feedback reduction and performance degradation of the CDI-based allocation compared with the perfect CSIT-based allocation.

Appendix B: Derivation of (10)

Let wk(k, ) = W exp

1

Bln 2 (1 + k)

.

kwk (k, )1 + wk (k, ) ln (wk (k, ))

+

1 + k

Replacing nk in (6) by its optimal value given by (8), we get the dual function

L (k, ) =

kwk (k, )1 + wk (k, ) ln (wk (k, ))

+

1 + k

kwk (k, ) (1 + wk (k, ))2

+ 2 ln 2

B(1 + k)2

kwk (k, ) (1 + wk (k, ))3 .

(B:4)

K

k=1

kwk (k, )1 + wk (k, ) B log2

1wk (k, )

+

K

k=1k

kwk (k, )1 + wk (k, ) B log2 1wk (k, )

Rk

(B:1)

kwk (k, )1 + wk (k, ) N

.

Applying KKT optimality conditions, we set the derivative (B.4) to zero to obtain

Rk

k +

K

k=1

Equation B.1 can be rewritten as

L (k, ) =N

K

k=1kRk

Bln 2

wk

#k,

$1 + wk

#k,

ln

#wk

#k,

$$

K

k=1

kwk (k, ) 1 + wk (k, )

+

1 + k

wk

#k,

$1 + wk

ln

#wk

(B:2)

Applying (2) for n = 1 and using the property of the derivative of a composite function, we obtain the derivative of wk with respect to lk for fixed as

dwk (k, ) dk =

wk (k, ) 1 + wk (k, )

#k,

$$

+

K

k=1

(k + 1) kwk (k, )1 + wk (k, )B log2(wk(k, ))

#k,

(B:5)

+

1 + k

wk

#k,

$

#1 + wk

#k,

$$2

wk

#k,

+ 2 ln 2

B

#1 + k

$

= 0,

2 #1 + wk

#k,

$$3

ln 2 B

1(1 + k)2 . (B:3)

Using (B.3), we calculate the derivative of L(lk, ) with

respect to lk for fixed as

dL (k, )dk = Rk +

Bln 2

where k is the optimal value of lk.

Brah et al. EURASIP Journal on Wireless Communications and Networking 2011, 2011:19 http://jwcn.eurasipjournals.com/content/2011/1/19

Page 13 of 13

We see that Equation B.5 can be rewritten in the form of Equation 10.

Appendix C: Proof of Proposition 1 Let

gk,m() = k wk()

1 + wk()

where

wk() = W exp 1

Bln 2 (1 + k)

.

The derivative of wk with respect to is given by

dwk()

d =

wk()

1 + wk()

1

Bln 2 (1 + k)

. (C:1)

Using (C.1), we can calculate the derivative of gk,m()

with respect to as

dgk,m()

d =

k

wk()

1 + wk()

1

Bln 2 (1 + k)

(C:2)

$2 < 0.

#1 + wk()

Thus

dgm()

d =

K

k=1dgk,m()d < 0. (C:3)

namely, gm() is a strictly decreasing function of . This completes the proof.

AbbreviationsBS: base station; BER: bit-error-rate; CDI: channel distribution information; CSI: channel state information; cdf: cumulative distribution function; FORA: full optimal resource allocation; FURA: full uniform resource allocation; MC: mesh clients; MR: mesh router; MS: mobile station; MORA: MR-based optimal resource allocation; RS: relay station; WMNs: wireless Mesh networks; ZMCSCG: zero mean circularly symmetric complex Gaussian.

Author details

1ICTEAM Institute, Universit Catholique de Louvain, Place du Levant 2, 1348 Louvain-la-Neuve, Belgium 2SYSCOM, Universit Paris-Est, Marne la Valle, France

Competing interestsThe authors declare that they have no competing interests.

Received: 4 October 2010 Accepted: 20 June 2011 Published: 20 June 2011

References1. A Nosratinia, A Hedayat, Cooperative communication in wireless networks. IEEE Commun Mag. 42(10):7480 (2004). doi:10.1109/MCOM.2004.1341264

2. JN Laneman, D Tse, GW Wornell, Cooperative diversity in wireless networks: efficient protocols and outage behavior. IEEE Trans Inf Theory. 51(9):30623080 (2004)

3. G Kramer, M Gastpar, P Gupta, Cooperative strategies and capacity theorems for relay networks. IEEE Trans Inf Theory. 51(9):30373063 (2005). doi:10.1109/TIT.2005.853304

4. IF Akyildiz, X Wang, W Wang, Wireless mesh networks: a survey. Comput Netw ISDN Syst. 47(4):445487 (2005)

5. KD Lee, VCM Leung, Fair allocation of subcarrier and power in an OFDMA wireless mesh networks. IEEE J Sel Areas Commun. 24(11):20512060 (2006)

6. HT Cheng, W Zhuang, Novel packet-level resource allocation with effective QoS provision for Wireless Mesh Networks. IEEE Trans Wireless Commun. 8(2):694700 (2009)

7. A Host-Madsen, J Zhang, Capacity bounds and power allocation in wireless relay channel. IEEE Trans Inf Theory. 51(6):20202040 (2005). doi:10.1109/ TIT.2005.847703

8. Y Yao, X Cai, GB Giannakis, On energy efficient and optimum resource allocation of relay transmissions. IEEE Trans Wireless Commun. 4(6):29172927 (2005)

9. F Brah, J Louveaux, L Vandendorpe, CDIT-Based constrained resource allocation for mobile WiMAX systems. EURASIP J Wireless Commun Netw 2009, 18 (2009). Article ID 425367

10. D Grunduz, E Erkip, Opportunistic cooperation by dynamic resource allocation. IEEE Trans Wireless Commun. 6(4):14461454 (2007)

11. CTK Ng, AJ Goldsmith, The impact of CSI and power allocation on relay channel capacity and cooperation strategies. IEEE Trans Wireless Commun. 7(12):53805389 (2008)

12. RM Corless., et al, On the Lambert W function. Adv Comput Math. 5, 329359 (1996). doi:10.1007/BF02124750

13. N Galidakis, On an application of Lamberts W function to infinite exponentials complex variables. Elliptic Equ. 49(11):759780 (2004)

14. P Hruska, Z Chobola, L Grmela, Diode I-U curve fitting with Lambert W function. Proceedings of the IEEE International Conference on Microelectronics, Belgrade. 468471 (2006)

15. P Sengupta, The Lambert-W function and solutions to Keplers equation. Clestial Mech Dyn Astron. 99(1):1322 (2007). doi:10.1007/s10569-007-9085-6

16. RL Graham, DE Knuth, O Patashnik, Concrete Mathematics: A Foundation for Computer Sciences,, 2nd edn. (Addison-Wesley, Reading, 1994)

17. S Boyd, L Vandenberghe, Convex Optimization. (Cambridge University Press, Cambridge, 2004)

doi:10.1186/1687-1499-2011-19Cite this article as: Brah et al.: On the Lambert-W function for constrained resource allocation in cooperative networks. EURASIP Journal on Wireless Communications and Networking 2011 2011:19.

Submit your manuscript to a journal and benet from:

7 Convenient online submission7 Rigorous peer review7 Immediate publication on acceptance7 Open access: articles freely available onlihttp://www.springeropen.com/

Web End =ne 7 High visibility within the eld7 Retaining the copyright to your article

Submit your next manuscript at 7 http://www.springeropen.com/

Web End =springeropen.com