Philippe Jouan
email: philippe.jouan@univ-rouen.fr

Ronald Manríquez
email: ronald.manriquez-penafiel@universite-paris-saclay.fr

Solvable Approximations of 3-dimensional Almost-Riemannian structures

Keywords: Almost-Riemannian geometry, Nilpotent approximation AMS subject classifications: 53C15, 53C17, 22E25, 53B99

In some cases, the nilpotent approximation of an almost-Riemannian structure can degenerate into a constant rank sub-Riemannian one. In those cases, the nilpotent approximation can be replaced by a solvable one that turns out to be a linear ARS on a nilpotent Lie group or a homogeneous space.

The distance defined by the solvable approximation is analyzed in the 3Dgeneric cases. It is shown that it is a better approximation of the original distance than the nilpotent one.

Introduction

The aim of this paper is to locally approximate almost-Riemannian structures (ARS in short) at singular points, by ARSs on Lie groups and to show that this approximation is generally better than the nilpotent one.

An ARS on an n-dimensional differential manifold is a rank-varying sub-Riemannian structure that can be defined, at least locally, by a set of n vector fields satisfying the Lie algebra rank condition (Larc in short). We denote by ∆ p the linear span of the vector fields at the point p. The set of points where dim(∆ p ) < n is called the singular locus or the singular set and denoted by Z. Many papers dedicated to the study of ARSs can be found in the literature, for instance [START_REF] Agrachev | Twodimensional almost-Riemannian structures with tangency points[END_REF], [START_REF] Bonnard | Conjugate and cut loci of a two-sphere of revolution with application to optimal control[END_REF], [START_REF] Bonnard | The sphere and the cut locus at a tangency point in two-dimensional almost-Riemannian geometry[END_REF], [START_REF] Boscain | Normal forms and invariants for 2dimensional almost-Riemannian structures[END_REF] [START_REF] Boscain | Lipschitz Classification of Almost-Riemannian Distances on Compact Oriented Surfaces[END_REF].

In the generic 3-dimensional case, in which we are particularly interested, the singular set is a codimension one embedded submanifold and the points where ∆ p = T p Z are isolated (see [START_REF] Agrachev | A gauss-bonnet-like formula on twodimensional almost-riemannian manifolds[END_REF] and [START_REF] Boscain | Local properties of almost-Riemannian structures in dimension 3[END_REF]).

We are likewise interested in the so-called simple ARSs on Lie groups (or homogeneous space) because they will be used as approximating structures for general ARSs: a simple ARS on an n-dimensional Lie group is an almost-Riemannian structure defined by n -1 left-invariant vector fields and one vector field whose flow is a one-parameter group of automorphisms, called linear in the sequel. Under some conditions, the singular set of such structures is a subgroup or an analytic, embedded, codimension one submanifold (see [START_REF] Ayala | Almost-Riemannian Geometry on Lie Groups[END_REF] and [START_REF] Jouan | Isometries of almost-Riemannian structures on Lie groups[END_REF]).

In some cases the nilpotent approximation of an ARS degenerates, because it is no longer an ARS but a constant rank sub-Riemannian structure. In other words, it may happen that some of the vector fields of the nilpotent approximation vanish, changing the almost-Riemannian structure into a constant rank sub-Riemannian one. For instance, if

X 1 =   1 0 0   , X 2 =   0 1 x   and X 3 =   0 0 x 2   ,
then its nilpotent approximation is

X 1 =   1 0 0   , X 2 =   0 1 x   and X 3 = 0.
It is what happens in some generic 3-dimensional cases (see for instance [START_REF] Boscain | Local properties of almost-Riemannian structures in dimension 3[END_REF]). In this paper we are interested in the case where only one of the vector fields vanishes and the other ones are independent: then they define a left-invariant sub-Riemannian structure on a Lie group (or a homogeneous space).

Our aim consists in recovering the almost-Riemannian structure lost in the nilpotent approximation, thanks to a vector field, denoted X n which is the homogeneous component of degree 0 of the Taylor expansion in privileged coordinates of the vector field that vanishes. The new family of vector fields composed by the nilpotent approximation and X n is called the solvable approximation.

The Lie algebra generated by this new family of vector fields is finite dimensional and solvable. However, we are interested in some nilpotent Lie group on which X n acts as a linear vector field (these vector fields were generalized in [START_REF] Ayala | Linear control systems on Lie groups and controllability[END_REF]). Thanks to the equivalence theorem of [START_REF] Jouan | Equivalence of control systems with linear systems on Lie groups and homogeneous spaces[END_REF] we know that the space R n is diffeomorphic to a homogeneous space. Through this diffeomorphism, the solvable approximation is equivalent to a simple ARS on a homogeneous space or a Lie group. It is important to notice that in the 3D-generic case the non-degenerated nilpotent approximation, and the solvable one in the degenerated case, are simple ARSs on Lie groups or homogeneous space (see Section 3.3).

On the other hand, the solvable approximation gives rise to a distance denoted by d. This distance has the advantage to be really almost-Riemannian unlike the distance d associated to the nilpotent approximation in the degenerated cases. The distance d is not homogeneous but always satisfies d ≤ d.

Denoting by d the distance associated to the original structure we show that in some 3D-generic cases the order of |d -d| is strictly better than the one of |d -d|. More accurately, the order of |d -d| is d Moreover, the nilpotent distance d is left-invariant while d and d are not. Using this fact we prove that for some pairs (q, q ) of points translated from the singular locus the difference |d(q, q ) -d(q, q )| is strictly smaller than |d(q, q ) -d(q, q )|.

The paper is organized as follows. Section 2 contains generalities about ARSs, nonholonomic order, privileged coordinates, the nilpotent approximation, linear vector fields and simple ARS on Lie groups or homogeneous spaces.

In Section 3 we introduce the definition of a solvable approximation, we analyze its algebraic structure and an example is detailed.

Section 4 is divided in two parts. In the first one, we state two propositions about the almost-Riemannian distance d defined by the solvable approximation. The second part is devoted to analyze d in the 3-dimensional generic case.

Finally, in Section 5 we provide the Hamiltonian associated to the flow defined by the solvable approximation in the 3D generic case and we compute the geodesics with initial condition x(0) = y(0) = z(0) = 0 and p(0) = cos(θ), q(0) = sin(θ), r(0) = r in a particular case.

Preliminaries

In this section some definitions and results are reviewed and come from [START_REF] Agrachev | A comprehensive introduction to sub-riemannian geometry[END_REF], [START_REF] Bellaïche | The Tangent space in sub-Riemannian geometry[END_REF] and [START_REF] Jean | Control of Nonholonomic Systems: from Sub-Riemannian Geometry to Motion Planning[END_REF].

Almost-Riemannian structures

An almost-Riemannian structure can always be locally defined by a set of n vector fields, where n is the dimension of the state space. Since we are interested in local questions, the following definition will be enough in this paper, and the reader is referred to [START_REF] Agrachev | A comprehensive introduction to sub-riemannian geometry[END_REF], [START_REF] Ayala | Almost-Riemannian Geometry on Lie Groups[END_REF] and [START_REF] Jean | Control of Nonholonomic Systems: from Sub-Riemannian Geometry to Motion Planning[END_REF] for the global definition on manifolds.

We denote by Lie(X 1 , . . . , X n ) the Lie algebra generated by the vector fields X 1 , . . . , X n on R n . Definition 1. We say that the vector fields X 1 , . . . , X n satisfy the Lie algebra rank condition (Larc in short) on an open set (ii) The singular locus, that is Z = {p ∈ Ω/rank (X 1 (p), X 2 (p), . . . X n (p)) < n} is non-empty, but with empty interior.

Ω of R n if Lie(X 1 , . . . , X n )(p) = T p R n , for all p ∈ Ω.
The metric is defined by declaring the frame to be orthonormal.

Remark 1.

1. The structure is Riemannian out of Z.

Let

v ∈ T p Ω. If p is a Riemannian point then v = n i=1 u i X i (p) in a unique way and its length is ||v|| = n i=1 u i 2 1 2
. If p ∈ Z then the decomposition of v, if it exists, is not unique and ||v|| = inf

   n i=1 u i 2 1 2 : v = n i=1 u i X i (p)    . An absolutely continuous curve γ : [0, T ] -→ R n is admissible if there exists a measurable essentially bounded function t → u(t) from [0, T ] into R n called control function such that γ(t) = u 1 (t)X 1 (γ(t)) + u 2 (t)X 2 (γ(t)) + . . . + u n (t)X n (γ(t)) for almost every t ∈ [0, T ]. Given an admissible curve γ : [0, T ] -→ R n , the length of γ is l(γ) = T 0 || γ(t)||dt.
The almost-Riemannian distance (or Carnot-Caratheodory distance) on Ω associated with the n-ARS is defined by

d(p 0 , p 1 ) = inf {l(γ) : γ(0) = p 0 , γ(T ) = p 1 , γ admissible} .
It induces the usual topology on Ω.

Nonholonomic orders

In what follows {X 1 , X 2 , . . . , X n } defines an ARS on Ω ⊂ R n . Definition 3. Let f : M → R be a continuous function. The nonholonomic order of f at p, denoted ord p (f ), is the real number defined by

ord p (f ) = sup {s ∈ R : f (q) = O (d(p, q) s )} .
This order is always nonnegative. Let C ∞ (p) denote the set of germs of smooth functions at p. For f ∈ C ∞ (p), we call nonholonomic derivative of order 1 of f the Lie derivatives

X 1 f, • • • , X n f . We call further X i X j f, X i X j X k f, . . . , the nonholonomic derivatives of f of order 2, 3, . . . of f . The nonholonomic derivative of order 0 of f at p is f (p).
As a consequence, the nonholonomic order of a smooth (germ of) function is given by the formula

ord p (f ) = min {s ∈ N : ∃ i 1 , . . . , i s ∈ {1, . . . , n} s.t. (X i 1 . . . X is f ) (p) = 0} ,
where as usual we adopt the convention that min ∅ = +∞.

Let V F (p) denote the set of germs of smooth vector fields at p. Definition 4. Let X ∈ V F (p). The nonholonomic order of X at p, denoted by ord p (X), is the real number defined by:

ord p (X) = sup {σ ∈ R : ord p (Xf ) ≥ σ + ord p (f ), ∀ f ∈ C ∞ (p)} .

Privileged coordinates

We adopt the notation of [START_REF] Jean | Control of Nonholonomic Systems: from Sub-Riemannian Geometry to Motion Planning[END_REF] to define privileged coordinates. Let V F (Ω) denote the set of smooth vector fields on Ω. We define ∆

1 = span {X 1 , . . . , X n }. For s ≥ 1, define ∆ s+1 = ∆ s + [∆ 1 , ∆ s ],
where

[∆ 1 , ∆ s ] = span [X, Y ] : X ∈ ∆ 1 , Y ∈ ∆ s .
For p ∈ Ω, we set for s ≥ 1, ∆ s (p) = {X(p) : X ∈ ∆ s }. By definition these sets are linear subspaces of T p Ω. The evaluation of these sets at p forms a flag of subspaces of T p Ω, and since X 1 , . . . , X n satisfy Larc, we get,

∆ 1 (p) ⊂ ∆ 2 (p) ⊂ • • • ⊂ ∆ r-1 (p) ∆ r (p) = T p Ω, (1)
where r = r(p) is called the degree of nonholonomy at p.

Let n i (p) = dim ∆ i (p).
The r-tuple of integers (n 1 (p), . . . , n r (p)) is called the growth vector at p. The first integer in the growth vector is the rank n 1 (p) ≤ n of the family X 1 (p), . . . , X n (p), and the last one n r (p) = n is the dimension of R n .

