Farah Moety

Samer Lahoud

Bernard Cousin
email: bernard.cousin@irisa.fr

Kinda Khawam
email: kinda.khawam@prism.uvsq.fr

Joint Power-Delay Minimization in 4G Wireless Networks

In this paper, we formulate an optimization problem that jointly minimizes the network power consumption and transmission delay in broadband wireless networks. Power saving is achieved by adjusting the operation mode of the network Base Stations (BSs) from high transmit power levels to low transmit levels or switched-off. Minimizing the transmission delay is achieved by selecting the best user association with the BSs. We study the case of a realistic Long Term Evolution (LTE) Network where the challenge is the high computational complexity necessary to obtain the optimal solution. Therefore, we propose a simulated annealing based heuristic algorithm for the power-delay minimization problem. The proposed heuristic aims to compute the transmit power level of the network BSs and associate users with these BSs in a way that jointly minimizes the total network power and the total network delay. The simulation results show that the proposed algorithm has a low computational complexity which makes it advantageous compared with the optimal scheme. Moreover, the heuristic algorithm performs close to optimally and outperforms the existing approaches in realistic 4G deployments.

I. INTRODUCTION

In the past years, operators have focused on technological developments to meet capacity and Quality of Service (QoS) demands of the User Equipments (UEs). Recently, pushed by the needs to reduce energy, mobile operators are rethinking their network design for optimizing its energy efficiency and satisfying user QoS requirements. Knowing that over 80% of the power in mobile telecommunications is consumed in the radio access network, more specifically at the base stations (BSs) level [START_REF] Richter | Energy efficiency aspects of base station deployment strategies for cellular networks[END_REF], a lot of research activities focused on improving the energy efficiency of broadband wireless networks. In [START_REF] Richter | Energy efficiency aspects of base station deployment strategies for cellular networks[END_REF] [START_REF] Tombaz | Energy efficiency improvements through heterogeneous networks in diverse traffic distribution scenarios[END_REF], different network deployment strategies were studied and simulations showed that the use of low power BSs improves the network energy efficiency. Wu et al. [START_REF] Wu | Energy efficient coverage planning in cellular networks with sleep mode[END_REF] studied the coverage planning in cellular networks taking into account the sleep mode and the power adjustment for energy saving. Hossain et al. [START_REF] Hossain | A protocooperationbased sleep-wake architecture for next generation green cellular access networks[END_REF] proposed an energy efficient algorithm in cellular networks based on the principle of cooperation between BSs. In this algorithm, the BSs dynamically switch between active/sleep modes or change their transmit power depending on the traffic situation. In the literature, there are quite few examples which consider the QoS (such as delay, blocking probability, etc) as an important criteria. Among them, Han et al. [START_REF] Feng Han | Energy-efficient cellular network operation via base station cooperation[END_REF] used deterministic patterns for switching BSs through mutual cooperation among BSs. QoS is guaranteed by focusing on the worst case transmission/reception location of the UE situated in the switched-off cell. For the LTE-Advanced standard, a greedy heuristic algorithm was proposed to switch off a BS according to the average distance of its users and without compromising the outage probability of the UEs [START_REF] Bousia | Distanceaware base station sleeping algorithm in LTE-Advanced[END_REF]. Niu et al. [START_REF] Niu | Cell zooming for cost-efficient green cellular networks[END_REF] proposed a centralized and a decentralized cell zooming algorithms based on the transmission rate requirements of the users and the capacity of the BSs. The proposed algorithms leverage the tradeoff between energy consumption and outage probability. Son et al. [START_REF] Son | Base station operation and user association mechanisms for energy-delay tradeoffs in green cellular networks[END_REF] formulated a joint minimization problem that allows for a flexible tradeoff between flow-level performance and energy consumption. Users are associated to BSs in such a way to minimize the average flow delay, and greedy algorithms are proposed for switching on/off the network BSs. The case where BSs switch between on and off modes without adjusting their transmit power was investigated.

In this paper, we tackle the joint optimization problem of power saving and transmission delay minimization in LTE networks. Specifically, power saving is achieved by adjusting the operation mode of the network BSs from high transmit power levels to low transmit levels or switched off. In this context, changing the operation mode of the BSs is coupled with user association. Such coupling makes solving the problem more challenging. Furthermore, minimizing the transmission delay is achieved by selecting the best user association with the network BSs.

Our approach presents multiple novelties compared to the state-of-the-art: i) we formulate the power-delay minimization problem as an non-linear optimization problem in 4G wireless networks. This formulation enables us to evaluate the tradeoffs between minimizing the network power consumption and the network delay. ii) Our formulation captures the specificity of LTE technology in terms of power model and radio resource allocation. iii) Unlike, most of the previous studies, we combine the different green approaches (BS on/off mode, adjustment of BS transmit power, user association) to provide power saving. Due to the high computational complexity of the Power-Delay-Min problem, we propose in this paper with a novel Simulated Annealing (SA) based heuristic algorithm for this problem. The heuristic computes satisfactory solutions for the problem while keeping the computation complexity suitably low for practical implementations. Thus, we apply our heuristic to real life scale scenario.

Our heuristic is based on the SA technique which is a probabilistic searching method. The proposed heuristic aims at computing the transmit power level of the BSs deployed in the network and associating users with these BSs in a way that jointly minimizes the total network power and the total network delay. In order to evaluate the efficiency of the heuristic algorithm for the Power-Delay problem, we compare the results obtained by this heuristic with the optimal solution and the existing solutions.

The rest of the paper is organized as follows. In Section II, we describe the network model considering an LTE network. In Section III, we present the Power-Delay minimization problem. In Section IV, we present our proposed heuristic algorithm. In Section V, we present the existing approaches. In Section VI, we provide the simulation results. Conclusions are given in Section VII.

II. NEWORK MODEL

We consider an LTE network with N bs BSs. We assume that the each BS operates in two modes: active and switchedoff. We denote by N l the number of transmit power levels of a BS. Transmitting at different power levels leads to different coverage area sizes. The indexes i ∈ I = {1, . . . , N bs }, and j ∈ J = {1, . . . , N l }, are used throughout the paper to designate, respectively, a given BS and its transmit power level. Note that, for j = 1 we consider that the BS transmits at the highest power level and for j = N l the BS is switched off. We term by k ∈ K = {1, . . . , N u }, the index of a given UE where N u is the number of UEs in the network.

A. Traffic and Delay Model

In this paper, we only consider the downlink traffic since it is several orders higher than the uplink one. We assume that i) the network is in a static state where UEs are stationary, ii) the network is in a saturation state. A saturation state is a worst case scenario where every BS has persistent traffic toward UEs. Moreover, in the emerging cellular systems such as LTE networks, Orthogonal Frequency Division Multiple Access (OFDMA) is adopted as the downlink access method. The latter allows multiple UEs to transmit simultaneously on different subcarriers. As subcarriers are orthogonal, intracell interference is highly reduced. Furthermore, in order to mitigate the inter-cell interference, we use the classical interference avoidance scheme which is the Frequency Reuse 3 scheme [START_REF] Elayoubi | Performance evaluation of frequency planning schemes in OFDMA-based networks[END_REF]. This scheme consists of dividing the frequency band into 3 sub-bands and allocates only one sub-band to a given cell, in such a way the adjacent cells use different frequency bands.

1) Radio Conditions:

The peak rate of a given UE is defined as the throughput experienced by the UE when alone in the cell. The peak rate of each UE depends on its received Signal to Noise Ratio (SNR). We denote by χ i,j,k the peak rate perceived by UE k from BS i transmitting at power level j.

2) Data Rate Model: In OFDMA, the system spectrum is divided into a number of consecutive orthogonal OFDM subcarriers. The Resource Block (RB) is the smallest resource unit that can be scheduled. The RB consists of 12 consecutive subcarriers for one slot (0.5 msec) in duration. In this paper, we consider a flat channel model where each UE has similar radio conditions on all the RBs. Moreover, we consider a fairtime sharing model where RBs are assigned with equal time to UEs within a given cell. These UEs are given the same chance to access the RBs. Based on these considerations and on UEs being stationary, the scheduler is equivalent to one that allocates periodically all RBs to each UE at each scheduling epoch. Hence, when UE k is associated with BS i transmitting at level j, its mean throughput R i,j,k depends on its peak rate χ i,j,k and on the number of UEs associated with the same BS. R i,j,k is given by [START_REF] Khawam | Individual vs. global radio resource management in a hybrid broadband network[END_REF]:

