Aug 18, 2009 - Tel/Fax: +493031002-860/-863, e-mail: {giovanidis, stanczak} @ hhi.de and with the ..... network, hence will be able to provide unrelia...

0 downloads 0 Views 945KB Size

Stability and Distributed Power Control in MANETs with Outages and Retransmissions arXiv:0908.2542v1 [cs.NI] 18 Aug 2009

Anastasios Giovanidis, Member, IEEE and Sławomir Sta´nczak, Member, IEEE

Abstract In the current work the effects of hop-by-hop packet loss and retransmissions via ARQ protocols are investigated within a Mobile Ad-hoc NET-work (MANET). Errors occur due to outages and a success probability function is related to each link, which can be controlled by power and rate allocation. We first derive the expression for the network’s capacity region, where the success function plays a critical role. Properties of the latter as well as the related maximum goodput function are presented and proved. A Network Utility Maximization problem (NUM) with stability constraints is further formulated which decomposes into (a) the input rate control problem and (b) the scheduling problem. Under certain assumptions problem (b) is relaxed to a weighted sum maximization problem with number of summants equal to the number of nodes. This further allows the formulation of a noncooperative game where each node decides independently over its transmitting power through a chosen link. Use of supermodular game theory suggests a price based algorithm that converges to a power allocation satisfying the necessary optimality conditions of (b). Implementation issues are considered so that minimum information exchange between interfering nodes is required. Simulations illustrate that the suggested algorithm brings near optimal results. Index Terms Automatic Retransmission reQuest Protocols, Network Stability, Network Utility Maximization, Distributed Power Control, Supermodular Games

0

This research is supported by the FET Open Project - FP6 - IST-034413 NetReFound.

Part of this work has been presented during the 5th Int. Workshop on Resource Allocation, Cooperation and Competition in Wireless Networks (RAWNET/WNC3), Seoul, Korea, June 2009 (part of WiOpt’09). The authors are with the Fraunhofer German-Sino Mobile Communications Lab, Heinrich-Hertz-Institut, Einsteinufer 37, D-10587 Berlin, Germany. Tel/Fax: +493031002-860/-863, e-mail: {giovanidis, stanczak} @ hhi.de and with the Technical University of Berlin, Heinrich Hertz Chair for Mobile Communications, Werner-von-Siemens-Bau (HFT 6), Einsteinufer 25, D-10587 Berlin, Germany.

2

I. I NTRODUCTION The current work considers a Mobile Ad-hoc NETwork (MANET) where data flows entering from a set of source nodes should be routed to their destinations. In such networks a major concern is the maximum set of incoming rates that can be supported, since interference is the bottleneck. If a utility function is related to each incoming flow a very interesting problem is to maximize the sum of all utilities under the constraint that the queues of all nodes remain stable. Such problems have been addressed in [1], [2], [3], [4], [5] and algorithms that optimally adapt the incoming rates and the transmission powers of each node have been suggested. In the current work we are interested in bringing these models a step further and investigate how the stability regions and the optimal policies for congestion control, routing and power allocation vary, when the queues of each node use ARQ protocols to repeat transmissions of erroneous packets due to outages. In the current literature, investigations already addressing the network utility maximization (NUM) problem with erroneous transmissions through the links consider mainly fixed routing. In [6] the model does not consider queueing aspects and a NUM problem with rate-outage constraints per link is approximately solved. In [7] the effect of end-to-end error probability is included in the utility of each source. The same problem with average power and reliability requirements is posed and algorithmically solved in [8]. Furthermore, in [9] a single hop ad-hoc network with outages is considered where a solution for joint admission control, rate and power allocation is derived based on a stochastic game formulation. Other contributions that investigate the effect of retransmissions in MANETs incorporating Random Access MAC protocols include [10], [11]. Motivated by a comment in [12] where it is stated that "in practical communication systems, the link capacity should be defined appropriately, taking packet loss and retransmissions into account, hence the flow conservation law holds for goodputs instead of rates", and after a presentation of the model under study in Section II, we derive in Section III the goodput capacity region. The success probability for the transmission over a wireless link depends on the entire power allocation and the scheduled transmission rate. We constrain our investigations to functions with specific properties presented in section IV, where it is shown that these also hold for the expression with Rayleigh fading [13]. The NUM problem naturally decomposes in Section V into the input rate control and the scheduling problem. At this point a major challenge is to achieve a decentralized solution of the second problem. This is always possible of course for the case of parallel channels (see also [12] and [14]). Algorithmic suggestions can be found in [2] for zero-full power allocations and in [15] by solving a maximum weighted matching problem over a conflict graph. In our work fully distributed implementation is achieved by approaching the second problem with the arsenal of supermodular game theory in section VI - an idea appearing in [16] and [17] - and result to the suggestion of a price based algortithm in

3

VI.D and VI.E that achieves almost optimal solutions with minimum information exchange between the nodes. Simulation results are finally presented in section VII. II. M ODEL

UNDER

S TUDY

We consider a wireless network consisting of N nodes N = {1, . . . , N}, while L is the set of all possible L = N · (N − 1) links. The time is divided into slots of equal duration T (normalized to 1) and t = {0, 1, . . .} is the time index. Data flows enter the network at source nodes and are removed at destination nodes D = {1, . . . , D}. The set of data flows (commodity flows) injected into the network at a source node with a predefined destination is denoted by S = {1, . . . , S}. The routes of the data flows through the network are not fixed. Furthermore, each link l ∈ L is characterized by an origin node b (l) (begin) and an end node e (l) (end). At each node n, a total of D buffers - one for each commodity flow - are reserved (see also Fig.1). In the general case investigated, each node n ∈ N chooses at slot t a power pl (t) as well as a rate µl (t) to transmit data through link l, as long as n = b (l). The total transmission rate of packets through link l at some time slot t is the sum of the transmission rates of the individual commodities sharing P d d the link meaning µl (t) = D d=1 µl (t). Scheduled packets of variable length µl (t) for each commodity d are combined into a common packet of length µl (t) and sent through the link. The resulting long packet may be received at node e (l) with errors due to fading and interference. The probability of N ·(N −1)

successful transmission is then a real valued function q (~p, µ) : R+ power allocation at slot t, p~ (t) ∈ Π ⊆

× M → [0, 1] of the entire

N ·(N −1) R+

and the scheduled rate µl (t). The set of all possible P scheduling rates is denoted by M. The nodes have power restrictions, e.g. ∀n, l:n=b(l) pl (t) ≤ Pn and Π is the convex compact set of all feasible power allocations.

Examples of such success probability functions for flat block-fading channels can be found using the outage probability definition [18]. Given an SINRl threshold value γ (µl ) = eµl − 1 of link l (we often simply write γl := γ (µl )) Gll Fll pl 2 j6=l Glj Flj pj + σe(l)

ql (~p, µl ) = P (SINRl (~p) ≥ eµl − 1) ,

SINRl (~p) = P

(1)

where Ylj stands for Yb(j)e(l) , µl is the scheduled transmission rate through the link, Gb(j)e(l) is the slow varying path gain and Fb(j)e(l) is the associated flat fading component of the channel. For the case of Rayleigh/Rayleigh fading (meaning Rayleigh slow fading for both the desired and interference signals), a closed form expression of (1) can be found in [13] and [19]

