domain: spi info

text:
Mohamad Maaz
email: mohamad.maaz@orange.com

Member, IEEE Philippe Mary

Member, IEEE Maryline Hélard

Energy Minimization in HARQ-I Relay-Assisted Networks with Delay-Limited Users

Keywords: Energy minimization, power allocation, relay selection, HARQ, MCS, convex optimization, integer programming. I

This paper investigates a practical energy minimization problem for multi-user relay-assisted downlink cellular networks. The system adopts an hybrid-automatic-repeat-request of type I (HARQ-I) protocol and each user has an average delay constraint to be satisfied under a total power constraint for the system. The contribution of this paper lies in several folds: i) By introducing new constraints and new variables in the original problem, the solution is analytically obtained by the dual method. ii) An algorithm that jointly allocates for every user the optimal downlink power at base station (BS) and relay station (RS) and selects the RS (if cooperation is decided) is proposed. iii) Another binary integer programming algorithm that selects the optimal modulation and coding scheme (MCS) and optimizes the number of time-frequency resource blocks (RBs) between users is proposed. In order to corroborate our findings, simulation results in terms of energy-delay tradeoff, average starvation user rates and selected MCS statistics are presented. Our analyses show that relay-assisted strategy improves up to 30 % the energy consumption compared to non-relay-assisted one.

Traditional resource allocation policies focusing on the throughput maximization are generally not energy-aware [START_REF] Blume | Most promising tracks of green network technologies[END_REF], [START_REF] Miao | Distributed Interference-Aware Energy-Efficient Power Optimization[END_REF]. Moreover, most of the green wireless strategies focus on energy minimization or efficiency under the classical Shannon theory framework, i.e. by considering reliable communications or theoretical outage capacity [START_REF] Chen | Fundamental Trade-offs on Green Wireless Networks[END_REF]. Thus, in multi-user (MU) context, minimizing the energy consumption under non reliable communication, i.e. non zero PER, is a challenging task for the scientific community in order to enhance future cellular networks. Moreover, relay-assisted communication has already been identified as a promising technology to provide higher coverage and data-rate for high QoS wireless services [START_REF] Salem | Opportunities and Challenges in OFDMA-Based Cellular Relay Networks: A Radio Resource Management Perspective[END_REF].

In [START_REF] Stanojev | Energy efficiency of non-collaborative and collaborative Hybrid-ARQ protocols[END_REF] the authors studied the energy efficiency (EE) for cooperative and non cooperative HARQ schemes by minimizing the energy consumed for a single user with outage probability constraint. In [START_REF] Qi | H2-ARQ-Relaying: Spectrum and Energy Efficiency Perspectives[END_REF], the authors studied the energy efficiency for decode-and-forward (DF), amplify-and-forward (AF) and compress-and-forward (CF) relaying schemes with HARQ under outage probability and delay constraints. Moreover, some recent works have been granted in resource allocation for HARQ-based systems in [START_REF] Kim | Rate-Adaptation-Based Cooperative Hybrid-ARQ Relaying Scheme in Rayleigh Block-Fading Channels[END_REF], [START_REF] Song | Rate Adaptation and Power Allocation for Cognitive Radio Networks with HARQ-Based Primary System[END_REF]. The authors have investigated some power-rate allocation strategies for cooperative transmissions in source-relay-destination configurations. In [START_REF] Song | Rate Adaptation and Power Allocation for Cognitive Radio Networks with HARQ-Based Primary System[END_REF], the authors have been interested in the context of cognitive radio, where secondary users (SU) may help primary users (PU) as relays when PUs retransmit the same data packet in HARQ mode. However, they have considered neither energy-efficiency performances nor multi-users resource allocation with delay constraints. It is also convenient to note that an important amount of works in wireless sensor networks (WSN) considers that the energy consumption is of crucial importance, e.g. [START_REF] Zhang | Low Bound of Energy-Latency Trade-Off of Opportunistic Routing in Multi-Hop Networks[END_REF] and [START_REF] Lin | Energy Efficient Clustering Protocol for Large-Scale Sensor Networks[END_REF], [START_REF] Xu | Energy-Efficiency-Based Optimal Relay Selection Scheme With a BER Constraint in Cooperative Cognitive Radio Networks[END_REF] for recent contributions on this topic. However, all works above did not consider jointly the resource allocation strategy in MU cellular context with HARQ schemes under delay constraint and non-reliable communications.

In our previous works [START_REF] Maaz | Energy Efficiency Analysis in Relay Assisted Hybrid-ARQ Communications[END_REF], [START_REF] Maaz | Energy Efficiency Analysis of Hybrid-ARQ Relay-Assisted Schemes in LTE-Based Systems[END_REF], EE in relay-assisted HARQ scheme have been analyzed in a single user context without considering any resource optimization problem. In particular in [START_REF] Maaz | Energy Efficiency Analysis of Hybrid-ARQ Relay-Assisted Schemes in LTE-Based Systems[END_REF], we have been interested in the EE analysis for HARQ schemes in single user source-relay-destination framework, when a practical FPGA target is considered. However, no resource allocation problems for optimizing throughput and/or power have been formulated nor solved. The main challenge comes from the need of a closed-form expression of PER with HARQ in order to express the delay requirements [START_REF] Martret | Analytical Performance Derivation of Hybrid ARQ Schemes at IP Layer[END_REF]. In this work, we propose a new resource allocation algorithm for MU relay-assisted HARQ-I (i.e. considering coded packets [START_REF] Martret | Analytical Performance Derivation of Hybrid ARQ Schemes at IP Layer[END_REF]) scheme that aims at allocating powers at base station (BS) and relay stations (RS) and selects the optimal relay that minimizes the energy consumption while satisfying the delay constraint for every user and respecting the total power constraint of the system. In this work, we formulate the energy minimization problem by introducing intermediate variables that enable to efficiently solve this problem thanks to the Lagrange dual optimization. Hence, an energy minimization algorithm that distributes the optimal powers between users is derived. Finally, a binary-integer programming algorithm is proposed aiming to select the optimal modulation and coding scheme (MCS) and number of resource blocks (RB) for every user minimizing the total energy consumed. To the best of our knowledge, this is the first work that jointly considers an HARQ scheme and MCS in multiuser relay-assisted network in order to minimize the overall energy for delay constrained users.

