Keywords: Energy-eciency, Cellular networks, QoS and sleep modes

In this paper we study base station sleep modes that, by reducing power consumption in periods of low trac, improve the energy eciency of cellular access networks. We assume that when some base stations enter sleep mode, radio coverage and service provisioning are provided by the base stations that remain active, so as to guarantee that service is available over the whole area at all times. This may be an optimistic assumption in the case of the sparse base station layouts typical of rural areas, but is, on the contrary, a realistic hypothesis for the dense layouts of urban areas, which consume most of the network energy. We consider the possibility of either just one sleep mode scheme per day (bringing the network from a high-power, fully-operational conguration, to a low-power reduced conguration), or several sleep mode schemes per day, with progressively fewer active base stations. For both contexts, we develop a simple analytical framework to identify optimal base station sleep times as a function of the daily trac pattern. We start by considering homogeneous networks, in which all cells carry the same amount of trac and cover areas of equal size. Considering both synthetic trac patterns and real trac traces, collected from cells of an operational network, we show that the energy saving achieved with base station sleep modes can be quite signicant, the actual value strongly depending on the trac pattern. Our results also show that most of the energy saving is already achieved with one sleep mode scheme per day. Some additional saving can be achieved with multiple sleep mode schemes, at the price of a signicant increase in complexity. We then consider heterogeneous networks in which cells with dierent coverage areas and dierent amounts of trac coexist. In particular, we focus on the common case in which some micro-cells provide additional capacity in a region covered by an umbrella macro-cell, and we prove that the optimal scheduling of micro-cell sleep times is in increasing order of load, from the least loaded to the most loaded. This provides a valuable guideline for the scheduling of sleep modes (i.e., of low-power congurations) in complex heterogeneous networks.

L'ecacité des modes de sommeil uniques et multiples pour les stations de base dans les réseaux cellulaires Résumé :

Dans ce rapport, nous étudions les modes de mise en veille des stations de base. En réduisant la puissance en période de trac faible, l'ecacité énergétique des réseaux d'accès cellulaires se trouve améliorée. Nous supposons que le service est toujours disponible sur tout le réseau. Ainsi, lorsque certaines stations de base sont mises en veille, les stations de base restant actives assurent la couverture radio et la fourniture de services. Cette hypothèse peut sembler optimiste là où les stations de base sont éparses (cas typique des zones rurales) mais elle est réaliste dans les zones urbaines, qui correspondent au pic de la consommation énergétique du réseau. Deux scénarios de mise en veille sont considérés : dans le premier, la mise en veille est eectuée une seule fois par jour sur tout le réseau, celui-ci passe alors d'une conguration entièrement fonctionnelle à une conguration réduite; dans le deuxième scénario, le nombre des stations de base actives est progressivement réduit au cours de la journée. Pour chaque scénario, nous développons une analyse simple pour identier les durées optimales de mise en veille selon le trac journalier. Dans un premier temps, nous considérons le cas homogène dans lequel toutes les cellules transportent la même quantité de trac et ont des zones de couvertures identiques. Nous montrons sur des traces de trac d'abord synthétiques ensuite réelles (fournies par un opérateur) que l'économie d'énergie réalisée avec la mise en veille des stations de base peut être très importante, sa valeur dépendant fortement de la nature du trac. Nos résultats montrent également que l'économie d'énergie réalisée est obtenue majoritairement avec une seule mise en veille journalière dans le réseau. La réduction progressive du nombre de stations actives apporte certes un surplus d'économie d'énergie, mais au prix d'une augmentation signicative de la complexité. Dans un second temps, nous considérons le cas hétérogène dans lequel des cellules de zones de couverture diérentes et de trac diérent coexistent. Nous nous concentrons en particulier sur le cas courant dans lequel certaines micro-cellules fournissent une capacité supplémentaire dans une région couverte par une macro-cellule et prouvons que l'ordonnancement optimal des mises en veille des micro-cellules est selon l'ordre croissant de la charge. Ceci fournit une indication importante pour la planication des mises en veille dans les réseaux hétérogènes complexes.

Introduction

Eskimos are said to use many words for snow, because snow pervades their environment. On the contrary, in the early days of networking, the term power was used to identify the ratio of throughput over delay [START_REF] Giessler | Free buer allocation: An investigation by simulation[END_REF][START_REF] Kleinrock | Power and Deterministic Rules of Thumb for Probabilistic Problems in Computer Communications[END_REF], because energy issues did not belong in the networking landscape. Then, cellular networks and battery-operated terminals (most notably mobile phones) came along, and power control (now real power, measured in J/s) became an issue, in order to extend both the distance from the base station at which a terminal could be used, and the battery charge duration (in the early '90s, heavy users carried a spare charged battery in their pocket, to avoid being cut o around noon). Next, sensor networks brought with them the question of power minimization to increase the network lifetime. Still, before the turn of the century, power consumption was not an element of the wired network design space. The rst paper that addressed energy issues in xed networks was [START_REF] Gupta | Greening of the Internet[END_REF], where Gupta and Singh investigated the energy consumption of Internet devices, and discussed the impact of sleep modes on network protocols. Since then, the interest in energy-ecient networking has been steadily rising, and the energy issue is now addressed in many conferences and research projects, among which we wish to mention TREND (Towards Real Energy-ecient Network Design) [START_REF]TREND Project[END_REF], the Network of Excellence funded by the European Commission within its 7th Framework Programme, which supported the work reported in this paper.

The directions that are presently pursued to achieve energy eciency in networking can be grouped in two classes: 1) development of new technologies that reduce energy consumption, and 2) identication of approaches that make the network energy consumption proportional to trac. The rationale for the second direction derives from the observation that today network equipment exhibits power consumption which is practically independent of load. For example, a base station of a cellular network consumes at zero load about 60-80% of the energy consumption at full load [START_REF] Son | SpeedBalance: Speed-Scaling-Aware Optimal Load Balancing for Green Cellular Networks[END_REF].