ql (~p, µl ) = exp

−σ 2 γl Gll pl

Y j6=l

γl Glj pj 1+ Gll pl

−1

.

(2)

4

Observe that the success functions used imply that only the channel fast fading statistics are known and the nodes have no other instantaneous channel state information (CSI) over the fading gains, except possibly - the slow varying path gains. The actual amount of data transmitted through each link equals µl (t) · Xl (t). Xl (t) is a binary random variable which equals 1 for success (with prob. ql ) and 0 for failure (with prob. 1 − ql ). The expected transmission rate through link l is then

gl (~p, µl ) := µl · ql (~p, µl )

(3)

and is called the goodput of link l [20], [21]. Furthermore, in the analysis that follows we often encounter a quantity called maximum goodput defined as (see [20] and [22] for parallel Rayleigh fading channels)

gl (~p) = max µl · ql (~p, µl ) .

(4)

µl ∈M

In case a packet of length µl (t) is received at node e (l) with errors, we assume that this can always be detected during decoding. When reception is correct an ACK is fed back otherwise a NAK signal is transmitted to b (l) via a reliable zero-delay wireless feedback link. In the latter case the packets of all transmitted commodities are then not removed from the buffer but wait for a future retransmission (Stop-and-Wait ARQ) under some new scheduling decision. The queue evolution for each node n and commodity flow d at slot t, is given by

udn (t + 1) = udn (t) −

X

k:n=b(k)

+

µdk (t) Xk (t) +

X

µdl (t) Xl (t) + αnd (t + 1) .

(5)

l:n=e(l)

The success probability of the transmission through link l is equal for all commodities d, since it P depends on the sum rate µl . In the expression (5), k:n=b(k) µdk (t) Xk (t) is the actual outgoing data P ("actual" meaning "error free") from node n, l:n=e(l) µdl (t) Xl (t) is the actual incoming data from

links l ∈ L : n = e (l), n 6= d and αnd (t + 1) is the amount of commodity d bits arriving exogenously

to the network at node n during t. We associate each incoming flow to the network at node n with destination d ∈ D, αnd = αs , with a utility function Us : R+ → R+ . The utility function takes as argument the average incoming data rate E (αs ) = xs and is non-decreasing, strictly concave and continuously differentiable over the range xs ≥ 0 (elastic traffic, [23]). The utilities describe the satisfaction received by transmitting data from node s ∈ S to d ∈ D. The aim here is to find an incoming rate vector ~x = (x1 , . . . , xS ) to maximize the sum of the utilities P s∈S Us (xs ) subject to the constraint that the system remains stable and furthermore explicitly provide

5

the stabilizing scheduling policy ∀~x ∈ Λ. Λ denotes the capacity region of the system, the largest set of ~x for which the system remains stable. Formally we write

max

X

Us (xs ) subject to ~x ∈ Λ.

(6)

s∈S

III. N ETWORK C APACITY R EGION

AND

VARIATIONS

WITH

D ROPPING PACKET D ECISIONS

The problem posed so far is similar to the models investigated in [2], [3], [4] and [15]. Due to the occurence of errors and the use of retransmissions, the capacity region of the model under investigation is definitely reduced and has a different expression compared to the works mentioned. Theorem 1 The capacity region Λ of the wireless network under study is the set of all non-negative d∈D vectors ~x = (x1 , . . . , xS ) such that there exist multicommodity goodput flow variables gld l∈L , satisfying • • •

gld ≥ 0, ∀l ∈ L, d ∈ D and gld = 0 if e (l) = d P P ∀n ∈ N , d ∈ D: l:e(l)=n gld + xdn ≤ k:b(k)=n gkd P d ˆ and g = {gl } ∈ Γ, where Γ = co Γ d∈D gl ≤ gl , ~