Definition 5. The point p is regular if the growth vector is constant in some neighborhood of p. Otherwise we say that p is a singular point.

The structure of the flag (1) may also be described by another sequence of integers. We define the weights at p, w i = w i (p), i = 1, . . . , n, by setting w j = s if n s-1 (p) < j ≤ n s (p), where n 0 = 0. In other words, we have

w 1 = • • • = w n 1 = 1, w n 1 +1 = • • • = w n 2 = 2, . . . , w n r-1 +1 = • • • = w nr = r.
Definition 6. A system of privileged coordinates at p is a system of local coordinates (x 1 , . . . , x n ) such that ord p (x j ) = w j , for j = 1, . . . , n.

On the other hand, given a sequence of integers α = (α 1 , . . . , α n ) we define the weight of the monomial

x α = x α 1 1 • • • x αn n to be w(α) = w 1 α 1 + • • • + w n α n
and the weighted degree of the monomial vector field x α ∂ ∂x j to be w(α) -w j . The weighted degrees allow to compute the orders of functions and vector fields in a purely algebraic way. Constructions of privileged coordinates can be found in [START_REF] Bellaïche | The Tangent space in sub-Riemannian geometry[END_REF] and [START_REF] Jean | Control of Nonholonomic Systems: from Sub-Riemannian Geometry to Motion Planning[END_REF].

Proposition 1 ([15], Proposition 2.2). For a smooth function f with a Taylor expansion in privileged coordinates

f (x) ∼ α c α x α ,
the order of f is the least weighted degree of monomials having a nonzero coefficient in the Taylor series. For a vector field X with a Taylor expansion in privileged coordinates

X(x) ∼ α,j a α,j x α ∂ ∂x j ,
the order of X is the least weighted degree of a monomial vector field having a nonzero coefficient in the Taylor series.

Remark 2. A vector field of degree < -r vanishes.

The one-parameter family of dilations δ λ : R n -→ R n is defined by δ λ (x) = (λ w 1 x 1 , λ w 2 x 2 , . . . , λ wn x n ), λ ≥ 0. A dilation δ λ acts also on functions and vector fields by pull-back:

δ * λ f = f • δ λ and δ * λ X is the vector field such that (δ * λ X)(δ * λ f ) = δ *
λ (Xf ). So we have the following definition. Proposition 5.16). Let X and Y be vector fields on M . If X and Y are homogeneous of degree k and l respectively (in the chosen system of privileged coordinates) then [X, Y ] is homogeneous of degree k + l or vanishes. w i is the so-called pseudo-norm at p. Remark 3. Let x = (x 1 , . . . , x n ) be a system of privileged coordinates defined on an open neighborhood U of the point p. When composed with the coordinate functions, the pseudo-norm at p is (non smooth) homogeneous of order 1, that is, ||x(q)|| p = O(d(p, q)), where x(q) are the coordinates of q ∈ U .

