Axel Barrau

Silvère Bonnabel

Stochastic observers on Lie groups: a tutorial

In this tutorial paper, we discuss the design of geometric observers on Lie groups in the presence of noise. First we review Lie groups, and the mathematical definition of noises on Lie groups, both in discrete and continuous time. In particular, we discuss the Itô-Stratonovich dilemma. Then, we review the recently introduced notion of group affine systems on Lie groups. For those systems, we discuss how using the machinery of Harris chains, (almost) globally convergent deterministic observers might be shown to possess stochastic properties in the presence of noise. We also discuss the design of (invariant) extended Kalman filters (IEKF), and we recall the main result, i.e., the Riccati equation computed by the filter to tune its gains has the remarkable property that the Jacobians (A,C) with respect to the system's dynamics and output map are independent of the followed trajectory, whereas the noise covariance matrices that appear in the Riccati equation may depend on the followed trajectory. Owing to this partial independence, some local deterministic convergence properties of the IEKF for group-affine systems on Lie groups may be proved under standard observability conditions.

I. INTRODUCTION

Over the past decade, the design of observers on Lie groups has been a vibrant research topic, see [START_REF] Bonnabel | Non-linear symmetrypreserving observers on Lie groups[END_REF], [START_REF] Mahony | Nonlinear attitude observers on so (3) for complementary and compatible measurements: A theoretical study[END_REF], [START_REF] Lagemann | Gradient-Like Observers for Invariant Dynamics on a Lie group[END_REF], [START_REF] Izadi | Rigid body attitude estimation based on the Lagrange-dAlembert principle[END_REF], [START_REF] Hua | Stability analysis of velocityaided attitude observers for accelerated vehicles[END_REF], [START_REF] Zlotnik | Gradient-based observer for simultaneous localization and mapping[END_REF], to cite a few. In the presence of noise, observer design is generally referred to as a "filtering problem". Several approaches to filtering for systems possessing a geometric structure have been historically developed. For stochastic processes on Riemannian manifolds [START_REF] Itô | Stochastic differential equations in a differentiable manifold[END_REF] some results have been derived, see e.g., [START_REF] Ng | Nonlinear filtering in Riemannian manifolds[END_REF]. The specific situation where the process evolves in a vector space but the observations belong to a manifold has also been considered, see e.g. [START_REF] Duncan | Some filtering results in Riemann manifolds[END_REF], [START_REF] Pontier | Filtering on manifolds[END_REF] and more recently [START_REF] Said | On filtering with observation in a manifold: Reduction to a classical filtering problem[END_REF]. For systems on Lie groups harmonic analysis has been used [START_REF] Willsky | Dynamical Systems Defined on Groups: Structural Properties and Estimation[END_REF], [START_REF] Willsky | Some estimation problems on Lie groups[END_REF], notably in the case of bilinear systems [START_REF] Willsky | Estimation for bilinear stochastic systems[END_REF] and estimation of a Brownian motion [START_REF] Duncan | An estimation problem in compact Lie groups[END_REF].

Whereas this paper is concerned with the stochastic approach, an alternative stream of research consists of geometric deterministic approaches that do account for uncertainty, by solving a least squares (i.e., minimal energy) problem on the Lie group, see [START_REF] Han | Least squares tracking on the Euclidean group. Automatic Control[END_REF], [START_REF] Zamani | Minimum-energy filtering for attitude estimation[END_REF]. Minimal energy filtering on groups compares favorably to state-of-the art, see e.g., [START_REF] Berger | Second Order Minimum Energy Filtering on SE(3) with Nonlinear Measurement Equations[END_REF]. Note that, they are related to optimal control theory where geometric methods have long played an important role [START_REF] Brockett | Lie algebras and Lie groups in control theory[END_REF]. S. Bonnabel is with MINES ParisTech, PSL Reasearch University, Centre for Robotics, 60 bd Saint-Michel, 75006 Paris, France.

silvere.bonnabel@mines-paristech.fr.

A. Barrau is with SAFRAN TECH, Groupe Safran, Rue des Jeunes Bois -Chateaufort, 78772 Magny Les Hameaux CEDEX, France, axel.barrau@safrangroup.com.

II. PRIMER ON LIE GROUPS

For a tutorial and robotics oriented introduction to matrix Lie groups, see [START_REF] Barfoot | State Estimation for Robotics[END_REF], chapter 7. For a more mathematical and differential geometry based treatment, see [START_REF] Helgason | Differential Geometry, Lie Groups and Symmetric Spaces Academic[END_REF].

Matrix Lie group: In this paper, we will only consider matrix Lie groups, although the results remain valid for general Lie groups. Indeed, matrix Lie groups provide a more concrete picture to the unfamiliar reader. A matrix Lie group G is subgroup of GL N (R) (invertible square N × N matrices) and an embedded manifold of R N×N . The first condition means G is a subset of GL N (R) containing identity (I N ∈ G) and stable by multiplication and inversion: for χ 1 , χ 2 matrices of G, we have χ 1 χ 2 ∈ G, and χ -1 1 ∈ G. The second condition means that an affine subspace χ + T χ G "tangent to G at χ" can be defined for any point χ ∈ G as on Figure 1 (the base "point" χ being a matrix and T χ G a sub-vector space of R N×N ). The vector space T χ G is called "tangent space at χ". The dimension of this space, independent of the chosen point χ, is the dimension

d of G. One of the most basic examples is SO(3) = {R ∈ R 3×3 | det R = 1, R T R = I 3 } where I 3 denotes the identity matrix of R 3×3 . SO(3) is a 3 dimensional Lie group, that is, d = 3 and N = 3.
Lie algebra: The identity matrix I N ∈ G is the neutral element for the group composition. The tangent space T χ G ∈ R N×N mentioned avove, taken at χ = I N , can be defined as the vector space spanned by all initial velocity vectors d dt γ(0) for curves γ(t), that start at γ(0) = I N and entirely lie in G, see Figure 1, left plot. The tangent space T I N G is called the Lie algebra of G, and is denoted by g, i.e.,

T I N G := g ⊂ R N×N . It is a vector subspace of R N×N , having dimension d < N 2 .
Identification of the Lie algebra with R d : g being a ddimensional vector subspace of R N×N , identifying it to the vector space R d makes all computations easier. A map, R d → g filling this task 1 will be denoted by ξ → ξ ∧ . Thus ξ ∈ R d is a vector, and ξ ∧ ∈ R N×N is a matrix. This is illustrated on Figure 1, right plot. We will denote the inverse of ∧ by ∨ , that is (ξ ∧ ) ∨ = ξ .

Exponential map: There is a natural map between g and G, based on the matrix exponential exp m . As g can be identified to R d , we also have a local parameterization of G in the neighborhood of I N by vectors of R d : ξ → exp m (ξ ∧ ) which proves very useful in practice. In the remainder of the paper, we will define and refer to the exponential map exp : R d → G as the map defined by exp(ξ ) := exp m (ξ ∧ ). Using a first order Taylor expansion of the matrix exponential, we obtain the local approximation exp(ξ

) = I N + ξ ∧ + O(||ξ || 2 ) in R N×N . Alternatively, exp(ξ ) is the solution at time t = 1 to d dt χ t = χ t ξ ∧ , for χ 0 = I N . It defines a diffeomorphism from R d to G, invertible at least in an open subset of R d containing 0. Its local inverse is called the Lie logarithm log χ.
Linearization on groups: Similarly, the tangent space T χ G at arbitrary χ ∈ G can be identified to R d as multiplication by χ transports T I N G to T χ G. Indeed, T χ G = χg = gχ. This means vectors of T χ G can be written as χξ ∧ with ξ ∈ R d , or ( ξ ∧ )χ with a different ξ = ξ (see Figure 1, center plot), but we will privilege left multiplications, for exposition purposes. To linearize a function h : G → R p , at an arbitrary point χ ∈ G, we can evaluate how it changes by infinitesimally following an arbitrary tangent vector χξ ∧ at χ. The left linear approximation to h : G → R p at χ in the direction ξ ∈ R d can then be defined as the matrix

