N Frikha
email: frikha@math.univ-paris-diderot.fr

S Menozzi
email: menozzi@cmap.polytechnique.fr

CONCENTRATION BOUNDS FOR STOCHASTIC APPROXIMATIONS

Keywords: 1991 Mathematics Subject Classification. 60H35, 65C30, 65C05. December 10, 2012 Non asymptotic bounds, Euler scheme, Stochastic approximation algorithms, Gaussian concentration

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Statement of the Problem

Let us consider a d-dimensional stochastic evolution scheme of the form

ξ n+1 = ξ n + γ n+1 F (n, ξ n , Y n+1 ), n ≥ 0, ξ 0 = x ∈ R d , (1.1)
where (γ n ) n≥1 is a deterministic positive sequence of time steps, the function F : N × R d × R q → R d is a measurable function satisfying some assumptions that will be specified later on, and the (Y i ) i∈N * are i.i.d. R qvalued random variables defined on some probability space (Ω, F , P) whose law satisfies a Gaussian concentration property. That is, there exists α > 0 s.t. for every real-valued 1-Lipschitz function f defined on R q and for all λ ≥ 0:

E[exp(λf (Y 1 ))] ≤ exp(λE[f (Y 1 )] + αλ 2 4
).

(GC(α))

From the Markov exponential inequality and (GC(α)), one derives D(f, r)

:= P[f (Y 1 ) -E[f (Y 1 )] ≥ r] ≤ exp(-λr + αλ 2 4
), ∀λ, r ≥ 0. An optimization over λ gives that D(f, r) has sub-Gaussian tails bounded by exp(-r 2 α ). A practical criterion for (GC(α)) to hold is given by Bolley and Villani [START_REF] Bolley | Weighted Csiszár-Kullback-Pinsker inequalities and applications to transportation inequalities[END_REF]. If there exists ε > 0 s.t. E[exp(ε|Y 1 | 2 )] < +∞, then the law of Y 1 satisfies (GC(α)) with α := α(ε). The two claims are actually equivalent. In the following (GC(α)) is the only crucial property we require on the innovations (Y i ) i∈N * . In particular we do not assume any absolute continuity of the law of Y 1 w.r.t. the Lebesgue measure.

We are interested in giving non asymptotic concentration bounds for two specific problems related to evolutions of type (1.1). We first want to control the deviations of the empirical mean associated to a function of an Euler like discretization scheme of a diffusion process at a fixed deterministic time from the real mean. Secondly, we want to derive deviation estimates between the value of a Robbins-Monro type stochastic algorithm taken at fixed time-step and its target. Under some mild assumptions, we show that the Gaussian concentration property of the innovations transfers to the scheme. Concerning stochastic algorithms, our deviation results are to our best knowledge the first of this nature.

Euler like Scheme of a Diffusion Process

Let (Ω, F , (F t ) t≥0 , P) be a filtered probability space satisfying the usual conditions and (W t ) t≥0 be a qdimensional (F t ) t≥0 Brownian motion. Let us consider a d-dimensional diffusion process (X t ) t≥0 with dynamics:

X t = x + t 0 b(s, X s )ds + t 0 σ(s, X s )dW s , (1.2)
where the coefficients b, σ are assumed to be uniformly Lipschitz continuous in space and measurable in time.

For a given Lipschitz continuous function f and a fixed deterministic time horizon T , quantities like E x [f (X T )] appear in many applications. In mathematical finance, it represents the price of a European option with maturity T when the dynamics of the underlying asset is given by (1.2). Under suitable assumptions on the function f and the coefficients b, σ, namely smoothness or non degeneracy, it can also be related to the Feynman-Kac representation of the heat equation associated to the generator of X. Two steps are needed to approximate E x [f (X T )]: -The first step consists in approximating the dynamics by a discretization scheme that can be simulated. For a given time step ∆ = T /N, N ∈ N * , setting for all i ∈ N, t i := i∆, we consider an Euler like scheme of the form:

X ∆ 0 = x, ∀i ∈ [[0, N -1]], X ∆ ti+1 = X ∆ ti + b(t i , X ∆ ti )∆ + σ(t i , X ∆ ti ) √ ∆Y i+1 , (1.3)
where the (Y i ) i∈N * are R q -valued i.i.d. random variables whose law satisfies (GC(α)) for some α > 0. We also assume

E[Y 1 ] = 0 q , E[Y 1 Y * 1 ] = I q
, where Y * 1 stands for the transpose of the column vector Y 1 and 0 q , I q respectively stand for the zero vector of R q and the identity matrix of R q ⊗ R q . The previous assumptions include the case of the standard Euler scheme, corresponding to Y 1 law = N (0, I q ), which yields (GC(α)) with α = 2 and the Bernoulli law

Y 1 law = (B 1 , • • • , B q ), (B k ) k∈[[1,q]] i.i.d with law µ = 1 2 (δ -1 + δ 1 )
. This latter choice can turn out to be useful, in terms of computational effort, to approximate (1.2) when the dimension is large.

-The second step consists in approximating the expectation E x [f (X ∆ T )] involving the scheme (1.3) by a Monte-Carlo estimator:

E ∆ M (x, T, f ) := 1 M M j=1 f ((X ∆,0,x T ) j ),
where the ((X ∆,0,x T ) j ) j∈[ [1,M]] are independent copies of the scheme (1.3) starting at x at time 0 and evaluated at time T . The global error between E x [f (X T )], the quantity to estimate, and its implementable approximation E ∆ M (x, T, f ) can be decomposed as follows:

E(∆, M, x, T, f ) := (E x [f (X T )] -E x [f (X ∆ T )]) + (E x [f (X ∆ T )] -E ∆ M (x, T, f )) := E D (∆, x, T, f ) + E S (∆, M, x, T, f ).
(1.4)

The term E D (∆, x, T, f ) corresponds to the discretization error and has been widely investigated in the literature since the seminal work of Talay and Tubaro [START_REF] Talay | Expansion of the global error for numerical schemes solving stochastic differential equations[END_REF]. For the standard Euler scheme, this contribution usually yields an error of order ∆, provided the coefficients b, σ and the function f are sufficiently smooth, which are the assumptions required in [START_REF] Talay | Expansion of the global error for numerical schemes solving stochastic differential equations[END_REF], or that b, σ satisfy some non-degeneracy assumptions which allow to weaken the smoothness assumptions on f . This is for instance the case in Bally and Talay [START_REF] Bally | The law of the Euler scheme for stochastic differential equations: I. Convergence rate of the distribution function[END_REF] who obtain the expected order for a bounded measurable f and smooth coefficients satisfying a (possibly weak) hypoellipticity condition. Their proof relies on Malliavin calculus. When the diffusion coefficient is uniformly elliptic and bounded, if b, σ are also assumed to be three times continuously differentiable, the control at order ∆ for E D (∆, x, T, f ) can be derived from Konakov and Mammen [START_REF]Edgeworth type expansions for Euler schemes for stochastic differential equations[END_REF] who use a more direct parametrix approach. When the Gaussian increments of the standard Euler scheme are replaced by more general (possibly discrete) random variables (Y i ) i≥1 having the same covariance matrix and odd moments up to order 5 as the standard Gaussian vector of R q , it can be checked that the error expansion at order ∆ of [START_REF] Talay | Expansion of the global error for numerical schemes solving stochastic differential equations[END_REF] still holds for b, σ, f smooth enough. In that framework we also mention the works of Konakov and Mammen [START_REF] Konakov | Local limit theorems for transition densities of Markov chains converging to diffusions[END_REF], [START_REF]Local approximations of markov random walks by diffusions[END_REF], concerning local limit theorems for the difference between (1.2) and the scheme (1.3). As in [START_REF]Edgeworth type expansions for Euler schemes for stochastic differential equations[END_REF], the coefficients are supposed to be smooth and σ uniformly elliptic. The associated error is then of order ∆ 1/2 , speed of the Gaussian local limit theorem, see Bhattacharya and Rao [START_REF] Bhattacharya | Normal approximations and asymptotic expansions[END_REF].

The term E S (∆, M, x, T, f ) in (1.4) corresponds to the statistical error. Under some usual integrability conditions, i.e. f (X ∆ T ) ∈ L 2 (P), it is asymptotically controlled by the central limit theorem. A first nonasymptotic result is given by the Berry-Essen theorem provided f (X ∆ T ) ∈ L 3 (P), but for practical purposes, the crucial quantity to control non-asymptotically is the deviation between the empirical mean E ∆ M (x, T, f ) and the real one E x [f (X ∆ T )]. Precisely, for a fixed M and a given threshold r > 0, one would like to give bounds on the quantity

P[|E ∆ M (x, T, f ) -E x [f (X ∆ T )]| > r].
In the ergodic framework and for a constant diffusion coefficient Gaussian controls have been obtained by Malrieu and Talay [START_REF] Malrieu | Concentration inequalities for Euler schemes, Monte Carlo and Quasi-Monte Carlo Methods[END_REF]. In the current context and for the standard Euler scheme, a first attempt to establish two-sided Gaussian bounds for E S (∆, M, x, T, f ) can be found in [START_REF] Lemaire | On some non asyptotic bounds for the Euler scheme[END_REF] under some non-degeneracy conditions up to a systematic bias independent of M .

In the current work we assume that the coefficients satisfy the mild smoothness condition:

(A) The coefficients b, σ are uniformly Lipschitz continuous in space uniformly in time, σ is bounded.

Note that we do not assume any non-degeneracy condition on σ in (A).

We next show that when the innovations satisfy (GC(α)), the Gaussian concentration property transfers to the statistical error

E ∆ M (x, T, f ) -E x [f (X ∆ T )].
In particular we get rid off the systematic bias in [START_REF] Lemaire | On some non asyptotic bounds for the Euler scheme[END_REF]. The key tool consists in writing the deviation using the same kind of decompositions that are exploited in [START_REF] Talay | Expansion of the global error for numerical schemes solving stochastic differential equations[END_REF] for the analysis of the discretization error. Denote by X ∆,ti,x T the value at time T of the scheme (1.3) starting from x ∈ R d at time t i , i ∈ [[0, N ]] and by F i := σ(Y j , j ≤ i) the filtration generated by the innovations. We write

f (X ∆,0,x T ) -E[f (X ∆,0,x T )] := N i=1 E[f (X ∆,0,x T )|F i ] -E[f (X ∆,0,x T )|F i-1 ] = N i=1 E[f (X ∆,0,x T )|X ∆,0,x ti ] -E[f (X ∆,0,x T )|X ∆,0,x ti-1 ],
using the Markov property for the last equality. Introducing the function v ∆ (t i , x)

:= E[f (X ∆ T )|X ∆ ti = x], (i, x) ∈ [[0, N ]] × R d , we obtain: f (X ∆,0,x T ) -E[f (X ∆,0,x T )] := N i=1 v ∆ (t i , X ∆,0,x ti ) -v ∆ (t i-1 , X ∆,0,x ti-1 ). (1.5)
The definition of v ∆ now yields:

f (X ∆,0,x T ) -E[f (X ∆,0,x T )] = N i=1 v ∆ (t i , X ∆,0,x ti ) -E[v ∆ (t i , X ∆,0,x ti )|X ∆,0,x ti-1 ] = N i=1 f ∆ i (X ∆,0,x ti-1 , √ ∆Y i ) -E[f ∆ i (X ∆,0,x ti-1 , √ ∆Y i )|X ∆,0,x ti-1 ], (1.6)
where

f ∆ i (x, y) := E[f (X ∆ T )|X ∆ ti = x + b(t i-1 , x)∆ + σ(t i-1 , x)y], for all (i, x, y) ∈ [[1, N ]] × R d × R q .
The decomposition (1.5) is similar to the first step of the analysis of the discretization error. In that

framework, v ∆ (t i , X ∆,0,x ti ) is replaced by v(t i , X ∆,0,x ti ) = E[f (X ti,X ∆,0,x t i T )]
, that is the expectation involving the diffusion at time T starting from the current value of the scheme at t i , see [START_REF] Talay | Expansion of the global error for numerical schemes solving stochastic differential equations[END_REF]. Under some non degeneracy assumptions or smoothness of the coefficients, v is smooth and Itô-Taylor expansions lead to the previously mentioned first order error for E D (∆, x, T, f ).

To analyze the statistical error, the key idea is to exploit recursively from (1.6) that the increments of the scheme (1.3) satisfy (GC(α)). The Gaussian concentration property will readily follow provided the f i are Lipschitz in the variable y. Under (A), this smoothness is actually derived from direct stability arguments using flow techniques, see Proposition 4.1 and its proof in Section A.1.

Let us here mention the work of Blower and Bolley [START_REF] Blower | Concentration inequalities on product spaces with applications to Markov processes[END_REF] who obtained Gaussian concentration properties for the joint law of the first n positions of stochastic processes (possibly non Markov) with values in general separable metric spaces. This result is in some sense much stronger than ours, since it can for instance yield to non asymptotic controls of the Monte-Carlo error for smooth functionals of the path, such as the maximum. However, some continuity assumptions in Wasserstein metric are assumed on the transition measures of the process, see e.g. condition (ii) in their Theorems 1.2 and 2.1. This is required from the coupling techniques used in the proof. Checking this kind of continuity can be hard in practice, in [START_REF] Blower | Concentration inequalities on product spaces with applications to Markov processes[END_REF] the authors give some sufficient conditions that require the transition laws to be absolutely continuous and smooth, see their Proposition 2.2. In the current work we only need the property (GC(α)) for the innovations, which can in particular hold for discrete laws.

Also, we want to stress that, even if the concentration results coincide when the innovations (Y i ) i∈N * have a smooth density, the nature of the proofs is different. Blower and Bolley exploit optimal transportation techniques whereas our approach consists in adapting the PDE arguments used for the analysis of the discretization error to the current setting. It is actually striking that a similar error decomposition can be used for investigating both the discretization and statistical error.

We conclude mentioning some works related to the deviations of the 1-Wasserstein distance between a reference measure and its empirical version. In the i.i.d. case, such results were first obtained for different concentration regimes by Bolley, Guillin, Villani [START_REF] Bolley | Quantitative concentration inequalities for empirical measures on non-compact spaces[END_REF] relying on a non-asymptotic version of Sanov's Theorem. Some of these results have also been derived by Boissard [START_REF] Boissard | Simple bounds for the convergence of empirical and occupation measures in 1-Wasserstein distance[END_REF] using concentration inequalities and extended to ergodic Markov chains up to some contractivity assumptions in the Wasserstein metric on the transition kernel. In the i.i.d. case and Gaussian concentration regime, these results lead to the following type of estimates:

P   sup f,1-Lip 1 M M j=1 f (Z j ) -E[f (Z)] ≥ r   ≤ C(r) exp -KM r 2
where the (Z j ) j∈N * are i.i.d. having the same distribution as Z and the constants C(r) and K may be explicitly but tediously computed. This kind of uniform deviation bounds are of interest in statistics and numerical probability from a practical point of view. They can indeed lead to deviation bounds for the estimation of the density of the invariant measure of a Markov chain, see [START_REF] Bolley | Quantitative concentration inequalities for empirical measures on non-compact spaces[END_REF]. However, the (possibly large) constant C(r) is the trade-off to obtain uniform deviations over all Lipschitz functions. We do not intend to develop these aspects but similar bounds could be established in our context.

Robbins-Monro Stochastic Approximation Algorithm

Besides our considerations for the Euler scheme, we derive non asymptotic bounds for stochastic approximation algorithms of Robbins-Monro type. These recursive algorithms aim at finding a zero of a continuous function h : R d → R d which cannot be directly computed but only estimated through simulation. Such procedures are commonly used in a convex optimization framework since minimizing a function amounts to finding a zero of its gradient. Precisely, the goal is to find a solution θ * to h(θ) := E[H(θ, Y )] = 0, where H : R d × R q → R d is a Borel function and Y is a given R q -valued random variable. Even though h(θ) cannot be directly computed, it is assumed that the random variable Y can be easily simulated (at least at a reasonable cost), and also that H(θ, y) can be easily computed for any couple (θ, y) ∈ R d × R q . The Robbins-Monro algorithm is the following recursive scheme

θ n+1 = θ n -γ n+1 H(θ n , Y n+1 ), n ≥ 0, θ 0 ∈ R d , (1.7)
where (Y n ) n≥1 is an i.i.d. R q -valued sequence of random variables defined on a probability space (Ω, F , P) and (γ n ) n≥1 is a sequence of non-negative deterministic steps satisfying the usual assumption n≥1 γ n = +∞, and

n≥1 γ 2 n < +∞. (1.8)
When the function h is the gradient of a potential, the iterative scheme (1.7) can be viewed as a stochastic gradient algorithm. Indeed, replacing H(θ n , Y n+1 ) by h(θ n ) in (1.7) leads to the usual deterministic gradient method. One of the ideas in (1.7) is to take advantage of an averaging effect along the scheme due to the specific form of h(θ)

:= E[H(θ, Y )]
. This allows to avoid the explicit computation or estimation of h. We refer to [START_REF] Duflo | Algorithmes stochastiques, Mathématiques & Applications[END_REF], [START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF] for some general convergence results of the sequence (θ n ) n≥0 defined by (1.7) towards its target θ * under the existence of a so-called Lyapunov function, i.e. a continuously differentiable function L : R d → R + such that ∇L is Lipschitz, |∇L| 2 ≤ C(1 + L) for some positive constant C and ∇L, h ≥ 0.

See also [START_REF] Laruelle | Stochastic approximation with averaging innovation applied to finance[END_REF] for a convergence theorem under the existence of a pathwise Lyapunov function. In the sequel, it is assumed that θ * is the unique solution of the equation h(θ) = 0 and that (θ n ) defined by (1.7) converges a.s. towards θ * . We assume that the innovations (Y i ) i∈N * satisfy (GC(α)) for some α > 0 and also that the following conditions on the function H and the step sequence (γ n ) n≥1 in (1.7) are in force:

(HL) The map (θ, y) ∈ R d × R q → H(θ, y) is uniformly Lipschitz continuous. (HUA) The map h : θ ∈ R d → E[H(θ, Y )] is continuously differentiable in θ and there exists λ > 0 s.t. ∀θ ∈ R d , ∀ξ ∈ R d , λ|ξ| 2 ≤ Dh(θ)ξ, ξ (Uniform Attractivity).
In order to derive a Central Limit Theorem for the sequence (θ n ) n≥1 as described in [START_REF] Duflo | Algorithmes stochastiques, Mathématiques & Applications[END_REF] or [START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF], it is commonly assumed that the matrix Dh(θ * ) is uniformly attractive. In our current framework, this local condition on the Jacobian matrix of h at the equilibrium is replaced by the uniform assumption (HUA). This allows to derive non-asymptotic concentration bounds uniformly w.r.t. the starting point θ 0 .

Note that under (HUA) and the linear growth assumption

∀θ ∈ R d , E |H(θ, Y )| 2 ≤ C(1 + |θ -θ * | 2 ),
(which is satisfied if (HL) holds and Y ∈ L 2 (P)) the function L : θ → 1 2 |θθ * | 2 is a Lyapunov function for the recursive procedure defined by (1.7) so that one easily deduces that θ n → θ * , a.s. as n → +∞.

As for the Euler scheme, we decompose the global error between the stochastic approximation procedure θ n at a given time step n and its target θ * as follows:

z n := |θ n -θ * | = (|θ n -θ * | -E[|θ n -θ * |]) + E[|θ n -θ * |] := E Emp (γ, n, H, λ, α) + δ n (1.9)
where

δ n := E[|θ n -θ * |].
The term E Emp (γ, n, H, λ, α) corresponding to the difference between the absolute value of the error at time n and its mean can be viewed as an empirical error. As for the Euler scheme, the Gaussian concentration property transfers to this quantity under (HL) and (HUA). The strategy consists in introducing again a telescopic sum of conditional expectations. Denoting for all i ∈ N, F i := σ(Y j , j ≤ i) (i.e. (F i ) i∈N is the natural filtration of the algorithm), we write for all n ∈ N * :

E Emp (γ, n, H, λ, α) = |z n | -E[|z n |] = n i=1 E[|z n ||F i ] -E[|z n ||F i-1 ] = n i=1 v i (θ i ) -E[v i (θ i )|F i-1 ], = n i=1 f γ i (θ i-1 , Y i ) -E[f γ i (θ i-1 , Y i )|F i-1 ],
where we used the Markov property for the second equality and we introduced the notations v i (θ

) := E[|θ n - θ * ||θ i = θ], ∀(i, θ) ∈ [[1, n]] × R d , f γ i (θ, y) = v i (θ -γ i H(θ, y)).
The stability of the Gaussian concentration property is then derived using that the f γ i are Lipschitz in the variable y, see Proposition 5.1. The term δ n in (1.9) corresponds to the bias of the sequence (θ n ) n≥0 with respect to its target θ * . This contribution strongly depends on the choice of the step sequence (γ n ) n≥1 and the initial point θ 0 . Under (HL) and (HUA), we analyze this quantity in Proposition 5.2.

Main Results

Deviations on the Euler Scheme Theorem 2.1 (Concentration Bounds for the Euler scheme). Denote by X ∆

T the value at time T of the scheme (1.3) associated to the diffusion (1.2). Assume that the innovations (Y i ) i∈N * in (1.3) satisfy (GC(α)) for some α > 0 and that the coefficients b, σ satisfy (A). Let f be a real valued uniformly Lipschitz continuous function on R d . For all M ∈ N * and all r ≥ 0, one has