Definition 7. A function f is homogeneous of degree s if δ * λ f = λ s f . A vector field X is homogeneous of degree s if δ * λ X = λ s X. Proposition 2 ([7],

Nilpotent approximation

Fix a system of privileged coordinates (x 1 , . . . , x n ) at p. Every vector field X i is of order ≥ -1, hence it has, in x coordinates, a Taylor expansion

X i (x) ∼ α,j a α,j x α ∂ ∂x j ,
where w(α) ≥ w j -1 if a α,j = 0. Grouping together the monomial vector fields of same weighted degree we express X i as a series of homogeneous vector fields of the form

X i = X (-1) i + X (0) i + X (1) i + X (2) i + • • • , (2) where X
(s) i has degree s. We set

X i = X (-1) i , i = 1, . . . , n.
Definition 9. The family of vector fields X 1 , . . . , X n is called the nilpotent approximation of the system (X 1 , . . . , X n ) at p. Proposition 3 ([7], Proposition 5.17). The vector fields X i , i = 1, . . . , n, generate a nilpotent Lie algebra Lie X 1 , . . . , X n of step r = w n . They satisfy Larc at every point y ∈ R n , and the distance d is finite for every x, y ∈ R n .

The following results are found in [START_REF] Bellaïche | The Tangent space in sub-Riemannian geometry[END_REF] and [START_REF] Jean | Control of Nonholonomic Systems: from Sub-Riemannian Geometry to Motion Planning[END_REF] and will be useful in this work.

Proposition 4 ([7] Proposition 7.25 and [START_REF] Jean | Control of Nonholonomic Systems: from Sub-Riemannian Geometry to Motion Planning[END_REF], Lemma 2.1). There exist positive constants C, C such that for all q ∈ R n we have

C||q|| p ≤ d p (p, q) ≤ C ||q|| p .
Lemma 1 ([15], Lemma 2.2). There exists constant C and ε > 0, such that, for any z 0 ∈ R n and any t ∈ R + satisfying τ = max (||z 0 || p , t) < ε, we have

||z(t) -z(t)|| p ≤ Cτ t 1 r ,
where z(•) and z(•) are trajectories of the nonholonomic systems defined respectively by X 1 , . . . , X n and X 1 , . . . , X n starting at the same point z 0 , associated with the same control function u(•), and satisfying ||u(t)|| = 1 a.e.

To finish, we recall the very important Theorem 7.32 of [START_REF] Bellaïche | The Tangent space in sub-Riemannian geometry[END_REF] stated here with a slight modification.

Theorem 1 (Theorem 7.32 in [START_REF] Bellaïche | The Tangent space in sub-Riemannian geometry[END_REF]). There exist constants ε > 0 and C > 0 such that for any q, q ∈ B(p, ε), we have

-Cτ d(q, q ) 1 r ≤ d(q, q ) -d(q, q ) ≤ C τ d(q, q ) 1 r ,
where τ is as in Lemma 1 and τ is similarly defined, this is τ = max (||q|| p , d(q, q )) and τ = max ||q|| p , d(q, q ) .

Linear vector fields

The definition of linear vector fields comes from [START_REF] Ayala | Linear control systems on Lie groups and controllability[END_REF] and [START_REF] Jouan | Equivalence of control systems with linear systems on Lie groups and homogeneous spaces[END_REF].

Let G be a connected Lie group and g its Lie algebra (the set of left-invariant vector fields, identified with the tangent space at the identity). The set of analytic vector fields on G is denoted by V ω (G), and the normalizer of g in V ω (G) is by definition

N = norm V ω (G) g = {X ∈ V ω (G) : ∀ Y ∈ g [X, Y ] ∈ g} .
Definition 10. A vector field X on G is said to be linear or to be infinitesimal automorphism (see [START_REF] Bourbaki | Eléments De Mathematique. Groupes et Algèbres de Lie: Chapitres 2 et 3[END_REF]), if X belongs to N and X (e) = 0, where e is the identity of G.

We can see in [START_REF] Jouan | Equivalence of control systems with linear systems on Lie groups and homogeneous spaces[END_REF] that a vector field X on G if and only its flow (φ t ) t∈R is a one-parameter group of automorphisms of G and a linear vector field is consequently analytic and complete.

Simple ARS's on Lie groups

Linear and invariant vector fields make it possible to define almost-Riemannian structures on Lie groups. The following definition is given in [START_REF] Ayala | Almost-Riemannian Geometry on Lie Groups[END_REF]. Definition 11. A simple ARS is an ARS defined on a connected Lie group G by a set of n vector fields {X , Y 1 , . . . , Y n-1 } where X is linear, Y 1 , . . . , Y n-1 are leftinvariant, dim G = n and the rank of X , Y 1 , . . . , Y n-1 is full on a non empty subset of G and the set {X , Y 1 , . . . , Y n-1 } satisfies Larc.

For instance, the famous Grushin plane on the Abelian Lie group R 2 is a simple ARS. This structure was introduced in [START_REF] Ayala | Almost-Riemannian Geometry on Lie Groups[END_REF] and its isometries have been study in [START_REF] Jouan | Isometries of almost-Riemannian structures on Lie groups[END_REF].

In Section 3.3 a 3-dimensional example will be provided.

Simple ARS's on homogeneous spaces

Consider a homogeneous space G/H of a connected and simply connected Lie group G by a closed subgroup H (the elements of G/H are right cosets of H because we deal with left-invariant vector fields). Since we are interested in simply connected quotients we assume H to be connected. Let g be the Lie algebra of G, identified with the space of left-invariant vector fields. The projection of such a vector field Y on G/H is well-defined, is referred to as a left-invariant vector field, and we can assume that it vanishes identically only if Y is the zero field (see details in [START_REF] Jouan | Equivalence of control systems with linear systems on Lie groups and homogeneous spaces[END_REF]). 2. The singular set Z where their rank is less than n is proper with empty interior.

In the sequel, we will need (a simplified version of) the equivalence Theorem (see [START_REF] Jouan | Equivalence of control systems with linear systems on Lie groups and homogeneous spaces[END_REF] and [START_REF] Ayala | Almost-Riemannian Geometry on Lie Groups[END_REF]).

Theorem 2 (Equivalence Theorem). Let f 1 , . . . , f n be a set of n complete vector fields on R n and let us assume:

1. f 1 , . . . , f n define an Almost-Riemannian Structure on R n ; 2. The Lie algebra L generated by f 1 , . . . , f n is finite dimensional; 3. The ideal g generated in L by f 1 , . . . , f n-1 is nilpotent and of codimension 1 in L.
Then R n is diffeomorphic to a homogeneous space G/H of the nilpotent simply connected group G generated by g and f 1 , . . . , f n defines a simple ARS on G/H. More accurately the vector fields f 1 , . . . , f n-1 are left-invariant and f n is linear on this homogeneous space.

Solvable Approximation

In this section we introduce the solvable approximation of an ARS and we analyze its algebraic structure.

Definition

Let {X 1 , . . . , X n } be a set of vector fields defining an almost-Riemannian structure on an open neighborhood of 0 ∈ R n . The point p = 0 is assumed to belong to the singular locus, the natural coordinates of R n to be privileged and we consider the nilpotent approximation X 1 , . . . , X n of {X 1 , . . . , X n } at p = 0.

It may happen that some of the vector fields X i vanish, possibly changing the almost-Riemannian structure defined by X 1 , . . . , X n into a constant rank sub-Riemannian one. It is what happens in some cases of generic 3-dimensional ARSs that are described in detail in Section 3. [START_REF] Agrachev | A gauss-bonnet-like formula on twodimensional almost-riemannian manifolds[END_REF]. In what follows we are interested in the case where only one of the X i 's vanishes, say X n = 0, and the other ones are independent and define a left-invariant sub-Riemannian structure on a Lie group, or a homogeneous space, the underlying manifold of which is R n . Recall that each X i can be expanded in a series of homogeneous vector fields in the system of privileged coordinates at p = 0, this is

X i = X (-1) i + X (0) i + X (1) i + . . . , ∀ i ∈ {1, . . . , n}, where X (k) i is the homogeneous component of degree k. Denoting X n = X (0)
n , we introduce the following definition: Definition 12 (Solvable approximation). The family X 1 , . . . , X n-1 , X n is the solvable approximation of {X 1 , . . . , X n }. Proposition 5. L = Lie X 1 , . . . , X n-1 , X n is a finite dimensional solvable Lie algebra. Its step of solvability is less than or equal to log 2 (r) + 1, where r is the degree of nonholonomy at p = 0.

Proof. Let D k L stand for the k th derived algebra of L, with L = D 0 L. According to Proposition 2 and Remark 2 the algebra L is generated by homogeneous vector fields of degree 0, -1, . . . , -r because the X i 's are homogeneous of degree -1, for i = 1, . . . , n -1, and X n is homogeneous of degree 0. According to Proposition 2 again D 1 L is generated by homogeneous vector fields of degree -1, . . . , -r. More generality D s L is generated by homogeneous vector fields of degree -2 s-1 , -2 s , . . . , -r, so that D s L = 0 if 2 s > r. Therefore L is solvable and the step of solvability σ of L satisfies σ ≤ log 2 (r) + 1. On the other hand, the Lie algebra L splits into homogeneous components

L = L 0 ⊕ L -1 ⊕ L -2 ⊕ . . . ⊕ L -r ,
where L -s is the set of homogeneous vector fields of degree -s under the action of δ λ . A homogeneous vector field X of degree w ∈ {0, -1, -2, . . . , -r} writes in

coordinates X(x) = n i=1 f i (x) ∂ ∂x i
, where f i (x) is a homogeneous polynomial function of degree w + ord(x i ). Since the space of polynomials of degree w + ord(x i ) is finite dimensional, L -w is finite dimensional. Therefore L is finite dimensional.

Remark 4. It is clear that the families of vector fields X 1 , . . . , X n-1 , X n and {X 1 , . . . , X n } have the same nilpotent approximation. Consequently the family of vector fields X 1 , . . . , X n-1 , X n satisfies Larc on R n and the growth vector at 0 of X 1 , . . . , X n-1 , X n is equal to the one of {X 1 , . . . , X n }.

Structure of the approximating system

Fundamental remark. Despite the previous result we are not interested in the solvable Lie group associated to the Lie algebra Lie X 1 , . . . , X n-1 , X n but in some nilpotent Lie group on which X n acts as a linear vector field.

For this reason we denote by h the Lie algebra generated by X 1 , . . . , X n-1 and by g the ideal generated by h in L = Lie X 1 , . . . , X n-1 , X n . Proposition 6. The ideal g is the space of vector fields of L whose nonholonomic order is negative. It is a nilpotent Lie algebra and

L = g ⊕ R X n . Moreover D = -ad( X n ) is a derivation of g.
Proof. Since g is the ideal generated by h in L, we have L = R X n ⊕ g and ad X n is a derivation of g.

Let G be the simply connected Lie group whose Lie algebra is isomorphic to g. According to [START_REF] Jouan | Equivalence of control systems with linear systems on Lie groups and homogeneous spaces[END_REF] there exists a linear vector field on G associated to the derivation D = -ad X n . With a clear abuse of notation we will denote it by X n . Thanks to the equivalence theorem we have the following: Theorem 3. The space R n is diffeomorphic to a homogeneous space G/G 0 of G. Through this diffeomorphism X 1 , . . . , X n-1 , X n is equivalent to a simple ARS on G/G 0 , and the Lie algebra g 0 of G 0 is isomorphic to the set of vector fields of g that vanish at 0.

Proof. First of all, notice that the vector fields X 1 , . . . , X n-1 , X n are complete from their triangular form, namely, in the equation ẋ = n i=1 u i X i (x) + u n X n (x), ẋj is linear with respect to the coordinates of weight w j and polynomial with respect to coordinates of weight < w j (see [START_REF] Bellaïche | The Tangent space in sub-Riemannian geometry[END_REF] or [START_REF] Jean | Control of Nonholonomic Systems: from Sub-Riemannian Geometry to Motion Planning[END_REF] for details). They define an ARS, hence in particular satisfy Larc and generate a finite dimensional Lie algebra (Proposition 5). According to Theorem 2 R n is diffeomorphic to a homogeneous space G/G 0 of G, where G 0 is the connected subgroup of G whose Lie algebra is, after identification of L(G) with g, the set of elements of g that vanish at 0. Thanks to the diffeomorphism between R n and G/G 0 the system X 1 , . . . , X n-1 , X n can be identified to a simple ARS on G/G 0 .

We are also interested in conditions for which G = R n . Theorem 4. With the previous notations the following assertions are equivalent:

(i) ad X n . X i belongs to Span X 1 , . . . , X n-1 for i = 1, . . . , n -1;

(ii) h is ad X n -invariant; (iii) h = g.
Under these conditions X n is a linear vector field on exp(h).

Proof.

(i) ⇒(ii) It is an immdiate consequence of the Jacobi identity.

(ii)⇒(iii) Condition (ii) implies L = h ⊕ R X n , hence h = g. (iii)⇒(i) Condition (iii) implies that h is ad X n -invariant.
According to Proposition 2 the set of elements of h of order -1 is Span X 1 , . . . , X n-1 . For i = 1, . . . , n -1 the bracket X i , X n belongs to h, since h = g, and is of order -1 or is equal to 0. Therefore it belongs to Span X 1 , . . . , X n-1 .

Example. The 3D-generic case

The local representation of a generic ARS in dimension 3 is detailed in Section 4.2. Its nilpotent approximation at a point of the singular locus is the following:

X 1 =   1 0 0   , X 2 =   0 1 x cos σ   , X 3 =   0 0 x sin σ   , where σ ∈ 0, π 2 .
There are two particular cases, according to the value of the parameter σ. The first one for σ = π 2 , because the bracket of X 1 and X 2 vanishes, and the second one for σ = 0, because X 3 vanishes, it is the tangent case.

More accurately the Lie brackets are:

X 1 , X 2 =   0 0 cos σ   , X 1 , X 3 =   0 0 sin σ   , X 2 , X 3 = 0.
The analysis of the different cases is as follows:

1. General case σ ∈ 0, π 2 .

We can set Z =   0 0 cos σ   so that X 1 , X 2 = Z and ( X 1 , X 2 , Z) is the Heisenberg Lie algebra. Since X 3 vanishes at (0, 0, 0) and since its Lie brackets with X 1 , X 2 and Z are

X 1 , X 3 = tan(σ)Z and X 2 , X 3 = Z, X 3 = 0,
it is a linear vector field on the Heisenberg group, the associated derivation of which is

D =   0 0 0 0 0 0 tan σ 0 0   .
The conclusion is that X 1 , X 2 , X 3 defines a simple ARS on the 3D Heisenberg group.

Particular case

σ = π 2 .
Then

X 1 =   1 0 0   , X 2 =   0 1 0   , X 3 =   0 0 x   .
It is a simple ARS on the Abelian Lie group R 3 . Indeed X 1 and X 2 are (left and right) invariant and X 3 is linear.

3. Tangent case σ = 0. Here the nilpotent approximation degenerates into the following sub-Riemannian structure on the Heisenberg group

X 1 =   1 0 0   , X 2 =   0 1 x   , X 3 =   0 0 0   .
However we will see after the next remark that in case where the component X 3 of order 0 of the vector field X 3 does not vanish then X 1 , X 2 , X 3 defines a simple ARS on a homogeneous space.

Remark 5. In the cases σ = π 2 and σ ∈ 0, π 2 the Lie algebra generated by X 1 , X 2 , X 3 is 4-dimensional and two points of view are possible. The usual one consists in considering R 3 as a homogeneous space of a nilpotent 4-dimensional Lie group. Our point of view is to consider X 3 as a linear vector field on the 3dimensional Lie group R 3 endowed with the Abelian structure if σ = π 2 and the Heisenberg one if σ ∈ 0, π 2 . Following this way we will consider the solvable approximation whenever σ = 0, and finally all approximations of generic 3D-ARS will appear as being simple ARS.

The solvable approximation of the tangent case σ = 0.

The homogeneous component of nonholonomic order 0 of X 3 is

X 3 =   0 0 az + bx 2 + cy 2   = az + bx 2 + cy 2 ∂ ∂z (See Section 4.2 again).
As well as in the general case the Lie algebra generated by X 1 and X 2 is:

h = Span X 1 , X 2 , Z = X 1 , X 2 where Z =   0 0 1   = ∂ ∂z ,
that is the Heisenberg algebra. On the other hand the algebra generated by X 1 , X 2 and X 3 is Span X 1 , X 2 , Z, X 1 , X 3 , X 2 , X 3 , X 3 , where:

X 1 , X 3 =   0 0 2bx   = 2bx ∂ ∂z and X 2 , X 3 =   0 0 2cy + ax   = (2cy + ax) ∂ ∂z ,
and the ideal generated by X 1 and X 2 is:

g = Span ∂ ∂x , ∂ ∂y + x ∂ ∂z , 2bx ∂ ∂z , 2cy ∂ ∂z + ax ∂ ∂z , ∂ ∂z .
A straightforward computation shows that X 3 acts as a derivation on g. If we assume b = 0 and c = 0 then we have also:

g = Span ∂ ∂x , x ∂ ∂z , ∂ ∂y , y ∂ ∂z , ∂ ∂z .
This is the 5-dimensional Heisenberg Lie algebra h 2 and in this basis the derivation D = -ad( X 3 ) is given by the following matrix:

D =       0 0 2b a 0 0 2c a a       .
Finally the solvable approximation X 1 , X 2 , X 3 is a simple ARS on R 3 diffeomorphic to a quotient of the 5-dimensional group Heisenberg H 2 .

Distances

We can distinguish three different families of vector fields from the above section: {X 1 , X 2 , . . . , X n }, X 1 , . . . , X n-1 and X 1 , . . . , X n-1 , X n which satisfy Larc. Assuming orthonormality, they define three different distances: d, d and d respectively, where d and d are defined on R n . This section is divided in two parts. In the first one, we give two propositions about the almost-Riemannian distance d defined by the solvable approximation. The second part is devoted to analyze d in the 3-dimensional generic case.

The almost-Riemannian distance d

The following proposition establishes a relation between d and d. It is important because it allows us to find an upper bound for d (see Section 4.2.2) and to compare the distances of the solvable and nilpotent approximation.

Proposition 7. For all x, y ∈ R n , d(x, y) ≤ d(x, y).

Proof. Let x, y ∈ R n and let γ be a minimizing geodesic for ẋ =

n-1 i=1 u i X i , such that γ(0) = x, γ(T ) = y. Setting u n = 0 the curve γ is admissible for ẋ = n-1 i=1 u i X i + u n X n .
Since u n = 0 the length of γ is the same for both metrics, hence

d(x, y) ≤ l(γ) = d(x, y).
Let δ λ be the dilation related to the privileged coordinates and the weights at p = 0. We know that the distance d is homogeneous of degree 1 with respect to δ λ (see [START_REF] Jean | Control of Nonholonomic Systems: from Sub-Riemannian Geometry to Motion Planning[END_REF]). However d does not possess this property. This is due to the fact that X n and the X i 's do not have the same degree of homogeneity. Proposition 8. The almost-Riemannian distance d is not homogeneous.

Proof. Let γ be an admissible curve for d, that is

γ(t) = n-1 i=1 u i X i (γ(t)) + u n X n (γ(t)). (3)
Since X i and X n are homogeneous of degree -1 and 0 respectively and the pullback by δ λ of a vector field X (see [START_REF] Abraham | Manifolds, tensor analysis, and applications[END_REF]) is defined by

dδ λ (q) (δ * λ X(q)) = X δ λ (q) , (4)
we get

dδ λ (q). X i (q) = dδ λ (q).λ • δ * λ X i (q) = λ X i δ λ (q) and dδ λ (q). X n (q) = dδ λ (q).δ * λ X n (q) = X n δ λ (q) .
(

) Therefore d dt (δ λ • γ) (t) = dδ λ (γ(t)) . γ(t) = n-1 i=1 u i dδ λ γ(t) . X i γ(t) + u n dδ λ γ(t) . X n γ(t) = n-1 i=1 λu i X i δ λ γ(t) + u n X n δ λ γ(t) . 5
This implies that l(δ λ γ) = λl(γ), except if u n (t) vanishes a.e. This proves the non homogeneity of d.

The 3D-tangential case

In Section 3, we have established a model to locally approximate an n-ARS whose nilpotent approximation is a constant rank sub-Riemannian structure, by a solvable approximation. In this context we want to determine conditions for |d -d| to be smaller than |d -d|.

Recall that ∆(p) = span {X 1 (p), . . . , X n (p)} and the singular locus Z is the set of points of R n where the rank of the linear span of the vector fields is less than n. From [START_REF] Boscain | Local properties of almost-Riemannian structures in dimension 3[END_REF] we take the following.

type-2 points where ∆(p) has dimension 2 and is tangent to Z.

Moreover type-2 points are isolated, type-1 points form a 2 dimensional manifold and all other points are Riemannian.

The local representation of the 3-dimensional ARS at type-2 points is given by the vector fields

X 1 =   1 0 0   , X 2 =   0 1 + δ(x, y, z) x (1 + θ(x, y, z))   , X 3 =   0 0 az + bx 2 + cy 2 + o (x 2 + y 2 + |z|)   ,
where δ and θ are smooth functions of order greater than or equal to 1 anda, b, c are not all zero. Furthermore, from Subsection 3.3, the nilpotent approximation in privileged coordinates is

X 1 = X 1 =   1 0 0   , X 2 =   0 1 x   , X 3 = 0. and X 3 =   0 0 az + bx 2 + cy 2   .
X 1 , X 2 , X 3 is the solvable approximation at p = 0 in case when 0 is a tangential (type-2) point.

Divergence of curves

Let p = 0 be a type-2 point such that the coordinates centered at p are privileged and q, q belonging to the ball centered at p and radius , denoted by B(p, ).

In this subsection we analyze the divergence of curves respectively admissible for d and d, defined by the same control functions and starting at the same point q. More accurately: let γ be the geodesic for d such that γ(0) = q, γ(T ) = q with u 2 1 + u 2 2 + u 2 3 = 1 and let γ be the admissible curve for d defined by the same control functions as γ with γ(0) = q. We have the following:

γ(t) -˙ γ(t) = u 1 X 1 (γ) -X 1 ( γ) + u 2 X 2 (γ) -X 2 ( γ) + u 3 X 3 (γ) -X 3 ( γ)   ẋ(t) -˙ x(t) ẏ(t) -˙ y(t) ż(t) -˙ z(t)   =   0 u 2 δ(x, y, z) u 2 xθ(x, y, z) + u 3 (a(z -z) + b (x 2 -x 2 ) + c (y 2 -y 2 ) + o (x 2 + y 2 + |z|))  
We have successively:

• ẋ(t) = ˙ x(t), hence x(t) = x(t). • ẏ(t) -˙ y(t) = u 2 δ(x, y, z), hence y(t) -y(t) = t 0 u 2 (s)δ(x, y, z)ds.
We denote by ρ ≥ 1 the order of δ.

Then |δ(x, y, z)| ≤ Cst • ||γ(s)|| ρ p ≤ Cst • τ ρ because ||γ(s)|| p ≤ Cst • τ
, where τ = max (||q|| p , t) (the proof of the above inequality is given in the proof of Lemma 1 of [START_REF] Jean | Control of Nonholonomic Systems: from Sub-Riemannian Geometry to Motion Planning[END_REF]), hence

|y(t) -y(t)| ≤ t 0 Cst • ||γ(s)|| ρ p ds ≤ t 0 Cst • τ ρ ds = Cst • τ ρ • t. (6)
•

ż(t)-˙ z(t) = u 2 xθ(x, y, z)+u 3 (a(z -z) + c (y 2 -y 2 ) + o (x 2 + y 2 + |z|)), hence z(t)-z(t) = t 0 u 2 (s)xθ(x, y, z)ds+ t 0 u 3 (s)a(z-z)ds+ t 0 u 3 (s)c y 2 -y 2 ds+ t 0 u 3 (s)o x 2 + y 2 + |z| ds.
Since (x, y, z) are privileged coordinates at 0, then

x 2 +y 2 +|z| ≤ C•d(0, (x, y, z)) 2 . Moreover, if f ((x, y, z)) = o(x 2 +y 2 +|z|), then f ((x, y, z)) = o(d(0, (x, y, z)) 2 ). This implies that ord p (f ) > 2, hence f (γ(t)) = O (d(0, γ(t)) 3 ). Therefore |f (γ(t))| ≤ Cst • τ 3 .
On the other hand, let us denote by m ≥ 1 the order of θ.

Then |x • θ(x, y, z)| ≤ Cst • τ • ||γ(s)|| m p ≤ Cst • τ m+1 because ẋ = u 1 , hence |x| ≤ Cst • t + ||q|| p ≤ Cst • τ . Also notice y 2 -y 2 = |y + y| |y -y| ≤ Cst • τ ρ • t • τ = Cst • t • τ ρ+1 , because ẏ = u 2 (1 + δ(x, y, z)), hence |y| ≤ Cst • t + ||q|| p ≤ Cst • τ . Similarly for y. Then |z(t) -z(t)| ≤ Cst • t • τ m+1 + Cst • t 2 • τ ρ+1 + Cst • t • τ 3 + t 0 |a||z -z|ds |z(t) -z(t)| ≤ Cst • t • τ m+1 + t 2 • τ ρ+1 + t • τ 3 e |a|t |z(t) -z(t)| ≤ Cst • t • τ min(m+1,ρ+1,3) . (7)
Finally,

||γ(t) -γ(t)|| p = |x(t) -x(t)| + |y(t) -y(t)| + |z(t) -z(t)| 1 2 ≤ Cst t • τ ρ + t 1 2 • τ min(m+1,ρ+1,3) 2 ≤ Cst • t 1 2 • τ min(m+1,ρ+1 ,3) 2 . (8)
Remark 6. The order of δ(x, y, z) does not change the inequality

||γ(t) -γ(t)|| p ≤ Cst • τ • t 1 2 ,
that comes from Lemma 1. Indeed,

||γ(t) -γ(t)|| p ≤ Cst t • τ ρ + t 1 2 • τ ≤ Cst • t 1 2 • τ.

Upper bounds

In order to state our main result in the next section, we need upper bounds for the distances d and d.

We know that the distance d is left-invariant, this is to say, d(q, q ) = d(a•q, a•q ), for all a ∈ R 3 . Here • stands for the Heisenberg product defined by

(x, y, z) • (x , y , z ) = (x + x , y + y , z + z + xy ) . (9)
Recall also that d(q, q ) ≤ d(q, q ). Considering the above, we have d(q, q ) ≤ d(q, q ) = d(0, q -1 q ) ≤ C||q -1 q || p .

Considering q = (x, y, z) and q = (x , y , z ) and from ( 10) and ( 9) we have

d(q, q ) ≤ C||q -1 • q || p = C |x -x| + |y -y| + |z -z + x(y -y )| 1 2 ≤ C |x -x | + |y -y | + |z -z | 1 2 + |x(y -y )| 1 2 ≤ C ||q -q || p + ||q|| 1 2 p |y -y | 1 2 . ( 11
)

Upper bound for d

From Theorems 7.31 and 7.26 of [START_REF] Bellaïche | The Tangent space in sub-Riemannian geometry[END_REF] we get

d(q, q ) ≤ Cst k,j|w k ≤w j ||q|| 1- w k w j p |q k -q k | 1 w j , (12)
Since w 1 = w 2 = 1 and w 3 = 2 we obtain that

d(q, q ) ≤ Cst ||q -q || p + ||q|| 1 2 p |y -y 2 | 1 2 + |x -x 2 | 1 2 . ( 13
)

Main result

We have seen that the order of δ does not change the estimation of ||γ(t) -γ(t)|| p according to Lemma 1, moreover, it does not change the estimates of d as well, this is to say, d(γ(t), γ(t)) ≤ Cst • t 1 2 • τ . Indeed, from inequality [START_REF] Boscain | Local properties of almost-Riemannian structures in dimension 3[END_REF] and Remark 6, we get

d(γ(t), γ(t)) ≤ Cst t 1 2 • τ + t • τ 1 2 +ρ , then d(γ(t), γ(t)) ≤ Cst • t 1 2
• τ . However, the above is not true when we want to estimate d, because the estimates depend of ρ and m. Indeed, from inequalities [START_REF] Bonnard | Conjugate and cut loci of a two-sphere of revolution with application to optimal control[END_REF] and [START_REF] Boscain | Normal forms and invariants for 2dimensional almost-Riemannian structures[END_REF] we get

d(γ(t), γ(t)) ≤ Cst • t 1 2 • τ min(m+1,ρ+1,3) 2 + t 1 2 • t 1 2 • τ ρ 2 ≤ Cst • t 1 2 • τ min(m+1,ρ+1 ,3) 2
.

Therefore, we can conclude that if ρ ≥ 2 and m ≥ 2 then

d(γ(t), γ(t)) ≤ Cst • t 1 2 • τ 3 2 .
Finally, we obtain:

Proposition 11. If ord p (δ) ≥ 2 and ord p (θ) ≥ 2, then 1. d(γ(t), γ(t)) ≤ Cst • t 1 2 • τ 3 2 . 2. d(γ(t), γ(t)) ≤ Cst • t 1 2 • τ 3 2 .
Proof. The proof of item 2 follows from inequalities [START_REF] Bonnard | Conjugate and cut loci of a two-sphere of revolution with application to optimal control[END_REF] and [START_REF] Bourbaki | Eléments De Mathematique. Groupes et Algèbres de Lie: Chapitres 2 et 3[END_REF].

Theorem 5. If m ≥ 2 and ρ ≥ 2, then there exists constants C and > 0, such that, for all q, q ∈ B(p, ), we have

-Cτ 3 2 d(q, q ) 1 2 ≤ d(q, q ) -d(q, q ) ≤ C • τ 3 2 d(q, q ) 1 2 , (14)
where τ = max (||q|| p , d(q, q )) τ = max ||q|| p , d(q, q ) .

Proof. Let q belonging to B(p, ). Let us consider the geodesics γ : [0, T ] → M for the distance d such that γ(0) = q, γ(T ) = q and associated with the control function u(•) satisfying ||u(t)|| = 1 and γ the admissible curve for d defined by the same control functions that γ with γ(0) = q. By Proposition 11 item 1

d (γ(T ), γ(T )) ≤ Cst • T 1 2 • τ 3 2 . ( 15
)
On the other hand, note that d(q, q ) = l(γ) = l( γ) ≥ d (q, γ(T )) .

Moreover, by triangle inequality, we have d (q, γ(T )) ≥ d (q, q ) -d (q , γ(T )) ,

Then, from [START_REF] Jean | Control of Nonholonomic Systems: from Sub-Riemannian Geometry to Motion Planning[END_REF], transitivity and since γ(T ) = q , we get

d(q, q ) ≥ d (q, q ) -Cst • T 1 2 • τ 3 2 d(q, q ) -d (q, q ) ≥ -Cst • T 1 2 • τ 3 2 (16)
Now, we change the roles of d and d and by Proposition 11 item 2, we obtain

d(q, q ) -d (q, q ) ≤ Cst • T 1 2 • τ 3 2 , ( 17
)
where T = d(q, q ). Therefore from ( 16) and ( 17)

-Cτ 3 2 d(q, q ) 1 2 ≤ d(q, q ) -d(q, q ) ≤ C • τ 3 2 d(q, q ) 1 2 .
The proof is complete.

Translations

We mentioned in Section 4.2.2 that the distance d is left-invariant. It is not the case of d. Let q be a point in a neighborhood of 0 and g ∈ R 3 . We are interested in conditions under which d(g, g • q) ≤ d(0, q) (the product is the Heisenberg one). Let γ(t) = x(t), y(t), z(t) be a geodesic of d such that γ(0) = 0 with control functions u 1 , u 2 and u 3 . We consider g = (g 1 , g 2 , g 3 ) ∈ R 3 . Let γ g (t) = L g (γ(t)) = (x g (t), y g (t), z g (t)) and u 1 , u 2 , u 3 its control functions. Note that γ g is admissible for d as long as it does not meet Z. Indeed, all absolutely continuous curves are admissible out of the singular locus since the metric is Riemannian. The goal is to find conditions for g such that γ g has a length less than γ. Since Lie X 1 , X 2 is the Heisenberg algebra, then L g (γ(t)) = (x(t) + g 1 , y(t) + g 2 , z(t) + g 1 y(t) + g 3 ) .

We set h(x, y, z) = az + bx 2 + cy 2 . Then

h(γ g ) = a(z + g 1 y + g 3 ) + b(x + g 1 ) 2 + c(y + g 2 ) 2 = h(γ) + h(g) + (2bx + ay)g 1 + 2cyg 2 = h(γ) + h(g) + f (g, γ),
where f (g, γ) = (2bx + ay)g 1 + 2cyg 2 . We assume that h(γ g ) does not vanish, this is to say γ g is not on Z. In particular for t = 0, h(γ g ) = h(g) then h(g) = 0 this is equivalent to g / ∈ Z. We have the following result. Theorem 6. Let γ : [0, T ] -→ R n be a length minimizer of d with control functions u 1 (t), u 2 (t), u 3 (t) with u 3 (t) = 0 a.e, and h (γ g ) = 0. If |h(γ)| ≤ |h(γ g )| then d (γ g (0), γ g (T )) ≤ d (γ(0), γ(T )).

Proof. Since x g (t) = x(t) + g 1 then ẋg (t) = ẋ(t) = u 1 (t). This implies that u 1 (t) = u 1 (t). In the same way, we obtain u 2 (t) = u 2 (t) because y g (t) = y(t) + g 2 . Furthermore, z g (t) = z(t) + g 1 y(t) + g 3 then żg

(t) = ż(t) + g 1 ẏ(t) = u 2 (t)x g (t) + u 3 (t)h (γ(t)) . (18)
Besides the above equation, z g (t) satisfies the equation

żg (t) = u 2 (t)x g (t) + u 3 (t)h (γ g (t)) , (19)
because γ g is an admissible curve for d. Finally, from the equations ( 19) and ( 18) and as u 2 (t) = u 2 (t) we get

u 3 (t) = u 3 (t)h (γ(t)) h (γ g (t)) . The condition |h(γ)| ≤ |h(γ g )| implies that |u 3 (t)| ≤ |u 3 (t)|, hence u 3 (t) 2 ≤ u 3 (t) 2 .
Therefore the length of γ g decreases and consequently d (γ g (0), γ g (T )) ≤ d (γ(0), γ(T )).

In the same sense of the above theorem, the following result gives us a sufficient condition to determine when the distance of the points translated by g is less than the distance from the origin to γ(T ). Theorem 7. With the same conditions of the above. If

∂ ∂g i (h(g) + f (g, γ)) h (γ g ) > 0
then d (γ g (0), γ g (T )) < d (γ(0), γ(T )).

Proof. From Theorem 6, the control functions of γ g are u 1 (t), u 2 (t) and u 3 (t), hence

l (γ g ) = T 0 u 1 (t) 2 + u 2 (t) 2 + u 3 (t) 2 1 2 dt = T 0 u 1 (t) 2 + u 2 (t) 2 + u 3 (t) 2 h(γ(t)) 2 h(γ g (t)) 2 1 2 dt ∂ ∂g i l (γ g ) = T 0 1 2 (u 1 (t) 2 + u 2 (t) 2 ) h(γ g (t)) 2 + u 3 (t) 2 h(γ(t)) 2 h(γ g (t)) 2 -1 2 • ∂ ∂g i u 3 (t) 2 h(γ(t)) 2 h(γ g (t)) 2 dt = T 0 -|h(γ g (t))|u 3 (t) 2 h(γ(t)) 2 ((u 1 (t) 2 + u 2 (t) 2 ) h(γ g (t)) 2 + u 3 (t) 2 h(γ(t)) 2 ) 1 2 h(γ g (t)) 3 • ∂ ∂g i (h(g) + f (g, γ)) dt = - T 0 u 3 (t) 2 h(γ(t)) 2 ∂ ∂g i (h(g) + f (g, γ)) ((u 1 (t) 2 + u 2 (t) 2 ) h(γ g (t)) 2 + u 3 (t) 2 h(γ(t)) 2 ) 1 2 |h(γ g (t))|h(γ g (t))
dt.

Note that the function S defined by

S(t) = u 3 (t) 2 h(γ(t)) 2 ∂ ∂g i (h(g) + f (g, γ)) (u 1 (t) 2 + u 2 (t) 2 h(γ g (t)) 2 + u 3 (t) 2 h(γ(t)) 2 ) 1 2 |h(γ g (t))|h(γ g (t))
is positive if and only if

∂ ∂g i (h(g) + f (g, γ)) h(γ g (t)) > 0.
In this case ∂l(γ g ) ∂g i < 0 and d (γ g (0), γ g (T )) < d (γ(0), γ(T )).

In particular at g = (0, 0, 0),

∂ ∂g i l (γ g ) (g 1 ,g 2 ,g 3 )=(0,0,0) = - T 0 u 3 (t) 2 ∂ ∂g i (h(g) + f (g, γ)) h(γ(t)) dt.

Conclusion

In Section 3, we have shown that in case where the nilpotent approximation of an ARS degenerates, that is when it is no longer an ARS but a sub-Riemannian structure, we can replace it by a simple ARS on a Lie group or a homogeneous space. Thanks to formula [START_REF] Byrd | Handbook of elliptic integrals for engineers and physicists[END_REF] of Theorem 5 we know that, at least in some 3D generic cases, the order of the approximation of d by d is better than the one of the approximation of d by d. Indeed, this order is d2 in the first case and d

For this purpose, we consider here the 3D-generic case of Section 4.2 with the particular values a = 1, b = c = 0, that is X 3 = z ∂ ∂z . The singular locus of the solvable approximation is then the plane {z = 0}.

In what follows we consider a (normal) geodesic γ for d, originated at (0, 0, 0) and parametrized by arc length on [0, T ]. Denoting γ(t) = (x(t), y(t), z(t)) it is moreover assumed that z(t) > 0 on ]0, T ].