[ N ·(N −1) ˆ= Γ ~g ∈ R+ : ∀l ∈ L, gl ≤ µ ¯l (~p) · ql (~p, µ ¯ l (~p)) , µ ¯ l (~p) = arg max µl · ql (~p, µl ) . p ~∈Π

µl ∈M

(7)

Proof: Similar to the derivation of the network capacity region in [2] and can be found in [24]. d∈D In the above gld l∈L is the D · N · (N − 1) size vector of goodput flow variables for all commodities

through the network. An optimal policy achieving stability for all vectors within Λ is a variation of the

well-known backpressure policy [1], [2] where goodputs replace the rate vectors. This is named here goodput backpressure policy. We further denote with Γ the goodput region of the network, which equals ˆ given in (7). Comparing this region to the ones appearing in [2] and [14] the convex hull (co) of Γ the rate-power mapping rl (~p) = log (1 + SINRl (~p)) is replaced here by the maximum goodput-power mapping gl (~p). Let us now assume that the nodes can decide, in addition to the transmission power pl and rate µl over the link l ∈ L : n = b (l), whether the possibly erroneous packet at time slot t should be dropped or should be held in the node’s queues and wait to be retransmitted at the next time slot t + 1. We use the binary decision variable Al (t) taking values Al (t) = 0 for dropping decision and Al (t) = 1 for a decision to continue. The single queue evolution will be the same as in (5) where Xl (and similarly

6

Xk ) should be replaced by the expression 1 − Al (t) (1 − Xl (t)) which equals Xl (t) when Al (t) = 1 and 1 when Al (t) = 0. If the decisions on dropping are randomized, with a fixed probability of dropping per link equal to 1 − δl ∈ [0, 1] (and hence EAl (t) = δl ), the network capacity region Λ~δ , ~δ = (δ1 , . . . , δL ), will be the ˆ In this case we have that same as in Theorem 1 with a modification on the region Γ.

ˆ~ = Γ δ

o [n N ·(N −1) δl δl ¯l ~g ∈ R+ : ∀l ∈ L, gl ≤ µ ¯l 1 − δl · 1 − ql p~, µ

(8)

p ~∈Π

¯l (~p, δl ) = arg maxµl ∈M µl · (1 − δl · (1 − ql (~p, µl ))). Choice of the vector ~δ = ~1 := (1, . . . , 1) µ ¯δl l := µ results in the region of Theorem 1 where no dropping takes place, while for ~δ = ~0 := (0, . . . , 0), dropping always takes place after an erroneous transmission and this provides the maximum network ˆ ~ equal to capacity region with Γ δ

n o N ·(N −1) ∗ ˆ ~ ~ = ~g ∈ R+ Γ : ∀l ∈ L, g ≤ µ l l δ=0

(9)

where µ∗l = arg maxµl ∈M µl is the maximum allowable transmission rate per link. We can then obtain different regions Λ~δ between these two extremes by varying the dropping probabilities per link. To understand why this is important suppose that a network user transmitting a data flow with source node s ∈ S has a higher data rate than that offered by the actual error free network capacity region Λ~δ=~1 . We may then vary the vector ~δ so that the network will fit the requirements of the user. Of course the average rate of correctly transmitted packets through the network will not change. What will happen is that, instead of removing part of the user’s packets at entering the network (admission control), the network will offer per link at least one chance for all packets to be correctly transmitted through the network, hence will be able to provide unreliable service to the entire required high data rate, with index of reliablity ~δ. IV. P ROPERTIES

OF THE SUCCESS FUNCTION AND THE MAXIMUM GOODPUT FUNCTION

The success probability function ql (~p, µl ) for transmission over link l ∈ L considered in this work, has the following properties1 .

1

•

P.1 ql is strictly increasing in pl and the log of the function is concave in pl

•

P.2 ql is strictly decreasing and convex in pk , ∀k 6= l, k ∈ L

•

P.3 ql is strictly decreasing in µl

The game-theoretic notation ql (pl , p ~−l , µl ) is often used, where ~ p−l is the entire power vector excluding the l-th element pl .

7

•

P.4 The log of the function has increasing differences for the pair of variables (pl , µl ) meaning that − log ql pl , p~−l , µ+ log ql p+ p−l , µl − log ql (pl , ~p−l , µl ) ≤ log ql p+ p−l , µ+ l l ,~ l l ,~

(10)

+ where p+ l ≥ pl and µl ≥ µl . •

P.5 The log of the function has increasing differences for each pair of variables (pl , pj ) , ∀j 6= l. The differences are constant for all pairs (pi , pj ), where i 6= j and i, j ∈ L\ {l}.

The last property actually implies - using [25, Corollary 2.6.1] - that the function is log-supermodular. By property P.4 a positive change on the transmission power pl has a greater impact on the increase of the (logarithm of the) success probability, the higher the rate of transmission. If we e.g. transmit with 16-QAM modulation, an increase of power by ∆pl > 0 will increase log q much more than in the case of transmission with BPSK. Theorem 2 The success probability function for the Rayleigh/Rayleigh fading case, given in (2) satisfies properties P.1-P.5. Proof: For the proof, the expressions (11) - (15) of first and second order partial derivatives are required. Specifically, from (11) and (12) the function is increasing in pl and decreasing in pj (strictly if pl ≥ Plmin > 0 and same for j). From (14) the logarithm of the function is concave in pl . The convexity in P.2 comes directly from the partial derivative of (12) over pj which is easily shown to be positive. P.3 is shown in (13), whereas P.4 comes directly by derivating (13) w.r.t. pl . Finally, P.5 is a direct consequence of the fact that - in (15) -

∂ 2 log ql (~ p,µl ) ∂pl ∂pj

∂ql (pl , ~p−l , µl ) = ql (pl , ~p−l , µl ) · ∂pl ∂ql (pl , ~p−l , µl ) = ∂pj

≥ 0 and " σ2 γl (µl ) Gll p2l

∂ 2 log ql (~ p,µl ) ∂pi ∂pj

+

−ql (pl , ~p−l , µl ) ·

1

P

j6=l

∂ 2 log ql (pl , p~−l , µl ) = ∂pl ∂pj

2 − 2σGγlllp(µ3 l ) l

−

P

+pj

eµl Glj pj Gll pl +γl (µl )Glj pj

2pl Gll γl (µl )Gljp j

j6=l „

Gll p2 l γl (µl )Glj pj

(

)

Gll pl γl (µl )Glj

+pj

«2

+1

+pl

≥0

(11)

≤0

(12)

i

≤0

(13)

≤0

(14)

≥ 0.

(15)

+pl

1

Gll γl µl Glj

„

Gll p2 l γl (µl )Glj pj

Gll pl γl (µl )Glj

h 2µ P ∂ql (pl , p~−l , µl ) e l = ql (pl , p~−l , µl ) · −σ − j6=l Gll pl ∂µl

∂ 2 log ql (pl , p~−l , µl ) = ∂p2l

= 0 (see [25, p.42]). #

«2

Using the above properties we can derive important properties for the maximum goodput function in (4), which as seen in (7) plays a critical role in the definition of the system capacity region.

8

Theorem 3 If the success probability function satisfies P.1-P.5 then the maximum goodput function in (4) has the following properties (where µ¯l (~p) = arg maxµl ∈M µl ql (~p, µl )) •

P’.1 gl (~p) is strictly increasing in pl

•

P’.2 gl (~p) is strictly decreasing and convex in pk , ∀k 6= l

•

P’.3 µ¯l (~p) is non-decreasing in pl

•

P’.4 µ¯l (~p) is non-increasing in pk , ∀k 6= l Proof: Proofs of P’.1-P’.4 are found in Appendix A.

The above properties are illustrated in Fig.2 and Fig.3 using a success probability function with the expression in (2) for the 2-user Rayleigh/Rayleigh fading case. These will not be directly used in what follows but are rather useful for the characterisation of the stability region and the optimal scheduling policies of such systems. Examples of the goodput region are shown in figures Fig.4 and Fig.5 for two simple network topologies: 2 transmitting nodes with 1 receiving, 1 transmitting node with 2 receiving. Remark 1 In economic terms, we can interpret the success probability function ql as the demand of product l in a market of L firms. In this framework µl is the product’s price and gl is the firm’s revenue. Then gl (pl , p~−l , µl ) = µl ×ql (pl , ~p−l , µl ) is firm’s l (revenue) = (price)×(demand). The demand is by P.3 a decreasing function of the price, is increasing by P.1 in pl and decreasing by P.2 in pk , k 6= l. Then pl can be interpreted as a variable valuating product’s l quality (or maybe the money spent by firm l in advertisement) and pk as the quality (or money for advertisement) of products from competitors k 6= l. Then the maximum goodput gl (~p) is the maximum revenue that a firm l can obtain by choosing an optimal price µ ¯l (~p), given a vector ~p. By properties P’.1 and P’.2 the maximum revenue is increasing in pl and decreasing in pk , k 6= l, whereas by P’.3 and P’.4 the optimal price is also increasing in pl and decreasing in pk . Notice that if in P.4 log-supermodularity would be replaced by log-submodularity the optimal price would be a decreasing function of pl . V. NUM P ROBLEM D UAL D ECOMPOSITION The utility maximization problem in (6) given the network capacity region in Th. 1 takes the form maxxs ≥0,

gld ≥0

subject to

P

s∈S

Us (xs )

gld + xdn ≤ ˆ =Γ ~g ∈ co Γ P

l:e(l)=n

P

k:b(k)=n

gkd ∀n, d

ˆ is given in (7). The constraint set is convex and compact (see [26, Appendix 4.C]), the objective and Γ function is concave and Slater’s condition can be shown to hold, hence strong duality also holds and

9

known distributed algorithms, like the one following, can solve the Lagrange dual problem min~λ≥0 L ~λ d ~ which involves the (N · D)-vector associated with the primal λof dual variables λn . The Lagrangian NUM problem is denoted by L ~x, ~λ while the dual function L ~λ yields, due to the linearity of the differential operator (see [23], [4], [15])

X X X X λdn gkd − gld L ~λ = max {Us (xs ) − λs xs } + max s∈S

xs ≥0

~g ∈Γ

n,d

k:b(k)=n

l:e(l)=n

and λs = λdn , xs = xdn for the flow s with source node n and destination d. We can interpret λdn as the implicit cost per pair (n, d). Thus, the NUM problem is decomposed into: (a) The input rate control problem

Prob.1 :

X s∈S

max {Us (xs ) − λs xs }

(16)

xs ≥0

solved for each commodity flow at the incoming nodes independently xs = Us´ −1 (λs ). Observe that by assumption Us´(xs ) is continuous and monotone decreasing in R+ (thus a bijection) and the inverse of the function exists. Since Us (xs ) is strictly concave the solution is unique for each λs . (b) The scheduling problem

Prob.2 : max~g∈Γ

d n,d λn

P

P

d k:b(k)=n gk −

d l:e(l)=n gl

P

= max ~g ∈Γ

≤ max ~ g ∈Γ

X

gld · λdb(l) − λde(l)

l,d

X

wl · gl

(17)

l

Through each link l the commodity d∗ = arg maxd λdb(l) − λde(l) is scheduled to be routed with goodput d d rate gl and wl = maxd λb(l) − λe(l) , 0 . This is the well known backpressure policy [1]. The solution

of (17) further provides the optimal multicommodity goodput flow variables {gl∗ }. The optimal solution described is very similar to the DRPC policy in [2]. If we can solve (17) distributedly, then algorithms can be provided, that solve the dual problem min L ~λ also in a distributed manner, and converge to the optimal average incoming rate vector ~x∗ and average price vector ~λ∗ . The dual problem can be solved by the subgradient method. The prices λd n

for each node-destination pair (n, d) are step-wise adjusted by

λdn (t + 1) = [λdn (t) + γt · (xdn (t) −

X

k:b(k)=n

gkd (t) +

X

l:e(l)=n

gld (t))]+ .

(18)

10

In the above γt is a positive scalar stepsize, [. . .]+ denotes the projection onto the set R+ and for each t the values xdn (t) and gnd (t) are calculated by solving problems (16) and (17) respectively and using prices ~λ (t). As noted in the aforementioned works, in practice a constant stepsize is used for t→∞

implementation purposes, although the convergence of the algorithm is guaranteed for γt → 0. For constant stepsizes statistical convergence to ~λ∗ , ~x∗ is guaranteed as shown in [15, Def.1,Th.2]. VI. T HE S CHEDULING P ROBLEM A. Relaxation As was mentioned previously it is very important that the problem in (17) is solved in a distributed manner. To this aim the theory of supermodular games can be used. We make the following two assumptions 1) Assumption 1: Each origin node chooses a single end node to transmit 2) Assumption 2: Each node can transmit and receive at the same time 3) Assumption 3: Fixed scheduled rates per link µl are considered. Specifically the last assumption constraints the generality of the initial model but is necessary for the approach that follows. Variable scheduled rates would involve a joint maximization over power allocation and rates. This would complicate the analysis, but is a rather important topic for future research. The maximization in (17) can be written as