The remaining of the paper is organized as follows: the system model and hypothesis are stated in Section II. Section III presents the proposed energy minimization problem. Section IV deals with the solution of the optimization problem: optimal power, delays at BS and RS and the relay selection strategy. In Section V, the proposed energy minimization algorithm is described. In section VI, a jointly MCS and resource blocks allocation algorithm is proposed while Section VII deals with numerical results. Finally, a conclusion is drawn in Section VIII.

II. SYSTEM DESCRIPTION

A. System model

We consider a downlink multiuser relay-assisted network consisting of a BS, a set of relays K = {1, • • • K} deployed around the BS and a set of randomly distributed users M = {1, • • • M } to be served simultaneously. The system is considered adopting the orthogonal frequency division multiple access (OFDMA) technique with N RB RBs to be shared among users. Considering also an HARQ based system, the communication protocol between BS and every user is described as follows:

BS transmits a packet to the m-th user u m and the k-th selected relay r k is hearing the transmission. If u m decodes/does not decode the packet, u m sends an acknowledgment (ACK) /non-ACK (NACK) to BS, respectively. The ACK/NACK packets are assumed to be received error-free with a negligible delay which is a reasonable assumption considering the low rate of these packets [START_REF] Maham | Analysis of Outage Probability and Throughput for Half-Duplex Hybrid-ARQ Relay Channels[END_REF]. If r k successfully decodes and u m does not, r k sends an ACK to BS and starts retransmitting the packet until u m decodes it. If neither r k nor u m decodes the packet, BS keeps transmitting the same packet until r k or u m receives it.

According to the data packet size and required QoS, the resource scheduler at BS has to decide for every user whether direct or relay-assisted transmission is preferable in order to minimize the energy consumption. Moreover, this latter also depends on MCS and the number of time and frequency RBs. Hence, let us consider that each RB consists of N s subcarriers and has a duration of N F OFDMA symbols. Moreover each symbol has a duration of T OFDM and hence the subcarrier spacing is ∆f = 1/T OFDM . Fig. 1 illustrates the RB sharing process between users. Let us consider that each subcarrier is affected by a centered additive-white Gaussian noise (AWGN) n ∼ CN (0, σ 2 ). Moreover, the small scale channel fading coefficients are independent and identically Rayleigh distributed for different RBs and users. Let us assume that the average received SNR is γ = E[γ] = g σ 2 p where p is the transmitted power and g is the channel gain which is pathloss dependent. Therefore, for a given MCS, the average PER (in fading channel) could be tightly approximated as follows [START_REF] Mackay | Performance of Low Density Parity Check Codes as a Function of Actual and Assumed Noise Levels[END_REF]:

Π(γ) = 1 -exp -aγ b c (1)
where a, b, and c are curve fitting parameters which depend on the adopted MCS and are given in table I. These parameters have been estimated based on the turbo coding scheme that is adopted in LTE [START_REF] Gpp | Multiplexing and channel coding[END_REF].

Let us assume that for user m, the scheduler has to select a certain QAM modulation order Q m and a coding rate R m . Therefore, according to the packet length L, the number of required frequency or/and time RBs to be allocated to user m is summarized in Table I and given by

RB m = L R m log 2 (Q m )N s . (2)
Moreover, let us assume that user m has a delay constraint D m , in time slots, to be satisfied, where a time slot is the duration of one resource block. The possible number of RBs to be allocated to user m varies between 1 and RB m . Thus, as the number of allocated RBs increases, the delay constraint becomes less stringent and varies between D m and RB m D m due to the possibility of multiplexing in frequency. Therefore, for every possible combination of MCS and every selected number of RBs, the scheduler has to allocate a transmission power such that the delay constraint is guaranteed.

B. Delay model

Let us consider that correct detection events at the instants n and n -1 are independent at each node. Moreover, we assume that the number of allowed retransmissions, N max , is large enough to neglect the packet loss and hence can be considered as infinite [START_REF] Lagrange | Throughput of HARQ Protocols on a Block Fading Channel[END_REF]. Let us define N d 0m as the average delay per received packet between BS and user m in case of direct transmission. The subscripts '0' and 'm' stand respectively for BS and user m while the superscript 'd' stands for direct transmission. By definition of the expectation of a discrete random variable, the average delay per received packet is [START_REF] Maaz | Energy Efficiency Analysis in Relay Assisted Hybrid-ARQ Communications[END_REF], [START_REF] Lagrange | Throughput of HARQ Protocols on a Block Fading Channel[END_REF], where q d 0m (n) is the successful decoding probability at instant n which is the probability that u m does not decode at instants 1, 2,

N d 0m = +∞ n=1 nq d 0m (n)
• • • , n -1 but decodes at n. Hence, q d 0m (n) = Π d 0m n-1 (1 -Π d 0m
) and using [22, eq. (2) §0.231, pp. 8], we obtain:

N d 0m = 1 1 -Π d 0m (γ d 0m ) (3)
where γ d 0m = g 0m p d 0m σ 2 , g 0m , p d 0m and Π d 0m are respectively the average received SNR, the channel gain, the allocated power and the PER in the BSu m link. The average PER Π d 0m has a similar form as in [START_REF] Imran | Most suitable efficiency metrics and utility functions[END_REF] and it depends on the curve fitting parameters a, b and c that are provided in Table I for every MCS.

Let us consider that relay r k has been selected to help user u m . The allocated powers at BS and r k are respectively p c 0km and p c km . The average channel gains in BSu m , BSr k and r ku m links are respectively g c 0m , g c 0km and g c km . Therefore, under cooperation between BS and r k , the average delay induced when BS is transmitting is

N c 0km = +∞ n=1 nq c 0km (n) with q c
0km (n) being the successful decoding probability at u m or r k at the instant n due to BS transmissions. The correct (or not) decoding events at u m and r k are independent, hence the error probability at any instant is

Π c 0m (γ c 0m )Π c 0km (γ c 0km ), with γ c 0m = g c 0m p c 0km σ 2 and γ c 0km = g c 0km p c 0km σ 2 .
Moreover, the error events are independent from one time slot to another; q c 0km (n) is hence given by q

c 0km (n) = (1 -Π c 0m (γ c 0m )Π c 0km (γ c 0km ))(Π c 0m (γ c 0m )Π c 0km (γ c 0km )) n-1
and using [22, eq. (2) §0.231, pp. 8], we obtain:

N c 0km = 1 1 -Π c 0m (γ c 0m )Π c 0km (γ c 0km ) . (4)
If at instant n ′ , user u m has not received the packet but relay r k did, BS stops transmitting the packet, while r k continues to forward the packet to u m . Thus, the average delay induced when r k transmits is

N c km = ∞ n ′ =1 q c 0k (n ′ ) × ∞ n=n ′ +1 (n -n ′ )q c km (n) where q c
0k (n ′ ) is the successful decoding probability at r k at n ′ and considering that u m has not decoded. Moreover, q c km (n) is the successful decoding probability at u m due to r k transmissions at the instant n > n ′ . Hence,

q c 0k (n ′ ) = Π c 0m (γ c 0m ) n ′ Π c 0km (γ c 0km ) (n ′ -1) (1 -Π c 0km (γ c 0km )) and q c km (n) = Π c km (γ c km ) (n-n ′ ) (1 -Π c km (γ c km )), with γ c km = g c km p c km σ 2 being the average SNR in the r k -u m link.
Using [22, eq. (2) §0.231, pp. 8], the average delay when r k transmits is:

N c km = Π c om (γ c 0m ) (1-Π c 0km (γ c 0km )) 1-Π c 0m (γ c 0m )Π c 0km (γ c 0km ) 1 1-Π c km (γ c km ) (5)
Hence, in case of cooperation with relay r k , the average delay per successfully received packet at u m is:

N km = N c 0km + N c km (6)

C. Energy Consumption model

Let us assume that the static power consumed by circuits for transmitting or receiving a modulated signal at BS, RS and UE are respectively denoted by P bs , P rs and P ue . Let us also denote by E i tx and E i rx , the energy consumed for transmitting and receiving a packet at i ∈ {bs, rs, ue} respectively. Hence, in case of direct transmission with u m , the consumed energy for transmitting one packet is [START_REF] Zhang | Low Bound of Energy-Latency Trade-Off of Opportunistic Routing in Multi-Hop Networks[END_REF]:

f 1 (p d 0m ) = E bs tx + E ue rx + E ack (7)
with E bs tx = η m P bs + β amp p d 0m and E ue rx = η m P ue , where η m = L/(∆f log 2 (Q m )R m ) depends on the packet length L, the sub-carrier spacing ∆f and the selected MCS that is represented by the modulation order Q m and the coding rate R m . The factor β amp stands for the power amplifier (PA) inefficiency factor, i.e. the larger β amp , the larger power consumption due to PA. Moreover, E ack = τ (E bs tx + E ue rx ) is the energy consumed for the N/ACK, with τ being the ratio of the number of transmitted bits for ACK and the number of transmitted bits in the data packet. Therefore, f 1 (p d 0m ) can be re-written as:

f 1 (p d 0m ) = k 1 + k 2 p d 0m (8)
with

k 1 = η m (1 + τ )(P bs + P ue ) and k 2 = η m (1 + τ )β amp .
Therefore, the average energy consumed per received packet is:

E d 0m = f 1 (p d 0m )N d 0m (9)
In case of cooperation between BS and r k that assists the communication with user u m , the relay r k and u m receive a copy of the transmitted packet from BS and then they transmit an N/ACK to BS. The consumed energy when BS transmits one packet can be expressed as:

f 2 (p c 0km ) = (1 + 2τ ) E bs tx + (1 + τ ) (E rs rx + E ue rx ) (10)
Hence, the consumed energy when BS transmits can be written as:

f 2 (p c 0km ) = k 3 + k 4 p c 0km (11)
with

k 3 = η m ((1 + 2τ ) P bs + (1 + τ ) (P rs + P ue )) and k 4 = η m (1 + 2τ ) β amp . M m=1          1 - K k=1 s km f 1 (p d 0m ) 1 -Π d 0m (p d 0m ) + K k=1 s km f 2 (p c 0km ) 1 -Π c 0m (p c 0km )Π c 0km (p c 0km ) + Π c 0m (p c 0km )(1 -Π c 0km (p c 0km )) 1 -Π c 0m (p c 0km )Π c 0km (p c 0km ) f 3 (p c km ) 1 -Π c km (p c km ) (12)
Furthermore, when r k successfully decodes the packet received from BS, it starts retransmitting the packet to u m . Then N/ACK are sent from u m to r k and BS and the consumed energy when r k is transmitting is:

f 3 (p c km ) = E rs tx + E ue rx + τ E rs tx + E ue rx + E bs rx (13) = k 5 + k 6 p c km ( 14
)
where k 5 = η m (τ P bs + (1 + τ ) (P rs + P ue )) and k 6 = η m (1 + τ )β amp . Hence, the consumed energy per received packet in relay-assisted mode is:

E c km = f 2 (p c 0km )N c 0km + f 3 (p c km )N c km (15)

III. PROBLEM FORMULATION

The objective function of the original problem is defined in [START_REF] Zhang | Low Bound of Energy-Latency Trade-Off of Opportunistic Routing in Multi-Hop Networks[END_REF] on the top of the page and has constraints (c 1 ), (c 2 ), (c 6 ) and (c 7 ) defined in [START_REF] Maaz | Energy Efficiency Analysis of Hybrid-ARQ Relay-Assisted Schemes in LTE-Based Systems[END_REF] on the next page. The expression in [START_REF] Zhang | Low Bound of Energy-Latency Trade-Off of Opportunistic Routing in Multi-Hop Networks[END_REF] is the overall energy consumed in the cell where the left most term is the energy consumed when a group of users has been selected to communicate directly with BS, i.e. K k=1 s km = 0. The binary variable s km is equal to 1, if the relay r k is selected to help the user u m and zero otherwise. The right most term is the energy consumed in relay-assisted mode, i.e s km = 1. The constraint (c 1 ) ensures that the average delay is less than or equal to D m for every user u m . (c 2 ) ensures that only one relay can be selected per user. The constraint (c 6 ) states that the total allocated power (for BS and relays) is less than or equal to the power constraint P tot . (c 7 ) ensures the positivity of allocated powers. The solution of this problem over the variables p d 0m , p c 0km , p c km and the integer variable s km is very challenging due to the combination of non convex functions and binary constraints that make the problem intractable. In order to overcome the difficulty implied by this non linear problem, we consider that the delays N d 0m , N c 0km and N c km ∀k, m are also variables satisfying the new equality constraints in (c 3 ), (c 4 ) and (c 5 ) respectively. Hence, the energy minimization problem under average delay and power constraints can be formulated as in [START_REF] Maaz | Energy Efficiency Analysis of Hybrid-ARQ Relay-Assisted Schemes in LTE-Based Systems[END_REF]. One can notice that problem ( 12) is equivalent to [START_REF] Maaz | Energy Efficiency Analysis of Hybrid-ARQ Relay-Assisted Schemes in LTE-Based Systems[END_REF] by just substituting the equality constraints (c 3 ), (c 4 ) and (c 5 ) in the objective function [START_REF] Maaz | Energy Efficiency Analysis of Hybrid-ARQ Relay-Assisted Schemes in LTE-Based Systems[END_REF]. Solving ( 16) is equivalent to find the optimal vector