This geodesic is translated by g = (0, 0, g), with g ≥ 0, into γ g = L g γ. Since g belongs to the center of the Heisenberg group the curve γ g is simply γ g (t) = (x(t), y(t), z(t) + g).

The different distances between g and γ g (T ) are analyzed in several steps.

1. Since the controls associated to γ g are u 1 , u 2 , and

z(t) z(t) + g u 3 the length of γ g related to d is l(γ g ) = T 0 u 2 1 + u 2 2 + z(t) z(t) + g 2 u 2 3 1 2 dt. Since z -→ z z + g
is increasing we have l(γ g ) ≤ I g , where I g stands for

I g = T 0 u 2 1 + u 2 2 + z m z m + g 2 u 2 3 1 2 dt, with z m = max{z(t); t ∈ [0, T ]}.
2. We apply now formula [START_REF] Byrd | Handbook of elliptic integrals for engineers and physicists[END_REF], which writes here:

d(g, γ g (T )) ≤ d(g, γ g (T )) + C • τ 3 2 d(g, γ g (T )) 1 2 ,
where τ = max g p , d(g, γ g (T )) . It will always be assumed that g p ≤ d(g, γ g (T )), that is g It is important to notice that r 0 can be chosen arbitrarily large because H(t = 0) = 1 2 (p 2 0 + q 2 0 ). We make the choice p 0 = q 0 and the following approximations hold:

