Patrick Cattiaux
email: cattiaux@math.univ-toulouse.fr

Arnaud Guillin
email: guillin@math.univ-bpclermont.fr

26d10

HITTING TIMES, FUNCTIONAL INEQUALITIES, LYAPUNOV CONDITIONS AND UNIFORM ERGODICITY

Keywords: Lyapunov functions, hitting times, uniform ergodicity, F-Sobolev inequalities, Poincaré inequality, ultracontractivity, 47D07, 60G10, 60J60

 that there is an equivalence between a Poincaré inequality, the existence of some Lyapunov function and the exponential integrability of hitting times. In the present paper, we close the scheme of the interplay between Lyapunov conditions and functional inequalities by

• showing that strong functional inequalities are equivalent to Lyapunov type conditions;

• showing that these Lyapunov conditions are characterized by the finiteness of generalized exponential moments of hitting times. We also give some complement concerning the link between Lyapunov conditions and integrability property of the invariant probability measure and as such transportation inequalities, and we show that some "unbounded Lyapunov conditions" can lead to uniform ergodicity, and coming down from infinity property.

Introduction

Let D be some smooth open domain in R d . In this paper, we will mainly consider the differential operator defined for smooth functions f ∈ C ∞ (D) by

Lf = 1 2 ij (σ σ * ) ij (x) ∂ 2 ij f ∂x ij + i b i (x) ∂ i f ∂x i ,
where σ is an R d×m smooth and bounded (for simplicity C ∞ b ( D)) matrix field and b a C ∞ ( D) vector field. We may see L as the infinitesimal generator of a diffusion process associated to the stochastic differential equation (SDE) dX t = σ(X t )dB t + b(X t )dt , X 0 = x , Date: April 18, 2016. where B t is an usual R m -Brownian motions when D = R d , or to the reflected SDE dX t = σ(X t )dB t + b(X t )dt + dN t , t 0 1 ∂D (X s )dN s = N t X 0 = x , if D is some smooth subdomain. The domain D(L) of L (viewed as a generator) is thus some extension of the set of smooth and compactly supported functions C ∞ c ( D) such that the normal derivative ∂f ∂n vanishes on ∂D (if ∂D is non void). This corresponds to normal reflection or to a Neumann condition on the boundary. We also define P t the associated semi-group

P t f (x) = E x (f (X t ))
which is defined for bounded functions f . In order to use classical results in PDE theory we will also assume that L is uniformly elliptic, i.e.

σ σ * ≥ a Id in the sense of quadratic forms for some a > 0, or more generally that L is uniformly strongly hypo-elliptic in the sense of Bony (see [START_REF] Bony | Principe du maximum, inégalité de Harnack et unicité du problème de Cauchy les opérateurs elliptiques dégénérés[END_REF]) and that the boundary is non characteristic. For details we refer to [START_REF] Cattiaux | Stochastic calculus and degenerate boundary value problems[END_REF].

We will also assume (though it should be a consequence of some of our assumptions) that there exists a probability measure µ(dx) = e -V (x) dx which is an invariant measure for the process (or the semi-group) i.e. for all bounded and smooth function f ∈ D(L), Lf dµ = 0 or equivalently for all t, E µ (f (X t )) = f dµ . P t then extends to a contraction semi-group on L p (µ) for 1 ≤ p ≤ +∞. We shall say that µ is symmetric, or that P t is µ symmetric if for smooth f and g in the domain of L, f Lg dµ = Lf g dµ .

The standard example of µ-symmetric semi-group is obtained for σ = √ 2 Id and b = -∇V (provided V is smooth enough). In all cases our ellipticity assumptions imply that this measure is unique and ergodic.

Among the most fascinating recent developments at the border of analysis and probability theory, a lot of work has been devoted to the study of the relationship between

• geometric properties of the measure µ, for instance concentration properties,

• functional inequalities (the study of weighted Sobolev or Orlicz-Sobolev spaces associated to L and µ) like the Poincaré (Wirtinger) inequality or the Gross logarithmic Sobolev inequality, • transportation inequalities like the T 2 Talagrand's inequality,

• the rate of convergence to equilibrium for the semi-group P t in various functional spaces, L 2 (µ), Orlicz spaces related to µ, • the rate of convergence of its dual P * t (i.e. the distribution of the process at time t) in total variation or in Wasserstein distance,

• the existence of Lyapunov functions, • and finally some properties of the stochastic process X . in particular existence of general moments for hitting times of some subsets (for instance the control of how the process comes down from infinity in the ultracontractive situation).

We refer to the monographs of Davies [START_REF] Davies | Heat kernels and spectral theory[END_REF], Ledoux [START_REF] Ledoux | The concentration of measure phenomenon, volume 89 of Mathematical Surveys and Monographs[END_REF], Wang [START_REF] Wang | Functional inequalities, Markov processes and Spectral theory[END_REF] and Bakry-Gentil-Ledoux [START_REF] Bakry | Analysis and Geometry of Markov Diffusion Operators[END_REF], the surveys by Gross [START_REF] Gross | Logarithmic Sobolev inequalities and contractivity properties of semi-groups[END_REF] and Ledoux [START_REF] Ledoux | Concentration of measure and logarithmic Sobolev inequalities[END_REF], the collective book [START_REF] Ané | Sur les inégalités de Sobolev logarithmiques[END_REF] and the papers [START_REF] Aida | Logarithmic Sobolev inequalities and exponential integrability[END_REF][START_REF] Bakry | Diffusions hypercontractives[END_REF][START_REF] Barthe | Interpolated inequalities between exponential and Gaussian, Orlicz hypercontractivity and isoperimetry[END_REF][START_REF] Barthe | Concentration for independent random variables with heavy tails[END_REF][START_REF] Barthe | Isoperimetry between exponential and Gaussian[END_REF][START_REF] Barthe | Mass transport and variants of the logarithmic Sobolev inequality[END_REF][START_REF] Bobkov | Poincaré's inequalities and Talagrands concentration phenomenon for the exponential distribution[END_REF][START_REF] Bobkov | Exponential integrability and transportation cost related to logarithmic Sobolev inequalities[END_REF][START_REF] Bobkov | Hypercontractivity of Hamilton-Jacobi equations[END_REF][START_REF] Cattiaux | A pathwise approach of some classical inequalities[END_REF][START_REF] Cattiaux | On quadratic transportation cost inequalities[END_REF][START_REF] Cattiaux | Weak logarithmic Sobolev inequalities and entropic convergence[END_REF][START_REF] Lata | Between Sobolev and Poincaré. in geometric aspects of Functional Analysis[END_REF][START_REF] Otto | Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality[END_REF] among many others, for the first four items.

For the last three items we refer to the monographs of Hasminskii [START_REF] Antonio | Has'minskii. Stochastic stability of differential equations[END_REF] and Meyn-Tweedie [START_REF] Meyn | Markov chains and stochastic stability[END_REF] and the papers [START_REF] Carmona | Exponential moments for hitting times of uniformly ergodic Markov processes[END_REF][START_REF] Douc | Subgeometric rates of convergence of f -ergodic strong Markov processes[END_REF][START_REF] Down | Exponential and uniform ergodicity of Markov processes[END_REF][START_REF] Glynn | A Liapounov bound for solutions of the Poisson equation[END_REF][START_REF] Meyn | Stability of markovian processes II: continuous-time processes and sampled chains[END_REF][START_REF] Meyn | Stability of markovian processes III: Foster-Lyapunov criteria for continuous-time processes[END_REF][START_REF] Yu | On polynomial mixing bounds for stochastic differential equations[END_REF] among many others.

The link between both approaches was done in [START_REF] Bakry | Rate of convergence for ergodic continuous Markov processes : Lyapunov versus Poincaré[END_REF] for the first time, up to our knowledge. It was extended in [START_REF] Bakry | A simple proof of the Poincaré inequality for a large class of probability measures[END_REF][START_REF] Cattiaux | Trends to equilibrium in total variation distance[END_REF][START_REF] Cattiaux | Lyapunov conditions for super Poincaré inequalities[END_REF][START_REF] Cattiaux | A remark on Talagrand's transportation inequality and logarithmic Sobolev inequality[END_REF][START_REF] Cattiaux | Some remarks on weighted logarithmic Sobolev inequalities[END_REF]. One can see the (now outdated) survey [START_REF] Cattiaux | Functional inequalities via Lyapunov conditions[END_REF].

To be a little bit more precise, let us recall the following result from [START_REF] Cattiaux | Poincaré inequalities and hitting times[END_REF] Theorem 2.3 (also see [START_REF] Kulik | Poincaré inequality and exponential integrability of the hitting times of a Markov process[END_REF] for a similar statement) (HP2) There exist an open connected bounded subset U and a constant θ > 0 such that for all x,

E x e θ T U < +∞ ,
where T U denotes the hitting time of U . (HP3) The process is geometrically ergodic, i.e. there exist constants β > 0 and C > 0 and a function W ≥ 1 belonging to L 1 (µ) such that for all x P t (x, .) -µ T V ≤ C W (x) e -β t , where P t (x, .) denotes the distribution of X t (when X 0 = x) and . T V denotes the total variation distance. (HP4) µ satisfies a Poincaré inequality, i.e. there exists a constant C P (µ) such that for all smooth f ∈ D(L),

Var µ (f ) ≤ C P (µ) E(f ) ,
where

E(f ) = -Lf f dµ = 1 2 |σ ∇f | 2 dµ .
(HP5) There exists a constant λ P (µ) such that for all f ∈ L 2 (µ),

Var µ (P t f ) ≤ e -λ P (µ) t Var µ (f ) .
Then (HP 5) ⇔ (HP 4), (HP 4) ⇒ (HP 2), (HP 2) ⇔ (HP 1) and (HP 1) ⇒ (HP 3). Actually (HP 4) implies (HP 2) for all (non-empty) open connected and bounded subset U . If in addition µ is symmetric, then (HP 1) ⇔ (HP 2) ⇔ (HP 3) ⇔ (HP 4) ⇔ (HP 5) .

When µ is not symmetric, examples are known (kinetic diffusions) where (HP 1) (hence (HP 3)) is satisfied but (HP 4) is not. In the case of kinetic diffusions, it is evident that (HP 4) cannot hold as the Dirichlet form is degenerate. It is however also possible to build "monster" diffusion where the invariant probability measure has some polynomial tail but the diffusion (with identity diffusion matrix) may converge exponentially fast and thus a Lyapunov condition holds.

The first equivalence is well known (see [START_REF] Ané | Sur les inégalités de Sobolev logarithmiques[END_REF]), the second one is a simple application of Ito's calculus and PDE results (see [START_REF] Cattiaux | Poincaré inequalities and hitting times[END_REF] and [START_REF] Cattiaux | Stochastic calculus and degenerate boundary value problems[END_REF]), the final implication is a consequence of the Meyn-Tweedie theory. The implication (HP 4) ⇒ (HP 2) is shown in [START_REF] Cattiaux | Poincaré inequalities and hitting times[END_REF] by using the deviation results for the occupation measure obtained in [START_REF] Cattiaux | Deviation bounds for additive functionals of Markov processes[END_REF] (using a beautiful deviation result obtained in [START_REF] Wu | Large and moderate deviations and exponential convergence for stochastic damping Hamiltonian systems[END_REF]). We shall see in the next section another much more direct approach. Finally, in the symmetric case the converse implications are obtained by using the method in [START_REF] Bakry | A simple proof of the Poincaré inequality for a large class of probability measures[END_REF].

Some extensions of this theorem to polynomial ergodicity are discussed in [START_REF] Cattiaux | Poincaré inequalities and hitting times[END_REF] in connexion with weak Poincaré inequalities. A deeper study of this situation is done in [START_REF] Löcherbach | Polynomial deviation bounds for recurrent Harris processes having general state space[END_REF][START_REF] Löcherbach | Spectral condition, hitting times and Nash inequality[END_REF][START_REF] Löcherbach | Polynomial bounds in the ergodic theorem for one-dimensional diffusions and integrability of hitting times[END_REF].