λ km = {λ km : (k, m) ∈ K × M} with λ km = [s km p d 0m p c 0km p c km N d 0m N c 0km N c km ]
. This problem is a mixed combinatorial and continuous optimization problem, which is still very difficult to solve in this form. We first relax the integer constraint on s km , assuming it could be a time sharing factor between 0 and 1, leading to

K k=1 s km ≤ 1 ∀m = {1, • • • , M } [23]
, however the problem in ( 16) is still not convex.

The Lagrangian L associated with this problem is expressed in [START_REF] Mackay | Performance of Low Density Parity Check Codes as a Function of Actual and Assumed Noise Levels[END_REF], where the PER dependency on transmit powers has been removed in order not to clutter the notation. We refer to the vectors

γ m = [γ 1 , • • • , γ M ], φ m = [φ 1 , • • • , φ M ], α km = (α d 0m , α c 0km , α c km ) : (k, m) ∈ K × M
and µ as the Lagrange multipliers respectively associated to the constraints from (c 1 ) to (c 6 ), K and M stand for the sets of relays and users respectively. A lower bound of the original minimization problem can be found by solving the Lagrange dual problem. The dual G associated with the primal problem in ( 16) is defined as:

G(γ m , µ, α km , φ m ) = inf λkm L(λ km , γ m , µ, α km , φ m ) (17)
Since the dual function G is an infimum of a family of affine functions of dual variables (γ m , µ, α km , φ m ), then it is concave even if the problem is not convex [START_REF] Boyd | Convex Optimization[END_REF] and yields to a lower bound of the primal problem for any γ m and µ ≥ 0. Therefore, the dual optimization problem of ( 16) can be expressed as follows:

max γm, µ, αkm, φm G(γ m , µ, α km , φ m ) subject to: γ m , µ ≥ 0 (18)
The primal problem in [START_REF] Maaz | Energy Efficiency Analysis of Hybrid-ARQ Relay-Assisted Schemes in LTE-Based Systems[END_REF] cannot be proved to be strictly convex for all possible combinations of users and relays. In that sense, solving the dual problem leads to a lower bound of the primal without a zero optimality gap. However, a lower bound remains very interesting since no closed form can be obtained from the primal problem due to the complexity of expressions involved.

IV. PROBLEM SOLUTION According to [START_REF] Maham | Analysis of Outage Probability and Throughput for Half-Duplex Hybrid-ARQ Relay Channels[END_REF], it is convenient to firstly find the infimum of the Lagrangian function L in [START_REF] Mackay | Performance of Low Density Parity Check Codes as a Function of Actual and Assumed Noise Levels[END_REF] over the set of primal variables λ km and then find the supremum of G over the dual variables. Thus, the primal variables can be expressed as function of dual variables as follows:

A. Power allocation

Applying the gradient operator over the Lagrangian function L w.r.t N d 0m , we get the following:

∇ N d 0m L = 1 - K k=1 s km f 1 p d 0m + γ m -α d 0m ( 20
)
min λkm M m=1 1 - K k=1 s km f 1 (p d 0m )N d 0m + K k=1 s km f 2 (p c 0km )N c 0km + f 3 (p c km )N c km
subject to:

(c 1 ) 1 - K k=1 s km N d 0m + K k=1 s km N c 0km + N c km ≤ D m ∀m ∈ {1, • • • , M } (c 2 ) s km = {0, 1} ∀ (k, m) ∈ {1, • • • , K} × {1, • • • , M } and K k=1 s km = {0, 1} ∀m ∈ {1, • • • , M } (c 3 ) N d 0m = 1 1 -Π d 0m (p d 0m ) ∀m ∈ {1, • • • , M } (c 4 ) N c 0km = 1 1 -Π c 0m (p c 0km )Π c 0km (p c 0km ) ∀ (k, m) ∈ {1, • • • , K} × {1, • • • , M } (c 5 ) N c km = Π c 0m (p c 0km )(1 -Π c 0km (p c 0km )) (1 -Π c 0m (p c 0km )Π c 0km (p c 0km ))(1 -Π c km (p c km )) ∀ (k, m) ∈ {1, • • • , K} × {1, • • • , M } (c 6 ) M m=1 1 - K k=1 s km p d 0m + K k=1 s km (p c 0km + p c km ) ≤ P tot (c 7 ) p d 0m , p c 0km , p c km ≥ 0 (16)
L = M m=1 K k=1 s km (f 2 (p c 0km ) + γ m ) N c 0km + (f 3 (p c km ) + γ m ) N c km -f 1 (p d 0m ) + γ m N d 0m +α c 0km 1 1 -Π c 0m Π c 0km -N c 0km + α c km Π c 0m (1 -Π c 0km ) (1 -Π c 0m Π c 0km )(1 -Π c km ) -N c km + M m=1 α d 0m 1 1 -Π d 0m -N d 0m + µ M m=1 1 - K k=1 s km p d 0m + K k=1 s km (p c 0km + p c km ) -µP tot + M m=1 φ m K k=1 s km -1 + M m=1 f 1 (p d 0m ) + γ m N d 0m -γ m D m ( 19
)
which nullifies at the optimum delay, i.e.

∇ N d * 0m L = 0. Therefore, if K k=1 s km = 1, i.e ∃ (k, m) such that s km = 1, then α d 0m = 0. Moreover if K k=1 s km = 0, i.
e there is no relay that minimizes the overall energy consumed when serving user m, then a direct transmission is preferable and the optimal allocated power p d 0m for direct transmission is given by:

p d 0m = α d 0m -γ m -k 1 k 2 + ( 21
)
where [.] + △ = max {0, .}. Moreover, optimizing respectively over the variables N c 0km and N c km , we get the following:

∇ N c 0km L = s km (f 2 (p c 0km ) + γ m ) -α c 0km (22)
∇ N c km L = s km (f 3 (p c km ) + γ m ) -α c km ( 23
)
and then at the optimum point ∇ N c * 0km L = 0 and ∇ N c * km L = 0. Therefore, if s km = 0, then α c 0km = 0 and α c km = 0. Moreover, let us consider that a relay k is selected to help user m, then s km = 1. Hence, using ( 22) and ( 23), the allocated powers when BS or relay k communicating with user m are respectively p c 0km and p c km and are given by:

p c 0km = (α c 0km -γ m -k 3 ) k 4 + ( 24
)
p c km = (α c km -γ m -k 5 ) k 6 + (25)
Since, γ m , k 1 , k 3 and k 5 are positive, then

α d 0m ≥ γ m + k 1 , α c 0km ≥ γ m + k 3 and α c km ≥ γ m + k 5 .

B. Optimal delay

By deriving L w.r.t to the primal variable p d 0m , we get the following:

∇ p d 0m L = 1 - K k=1 s km k 2 N d 0m + µ + α d 0m ∇ p d 0m F d 0m ( 26
)
where

F d 0m = 1 1-Π d 0m
and at the optimum ∇ p d * 0m L = 0. Since the constraint (c 3 ) has to be satisfied, the value of [START_REF]Graph implementations for nonsmooth convex programs[END_REF]. Then, α d * 0m is obtained by solving numerically ∇ p d * 0m L = 0. Moreover, by applying the gradient of L over p c km and p c 0km , we obtain receptively:

N d 0m is substituted in
∇ p c km L = s km k 6 N c km + µ + α c km F 1 F 2 ∇ p c km F 3 (27) ∇ p c 0km L = s km k 4 N c 0km + µ + α c 0km ∇ p c 0km F 1 +α c km ∇ p c 0km (F 1 F 2 F 3 ) (28)
with The addition of the constraints from (c3) to (c5) in ( 16) allows us to solve the power allocation problem by computing iteratively the Lagrange multipliers α d 0m , α c 0km , α c km and substituting the values in [START_REF] Lagrange | Throughput of HARQ Protocols on a Block Fading Channel[END_REF], [START_REF] Boyd | Convex Optimization[END_REF] and [START_REF] Grant | CVX: Matlab software for disciplined convex programming, version 2.1[END_REF].