Approaches that aim at improving the proportionality between the network energy consumption and the network load can be further divided in 2 sub-classes: 2a) development of equipment exhibiting better proportionality of energy consumption to load, and 2b) identication of algorithms that allow the reduction of the functionality of network equipment in periods of low trac, so as to decrease energy consumption in such periods. The algorithms that received most attention in class 2b are often called speed scaling, and sleep modes. By speed scaling we normally mean that the equipment can operate at dierent clock rates, with lower rates corresponding to lower power (and lower performance). By sleep modes we mean that in periods of low trac the network operates with a subset of its equipment, the rest being switched o to save energy.

In the case of cellular networks, the critical equipment for power consumption is the base station (BS), whose typical consumption ranges between 0.5 kW and 2 kW [START_REF] Arnold | Power consumption modeling of dierent base station types in heterogeneous cellular networks[END_REF][START_REF] Lorincz | Measurements and Modelling of Base Station Power Consumption under Real Trac Loads[END_REF], including power ampliers, digital signal processors, feeders, and cooling system. Moreover, according to [START_REF] Louhi | Energy eciency of modern cellular base stations[END_REF], all together, the BSs make up for about 80% of the total energy consumption of the cellular network.

In this paper we consider sleep modes for BSs in cellular networks, with reference to 3G technology, and we investigate the benets that can be achieved by putting to sleep, i.e., bringing to a low-power-idle (LPI) state, a BS during periods of low trac. This means that, in the future, the cellular access network planning should allow the selection of dierent operational layers corresponding to network congurations that specify the set of active BSs to serve dierent levels of trac. These congurations can be activated according to predened schedules, that are derived based on a combination of trac forecasts and logs of trac measurements. We compute the maximum amount of energy that can be saved with this approach, and we study the impact of the number of congurations, considering dierent types of network topologies with idealized Inria cell structures, as well as a real BS layout and a very realistic coverage map.

We assume that when some BSs are in sleep mode, radio coverage and service provisioning are taken care of by the base stations that remain active, so as to guarantee that service is available over the whole area at all times. This may be an optimistic assumption in the case of sparse base station layouts in rural areas (where network planning usually aims at coverage using large cells), but is on the contrary a realistic hypothesis for the dense layouts of urban areas (where network planning normally aims at capacity, with very redundant coverage, based on few large and many small cells), which consume most of the network energy. When some BSs enter the LPI state, the base stations that remain active may need to increase their transmission power, so as to cover also the area that was covered by the sleeping BSs. However, in our previous study [START_REF] Ajmone Marsan | Energy-Ecient Management of UMTS Access Networks[END_REF] we showed that this increment is usually negligible.

The main contributions of this paper are the following. We develop an analytical framework to identify the optimal scheduling of low-power network congurations (including how many BSs should be put into sleep mode and when) as a function of the daily trac pattern, in the cases in which either just one low-power conguration per day is possible (bringing the network from a high-power, fully-operational conguration, to a low-power reduced-capacity conguration), or several low-power congurations per day are permitted (progressively reducing the number of active base stations, the network capacity, and the network power). We then compute the achievable energy savings in several cases: i) assuming that any fraction of base stations can be put to sleep, ii) accounting for the constraints resulting from typical regular base station layouts, and iii) considering the case of a realistic network deployment. Moreover, we consider heterogeneous networks in which coverage is obtained by the superposition of macro-cells, that act as umbrella cells, and micro-cells, that provide additional capacity in specic areas. We prove that the optimal scheduling according to which micro-cells should be put to sleep is in order of increasing load, and that large saving can be achieved in this case as well.

The rest of the paper is organized as follows. Section 2 reviews the related literature. Optimal energy savings schemes for homogeneous networks are presented in Section 3. Savings on regular congurations are computed in Section 3.5. Section 4 details the analysis of heterogeneous networks, and provides a case study of a real network. Finally, Section 5 concludes the paper.

Related Work

The fact that BSs are the most energy-greedy components of cellular networks, and are often under-utilized, was realized only few years ago [START_REF] Louhi | Energy eciency of modern cellular base stations[END_REF][START_REF] Scheck | Energy Eciency of Cellular Networks[END_REF][START_REF]Global Action Plan, An inecient truth[END_REF][START_REF] Hodes | Energy and power conversion: A telecommunication hardware vendor's perspective[END_REF]. Since then, several approaches have been pursued to reduce the carbon footprint of BSs, ranging from the use of renewable energy sources [START_REF]Green Power for Mobile[END_REF], to the improvement of hardware components [START_REF] Claussen | Eects of joint macrocell and residential picocell deployment on the network energy eciency[END_REF], to cell zooming techniques [START_REF] Niu | Cell zooming for cost-ecient green cellular networks[END_REF], to the adoption of sleep modes. As regards sleep modes, starting from our early works [START_REF] Chiaraviglio | Energy-Aware UMTS Access Networks[END_REF][START_REF] Ajmone Marsan | Optimal Energy Savings in Cellular Access Networks[END_REF][START_REF] Ajmone Marsan | Energy-Ecient Management of UMTS Access Networks[END_REF], it has been shown that sleep modes adoption for BSs is an ecient solution that allows a signicant amount of energy to be saved during low trac periods. Later, also the authors of [START_REF] Oh | Toward dynamic energy ecient operation of cellular network infrastructure[END_REF] showed, using real data traces, that promising potential savings are achievable by turning o BSs during low trac periods. Recently, in [START_REF] Son | Base Station Operation and User Association Mechanisms for Energy-Delay Tradeos in Green Cellular Networks[END_REF] the authors have investigated energy savings in dynamic BS operation and the related problem of user association, showing that their algorithms can signicantly reduce the energy consumption. A distributed solution to switch o underutilized BSs when trac is low, and switch them on when the trac is high, was proposed in [START_REF] Peng | Trac-Driven Power Saving in Operational 3G Cellular Networks[END_REF]; large savings, that depend on temporal-spatial trac dynamics, are shown to be possible.