P x [| 1 M M i=1 f ((X ∆ T ) i ) -E x [f (X ∆ T )]| ≥ r] ≤ 2 exp(- r 2 M T Ψ(T, f, b, σ, q) ), Ψ(T, f, b, σ, q) := 4α[f ] 2 1 |σ| 2 ∞ exp (2([b] 1 + c[σ] 1 (1 ∨ c[σ] 1 ))T ) ,
where q is the dimension of the underlying Brownian motion in (1.2) and c := c(q).

Note that in the above theorem, we do not need any non-degeneracy condition on the diffusion coefficient. As developed in Section 1.1, see (1.6), to handle the previous quantity we rewrite f (X

∆ T ) -E[f (X ∆ T )] := N i=1 f ∆ i (X ∆ ti-1 , √ ∆Y i ) -E[f ∆ i (X ∆ ti-1 , √ ∆Y i )|F i-1 ], where f ∆ i (x, y) := E[f (X ∆ T )|X ∆ ti = x + b(t i-1 , x)∆ + σ(t i-1 , x)y], for all (i, x, y) ∈ [[1, N ]] × R d × R q .
If at some point along the time-discretization the process has a degenerate diffusion term, we can see that the difference

f ∆ i (X ∆ ti-1 , √ ∆Y i ) -E[f ∆ i (X ∆ ti-1 , √ ∆Y i )|F i-1 ]
will not give any additional contribution in the global deviation.

With respect to the previous work [START_REF] Lemaire | On some non asyptotic bounds for the Euler scheme[END_REF], we got rid off the systematic bias. Anyhow, the concentration constants now depend on the Lipschitz constant of the function v ∆ (0, x) := E[f (X ∆ T )|X ∆ 0 = x] which has order Ψ(T, f, b, σ, q) 1/2 . This magnitude corresponds to the product of the Lipschitz constant of the final function f and the mean of the Lipschitz constant for the flow of the scheme, which gives the exponential dependence in time, see Proposition 4.1 and its proof for details.

Remark 2.1 (Extension to smooth functionals of the path). We point out that the previous concentration results could be extended to some smooth functionals of the path such as the maximum for a scalar scheme. Indeed, introducing in that case the additional state variable

(M ∆ ti ) i∈N := (max j∈[[0,i]] X ∆ tj ) i∈N , the couple (X ∆ ti , M ∆ ti )
i∈N is Markovian and the flow arguments of Proposition 4.1 could be extended to the couple for Lipschitz functions in both variables.

Remark 2.2 (Linear SDEs and concentration). Observe that it is the boundedness of σ that gives the Gaussian concentration regime. However, in many popular models in finance, the diffusion coefficient is linear, see e.g. the Black-Scholes like dynamics

X t = x 0 + t 0 b(X s )X s ds+ t 0 σ(X s )X s dW s for smooth, bounded coefficients b, σ. For the estimation of E[f (X ∆
T )] of the associated Euler scheme, if f is bounded then the Gaussian concentration holds for the statistical error from the Bolley and Villani criterion applied to f (X ∆ T ). However, for a general Lipschitz function, the expected concentration is the log-normal one.

Deviations for Robbins-Monro algorithms

Theorem 2.2 (Concentration Bounds for Robbins-Monro algorithms). Assume that the function H of the recursive procedure (θ n ) n≥0 (with starting point θ 0 ∈ R d ) defined by (1.7) satisfies (HL) and (HUA), and that the step sequence (γ n ) n≥1 satisfies (1.8). Suppose that the law of the innovation satisfies (GC(α)), α > 0.Then, for all N ∈ N * and all r ≥ 0,

P (|θ N -θ * | ≥ r + δ N ) ≤ exp - r 2 α[H] 2 1 Π N N k=1 γ 2 k /Π k where Π N := N -1 k=0 1 -2λγ k+1 + [H] 2 1 γ 2 k+1 and δ N := E [|θ N -θ * |].
Moreover, the bias δ N at step N satisfies

δ N ≤ exp (-λΓ N ) |θ 0 -θ * | + [H] 1 σ Y N -1 k=0 e -2λ(ΓN -Γ k+1 ) γ 2 k+1 1 2
, where

Γ N := N k=1 γ k , σ Y := E F 2 (Y ) 1/2 < +∞, with F : y → E [|y -Y |].
Concerning the choice of the step sequence (γ n ) n≥1 and its impact on the concentration rate and bias, we obtain the following results:

• If we choose γ n = c n , with c > 0. Then δ N → 0, N → +∞, Γ N = c log(N ) + c ′ 1 + r N , c ′ 1 > 0 and r N → 0, so that Π N = O(N -2cλ ). -If c < 1 2λ , the series N k=1 γ 2 k /Π k converges so that we obtain Π N N k=1 γ 2 k /Π k = O(N -2cλ ). -If c > 1 2λ
, a comparison between the series and the integral yields

Π N N k=1 γ 2 k /Π k = O(N -1
). Let us notice that we find the same critical level for the constant c as in the Central Limit Theorem for stochastic algorithms. Indeed, if c > 1 2Re(λmin) where λ min denotes the eigenvalue of Dh(θ * ) with the smallest real part then we know that a Central Limit Theorem holds for (θ n ) n≥1 (see e.g. [START_REF] Duflo | Algorithmes stochastiques, Mathématiques & Applications[END_REF]). However, this local condition on the Jacobian matrix of h at the equilibrium is replaced by a uniform assumption in our framework. This is quite natural since we want to derive non-asymptotic bounds for the stochastic approximation (1.7).

Concerning the bias we have the following bound:

δ N ≤ |θ 0 -θ * | N λc + K[H] 1 σ Y 1 N λc∧ 1 2 , K := K(c). • If we choose γ n = c n ρ , c > 0, 1 2 < ρ < 1, then δ N → 0, Γ N ∼ c 1-ρ N 1-ρ
as N → +∞ and elementary computations show that there exists C > 0 s.t. for all N ≥ 1, Π N ≤ C exp(-2λ c 1-ρ N 1-ρ ). Hence, for all ǫ ∈ (0, 1ρ) we have:

Π N N k=1 γ 2 k Π -1 k ≤ c 2    Π N Π -1 N -N ρ+ǫ N -N ρ+ǫ k=1 1 k 2ρ + N k=N -N ρ+ǫ +1 1 k 2ρ    ≤ c 2 C exp(-2λ c 1 -ρ (N 1-ρ -(N -N ρ+ǫ ) 1-ρ )) + N ρ+ǫ (N -N ρ+ǫ + 1) 2ρ ≤ c 2 C exp(-2λcN ǫ ) + 1 N ρ-ǫ . Up to a modification of ǫ, this yields Π N N k=1 γ 2 k Π -1 k = o(N -ρ+ǫ ), ǫ ∈ (0, 1 -ρ).
Concerning the bias, from the above control, we have the following bound:

δ N ≤ exp - λc 1 -ρ N 1-ρ |θ 0 -θ * | + [H] 1 σ Y K N ρ 2 -ǫ , K := K(c), ∀ǫ > 0.
Since each step is bigger compared to the case γ n = c n , the impact of the initial difference |θ 0θ * | is exponentially small.

Abstract concentration properties for a general evolution scheme

In this section we assume that (Y i ) i∈N * is a sequence of i.i.d. R q -valued random variables whose law µ satisfies the Gaussian concentration property (GC(α)) for a given α > 0. Proposition 3.1 (Gaussian concentration for a stochastic evolution scheme).

Fix N ∈ N * . Define for all i ∈ [[1, N ]], D i := f i (X i-1 , Y i ) -E[f i (X i-1 , Y i )|F i-1 ] for some F i-1 -measurable random variables X i-1 where the real-valued functions (f i ) i∈[[1,N ]] are Lipschitz continuous in the y variable with constants ([f i ] 1 ) i∈[[1,N ]] > 0 uniformly in x. Let (γ i ) i∈[[1,N ]]
be a given sequence of time steps. For all r ≥ 0, we have:

P[ N i=1 γ i D i ≥ r] ≤ exp - r 2 α N i=1 ([f i ] 1 γ i ) 2 . Proof. Set P(r) := P[ N i=1 γ i D i ≥ r].
For λ ≥ 0 to be specified later on, the Tchebychev exponential inequality yields:

P(r) ≤ exp(-λr)E[exp λ N i=1 γ i D i ] ≤ exp(-λr)E[exp λ N -1 i=1 γ i D i E [exp(λγ N D N )|F N -1 ]]. (3.1)
Observe now that working with regular conditional expectations, we have

E [exp(λγ N D N )|F N -1 ] = E µ [exp (λγ N (f N (x, Y ) -E µ [f N (x, Y )]))]| x=XN-1 ,
where Y is a random variable with law µ. From (GC(α)), we derive

E [exp(λγ N D N )|F N -1 ] ≤ exp(α([f N ] 1 γ N λ) 2 /4).
Plugging this estimate in (3.1) and iterating the procedure we derive

P(r) ≤ exp(-λr) exp αλ 2 4 N i=1 ([f i ] 1 γ i ) 2 ,
and optimizing w.r.t λ, we obtain: P(r) ≤ exp -

r 2 α N i=1 ([fi]1γi) 2 .

Euler Scheme: Proof of the Main Results

In order to apply Proposition 3.1 from the decomposition (1.6), all we need is to have a control on the Lipschitz modulus in the variable y of the functions f ∆ i (x, y), uniformly in x. Under the current assumptions of Theorem 2.1, we have the following Proposition which is proved in Section A.1. i introduced after (1.6) are uniformly Lipschitz continuous in the space variable y uniformly in x and we have that there exists c := c(q) (dimension of the underlying Brownian motion) s.t:

[f ∆ i ] 1 := sup x∈R d ,y =y ′ |f ∆ i (x, y) -f ∆ i (x, y ′ )| |y -y ′ | ≤ 2[f ] 1 |σ| ∞ exp ({[b] 1 + c[σ] 1 (1 ∨ c[σ] 1 )} (T -t i )) .
where [f ] 1 stands for the Lipschitz constants of the function f .

Set γ i = 1, D i = f ∆ i (X ∆ ti-1 , √ ∆Y i ) -E[f ∆ i (X ∆ ti-1 , √ ∆Y i )|F ti-1 ], ∀i ∈ [[1, N ]].
Since the random variable √ ∆Y i satisfies the Gaussian concentration property (GC(∆α)), we derive from Propositions 3.1 and 4.1:

P x [f (X ∆ T ) -E x [f (X ∆ T )] ≥ r] ≤ exp(- r 2 ∆α N i=1 [f ∆ i ] 2 1 ) ≤ exp(- r 2 4αT [f ] 2 1 |σ| 2 ∞ exp (2([b] 1 + c[σ] 1 (1 ∨ c[σ] 1 ))T ) ) := exp(- r 2 T Ψ(T, f, b, σ, q)
).

Hence the random variable X ∆ T satisfies (GC(β)) for β := T Ψ(T, f, b, σ, q)/[f ] 2 1 . The bound of Theorem 2.1 now follows from a simple tensorization argument for independent random variables satisfying the Gaussian concentration property. Namely, for λ, r ≥ 0,