max ~g ∈Γ

X

(a)

wl · gl = max

l

ˆ ~g ∈Γ

X

wl · gl = max p ~∈Π

l

(b)

=

X

X

wl · µl ql (~p, µl )

n:n=b(l) n:n=e(l)

max

pn ∈[Pnmin ,Pnmax ]

X

wn · µn qn (~p, µn )

(19)

n:n=b(l)

where (a) comes from the fact that the objective function is linear and the supporting hyperplanes to the n o ˆ and Γ = co Γ ˆ are the same, while (b) from Assumption 1. The latter simplifies the problem sets Γ

to a weighted sum maximization problem with number of summants equal to the number of nodes and allows the formulation of a noncooperative game in the following subsections, where each node decides independently over its transmitting power through a single chosen link. The capacity region of the system in Theorem 1 is of course reduced. An important question is how each node choses the optimal single link to transmit. The number of links with node n as origin are all links {l ∈ L : n = b (l) & wl > 0}. This is the

connectivity set of node n. The optimal link is obviously the one which provides maximum weighted goodput to the above summation, for a given power allocation pn ∈ Pnmin, Pnmax .

11

Departing here briefly from the main line of the analysis, we end this subsection with a heuristic suggestion for an almost optimal choice of a single receiver node, using low information exchange between the network nodes. Applying Markov’s inequality in (1) ωl µ l E (SINRl (~p)) . eµl − 1 Suppose that the end node e (l) of each link l measures the received level of interference, the latter ωl µl P (SINRl (~p) ≥ eµl − 1) ≤

denoted by Il . This is not any more a random variable with unknown realization but rather a known deterministic quantity. The right handside then reduces to Gl,l pl ωl µl E (Gl,l Fl,l pl ) ωµ = µl l . − 1 I + σ2 e l − 1 I + σ2

eµl

l

e(l)

l

(20)

e(l)

This is an upper bound on the actual error probability. The process of the sub-optimal choice then is as follows. Each destination node of links belonging to the connectivity set of node n, informs the origin 2 node over Il + σe(l) and afterwards n chooses to transmit over the link with the maximum ratio (20),

since Gl,l , ωl and µl are known to n. An alternative way to choose a single receiver node could be by assigning to each element of the connectivity set a probability, with sum equal to one per transmitting node, and the choice will then be a random process. B. Optimality conditions Using the Karush-Kuhn-Tucker (KKT) optimality conditions and observing that the active inequality constraint gradients are linearly independent [27, pp.315-317] all feasible vectors p~ are regular and we have the following necessary conditions for ~p∗ to be a local maximizer of the objective function in (19).

0=

∂qn (~p∗ , µn ) X ∂qm (~p∗ , µm ) ∂ L p~∗ , ~ν l , ~ν u = νnl − νnu + ωn · µn + ωm · µ m ∂pn ∂pn ∂pn m6=n

(21)

for each n and the complementary slackness conditions satisfy νnl · Pnmin − p∗n = 0 & νnu · (p∗n − Pnmax ) = 0 (22) L ~p∗ , ~ν l , ~ν u is the Lagrangian of the problem in (19). The conditions are only necessary and not

sufficient. We make here the remark that if the objective function were concave, the dual gap would be zero and any local maximizer would also be global for the problem at hand. In this case the conditions would also be sufficient. Unfortunately this generaly does not hold for the specific objective function.

12

Divide (21) and (22) by qn (~p∗ , µn ) (which is definitely positive if we choose Pnmin > 0, ∀n ∈ N ) and then - approching the problem similarly to [16] - set

0 ≥ ωm · µ m

∂qm (~p, µm ) 1 πm,n (~p) = ∂pn qn (~p, µn ) qn (~p, µn ) = π ˆm,n (~p)

(23) (24)

and for the Lagrange multipliers νˆnu =

νnu ≥ 0 & νˆnl = qn (~p∗ , µn )

l νn qn (~ p∗ ,µn )

≥ 0.

(25)

With the above substitutions the per node condition in (21) is rewritten as ∂qn (~p∗ , µn ) X 1 + π ˆm,n (~p∗ ) = νˆnu − νˆnl . ωn · µ n qn (~p∗ , µn ) ∂pn m6=n

(26)

Then (26) with the related complementary slackness conditions are the necessary and sufficient conditions for p∗n to be the global maximizer of the problem

maxpn ωn µn log qn pn ; ~p∗−n , µn

+ pn

P

m6=n

π ˆm,n (~p∗ )

(27)

since by property P.1 of the success function, log qn (~p, µn ) is concave in pn , the constraint set pn ∈ min max Pn , Pn is convex and compact and Slater’s condition holds true. This explains now why the division in (23) and (25) was required. C. A Supermodular Game If we view −ˆ πm,n (~p) as the price charged by user m to user n for affecting its goodput by creating interference, we can approach the solution to the optimal power allocation problem in a distributed fashion with the use of game theory. We denote the noncooperative game by the triple G = (N , Π, {Jn (·) , n ∈ N }) where N are the players, Π is the set of feasible joint strategies and Jn is the payoff function for user n. We distinguish between two types of players. First, the power players who belong to the set N p , each one of which represents a node and the set of feasible joint strategies Πp is identical to the set Π of feasible power allocations. Their payoff function equals