H ∈ R p×d such that h(χ exp(ξ ))-h(χ) = Hξ +O(||ξ || 2 ), that is, Hξ = d ds h(χ exp(sξ )) | s=0 .
It is usually called the left-trivialized tangent map. If h is defined for any matrix M ∈ R N×N , with differential Dh χ : R N×N → R p , the first order approximation of the exponential above thus yields Hξ = Dh χ (χξ ∧ ) . One must then bear in mind that infinitesimal shifts at any χ ∈ G are thus always represented by elements of R d .

Adjoint representation: The operator Ad χ , encoded by a matrix of R d×d , is called the adjoint representation of the Lie group G, and is defined by (Ad χ ξ ) ∧ := χ(ξ ∧ )χ -1 . We have the useful relation χ exp(ξ ) = exp(Ad χ ξ )χ.

III. NOISY DYNAMICS ON GROUPS

Dynamical systems on a matrix Lie group G are easily defined. However, to account for dispersion under the effect of noise, the usual method that resorts to additive Gaussian white noise in the Euclidean setting does not directly carry over to Lie groups, as G is not a vector space.

A. Discrete time noisy dynamics

Consider a system evolving on G in discrete time:

χ t+1 = f (χ t ), with f : G → G. (1)
Suppose we want to add a centered d-dimensional Gaussian noise ξ ∼ N (0, Q) to the dynamics, to reflect uncertainties in the evolution model. As f (χ t ) ∈ G, standard addition f (χ t ) + ξ / ∈ G does not make sense: first we must find a group counterpart to ξ ∈ R d , and then "add" it to f (χ t ).

"Gaussian" noise on G: A natural counterpart to ξ ∼ N (0, Q) on G is easily obtained defining W = exp(ξ ) ∈ G as a random element of G, as largely advocated in [START_REF] Bourmaud | Discrete extended Kalman filter on Lie groups[END_REF], [START_REF] Barfoot | Associating uncertainty with threedimensional poses for use in estimation problems[END_REF], [START_REF] Barfoot | State Estimation for Robotics[END_REF]. The law of W is often referred to as wrapped normal distribution. See also [START_REF] Chirikjian | Stochastic Models, Information Theory, and Lie Groups[END_REF] for a slightly different definition.

"Adding" noise on G: Now that we have a notion of "centered" random "Gaussian" variable exp(ξ ) on G, we need to apply it to f (χ t ) to model dispersion with respect to the deterministic dynamics (1). To do so, standard addition may be replaced with group multiplication. Depending on the choice of left or right multiplication, this yields two alternative noisy dynamics

χ t+1 = f (χ t ) exp(ξ ) with ξ ∼ N (0, Q) (2) or χ t+1 = exp(ξ ) f (χ t ) with ξ ∼ N (0, Q) (3)
"Isotropic" noise: As χ exp(ξ ) = exp(Ad χ ξ )χ, we speak of "isotropic" (or Ad-invariant or bi-invariant) noise ξ ∼ N (0, Q) if for all χ ∈ G we have Ad χ QAd χ = Q. In this case both dynamics ( 2) and ( 3) define processes having identical probability distributions for noise-free f (χ t ).

B. Continuous time noisy dynamics

Consider a system evolving on G in continuous time:

d dt χ t = f (χ t ) (4)
with f : G → T χ t G, such that d dt χ t is a tangent vector to G at χ t , see Figure 1, central plot.

Suppose we want to add a centered d-dimensional white noise with covariance Q to the dynamics, to reflect some uncertainties in the evolution model. As the tangent space T χ t G is a vector space, and as χ(w ∧ ) ∈ T χ G for any vector w ∈ R d , a mere addition might work, that is,

d dt χ t = f (χ t ) + χ t (w ∧ t ) ∈ T χ t G (5)
where we let w t be a continuous centered white noise in R d with covariance matrix Q. Note that, here again, we could have instead added a term of the form ( w∧ t )χ t , as the latter is also an element of T χ t G. Owing to the definition of Ad χ , we see that if wt = Ad χ t w t then both equations are identical. As a result, we only need consider [START_REF] Barrau | An EKF-SLAM algorithm with consistency properties[END_REF], at least at this stage.

The problem is that ( 5) is a stochastic differential equation (SDE) on G, since it contains the stochastic term χ t (w ∧ t ), and it should be given a proper mathematical meaning. It turns out that, adding stochastic terms to ordinary differential equations generates some (apparently inevitable) mathematical issues whereas adding uncertainty is relatively straightforward in the discrete time case. This prompts the following paragraphs, that are meant to be a gentle, but rather mathematically loose, introduction to the subject.

C. Stochastic differential equations in R d

For a physical introduction to stochastic differential equations (SDE) see [START_REF] Van Kampen | Stochastic processes in physics and chemistry[END_REF]. Consider a stochastic differential equation (SDE) in R d of the form:

d dt x t = g(x t ) + wt ( 6
)
where wt is a continuous centered white noise in R d with covariance matrix Q. It can be re-written as:

d dt x t = g(x t ) + Q 1/2 w t (7)
with w t a white noise with identity covariance matrix I d .

White noise: The noise w t cannot be mathematically defined as a a random function of time t, only its integral (the noise cumulated over a time interval) is: for all t 1 ,t 2 ≥ 0 we have t 2 t 1 w s ds = W t 2 -W t 1 , with W t a d-dimensional Wiener process, also known as d-dimensional Brownian motion (and the white noise w t can be interpreted as its time derivative). The Wiener process or Brownian motion is a well-known stochastic process, characterized by the fact that it is continuous, centered, with statistically independent increments and such that W t+∆t -W t ∼ √ ∆tN (0, I d ). Discretization scheme: Eq. ( 7) can thus be given a proper mathematical meaning through its integral counterpart, that is, the well-defined equation (W t is a d-Wiener process):

x t = x 0 + t 0 g(x s )ds + Q 1/2 W t . (8)
We can then define a solution to SDE (7) as any (x t ) t≥0 that satisfies the integral equation ( 8). Moreover we can write the increment x tx 0 as the sum of all the variations over intervals of length ∆t, that is, ∑

(t/∆ t ) i=0 [x (i+1)∆t -x i∆t ]. Using in (8) that (i+1)∆t i∆t g(x s )ds = g(x i∆t )∆t + O(∆t 2 )
, and owing to the property of the Wiener process above, we have thus

x t -x 0 = lim ∆t→0 (t/∆ t ) ∑ i=0 [g(x i∆t )∆t + √ ∆tQ 1/2 ξ i ]
in distribution, where the ξ i ∼ N (0, I d ) are i.i.d standard Gaussians. More prosaically (and quite loosely speaking) it means that the solution to the differential equation [START_REF] Barrau | Invariant Kalman Filtering[END_REF], and thus to [START_REF] Barrau | The invariant extended Kalman filter as a stable observer[END_REF], may be defined as the limiting process as ∆t → 0 of the following (Euler-Maruyama) discretization method;

x t+∆t = x t + ∆tg(x t ) + √ ∆tξ with the ξ s i.i.d Gaussians with distribution N (0, Q). Mathematical problems arise, though, with equation

d dt x t = g(x t ) + r(x t )w t (9)
where r : R d → R d×d an arbitrary function of x t . There are then two ways to cope with the multiplicative term r(x t ).

Itô's approach: Roughly speaking, it consists in defining the solution to (9) as the limit as ∆t → 0 of the following (Euler-Maruyama) discretization method

x t+∆t = x t + ∆tg(x t ) + √ ∆t r(x t )ξ (10)
with the ξ s i.i.d Gaussians with distribution N (0, Q).

Stratonovich's approach: Roughly speaking, it consists, in contrast, in defining the solution to (9) as the limit as ∆t → 0 of the following discretization method

x t+∆t = x t + ∆tg(x t ) + √ ∆t r ((x t + x t+∆t )/2) ξ
with the ξ s i.i.d Gaussians with distribution N (0, Q).

Although Itô's approach seems more natural, as it leads to an explicit integration scheme instead of an implicit one, Stratonovich's approach has the merit to be compatible with chain's rule, i.e., if F is any smooth function, and x t is the solution to [START_REF] Bonnabel | Non-linear symmetrypreserving observers on Lie groups[END_REF] in the sense of Stratonovich, then z t = F(x t ) is the solution in the sense of Stratonovich to equation d dt z t = DF(x t ) g(x t ) + r(x t )w t . Unfortunately, this is not true as concerns the solution to [START_REF] Bonnabel | Non-linear symmetrypreserving observers on Lie groups[END_REF] in the sense of Itô.

