Grit Claßen
email: classen@umic.rwth-aachen.de

Arie M C A Koster
email: koster@math2.rwth-aachen.de

Anke Schmeink
email: schmeink@umic.rwth-aachen.de

Robust Planning of Green Wireless Networks

Current methods dealing with the energy efficient wireless network planning problem require a static model. However, bit rate requirements vary and rise over time, users move around and path gain fluctuates. In this paper, robust optimization is applied to deal with demand uncertainty. We present a robust optimization model for the energy-efficient planning of wireless networks and apply cutting planes to reduce the complexity of the model. Furthermore, a case study is performed to compare the robust formulation to its deterministic counterpart and to conventional network planning.

I. INTRODUCTION

Future radio networks are obliged to cope with drastically increasing user demands. This leads inevitably to a significantly increasing energy consumption (e. g., the energy consumption of Vodafone Group already increased about 27 % from 2006/07 to 2009/10 [START_REF]Sustainability report[END_REF]). The high user demands (compared to the requirements for ordinary telephony and short message services) result from, e. g., traffic-intensive smartphone applications. Even though user demand and resource restrictions have been considered in the planning of third generation (3G) networks [START_REF] Amaldi | Radio planning and coverage optimization of 3G cellular networks[END_REF][START_REF] Eisenblätter | Integer Programming Methods for UMTS Radio Network Planning[END_REF][START_REF] Siomina | An effective optimization algorithm for configuring radio base station antennas in UMTS networks[END_REF], these networks reach the limits of their capacity. High data rates can be offered, but only for some users and with limited coverage. Thus, more base stations (BSs) are needed and the energy consumption rises (not only by signal power but also by air-conditioning etc. [START_REF] Deruyck | Comparison of power consumption of mobile WiMAX, HSPA and LTE access networks[END_REF]). To tackle the problem of inferior network performance, future networks utilize a couple of advanced techniques, e. g., Orthogonal Frequency Division Multiple Access (OFDMA). Nevertheless, an optimal planning of wireless networks is of utmost importance to fully utilize the technological gains and to reduce the energy consumption.

Energy efficient wireless network planning has recently attracted a great deal of attention: [START_REF] Fehske | Energy efficiency improvements through micro sites in cellular mobile radio networks[END_REF][START_REF] Richter | Energy efficiency aspects of base station deployment strategies for cellular networks[END_REF][START_REF] Richter | Traffic demand and energy efficiency in heterogeneous cellular mobile radio networks[END_REF] to name just three. Current wireless network planning [START_REF] Eisenblätter | Integer Programming Methods for UMTS Radio Network Planning[END_REF][START_REF] Fehske | Energy efficiency improvements through micro sites in cellular mobile radio networks[END_REF][START_REF] Richter | Energy efficiency aspects of base station deployment strategies for cellular networks[END_REF][START_REF] Siomina | An effective optimization algorithm for configuring radio base station antennas in UMTS networks[END_REF] requires a static model of the problem. However, many factors of wireless networks are non-deterministic. Fluctuating bit rate requirements and channel conditions are just two of prominent examples of uncertain parameters.

The robust optimization approach by Bertsimas and Sim [START_REF] Bertsimas | The price of robustness[END_REF] deals with uncertainty by limiting the number of uncertain

The research described in this paper was supported by the excellence initiative of the German federal and state governments and by the UMIC Research Centre at RWTH Aachen University.

factors by a robustness parameter. The robustness of the solution can be adapted by varying the parameter.

In this paper, robust optimization is applied to deal with demand uncertainty. In Section II, we develop a static system model and formulate the problem as an integer linear program (ILP) based on [START_REF] Engels | Profit-oriented combination of multiple objectives for planning and configuration of 4G multi-hop relay networks[END_REF] for the energy efficient planning of wireless networks. A simplified inter-cell interference model is used to unveil the novelty of the robust optimization model presented in Section III. The robust formulation is enhanced by the application of three types of cutting planes in Section IV. In Section V, we perform a case study for a realistic wireless network scenario to compare the robust ILP to its deterministic counterpart and to conventional wireless network planning.

II. SYSTEM MODEL AND PROBLEM FORMULATION

First, we introduce the system model considering a future wireless network and downlink (DL) data transmission based on the model presented in [START_REF] Engels | Profit-oriented combination of multiple objectives for planning and configuration of 4G multi-hop relay networks[END_REF]. Let S be a set of candidate sites (more precisely, site configurations) for BSs. A deployed BS s ∈ S consumes power p s and provides a total DL bandwidth b s . Furthermore, let T be a set of traffic nodes (TNs) to be assigned to the deployed BSs. Each t ∈ T has a demand w t and can be assigned to at most one BS (i. e., no soft handover), which applies, e. g., to 4G networks.

By considering OFDMA as DL transmission technology, we assume that no intra-cell interference occurs. A simplified inter-cell interference model is used requiring the selected BSs to constitute an independent set in a predefined conflict graph G = (S, E), i. e., a subset of S such that ij / ∈ E ∀ i, j ∈ S. Additionally, for each (s, t) pair a value e st called spectral efficiency is defined to incorporate, e. g., the modulation and coding scheme that is supported by the associated signal-tonoise ratio (SNR). To establish a transmission link, it must exceed a certain threshold e min . (Note that this restriction implicitly also guarantees a minimum SNR.)

If TN t is assigned to BS s, the established transmission link from s to t occupies a certain amount of the available DL bandwidth b s . This amount can be computed by division of demand w t by spectral efficiency e st (provided e st ≥ e min ).

To model the energy efficient planning problem as an ILP, we introduce the following auxiliary sets of indices to incorporate the constraint on the sprectral efficiency.

S * T := {(s, t) ∈ S × T : e st ≥ e min }, S t := {s ∈ S : (s, t) ∈ S * T } ∀t ∈ T, T s := {t ∈ T : (s, t) ∈ S * T } ∀s ∈ S.
Let x s ∈ {0, 1} denote whether or not BS s ∈ S is deployed and z st ∈ {0, 1} whether t ∈ T s is assigned to s. We introduce a slack variable u t ∈ {0, 1} that denotes whether t is not assigned to any BS. The main objective is to minimize the total power consumption of the network while minimizing the number of TNs not served by any BS, i.e., maximizing the number of covered TNs (without this part, the optimal solution would be zero). To combine these conflicting objectives, the parameter λ is introduced. The optimization model is defined as follows.

min s∈S p s x s + λ t∈T u t (1a) s.t. s∈St z st + u t = 1 ∀ t ∈ T (1b) x i + x j ≤ 1 ∀ ij ∈ E (1c) t∈Ts w t e st z st ≤ b s x s ∀ s ∈ S (1d) x s , z st , u t ∈ {0, 1} (1e)
Constraints (1b) ensure that a TN is covered by at most one BS. To limit inter-cell interference, constraints (1c) guarantee an independent set of deployed BSs. The capacity constraints (1d) ensure that the total bandwidth allocated does not exceed the total available DL bandwidth. Furthermore, these constraints implicitly make sure that a TN can be assigned to a BS if and only if this BS is deployed.

III. ROBUST FORMULATION

Although many parameters in a wireless network are uncertain, such as channel conditions, interference etc., we only consider demand uncertainty in our model. We apply the robust optimization approach presented in [START_REF] Bertsimas | The price of robustness[END_REF] to formulation [START_REF]Urban micro cell measurements and building data[END_REF]. The demand values are now modelled as symmetric and bounded random variables that take values in [ wt -ŵt , wt + ŵt ], where wt denotes a nominal value and ŵt its highest deviation. We assume that at most Γ ∈ {0, . . . , |T |} demand values per BS deviate from the default value wt simultaneously (in the worst case towards wt + ŵt ). Hence, constraints (1d) are replaced by: t∈Ts wt e st z st + max

T ′ ⊆Ts,|T ′ |≤Γ t∈T ′ ŵt e st z st ≤ b s x s ∀ s ∈ S (2)
By exploiting LP duality (introducing dual variables µ s and ν st ), the maximum in (2) can be linearized, resulting in the following ILP as robust counterpart of (1) (see [START_REF] Bertsimas | The price of robustness[END_REF]).

µ s + ν st ≥ ŵt e st z st ∀(s, t) ∈ S * T (3b) µ s ≥ 0, ν st ≥ 0 (3c) IV. CUTTING PLANES
The performance of the branch-and-bound algorithm for solving ILPs can significantly be improved by cutting planes, i. e., inequalities that are valid for all integer points but not for some linear relaxation solutions. State-of-the-art ILP solvers like CPLEX [START_REF][END_REF] generate cutting planes internally but cannot take advantage of the particular problem structure known to the user. For the problem at hand, we identified a number of problem-specific inequalities, partly well-known for substructures contained in [START_REF] Bertsimas | The price of robustness[END_REF]. Without these cuts our computations would have been far less competitive. [START_REF] Van Roy | A cross decomposition algorithm for capacitated facility location[END_REF] Constraints (3a) implicitly state that a TN can be assigned to a BS iff this BS is deployed. It is well-known that (3) can be strengthened by adding these constraints explicitly:

A. Variable Upper Bounds

z st ≤ x s ∀(s, t) ∈ S * T (4)

B. Maximal Clique Inequalities [15]

A clique of a graph G = (S, E) is a subset U ⊆ S for which holds: u, v ∈ U ⇒ uv ∈ E, i. e., a clique is a complete subgraph. A clique is maximal if it is not included in a larger clique. We replace constraints (1c) by all maximal clique inequalities for the independent set polytope:

s∈U x s ≤ 1 ∀U ⊂ S, U is a maximal clique in G = (S, E).
Though NP-complete, all maximal cliques can be computed by the Bron-Kerbosch algorithm [4] without much effort.

C. Cover Inequalities

Constraints (2) are closely related to the robust knapsack problem. The general structure of (2) can be written as i∈I āi y i + max

I ′ ⊆I:|I ′ |≤Γ i∈I ′ âi y i ≤ bx . ( 5
)
where I denotes the set of items (TNs), āi the default knapsack weight, âi its deviation, and b the knapsack capacity. If x = 1, (5) describes a robust knapsack. Since x = 0 implies y i = 0 for all i ∈ I, every valid inequality for the robust knapsack problem can be adapted to a valid inequality for (5) (and thus for (3)) by multiplying its right hand side with x.

In [START_REF] Klopfenstein | Cover inequalities for robust knapsack sets -Application to the robust bandwidth packing problem[END_REF] the well-known cover inequalities for the knapsack problem have been generalized to the robust knapsack problem. A set

(C ∪ J) ⊆ I is a robust cover if |J| ≤ Γ, |C| ≥ 0 and i∈C āi + i∈J (ā i + âi ) > b
For any robust cover C ∪ J, the robust cover inequality

i∈C∪J y i ≤ (|C ∪ J| -1)x (6)
is valid for [START_REF] Büsing | Recoverable robustness in optimization[END_REF]. Such a cutting plane can be strenghtened by means of the concept of an extended cover, cf. e. g., [START_REF] Büsing | Recoverable robustness in optimization[END_REF][START_REF] Büsing | Recoverable Robust Knapsacks: the Discrete Scenario Case[END_REF]: selecting an item i whose default weight āi is greater than or equal to the maximum default weight in C and whose peak weight āi + âi is greater than or equal to the maximum peak weight in J implies that at most |C ∪J|-2 items of the robust cover can be taken. Hence, i∈E(C,J)

y i ≤ (|C ∪ J| -1)x (7)
is also valid, with E(C, J) := E ∪ (C ∪ J) defined by

E := i ∈ I : āi ≥ max j∈C āj , āi + âi ≥ max j∈J (ā j + âj ) (8)
Since there exist (exponentially) many robust cover inequalities, these are not added to (3) in advance, but are separated on the fly. The separation problem is NP-hard in itself. Therefore, we adapt the separation heuristic given in [START_REF] Klopfenstein | Cover inequalities for robust knapsack sets -Application to the robust bandwidth packing problem[END_REF] for robust cover inequalities. The main steps of this heuristic can be summarized as follows.

The items are sorted according to the smallest ratios of profit (i.e., in the objective of the separation problem) to peak demand in the first step. Then the set J, consisting of all TNs considered with their peak demands, is determined. If the capacity is already exceeded, we stop. Otherwise, the set C is filled with TNs, for which the nominal demand is considered, until the capacity is exceeded. Finally, the constructed robust cover is extended by means of (8), if possible.