Jn (pn ; ~p−n , (ˆ πm,n )) = ωn µn log (qn (pn ; ~p−n , µn )) + pn ·

X

m6=n

π ˆm,n

(28)

13

We often set cn :=

P

m6=n

π ˆm,n to emphasize the dependence of Jn on the sum instead of the individual

prices. The best response correspondence for player n is the set

Yn (~p−n ) = arg

max

pn ∈Πn (~ p−n )

Jn (pn ; ~p−n , (ˆ πm,n ))

(29)

where Πn (~p−n ) = {pn : (pn , ~p−n ) ∈ Πp }. Second, the price players who belong to the set N pr := {(m, n) : m 6= n, m, n ∈ N } with cardinality N × (N − 1). The feasible set of strategies for player (m, n) is

Πpr m,n

=

π ˆm,n ∈ min π ˆm,n (~p) , 0 p ~∈Π

(30)

where π ˆm,n (~p) is given in (24). The best response for a price player is denoted by (following [16])

pr Ym,n = arg

maxpr − (ˆ πm,n − π ˆm,n (~p))2

π ˆm,n ∈Πm,n

(31)

and Πpr = Π(2,1) , . . . , Π(N −1,N ) is the joint feasible set.

A Nash equilibrium (NE) for the game G is defined as the set of power vectors p~e = (pe1 , . . . , peN ) e e e e and price vectors π ˆ~e = π ˆ2,1 ,...,π ˆn,1 ,...,π ˆ1,n ,...,π ˆn−1,n with the property for every n, m ∈ N p and

every (m, n) ∈ N pr

e e e Jn pen , ~pe−n , (ˆ πm,n ) ≥ Jn pn , ~pe−n , (ˆ πm,n ) , & π ˆm,n =π ˆm,n (~pe ) , ∀pn ∈ Πn p~e−n

(32)

Hence pen belongs to the best response correspondence of player n, ∀n ∈ N p , given the equilibrium e prices, whereas π ˆm,n belongs to the best response correspondence of player (m, n) ∈ N pr given the

equilibrium powers. The existence and uniqueness of the NE when the prices do not take part as players in the game has been proven in [28, Th.III.1] under mild assumptions on the problem parameters usually satisfied in practice. In our case however with N +N ×(N − 1) = N 2 players the uniqueness of a Nash equilibrium is not guaranteed. We can however make use of the theory of supermodular games, exploiting the structure of the payoff function in (28) to find algorithms that converge to one of the Nash Equilibria. We first give the definition of a supermodular game from Topkis [25] Definition 1 A noncooperative game with N players {N , Π, {fn : n ∈ N }}, each having strategy xn belonging to the feasible set of strategies Πn (~x−n ), is supermodular if the set Π of feasible joint

14

strategies is a sublattice of RN and for each n the payoff function fn is supermodular in player n’s strategy xn and has increasing differences for all pairs (xi , xj ) ∈ Πi × Πj , i 6= j, i, j ∈ N . Theorem 4 The noncooperative game with N power players and N × (N − 1) price players is a supermodular game [25, p.178]. Furthermore, the set of equilibrium points is a nonempty complete lattice and a greatest and least equilibrium point exist. Proof: See Appendix B. After proving that the problem at hand has the desired properties so that supermodular game theory can be applied we prove in the following that the Nash Equilibria of the game are exactly the power allocations that satisfy the KKT necessary optimality conditions of the original sum weighted maximization problem. Theorem 5 Under the condition that ∀n, Pnmin > 0, a power vector p~e is a Nash Equilibrium of the supermodular power-price game if and only if it satisfies the necessary optimality conditions (21)-(22). Proof: See Appendix C. The above theorem is rather important because it shows that the formulated game leads to one of the solutions of the scheduling problem. If the objective function in (19) is concave then the NE is also unique and the game converges to the unique global maximizer. The suboptimality of the proposed scheme in the current work thus lies solely on the fact that the KKT conditions are only necessary but not sufficient. If we can define the region of Π for which the objective function is concave and restrict the feasible power allocations to that, the suggested distributed solution is the optimal one. This can be a topic for future investigations. D. The Scheduling Algorithm In the current paragraph we provide an algorithm which updates for each player the power allocation pn and the price πm,n . Starting from any initial point within the joint feasible region, the algorithm will eventually converge to a NE bounded component-wise by the greatest and least NE. It is related to the Round-Robin optimization for supermodular games [25, Ch. 4.3.1], versions of which are suggested in [16] and [17]. The algorithm has two phases for each iteration t and is given in Table I. The power update phase (t)

calculates the best response for each user n by (28) given fixed prices π ˆm,n and the opponents’ decisions (t)

p~−n . (t)

During the price update phase each user m calculates (N − 1) new prices πm,n (without the hat) by (t)

(23) given the updated power vector. Then all users m 6= n communicate the values πm,n to user n, (t+1)

who divides their sum by qn (~p, µn ) to form the new sum price cn

for the next power update phase.

15

Observe that for each iteration, user n should know: (a) Its own rate of transmission µn (which defines qn ) and weight ωn , (b) the power profile of the other users ~p−n , (c) the prices πm,n communicated by the interfering users and (d) the slow fading coefficients Gm,n which depend on the distance between the nodes. E. Implementation Issues Considering implementation issues of the algorithm, information (b) and (c) should be communicated to node n, while (d) should be globally known. Notice that communicating the information over the power profile of the interfering users will violate the distributed nature of the algorithm. Instead of the power vector ~p−n however, it suffices for each user to measure the current level of interference P In = m6=n Gmn Fmn pm in which case we write Gnn Fnn pn ≥ γn (µn ) 2 In + σe(l)

qˆn (pn , In , µn ) = P

!

2 γ (µ ) − I + σ n n n e(l) Rayl. = exp Gnn pn

where l : b(l) = n and the second equality holds for Rayleigh fading. The payoff function will change accordingly. In the price update phase observe that the partial derivative of qˆm with respect to pn will be given by πm,n ∂ qˆm (pm , Im , µm ) ∂ qˆm (pm , Im , µm ) ∂Im φm (pm , Im ) = = =− Gnm Fnm (33) ωm µ m ∂pn ∂Im ∂pn ωm µ m The new values φm can be computed by each user m and are independent of the destination user n.

γm (µm ) φm (pm , Im ) = ωm µm qˆm (pm , Im , µm ) Gmm pm In the form (33) observe that the actual realization of the random variable Fnm appears. Remember that Rayl.

Fnm is the fast fading channel power coefficient. This information is unknown. But node n is interested in the sum cn of the prices π ˆm,n (see (41)) which can be written as

cn = −

X 1 Gnm Fnm φm (pm , Im ) qn (pn ; In , µn ) m6=n

If each node m 6= n broadcasts a sequence of random symbols Sm , |Sm |2 = 1 with power the received signal at node n will be (assuming reciprocity of the channel gains)

Yn =

X

m6=n

Hnm

p

