Eugenio Della Vecchia

Silvia Di

Alain Jean-Marie

Approximations on Risk-Averse Markov Decision Processes

Keywords: Markov Decision Processes, Rolling Horizon, risk aversion Markov Decision Processes, horizon roulant, aversion au risque

We consider the problem of approximating the values and the optimal policies in risk-averse discounted Markov Decision Processes with infinite horizon. We study the properties of the rolling horizon and the approximate rolling horizon procedures, proving bounds which imply the convergence of the procedures when the horizon length tends to infinity.

We also analyze the effects of uncertainties on the transition probabilities, the cost functions and the discount factors.

Introduction

Consider a random dynamical system, observed at discrete times. At each time t ∈ N, the state s t is observed, an action a t is chosen, and the system moves to a new state s t+1 , resulting in an instantaneous cost (or negative reward) r at (s t , s t+1 ). The cost function r is supposed to be independent on time. The actions a t chosen at each time t in the respective state s t determine a policy π whose performance is evaluated through a dynamic risk measure. Dynamic risk measures generalize the expected discounted sums of all costs, to which they reduce in the "risk neutral" case.

The objective of the controller is to find (when it exists) the policy that minimizes, given the current state s, the total performance defined over the infinite time horizon. However, for a wide class of stochastic control problems in discrete time and infinite horizon, obtaining an optimal policy explicitly is a difficult task. This is why practitioners often use instead a heuristic method called the Rolling Horizon (RH) procedure

On the other hand, in the context of stochastic sequential decision models, the controller has to take decisions, based on the knowledge of the current state, but without the certainty of the dynamics of the system, which will be governed by distributions of probabilities on the space of states, known a priori.

In both cases, an approximation of some original problem is solved. In such situations, it is useful to know bounds on the error incurred by solving approximated problems. The robustness of the model can indeed be assessed by analyzing the sensitivity of the optimal controls and the value function when considering approximations of the elements of the models. This analysis has been the topic of many publications in the case where the "performance" of the system is measured with the expected total discounted cost. For instance in [START_REF] Hernández-Lerma | Error bounds for rolling horizon policies in discretetime Markov control processes[END_REF] in the MDP (Markov Decision Process) context and in [START_REF] Vecchia | Rolling horizon procedures in Semi-Markov Games: The Discounted Case[END_REF] for Semi-Markov Games (and consequently for Semi-Markov Decision Problems). Structural approximations for Semi-Markov Games are obtained in [START_REF] Vecchia | Structural approximations in discounted Semi-Markov Games[END_REF].

On the other hand, using the expected cost as a metric is known to be characteristic of "riskneutral" optimizing agents. One may want to use a different, risk-sensitive metric: this is the purpose of risk measures. The use of dynamic risk measures in the context of optimal control problems of the MDP type, was proposed by A. Ruszczyński in [START_REF] Ruszczyński | Risk-averse dynamic programming for Markov decision processes[END_REF] and in a posterior work with O. Çavuş in [START_REF] Çavuş | Risk-Averse Control of Undiscounted Transient Markov Models[END_REF]. The purpose of the present work is to analyze the Rolling Horizon heuristic and perform a sensitivity analysis in this new context. We therefore generalize the results of [START_REF] Vecchia | Rolling horizon procedures in Semi-Markov Games: The Discounted Case[END_REF][START_REF] Vecchia | Structural approximations in discounted Semi-Markov Games[END_REF] to dynamic risk measures. The approximations obtained for MDPs in the literature are then recovered by specializing to the risk-neutral case. In [START_REF] Ruszczyński | Conditional risk mappings[END_REF], the authors use the terminology dynamic risk mappings, and in [START_REF] Ruszczyński | Optimization of Convex Risk Functions[END_REF][START_REF] Ruszczyński | Risk-averse dynamic programming for Markov decision processes[END_REF][START_REF] Çavuş | Risk-Averse Control of Undiscounted Transient Markov Models[END_REF], they talk about dynamic risk measures. In this work we adopt this last terminology.

The paper is organized as follows. We complete this introduction with a brief literature review of the approximation techniques made in the risk neutral case, similar to the ones proposed in this work. In Section 2 we make more precise the elements of the MDP model, following [START_REF] Hernández-Lerma | Adaptive Markov Control Processes[END_REF], and introduce the definitions and results on dynamic risk measures following [START_REF] Ruszczyński | Risk-averse dynamic programming for Markov decision processes[END_REF] and [START_REF] Çavuş | Risk-Averse Control of Undiscounted Transient Markov Models[END_REF]. Then in Sections 3 and 4 we state the RH procedures and the structural approximations on the elements of the models, respectively, and give bounds for the errors incurred in each case. An example developed in Section 5 illustrates some of these bounds and raises some issues. Conclusions are presented in Section 6.

Rolling Horizon Approximations are used in [START_REF] Hernández-Lerma | Error bounds for rolling horizon policies in discretetime Markov control processes[END_REF] to obtain almost optimal stationary policies in discounted and average MDP models. In [START_REF] Chang | Two-person zero-sum games: receding horizon approach[END_REF], the authors analyze the performance of the procedures when they are applied on Markov Games (MG). These authors also introduce the idea of approximate Rolling Horizon. On the other hand, structural approximations were studied in the book [START_REF] Altman | Constrained Markov Decision processes[END_REF], on constrained MDP, in [START_REF] Tidball | Approximations in Dynamic Zero-Sum Games[END_REF], for the MG case, and in [START_REF] Vecchia | Structural approximations in discounted Semi-Markov Games[END_REF], on Semi-Markov Games.

Preliminaries and Notations

Markov Decision Processes

We consider a Markov Decision Process of the form

M := (S, A, {A s : s ∈ S}, {Q a (•|s) : s ∈ S, a ∈ A s }, r, α) , ( 1
)
where S is the state space; for every s ∈ S, A s is the set of actions available in state s and A = s∈S A s is the action space. We set K = {(s, a) : s ∈ S, a ∈ A s }. Given a state s and an action a ∈ A s , the transition law Q a (•|s) is a stochastic kernel on S. The costs of transitions between states is a function r : K × S → R and α is a discount factor. For Borel sets X and Y , we will note with P(X) the family of probability measures on X endowed with the weak topology, and with P(X|Y ) the family of transition probabilities from state Y to X.

The space H t := K t × S of admissible histories of the process at the t-th decision epoch, consists of sequences of states and decisions up to that epoch.

A Markov policy is a sequence π = {π t } of stochastic kernels π t ∈ P(A|H t ) such that for every h t ∈ H t and t ∈ N, π t (A st |h t ) = 1. We denote by Π the set of all Markov policies. A Markov policy π = {π t } is stationary if there exists f ∈ P(A|S) such that f (s) ∈ P(A s ) and π t = f for all s ∈ S and t ∈ N. In this case, we identify π with f , i.e., π = f = {f, f, ...}. We denote by Π stat the set of all stationary policies.

For each policy π ∈ Π and any initial state s there exist a unique probability measure P π s and stochastic processes {S t } and {A t }. S t and A t represent the state and the actions at the t-th decision epoch. E π s denotes the expectation operator with respect to P π s . In general, for functions defined on S, we shall not write the state variable s, but sometimes it will be convenient to emphasize this dependency. In addition, given a stationary policy f ∈ Π stat we let φ f (s) = φ f (s) (s). The notation is also extended to probability distributions: for ξ on A s , h ξ (s) = As h a (s)ξ(da) whenever the integral is well defined. In the same spirit, we shall denote r a (s, s ′ ) = r(s, a, s ′ ).

In order to evaluate the performance of policies, a discounted criterion is often used. For N ≧ 1, s ∈ S, π ∈ Π, the expected N -horizon α-discounted cost is defined by

V π N (s) = E π s N -1 t=0 α t r At (S t , S t+1 ) ,
and for the infinite horizon problem by

V π (s) = E π s ∞ t=0 α t r At (S t , S t+1 ) .
In this so called risk neutral case, and under standard assumptions, the problem has Markov optimal policies for finite-horizon models and stationary optimal policies in the finite-horizon case.

Inria

Introduction of Markov Risk Measures in the MDP

In [START_REF] Ruszczyński | Risk-averse dynamic programming for Markov decision processes[END_REF] A. Ruszczyński introduces risk aversion to dynamic problems, replacing the expected value operator by a dynamic risk measure. In [START_REF] Çavuş | Risk-Averse Control of Undiscounted Transient Markov Models[END_REF] the use of dynamic risk measures is extended to transient problems, in which there exists an state s * such that for all a ∈ A s * , Q a (s * |s * ) = 1 and r a (s * , s * ) = 0, sometimes referred to as "stochastic shortest path problems". We adopt from those works the notations and refer to them for the definitions involved.

We assume at first that a probability space (Ω, F , P) is fixed. F t will denote the σ-subalgebras generated by the histories h t , and define spaces Z t of F t -measurable random variables on Ω. Precisely, we shall work with Z t = L p (Ω, F t , P), for some p ∈ [1, ∞), the spaces of real-valued, F t -measurable and p-integrable random variables on Ω. For details on the construction and generalizations on the fixed probability space we refer to [3, Section 3]

ρ t (v(S t+1 )) = σ(v, s t , Q at (•|s t )) .
The r.h.s. of this expression is parametrized by the state s t , and it defines a function S → R.

Suppose that N is a fixed horizon. Each policy π = {f 0 , f 1 , ..., f N -1 } results in a cost sequence Z t = r At-1 (S t-1 , S t ), t = 1, ..., N . The risk of this sequence in the finite-horizon case will be evaluated by using the functional [3, Equation (1), p. 3]

J π N (s) = ρ 1 r A0 (s, S 1 ) + αρ 2 r A1 (S 1 , S 2 ) +α 2 ρ 3 (r A2 (S 2 , S 3 ) + ... + α N -1 ρ N (r AN-1 (S N -1 , S N ))...) ,
where ρ t are the Markov conditional risk measures introduced above.