F 1 (p c 0km ) = 1 1 -Π c 0m Π c 0km (29a) F 2 (p c 0km ) = Π c 0m (1 -Π c 0km ) (29b)
F 3 (p c km ) = 1 (1 -Π c km ) (29c

C. Relay selection strategy

Our problem relies also on relay selection, i.e. determining the value of s km that leads to the minimum energy path. Hence, minimizing the primal problem w.r.t. s km [START_REF] Hui | Cross-Layer Design for OFDMA Wireless Systems With Heterogeneous Delay Requirements[END_REF], we get the following:

∇ s km L = Z km + φ m (30)
with

Z km = (f 3 (p c km ) + γ m )N c km + (f 2 (p c 0km ) + γ m )N c 0km -(f 1 (p d 0m ) + γ m )N d 0m (31)
and

∇ s km L| λ * km = 0, if s km ∈]0, 1[, < 0, if s km = 1. (32)
Z km can be interpreted as a weighted difference between the energy consumption of a relay-assisted communication and a direct communication. Since φ m is common to all relays, only the relay k with the smallest Z km can be selected to help the user m. Hence, s km = 1 if Z km < 0 and s km = 0 if Z km > 0. The relay selection strategy can be summarized in Algorithm 1:

Algorithm 1 Relay Selection Procedure 1: for m = 1 : M do 2: if Z km > 0 ∀ k ∈ K then 3:
s km = 0 Find α c 0km and α c km , ∀ (k, m) ∈ K × M, by solving the system of non-linear equations ∇ p c 0km L = 0 and ∇ p c km L = 0 by applying Newton-Raphson method.

6:

Apply the relay selection strategy in Algorithm 1 Return to step 1 21: end while

V. ENERGY MINIMIZATION ALGORITHM

As it can be noticed, the optimization problem in ( 18) is a maximization problem with no constraint and it can be solved w.r.t. γ m , µ, α km with subgradient method.

The Lagrange multipliers γ m and µ are updated according to (33) and (34) respectively. Moreover, β γm and β µ are constant steps belonging to ]0, 1[. For each µ, the Lagrange multiplier γ m is updated in parallel for every user m until they satisfy their delay constraints. Thereafter, the optimal Lagrange variables α d * 0m , α c * 0km and α c * km are obtained as explained in Section IV. Then, the resource scheduler performs the relay selection strategy defined in Algorithm 1 until all users satisfy their delay constraints or reaching a stopping criterion.

Algorithm 2 jointly allocates powers at BS and RS and selects an optimal relay if needed. This algorithm firstly starts by initializing the Lagrange multiplier µ (step 1) that is related to the power constraint. Then, the resource scheduler updates

γ m (t + 1) = γ m (t) + β γm 1 - K k=1 s km N d 0m + K k=1 s km N c 0km + N c km -D m + (33) µ(t + 1) = µ(t) + β µ P tot - M m=1 1 - K k=1 s km p d 0m + K k=1 s km (p c 0km + p c km ) + (34)
for all users in parallel the Lagrange multiplier γ m (steps 3 to 7) until they satisfy their delay constraints. If γ m (t) = 0 for t > 1 this means that delay of user m is less than D m .

For each updated γ m , the resource scheduler has also to find the variables α d * 0m , α c * 0km and α c * km that nullify ( 26), ( 27) and [START_REF] Chen | A Dual Least-Square Approach of Tuning Optimal Propagation Model for Existing 3G Radio Network[END_REF]. The algorithm then associates a relay k to a user m or not according to the minimal energy path (step 6). If the power constraint P tot can satisfy all users, the algorithm stops. Otherwise, the Lagrange multiplier µ is updated according to (34) and the resource scheduler restarts allocation process.

In order to better understand how the resource scheduler allocates the power according to the delays and power constraints, let us consider only one user and a relay k is selected to assist this user such as the allocated power is p m = p c 0km + p c km . Fig. 2 shows the average energy and average delay versus the power p m for user m. Moreover, the energy curve has a minimum E min at p m = p Emin which corresponds to a delay D Emin . Therefore, the average energy function is strictly decreasing for p m < p Emin and increasing for p m > p Emin . Several operating conditions may occur during the power allocation process that can be stated as follows:

• If user m has a delay constraint D m < D Emin , then the required power is such as p m > p Emin , since the delay versus p m is strictly decreasing. Hence, if p m ≤ P tot , user m is served otherwise, it goes in starvation. • If D m ≥ D Emin , then the required power p m ≤ p Emin .

Therefore if p Emin ≤ P tot , then the optimal power p m leading to the minimum energy consumed is the solution of N c 0km + N c km = D Emin , i.e p m = p Emin and the consumed energy is E min . In that case, the problem is equivalent to find the minimum of the energy function without considering the delay constraint (γ m = 0).

• If D m ≥ D Emin and p Emin > P tot , the resource scheduler has to allocate a power in p m ∈ ]0, p Emin [ and thus the energy function starts increasing as p m decreases (decreasing p m means increasing the delay and thus increasing the energy consumption). Hence, µ is updated until p m ≤ P tot and until the inequality

N c 0km + N c km ≤ D m is satisfied.
If such a power can be achieved then the user is served, otherwise, it goes in starvation. This example also shows that the total consumed energy is at its minimum value if the power constraint is relaxed, i.e. large P tot . As Algorithm 2 updates µ, this signifies that some users have not yet satisfied their delay constraints and hence P tot is not large enough to serve all users. By referring to Fig. 2, powers that satisfy the inequality constraint in (c 1 ) are on the Therefore, as µ increases, the system energy consumption increases. If all delay constraints are exactly satisfied but there is no sufficient amount of power, then the problem is infeasible. Hence, the resource scheduler rejects the user that has the greater energy ratio ER m (step 18) and restarts allocation process. With multiple users, global optimum cannot be ensured because of possible multiple local minima involved in the objective function. However, our algorithm ensures to find at least a local minimum satisfying the constraints. The energy ratio for each user is defined as the ratio of the average energy consumed in Joules, i.e. E * m , and the average delay associated in seconds. If the delay in time slots is N * m and the time slot duration in second is N F /∆f (resource block duration), then ER m is expressed in Watts and can be written as:

ER m = ∆f × E * m N F × N * m ( 35
)
Algorithm 2 solves the modified problem in [START_REF] Maaz | Energy Efficiency Analysis of Hybrid-ARQ Relay-Assisted Schemes in LTE-Based Systems[END_REF], i.e. considering the delays as variables and forcing them to be equal to their expressions in constraints (c3)-(c5). This reformulation allows to iteratively solve the powers to be allocated to each user by computing the Lagrangian multipliers α d 0m , α c 0km and α c km as discussed in the previous section. Since the problem is non linear, the powers cannot be obtained directly and require an iterative procedure. Moreover, if the problem is infeasible, e.g. the power budget is not high enough to satisfy all the users' delay, the rejection of the user the less energy-efficient guarantees the algorithm to end. This highlights the importance of monitoring the starvation rate and the energy consumption at the same time.

VI. MCS AND RESOURCE BLOCKS ALLOCATION PROBLEM

In LTE system, the resource allocation manager selects for every user an MCS and a certain number of time/frequency resource blocks in order to satisfy the demanding QoS. We assume that the number of possible MCS is N mcs and the total number of frequency resource blocks is N RB . For a given allocated power policy, the energy consumed by the system depends on MCS and RBs. The minimization of the consumed energy can be formulated in the canonical form as follows: (36) where E mcs mr is the energy consumed for a particular MCS, i.e. mcs, and a number of RBs, i.e. r, p mcs mr is the power allocated per subcarrier for user m and N RB , N mcs are the sets of RBs and MCS respectively. Moreover, N s is reminded to be the number of subcarriers per RB. The problem in (36) is a binaryinteger programming problem, since the variables x mcs mr and r in (c 1 ) and (c 3 ) are binary and integer respectively. The constraint (c 2 ) ensures that only one combination of MCS and RB is attributed for every user u m . The constraint (c 3 ) ensures that the total number of allocated RBs for all users is less than or equal to N RB . The constraint (c 4 ) states that the overall allocated power is constrained by P tot .

Integer programming problems are in general NP-difficult to solve. However, some efficient algorithms can be found and perform well in practice. Dedicated solvers to mixed integer and convex problem exist in open or professional literature such as Gurobi and MOSEK [START_REF] Grant | CVX: Matlab software for disciplined convex programming, version 2.1[END_REF]. In order to efficiently solve problem (36), we used the CVX toolbox in conjunction with an integer programming solver [START_REF] Grant | CVX: Matlab software for disciplined convex programming, version 2.1[END_REF], [START_REF]Graph implementations for nonsmooth convex programs[END_REF] in order to provide for every user, the optimal number of RBs and MCS index leading to the minimum energy consumption. The global procedure iterates the integer programming solver for each allocated power p mcs mr obtained in Algorithm 2 until all users are satisfied or a non feasible solution is declared. In that case, the user with the highest energy consumption goes in starvation and the algorithm restarts allocation. In other words, for a given µ, Algorithm 2 first computes the required powers that satisfy the delay constraints for all users, MCS and number of RBs. Then, for every user with any possible selection of a couple of MCS and number of RBs, the energy and power values found in Algorithm 2 are used as inputs in the optimization problem in (36). Then, the solver searches for the best number of RBs in frequency and the best MCS that minimize the energy consumption under the total power constraint, i.e. (c 4 ) in (36). If the power constraint cannot be satisfied, the Lagrange multiplier µ is updated and the process described above is repeated. The computational complexity order of Algorithm 2 depends on the number of relays K, the number of MCS N mcs and the total number of frequency resource blocks N RB and is O(K × N mcs × N RB ). The powers are allocated in parallel for all users and hence only memory space in this dimension, i.e. M , is required. It is also worthwhile noting that each update of the Lagrange multiplier µ involves the execution of the Newton-Raphson algorithm to obtain the multipliers α d 0m , α c 0km and α c km . However, the complexity of this algorithm is quite low and the convergence really fast (less than 10 iterations). The update of the Lagrange multipliers µ and γ m are performed through a sub-gradient method, i.e. in (33), (34), which is a very low complexity procedure. Technically, the complexity of problem (36) is in O 2 M×Nmcs×NRB . However, the MOSEK solver that we adopted for solving this problem uses the semidefinite optimization by binary relaxation to get a lower bound on the optimal solution with polynomial complexity [START_REF] Mosek | Mosek modeling manual[END_REF].

VII. NUMERICAL ANALYSIS

This section investigates the performance of our algorithms in terms of the overall energy consumption [Joule/bit] and the average starved user rate, i.e. the average number of users that cannot satisfy their delay constraint. Our relayassisted resource allocation algorithms are compared to direct communications. A single circular cell of radius R = 1 km is considered, with 4 circularly distributed relays located at distance R/2 from BS. We also consider that M = 4, 8 or 12 users are uniformly distributed in the cell. The resource scheduler can select different MCSs according to Table I, where each packet contains L = 1024 information bits. The same path loss model is used for each link, i.e. BS-RS, RS-UE and BS-UE, and the path loss gain in dB between nodes i and j is l ij = -139.90 -34.41 • log 10 (d ij ), where d ij is the distance between two nodes in km [START_REF] Chen | A Dual Least-Square Approach of Tuning Optimal Propagation Model for Existing 3G Radio Network[END_REF]. Moreover, the circuitry power consumption per subcarrier at BS is about 17 dBm and at RS and UE, the circuity power consumption is about 7 dBm. This parameter settings will be used throughout this section unless otherwise mentioned. Let us consider that each user has a delay constraint D m = 3 ∀ m to be satisfied. Figures 3 and4 show the overall consumed energy and the average starvation rate w.r.t. the power constraint P tot in dBm respectively. One can notice that as the total power budget increases the starvation rate decreases as expected since more and more users can be served when the power constraint becomes less stringent. For M = 4 on Fig. 3, we can observe that the energy consumption starts increasing up to P tot = 38 dBm due to the decrease in starvation user rate leading to a higher number of satisfied users and hence a larger energy consumption. At P tot = 38 dBm, the energy consumption achieves a maximum and the starvation rate is nearly zero. For higher power budget, the overall energy slightly decreases and finally becomes constant for large values of P tot . When M = 8, 12 the same behavior can be observed but at different P tot . A stringent power budget leads to a low energy consumption but to a high number of unsatisfied users. As the available amount of power increases, the energy consumed increases but the number of satisfied users increases also. For instance, for M = 8 the energy consumption of direct and cooperative networks increases up to P tot = 44 dBm for which the starvation rate reaches zero. While the starvation rate is nearly the same for networks with and without cooperation, this is not the case for energy consumption for which significant gains can be expected with relay-assisted communications. For M = 4, relay-assisted scheme can save about 31 % of energy compared to direct transmission and for P tot = 45 dBm the energy saving between cooperative and direct transmissions achieves 28 and 29% for M = 8 and 12 respectively. It is worth mentioning that when comparing the starvation rate of direct and relayassisted transmissions, this should be done with a look on the consumed energy for a fixed power constraint. Indeed, the power constraint P tot can be partially or completely consumed, according to the users' position, and does not give any information how much power is consumed. Moreover, since the consumed energy depends on the circuitry power consumption and the required transmission power for all users, relay-assisted network makes a better use of power than non relay-aided system, in average. Fig. 5 depicts for cooperative transmission the total average required power in Watts (the sum of all optimized powers for all users) as a function of the delay constraint and the number of users, i.e. M = 4, 8 and 12. We firstly notice that the required power increases as the number of users increases and this difference is larger for small delay constraint, i.e. D m = 3 TSs, than higher delay constraint, i.e. D m = 4 TSs. Moreover, the required transmission power reduces if the delay constraint becomes loose whatever the number of users considered. The required transmission power for M = 12 and stringent delay constraint, e.g. D m = 3, is very high compared to M = 4 and 8 since the number of frequency RBs has to be shared among more users and then the delay constraints can only be satisfied by allocating high transmission powers for all users. On the other hand, higher delay constraints can be satisfied by selecting a lower number of resource blocks leading to a lower transmission power. Figures 6 and7 represent the fraction of usage of different MCS as function of the total power budget, for direct and cooperative transmissions respectively and for M = 12. For very stringent power constraint, a large starvation user rate can be observed as it has been previously remarked. Moreover, in this case, the most common MCS is the one with the lowest index, corresponding to a QPSK and a low coding rate inducing a low energy consumption but also a low data rate. As P tot increases, the starvation rate decreases and more users can be satisfied and high MCS indexes start to be used, enabling a higher spectral efficiency. It is also interesting to remark that relay-assisted scheme, Fig. 7, enables the use of the MCS 9, i.e. allowing the highest spectral-efficiency, for P tot = 45 dBm, which is not possible for a cell without relays as it can be inferred from Fig. 6.

Figure 8 depicts the average consumed energy (Joule/bit) w.r.t. the delay constraint in time slots, for M = 4 and 8 when there is no constraint on power. From this figure, one can remark that relay-assisted scheme outperforms direct transmissions whatever the delay constraint. For large delay constraints, i.e. 4.5 TS, the energy saving reaches about 27% and 31% for 4 and 8 users respectively. For M = 4, the energy consumed remains relatively constant w.r.t. the delay constraint. This is because the power budget and the number of available RBs are sufficiently important to satisfy the users whatever their delay constraints. On the other hand, for M = 8, the overall consumed energy significantly decreases for both direct and cooperative transmissions. For low values of delay constraint, the communication becomes more stringent and then more resource blocks are needed leading to a higher energy consumption. As the delay constraint becomes loose, the resource manager may operate at power values that lead to the minimum energy consumption. Since the spectral efficiency that the network may achieve is also of great interest, Fig. 9 plots the tradeoff between the average consumed energy and the delivered throughput efficiency (bits/sec/Hz) in the network. As it can be noticed, for M = 4, the spectral efficiency increase is almost energy-free except for very high spectral-efficiency region and cooperative scheme. In this case indeed, there are enough resource blocks to satisfy all users. Moreover, cooperation enables an energy saving of about 26 % compared to a direct transmission. For M = 8, the energy consumption logically increases with the spectral efficiency, since the number of resource blocks becomes not sufficient w.r.t. the number of users and their constraints. However, for M = 8 and for a spectral efficiency of 9 bits/sec/Hz, we can see that cooperation enables an energy saving of about 34 % compared to the direct transmission.

VIII. CONCLUSION

In this work, an energy minimization problem for LTE multi-user relay-assisted HARQ network has been investigated. The energy optimization problem has been tackled under total power and individual user delay constraints and considering static and dynamic energy consumption of nodes. Moreover, HARQ-I protocol has been taken into account when optimizing resources. A new energy minimization algorithm that jointly allocates the optimal power at base station and relays has been proposed. In addition to the power allocation, a relay selection procedure is performed to determine whether direct or cooperative transmission is preferable for a particular user from an energy consumption point of view. Moreover, based on the energy minimization algorithm, we proposed a binary and integer programming problem that jointly chooses the optimal MCS and number of RBs for every user according to the total power budget. Our investigations have shown that the proposed algorithms allow to save up to 30% of energy in relay-assisted network compared to direct communications between BS and mobiles. In further works, advanced HARQ mechanisms and multi-cell environments could be investigated.

Fig. 1 :

 1 Fig. 1: Resource blocks (RB) sharing scheme between users.

  ) where at the optimum ∇ p c * km L = 0 and ∇ p c * 0km L = 0. Since the equality constraints (c 4 ) and (c 5 ) have to be satisfied, the values of N c km and N c 0km are respectively substituted in (27) and (28), and the optimal values of the Lagrange multipliers α c * 0km and α c * km are obtained by applying the Newton-Raphson method to the system of two equations ∇ p c * km L = 0 and ∇ p c * 0km L = 0.