P x [ 1 M M j=1 f ((X ∆ T ) j ) -E x [f (X ∆ T )] ≥ r] ≤ exp(-λr)E x exp λ 1 M ( M j=1 f ((X ∆ T ) j ) -E x [f (X ∆ T ) j ]) (GC(β)) ≤ exp(-λr) exp( βλ 2 [f ] 2 1 4M 2 ) M = exp(-λr + T Ψ(T, f, b, σ, q)λ 2 4M
).

An optimization in λ gives the result.

Robbins-Monro Algorithm: Proof of the Main Results

With the notations of Section 1.2, in order to apply Proposition 3.1 we have to control the Lipschitz constants in y of the functions

f γ i (θ, y) = v i (θ -γ i H(θ, y)), ∀(i, θ, y) ∈ [[1, n]] × R d × R q where v i (θ) := E[|θ n -θ * ||θ i = θ].
Under the assumptions of Theorem 2.2, the following control holds. Proposition 5.1 (Controls of the Lipschitz constants). For all i ∈ [ [1, n]], the function f γ i satisfies:

[f γ i ] 1 := sup θ∈R d ,y =y ′ |f γ i (θ, y) -f γ i (θ, y ′ )| |y -y ′ | ≤ Π n Π -1 i 1/2 γ i [H] 1 .
where

Π n := n-1 k=0 1 -2λγ k+1 + [H] 2 1 γ 2 k+1 , n ≥ 1. The proof is postponed to Section A.2. Set D i = f γ i (θ i-1 , Y i ) -E[ f γ i (θ i-1 , Y i )| F i-1 ].
Recalling that the random variables (Y i ) i∈N * satisfy (GC(α)), we obtain from Proposition 3.1 that for all r ≥ 0:

P (|θ N -θ * | ≥ r + δ N ) = P (|θ N -θ * | -E[|θ N -θ * |] ≥ r) ≤ exp - r 2 α[H] 2 1 Π N N k=1 γ 2 k /Π k .
Contrary to the result concerning the Euler scheme, a bias appears in the non-asymptotic bound for the stochastic approximation algorithm. Consequently, it is crucial to have a control on it. At step n of the algorithm, it is equal to

δ n := E[|θ n -θ * |].
Under the current assumptions (HL) of Lipschitz continuity of H and (HUA) of uniform attractivity, we have the following proposition. Proposition 5.2 (Control of the bias). For all n ≥ 1, we have

δ n ≤ exp (-λΓ n ) |θ 0 -θ * | + [H] 1 σ Y n-1 k=0 e -2λ(Γn-Γ k+1 ) γ 2 k+1 1 2 , where Γ n := n k=1 γ k , σ Y := E F 2 (Y ) 1/2 < +∞, with F : y → E [|y -Y |].
Proof. With the notations of Section 1.2, we define for all n ≥ 1,

∆M n := h(θ n-1 ) -H(θ n-1 , Y n ) = E[ H(θ n-1 , Y n )| F n-1 ] -H(θ n-1 , Y n ). Recalling that (Y i ) i∈N * is
:= σ(Y i , i ≤ n), n ≥ 1).
From the dynamics (1.7), write now for all n ∈ N,

z n+1 := θ n+1 -θ * = θ n -θ * -γ n+1 {h(θ n ) -∆M n+1 } = θ n -θ * -γ n+1 1 0 dλDh(θ * + λ(θ n -θ * ))(θ n -θ * ) + γ n+1 ∆M n+1 ,
where we used that h(θ * ) = 0 for the last equality. Setting J n := 1 0 dλDh(θ * + λ(θ nθ * )), we obtain

z n+1 = (I -γ n+1 J n )z n + γ n+1 ∆M n+1 .
Take now the square of the L 2 -norm in the previous equality. Recalling that ∆M n+1 is a martingale increment, we derive:

E[|z n+1 | 2 ] = E[|(I -γ n+1 J n )z n | 2 ] + γ 2 n+1 E[|∆M n+1 | 2 ] ≤ exp(-2λγ n+1 )E[|z n | 2 ] + γ 2 n+1 [H] 2 1 σ 2 Y .
For the last inequality we used (exploiting assumption (HUA), uniform attractivity of the Jacobian matrix of h) ||Iγ n+1 J n || ≤ exp(-λγ n+1 ), . standing for the matrix norm on R d ⊗ R d , and the inequality

E[|∆M n+1 | 2 ] ≤ [H] 2 1 σ 2
Y which follows from (HL). A direct induction yields for all n ≥ 1:

E[|z n | 2 ] ≤ exp (-2λΓ n ) |z 0 | 2 + [H] 2 1 σ 2 Y n-1 k=0 e -2λ(Γn-Γ k+1 ) γ 2 k+1 ,
which completes the proof.

Appendix A. Technical results

A.1. Proof of Proposition 4.1

The proof follows from usual stochastic analysis arguments that we now recall for the sake of completeness. For i = N we directly get from the definition of f

∆ N (x, y) that [f ∆ N ] 1 ≤ [f ] 1 |σ| ∞ . For i ∈ [[1, N -1]], define for y = y ′ the quantity D ∆ ti (T, x, y, y ′ ) := sup j∈[[i,N ]] |X ∆,ti,G ∆ i-1 (x,y) tj -X ∆,ti,G ∆ i-1 (x,y ′ ) tj | |y -y ′ | , ∀z ∈ R d , G ∆ i-1 (x, z) := b(t i-1 , x)∆ + σ(t i-1 , x)z.
Write now:

D ∆ ti (T, x, y, y ′ ) ≤    |G ∆ i-1 (x, y) -G ∆ i-1 (x, y ′ )| |y -y ′ | + ∆[b] 1   N -1 k=i |X ∆,ti,G ∆ i-1 (x,y) t k -X ∆,ti,G ∆ i-1 (x,y ′ ) t k | |y -y ′ |   + sup j∈[[i,N ]] j k=i   σ(t k , X ∆,ti,G ∆ i-1 (x,y) t k ) -σ(t k , X ∆,ti,G ∆ i-1 (x,y ′ ) t k ) |y -y ′ |   √ ∆Y k+1    .
One can easily show that for all (z, j) ∈ R q × [[0, N ]], X ∆,ti,G ∆ i-1 (x,z) tj ∈ L 1 (P). Hence, taking the expectation and using the the Burkholder-Davis-Gundy inequality (see e.g. Chapter 7, §3 in Shiryaev [START_REF] Shiryaev | Probability[END_REF]) we obtain: = |θ θ,i jθ θ ′ ,i j | 2 -2γ j+1 θ θ,i jθ θ ′ ,i j , H(θ θ,i j , Y j+1 ) -H(θ θ ′ ,i j , Y j+1 ) +γ 2 j+1 |H(θ θ,i j , Y j+1 ) -H(θ θ ′ ,i j , Y j+1 )| 2 = |θ θ,i jθ θ ′ ,i j | 2 -2γ j+1 θ θ,i jθ θ ′ ,i j , h(θ θ,i j )h(θ θ ′ ,i j ) -2γ j+1 θ θ,i jθ θ ′ ,i j , ∆M θ,i j+1 -∆M θ ′ ,i j+1

E[D ∆ ti (T, x, y, y ′ )] ≤    |σ| ∞ + [b] 1 ∆ N -1 k=i E   |X ∆,ti,G ∆ i-1 (x,y) t k -X ∆,ti,G ∆ i-1 (x,y ′ ) t k | |y -y ′ |   + cE        N -1 k=i σ(t k , X ∆,ti,G ∆ i-1 (x,y) t k ) -σ(t k , X ∆,ti,G ∆ i-1 (x,y ′ ) t k ) |y -y ′ | √ ∆Y k+1 2    1/2            . ≤ |σ| ∞ + [b] 1 ∆ N -1 k=i E[(D ∆ ti (t k , x, y, y ′ )] +c[σ] 1 E      ∆ N -1 k=i |X ∆,ti,G ∆ i-1 (x,y) t k -X ∆,ti,G ∆ i-1 (x,y) t k | 2 |y -y ′ | 2 |Y k+1 | 2
)] ≤ |σ| ∞ exp {[b] 1 + c[σ] 1 E[|Y 1 | 2 ]η -1 }(T -t i ) , η ∈ 0, 1 c[σ] 1 ∧ 1 .
+γ 2 j+1 |H(θ θ,i j , Y j+1 ) -H(θ θ ′ ,i j , Y j+1 )| 2 ,
where we introduced the martingale increments ∆M θ,i j+1 = H(θ θ,i j , Y j+1 )h(θ θ,i j ) and ∆M θ ′ ,i j+1 = H(θ θ ′ ,i j , Y j+1 )h(θ θ ′ ,i j ), j ≥ 0 in the last equality. Now, using (HL) and (HUA) yields:

|θ θ,i j+1 -θ θ ′ ,i j+1 | 2 ≤ |θ θ,i j -θ θ ′ ,i j | 2 1 -2λγ j+1 + [H] 2 1 γ 2 j+1
-2γ j+1 θ θ,i jθ θ ′ ,i j , ∆M θ,i j+1 -∆M θ ′ ,i j+1 , and, by induction on j, we easily obtain:

|θ θ,i n -θ θ ′ ,i n | 2 ≤ |θ -θ ′ | 2 n-1 j=i 1 -2λγ j+1 + [H]

Proposition 4 . 1 (

 41 Control of the Lipschitz constants). Denote the respective Lipschitz constants of b, σ in (1.3) by [b] 1 , [σ] 1 . Denote the supremum of σ by |σ| ∞ . Then for all i ∈ [[1, N ]], the functions f ∆