R i,j,k = χ i,j,k 1 + Nu k ′ =1,k ′ =k θ i,k ′ , (1)
where θ i,k ′ is the binary variable indicating whether or not UE k ′ is associated with BS i.

3) Delay Model: We denote by T i,j,k the amount of time necessary to send a data unit to UE k from BS i transmitting at level j. In fact, the bit transmission delay for a given UE is the inverse of the throughput perceived by this UE. Thus,

T i,j,k = 1 + Nu k ′ =1,k ′ =k θ i,k ′ χ i,j,k . (2)

B. Power Consumption Model

Following the model proposed in the Energy Aware Radio and neTwork tecHnologies (EARTH) project [START_REF] Auer | Energy efficiency analysis of the reference systems, areas of improvements and target breakdown[END_REF], the power consumption of a BS is modeled as a linear function of the average transmit power as below:

∀i ∈ I, p i,j =      N T RX • (vπ j + w j ), 0 < π j ≤ π 1 , j = 1, . . . , (N l -1); N T RX • w N l , π N l = 0. (3)
where p i,j and π j denote respectively the average consumed power per BS i and the transmit power at level j respectively. In our paper, the BS is switched off for j = N l . The coefficient v is the slope of the load-dependent power consumption and it accounts for the power consumption that scales with the transmit power due to radio frequency amplifier and feeder losses. The coefficients w j , j = 1, .., (N l -1), represents the power consumption at the zero output power (it is actually estimated using the power consumption calculated at a reasonably low output power, assumed to be 1% of π 1 ). These coefficients model the power consumption independently of the transmit power due to signal processing, power supply consumption and cooling. w N l is the coefficient that represents the sleep mode power consumption. N T RX is the number of BS transceivers.

C. Coverage Area

Transmitting at different power levels leads to different coverage area sizes. Note that, all UEs within the coverage area of a BS require some minimum received SNR for acceptable performance. In our paper, a UE is thus considered covered by a BS if its SNR is above a given threshold. As mentioned in II-A1, the peak rate perceived by a given UE depends on its SNR. Consequently, a UE is covered if it perceives a peak rate, from at least one BS, higher than a given peak rate threshold (χ threshold ).

III. OPTIMIZATION PROBLEM

A. Problem Formulation

Our approach is formulated as an optimization problem that consists in minimizing the power consumption of the network and the sum of the data unit transmission delays of all UEs. A key trade-off in our problem is between these two objectives. On the one hand, reducing the transmit power level of the BSs or switching them off to save energy may result in increasing the transmission delay (indeed, if there is no coverage constraints, then all BS could be switched off and no user is served: the transmission delay becomes infinite). On the other hand, to minimize the transmission delay, each BS should transmit at the highest power level possible.

The design variable in our Power-Delay problem is to decide what follows:

• The operation mode of the network BSs (on/off) and for active BSs, the corresponding transmit power level. • The users association with the network BSs. Let λ i,j be a binary variable that indicates whether BS i transmits at level j or not. λ i,j are the elements of the matrix Λ defining the operation mode of the network BSs. Let θ i,k be a binary variable that indicates whether a user k is associated with BS i or not. θ i,k are the elements of the matrix Θ defining the users association with the network BSs.

The Power-Delay-Min problem consists in computing the transmit power level of the BSs and in associating UEs with these BSs in a way that jointly minimizes the total network power and the total network delay. The total network power, denoted by C p (Λ), is defined as the total power consumption of active BSs in the network and is given by:

C p (Λ) = i∈I,j∈J N T RX • (vπ j + w j ) • λ i,j . (4)
The total network delay, denoted by C d (Λ, Θ), is defined as the sum of data unit transmission delays of all UEs in the network and is given by:

C d (Λ, Θ) = i∈I,j∈J,k∈K T i,j,k • λ i,j • θ i,k (5)
Therefore, the total network cost, denoted by C t (Λ, Θ), is thereby defined as the sum of power and delay components and is given by:

C t (Λ, Θ) = αC p (Λ) + ββ ′ C d (Λ, Θ), (6)
α and β are the weighting coefficients representing the relative importance of the two objectives. It is usually assumed that α + β = 1 and that α and β ∈ [0,1]. β ′ is a normalization factor that will scale the two objectives properly. Consequently, our Power-Delay-Min problem (P) is given by: minimize

Λ,Θ C t (Λ, Θ) = αC p (Λ) + ββ ′ C d (Λ, Θ), subject to (7) j∈J λ i,j = 1, ∀ i ∈ I, (8)
i∈I θ i,k = 1, ∀ k ∈ K, (9)
λ i,N l + θ i,k = 0, ∀ (i, k) : i ∈ I, k ∈ K. (10)
Constraints [START_REF] Feng Han | Energy-efficient cellular network operation via base station cooperation[END_REF] state that every BS transmits only at one power level. Constraints [START_REF] Hossain | A protocooperationbased sleep-wake architecture for next generation green cellular access networks[END_REF] ensure that a given UE is connected to only one BS. Finally, constraints [START_REF] Khawam | Individual vs. global radio resource management in a hybrid broadband network[END_REF] ensure that a given UE is not associated with a switched off BS.

B. Optimal Solution

(P) is a binary non-linear optimization problem. Such problem can be solved using an exhaustive search algorithm [START_REF] Moety | Power-delay tradeoffs in green wireless access networks[END_REF]. However, the complexity of searching only for the operation mode of the BS is in O(N N bs l ). This makes the exhaustive search very computational intensive, and rapidly becomes intractable for modest sized networks. In [START_REF] Moety | Joint powerdelay minimization in green wireless access networks[END_REF], we converted (P) into a MILP problem and used a branch-andbound (BB) approach to solve it. In the latter approach, the number of integer variables determines the size of the search tree and impacts the computation time of the algorithm. Thus, we noted that our MILP conversion can not deliver solutions for realistic networks. Hence, in this paper we introduce a heuristic that computes satisfactory solutions for the problem while keeping the computation complexity suitably low for practical implementations.

IV. HEURISTIC ALGORITHM

Due to the high computational complexity of the Power-Delay-Min problem, we propose in this paper a novel SA heuristic algorithm for this problem. The proposed heuristic aims at computing the transmit power level of the BSs deployed in the network and associating users with these BSs in a way that jointly minimizes the total network power and the total network delay.

The SA algorithm includes an acceptance probability, which can prevent the algorithm from terminating at local minima [START_REF] Pham | Intelligent Optimisation Techniques: Genetic Algorithms, Tabu Search, Simulated Annealing and Neural Networks[END_REF]. Such characteristic is very suitable to our problem. Moreover, there is a number of other features associated with the SA algorithm that is of particular appeal to our formulation: its ability to scale for large scale optimization problems, and its effectiveness against the exhaustive search.

Our heuristic starts with an initial feasible solution where all the network BSs transmit at the corresponding power level and all UEs are associated with the network BSs. Such solution determines the total network cost. Then, at each iteration, a BS is randomly chosen to change its transmit power level which is selected uniformly from the available power levels. For each change of the BS transmit power level, UEs are associated with the best BS according to Power-Coverage Based User Association (PoCo-UA) (explained later in Section IV-A1). This is a candidate solution to be used and its total network cost is computed. The candidate solution is accepted as a current solution based on a certain probability. Typically, the steps are repeated until a given stop criterion is satisfied.

A. SA Heuristic Algorithm for the Power-Delay-Min Problem

Algorithm 1 describes the different steps of our SA heuristic algorithm for the Power-Delay-Min problem. The algorithm takes as inputs the number of BSs, the number of transmit power levels, the number of UEs in the network, and the initial solution: initial operation mode of the BS Λ 0 , initial user association Θ 0 , initial cost total network cost C 0 t (Step 1). The algorithm outputs the operation mode of the BSs Λ SA , the user association Θ SA and the total network cost C tSA (Step 2). Let N iterations denotes the maximum number of the algorithm's iterations and C q t denotes the total network cost at iteration q. Let ǫ be the precision parameter, and T be a positive constant. The algorithm starts with an initial feasible solution where all the network BSs transmit at the corresponding power level and all UEs are associated with the network BSs. Such solution determines the initial total network cost which is computed according to [START_REF] Elayoubi | Performance evaluation of frequency planning schemes in OFDMA-based networks[END_REF]. Then, at each iteration, a BS is randomly chosen to change its transmit power level which is selected uniformly from the available power levels (Step 4). Afterwards, the coverage constraint is verified for all UEs in the network (Step 5). If all network UEs are covered then each UE is associated with the active BSs according to PoCo-UA (Step 6), and the total network cost C * t is computed according to (6) (Step 7). This is a candidate solution to be used. If the difference of the total network cost between the candidate solution and the current solution is negative, the candidate solution is directly taken as the current solution (Step 11). Otherwise, it is accepted as the current solution with probability e (C * t -C q-1 t )/T (Step 13). Typically, the iterations are repeated until a given stop criterion is satisfied. For instance, a maximum number of iterations has been exceeded (Step 3) or no more improvement in terms of total network cost can be achieved (Step 8). Once the stopping criteria is met, the algorithm outputs the operation mode of the BSs Λ SA and the user association Θ SA of the iteration q SA that has the minimal total network cost C qSA tSA (Steps 19 and 20).