2 4 :

 24 Joint Power and Relay Selection algorithm 1: Initialize: µ ← 0 2: Initialize: γ m ← 0 ∀m ∈ M 3: while ∃m s.t. (c 1 ) not satisfied do Find α d 0m by solving ∇ p d 0m L = 0 ∀ m ∈ M 5:

18 :

 18 Reject u m = arg max m {SR m : m ∈ M} 19: M = M -{u m } 20:

Fig. 2 :

 2 Fig. 2: Energy-Delay versus power p m = p c 0km + p c km

  (c 1 ) x mcs mr ∈ {0, 1} ∀(m, r, mcs) ∈ M × N RB × N mcs (c 2 ) mcs mr p mcs mr ≤ P tot

Fig. 3 :

 3 Fig. 3: Average energy consumption in Joule/bit versus Ptot in dBm. The number of users is M = 4, 8 and 12 and each user has a delay constraint of 3 time slots.

Fig. 4 :

 4 Fig. 4: Average starvation user rate versus Ptot in dBm. The number of users is M = 4, 8 and 12 and each user has a delay constraint of 3 time slots.

Fig. 5 :

 5 Fig. 5: Average required power in Watts versus the delay constraint in time slots, labeled on the number of users, i.e. M = 4, 8 and 12.

Fig. 7 :

 7 Fig. 7: Fractions of usage of MCS w.r.t. the power constraint in cooperative network with M = 12. Each user has a delay constraint of 3 time slots.