The questions we shall address in the present paper are not concerned with weakening but with reinforcing of the assumptions, that is, does it exist similar results as in Theorem 1.1 if we replace the Poincaré inequality by stronger inequalities, for instance F -Sobolev inequalities in the spirit of [START_REF] Aida | Uniform positivity improving property, Sobolev inequalities and spectral gaps[END_REF][START_REF] Barthe | Interpolated inequalities between exponential and Gaussian, Orlicz hypercontractivity and isoperimetry[END_REF][START_REF] Barthe | Isoperimetry between exponential and Gaussian[END_REF] ?

Partial answers are known: an F -Sobolev inequality is equivalent to exponential stabilization in some Orlicz space (see [START_REF] Roberto | Orlicz-Sobolev inequalities for sub-Gaussian measures and ergodicity of Markov semi-groups[END_REF]) and in the symmetric situation, reinforced Lyapunov conditions imply super-Poincaré inequalities or F -Sobolev inequalities (see [START_REF] Cattiaux | Lyapunov conditions for super Poincaré inequalities[END_REF][START_REF] Cattiaux | A remark on Talagrand's transportation inequality and logarithmic Sobolev inequality[END_REF][START_REF] Cattiaux | Some remarks on weighted logarithmic Sobolev inequalities[END_REF]). Recently, Liu ([47, 46]) proposed some new ideas in order to directly link Lyapunov conditions on one hand, concentration properties or functional inequalities on the other hand. Though some aspects of his proofs are a little bit obscure for us, we shall follow his main idea in order to deduce a Lyapunov condition from a functional inequality, and then get equivalent results in terms of hitting times. This yields the following result written here for the logarithmic Sobolev inequality which is the best known F -Sobolev

E x exp T U 0 θ |X s | 2 ds < +∞ ,
where T U denotes the hitting time of U .

(HLS2') There exist an open connected bounded subset U and a constant θ > 0 such that for all x,

E x exp T U 0 θ V (X s ) ds < +∞ ,
where T U denotes the hitting time of U . (HLS4) µ satisfies a logarithmic-Sobolev inequality, i.e. there exists a constant C LS (µ) such that for all smooth f ∈ D(L),

Ent µ (f 2 ) := f 2 ln f 2 f 2 dµ dµ ≤ C LS (µ) E(f ) ,
where

E(f ) = -Lf f dµ = 1 2 |σ ∇f | 2 dµ .
(HLS5) There exists a constant C E (µ) such that for all

f 2 ∈ L ln L(µ) s.t. f 2 dµ = 1, Ent µ (P t (f 2 )) ≤ e -C E (µ) t Ent µ (f 2 ) .
Then 1) (HLS5) ⇔ (HLS4), (HLS4) ⇒ (HLS1) and (HLS2) ⇔ (HLS1).

1') Assume that V goes to infinity at infinity and that there exists some a > 0 such that µ(e aV ) < +∞. Then (HLS5) ⇔ (HLS4), (HLS4) ⇒ (HLS1 ′ ) and (HLS2 ′ ) ⇔ (HLS1 ′ ).

Actually (HLS4) implies in both cases (HLS2) or (HLS2 ′ ) for all open nice subset U .

Assume in addition that µ is symmetric and that σ.σ * is uniformly elliptic.

2') Assume that V goes to infinity at infinity, that |∇V (x)| ≥ v > 0 for |x| large enough and that there exists some a > 0 such that µ(e aV ) < +∞.

Then (HLS1 ′ ) ⇔ (HLS2 ′ ) ⇔ (HLS4) ⇔ (HLS5).

2) Assume the curvature condition Ric + HessV ≥ -C > -∞ where Ricci and Hess are related to the riemanian metric defined by σ. Then (HLS1) ⇔ (HLS2) ⇔ (HLS4) ⇔ (HLS5).

Except (HLS5) ⇔ (HLS4) which is well known, we will prove this Theorem (and actually more general results) in section 3. Part of this result can be extended to general F -Sobolev inequalities, this is done in section 4.

The next two sections are devoted to the rate of convergence of P t (ν, .), the distribution at time t of the process with initial distribution ν, to the invariant distribution µ for the total variation distance. In section 5 Theorem 5.4 we get the following: under some natural assumptions on µ, almost any F -Sobolev inequality combined with the Poincaré inequality provides an exponential convergence

P t (ν, .) -µ T V ≤ C(ν) e -β t ,
for all ν absolutely continuous w.r.t. µ such that dν dµ belongs to L p (µ) for some p > 1. The remarkable fact here is that β does not depend on the integrability property (the p) of dν/dµ.

If this and more general results were proved in [START_REF] Cattiaux | Trends to equilibrium in total variation distance[END_REF], the proof given here is particularly simple and understandable. In the next section 6 we study L ∞ properties of the Lyapunov functions, in relation with the property of "coming down from infinity" for the process. In particular we show that if the ultra boundedness property of the semi-group implies the "coming down from infinity" property for the process, the converse is not true. All these notions are particularly relevant in the study of quasi-stationnary distributions.

Finally in the last section we directly rely general Lyapunov condition to the existence of some exponential moments for the measure µ, extending the results in [START_REF] Liu | Gaussian integrability of distance function under the Lyapunov condition[END_REF].

Back to the Poincaré inequality.

As we said in the introduction, we shall give here a new direct proof of (HP 4) ⇒ (HP 1) in Theorem 1.1.

c = µ(A) min 1 4C P (µ) , 1 8 .
It is easily seen that if A is smooth an bounded, we can modify W to get (HP 1) (with a λ smaller than the c in the theorem).

Proof. Let start with a simple lemma.

Lemma 2.2. Assume that µ satisfies a Poincaré inequality with constant C P (µ). Then for all subset A such that µ(A) > 0 and all f in H 1 (µ) = D(E) it holds

f 2 dµ ≤ 2C P (µ) µ(A) E(f ) + 4 µ(A) A f 2 dµ .
Proof. Using Poincaré inequality and the elementary

(a + b) 2 ≤ (1 + λ)a 2 + 1 + 1 λ b 2 for all λ > 0 we can write f 2 dµ ≤ C P (µ) E(f ) + µ 2 (f ) ≤ C P (µ) E(f ) + µ 2 (f 1 A + f 1 A c ) ≤ C P (µ) E(f ) + (1 + λ) µ 2 (f 1 A ) + 1 + λ λ µ 2 (f 1 A c ) ≤ C P (µ) E(f ) + (1 + λ) µ(A) A f 2 dµ + 1 + λ λ µ(f 2 )µ(A c )
where we have used Cauchy-Schwartz in the final inequality. Hence provided

µ(A)(1 + λ) -1 > 0 ,
we have obtained

f 2 dµ ≤ λ C P (µ) µ(A)(1 + λ) -1 E(f ) + λ(1 + λ) µ(A) µ(A)(1 + λ) -1 A f 2 dµ .
The result follows by choosing λ = 2(1 -µ(A))/µ(A).

Now define

φ(x) = -c + 1 A (x) , (2.3)
and introduce for all smooth u ∈ D(L),

Hu = -Lu + φ u .
On one hand, it holds

µ(u.Hu) ≤ E(u) + A u 2 dµ .
On the other hand, applying the previous lemma we have

µ(u.Hu) = E(u) + A u 2 dµ -cµ(u 2 ) ≥ E(u) + A u 2 dµ -c 2C P (µ) µ(A) E(u) + 4 µ(A) A u 2 dµ ≥ 1 2 E(u) + A u 2 dµ if we choose c = µ(A) min 1 4C P (µ) , 1 8
.

Now we will linearize µ(u.Hu). If v ∈ D(L) and u ∈ H 1 (µ), H(u, v) = µ(u.
Hv) is well defined, and using an integration by parts (or the Green-Rieman formula since the normal derivative of v at the boundary vanishes) can be written as a (non necessarily symmetric) bilinear form on H 1 (µ). It is easily seen that this bilinear form H is continuous on H 1 (µ) equipped with the (usual) hilbertian norm E(u) + u 2 dµ 1 2 , hence equipped with the hilbertian norm

E(u) + A u 2 dµ 1 2
which is equivalent according to Lemma 2.2. But according to what precedes, H is also coercive for this norm. Hence, we may apply the Lax-Milgram theorem which tells us that for any g ∈ H 1 (µ) there exists some v ∈ H 1 (µ) such that for all u, H(u, v) = u, g . We will use this result with g ≡ 1. First of all, the previous relation with u compactly supported in D shows that Hv = g in D ′ (D), so that thanks to ellipticity (or hypo-ellipticity), v ∈ C ∞ (D) and satisfies Hv = g in the usual sense in D. When D = R d this is enough. Otherwise, since the boundary is non characteristic, v admits sectional traces on ∂D of any order (see [START_REF] Cattiaux | Stochastic calculus and degenerate boundary value problems[END_REF] Theorem 4.6) and using the results in [START_REF] Cattiaux | Stochastic calculus and degenerate boundary value problems[END_REF]

section 4, one can see that v ∈ C ∞ ( D) and satisfies ∂ n v = 0 on ∂D. Since Hv ∈ L 2 (µ), it follows that v ∈ D(H).
As a routine, defining v -= min(v, 0), one can check using integration by parts or the Green-Rieman formula, that µ(v -.Lv) = E(v -) so that, using the previous lower bound we obtain,

µ(v -.g) = H(v -, v) = µ(v -.Hv) = µ(v -.Lv) + µ(φ.v.v -) = -E(v -) -µ(φ.v 2 -) ≤ - 1 2 E(v -) + A v 2 -dµ
and v -= 0 µ since g > 0. So v ≥ 0 almost surely.

One should now use the maximum principle but we prefer use Ito's formula. Assume that A is open and bounded. Since φ = -c on A c , we get for any d(y,A) < ε} we may finally let t go to infinity, use the fact that v is bounded from below by a positive constant v(A, ε) on ∂A ε which is compact and obtain that v(x) ≥ v(A, ε) for all x ∈ A c ε using the previous inequality (which actually furnishes exactly the minimum principle). For a general open set A just take the intersection with a large ball to get a bounded subset.