x(t) ≈ p 0 t, ż ≈ q 0 p 0 t = 1 2 t, z(t) ≈ 1 4 t 2 , u 3 (t) = r(t)z(t) ≈ 1 4 r 0 t 2 .

In order to compute l(γ g ), we need to apply the condition g 1 2 ≤ d(g, γ g (T )) of point 2. We do not know d(g, γ g (T )) but we can set d(g, γ g (T )) = βT with 0 < β < 1 (this estimation "a priori" will be justified later), and set g = β 2 T 2 . Then we get z z + g ≤ z m z m + g ≈ dt.

We write δ = 2β 4 +β 2 2(1+4β 2 ) 2 and we set δr 2 0 T 4 = 1 2 . Notice that this is possible, even if T is small, by increasing r 0 . Thanks to (1 -c) Therefore d(g, γ g (T )) -d(g, γ g (T )) > d(g, γ g (T )) -d(g, γ g (T )) as soon as T Ig -1.01 > 0.01 hence as soon as Ig T < 0.98. According to Point 3, we can obtain I g ≤ 0.95T and in that case the solvable distance between g and γ g (T ) is strictly closer to the original distance between these points than the nilpotent one.

Geodesics

In this section the Hamiltonian for the normal flow defined by the solvable approximation in the 3D generic case is given. We compute the geodesic with initial condition x(0) = y(0) = z(0) = 0 and covector λ = (p, q, r) ∈ T * R 3 with p(0) = cos(θ), Since q(0) = sin(θ) and q = 0, then q = sin(θ). Hence ẍ + r 2 x + 2r 2 x 3 = -r sin(θ).

(

) 23
The equation ( 23) is equivalent to ẍ + r 2 x + 2r 2 x 3 = -r sin(θ)cn(0, k 2 ),

where cn(0 • t, k 2 ) is the Jacobian elliptic function that has a period in 0 • t equal to 4K(k 2 ) and K(k 2 ) is the complete elliptic integral of the first kind for the modulus k (see more in [START_REF] Byrd | Handbook of elliptic integrals for engineers and physicists[END_REF]). This equivalence is due to the fact that cn(0, k 2 ) = 1.

In [START_REF] Zúñiga | A General Solution of the Duffing Equation[END_REF] a general solution to ẍ + c n ẋ + w n x + x 3 = F cn(wt, k 2 ), is given by x(t) = a 1 (t)cn w 1 t + φ, k 2 1 + A 1 (t)cn wt, k 2 + B 1 (t) • sn wt, k 2 .

Therefore, the solution for the equation ( 24) is given by

x(t) = a 1 (t)cn w 1 t + φ, k 2 1 + A 1 (t),
where a 1 (t), A 1 (t), w 1 , φ and k 1 need to be determined. Notice that B 1 (t) • sn (wt, k 2 ) vanishes because sn(0, k 2 ) = 0.

Definition 2 .

 2 The set {X 1 , . . . , X n } defines an almost-Riemannian structure (ARS in short) on the open and connected subset Ω of R n if:(i) It satisfies Larc.

Definition 8 .

 8 The function defined by x → ||x|| p = n i=1 |x i | 1