φm (pm , Im )Sm + Noise

(34) p φm (pm , Im ) (35)

16

and its power is |Yn |2 =

P

m6=n

Gnm Fnm φm (pm , Im )+σn2 . If the receiving node n divides by −qn (pn ; In , µn )

we get a noisy version of the expression in (34). The above idea is borrowed from recent works that deal with ways to use the Wireless Multiple Access Channel (MAC) in order to compute general functions of data among which is also addition [29]. The above method using power to convey information can be found specifically in [30]. From the above we realize that although the fast fading coefficients are not known to the users m that have to calculate the prices πm,n these can be revealed to the receiver n within the sum signal in (34). Finally rather important is the fact that for the implementation of the algorithm, each user m has to be aware of its received interference Im and actually calculate only a single price φm . Then in a single step during the price update phase each player/node broadcasts its price φm , while acting simultaneously as a receiver (remember Assumption 2) to obtain the channel-power-weighted sum of the prices of the other N − 1 users. The entire network topology is not any more necessary to be known to each user m, only the slow fading gain Gmm . This allows the scheduling algorithm to have as well application in cases where the topology possibly changes due to user mobility. VII. S IMULATIONS Simulation results of the proposed scheme for congestion control, routing and distributed power allocation when hop-by-hop retransmissions are taken into account are presented in Fig.6. We used a four node topology having two commodity flows with sorce node 1 and destination nodes 3 and 4 respectively. The congestion control requires the solution of the subproblems (16) and (17) respectively with prices ~λ (t). The prices are updated per node using the expression in (18). The optimal links per node are chosen at each step using (20). The scheduling problem in (19) is solved initially by brut force (left column) to provide a comparison with the results obtained when the price based algorithm is used (right column). We notice that although the uniqueness of the Nash Equilibrium cannot be guaranteed the results of the suggested algorithm considering the maximum supported incoming rate as well as the queue length (price λ1 ) are almost optimal. An important remark is that the two solutions would be exactly the same if the objective function in (19) would be concave. VIII. A PPENDIX A. Proof of Theorem 3 In the following we will neglect the dependence of functions on variables that are considered constant throughout a proof. •

+ + P’.1: Suppose p+ ¯ l := arg maxµl ∈M µl ql (pl , µl ). l > pl and let µl := arg maxµl ∈M µl ql pl , µl , and also µ Then ∀µl ∈ M

17

(a) (b) + + ≥ µl ql p+ µ+ l , µl > µl ql (pl , µl ) l ql pl , µl

•

In the above, (a) comes from the definition of µ+ l and (b) from P.1 of the success probability function. Since the inequality holds ∀µl it also holds for µl = µ ¯l , hence gl p+ , p ~ > gl (pl , p~−l ). −l l + + P’.2: For the monotonicity we proceed as above, where pk > pk , µl := arg maxµl ∈M µl ql p+ k , µl , and also µ ¯ l := arg maxµl ∈M µl ql (pk , µl ). Then ∀µl ∈ M (c)

(d)

µ ¯l ql (pk , µ ¯l ) ≥ µl ql (pk , µl ) > µl ql p+ k , µl

where (c) comes from the definition of µ+ l and (d) from the monotonicity in P.2. Since the inequality + holds ∀µl it also holds for µl = µl , hence gl p+ ~−k < gl (pk , p~−k ). k ,p (1)

(2)

For the convexity we write for pk 6= pk

(P.2) (1) (2) (1) (2) gl θpk + (1 − θ) pk = max µl ql θpk + (1 − θ) pk , µl ≤ µl n o (1) (2) (1) (2) max θµl ql pk , µl + (1 − θ) µl ql pk , µl ≤ max θµl ql pk , µl + max (1 − θ) µl ql pk , µl µl µl µl (1) (2) = θgl pk , ~p−k + (1 − θ) gl pk , p~−k b a b b a a • P’.3 Choose pl ≥ pl and denote µl := arg maxµl ∈M µl ql pl , µl , and also µl := arg maxµl ∈M µl ql (pl , µl ). By definition

µbl ql

pbl , µbl

≥

µal ql

pbl , µal

ql pbl , µal µbl ≥ ⇒ µal ql pbl , µbl

(36)

We prove the property by contradiction. Suppose that µbl < µal . From the log-supermodularity property P.4

Combining (36) and (37)

ql pbl , µal ql pbl , µbl > ql (pal , µal ) ql pal , µbl

µbl (36) ql pbl , µal (37) ql (pal , µal ) > ⇒ µbl ql pal , µbl > µal ql (pal , µal ) ≥ a b b a b µl ql pl , µl ql pl , µl

But (38) is impossible from the definition of µal := arg maxµl ∈M µl ql (pal , µl ) hence µbl ≥ µal .

(37)

(38)

18

•

(1) (1) there always exists another one P’.4: We make use of the fact that given a pair pl , µl (2) (2) (1) (2) (1) (2) (1) (1) (2) (2) = ql pl , p~−l , µl . pl , µl , with pl 6= pl and µl 6= µl such that ql pl , ~p−l , µl

This is because ∀µl ∈ M, the success probability function ql (pl , µl ) ∈ [0, 1] is strictly increasing

in pl and strictly decreasing in µl by P.1 and P.3 (here pl ∈ R+ ). Denote by µbl := arg maxµl ∈M µl ql pbk , µl , and also µal := arg maxµl ∈M µl ql (pak , µl ). Using the above fact we can write ql (pl , pak , µal ) = ql (pal , pak , µl ) and ql pl , pbk , µbl = ql pbl , pbk , µl , e.g. for some µl ≥ max µal , µbl , pal ≥ pl and pbl ≥ pl . By definition ql pal , pbk , µl ql pl , pbk , µal µbl = ≥ µal ql pl , pbk , µbl ql pbl , pbk , µl

(39)

The property is proven by contradiction.. Choose pbk ≥ pak and suppose that µbl ≥ µal ql pbl , pbk , µl ≤ ql pal , pbk , µl

(P.3)

⇔ ql pl , pbk , µbl ≤ ql pl , pbk , µal ⇔ (P.1) ⇔ pbl ≤ pal (40) From the log-supermodularity property P.5 we reach the inequality µbl ql pl , pak , µbl ≥ µal ql (pl , pak , µal ) which is impossible by the definition of µal ⇒ pbl ≤ pal is impossible ⇔ µbl ≥ µal is impossible.

B. Proof of Theorem 6 2

2

The set of joint feasible strategies Πp ×Πpr ∈ RN is a sublattice of RN . The set is also compact since for a power player n ∈ N p , pn ∈ Pnmin, Pnmax while for a price player πm,n ∈ [minp~∈Πp π ˆm,n (~p) , 0]