1) Power-Coverage Based User Association (PoCo-UA): Algorithm 2 describes the different steps of PoCo-UA. The PoCo-UA algorithm takes as inputs the set of BSs covering UE k denoted by Ψ k , and the number of UEs covered by BS ψ denoted by c(ψ) (Step 1). It outputs the user association denoted by Θ P oCo-U A (Step 2). For UEs covered by several BSs (Step 5), the algorithm proceeds as follows: each UE k computes two coefficients r ψ k and ρ k ψ for each of its covering BS ψ ∈ Ψ k (Step 7). These coefficients take into consideration respectively the received SNR at the UE side and the number of UEs covered by the corresponding BS. We combine these coefficients with a probability function in such a way that the Algorithm 1 SA Heuristic Algorithm for the Power-Delay-Min Problem 1: Input: N bs , N l , N u , Λ 0 , Θ 0 , C 0 t . 2: Output: Λ SA , Θ SA , C tSA ; 3: for q=1 to N iterations do 4: compute new operation mode of the BS Λ * ; 5:

if ∀k ∈ K, ∃(i, j) ∈ (I, J)/χ i,j,k • λ * i,j ≥ χ threshold then 6:
Compute the new user association Θ * according to PoCo-UA; if

|C * t -C q-1 t | C q-1 t < ǫ then 9: break; 10: else if C * t -C q-1 t ≤ 0 then 11: C q t = C * t , Λ q =Λ * , Θ q =Θ * ; 12: else if C * t -C q-1 t > 0 then 13: C q t = C * t , Λ q =Λ * , Θ q =Θ * with probability e (C * t -C q-1 t )/
if |Ψ k | = 1 then 6: for ψ ∈ Ψ k do 7: Compute r ψ k = χ ψ,j,k ψ∈Ψ k χ ψ,j,k , ρ k ψ = c(ψ) ψ∈Ψ k c(ψ) ; 8: Compute δ ψ,k = r ψ k /ρ k ψ ψ∈Ψ k r ψ k /ρ k ψ ; 9: ∆ k ← ∆ k ∪ {δ ψ,k }; 10:
end for 11:

ψ * k = Random(Ψ k , ∆ k ) ⇒ θ heur = θ ψ * k ,k = 1;
12: else 13:

ψ * k = {Ψ k } ⇒ θ heur = θ ψ * k ,k = 1; 14:
end if 15: end for probability to be associated with a given BS is proportional to the peak rate perceived by the UE and inversely proportional to the number of UEs covered by the corresponding BS. Then, each UE k computes δ ψ,k the probability to be associated with BS ψ (Step 8).

The complexity of executing PoCo-UA algorithm is in

O(N u × |Ψ k | log |Ψ k |).
The complexity of executing the heuristic algorithm for the Power-Delay-Min problem (Algorithm 1) corresponds to the complexity of executing PoCo-UA at each change of the transmit power level for each BS. Hence, the complexity of Algorithm 1 is in:

O(N u × |Ψ k | log |Ψ k | × N iterations ). (11)
V. EXISTING APPROACHES

In this paper, we consider two existing approaches. The first approach, denoted by A 1 , is based on legacy cellular networks where BSs transmit at a fixed power level and UEs are associated with the BS delivering the highest SNR [START_REF] Wang | Energy efficiency of heterogeneous cellular network[END_REF]. Therefore, in A 1 , we assume that all BSs transmit at the highest power level. In this case, all UEs are thus covered by at least one BS and they are associated with the BS delivering the highest SNR.

The second approach, denoted by A 2 , is based on the existing approaches that consists in minimizing the total network power while ensuring the coverage constraint for all network UEs. It also considers the power adjustment capability of the BS as in our approach. We introduce a new parameter ρ i,j,k that indicates whether user k is covered by BS i transmitting at power level j. Thus, approach A 2 can be formulated as the following optimization problem (P 1 ):

minimize Λ C p (Λ) subject to (12) j∈J λ i,j = 1, ∀ i ∈ I, (13)
i∈I,j∈J

ρ i,j,k • λ i,j ≥ 1, ∀ k ∈ K, (14)
Constraints [START_REF] Niu | Cell zooming for cost-efficient green cellular networks[END_REF] state that every BS transmits only at one power level. Constraints [START_REF] Pham | Intelligent Optimisation Techniques: Genetic Algorithms, Tabu Search, Simulated Annealing and Neural Networks[END_REF] ensure that a given UE covered by at least one BS. Solving problem (P 1 ) provides the operation mode of the network BSs. For the user association, UEs are associated with the BS delivering the highest SNR.

For both approaches, the total network power, the total network delay and the total network cost are computed respectively according to (4), ( 5) and ( 6).

VI. PERFORMANCE EVALUATION

A. Evaluation Method

In order to study the efficiency of the proposed heuristic algorithm for the Power-Delay-Min problem, we implement this algorithm and compare its solution with the optimal one and the existing approaches. Based on our previous work in [START_REF] Moety | Joint powerdelay minimization in green wireless access networks[END_REF], we convert (P) into a Mixed Integer Linear Programming (MILP) problem. The optimal solutions of both MILP and (P 1 ) problems are solved using the BB method with the CPLEX solver. We consider the realistic positioning of the 4G network BS for the district 14 of Paris-France [START_REF]Antennes mobiles[END_REF]. The network topology is composed of 18 cells (N bs =18) and the positioning of UEs follows a random uniform distribution, as shown in Fig. 1. For the BS power model, we set for simplicity the number of transmit power levels to three (N l =3). Precisely, an active BS is able to transmit at two different power levels, and when the power level equals N l = 3, the BS is switched off. Moreover, we consider that the BSs are transmitting using omni-directional antennas. The simulated LTE system bandwidth is 5 MHz, therefore we have 25 RBs available in each cell. We assume a frequency reuse 3 scheme in the network to mitigate the inter-cell interference. Thus, the system bandwidth is divided into 3 equal sub-bands, each of these sub-bands are allocated to cells in a manner that no other surrounding cell is using the same sub-band. Consequently, we have 8 RBs available in each cell. The fair-time sharing model is used, and the scheduler allocates all RBs to one user at each scheduling epoch as explained in Section II-A2. Moreover, we assume a full buffer traffic model. The simulation parameters and the pathloss model follow that in [START_REF] Gpp | Spacial channel model for Multiple Input Multiple Output (MIMO) simulations v6.1.0[END_REF], [START_REF] Gpp | Evolved Universal Terrestrial Radio Access (E-UTRA)[END_REF] and [START_REF] Auer | Energy efficiency analysis of the reference systems, areas of improvements and target breakdown[END_REF], which are summarized in Tab. I.

In this paper, the Path Loss (P L) between the BS and the UE is computed according to the Cost 231 extended Hata model considering a urban environment [START_REF] Gpp | Evolved Universal Terrestrial Radio Access (E-UTRA)[END_REF], with a carrier frequency f of 2000 MHz. The shadowing is represented by a random variable following normal distribution with a mean of 0 dB and a standard deviation of 10 dB. a) Peak rate computation: Knowing the path loss, calculation of the signal strength S i,j,k detected by UE k from BS i transmitting at power level j is performed according to:

S i,j,k = 10 × log 10 (π j × 1000) -(P L -G T -G R ) [dBm], (15)
where G T and G R are respectively the transmit and receiver antenna gain. The SNR detected by UE k from BS i transmitting at power level j is thus given by: The thermal noise power denoted by T h N P is given by:

SN R = S i,j,k -T hermalN oiseP ower [dB]. (16)
T RX =1, v = 4.7, w 1 = w 2 = 130 W w 3 = 0 W Transmit power π 1 =10 W, π 2 =5 W π 3 =0 Average power consumed per BS i p i,1 =177 W, p i,2 =153.5 W, p i,3 =0 W (i = 1, . . . ,
T h N P = 10 × log 10 (1000 × T hermalN oiseDensity × BandwidthperRB × N umberof RBperCell) + N oiseF igure [dBm]. (17)
Knowing the SNR, calculation of the spectral efficiency (in bit/s/Hz) is performed according to Fig. 2 in the 3GPP TR 36.942 [START_REF] Gpp | Evolved Universal Terrestrial Radio Access (E-UTRA)[END_REF]. As mentioned earlier, the scheduler allocates all RBs to one user at each scheduling epoch. Therefore, to compute the peak rate χ i,j,k perceived by UE k from BS i transmitting at power level j in bit/s, we multiply the value obtained from Fig. 2 by the Bandwidth per RB and by the Number of RBs per cell.

Furthermore, we only consider the case where α=β=0.5 in [START_REF] Grodzevich | Normalization and other topics in multi-objective optimization[END_REF]. This balances the tradeoff between minimizing power and delay. The normalization factor β ′ is calculated in such a way to scale the total network power and the total network delay [START_REF] Grodzevich | Normalization and other topics in multi-objective optimization[END_REF]. Moreover, the user association problem is a very challenging one. Therefore, in each iteration of the heuristic algorithm, we run the PoCo-UA user association (Algorithm 2) 10 times and select the best θ P oCo-U A that gives the minimal total network delay. In our SA heuristic algorithm, we take N =10 3 , ǫ=10 -4 , T =0.1. For the results of the SA heuristic, A 1 and A 2 approaches, we adopt the Monte Carlo method by generating 50 snapshots with different random uniform UE distribution. After doing the calculations for all the snapshots, we provide the 95% Confidence Interval (CI) for each simulation result. For the result of the MILP problem, we generate only two snapshots and provide the average values. This is because the large scale test scenario, the memory space limitation and the high computational complexity of the joint Power-Delay-Min problem. For the same reason, we also set a bound limit of 1200 s on the running time in the CPLEX optimization tool. The latter provides the best solution found within a given number of brand and bound iterations. It also provides the gap-to-optimality metric which expresses the gap between the obtained solution and the optimal solution estimated by the solver. In the sequel, we present the simulation results.

B. Simulation Results

Let us start by examine the cost reduction that is achieved by our SA heuristic compared with other solutions. The cost reduction is defined as follows: 100 × (1 -total network cost for the SA heuristic total network cost for the considered solution ), [START_REF] Wang | Energy efficiency of heterogeneous cellular network[END_REF] Recall that the total network cost is the sum of the total network power and the total network delay. Table II shows the percentage of cost reduction for SA heuristic compared with other solutions with variation of the number of UEs per cell. On the one hand, results shows that the proposed heuristic performs very close to the optimal solution for a small number of UEs per cell (i.e., ≤ ). Moreover, the heuristic has low computational complexity whereas the optimal solution cannot be computed due to memory space limitation, for a high number of UEs per cell (i.e., 20). It is worth mentioning that the average gap-to-optimality provided by the CPLEX solver is respectively 25.64%, 26.34% and 21.05% for 6, 8 and 10 UEs per cell. This is why, our SA heuristic provides a small positive cost reduction compared to the optimal solution. On the other hand, results shows that our heuristic outperforms A 1 with a cost reduction between 24.58 % and 36.63 % for all the considered number of UEs per cell. In fact, approach A 1 does not take into consideration neither saving power, nor minimizing the delay. Since in this approach all BSs transmit at the highest power level, and UEs are associated according to Po-UA, A 1 solution has the highest total network cost for a given number of UEs per cell. Thus, the highest the cost reduction is for our SA heuristic compared with A 1 solution for a given number of UEs per cell. Moreover, our heuristic also outperforms A 2 with a cost reduction between 10.07% and 33.73 % for all the considered number of UEs per cell. In A 2 , the aim is to minimize only the total network power which is one component of the total network cost and ensure coverage for all UEs in the network. Thus, A 2 approach does not take into account the delay minimization. However, in our SA heuristic, our aim is to minimize simultaneously the total network power and the total network delay. We consider the case where we have 20 UEs per cell, and we show in Tab. III the power saving and the delay reduction that are achieved by our solution compared with A 1 and A 2 solutions. The power saving and the delay reduction are computed as in [START_REF] Wang | Energy efficiency of heterogeneous cellular network[END_REF] but we replace the total network cost by respectively the total network power and the total network delay. Compared with A 1 , the results show that our SA heuristic provides power saving of up to 18 % and delay reduction of up to 32 %. The cause of power saving in our SA heuristic comes from switching off some BS and adjusting the transmit power of others. Moreover, the cause of delay reduction is that our heuristic associate UEs with the network BS in such a way to minimize the total network delay. Therefore, approach A 1 which is equivalent to legacy networks waste the power without enhancing the delay. In comparison with A 2 , the power saving is -17% while the delay reduction is up to 31 %. In fact, in A 2 the percentage of switched-off BS and the percentage of BS transmitting at low power level are respectively 29.56 % and 4.22 %. However, in our heuristic, the former equals 16.11 % and the latter equals 16.33 %. On the one hand, This explains why the power saving in this case is negative. On the other hand, with a high percentage of switched-off BS, the total network delay increases. Therefore, approach A 2 minimizes the total network power in the detriment of total network delay increase. Consequently, minimizing only the total network power while ensuring covering for UEs in the network, can no longer be considered alone. Further, our SA heuristic balances the tradeoff between minimizing the power and delay.

Considering also the case where we have 20 UEs per cell, we vary the value of the precision parameter in our SA heuristic algorithm. We plot in Fig. 3 the total network cost, the number of iterations of the heuristic algorithm and its computation time as a function of the log of the precision parameter. Figure 3(a) shows that we obtain the lowest total network cost for the lowest simulated value of ǫ (i.e., 10 -5 ), and as ǫ decreases the total network cost decreases. Moreover, Fig. 3(b) shows that with small values of ǫ, the number of algorithm's iterations increases. This also increases the computation time of the algorithm as shown in Fig. 3(c). In our simulations, we choose ǫ = 10 -4 providing solution near to the optimal one with a very moderate time and iterations.

VII. CONCLUSION

In this paper, we developed a joint Power-Delay minimization problem in LTE networks. Due to the high computational complexity to obtain the optimal solution, we proposed a novel SA based heuristic algorithm for this problem. Our goal was to come-up with a large-scale heuristic that has low computational complexity and that reduces the total network cost. We evaluated our SA algorithm on the realistic 4G network in Paris-France. Simulation results showed that the proposed heuristic performs close to the optimal and outperforms existing approaches in terms of cost reduction. Moreover, for large number of UEs in the network, the optimal solution is intractable whereas the heuristic algorithm provides efficient results in a reasonable time. Furthermore, compared with legacy solutions, our heuristic provides power saving of up to 18% and delay reduction of up to 32%. Thus, it balances the tradeoff between minimizing the power and delay. In future work, we plan to study the joint Power-Delay-Min problem in heterogeneous networks. Thus, we will study the case of macro BS integrated with WLAN access points located in different hotspots in the network area.

Figure 1 .

 1 Figure 1. 4G network topology of the district 14 of Paris.

  ] Downlink spectral efficiency [bit/s/Hz]

Figure 2 .

 2 Figure 2. Spectral efficiency in LTE as a function of SNR [3].

  Computation time for SA heuristic [sec](c) Computation time Figure3. SA heuristic results with variation of the precision parameter for 20 UEs per cell.

  T ;

	14:	end if
	15:	else
	16:	Go to Step 4;
	17:	end if
	18: end for 19: C qSA tSA =	min q={1,...,Niterations}	C q t ;

20: Λ SA = Λ qSA , Θ SA = Θ qSA . Algorithm 2 Power-Coverage based User Association 1: Input: Ψ k , c(ψ), ψ ∈ Ψ k ; 2: Output: Θ P oCo-U A ; 3: Initialize ∆ k = ∅; 4: for k ∈ K do 5:

Table II PERCENTAGE

 II OF COST REDUCTION FOR SA HEURISTIC COMPARED WITH OTHER SOLUTIONS [%].

	Number of UEs per cell		6	8	10	20
	Optimal	Mean	0.75	1.01	1.02	-
	A1	Mean	36.63	30.48	24.58	24.78
		95% CI [35.34, 37.93] [29.51, 31.46] [23.86, 25.30] [24.36, 25.20]
	A2	Mean	33.73	22.05	10.07	10.35
		95% CI [32.07, 35.39] [20.76, 23.33]	[9.03, 11.11]	[9.33, 11.37]