D. Stochastic differential equations (SDE) on Lie groups

Hence, there are two ways to interpret the stochastic term χ t w ∧ t of ( 5). The first one is Itô's intepretation of SDE [START_REF] Barrau | An EKF-SLAM algorithm with consistency properties[END_REF]. Roughly speaking, it means that the solution to the differential equation (5) corresponds to the limit as ∆t → 0 of the following (Euler-Maruyama) discretization method

χ t+∆t = χ t + ∆t f (χ t ) + √ ∆tχ t (ξ ∧ t ) (11)
with ξ 's independent Gaussians with distribution N (0, Q).

Stratonovich's interpretation leads instead to

χ t+∆t = χ t + ∆t f (χ t ) + √ ∆t (χ t + χ t+∆t ) 2 (ξ ∧ t ) (12)
The question is whether the limiting processes (χ t ) t≥0 of discretizations ( 11) and ( 12) as ∆t → 0 actually remain inside G at all times, or if we end up with matrices of the ambiant space R N×N that lie outside G. Itô vs. Stratonovich: It turns out that, only the Stratonovich approach guarantees that the solution (χ t ) t≥0 remains in G. Indeed, Stratonovich's approach is the only one that is compatible with the geometry. From Von Neumann's closed subgroup theorem, we know that any matrix Lie group G corresponds to a level set of a submersion F : R N×N → R N 2 . Thus, the the tangent space at χ is the set

T χ G = {v ∈ R N×N | DF(χ)v = 0}
. This implies that, if at all times d dt χ t = v t is a (possibly random) element of T χ t G then, and χ t is defined as the solution in the Stratonovich sense, we have d dt F(χ t ) = DF(χ t )( d dt χ t ) since Stratonovich's stochastic calculus is compatible with the chain rule, and thus d dt F(χ t ) = 0 at all times; so that x t remains in G. As an exemple, we may choose F(χ) = (χ T χ, det χ), and matrices of SO(3) correspond to the level set F(χ) = I 3 , det(χ) = 1. For more details, see Section 20.4 of [START_REF] Chirikjian | Stochastic Models, Information Theory, and Lie Groups[END_REF].

With Itô's approach, the solution unfortunately steps out of the group almost surely, see e.g. [START_REF] Barrau | Intrinsic filtering on SO (3) with discretetime observations[END_REF].

Implementation of SDE on Lie groups: Another route is as follows. Note that, f (χ t ) ∈ T χ t G and thus it is of the form f (χ t ) = χ t (ω ∧ t ) where ω ∧ t ∈ g, and where ω t ∈ R d is defined as

ω t = [χ -1 t f (χ t )] ∨ . With this notation, Equation (5) then becomes d dt χ t = χ t (ω t + w t ) ∧ . (13)
As ω t + w t ∈ R d , one could be tempted to discretize this equation using a group multiplicative counterpart of Itô's approach [START_REF] Bonnabel | Left-invariant extended Kalman filter and attitude estimation[END_REF], that is, using i.i.d. Gaussians ξ ∼ N (0, Q):

χ t+∆t = χ t exp m (∆t(ω t ) ∧ + √ ∆t(ξ ∧ )) = χ t exp(∆tω t + √ ∆tξ ), (14)
and the limiting process as the discretization step ∆t → 0 may serve as a direct definition for the solution of (10) on G. Indeed, we readily see the scheme ( 14) defines a stochastic process that does remain in G at all times, since ∆t(ω t ) ∧ + √ ∆t(ξ ∧ ) ∈ T I N G = g, so that exp m (∆t(ω t ) ∧ + √ ∆t(w ∧ t )) ∈ G. Moreover, it reminds much of the discrete time case of Section III-A. It turns out this is a valid route indeed, owing to results by McKean [START_REF] Mckean | Stochastic integrals[END_REF] and related to his multiplicative stochastic integral, and more remotely to Brownian motion on Lie groups, [START_REF] Perrin | Étude mathématique du mouvement brownien de rotation[END_REF], [START_REF] Itô | Stochastic differential equations in a differentiable manifold[END_REF], [START_REF] Yosida | On brownian motion in a homogeneous riemannian space[END_REF].

Proposition 1 ( [START_REF] Mckean | Stochastic integrals[END_REF], see also [START_REF] Chirikjian | Stochastic Models, Information Theory, and Lie Groups[END_REF]): The discretized solution of the multiplicative scheme [START_REF] Crassidis | Survey of nonlinear attitude estimation methods[END_REF] converges in probability to the solution in the sense of Stratonovich to [START_REF] Chirikjian | Stochastic Models, Information Theory, and Lie Groups[END_REF] and thus to the solution to SDE [START_REF] Barrau | An EKF-SLAM algorithm with consistency properties[END_REF].

Corollary 1: Discretization ( 14) thus serves as an explicit convergent implementation scheme with time step ∆t of the EDS (13) and thus [START_REF] Barrau | An EKF-SLAM algorithm with consistency properties[END_REF], that guarantees the solution remains in the group G at all times, regardless of the chosen step ∆t.

Numerical schemes: A wide variety of powerful methods exist and the reader is referred to e.g., Runge-Kutta-Munthe-Kaas (RKMK) methods [START_REF] Munthe-Kaas | High order Runge-Kutta methods on manifolds[END_REF] and more generally geometric numerical integration [START_REF] Hairer | Geometric numerical integration: structure-preserving algorithms for ordinary differential equations[END_REF], [START_REF] Persson | Sharf Invariant trapezoidal Kalman filter for application to attitude estimation[END_REF].

IV. STOCHASTIC OBSERVERS ON LIE GROUPS

A. Considered stochastic observer problem

On the matrix Lie group G ⊂ R N×N , we consider continuous time (not necessarily invariant) dynamics of the form

d dt f u t (χ t ) (15)
here f u t : G → T χ t G. This echoes (4), except that to be more relevant to applications we allow f to also depend on a timevarying input t → u t , where u t ∈ U lives in some space U . To model possible uncertainties in the dynamics, noise must be added in the tangent space along the lines of Section III-B.

Stochastic dynamics: This yields the two noisy dynamics

d dt χ t = f u t (χ t ) + χ t (w ∧ t ) ∈ T χ t G (16)
d dt χ t = f u t (χ t ) + ( w∧ t )χ t ∈ T χ t G (17)
The choice between ( 16) and ( 17) is generally dictated by the application. In many applications, χ t represents the configuration of a vehicle in space, i.e., a transformation that maps the body (i.e., vehicle) frame to an earth fixed frame.

In this case when confronted with relations of the form

α = χ t β , α, β ∈ R N , χ t ∈ G
we generally say that β is a vector of the body frame, whereas α is a vector of the fixed frame. In the main applications, u t represents the measurements from motion sensors, such as accelerometers, gyrometers, and odometers, which are all attached to the body, and w t then represents sensor noise, and is thus also a vector of the body frame, so that ( 16) are the dynamics to consider. The typical example is when χ t = R t ∈ SO(3) denotes a rotation matrix, in which case u t ∈ R 3 denotes the (bias free) gyrometers measurements, and w t ∈ R 3 the gyrometers' noise, that models the (random) discrepancy between measured angular velocity and the true angular velocity. The dynamics then write

d dt R t = R t ((u t + w t ) ∧ ) = R t (u ∧ t ) + R t (w ∧ t ) indeed.
Measurement model: Suppose that there are noisy partial measurements of the state, available at discrete times t 0 < t 1 < t 2 • • • , and which write

Y n = h(χ t n ) +V n ( 18
)
with h : G → R p an output map. The stochastic observer problem consists in providing the best estimate of χ t given all past measurements Y 1 , • • • ,Y n where t n ≤ t < t n+1 .

B. Gaussian observers

The main application of the present Lie group based framework is designing EKF-like observers for systems without a proper vector space structure. In an EKF, the true state is modeled as x t = xt + e t , with e t a Gaussian error variable. A Lie group counterpart may be written as χ t = χt exp(e t ) with e t ∈ R d . Then, as in standard EKF, first-order expansion in e t is performed. The most convincing application is attitude estimation, where the roll-pitch-yaw parameterization is obviously unadapted to EKF design, notably because of singularities. Interestingly, it has been noticed since, at least, the 1970s that the most efficient implementations of EKF for this problem relied on linearizing a multiplicative error parameterized by a small rotation vector (or a quaternion equivalent). In other words, the Lie group approach was implicitly adopted from the beginning, and preferred to the roll-pitch-yaw vector parameterization. See [START_REF] Crassidis | Survey of nonlinear attitude estimation methods[END_REF] for a survey.