x ∈ A c , v(x) = E x (v(X t∧T A ) + E x t 0 1 s≤T A (Hv -φ v)(X s ) ds ≥ E x (t ∧ T A ) > 0 since T A > 0 if x ∈ A c . Replacing A by A ε = {y,
Remark 2.4. As soon as we know the existence of a Lyapunov function satisfying (HP 1) it immediately follows using Ito's formula with the function (t, y) → e λt W (y) that for all x,

W U (x) = E x (e λ T U ) < +∞ ,
and conversely, if the exponential moment is finite, W U is a Lyapunov function (see [START_REF] Cattiaux | Poincaré inequalities and hitting times[END_REF]). Also notice that the proof of Theorem 2.1 furnishes a Lyapunov function in H 1 (µ), hence in

D(L) since Lv = (1 A -c)v -1 implies Lv ∈ L 2 (µ). Hence the previous W U belongs to D(L). Conversely if W U is finite, LW U = -λW U in U c
. Replacing λ by λ/2 if necessary, we may assume that W U is in L 2 (µ) so that LW U is square integrable too (at least in U c ). If U is relatively compact it is easy to see that one can modify U and W U to get a smooth function everywhere that belongs to D(L). ♦

The logarithmic Sobolev inequality.

We start with an analogue of Theorem 2.1.

Proposition 3.1. Assume that µ satisfies the logarithmic Sobolev inequality (HLS4). Let h be a non-negative continuous function such that b = 2µ(e h ) < +∞.

For ε > 0, define U ε (h) = {(1 -ε)h > b}.
Then there exists a Lyapunov function

W ∈ D(L) such that W (x) ≥ w ε > 0 on U ε (h) and (HLh) LW ≤ - ε 2 C LS h W on U ε (h).
Proof. We follow and modify the proof in [START_REF] Liu | A link between the log-Sobolev inequality and Lyapunov condition[END_REF]. Assume that h is a non-negative function such that µ(e h ) < +∞. We follow the proof of Theorem 2.1 and define, for 2 ρ ≤ 1

C LS so that 2ρ Ent µ (u 2 ) ≤ E(u), φ(x) = ρ (-h(x) + b) , (3.2)
with b = 2µ(e h ) and introduce for all smooth u ∈ D(L),

Hu = -Lu + φ u .
On one hand, it holds µ(u.Hu) ≤ E(u) + ρ b µ(u 2 ) .

On the other hand, applying this time Young's inequality and LSI, we get for a smooth u ∈ D(L),

µ(u.Hu) = E(u) + ρ b µ(u 2 ) -ρ µ(hu 2 ) ≥ E(u) + ρ b µ(u 2 ) -ρ µ(u 2 ) µ e h - u 2 µ(u 2 ) + u 2 µ(u 2 ) ln u 2 µ(u 2 ) ≥ E(u) + ρ b µ(u 2 ) -ρ b 2 µ(u 2 ) + ρ µ(u 2 ) -ρ Ent(u 2 ) ≥ 1 2 E(u) + ρ b µ(u 2 ) .
We can then follow the proof of Theorem 2.1, and thus apply again the Lax-Milgram theorem to get the existence of a non-negative smooth function v ∈ H 1 (µ) satisfying

Lv = φ v -1 = -1 -ρ (b -h) v . If in addition h(x) > b , ∀x ∈ U c
we obtain that v is bounded from below by a positive constant in U c ε . The proof is completed.

This result is in particular interesting when D is not bounded and h goes to infinity at infinity. Two cases are mainly relevant, due to the converse statements we will prove below Corollary 3.3. Assume that µ satisfies the logarithmic Sobolev inequality (HLS4) and that D is not bounded. Then 1) for all x 0 ∈ D, there exists a Lyapunov function

W ∈ D(L) with W (x) ≥ w > 0 for all x ∈ D satisfying LW (x) ≤ -λ d 2 (x, x 0 ) W (x) + b ,
for some λ and b strictly positive; 2) if in addition V goes to infinity at infinity and e aV ∈ L 1 (µ) for some a > 0, there exists a Lyapunov function

W ∈ D(L) with W (x) ≥ w > 0 for all x ∈ D satisfying LW (x) ≤ -λ V (x) W (x) + b ,
for some λ and b strictly positive.

We may replace b by b1 A for some well chosen bounded subset A of D.

Proof. In case 2), just apply the previous proposition with h = a|V | and modify W in the corresponding level set A of V . For case 1), recall that the logarithmic-Sobolev inequality implies that there exists some c > 0 such that µ(e cd 2 (.,x 0 ) ) < +∞ and conclude as before with h = cd 2 (., x 0 ).

Introducing the process dH t = h(X t ) dt and applying Ito's formula to (H, x) → e ε 2 C LS H it is easy to show that (HLh) implies for all

x, W h,ε (x) = E x exp T U ε(h) 0 ε 2 C LS h(X s ) ds < +∞ . (3.4)
Conversely, if W h,ε (x) is finite for all x, using the arguments in [START_REF] Cattiaux | Stochastic calculus and degenerate boundary value problems[END_REF] one can prove that it satisfies (HLh) with an equality instead of an inequality. Notice that once again we may apply the arguments in Remark 2.4.

To complete the proof of Theorem 1.2, it remains to look at the converse statements in the symmetric situation. The first case is the case h(x) = cd 2 (x, x 0 ). Statement 2) in Theorem 1.2 under the curvature assumption is proved in [START_REF] Cattiaux | A remark on Talagrand's transportation inequality and logarithmic Sobolev inequality[END_REF] using transportation inequalities. An alternative method of proof was recently proposed in [START_REF] Liu | A link between the log-Sobolev inequality and Lyapunov condition[END_REF] (with some points to be corrected). For the second case h = aV we will use the results in [START_REF] Cattiaux | Lyapunov conditions for super Poincaré inequalities[END_REF] based on super-Poincaré inequalities.

Proposition 3.5. Assume that µ is symmetric and that σ.σ * is uniformly elliptic. Assume in addition that V goes to infinity at infinity, that |∇V (x)| ≥ v > 0 for |x| large enough and that e aV ∈ L 1 (µ) for some a > 0.

If there exists a Lyapunov function W with W (x) ≥ w > 0 for all x ∈ D, ∂W ∂n = 0 on ∂D and satisfying

LW (x) ≤ -λ V (x) W (x) + b ,
for some λ and b strictly positive, then µ satisfies a logarithmic-Sobolev inequality.

Proof. We follow the method in [START_REF] Cattiaux | Lyapunov conditions for super Poincaré inequalities[END_REF] Theorem 2.1 (itself inspired by [START_REF] Bakry | A simple proof of the Poincaré inequality for a large class of probability measures[END_REF]). Let A r = {V ≤ r}.

For r 0 large enough and some λ ′ < λ we have

LW (x) ≤ -λ ′ V (x) W (x) + b 1 Ar 0 ,
so that we may assume that LW W (x) ≤ -λ V (x) for x ∈ A c r and all r large enough.

Denote by M = sup(-V ). We have for s ≤ s 0 and r > r 0 ,

f 2 dµ = Ar f 2 dµ + A c r f 2 dµ ≤ e M 1 + b λr 0 Ar f 2 dx + 1 λr λV (x) f 2 dµ, ≤ e M 1 + b λr 0 Ar f 2 dx + 1 λ r f 2 -LW W dµ ≤ e M 1 + b λr 0 s Ar |∇f | 2 dx + C s d/2 Ar |f | dx 2 + 1 λ r |σ.∇f | 2 dµ .
The first part of the last bound is obtained by using (3.1.4) in [START_REF] Cattiaux | Lyapunov conditions for super Poincaré inequalities[END_REF] (it is here that we are using the assumption on |∇V |), while the second bound is obtained using integration by parts or the Green-Rieman formula (see [START_REF] Cattiaux | Lyapunov conditions for super Poincaré inequalities[END_REF] (2.2)). Using uniform ellipticity we thus obtain,

denoting c = e M 1 + b λr 0 µ(f 2 ) ≤ s c a + 1 λ r |σ.∇f | 2 dµ + C s -d/2 c e 2r |f | dµ 2 . (3.6)
Hence choosing r = c ′ /s we get the following super-Poincaré inequality for small s,

µ(f 2 ) ≤ s |σ.∇f | 2 dµ + C ′ e c/s |f | dµ 2 ,
which is known to be equivalent to a defective logarithmic Sobolev inequality (see the introduction of [START_REF] Cattiaux | Lyapunov conditions for super Poincaré inequalities[END_REF]). But the Lyapunov condition being stronger than (HP 1), we know that µ satisfies a Poincaré inequality, hence using Rothaus lemma, that it satisfies a (tight) log-Sobolev inequality.

Remark 3.7. With some additional effort one should replace (3.1.4) in [START_REF] Cattiaux | Lyapunov conditions for super Poincaré inequalities[END_REF] directly by a similar statement with σ.∇f instead of ∇f , even in the strongly hypo-elliptic case, replacing the arguments in [START_REF] Cattiaux | Lyapunov conditions for super Poincaré inequalities[END_REF] by the Jerison and Sanchez-Calle estimates for such operators, up to a modification of the power s -d/2 replaced by s -m where m depends on the dimension of the graded Lie algebra. We do not want to go further into details here, that is why we choosed to only consider the uniformly elliptic situation. ♦ 4. F-Sobolev inequalities.