Table III PERCENTAGE

 III OF POWER SAVING [%] AND DELAY REDUCTION [%] FOR SA HEURISTIC COMPARED WITH A 1 AND A 2 SOLUTIONS FOR 20 UES PER

		CELL.
		(a) Power saving
	A1	Mean	18.28
		95% CI	[17.08, 19.48]
	A2	Mean	-17.07
		95% CI [-18.99, -15.15]
		(b) Delay reduction
	A1	Mean	31.99
		95% CI [30.24, 33.74]
	A2	Mean	31.53
		95% CI [29.24, 33.81]


Farah Moety

Samer Lahoud

Bernard Cousin
email: bernard.cousin@irisa.fr

Kinda Khawam
email: kinda.khawam@prism.uvsq.fr

A Heuristic Algorithm for Joint Power-Delay Minimization in Green Wireless Access Networks

In this paper, we seek to jointly minimize the network power consumption and the user transmission delays in green wireless access networks. We recently studied the case of a WLAN, where we evaluated the tradeoffs between these two minimization objectives using a Mixed Integer Linear Programming (MILP) formulation. However, the MILP formulation could not deliver solutions in a reasonable amount of time due to computational complexity issues. As a result, we propose here a heuristic algorithm for the power-delay minimization problem. The proposed heuristic aims to compute the transmit power level of the Access Points (APs) deployed in the network and associate users with these APs in a way that jointly minimizes the total network power and the total network delay. The simulation results show that the proposed algorithm has a low computational complexity, which makes it advantageous compared with the optimal scheme, particularly in dense networks. Moreover, the heuristic algorithm performs close to optimally and provides power savings of up to 45% compared with legacy networks.

I. INTRODUCTION

Green radio has received recently a significant attention. Knowing that over 80% of the power in mobile telecommunications is consumed in the radio access network, more specifically at the base stations (BSs) level [START_REF] Richter | Energy efficiency aspects of base station deployment strategies for cellular networks[END_REF], a lot of research activities focused on improving the energy efficiency of wireless access networks. In [START_REF] Wu | Energy efficient coverage planning in cellular networks with sleep mode[END_REF], authors studied the coverage planning in cellular networks taking into account the sleep mode for energy saving. Results showed that network energy consumption can be reduced for a careful design of the inter-cell distance. Authors in [START_REF] Hossain | A protocooperationbased sleep-wake architecture for next generation green cellular access networks[END_REF] proposed an energy efficient algorithm in cellular networks based on the principle of cooperation between BSs. In this algorithm, the BSs dynamically switch between active/sleep modes or change their transmit power depending on the traffic situation. In [START_REF] Richter | Energy efficiency aspects of base station deployment strategies for cellular networks[END_REF], [START_REF] Tombaz | Energy efficiency improvements through heterogeneous networks in diverse traffic distribution scenarios[END_REF], different network deployment strategies were studied and simulations showed that the use of low power BSs improves the network energy efficiency. However satisfying user Quality of Service (QoS) has not been considered as a constraint in these works. Notable exceptions are the works in [START_REF] Lorincz | Optimized network management for energy savings of wireless access networks[END_REF], [START_REF] Son | Base station operation and user association mechanisms for energy-delay tradeoffs in green cellular networks[END_REF]. In [START_REF] Lorincz | Optimized network management for energy savings of wireless access networks[END_REF], the authors considered the case of WLANs and they proposed an optimization approach that minimizes power consumption while ensuring coverage of active users and enough capacity for guaranteeing QoS. In [START_REF] Son | Base station operation and user association mechanisms for energy-delay tradeoffs in green cellular networks[END_REF], the authors formulated a minimization problem that allows for a flexible tradeoff between flow-level performance and energy consumption. They proposed greedy algorithms to solve the problem. State-of-the-art power saving approaches studied can also be performed in Wireless Local Area Networks (WLANs). Although power consumption of a cellular network BS is much higher than that of a WLAN Access Point (AP), the large number of APs deployed in classrooms, offices, airports, hotels and malls, contributes to a rapid increase in the power consumption in wireless access networks. Hence, efficient management of the power consumed by a WLAN is an interesting challenge. In this paper, we tackle the problem of jointly minimizing the network power consumption and the sum of user transmission delays in WLANs. This is realized by finding a tradeoff between reducing the number of active APs and adjusting the transmit power of those that remain active while selecting the best user association that incurs the lowest transmission delay. Our approach presents multiple novelties compared to the state-of-the-art. Authors in [START_REF] Lorincz | Optimized network management for energy savings of wireless access networks[END_REF] considered the theoretical data rate of the IEEE 802.11g, which is a pessimistic bound compared to the effective data rate we use in our paper. In [START_REF] Son | Base station operation and user association mechanisms for energy-delay tradeoffs in green cellular networks[END_REF], the delay is computed using the M/GI/1 queue, which is also a pessimistic bound compared to the realistic delay model we use. Moreover, the authors studied only the case where BSs switch between on/off modes without adjusting the transmit power.

In our previous work [START_REF] Moety | Joint Power-Delay minimization in green wireless access networks[END_REF], we formulated the power-delay minimization problem, denoted by Power-Delay-Min problem, as a Mixed Integer Linear Programing (MILP). This enables us to evaluate the tradeoffs between minimizing the network power consumption and the network delay. In this paper, we assess the computational complexity of the optimal solution, and show that the MILP formulation can not deliver solutions in a reasonable amount of time. Therefore, in this paper we come up with a novel heuristic for the Power-Delay-Min problem that has low computational complexity. This makes the proposed algorithm applicable for practical implementations while achieving a satisfactory solution.

The proposed heuristic aims at computing the transmit power level of the APs deployed in the network and associating users with these APs in a way that jointly minimizes the total network power and the total network delay. Our heuristic is two-fold: first, it starts with an initial network state where all APs transmit at the highest power level. Then, it changes iteratively the transmit power level of candidate APs. Second, for each change in any AP transmit power level, the heuristic seeks to associates User Equipments (UEs) with the best AP.

The selection of the best AP takes into account the peak rate perceived by the UE and the number of covered UEs. In order to evaluate the efficiency of the heuristic algorithm for the Power-Delay problem, we compare the results obtained by this heuristic with the MILP optimal solution. Moreover, we introduce reference models for power and user association that enables to assess the power saving and the delay obtained by the mentioned solutions.

The rest of the paper is organized as follows. In Section II, we describe the network model considering an IEEE 802.11g WLAN. In Section III, we present the Power-Delay minimization problem. In Section IV, we present our proposed heuristic algorithm. In Section V, we present the legacy network models. In Section VI, we provide the simulation results. Conclusions are given in Section VII.

II. NEWORK MODEL

A. Power Consumption Model

We consider the power consumption of an IEEE 802.11g WLAN, with APs working in infrastructure mode. Assume that each AP operates in two modes: active and switched-off. In practice, the transmission power of an AP is discrete and the maximum number of transmit power levels is equal to 5 or 6 depending on the AP manufacturer. In this paper, we denote by N ap and N l the number of APs in the network and the number of transmit power levels respectively. The indexes i ∈ I = {1, . . . , N ap }, and j ∈ J = {1, . . . , N l }, are used throughout the paper to designate a given AP and its transmit power level respectively. Note that, for j = 1 we consider that the AP transmits at the highest power level and for j = N l the AP is switched off. Following the model proposed in [START_REF] Richter | Energy efficiency aspects of base station deployment strategies for cellular networks[END_REF], the power consumption of an AP is modeled as a linear function of the average transmit power per site as below:

p i,j = L • (aπ j + b), (1)
where p i,j and π j denote the average consumed power per AP i and the transmit power at level j respectively. The coefficient a accounts for the power consumption that scales with the transmit power due to radio frequency amplifier and feeder losses while b models the power consumed independently of the transmit power due to signal processing and site cooling.

L reflects the activity level of the APs. As we assume that the network is in a saturation state, L is equal to one, e.g., each active AP has at least one UE requesting data to which all resources being allocated.

B. Traffic and Delay Model

In this paper, we only consider the downlink traffic as it is several orders higher than the uplink one. We assume that i) the network is in a static state where UEs are stationary, ii) the network is in a saturation state. A saturation state is a worst case scenario where every UE has persistent traffic. Moreover, we assume that interference is mitigated by assigning adjacent APs to the different IEEE 802.11 channels [START_REF] Chieochan | Channel assignment schemes for infrastructure-based 802.11 wlans: A survey[END_REF].