Besides BSs switch-o, sleep modes can be enabled also considering dierent options, ranging from the reduction of the number of active transmitters [START_REF] Saker | Sleep mode implementation issues in green base stations[END_REF], to the switch-o of a whole network, when coverage is provided by other technologies of the same operator, or when several operators oer coverage in the same service area [START_REF] Ajmone Marsan | Energy Ecient Wireless Internet Access with Cooperative Cellular Networks[END_REF], by allowing customers to roam from the network that switches o to one that remains on. Dierently from most previous works, but expanding our analysis in [START_REF] Ajmone Marsan | Optimal Energy Savings in Cellular Access Networks[END_REF] and [START_REF] Ajmone Marsan | Multiple Daily Base Station Switch-Os in Cellular Networks[END_REF], here we analytically characterize the maximum energy savings that can be achieved in regular networks, under a given trac prole. In particular, we analytically show that the optimal trade-o between energy savings and complexity in network management is obtained when only few lowpower congurations per day are allowed, and BSs are put to sleep according to increasing load. These results are also corroborated by a case-study analysis.

T/2 t 1 f(τ 1 ) τ 1 f(τ 3 ) τ 3 Saving f(τ 2 ) τ 2
The extensions that we provide with respect to [START_REF] Ajmone Marsan | Optimal Energy Savings in Cellular Access Networks[END_REF] and [START_REF] Ajmone Marsan | Multiple Daily Base Station Switch-Os in Cellular Networks[END_REF] are mainly the following: i) we consider a more realistic energy consumption model, ii) we consider the case of multiple, progressive low-power congurations per day, proving that small numbers of congurations are sucient to achieve most of the possible energy savings; iii) we prove that the optimal sleep order consists in putting BSs to sleep in increasing order of load; iv) we consider dierent cell types (business and residential); v) we obtain analytical results from a more detailed synthetic trac pattern, and vi) we consider as a case study the heterogeneous BS layout in a square of 800 by 800 m in downtown Munich, with real trac proles, resulting from measurements in an operational network.

Optimal Sleep Modes in Homogeneous Networks

In this section we propose a simple analytical framework to compute the maximum energy saving that can be achieved by properly scheduling multiple low-power network congurations in homogeneous networks. We rst consider an idealized synthetic trac prole, that we call two-step trac pattern, for which we easily obtain analytical results. Then, we present results obtained with some measured trac patterns collected from a cellular network in operation.

The network and trac model

Let f (t) be the daily trac pattern in a cell, i.e., the trac intensity as a function of time t, with t ∈ [0, T ], T = 24 h, and t = 0 at the peak hour; f (t) is normalized to the peak hour trac, so that f (0) = 1. As an example, in Fig. 1 we report a typical daily trac pattern that, for simplicity, is symmetric around T /2. We assume that f (t) is a continuous and dierentiable function of t.

The cellular access network is dimensioned so that at peak trac a given QoS constraint is met. Clearly, if the QoS constraint is met under peak trac f (0), it is also met for lower values of trac intensity, and thus during the whole day. For analytical tractability, we assume that in the considered area all cells have identical trac patterns; thus, we say that the network is homogeneous. We recognize that BSs deployed in real networks can be subjected to dierent trac patterns, and we will consider trac heterogeneity in Section 4.

Consider an area with M homogeneous cells and consider a low-power network conguration Φ such that, during periods of low trac, a fraction x < 1 of the cells, i.e., xM cells, are active, while the remaining fraction, 1 -x, of the cells (actually, of the respective BSs) are in LPI (or sleep) mode. When the low-power conguration Φ is applied, the xM active BSs have to sustain, in addition to their own trac, the trac that in normal conditions is taken care of by the (1 -x)M sleeping BSs; thus, their trac becomes:

f (Φ) (t) = f (t) + (1 -x)M xM f (t) = 1 x f (t) (1)
i.e., an active cell receives 1/x times its own trac . Thus, to always satisfy the QoS constraint, Φ can be applied whenever the trac f (t) is so low that f (Φ) (t) is still below 1, that is the peak hour trac; this is what we call the load constraint,

f (Φ) (t) = 1 x f (t) < 1 (2)
Starting from the peak hour, with decreasing f (t), the earliest time instant τ in which Φ can be applied is dened by,

f (Φ) (τ ) = 1 (3)
so that,

τ = f -1 (x) (4)
By assuming that the low-power conguration Φ is applied as soon as the trac prole permits, the scheme Φ is fully specied by the value of τ . Considering, for simplicity, a daily trac pattern that is symmetric around T /2, i.e., such that

f (τ ) = f (T -τ ) with τ ∈ [0, T /2],
and assuming that f (t) is monotonically decreasing in [0, T /2], the period in which Φ can be applied starts in τ and lasts for the whole time in which the trac intensity is below f (τ ) = x, i.e., for a period of duration T -2τ .

The energy consumption model

Coherently with the assumption of a homogeneous network, we assume that in the considered area all BSs have identical power consumption. Actually, BSs deployed in real networks may consume a dierent amount of power (e.g., due to dierent technology); however, the assumption that all the BSs consume the same amount of power is reasonable, at least in some portions of dense urban areas.

For each BS, we assume that the power consumption equals W LP I in the LPI state, i.e., when the BS is in sleep mode. Instead, when the BS carries a trac f (t), its power consumption can be expressed as

P (t) = W LP I + W 0 + W T f (t) (5)
where W 0 is the power necessary for an active BS carrying zero trac, in addition to W LP I , and W T is the power necessary for the BS to handle one unit of trac. Note that, in our computations, we will consider the normalized values of the three power components, such that the sum is equal to one when the trac is maximum (i.e., equal to one).

Obviously, the values of W LP I , W 0 , and W T depend on the BS technology and model, but normally the W 0 component dominates (see for example [START_REF] Lorincz | Measurements and Modelling of Base Station Power Consumption under Real Trac Loads[END_REF]). Typically, the higher is the power consumption in the LPI state, the shorter is the BS activation time. Therefore, the values of W LP I depend on the policy that an operator may want to adopt, based on activation and deactivation times of BSs. In our computations, we will use low values of W LP I , since we assume the BSs are put in LPI state only a few times per day. This implies that activation/deactivation times, even if long in absolute terms (e.g., tens of seconds or even few minutes), can be considered negligible with respect to long sleep time intervals.

The energy consumed in a day by a BS in a cellular network in which all BSs remain always on is