C. Invariant observers

Invariant observers on Lie groups, or more generally nonlinear observers on Lie groups, are estimators that notably ensure the estimate χt remains in the group G at all times. Referring to, e.g., [START_REF] Bonnabel | Non-linear symmetrypreserving observers on Lie groups[END_REF], [START_REF] Mahony | Nonlinear attitude observers on so (3) for complementary and compatible measurements: A theoretical study[END_REF], [START_REF] Lagemann | Gradient-Like Observers for Invariant Dynamics on a Lie group[END_REF], [START_REF] Izadi | Rigid body attitude estimation based on the Lagrange-dAlembert principle[END_REF], [START_REF] Hua | Stability analysis of velocityaided attitude observers for accelerated vehicles[END_REF], [START_REF] Zlotnik | Gradient-based observer for simultaneous localization and mapping[END_REF], they are continuous time and are generally of the form d dt χt = f u t ( χt ) + χt L(y(t)h(χ t )) ("left-invariant" observer), or alternatively of the form d dt χt = f u t ( χt )+L(y(t)-h(χ t )) χt ("right-invariant" observer), where y(t) is a continuous time output noise-free measurement and L : R p → g some nonlinear map to be tuned by the user. Note that, as χt L(y(t)h(χ t )) ∈ T χt G the estimates are garanteed to remain inside G. However, noisy discrete-time measurements of the form (18) are more easily defined that continuous-time noisy measurements. Moreover, in practice, measurements always come in discrete time. The continuous-discrete counterpart of nonlinear observers on Lie groups is of the form

d dt χt = f u t ( χt ), t n-1 ≤ t < t n (19)
χ+ t n = χt n exp(L n (Y n -h(χ t n ))), t = t n (20)
with L n : R p → R d a nonlinear map to be tuned by the user. Remark 1: The choice between left and right multiplication leads to two different families of observers. In [START_REF] Helgason | Differential Geometry, Lie Groups and Symmetric Spaces Academic[END_REF], we have opted for left multplication by χt n . However, right multiplications by χt n might prove suited to some applications. For more details, and guidelines see [START_REF] Barrau | The invariant extended Kalman filter as a stable observer[END_REF].

Step [START_REF] Hartley | Contact-Aided Invariant Extended Kalman Filtering for Legged Robot State Estimation[END_REF] is called the propagation step, and Step [START_REF] Helgason | Differential Geometry, Lie Groups and Symmetric Spaces Academic[END_REF] the update step. To evaluate the accuracy of the estimates, consider the error η t = χ -1 t χt in the sense of group multplication, between the estimate and the true state. An absence of error leads to η t = I N . Of course, due to noise it is not possible to have η t → I N , but one can try to minimize the dispersion of η t under the effect of noise.

D. Group affine systems

The Lie group formalism has been utilized for the ease of parametrization of the state space it provides, see Section IV-B. It has also lead to powerful nonlinear estimation methods: the literature being too broad to be covered see e.g., [START_REF] Barfoot | Associating uncertainty with threedimensional poses for use in estimation problems[END_REF], [START_REF] Izadi | Rigid body attitude estimation based on the Lagrange-dAlembert principle[END_REF], [START_REF] Lagemann | Gradient-Like Observers for Invariant Dynamics on a Lie group[END_REF]. In the next sections we will focus on specific systems for which the Lie group framework allows generalizing some properties of the linear case, as initiated in [START_REF] Bonnabel | Non-linear symmetrypreserving observers on Lie groups[END_REF].

Over the past decade, many convergence results have been made possible by the fact one was dealing with systems being left or right-invariant, as in [START_REF] Bonnabel | Non-linear symmetrypreserving observers on Lie groups[END_REF]. In [START_REF] Barrau | The invariant extended Kalman filter as a stable observer[END_REF], the following "group affine" property was shown to bring striking properties, and to be the proper framework generalizing linear systems:

∀u ∈ U , a, b ∈ G f u (ab) = a f u (b) + f u (a)b -a f u (Id)b. (21)
In this equation

f u (ab) ∈ T ab G, f u (a) ∈ T a G, f u (b) ∈ T b G.
For example the left-invariant dynamics d dt χ t = χ t ω t , the right-invariant ones d dt χ t = ω t χ t and the mixed-invariant ones d dt χ t = χ t ω

(1)

t + ω (2)
t χ t all are group-affine dynamics. However they are not limited to them: the usual navigation equations 2 on flat earth with an IMU consists of unbiased accelerometers and gyrometers are neither left nor right nor mixed-invariant, but they satisfy [START_REF] Hua | Stability analysis of velocityaided attitude observers for accelerated vehicles[END_REF] as proved in [START_REF] Barrau | The invariant extended Kalman filter as a stable observer[END_REF].

The fundamental assumption [START_REF] Hua | Stability analysis of velocityaided attitude observers for accelerated vehicles[END_REF] has been shown to be valid for a number of systems that revolve around navigation and simultaneous localization and mapping (SLAM) [START_REF] Barrau | An EKF-SLAM algorithm with consistency properties[END_REF]. It is yet possibly limiting: if, e.g., biases of accelerometers and gyrometers are added in the navigation example just mentioned, the system is not group-affine anymore. However, the obtained system is "close" to being group-affine, ensuring the success of geometric methods in practice, see [START_REF] Barrau | Invariant Kalman Filtering[END_REF], [START_REF] Hartley | Contact-Aided Invariant Extended Kalman Filtering for Legged Robot State Estimation[END_REF].

Fundamental property of invariant filtering: Consider two trajectories χ t , χt of the noise free system [START_REF] Duncan | An estimation problem in compact Lie groups[END_REF]. Let η t = χ -1 t χt ∈ G be the error between those two solutions in the sense of group multiplication. It is the group analog of the linear error χ t -χt , which does not make sense on the group G, since it is not a vector space. We have Theorem 1 ([6]): f u t satisfies Equation ( 21) if and only if there exists a map g u t such that d dt η t = g u t (η t ). Moreover, we have necessarily that g u t (η) = f u t (η)f u t (I N )η.

Corollary 2 (of Thm 1, see [START_REF] Barrau | The invariant extended Kalman filter as a stable observer[END_REF]): Consider ( 16), with f u t group-affine, and observer ( 19)- [START_REF] Helgason | Differential Geometry, Lie Groups and Symmetric Spaces Academic[END_REF]. During the propagation step, we have d dt η t = g u t (η t ) -(w ∧ t )η t , that is the evolution of the error does not depend explicitly on the trajectory χt .

d dt χ -1 t = -χ -1 t ( d dt χ t )χ -1 t . This yields d dt η t = χ -1 t [ f u t ( χt ) -f u t (χ t )η t ] -(w ∧ t )η t = f u t (η t ) -f u t (I N )η t -(w ∧ t )η t = g u t (η t ) -(w ∧ t )η t where we have used (21) that implies f ( χ) = f (χη) = χ f (η) + f (χ)η -χ f (I N )η.
The latter corollary ensures the error evolution during the propagation step is independent from the trajectory, and with slight abuse it is referred to as "autonomous error" evolution. Moreover, the group-affine property automatically implies g u t is linear under a suitable change of coordinates [START_REF] Barrau | The invariant extended Kalman filter as a stable observer[END_REF]. This property is referred to as "log-linearity" of the error equation.

E. Harris chains and gradient-like observers

The paper [START_REF] Lagemann | Gradient-Like Observers for Invariant Dynamics on a Lie group[END_REF] discusses systems on Lie groups having a synchrony property. In the present formalism this property means there exists input trajectories u t such that g u t (η) = 0 ∀η,t. In this case Eq. ( 24) defines a Brownian motion on G (i.e. a "random walk" on G), and if Ln (•) = K(•) is minus a gradient term that tends to make the output error Y nh( χt n ) decrease, inspiring from gradient-like observers [START_REF] Lagemann | Gradient-Like Observers for Invariant Dynamics on a Lie group[END_REF], then there are hopes that the distribution of the error η t will asymptotically converge to a stationary distribution, resorting to the machinery of Harris chains, as proved in [START_REF] Barrau | Intrinsic filtering on Lie groups with applications to attitude estimation[END_REF] for the SO(3) case, allowing optimal offline tuning of the gains w.r.t. the stationary error distribution.