1) Radio Conditions:

The peak rate of each UE depends on its received Signal to Noise Ratio (SNR). We term by k ∈ K = {1, . . . , N u }, the index of a given UE where N u is the number of UEs in the network. We also denote by χ i,j,k the peak rate perceived by UE k from AP i transmitting at level j.

2) Data Rate and Delay Models in WiFi: Neglecting the uplink traffic leads to a fair access scheme on the downlink channel. Accordingly, when a low rate UE captures the channel, this UE will penalize the high rate UEs and reduces the fair access strategy to a case of fair rate sharing of the radio channel among UEs [START_REF] Heusse | Performance anomaly of 802.11b[END_REF] with the assumption of neglecting the 802.11 waiting times (i.e., DIFS1 , SIFS2 ). Thus, all UEs will have the same mean throughput. Hence, when UE k is associated with AP i transmitting at level j, its mean throughput (R i,j,k ) depends on its peak rate (χ i,j,k ) and the peak rates of other UEs associated with this same AP (χ i,j,k ′ , k ′ = k), and it is given by [START_REF] Khawam | Individual vs. global radio resource management in a hybrid broadband network[END_REF]:

R i,j,k = 1 1 χ i,j,k + Nu k ′ =1,k ′ =k θ i,k ′ χ i,j,k ′ , (2)
where θ i,k ′ is a binary variable that indicates whether UE k ′ is associated with AP i or not. We denote by T i,j,k the amount of time necessary to send a data unit to UE k from AP i transmitting at level j. In fact, the bit transmission delay for a given UE is the inverse of the throughput perceived by this UE. Thus,

T i,j,k = 1 χ i,j,k + Nu k ′ =1,k ′ =k θ i,k ′ χ i,j,k ′ . (3)

C. Coverage Area

Transmitting at different power levels leads to different coverage area sizes. Note that, all UEs within the coverage area of an AP require a minimum received SNR for acceptable performance. In our paper, a UE is thus considered covered by an AP if its SNR is above a given threshold. As mentioned in II-B1, the peak rate perceived by a given UE depends on its SNR. Consequently, a UE is covered if it perceives a peak rate, from at least one AP, higher than a given peak rate threshold (χ threshold ).

III. OPTIMIZATION PROBLEM

A. Problem Formulation

In [START_REF] Moety | Joint Power-Delay minimization in green wireless access networks[END_REF], we formulated the Power-Delay-Min problem, that jointly minimizes the network power consumption and the sum of data unit UE transmission delays. Now, let us introduce some notations before presenting our problem. Let Λ be the matrix, with elements λ i,j , defining the operation mode of the network APs; and λ i,j be a binary variable that indicates whether AP i transmits at level j or not. Let Θ be the matrix, with elements θ i,k , defining the users association with the network APs; and θ i,k be a binary variable that indicates whether a user k is associated with AP i or not. The Power-Delay-Min problem consists in computing the transmit power level of the APs and in associating UEs with these APs in a way that jointly minimizes the total network power and the total network delay. The total network power, denoted by C p (Λ), is defined as the total power consumption of active APs in the network and is given by:

C p (Λ) = i∈I,j∈J (aπ j + b) • λ i,j . (4)
The total network delay, denoted by C d (Λ, Θ), is defined as the sum of data unit transmission delays of all UEs in the network and is given by:

C d (Λ, Θ) = i∈I,j∈J,k∈K T i,j,k • λ i,j • θ i,k (5)
Therefore, the total network cost, denoted by C t (Λ, Θ), is thereby defined as the sum of power and delay components and is given by:

C t (Λ, Θ) = αC p (Λ) + ββ ′ C d (Λ, Θ), (6)
α and β are the weighting coefficients representing the relative importance of the two objectives. It is usually assumed that α + β = 1 and that α and β ∈ [0,1]. β ′ is a normalization factor that will scale the two objectives properly. Consequently, our Power-Delay-Min problem (P) is given by: minimize

Λ,Θ C t (Λ, Θ) = αC p (Λ) + ββ ′ C d (Λ, Θ), subject to (7)
j∈J λ i,j = 1, ∀ i ∈ I, (8)
i∈I θ i,k = 1, ∀ k ∈ K, (9)
λ i,N l + θ i,k = 0, ∀ (i, k) : i ∈ I, k ∈ K. (10)
Constraints [START_REF] Lorincz | Optimized network management for energy savings of wireless access networks[END_REF] state that every AP transmits only at one power level. Constraints [START_REF] Moety | Joint Power-Delay minimization in green wireless access networks[END_REF] ensure that a given UE is connected to only one AP. Finally, constraints [START_REF] Richter | Energy efficiency aspects of base station deployment strategies for cellular networks[END_REF] ensure that a given UE is not associated with a switched off AP.

B. Optimal Solution

(P) is a binary non-linear optimization problem. In [START_REF] Moety | Joint Power-Delay minimization in green wireless access networks[END_REF], we converted (P) into a MILP problem and used a branch-andbound (BB) approach to solve it. In this approach, the number of integer variables determines the size of the search tree and impacts the computation time of the algorithm. Thus, we noted that our MILP conversion can not deliver solution for dense networks. In order to assess the computational complexity of the optimal solution, we calculate in the following its computation time and the number of binary integer variables. In addition, we compute the number of non-zero elements of the matrix defining the constraints of the minimization problem. We consider a network topology consisting of 9 APs with three transmit power levels and 54 UEs. Moreover, we only study the case where α=β=0.5. Such case balances the tradeoff between minimizing power and delay. Furthermore, the normalization factor β ′ is calculated in each simulation in such a way to scale the two components of the total network cost [START_REF] Grodzevich | Normalization and other topics in multi-objective optimization[END_REF]. We run over 50 simulation instances, and we show in Figure 1 the 95% Confidence Interval (CI) of the computational complexity measurements as a function of the inter-cell distance (D). We note that the computation time of the optimal solution decreases when D increases, as shown in Figure 1(a). Precisely, when D increases, the number of binary integer variables and non-zero elements decreases, as shown in Figures 1(b) and 1(c). In fact, when the inter-cell distance increases, the number of covering APs per UE decreases. This causes the related solution space (for selecting the BS transmit power level, and the user association) to be small, which decreases the number of binary integer variables and non-zero elements. Moreover, we notice that we cannot obtain solutions for dense networks (e.g., D ≤ 120.8 m) as the problem becomes intractable. Hence, in this paper we introduce a heuristic that computes satisfactory solutions for the problem while keeping low computation complexity.

IV. HEURISTIC ALGORITHM Due to the high computational complexity of the Power-Delay-Min problem, we propose in this paper a novel heuristic algorithm for this problem. The proposed heuristic aims at computing the transmit power level of the APs deployed in the network and associating users with these APs in a way that jointly minimizes the total network power and the total network delay. Our heuristic is two-fold: i) it starts with an initial network state where all APs transmit at the highest power level, then it changes (switches off / decreases) iteratively the transmit power level of candidate APs. ii) For each change in any AP transmit power level, it seeks to associate UEs with the best AP according to Power-Coverage Based User Association (PoCo-UA) (explained later in Section IV-A2). Intuitively, in PoCo-UA, the probability that a UE is associated with a given AP is proportional to the peak rate perceived by this UE and inversely proportional to the number of UEs covered by the corresponding AP. The heuristic algorithm stops when no more improvement can be achieved in terms of power and delay reduction. Let I j , j ∈ J, be the set of APs transmitting at level j.

A. Heuristic Algorithm for the Power-Delay-Min Problem

Algorithm 1 describes the different steps of our heuristic algorithm for the Power-Delay-Min problem. The algorithm takes as inputs the number of APs, the number of transmit power levels, and the number of UEs in the network (Step 1). The algorithm outputs the transmit power levels of the APs and the user association (Step 2). The algorithm starts with an initial network state where all APs transmit at the highest power level (Step 3), i.e., λ i,1 = 1 ∀i ∈ I and λ i,j = 0 ∀(i, j) ∈ (I, J -{1}). The algorithm is composed of (N l -1) phases (Step 4). In the first phase (l = N l ), the SearchForAP function (in Step 6) finds a set of candidate APs (i cand ) to switch off. Starting from this set, the algorithm chooses to switch off AP i * which results in minimizing the total network delay (Step 8). We note that, the minimum total network delay t * is computed according to [START_REF] Heusse | Performance anomaly of 802.11b[END_REF]. The algorithm (i cand , t cand ) = SearchForAP (I l-(N l -1) , l);