Proposition 9 .

 9 Consider a 3-ARS. The following conditions are generic for 3-ARSs (G1) dim(∆(p)) ≥ 2 and ∆(p) + [∆(p), ∆(p)] = T p M for every p ∈ M ; (G2) Z is an embedded (possibly empty) two-dimensional submanifold of M ; (G3) the points where ∆(p) = T p Z are isolated. Proposition 10. Under the previous conditions there are three types of points: 1. Riemannian points where ∆(p) = T p M . 2. type-1 points where ∆(p) has dimension 2 and is transversal to Z.

1 2 ≤T 2 d

 22 d(g, γ g (T )). Taking into account d(g, γ g (T )) ≤ d(g, γ g (T )) = d(0, γ(T )), we get d(g, γ g (T )) ≤ d(g, γ g (T )) + C • d(g, γ g (T )) 2 ≤ I g T d(0, γ(T )) + C • I g

3 .

 3 In order to approximate z(t) and u 3 (t), we consider the Hamiltonian equations (see details in the next section), for the values a = 1, b = c = 0. They are: ẏ = q + rx ż = (q + rx)x + rz 2

1 2 ≤ 2 =

 22 1 -0.5c whenever 0 ≤ c ≤ 1 we get:l(γ g ) ≤ I g ≤ T 0 1 -0.5δr 2 0 t 4 dt = T -0.5δr 2 0 T 5 5 = T (1 -0.1δr 2 0 T 4 ) ≈ 0.95T. 4. Assuming C • d(0, γ(T )) = C • T ≤ 0.01 we get on one hand:d(g, γ g (T )) ≤ d(g, γ g (T )) + C • d(g, γ g (T )) d(g, γ g (T ))(1 + C • d(g, γ g (T ))) ≤ 1.01 d(g, γ g (T )).On the other hand:d(g, γ g (T )) -d(g, γ g (T )) ≥ d(g, γ g (T ) 1 -1.01 I g T = d(g, γ g (T )) d(g, γ g (T )) d(g, γ g (T )) 1 -1.01 I g T ≥ d(g, γ g (T )) T I g 1 -1.01 I g T = d(g, γ g (T )) T I g -1.01 .

Figure 1 :

 1 Figure 1: Geodesics for θ ∈ 0, π 3 , 2π 3 , π, 4π 6 , 5π 6 when r = 0.

and the one of |d -d| is d 2 in the cases we consider.

in the second one. However, this does not prove that the solvable approximation is really better than the nilpotent one, and anyway it is certainly not true for any pair of points.Since under left translations the nilpotent distance d is invariant while the solvable distance d may be decreasing, we can expect to prove that the approximation by d is strictly better than the one by d for pairs of points translated in a suitable direction.

q(0) = sin(θ), r(0) = r.

From the above sections, the solvable approximation is defined by

From (20), the Hamiltonian for the normal flow is given by

where λ = (p, q, r) ∈ T * R 3 . Hence

are the associated Hamiltonian equations to the solvable approximation.

The geodesic with initial condition x(0) = y(0) = z(0) = 0 and p(0) = cos(θ), q(0) = sin(θ) and r(0) = r = 0 is given by

because p(t) = cos(θ) and q(t) = sin(θ), this is to say p and q are constants. Notice that the above geodesic for d is the same as the geodesic for d. The above implies that this geodesic is optimal for any time and has no conjugate time (see Theorem 5.1 and 5.2 in [START_REF] Boscain | Local properties of almost-Riemannian structures in dimension 3[END_REF]). We can see some geodesics in Figure 1 when r = 0.

Due to the complexity of the Hamiltonian system of equations, we compute the geodesics considering a = c = 0 and b = 1. Thus the Hamiltonian is

Considering the initial condition x(0) = 0 then p(0) = cos(θ), q(0) = sin(θ) and r(0) = r. If r = 0 then the solution to the differential systems ( 22) is given by (21). If r(0) = r = 0, since ẋ(t) = p, we get ẍ = -r(q + rx) -2r 2 x 3 ẍ + r 2 x + 2r 2 x 3 = -rq.

From [START_REF] Zúñiga | A General Solution of the Duffing Equation[END_REF] is possible to obtain that a 1 (t) and A 1 (t) are constants. Then

Moreover, since x(0) = 0

Furthermore, differentiating in (25) and since ẋ(0) = p(0) = cos(θ), we have

Finally, since y(0) = z(0) = 0,

where k 2 1 + k 2 1 = 1, E(•) is the incomplete elliptic integral of the second kind and


Walid Saad

Zhu Han

Are Hjørungnes

Mérouane Debbah

Network Formation Games for Distributed Uplink Tree Construction in IEEE 802.16j Networks

This paper investigates the problem of the formation of the uplink tree structure among the mobile multi-hop relay (MMR) network's base station (MMR-BS) and its different relay stations (RSs). We model the problem as a network formation game in which the RSs want to form a directed tree graph to improve their utility in terms of the Packet Success Rate (PSR) by using multi-hop cooperative transmission while accounting for a link maintenance cost. In this game, the relay stations engage in bilateral negotiations which result in a contractual agreement to form a directed link between each pair. For network dynamics, we propose a myopic algorithm based on the local best responses of the RSs that converges to a local Nash network. Moreover, the proposed dynamics algorithm allows the RSs to autonomously adapt the network topology to changes in the environment due to mobility or to the presence of heterogeneous traffic. Simulations results show how the RSs can self-organize in a tree structure while improving the network's overall PSR up to 17.5% and 15.6% compared, respectively, to the cases where no RSs exist and where the RSs are directly connected to the MMR-BS.

I. INTRODUCTION

Spatial diversity has proven to be an effective technique for mitigating the fading effects of the wireless channel. Through relaying, mobile nodes cooperate with a given source node in the transmission of its information to a particular destination allowing the source node to benefit from spatial diversity gains. This class of cooperating nodes is referred to as cooperative communications [1] where multiple nodes cooperate to form a virtual multiple antenna array. It has been shown that by using one or multiple relays [1-3] a significant improvement can be witnessed in terms of Bit Error Rate (BER), outage probability and other QoS parameters. For this purpose, the incorporation of cooperative transmission in wireless network standards such as cellular or broadband networks has been under thorough investigation recently. For instance, the IEEE 802.16j Mobile Multi-hop Relay (MMR) task group introduced the concept of multi-hop relaying in the IEEE 802.16 WirelessMAN (WiMAX) family of broadband networks [START_REF]The Relay Task Group of IEEE[END_REF]. In 802.16j, a new node, known as the Relay Station (RS) is introduced in the network for the purpose of enhancing capacity and coverage through multi-hop relaying.

The introduction of the RS yields several performance improvements but also faces various challenges. Existing literature tackles several issues related to MMR networks. On one hand, the authors in [START_REF] Lin | Optimal relay station placement in IEEE 802.16j networks[END_REF] study the possibility of selecting an optimal position of one RS, which maximizes the total rate, in the presence of one or multiple subscriber stations for the downlink. On the other hand, the work done in [START_REF] Yu | Planning base station and relay station locations in IEEE 802.16j multi-hop relay networks[END_REF] investigates the MMR network planning problem with the main aim to find the optimal locations of the MMR-BSs and the RSs for the full deployment of an 802.16j network with minimal monetary costs. The work in [START_REF] Shrestha | New approaches for relay selection in IEEE 802.16 mobile multi-hop relay networks[END_REF] provides an algorithm for selecting the optimal downlink path from the MMR-BS to an MS through one or several RS based on a maxi-min throughput criterion. Nevertheless, one promising area in the context of 802.16j networks, which remains an open problem is the formation of the tree structure connecting the MMR-BS to the RSs in its coverage area [START_REF]The Relay Task Group of IEEE[END_REF]. In general, the tree can either be formed at the level of the MMR-BS (centralized approach) or as a result of individual decisions of the RS (distributed approach) [START_REF]The Relay Task Group of IEEE[END_REF], [START_REF] Lee | Link adaptive multihop path management for IEEE 802.16j[END_REF]. To our knowledge, few existing work has tackled the tree formation problem. The main existing work is done in [START_REF] Lee | Link adaptive multihop path management for IEEE 802.16j[END_REF] through a centralized approach that accounts for the link quality between the RSs. Nevertheless, [START_REF] Lee | Link adaptive multihop path management for IEEE 802.16j[END_REF] does not account for cooperative transmission on the physical layer. In addition, a centralized approach can yield significant communication overhead, notably in large scale networks with a rapidly changing environment due to RS mobility or incoming heterogeneous traffic.

The main contribution of this paper is to derive a distributed tree formation algorithm for the uplink of an MMR network while accounting for multi-hop cooperative transmission. We model the problem as a network formation game among the RSs. The utility of each RS accounts for the QoS in terms of Packet Success Rate (PSR) as well as the costs for link maintenance. Moreover, we derive a myopic dynamics algorithm for network formation based on local best response strategies of the RSs. In the proposed dynamics, each pair of RSs engage in bilateral negotiations for forming a directed link that can improve the utility of both the initiating and accepting nodes. The dynamics algorithm allows the RSs to self-organize into a local Nash network tree structure rooted at the MMR-BS. Finally, we show how the RSs can autonomously self-organize in order to cope with changes in the environment due to mobility or the presence of heterogeneous data traffic.

The rest of this paper is organized as follows: Section II presents the system model and the game formulation. Section III exposes the properties of the network formation game and presents the proposed dynamics algorithm. Simulation results are presented and analyzed in Section IV. Finally, conclusions are drawn in Section V.

II. SYSTEM MODEL A. System Model and Game Formulation

Consider the uplink of an MMR network with M RSs and one MMR-BS (referred to as BS hereafter). The goal is to propose a distributed algorithm for forming the tree encompassing the BS and all the RSs. Once the uplink tree is formed, the mobile stations (MSs) can connect to the network by selecting a serving RS (or by connecting directly to the BS). We assume that each MS deposits its packets at the serving RS through direct transmission. Subsequently, the serving RS acts as a source node and transmits the packets of the MS to the BS through one or multiple hops using cooperative transmission. This assumption on the MSs is considered in order to restrict our attention to the tree formation problem among the RSs which belong to a single WiMAX operator. By doing so, we can propose an algorithm that can be easily integrated within a new or an existing WiMAX network without relying on external entities such as the MSs. For the transmission between each RS and the BS we adopt the decoded relaying multi-hop diversity channel of [START_REF] Boyer | Multihop diversity in wireless relaying channels[END_REF]. In this model, each intermediate node on the path between a transmitting RS and the BS combines, encodes and reencodes the received signal from all preceding terminals before relaying (decode-and-forward). Formally, each RS i will receive T i packets from all connected MSs, and is required to transmit these packets to the BS through multi-hop relaying along the tree. We also denote by R i the packets received by RS i from connected RSs for relaying purposes. In addition, we assume that all the RSs will continuously transmit one packet, known as a "HELLO" packet in order to maintain their links to the BS active during periods of no activity, i.e., in the absence of MSs. An illustrative example of this system model is shown in Fig. 1.

For modeling the distributed formation of an uplink tree such as in Fig. 1, network formation games provide a suitable framework [START_REF] Jackson | The evolution of social and economic networks[END_REF][START_REF] Demange | Group formation in economics: networks, clubs and coalitions[END_REF][START_REF] Johari | A contract based model for directed network formation[END_REF][START_REF] Derks | Local dynamics in network formation[END_REF]. These games study the interactions among multiple players that want to form a network graph. Each player is considered as a decision maker, and through the various communications among these decision makers a final graph G can form. We model the uplink tree formation problem among the RSs as a network formation game with the RSs being the players. The result of this game is a directed graph G(V, E) formed from V = {1, . . . , M } vertices corresponding to the M RSs and E edges or links. Each link between two RSs i and j denoted ij ∈ E is a directed connection that goes from RS i to RS j representing the communication flow in the uplink from i to j. Each pair of RSs i and j engage in bilateral negotiations, where RS i suggests to form a link with j, and RS j has the opportunity to either accept or reject the offer. If RS j accepts the proposition of i, a contract is formed between i and j corresponding to the directed link ij. We assume that the BS accepts any connection from any RS, and thus it is considered as an additional fixed vertex in any network graph G. This assumption is motivated by the fact that the WiMAX operator deploys the RSs in order to enhance the performance of the BS and thus, the BS should be able to serve all the deployed RSs. Therefore, in addition to the other RSs, a RS can also negotiate a contract with the BS. The strategy space of each RS is further detailed in Section III. Additionally, we define the notion of path as follows.

Definition 1: A path between two nodes i and j in the graph G is defined as a sequence of nodes i 1 , . . . , i K such that i 1 = i, i K = j and each directed link i k i k+1 ∈ G for each k ∈ {1, . . . , K -1}. We denote the set Q i as the set of all paths from node i to the BS, and thus |Q i | represents the number of paths from node i to the BS.

Each RS extracts a positive utility from the packets success- fully transmitted to the BS out of the T i packets received from external MSs, while accounting for the BER of transmission which constitutes a first cost for transmission. In addition, a RS extracts a positive utility proportional to the number of packets relayed R i . The main driver behind this relaying benefit is that the importance of the role of a RS i in the network increases if this RS i serves more RSs and relays more packets, and thus its utility should also increase. Moreover, for each RS j, a maintenance cost must be paid for each connection resulting from a link ij directed from RS i to RS j. In summary, given a network graph G, for each RS i ∈ V the cost and benefit is captured by the following utility

U i (G) = α i • (T i + 1) |Q i | • |Qi| q=1 (1 -P e q ) K + β i • R i -C(L i ), (1)
where P e j is the BER that RS i achieves while transmitting the T i data packets and 1 HELLO packet to the BS using the decodeand-forward model of [START_REF] Boyer | Multihop diversity in wireless relaying channels[END_REF] encompassing all the RSs connecting i to the BS through the path q ∈ Q i (i divides its packets equally among all paths) and K is the size of the packets in bits. Consequently, the term (1 -P e q ) K represents the Packet Success Rate (PSR) of the traffic going through each path q ∈ Q i from i to the BS. R i is the number of packets received by i from other RSs for relaying purposes. C(L i ) is a maintenance cost factor that is an increasing function of the number L i of incident links from other RSs on RS i. α i and β i are a price per unit of packets correctly transmitted or relayed; without loss of generality, we assume

α i = β i = 1. For a transmission between a node V 1 ∈ V to a destination V n+1 (the destination is always the BS, thus V n+1 = BS) going through n -1 intermediate relays {V 2 , . . . , V n } ⊂ V , denote N r
as the set of all receiving terminals, i.e., N r = {V 2 . . . V n+1 } and N r(i) as the set of terminals that transmit a signal received by terminal V i . For a relay V i on the path from the source V 1 to the destination V n+1 , we have V r(i) = {V 1 , . . . , V i-1 }. Given this notation, the BER between a source RS V 1 ∈ V and the BS destination V n+1 = BS will be computed along the path q = {V 1 , . . . , BS} ∈ Q V1 using the tight upper bound given in [START_REF] Boyer | Multihop diversity in wireless relaying channels[END_REF] for the decoded relaying multi-hop diversity channel with BPSK modulation as follows

P e q ≤ Ni∈Nr 1 2     N k ∈N r(i)     Nj ∈N r(i) N j =N k γ k,i γ k,i -γ j,i × 1 - γ k,i γ k,i + 2 . (2) With γ i,j = Pi•hi,j σ 2
the average received SNR at node j from node i where P i is the transmit power of node i, σ 2 the noise variance and h i,j = 1

d µ i,j
is the path loss with d i,j the distance between i and j and µ the path loss exponent. Without loss of generality, we assume that all the RSs will transmit with equal power P i = P , ∀i. Finally, for a RS i which is connected to the BS through a direct transmission path q d ∈ Q i with no intermediate hops, the BER can be given by P e q d = 1 2 1 -γi,BS 2+γi,BS [START_REF] Sadek | Multinode cooperative communications in wireless networks[END_REF], [START_REF] Boyer | Multihop diversity in wireless relaying channels[END_REF]; with γ i,BS is the SNR received at the BS from RS i.

B. Cost

Any well designed maintenance cost function C(L i ) for a RS i must satisfy several requirements that are needed for adequately modeling the cost for connectivity. For this purpose, we will inspect the part of the utility which shows the rewards and costs on a RS i for accepting a connection from other RSs that is

f (L i ) = R i -C(L i ).
First, for any RS i, accepting a first link must incur a very low cost C(L i ) and must be feasible for the smallest possible reward in terms of relayed packets R i . Thus, we must have f (1) > 0 for the smallest reward R i = 1, yielding C(1) < 1 (obviously C(0) = 0), that is a RS i will accept at least one link from other RSs. Second, each RS i can only support a fixed number of connections λi < λ i from other RSs. The maximum number of connections λ i can be configured by the operator in the RSs or it can have a fixed value based on the physical capabilities of the RS. As a result, we must have f (λ i ) = -∞ and thus C(λ i ) = +∞. The final requirement is that, as the number L i increases, C(L i ) must start increasing slowly and then must reach a steeper increase slope. One function satisfying these requirements is the log barrier function

C(L i ) = -c i • log (1 -( L i λ i ) 2 ), (3)
where λ i represents the maximum number of connections whereby C(L i ) = +∞; ∀L i ≥ λ i and c i represents a pricing parameter that imposes the minimum relaying benefit required for adding one link (moving from L i to L i + 1). Similarly to λ i , the pricing parameter c i can be configured in the RSs by the network operator depending on the requirements in terms of minimum packet needs for different L i . For a better understanding of the pricing parameter c i consider the rate of increase of f as we move from L i links to

L i + 1 links given by ∆f = f (L i +1)-f (L i ) = (R i (L i +1)-R i (L i ))+(C(L i )-C(L i +1)), thus ∆f = ∆R i -c i • log (1 -( Li λi ) 2 ) (1 -( Li+1 λi ) 2 ) . (4)
The minimum number of packets ∆R i that a RS i requires in order to accept an incoming connection is given by setting ∆f > 0 and thus yielding

∆R i to move from L i to L i +1 c i =1 c i =5 c i =10 c i =15
Fig. 2. Minimum required number of packets ∆R i for RS i in order to accept one additional incoming link (moving from L i to L i + 1) for λ i = 5.

∆R i > c i • log (1 -( Li λi ) 2 ) (1 -( Li+1 λi ) 2 ) . (5)
Through ( 5) we note that, for a fixed maximum number of RS connections λ i , the pricing parameter c i determines the minimum required number of packets ∆R i for different L i . The relation between c i and ∆R i is shown in Fig. 2 for λ i = 5. For a given L i , as c i increases the minimum ∆R i required by RS i increases. For example, for c i = 10 RS i requires 1 packet only to accept a first link (L i = 0) but it requires at least 6 packets to accept a fourth link (L i = 3). Finally, the curve's rate of increase in L i satisfies our requirements and is asymptotic to L i = 4 since λi < 5 (adding 1 link from L i = 4 yields an infinite cost).

III. NETWORK FORMATION GAME: PROPERTIES, STRATEGIES AND DYNAMICS A. Properties and strategy space of the proposed game

Several properties of the proposed game can be highlighted. The first property relates to the connectivity of any network graph G formed using our model as follows.

Property 1: Any network graph G resulting from the proposed network formation game will be a connected graph where all the relay stations can communicate through the BS.

Proof: First of all, as mentioned in the previous section, the BS will accept a connection from any RS. Moreover, by inspecting the utility in (1) we notice that if a RS i is not connected to the BS through direct transmission or other multihop paths, the BER will be P e q = 1, ∀q ∈ Q i since Q i = ∅ (no path from the RS i to the BS) and thus the first term in the utility will be 0 and no RS can improve its utility by disconnecting a link. In other words, a disconnection by any RS will drastically decrease its utility. Therefore, any graph G formed using the proposed game will be a connected graph where all the RSs can communicate through the BS. Moreover, due to the high disconnection cost, if a RS is unable to find any partner willing to accept forming a link with it, it will connect to the BS through direct transmission. Thus, our network initially starts with all the RSs connected to the BS, before engaging in the network formation game.

As expressed in (1) in the case where a relay is connected to the BS through multiple paths the traffic will be split along these paths. However, after careful inspection of (1), we have the following properties Property 2: In the proposed network formation game, each RS i will only have one path q 0 ∈ Q i to the BS, thus |Q i | = 1 ∀i and no RS has incentive to form redundant links. As a result, the utility of a RS i reduces to

U i (G) = (T i + 1) • (1 -P e q0 ) L + R i -C(L i ). (6)
Proof: By inspecting the first term in the utility of (1), we note that each RS i can improve its utility by directing all of its traffic on the path q 0 = {i, i 2 , . . . , i BS } ∈ Q i exhibiting the lowest BER. The RS can choose to break all the paths, and keep only q 0 , since relaying more packets will not incur extra costs on the accepting RS i 2 because i 2 has already paid the maintenance cost for its connection with i regardless of the traffic that i will deliver (recall that the maintenance cost C(L i ) is a function of the number of RS links and not the amount of traffic). Consequently, RS i benefits by delivering all of its packets to RS i 2 which provides the smallest BER. Thus, no RS has any incentive to form redundant links and it is easily seen that in this case (1) reduces to [START_REF] Yu | Planning base station and relay station locations in IEEE 802.16j multi-hop relay networks[END_REF].

Property 3: Any network graph G resulting from a network dynamics algorithm applied to our network formation game will be a connected tree rooted at the BS.

Proof: This is an immediate consequence of properties 1 and 2. As no RS has the incentive to disconnect from the BS nor to form more than one path to the BS, the final graph resulting from any network dynamics in our game will be a connected tree rooted at the BS. As a result of these properties, every new link established by a RS i implicitly implies that RS i broke its previous link. Moreover, any network formation dynamics will converge to a tree topology as required by the 802.16j standard. Furthermore, we inspect the possible actions or strategies that each RS can take in the proposed game. The strategy space of each RS i consists of the RSs that i wants to connect to (the links that allow i to improve its BER) as well as the links already accepted by i (links directed towards i). Therefore, the strategy of a RS i is to select the link that it wants to form from the available RSs (or the BS) as well as to select which already accepted links should be maintained. We note that, a RS i cannot connect to a RS j which is already connected to i, in the sense that if ji ∈ G, then ij / ∈ G. Formally, denote A i = {ji|j ∈ V -{i}} as the set of links that RS i accepted from other RSs and B i = {ij|j ∈ (V BS)/({i} A i )} as the set of nodes (RSs or the BS) with whom i wants to connect (note that i cannot connect to RSs that are already connected to it, i.e., RSs in A i .). In consequence, each strategy s i of a RS i consists of the pair

s i = (a i , b i ) ∈ S i = 2 Ai ×B i ,
where 2 Ai is the set of all subsets of A i , a i ∈ 2 Ai are the accepted links that i wants to maintain, i.e., the links in the set A i /a i will be broken by RS i and b i ∈ B i is the node with whom i wants to be connected. Note that a RS can only be connected to one other node in our game so selecting to form a link with b i through strategy s i = (a i , b i ) implicitly implies that RS i will replace its previously connected link (if any) with the new link ib i . Finally, analogous to the terminology in [START_REF] Derks | Local dynamics in network formation[END_REF], we refer to all the strategies s i ∈ S i as local strategies.

Moreover, forming the directed link ib i through a local strategy s i requires the consent of the accepting node b i ∈ B i .

Therefore, RS i does not have the freedom to choose all the possible strategies in the strategy space S i and thus the following definition is required Definition 2: A local strategy s i = (a i , b i ) ∈ S i is a feasible local strategy for a RS i ∈ V if and only if b i is willing to accept a link from RS i. Denote F i ⊆ S i as the set of feasible local strategies.

Denote G si,s-i as the graph G formed when RS i plays a feasible local strategy s i ∈ F i while all other RSs maintain their vector of strategies s -i = [s 1 , . . . , s i-1 , s i+1 , . . . , s M ]. We define the local best response for a RS as follows [START_REF] Derks | Local dynamics in network formation[END_REF].

Definition 3: A feasible local strategy s * i ∈ F i is a local best response for a RS i ∈ V if U i (G s * i ,s-i ) ≥ U i (G si,s-i ), ∀s i ∈ F i .
Thus, the local best response for a RS i is to make the selection of links that maximizes its utility given that the other RSs maintain their vector of strategies.

B. Dynamics of network formation

By using the different properties of the RS network formation game, we propose a dynamics algorithm that allows a distributed formation of the network graph. The proposed dynamics assume that each RS is myopic, in the sense that the RSs aim at improving their payoff considering only the current state of the network without taking into account the future evolution of the network. Several models for myopic dynamics have been considered in the network formation literature for directed and undirected graphs [START_REF] Jackson | The evolution of social and economic networks[END_REF][START_REF] Demange | Group formation in economics: networks, clubs and coalitions[END_REF][START_REF] Johari | A contract based model for directed network formation[END_REF][START_REF] Derks | Local dynamics in network formation[END_REF]. In this paper, we propose a myopic dynamics algorithm inspired from [START_REF] Jackson | The evolution of social and economic networks[END_REF] and [START_REF] Derks | Local dynamics in network formation[END_REF]. The proposed algorithm is composed of several rounds where each round mainly consist of two phases: a fair prioritization phase and a dynamics phase. In the fair prioritization phase, we propose a priority function that assigns a priority to each RS. In the dynamics phase, by increasing priority, each RS chooses to play one of its feasible local strategies.

Therefore, each round of the proposed algorithm begins with the fair prioritization phase where each RS is assigned a priority depending on its actual perceived BER: RSs with a higher BER are assigned a higher priority. The motivation behind this procedure is to fairly allow RSs that are perceiving a bad channel to possess an advantage in selecting their partners; for the purpose of improving their BER. Thus, the RSs experiencing a high BER can select their partners out of a larger space of feasible strategies during the dynamics phase. Following prioritization, the RSs start selecting their strategies sequentially. For any strategy s i = (a i , b i ) ∈ S i that RS i intends to choose, node b i approves to form ib i only if it is able to improve its utility by either adding ib i or replacing one or more of its already accepted links in A bi by ib i . Replacing implies that node b i will break one or more of its already accepted links and replace them with ib i if this will improve its utility. Taking these conditions into account, each RS i chooses to play its local best response s * i ∈ F i (which is a feasible strategy) in order to maximize its utility at each round. In summary, during the dynamics phase, RSs select their local best responses which maximize the utility while taking into account the approval of the accepting nodes in the strategy. Multiple rounds consisting of the above two phases will be run until convergence to the final tree structure G † where The RSs take action sequentially by priority. Each RS i plays its local best response s * i = (a * i , b * i ) : a) RS i selects to maintain the subset a * i ⊆ A i of accepted links, improving its utility by breaking the links in the RSs can no longer improve their utility through local best responses. The proposed algorithm is summarized in Table I. The stability of the final graph G † is given using the following concept [START_REF] Derks | Local dynamics in network formation[END_REF] Definition 4: A network graph G in which no node i can improve its utility by a unilateral change in its local feasible strategy s i ∈ F i is a local Nash network. Alternatively to the above definition, a local Nash network is a network where the links chosen by each node are the local best responses. The local Nash network is thus a network where the nodes are in a Nash equilibrium with no node able to improve its utility by unilaterally changing its current local strategy. When our dynamics converge, we have Lemma 1: The final tree structure G † resulting from the proposed dynamics is a local Nash network.