For the infinite horizon context the risk will be evaluated using discounted risk functional [12, Sections 6-7, pp. 248-250] of the form

J π (s) = lim N →∞ J π N (s) . (2)
In order to prove optimality results, the following dynamic programming operators on the space of bounded functions are introduced. For any stationary policy f ∈ Π stat , and s ∈ S,

(T f v)(s) = σ r f (s, •) + αv(•), s, Q f (•|s) (3)
and

(T v)(s) = inf a∈As σ (r a (s, •) + αv(•), s, Q a (•|s)) , (4)
where, for s ∈ S, σ (•, s, Q) is the risk transition mapping associated to the probability distribution Q ∈ P(S|{s}) on S given s.

As it is also developed in [12, Section 4, p. 243-246], if for any s ∈ S and Q ∈ P(S|{s}), σ is lower semicontinuous with respect to the first argument, then there exists a closed convex multifunction A(s, Q), with values in P(S), such that for every bounded real function v,

σ (v, s, Q) = sup m∈A(s,Q) S v(z)dm(z) . (5)
We can now state our working assumptions and some preliminary results.

Assumption 1.

(a) S is a Borel set.

(b) For each s ∈ S, A s is a compact set.

(c) For each s ∈ S the mapping a → Q a (•|s) is continuous in A s .
(d) For each t ∈ N, the conditional risk measure ρ t is a Markov risk measure, and such that for every s ∈ S, A(s, •) is lower semicontinuous.

(e) r is a bounded function on K × S:

there exists M ∈ R such that ||r|| ∞ = M . (f) For each s, s ′ ∈ S, r a (s, s ′ ) is a lower semicontinuous function on A s .
Lemma 2.1. If Assumption 1 holds, for any stationary policy f ∈ Π stat , T f in a non decreasing and α-contractive operator on the space of bounded functions. The same properties hold for the operator T . Moreover, the value J f of a stationary policy f is the unique bounded solution of the equation

T f v = v.
a) For all π ∈ Π, ||J π || ∞ ≦ M 1-α . (b)
The finite horizon problems have optimal values. Moreover, starting from

J * 0 ≡ 0, for n ≧ 1, the function J * n := T J * n-1

is the value function for the n-horizon problem, and the Markovian policy {f

* n-1 , f * n-2 , ..., f * 1 , f * 0 }
, where the functions f * k are the corresponding minimizing functions, for k = 0, ..., n -1, is optimal.

(c) The infinite-horizon problem has a value J * , and for all s ∈ S,

|J * (s) -J * n (s)| ≦ M α n 1 -α → 0
as n → ∞.

(d) J * is the unique bounded function satisfying the optimality equation

T v = v.
Moreover, there exists an stationary policy f * which is optimal for the infinite-horizon problem.

Proof 3 Rolling Horizon Approximation Procedures

The Rolling Horizon Procedure

When large stochastic control problems are analyzed, the complete computation of explicit optimal strategies is a difficult, or even an impossible task. Instead, in practice a heuristic method called the Rolling Horizon procedure (also, Receding Horizon, or Model Predictive Control) is often used. The RH method prescribes to repeatedly solve a finite-stage horizon problem, taking the current state as initial state. Then, only the first decision will be applied. Specifically, the procedure to construct a RH policy is the following one. Fix some integer N (the horizon length) and consider a sequence of epochs indexed by t ∈ N.

Inria

RH1 At iteration t, and for the current state s t , solve the finite horizon problem (FHP) with horizon N . In the context of risk measures, this problem would be:

(FHP) inf π ρ 1 r A0 (s, S 1 ) + αρ 2 r A1 (S 1 , S 2 ) +α 2 ρ 3 (r A2 (S 2 , S 3 ) + ... + α N -1 ρ N (r AN-1 (S N -1 , S N ))...) , taking s = s t as initial state. An action f N -1 (s t ) is obtained. RH2 Apply a t = f N -1 (s t ).
RH3 Observe the achieved state at time t + 1: s t+1 .

RH4 Set s t := s t+1 and t := t + 1 and go to step RH1.

The RH procedure does not specify how to compute the value f N -1 (s t ). Its efficiency is based on the idea that computing the value f N -1 (s t ) alone is usually much easier than computing the N decision rules (f N -1 , f N -2 , . . . , f 1 , f 0 ) that are the usual result of solving (FHP) for all possible initial states. On the other hand, the performance of the resulting sequence of decisions is not the optimal one, although the intuition is that when N is "large enough", the performance should be close to the optimal. The practical issue is then to choose N so as to obtain a proper compromise between precision and the computational effort needed to obtain f N -1 (s t ). We address this issue through two formal qualitative and quantitative questions. Let U N (s) be the cost incurred by using the RH policy of horizon length N , starting in state s: Q1 Under which conditions on the problem is it true that lim

N →∞ U N (s) = J * (s)? Q2 Given a state s and ε > 0, is it possible to compute N such that U N (s) -J * (s) < ε?
In what follows we prove the convergence of the procedure to the value of the original problem, stated as Theorem 3.1 and Theorem 3.2. The term "convergence" has to be understood in the sense that when the horizon N goes to infinity, the value obtained with the procedure approaches the value of the problem as in Q1. The preliminary observation, classical for studying RH, is that the procedure effectively implements a stationary policy. Since the controller will repeatedly act according to the state-feedback function f N -1 , we have U N = J fN-1 .

In order to improve the bounds in the next results, we consider the following additional assumption, which refers to the sequence J * n of Theorem 2.1. Assumption 2. For all s ∈ S, J * 1 (s) ≧ 0. Observe that this is the case, for instance, when the cost function r is positive. It is easy to prove that if Assumptions 1 and 2 hold, then for n ∈ N and s ∈ S, J * n (s) ≦ J * n+1 (s). Theorem 3.1. Suppose that Assumption 1 hold. Then, for all s ∈ S,

0 ≦ U N (s) -J * (s) ≦ 2M α N 1 -α ,
and in consequence

||J * -U N || ∞ ≦ 2M α N 1 -α .
If in addition Assumption 2 holds,

||J * -ŨN || ∞ ≦ M α N 1 -α .
Proof. This result is a corollary of Theorem 3.3, taking ε = 0. Indeed, in that case J = J * N -1

and

T f J = T J * N -1 = J * N , which means that fN-1 = f N -1 and ŨN = U N . Theorem 3.2. Let J * n be the sequence of functions defined in Theorem 2.1, part (b). Then, if ||J * N -J * N -1 || ∞ ≦ ε, then the RH policy f N is 2αε 1-α -optimal. That is, ||J * -U N || ∞ ≦ 2αε 1 -α .
Proof. This result is a corollary of Theorem 3.4, taking ε 2 = 0.

An Approximate Rolling Horizon Procedure

Suppose now that the controller does not have exact information about the problem to be solved at RH1 in the RH procedure, but he knows or he is able to compute an approximation of that value. We are interested in implementing a procedure where this last approximation is used instead of the value function of the problem with finite horizon and estimate the error introduced.

Then, for a function J, supposed to be close in some sense to

J * N -1 , choose fN (s) ∈ arg min a∈As σ (r a (s, •) + αJ(•), s, Q a (•|s)) .
Specifically, ARH1 Choose some function J a priori near J * N -1 where J * N -1 is the N -1-stage value function.

ARH2 At iteration t, and for the current state s t , solve

min a∈As t σ (r a (s, •) + αJ(•), s t , Q a (•|s t )) .
An action fN-1 (s t ) is obtained.

ARH3 Apply a t = fN-1 (s t ).

ARH4 Observe the achieved state at time t + 1: s t+1 .

ARH5 Set s t := s t+1 and t := t + 1 and go to step ARH2.

We will note with ŨN the total discounted reward of the stationary policy fN-1 . Theorem 3.3 gives answers to questions Q1 and Q2 stated in this section for the sequence of successive rewards ŨN . We begin with a lemma of general character. Lemma 3.1. Suppose that Assumption 1 holds. Let f ∈ Π stat be a stationary policy, with total discounted cost J f , v a bounded function and C a positive constant such that

v ≧ T f v -C , then, for any n ∈ N, (T f ) n v ≧ J f - Cα n 1 -α .

Inria

Proof. First of all, observe that:

T f (v -C) = σ r f + α(v -C), •, Q f = σ r f + αv -αC, •, Q f = σ r f + αv, •, Q f -αC = T f v -αC .
The third equality is an easy consequence of (5). Then, by the monotonicity of T f , we have successively:

v ≧ T f v -C T f v ≧ T f (T f v -C) = (T f ) 2 v -αC
and by recurrence, it is clear that for all t:

(T f ) t v ≧ (T f ) t+1 v -α t C .
Summing up these inequalities for t from n to m, we obtain:

(T f ) n v ≧ (T f ) m+1 v -C m t=n α t . (6)
Since T f is contractive with J f as its unique fixed point (Lemma 2.1), for any bounded function v, lim

m→∞ (T f ) m+1 v = J f .
Finally, the second term in the right-hand side of (6) converges, as m → ∞, to Cα n 1-α , and the stated bound follows.

Theorem 3.3. Suppose that Assumption 1 holds. Given J a bounded function such that for some

N ≧ 0, ||J * N -1 -J|| ∞ ≦ ε, consider a policy f ∈ Π stat such that T f J = T J. Then, 0 ≦ ŨN (s) -J * (s) ≦ 2M α N 1 -α + 2αε 1 -α ,
and in consequence

||J * -ŨN || ∞ ≦ 2M α N 1 -α + 2αε 1 -α .
If in addition Assumption 2 holds,