F. Invariant extended Kalman filter (IEKF)

Suppose that, moreover, h(χ) is of the form h(χ) = χ d with d ∈ R N a vector. Resorting to the methodology of invariant extended Kalman filtering, originally introduced in [START_REF] Bonnabel | Left-invariant extended Kalman filter and attitude estimation[END_REF], the Left-invariant EKF (LIEKF) for continuous-discrete group affine systems with left-equivariant output writes [START_REF] Barrau | The invariant extended Kalman filter as a stable observer[END_REF]:

d dt χt = f u t (
η + t n = η t n exp(K n (η -1 t n d -d -χ-1 t n V n )), t = t n (25)
Using linearization on Lie groups discussed at Section II, the error system ( 24)-( 25) may be linearized around η = I N writing η = exp(ξ ). Let A t be defined by g u t (exp(ξ )) = (A t ξ ) ∧ + O(||ξ || 2 ) and C by exp(ξ ) Stochastic first-order optimality: as the conventional EKF, the IEKF is stochastically optimal for the linearized system around the estimate, with respect to chosen noises. This property is important in practice, but provides no guarantee regarding the nonlinear system. Yet, nonlinear guarantees exist for the IEKF in a deterministic setting.

Deterministic nonlinear convergence properties: Note that, owing to the group-affine property of f u t , the Jacobian A t is independent from χt , and so is C owing to the form of output assumed. This reminds much of the linear Kalman filter theory. The fact that covariance matrix Nn may depend on the estimates, impacts only mildly the stability of the error system. As a result, it could recently be proved in [START_REF] Barrau | The invariant extended Kalman filter as a stable observer[END_REF] that, when used as non-linear observer the IEKF enjoys local asymptotic convergence properties for all (observable) group-affine systems. This is a non-trivial result as there are few local convergence results for the conventional EKF, unless some impractical assumptions on the stability of the covariance matrix are made. see e.g., [START_REF] Song | The extended Kalman filter as a local asymptotic observer for nonlinear discrete-time systems[END_REF].

For comparisons of invariant EKF with other methods, the reader is referred to e.g., [START_REF] Barrau | Invariant Kalman Filtering[END_REF], [START_REF] Hartley | Contact-Aided Invariant Extended Kalman Filtering for Legged Robot State Estimation[END_REF], [START_REF] Barrau | An EKF-SLAM algorithm with consistency properties[END_REF].

Fig. 1 .

 1 Fig.1. Left and right multiplications offer two ways to identify the tangent space T χ G at χ with the tangent space at Identity T I N G, called the Lie algebra and denoted g. In turn, the application ξ → ξ ∧ provides a linear bijection between the Euclidean space R d and g.

  , d dt V t = g+R t u t with g the earth gravity vector, ω t , u t the gyro and accelero outputs, R t the orientation, P t the position and V t the velocity of the body that carries the IMU.

	Proof: We write d dt η t = ( d dt χ -1 t ) χt + χ -1 t ( d dt χt ) and then
	we use the general matrix equality

2 the equations then write

d dt R t = R t ω ∧ t d dt P t = V t

  χt ), t n-1 ≤ t < t n[START_REF] Itô | Stochastic differential equations in a differentiable manifold[END_REF] χ+ t n = χt n exp(K n ( χ-1 t n Y n -d)), t = t n(23)with K n ∈ R d×N a gain matrix to be defined in the sequel. Then, using Cor. 2 and elementary computations, we see the error η t = χ -1 t χt satisfies the error equation:d dt η t = g u t (η t ) -(w ∧ t )η t , t n-1 ≤ t < t n(24)

  -1 dd = Cξ the linearized error equation writes for ξ t = log(η t )d dt ξ t = A t ξ tw t , t n-1 ≤ t < t n(26)ξ + t n = ξ t n + K n (Cξ t n -Vn )), t = t n(27)where Vn = χ-1 t n V n and as in the EKF methodology the gain may be defined through a Riccati equationd dt P t = A t P t + P t A T t + Qt , P + t n = (I d -K n C)P t nwith S n = CP t n C T + Nn and K n = P t n C T S -1 where Q t = cov(w t ) and Nn = cov( Vn ).

Note that, specifying the map ∧ amounts in fact to choosing a basis of the Lie algebra.

ACKNOWLEDGMENTS

The authors thank Salem Said, for proofreading and advice, and Tarek Hamel and Robert Mahony for inviting them to participate in this tutorial session at CDC.


Israel Márquez Salinas

Renata Teixeira

Timur Friedman

Sara Ayoubi

Francesco Bronzino

Home Wi-Fi Impairments

The preferred method to access Internet from home is Wi-Fi. Unfortunately poorly placed Wi-Fi access point can experience Wi-Fi impairments such as interference or congestion, leading to degraded Internet performance. Identifying these impairments can be challenging, even for wireless experts. To approach this challenge we develop a tool to identify home Wi-Fi impairments. In our work we conduct experiments triggering wireless and non-wireless issues in a testbed. The two methods we work with are active probing and passive wireless metrics collection from wireless AP and wireless client. The wireless metrics we collect include but are not limited to, RSSI, PHY Rate, Noise, etc. With these metrics we get a sense of the status of home Wi-Fi and correlate it with our active probing results. Finally, to identify a wireless impairment we run our dataset through supervised learning algorithms. We obtain the best results with random forest algorithm. Random forest is well known for its precision to classify events based on a specific set of features. We close our paper by presenting the results of home Wi-Fi impairment detection by modeling it as a classification problem.

INTRODUCTION

The most common way to access Internet from home is Wi-Fi. The variety of services and devices using the home Wi-Fi to access Internet is vast. It is common today for a home user to stream a movie on his laptop while connected to the home Wi-Fi. In some cases, the movie streaming is degraded, which is frustrating for the users. One of the potential causes of poor streaming experience is the home Wi-Fi. In fact, previous work [START_REF] Sundaresan | Home network or access link? locating last-mile downstream throughput bottlenecks[END_REF] has identified home Wi-Fi as the bottleneck along the end-to-end path. The cause of poor home Wi-Fi experience can be varied [START_REF] Kim | Wislow: A wi-fi network performance troubleshooting tool for end users[END_REF], channel congestion, poor client or AP placement and interference are the most common causes. Other work [START_REF] Pei | Wifi can be the weakest link of round trip network latency in the wild[END_REF] has analyzed the impact of Home Wi-Fi on the latency in a network path. They have identified that Wi-Fi latency can contribute up to 60% of the overall round trip time along the endto-end path. ISPs are often held responsible for poor Internet experience [START_REF] Da Hora | Predicting the effect of home Wi-Fi quality on QoE[END_REF]. Home users, in the search for a solution can switch between ISPs or content providers even though the problem is within the home. In this research paper we develop a tool to identify home Wi-Fi impairments. We describe the initial stages of this tool in this paper.

Identifying where the root cause is within the home Wi-Fi is challenging due to multiple factors. First, wireless nature is volatile as it uses an open and shared medium, shared among Wi-Fi and non-Wi-Fi devices. Second, it is required to have a vantage point within the home. This vantage point should be common across home deployments and capable of collecting Wi-Fi metrics to assist on the identification of Wi-Fi impairments. Most research work has mainly implemented passive techniques to identify where the potential cause for a degraded service is located [START_REF] Joumblatt | Hostview: Annotating end-host performance measurements with user feedback[END_REF], [START_REF] Neves Da Hora | Passive wi-fi link capacity estimation on commodity access points[END_REF], [START_REF] Patro | Observing home wireless experience through wifi aps[END_REF]. A couple others have relied upon active techniques [START_REF] Kanuparthy | Can user-level probing detect and diagnose common home-wlan pathologies[END_REF], [START_REF] Syrigos | Enabling wireless lan troubleshooting[END_REF]. Depending on the type of measurement technique, it is required to address different considerations. Passive techniques face the challenge of requiring access to the AP to collect the metrics. Making changes to the AP to collect metrics is another challenge as most APs are not open to be customized. With active techniques the complication is the potential overhead caused by the measurement tool. In other words, with active techniques the network can experience disruption.