E ALLON = T 0 (W LP I + W 0 + W T f (t)) dt = T (W LP I + W 0 ) + W T T 0 f (t)dt (6)
Consider now a network in which the low-power conguration Φ is applied at time τ . In this case, the BSs have dierent daily consumption, depending on whether they are always on or they enter sleep mode when trac is low. The energy consumed in a day by a BS which is put to sleep according to conguration Φ is equal to [START_REF] Son | SpeedBalance: Speed-Scaling-Aware Optimal Load Balancing for Green Cellular Networks[END_REF] because from 0 to τ and from T -τ to T the BS is on, while for the rest of the day the BS is in the LPI state. The energy consumed in a day by a BS which remains on while other cells are put to sleep according to conguration Φ is equal to [START_REF] Arnold | Power consumption modeling of dierent base station types in heterogeneous cellular networks[END_REF] because from 0 to τ and from T -τ to T the BS carries only its trac share, while for the rest of the day the BS carries also a portion of the trac of the BSs in the LPI state.

E SLEEP = 2 τ 0 (W LP I + W 0 + W T f (t)) dt + 2(T /2 -τ )W LP I = T W LP I + 2τ W 0 + 2W T τ 0 f (t)dt
E ON = 2 τ 0 (W LP I + W 0 + W T f (t))dt + 2 T /2 τ (W LP I + W 0 + W T 1 x f (t))dt = T (W LP I + W 0 ) + 2W T τ 0 f (t)dt + 2W T 1 x T /2 τ f (t)dt
Considering that a fraction 1 -x of the BSs is put to sleep according to conguration Φ, while the remaining fraction x remains on, the average energy consumption of a BS is

E Φ = (1 -x)E SLEEP + xE ON = T W LP I + [2(1 -x)τ + T x]W 0 + 2W T τ 0 f (t)dt + 2xW T 1 x T /2 τ f (t)dt = T W LP I + T W 0 -(1 -x)[T -2τ ]W 0 + W T T 0 f (t)dt (9)
Thus, the energy saved by using conguration Φ with respect to the always-on case is:

S = E ALLON -E Φ = (1 -x)[T -2τ ]W 0 (10)
which corresponds to saving the power W 0 for the fraction of cells in LPI state, and for the period in which the low-power conguration Φ is used. The fact that no trac is lost is reected in the independence of S from W T . In the numerical results that we will report in what follows we will often use the percentage saving obtained by dividing S by E ALLON .

Let us now focus on the case of multiple low-power congurations in which N low-power network congurations are allowed per day, each conguration being denoted by Φ i with i = 1, ..., N . In particular, given a decreasing trac prole f (t), symmetric around T /2, we assume that the congurations Φ i are ordered in such a way that the fraction of BSs in sleep mode increases with i. In other words, we assume to put to sleep a fraction (1 -x 1 ) of BSs at a certain time instant τ 1 , a fraction (1-x i ) at τ i , ..., and

(1-x N ) at τ N , with x 1 > • • • > x i > • • • > x N . Let the N -dimensional vector τ collect the switching instants τ i , i.e., τ = [τ 1 , τ 2 , • • • , τ N ].
Extending [START_REF] Louhi | Energy eciency of modern cellular base stations[END_REF], the energy saving with respect to the always-on case is, [START_REF] Scheck | Energy Eciency of Cellular Networks[END_REF] with τ N +1 = T /2. Indeed, with reference to Fig. 1 for the case N = 3, the saving is given by the white area made of three rectangles and, for example, from τ 1 to τ 2 the saving is given by 1 -f (τ 1 )(τ 2 -τ 1 ), from τ 2 to τ 3 the saving is given by 1 -f (τ 2 )(τ 3 -τ 2 ), and so on.

S N (τ ) = 2W 0 N i=1 (τ i+1 -τ i )(1 -f (τ i ))
The saving can be maximized (and the consumption minimized) by choosing the congurations Φ i so as to maximize S N (τ ). Assuming that the function S N (τ ) is piecewise dierentiable and convex (these conditions are satised by construction given the conditions we imposed on f (τ )), the optimal choice of the schemes, i.e., the optimal τ , namely τ * , is such that

∂S N (τ )/∂τ i = 0, for i = 1, • • • , N .
The optimal scheme is given by the solution of the following system of equations,

-f ′ (τ i )(τ i+1 -τ i ) + f (τ i ) -f (τ i-1 ) = 0, (12)
with i = 1, ..., N , and f ′ (t) is the derivative of f (t) with respect to time t, and τ 0 = 0 (so that f (τ 0 ) = 1) and τ N +1 = T /2. Notice that there may exist dierent schemes corresponding to the same consumption, and there may exist dierent solutions of (12) that are local maxima of [START_REF] Scheck | Energy Eciency of Cellular Networks[END_REF]; among these values, one of those leading to S(τ * ) can be selected as the optimum. For example, in Fig. 2, two (single) low trac congurations corresponding to time instants τ 1 and τ 2 lead to the same energy saving.

The corresponding maximum energy saving is denoted by S N and it represents the best that can be done under trac f (t) by allowing the network to move across N dierent low-power congurations.

An upper bound to the achievable network saving can be obtained by considering that the fraction of BSs that is in sleep mode increases in a continuous way, through innitesimal increments. In other terms, the upper bound of the saving, namely S U , can be computed as the complement of the integral of f (t),

S U = 2W 0 2 T T /2 0 (1 -f (τ ))dτ (13)
In the case of a non-symmetric trac pattern f (t), it can be easily shown that the optimum scheme can be derived in a similar way, by solving the derivative of the saving S N (τ ) that corresponds to the asymmetric prole.

A synthetic trac pattern

To start analyzing the eect of the number of network congurations used in a day, we consider a synthetic trac pattern, that, while being very simple, allows us to tune the trac shape by acting on a single scalar parameter. We consider the family of two-step trac proles plotted in Fig. 3 and dened by

T/2 t 1 f(τ 1 ) τ 1 f(τ 2 ) τ 2
f (t) =    L-1 L 2t T + 1 0 ≤ t < T 2 L L L-1 ( 2t T -1) T 2 L ≤ t ≤ T 2 (14)
with L ∈ [0, 1]. The parameter L denes the position of the curve knee: the knee is in (LT /2, L); for L = 1/2 the curve is made of just two segments: one for decreasing trac and one for increasing trac. We start by analyzing the case of one low-power network conguration, N = 1, that alternates to the normal full-capacity conguration. When L > 1/2, the maximum energy saving is reached for two values of τ ,