||J * -ŨN || ∞ ≦ M α N 1 -α + 2αε 1 -α .
Proof. As a prelude to the proof, let us first note that if r is bounded by M , the random variables Z t = r At-1 (S t-1 , S t ), which represents the gain at time t -1 by application of the Markov policy π, satisfy -M ≦ Z N ≦ M , and following the ideas in the proof of [12, Theorem 3, pp. 249-250] the next inequality holds:

ρ α 1,N (Z 1 , ..., Z N ) ≦ ρ α 1,N -1 (Z 1 , ..., Z N -1 ) + M α N -1 ,
with the notation, for t ∈ N,

ρ α 1,t (Z 1 , ..., Z t ) = ρ 1 Z 1 + αρ 2 Z 2 + α 2 ρ 3 Z 3 + ... + α t-1 ρ t-1 (Z t ) ... .
Then, for all N ∈ N the value functions of the problems with horizons N -1 and N verify

J * N -1 = inf π ρ α 1,N -1 (Z 1 , ..., Z N -1 ) ≧ inf π ρ α 1,N (Z 1 , ..., Z N ) -M α N -1 = J * N -M α N -1 . (7)
Let us start the proof using the triangular inequality

||J * -ŨN || ∞ ≦ ||J * -T J|| ∞ + ||T J -ŨN || ∞ . (8)
To bound the first term in the right-hand side of ( 8), let us observe that, by Lemma 2.1,

||T J * N -1 -T J|| ∞ ≦ α||J * N -1 -J|| ∞ ≦ αε , (9)
and also by Theorem 2.1 (c),

||J * -T J * N -1 || ∞ = ||J * -J * N || ∞ ≦ M α N 1 -α . Then ||J * -T J|| ∞ ≦ ||J * -T J * N -1 || ∞ + ||T J * N -1 -T J|| ∞ ≦ M α N 1 -α + αε . (10)
For the second term in the right-hand side of (8), we use recursively the hypothesis made on function J, together with Inequalities (7) and [START_REF] Puterman | Markov Decision Processes[END_REF]. We obtain

J ≧ J * N -1 -ε ≧ J * N -(ε + M α N -1 ) ≧ (T J) -(αε + ε + M α N -1 ) , or, since T J = T f J: J ≧ T f J -(αε + ε + M α N -1 ) . (11)
At this point we can use Lemma 3.1, with n = 1 and

C = (α + 1)ε + M α N -1 , to get ŨN -(T J) ≦ ((α + 1)ε + M α N -1 ) α 1 -α = αε(1 + α) + M α N 1 -α .
Finally,

ŨN -J * = ŨN -(T J) + (T J) -J * ≦ αε(1 + α) 1 -α + M α N 1 -α + M α N 1 -α + αε = 2M α N 1 -α + 2αε 1 -α ,
Inria which is the stated bound. If in addition Assumption 2 holds, the proof can be made using the inequality

J ≧ (T f J) -(αε + ε)
to arrive at:

ŨN -(T J) ≦ αε(1 + α) 1 -α , (12)
and instead of [START_REF] Ruszczyński | Optimization of Convex Risk Functions[END_REF], and the bound becomes

||J * -ŨN || ∞ ≦ M α N 1 -α + 2αε 1 -α .
Theorem 3.4. Suppose that Assumption 1 holds. Suppose that, for some

N , ||J * N -J * N -1 || ∞ ≦ ε 1 . Given J a bounded function such that ||J * N -1 -J|| ∞ ≦ ε 2 , consider a policy f ∈ Π stat such that T f J = T J. Then, ||J * -ŨN || ∞ ≦ 2α(ε 1 + ε 2 ) 1 -α .
Proof. Let us start with the triangular inequality

||J * -ŨN || ∞ ≦ ||J * -J * N || ∞ + ||J * N -ŨN || ∞ .
To bound the first term in the r.h.s. of this inequality, observe that, for any m ∈ N,

||J * N +m -J * N || ∞ ≦ m-1 k=0 ||J * N +k+1 -J * N +k || ∞ = m-1 k=0 ||T k+1 J * N -T k+1 J * N -1 || ∞ ≦ m-1 k=0 α k+1 ||J * N -J * N -1 || ∞ = α (1 -α m ) 1 -α ||J * N -J * N -1 || ∞ ,
and, taking limits when m → ∞,

||J * -J * N || ∞ ≦ αε 1 1 -α . ( 13
)
To bound the second term, we use the facts that T f J = T J, T f ŨN = ŨN , and T f is a contraction of modulus α. With that,

||J * N -ŨN || ∞ = ||J * N -T f ŨN || ∞ ≦ ||J * N -T f J|| ∞ + ||T f J -T f ŨN || ∞ = ||T J * N -1 -T J|| ∞ + α||J -ŨN || ∞ ≦ α ε 1 + α (||J -J * N -1 || ∞ + ||J * N -1 -J * N || ∞ + ||J * N -ŨN || ∞ ) ≦ αε 2 + α(ε 2 + ε 1 ) + α ||J * N -ŨN || ∞ . which implies (1 -α)||J * N -ŨN || ∞ ≦ 2αε 2 + αε 1 , or ||J * N -ŨN || ∞ ≦ 2αε 2 + αε 1 1 -α . (14)
Finally, by ( 13) and ( 14),

||J * -ŨN || ∞ ≦ 2α(ε 1 + ε 2 ) 1 -α .
Remark 3.1. The statement of Theorem 3.3 can be proved combining Theorems 3.4 and 2.1(c).

In spite of that, we include the proofs of both results, since in any case, they make use of different properties of the dynamic programming operator.

In the proof of Theorem 3.3 the monotonicity property is prevalent. On the other hand, the contractivity property is fundamental in the proof of Theorem 3.4.

Besides, as consequence of Inequality [START_REF] Ruszczyński | Risk-averse dynamic programming for Markov decision processes[END_REF] in the proof of Theorem 3.3, with ε = 0, we obtain an order relation, under Assumption 2, between the RH value U N and J * N , the value of the N -horizon problem, which can not be obtained as a consequence of Theorem 3.4 nor of its proof.

Structural Approximations

In the context of stochastic control problems, the controller has to take decisions, based on the knowledge of the current state, but without the certainty of the dynamics of the system, which will be governed by distributions of probabilities on the space of states, known a priori for him.

In many situations, the controller may not have the exact information on these probability distributions because they are known only through some statistical method, for example. This lack of information could stem from imprecisions on the measure of quantities involved, and it could be improved by some investment of effort or money. Assessing whether this spending is necessary or excessive is an interesting practical issue. In these cases then, there arises the necessity of having bounds to the errors involved when choosing actions (and then policies) considering the inexact probability distributions. Other model parameters may have also imprecisions. It is also interesting to study the errors produced by such uncertainties.

Through this section, we shall work with approximating stochastic control models of the form

M n := (S, A, {A s : s ∈ S}, {Q a n (•|s) : s ∈ S, a ∈ A s }, r n , α n ) , (15)
all differing in the transition probabilities, the reward functions and the discount factors.

In what follows we are interested in approximating the infinite horizon problem defined in (1) through suitable approximating problems.

For the models (15) we define, given a policy f ∈ Π stat , the corresponding dynamic programming operator

(T f n v)(s) = σ r f n (s, •) + α n v(•), s, Q f n (•|s)
, for s ∈ S, and we will denote with J f n the unique bounded solution (Lemma 2.1) of the equation

T f n v = v . ( 16
)

Inria

Let the values of the models M n be defined as

J n = inf π∈Π J π n .
Tidball and Altman in [START_REF] Tidball | Approximations in Dynamic Zero-Sum Games[END_REF], in the context of zero sum games, tried to answer the following questions:

1. Do the sequence of values of the approximating models M n converges to the value of the original problem M? If so, is it possible to establish bounds on the error from the approximations?

2. Do optimal (or almost optimal) policies of the approximating models M n converge, in some sense, to optimal policies of the limit problem M?

3. Given an optimal policy of the model M n , will it be an almost optimal for the limit problem if n is sufficiently large?

4. Conversely, given an optimal policy for M, will it be almost optimal for M n for all n sufficiently large?

To answer to these questions, the next Key Theorem is proved in the same paper ([13, Theorem 2.1., p. 312]). We enunciate here a simpler version, adapted to our case. (b) For any ε ′ > ε, there exist N such that π * n is ε ′ -optimal for the limit problem, for n ≧ N .

(c) Let π * be ε-optimal for the limit problem. Then for all ε ′ > ε, there exist N (ε ′ ) such that π * is an ε ′ -optimal policy for all n ≧ N (ε ′ ).

We can now make precise the sense in which M n approximates M.

Assumption 3.

(a) The sequence of stochastic kernels Q n verifies

sup v:||v||∞≦1 |σ (v, s, Q a (•|s)) -σ (v, s, Q a n (•|s)) | → 0 uniformly on K;
(b) The sequence of discount factors α n verifies α n → α;

(c) The functions r n are bounded on K × S. That is, there exist constants M n > 0, such that, for (s, a) ∈ K, z ∈ S, |r a (s, z)| ≦ M n ;

(d) The sequence r n satisfies r n → r uniformly on K × S. Consequently, the constants M n and M can be chosen verifying M n → M .

Remark 4.1. In the risk neutral context, the sets A(s, Q) reduce to {Q} and Assumption 3 (a) expresses the uniform convergence in total variation norm of the sequence of kernels Q n to the kernel Q.

The proof of the next lemma is similar to Theorem 2.1 (a). We include that statement for the sake of completeness. Lemma 4.1. Under Assumption 1 (c), Assumption 1 (e), M being the bound on r and Assumption 3 (c), for any stationary policy f ∈ Π stat , the cost in the model M, J f , defined by [START_REF] Cavazos-Cadena | Finite-state approximations for denumerable state discounted Markov decision processes[END_REF], and the cost in the models M n , J f n , defined by ( 16), satisfy:

||J f || ∞ ≦ M 1 -α , ||J f n || ∞ ≦ M n 1 -α n .
Theorem 4.2. Consider the models M n defined in ( 15) and M like in [START_REF] Altman | Constrained Markov Decision processes[END_REF]. Assume that Assumption 1 holds. Let us define, for any stationary policy f ∈ Π stat , the reward for the limit model M, J f , by [START_REF] Cavazos-Cadena | Finite-state approximations for denumerable state discounted Markov decision processes[END_REF], and for the approximating one M n , J f n , by ( 16). Then, for any f ∈ Π stat :

||J f -J f n || ∞ ≦ ε := ||r f -r f n || ∞ 1 -α + M (1 -α) 2 sup s∈S sup v:||v||∞≦1 |σ v, s, Q f (•|s) -σ v, s, Q f n (•|s) | + M n (1 -α n )(1 -α) |α -α n |.
and then

||J * -J n || ∞ ≦ ε .
If Assumption 3 holds in addition, then J f n converges uniformly to J f as n → ∞, and the hypotheses of the Key Theorem hold.

Proof. If v is a bounded function with C a bound and Q is a transition kernel, in view of the representation [START_REF] Vecchia | Rolling horizon procedures in Semi-Markov Games: The Discounted Case[END_REF]

, σ v, s, Q f,g (•|s) ≦ σ C, s, Q f,g (•|s) = C. Now, for a fixed stationary policy f ∈ Π stat , for s ∈ S, |J f (s) -J f n (s)| = σ r f + αJ f , s, Q f (•|s) -σ r f n + α n J f n , s, Q f n (•|s)
Introducing the intermediate terms:

|J f (s) -J f n (s)| ≦ |σ r f + αJ f , s, Q f (•|s) -σ r f + αJ f , s, Q f n (•|s) | +|σ r f + αJ f , s, Q f n (•|s) -σ r f + αJ f n , s, Q f n (•|s) | +|σ r f + αJ f n , s, Q f n (•|s) -σ r f + α n J f n , s, Q f n (•|s) | +|σ r f + α n J f n , s, Q f n (•|s) -σ r f n + α n J f n , s, Q f n (•|s) | = ∆ 1 n + ∆ 2 n + ∆ 3 n + ∆ 4 n .
Now we bound each term in the last expression. First, Lemma 4.1 implies:

||r f + αJ f || ∞ ≤ M + αM 1 -α = M 1 -α . Inria ∆ 1 n ≦ M 1 -α σ M 1 -α -1 r f + αJ f , s, Q f (•|s) -σ M 1 -α -1 r f + αJ f , s, Q f n (•|s) ≦ M 1 -α sup v:||v||∞≦1 |σ v, s, Q f (•|s) -σ v, s, Q f n (•|s) | . Next, observe that | sup µ f 1 (µ)-sup µ f 2 (µ)| = max{sup µ f 1 (µ)-sup µ f 2 (µ), sup µ f 2 (µ)-sup µ f 1 (µ)} ≤ max{sup µ (f 1 -f 2 )(µ), sup µ (f 2 -f 1 )(µ)} ≤ sup µ |(f 1 -f 2 )(µ)|. Accordingly, ∆ 2 n = sup µ∈A(s,Q f n ) S (r f (z) + αJ f (z))dµ(z) - sup µ∈A(s,Q f n ) S (r f (z) + αJ f n (z))dµ(z) ≦ sup µ∈A(s,Q f n ) S (r f (z) + αJ f (z)) -(r f (z) + αJ f n (z)) dµ(z) = α sup µ∈A(s,Q f n ) S (J f (z) -J f n (z))dµ(z) ≦ α sup µ∈A(s,Q f n ) S |J f (z) -J f n (z)|dµ(z) ≦ α||J f -J f n || ∞ .
With the bound given by Lemma 4.1, ||J f n || ∞ ≦ Mn 1-αn :

∆ 3 n = sup µ∈A(s,Q f n ) S (r f (z) + αJ f n (z))dµ(z) - sup µ∈A(s,Q f n ) S (r f (z) + α n J f n (z))dµ(z) ≦ sup µ∈A(s,Q f n ) S (r f (z) + αJ f n (z)) -(r f (z) + α n J f n (z)) dµ(z) = sup µ∈A(s,Q f n ) S (α -α n )J f n (z)dµ(z) ≦ |α -α n | sup µ∈A(s,Q f n ) S |J f n (z)|dµ(z) ≦ M n 1 -α n |α -α n | .
Finally,

∆ 4 n = sup µ∈A(s,Q f n ) S (r f (z) + α n J f n (z))dµ(z) - sup µ∈A(s,Q f n ) S (r f n (z) + α n J f n (z))dµ(z) ≦ sup µ∈A(s,Q f n ) S (r f (z) + α n J f n (z)) -(r f n (z) + α n J f n (z)) dµ(z) = sup µ∈A(s,Q f n ) S (r f (z) -r f n (z))dµ(z) ≦ sup µ∈A(s,Q f n ) S |r f (z) -r f n (z)|dµ(z) ≦ ||r f -r f n || ∞ .
In consequence,

||J f -J f n || ∞ ≦ ||r f -r f n || ∞ + M 1 -α sup s∈S sup v:||v||∞≦1 |σ v, s, Q f (•|s) -σ v, s, Q f n (•|s) | + α||J f -J f n || ∞ + M n 1 -α n |α -α n | ,
which gives the stated bound.

Let us observe that if Assumption 3 holds, this bound tends to zero uniformly, and so does J f -J J n .

Remark 4.2. If costs r(•) in model M do not depend on the final state of the transition, then for any f , σ(r f + g, s, m) = r f + σ(g, s, m). The bound for ∆ 1 n is improved as:

∆ 1 n = σ r f + αJ f , s, Q f (•|s) -σ r f + αJ f , s, Q f n (•|s) = (r f + ασ J f , s, Q f (•|s) ) -(r f + ασ J f , s, Q f n (•|s) ) = α σ J f , s, Q f (•|s) ) -σ J f , s, Q f n (•|s) ) ≦ M α 1 -α σ M 1 -α -1 J f , s, Q f (•|s) -σ M 1 -α -1 J f , s, Q f n (•|s) ≦ M α 1 -α sup v:||v||∞≦1 |σ v, s, Q f (•|s) -σ v, s, Q f n (•|s) | .
This improved bound carries over in the bound of Theorem 4.2. Then, in the risk-neutral case (see Remark 4.1), the statement corresponds to the MDP version of [START_REF] Vecchia | Structural approximations in discounted Semi-Markov Games[END_REF]Theorem 2]. In this risk-neutral case, and when costs do depend on the resulting state, it is standard to transform the problem into one where the cost depends only on the original state, by taking expectations on the future state [9, Chapter 2, p. 20].

Example

As an example of application of the RH approximation, let us consider a modification of the device maintenance problem presented in [START_REF] Ruszczyński | Risk-averse dynamic programming for Markov decision processes[END_REF]Example 1,p. 238].

In this case, the state of a device represents its condition. We shall assume four states, S = {s 1 , s 2 , s 3 , s 4 } with s 1 ="faultless" , s 3 ="irreparable and not insured", s 4 ="irreparable and insured" and s 2 an intermediate state between "faultless" and "irreparable".

The actions available at the different states consist on the maintenance strategies and the possibilities of purchase an insurance that reduces the cost of replacing the device when it reaches Inria the "irreparable" state. More precisely, the set of actions is A = { a 1 ="do not make maintenance tasks and do not buy insurance", a 2 ="perform maintenance and do not buy insurance", a 3 ="do not make maintenance tasks and buy insurance", a 4 ="perform maintenance and buy insurance" , a 5 ="replace item" } .

According to the model, since at the state s 1 the action "replace" is meaningful and at states s 3 , s 4 "perform maintenance" and "do not make maintenance tasks" are not options, the sets of corresponding available actions are

A s1 = A \ {a 5 }, A s2 = A, A s3 = A s4 = {a 5 } .
The non-zero transition probabilities and costs are given by In this example we evaluate the performance of strategies through the mean deviation measure and using the expression of σ given in [12, Example 4, Equation (16), p. 244]:

Q a1 (s 1 |s 1 ) = Q a3 (s 1 |s 1 ) = Q a1 (s 3 |s 1 ) = Q a3 (s 4 |s 1 ) = 0.1 Q a1 (s 2 |s 1 ) = Q a3 (s 2 |s 1 ) = 0.8 , Q a1 (s 2 |s 2 ) = Q a3 (s 2 |s 2 ) = 0.6 Q a1 (s 3 |s 2 ) = Q a3 (s 4 |s 2 ) = 0.4 , Q a2 (s 1 |s 1 ) = Q a4 (s 1 |s 1 ) = 0.25 Q a2 (s 2 |s 1 ) = Q a4 (s 2 |s 1 ) = Q a2 (s 2 |s 2 ) = Q a4 (s 2 |s 2 ) = 0.7 Q a2 (s 1 |s 2 ) = Q a4 (s 1 |s 2 ) = 0.1 , Q a2 (s 3 |s 1 ) = Q a4 (s 4 |s 1 ) = 0.05 Q a2 (s 3 |s 2 ) = Q a4 (s 4 |s 2 ) = 0.2 , Q a5 (s 1 |s 3 ) = Q a5 (s 1 |s 4 ) = 1 , r a2 (s 1 ) = r a2 (s 2 ) = 10 , r a3 (s 1 ) = 20 , r a4 (s 1 ) = 30
σ(v, x, m) = < v, m > + κ(x) < ((v-< v, m >) + ) 2 , m > 1/2 .
where κ ∈ [0, 1] is a parameter modeling the risk attitude of the controller, and (y) + denotes max{y, 0}. With it, the dynamic programming operator takes the form:

(T v)(s) = min a∈As r a (s) +α     z∈S v(z)Q a (z|s) + κ    w∈S   v(w) - z∈S v(z)Q a (z|s) +   2 Q a (w|s)    1 2           
By application of the RH procedure with horizon 100 to the problem with discount α = 0.9, we obtain four different strategies, depending on the risk parameter κ (assumed to be the same for all states).

For κ = 0 and κ = 0.046, the strategy obtained is (a 1 , a 2 , a 5 , a 5 ), consisting on not doing anything when the device is new, performing maintenance in the intermediate state, and not buying insurance in any case.

For κ = 0.047, κ = 0.562, the strategy is (a 2 , a 2 , a 5 , a 5 ), consisting in performing the maintenance at the new and the intermediate state, and again not buying the insurance.

For κ = 0.563, κ = 0.567, the strategy is (a 2 , a 3 , a 5 , a 5 ), which states: performing maintenance without buying the insurance in new devices, and buying the insurance at the intermediate state, without performing any maintenance.

Finally, for κ = 0.568, κ = 1, the RH strategy is (a 3 , a 3 , a 5 , a 5 ): do not do anything but buy an insurance, when the state is not irreparable.

We calculate the error bounds in the RH procedure provided by Theorems 3.3 (for positive costs, applied with ε = 0) and 3.4 (with ε 2 = 0):

||J * -J N || ∞ ≦ B1 := 200 × 0.9 N 1 -0.9 , ||J * -J N || ∞ ≦ B2 := 2 × 0.9 × ||J * N -J * N -1 || ∞ 1 -0.9 ,
as well as the relative error bounds

RB1 = B 1 min J * , RB2 = B 2 min J *

Inria

Since the bound given by Theorem 3.3 does not depend on the parameter κ, values B1 coincides for the same values of N , but is not the case for RB1, which depends on the optimal value J * .

In this instance of the problem, the RH policies converge to the optimal ones after 3 iterations for the case κ = 0.01 and after 4 iterations for the values κ = 0.5 and κ = 0.99.

From these experiments, we draw some preliminary conclusions for approximate rolling horizon:

• The numerical values obtained from Theorems 3.3 and 3.4 are disappointingly large, however the relative values are more reasonable.

The bound obtained from Theorem 3.4 is better: this illustrates the benefit of using successive steps of Value Iteration instead of only the last one.

• As in standard risk-neutral dynamic programming, the policies appear to converge much faster than values, and values much faster than what bounds predict.

The first fact validates in practice the use of Rolling Horizon with a relatively small horizon.

The second one suggests that developing bounds that take into account some of the problem structure is an interesting challenge.

Concerning structural approximations, the practical issue is currently the way to evaluate numerically (or bound efficiently) the "distance" between two transition kernels:

sup v:||v||∞≦1 σ v, s, Q f (•|s) -σ v, s, Q f n (•|s) .

Concluding Remarks

Through this work we have dealt with risk-averse MDP with discounted cost, studying the performance of two different ways of approximations of value functions and optimal policies. In Section 3, we have studied the performance of the Rolling Horizon procedure and of an Approximate Rolling Horizon procedure, the former being a particular case of the latter. We have proved the uniform geometrical convergence of the values related to the RH procedure to the optimal cost function. For the ARH we have obtained the same convergence bound plus a constant term in the horizon, which can be improved with the initial approximation.

In Section 4 we have studied approximations of the value function of the infinite-horizon riskaverse MDP and their optimal policies, by considering it as a limit of a sequence of approximating models. The approximating models are obtained by perturbing transition probabilities, cost functions and discount factors. The perturbation is measured by supremum norms for functions and parameters, and we introduce a metric for perturbation of operators. We obtain a bound in terms of these perturbations, which implies the uniform convergence of values when parameters are converging uniformly to the original ones.

Finally, in Section 5 we have provided a numerical example and raised some issues for future research.

Theorem 2 . 1 .

 21 Proof. See[12, Lemma 1, p. 252], [12, Lemma 2, p. 252] and [12, Lemma 4, p. 253]. Suppose that Assumption 1 holds. Then