and the lowest endpoint of the interval is > −∞ for Pnmin ≥ ǫ > 0, ∀n (see the expression for the success probability (2) and its derivative (11). Since the set of feasible strategies for power player n is a compact subset of R1 the payoff function in (28) is supermodular in pn . We have further seen in property P.5 that the logarithm of the success probability function of user n has increasing differences for each pair (pn , pm ) , ∀m 6= n and constant differences for each pair (pm1 , pm2 ), m1 6= n, m2 6= n. Then log qn (~p, µn ) is supermodular in p~ ∈ Πp . P Observe that pn · m6=n π ˆm,n is also supermodular and by property [25, Lemma 2.6.1(b)] the sum of supermodular functions is supermodular. We reach the conclusion that Jn = ωn µn · log qn (~p, µn ) + cn pn has increasing differences in all pairs (pi , pj ) for distinct i, j ∈ N p . The expression for Jn in (28) is a valuation (has constant differences) for each pair (ˆ πi,n , π ˆj,n ), i, j 6= n. Finally for the pairs (pi , π ˆj,n ) the function has also increasing differences if i = n and is a valuation for i 6= n. Then we reach the conclusion that Jn has increasing differences for each pair (xi , xj ), i, j ∈ N p ∪ N pr . By definition 1 the game is supermodular.

19

The set of feasible joint startegies Πp × Πpr is shown to be compact. Observing that the expression in (2) and hence Jn is continuous in pn and having proven that the game is supermodular, the ’Furthermore’ part of the theorem comes from [25, Th.4.2.1]. C. Proof of Theorem 7 The ’if’ part comes directly from the way the extended supermodular game was formulated. For the ’only if’ part we argue as follows. Suppose p~e is a Nash Equilibrium of the problem. Then for each n

pen = arg maxpn ∈[Pnmin ,Pnmax]

(

= arg maxpn ∈[Pnmin ,Pnmax]

(

= arg maxpn ∈[Pnmin ,Pnmax]

(

ωn µn log qn pn ; ~pe−n , µn + pn

ωn µn log qn pn ; ~pe−n , µn ωn µn log qn pn ; ~pe−n , µn

X

m6=n

e π ˆm,n

)

ωm µm ∂qm (~pe , µm ) + pn qn (~pe , µn ) ∂pn m6=n X

)

∂qm (~pe , µm ) · qn (~pe , µn ) + pn ωm µ m ∂pn m6=n X

)

The necessary and sufficient optimality conditions for the above problem are X ∂qn pn ; p~e−n , µn ∂qm (~pe , µm ) qn (~pe , µn ) ω µ · + νnl − νnu = 0 + ωn µ n m m ∂pn qn (pn , p~e−n , µn ) m6=n ∂pn νnl · Pnmin − pn ≥ 0 & νnu · (pn − Pnmax ) ≥ 0

Since pen is the global maximizer (remember that the objective function is concave) the necessary conditions (21)-(22) of the scheduling problem are satisfied ∀n. R EFERENCES [1] L. Tassiulas and A. Ephremides. Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks. IEEE trans. on Automatic Control, 37, No. 12, Dec 1992. [2] M.J. Neely, E. Modiano, and C.E. Rohrs. Dynamic Power Allocation and Routing for Time-Varying Wireless Networks. IEEE JSAC, 23, No. 1, Jan 2005. [3] M.J. Neely, E. Modiano, and C.-P. Li. Fairness and Optimal Stochastic Control for Heterogeneous Networks. IEEE/ACM Trans. on Networking, 16, No. 2, Apr. 2008. [4] X. Lin and N.B. Shroff. Joint Rate Control and Scheduling in Multihop Wireless Networks. Proc. IEEE CDC 2004. [5] S. Stanczak, M. Wiczanowski, and H. Boche. Fundamentals of Resource Allocation in Wireless Networks: Theory and Algorithms. W. Utschick, H. Boche, R. Mathar, Foundations in Signal Processing, Communications and Networking, Springer, Second Expanded Edition ed., 2009, vol. 3, 2009. [6] J. Papandriopoulos, S. Dey, and J. Evans. Optimal and Distributed Protocols for Cross-Layer Design of Physical & Transport Layers in MANETs. IEEE/ACM Trans. on Networking. [7] J.-W. Lee, M. Chiang, and A.R. Calderbank. Price-Based Distributed Algorithms for Rate-Reliability Tradeoff in Network Utility Maximization. IEEE JSAC, 24, no. 5, May 2006.

20

[8] D. O’Neill, B.S. Thian, A. Goldsmith, and S. Boyd. Wireless NUM: Rate and Reliability Tradeoffs in Random Environments. Proc. Allerton Conference on Communication, Control, and Computing, UIUC, 2008. [9] Sara Akbarzadeh, Laura Cottatellucci, Eitan Altman, and Christian Bonnet. Distributed Communication Control Mechanisms for Ad hoc Networks. In ICC, 2009. [10] Robert J. McCabe, Nikolaos M. Freris, and P. R. Kumar. Controlled Random Access MAC for Network Utility Maximization in Wireless Networks. In CDC, 2008. [11] Ralph El-Khoury and Rachid El-Azouzi. Dynamic Retransmission Limit Scheme in MAC Layer for Routing in Multihop Ad hoc Networks. Hindawi Publishing Corporation, Journal of Computer Systems, Networks and Communications, 2008. [12] L. Xiao, M. Johansson, and S.P. Boyd. Simultaneous Routing and Resource Allocation via Dual Decomposition. IEEE Trans. on Communications, 52, no. 7, July 2004. [13] S. Kandukuri and S. Boyd. Optimal Power Control in Interference-Limited Fading Wireless Channels with Outage-Probability Specifications. IEEE Trans. on Wireless Comm., 1, No. 1, Jan. 2002. [14] M. Chiang and J. Bell. Balancing supply and demand of Bandwidth in Wireless cellular Networks: Utility Maximization over Powers and Rates. Proc. INFOCOM, 2004. [15] L. Chen, S.H. Low, M. Chiang, and J.C. Doyle. Cross-layer Congestion Control, Routing and Scheduling Design in Ad Hoc Wireless Networks. Proc. INFOCOM 2006. [16] J. Huang, R. Berry, and M.L. Honig. Distributed Interference Compensation for Wireless Networks. JSAC, 24, May 2006. [17] C. U. Saraydar, N. B. Mandayam, and D. J. Goodman. Efficient Power Control via Pricing in Wireless Data Networks. IEEE Trans. on Comm., 50, no.2, Feb. 2002. [18] A. Giovanidis, G. Wunder, H. Boche, and S. Stefanov. Optimal Control of Transmission Errors with Power Allocation and Stability in ARQ Downlink. CISS’08, Princeton, USA, mar. 2008. [19] J. Papandriopoulos, J.S. Evans, and S. Dey. Optimal power control for Rayleigh-faded multiuser systems with outage constraints. IEEE Trans. on Wireless Comm., 47, no. 6, Nov. 2005. [20] N. Ahmed and R.G. Baraniuk. Throughput Measures for Delay-Constrained Communications in Fading Channels. 41st Annual Allerton Conference on Communications, Control and Computing, Oct. 2003. [21] I. Bettesh and S. Shamai (Shitz). Optimal Power and Rate Control for Minimal Average Delay: The Single-User Case. IEEE Trans. on Inf. Theory, Sep. 2006. [22] A. Giovanidis, G. Wunder, and H. Boche. A short-term throughput measure for communications using ARQ protocols. Proc. 7th ITG Conf. on SCC, 2008. [23] F. Kelly. Charging and rate control for elastic traffic. European Transactions on Telecommunications, 8:33–37, 1997. [24] A. Giovanidis and S. Stanczak. Retransmission Aware Congestion Control and Distributed Power Allocation in MANETs. Proc. 5th Int. Workshop on Resource Allocation, Cooperation and Competition in Wireless Networks (RAWNET/WNC3), Seoul, Korea, June 2009. [25] Donald M. Topkis. Supermodularity and Complementarity. Princeton University Press, 1998. [26] M.J. Neely. Dynamic power allocation and routing for satellite and wireless networks with time varying channels. Ph.D. dissertation, LIDS, Mass. Inst. Technology, Cambridge, MA, 2003. [27] Dimitri P. Bertsekas. Nonlinear Programming. Athena Scientific. [28] T. Alpcan, T. Basar, and S. Dey. A Power Control Game Based on Outage Probabilities for Multicell Wireless Data Networks. IEEE Trans. on Wireless Communications, 5, no. 4, Apr. 2006. [29] B. Nazer and M. Gastpar. Computation over Multiple-Access Channels. IEEE Trans. on Inf. Theory, 53, no. 10, Oct. 2007. [30] M. Goldenbaum, S. Stanczak, and M. Kaliszan. On Function Computation via Wireless Sensor Multiple-Access Channels. Proc. IEEE WCNC, 2009.

21

TABLES

22

F IGURES

Fig. 1.

An example of the wireless network with a single commodity d = 4. Detail of node 3

23 Optimal Rate µ (p ,p ) vs power p

Maximum goodput g (p ,p ) vs. power p 1

1

2

1

1

1

2

1

1.6 0.7 1.4 0.6 1.2

µ = 0.8 bps 1

g1(p1,p2) = maxµ µ1 q1(p1,p2,µ1)

0.5

µ1(p1,p2)

1

0.4

2

g (p ,p )

1

1

µ = 1.2 bps 1

l

µ = 0.4 bps

0.8

1

0.3

0.6

0.2

0.4

0.1

0

0.2

0

2

4

6

8

10

12

14

16

18

0

20

0

2

4

6

8

Power p

Fig. 2.

10

12

14

16

18

20

Power p

l

1

We simulate a 2-user Rayleigh/Rayleigh fading channel with set of rates M = {0.4, 0.8, . . . , 2} and p2 = 5 Watt, P1 = 20

Watt. Properties P’.1 and P’.3 are illustrated a. Maximum Goodput g1 (p1 , p2 ) vs power p1 , b. Optimal rate µ ¯1 (p1 , p2 ) vs power p1 .

Maximum rate µ (p ,p ) vs Power p

Maximum goodput g (p ,p ) vs power p 1

1

2

2

1

1.5

1

2

2

2.5

2

1

g1(p1,p2)

µ1(p1,p2)

1.5

1 0.5

0.5

0

0

5

10

15

Power p

2

Fig. 3.

20

25

0

0

5

10

15

20

25

Power p

2

We simulate a 2-user Rayleigh/Rayleigh fading channel with set of rates M = {0.4, 0.8, . . . , 2} and p2 = 20 Watt, P1 = 25

Watt. Properties P’.2 and P’.4 are illustrated a. Maximum Goodput g1 (p1 , p2 ) vs power p2 , b. Optimal rate µ ¯1 (p1 , p2 ) vs power p2 .

24

Goodput Region Γ for a network with 2 transmitting + 1 receiving node

0.6

2

max µ q (p ,p ,µ )

0.5

µ

2

2

2

1

2

0.4

0.3

0.2

0.1

0

0

0.05

0.1

0.15

0.2

max

µ

Fig. 4.

0.25

0.3

0.35

0.4

0.45

µ q (p ,p ,µ ) 1

1

1

1

2

1

ˆ 1 and Γ1 for the network of 2 transmitters and a single receiver. The convex The 2-user Rayleigh/Rayleigh goodput region Γ

hull is shown with the dashed dot lines. For the illustration M = {0.4, 0.8, . . . , 1.8}, P1max = 2 Watt, P2max = 3 Watt and the success probability function in (2) has been used with G1,1 = G1,2 = 1, G2,2 = G2,1 = 1.

Goodput Region Γ for a network with 1 transmitting + 2 receiving nodes 1

0.9

0.8

0.6

0.5

2

maxµ q2(p1,p2,µ2)

0.7

0.4

0.3

0.2

0.1

0

0

0.1

0.2

0.3

0.4

max

µ

1

0.5

0.6

q (p ,p ,µ ), p +p ≤ P 1

1

2

1

1

0.7

0.8

0.9

1

2

ˆ 2 and Γ2 for the network consisting of 1 transmitter and 2 receivers. The convex Fig. 5. The 2-user Rayleigh/Rayleigh goodput region Γ hull is shown with the dashed dot lines. For this topology, M = {0.2, 0.4, 0.6}, p1 + p2 ≤ P = 10 Watt and the success probability function in (2) has been used with G1,1 = G2,2 = 1, G1,2 = 0.5, G2,1 = 0.8.

25

Distributed Algorithm for the Scheduling Problem INITIALIZE •

Choose the least element of Πp × Πpr : Pnmin for the power players and (minp~∈Πp π ˆm,n (~p)) for the price players.

•

Set t = 0, k = 0.

REPEAT 1) Power Update: For k = 1, . . . , N (t) • Given π ˆm,n and p~(t,k−1) (t,k) pk