τ * = T /2 3L -1 2L and τ * = T /4 (15)
When L ≤ 1/2, the maximum occurs at the curve knee, that is for

τ * = T L 2 (16)
When two low-power congurations are allowed, i.e., N = 2, the maximum saving is achieved for

(τ * 1 , τ * 2 ) with, (τ * 1 , τ * 2 ) = T 4 L(3L-1) 2L 2 -1/2(L-1) 2 , T 2
L(3L-1) 2L 2 -1/2(L-1) 2 if L > 1/3 T 2 L, T 4 (L + 1) otherwise ( 17
)
For a case in which the BS consumption is independent of the trac (similar to existing equipment), i.e., W T = 0 in (5), Fig. 4 shows, in percentage, the maximum network saving versus L for various values of N ; the upper bound is also reported. Clearly, the saving increases with N , reaching the upper bound for N → ∞. Values of N equal to 2 or 3 are enough to achieve saving that is close to the upper bound. Higher values of N bring small additional improvements only, while introducing higher complexity in network management. By computing the dierence between the maximum achievable saving in the case of two low-power congurations and one only, we found that the saving increase is at most 8%, suggesting that the use of two congurations instead of one only does improve the maximum achievable saving, but to a limited extent.

Measured Trac patterns

We now consider trac proles measured from the network of an anonymized cellular operator.

In particular, we consider trac proles taken from two individual urban cells with dierent user types: one cell refers to a business area, and the other one to an area that is mainly residential. Moreover, for each of these cells, we consider two proles: the weekday prole is chosen as the average of the weekday proles collected during a week; the weekend prole is an average of the two weekend days of the same week. The trac proles are reported in Figs. 5 and6. Proles are normalized to the weekday peak value, that occurs around 11am for the business area, and in the evening for the residential area. Clearly, two completely dierent trends characterize the two areas: trac is concentrated during the working hours of the weekdays for the business area, while trac is higher during the evening for the residential area, where the dierence between weekdays and weekends is marginal. However, for both proles, trac is very low from late night to early morning, i.e., from 2.30am to 7.30am approximately. The transitions from peak to o-peak and vice-versa are extremely steep in the business weekday prole, while they are slow in the residential area. As expected, proles are very specic of given areas and can vary quite remarkably. However, from the set of real measurements we analyzed, we found that, given a certain type of area (residential or business), all trac proles relative to that area are characterized by a very similar trend. This suggests that the sleep scheme should be planned based on the type of the urban area.

Table 1 shows the maximum achievable savings under dierent sleep schemes. We also consider dierent power consumption models, by varying the values of W LP I , W 0 and W T . We observe that saving is higher when W 0 equals the maximum power consumption (i.e., the normalized value is equal to one), and the consumptions W LP I and W T are zero. Obviously, saving decreases as W T increases (and W 0 decreases accordingly), and when the power consumption in LPI mode increases.

Among the considered proles, the largest saving is achieved with the business weekend prole, since trac is extremely low during the whole day. As expected, saving increases with N for all proles . Again, as N increases, the additional saving with respect to the single low-power conguration case is limited, with some dierences between the business and residential cases. In the case of the business weekday prole, with very steep transitions from o-peak to peak trac, one low-power network conguration, N = 1, is already very eective and only marginal improvements are achieved with higher values of N . For the residential area case, improvements with N are larger. This dierence again suggests that the choice of the sleep scheme should be tailored to the trac proles and the type of area.

Sleep Modes with Deployment Constraints

While in the previous section we derived the optimal energy saving considering the shape of function f (t) only, in real cases it is not possible to put to sleep any fraction 1 -x of the Note that, we suppose that an operator may apply multiple low-power network congurations only during suciently large time intervals (e.g., during night), and does not apply any sleep scheme during short intervals of low trac, i.e., when trac decreases for few minutes only. cells, since the access network geometry and the actual site positioning constrain the fraction of sleeping cells to only a few specic values. In this section, we start by focusing on two simple abstract regular cell layouts, and we evaluate, taking into account the deployment constraints, the actual achievable saving. Two frequently considered cellular network congurations are the following:

Inria

X Hexagonal cells with tri-sectorial antennas: the BS is at a vertex of the cell, during low trac periods the cell expands so as to cover the equivalent of 4 or 9 cells. This scheme results in 3 cells being put to sleep out of 4 or 8 out of 9, as sketched in Fig. 7.

X Manhattan layout: cells form a grid structure; this case is typical of streets in a urban scenario. Many sleep schemes are possible, depending on whether the cell is extended along a line or in an omnidirectional fashion, creating square-shaped cells. For the linear case, we consider the schemes represented in the top part of Fig. 8 (1/2, 2/3 and 3/4 cells are put to sleep); for the squared case, as represented in the bottom part of the same gure, we consider schemes leading to 3 out of 4 and 8 out of 9 sleeping cells.

Under the constraints imposed by the regular cell layouts described above, we consider both the synthetic and measured trac proles presented in the previous section. Fig. 9 reports the percentage saving versus the parameter L of the synthetic trac prole, obtained when two low-power network congurations are used. For completeness, the saving upper bound and the maximum saving achievable with N =2 are reported as well. Several cases are considered; for example, the case labeled '1/2-2/3' means that one out of two cells are put to sleep at time instant τ 1 and two out of three are in sleep mode from time instant τ 2 . For small values of L (right part of the curves) the largest saving is obtained by putting into sleep mode the largest fraction of cells (conguration 8/9). These values of L correspond to cases in which the transient from the peak to the o-peak trac is short (steep decrease) and it is convenient to put to sleep a larger number of cells for a (slightly) shorter time. However, the saving rapidly decreases as L increases, and the schemes that correspond to put to sleep a smaller number of cells, such as 1/2 or 2/3, become more convenient.