We will extend the results of the previous section to general F -Sobolev inequalities introduced by Aida ( [START_REF] Aida | Uniform positivity improving property, Sobolev inequalities and spectral gaps[END_REF]) and studied in [START_REF] Wang | Functional inequalities, Markov processes and Spectral theory[END_REF][START_REF] Barthe | Interpolated inequalities between exponential and Gaussian, Orlicz hypercontractivity and isoperimetry[END_REF][START_REF] Barthe | Isoperimetry between exponential and Gaussian[END_REF]. Actually we will not be as complete as for the log-Sobolev inequality, because for general functions F instead of the logarithm, results are much more intricate. In particular the reader will find in [START_REF] Roberto | Orlicz-Sobolev inequalities for sub-Gaussian measures and ergodicity of Markov semi-groups[END_REF] convergence results in Orlicz spaces (replacing (HLS5) we shall not give here.

We are mainly interested here with the following version of (defective) F -Sobolev inequalities for a nice F defined on R + :

(HF S4def ect) f 2 F f 2 f 2 dµ ≤ C F (µ) E(f ) + D F µ(f 2 ) .
When D F = 0 one say that the inequality is tight and simply denote it by (HF S4). The relationship between F -Sobolev and super-Poincaré inequalities is due to Wang ([58] Theorem 3.3.1 and Theorem 3.3.3). Recall some basic facts on these inequalities Proposition 4.1. We have:

• (see [58].) A super-Poincaré inequality µ(f 2 ) ≤ s E(f ) + β(s) (µ(|f |)) 2
implies (HF S4def ect) for

F (u) = 1 u u 0 ξ(t/2) dt , ξ(t) = sup a>0 1 a - β(a)
ta .

• (see [START_REF] Wang | Functional inequalities, Markov processes and Spectral theory[END_REF].) If (HF S4def ect) holds true for F such that +∞ .

1 uF (u) du < +∞, then the semi-group P t is ultra-bounded, i.e. for all t > 0 there exists C(t) such that,

P t f ∞ ≤ C(t) f L 1 (µ)
so that if in addition a Poincaré inequality holds,

P t f -µ(f ) ∞ ≤ M e -Ct f -µ(f ) L 2 (µ)
for some C > 0 (one can replace L 2 by any L p for p > 1 just changing C using interpolation results, see e.g. [START_REF] Cattiaux | Trends to equilibrium in total variation distance[END_REF][START_REF] Cattiaux | Poincaré inequality and the l p convergence of semi-groups[END_REF]).

• (see [START_REF] Barthe | Interpolated inequalities between exponential and Gaussian, Orlicz hypercontractivity and isoperimetry[END_REF] We thus have two situations: either F ≤ log (interpolating between Poincaré and log-Sobolev), in which case (with additional structural conditions on F ) F -Sobolev inequalities are equivalent to an exponential convergence in some Orlicz space ( [START_REF] Roberto | Orlicz-Sobolev inequalities for sub-Gaussian measures and ergodicity of Markov semi-groups[END_REF]), we still have some Rothaus(-Orlicz) lemma allowing us to tight a defective F -Sobolev inequality and a lot of additional properties connected with Orlicz hyperboundedness, concentration and isoperimetry (see [START_REF] Barthe | Interpolated inequalities between exponential and Gaussian, Orlicz hypercontractivity and isoperimetry[END_REF][START_REF] Barthe | Isoperimetry between exponential and Gaussian[END_REF]), or +∞ .

lemma 8.) If F (1) = 0, F is C 2 in a neighborhood of
1 uF (u) du < +∞ in which case exponential convergence holds in L ∞ , with a very small gap between both classes of F .

We will now prove the analogue of Proposition 3.1. To this end we need to introduce some convexity notions. For instance if F (u) behaves like ln β + (u) at infinity for some β > 0, then G * (t) behaves like β t (β-1)/β e t 1 β at infinity (see [START_REF] Barthe | Interpolated inequalities between exponential and Gaussian, Orlicz hypercontractivity and isoperimetry[END_REF] subsection 7.1 to see the correct F to be chosen). Proposition 4.3. Assume that µ satisfies the F-Sobolev inequality (HF S4def ect) and that

G(s) = sF (s) is convex. Let h be a non-negative continuous function such that b = 2(D F + µ(G * (h))) < +∞. For ε > 0, define U ε (h) = {(1 -ε)h > b}.
Then there exists a Lyapunov function

W ∈ D(L) such that W (x) ≥ w ε > 0 on U ε (h) and LW ≤ - ε 2 C F h W on U ε (h).
Proof. The proof mimic the one of proposition 3.1 with the following modifications: take

φ = ρ(-h + b) with b = 2(D F + µ(G * (h))) and ρ C F = 1 2 , use Young's inequality st ≤ G(s) + G * (t).
We thus obtain, for a particular choice of F : Theorem 4.4. Assume that D is not bounded, that V goes to infinity at infinity and that e aV ∈ L 1 (µ) for some a > 0. Consider the following properties We know in particular (see [START_REF] Barthe | Interpolated inequalities between exponential and Gaussian, Orlicz hypercontractivity and isoperimetry[END_REF]) that for V (x) = |x| α , α ≥ 1, µ satisfies (HF Sβ) with

β = 2 1 - 1 α .
The main reason for writing Theorem 4.4 only in the case F ∼ ln β + is the converse part (HF S1) ⇒ (HF Sβ) for which the argument is easy since we have an explicit expression of G * . Of course Proposition 4.3 contains much more general situations. Here is one which will be useful in the sequel Theorem 4.5. Assume that D is not bounded, that µ satisfies both a Poincaré inequality and the F-Sobolev inequality (HF S4def ect), that G(s) = sF (s) is convex, non decreasing at infinity and that (G * ) -1 (the inverse function of G * ) growths to infinity at infinity. Then for all x 0 ∈ D there exist a and θ two positive constants, such that, defining h(x) = (G * ) -1 (e ad(x,x 0 ) ) , we have for all x and all non empty, open and bounded subset U ,

W θ,U,h (x) = E x exp T U 0 θ h(X s ) ds < +∞ ,
where T U denotes the hitting time of U . Actually W θ,U,h ∈ L 1 (µ).

Proof. Since µ satisfies a Poincaré inequality, it is known that there exists a > 0 such that µ(G * (h)) = µ(e ad(x,x 0 ) ) < +∞ .

In addition h goes to infinity at infinity so that its level sets are compact. It remains to apply Proposition 4.3 to get the Lyapunov function W θ,U,h and consequently the result. As usual since LW θ,U,h + θhW θ,U,h ≤ 0 outside of a compact set, we get that h W θ,U,h is integrable and since h goes to infinity that W θ,U,h is integrable too.

L p geometric ergodicity and functional inequalities.

Come back to the geometric ergodicity property (HP 3). If we replace the initial distribution δ x by some initial probability distribution ν, we have

P t (ν, .) -µ T V ≤ C e -β t , provided (LW ν) W ∈ L 1 (ν) . (5.1)
If ν is absolutely continuous w.r.t. µ and dν dµ ∈ L p (µ) a sufficient condition is thus (LW q) W ∈ L q (µ)

for 1 p + 1 q = 1.
It is thus interesting to study the property (LW q). As shown in [START_REF] Cattiaux | Poincaré inequalities and hitting times[END_REF], once (HP 1) is satisfied, (LW 1) is satisfied too. It follows that for some θ > 0, W θ (x) = E x (e θT U ) is finite, hence satisfies LW θ = -θW θ on U c , so that enlarging a little bit U (say U ε ) we can modify the previous W θ in U ε in order to get a new Lyapunov function, still denoted W θ for simplicity satisfying

LW θ ≤ -θW θ + b1 Ū .
Hence W θ ∈ L 1 (µ). It follows that for every p ≥ 1, defining W θ,p (x) = E x (e θ p T U ), we have first that W θ,p ∈ L p (µ), second that (after similar modifications) W θ,p is a Lyapunov function with θ replaced by θ/p. Since Ū is compact, these modifications do not modify the integrability properties of W θ,p . Hence we have obtained Proposition 5.2. If (HP 1) is satisfied, for all p > 1, one can find another Lyapunov function (associated to a different λ and a different U ) W p ∈ L p (µ). Hence there exists some β p such that as soon as dν dµ ∈ L q (µ) with 1 p + 1 q = 1,

P t (ν, .) -µ T V ≤ C(ν) e -βp t .
In the symmetric case the situation is better understood. Indeed, (HP 1) implies the geometric ergodicity in L 2 (µ) (HP 5), so that using Riesz-Thorin interpolation theorem in an appropriate way (see [START_REF] Cattiaux | Poincaré inequality and the l p convergence of semi-groups[END_REF]) we have that provided dν dµ ∈ L q (µ) for some 1 < q ≤ 2,

P t dν dµ -1 L q (µ)
≤ K q e -(q-1)

q λ P (µ) t dν dµ -1 L q (µ)
.

In this situation we thus have geometric convergence for a stronger topology.

But the discussion preceding Proposition 5.2 furnishes a stronger result. Indeed (HP 1) yields (HP 3)

H(x) = P t (x, .) -µ T V ≤ C W (x) e -β t , (5.3)
so that H(x) converges to 0 for all x at a geometric rate. But we may replace W by W p and β by β p and get that actually H converges to 0 in all L p (µ) for 1 ≤ p < +∞, with a geometric rate depending on p.

Assume from now on that µ satisfies some F -Sobolev inequality, for some smooth F . Does it improve the previous results ? In this situation, the rate of convergence to equilibrium in total variation distance was studied in [START_REF] Cattiaux | Trends to equilibrium in total variation distance[END_REF]. The results we proved in the previous sections allow us to give a new and substantially simpler proof of some results contained in [START_REF] Cattiaux | Trends to equilibrium in total variation distance[END_REF]. Here is a result in this direction:

Theorem 5.4. Under the assumptions of Theorem 4.5, there exists λ > 0 such that for all non-empty, open and bounded set U ,

W (.) = E . e λ T U ∈ 1≤q<+∞ L q (µ) .
It thus follows that there exists some β > 0 such that for all ν absolutely continuous w.r.t. µ such that dν dµ belongs to L p (µ) for some p > 1,

P t (ν, .) -µ T V ≤ C(ν) e -β t .
Actually H defined in (5.3) converges to 0 in all the L p 's with a rate e -β t .

Proof. Let h as in Theorem 4.5. The level sets H R = {h ≤ R} of h are smooth (since F is smooth) compact sets. Denote by T R the hitting time of H R . For R large enough, H R contains U . Let λ > 0 be such that W (x) = E x (e λT U ) < +∞ for all x. Such a λ exists since µ satisfies a Poincaré inequality. If y ∈ HR , W (y) ≤ K(R) < +∞ using the regularity of W . If x / ∈ H R , we have

E x e λT U = E x e λ T R E X T R e λ T U ≤ K(R) E x e λ T R . But now for θR > q λ, W q (x) ≤ K q (R) E q x e λ T R ≤ K q (R) E x e q λ T R ≤ K q (R) E x e T R 0 θ h(Xs) ds = K q (R) W θ,U,h (x) .
The first part of the Theorem follows from Theorem 4.5. The second part is immediate.

Remark 5.5. If dν dµ ∈ L 1 (µ), La Vallée-Poussin theorem implies that there is some Young function φ(u) = uψ(u) with ψ growing to infinity, such that dν dµ belongs to the Orlicz space L φ . Hence the second part of the Theorem will follow from the first one and the Hölder-Orlicz inequality, once W ∈ L φ * (µ). But for the previous proof to work we need something like φ * (e λu ) ≤ C e φ * * (λ) u which is not true for φ * growing faster than a power function. That is why the result is only stated for ν with a density belonging to some L p space. ♦

This result is nor new nor surprising. For instance, when a logarithmic Sobolev inequality holds true, Theorem 2.13 in [START_REF] Cattiaux | Trends to equilibrium in total variation distance[END_REF] shows that there is exponential convergence to the equilibrium in total variation distance as soon as ν belongs to the space L ln L. It is then a simple consequence of Pinsker's inequality and the entropic convergence to equimibrium. More generally, the courageous reader will find in the jungle of section 3 of [START_REF] Cattiaux | Trends to equilibrium in total variation distance[END_REF] similar results for general F -Sobolev inequalities. It should be interesting to recover these results by using Lyapunov functions.

Actually we should describe the problem as follows: we know that reinforcing functional inequalities from Poincaré to F -Sobolev, reinforces the Lyapunov condition and conversely in the symmetric case. Does a reinforced functional inequality reinforce the integrability of the Lyapunov function and conversely in the symmetric case ? In particular can we characterize (at least in the symmetric case) a functional inequality through integrability properties of (some) Lyapunov function ?

Example 5.6. Look at the simple symmetric case L = ∆ -∇V.∇ in the whole R d . Then it is easily seen that the following holds: there is an equivalence between

• x.∇V (x) ≥ α |x| 2 for large |x|,
• W e (x) = e α |x| 2 /2 is a Lyapunov function, i.e. satisfies (HP 1),

• W 2 (x) = |x| 2 also satisfies (HP 1).

The first item is of course equivalent to the fact that V is uniformly convex. We see that the behavior of various Lyapunov functions can be very different. They also imply various integrability properties and functional inequalities. Notice however that thanks to what we said previously we can directly make the following reasoning: if V is uniformly convex, W 2 is a Lyapunov function and admits some exponential moment so that convergence to the equilibrium in total variation distance holds as soon as ν belongs to the space L ln L as expected. Indeed, we have by (HP 1) that for some δ and some r (denoting B r the euclidean ball of radius r, and x ∈ B c r E x (e δT Br ) ≤ W 2 (x).

Note however that in fact W e satisfies a stronger Lyapunov condition, i.e.

LW e (x) ≤ -λ|x| 2 W e (x) + b1 Br so that by the previous result on logarithmic , we have a stroonger integrability property linked to hitting times:

E x e δ T Br 0 X 2 s ≤ W e (x).
However, it does not seem possible to pass from this last control to the previous one. Hence, finally, these results do not give any precise idea of the dependence in x of E x (e λT U ) for a given bounded U . Actually this is a very difficult problem for which results are only known in the gaussian case (i.e. for the Ornstein-Uhlenbeck process). ♦

In the next section we shall look more into details at the case where one can find a bounded Lyapunov function.

6. Coming down from infinity, uniform geometric ergodicity and Lyapunov functions.

If dν/dµ only belongs to L 1 , it is interesting to look at a bounded Lyapunov function. What precedes allows us to state Proposition 6.1. The following statements are equivalent:

• there exists λ > 0 such that sup x∈ D E x e λT U < +∞ for one (or all) non empty, open and bounded set U , • there exists a bounded Lyapunov function satisfying (HP 1),

• the process is uniformly geometrically ergodic, i.e. there exist β > 0 and C > 0 such that sup

x∈ D P t (x, .) -µ T V ≤ C e -β t .
In this case of course, for any initial probability measure ν,

P t (ν, .) -µ T V ≤ C e -β t .
There exists a stronger form of uniform exponential integrability, the notion of "coming down from infinity" which is used by people who are studying quasi-stationary distributions or more precisely Yaglom limits (see e.g. the recent book [START_REF] Collet | Probability and its applications[END_REF]). We shall use the following definition Definition 6.2. We say that the process comes down from infinity if for all a > 0 there exists some open, bounded subset U a such that sup x E x e a T Ua < +∞.

In one dimension, this property was related to the uniqueness of quasi-stationary distributions (QSD) and to the fact that ∞ is an entrance boundary, in [START_REF] Cattiaux | Quasi-stationarity distributions and diffusion models in population dynamics[END_REF]. Uniqueness of a (QSD) also follows from the ultraboundedness property of the semi-group, even in higher dimension (see e.g. [START_REF] Cattiaux | Competitive or weak cooperative stochastic LotkaVolterra systems conditioned to non extinction[END_REF]). In [START_REF] Cattiaux | Poincaré inequalities and hitting times[END_REF] Proposition 5.3, we claimed that ultraboundedness is actually equivalent to coming down from infinity for one dimensional diffusion processes with generator ∆ -∇V.∇ satisfying some extra condition. D. Loukianova pointed out to us that the proof of this proposition in fact needs slightly more stringent assumptions (the function z → F (z)/z therein is not necessarily non-increasing) for this equivalence to hold true.

Nevertheless, part of this result is true and we shall give a direct and simple proof.

Indeed, assume that W satisfies (HP 1). We have seen that we can always assume that W ∈ L 2 (µ) and then W ∈ D(L)). It follows that

L(P t W ) = P t (LW ) ≤ -λ P t W + P t (1 Ū ) . (6.3)
Now assume that R ≤ d(x, Ū ) ≤ 2R. We have

P t (1 Ū )(x) = E x 1 Xt∈ Ū ≤ E x 1 T Ū <t ≤ sup d(y, Ū )≥R Q y (T Ū < t)
where Q y denotes the law of the process Y . with the same generator L but reflected on d(z, Ū ) = 2R (which can be assumed to be smooth) and starting from y. Indeed if the process X . hits Ū before to leave {d(z, Ū ) ≤ 2R}, it coincides with Y . (with the same starting point) up to T Ū . If not, X . leaves {d(z, Ū ) ≤ 2R} before T Ū , but in order to hit Ū it has to come back to {d(z, Ū ) ≤ 2R} first, so that using the Markov property we may apply the same argument as before this time starting from X T R where T R is the hitting time of {d(z, Ū ) ≤ 2R}. That is why the final upper bound contains the supremum over y. Now, since all coefficients are smooth, they are bounded with bounded derivatives of any order in {d(z, Ū ) ≤ 2R} which is compact. It is then well known that sup

d(y, Ū )≥R Q y (T Ū < t) ≤ C e -cR/t
for some constants C and c only depending on these bounds. Hence

P t (1 Ū )(x) ≤ C e -cR/t , as soon as R ≤ d(x, Ū ) ≤ 2R. If d(x, Ū ) > 2R, T U > T R
, and we may apply again the Markov property to get the same upper bound. Pick some R > 0 once for all and choose t > 0 in such a way that Ce -cR/t < 1 2 λ w .

We thus have

L(P t W )(x) ≤ -λ P t W (x) + 1 d(x, Ū )≤R + Ce -cR/t 1 d(x, Ū )≥R ≤ - λ 2 P t W (x) + 1 d(x, Ū )≤R ,
so that P t W is a new Lyapunov function with λ/2 and {d(x, Ū ) ≤ R} in place of λ and Ū (of course P t W belongs to D(L) and satisfies P t W ≥ w > 0). We deduce immediately Theorem 6.4. Assume that (HP 1) is satisfied (for example µ satisfies a Poincaré inequality) and that the semi-group P . is ultra-bounded, i.e. that P t maps continuously L 1 into L ∞ for any t > 0. Then the process comes down from infinity.

Proof. (HP 1) together with ultra-boundedness imply that the semi-group is hyper-contractive so that µ satisfies a logarithmic Sobolev inequality according to Gross theorem. Hence, we may apply Corollary 3.3 and find a Lyapunov function W such that

LW ≤ -λ d 2 (., x 0 ) W + b 1 Ū
for some bounded open subset U . Hence for all large enough a > 0,

LW ≤ -2a W + b a 1 Ua with U a = {x ; λ d 2 (x, x 0 ) ≤ 2a} and b a = sup x∈Ua LW , a being large enough for Ū ⊂ U a .
According to the previous discussion there exists a new Lyapunov function W a = P t W for some adequat t which is bounded and satisfies LW a (x) ≤ -aW a (x) for x ∈ V a = {d(x, U a ) > R}, so that sup

x E x e aTa < +∞ for T a the hitting time of V c a .

Remark 6.5. The fact that P t W is still a Lyapunov function is interesting by itself, but except in the ultra-bounded situation, it does not furnish new results. For instance if we want to get a Lyapunov function that belongs to all the L p spaces, we have to assume that P . is immediately hyper bounded, which is stronger than log-Sobolev, while Theorem 5.4 gives the result under a simple F -Sobolev condition. Working a little bit more, one can extend the previous result to discrete valued Markov process, which are ultracontractive (birth-death processes,...). ♦

The previous proof indicates a way to prove "coming down from infinity" using Lyapunov functions, more precisely nested Lyapunov conditions Definition 6.6.

(SLC) We shall say that a Super-Lyapunov condition is satisfied if there exist a sequence W k ≥ 1, a sequence of increasing bounded sets B k growing to R n , an increasing sequence λ k > 0 growing to infinity and a sequence b k > 0 such that

LW k ≤ -λ k W k + b k 1 B k .
For instance in the situation of Theorem 4. Assume that (SLC) is satisfied. Denote by T k the hitting time of B k and choose some δ > 0.

As we did in the proof of Theorem 5.4, for k ≥ k 0 and λ k 0 > δ we have for x / ∈ B k ,

E x e δT k 0 = E x e δ T k E X T k e δ T k 0 ≤ E x e δ T k sup y∈∂B k E y e δT k 0 ≤ E x e λ k T k δ/λ k sup y∈∂B k E y e δT k 0 ≤ (W k (x)) δ/λ k sup y∈∂B k E y e δT k 0 . Define w k = sup y∈B k+1 -B k W k (y) .
Proceeding by induction we have for all

x / ∈ B k 0 +1 E x e λT k 0 ≤ C k 0 +∞ k=k 0 (w k ) δ λ k . (6.7)
As we see, if the sequence λ k goes to infinity, δ has no role in the convergence of the previous infinite product, as well as the value of k 0 . We thus have Theorem 6.8. If (SLC) is satisfied, and for some k 0 ,

+∞ k=k 0 ln w k λ k < +∞ ,
the process comes down from infinity. Hence (SLC) is satisfied with another sequence (λ k , W k , B k ) where all the W k are bounded.

Example 6.9. In one dimension consider (for β > 0) the potential

V β (x) = (1 + x 2 ) ln β (1 + x 2 ) .
For W (x) = e x 2 /2 it holds for |x| large enough,

L β W (x) ≤ -(1 -ε) x 2 ln β (1 + x 2 ) W (x) . Hence if B k = B(0, R k ) we have ln(w k ) ≤ 1 2 R 2 k , while for |x| > R k , we may choose λ k = c R 2 k ln β (R k ).
It follows that the process comes down from infinity for any β > 0 by choosing for instance R k = exp k 2/β in Theorem 6.8. It is known however that the semi-group is ultra-bounded if and only if β > 1 (see e.g [START_REF] Kavian | Quelques remarques sur l'ultracontractivité[END_REF]). Hence we have some examples of processes coming down from infinity for which the semi-group is not ultra-bounded (but is immediately hyper-contractive as shown in [START_REF] Kavian | Quelques remarques sur l'ultracontractivité[END_REF]).

Integrability and Lyapunov conditions.

In this section we will study the interplay between Lyapunov conditions and integrability conditions. So it is not a restriction to look at L = ∆ -∇V.∇ such that µ is symmetric (or reversible). Let us recall that integrability conditions are related to transportation inequalities. Indeed, if µ satisfies a Gaussian integrability condition, i.e. ∃δ > 0, x 0 e δd(x,x 0 ) 2 dµ < ∞ then (T 1) ∀ν ∈ P 1 , W 1 (ν, µ) ≤ 2CH(ν|µ) for some explicit C (see [START_REF] Djellout | Transportation cost-information inequalities for random dynamical systems and diffusions[END_REF]), where W 1 and H denote respectively the 1-Wasserstein distance and the relative entropy (or Kullback-Leibler information). The converse, (T 1) implies gaussian integrability is also true and due to K. Marton [START_REF] Marton | Bounding d-distance by informational divergence: a method to prove measure concentration[END_REF]. Gozlan [START_REF] Nathael Gozlan | Integral criteria for transportation-cost inequalities[END_REF] has generalized the approach to various type of (T 1) type transportation inequalities, getting that integrability property ∃δ > 0, x 0 e α(δd(x,x 0 )) dµ < ∞ for α convex (quadratic near 0) is equivalent to α(W 1 (ν, µ) ≤ C H(ν|µ) for very ν. The links between functional inequalities and integrability properties are usually consequences of concentration properties of lipschitzian function (as Herbst argument for logarithmic Sobolev inequality). A more direct approach is taken in [START_REF] Cattiaux | On quadratic transportation cost inequalities[END_REF], where in particular an equivalence between a Poincaré inequality and a weak form of a (T 2) inequality (involving W 2 ) is shown. Note however that we won't require here some local inequality, so that we cannot hope to get better functional inequalities than (T 1) like.

We shall now investigate the relationship between the existence of Lyapunov functions and integrability properties. In the sequel we will thus assume the following If we define U = ln(W ) it is immediately seen that

LU + |∇U | 2 ≤ -φ 2 + b min C W 1 C . (7.2)
Using this inequality it is shown in [START_REF] Cattiaux | A remark on Talagrand's transportation inequality and logarithmic Sobolev inequality[END_REF] lemma 3.4 that for any smooth h,

h 2 φ 2 dµ ≤ E(h) + b min C W C h 2 dµ . (7.3)
Of course, if C h dµ = 0, and provided C is smooth enough (which is not a restriction), we may apply the Holley-Stroock perturbation argument and get

h 2 φ 2 dµ ≤ 1 + b min C W e Osc C V C P (C, dx) E(h)
where Osc U (V ) denotes the oscillation of V on the subset U and C P (U, dx) the Poincaré constant of the uniform measure on U . If φ goes to infinity at infinity, the previous inequality is thus stronger than the Poincaré inequality (as expected). It is well known that the Poincaré inequality implies the exponential integrability of c d(., x 0 ) for some small enough positive c, as the logarithmic Sobolev inequality implies the exponential integrability of c d 2 (., x 0 ) for some small enough positive c (we previously recalled this result).

In [START_REF] Liu | Gaussian integrability of distance function under the Lyapunov condition[END_REF], Yuan Liu proved that (φ -Lyap) with φ(x) = a d(x, x 0 ) implies the exponential integrability of c d 2 (., x 0 ) for c < a. This result is not surprising since in this case (φ -Lyap) is exactly (HLS1) which is equivalent to the logarithmic-Sobolev inequality, at least if the curvature is bounded from below according to Theorem 1.2, hence implies as a consequence the quoted exponential integrability. We shall here follow and generalize Liu's argument in order to answer the following question: what are sufficient conditions on ψ for c ψ 2 to be exponentially integrable when (φ -Lyap) is satisfied ? A particularly interesting example is the case when φ(x) = a d p (x, x 0 ). Indeed, for p = 0 we know that a Poincaré inequality is satisfied and for p = 1 a log-Sobolev inequality is satisfied under a curvature assumption. The use of curvature is very specific and strongly connected to p = 1. Hence for 0 < p < 1 we do not know whether (φ -Lyap) implies some natural functional inequality or not, even for bounded from below curvature. We shall see however that c d p+1 (., x 0 ) is exponentially integrable for some small enough positive c and all 0 ≤ p, so that a generalized transportation inequality holds.

For ψ ≥ 0, introduce β n := ψ 2n dµ .

We will use ( Let us assume then that there exists α, β, γ > 0 and 0 < δ < 1, (at least outside a compact K, and if so choose ψ to be 0 on K) such that

ψ 2 |∇ψ| 2 φ 2 ≤ α, ψ∇φ.∇ψ φ 3 ≤ β, |∇φ| 2 φ 4 ≤ δ, sup C ψ 2 φ 2 ≤ γ . (7.4)
Under these assumptions, we get that

β n ≤ α 1 -δ n 2 β n-2 + 2nβ + γ b 1 -δ β n-1 .
Combined with a direct consequence of Cauchy-Schwarz inequality, we obtain

β n ≤ β n+1 β n-1 ≤ α 1 -δ (n + 1) 2 β n-1 + 2(n + 1)β + γ b 1 -δ β n 1 2 β 1 2
n-1 .

We then easily deduce that Now come back to (7.4). I f we assume that φ is bounded from below by some positive constant in C, the condition on γ is satisfied as soon as φ and ψ are, say, continuous. The condition on δ says that 1/φ is a contraction outside some compact set. Assuming this condition we see that both conditions on α and β are the same, i.e. |∇(ψ 2 )|/φ is bounded. Thus Theorem 7.5. Assume that (φ-Lyap) is satisfied for some function φ such that φ is bounded from below by a positive constant on C and 1/φ is η-Lipschitz for some η < 1. Then for all function ψ 2 such that |∇(ψ 2 )|/φ is bounded, there exists a ′ > 0 such that e a ′ ψ 2 dµ < +∞.

β n ≤ 1
Example 7.6.

(1) For a constant φ we recover the fact that any Lipschitz function has an exponential moment, hence the usual concentration result once a Poincaré inequality is satisfied. For φ(x) = ad 2 (x, x 0 ), we recover the gaussian nature of the tails once a log-Sobolev inequality is satisfied.

(2) If we take φ(x) = ad p (x, x 0 ) for p ≥ 0 we obtain exponential integrability of functions g such that |∇g| ≤ C |x| p , hence for instance for g(x) = d p+1 (x, x 0 ). As for the Poincaré or the log-Sobolev case, this exponential integrability is sharp, since for µ(dx) = Z p e -|x| p+1 , (φ -Lyap) is satisfied with φ(x) = c|x| p and W (x) = e a|x| p for a small enough a. (3) One may of course also consider φ 2 (x) = ad -1 (x, x 0 ), if a > 1, which can be obtained for Cauchy type measures (see [START_REF] Cattiaux | Functional inequalities for heavy tailed distributions and applications to isoperimetry[END_REF] for details). In this case we may take ψ 2 behaving as log(|x|) at infinity recovering polynomial integrability (also quite sharply). Note also that in [START_REF] Cattiaux | Functional inequalities for heavy tailed distributions and applications to isoperimetry[END_REF]Th. 5.1], it is shown how a converse Poincaré inequality (obtained by a (φ -Lyap) condition and a local Poincaré inequality) plus an involved integrability condition implies a weak Poincaré inequality. This integrability condition can be checked using Th. 7.5 for example for Cauchy type measure (via tedious computations), so that only a Lyapunov condition and local inequality are also sufficient for weak Poincaré inequality.

Of course there is no converse statement for Theorem 7.5, since for instance exponential integrability for the distance cannot imply a Poincaré inequality (disconnected domains for example).

Finally recall that that (φ -Lyap) is equivalent to the following

E x e T C 0 φ 2 (Xs) ds < +∞ ,
where in our situation

X t = X 0 + √ 2 W t - t 0 ∇V (X s ) ds .
It would be particularly interesting to show that weak Poincaré inequality implies back Lyapunov condition as done in section 2 for Poincaré inequality.

Theorem 1 . 1 .

 11 Consider the following properties (HP1) There exists a Lyapunov function W , i.e. a smooth function W : D → R, s.t. W ≥ w > 0, and there exist a constant λ > 0 and an open connected bounded subset U such that ∂W ∂n = 0 on ∂D and LW ≤ -λ W + 1 Ū .

Theorem 1 . 2 .

 12 Assume that D is not bounded. Consider the following properties (HLS1) There exists a Lyapunov function W , i.e. there exists a smooth function W : D → R, with W ≥ w > 0, and there exist constants λ > 0 and b > 0 such that ∂W ∂n = 0 on ∂D and LW (x) ≤ -λ |x| 2 W (x) + b . (HLS1') There exists a Lyapunov function W , i.e. there exists a smooth function W : D → R, with W ≥ w > 0, and there exist constants λ > 0 and b > 0 such that ∂W ∂n = 0 on ∂D and LW (x) ≤ -λ V (x) W (x) + b . (HLS2) There exist an open connected bounded subset U and a constant θ > 0 such that for all x,

Theorem 2 . 1 .

 21 Assume that µ satisfies a Poincaré inequality with constant C P (µ). Then for all open subset A, there exists a smooth Lyapunov function W ∈ D(L) i.e. a smooth function satisfying W ≥ w > 0 on A c and LW ≤ -c W on A c with

  1 and 2F ′ (1)+F ′′ (1) = c > 0, (HF S4) implies the Poincaré inequality (HP 4) with C P (µ) = 1/(2c). • (see [9] Remark 22.) If F ≥ 0 and F (u) ≥ c > 0 for u ≥ 2, then (HF S4) implies the Poincaré inequality (HP 4). • (see [9] lemma 9.) If F is concave, non-decreasing, growths to infinity and satisfies F (1) = 0 and uF ′ (u) ≤ M , then (HF Sdef ect) and the Poincaré inequality imply (HF S4).

Definition 4 . 2 .

 42 Assume that u → uF (u) = G(u) is convex. We define G * as the Fenchel-Legendre dual function of G i.e. G * (u) = sup t>0 (ut -G(t)).

( 0 θ 1 β

 01 HFS1) There exists a Lyapunov function W , i.e. there exists a smooth function W : D → R with W ≥ w > 0, and there exist constants λ > 0 and b > 0 such that ∂W ∂n = 0 on ∂D and LW (x) ≤ -λ |V | β (x) W (x) + b .(HFS2) There exist an open connected bounded subset U and a constant θ > 0 such that for all x,E x exp T U |V | β (X s ) ds < +∞ ,where T U denotes the hitting time of U . (HF Sβ) µ satisfies (HF S4def ect) with F (s) = ln β + (s). Then (HF Sβ) ⇒ (HF S1) and (HF S1) ⇔ (HF S2).If in addition µ is symmetric, σ.σ * is uniformly elliptic and |∇V (x)| ≥ v > 0 for |x| large enough, then (HF Sβ) ⇔ (HF S1) ⇔ (HF S2) .For β ≤ 1 we may replace (HF Sβ) by its tight version.Proof. For the first part we use the previous proposition with h = a|V | β for some a small enough. In the symmetric situation, we mimic the proof of proposition 3.5 yielding a super-Poincaré inequality with β(s) = e c/s hence the corresponding defective F -Sobolev inequality using Proposition 4.1. But (HF S1) implies (HP 1) hence a Poincaré inequality and we can use the final statement of Proposition 4.1 to get a tight version when β ≤ 1.

Definition 7 . 1 .

 71 Let φ be a (strictly) positive function. We say that (φ -Lyap) is satisfied if there exist W > 0, b ≥ 0 and a bounded open subset C such that LW ≤ -φ 2 W + b 1 C .

7 . 3 )+ |∇φ| 2 φ 4 ψ

 734 to initiate a recurrence on β n using the notation b = b min C W , 2n dµ.

2 

 2 and n large enough. It then follows that for some c β n ≤ ca n n! and thus we have that for a ′ < a -1 e a ′ ψ 2 dµ ≤ c 1 -a ′ a .

  5, (SLC) is satisfied with the same Lyapunov function W , i.e. W = W k , similarly as what we have done (in the case of log-Sobolev) in the previous proof. Of course if all the W k are bounded, (SLC) is equivalent to "coming down from infinity".


Anna Maria

Anna Maria Vegni
email: annamaria.vegni@uniroma3.it

Enrico Natalizio
email: enrico.natalizio@hds.utc.fr

Forwarder Smart Selection Protocol for Limitation of Broadcast Storm Problem

Keywords: Vehicular ad hoc networks, opportunistic routing, clusters, broadcast storm problem

Forwarder smart selection protocol for limitation of broadcast storm problem

Introduction

Vehicular Ad hoc NETworks (VANETs) are emerging as the preferred network design for Intelligent Transportation Systems (ITS), providing inter-vehicular shortrange communications, for the support of Internet access and safety applications.

VANETs are a particular class of Mobile Ad-hoc NETworks (MANETs), showing typical characteristics. Indeed, VANETs consist of mostly highly mobile nodes moving along the same or opposite directions (i.e., vehicles), forming clusters according to a Poisson distribution, [START_REF] Hartenstein | VANET: Vehicular Applications and Internetworking Technologies[END_REF]. Communications are supported due to "smart" vehicles, equipped with On-Board Unit with multi-Network Interface Cards (NIC), such as IEEE 802.11p, WiMax, Long Term Evolution, and also GNSS receiver. However, communications among vehicles belonging to different clusters are not always guaranteed, due to connectivity disruptions caused by quick topology network changes, vehicle speed and sparse or totally disconnected scenarios. Moreover, also the market penetration rate can hinder inter-vehicular communications: unequipped vehicles physically occupy space and alter the spatial distribution of equipped vehicles and their mobility. On the other side, connectivity improves as the market penetration increases, since it directly translates in an increasing probability of finding a neighboring vehicle that forwards messages.

Inter-vehicle communications are expected to significantly improve transportation safety and mobility on the road. Several applications of inter-vehicle communications have been identified, from safety and warning applications, up to traffic control and driver assistance applications [START_REF] Hartenstein | VANET: Vehicular Applications and Internetworking Technologies[END_REF]. Many of these applications require multicast routing protocol to a group of vehicles satisfying a geographical criterion.

In this vision, most applications targeting VANETs rely heavily on broadcast transmissions, such as to discover neighboring vehicles, as well as to disseminate traffic-related information to all reachable vehicles within a certain geographical area i.e., mostly in general for context-aware applications. On the other side, broadcasting packets may lead to frequent contention and collisions, due to redundant transmissions among vehicles in dense network topologies (e.g., in rush traffic scenarios). This problem is referred to as the broadcast storm problem [START_REF] Tonguz | Broadcasting in VANET[END_REF][START_REF] Wisitpongphan | Broadcast storm mitigation techniques in vehicular ad hoc networks[END_REF].

It affects inter-vehicle communications, since redundant rebroadcasts, contention and collisions can be largely increased; when a vehicle rebroadcasts a message, it is highly likely that the neighboring vehicles have already received it, and this results in a large number of redundant messages and replica.

In traditional MANET environment, multiple solutions have been proposed in order to alleviate the broadcast storm effect, but only a few solutions have been addressed to the VANET context [START_REF] Bür | Evaluation of Selective Broadcast Algorithms for Safety Applications in Vehicular Ad Hoc Networks[END_REF][START_REF] Tonguz | On the Broadcast Storm Problem in Ad hoc Wireless Networks[END_REF]. Most of recent research works have focused on analyzing VANETs as well-connected networks, providing high vehicular traf-fic density. As vehicles in close proximity detect the same dangerous situation (e.g., they are approaching a zone-of-relevance), they will inevitably broadcast messages relating to the same event, leading to a dramatically excessive message redundancy. In such scenarios, broadcast suppression solutions have to be considered [START_REF] Wisitpongphan | Broadcast storm mitigation techniques in vehicular ad hoc networks[END_REF][START_REF] Koubek | Event Suppression for Safety Message Dissemination in VANETs[END_REF]. In contrast, in low vehicular traffic density environment, with a sparse RSU settling and a low market penetration rate, vehicular connectivity results intermittent, poor, and short-lived [START_REF] Wisitpongphan | Broadcast storm mitigation techniques in vehicular ad hoc networks[END_REF]. In this context, the design of reliable and efficient routing protocols for supporting highly diverse and mainly intermittently connected vehicular network topologies is still a challenge.

In this paper, we present a cluster-based broadcast technique for safety applications in VANETs (e.g., car-platoons detection). Our approach is called Selective Reliable Broadcast (SRB), and relies on the opportunistic cluster selection in order to reduce the broadcast storm effect: SRB selects only one vehicle within a cluster-namely, a cluster-head-in order to efficiently rebroadcast emergency and control messages. SRB technique is then able to detect the well-known car platoons, which cause traffic congestions and delays, in a fast way and with low overhead, in order to eventually recommend alternative paths to other vehicles.

Comparison with traditional broadcast approach has shown how SRB limits the number of transmissions but preserves good network performance. This paper is organized as follows. In Section 2 we address pre-existing different solutions for the broadcast storm problem in VANETs. In Section 3, we describe the main phases of SRB technique, and in particular the cluster detection mechanism. In order to enforce the benefit of SRB, we extend the previous work in [START_REF] Vegni | SRB: A Selective Reliable Broadcast Protocol for Safety Applications in VANET[END_REF]: in Section 4 we stress the simulation results by a comparison with traditional broadcast protocol. Simulations have been carried out in different scenar-ios, showing how SRB provides an automatic cluster detection mechanism, while keeping low the number of forwarder vehicles. Finally, conclusions are drawn in Section 5.

Related Work

In this section we give an overview of previous contributions in broadcast protocols for VANETs, particularly focusing on cluster-based approaches. Within the discussion, we clarify the paper objective and then introduce our proposed approach.

Reliable protocols use three methods i.e., (i) rebroadcasting, where the transmitter node retransmits the same message for many times, (ii) selective ACK, where the transmitter requires ACK from a small set of the neighbors, and (iii) changing parameters, where the transmitter changes transmission parameters according to the expected state of the network.

The problem statement for reliable protocols is to design a protocol that can deliver a message from a single source to every node in the own transmission range with the highest possible reliability and minimum delay. A successful message dissemination in VANETs needs an efficient decision mechanism in order to maximize reliability and keep the overhead low. The decision criterion about when and how a safety message should be delivered or repeated is an open issue.

Given the requirements of safety applications (i.e., low delay and effective reliability), and the limitations of vehicular communications (i.e, short-lived connectivity links), selective broadcast or multicast strategies seem more applicable than either unicast routing or flooding. In fact the latter generates a high overhead without increasing the success rate substantially, [START_REF] Chen | A survey and challenges in routing and data dissemination in vehicular ad-hoc networks[END_REF]. Several solutions have been made to introduce intelligence to the basic broadcast concept and make it more selective and, thus, more efficient in its resource usage.

A largely common assumption in connectivity models for VANETs is that a vehicular network is partitioned into a number of clusters [START_REF] Little | An Information Propagation Scheme for Vehicular Networks[END_REF]; vehicles within a partition can communicate either directly or through multiple hops among each other, but no direct connection exists between partitions, as well depicted in Fig- ure 1. A particular class of routing protocols uses this assumption by exploiting clusters formation, namely cluster-based approaches [START_REF] Kakarla | A Survey on Routing Protocols and its Issues in VANET[END_REF].

Based on geographical locations, directions of movement, speed and many other metrics, vehicles can group into different clusters. Clustering enhances effective broadcasting and relaying of messages, while reducing the overhead associated with signaling and the number of unnecessary message replica. This is due since links among vehicles within the same cluster tend to be more stable, although dynamic topology changes can occur. Leveraging on this issue, an efficient clustering should be based on adequate metrics and should take into account the frequent topology changes. The formation of clusters and the selection of the cluster-head (i.e., a vehicle leader within the cluster, responsible for intra and inter-cluster communications) is strongly affected by the high mobility dynamic cluster formation process.

In [START_REF] Ni | The broadcast storm problem in a mobile ad hoc network[END_REF], Ni et al. consider each cluster comprised of three node types: head, gateway and member. The gateway nodes are those who connect to the gateway nodes in other clusters, while the cluster-head is a node whose transmission radius can reach everyone in the same cluster. Finally, members are those who do not belong in either head or gateway group. When a gateway node receives a message from other clusters, it will rebroadcast the message that will be received, and then further retransmitted, by the cluster-head. Although this cluster architecture is correct, the authors did not specify the procedure for the cluster-head election.

In [START_REF] Fasolo | An Effective Broadcast Scheme for Alert Message Propagation in Vehicular Ad hoc Networks[END_REF], Fasolo et al. propose a Smart Broadcast protocol, which exploits vehicles' positions. The proposed technique assumes that the vehicular network is partitioned in adjacent sectors and that vehicles are able to estimate their own position and, therefore, the sector they belong to. The Smart Broadcast technique considers a contention resolution procedure to elect the relay nodes. Although this technique seems very efficient, it has not been validated in terms of network performance and system overhead. Another work which considers both information on vehicles' position and the cluster formation is presented by Luo et al. [START_REF] Luo | A New Cluster Based Routing Protocol for VANET[END_REF].

Their approach is a cluster-based routing protocol and the basic idea is to divide the geographic area into foursquare grids, where a vehicle is elected as the clusterhead to route data packets across nearby grids. Also this technique needs to be validated via simulation results.

In all previous works, mobility aspects have not been considered, while it is noticeable that the cluster selection process is particularly affected by vehicle mobility and cluster stability. Benslimane et al. [START_REF] Benslimane | Dynamic Clustering-Based Adaptive Mobile Gateway Management in Integrated VANET-3G Heterogeneous Wireless Networks[END_REF] consider the cluster formation on the basis of the direction of vehicles movement, the Received Signal Strength (RSS), and the inter-vehicular distance. In this envision, the directional antennabased MAC protocols are exploited to accurately group vehicles on the basis of the direction of their movements and the transmission angles. In [START_REF] Gunter | Cluster-based Medium Access Scheme for Vanets[END_REF], Gunter et al. take into account mobility during cluster collision, and a cluster-head vehicle is that one with the lowest relative mobility and closest proximity to its neighbors. Alternatively, in [START_REF] Kayis | Clustering formation for inter-vehicle communication[END_REF] Kayis and Acarman classify nodes into speed groups, so that nodes belonging to the same speed group will be in the same cluster. Finally, a well-known mobility-based clustering technique is MOBIC [START_REF] Basu | A mobility based metric for clustering in mobile ad hoc networks[END_REF], which considers an aggregate local mobility metric as the basis for cluster formation: the node with the smallest variance of relative mobility to its neighbors is elected as the cluster-head.

In this work, we present SRB, a reliable cluster-based routing protocol that is expected to minimize the number of rebroadcast messages. SRB considers the cluster selection process, and the cluster-head election, by exploiting the intervehicle distance and the time delay. Via simulation results, SRB results in an efficient method to detect clusters and alleviate the broadcast storm problem.

Selective Reliable Broadcast

The aim of SRB is twofold: (i) to avoid rebroadcast messages (i.e., a limitation of broadcast storm problem), and (ii) to detect clusters in automatic and fast way. The proposed approach considers the message rebroadcast process within a VANET by selecting a limited number of vehicles, acting as forwarders. Far from traditional broadcast routing, SRB detects clusters of vehicles in a fast and efficient way, and elects one Cluster-Head (CH) vehicle for each cluster detected.

The CH is then selected as the next message forwarder.

Let us assume a hybrid traffic scenario, consisting of both high and low speed vehicles, as well as high and low vehicle density areas. This scenario well depicts a real vehicular environment, i.e. a clear highway with congested entries. To avoid sudden and emergency braking, information about congested areas should reach high speed approaching vehicles in a timely fashion. We consider an aggregated vehicles group as a Zone-of-Relevance (ZOR) 1 , depicted by the following features i.e., (i) high vehicular density, and (ii) low vehicle speed. We will show how SRB is able to efficiently discover the ZOR (i.e., with low overhead and delay). SRB leverages on two main assumptions, i.e. (i) the vehicular area is partitioned in adjacent sectors, and (ii) all vehicles equipped with GPS are able to estimate their own position. Network partitioning (or fragmentation, [START_REF] Little | An Information Propagation Scheme for Vehicular Networks[END_REF]) is introduced in order to accordingly propagate information messages inside the VANET, while avoiding multiple copies of the same message to the same recipients.

Sectors provide loop-free message propagation along the transmission direction from the source vehicle, and are identified as portions of a circle. The sector size varies as a dynamic process, iteratively hop-by-hop, depending on the transmission direction from each transmitting vehicle (i.e., forward and backward in a highway scenario). The i-th sector is identified by an angle α i (h), where h is the index of current hop. Initially, in the h = 1 hop, there is a unique sector that includes the source vehicle's transmission range i.e., corresponding to an angle α(h) = 360 • . On the next hops (i.e., when h > 1), n sectors are identified, each one associated to the n-th forwarder vehicle, so that the following equation holds

n i=1 α i (h = 1) = 360 • , (1)
where α i (h = 1) is the i-th angle of the Direction-of-Arrival of each message transmitted by the source vehicle during the first hop. Notice that in order to avoid unnecessary message transmissions -message replications-, by the second hop (h = 2) we consider that each forwarder vehicle has an angle corresponding to its forward or backward transmission range, so that α(h = 2) = 180 • . Figure 2 depicts the sector identification in the first and second hop.

SRB considers a contention resolution procedure necessary to detect the ZOR and nearby clusters, and then elects relay nodes, each per single cluster. The contention procedure and cluster detection mechanism are detailed as follows:

• RTB transmission: A source vehicle transmits an Request-to-Broadcast (RTB) control message to all neighboring vehicles in the transmission range.

The RTB is a MAC-broadcast packet that contains the geographical position of the transmitter node. The RTB message size is 7.5 byte, (see Table 1). In the first hop, the message propagation direction is omnidirectional, while it changes for the next hops;

• Waiting time calculation: Upon receiving an RTB, vehicles compute their distance from the source vehicle (i.e., d [m]). The distance information is exploited in the calculation of the waiting time (i.e., t w [s])-a backoff time-which depends on maximum and minimum contention window, as follows:

t w = r tx -d r tx • (CW max -CW min ) + CW min • t slot , (2)
where r tx [m] is the transmission range, and CW max,min are the maximum and minimum contention window sizes, respectively. By using (2) vehicles in the further regions always transmit before the others. According to the CSMA/CA policy of IEEE 802.11, the backoff time is decremented by 1 at each idle slot, while the decrease is stopped when the medium is busy;

• CTB transmission: Whenever the waiting time associated to a vehicle countdowns to zero, the vehicle sends back to the source a Clear-to-Broadcast (CTB) packet, containing the vehicle ID and its distance from the source.

We set the CTB message size to 7.5 byte, (see Table 1) After receiving a valid CTB packet, vehicles exit the contention phase; in case of collisions, vehicles remain in the contention phase and resume the backoff process;

• Cluster detection: The source vehicle receives information on the ID and the distance from its nearby vehicles. By measuring the DoA of the CTB messages, the source vehicle is able to calculate all the mutual inter-vehicle distances among its nearby vehicles. If the distance between each couple of nearby vehicles is lower than a threshold value (i.e., D min ), the two vehicles will be considered belonging to the same cluster. The choice of D min influences the number of clusters identified: the higher the distance threshold, the higher the number of vehicles in each cluster. When 0 ← D min , each vehicle identifies a 1-size cluster; • Cluster-head election: After detecting multiple clusters, the source vehicle elects the furthest vehicle inside each cluster as the Cluster-Head, and transmits a data message only to such vehicle. We assume that the data message has a length of 1526 byte, (see Table 1). Upon receiving the data message, each CH will become the message source for the next contention phase, and the SRB algorithm is repeated for the next hops.

In Table 1 we report the main messages exchanged in the SRB technique. the availability of a third vehicle whose distance from the vehicle j is less than the threshold. When j > (i + 1), it is still possible to find other combinations of i and j (by increasing i), in order to assess if the cluster is a new cluster. An example of using the cluster detection mechanism is described in Figure 4.

Finally, in the next performance evaluation section, we will show that our technique delivers data with reasonable delay to most of the intended vehicles.

Moreover, the amount of transmitted packets per hop depends on the number of selected vehicles as forwarders, and it is expressed as:

pkt/hop = N i=1 (2n i + 1), ( 4
)
where N is the number of clusters detected by a source node per hop, and n i is the number of vehicles comprising the i-th cluster. The terms 2n i and 1 represent respectively the maximum number of packets RTB and CTB, and one data packet, transmitted in each hop3 .

Simulation Results

In this section, we analyze the performance of the proposed technique in two different cases i.e., (i) urban, and (ii) highway scenario. For urban scenario, we generate a 4 kilometers square grid with one lane per direction. In highway scenario, we select a 4 kilometers square area comprised of straight roads with 3 lanes per direction and several entries.

In both scenarios, we assume there are some ZORs, as previously defined, in unknown areas. Packets are generated with a constant generation rate (i.e., In order to assess the effectiveness of the proposed SRB protocol, we compare network performance with traditional broadcast approach, since SRB rises from this protocol.

Urban scenario

The urban scenario has been generated through the VanetMobiSim software [START_REF] Vanetmobisim | [END_REF], considering a 4 kilometers square grid, as shown in Figure 5 (a). Performance have been evaluated in terms of (i) throughput, (ii) number of elected CHs, (iii) message propagation, and (iv) end-to-end delay, by means of numerical simulations carried out with the ns-2.34 simulator [START_REF]Network simulator 2[END_REF]. In this scenario, we assume 150

vehicles are moving at constant speeds, and forming clusters only for a limitedshort-life-time interval.

The SRB performance mainly depends on the value of the distance threshold D min , since this parameter affects the number of vehicles in a cluster. As a consequence, the higher the distance threshold, the lower the number of clusters detected, or equally, the number of CH vehicles. By comparing results in Figure 6 (a) and (b), we notice that SRB protocol reaches peaks of 30 kbps, while for vehicles broadcasting packets the performance are limited to 5 kbps that could appear as a quite counterintuitive result. Basically, this is due since for a simple broadcast approach the vehicles forward messages to all neighboring, causing multiple copies of the same message, as well as higher collision probability. On the other side, SRB allows only a limited number of vehicles to retransmit packets, opportunistically selected, and then reducing the collision probability, as well as the number of message replica. In the broadcast case, the low value of average throughput is due only to the effective transmitted messages, without multiple copies and the collided ones. This result can be better analyzed together with the number of elected CH vehicles, giving information about the effectiveness of SRB protocol. Compared to traditional broadcast, the SRB selects only the 45% of vehicles as CHs and reaches an average throughput of 13 kbps. The resource usage is then limited.

In Figure 8 Finally, we show the comparison between SRB and traditional broadcast in terms of average end-to-end delay [s], versus the simulation time. In the case of SRB, Figure 9 (a) depicts how on average the delay is lower than 400 ms, which is particularly suitable for safety applications. Some delay peaks occur, due to multi-hop message propagation time, and the waiting time parameter, while the processing time to select CHs has been considered negligible. For the broadcast approach, as expected, the end-to-end delay is very short, since the message propagation is reduced to one hop propagation due to collisions and packet losses of broadcast storm effect. Figure 9 (b) depicts the end-to-end delay, basically corresponding to one-hop delay for broadcast approach.

All previous simulation results have shown that in urban scenarios, where vehicle density is not uniform and can limit the cluster formation, SRB provides high message propagation distance with low end-to-end delay, as well as an effective throughput. SRB overcomes traditional broadcasting techniques, and limits the effect of broadcast storming (i.e., collisions, message replica and packet losses).

Highway scenario

The second scenario, shown in Figure 5 (b), is based on a real urban map of a square-shaped portion of the city of Rome (Italy), with an area equal to 15 km 2 .

The map has been retrieved from the website of the Open Street Map (OSM) [START_REF]Open street map[END_REF].

The scenario represents a portion of GRA (Grande Raccordo Anulare, literally "Great Ring Road"), that is a toll-free, ring-shaped orbital motorway encircling Rome. GRA is one of the most important roads in Rome, and traffic reaches up to 160.000 vehicles per day. GRA features up to 42 junctions and in rush hours traffic congestions affect the road condition.

In such scenario we validated the SRB technique works very efficiently to detect clusters in an automatic and fast way, so that vehicles can avoid traffic congestions, and potentially are rerouted to different paths. The simulated scenario consists of a congested area with at least 15 vehicles driving in a platoon at low speed, while 70 vehicles drive into a nearby free area at high speed. Due to the huge area taken into account, we consider a simulation time of 300 s, in order to allow vehicles to move and communicate each others.

A vehicle coming from the free area should be able to fast detect the traffic congestion when approaching. Unlikely the urban scenario where vehicles form several clusters randomly, in highway environment we consider a huge cluster, depicted by low vehicle speed and high vehicle density. In the simulations we used a traffic simulator called Simulation of Urban Mobility (SUMO) [START_REF]SUMO project[END_REF] to generate traffic scenarios, and the trace files have been simulated on the network simulator ns-2.34.

In this section we show the most significant result, which allow to detect clusters in SRB approach i.e., (i) the average throughput. Again, the comparison to the broadcast protocol highlights the effectiveness of SRB.

Figure 10 (a) and (b) show the average throughput, respectively for SRB and broadcast protocol, versus the simulation time. In both cases, we notice an increase of throughput for t ≥ 175 s, when both SRB and broadcast protocol reach on average 2.0 kbps. This behavior is justified since at t = 175 s a vehicle moving in the highway approaches the congested area, and then an high number of data messages are exchanged. However, due to the nature of highway scenario, with a huge cluster of vehicles, the average value of throughput is lower than that in urban scenario. The initial peaks experienced with the broadcast protocol can be justified because of the increasing number of messages exchanged within the transmission range, which occurs at the beginning of the simulation.

Conclusions

In this paper we have addressed to recent efforts for mitigating the broadcast storm problem in VANETs. The Selective Reliable Broadcast (SRB) allows vehicles to selectively transmit messages within their own transmission range, resulting in a reduction of network overload, and limitation of message duplication.

SRB is particularly effective for safety applications: it relies on cluster-based routing protocols, as well as exploits the vehicles' positions, in order to detect traffic congestions (i.e., car platoons) in a fast way and with low overhead. Only a limited number of vehicles are elected as cluster-heads to forward messages. This allows to save network resources while keeping high performance.

SRB has been validated through extensive simulations, both in urban and highway scenarios, compared to traditional broadcast protocol. Results have shown that the proposed approach is able to detect vehicle clusters, and provides high distances for message dissemination. Especially in highway scenarios, SRB works efficiently by means of detecting congestion areas in a fast way.

Figure 1 :

 1 Figure 1: Schematic of several vehicle clusters. Vehicles belonging to the same cluster can communicate each other, while due to gaps among consecutive clusters, no inter-cluster communications are available.

Fig- ure 3

 3 depicts the main phases of SRB technique, for a forward data transmission along the vehicular grid. Once the CH vehicles are identified, they will forward messages according to SRB protocol.The design and implementation of the cluster detection mechanism in the SRB algorithm follows the steps of the method ClusterDetection(), as shown in the Algorithm 1 2 . Let us define:• veh, as a m × 1 array whose elements are the vehicles' IDs reachable by the transmitter vehicle. The array is sorted according to the angles formed by the DoA of the messages sent to the transmitter;

Figure 7

 7 depicts the percentage of CHs for different values of D min . Notice that for a low value of distance threshold the SRB is not able to select a limited number of CHs, and approximates the behavior of a traditional broadcast protocol (i.e., all neighboring vehicles are involved in data forwarding). In our simulations, we have considered D min = 150 m, which represents a good tradeoff with the transmission range (i.e., D min = r tx /2).

Figure 6

 6 Figure 6 depicts the average throughput [bit/s] experienced by vehicles communicating each others, in the case of SRB and traditional broadcast. During the simulation time, the vehicle cluster aggregation occurs in a random fashion, due tothe not homogeneous nature of the urban scenario (i.e., the presence of junctions and traffic lights can reduce cluster formation). Leveraging on this consideration, we can observe a variable behavior of throughput experienced in SRB technique, as shown in Figure6(a): in the first part of the simulation (i.e., for t < 50 s), the throughput shows high values and reaches 30 kbps, while in the second part (i.e., for t ≥ 50 s) low values of throughput occur. This is justified by an increase of data exchange which occurs for t < 50 s, when the cluster detection occurs; while for t ≥ 50 s vehicles aggregation in clusters is reduced and traffic flow becomes uncongested.

  (a) and (b) is depicted the average message propagation [m], for SRB and broadcast protocols. Data messages for SRB propagate in the network and reach on average long distances (i.e., up to 1.3 km far from the source); the vehicular environment is then almost fully "covered". It is also important to notice that performance trend reaches high values since a few seconds from the beginning of the simulation. These results suggest that the vehicular connectivity is largely guaranteed in the network. On the other hand, in Figure8(b) for traditional broadcast the message propagation shows low values (i.e., < 300 m corresponding to the maximum one-hop size). Again, this result is due mainly to the number of collisions and the packet drop probability; for each hop, packets are transmitted by a source vehicle to all the neighbors, resulting as a broadcast storm.

(h = 1 )

 1

Figure 2 :

 2 Figure 2: Sector formation process in SRB technique. The red and black points are respectively the source and neighboring vehicles, while the blue area represents the transmission range of one vehicle. In the first hop, during (a) RTB transmission, (b) CTB transmission, and (c) cluster-head selection, α(h = 1) = 360 • . By the second hop, (d) the message propagation is only backward or forward, and then α(h = 2) = 180 • .

Figure 3 :

 3 Figure 3: Main phases of SRB technique: (a) RTB transmission, (b) CTB transmission, (c) Cluster detection and CH election, and (d) message propagation.

d 10 < 1 d 2 d 3 d 1 j = 4 d 2 j = 4 d

 101231424 D min i = 0 j = 20 < D min i = 0 j = 30 > D min i = 0 j = 31 < D min i = 1 j = 3 d 41 > D min i = 42 > D min i = 43 > D min i = 3 j = 4

Figure 4 :

 4 Figure 4: Cluster detection mechanism implemented in SRB technique. From left to right, each vehicle computes the inter-distance among neighbors (i.e., d ij ) and compares it to the threshold (i.e., D min ), till the cluster is detected.

Figure 5 :

 5 Figure 5: Simulated scenarios for the assessment of SRB performance. (a) Urban scenario generated with VanetMobiSim [18], and (b) highway scenario (i.e., a selected portion of GRA, Rome Italy) generated with SUMO [19].

Figure 6 :

 6 Figure 6: Urban scenario. Average throughput for (a) SRB technique, and (b) broadcast approach, vs. simulation time.

Figure 7 :Figure 10 :

 710 Figure 7: Percentage of selected CH vehicles (dark blue) for different values of distance threshold. From left to right, D min = 250 m, 150 m, and 50 m. The rest of vehicles (light blue) is not involved into the message dissemination process.

Table 1 :

 1 Message exchanged classification and content.

	Message	Content	Size [byte]
	RTB	Source node's position	7.5
	CTB	Source-Destination distance	7.5
	Data	CH ID, data information	1526

Table 2 :

 2 Simulation Parameters

	Parameter	Value
	Simulation Duration	[100, 300] s
	IEEE 802.11b Transmission Range (r tx ) 300 m
	Data Rate (R)	6 Mbps
	D min	150 m

λ [pck/s]), and are transmitted according to a fixed data rate within a fixed transmission range. All vehicles are equipped with a GPS receiver and radio interfaces, compliant with the IEEE 802.11b standard. Table

2

collects the main parameters used in the simulations.

In this paper we use the term ZOR with the meaning of a congested traffic area.

The Algorithm 1 only represents the main scheme for cluster detection used in the SRB technique, but it is not that one used in our simulations

Eq. (4) represents an ideal scenario where drop packets and any collisions are omitted, or at least minimized.

• sels, as a dynamic array, initially null, whose elements are the forwarder vehicles' IDs (i.e., the selected vehicles for next hop forwarding).

During the initialization, we define three indexes i.e., i and j used to calculate the inter-vehicle distances, and k is the index associated to the array of forwarders (i.e., sels). The method ClusterDetection has a while command, which considers three different cases:

• Case 1: the index j is greater than the number of elements comprised in veh;

• Case 2: the distance between a couple of vehicles is less than R i.e., the minimum distance among clusters;

• Case 3: the distance between a couple of vehicles is greater than

The calculus of distances between two neighboring vehicles v i,j is done by means of the method distance(v i , v j ), and starts for a null value of angle. This means that the first comparison will be between the vehicle with index 0 and the vehicle with index 1, where 1 and 0 are the positions of elements of the array.

Each time that the distance is less of that one selected, the index j increases, while i is unchanged (i.e., we obtain j = 2 and i = 0). This represents the Case 1 in the above list. Notice that the value of M axDist has to be lower than the threshold D min . In the Case 2, when the inter-vehicle distance is higher than that one selected, the following condition holds j ≥ (i + 1).

(3)

When j = (i + 1), it is easy to understand that a new cluster has been detected, since all the possible combinations of i and j have been proven in order to verify Method: ClusterDetection()