V. CASE STUDY

In this section, we describe a case study to reveal the added value of the robust optimization approach. After the description of the scenario, we discuss the optimization results and propose a way to determine a good choice for Γ. Finally, we compare the solutions with static network planning.

A. The Scenario

The proposed model is tested for a planning scenario based on signal propagation data for Munich, available at [START_REF]Urban micro cell measurements and building data[END_REF] with 40 BS candidate sites and 450 randomly distributed TNs. The signal prediction is done by a cube oriented ray launching algorithm [START_REF] Mathar | A cube oriented ray launching algorithm for 3D urban field strength prediction[END_REF]. Two BSs are adjacent in the conflict graph iff the distance between them is at most 500 m. The resulting graph is illustrated in Fig. 1. Furthermore, we use the following scenario parameters: b s = 10 MHz, p s = 4000 W ∀s ∈ S (based on [START_REF] Deruyck | Comparison of power consumption of mobile WiMAX, HSPA and LTE access networks[END_REF]), e min = 0.5 bps/Hz. For each t ∈ T , wt is computed by randomly generating user profiles from Table I: for both data and web services a percentage and bit rate is uniformly drawn from the intervals. The remaining percentage is used for Voice-over-IP (VoIP) with a bit rate of 64 kbps. The value ŵt is computed such that wt + ŵt = 643.2 kbps, simulating a worst case demand.

Since the solution depends on the choice of λ, we tested three values: 1000, 2000, 4000. Hence, based on the value of the total power consumption of a BS, it becomes beneficial to deploy an additional BS if more than four, two, or one TN(s) cannot be covered.

We used a Linux machine with a 2.93 GHz Intel Xeon W3540 processor, 12 GB RAM, and CPLEX 12.2 [START_REF][END_REF]. A CPU time limit of 4 h is set. Note, without the cutting planes described in Section IV the computations would have been far less competitive.

B. Γ-Robust Wireless Network Planning

For Γ ∈ {0, 1, . . . , 40} and λ ∈ {1000, 2000, 4000}, Fig. 2 shows the best solution value (primal bound) and a lower bound on the optimal solution value (dual bound) found within the given time limit. In about 59% of the cases both bounds match, hence an optimal solution is found. We observe that the optimality gap increases with increasing Γ (the course of the bounds is similar, independent of λ). The increase in the objective value is the price of robustness, i. e., more robust solutions come at a price.

Figure 3 shows for all λ the number of deployed BSs as well as the number of served TNs per BS. As expected, with increasing Γ the number of deployed BSs increases stepwise, whereas the TNs per BS decreases. Deviations from this rule can be explained by the non-optimality of the solutions.

C. Evaluation of Robust Planning

To evaluate the robustness of the different solutions, we computed 1000 snapshots to simulate various traffic demand scenarios. In each snapshot, the demand of the TNs is binomially distributed between wt and wt + ŵt with a probability of 0.5 (this value is chosen rather high to increase the exploratory power of the evaluation). From this, we compute the (over)load for each deployed BS in a solution: the allocated bandwidth divided by the DL bandwidth. Fig. 4 shows the maximum load of the BSs for each λ and Γ averaged over the snapshots. A value less than 1 means that there is no overload; the TNs can be served at their required bit rates and it is even possible to serve more than the assigned TNs.

With increasing Γ the average overload decreases. Since the snapshots are representative for our model, Fig. 4 suggests to set Γ = 16 for a robust solution, independent of λ.

D. Conventional Wireless Network Planning

In conventional wireless network planning any uncertainties of parameters are ignored; all parameters are assumed to be static. To be able to compensate demand fluctuations, a network operator should plan with values equal or close to the peak demand values [START_REF] Olinick | Mathematical programming models for third generation wireless network design[END_REF]. To compare our results with such a conventional planning approach, we run model (1) with w t = wt + ŵt for all t ∈ T . The best/optimal solution value ranges from 66, 000 (λ = 1000) to 96, 000 (λ = 4000). By definition of the demand values, no overload can occur in these solutions.

In comparison to the solutions for Γ = 16, the conventional solutions for λ = 1000, 2000 require one more BS (13, 14 in total). For λ = 4000, the same number of BSs is deployed [START_REF] Padberg | On the facial structure of set packing polyhedra[END_REF], but less TNs can be covered (441 compared to 443). Stated otherwise, in all cases, a solution with higher energy efficiency could be found by the robust optimization approach, either by deploying less BSs, or serving more TNs with the same amount of energy.

VI. CONCLUDING REMARKS

We have introduced an optimization model for the energy efficient planning of future wireless networks which considers technical system characteristics such as OFDMA. Applying Γrobustness, we incorporated demand uncertainty. Network operators can assess the trade-off between robustness and energy consumption by varying the robustness parameter and the λ. In our case study, we observed energy savings either by deploying less BSs or serving more TNs with the same number of BSs.

The above results naturally depend on the probability of high traffic volumes. If deviations in the snapshots simulated in Section V-C are less likely to happen, lower Γ values will suffice for planning a wireless network without overload situations. Ideally, snapshots based on real-traffic data are used to determine the value of Γ and the corresponding design.

Fig. 1 .

 1 Fig. 1. The scenario. BSs are denoted by (blue) crosses. Each line is an edge in the conflict graph. (Black) dots stand for TNs.

Fig. 3 .

 3 Fig. 3. Number of covered TNs averaged over the number of BSs and deployed BSs.

Fig. 2 .

 2 Fig. 2. Primal and dual bounds.

ACKNOWLEDGEMENT

The authors would like to thank Alexander Engels for providing us with realistic network data and Manuel Kutschka for assisting in algorithmic implementations.


François Mériaux
email: meriaux@lss.supelec.fr

Samson Lasaulce
email: lasaulce@lss.supelec.fr

Mean-Field Games and Green Power Control

In this work, we consider a distributed wireless network where many transmitters communicate with a common receiver. Having the choice of their power control policy, transmitters are concerned with energy constraints : instantaneous energy-efficiency and long-term energy consumption. The individual optimization of the average energy-efficient utility over a finite horizon is studied by using control theory and a coupled system of Hamilton-Jacobi-Bellman-Fleming equations is obtained. Even though the existence of a solution to the corresponding stochastic differential game is proven, the game is difficult to analyze when the number of transmitters is large (in particular, the Nash equilibrium analysis becomes hard and even impossible). But when the number of transmitters is large, the stochastic differential game converges to a mean-field game which is ruled by a more tractable system of equations. A condition for the uniqueness of the equilibrium of the mean-field game is given.

I. INTRODUCTION

Power control has always been recognized as an important problem for multiuser communications [START_REF] Foschini | A simple distributed autonomous power control algorithm and its convergence[END_REF], [START_REF] Yates | A framework for uplink power control in cellular radio systems[END_REF]. With the appearance of new paradigms such as ad hoc networks [START_REF] Gupta | A system and traffic dependent adaptive routing algorithm for ad hoc networks[END_REF], unlicensed band communications, and cognitive radio [START_REF] Mitola | Cognitive radio: making software radios more personal[END_REF], [START_REF] Fette | Cognitive Radio Technology[END_REF], designing distributed power control policies has become especially relevant; in such networks, terminals can freely choose their power control policies and do not need to follow orders from central nodes. More recently, the need for building green communication networks has appeared to be stronger and stronger [START_REF] Palicot | Cognitive radio: an enabling technology for the green radio communications concept[END_REF]. The goal is to manage energy consumption both at the mobile terminals and network infrastructure sides [START_REF] Richter | Energy efficiency aspects of base station deployment strategies for cellular networks[END_REF]. The work reported in this paper precisely falls into this framework that is, the design of green distributed power control policies in multiuser networks.

More precisely, we consider a network which comprises many transmitters and one receiver. Each transmitter chooses its power control policy in order to maximize its average energy-efficiency (measured in bit per Joule). Note that a similar framework was analyzed in [START_REF] Goodman | Power control for wireless data[END_REF]. In [START_REF] Goodman | Power control for wireless data[END_REF], the problem is modeled by a static game: for each transmission block, the transmitters choose their power levels strategically but independently from past blocks. In [START_REF] Treust | A repeated game formulation of energyefficient decentralized power control[END_REF], it has been shown that much more efficient control policies can be obtained by exploiting long-term interactions, which is done by using the models of repeated games. But, as the channel gains associated

The authors would like to thank Hamidou Tembine from École Supérieure d'Électricité, Supélec for his many constructive comments (tembine@iee.org).

with the different communication links vary over time, there is generally a loss of optimality when using repeated games. Indeed, in [START_REF] Treust | Implicit cooperation in distributed energy-efficient networks[END_REF], [START_REF] Mériaux | Energy-efficient power control strategies for stochastic games[END_REF], it is shown that the model of stochastic games is more appropriate and can lead to better policies. The problem is that, even though some special ad hoc policies can be found [START_REF] Mériaux | Energy-efficient power control strategies for stochastic games[END_REF], stochastic games are not fully characterized in general; in particular, Folk theorems are only available in special cases. Additionally, the problem of characterizing the performance of distributed networks modeled by stochastic games becomes very hard and even impossible when the number of players becomes large. The same statement holds for determining individually control strategies. This is where mean-field games come into play. Mean-field games [START_REF] Lasry | Mean field games[END_REF] represent a way of approximating a stochastic differential (or difference) game, by a much more tractable model. Typically, instead of depending of the actions and states of all the players, the mean-field utility of a player only depends on its own action and state, and depends on the others through a meanfield. It seems that the only work where mean-field games has been used for power control is [START_REF] Tembine | Joint power controlallocation for green cognitive wireless networks using mean field theory[END_REF]. Compared to the latter reference, the present work is characterized by a different utility function (no linear quadratic control assumptions is made here), the fact that the battery level of a transmitter is considered as part of a terminal state, and the existence and uniqueness analysis for of mean-field equilibria is conducted.

This article is organized as follows. In Section II, the wireless context is described and we explain how we model our problem with a stochastic differential game. In Section III, the convergence of this stochastic differential game to a meanfield game is proven and a condition for the uniqueness of the solution to this game is given. Finally, in Section IV we conclude this work.

II. PROBLEM STATEMENT

A. Wireless context

In a wireless network depicted by Fig. 1 with a set of transmitters 𝒩 = {1, . . . , 𝑛} and one receiver, the received signal is As we consider that transmitters are concerned about their transmission rate but also about the energy they spend to reach this rate, we use energy-efficient utility as introduced by Mandayam and Goodman [START_REF] Goodman | Power control for wireless data[END_REF] : for each transmitter, the instantaneous utility is

𝑦(𝑡) = 𝑛 ∑ 𝑖=1 ℎ 𝑖 (𝑡)𝑎 𝑖 (𝑡) + 𝑧(𝑡) (1)
𝑢 𝑖 (𝑝(𝑡), ℎ(𝑡)) = 𝑅𝑓 (𝛾 𝑖 (𝑝(𝑡), ℎ(𝑡))) 𝑝 𝑖 (𝑡) (2)
where 𝑅 in bits/s is the transmitting rate of transmitter 𝑖 (as we do not use this rate as a control in our work, we consider that it is constant for all the transmitters), 𝛾 𝑖 is the 𝑆𝐼𝑁 𝑅 of transmitter 𝑖, 𝑝(𝑡) = (𝑝 1 (𝑡), . . . , 𝑝 𝑛 (𝑡)) and ℎ(𝑡) = (ℎ 1 (𝑡), . . . , ℎ 𝑛 (𝑡)). 𝑓 is an efficiency function which represents the transmission success rate at the receiver. It takes its values in [0, 1] and depends on the 𝑆𝐼𝑁 𝑅 of transmitter 𝑖. More details about 𝑓 can be found in [START_REF] Goodman | Power control for wireless data[END_REF]. The 𝑆𝐼𝑁 𝑅 writes

𝛾 𝑖 (𝑝(𝑡), ℎ(𝑡)) = 𝑝 𝑖 (𝑡)|ℎ 𝑖 (𝑡)| 2 ∑ 𝑛 𝑗∕ =𝑖 𝑝 𝑗 (𝑡)|ℎ 𝑗 (𝑡)| 2 + 𝜎 2 , ( 3
)
with |ℎ 𝑖 (𝑡)| 2 the channel gain between transmitter 𝑖 and the receiver.