A i /a * i . b) RS i requests to form the link ib * i with node b * i ∈ B i . b.1) If b * i is a RS, it
Proof: In each round of the proposed algorithm, each RS selects the local best response that maximizes its utility in this round. The proposed algorithm converges when no individual RS i can improve its utility by unilaterally changing its strategy s i . Thus, at the convergence, the RSs are in a Nash equilibrium resulting from playing the local best responses and the final tree structure G † resulting from the proposed dynamics is a local Nash network. The proposed algorithm can be implemented in a distributed manner. For choosing the local best response s * i = (a * i , b * i ), each RS can locally assess its current contracts and choose the subset a i that it wants to maintain while breaking the rest. In addition, each RS can easily survey neighboring RSs and acquire the BER that each neighbor can provide. As a result, each RS can take an individual decision to select the node b * i that can maximize its utility; without relying on any centralized entity. The signaling required for gathering this information can be minimal as each RS can easily measure its current channel towards the BS and feed it back to the neighboring RSs. Finally, in order to allow the RSs to adapt to mobility as well as to the presence of MSs; the proposed algorithm will periodically run, allowing the RSs to self-organize and cope with these environmental changes. Broken by 3

Broken by 4

Fig. 3. Snapshot of a tree topology formed using the proposed algorithm with 10 RSs before and after the deployment of 5 MSs.

