2013 IEEE International Symposium on Information Theory
Energy Ef?cient Power Allocation for MIMO Multihop Networks
Kalle L¨ ahetkangas
Centre for Wireless Communications University of Oulu Oulu, Finland Email: kallela@ee.oulu.?
Marian Codreanu
Centre for Wireless Communications University of Oulu Oulu, Finland Email: codreanu@ee.oulu.?
Behnaam Aazhang
ECE Department Rice University Houston, TX USA Email: aaz@rice.edu
Abstract—We present a transmission energy ef?cient power allocation method for different end-to-end rates in a Multiple Input Multiple Output (MIMO) multihop network. This method is intended for a network consisting of MIMO nodes that use simple time division scheduling. We formulate the power allocation problem for the various degrees of freedom of MIMO hops as an energy minimization problem and present our iterative solution. Our method calculates the power allocations to the known routes for a requested data transmission time and takes the quality of the channels into account. We perform simulations to show the energy ef?ciency of these routes.
represent the water-?lling capacity for MIMO hops with one variable and use this formulation to reduce the problem to a lower dimensional one. We present an iterative solution using bisection with Newton-Raphson method [9]. We analyze the performance of the resulting power allocation algorithm in a multi-hop transmission through various routes. II. S YSTEM M ODEL We consider a wireless multihop MIMO network model with homogenous nodes with n receive and transmit antennas. We assume a single ?ow of information between a randomly selected source node and a corresponding destination node. Nodes can be used as relays in a multihop manner, to support transmission of packets from the source to the destination. We assume that the relay nodes use decode and forward to transmit the data. The data transmissions via different hops are scheduled to different time slots with simple time division scheduling. This way there is no interference between different hops. A route from the source to the destination consists of I hops. These hops are the links used for the data transmission between the source and the destination. We number the hops from 1 to I . The goal is to transmit D bits to the destination in T seconds. The D bits are transmitted sequentially over every I hop. The time to transmit the data is T = i=1 Ti , where Ti is the time to transmit the data on hop number i. The rate for the hop i is D (1) ri = . Ti We have full channel state information (CSI) at the transmitter and the receiver for the data transmission. We assume that the MIMO channels for different hops are slowly varying and obtaining the full CSI is possible via pilot signals. The transmitter and the receiver obtain the right and left singular vectors for the transmission respectively. The end destination for the data ?nds out the channel characteristics of the route during the route discovery of an on-demand routing protocol. More speci?cally, it is assumed that the end destination can obtain the estimated singular values of the different hops from the route request packets. We assume that every hop uses a bandwidth B for transmitting the data symbols. Let σ 2 denote the background noise
I. I NTRODUCTION The joint power and rate allocating has been considered for multihop networks without Multiple Input Multiple Output (MIMO) in [1]. Advanced MIMO techniques offer the opportunity to increase the capacity with multiplexing and to increase reliability with diversity gains [2]. In MIMO networks these methods are used to gain more range or capacity, but ?nding the route is usually done by selecting the shortest hop route [3], [4], [5]. One critical open research question in the area of MIMO networking is how different MIMO channel capabilities can affect the route selection. For example, a route where we can apply multiplexing can be more energy ef?cient than a route that provides only beamforming. In addition, using a longer hop route with good quality can be more energy ef?cient than using a bad quality shortest hop route. It is important to consider these aspects from an optimization point of view when selecting the route in wireless networks. In the literature of MIMO power allocating, a common starting point is to minimize the transmission time or maximize the utility of the network [6], [7]. In this paper, the end-toend transmission time is kept ?xed. We present a transmission energy ef?cient power allocation method for MIMO ad-hoc networks, in which data ?ow has a speci?ed rate requirement. This method is intended to work centralized at the destination, which knows the channel characteristics of various routes. With this method, the destination can calculate the power allocations for a set of routes, and then the most energy ef?cient one can be selected. This way, the channel characteristics of different routes are taken into account. We formulate the power allocation for data transmission in a MIMO network as an energy minimization problem based on an information theoretic view of MIMO channels [8]. We
978-1-4799-0446-4/13/$31.00 ?2013 IEEE
3035
2013 IEEE International Symposium on Information Theory
power over this bandwidth. We refer to the spatial dimensions of the MIMO channel as subchannels. Let pi be the power allocation vector for hop i, i.e. pi = [Pi1 , . . . , Pin ]. These powers are allocated to the n subchannels. The achievable rate for the hop number i with power allocation pi is given by [8]
n
that satis?es inequalities ? k ? ? ? P > (j ? 1) ? i ? ?
j =1 k
σ2 σ2 ? 2 2 λij λi(j ?1) ? σ2 λ2 ij ,
(6)
Ri ( p i ) = B
j =1
log2
Pij λ2 ij 1+ σ2
bits/s,
? ? ? ? ? ? Pi ≤
j
j =1
σ2 λ2 i(j +1)
(7)
(2)
where λij is the singular value of the j th subchannel of hop i. Note that the subchannels represent orthogonal decompositions of the n × n MIMO channel. III. E NERGY M INIMIZATION P ROBLEM Our problem is to allocate power across all the hops to all the subchannels so that the sum transmission energy is minimized. We have an end-to-end time constraint for transmission of the data. We formulate the minimization problem as Minimize subject to
I i=1 I i=1
(1T pi )Ti Ti ≤ T
(3)
where λi0 = ∞ and λi(n+1) = 0. Here, the inequality (6) is the lower bound on the power Pi for using k degrees of freedom. It is obtained by setting the water-level just enough to inundate completely the k ? 1 subchannels while the power level in the k ’th subchannel is still zero. The inequality (7) is the upper bound on the power Pi for using k degrees of freedom. It is obtained by setting the water-level just enough to inundate completely the k subchannels, while the power level in the k + 1’th subchannel is still zero. By substituting (4) into (5) and by setting the number of degrees of freedom n of (5) to be ki (Pi ), we obtain ? ? ki ( Pi ) 2 σ ? 1 ? . (8) Pi + μi = 2 ki (Pi ) λ ij j =1 By substituting (8) into (4) and (4) into (2) the achievable rate for the i’th MIMO hop is ? ? ki (Pi ) σ 2 ki ( P i ) λ2 ij Pi + u=1 λ2 iu ? bits/s. log2 ? r i ( Pi ) = B 2 k ( P ) σ i i j =1 (9) This is an equivalent expression of the achievable rate (2) when the power Pi is allocated to the active subchannels according to the water-?lling solution. Thus Ri (pi ) in problem (3) can be replaced by ri (Pi ), where Pi = 1T pi (see (5)). Note that the second constraints in problem (3) are tight. Thus by eliminating Ti between the ?rst and the second constraint, problem (3) can be written equivalently as I Pi Minimize D (10) i=1 ri (Pi ) I T 1 ? ≤ 0, subject to i=1 ri (Pi ) D where the function ri (Pi ) is given by (9) and Pi for i = 1, . . . , I are the variables. In this problem, we have an implicit constraint Pi > 0 for all i = 1, . . . , I , because the power Pi must belong to the domain of function ri (Pi ) de?ned in (9). Let p be the power allocation vector for all the hops, i.e. p = [P1 , . . . , PI ]. Let us denote the objective function of problem i (10) by f0 (p) = D i riP (Pi ) . The i’th element of its gradient is ri (Pi ) ? Pi ri (Pi ) [?f0 (p)]i = D . (11) r i ( Pi ) 2 Next we show that this is positive. Note that the function ri (Pi ) is a strictly concave and differentiable function of Pi with the domain Pi > 0 (see the appendix). Thus, for all Pi > c ≥ 0 we have ri (c) < ri (Pi ) + ri (Pi )(c ? Pi ), (12)
Ri (pi )Ti ≥ D, i = 1, . . . , I pi 0, i = 1, . . . , I Ti > 0, i = 1, . . . , I, where the function Ri (pi ) is given by (2) and the variables are pi ∈ Rn and Ti for all i = 1, . . . , I . Power allocation via water-?lling maximizes the rate of a hop, when full CSI is known at the transmitter and at the receiver [8]. Note that maximizing the rate for a certain power is equivalent to minimizing the transmission time for a certain power. To obtain the same transmission time at the same hop with any other power allocation method, we would need more power. Therefore, water-?lling minimizes the energy used for a certain rate for a certain hop. The power allocation for the different subchannels j at the hop i is the water-?lling solution [8] Pij = where μi is selected so that ||pi ||1 =
n j =1
σ2 μi ? 2 λij
+
,
(4)
Pij = Pi ,
(5)
where Pi is the amount of power at hop i. For each MIMO link there are n degrees of freedom available for transmission. Depending on the available power, we use ki (Pi ) ≤ n degrees of freedom at hop i. Without loss of generality, we assume that the singular values of the channels are ordered as λi1 ≥ λi2 ≥ . . . ≥ λin . Then, the number of degrees of freedom ki (Pi ) is the positive integer k
3036
2013 IEEE International Symposium on Information Theory
which for c = 0 implies that 0 < ri (Pi ) ? Pi ri (Pi ), (13)
This equation de?nes the values of power Pi where the value of ki (Pi ) changes. It is obtained similarly to (6). When de?ned, the derivative of νi (Pi ) with respect to Pi is νi (Pi ) = ?D r i ( Pi ) r i ( Pi ) . ri (Pi )2 (18)
since ri (0) = 0. Hence, ?f0 (p) 0 for p 0 , i.e., f0 (p) is increasing in each variable. Next we observe, that the left hand side of the constraint in (10) is decreasing in each variable. Because the objective is increasing while the constraint is decreasing in each variable, it can be shown (by contradiction) that the constraint is tight (i.e., holds with equality at the optimal point of problem (10)). We solve our problem by ?nding the point that satis?es the Karush-Kuhn-Tucker (KKT) conditions. The KKT conditions are the ?rst-order necessary conditions for local optimality [10]. Note that our problem has to have a minimum. Lemma 1. The KKT conditions of problem (10) have at most one solution at p 0. Proof: Let us denote the constraint function of problem T 1 (10) by f1 (p) = i ri (Pi ) ? D . The KKT conditions for the optimal values of ν and p are 1) ?f0 (p) + ν ?f1 (p) = 0, 2) f1 (p) = 0, 3) ν > 0 We ?rst proof that for a certain value of the dual variable ν , there is only one p, that satis?es the ?rst condition. The ?rst KKT condition can be written equivalently as ν=D r1 ( P 1 ) ? P1 r 1 ( P1 ) = ··· = D r I ( PI ) ? PI rI (PI ) , (14)
by replacing the elements of ?f0 (p) with (11) and the elements of ?f1 (p) with [?f1 (p)]i = ? ri (Pi ) . r i ( Pi ) 2 (15)
for all i. The equations in (14) are equalities that need to hold for the ?rst KKT condition to hold. The value of ν , with a power Pi for the hop i can be written as ν i ( Pi ) = D ri (Pi ) ? Pi ri (Pi ) = ν, i = 1, . . . , I. (16)
Note that the second derivative ri (Pi ) is negative (see (28)). Thus, the function νi (Pi ) has a positive derivative on all the intervals where it is de?ned. Recall, that it is also continuous. Therefore, it is increasing and invertible. This means that there is only one p, that satis?es the ?rst KKT condition for a certain value of ν . Next we proof that the optimal value for the dual variable ν is unique, e.g., there cannot exist two values of ν that satisfy the KKT conditions. The ?rst KKT condition is written equivalently as I equations and unknown parameters Pi in (14). These unknown parameters Pi are the values of p. Note that these equations are invertible and increasing in Pi for all i = 1, . . . , I . Then, there cannot be more than one ν , which inverts to p and satis?es the second KKT condition f1 (p) = 0, because the function f1 (p) is decreasing in each variable. Because KKT condition holds only at one point, it is the minimum for our problem. In other words, if we ?nd a point that satis?es the KKT conditions for our problem (10), we have the optimal values of power allocated to each link. These values of power satisfy the ?rst constraint. The ?rst KKT condition (14) is shown to be invertible in the proof of Lemma 1, so if we ?nd the optimal dual variable ν , we can obtain the optimal powers Pi of (16) for each hop in the route. We can solve for the values of the inverse using any ef?cient root ?nding techniques. We use the Newton-Raphson method because of its convergence speed. We will now focus on using the Newton-Raphson method to ?nd all Pi ’s that satisfy the ?rst KKT condition (14). More speci?cally, for every i we ?nd the value of Pi that is the root of the function h i ( Pi ) = ν ? D ri (Pi ) + Pi . r i ( Pi ) (19)
Let xm denote the value of Pi at iteration number m. The Newton-Raphson iteration to ?nd the root for a function hi (Pi ) is de?ned as gi (xm ) = xm+1 = xm ? hi ( x m ) , hi ( x m ) (20)
These are the ith functions of (14). If these functions are invertible, there is only one p, that satis?es the ?rst condition (14) for a certain value of ν . Next we show that the νi (Pi ) is indeed invertible by showing that it is continuous and strictly increasing function of Pi . The function νi (Pi ) is continuous in Pi > 0, because functions ri (Pi ) and ri (Pi ) are continuous (see Lemma 2 in the appendix). The function νi (Pi ) is differentiable almost everywhere Pi > 0 except at
k
Pi =
j =1
(j ? 1)
σ2 σ2 ? 2 2 λij λi(j ?1)
,
k = 1, . . . , n.
(17)
where the gi (xm ) is Newton-Raphson iteration function and the xm+1 is the result of this iteration function with an input xm . We use (28) with every Pi as the second derivative of ri (Pi ) when calculating the derivative of hi (Pi ). We begin the iteration with a starting value x0 and obtain gi (x0 ) = x1 . We then insert the x1 to the function (20) again, and obtain gi (x1 ) = x2 . We continue iteratively, until gi (xm ) = xm+1 = xm . This value xm is the value of the root for the function (19). In other words, this is the value of Pi that is the inverse for νi (Pi ) = ν de?ned in the equation (16).
3037
2013 IEEE International Symposium on Information Theory
6XPHQHUJ\WRWUDQVPLW'ELWV>-RXOHV@
Due to the lack of space we omit the proof of convergence of Newton-Raphson method for our problem. Next, we present a pseudocode for solving the KKT conditions in Algorithm 1. This algorithm is based on bisection. In this algorithm, we ?nd the optimal value for ν . The lower limit for ν is 0. The upper limit νu can be found by setting the power levels for all the hops equal, and by ?nding the power vector p with equal elements, that satisfy the ?rst constraint f1 (p) = 0. Then, the upper limit for νu is the maximum νi (Pi ) obtained from the equation (16) with i = 1, . . . , I . We start the bisection by ?rst selecting ν as the middle point of the lower limit νl and the upper limit νu . We then solve the equalities (14) for all i = 1, . . . , I . Recall, that the invertibility of νi (Pi ) is proven in the proof of Lemma 1. Now, the ?rst KKT condition holds. Then we check, if the constraint f1 (p) = 0 holds. If it holds, we have the optimal values for the power. If it does not hold, we change the upper or lower limit according the positivity of the constraint f1 (p). We continue bisecting until we ?nd the value ν that satisfy f1 (p) = 0, with enough accuracy . Algorithm 1: Finding p Input: νl = 0, νu = α Output: p? 1 while νu ? νl ≥ do 2 ν := (νl + νu )/2; 3 Pi := inverse of ν = νi (Pi ) for all i = 1, . . . , I ; 4 if f1 (p) > 0 then 5 νl := ν ; 6 else 7 νu := ν ;
8 ?
ef?ciently, we need to select different routes depending of the transmission time T we have. For a fast transmission we need to use the Route 1 with one hop. For a slow transmission we prefer the Route 4 with three hops. For a moderate transmission time the Route 3 is the most energy ef?cient.
TABLE I T HE SINGULAR VALUES OF THE ROUTES .
Hop 1 Route 1 Route 2 Route 3 Route 4 λ11 = 0.0008 λ12 = 0.0003 λ11 = 0.0036 λ12 = 0.0012 λ11 = 0.0033 λ12 = 0.0015 λ11 = 0.0074 λ12 = 0.0039 λ21 = 0.0027 λ22 = 0.0004 λ21 = 0.0431 λ22 = 0.0113 λ21 = 0.0225 λ22 = 0.0032 λ31 = 0.0431 λ32 = 0.0113 Hop 2 Hop 3
í
í
5RXWH 5RXWH 5RXWH 5RXWH
í
í
í
7LPHWRWUDQVPLW'ELWV>V@
return p IV. R ESULTS
Fig. 1. The total transmission energy to transmit D bits of data as a function of the total transmission time.
In this section, we present some sample simulation results of our algorithm for a set of different routes. We consider a scenario where the source has D = 8 Mbits data to send to the destination. Without loss of generality, we also assume that the noise power is σ 2 = ?92dBm and that the bandwidth is B = 312.5kHz. We consider all the nodes to have two antennas for receiving and transmitting. In Table I we present the singular values used in the simulations. The singular values have been obtained from channel measurements in an indoor environment. The Route 1 has one long hop with non-lineof-sight (NLOS) between the source and the destination. The Route 2 has two NLOS hops. The Route 3 has one NLOS hop and one line-of-sight (LOS) hop. The Route 4 has one NLOS hop and two LOS hops. In Fig. 1, we plot the total transmission energy used to transmit D bits to the destination as a function of total transmission time, T. To be the most energy ef?cient, we would transmit at a low rate via the Route 4. It is the most energy ef?cient route out of these routes though it has three hops. Furthermore, we observe that to transmit data energy
V. C ONCLUSION In this work, we introduced the power allocation method for a predetermined rate in a MIMO multihop network. The method takes the degrees of freedom and the qualities of the channels into account when calculating the transmission energy ef?cient power allocation for the route. We formulated the power allocation as a concave minimization problem. We presented an algorithm for solving this problem. We simulated the outcome of our algorithm for various routes, and illustrated the possible gains in transmission energy ef?ciency against the shortest hop routing protocol. Choosing the energy ef?cient route depends on the requested end-to-end rate and the channel characteristics of the different routes. We are developing a new on-demand routing algorithm from the basis of this work. Here the most transmit energy ef?cient path for a speci?c end-to-end time constraint is found during the route discovery.
3038
2013 IEEE International Symposium on Information Theory
A PPENDIX Lemma 2. The function (9) is differentiable and strictly concave. Its derivative is Bki (Pi ) , (21) r i ( Pi ) = ki ( Pi ) σ 2 ln(2)(Pi + j =1 ) 2 λ
ij
the value of the power where the k changes to k + 1. For this power, we water-?ll only k subchannels. After this power, we water-?ll k + 1 subchannels. For this value of power, the value for (25) is
1 B (k + 1) ln(2) k+1 j =1 (j
where ki (Pi ) is a positive integer k that satis?es inequalities (6) and (7). This derivative is continuous and positive at every Pi > 0. Proof: We ?rst calculate the derivative for (9) with respect to Pi when Pi is at the interval where k subchannels are water?lled. We then calculate the value for this derivative for the maximum value of Pi where we still use k subchannels. Then we calculate the derivative for (9) with respect to Pi when Pi is at the interval where k + 1 subchannels are water?lled. We also calculate the value for this derivative for the maximum value of Pi where where we still use k subchannels. We notice that these values for the derivatives with k and k +1 subchannels are the same for the power, where the number of subchannels change. This means that the function (9) is differentiable. When the Pi is at the interval, where k subchannels are water-?lled, the derivative of (9) with respect to Pi is
1 Bk ln(2) k σ2 Pi + j =1 λ 2 ij
? 1) .
σ2 λ2 ij
?
σ2 λ2 i(j ?1)
+
k+1 σ 2 j =1 λ2 ij
=
Bλ2 i(k+1) σ 2 ln(2)
(27)
Note that (27) can be established mathematical induction. Also note that the right hand side of (27) is identical to the right hand side of (24). Therefore, the derivative of (9) is continuous at powers where the number of subchannels change. Therefore, the derivative (21) is continuous and positive. Note, that this proof can be straightforwardly extended to the cases where some singular values are equal. Next we proof the concavity of the function (9). The second derivative of (9) with respect to positive Pi is de?ned as r i ( Pi ) = ? Bki (Pi ) ln(2)(Pi +
ki ( Pi ) σ 2 2 ) j =1 λ2 ij
,
(28)
.
(22)
everywhere except in the points that satisfy (17). The second derivative is negative on all open intervals where it is de?ned. Note, that the derivative of the function (9) with respect to Pi is continuous. Then, the function (9) is concave. R EFERENCES
When we water-?ll k subchannels, the maximum Pi is
k
Pi =
j =1
j
σ2 λ2 i(j +1)
?
σ2 λ2 ij
,
(23)
because it is the upper bound for Pi shown by (7). For this value of power, the value for (22) is
1 Bk ln(2) k j =1
j
σ2 λ2 i(j +1)
?
σ2 λ2 ij
+
k σ2 j =1 λ2 ij
=
Bλ2 i(k+1) σ 2 ln(2)
.
(24)
Note that (24) can be established by mathematical induction. When Pi is at the interval, where k + 1 subchannels are water-?lled, the derivative of (9) with respect to Pi is
1 B (k + 1) ln(2)
Pi +
k+1 σ 2 j =1 λ2 ij
.
(25)
When we water-?ll k + 1 subchannels, the minimum Pi is bounded by value
k+1
Pi =
j =1
(j ? 1)
σ2 σ2 ? 2 2 λij λi(j ?1)
,
[1] P. Soldati and M. Johansson, “Reducing signaling and respecting timescales in cross-layer protocols design for wireless networks,” in Global Telecommunications Conference, GLOBECOM, dec 2009, pp. 1–8. [2] L. Zheng and D. Tse, “Diversity and multiplexing: A fundamental tradeoff in multiple-antenna channels,” IEEE Transactions on Information Theory, vol. 49, no. 5, pp. 1073–1096, 2003. [3] K. Sundaresan and R. Sivakumar, “Routing in ad-hoc networks with MIMO links,” in IEEE ICNP, Boston, nov. 2005. [4] N. Nie and C. Comaniciu, “Energy ef?cient AODV routing in CDMA ad hoc networks using beamforming,” in Vehicular Technology Conference, vol. 4, 2005, pp. 2449 – 2453 Vol. 4. [5] M. Takai, J. Martin, R. Bagrodia, and A. Ren, “Directional virtual carrier sensing for directional antennas in mobile ad hoc networks,” in Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, 2002, pp. 183–193. [6] S.-J. Kim and G. Giannakis, “Optimal resource allocation for mimo ad hoc cognitive radio networks,” IEEE Transactions on Information Theory, vol. 57, no. 5, pp. 3117–3131, 2011. [7] J. Liu, Y. Hou, Y. Shi, and H. Sherali, “Cross-layer optimization for mimo-based wireless ad hoc networks: Routing, power allocation, and bandwidth allocation,” IEEE Journal on Selected Areas in Communications, vol. 26, no. 6, pp. 913–926, 2008. [8] D. Tse and P. Viswanath, Fundamentals of wireless communication. Cambridge University Press, 2005. [9] J. Mathews and K. Fink, Numerical methods using MATLAB. Prentice Hall Upper Saddle River, 1999, vol. 31. [10] H. Kuhn and A. Tucker, “Nonlinear programming,” in Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, J. Neyman, Ed. University of California Press, Berkeley, California, 1951, pp. 481–492.
(26)
because it is the lower bound for Pi shown by (6). Note, that the value of (23) is equal to the value of (26), because it is
3039