Consider now the measured trac proles of the business area. Fig. 10 reports the network saving that can be achieved with two low-power network congurations, considering the weekday trac pattern. The graph, with its level curves, shows the saving achievable when the rst conguration is entered at τ 1 and the second one at τ 2 . Observe that, by the denition of τ i , the white area for which τ 1 > τ 2 corresponds to non admissible points. The markers localize the cases possible with regular topologies. Saving is maximized when the rst conguration occurs in the evening, and the second is during night. The strange behavior of the curves corresponding to the vertical slice around lunch time is due to the corresponding gap in the trac prole, see Fig. 5. Interestingly, regular topologies, identied by the markers in the gure, achieve good saving, pretty close to the maximum possible. This suggests that, even in presence of some topological and physical layout constraints, sleep schemes can be quite eective.

Heterogeneous Networks

In the previous section, we have considered homogeneous networks in which all BSs are characterized by the same power consumption and the same trac load, and cells are equivalent and interchangeable in terms of coverage, so that any number of cells can be put into sleep mode while the remaining active cells guarantee coverage. We now consider the case of heterogeneous networks, i.e., networks in which cells of dierent size and load coexist (possibly covered by BSs of dierent technologies). In particular, we consider a scenario in which an umbrella (macro) cell provides coverage over an area, and K micro-cells are deployed to provide additional capacity. To save energy, micro-cells can be put to sleep when their trac is low and can be carried by the macro-cell; in this case, their trac cannot be carried by the other micro-cells due to coverage limits.

As before, we assume that the trac prole f (t) of the umbrella cell is decreasing with t and is symmetric around T /2. The micro-cells have the same trac prole shape as the macro-cell, since this is given by the typical human behavior that is assumed to be uniform in a given area; however, based on the cell size and user density, the shape can be scaled of a given factor, i.e., micro-cell i supports a trac that is α i f (t). We assume that micro-cell i consumes an amount of power equal to

P (i) (t) = W (i) LP I + W (i) 0 + W (i) T α i f (t) (18)
while the macro-cell consumes

P (M ) (t) = W (M ) LP I + W (M ) 0 + W (M ) T f (t) (19)
In the case of homogeneous networks, a low-power network conguration Φ was dened by the fraction of active cells x and the corresponding smallest instant τ in which the load constraint (2) was satised. Here, in the heterogeneous case, we dene a low-power conguration by specifying the active/sleep state, micro-cell by micro-cell. In particular, a conguration Ψ can be represented through an indicating function,

I (Ψ) (k) with k = 1, • • • , K, that
denes the state of the micro-cell k, that can be either sleeping or active,

I (Ψ) (k) = 1 if micro-cell k is sleeping 0 if micro-cell k is active (20)
The conguration Ψ is feasible at time t if the following load constraint condition holds,

1 + K k=1 α k I (Ψ) (k) f (t) < 1 (21)
This condition imposes that the load in the macro-cell does not exceed the maximum allowable load, namely 1; and that the macro-cell is receiving the trac of all the micro-cells that are in sleep mode, i.e., for which I (Ψ) (k) = 1. Assuming, as before, that f (t) is symmetric and decreasing in [0, T /2], the scheme Ψ becomes feasible at time τ , with,

τ = f -1 1 1 + K k=1 α k I (Ψ) (k) (22)
Putting to sleep micro-cell k at time t is convenient in terms of energy consumption when the additional cost that the macro-cell has to sustain to carry the trac of micro-cell k is smaller than the saving achieved by putting micro-cell k into sleep mode; i.e., when the following saving constraint holds,

W (k) 0 + W (k) T α k f (t) ≥ W (M ) T α k f (t) (23)
We dene, then, a scheme Ψ to be convenient at time t if (23) holds for every micro-cell k in sleep mode. When Ψ is applied, the power saving is equal to,

S (Ψ) (t) = K k=1 W (k) 0 + (W (k)
T -W (M ) T )α k f (t) I (Ψ) (k) (24)
To nd the optimal multiple low-power conguration sleep scheme, we rst dene the set of all possible congurations, C. The set C contains 2 K elements that correspond to all possible combinations of any micro-cell being either active or sleeping, C = {Ψ i } with i = 0, • • • , 2 K . At time t, the set of the feasible and convenient congurations is dened by those congurations Ψ i that, at t, satisfy both the load constraint [START_REF] Peng | Trac-Driven Power Saving in Operational 3G Cellular Networks[END_REF] and the saving constraints [START_REF] Ajmone Marsan | Energy Ecient Wireless Internet Access with Cooperative Cellular Networks[END_REF],

C(t) ⊂ C, with C(t) = Ψ i 1 + K k=1 α k I (Ψ i ) (k) f (t) < 1 ∩ Ψ i ∀k, I (Ψ i ) (k) W (k) 0 + (W (k) T -W (M ) T )α k f (t) ≥ 0
Among the congurations in C(t), an optimal choice, Ψ * (t) ∈ S(t), is given by one of the congurations that maximizes the saving in [START_REF] Auer | How much Energy is needed to run a Wireless Network?[END_REF],

Ψ * (t) = max Ψi∈C(t) S (Ψ) (t) (25)
We focus now on the (realistic) case in which the cost to carry a unit of trac in the macrocell, W (M ) T is larger than the costs to carry the same amount of trac in the micro-cells, W (k) T . Indeed, the larger transmission power makes this happens most of the time [START_REF] Auer | How much Energy is needed to run a Wireless Network?[END_REF].

This assumption means that in [START_REF] Auer | How much Energy is needed to run a Wireless Network?[END_REF] the terms

W (k) T -W (M ) T
are negative, and the larger the trac α k f (t) is, the smaller the saving is. the least-loaded policy, consisting in putting the micro-cells into sleep mode in reverse order w.r.t. their load, i.e., from the least loaded to the most loaded, is optimal in terms of the achieved saving.

Proof. Consider a conguration Ψ i . The term f (t) K k=1 α k I (Ψi) (k) represents the trac increment that the macro-cell undergoes when Ψ i is applied; where α k f (t) is the contribution to trac due to micro-cell k going to sleep mode. Now, since f (t) is monotonically decreasing in [0, T /2], the time τ i at which Ψ i can be applied depends on this trac increment; considering two congurations Ψ i and Ψ j ,