IV. SIMULATION RESULTS AND ANALYSIS

For simulations, we consider a square area of 2 km × 2 km with the BS at the center. We deploy the RSs and the MSs within this area. The transmit power is P = 0.01 W, and the noise level is -110 dBm. The propagation loss is α = 3 and the packet length is K = 128 bits. The maximum number of RS connections per RS i is λ i = 5, ∀i ∈ V and the pricing parameter c i = 10, ∀i ∈ V .

In Fig. 3 we randomly deploy M = 10 RSs within the BS area and all these RSs start by connecting directly to the BS. As a first step, we run the proposed algorithm prior to the presence of any MS in the network (the case where each RS has only 1 HELLO packet and T i = 0 ∀i) and the final local Nash structure that forms in this step is shown in the figure by the solid arrows between the RSs. Moreover, through this figure we can clearly see how the proposed algorithm proceeds before any MS enters the network. For example, RS 4 connects itself directly to the BS although it is closer to RS 6. This is due to the fact that the priority of RS 4 is lower than that of RSs 3 and 7, thus the bidding turn of RS 4 on the resources of RS 6 follows that of 3 and 7. As a result, when RS 4 bids to connect to RS 6; the latter had already accepted two links from RSs 3 and 7 and will not accept a third unless this third can satisfy the minimum requirement of 3 packets (Fig. 2). However, RS 4 cannot satisfy this bid and thus, it remains connected to the BS since it is unable to find any other alternative to improve its utility. This example shows how the initial tree forms through our dynamics.

After the initial tree structure is formed, 5 MSs having 5 packets each are randomly deployed as shown in Fig. 3 (each MS connects to the closest RS). Once this additional traffic enters the network, the RSs can self-organize and modify the topology in order to efficiently cope with the incoming traffic. The changes in the topology are shown with labels (broken links) and dashed lines (newly formed links) in Fig. 3. For instance, RSs 2 and 4 are able to break their existing connection with the BS and improve their QoS by connecting to RSs 8 and 6 respectively. Prior to the presence of the MS traffic on RSs 2 and 4, they could not satisfy the minimum required packets for connecting to RSs 8 and 6 respectively. Moreover, we note that RS 3 is also able to improve its utility by breaking its contract with 6 and connecting to RS 7. In a nutshell, Fig. 3 summarizes the operation of the proposed dynamics algorithm with and without the presence of external MS data traffic.

Furthermore, we assess the effect of mobility on the network structure. We consider the network of Fig. 3 prior to the deployment of the MSs and we assume that RS 7 is moving upwards on the positive y-axis while the other RSs remain fixed. The changes in utility of the concerned RSs during the movement of RS 7 are shown in Fig. 4. As RS 7 moves upwards; it gets closer to the BS and starts by improving its utility. As it moves around 0.3 km; RS 7 distances itself from RS 6 and thus its utility starts to drop. As it moves around 1 km, RS 7 is able to improve its utility by disconnecting the link with RS 6 and connecting to RS 7. We note that when RS 7 splits from 6; the utility of RS 6 drops while that of RS 1 improves due to the additional packets for relaying provided by RS 7. Through these results, the operation of the algorithm in the presence of mobile RSs is illustrated.

Finally, we inspect the average overall network's PSR achieved at the BS by all the MSs. We compare the performance with the case with no RSs and the case where the RSs are directly connected to the BS (no tree). We randomly deploy two classes of MSs with equal probability, a first class representing medium traffic with 5 packets per MS and a second class representing heavy traffic with 10 packets per MS. The results are averaged over random positions of the MSs and the RSs and are shown in Fig. 5 for different numbers of MSs and RSs. In this figure, as the number of MSs increases, for all the schemes, the PSR increases and then stabilizes to a constant maximum. Furthermore, as the number of RSs increases, the performance advantage of our algorithm, in terms of PSR, increases significantly at all network loads. The proposed algorithm presents, respectively, an overall PSR improvement up to 17.5% and 15.6% over the schemes without RSs and with direct RS-BS connection.

V. CONCLUSIONS This paper proposed a novel distributed approach to the uplink tree formation problem in 802.16j networks through a network formation game model. In the proposed game, the RSs engage in pairwise negotiations for forming directed links that result in a final tree structure rooted at the BS. The proposed model accounts for the PSR gains from cooperative decode-andforward transmission as well as the costs for link maintenance. For modeling the interactions between the RSs, a distributed myopic dynamics algorithm is derived. The algorithm enables the RSs to maximize their utility while forming a local Nash network. Through simulations, we showed how the RSs are able to autonomously self-organize, adapting the topology to environment changes due to mobility and heterogeneous traffic while improving the overall network's PSR.

Fig. 1 .

 1 Fig. 1. Example of the uplink tree model.

  incident links L i on RS i Minimum bid

Fig. 4 .

 4 Fig.4. Self-adaptation of the network's tree topology to mobility shown through the variation of the utility of RS 7 as it moves upwards on the y-axis.

Fig. 5 .

 5 Fig. 5. Total PSR at the BS for different number of RSs and MSs.

TABLE I PROPOSED

 I NETWORK FORMATION DYNAMICS ALGORITHM Initial State All the RSs start by directly connecting to the BS. Two phases in each round of the dynamics Phase 1 -Fair Prioritization: Prioritize the RSs from the highest to the lowest current BER. Phase 2 -Dynamics:

  accepts to form ib * i through add or replace (s * i is a feasible strategy, see definitions 2 and 3). i-b * i adds ib * i if doing so improves it utility or ii-b * i replaces one ore more of its current links with ib * i if doing so improves it utility. b.2) If b * i is the BS, it accepts to form ib * i through add. Multiple rounds are run until convergence to the final local Nash tree G † where no RS can improve its utility by a unilateral change of strategy.