B. Evolution laws of the system

Depending on time, two parameters of the considered model vary. These are the energy left at transmitter and the channel coefficients between the transmitter and the receiver.

First, we consider that the manufacturer of the mobile transmitter wants its device to be able to transmit during a finite horizon which represents the desired battery life. We denote 𝐸 0 the initial available energy for each transmitter. The dynamics of 𝐸 𝑖 (𝑡), the energy left for transmitter 𝑖 at time 𝑡, is directly linked to the transmitting power through the following deterministic law d𝐸 𝑖 (𝑡) = -𝑝 𝑖 (𝑡)d𝑡.

(4)

Secondly, we consider that for each transmitter the dynamics of its channel coefficients is a Wiener process, meaning that

∀𝑖 ∈ 𝒩 dℎ 𝑖 (𝑡) = 𝜂d𝕎 𝑖 (𝑡) (5)
where ∀𝑖 ∈ 𝒩 , 𝕎 𝑖 (𝑡) are mutually independent Wiener processes of dimension 2 and 𝜂 is the variance of ℎ 𝑖 (𝜂 < +∞).

Contrary to the evolution of the energy left at the transmitter, the channel coefficients evolve according to a stochastic law.

C. A stochastic differential game

It is assumed that each transmitter wants to maximize its utility during a finite horizon 𝑇 → 𝑇 ′ while taking into account the dynamics of the system, then the problem can be written ∀𝑖 ∈ 𝒩

𝑣 𝑖 (𝑇 ) = sup 𝑝𝑖(𝑇 →𝑇 ′ ) 𝔼 [∫ 𝑇 ′ 𝑇 𝑢 𝑖 (𝑝(𝑡), ℎ(𝑡))d𝑡 + 𝑞(𝐸(𝑇 ′ ), ℎ(𝑇 ′ )) ] dℎ 𝑖 (𝑡) = 𝜂d𝕎 𝑖 (𝑡) d𝐸 𝑖 (𝑡) = -𝑝 𝑖 (𝑡)d𝑡 (6)
where 𝑣 𝑖 (𝑇 ) is the Bellman function, the expectation of the continuous sum of utility for the optimal control path, 𝐸(𝑡) = (𝐸 1 (𝑡), . . . , 𝐸 𝑛 (𝑡)), and 𝑞(𝐸(𝑇 ′ ), ℎ(𝑇 ′ )) is the instantaneous utility value for the final state.

We denote 𝑋(𝑡) = (𝐸(𝑡), ℎ(𝑡)) T the state of the system at time 𝑡. Then d𝑋(𝑡) = (-𝑝(𝑡)d𝑡, 𝜂d𝕎(𝑡)) T , [START_REF] Richter | Energy efficiency aspects of base station deployment strategies for cellular networks[END_REF] with 𝕎(𝑡) a 2𝑛-dimension Wiener process. ( 6) can be rewritten

𝑣 𝑖 (𝑇, 𝑋) = sup 𝑝𝑖(𝑇 →𝑇 ′ ) 𝔼 [∫ 𝑇 ′ 𝑇 𝑢 𝑖 (𝑋(𝑡), 𝑝(𝑡))d𝑡 + 𝑞(𝑋(𝑇 ′ ))
] d𝑋(𝑡) = (-𝑝(𝑡)d𝑡, 𝜂𝕎 𝑡 ) T (8) If 𝑝 𝑖 (𝑡) is now considered as a feedback control 𝑝 𝑖 (𝑡) = 𝑝 𝑖 (𝑡, 𝑋(𝑡)), [START_REF] Treust | A repeated game formulation of energyefficient decentralized power control[END_REF] we are exactly in the context of a stochastic differential game.

D. Existence of a Nash equilibrium to the stochastic differential game

Definition 1 (Nash equilibrium of the stochastic differential game). A power profile

𝑝 * (𝑡, 𝑋(𝑡)) = (
) . ( 11
)
According to [START_REF] Bressan | Noncooperative differential games. a tutorial[END_REF], a sufficient condition for the existence of a Nash equilibrium for the stochastic differential game is the existence of a solution to the Hamilton-Jacobi-Bellman-Fleming [START_REF] Fleming | Controlled Markov processes and viscosity solutions, ser. Applications of mathematics[END_REF]

) is smooth (see [START_REF] Evans | Partial differential equations[END_REF] for more details). And with a similar reasoning as in [START_REF] Mériaux | Long-term energy constraints and power control in cognitive radio networks[END_REF], we can show that finding optimal power profiles ) 2 [START_REF] Evans | Partial differential equations[END_REF] Note that we consider that ∂ 𝐸𝑖 𝑉 𝑖 (𝑡, 𝑋(𝑡)) ≥ 0, otherwise the optimal power 𝑝 * 𝑖 (𝑡) → ∞. In other words, we consider that the more energy we have in our battery, the better the payoff can be.