2 1/ 2 ≤ 1 N - 1 k=iE

 2211 ti (T, x, y, y′ ) 1/2 ∆ N -1 k=i D ∆ ti (t k , x, y, y ′ )|Y k+1 | ηE[D ∆ ti (T, x, y, y ′ )] + η -[D ∆ ti (t k , x, y, y ′ )]E[|Y 1 | 2 ], ∀η ∈ (0, 1), which plugged into (A.1) yields thanks to the Gronwall Lemma(1c[σ] 1 η)E[D ∆ ti (T, x, y, y ′

A. 2 . 1 From

 21 ti (T, x, y, y ′ )] ≤ 2|σ| ∞ exp {[b] 1 + 2cE[|Y 1 | 2 ][σ] 1 (1 ∨ c[σ] 1 )}(Tt i ) , which recalling [f ∆ i ] 1 ≤ [f ] 1 sup y =y ′ E[|D ∆ ti (T,x, y, y ′ )|] completes the proof up to a modification of c. Proof of Proposition 5.the definitions in Section 1.2, it suffices to control the difference E[|θ θ,i nθ θ ′ ,i n |], that is the sensitivity of the algorithm w.r.t. the starting point at time i ∈ [[1, n]]. Write for all j ∈ [[i, n -1]]:|θ θ,i j+1θ θ ′ ,i j+1 | 2 = |θ θ,i jθ θ ′ ,i j γ j+1 H(θ θ,i j , Y j+1 ) -H(θ θ ′ ,i j , Y j+1 ) | 2

1 j=i 1 -γ 1 i 1 / 2

 11112 jθ θ ′ ,i j , ∆M θ,i j+1 -∆M θ ′ ,i j+1 (A.2)where γj+1 := γ j+1 / j k=i 1 -2λγ k+1 + [H] 2 1 γ 2 k+1 .Taking the expectation in (A.2), we derive:E[|θ i,θ nθ i,θ ′ n | 2 ] |θθ ′ | 2 ≤ n-2λγ j+1 + [H] 2 1 γ 2 j+1 .Now:|f γ i (θ, y)f γ i (θ, y ′ )| = |E[|θ i,θ-γiH(θ,y) n θ * |] -E[|θ i,θ-γiH(θ,y ′ ) n θ * |]| ≤ E[|θ i,θ-γiH(θ,y) n θ i,θ-γiH(θ,y ′ ) i [H] 1 |yy ′ | = Π n Π -γ i [H] 1 |yy ′ |,which completes the proof of the Proposition.

  a sequence of i.i.d. random variables we have that (∆M

n ) n≥1 is a sequence of martingale increments w.r.t. the natural filtration (F n

Acknowledgments

We would like to thank Florent Malrieu for fruitful discussions and two anonymous referees for their careful reading and comments. We thank Bernard Bercu who pointed out an error in the control of the bias in the previously published version of this work.


Hicham Badri
email: hichammbadri@gmail.com

Mohammed El Hassouni
email: mohamed.elhassouni@gmail.com

Driss Aboutajdine

Kernel-Based Laplacian Smoothing Method for 3D Mesh Denoising

In this paper, we present an improved Laplacian smoothing technique for 3D mesh denoising. This method filters directly the vertices by updating their positions. Laplacian smoothing process is simple to implement and fast, but it tends to produce shrinking and oversmoothing effects. To remedy this problem, firstly, we introduce a kernel function in the Laplacian expression. Then, we propose to use a linear combination of denoised instances. This combination aims to reduce the number of iterations of the desired method by coupling it with a technique that leads to oversmoothing. Experiments are conducted on synthetic triangular meshes corrupted by Gaussian noise. Results show that we outperform some existing methods in terms of objective and visual quality.

Introduction

Denoising is one of the greatest challenges in image processing and computer graphics. Fast and efficient algorithms are needed to recover noised data (images and 3D models) while preserving their geometrical structure. Measurements are perturbed by noise in all real applications. Notably, 3D models acquisition using scanners. These scanners provide the real scanned object as a 3D digital mesh, usually represented as a triangular mesh, that can be manipulated by any 3D processing tool, for many purposes in various fields such as medical imaging, video games, etc ... In recent years, various partial differential equations (PDE)-based techniques have been used for 2D image denoising such as the anisotropic diffusion proposed by P. Perona et al. [START_REF] Perona | Scale space and edge detection using anisotropic diffusion[END_REF]. 2D image denoising techniques were adapted for 3D mesh denoising. Taubin [START_REF] Taubin | A signal processing approach to fair surface design[END_REF] proposed a Laplacian-based technique called Laplacian flow that repeatedly adjusts the location of each vertex to the geometric center of its vertex neighborhood. This technique is quite simple and fast but produces an oversmoothing result. Many anisotropic diffusion methods were proposed such as the diffusion and curvature flow technique presented in [START_REF] Desbrun | Implicit fairing of irregular meshes using diffusion and curvature flow[END_REF], this method gives better results than the Laplacian flow technique but takes more processing time.

Y. Zhang et al. proposed an efficient diffusion technique [START_REF] Zhang | Vertex-Based Diffusion for 3-D Mesh Denoising[END_REF] based on solving a nonlinear discrete partial differential equation. M. El Hassouni et al. improved this technique [START_REF] El Hassouni | 3D-Mesh denoising using an improved vertex based anisotropic diffusion[END_REF] by using other diffusion functions such as Laplacian, Reduced Centered Gaussian and Rayleigh function instead of the Cauchy function.

In this article, we propose a vertex-based method for 3D mesh denoising. The main idea is to reduce the smoothing effect by introducing a kernel function in the Laplacian flow expression. Then we present a linear combination of denoised instances in order to reduce the number iterations of the desired technique by combining it with a fast (oversmoothing) technique like the local averaging method. Experimental results show that the proposed work gives competitive results in comparison with existing methods while reducing the processing time.

This paper is organized as follows : Section 2 presents the problem formulation. Section 3 describes the Laplacian smoothing method. In section 4, we present the proposed work. Section 5 deals with experimental results. Finally, we give some concluding remarks in Section 6.

Problem Formulation

A 3D object is usually presented as polygonal or triangular mesh. A triangle mesh M denotes a triple M = (V, E, T ) where V = {v 1 , ..., v k } represents the set of vertices, E = {e ij } denotes the set of edges and T = {t 1 , ..., t n } denotes the set of triangles. An edge e ij consists of two vertices {v i , v j } and we say that two vertices v i , v j ∈ V are adjacent if the are connected by an edge e ij ∈ E (and we write v i ∼ v j ). We define the neighborhood of a vertix v i , the set of adjacent vertices

v * i = {v j ∈ V : v i ∼ v j }. The degree of a vertex v i is the number of the neighboring vertices d(i) = | v * i |.
We denote by t * i the set of all triangles sharing a vertex or an edge with a triangle t i ∈ T and by T (v * i ) the set of triangles of the neighborhood v * i . We denote by n(t j ), with t j ∈ t * i a triangle, the unit normal of t j and by n i the normal at a vertex v i given by the following formula :

n i = 1 d i tj ∈T (v * i ) n(t j ) (1)
We denote by A(t j ) the area of the triangle t j . The mean edge length l of the mesh is given by :

l = 1 |E| eij ∈E e ij ( 2
)
Where

e ij = v i -v j if v i ∼ v j e ij = 0 otherwise
Measurements are perturbed by noise (supposed additive in our case) in all real applications. This can be formulated by :

v = v + η ( 3
)
Where v is the observed vertex, v is the original one and η is a random noise process assumed to be Gaussian.

Laplacian Smoothing

Laplacian Smoothing is a very simple PDE-based smoothing approach formulated as follows [START_REF] Taubin | A signal processing approach to fair surface design[END_REF]:

v i ← v i + vj ∈v * i v j -v i d i (4)
This process can be done repeatedly to correct the location of each vertex to the geometric center of its neighboring vertices. This approach is simple and fast, however, it produces an oversmoothing result after few iterations. Note that the Laplacian Smoothing is just a special case of the Weighted Laplacian Filter [START_REF] Desbrun | Implicit fairing of irregular meshes using diffusion and curvature flow[END_REF], also called Local Averaging:

v i ← v i + 1 vj ∈v * i w ij vj ∈v * i w ij (v j -v i ) (5)
Where w ij are the weights defined as :

w ij = > 0 if v j ∈ v * i 0 otherwise For w ij = 1 if v j ∈ v * i we retrieve the Laplacian Smoothing update rule, vj ∈v * i w ij = d i .

Proposed Method

In this section, we present at first an improved version of the Laplacian technique by introducing a kernel function. Then, we propose a linear combination of two denoised instances in order to reduce the number of iterations.

Kernel Based Laplacian Smoothing

The proposed approach consists in introducing a kernel function g to attenuate the added term, hence, overcome the oversmoothing problem.

The update rule is given by :

v i ← v i + vj ∈v * i v j -v i d i g(|∇v i |) ρ ( 6
)
Where

|∇v i | = ⎛ ⎝ vj ∈v * i v i √ d i - v j d j 2 ⎞ ⎠ 1/2 (7)
g is a kernel function and ρ is a parameter to estimate, it can be either a scalar or a 3D vector (x,y,z). In this paper, we are going to use ρ as a scalar.

Another update rule can also be used, inspired by [START_REF] Zhang | Vertex-Based Diffusion for 3-D Mesh Denoising[END_REF]:

v i ← v i + vj ∈v * i v j -v i d i g(|∇v i |) + g(|∇v j |) ρ (8)
The same functions in [START_REF] El Hassouni | 3D-Mesh denoising using an improved vertex based anisotropic diffusion[END_REF] can be used as a kernel function. Note that for the following ρ value applied to the equation ( 8), we retrieve the formula presented in [START_REF] Zhang | Vertex-Based Diffusion for 3-D Mesh Denoising[END_REF] :

⎧ ⎪ ⎨ ⎪ ⎩ ρ = √ didj di+ √ didj +β β = -vj √ didj+vidi vj -vi
The update rule ( 6) is the one that will be evaluated in this paper.

Linear Combination

The following method consists in combining 2 techniques using the following linear formula :

M = α M 1 + (1 -α) M 2 , α∈ [0, 1] (9)
Where M 1 is the denoised mesh with the method 1 and M 2 and denoised mesh with the method 2. This technique can be used to reduce the number of iterations of the desired technique by coupling it with a fast method that leads quickly to oversmoothing (like the Local Averaging).

The only combining approach that will be evaluated in this paper is the Local Averaging.The version used is the same one in [10]. Other combinations may give better results.

Experimental Results

This section presents simulation results where the proposed method is applied to 3D models contaminated by an additive zero-mean Gaussian noise. For ease to use, we developed a simple Graphical User Interface using Matlab/Java and the toolbox graph [10]. The 3D objects used in this section are presented in Figure 1. To quantify the performance of the proposed method in comparison with other 3D mesh denoising techniques, we compute the facenormal error metric [START_REF] Taubin | Linear Anisotropic Mesh Filtering[END_REF] given by :

E fne = 1 A( M) ti∈ T A( ti ) n(t i ) -n( ti )
Where n(t j ) and n( ti ) are the unit normals, A( ti ) is the area of the triangle ti and A( M) is the total area of the mesh defined by the following formula :

A( M) = ti∈ T A( ti )
We also use the visual error metric given by :

E ve = 1 2m m i=1 v i -vi 2 + m i=1 I(v i ) -I(v i ) 2 I(v i ) = v i -1 di vj ∈v * i v j
This metric is computed on mesh vertices. For all methods, parameters have been tuned experimentally in order to get the best trade-off between the visual error and the face-normal error for each technique. Also, We choose to report results only for one Kernel function and one noise level for each processed object. Here, use Laplacian as a Kernel function for all experiments with (c = 2). Figures 3 and5 show the visual errors and Face-normal error for compared denoising methods. We remark that proposed method (kernel based Laplacian (e)) outperforms the standard Laplacian smoothing (b) and the improved vertexbased diffusion (d). Note that only one iteration is sufficient in this case, while 5 iterations were needed for the improved vertex-based diffusion. According to these graphs, linear combination gives better results for the improved vertexbased diffusion (f) while reducing the number of iterations. Combining proposed method and local averaging improves slightly the denoising performance. Figure 2 and 4 are given to assess the visual impact of the denoising. We can see that for both case the Kernel Based Laplacian processed objects exhibit a more appealing visual appearance.

Note that Local Averaging using one iteration was the only technique used in the linear combination scheme. Other combinations may give better results.

Conclusion

We presented in this paper an kernel-based Laplacian smoothing method for 3D mesh denoising. The main idea is to reduce the smoothing effect by introducing a kernel function. Then we proposed a linear combination of denoised instances by different techniques. This method can be used to reduce the number of iterations in iterative denoising techniques of the desired method by combining it with a very fast (oversmoothing) technique like the local averaging method. Experimental results showed that the kernel-based Laplacian method proposed outperforms the standard Laplacian technique and the improved vertex-based diffusion [START_REF] El Hassouni | 3D-Mesh denoising using an improved vertex based anisotropic diffusion[END_REF] while using only 1 or 2 iterations. The linear-combination technique gave also good results while reducing the number of iterations. Using other techniques instead of the Local Averaging may give better results.

Fig. 1 .

 1 Fig. 1. 3D meshes used for experimentation : (a) mushroom (226 vertices), (b) nefertiti (299 vertices)

Fig. 2 .

 2 Fig. 2. Mesh denoising results for the mushroom instance. (a) Noisy 3D model σ² = 0.0015, (b) Laplacian smoothing (1 iteration), (c) Local Averaging (1 iteration), (d) Improved vertex-based diffusion (5 iterations), (e) Kernel-based Laplacian (1 iteration, ρ = 0.65) , (f) Linear combination : Local Averaging (1 iteration) + improved vertexbased diffusion, (3 iterations, α = 0.53), (g) Linear-combination : Local averaging (1 iteration) + kernel-based Laplacian (3 iterations, α = 0.58, ρ = 2)

Fig. 3 .

 3 Fig. 3. Visual Error and Face-normal error for the mushroom object

Fig. 4 .

 4 Fig. 4. Mesh denoising results for the nefertiti instance. (a) Noisy 3D model σ² = 0.001, (b) Laplacian smoothing (1 iteration), (c) Local Averaging (1 iteration), (d) Improved vertex-based diffusion (3 iterations), (e) Kernel-based Laplacian (1 iteration, ρ = 0.72) , (f) Linear-combination : Local Averaging (1 iteration) + improved vertexbased diffusion (1 iteration, α = 0.3), (g) Linear-combination : Local averaging (1 iteration) + kernel based Laplacian (1 iteration, α = 0.28, ρ = 3)

Fig. 5 .

 5 Fig. 5. Visual Error error and Face-normal error for the nefertiti object

A. Elmoataz et al. (Eds.): ICISP 2012, LNCS 7340, pp. 77-84, 2012. © Springer-Verlag Berlin Heidelberg 2012


Dr Adel Soudani
email: adel.soudani@issatso.rnu.tn

Thierry Divoux
email: thierry.divoux@cran.uhp-nancy.fr

Rached Tourki
email: rached.tourki@fsm.rnu.tn

Data traffic load balancing and QoS in IEEE 802.11 Network: Experiemental study of the SNR Effect

Keywords: IEEE 802.11, Load Balancing Algorithm, Signal to Noise Ratio, Quality of service, video transmission

Recently there is a growing interest in the internet and multimedia wireless networking where the bandwidth and the Quality of Service ( QoS) should be managed with careful. The performances of applications built on these systems depend on bandwidth availability that arises as the most limit of this solution. In fact, the IEEE 802.11 standards do not provide performed mechanism of loading distribution among different APs of the network. Then, an AP can be heavily overloaded leading to station throughput degradation.

For this problem, load balancing algorithms (LBA) was been considered as one of the attractive solution to share the traffic through the available access points (APs) bandwidths. However, applying the load balancing algorithm (LBA) and shifting a mobile connection from an access point to another without considering the signal to noise ratio (SNR) of the concerned APs might causes worst communication performances. This paper is then a contribution to check the performance's limits of the LBA algorithm through an experimental study of communication metrics for MPEG-4 video transmission over IEEE 802.11 network. The paper focuses, then, on the proposition of a new structure of the LBA algorithm with the introduction of the SNR level.

Introduction.

Nowadays, Hotspots environment based on IEEE 802.11 networks are widely used due to their low-cost hardware infrastructure. The growing interest in the internet and in multimedia wireless networking in these hotspot environments has revealed the necessity to focus more on the quality of service management [START_REF] Balachandran | Characterizing User Behavior and Network Performance in a Public Wireless LAN[END_REF][START_REF] Ni | A Survey of QoS Enhancements for IEEE 802.11 Wireless LAN[END_REF]. In the work presented in [START_REF] Jabri | IEEE 802.11 Load Balancing: An Approach for QoS Enhancement[END_REF], we have studied the different mechanisms of quality of service, being adopted in the IEEE 802.11 based networking systems. We have defended in this paper a general approach based on a centralized architecture intended to share mobiles on available APs that belong to the hotspot environment. The proposed approach is based on the use of the Load Balancing Algorithm (LBA) [2, 3, and 4]. The basic idea of the LBA algorithm is to ensure a fair (balanced) distribution of the traffic. For that purpose, if a new mobile access to the network or when a mobile change the BSS or when the application level change the requirements the LBA algorithm will be processed to find the best new distribution based only on traffic load criterion for fair bandwidth use. The load balancing algorithm (LBA) will evaluate the traffic load of each access point in the network to decide whether it is considered as under-loaded or overloaded. According to the LBA server decision, a new distribution of mobiles will be applied. Then, some mobile's connections will be shifted from AP to others, regardless the quality of their channel links, in the aim to share the general bandwidth of the network, We presented in [START_REF] Jabri | IEEE 802.11 Load Balancing: An Approach for QoS Enhancement[END_REF] an efficient centralized architecture for the application of this approach. We designed the a protocol structure to manage data transaction between the LBA server, APs, and mobiles. A set of required new requests for quality of service handling in this architecture has been defined and checked with SDL tool. In addition, a simulation study was been carried using Opnet tool to testify the performances of our approach when applied to a network with different data flow types. The results obtained in this study proved the efficiency of this approach to enhance the quality of service at the receiver application level. It shows that, with the LBA application, the global dropped data amount at the network was minimised, the MAC access delay has been enhanced and the average network throughput to the applications' layers was increased. . Despite the good performances proved with the application of the ,load balancing algorithm, our work proposed in [START_REF] Jabri | IEEE 802.11 Load Balancing: An Approach for QoS Enhancement[END_REF] had not addressed the limitations of the LBA approach. In fact, when finding the optimal distribution, the LBA server doesn't take in account the SNR of the new target AP and no comparison with the SNR of the current AP will be performed. So, it may happen that a mobile will be moved from an AP to another one that provides less SNR level that might destroy the quality of service. Taking in account the Shannon formula about the bandwidth effectively offered (C max ) by an access point that is expressed by equation 1.

C max = BW * log 2 (1 + SNR) [START_REF] Balachandran | Characterizing User Behavior and Network Performance in a Public Wireless LAN[END_REF] Where BW is the bandwidth and SNR is the signal-to-noise ratio. Based on that we think that more work is yet required to explore the application's limits of the LBA approach. The impact of the SNR level of the wireless channel link to the efficiency of the LBA application should be clarified in order to correlate the involving of the SNR with the traffic load consideration in a new structure of the Load Balancing Algorithm (LBA).

This paper contributes in this objective at three levels.. It aims first of all to make a proof with an experimental study on the efficiency of the LBA algorithm to improve the quality of service not only in the network level, as being studied in [START_REF] Jabri | IEEE 802.11 Load Balancing: An Approach for QoS Enhancement[END_REF], but also at the quality of service at application's processes. At a second level, this paper explores the application's limits of the LBA algorithm to enhance the quality of service in a communication process in regard to SNR of the wireless channel between the mobile station and the AP.. For this purpose, this paper presents a set of experimentation concerning the analysis of the LBA effect on the quality of service with the consideration of the associated SNR connection between the mobile and the access point AP. The main goal of this third part is to involve the SNR as a parameter in the LBA algorithm decision.

In that case, the shifting of a mobile to a new connection with another AP will be applied not only with the traffic balancing consideration but also with the SNR value. Then, based on the obtained results the paper presents a new structure of the LBA algorithm.

Overview of QoS in IEEE 802.11 and related work

The basic criterion to establish a connection for a mobile in overlapped IEEE 802.11 cells is the level of the Signal to Noise Ratio (SNR). This criterion is based on the Shannon formula expressing the available bandwidth as an increasing function of the SNR value. As a consequence, a mobile station is associated to the access point offering the best Signal by Noise Ratio (SNR) independently of the load being applied to the access point by other users. This can cause, in many cases, unbalanced load between access points. Some access points will be over loaded, others are under loaded. When an access point is overloaded, applications requirements are not fulfilled and the end users will not be satisfied about the ensured quality of service (QoS) [START_REF] Jabri | IEEE 802.11 Load Balancing: An Approach for QoS Enhancement[END_REF][START_REF] Bianchi | Improving Load Balancing Mechanisms in Wireless Packet Networks[END_REF]. To better manage quality of service in these networks, different mechanisms have been proposed to enhance the communication processes. We cite here some of the most important [START_REF] Ni | A Survey of QoS Enhancements for IEEE 802.11 Wireless LAN[END_REF].

• Service Differentiation. Basically, service differentiation is achieved by two main methods: priority and fair scheduling [START_REF] Pattara-Atikom | Distributed Mechanisms for Quality of Service in Wireless LAN[END_REF]. While the former binds channel access to different traffic classes by prioritized contention parameters, the latter partitions the channel bandwidth fairly by regulating wait times of traffic classes in proportion according to given weights [START_REF] Ni | A Survey of QoS Enhancements for IEEE 802.11 Wireless LAN[END_REF]. Used parameters for both approaches are associations. The authors of [START_REF] Balachandran | Characterizing User Behavior and Network Performance in a Public Wireless LAN[END_REF] describe a centralized load balancing algorithm which is not completely transparent to wireless users: stations have to explicitly change positions to get the required quality of service. A scheme proposed in [START_REF] Brickley | Load balancing for QoS enhancement in IEEE802.11e WLANs using cell breathing techniques[END_REF] aims to fairly distribute load between access points by changing their coverage area. Some other works describe load balancing mechanisms for 802.11 wireless networks but are applied in particular contexts such as in [START_REF] Zhao | Admission control with load balancing in IEEE 802.11-based ESS mesh networks[END_REF] which study a routing connection admission control in ESS (Extended Service Set) mesh networks.

In [START_REF] Al-Rizzo | Enhanced Channel Assignment and Load Distribution in IEEE 802.11 WLANs[END_REF], Al-Rizzo et al proposed an algorithm to decrease congestion and to balance the user's traffics in IEEE 802.11. Each access point has one different AP channel to avoid congestion event and signal interference problems. The algorithm found the Most Congested Access Point (MCAP), analyses the users association and decrease the congestion of MCAP. A user will not be connected to an AP with the result that the Signal to Interference Ratio (SIR) is positive and the signal power is more than a fixed threshold. [START_REF] Brickley | Load balancing for QoS enhancement in IEEE802.11e WLANs using cell breathing techniques[END_REF][START_REF] Hajiaghayi | Cell breathing in wireless lans: algorithms and evaluation[END_REF] Presented a Cell breathing Technique to balance the APs load and improve QoS of real time applications. It reduces the signal length of the congested APs (cell area), so reduce the AP's impact and user's number per congested AP. On the other hand, it increase the signal length and the impact of the under loaded APs. Then, as a result, it makes new connection with the disconnected stations.

T. Scully et al in [START_REF] Scully | Wireless LAN load balancing with genetic algorithms[END_REF] had studied the efficiency of Genetic-based load balancing algorithm. They proposed, for this purpose, two algorithms: the first one is a standard genetic algorithm (MacroGA), while the second is a micro-genetic algorithm ( MicroGA). They evaluated these algorithms using an empirical approach and they demonstrated that both algorithms outperform the WLAN techniques in terms of total network throughput and distribution of user bandwidth. However, the studied approach doesn't consider the signal strength in the mobile distribution among the available access points.

The proposed architecture supporting the LBA for QoS enhancement

The architecture we have proposed to support the application of the LBA algorithm is a centralized architecture around a Load balancing server able to provide the best mobile distribution any time a new event will occur in the network. We have proposed for this architecture a protocol structure for the set of exchanged request making up the different steps of signaling, connection association and dissociation between mobiles and APs [START_REF] Jabri | IEEE 802.11 Load Balancing: An Approach for QoS Enhancement[END_REF].

Even though that, in general, the centralized architecture may not be the suitable one for communication environment with user QoS constraints since it leads to a system with one point failure, this architecture is the most adequate to the LBA application. In fact, to find the best new fair mobile station distribution the LBA algorithm requires a collection of the different AP traffic load states. In a distributed approach for LBA application, the decision will take more processing time and requires more interactions between AP that increases the traffic load for APs. The LBA can be summarised as follow, the algorithm checks if the new distribution is balanced mainly by computing a balance index β. The balance index appeared in the first time in [START_REF] Chiu | Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks[END_REF] and it is used in [START_REF] Balachandran | Characterizing User Behavior and Network Performance in a Public Wireless LAN[END_REF][START_REF] Velayos | Load Balancing in Overlapping Wireless Cells[END_REF] as a performance measure. The balance index reflects the used capacity in each access point. It is computed in each overlapping zone between two or more APs in the WLAN Extended Service Set.

Let Ti be the total traffic of the APi. Then, the balance index β j of an overlapping zone Z j is:

β j = (Σ i T i ) 2 / (n*Σ i T i 2 ) ( 2
)
With Ti is the total traffic of an APi overlapping with other access points in the zone j and n is the number of access points overlapping in the zone j.

The proposed distribution of mobile stations is balanced if the balance indexes of all the overlapping cells converge to 1. At this step, overlapping Access Points in the Wireless LAN are fairly loaded. We use a tolerance parameter α that defines the balancing zone width. We use therefore the Average Network Load (ANL) calculated as:

ANL= Σ i T i / n (3)
δ 1 = ANL + α.ANL. (4)
δ 2 = ANL -α.ANL (5)
It is balanced when its load is in the interval [δ 1 , δ 2 ], An AP is under loaded if its load is under δ 2 (equation 5). The α parameter acts upon the stability of the system, when its value go near zero an access point state will topple during the LBA application between over-loaded and under-loaded state. In this case it will not be easy to find the best distribution and the algorithm may not converge. The compromise that should be considered during the definition of the α value is to get a sufficient gap within the AP will be considered loaded, but not too much to get unfair traffic load distribution. In [START_REF] Jabri | IEEE 802.11 Load Balancing: An Approach for QoS Enhancement[END_REF] we have used 20% as value of α, but we think that it can range between 10% et 20% according to the network and the application constraints.

When a new mobile station asks for a connection with an access point, this later will check if it will be able to provide the required bandwidth for the user application. If possible the connection request will be accepted and the LBA server will not be invoked, avoiding network instability. In the other case the load balancing algorithm calculates the average network load, the δ 1 and δ 2 balancing thresholds for all the APs in the network. If there is some overloaded access point, the algorithm has to seek for a new distribution of mobile stations to have balanced load among access points. Mobile stations have to be moved from overloaded access points to less loaded ones overlapping in the zone min. Zone min is the overlapping zone which has the minimum balance index value. The load balancing algorithm computes the difference between the load of the most loaded AP and the average network load. The station to move is the one with the load nearest to this difference.

As being explained in the previous section, in the LBA algorithm, the dissociation between a mobile and an access point is taken with the only consideration of APs load balancing. The moving decision doesn't care about the comparison between source and destination AP provided SNR. So, even it had been proved that the LBA enhances the provided quality of service at the reception level it is clear that in its actual structure, the LBA suffers of some limits.

In this context, this paper presents an experimental study in order to check the efficiency of the LBA application and to discover its limits

Experimental target platform and QoS metrics

The basic idea we had adopted to check the influences of the LBA algorithm application is summarised in figure 2. In this architecture some communication processes have been introduced to load the APs. These processes carry FTP and HTTP traffics. A specific MPEG4 short head video process has been, also, used to analyse the quality of service provided with a connection through AP1 and AP2. The connection with AP1 and AP2 are provided with different SNR values. The traffic load of an AP is being calculated as the average sum of its up-link and the down-link traffic.

AP2 AP1 BSS 2 BSS 1
To make possible the analysis of the quality of service ensured for a communication process, we had developed a specific Java-client application. This application (QoS monitoring) is able to measure a set of parameters that can be used to quantify the quality of service provided for the communication process at the receiver level.

The application receives the data flow from the appropriate communication channel of the wireless video camera (Trend net IP 300 w). This camera incorporating an embedded video server, provides MPEG-4 short header coded data structure with different resolutions and different image's rates (1, 3, 7, 15, 25 images/s).

As, a standard way to use this camera, the provider makes easy to capture the video through internet navigator using HTTP protocol. However this method doesn't allow the user to analyse the different parameters of video quality, since he cannot add his appropriate function to make possible analysis of the provided video streaming.

Thus why, we have developed this application that pops the compressed video ( VAM format) form the memory of the server. Several metrics have been defined in order to quantify the quality of the received video stream. The analysis of the received flow is processed in real time (figure 3). So, the developed application calculates these values and plots the variation of the defined metrics during data reception.

General features of the processed video stream

As being previously explained, to evaluate the efficiency of the LBA application in regard to the provided SNR value and the traffic load of the associated AP, we have used the QoS Monitor application that allows to measure in a real time way different metrics.

Used QoS metrics,

As being explained in the previous section the QoS monitoring application provides a set of metrics. In this paper, we will present only the results for some metrics that we consider as the most significant to quantify the quality of service at the reception level: All of these metrics will be applied to the MPEG 4 short head process at the reception level in order to quantify the quality of service for the end user.

• The bit rate, it represents the most used criterion to measure the quality of service of a given communication process.

• The end to end delay, it reflects the capacity of the system to satisfy constraints of short time transmission for time sensitive applications.

• The Jitter, the fluctuation of the inter-arrival time image at the reception level influences mainly the synchronisation. More is the fluctuation of the jitter worst is the quality of the received video.

• Video PSNR (Peak Signal Noise Ratio), it represents the quality of the received video. It is calculated, in decibels, over all the video between source and received images. Its expression is given by equation 6 PSNR = 20 log 10 (255/RMSE),

With RMSE (Root Mean Square Error)

The mean-squared error is represented by the following equation:

In the previous MSE equation, I 1 and I 2 represent pixel's values respectively for the source image and the received image. M and N represents the number of rows and columns in the images. The video PSNR is calculated is the average PSNR of N images received in a time period.

Experimentation and quality of service analysis of the LBA algorithm application

As a first goal of this study we have tried to make an experimental proof that the application of LBA algorithm enhances the quality of service. We have measured the defined metrics at the reception level for different traffic loads of the AP and for different SNR values.

Figure 4 plots the evolution of the bit rate of the MPEG4 process at the reception level in regard to the traffic load and the SNR value. We notice that for an access point with different traffic loads, the bit rate of the processed MPEG flow increases with the SNR. However, we can also see that the evolution of the bit rate depends on the current traffic crossing the access point. In fact, with SNR value of 50 dB for traffic load 12237

Kbps the bit rate (243kbps) provided by the AP for the MPEG4 process is less than the bit rate (457 Kbps) provided with 2944 Kbps as à traffic load. In addition, figure 4 shows that with SNR level at 20 dB we can reach a bit rate of 360 Kbps through AP loaded of about 570 Kbps, this bit rate level is much more better than the bit rate provided with 50 dB under a bit rate level of 12237 Kbps (234 kbps).

We have measured, for the same experience, the end to end delay for image transmission between the wireless camera and the application running in a PC, through an AP. Figure 5 resumes the end to end delay according to the variation of the SNR and the AP load traffic. According to this graph, for all traffic loads, the image's end to end delay is conversely proportional to the SNR value. This statement confirms that the connection to AP with a high SNR value reduces the end to end delay. However, we note that for an AP traffic load of 12237 kbps with a high SNR value ( 50 dB), the image end to end delay (333 ms) is worse than the one measured ( 52 ms) for a traffic load of 480 kbps . This expresses that in general, the end to end delay, may not be improved through a new connection with high SNR value and heavy traffic load.

Traffic load

Figure 6 sums up the average of the absolute value of the image jitter at the reception level for different SNR levels and traffic loads. We see, through this figure, that the average of the image jitter absolute value decreases for the same traffic load (570 kbps) when the SNR value increases. However, this figure shows that the interval of jitter variation for a traffic load of 12237 kbps is very high with a maximum value of 300 ms. This measured interval for jitter range is the widest of all the measured interval within the set of traffic load values{2944 Kbps, 570 Kbps and 480 Kbps} values. This result confirms the expected conclusion that, obviously, when we load the AP we get decrease in the quality of service. The increase on the Jitter range is a symptom of big depth of packet's buffering that increases the packet losses probability and the end to end delays.

One other important note from this figure is that weak Jitter intervals was measured at 40 dB for all the values of traffic load when compared to the Jitter interval width measured for 12273 Kbps at 50 dB. This means that if we take only the SNR as a criterion, better quality of service can be ensured through connection with weak SNR level.

These results confirm the same observation. In fact, the jitter variation is not optimised only when we increase the SNR of Mobile/ AP connection. We should, in fact, consider the traffic load exchanged through this AP. The same note is confirmed for the quality of video received at the application level. Figure 7 summarises the MPEG4 quality with the PSNR values for different connection mobile-AP SNR levels and traffic loads.

Jitter Interval

This figure (figure 7) shows that the PSNR quality of the received video will be enhanced, for the same AP traffic load (815 kbps), when SNR level for the mobile/AP increases. This is an expected result since we know that the wireless link bandwidth will be increased with the increase in SNR level. With higher bandwidth the transmission time for packet decreases which in turn decreases the collusion rate and then the packet losses probability. However, we see that for 30 dB SNR level, we got a PSNR received video (44, 9 dB) when the traffic load is 570 kbps. With 11657 kbps AP traffic load, we have measured for higher SNR level ( 50 dB) a PSNR at 14.1 dB. This note reveals that the PSNR will not be increased automatically in all cases when we increase the SNR level. In fact the load of the target AP has a big influence.

As a conclusion of this first experimentation set of results, we can conclude that the SNR level that characterizes the physical link between mobiles and AP is not enough to predict the quality of service that will be ensured over the AP. In fact, over all these experimentations, it had been proved that the AP traffic load influences heavily the provided quality of service for a given communication process. Consequently, during the application of the LBA algorithm, when moving mobile from an AP connection to another, aiming to distribute the traffic and to optimize the provided quality of service, we have to care about the SNR level provided by the destination AP.

Duality between load traffic and SNR level for quality of service insurance

The question, at this level, is what should be the new proportions of the SNR level and the associated AP traffic load when taking the moving decision in the Load Balancing Algorithm (LBA) algorithm? For this purpose we have tried to evaluate through others experimentations the relation that should be considered for le LBA algorithm when sharing the mobiles through the available APs. We have used the same analysis platform to address this problem. So, while keeping the same communication process issued by the MPEG4 camera we have measured the quality of service for connection through two APs with different traffic loads. The same QoS metrics have been used to quantify the quality of the received video. The idea of these new measurements is to evaluate the QoS metrics, for the MPEG4 short head process, when the wireless video camera connection is moved from a heavily loaded AP (AP_1) to a new AP (AP_2) with under-load traffic state. The new connection with the AP_2 is being evaluated with different SNR level. The main goal is to bring out an association between the SNR and the traffic load when making the decision about the dissociation of a mobile from an access point (AP_1) and its association with a new AP (AP_2).

Figure 8 resumes the bit rate evolution when the connection is first of all established with a heavily loaded AP ( AP_1) and then moved to less loaded AP (AP_2). Figure 8 (a) shows that for the same SNR level (80 dB), when the connection is moved to AP_2 ( 4050 Kbps) which is less loaded compared to AP_1 (2100 kbps) the bit rate increases. We see, also, that even when AP_2 has a SNR connection, with the wireless video camera, of 50 dB we get an increase in bit rate, which means that this note continue to be right for higher SNR level ({60…80} dB). The same reading is applied for figure 8 (b &c) using different starting SNR with AP_1 and also different traffic load for AP_1 and AP_2.

The general conclusion is that when the connection is moved from AP_1 to AP_2, that is under-loaded, it will increases the bit rate for this connection unless the SNR for AP_2 (SNR_AP2) is equal or under than (SNR_AP_1/2).

For the others metrics studied in this section, only one figure for each metric will be presented to resume its evolution in regard to AP traffic load and the SNR connection level. Figure 9 represents the end to end image delay (ms) evolution when the connection is moved from AP_1 to AP_2. According to this figure we can see that the new connection with 80_dB with AP_2 will make short the end to end delay (0.096 ms instead of 0.13 ms). This enhancement in bit rate will not occur when the AP2 provides a SNR connection (SNR_AP2) for the mobile lower or equal to (SNR_AP1/ 2).

The quality of the received video is evaluated with the same scenario (figure 10). We note at this level the difficulty to get measurements for different SNR level and heavy traffic loads. This figure proves the same statement. In fact, the quality of the received video, evaluated with PSNR, will not be improved if the SNR connection with AP2 is not higher than (SNR_AP1/2). Based in the analysis of the previous measurements for QoS metrics, we have concluded that the structure of the LBA algorithm should be modified to take in account, both the provided SNR level and the data traffic, during the dissociation and the association between a mobile and two APs. the objective of this study is to introduce a new criterion when we apply the LBA for a fair sharing of the mobiles through the available APs to enhance the achieved QoS. We remind that the LBA algorithm is processed in different steps

• The first step, it consists of identifying which AP has to dissociate mobiles and which one can receive new connection. At this level the algorithm is based on the ANL (Average Network Load)

to determine for an overlapped area between two or more APs, those considered over-loaded and under-loaded. So, as being explained in section 3, an AP is considered balanced when its load is in the interval [δ 1 , δ 2 ] (figure 11).

ANL δ 2 = ANL -α.ANL

AP load

AP under-loaded AP loaded AP over-loaded

δ 2 = ANL + α.ANL
• The second step is to select from the overlapped area between two APs, the best candidate (mobile) to achieve the network balanced situation. In this step, we have to find the mobile that when moving it from the over-loaded AP to the under-loaded AP will contribute in the network traffic load balancing.

The main contribution we introduce in this algorithm is located at this step, in fact, we have proved, through the presented measurements of some QoS metrics, that these later will not be enhanced when moving the connection from AP to another unless the destination AP provides a SNR level at least higher or equal to the half of the SNR provided by the first AP. The new proposed decision in the LBA algorithm can be then summarized by figure 12. To evaluate the performances of this enhanced structure of the LBA algorithm we have applied it to a WLAN where we processed the wireless MPEG-4 video transmission within different others data communication processes based mainly on HTTP and FTP. The connection of the wireless camera (sender of MPEG-4 video process) has been shifted from AP-source (AP-S), considered heavily loaded and providing high SNR level, to AP-destination (AP-D) with less traffic load. We have considered during this study different offered SNR between the connection AP-D and the wireless camera in order to check up the capabilities of this new LBA structure to enhance the quality of service at the application level. Table 1 sums up the significant part of these results. Several QoS metrics have been evaluated for the connection with AP-S and AP-D. In this table some cells are labeled with 'NM' to Zone min is the overlapping zone which has the minimum balance index value [START_REF] Balachandran | Characterizing User Behavior and Network Performance in a Public Wireless LAN[END_REF] express that it was impossible to get these values either due to the weak signal strength or for overloaded traffic through the AP.

We see, that for all the considered metrics, the assumption, that the QoS will be enhanced when the LBA establishes a new connection with an AP that offers SNR level higher or equal than the half of the pervious connection SNR level, is verified. It is shown for all the metrics when the SNR level with the AP-D is equal to 40 dB or 50 dB. We see that the obtained values reflect better quality of service than that evaluated at 80 dB with heavy traffic load. We also see, for some metrics, that when the traffic load of the AP-D is too much low, the new connection can achieve better quality of service even with weak SNR level (less than 40 dB). In fact with a new connection with AP-D 30 dB having a data traffic load of 450 Kbps the obtained end to end delay (70 ms) is better than the measured value of this delay at 80 dB. This note confirms that our proposal to enhance the LBA structure is valid when we are at the same range of data traffic load, which is often the case in the LBA application. In this table, the As a conclusion, this experiment confirms that the new structure of this algorithm for load balancing in overloaded wireless network. It offers more reliability to enhance the quality of service in the network.

Several works had addressed the problem of load balancing and quality of service QoS in wireless environment. In these works, often, the traffic load and the signal strength had been considered independently. However, and as being shown in this paper, the best quality of service will be ensured when both of them are considered. Admission control with load balancing [17] MITOS [START_REF] Alyfantis | Exploiting user Location for Load Balancing WLANs and Improving Wireless QoS[END_REF] Inter-Access Point Communications [START_REF] Garcia | Inter-Access Point Communications for distributed Resource Management in 802.11 Networks[END_REF] Our solution As a first result, we have proved that the application of the LBA algorithm to share fairly the traffic through the available APs in the network will contribute in the enhancement of the QoS of the traffic at the reception level.

Wireless

As a second goal of this paper, we have addressed the relationship that should be considered between the provided SNR and the traffic load by the target AP and its comparison to those that characterize the current AP. We have conclude that a relationship should be filled between SNR levels of the source AP and the destination AP when moving a mobile connection as a decision of the LBA algorithm. Based on these results we have proposed a new structure for the LBA algorithm.

For the future work, we would like to extend the LBA structure in order to introduce others techniques that have been studied in related works such as cell breathing and channel allocation. In addition, further study should be carried to analyze the performances of centralize solution and distributed solution for the application of the LBA algorithm.

Figure 1 :

 1 Figure 1: The proposed IEEE 802.11 target architecture supporting the LBA algorithm

Figure 2 .

 2 Figure 2. Experimentation of the LBA algorithm application

Figure 3 .

 3 Figure 3. User interface for QoS Monitoring application

Figure 5 .

 5 Figure 5. End to end delay for image reception according to different SNR and AP traffic load

Figure 6 .Figure 7 .

 67 Figure 6. Image Jitter average variation in regard to the SNR and the traffic Load 20_dB 30_dB 40_dB 50_dB

Figure 8 ,

 8 Fig 8 (a)

7 .

 7 Enhanced new structure of the LBA algorithm

Figure 9 .Figure 10 .

 910 Figure 9. End to end image delay evolution for MPEG 4 process when moving connection from a loaded AP to balanced one

Figure 11 .

 11 Figure 11. General consideration in AP traffic load classification

Figure 12 .

 12 Figure 12. General consideration in AP traffic load classification

  In this paper, we have studied the enhancement achieved by the application of the LBA algorithm on the quality of service at the application level in IEEE 802.11 network. For this purpose, we have based our study on the analysis of some QoS metrics (Jitter, end to end delay, bit rate and PSNR) for a video MPEG-4 process transmission via different APs in the same network.

Table .

 . Performances evaluation of the LBA algorithm when considering the signal strength and the AP data traffic load measures of the absolute jitter values don't provide a good conclusion. This is due to the fluctuated nature of the jitter.

		Connected to AP1	Mobile station connected to AP2, acceptor for new connections,
		overloaded before			after applying the LBA
		applying LBA
			AP2 connection with different SNR levels and traffic load
		SNR= 80dB
		Traffic load for AP1	SNR		Traffic load for AP2 (Kbps)
		(Kbps)	(dB)
		4150 kbps		450	1000	1200	2010	3000	11000
	Bit rate (	495	30 dB	490	480	300	286	200	NM
	kbps)		40 dB	634	620	611	602	421	60
			50 dB	760	751	724	610	520	130
	Jitter (ms)	36	30 dB	028	035	036	036	037	NM
			40 dB	021	029	035	034	037	NM
			50 dB	021	029	035	034	036	NM
	Delay packet	220	30 dB	70	110	140	230	255	311
	(ms)		40 dB	59	100	123	190	208	295
			50 dB	55	65	118	170	192	240
	PSNR (dB)	20	30 dB	43	41.2	19.2	18.2	17.5	NM
			40 dB	46.5	45.2	26.9	20.9	20.7	NM
			50 dB	52.1	51.8	33.4	22	21.9	12.2

Table 2 .

 2 Table 2 sums up a comparison of our solution in regard to other proposed solutions. Comparison with other's solutions

	Load
	balancing
	through
	channel
	[19]