Our tool implements both techniques to take strong points of both and leverage the weakness with each other's strong points. In this initial phase we are using both techniques to identify the relationship between metrics passively collected and active probing results. We believe that mainly relying on active probing to identify home Wi-Fi impairments can be a breakthrough in the development of tools to be widely deployed in the wild. Further description of these techniques is covered in Section 2. Related work associated to home Wi-Fi study will be covered in Section 5. The instrumentation details of our tool are developed in Section 3. The mechanisms and techniques to evaluate the method used to identify home Wi-Fi impairments is explained in Section 4. Finally findings of our work are consolidated in Section 6. 1

WI-FI MONITORING

Active and passive techniques have their advantages and disadvantages. In the following, we outline the main characteristics of each one of them. Each of the techniques will be best-suited depending on the goal and context of the experiment.

Active

Active measurement is a technique in which traffic is injected in the network to get a sense of the network status. The injected packets are called probes. For our work we use active measurements to obtain metrics on bandwidth, Round-Trip Time (RTT) and packet loss. In the Wi-Fi context, bandwidth active measurements can help to identify where the bottleneck is happening. We have also used active bandwidth measurement tools to generate traffic in our experimental setup to resemble real-case scenarios. High RTT can help to identify if congestion is happening in the home Wi-Fi. In a similar way, packet loss can denote interference as frames are destroyed in the Wi-Fi link. While working with active measurements it is important to pay attention to the probes size and probing rate. Large probe sizes and aggressive probing rate can cause overhead. Overhead does not only disrupts user traffic but can also lead to biased measurements. In the following bullet points we outline the strengths and weaknesses of active measurements that we consider relevant for our work. We also include the ones we work with for this paper.

Strengths

• Full ownership of the network is not required.

• They do not require large space to store data collected as generally, probe packets are small.

• Privacy concerns are minimal as probe packets used to measure are made of random data which has no sensitive information.

• Useful to get the state of the network on-demand.

Weaknesses

• Overhead might occur if probe size and probing rate are chosen without due diligence of network conditions.

• Biased results can be obtained if probes, either size or rate, cause overhead in the network.

Under the scope of active measurement techniques, the following are the metrics to be actively collected for our work.

• Round Trip Time -For our goal, RTT can helps us identify if we are experiencing attenuation and interference in the home Wi-Fi. High RTT values can give a sense of latency in the home Wi-Fi which is potentially correlated to attenuation. Packet loss in the other hand, will point to interference related impairments as frames are being destroyed, causing the loss of these frames.

• Throughput -In Wi-Fi, throughput active measurement can assist to identify if congestion is happening in the Wi-Fi link. For example, if the AP reports a strong signal to the wireless client and minimal losses but the throughput is low, it is likely that the AP is experiencing congestion.

Passive

Passive measurement techniques rely on a "sit and listen" approach. The instrument conducting passive measurements in the network sits in a specific location along the path and records the metrics of interest. The monitor can be a component of the network itself, for example a router. It can also be device devoted to measure, such as a wireless sniffer. An important difference between active and passive techniques is that the latter do not trigger probes. Overhead due to probe packets is not present in passive measurements. However, computational and storage resources in the passive measuring device can be important factors to consider. The device might require to have enough space to store the data being collected. In a similar way, the computational power of the device can be required to be high depending on the speed of the link being measured. A Gigabit link in a core router will handle significantly more data than an 100Mbps Ethernet link in an access switch. Outlined in the following list a high level summary of the key strength and weaknesses of passive measurement techniques for our work purposes. We also outline the ones we use for our work. Strength

• No extra traffic is generated to collect metrics, risk of causing overhead is minimized.

Weaknesses

• Large storage capacity can be required to store collected data. Not all measuring devices have large storage capacity, i.e. Access Points.

• Access to equipment working as passive measurement device is required. This is not possible for most users at multiple devices along an Internet path.

• High computational power on the measuring device can be required depending on the link being monitored and data granularity pursued. Not all devices can provide high computational power, i.e. Access Points.

• RSSI -Received Signal Strength Indicator -In our experiments we collect the RSSI from the AP and the wireless client. The RSSI help us to identify if there is attenuation happening in the link. A low RSSI denotes attenuation in the wireless link.

-Low RSSI can be caused by poor AP placement due to large distance between wireless client and AP or, obstacles between both.

• PHY Tx Rate -The PHY Tx Rate at the wireless nodes can be an indicator of poor Wi-Fi link quality. A low PHY Tx Rate can help to diagnose a congestion, attenuation or interference Wi-Fi impairment. In collaboration with other metrics the scope of the impairment can be narrowed down.

-For example, if the RSSI is strong, meaning there is no attenuation; loss rate is minimal, meaning interference is not present, but Tx PHY Rate is low; the impairment scope can be narrowed down to congestion.

• Noise -Noise measurements assist know if environment where the wireless client or the AP is placed is suitable for Wi-Fi. For example, if the noise level at a particular wireless client is high, we expect that node to be the only one with Wi-Fi degraded quality. In the other hand, if the AP is the one sensing high noise levels, we can expect all the clients connected to that AP to experience degraded Wi-Fi.

-Noise can be caused by devices which "do not speak Wi-Fi language"such as microwave ovens, cordless phones and similar. Noise can help to distinguish between congestion and interference. Unlike congestion, interference is driven by non-WiFi sources.

• Throughput -Driver Logs -The throughput from the driver logs assist us to sense a Wi-Fi impairment. Low throughput can be an indicator of congestion, attenuation or interference.

-In a similar way as for actively measuring throughput, collaborating with other metrics can narrow down the potential Wi-Fi impairment.

-Additionally, passively measuring bandwidth helps to validate we obtain similar values obtained from active measurement techniques.

• Frame Delivery Ratio -Frame Delivery Ratio depicts the ratio between packets successfully received and total packets sent. The FDR metric can assist to get a sense of link quality. Low FDR indicates poor link quality.

-Poor link quality can be caused due to congestion, attenuation or interference. In a similar way as with other metrics in our work, we collaborate with other metrics to narrow down the potential Wi-Fi impairment being experienced.

The metrics described before have been collected from different devices in our setup. Previous works have identified that even with similar wireless conditions devices can experience different throughput and bitrates [START_REF] Sundaresan | Measuring the performance of user traffic in home wireless networks[END_REF], therefore we use different vantage points. Passive metrics have mostly been collected at the wireless client and AP. We extract these metrics from driver logs and derived statistic from them. Additionally we setup a wireless sniffer to get wireless captures. We use the wireless captures to validate the values we get from the logs at wireless client and AP. In the case of active metrics, we collect them from a wired client. The wired client works as the device in which we target to deploy our tool. From the wired client we trigger the active probing tool to collect RTT and throughput. The RTT measurements are collected using a custom ping-like tool. The active throughput is collected with iPerf. In section 3 we share instrumentation details on the tools we use to obtain the metrics we work with.

Finding the probing rate

Finding the probing rate is important when working with active measurements. A high rate can cause overhead, whereas a low rate can fail to capture the status of the network. To approach this challenge we conducted experiments in our office lab. Our experiments consisted in sending a series of ping trains which included multiple pings inside each train. We ran the tests with different train inter-spacing values and with different amount of pings inside the trains. The first finding from our experiments was a delay in RTT due to power save mode in devices. The power save mode sends the NIC to sleep. We refer to this delay as the "sleeping NIC". We found that when the inter-train spacing is smaller or equal to 100 msec the power save mode delay is not present. Based on this finding we set our lower bound for inter-train spacing to 100 msec. We set our upper bound to 1000 msec as the RTT within a single-hop home Wi-Fi network without significant cross-traffic is expected to be only a few milliseconds. This observation is remarked in the work of Sundaresan et al. [START_REF] Sundaresan | Home network or access link? locating last-mile downstream throughput bottlenecks[END_REF].