7: if i cand = ∅ then 8: (i * , t * ) = min (i,t)∈(i cand ,t cand )
t cand ;

9:

I l-(N l -1) ← I l-(N l -1) \{i * };
10: end while 18: end for proceeds to the second phase as soon as no further APs can be switched off ( Step 11). Then, the algorithm proceeds in the same way in the subsequent phases (l = N l -1 to 2), where the SearchForAP function finds a set of candidate APs to change their transmit power level gradually from ((N l -1) to 2) according to the value of l. The algorithm stops when no more improvement can be achieved. In other words, it stops when no more APs can reduce their transmit power level. In fact, our heuristic always decreases the APs transmit power level. Thus, the condition that no more APs can reduce their transmit power level (i.e., i cand = ∅) is guaranteed to be attained and the heuristic algorithm will converge.

I l ← I l ∪ {i * }; 11: if I l-(N l -
1) SearchForAP Function: The SearchForAP function takes as an input the set of APs transmitting at a given transmit power level (I f un ) to reduce their transmit power level according to the value of the transmit power level to be applied l ∈ L = {N l , (N l -1), .., 2}. the function outputs the set of candidate APs to switch off, denoted by i cand , and the set of total network delay resulting from the switch-off of the corresponding APs denoted by t cand . For each AP m in I f un (Step 3), the function applies the transmit power level l to the end if 15: end for appropriate AP (Step 4), and verifies the coverage constraint for all UEs in the network (Step 5). If all network UEs are covered then it computes the set of APs covering UE k denoted by Ψ k , and the number of UEs covered by AP ψ denoted by c(ψ). Afterwards, it associates each UE with the active APs according to PoCo-UA (Step 6), and it computes the total network delay C d (Λ, Θ) according to (5) (Step 7). Finally, AP m and the resulting total network delay are added respectively to the sets (i cand , t cand ) (Steps 8 and 9). Otherwise, the AP keeps its previous transmit power level (Step 11). The steps of this function is described in Algorithm 2.

if ∀k ∈ K, ∃(i, j) ∈ (I, J)/χ i,j,k • λ i,j ≥ χ threshold then 6: Compute Ψ k , ∀k ∈ K; 7: Compute c(ψ), ∀ψ ∈ Ψ k ; 8: Compute θ i,k = PoCo-UA (Ψ k , c(ψ)), ∀(i, k) ∈ (I, K); 9: Compute C d (Λ, Θ); 10: i cand ← i cand ∪ {m}; 11: t cand ← t cand ∪ {C d (Λ, Θ)};
2) Power-Coverage Based User Association (PoCo-UA): Algorithm 3 describes the different steps of PoCo-UA. The PoCo-UA algorithm takes as inputs the set of APs covering UE k denoted by Ψ k , and the number of UEs covered by AP ψ denoted by c(ψ) (Step 1). As an output, it returns the user association denoted by θ heur (Step 2). For UEs covered by several APs (Step 5), the algorithm proceeds as follows: each UE k computes two coefficients r ψ k and ρ k ψ for each of its covering AP ψ ∈ Ψ k (Step 7). These coefficients take into consideration respectively the received SNR at the UE side and the number of UEs covered by the corresponding AP. We combine these coefficients with a probability function in such a way the probability to be associated with a given Algorithm 3 Power-Coverage based User Association

1: Input: Ψ k , c(ψ), ψ ∈ Ψ k ; 2: Output: θ heur ; 3: Initialize ∆ k = ∅; 4: for k ∈ K do 5: if |Ψ k | = 1 then 6: for ψ ∈ Ψ k do 7: Compute r ψ k = χ ψ,j,k ψ∈Ψ k χ ψ,j,k , ρ k ψ = c(ψ) ψ∈Ψ k c(ψ) ; 8: Compute δ ψ,k = r ψ k /ρ k ψ ψ∈Ψ k r ψ k /ρ k ψ ; 9: ∆ k ← ∆ k ∪ {δ ψ,k }; 10:
end for 11:

ψ * k = Random(Ψ k , ∆ k ) ⇒ θ heur = θ ψ * k ,k = 1;
12: else 13:

ψ * k = {Ψ k } ⇒ θ heur = θ ψ * k ,k = 1; 14:
end if 15: end for AP is proportional to the peak rate perceived by the UE and inversely proportional to the number of UEs covered by the corresponding AP. Then, each UE k computes δ ψ,k the probability to be associated with AP ψ (Step 8). The complexity of executing PoCo-UA algorithm is in

O(N u × |Ψ k | log |Ψ k |).
The complexity of executing the heuristic algorithm for the Power-Delay-Min problem (Algorithm 1) corresponds to the complexity of executing PoCo-UA at each change of the transmit power level for each AP. Hence, the complexity of Algorithm 1 is in:

O(N u × |Ψ k | log |Ψ k | × N l × N ap ). ( 11
)
In order to evaluate the efficiency of the heuristic algorithm for the Power-Delay-Min problem, we will compare the optimal solution to the results obtained by this heuristic in section VI.

V. LEGACY NETWORK MODELS

In current WLAN deployments, APs transmit at a fixed power level and UEs are associated with the AP delivering the highest SNR [START_REF]The benefits of centralization in wlans via the cisco unified wireless network[END_REF]. Based on such WLAN deployments, we devise a reference model composed of: i) the Highest Power Level (HPL) as the reference power model, it assumes that all APs transmit at the highest power level; ii) the Power based User Association (Po-UA) as the reference user association model, it associates a UE with the AP where it gets the highest SNR. In the free space model considered in what follows, the SNR is directly related to the transmit power of AP. In what follows, we denote the reference model by Po-UA/HPL. The total network power, and the total network delay of this model will serve as reference values for result comparison.

VI. PERFORMANCE EVALUATION

A. Evaluation Method

In order to study the efficiency of the proposed heuristic algorithm for the Power-Delay-Min problem, we implement this algorithm and compare its solution with the optimal one. The optimal solution of the MILP problem is solved using the BB method with the GLPK solver. We consider a network topology composed of nine cells (N ap =9) using the IEEE 802.11g technology and six UEs in each cell (N u =9 × 6=54). The WLAN APs are distributed following a grid structure and the positioning of UEs follows a random uniform distribution. Moreover, we assign adjacent APs to different IEEE 802.11 channels to limit interference.

For the sake of simplicity, we consider only three transmit power levels (N l =3) with j=N l being the switched-off mode. Precisely, an active AP is able to transmit at two power levels and consequently has two coverage areas. The input parameters of the power consumption model in (1) are: i) a=3.2, b=10.2 [START_REF] Tombaz | Energy efficiency improvements through heterogeneous networks in diverse traffic distribution scenarios[END_REF]; ii) π 1 =0.03 W and π 2 =0.015 W [START_REF]Channels and maximum power settings for cisco aironet lightweight access points[END_REF] the transmit power at level one and two respectively. Consequently, the average consumed power for AP i the first and the second power levels are given respectively by p i,1 =10.296 W and p i,2 = 10.248 W (i=1,. . ., 9). Recall that, for j=3, the AP is switched off and p i,3 =0.

1) Coverage area and peak rate computation: We introduced in [START_REF] Moety | Joint Power-Delay minimization in green wireless access networks[END_REF] a benchmark scenario that enables the computation of: i) the peak rate perceived by the UE from the AP as a function of the distance between them and considering two different transmit powers (π 1 =0.03 W and π 2 =0.015 W); ii) the coverage radius for the first and the second power levels R 1 =107,4 m and R 2 =75,8 m respectively. These radii correspond to a SNR threshold that equals -0.5 dB at the cell boundary. This SNR is the minimum value to be maintained in order to consider that a given user is covered by an AP. It corresponds to a cell edge peak rate that equals 1 Mb/s (χ threshold =1 Mb/s) on the downlink.