8 M = 8 M = 4 Fig. 8 :

 8848 Fig. 8: Average consumed energy in joule/bit w.r.t. the delay constraint in Time Slots. The number of users is M = 4 and 8.

Fig. 9 :

 9 Fig. 9: Average consumed energy in joule/bit w.r.t. the throughput efficiency in bits/sec/Hz. The number of users is M = 4 and 8.

TABLE I :

 I Curve fitting parameters a, b and c for each MCS

	MCS index	QAM	Coding rate ×1024	a	b	c	# of RBs
	1	4	449	17.76	-1.90	4.25	15
	2	4	602	17.69	-1.50	3.98	12
	3	16	378	69.94	-1.64	3.65	9
	4	16	490	43.34	-1.27	3.85	7
	5	16	616	50.91	-1.22	2.98	6
	6	64	466	76.76	-1.04	3.98	5
	7	64	567	125.87	-1.16	2.49	4
	8	64	666	174.46	-1.20	1.75	4
	9	64	772	232.16	-1.30	0.97	3

TABLE II :

 II System model parameters

	Parameters	Description	value
	fs	Sampling rate	7.68 MHz
	Bw	Bandwidth	5 MHz
	∆f	Subcarrier spacing	15 kHz
	Nc	Number of subcarriers (FFT size)	512
	N CP	Cyclic prefix	128
	Ng	Number of Guard subcarriers	211
	N OFDM Number of OFDM symbols in a block	7
	NRB	Maximum number of RBs	25
	L	Block length	1024
	fc	Carrier frequency	2.6 GHz
	N0	Noise spectral density	-174 dBm/Hz
	βamp	Power amplifier inefficiency	1

  0018-9545 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TVT.2017.2654684, IEEE Transactions on Vehicular Technology TO APPEAR IN IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. XX, NO. XX, XXX 2017 10 Fig. 6: Fractions of usage of MCS w.r.t. the power constraint in direct networks with M = 12. Each user has a delay constraint of 3 time slots.

		0.8
															Starvation
															MCS 1
		0.7													MCS 2
								Starvation		MCS 5				MCS 3 MCS 4
		0.6													MCS 5
	Fractions of usage of MCS	0.3 0.4 0.5													MCS 6 MCS 7 MCS 8 MCS 9 MCS 7
		0.2
		0.1
		0	33	34	35	36	37	38	39	40	41	42	43	44	45
									Ptot [dBm]
		0.8
															Starvation
															MCS 1
		0.7					Starvation							MCS 2 MCS 3
											MCS 5				MCS 4
		0.6													MCS 5
	Fractions of usage of MCS	0.3 0.4 0.5											MCS 7	MCS 6 MCS 7 MCS 8 MCS 9
		0.2
															MCS 9
		0.1
		0	33	34	35	36	37	38	39	40	41	42	43	44	45
									Ptot [dBm]

TO APPEAR IN IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. XX, NO. XX, XXX 2017

ACKNOWLEDGMENT

The authors would like to thank the anonymous reviewers and the editor whose constructive comments have significantly helped to improve the quality of the paper. Dr. Philippe Mary wants to thank the Labex Cominlabs ANR-10-LABX-07-01 which partially supports this work.