τ i < τ j if K k=1 α k I (Ψi) (k) < K k=1 α k I (Ψj ) (k) (26)
That is, the time order in which the congurations become feasible (i.e., satisfy the load constraint) is according to increasing values of the total trac added to the macro-cell. Denote by φ i the time at which putting to sleep micro-cell i becomes convenient; from [START_REF] Ajmone Marsan | Energy Ecient Wireless Internet Access with Cooperative Cellular Networks[END_REF],

φ i = f -1   W 0 α i W (M ) T -W T   (27)
Since f (t) is monotonically decreasing, the times φ i are ordered according to increasing values of the individual micro-cell load, α i , that is:

φ i < φ j if α i < α j (28)
Now, consider the set A V ⊂ C of all the congurations Ψ i corresponding to V micro-cells in sleep mode,

A V = Ψ i K k=1 I (Ψi) (k) = V
Among these, the scheme Ψ V that saves the most, corresponds to putting to sleep the V least loaded cells. Indeed, from [START_REF] Auer | How much Energy is needed to run a Wireless Network?[END_REF], the saving is

S (ΨV ) = V W 0 + K k=1 W T -W (M ) T α k f (t)I (ΨV ) (k) (29)
and, since the second term is negative, due to W (M ) T > W T , the saving is maximized if the amount of trac of the sleeping cells is smallest.

Moreover, among the schemes in A V , Ψ V is also the one that becomes feasible at the earliest time, since according to [START_REF] Ajmone Marsan | Switch-O Transients in Cellular Access Networks with Sleep Modes[END_REF], the micro-cells can be put to sleep in the order of the amount of carried load.

When Ψ V satises the constraint [START_REF] Ajmone Marsan | Energy Ecient Wireless Internet Access with Cooperative Cellular Networks[END_REF], its saving is larger than the best scheme of A V -1 , that is Ψ V -1 : i.e., S (Ψ V ) > S (Ψ V -1 ) because the contribution to saving given by each micro-cell k that is sleeping is positive:

W 0 + W T -W (M ) T α k f (t) > 0 (30) RR n°8186
and the saving S (ΨV ) is composed of the sum of the same savings of Ψ V -1 plus a positive term, corresponding to the additional cell that is sleeping in

Ψ V w.r.t. Ψ V -1 .
Denote by t V the time instant in which Ψ V becomes feasible and convenient. By denition of t V , in the interval between t V and t V +1 , no conguration can save more than Ψ V , so that in the interval [t V , t V +1 ] the conguration Ψ V is optimum, in the sense that it achieves the maximum possible saving.

By extending this reasoning to the other time intervals, we conclude that putting to sleep micro BS from the least loaded to the most loaded, leads to the maximum saving.

4.1

Case Study

In the following, we nally show how the previous results can be applied to a realistic cell deployment.

We consider a portion of the central area of the city of Munich, in Germany, which corresponds to a square of 800 x 800 m, comprising 1 macro-cell, 8 micro-cells, and 10 femto-cells. Femto-cells are deployed to provide additional capacity during peak hours in indoor environments. However, we do not consider them in the sleep schemes, since they consume a negligible amount of power. The micro-cells are served by isotropic antennas, each with transmission power of 1 W, while the macro-cell has a tri-sectorial antenna with 40 W emitted power. We assume that the total power consumption of the macro-cell is seven times higher than the one of a micro-cell [START_REF] Auer | Cellular Energy Eciency Evaluation Framework, GreeNet workshop[END_REF]. Fig. 11 presents a map of the considered area, together with a side view (at the bottom of the gure).

The area coverage is computed from the signal strength received on the users' pilot channel. To estimate the channel conditions, i.e., the path losses, we use the results of a tool developed by Alcatel-Lucent, called Wireless System Engineering (WiSE) [START_REF] Fortune | WiSE Design of Indoor Wireless Systems: Practical Computation and Optimization[END_REF], that is based on ray-tracing techniques. We refer the reader to [START_REF] Ajmone Marsan | Switch-O Transients in Cellular Access Networks with Sleep Modes[END_REF] for further details on users' coverage computation.

The network is planned assuming that in the coverage areas of the micro-cells, the users density is 5 times higher than in the remaining area. As trac prole, we consider the weekday proles of either the business or the residential areas, see Figs. 5 and6. Moreover, we assume that at the peak trac hour, the most loaded cell carries a normalized trac load equal to 1. During low trac periods, micro-cells enter sleep mode, and the macro-cell acts as an umbrella cell which is never switched o. We assume that the macro-cell can guarantee full coverage, even when all the other cells are put into sleep mode.

Table 2 summarizes the network saving obtained under dierent schemes, for both the considered proles, and for dierent power consumption models. As already noted in Section 3, the highest saving is achieved when the power consumption W 0 is maximum and the power consumed in LPI state is zero, with saving that slightly decreases as W T increases. Moreover, the increase of W LP I makes the sleep mode scheme less convenient.

Saving of the order of 15-25% can be achieved with one low-power network conguration. The saving increases signicantly with two low-power congurations (up to 32%), while the saving increment is marginal as the number of congurations further increases. Note that, in the case of one low-power conguration, the savings achievable with the business trac prole are higher, due to the higher steepness of the transients; the maximum savings are, instead, comparable for the two trac proles.

Finally, Figs. 12 and 13 show the number of active micro BSs versus time, considering the weekday trac proles: the cases of one, two, three low-power congurations, are reported. For completeness, the curve obtained with the Least-Loaded policy is also shown (label 'Maximum'): this represents a lower bound on the minimum number of active BSs, and corresponds to the maximum achievable saving.

Conclusions

In this paper we investigated the energy saving that can be achieved in cellular access networks by optimizing the use of sleep modes according to daily trac variations.

By assuming that, as is usually the case in dense urban environments, when a cell is in sleep mode, coverage can be lled by its neighbors, we derived expressions for the optimal energy saving when the network can move among N dierent low-power network congurations, and an expression for a theoretical upper bound of saving. Our derivation proves that energy savings, as well as the optimal choice of the periods in which dierent low-power congurations should be adopted, are functions of the daily trac patterns. Thus, the rst main insight deriving from this work is that the daily trac pattern plays a central role in the design of dynamic network planning schemes that adopt sleep modes.