𝑝 * (𝑇 → 𝑇 ′ ) = (𝑝 * 1 (𝑇 → 𝑇 ′ ), . . . , 𝑝 * 𝑛 (𝑇 → 𝑇 ′ )) (14) such that ∀𝑖 ∈ 𝒩 , 𝑝 * 𝑖 (𝑇 → 𝑇 ′ ) ∈ arg max 𝑝𝑖(𝑇 →𝑇 ′ ) [ 𝑢 𝑖 (𝑋(𝑡), 𝑝(𝑡, 𝑋(𝑡))) -𝑝 𝑖 (𝑡, 𝑋(𝑡))∂ 𝐸𝑖 𝑣 𝑖 (𝑡, 𝑋(𝑡)) ] (15
The existence of a non-zero solution depends on the term

𝛽 𝑖 = ∂ 𝐸𝑖 𝑣 𝑖 (𝑡, 𝑋(𝑡)) 𝑅 ( 𝜎 2 + ∑ 𝑛 𝑗∕ =𝑖 |ℎ 𝑗 | 2 (𝑡)𝑝 * 𝑗 (𝑡) |ℎ 𝑖 | 2 (𝑡) ) 2 . ( 17
)
Heuristically, we can see that there exists a threshold 𝛽 max such that if 𝛽 𝑖 < 𝛽 max , there exists a unique global maximizer 𝛾 * different from 0 and if 𝛽 𝑖 ≥ 𝛽 max , 0 is the global maximizer. It is interesting to note that 𝛽 𝑖 being proportional to the interference of transmitter 𝑖, we can state that when the interference conditions of transmitter 𝑖 are favorable, transmitter 𝑖 should transmit whereas when the conditions are bad, it should not waste transmitting power. This behavior is illustrated on Fig. 2, where the considered efficiency function is

𝑓 (𝛾 𝑖 (𝑡)) = { 𝑒 -𝑎 𝛾 𝑖 (𝑡) if 𝛾 𝑖 (𝑡) > 0, 0 if 𝛾 𝑖 (𝑡) = 0. ( 18
)
an efficiency function introduced by Belmega et al. in [START_REF] Belmega | An information-theoretic look at mimo energy-efficient communications[END_REF]. In this simulation 𝑎 = 1. In order to use the implicit function theorem, we define

𝑔 : [0, 𝛽 max [×ℝ + → ℝ (𝛽, 𝛾) → 𝑓 ′ (𝛾)𝛾 -𝑓 (𝛾) -𝛽𝛾 2 . ( 19
)
𝑔 is 𝐶 ∞ , then if 𝑔(𝛽 0 , 𝛾 0 ) = 0, there exists 𝜑 :

ℝ → ℝ such that 𝛾 0 = 𝜑(𝛽 0 ). 𝜑 is 𝐶 ∞ and ∂𝜑 ∂𝛽 (𝛽 0 ) = - ∂𝑔(𝛽 0 ,𝛾 0 ) ∂𝛽 ∂𝑔(𝛽 0 ,𝛾 0 ) ∂𝛾 (20)

III. CONVERGENCE OF THE STOCHASTIC DIFFERENTIAL POWER CONTROL GAME TO A MEAN-FIELD GAME

The previous system of equations is hard to solve because for each transmitter, the associated partial differential equation depends on all the channel coefficients and all the power profiles of the other transmitters. Of course, if the number of transmitters in the system increases greatly, it is true that the complexity of the resolution increases as well. But an interesting fact is that if the number of transmitters is large enough, then for one single transmitter point of view, it becomes equivalent to consider all the other transmitters as a continuum. Therefore only the distribution of the other transmitters states is needed for one transmitter to take into account the other transmitters, which highly simplifies the formulation of the problem. This is what is developed in the present section.

Naturally, in a MAC network, the interaction between the different transmitters is expressed in the interference term. If we consider that CDMA is used in the network, then the interference seen by the receiver is

𝐼 𝑖 (𝑡) = 1 𝑛 -1 𝑛 ∑ 𝑗∕ =𝑖 𝑝 𝑗 (𝑡)|ℎ 𝑗 (𝑡)| 2 . ( 21
)
We consider homogeneous admissible control in own state feedback form ∀𝑖 ∈ 𝒩

𝑝 𝑖 (𝑡) = 𝛼(𝑡, 𝑠 𝑖 (𝑡)), (22)
with 𝑠 𝑖 (𝑡) = (ℎ 𝑖 (𝑡), 𝐸 𝑖 (𝑡)) T the own state of transmitter 𝑖and 𝔼[𝛼(𝑡, 𝑠 𝑖 (𝑡)) 2 ] < +∞. Then

𝐼 𝑖 (𝑡) = 1 𝑛 -1 𝑛 𝑛 𝑛 ∑ 𝑗∕ =𝑖 𝛼(𝑡, 𝑠 𝑗 (𝑡))|ℎ 𝑗 (𝑡)| 2 = 𝑛 𝑛 -1 1 𝑛 [ 𝑛 ∑ 𝑗=1 𝛼(𝑡, 𝑠 𝑗 (𝑡))|ℎ 𝑗 (𝑡)| 2 -𝛼(𝑡, 𝑠 𝑖 (𝑡))|ℎ 𝑖 (𝑡)| 2 ] = 𝑛 𝑛 -1 ∫ |ℎ| 2 𝛼(𝑡, 𝑠)𝑀 𝑛 𝑡 (d𝑠) - 𝛼(𝑡, 𝑠 𝑖 (𝑡))|ℎ 𝑖 (𝑡)| 2 𝑛 -1 = 𝑛 𝑛 -1 𝐴 𝑛 𝑡 - 1 𝑛 -1 𝐵 𝑖 𝑡 .
(23) with

𝑀 𝑛 𝑡 = 1 𝑛 𝑛 ∑ 𝑗=1 𝛿 𝑠𝑗 (𝑡) , ( 24
)
𝐴 𝑛 𝑡 = ∫ |ℎ| 2 𝛼(𝑡, 𝑠)𝑀 𝑛 𝑡 (d𝑠), (25)
𝐵 𝑖 𝑡 = 𝛼(𝑡, 𝑠 𝑖 (𝑡))|ℎ 𝑖 (𝑡)| 2 . ( 26
)
If the number of transmitters becomes very large (𝑛 → ∞), we can consider that we have a continuum of transmitters. The convergence of the interference term when 𝑛 → ∞ needs to be proven. Using admissible control, 𝔼[𝐵 𝑖 𝑡 ] < ∞, then

lim 𝑛→∞ 𝐵 𝑖 𝑡 𝑛 -1 = 0. (27)
As lim 𝑛→∞ 𝑛 𝑛-1 = 1, to prove 𝐼 𝑖 (𝑡) converges weakly, it suffices to prove 𝐴 𝑛 𝑡 converge weakly. A sufficient condition is the weak convergence of the process 𝑀 𝑛 𝑡 . As stated by Kotelenez and Kurtz in [START_REF] Kotelenez | Macroscopic limits for stochastic partial differential equations of mckean-vlasov type[END_REF], if the states and the controls are almost surely bounded and the (𝑠 𝑗 (0)) are exchangeable, then there exists a distribution 𝑚 𝑡 such that

𝑚 𝑡 = lim 𝑛→∞ 𝑀 𝑛 𝑡 . ( 28
where 𝑚 * 𝑡 is the mean-field optimal trajectory, 𝑚 * 0 being assumed to be known and d𝑠(𝑡) = (-𝑝(𝑡)d𝑡, 𝜂d𝕎(𝑡)) T , (

A solution of the mean-field response problem is a solution of

{ -∂ 𝑡 v𝑡 = H(𝑠(𝑡), ∂ 𝐸 v𝑡 , 𝑚 𝑡 ) + 𝜂 2 2 ∂ 2 ℎℎ v𝑡 ∂ 𝑡 𝑚 𝑡 + ∂ 𝐸 (𝑚 𝑡 ∂ 𝑢 H(𝑠(𝑡), ∂ 𝐸 v𝑡 , 𝑚 𝑡 )) = 𝜂 2 2 ∂ 2 ℎℎ 𝑚 𝑡 ( 35
)
with v𝑇 = 𝑞(𝑠(𝑇 )) and 𝑚 0 known and

H(𝑠, 𝑢, 𝑚) = sup 𝑝 {r(𝑠, 𝑝, 𝑚) + ⟨𝑝, -𝑢⟩} (36)
As for the stochastic differential game case, the first equation is a Hamilton-Jacobi-Bellman-Flemming equation. But it is now coupled with a Fokker-Planck-Kolmogorov equation. The former one is a backward equation whereas the latter one is a forward equation.

Similarly to section II-D, expressing H(𝑠(𝑡), ∂ 𝐸 v𝑡 , 𝑚 𝑡 ) requires to solve

𝛾𝑓 ′ (γ) -𝑓 (γ) = βγ 2 (37) with β = ∂ 𝐸 v𝑡 𝑅 (𝜎 2 + Î𝑖 (𝑡, 𝑚 𝑡 )) 2 |ℎ 𝑖 | 4 (38)
If there exists a solution different from zero, we denote γ * (𝑠(𝑡), ∂ 𝐸 v𝑡 , 𝑚 𝑡 ) this solution. With the parameters previously defined, we can derive a sufficient condition for uniqueness of the solution to the system of coupled equations (35). The proof is not given here.

Proposition 1 (Uniqueness of a solution). A sufficient condition for a solution of the solution to the mean-field game to be unique is ∀𝑠, ∀∂ 𝐸 v, ∀𝑚

(𝑓 ′′ (γ * (𝑠, ∂ 𝐸 v, 𝑚) -2 β)𝑓 ′ (γ * (𝑠, ∂ 𝐸 v, 𝑚)) + 𝑚γ * (𝑠, ∂ 𝐸 v, 𝑚) 2 𝛽 2 > 0 (39)

IV. CONCLUSION AND PERSPECTIVE

In a wireless model where the energy left for each transmitters evolves according to the power spent to transmit and the channel coefficients of these same transmitters evolve in a stochastic manner, we have shown that the problem of each transmitter maximizing the expectation of an energyefficient utility during a given time is equivalent to a stochastic differential game. The existence of a Nash equilibrium for this game has been proven. But as the resolution of the associated system of partial differential equations is hard, especially when the number of transmitter is high, we show that the stochastic differential game converges to a mean-field game which equilibrium is the solution of a system of two partial differential equations: a backward Hamilton-Jacob-Bellman equation and a forward Fokker-Planck-Kolmogorov equation. From a game theory point of view, this model highly simplifies the complexity of the interactions between a large number of players. A condition of uniqueness for the mean-field Nash equilibrium is given.

Of course, our main objective now is to characterize the mean-field equilibrium. This can be done numerically by implementing solutions as described in the work of Achdou [START_REF] Achdou | Mean field games: Numerical methods[END_REF]. Then the efficiency of this solution could be compared to equilibria obtained as solutions of simpler energy-efficient power control models.

  ) requires to solve ∀𝑖 ∈ 𝒩 , ∀𝑡 ∈ [𝑇, 𝑇 ′ ] 𝑓 ′ (𝛾𝑖(𝑡))𝛾𝑖(𝑡)-𝑓 (𝛾𝑖(𝑡))=𝛾𝑖(𝑡) 2 ∂ 𝐸 𝑖 𝑣 𝑖 (𝑡,𝑋(𝑡) 𝑅 ( 𝜎 2 + ∑ 𝑛 𝑗∕ =𝑖 |ℎ 𝑗 | 2 (𝑡)𝑝 * 𝑗 (𝑡) |ℎ 𝑖 | 2 (𝑡)

Figure 2 .

 2 Figure 2. Instantaneous global maximizer depending on 𝛽.

  with ℎ 𝑖 (𝑡) ∈ ℂ the channel coefficient between transmitter 𝑖 and the receiver at time 𝑡, 𝑎 𝑖 (𝑡) the symbols sequence sent by

				y (t)
	a 1 (t)	h 1	2 a (t) h 2	+ z(t) ...	h (t) n-1 n-1 a h	n	a	(t) n
			Figure 1. System model.
	transmitter 𝑖 during time-slot 𝑡 and 𝑧(𝑡) is a Gaussian noise
	with variance 𝜎 2 . We denote 𝑝 𝑖 (𝑡) = |𝑎 𝑖 (𝑡)| 2 the transmitting
	power of transmitter 𝑖 during time-slot 𝑡.

  equation for each transmitter 0 = sup 𝑝𝑖(𝑇 →𝑇 ′ ) [ 𝑢 𝑖 (𝑋(𝑡), 𝑝(𝑡, 𝑋(𝑡))) -𝑝 𝑖 (𝑡, 𝑋(𝑡))∂ 𝐸𝑖 𝑣 𝑖 (𝑡, 𝑋(𝑡))

					]
	+∂ 𝑡 𝑣 𝑖 (𝑡, 𝑋(𝑡)) +	𝜂 2 2	∂ 2 ℎℎ 𝑣 𝑖 (𝑡, 𝑋(𝑡)).	(12)
	with ∂ 𝑦 𝐹 and ∂ 2 𝑦𝑦 𝐹 respectively being the first order and the
	second order partial derivative of function 𝐹 with regard to 𝑦
			{	∂ 𝑦 𝐹 = ∂𝐹 ∂𝑦 ∂ 2 𝑦𝑦 𝐹 = ∂ 2 𝐹 ∂𝑦 2
	However there exists a solution if the function
	𝐻(𝑋(𝑡), 𝑝 -𝑖 (𝑡, 𝑋(𝑡)), ∂ 𝐸𝑖 𝑣 𝑖 (𝑡, 𝑋(𝑡))) = [	]
	sup 𝑝𝑖(𝑇 →𝑇 ′ )	𝑢 𝑖 (𝑋(𝑡), 𝑝(𝑡, 𝑋(𝑡))) -𝑝 𝑖 (𝑡, 𝑋(𝑡))∂ 𝐸𝑖 𝑣 𝑖 (𝑡, 𝑋(𝑡))


Rachid El-Azouzi

Habib Sidi

Francesco De Pellegrini

Yezekael Hayel

Markov Decision Evolutionary Game for Energy Management in Delay Tolerant Networks Invited paper

In this paper, we apply the concepts of Markov decision evolutionary games to non-cooperative forwarding control of Delay Tolerant Networks (DTN). Specifically, we rely on the design of mechanisms at the source node to study forwarding probability of the message in a DTN using the twohop routing. We study the forwarding probability as a function of the competition within a large population of mobiles which need occasionally to make some action. In particular, for each message generated by a source, each mobile may take a decision that concerns the strategy by which the mobile participates to the relaying of the message from source to destination. A mobile that participates receives a unit of reward if it is the first to deliver a copy of the packet to the destination. The action taken by a mobile determine not only the immediate reward but also the transition probability to its next battery energy state. We characterize the Evolutionary Stable Strategies (ESS) for these games and propose a method to compute them. We also propose a mechanism design at the source in order to maximize the message delivery probability to the destination, given the equilibrium behavior (called Evolutionary Stable Strategy -ESS).

I. INTRODUCTION

Delay tolerant networks (DTNs) emerged recently as a novel communication paradigm. Throughout this work, we focus on a specific class of DTNs where persistent connectivity cannot be guaranteed due to limited coverage and high mobility [START_REF] Zhao | Controlling the Mobility of Multiple Data Transport Ferries in a Delay-Tolerant Network[END_REF]. For such networks, forwarding strategies have been designed purposely to solve the problem of intermittent connectivity: a message is delivered to the intended destination leveraging the motion of a subset of nodes, i.e., relays, which carry copies of the message stored in their local memory. This is the so called carry-store-and-forward routing. The DTN paradigm has been validated by several experimental deployments [START_REF] Burgess | MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks[END_REF], [START_REF] Demmer | Implementing Delay Tolerant Networking[END_REF].

In order to reach the destination, a straightforward strategy is to disseminate multiple copies of the message in the network. This approach is known as epidemic forwarding [START_REF] Vahdat | Epidemic routing for partially connected adhoc networks[END_REF], in analogy to spread of infectious diseases. The aim in doing so is to let some of such message copies reach the destination with high probability within some target deadline [START_REF] Spyropoulos | Efficient routing in intermittently connected mobile networks: the multi-copy case[END_REF], [START_REF] Altman | Optimal monotone forwarding policies in delay tolerant mobile Ad-Hoc networks[END_REF]. We confine our analysis to the two hop routing protocol. In fact, it has two major advantages: first, compared to epidemic routing, it performs natively a better trade-off between the number of released copies and the delivery probability [START_REF] Altman | Optimal monotone forwarding policies in delay tolerant mobile Ad-Hoc networks[END_REF]. Second, forwarding control can be implemented on board of the source node. Under two hop routing, the source transmits a message copy to mobiles devices it encounters. Relays, conversely, forward to the destination only.

In this context, the higher the number of relays joining the forwarding process, the higher the success probability. However, battery lifetime of mobile devices may deplete due to continuous beaconing operations [START_REF] Altman | Optimal Activation and Transmission Control in Delay Tolerant Networks[END_REF], which may be a critical factor discouraging the usage of mobile devices as relays for DTN-based applications. A solution is to design reward-based forwarding mechanisms where the probability of forwarding becomes function of the competition within a population of mobiles: a relay receives a unit of reward if it is the first to deliver the message to the destination. For each message generated by the source, a relay may choose two different actions that affect message relaying: full activation or partial activation, i.e., being active for a shorter time period and then go back to low power mode, thus saving batteries.

This paper extends a similar framework studied by El-Azouzi et al. [START_REF] El-Azouzi | Evolutionary forwarding games in Delay Tolerant Networks[END_REF]. The novelty here is that the strategy of a mobile relay determines not only the immediate reward but also the transition probability to its next battery energy state. The problem is formulated as a Markov Decision Evolutionary Game (MDEG), where each relay wishes to maximize the expected utility. We characterize the Evolutionary Stable Strategies (ESS) for these games and show a method to compute them. Once determined the possible equilibria for the game, the optimal forwarding control at the source node that maximizes the forwarding probability has been derived. We show that the success probability is not always increasing with the number of message copies, and may well decrease under some conditions, which is adding an intriguing novel facet to the control of forwarding in DTNs.

II. BASIC NOTIONS ON EVOLUTIONARY GAMES

We consider the standard setting of evolutionary games :

• There is one population of users. The number of users in the population is large. • We assume that there are finitely many pure strategies or actions. Each member of the population chooses from the same set of strategies A = {1, 2, . . . , I}. • Let M := {(y 1 , . . . , y I ) | y j ≥ 0, I j=1 y j = 1} be the set of probability distributions over the I pure actions. I can be interpreted as the set of mixed strategies. It is also interpreted as the set of distributions of strategies among the population, where y j represents the proportion of users choosing the strategy j.

• The number of users interfering with a given randomly selected user is a random variable K in the set {0, 1, . . .}. • A player does not know how many players would interact with it. • The payoff function of all players depends of the player's own behavior and the behavior of the other players. The expected payoff of a user playing strategy j when the state of the population is y, is given by U av (j, y) = k≥0 P(K = k)U (j, k, y), where U (j, k, y) is the payoff of a user playing strategy j when the state of the population is y and given that the number of users interfering with a given randomly selected user is k. Hence the average payoff of a population in state y is given by F (y, y) = I i=1 y j U av (j, y).

• The game is played many times and there are many local interactions at the same time Evolutionary Stable Strategy Suppose that, initially, the population profile is y ∈ M. Now suppose that a small group of mutants enters the population playing according to a different profile mut ∈ M . If we call ǫ ∈ (0, 1) the size of the subpopulation of mutants after normalization, then the population profile after mutation will be ǫ mut + (1ǫ)y. After mutation, the average payoff of non-mutants will be given by F (y, ǫmut + (1ǫ)y) where F (x, y) := N j=1 x j U av (j, y). Note that U av need not to be linear in the second variable. Analogously, the average payoff of a mutant is F (mut, ǫmut+ (1ǫ)x).

Definition 1: A strategy y * ∈ M is an ESS if for any mut = y * , there exists some ǫ mut ∈ (0, 1), which may depend on mut, such that for all ǫ ∈ (0, ǫ mut ) one has

F (y * , ǫmut + (1 -ǫ)y * ) > F (mut, ǫmut + (1 -ǫ)y * ) (1)
which can be rewritten as N j=1 (y * jmut j )U av (j, ǫmut + (1ǫ)y * ) > 0. That is, y * is ESS if, after mutation, nonmutants are more successful than mutants. In other words, mutants cannot invade the population and will eventually get extinct.

III. MODEL

Consider a network with several sources s i , destination d i and a large number of mobiles in the system. Each mobile is equipped with some form of proximity wireless communications. We assume that the message that is transmitted by a source, is relevant during some time τ . The network is assumed to be sparse, so that, at any time instant, nodes are isolated with high probability. Communication opportunities arise whenever, due to mobility patterns, two nodes get within mutual communication range. We refer to such events as "contacts". The time between subsequent contacts of a node with the source s i or the destination d i is assumed to follow an exponential distribution with parameter λ > 0. The validity of this model for synthetic mobility models has been discussed in [START_REF] Al-Hanbali | Performance of Ad Hoc Networks with Two-Hop Relay Routing and Limited Packet Lifetime[END_REF].

The message contains a time stamp reporting its generation time, so that it can be deleted at all nodes when it becomes irrelevant. We do not assume any feedback that allows the source or other mobiles to know whether the message has been successfully delivered to the destination during time slot τ . We consider the two hop routing scheme [START_REF] Al-Hanbali | Performance of Ad Hoc Networks with Two-Hop Relay Routing and Limited Packet Lifetime[END_REF] in which a mobile that receives a copy of the packet from the source can only forward it to the destination. We use evolutionary games to study the competition individual mobiles in a routing game in DTN.

We apply evolutionary games to non-cooperative 'live time' selection in delay tolerant networks.Specifically, we assume that each relay node can choose two different live times for the message: τ , i.e. full activation and τ ′ i.e., partial activation, where τ ′ < τ . At each slot, a mobile has to take a decision to be fully active or partially active, based on his battery energy sate. To simplify, we assume that the state can take three values : {F, A, E} for Full, Almost empty or Empty. At state F only action τ is available, and at E participation on forwarding message is not possible any more. The life time of mobile is defined as the number of slots during which its battery is nonempty.

Local Interaction : Without loss of generality, we assume that in each local interaction, there is a source-destination pair in which the source has packet generated at each time t i+1 -t i = nτ where i = 1, 2.. and t 0 = 0. Let N be the number of mobiles (possibly random) in an area which is assumed fixed during time slot. We denote by y (resp. 1y) the fraction of mobiles sharing the strategy τ (resp. τ ′ ). Consider an active mobile in a local interaction with source s i , destination d i and N opponents.

Some notation

We introduce the following notations:

• P i (a) is the probability of remaining at energy level i when using action a. Since at state F only action τ is available, we write P F instead of P F (τ ) • M 2 := {(y, 1y)} be the set of probability distributions over the 2 pure actions τ and τ ′ . M can be interpreted as the set of mixed strategies. It is also interpreted as the set of distributions of strategies among the population, where y (resp. 1-y) represents the proportion of mobiles choosing the strategy τ (resp. τ ′ ).

The probability that the tagged mobile relays the copy of the packet to the destination within live time τ is given by 1 -Q τ where Q τ is given by Q τ = (1 + λτ )e -λτ and the probability that it relays the copy of the message if it chooses live time τ ′ is given by is given by 1 -Q τ ′ where Q τ ′ = (1 + λτ ′ )e -λτ ′ . Let P succ (τ, N, y) (resp. P succ (τ ′ , N, y)) be the probability that the tagged mobile receive the unit reward, if it chooses live time τ (resp. τ ′ ). Now

P succ (τ ′ , N, y) = (1 -Q τ ′ ) N k=1 C N -1 k-1 (1-Q τ ′ ) k-1 (1-(1-Q τ ′ )) N -k k = 1-(Q τ ′ ) N N
The gain obtained by a mobile using live time τ ′ is given by

U (τ ′ , y) = ∞ N =1 P (K = N )P succ (τ ′ , N, y)
Now the probability that a mobile receives the unit award, if it chooses live time τ , is given by P succ (τ, N, y)

= P succ (τ ′ , N, y) + (Q τ ′ ) N β N k=1 C N -1 k-1 β k-1 y k-1 (1 -yβ) N -k k = P succ (τ ′ , N, y) + (Q τ ′ ) N 1 -(1 -βy) N N y where β = 1 -Qτ Q τ ′ .
The utility for a mobile using live time τ

U (τ, y) = ∞ N =1 P (K = N )P succ (τ, N, y).
A general policy u is a sequence u = (u 1 , u 2 , ...) where u i is the strategy used at time t i if the state is A. We shall use a pure stationary policy in which there exist two pure stationary policies ; the one always choose τ and the one that always choose τ ′ .

A. Fitness

An active mobile during [t i , t i+1 ], will receive a unit of reward r if it is the first to deliver a copy of the packet to the destination. Assume that y is fixed and does not change in time (Note that assuming that y is fixed in time does not mean that the actions of each player are fixed in time. It only reflects a situation in which the system attains a stationary regime due to the averaging over a very large population, and the fact that all mobiles choose an action in a given individual state using the same probability low). Then the expected optimal fitness of an individual starting at a given initial state can be computed using the standard theory of total-cost dynamic programming, that states in particular that there exist optimal stationary policy (i.e. a policy for which at any time that the individual is at state A, the action u i of choosing T is the same). We shall therefore restrict to stationary policies unless stated otherwise.

Let V τ (i, y) (respectively V τ ′ (i, y)) to be the total expected fitness of a user given that it is in state i, that it uses action τ and given the parameter y.

We proceed by computing the individual's expected total utility and remaining lifetime that correspond to a given initial state and a stationary policy. We have V τ (A, y) = U (τ, y) + P A (τ )V τ (A, y) which gives that

V τ (A, y) = U (τ, y) 1 -P A (τ )
The total expected utility for a mobile starting from state F and using strategy τ , is giving by

V τ (F, y) = U (τ, y) + P F V τ (F, y) + (1 -P F )V τ (A, y) Thus V τ (F, y) = U (τ, y)( 1 1 -P F + 1 1 -P A (τ ) ) (2)
Similarly, the total expected utility for a mobile starting from state F and using strategy τ ′ , is giving by

V τ ′ (F, y) = U (τ, y) 1 -P F + U (τ ′ , y) 1 -P A (τ ′ ) )
Our game is different and has a more complex structure than a standard evolutionary game. In particular, the fitness that is maximized is not the outcome of a single interaction but of the sum of fitnesses obtained during all the opportunities in the mobile's lifetime. Let H be the function defined as

H : y ∈ (0, 1) → V τ (F, y) -V τ ′ (F, y) = U (τ,y) 1-PA(τ ) -U (τ ′ ,y) 1-PA(τ ′ ) ) = U (τ,y)(1-PA(τ ′ ))-U (τ ′ ,y)(1-PA(τ )) (1-PA(τ ′ ))(1-PA(τ )) = H(y) (1-PA(τ ′ ))(1-PA(τ )) thus H(y) = ∞ N =1 P (K=N ) (Q τ ′ ) N 1-(1-βy) N N y (1-PA(τ ′ ))- 1-(Q τ ′ ) N N (PA(τ ′ )-PA(τ )) (1-PA(τ ′ ))(1-PA(τ ))

B. Existence and Uniqueness of ESS

In this section, we are now looking at the existence and uniqueness of the ESS Proposition 1: (1) The strategy τ dominates the strategy τ ′ if and only if

P A (τ ′ ) -P A (τ ) ≤ ∞ N =1 P (K = N ) Q ′N τ (1 -β) N (1 -P A (τ ′ )) + 1 -P A (τ )
A 1 (2 The strategy τ ′ dominates the strategy τ if and only if

P A (τ ′ ) -P A (τ ) ≥ ∞ N =1 P (K = N )Q N τ ′ N β(1 - P A (τ ′ )) + P A (τ ′ ) -P A (τ ′ ) A 0 (3) If P A (τ ′ ) -P A (τ ) > A 1 and P A (τ ′ ) -P A (τ ) < A 0 ,
then there exists an unique ESS y * which is given by y * = H-1 (0) Proof (1) The strategy τ dominates the strategy τ ′ if and only if

V τ (F, y) ≥ V τ ′ (F, y) for all y ∈ [0, 1]. Since H is decreasing function and H(1) = A 1 -(P A (τ ′ ) - P A (τ )) ≥ 0, thus H(y) ≥ 0 for all y ∈ (0, 1). Then V τ (F, y) -V τ ′ (F, y) = H(y) = H(y) (1-PA(τ ′ ))(1-PA(τ )) ≥ 0 for all y T ∈ [0, 1]
. This completes the proof for (1) (2) The strategy τ ′ dominates the strategy τ if and only if

V τ ′ (F, y) ≥ V τ (F, y) for all y ∈ [0, 1]. Since the func- tion H is decreasing function and H(0) = A 0 -(P A (τ ′ )- P A (τ )) ≤ 0, thus H(y) ≤ 0 for all y ∈ (0, 1). Then V τ ′ (F, y) -V τ (F, y) = H(y) = H(y) (1-PA(τ ′ ))(1-PA(τ )) ≤ 0 for all β ∈ [0, (1 -Q τ ]. This completes the proof for (2) (3) A strictly mixed equilibrium y * is characterized V τ (F, y * ) = V τ ′ (F, y * ).
The function H is continuous and strictly decreasing monotone on (0, 1) with H(0) > 0 and H(1) < 0. Then the equation H(y) = 0 has a unique solution in the interval (0, 1). This completes the proof.

C. Poisson distribution

We consider that nodes are distributed over a plan following a Poisson distribution with density γ. The probability that there is N nodes in local interaction is given by the following distribution :

P(K = k) = γ k-1 (k-1)! e -γ , k ≥ 1.
Considering those node distributions and from previous theorems, the unique ESS y * is unique solution of the following equation:

e γQ τ ′ -e Q τ ′ (1-βy * )γ y * = (e γ -e Q τ ′ γ ) P A (τ ′ ) -P A (τ ) 1 -P A (τ )
Thus, the equilibrium is given by

y * = LambertW (-αβe -α(βe α -c) c c )c + αβe α cαβ where α = Q τ ′ γ and c = (e γ -e Q τ ′ γ ) PA(τ ′ )-PA(τ ) 1-PA(τ )

D. Dirac distribution

We consider that at a given time there is a fixed number of nodes in a local interaction. In this part, we suppose that the population of nodes is composed with many local interaction between n nodes where N > 2. The unique ESS y * of this game is the unique solution of the following equation:

1 -(1 -βy * ) N y = 1 -(Q τ ′ ) N (Q τ ′ ) N
Since this polynome is of order N we can have an explicit expression only for N ≤ 5 but we show some properties of the stable equilibrium by numerical computations in the next section.

For example:

N = 2 =⇒ y * = (1 -(Q τ ′ ) 2 )G -2Q τ ′ (Q τ ′ -Q τ ) (Q τ ′ -Q τ ) 2 with G = PA(τ ′ )-PA(τ ) 1-PA(τ )
. One can easily show that y * > 1 thus y * = 1.

For N = 3, y * is the solution of the equation

y 2 + 3 β y -k = 0 with k = 3 β 2 -1-(Q τ ′ ) 3 β 3 (Q τ ′ ) 3 G. δ = 9 β 2 + 4k with k = 3(Q τ ′ ) 2 [Q τ ′ -Q τ ] 2 + (Q τ ′ ) 4 -[Q τ ′ -Q τ ] β 2 (Q τ ′ ) 2 [Q τ ′ -Q τ ] 2 > 0
The realizable solution is y * =

-3 β + √ δ 2
. In this case the solution y * is positive when the conditions from proposition 1 are satisfied.

IV. MECHANISM DESIGN

In sight of the characterization of the ESS, we are interested in controlling the system in order to optimize for the energy consumption and the delivery probability. Let us assume that the source node controls the forwarding of message copies: a copy of the message is relayed with constant probability u upon meeting a node with no message during a local interaction, i.e., using a static forwarding policy [START_REF] Altman | Optimal monotone forwarding policies in delay tolerant mobile Ad-Hoc networks[END_REF]. The main quantity of interest is denoted P s and it is the success probability of a message at a local interaction; under the same assumptions of linearity in [START_REF] Altman | Optimal monotone forwarding policies in delay tolerant mobile Ad-Hoc networks[END_REF], the average energy expenditure at the source node is E = εΨ, where ε > 0 is the source energy expenditure per relayed message copy and Ψ is the corresponding expected number of copies released.

A. Activation control

Let us consider first the activation control. Due to the forwarding control, the probability that the tagged mobile relays the copy of the packet to the destination within live time τ is given by 1-Q u τ where Q u τ is given by Q u τ = e -λuτ -ue -λτ

1-u

and the probability that it relays the copy of the message if it chooses live time τ ′ is given by is given by

1 -Q u τ ′ where Q u τ ′ is given by Q u τ ′ = e -λuτ ′
-ue -λτ ′ 1-u so that the success probability in a local interaction with N mobiles

P s (u|N = k) = 1 -Q u τ kyT (u,k) ⇒ P s (u) = 1 - ∞ k=0 P (N = k) Q u τ kyT (u,k)
where y T (u, k) is the fraction of mobiles playing T when there are k nodes in the local interaction. At the equilibrium

P s (u|N = k) = 1 -Q u τ ′ k(1-y(u)) . Q u τ ky(u) ⇒ P s (u) = 1 - ∞ k=1 P (N = k) Q u τ ′ k(1-y(u)) . Q u τ ky(u)
Using the same notations for the ESS and the Poisson distribution, at the equilibrium we have :

y * (u) = LambertW (-αβe -α(βe α -c) c c )c + αβe α cαβ where α = Q u τ ′ γ , c = (e γ -e Q u τ ′ γ ) PA(τ ′ )-PA(τ ) 1-PA(τ ) and β = 1 - Q u τ Q u τ ′ .
The probability of success is:

P s (u) = 1 -e -γ e γ(Q u τ ′ ) (1-y(u)) .(Q u τ ) y(u) -1
The following theorem gives some results on the probability of success according to the behavior of the ESS when the controls change at the source.

Theorem 1: The maximum value of the probability of success is attained for y * = argmax{P s (1), P s (u 0 )}, where u 0 satisfies ȳ * (u 0 ) = 1 and y * (u 0 + δ) ≤ 1, δ > 0.

To proove this theorem we need the two following lemma on the costs function H(y, u), and other genral results.

Lemma 1: For a fixed number of users N in a local interaction, the function H is concave in u for a given y.

Lemma 2: Let ỹ * the solution of the equation H(y) = 0. The following assertions are verified:

• Q u τ ′ is a decreasing function in u. • Q u τ is a decreasing function in u. • ỹ * is a decreasing function in u .
• Under some specific conditions we have ỹ * (ǫ) ≥ 1 otherwise ỹ * (ǫ) ≤ 0 with ǫ a very small positive number.

Poofs of lemma 1 and 2 are given in the appendix of this paper. We give now the proof of the theorem 1. Proof: Given the expression of the probability of success, maximizing P s (u) comes down to minimize the expression

(Q u τ ′ ) (1-y(u)) . (Q u τ ) y(u) . Let f (u) = (1 -y(u)) log(Q u τ ′ ) + y(u) log(Q u τ )
, we need to minimize f (u).

f ′ (u) = y ′ (u) log(Q u τ ) -log(Q u τ ′ ) + (1 - y(u)) (Q u τ ′ ) ′ (Q u τ ′ ) - (Q u τ ) ′ (Q u τ ) + (Q u τ ) ′ (Q u τ ) .
For u small, using lemma 2, we have: y * = 1 or y * = 0 If y * = 0, given that y * is decreasing in u then y *

= 0 ∀ u. f ′ (u) = (Q u τ ′ ) ′ (Q u τ ′ ) ≤ 0 thus, f is decreasing and P s (u) is always increasing on [0, 1].
On the other hand, if y * = 1 for u small, we need to prove that if P s (u) = P max then u ∈ [u 0 , 1]. Since y * is a decreasing function of u, we have, ȳ * (0) = 1 =⇒ ∃u 0 s.t. ȳ * (u 0 ) = 1 and ȳ * (u 0 + δ) ≤ 1, δ > 0.Where ȳ * is the projection of y * on the interval [0, 1]. y * = 1 for u small ⇒ f is decreasing and P s is always increasing f or u ∈ [0, u 0 ].

Figure IV-A shows the shape of the ESS using the Poisson distribution for different set of values for the parameters. Values are set in table I for each cases. As we can see from the figures, the optimal value of the source control ( maximizing the probability of successful delivevry) is sometime obtained, according to the notations of theorem 1, inside the interval [u 0 , 1[. This means that increasing the control at the source does not alway insure a higher probability of success given that the ESS y * changes accordingly. A similar observation can also be deduced from Figure III-D for the Dirac distribution.

V. CONCLUSION

In this paper Markov decision evolutionary games are used to model competition between individual mobiles acting as relay nodes in a DTN routing game. The objective of the source node is to maximize the probability of success of delivering a message to destination. However, mobiles decide to join message relaying based on their current energy state, which in turn is influenced by the forwarding control used by the source, in trade for reward.

Under this framework, we studied a source-controlled evolutionary game aimed at optimizing the energy consumed by relays. We observed a clear trade-off, where the optimal solution in general does not correspond to forwarding at full rate at the source node, and we showed cases where such a greedy strategy is well sub-optimal in maximizing the probability of success at the equilibrium.

Figure 1 .

 1 Figure 1. Population profile and probability of success for different values of N using Dirac distribution

Population profile and probability of success using Poisson distribution: (Two main observed cases) VI. APPENDIX

A. Activation control

We recall lemma 1. We state that: For a fixed number of users N in a local interaction, the function H is concave in u for a given y.

Proof: For N fixed and a given y, let

we have,

Let B = A + yη; we express the derivative of h N (u):

Though the negativity of this last expression has been observed for all the several set of values we experimented, it is not obvious to see here. We will then assume that it is negative and conclude that the function H is concave in u.

We recall lemma 2. We state that: Let ỹ * the solution of the equation H(y) = 0. The following assertions are verified:

• Under some specific conditions we have ỹ * (ǫ) ≥ 1 otherwise ỹ * (ǫ) ≤ 0 with ǫ a very small positive number.

Proof: We proove here the two last points.

• To show that ỹ * is a decreasing function in u, we first show that H is a non-increasing function of y. Indeed, We have,

.

Only the term f (y

, in the expression of H is dependent on y. For every parameters (other than y) fixed, we have:

and

ỹ * is a decreasing funtion of u.

• We have, H(y, u) = V τ (F, y) -V τ (F, y), let's find a condition on τ and τ ′ so that H(y, u) ≥ 0,

When u is taken very small, we have,

Considering u small, we have, T > λτ +e -λτ -1 λτ ′ +e -λτ ′ -1 then H(y, u) ≤ 0 and y * = 0.


Lazaros Gkatzikis

Georgios S Paschos

Iordanis Koutsopoulos

Medium Access Games: The Impact of Energy Constraints

Keywords: ALOHA, contention, energy saving, game theory

We consider random medium access schemes for devices that support sleep modes, i.e. turning off electronic compartments for energy saving. Due to hardware limitations, sleep mode transitions cannot occur at the medium access timescale. Each terminal can choose when to turn on/off and its probability to transmit on an arbitrary slot. Thus, we develop a two level model, consisting of a fast timescale for transmission scheduling and a slower timescale for the sleep mode transitions. We take a game theoretic approach to model the user interactions and show that the energy constraints modify the medium access problem significantly, decreasing the price of anarchy. Our results give valuable insights on the energy-throughput tradeoff for contention based systems.

I. INTRODUCTION

As mobile communications become part of our everyday life, new challenges for the system designers come to the foreground. First of all, the scarcity of bandwidth resources leads to extreme competition for the medium. Besides, the total energy dissipation by communication devices has been shown to amount to a significant portion of a nation's power profile, motivating efforts of per device energy economy. In an attempt to minimize their energy footprint and/or maximize the battery lifetime, existing wireless devices support radio sleep modes.

A generic wireless terminal consists of several circuit building blocks with the RF transceiver (radio) contributing significantly to the overall energy consumption. The RF transceiver itself consists of four subblocks. The transmit block that is responsible for modulation and up-conversion (i.e. transforms the baseband signal to RF), the receive block dedicated to the down-conversion and demodulation, the local oscillator that generates the required carrier frequency, and the power amplifier that amplifies the signal for transmission. Existing wireless devices support radio sleep modes that turn off specific subblocks, to minimize their energy consumption while inactive. For example, as shown in Table I the CC2420 transceiver ( [START_REF]cc2420 radio transceiver[END_REF]) provides three different low power modes. In the deepest sleep mode, both the oscillator and the voltage regulator are turned off, providing hence the lowest current draw. However, this comes at the cost of the highest switching energy cost and the longest switching latency. On the other hand, the idle mode provides a quick and energy inexpensive transition back to the active state, but at the cost of higher current draw and consequently higher current consumption.

To address this tradeoff, the authors of [START_REF] Jurdak | Radio sleep mode optimization in wireless sensor networks[END_REF] propose a scheme to dynamically adjust the power mode according to the traffic conditions in the network. They show that in a low traffic scenario, deep sleep should be preferred since most of the time the nodes tend to be inactive. In a high traffic setting though, a "lighter" sleep mode would be preferable, because frequent mode transitions incur high delay and energy costs, overshadowing the energy saving due to the low current draw. In a similar setting, [START_REF] Azad | Optimal control of sleep periods for wireless terminals[END_REF] considers optimal scheduling of the sleep periods for the scenario of a mobile receiving data from a base station. The objective is to derive the sleeping strategy that balances the energy cost of frequent waking up to check for new packets and the retrieval latency.

In this direction, several energy aware MAC protocols have been proposed, either centralized or distributed ones, to resolve contention. However, most of them rely on the willingness of the nodes to comply with the protocol rules. Hence, they are vulnerable to selfish users that may deviate from the protocol in order to improve their own performance. Game theory comes as the ideal tool to model interactions among selfinterested entities competing for common resources and it has also been considered recently for medium access.

In [START_REF] Jin | Equilibria of a noncooperative game for heterogeneous users of an aloha network[END_REF], the Nash Equilibrium Points (NEP) in a slotted ALOHA system of selfish nodes with specific quality-ofservice requirements are studied. It has been observed that usually selfish behavior in medium access leads to suboptimal performance. For example, a prisoners dilemma phenomenon arises among selfish nodes using the generalized slotted Aloha protocols of [START_REF] Ma | An analysis of generalized slottedaloha protocols[END_REF]. A decrease in system throughput, especially when the workload increases due to the selfish behavior of nodes, has been observed in [START_REF] Altman | Slotted aloha as a game with partial information[END_REF], [START_REF] El-Azouzi | Cooperative and non-cooperative control for slotted aloha with random power level selections algorithms[END_REF].

The interplay of medium access contention and energy consumption was considered recently in [START_REF] Jin | Distributed contention window control for selfish users in ieee 802.11 wireless lans[END_REF]. In particular, a scenario of users selecting their back-off control parameters based on the measured collision rate and their power consumption was considered. Each user attempts to balance the utility acquired by transmitting and the disutility caused to him due to the induced energy consumption. The existence, uniqueness and stability of the equilibrium points of the arising game were investigated. In a similar framework and in an attempt to mitigate the effects of selfishness, the authors of [START_REF] Menache | Efficient rate-constrained nash equilibrium in collision channels with state information[END_REF] study the problem of minimizing the energy consumption for given throughput demands for a contention MAC. They show that whenever the demands are feasible, there exist exactly two Nash equilibrium points and derive a greedy mechanism that always converges to the best one.

In this paper we introduce an additional level of decision making capturing the ON-OFF strategy of the terminals over the classic ALOHA game. We model contention for the medium as a game, where users with specific energy constraints select both the proportion of time that they sleep and their medium access probabilities. To the best of our knowledge, this is the first work that addresses the interplay between contention and energy consumption for systems that support sleep modes. The contributions of this paper can be summarized in the following:

• We characterize the throughput optimal strategy under energy constraints, which differs from traditional Aloha and serves as a reference point. We also provide a distributed counterpart which focuses on fairness. • We formulate contention as a non-cooperative game and

show that it has a unique NEP and bounded Price of Anarchy (PoA), i.e. contrary to intuition from prior works we find that energy constraints reduce the negative impact of selfish behaviour. • Based on the rationality of the users we derive a modified strategy, which allows the users to observe competition. This policy is more efficient but has multiple NEPs. The main characteristics of slotted ALOHA are also apparent in most contemporary contention-based systems, such as the IEEE 802.11. For example, all these systems exhibit a certain amount of inherent inefficiency; the total throughput in a common channel breaks down significantly, as the number of users and the message burstiness increase (see [START_REF] Bianchi | Performance analysis of the ieee 802.11 distributed coor-dination function[END_REF]). Despite its limited applicability and mainly due to its simplicity, Aloha remains a tractable insightful tool for studying such systems. Consequently, our results provide insights for other contention based systems.

II. SYSTEM MODEL

We consider a communication scenario of N = |N | mobile terminals transmitting to a common destination (e.g. uplink to a Base Station). Time is slotted and within each timeslot each user may select either to transmit or to stay silent. Medium access is performed probabilistically, according to a slotted Aloha protocol, where a collision occurs whenever two or more terminals transmit concurrently. Each terminal has always packets at its buffer for transmission (i.e. saturated queue), but it has limited energy resources. Each device i is characterized by an energy budget ẽi , representing either its available battery power or the maximum energy it is willing to expend. In order to save energy it can turn into a sleep mode, where most of the circuits are turned off. For analytical tractability we assume that each terminal may be in one out of two possible operation modes, ON or OFF.

In general, a mode transition incurs significant energy and time (delay) costs. Besides, due to hardware limitations the time required for a mode transition is of the order of msec, much larger than the duration of a timeslot. Consequently, transition at the timeslot level is neither feasible nor desirable. Hence, we introduce a new timescale (we call it frame) where the mode switching takes place. Several timeslots constitute a frame. The beginning of each frame is a decision point, where a node may change its operation mode. Within a frame, the nodes keep their mode fixed and may access the medium randomly with probability p. This is also assumed fixed on a per frame basis. For decision reasons and without affecting the operation of the system, we introduce yet another timescale, that of the super frame, where an arbitrary number of frames, say K, forms a superframe (Fig. 1) A binary vector q i (j) = {0, 1} K , represents the ON or OFF state of user i on superframe j, and p i its access probability (i.e. the access probability is selected only once per superframe). In practice the mobile terminals are autonomous and due to the limited knowledge available node level, synchronization of sleep modes is a difficult task. On the other hand, probabilistic ON-OFF has been deemed a feasible strategy ( [START_REF] Dousse | Latency of wireless sensor networks with uncoordinated power saving mechanisms[END_REF]). Thus, we focus on a probabilistic version of the aforementioned problem. Each user i is characterized by a probability of being ON, denoted with q i and a medium access probability p i . In matrix notation the strategy space can be written as

I = {p, q}, with p = [p 1 , p 2 , . . . p N ] and q = [q 1 , q 2 , . . . q N ].
If we consider the probability of user i successfully transmitting a packet in an arbitrary slot we can calculate throughput as

Ti(p, q) = piqi j∈N \i (1-pjqj) p i q i =1 = piqi 1 -piqi j∈N (1-pjqj) (1)
Note that the throughput of user i is an increasing function of p i and q i , but decreasing in the number of terminals N contending for the medium. The latter is in compliance with the classic ALOHA, but in practice also holds for CSMA/CA protocols. The energy cost of user i is a random variable with a mean value of Ēi (p i , q i ) = q i (c 1 + c 2 p i ), where c 1 is the energy consumption while ON and c 2 the additional cost imposed by the transmission. Obviously, in order to transmit, the node has to be ON. Here, we do not consider the energy consumption of the transition itself.

III. THE IMPACT OF CONSTRAINED ENERGY RESOURCES

ON THE SYSTEM THROUGHPUT First, we would like to find the ON-OFF and the medium access probabilities that maximize the collision-free utilization of the medium, and consequently the throughput of the system. This can be formally expressed as the following optimization problem: maximize

I={p,q} N i=1 Ti (p, q) s.t. Ēi (p i , q i ) ≤ ẽi ∀i {p i , q i } ∈ [0, 1] 2 ∀i (2)
The intuitive explanation of the energy constraint is the fact that each battery cycle provides ẽi resource and thus, the maximum energy constraint is directly mapped to a minimum recharge time for the mobile. Throughout the paper, and without loss of generality, we assume that the users are ordered in decreasing energy budget, i.e. ẽ1 ≥ ẽ2 ≥ . . . ≥ ẽN .

A. Throughput optimal scheduling in energy constrained ALOHA with sleep modes

In the classic ALOHA setting, where no energy constraints exist, the throughput optimal strategy would be the one that eliminates contention. Thus, if we could force only a single user, say user k, to access the medium with probability p k = 1 in each frame, we would achieve the maximum total throughput. In our scenario though, due to the energy constraints, the users may not be able to stay continuously ON (i.e q k = 1) or to transmit with p k = 1. Then, what is the best way to exploit the available energy resources? For each user we need to find the portion of energy to spend for staying ON during the frames and the portion used for transmitting while being ON.

Lemma 1: Out of all the throughput optimal strategies the most energy efficient ones are of the form I * = {1, a} with 1 = [1, 1, . . . 1] and a ∈ [0, 1] N . Thus, without loss of optimality we may restrict the strategy search space only to strategies where the nodes transmit continuously inside any ON frame.

Proof: Let Î be a feasible throughput optimal strategy, where {p i , qi } the strategy of user i. From eq. 1 we may see that throughput depends only on the pq products. Let a i = pi qi . The strategy I * = {1, a} with a = [p 1 q1 , p2 q2 , . . . pi qi ] achieves the optimal throughput, i.e. T (I * ) = T Î .

Then, we prove that I * is also feasible, as the most energy efficient strategy.

Any other feasible throughput optimal strategy Î can be written as an expression of a as

{p i = ai ai+δi , qi = a i + δ i }, with 0 < δ i ≤ min{1 -a i , ẽi-ai(c1+c2) c1
}. Thus, regarding the energy efficiency we have:

Ē Î = N i=1 (a i + δ i ) c 1 + c 2 a i a i + δ i = N i=1 δ i c 1 + a i (c 1 + c 2 ) = Ē (I * ) + c 1 N i=1 δ i > Ē (I * ) .
This completes our proof.

Based on Lemma 1, the optimization problem described by eq. 2 can be simplified to an expression that depends only on q leading to the objective function

T (q) = N i=1 q i j∈N \i (1 -q j )
and constraints 0 ≤ q i ≤ qi = min ẽi c1+c2 , 1 ; this can be further simplified into a problem of binary integer programming.

Lemma 2: The optimal solution is of the form q * = b * diag[q 1 , q2 , . . . qN ] where b * is a binary row vector.

Proof: The partial derivative of the objective function is given by:

∂ T ∂q k = j∈N \k (1 -q j ) - j∈N \k q j l∈N \{k,j} (1 -q l ) = j∈N \k (1 -q j ) - j∈N \k q j 1 -q j l∈N \k (1 -q l ) = ⎛ ⎝ 1 - j∈N \k q j 1 -q j ⎞ ⎠ j∈N \k (1 -q j )
We have thus shown that the sign of the partial derivative with respect to the kth element depends only in the parameter j∈N \k q j 1q j . This leads to the following decision making: Proof: We will prove this by contradiction. Assume that b = b * , a vector of k ones (i.e. any vector where the ones are not placed in the first k places), is the throughput optimal binary vector. We can construct a new vector b = [1, 1, . . . 1, 0, 0, . . . 0], which has only the first k users activated and gives identical throughput, by deriving the ON-OFF vector q from the corresponding indices of b. To construct such a vector we need to move the rightmost 1, say from position l of the initial vector to an earlier zero position say m with m < l. Based on Lemma 2, we can show that by fully activating or deactivating users (i.e. meeting the constraint with equality or setting access probability to zero), we receive a new schedule b * = b and the corresponding q * of increased throughput. This leads us to a contradiction regarding the optimality of b.

q k = ⎧ ⎨ ⎩ qk , if j∈N \k q j 1 -q j < 1, 0, otherwise. (3
Based on the aforementioned lemmas we may derive the centralized Algorithm 1 that yields the throughput optimal probabilistic strategy and is of linear, in the number of users N , complexity. The main idea behind this algorithm is that contention may or may not be beneficial, depending on the energy constraints of the users. Namely, an additional user is useful if and only if the energy resources of the already active users are not sufficiently large, leaving thus the medium underutilized. An additional user introduces a gain due to the exploitation of the empty frames, but also a loss, due to the collisions whenever he is concurrently active within a frame with someone else. If the average gain is greater than the induced loss, it is beneficial for the system to be enabled.

Algorithm 1 Optimal probabilistic frame scheduling 1: Order users in decreasing ẽi . Without loss of generality, we reassign the indices such that q1 ≥ q2 ≥ . . . ≥ qN 2: q ← 0 3: j ← 1 4: while j ≤ N and

j i=1 q i 1 -q i < 1 do 5:
q j ← qj 6:

j ← j + 1 7: end while Theorem 1: Algorithm 1 yields the throughput optimal probabilistic strategy.

Proof: The optimality of 1 comes directly from Lemmas 1, 2 and 3.

Note that this algorithm gives also the throughput optimal scheduling for the constrained version of the Aloha problem, where each terminal has an individual constraint on its medium access probability p i . This is a simplified version of the problem considered in this work, where no sleep mode support exists, i.e. q i = 1.

The algorithm above promotes the k less energy constrained users (0 ≤ k ≤ N depends on actual constraints) and suppresses the rest. It will only serve as a performance benchmark, since it is a centralized algorithm that introduces important coordination and fairness issues. In particular, it requires extensive coordination among the users and causes extremely unfair treatment of the users of low energy budget. Thus, in the following sections we develop algorithms that capture the autonomous nature of the users and fit to the dynamic distributed environments considered here.

B. A distributed fair algorithm

In order to capture the notion of proportional fairness we substitute the original objective function with the following: U (p, q) = N i=1 w i log Ti . The multiplicative factor w i can be used to balance the throughput among the users of the system at will. For example, the value w i = ẽi k∈N ẽk would allow us to split the throughput proportionally to the energy budget of the users. By proper reformulation, the objective function can be rewritten as U (p, q) = N i=1 log (p i q i ) wi (1p i q i ) 1-wi . This is a separable per user function that leads to a fully distributed implementation, requiring minimal information exchange. Actually the only information required is the value of the total energy available in the terminals, namely

C. A modified strategy

Up to now we assumed that each user makes a decision once for his strategy and applies it forever. As a result, user k whenever active, transmits with p k = 1, independently of the number of active users within a frame. Thus, whenever two or more users select to transmit within a frame they receive zero payoff, but consume energy. Based on these observations, a rational player would be expected to backoff whenever a collision is detected. Although, the terminal is not allowed to switch off in a crowded frame, due to the switching time overhead incurred, it may reduce its access probability. This way, it would avoid spending energy on useless transmission that always lead on collisions and could utilize these savings for pursuing further contention-free frames. Building on this idea we propose the following modified strategy.

Any active user attempts a transmission within the first timeslot of the current frame. If the transmission succeeds he selects a medium access probability of p i = 1 and captures the whole frame successfully. Otherwise he adjusts his strategy, and reduces his transmission probability to pi . It can be shown that this strategy always yields better throughput than the original one. The expressions for throughput and energy consumption for this case are respectively given by:

Ti = q i ⎧ ⎨ ⎩ (1 -pi ) j∈N \i (1 -q j ) + pi j∈N \i (1 -pj q j ) ⎫ ⎬ ⎭ (4) Ēi = q i ⎧ ⎨ ⎩ c 1 + c 2 ⎡ ⎣ pi + (1 -pi ) j∈N \i (1 -q j ) ⎤ ⎦ ⎫ ⎬ ⎭ (5)
The complicated throughput and energy expressions for the modified scenario make the problem of optimal scheduling analytically intractable. Thus, in order to get insight on the performance of the modified strategy, we consider a simplified version of the problem by restricting the feasible user strategies. In particular, we assume that all the users of the system can be classified in one of the following three groups; the aggressive, the conservative and the passive ones. The former capture the medium whenever they are active (ON), the second transmit only whenever they sense an empty frame and the last do not participate at all.

We consider Algorithm 2 that performs a search over the solution subspace. This algorithm is of exponential complexity and will be used only for comparison purposes. It can be shown that in the optimal scheduling for our restricted solution space, at least one aggressive and one conservative user exist. In all the simulation cases that we have tried, this categorization did not to limit the system performance; nevertheless a formal proof that the optimal solution lies on the restricted subspace could not be derived.

Algorithm 2 Modified optimal probabilistic frame scheduling 1: Search over B = {A, C, P}, i.e. the set of all the possible partitions of N of size 3, with |A| ≥ 1 and |C| ≥ 1 for the throughput optimal assignment: 2: for all i ∈ A (% aggressive) do 3: (1-qj ) , 1 7: end for 8: for all j ∈ P (% passive) do 9:

{p i , q i } = {1, min ẽi c1+c2 , 1 } 4: end for 5: for all k ∈ C (% conservative) do 6: {p k , q k } = 0, min ẽi c1+c2 j∈N \k
{p j , q j } = {0, 0} 10: end for

IV. GAME THEORETIC APPROACH

Previously we derived probabilistic medium access protocols that require coordination of actions of the users involved. However, in an autonomous setting as the one considered here, individuals may not comply with the rules imposed by the protocol. Actually, users may exhibit selfish behaviour and select the strategy that maximizes their own utility, namely their individual throughput, at the expense of others. Thus, in this section we model the user interaction/contention as a noncooperative game. We derive models for both the initial and the modified scenario.

A non-cooperative game is defined by a set of players, a set of strategies and a metric that indicates the preferences of the players over the set of strategies. In our case we have:

• Players: the N users • Strategies: user's i set of feasible medium access and ON-OFF probabilities I i = {p i , q i : Ēi ≤ ẽi and 0 ≤ p i , q i ≤ 1} • User preferences: represented by a utility function U i (I i ); peer i prefers strategy Îi to

I i iff U i ( Îi ) > U i (I i ).

A. Our initial scenario as a non-cooperative game of perfect information

For the initial optimization problem (2) the utility function of user i is defined as U i (I i ) = Ti = p i q i j∈N \i (1-p j q j ). It can be easily verified that the throughput maximizing strategy of each individual is independent of the actions of the other users and comes as the solution of the following optimization problem: maximize Ii={pi,qi}

p i q i s.t. q i (c 1 + c 2 p i ) ≤ ẽi {p i , q i } ∈ [0, 1] 2 (6)
Lemma 4: The throughput optimal strategy for user i is {p i , q i } = 1, min{ ẽi c1+c2 , 1} . The resulting game has a unique Nash Equilibrium Point, described by the strategy I * = {1, q * }, with q * i = ẽi c1+c2 . Proof: Since the utility is an increasing function of both p i and q i the energy constraint should be satisfied with equality at the optimum.

The proof is similar in spirit to the one in Lemma 1. Let {p i , qi } be the throughput optimal strategy of user i, with pi < 1. From the energy constraint we have qi (c 1 + c 2 pi ) = ẽi . There exists the alternative strategy {ṕ i , qi } = {1, pi qi } of equivalent utility (individual throughput) but of lower energy consumption. In particular,

qi (c 1 + c 2 ṕi ) = qi (c 1 + c 2 ) = qi (c 1 ṕi + c 2 ṕi ) < ẽi (7)
Consequently, there exists δ > 0 such that (q i + δ)(c 1 + c 2 ) = ẽi . This strategy {p * i , q * i } = {1, qi + δ} obviously yields increased utility for the user, which contradicts the user optimality of {p i , qi } and completes our proof. The same result can be derived through the KKT conditions.

Given that the optimal strategy of a user is independent of the actions of the other users and is determined only by his own energy constraint, deriving the resulting NEP is straightforward.

From the above, we may deduce that at the Nash equilibrium point we receive throughput, only when a single user is ON in a frame. Given the NEP of the game we may quantify the performance loss arising due to the selfishness of the individuals, by using so called Price of Anarchy (PoA) metric. This is the ratio of the value of the objective function at the global optimum to its value at the NEP and in our setting is given by:

PoA = i∈S ẽi c 1 + c 2 j∈S\i (1 - ẽj c 1 + c 2 ) i∈N ẽi c 1 + c 2 j∈N \i (1 - ẽj c 1 + c 2 ) ≥ 1, ( 8
)
where S is the set of enabled users at the global optimum. Whereas in the classic Aloha games the PoA is unbounded, in our energy constrained Aloha setting the PoA is bounded, since the energy constraints impose a fictitious pricing scheme. The PoA grows unbounded only when at least two users have unconstrained energy resources. Then, these users (e.g. power plugged stations) would involuntarily act as jammers for each other and for all the others yielding hence zero system throughput.

B. The modified strategy as a non-cooperative game of perfect information

Here, we consider the game arising from the modified strategy. In this setting, we derive a non-cooperative game of perfect information, where at each iteration, given the parameters α = j∈N \i (1q j ) and β = j∈N \i (1 -pj q j ) a user selects its best response. By best response we mean that each user updates his decision variables, so as to maximize its utility function, in response to the others' actions.

Theorem 2: The best response strategy of user i is given by:

pi = 1, if [c 1 + c 2 α] β > (c 1 + c 2 )α, 0, otherwise. ( 9
)
q i = ẽi c 1 + c 2 [p i + (1 -pi )α] (10)
The arising modified game has multiple NEPs.

Proof: Since the utility is an increasing function of pi and q i , the constraint needs to be satisfied with equality. Thus, we may replace q i from eq. 5 into the throughput expression, namely eq. 4. Then, the partial derivative of the objective function is given by the following expression:

∂ T ∂ pi = ẽi [β -α] [c 1 + c 2 α] -c 2 α[1 -α] {c 1 + c 2 [p i + (1 -pi )α]} 2 = ẽi [c 1 + c 2 α] β -(c 1 + c 2 )α {c 1 + c 2 [p i + (1 -pi )α]} 2
The sign of this expression depends only on α = j∈N \i

(1q j ) and β = j∈N \i

(1 -pj q j ). As a result given the actions of the other users, the objective function is either a strictly increasing or a strictly decreasing function of pi . Thus, the best response strategy of user i is given by eq. 10.

V. NUMERICAL RESULTS

In order to quantify the throughput performance of the proposed schemes we perform extensive simulations of a small, easy to follow system. We consider a scenario of N = 5 terminals with energy constraints given by ẽ = [30, 25, 15, 10, 5] and {c 1 , c 2 } = {50, 70} units. By abusing slightly the definition of PoA, we use the modified optimal as the performance benchmark and for each scheme we derive the performance ratio metric defined as:

Performance ratio X = Throughput of modified optimal Throughput of scheme X (11) Thus, all the figures depict the performance degradation in comparison to the modified optimal. Since the modified game has several NEPs we depict the PoA i.e. the ratio of the throughput at the optimum to the throughput at the worst NEP, the price of stability (PoS) i.e. the ratio of the throughput at Fig. 3. The throughput performance of the system as the total energy budget of the system increases the optimum to the throughput at the best NEP, and the mean performance at the NEPs. Regarding the initial setting, we depict the performance degradation of the original optimal, the fair approach and the initial game theoretic scheme. Initially, we consider how the energy budget of the less energy constrained user affects the performance of the system as a whole. In Figure 2 we see that the additional power budget increases the performance degradation due to the additional collisions caused. The system stabilizes for ẽ1 = c 1 + c 2 , where user 1 has sufficient energy budget to capture medium entirely on his own. We notice also that the modified strategy, of backing off whenever a collision is detected, provides significant performance benefits. The improvement is becoming more significant as the available energy budget increases.

In Figure 3 we depict the system performance as we relax the energy constraints of every terminal. We start from the energy budget vector of ẽ = [30, 25, 15, 10, 5] and increase each dimension by 5 within each iteration. The x axis refers to the ẽ1 value, whereas the whole vector is given by ẽ = [ẽ 1 , ẽ1 -5, ẽ1 -15, ẽ1 -20, ẽ1 -25]. In this scenario, one Fig. 4. The throughput performance of the system as an expression of the transmission cost may notice the benefits that arise from the coordination among the terminals. The coordinated approaches are robust again the increased availability of energy, whereas in the game theoretic approaches this leads to an increased number of collisions, due to the increased aggressiveness of the users. Next, we consider the impact of the transmission cost c 2 . We notice in Figure 4 that in a scenario of low energy constraints the increased transmission cost makes the users less aggressive, leading thus to reduced collisions and consequently the performance gap among the coordinated and the game theoretic approaches diminishes. Nevertheless, the performance gap of the initial and the modified strategy remains more than 40% throughout.

Finally, we investigate the impact of the number of competing users on the performance at the resulting equilibria (Figure 5). Starting from a system of only two competing users with energy constraints ẽ = [START_REF] Ma | An analysis of generalized slottedaloha protocols[END_REF][START_REF] Bianchi | Performance analysis of the ieee 802.11 distributed coor-dination function[END_REF] we keep adding in each iteration a single terminal of increasing energy budget. Thus, newcomer i is characterized by energy constraint ẽi = 5i. As expected the introduction of additional users increases competition for the medium and leads to more collisions. Consequently, the performance of the game theoretic approaches deteriorates very fast, whereas the coordinated approaches exhibit significant robustness.

VI. CONCLUSION

This work is a first step towards characterizing the energythroughput tradeoff for mobile devices that support sleep modes and operate according to contention medium access schemes. We characterized the throughput optimal strategy under energy constraints and we developed game theoretic models that capture the autonomous nature of the terminals. We showed that energy constraints may reduce contention and lead to better exploitation of the medium. Finally, we developed a simple modified medium access scheme, where the contention state of the medium can be sampled within a frame by the competing stations. This scheme can lead to more efficient decision making even without any cooperation. In this work, we have assumed non-cooperative games of perfect information. The scenario where each involved entity has only a subjective belief on its opponents' strategies is an interesting topic of future study. Besides, mechanism design could be considered as a means of driving the system to more efficient equilibrium points. This could be achieved either in the form of penalizing the users that exhibit extremely aggressive behaviour or by incentivizing the individuals to adopt socially optimal strategies.

Fig. 1 .

 1 Fig. 1. The structure of a superframe

) Lemma 3 :

 3 The optimal solution b * is of the form b * = [1, 1, . . . 1, 0, 0, . . . 0].

  k∈N ẽk , information that can be easily acquired. The solution to this optimization problem, in accordance to Lemma 1, is of the form I * = {1, a} with a = [min {w 1 , q1 } , min {w 2 , q2 } , . . . , min {w N , qN }].

Fig. 5 .

 5 Fig. 5. The throughput performance of the system an expression of the number N of competing terminals

TABLE I SWITCHING

 I TIME AND ENERGY CONSUMPTION OF A CC2420 RADIO

	Power mode	Switching	Switching	Current
		time(ms)	Energy (μJ) Consumption (μA)
	Tx	0	0	10000
	idle	0.1	1.035	426
	power down	1.2	42.3	40
	deep sleep	2.4	85.7	0.02

ACKNOWLEDGMENT L. Gkatzikis' work is co-financed by the European Union (European Social Fund ESF) and Greek national funds through the Operational Program "Education and Lifelong Learning" of the National Strategic Reference Framework (NSRF) Research Funding Program: Heraclitus II-Investing in knowledge society through the European Social Fund. I.Koutsopoulos and G. S. Paschos acknowledge the support of the European Commission through the NoE project TREND (FP7-257740) and the Marie Curie AGILENET (FP7-269132).