In what follows, the simulation results for the heuristic and the optimal solutions are plotted as a function of the inter-cell distance (D). Particularly, this parameter has a large impact not only on the computational complexity of the algorithm but also on the quality of the solution. For small inter-cell distances, we obtain a dense coverage area, while large intercell distances produce sparse coverage area. Table I shows the average number of covering APs per UE as a function of the inter-cell distance. For D = 80.55 m we obtain a dense coverage area where the average number of covering APs per UE is 3.4. As D increases, the average number of covering APs per UE decreases to be equal to one when there is no overlap between cells (D=2R 1 ). Furthermore, for the optimal results, we run 50 simulation instances and illustrate the 95% CI. We only consider the case where α=β=0.5 in [START_REF] Khawam | Individual vs. global radio resource management in a hybrid broadband network[END_REF]. Such case balances the tradeoff between minimizing power and delay. Moreover, the normalization factor β ′ is calculated in each simulation in such a way to scale the two components of the total network cost [START_REF] Grodzevich | Normalization and other topics in multi-objective optimization[END_REF]. For the heuristic results, we run the heuristic algorithm (Algorithm 1) five times on each of the 50 simulated instances and illustrate the 95% CI. Moreover, the user association problem is a very challenging one. Therefore, in each iteration of the heuristic algorithm, we run the PoCo-UA user association (Algorithm 3) 50 times and select the best θ heur that gives the minimal total network delay. We plot in Figure 2, the total network power for the heuristic and the optimal solutions and for Po-UA/HPL reference model as a function of the inter-cell distance D. Note that the total network power is computed according to (4). In Po-UA/HPL reference model, all APs transmit at the highest power level. This explains why Po-UA/HPL model has the highest total network power for all D. Moreover, results show that the heuristic solution outperforms the optimal one for D ranging between 120.8 m to 161.1 m. In addition, for dense networks (i.e., D ≤ 120.8 m), the heuristic has low computational complexity whereas the optimal solution cannot be computed. The heuristic provides power savings up to 45% compared with Po-UA/HPL for D=80.6 m in a reasonable time. In addition, the heuristic and the optimal solutions show increasing curves for D ≤ 161.1 m. Then the total network power for these solutions becomes constant and equals the total network power for Po-UA/HPL model for D ≥ 161.1 m. a) Power Saving Compared with Po-UA/HPL: To examine the cause of power savings in the heuristic and the optimal solutions compared with Po-UA/HPL model for D ≤ 161.1 m, we plot Figures 3(a) and 3(b). These figures illustrate the percentage of the AP operation modes. For the heuristic solution, results are provided for D ranging between 80.6 m to 161.1 m. Whereas, for the optimal solution, results are provided for D ranging between 120.8 m to 161.1 m, as the optimal solution has high computational complexity for dense networks (i.e., D ≤ 120.8 m). We notice that in the heuristic solution, the percentage of switched-off APs and the percentage of APs transmitting at the second power level is greater than that in the optimal solution for D ranging between 120.8 m to 161.1 m. The reason for this is that the proposed heuristic has an aggressive power saving policy: it switches off iteratively the maximum number of possible APs then it reduces iteratively the transmit power level of the remaining possible APs, while associating users to the active APs in such a way to obtain in each iteration the minimum total network delay. However, the optimization problem minimizes simultaneously the total network power and the total network delay. This explains why we obtain a solution where the total network power is higher than the heuristic one. Moreover, for both (heuristic and optimal) solutions, we see that when D increases the percentage of switched off APs decreases, and the percentage of APs transmitting at the second power level increases. Precisely, for small values of D (i.e., 80.6 m), the number of covering APs per UE is relatively high (i.e., 3.4 as shown in Table I); thus, a large number of APs can be switched-off or can transmit at low power level (i.e., 44% of the APs are switched-off as shown in Figure 3(a)). However, when the value of D increases, the number of covering APs per UE decreases and thus the possibility to switch off an AP or to transmit at low power level decreases in order to ensure coverage for all UEs in the network. This explains the increasing curves for the corresponding inter-cell distances in Figure 2. Also, this logic validate why we obtain in these solutions a total network power equals to the one in Po-UA/HPL model for large D (i.e., D ≥ 161.1 m) in the same figure. We now investigate the total network delay for the heuristic and the optimal solutions compared with the Po-UA/HPL model while varying the inter-cell distance. The total network delay is computed according to [START_REF] Heusse | Performance anomaly of 802.11b[END_REF]. As expected, Figure 4 shows that the Po-UA/HPL model has the lowest total network delay followed by the optimal solution and then by the heuristic solution. This is due to the fact that, in Po-UA/HPL model where all APs transmit at the highest power level, all UEs perceive a relatively high SNR which lowers the total network delay. However for the heuristic solution, the number of APs transmitting at low level or switched off is greater than that of the optimal one (as shown in Figure 3) and this causes the total network delay of the heuristic to be higher than the optimal one. Moreover, we see that the total network delay for the optimal solution and for Po-UA/HPL model have increasing curves. Precisely, for the same UE distribution, when D increases, the SNR of the UE decreases, thus the perceived rate decreases which causes the delay to increase. Whereas, the heuristic solution has a decreasing curve for D between 80.6 m and 161.1 m then it has an increasing one for D ≥ 161.1 m. Typically, for D between 80.6 m and 161.1 m, the number of APs transmitting at either the highest power level or the second power level increases (as shown in Figure 3(a)) and thereby UEs experience a lower delay. Note that all the curves tend to converge to the same point. Precisely, for high values of inter-cell distance (D ≥ 161.1 m), the simulated algorithms converge to a solution where all APs transmit at the highest power level. This corresponds to the only feasible solution of the Power-Delay-Min problem. In this situation, this problem boils down to a user association problem that minimizes the sum of UE delays.

Finally, in order to study the computational complexity of the heuristic algorithm, we depict in Table II the average computation time of the heuristic and the optimal solutions as a function of the inter-cell distance. Results show that the heuristic solution has a low computational time for dense networks. For instance, for D equals 80.6 m, it takes 11.89 sec of computation time, whereas the optimal solution cannot be computed. Moreover, we notice that for D equals 128.08 m, the heuristic algorithm has a negligeable computation time compared to the optimal one. Furthermore, the computation time decreases when D increases. In fact, the complexity of executing the heuristic algorithm depends on the number of covering APs per user according to [START_REF] Son | Base station operation and user association mechanisms for energy-delay tradeoffs in green cellular networks[END_REF]. As shown in

VII. CONCLUSION

In this paper, we proposed a novel heuristic algorithm for the joint Power-Delay minimization problem in WLANs. Our goal was to come-up with a heuristic that has low computational complexity and provides a satisfactory solution. Simulation results showed that the proposed heuristic gives comparable power savings with respect to an optimal solution. Moreover, for dense scenarios, the optimal solution is intractable whereas the heuristic algorithm provides efficient results that show significant power savings up to 45% compared with legacy networks in a reasonable time. However, for both solutions, the network power is saved at the cost of an increase in network delay. In addition, for sparse scenarios, there is no substantial gain compared with a reference model and thus power saving is superfluous. In future work, we seek to study the joint Power-Delay-Min problem for cellular networks considering 4G technology.

Algorithm 1

 1 distance [m] Non zero elements (c) Number of non-zero elements Figure 1. Optimal solution computational complexity measurements. Heuristic Algorithm for the Power-Delay-Min Problem 1: Input: N ap , N l , N u ; 2: Output: λ i,j , θ i,k ∀(i, j, k) ∈ (I, J, K) 3: Initialize I 1 ={1, .., N ap }, I 2 =I 3 =...=I N l =∅, L={N l , N l -1, .., 2} and i cand = t cand = ∅; 4: for l ∈ L do 5: while (1) do 6:

Algorithm 2

 2 SearchForAP Function 1: Input: I f un , l ∈ L = {N l , N (l-1) , .., 2}; 2: Output: i cand , t cand ; 3: for m ∈ I f un do

  distance [m] Total network power [W]Po-UA/HPL Power-Delay-Min (Optimal) Heuristic

Figure 2 .

 2 Figure 2. Total network power for heuristic and optimal solutions and for Po-UA/HPL.

  (b) Optimal solution Figure3.Percentage of AP operation modes in heuristic and optimal solutions.

Figure 4 .

 4 Figure 4. Total network delay for heuristic and optimal solutions and for Po-UA/HPL.

Table I COVERING

 I APS PER UE VS. INTER-CELL DISTANCE.

	Inter-cell distance [m]	80.6 93.98 107.4 120.8 134.2 147.6 161.1 174.5 187.9 201.3 214.8
	Number of covering APs per UE	3.40	2.78	2.40	2.02	1.76	1.53	1.38	1.25	1.15	1.05	1.00
	B. Simulation Results

Table II COMPUTATION

 II TIME IN [SEC]: HEURISTIC VS. OPTIMAL.

	Inter-cell distance [m]	80.6	93.98 107.4	120.8
	Heuristic solution	11.89	9.64	7.18	4.57
	Optimal solution	N/A	N/A	N/A	1091.90

Table I ,

 I when D increases, the number of covering APs per user decreases causing the computation time to decrease.

DIFS: Distributed Coordination Function Interframe Space

SIFS: Short Interframe Space