(

Theorem 4 . 1 .

 41 Key Theorem Assume that for the sequence of problems {M n } and the original problem M it is verified that lim n→∞ J π n -J π = 0, uniformly in π ∈ Π . Then (a) lim n→∞ J n = J * .

r

  a3 (s 2 ) = 40 , r a4 (s 2 ) = 55 , r a5 (s 3 ) = 200 , r a5 (s 4 ) = 100 .

  in this example for horizons N = 20, N = 35 and N = 50 and for the risk parameters κ = 0.01, κ = 0.5 and κ = 0.99. κ = 0.01 N = 20 N = 35 N = 50 B1 243

Table 1 :

 1 Error bounds for parameter κ = 0.01. min J * = 321.345.

		.153	50.063	10.308
	B2 110.411	22.733	4.680
	RB1	0.757	0.156	0.032
	RB2	0.344	0.071	0.015
	κ = 0.5 N = 20 N = 35 N = 50
	B1 243.153	50.063	10.308
	B2 158.974	32.731	6.739
	RB1	0.513	0.106	0.022
	RB2	0.335	0.069	0.014

Table 2 :

 2 Error bounds for parameter κ = 0.5. min J * = 474.346.

	κ = 0.99 N = 20 N = 35 N = 50
	B1 243.153	50.063	10.308
	B2 167.795	34.538	7.111
	RB1	0.476	0.098	0.020
	RB2	0.328	0.068	0.014

Table 3 :

 3 Error bounds for parameter κ = 0.99. min J * = 511.081.

RR n°8393

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgements E. Della Vecchia wishes to thank the help and the encouragements of Andrzej Ruszczyński and Darinka Dentcheva during the Workshop of Stochastic Optimization organized at the Universidad de Chile in December 2012.


Shuguo Zhuo

Zhibo Wang
email: wangzhi@iipc.zju.edu.cn

Ye-Qiong Song
email: song@loria.fr

Luis Almeida

iQueue-MAC: A Traffic Adaptive duty-cycled MAC Protocol With Dynamic Slot Allocation

Duty-cycling technique has been widely adopted in MAC protocols for wireless sensor networks to conserve energy. However, low duty-cycle also leads to limited throughput in most of existing solutions. In this paper, we propose iQueue-MAC to provide immediate yet energy-efficient throughput enhancement for dealing with burst or heavy traffic. Combined with CSMA/CA, iQueue-MAC makes use of queue length of each sensor node and allocates suitable TDMA slots to them for packets transmission. During light traffic period, no extra slots will be allocated; iQueue-MAC acts like other low duty-cycle MACs to conserve power. While in burst or heavy traffic period, iQueue-MAC senses the build up of packet queues and dynamically schedules adequate number of slots for packet transmission. We have implemented iQueue-MAC on STM32W108 chips that offer IEEE 802.15.4 standard communication. We set up several realworld experimental scenarios, including a 46 nodes multi-hop test-bed for simulating a general application, and conducted numerous experiments to evaluate iQueue-MAC, in comparison with other traffic adaptive duty-cycle protocols, such as multichannel version RI-MAC and CoSenS. Results clearly show that iQueue-MAC outperforms multi-channel version of RI-MAC and CoSenS in terms of packet delay and throughput.

I. INTRODUCTION

In wireless sensor networks (WSN), keeping nodes in low duty-cycle, i.e., interleaving very short active and long sleeping periods, is the most efficient way to save energy, thus prolonging network lifetime. However, there is a cost to pay in both low network throughput and extra packet delay, since the network nominal data rate is roughly decreased by the dutycycle factor and a packet should wait until the next forwarder wakes up to transmit it. How to provide high throughput and short delay, while still keeping low power consumption (so low duty-cycle), is the main challenge of the current WSN MAC protocol research. In fact, from typical application point of view, in addition to low rate periodic traffic, burst traffic is triggered following event detections. So an ideal MAC protocol should be able to self-adapt its offered bandwidth to cope with the dynamic traffic load, so that the energy is only used for carrying the application traffic whenever needed.

Lots of low power traffic adaptive MAC protocols have been proposed [START_REF] Huang | The evolution of mac protocols in wireless sensor networks: a survey[END_REF]. For instance, in contention-based WSN, for better dealing with the collisions during burst traffic period, Strawman MAC protocol [START_REF] Österlind | Strawman: resolving collisions in bursty low-power wireless networks[END_REF], upon detection of collisions at the receiver, uses a kind of black burst mechanism [START_REF] Sobrinho | Quality-of-service in ad hoc carrier sense multiple access wireless networks. Selected Areas in Communications[END_REF] for better resolving collisions, instead of using random backoff of CSMA. Although Strawman MAC improves the throughput to a certain extent (and does better than RI-MAC [START_REF] Sun | RI-MAC: a receiver-initiated asynchronous duty cycle MAC protocol for dynamic traffic loads in wireless sensor networks[END_REF]), it still introduces overheads and additional delays. So there is space for improvement. To radically resolve this problem, the most efficient way is to only keep CSMA in light traffic for its flexibility, and use TDMA during heavy or burst traffic load periods for solving the inherent drawback of the contentionbased MAC, achieving thus high throughput. The first tentative of hybrid CSMA/TDMA for duty-cycled WSN includes IEEE 802.15.4 beacon-enabled mode (CSMA during CAP and GTS during CFP) and Z-MAC [START_REF] Rhee | Z-MAC: a hybrid MAC for wireless sensor networks[END_REF]. But the basic design approach of Z-MAC is essentially TDMA-based. CSMA is only used when the slot owner has no data to transmit (slot stealing). So only the slot owners can have their pre-allocated bandwidth guarantee. Burst traffic of the other nodes still cannot be efficiently carried. To deal with this problem, adaptive time slot assignment is the best way. TRAMA [START_REF] Rajendran | Energyefficient, collision-free medium access control for wireless sensor networks[END_REF] and AI-MAC [START_REF] Chatterjea | AI-LMAC: An adaptive, information-centric and lightweight MAC protocol for wireless sensor networks[END_REF] follow this idea. But TRAMA suffers from time slot spatial reuse problem and has high overhead for executing the adaptive election algorithm. AI-MAC only relies on the sink initiated query in a tree topology.

In this paper, we present iQueue-MAC, which runs in CSMA in light load. When load increases, the senders' queue length will be used to dynamically allocate time slots to the senders (TDMA). The whole network is composed of two kinds of nodes: simple nodes (e.g. RFD of IEEE 802. 15.4) and routers (FFD of IEEE 802. [START_REF] Sun | RI-MAC: a receiver-initiated asynchronous duty cycle MAC protocol for dynamic traffic loads in wireless sensor networks[END_REF].4, such as coordinators). Simple nodes only wakeup when they have data to send, so their energy consumption is minimized. Each simple node is associated to a router. A router is responsible of collecting the data packets of the simple nodes that are associated to it. The design of iQueue-MAC protocol follows five key features: using queue-length piggybacking as accurate load information without additional overhead, dynamically allocating TDMA time slots to simple nodes (data senders) for allowing high throughput, using LPL (as X-MAC [START_REF] Polastre | Versatile low power media access for wireless sensor networks[END_REF]) to "synchronize" neighboring routers, sending as a burst the queued packets (as T-MAC [START_REF] Van Dam | An adaptive energy-efficient MAC protocol for wireless sensor networks[END_REF]) from router to router for shortening the channel access delay, and using multi-channels (local channel to a router, and common channel between routers) for exploiting both time and spatial reuse. This results in a highly efficient MAC protocol that we have implemented on STM32W108 chips that offer IEEE 802.15.4 standard communication. For comparison, we also implemented the often referenced RI-MAC on the same platform, as well as CoSenS [START_REF] Nefzi | QoS for wireless sensor networks: Enabling service differentiation at the MAC sub-layer using CoSenS[END_REF], which was our previously proposed traffic adaptive protocol. Extensive measurements show its outstanding throughput performance for dealing with burst traffic, while it can still maintain low duty-cycle under light traffic load. Moreover, its traffic adaptation is faster than the existing protocols.

II. RELATED WORK

A lot of protocols have been proposed for variable traffic in WSNs. RI-MAC [START_REF] Sun | RI-MAC: a receiver-initiated asynchronous duty cycle MAC protocol for dynamic traffic loads in wireless sensor networks[END_REF] is a receiver-initiated duty-cycled MAC that aims at handling variable traffic. Receiver nodes frequently wake up and send out probing beacons for polling possible incoming data without using LPL preamble packets. Thus, compared to LPL, RI-MAC enhances throughput by reducing medium occupation. However, RI-MAC suffers from packet collisions when there are multiple senders. Thus throughput is bounded during bursts or heavy traffic. To this end, Strawman MAC [START_REF] Österlind | Strawman: resolving collisions in bursty low-power wireless networks[END_REF] schedules transmissions when collisions are detected using extra Collision packets. On the other hand, iQueue-MAC uses a hybrid CSMA/TDMA mechanism to allocate more slots when needed and transform most of the transmission from the random backoff CSMA period into the slotted TDMA period. Z-MAC [START_REF] Rhee | Z-MAC: a hybrid MAC for wireless sensor networks[END_REF] also adopts a hybrid CSMA/TDMA mechanism, but using a fixed TDMA schedule. [START_REF] Huang | RC-MAC: A receiver-centric medium access control protocol for wireless sensor networks[END_REF] uses a scheduling method to reduce collisions like iQueue-MAC. RC-MAC schedules packet transmissions by ordering the next packet sender using ACK piggybacking. However, how to allocate bandwidth among nodes is not specified in RC-MAC. iQueue-MAC automatically distinguishes the bandwidth demands by reading the sender queue length piggybacked on the data, and enhance the throughput rapidly by allocating extra transmission slots. To support burst packet transmission, BurstMAC [START_REF] Ringwald | BurstMAC-An efficient MAC protocol for correlated traffic bursts[END_REF] also allocates slots for burst transmissions. Senders in BurstMAC apply for slots using specific polling packets. However, BurstMAC requires global synchronization, and the maximum number of twohop neighbors is also bonded, no more than the number of available radio channels. iQueue-MAC requires only local beacon synchronization and does not limit the number of neighbor senders. Moreover, by piggybacking, iQueue-MAC realizes resource inquiring and slots allocation implicitly in a simple and effective way.

RC-MAC

Another popular solution to adjust bandwidth for variable traffic is to prolong the active period in a frame cycle. Max-MAC [START_REF] Hurni | Maxmac: A maximally traffic-adaptive mac protocol for wireless sensor networks[END_REF] switches the duty-cycle based on threshold values. When a node senses that the packet receiving rate has gone above a defined threshold value, it doubles its duty-cycle for absorbing more possible traffic. Compared to MaxMAC, iQueue-MAC reacts to traffic variation much more rapidly. A router in iQueue-MAC allocates slots to intensive senders at the start of packet queues build up.

pTunes [START_REF] Zimmerling | pTunes: Runtime parameter adaptation for low-power MAC protocols[END_REF] is a framework that adapts the MAC protocol parameters at runtime for maintaining network performance metrics. pTunes treats MAC parameters tuning as a multiobjective optimization problem and builds up a model of the network. However finding an accurate model itself for the network is not easy, while pTunes still requires extra operations like information collection and dissemination for the optimization which may induce extra overhead.

In our early work, CoSenS [START_REF] Nefzi | QoS for wireless sensor networks: Enabling service differentiation at the MAC sub-layer using CoSenS[END_REF], a collecting then sending burst protocol was proposed to deal with traffic adaptation. We distinguish simple nodes from routers. A router operates similarly as IEEE 802.15.4 beacon-enabled mode. It dynamically adjusts its data-collecting period (active CSMA period) according to the estimated traffic load. The estimation algorithm is based on the weighted exponential average (similar to that used for RTT in TCP protocol). Moreover, burst transmission mode (similar to T-MAC) is used to transmit packets from router to router. Compared to iQueue-MAC, its traffic estimation algorithm only gives average load, while iQueue-MAC gives exact queue length. Queue-MAC [START_REF] Zhuo | Queue-MAC: A queue-length aware hybrid CSMA/TDMA MAC protocol for providing dynamic adaptation to traffic and duty-cycle variation in wireless sensor networks[END_REF], our former work was proposed to tackle the limited throughput issue in duty-cycled MAC protocols. We have proved that Queue-MAC effectively provides sufficient throughput in a wide range of traffic loads, especially in critical burst periods. The first implementation of Queue-MAC showed a very interesting potential but some aspects have not been taken into account. Namely, multi hop forwarding has not been integrated.

In this paper, we propose iQueue-MAC, the improved Queue-MAC, using the main mechanism of Queue-MAC while integrating the scheme of "first collect then send burst" of CoSenS. Designed for multi-hop WSNs, iQueue-MAC is an energy-efficient solution for providing immediate and sufficient bandwidth in varied traffic loads, as we will further detail in following sections.

III. IQUEUE-MAC DESIGN

iQueue-MAC mainly targets data collecting networks that often adopt tree routing structure (but not limited to). Devices in the network are classified as routers and simple nodes. We first present the basic idea of iQueue-MAC and then elaborate on different aspects of the design. Figure 1 shows the basic idea of iQueue-MAC. Most existing duty-cycle MACs schedule an access window, the contention period (CP) in Figure 1, in the superframe cycle for simple nodes to transmit their packets [16][17]. When traffic grows, existing solutions prolong the CP period to transmit more data (method (1) in Figure 1). However, as traffic loads may vary, it is difficult for the transmitter to optimally determine the length of the CP period, and also difficult for the receiver to determine how long it should stay awake. Moreover, as traffic loads increase, contention becomes more and more serious as multiple senders may compete for accessing the channel at the same time. Similarly, a pure TDMA with fixed time slots is also not suitable for traffic adaptive network as it wastes energy for idle-listing in low traffic situation, and suffers large delay for data transmission in heavy traffic situation.

A. Basic Idea

By leveraging the advantages of CSMA and TDMA, iQueue-MAC integrates a variable TDMA period and a CSMA period for energy efficient and traffic adaptive data transmission. The basic idea of iQueue-MAC is shown in Figure 1. Instead of simply prolonging the CP, iQueue-MAC allocates an extra variable TDMA period (vTDMA) within the inactive period to enhance throughput. Simple nodes first apply in CP for extra transmission slots if they have pending packets. Then a router allocates requested number of slots to those senders in the vTDMA period. To realize this in an energy-efficient way, a sender node piggybacks its queue length value onto every data packet. The router checks the queue length information upon receiving a data packet. If the queue length value is nonzero, the router allocates the corresponding slots to the specific sender in the next cycle. In this way, iQueue-MAC dispatches packets transmissions in the TDMA phase as soon as packet queuing starts to build up, leading to short queue length and short packet delay. Moreover, iQueue-MAC has high energyefficiency by transforming most of the communication into a slot-organized TDMA round.

In the following, we will elaborate on the key issues of designing iQueue-MAC: packet modification, the superframe structure and slot allocation.

B. Packet Modification

To enable slots allocation, we slightly modify the packet structure at the MAC layer. As shown in Figure 2, a one byte field called queue indicator is set as the first byte of the packet payload without violating the existing IEEE 802.15.4 standard [START_REF]Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (LR-WPANs)[END_REF].

MAC HEADER Packet Payload

Queue indicator

Fig. 2: Packet structure for iQueue-MAC

The value of the queue indicator equals the number of buffered packets currently in the sender's forwarding queue. By examining the value of the queue indicator, any receiver of the data packet can know how many packets the sender still holds for further transmission and thus enables accurate bandwidth allocation. For instance, node 1 has 5 packets in its queue and sends one packet to router A successfully, carrying a queue indicator of 4. After extracting the queue indicator, router A knows that node 1 has 4 packets to be sent and allocates 4 slots accordingly to node 1 to send its pending packets in the next frame cycle.

C. Superframe Structure

Routers in the network broadcast beacons independently to divide time into repeating superframes. As depicted in Figure 3, a superframe comprise beacon period, Subframe period, CP and Transmitting Period (TP). Fig. 3: Superframe structure for iQueue-MAC Subframe consists of two parts: vTDMA (variable TDMA period) and SP (Sleeping Period). The vTDMA period consists of slots allocated to node devices while SP occupies the rest of Subframe period. During SP, a router sleeps most of the time but still wakes up periodically according to a predefined wake-up interval to check for potential preamble packets from other routers (dotted lines in the SP period). When there is no traffic, Subframe consists of only SP. When traffic grows, more slots will be allocated accordingly, resulting in longer vTDMA and shorter SP. To avoid beacons from colliding with nearby routers, before a new superframe cycle begins, a router sets the Subframe duration to a random value with a predefined average S and varying between 0.5*S and 1.5*S, similar to RI-MAC.

CP follows the Subframe and works as the access window for nodes. Nodes that have pending packets contend for transmission using CSMA/CA mechanism in CP. With the piggybacked queue indicator, the role of the sent out packets in CP is twofold: on the one hand, it is a normal data packet; on the other hand, it informs the router to allocate slots for pending packets. To reduce the contention in CP, every node is restricted to send at most one packet in this period, with remaining packets kept in the queue for the following vTDMA phase. Packets that arrive in the meanwhile are held for the next superframe.

The duration of the CP period is also variable as in T-MAC [START_REF] Van Dam | An adaptive energy-efficient MAC protocol for wireless sensor networks[END_REF]. Each router adjusts its CP to cope with the end of channel activity by extending CP duration to a certain amount upon every packet reception. Theoretically, CP has a minimum length L as:

L = 2 * L cca + L CW + L data (1)
where L cca is the time for a CCA execution, L CW represents the largest contention window, and L data represents the time for an intact data packet reception (Data+ACK).

A router burst transmits collected packets to the next hop in TP using LPL (low power listening) technique [START_REF] Buettner | X-MAC: a short preamble MAC protocol for duty-cycled wireless sensor networks[END_REF] [START_REF] Polastre | Versatile low power media access for wireless sensor networks[END_REF]. When the CP ends, the router first sends out a sequence of preamble packets as in X-MAC [START_REF] Buettner | X-MAC: a short preamble MAC protocol for duty-cycled wireless sensor networks[END_REF] to inform the next hop router. The first preamble packet is sent out using CSMA for collision avoidance while other following preambles are not. Once acknowledged by preamble-ACK, the router transmits all its buffered packets to the receiver in a burst. The beacon of the next cycle strictly follows the data stream as the router still occupies the medium. In case a router collects no packets in a superframe, there will be no TP period as the router has no packet to forward. Then the router broadcast its next beacon using CSMA/CA for collision avoidance.

D. Slots Allocation

Considering an extremely light traffic case where very few nodes report data, which is also a common scenario in WSNs, the CP period can handle all the scattered packets as the traffic load is low, Also, as no slots are allocated, there is no vTDMA period in the Subframe. Both routers and nodes sleep most of the time to save power. In this way, iQueue-MAC achieves a very low idle traffic duty-cycle.

When a sudden event is detected, nodes in the surrounding area may turn into intensive senders simultaneously and cause the traffic to grow significantly. Packet queuing starts to occur due to limited throughput. And by extracting the piggybacked queue indicator byte from every received data packet, a router knows exactly how many slots should be allocated to each sender to serve the increasing traffic load.

Every router maintains two lists: an ID list recording IDs of senders that have been allocated slots, and a Slot Allocating list for recording the numbers of the allocated slots. A router assesses slots allocation upon every packet reception, removes the node's ID from ID list if the queue indicator instructs 0, or adds more slots if needed. Together with other information, the router merges the two lists into the beacon before sending it out, as shown in Figure 4. Upon receiving a beacon, a node gets synchronized with the router's new superframe and checks for allocated slots and their locations within the Subframe. If the node's ID is in the ID list, the node finds out its sequence K in the ID list for further determining the number of allocated slots N slots [K] and the starting time of its slots period T start [K] :

N slots [K] = Slot Alocation list[K]
(2)

T start [K] = Size slot * K-1 i=1 N slots [i] (3)
where Size slot is the size of a TDMA slot. Then the node sleeps until T start [K] and transmits its pending packets back to back in its allocated slots. In case that the node finds no slots are allocated to it, it continues trying to send its packet during CP. On the other hand, if the node still finds itself with pending packets at the end of its slots period, it skips the contention in CP by knowing that it should have been allocated slots in the next superframe cycle. This execution further relieves the contention in CP by ticking out an additional number of contenders.

Figure 5 shows an example run of iQueue-MAC. Both N1 and N2 have multiple data packets to send. After receiving the router's first beacon, each of them sends out one packet during the CP of the first superframe after the generation of the packets and then retreat from CP. By checking the queue indicator of the received data packet, router R schedules 3 slots for N1 and 4 slots for N2 in the next cycle. Each node waits for the second beacon that contains a schedule list, finds the allocated slots period and sends out all the scheduled packets in a burst.

Slot Allocation Strategy: Assuming that one TDMA slot is just sufficient for one single packet transmission with ACK confirm, we use a flat strategy in slots allocation: the number of allocated slots for a node is proportional to its current queue indicator value. For a given Subframe duration , the number of available slots N is bounded to a maximum value M:

N = k i=1 Slot Alocation list[i] <= M = L sub-f rame Size slot (4)
The router stops scheduling new slots once N is equal to M and k represents the number of nodes with queued packets.

Multi-channel Operation: iQueue-MAC utilizes multichannel technique in the vTDMA period to allow parallel transmissions of the scheduled packets among neighbor routers. We assume that a channel scheduling algorithm allocates non-overlapping sub-channels to different routers in a local area. The beacon contains the router's sub-channel sequence and each node switches to the defined sub-channel before transmission in the vTDMA period. After the vTDMA period, all nodes and the router switch back to the public channel, and all the other communications will be carried out on the public channel. However, as the first step of our work, in this paper, we did not try to tackle the channel allocation problem. In fact, this has been set as one goal of our future work of implementing an integrated version of iQueue-MAC. Actually, in the following implementation experiments, we predefine non-overlapping sub-channels to different routers.

E. Discussion

By using the hybrid CSMA/TDMA mechanism, we can deal with varied traffic conditions in an efficient way. When the network is with light traffic, it is sufficient to use CP to handle all the rarely generated packets. As traffic grows, iQueue-MAC enhances its throughput immediately by allocating extra slots into the Subframe period. CP actually absorbs only a small part of the traffic load and mostly acts as a signaling mechanism to inform the router to setup the following TDMA period, which will handle most of the transmissions. As almost all the slots are allocated based on queue-length requests, no slot is wasted.

Thus iQueue-MAC maintains high energy-efficiency. On the other hand, iQueue-MAC allocates slots as soon as buffering emerging, thus achieving immediate throughput enhancement and guaranteeing short packet delay.

IV. IMPLEMENTATION

We have successfully implemented iQueue-MAC on IEEE 802.15.4 standard STW32W108 chips [START_REF]Stm[END_REF], and conducted numerous experiments for intensive evaluation. For comparison, we also implemented CoSenS and RI-MAC, and extended RI-MAC with multi-channel operation. We refer to this RI-MAC implementation as RI-MAC-MC. Like iQueue-MAC, every router in RI-MAC-MC is assumed to have a non-overlapping sub-channel sequence. Except for the first beacon broadcast on the public channel, a RI-MAC-MC router guides the following communication procedure onto its sub-channel. All devices turn back to the public channel at the end of a communication cycle. As RI-MAC-MC follows the main scheme of RI-MAC, it is still a contention based protocol and does not support back to back transmissions as multiple senders may simultaneously compete for medium accessing. CoSenS does not use multichannel technique.

For iQueue-MAC and RI-MAC-MC, we assume the existence of a channel allocation algorithm at the initiating stage of the network. However, at this point we actually predefine non-overlapping sub-channels to different routers.

To explore iQueue-MAC's performance under different scenarios, we set up two sample experiments and a general one, all of them on real world test-beds. In the first sample experiment, we test the performance of the different MACs in a wide range of traffic loads, while in the second sample experiment, we measure how different MACs react to sudden traffic bursts. We simulate a real-world general application scenario with a 46 nodes test-bed in the last experiment. Key MAC parameters are shown in Table I. Data packet size is always 120 bytes, and the slot size in the experiment is set to 5ms to grant one packet transmission with ACK. An actually larger minimum CP value is used in iQueue-MAC as we found that it seems to yield the best performance in numerous experiments. Available IEEE 802.15.4 channels from channel 11th to channel 21th are used in iQueue-MAC and RI-MAC-MC.

V. EXPERIMENTAL RESULTS

A. Adapting To Varying Traffic Loads

We set up a simple test bed that contains one router and 10 simple nodes as depicted in Figure 6. Simple nodes are closely placed and each node continuously generates up to 500 data packets with Poisson random distribution and sends them to the router. The router further relays those packets to Sink Router Simple Node Fig. 6: The topology of our testbed for performance evaluation The effect of data rate on the average delay the sink node. Each experimental run lasts for 800 seconds. By varying the node data rate from 1packet/1500ms (0.08kBps) to 1packets/100ms (1.2kBps), we measured the performance of the three MACs.

Figure 7 shows the average packet delay over different traffic conditions. At the beginning, all MACs have short delay under light traffic. When the data rate exceeds 1packet/800ms, RI-MAC-MC and CoSenS start to suffer from notably increasing delay. iQueue-MAC successfully maintains low packet delay over all scenarios.

Figure 8 shows the packet reception ratio comparison of the first sample experiment. Each experimental run consists of generating 5000 packets. All MACs maintain high packet reception ratio under light traffic. When the data rate exceeds 1packet/600ms, a large number of packets are dropped in CoSenS and RI-MAC-MC due to limited throughput, as most nodes have already reached their maximum queue-length (200). When the network is with high traffic, a single inquiring beacon in RI-MAC-MC causes fierce contention as it wakes multi nodes to compete the channel simultaneously in every round, which is an inherent drawback of the protocol. We have also observed on the sniffer that packets from different nodes continuously collided with each other and the contention window got increasingly extended but still failed to mitigate the contention and retransmissions. Similar to RI-MAC-MC, CoSenS suffers from heavy retransmissions and packet loss as most of the nodes compete for transmission during the same contending period. On the contrary, iQueue-MAC succeeds in absorbing almost all the generated packets, proving that Figure 9 shows the average queue length of nodes in different MACs. iQueue-MAC succeeds in maintaining very short queue-length over all experimental scenes. That is due to the fact that iQueue-MAC suppresses queuing by allocating the corresponding slots. CoSenS and RI-MAC-MC, however, failed to provide enough bandwidth as traffic grows, resulting in substantial packet accumulation and long queue lengths, which also explain the larger delays in Figure 7 and the higher packets loss in Figure 8.

Figure 10 is about the duty-cycle that every MAC achieves. As we can see, CoSenS is less energy-efficient than iQueue-MAC and RI-MAC-MC, both of which have similar performances. For all MACs the duty-cycle drops as the data rate grows beyond 1packet/600ms. Since under high traffic load RI-MAC-MC and CoSenS drop many packets due to queue overflows, the result is a lower number of packets transmitted and thus a shorter active time. On the other hand, as higher traffic loads usually lead to longer queue lengths, iQueue-MAC arranges more slots in the vTDMA period when data rate grows. As the scheduled TDMA transmission is more efficient than contention based transmissions, iQueue-MAC

B. Reacting To Burst Traffic

We used the same test-bed as described in section 5.1 and conducted a new set of experiments to show how different MACs react to peak or burst traffic. Initially, all nodes generate packets under a low data rate of 1packet/5seconds (0.024kBps). Two bursts are set to occur at 100s and 500s respectively and both last for 50s. During the burst period, all nodes adopt a higher data rate of 5packets/second (0.6kBps). We measured key metrics along with the time.

Figure 11 shows the network average packet delay. At the beginning, all MACs have low latency. Then, when burst occurs, RI-MAC-MC and CoSenS start to suffer from sharply increasing delay. The situation continues to deteriorate until all buffered packets are dispatched. Compared to the other MACs, iQueue-MAC maintains its low latency even under the burst period. Figure 12 Figure 13 shows the measured throughput of each MAC. We clearly see that iQueue-MAC sharply enhances its throughput at the emergence of a burst period, while RI-MAC-MC and CoSenS can only provide about one fourth of the throughput of iQueue-MAC and spread over a wider period. As a result, iQueue-MAC eliminates queuing and performs much better than the other MACs. The key of the bandwidth enhancement of iQueue-MAC is highlighted in Figure 14, which is the sudden allocation of TDMA slots. As we can see, iQueue-MAC allocates large numbers of slots during the burst periods. These allocated slots contribute to higher instantaneous bandwidth and thus shorter packet delay. Compared to other solutions, iQueue-MAC uses queue length as the feedback value for taking further control actions. This allows iQueue-MAC to react much faster as it does not need to predict the traffic loads.

C. General Experiment

As depicted in Figure 15, we set up a more general testing environment for simulating a real-world multi-hop application scenario. A test-bed of 46 nodes scattered over one layer of the lab building and arranged into a 4 clusters network contains at most 4-hops transmission distance. Each cluster is placed in a lab room and contains 10 children-nodes and one router (parent) node. Data relaying paths are also fixed to factor out routing influence on experimental results. Initially, all children-nodes generate packets under a light data rate of 1packet/5seconds (0.024kBps). Then, to simulate a series of urgent events, each cluster will experience a burst period adopting a higher data rate of 2 packets/1s (0.24kBps), as shown in Table II. To evaluate a more critical scenario in the network, all children-nodes simultaneously switch to the burst state during the final burst. The whole experiment lasts for 900 seconds. experiment. RI-MAC-MC has the worst performance during each burst period and CoSenS performs better, while iQueue-MAC behaves the best. iQueue-MAC maintains low packet delay over the whole experiment. Figure 17 shows the buffering situations with all MACs. Again, iQueue-MAC succeeds in maintaining much shorter queue lengths than other MACs. This is achieved since iQueue-MAC allocates a sufficient number of slots to senders as soon as packets queuing is detected. Conversely, CoSenS and RI-MAC-MC lead to relatively longer queues during the burst periods as they react slower to the traffic changes.

Figure 18 shows that iQueue-MAC provides faster and stronger throughput enhancement when burst traffic occurs. Higher throughput leads to faster packets dispatching thus iQueue-MAC also achieves shorter delay and queue length as depicted in Figure 16 and Figure 17, respectively. On the other hand, the slower reactions in throughput adaptation in CoSenS and RI-MAC-MC result in worse performance. In this paper, we presented iQueue-MAC, a MAC protocol for WSNs that efficiently manages the RF wireless medium resource under varying traffic conditions. This management combines CSMA and TDMA types of medium access control, the former for light traffic conditions and the latter for heavier traffic. The crux of the protocol is an accurate and fast assessment of the instantaneous communication requirements that promptly detects packets queuing in the senders and allows the router to schedule sufficient TDMA slots. Such assessment is carried out piggybacking a queue indicator onto all data packets, with slots requests and allocation done implicitly. Packets queuing is mitigated by allocating slots right upon queuing detection.

Compared to other solutions, iQueue-MAC has the following advantages: first, iQueue-MAC provides a bandwidth that precisely matches the requirements as it can learn the traffic load more accurately and allocate the needed slots; second, iQueue-MAC maintains high efficiency as it mitigates contention and retransmission by using TDMA slots for intensive senders.

Fig. 1 :

 1 Fig.1:The basic idea of the iQueue-MAC. Method (1) demonstrates a common way of prolonging the contention period used by most existing duty-cycle MAC protocol. In our iQueue-MAC, as shown in method (2), a variable TDMA period and a CSMA period are integrated to handle adaptive traffic.

Fig. 4 :

 4 Fig. 4: Beacon structure for iQueue-MAC

Fig. 5 :

 5 Fig. 5: An example run of iQueue-MAC

  Fig. 7: The effect of data rate on the average delay

Fig. 8 :Fig. 9 :

 89 Fig.8: The effect of data rate on the packet reception ratio

Fig. 10 :Fig. 11 :

 1011 Fig. 10: The effect of data rate on the duty-cycle

Fig. 12 :Fig. 13 :

 1213 Figure11shows the network average packet delay. At the beginning, all MACs have low latency. Then, when burst occurs, RI-MAC-MC and CoSenS start to suffer from sharply increasing delay. The situation continues to deteriorate until all buffered packets are dispatched. Compared to the other MACs, iQueue-MAC maintains its low latency even under the burst period. Figure12reveals the average queuing situation in all MACs which also explains the results in Figure11. It clearly shows that iQueue-MAC outperforms the other two MACs in maintaining a short queue length. This is because iQueue-MAC

Fig. 14 :Fig. 15 :

 1415 Fig. 14: The number of allocated Slots in iQueue-MAC

Figure 16 Fig. 16 :

 1616 Figure16shows the average packet delay of the general

Fig. 17 :

 17 Fig. 17: The comparison of the average queue length in the general experiment

Fig. 18 :

 18 Fig. 18: The comparison of the online throughput in the general experiment

TABLE I :

 I Parameters Setting For MAC Protocols Evaluation

		iQueue-MAC	CoSens	RI-MAC-MC
	Mean Subframe	500ms	500ms	500ms (sleep interval)
	Minimum CP	15ms	6ms	-
	Slot size	5ms	-	-
	Max retry	5 (in CP)	5 (in WP)	5
	Multichannel	Yes	No	Yes

TABLE II :

 II Burst Periods During General Experiment

	Cluster ID	Cluster 1	Cluster 2	Cluster 3	Cluster 4	All Clusters
	Burst period	100s-120s	200s-220s	300s-320s	400s-420s	600s-620s

We have successfully implemented iQueue-MAC on STM-32W108 SOC chips, and for comparison we also implemented CoSenS and RI-MAC-MAC and tested their throughput, network delay and queues length in numerous experiments. The results clearly show that iQueue-MAC outperforms CoSenS and RI-MAC-MAC in all the experimental scenarios. ACKNOWLEDGMENTS This work was supported in part by the French National Research Agency (ANR) and the National Science Foundation of China (NSFC) Joint Quasimodo Project (ANR 2010 INTB 0206 01, NSFC 61061130563), in part by the National Natural Science Foundation of China (NSFC) under Grant (61273079), in part by the Strategic Priority Research Program of the Chinese Academy of Sciences under Grant (XDA06020300, XDA06020201), in part by State Key Laboratory of Industrial Control Technology of Zhejiang University under Grant (1206, 1207), and in part by Key Laboratory of Wireless Sensor Network & Communication of Chinese Academy of Sciences under Grant 2011001.