=

(t) arg maxpk ∈[P min ,P max] Jk k k

where Jk is given in (28). •

(t,k)

(t,k−1) pk ; ~p−k

(t,k−1)

p~−k = p~−k

2) Price Update: •

For k = 1, . . . , N. Given p~(t,N ) each user k updates the N − 1 prices πk,n for k 6= n (t,N ) ∂q p ~ , µ k k πk,n ~p(t,N ) = ωk · µk ∂pn

and communicates them to user n •

Each user n receives N − 1 prices πk,n and calculates π ˆk,n

(t,N ) π p ~ k,n p~(t,N ) = qn (~p(t,N ) , µk )

c(t+1) = n

X

π ˆk,n p~(t,N )

k

3) Increase t by 1 •

(t,0)

Set p~

(t−1,N )

= p~

UNTIL p~(t,0) = p~(t−1,0)

(t) π ˆm,n

. Set = πˆm,n p~(t−1,N ) (t) (t−1) and π ˆm,n = π ˆm,n

(41)

26

commodity1

destination1

link 2

link 1 1

destination2

link 3 4

3

2 link 4

commodity2

link 5 link 6

commodity 1 commodity 2

1 0.8 0.6

0.5844

0.4

0.4572

0.2 0

0

200

400

600

800

the incoming rate x for two commodities−Pricing Algorithm U(x) = log(x) the incoming rate x

the incoming rate x

the incoming rate x for two commodities−brute force U(x) = log(x)

0.8

0.4

40 20 0

200

400

600

800

1000

the price lambda

the price lambda

60

time t

Fig. 6.

0

200

400

600 800 1000 time t the price lambda for two commodities on node 1−Pricing Algorithm

100 commodity1 commodity2

80

0

0.4269

0.2

time t the price lambda for two commodities on node 1−brute force 100

0.5710

0.6

0

1000

commodity1 commodity2

1

commodity1 commodity2

80 60 40 20 0

0

200

400

600

800

1000

time t

Congestion control for a four node topology with two commodity flows. The scheduling problem is solved using the suggested

pricing algorithm. Comparison plots with a brut force search to find the global optimum of the weighted sum maximization problem in (19) are provided in the first column.