The second relevant finding is associated to the RTT value of each ping within a train. We found that even with inter-train spacing values above 100 msec it is possible to overcome sleeping NIC delay by considering the RTT value of the 3rd or greater ping within a train. We noticed that the RTT value for ping greater or equal to the 3rd ping in a train depicted similar RTT values as when the sleeping NIC delay is not present. After these observations we defined our baseline to be 100 msec inter-train spacing and 3 pings per train. Figure 1 illustrates the values for the average round trip time of three pings in a train. The inter-ping spacing is equally distributed among the number of pings in a train and depends on the inter-train spacing. For example, the inter-ping spacing value for 3 pings in a 100 msec intertrain series is 100 msec/3 or 33.33 msec. With this exercise we defined our baseline, we implemented similarity tests between our baseline results and samples derived from the baseline. We refer to our baseline as aggressive probing. To keep the samples to follow the same distribution as our baseline we implemented a Poisson process to generate the inter-train space intervals. In other words, randomly sampling from a Poisson process will result in another Poisson-distributed process [START_REF] Raikov | On the decomposition of poisson laws[END_REF]. This feature has been included in our GoPing tool. We sampled our baseline to obtain from 10% to 90 % of our original data points. We implemented Bernoulli random sampling to extract our samples. Finally, we ran Two-sample Kolmogorov-Smirnov tests between our baseline and samples. From the results we noticed that the sample which delivers a similar ECDF to our baseline is the one that keeps 50% of the original baseline data points. Figure 2 illustrates both ECDFs.

In figure 2 we can see the overlap between the sample keeping 50% of original data points and the original baseline derived from aggressive probing. This was the sample in which the overlap occurred, based on this result we set our active probing rate. As the RTT ECDF After finding the active probing rate as described in Section 2.3 we tested it in the testbed where we ran our experiments. Further description on our labs setup is covered in Section 3.1. The tests consisted in sending as many batches as possible for 10 min at 100 and 200 msec probing rates. Additionally we varied the attenuation with values of 0, 15 and 30 dBm. Table 1 summarizes the values used for the test. The test sessions took place in the 2.4 GHz band using 802.11n WLAN with no authentication. We ran each experiment session 5 times, in total we obtained 30 samples. We compared the RTT ECDF of both to check similarity between probing rates. The expectation was for curves to be similar to each other. As expected, figure 3a illustrates the similarity between both RTT ECDF probing rates. The next expected behavior was for RTT to increase as the attenuation values increases. Figure 3b help us to validate the expected behavior. As we increase attenuation, RTT increases.

WIRELESS BOTTLENECK DETECTOR

We strive to detect Home Wi-Fi impairments, to achieve our goal we model our detector as a classification problem. To generate the data to train our model we ran experiments and trigger Wi-Fi impairments during the experiments. From the experiments we collect the metrics described in Section 2 and create datasets derived from them. Finally we consolidate our datasets and feed them into a supervised learning tool we used for classification.

Labs Setup

In order to run our experiment we work with two labs. A small In-office lab and a testbed to run experiments mostly associated to wireless technologies.

In-Office Lab

The In-office lab was mainly used to work on finding the probing rate to be used in the experiments at the testbed we worked with. The setup at our office is primarily composed by the following elements.

Orbit Lab

The second lab we work with is Orbit Lab [START_REF] Ott | Orbit testbed software architecture: Supporting experiments as a service[END_REF]. Orbit lab is a large testbed in which different wireless technologies can be tested. One of these wireless technologies is 802.11. Within Orbit Lab we work with Sandbox 4 (SB4) which includes features to vary the attenuation between the nodes in the Sandbox. The main components of SB4 we work with are the followings.

1. SB4 has 9 nodes, each one of them runs Ubuntu 12.04

2. Attenuation Controller which makes possible to vary the attenuation between the nodes.

Each of the nodes has an Atheros Wireless card, the models are Atheros 5K and 9K. The nodes we work with have Atheros chipsets which allow us to collect detailed Wi-Fi logs. The links between the nodes in SB4 can be set to attenuation values between 0-30 dBm from the attenuation controller. The topology of SB4 depends on the attenuation values for each link. For example, a full-mesh topology is achieved when the attenuation value for all the links is set to 0 dBm. Thanks to the attenuation controller we can setup experiments in which changes on the RSSI are visible. The RSSI, as descried in section 2, is a metric which can help to identify attenuation impairments. The main deployment we use in Orbit is similar to the deployment we have at the In-office lab. The node working as AP was setup using the hostapd utility. The WLAN settings for the AP are summarized in table 2

Experiments Setup

Once our labs were setup we ran our experiments. During our experiments we collect active and passive metrics using a diverse set of tools. Most of the tools we work with are out-of-the-box tools, such as iPerf, tc and tcpdump. The active measurement tool we use to collect RTTs is a custom implementation of Ping in GoLang. We refer to this tool as GoPing. We have customized GoPing to send ping trains and batches. To trigger Wi-Fi and non-Wi-Fi impairments we setup three main scenarios in Orbit SB4 testbed. Two of them, attenuation and congestion, are Wi-Fi-related. The third one is an access link impairment. Across the three scenarios we let running the collection of active and passive measurements. Our experiment sessions last 10 min. Passive wireless metrics logs are collected every 10 secs at the AP and Wireless client. We also setup a wireless a sniffer to obtain Over-the-Air packet captures. From the wired client we send pings towards the AP and log the stats from GoPing. For the throughput measurement with iPerf, we setup iPerf server at the wireless node and the iPerf client at the wired node. iPerf was setup in TCP mode with 4 parallel TCP streams. We chose TCP as we expect it to be the transport protocol most commonly used by services at home Wi-Fi networks. We work with 4 parallel streams as we expect the number of TCP streams in a home to be less than 5 TCP streams.

Attenuation

To trigger attenuation impairments in the testbed we vary the attenuation at the link between the wireless client and the access point. As mentioned before the setup we use at SB4 in Orbit is similar to our In-Office lab which is illustrated in figure 4. The additional component to this setup is the node working as a wireless sniffer. The attenuation impairment happens in the 3 rd and 9 th minute of the 10 min session. The experiment is designed this way to set a comparison between impairment-free and impairment conditions. This experiment design also assists on the evaluation of the classification tool we work with. We setup 5 scenarios with an increase of 3 dBm per impairment interval. Table 3 breakdowns the scenarios and the attenuation levels for each impairment interval. We ran each experiment 5 times.

Scenario

Attenuation

Congestion

To trigger congestion in our testbed, we connect more wireless clients to the same AP our main wireless client is connecting to. At the 4 th and 8 th minute we connect an additional wireless clients to the AP. The additional wireless clients send UDP traffic to the AP using iPerf, hence the AP is running an iPerf server instance. We increase by one the wireless nodes connecting to the AP per interval.

Access Link Limiting

The third scenario triggers a non-Wi-Fi impairment. The experiment consists in limiting the access link capacity at the wired node. We achieve limiting at the wired node by using tc, a traffic shaper utility. In a similar way to the attenuation scenario, we trigger the impairment conditions at the 3 rd and 9 th minute of the 10 min experiment window.

RSSI in the wild

With regards to the attenuation scenario we ran a survey to find the common RSSI value in home and office environments. We asked the colleagues at our office to run a script which collects Wi-Fi metrics on their laptops at different times during their stay at home or office. From the 760 samples collected we found that the most common RSSI value ranges between -60 and -65 dBm. Figure 5 illustrates the RSSI histogram of our survey.

Classification tool

After completing our experiments we moved on to the classification phase. To classify our events we use Weka. Weka is a software which has different supervised learning algorithms. We work with three algorithms avail-able in Weka, J48, AdaboostM1 and random forest. To train Weka we feed it with the dataset derived from our experiments. Our experiments are designed in a way in which each impairment happens during a specific interval within the 10 min experiment window. Therefore we know at which interval does the impairment occurs. In other words, each experiment session consists in 10 intervals, each one 60 sec long. Depending on the scenario; congestion, attenuation or access link, we trigger the impairment at a specific interval as described in Section 3.2.

EVALUATION METHOD

To evaluate the classification generated by Weka we create two datasets, binary and multiclass. We create these datasets to feed them into Weka and evaluate the results with different algorithms. In the binary dataset we work with only two labels. The goal is to identify if there is a Wi-Fi impairment or not. The labeling schema for the binary dataset is described in table 7.

Label

Issue Type 0 No Issue at all 1 Attenuation 0 Access-Link Limiting 1 Congestion

Table 7: Binary dataset labels