The numerical results we presented, derived for many cell layouts, trac patterns, and power consumption models, provide several additional interesting insights. First of all, for the considered real trac patterns, savings are quite signicant: they reach 90% in the case of weekend trac in business areas, and are of the order of 30-40% in other cases. This is an important signal indicating that sleep modes can indeed be a useful tool for energy-ecient networking. Second, we have shown that signicant savings can be achieved with only one low-power network conguration per day, while the benet of multiple congurations is minor. This is especially true in the case in which the trac prole has a steep transition from the o-peak hours to on-peak hours, like in business areas during weekdays. This is also an important message, because it shows that most of the gains can be obtained with limited eort on the side of network management. Third, savings can be strongly inuenced by the dierent power consumption components of a BS. Indeed, sleep modes are more eective when the power necessary to carry zero trac is high, and both the power consumption in LPI mode and the power proportional to the trac are low. Finally, we have also proved that in presence of deployment of BSs for additional capacity provisioning, the optimal order in which the BSs should enter sleep mode, i.e. the order that jointly maximizes energy saving and minimizes the number of BS transients, consists in putting cells to sleep according to increasing values of their load. This too, is a relevant result for network management.

Our results provide a tangible incentive for cellular network operators to implement sleep modes in their networks.

Figure 1 :

 1 Figure 1: Example of multiple sleep schemes with N =3.

Figure 2 :Figure 3 :

 23 Figure 2: Two schemes achieving the same energy saving.

Figure 4 :Figure 5 :

 45 Figure 4: Synthetic trac pattern: maximum achievable saving for various number of network congurations versus the parameter L.

Figure 6 :

 6 Figure 6: Residential cell: weekday and weekend trac proles.

Figure 7 :

 7 Figure 7: Hexagonal three-sectorial conguration: 3 cells being put to sleep out of 4 (left) and 8 out of 9 (right).

Figure 8 :Figure 9 :

 89 Figure 8: Manhattan congurations: linear (top) and squared (bottom).

InriaFigure 10 :

 10 Figure 10: Business cell -weekday prole: network saving with two low trac network congurations.

Lemma 1 :

 1 Under the two following conditions, 1. all micro-cells have the same power consumption model, i.e., W (k) LP I = W LP I , W (k) 0 = W 0 and W (k) T = W T ; Inria On the Eectiveness of Single and Multiple Base Station Sleep Modes in Cellular Networks 172. the cost to carry a unit of trac through the macro-cell is higher than through the microcell, i.e., W

Figure 11 :

 11 Figure 11: Case study: Map with cell identiers (SC = micro cell). Aerial view (top) and side view (bottom).

Figure 12 :

 12 Figure 12: Business weekday: number of active micro BSs versus time for dierent network congurations.

Figure 13 : 1 12 4Networks 15 4. 1

 13112151 Figure 13: Residential weekday: number of active micro BSs versus time for dierent network congurations.

Table 1 :

 1 Measured trac patterns: maximum achievable saving for various number of network congurations

	Power Consumption Model	Network conguration	S[%] Business WE	S[%] Business WD	S[%] Residential WE	S[%] Residential WD
	W LP I =0.0 W 0 =1.0 W T =0.0 W LP I =0.0 W 0 =0.6 W T =0.4 W LP I =0.1 W 0 =0.4 W T =0.5	Upper Bound N = 3 N = 2 N = 1 Upper Bound N = 3 N = 2 N = 1 Upper Bound N = 3 N = 2 N = 1 Upper Bound N = 3 N = 2 N = 1	91.40 89.85 89.28 84.30 80.46 79.10 78.62 74.21 86.38 84.92 84.38 79.67 67.26 66.12 65.70 62.04	61.86 50.96 46.57 42.01 52.68 43.39 39.65 35.77 48.99 40.35 36.88 33.27 35.50 29.24 26.72 24.10	50.10 40.06 34.55 26.61 42.16 33.71 29.07 22.40 37.45 29.94 25.82 19.90 26.60 21.27 18.34 14.13	59.90 49.21 44.91 33.90 50.90 41.82 38.16 28.81 46.97 38.58 35.21 26.58 33.91 27.86 25.42 19.19

W LP I =0.1 W 0 =0.8 W T =0.1

Table 2 :

 2 Case Study: savings with dierent network congurations

	Power Consumption Model Network conguration	S[%]	S[%]
			Business weekday Residential weekday
		Single (7/9)	26.39	19.73
	WLP I =0.0 W0=1.0 WT =0.0	Double (4/9)-(7/9) Triple (2/9)-(4/9)-(7/9)	31.96 34.64	32.16 33.43
		Maximum (Least-Loaded)	38.27	38.79
		Single (7/9)	23.18	17.24
	WLP I =0.1 W0=0.8 WT =0.1	Double (4/9)-(7/9) Triple (2/9)-(4/9)-(7/9)	27.84 30.06	27.73 28.78
		Maximum (Least-Loaded)	33.16	33.30
		Single (7/9)	24.69	17.92
	WLP I =0.0 W0=0.6 WT =0.4	Double (4/9)-(7/9) Triple (2/9)-(4/9)-(7/9)	28.73 30.05	27.31 28.18
		Maximum (Least-Loaded)	33.55	32.21
		Single (7/9)	18.99	13.53
	WLP I =0.1 W0=0.4 WT =0.5	Double (4/9)-(7/9) Triple (2/9)-(4/9)-(7/9)	21.71 22.94	20.00 20.59
		Maximum (Least-Loaded)	25.10	23.27

Mots-clés : Ecacité énergétique, réseaux cellulaires, QoS et modes de sommeil

RR n°8186

Inria

Note that (1) holds for the case of just one low-power network conguration, Φ, in an area where M cells are deployed. We discuss the case of several low-power congurations next.RR n°8186

Acknowledgement

The authors wish to thank Alberto Conte and Afef Feki of Alcatel-Lucent Bells Labs for providing data about the real BS deployment and coverage in downtown Munich. The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement n. 257740 (Network of Excellence TREND).