As represented in table 7, even though "access link limiting" is a network impairment it shares the same label as "no issue at all". They both share the same label as access link limiting nature is non-Wi-Fi. The second type of dataset is multiclass. The multiclass dataset has the goal to classify in more detail the impairment, to distinguish if it is congestion, access link limiting, attenuation or none of them. In multiclass dataset we assign a different label to each impairment. The labeling for the multiclass dataset is described in table 8 For both datasets we ran the algorithms J48, Ad-aBoostM1 and random forest. We used the default 10 fold cross-validation in Weka for these algorithms. The results obtained from the binary dataset are outlined in table [START_REF] Ott | Orbit testbed software architecture: Supporting experiments as a service[END_REF]. The best results are obtained with the "random forest" algorithm. The next step was to feed Weka with the multiclass dataset. As mentioned before, with the multiclass dataset the goal is to classify the impairment in more detail. The results are summarized in table 6. Once again the best results are obtained with the random forest algorithm.

RELATED WORK

The challenge to identify impairments in the home Wi-Fi has been approached before. To address this challenge the research community has relied on two measurement techniques, active and passive. While most of previous works have opted for passive techniques [START_REF] Joumblatt | Hostview: Annotating end-host performance measurements with user feedback[END_REF], [START_REF] Neves Da Hora | Passive wi-fi link capacity estimation on commodity access points[END_REF], [START_REF] Patro | Observing home wireless experience through wifi aps[END_REF]; others, have worked with active ones [START_REF] Kanuparthy | Can user-level probing detect and diagnose common home-wlan pathologies[END_REF], [START_REF] Syrigos | Enabling wireless lan troubleshooting[END_REF]. The work of Da Hora et al [START_REF] Neves Da Hora | Passive wi-fi link capacity estimation on commodity access points[END_REF] chose passive techniques. In their work they develop a method to detect poor QoE derived from Wi-Fi quality metrics. In their research context, active techniques have not been used to prevent user traffic disruption and battery drain of devices under study. Within the context of passive metrics, they excluded per packet analysis as it can result in overhead during high network utilization periods. Our efforts learn from their work on the meaningful Wi-Fi quality metrics to be passively collected. On the active probing side, we approach it in a different way as we implement an active probing rate which we believe will not cause user traffic disruption. In the work of Ashish et al [START_REF] Patro | Observing home wireless experience through wifi aps[END_REF], they present a metric called Witt which can help to get a sense of the home Wi-Fi experience from the AP perspective. Their implementation relies on passive measurements. Their AP, which is a custom AP, requires to be customized in hardware and software to interact with their infrastructure. From their work we takeaway the strong point of using the AP as a vantage point to get a sense of the home Wi-Fi experience. However, at this point we discard AP customization even though it increases the granularity and number of metrics collected. Our work pursues a software and hardware agnostic tool to facilitate its wide deployment in the wild and we believe AP customization can hinder this goal. On the active measurements techniques side, Kanuparthy et al [START_REF] Kanuparthy | Can user-level probing detect and diagnose common home-wlan pathologies[END_REF] have implemented user-level prob-ing. In their work they describe the ability to identify wireless pathologies derived from a metric proposed by them called wireless access delay. Their metric reflects the delays a packet faces while going through a 802.11 link. Their setup is almost agnostic as they require to deploy a wired device in the home Wi-Fi for their metric to be collected. Our work is similar to them as we also implement user-level probing. We use a ping-like tool to pursue software and hardware agnosticism. We approach the requirement of having a wired device deployed in the home Wi-Fi by leveraging with an existing project which facilitates the use of a wired device [START_REF] Joumblatt | Hostview: Annotating end-host performance measurements with user feedback[END_REF]. Under the same light of active measurement techniques, the work of Syrigos et al [START_REF] Syrigos | Enabling wireless lan troubleshooting[END_REF] defines a set of metrics to characterize Wi-Fi pathologies. The metrics proposed are derived from statistic available in most wireless devices. From their work we learn active metrics available in wireless equipment from which Wi-Fi impairments pathologies can be characterized. For the development of this paper we have learned from research mention along this section and continue to extend our knowledge on novel frameworks to approach the challenge of home Wi-Fi impairment detection.

CONCLUSION

In this initial stage the results obtained from random forest classification are promising nevertheless they can be considered "too good to be true". We consider that it is required for us to include more variability to the experiments we are working with and the size of the datasets to increase the robustness of our results. As mentioned in the opening of this paper, the goal is to include the findings of this initial stage to leverage the wide deployment of a home Wi-Fi impairments detector in the wild. We forecast leverage its deployment with existing projects already deployed in the wild. We are aware there is room for improvement in our work and we strive to further develop our methods to identify home Wi-Fi impairments.

Attribute

Figure 1 :

 1 Figure 1: Average RTT for Three Ping Series

Figure 2 :

 2 Figure 2: ECDF -Aggressive Probing vs Sample

  (a) Att. 0 dBm -Rate 100,200 msec (b) Rate 200 msec -Att. [0,15,30] dB

Figure 3 :

 3 Figure 3: RTT ECDFs for Attenuation and Probing Rate in Testbed

1 .

 1 Raspberry Pi 3 running Raspbian GNU/Linux 8 (Jessie) 2. Wireless Access Point TP-Link AC1750 3. Dell Inspiron Laptop running Ubuntu 16.04.4 LTS (Xenial Xerus) The wireless card driver on the Dell Laptop supports 802.11 a/b/g/n/ac. The driver is iwlwifi version 4.4.0-130-generic and firmware=17.948900127.0. At the In-Office lab we setup our deployment as illustrated in figure 4. The Pi was the device from which we send the pings towards the Laptop. As illustrated in figure 4 the Pi and access point are connected via Ethernet. The laptop is connected with the AP via 802.11n. During the tests at the In-lab office we switched between 2.4 and 5.0 GHz band depending on the goal of the experiment. The In-Office lab played a key role to test the features we included in our GoPing tool prior to running experiments at the second lab.

Figure 4 :

 4 Figure 4: In-Office Lab Deployment

Figure 5 :

 5 Figure 5: RSSI Survey Values Histogram

Table 1 :

 1 Attenuation and Probing Rate Validation Values

	Attenuation Probing Rate
	0 dBm	100msec
	0 dBm	200msec
	15 dBm	100msec
	15 dBm	200msec
	30 dBm	100msec
	30 dBm	200msec

Table 2 :

 2 . WLAN Settings at AP Node

	Setting	Value
	802.11 Protocol	802.11n
	Channel Bonding	No
	Band	2.4 GHz
	Security	Open

Table 3 :

 3 Attenuation Scenarios and Values

			Value [dBm]
		1st Interval	2nd Interval
	1	3	6
	2	9	12
	3	15	18
	4	21	24
	5	27	30

Table 4

 4

			consolidates the scenarios and
	number of wireless nodes connecting to the AP per in-
	terval.
	Scenario	Connected Wireless Nodes 1st Interval 2nd Interval
	1	1	1
	2	2	2
	3	3	3
	4	4	4
	5	5	5

Table 4 :

 4 Congestion Scenarios and Values

Table 5 :

 5 Table 5 details the scenarios and values for the Access Link Limiting scenario. Access Link Limiting Scenarios and Values

	Scenario	Throughput [Mbps] 1st Interval 2nd Interval
	1	100	90
	2	80	70
	3	60	50
	4	40	30
	5	20	10

Table 8 :

 8 . Multiclass dataset labels

	Label	Issue Type
	0	No Issue at all
	1	Attenuation
	2	Access-Link Limiting
	3	Congestion

Table 6 :

 6 Classification Results

	-Algorithm	Dataset	Correctly Classified	Incorrectly Classified	RMSE	Precision	Recall
	J.48	Binary Multiclass	99.47% 98.66%	0.53% 1.33%	0.06 0.07	0.99 0.98	0.99 0.98
	Adaboost	Binary Multiclass	99.73% 85.73%	0.27% 14.26%	0.05 0.20	0.99 0.99	0.99 0.85
	Random Forest	Binary Multiclass	100.00% 99.86%	0.00% 0.13%	0.03 0.04	1.00 0.99	1.00 0.99

ACKNOWLEDGEMENTS

I would like to thank the supervisors and advisors who guided me on this work. I also thank the colleagues at Inria, LINCS and UPMC who contributed to this paper. This work was supported by the French ANR Project no. ANR-15-CE25-0013-01 (BottleNet), by the Inria Project Lab BetterNet, and by a Google Faculty Award.