Lei Yu
email: [lei.yu@univ-rennes1.fr

Mohamed Laaraiedh
email: mohamed.laaraiedh@univ-rennes1.fr

Stéphane Avrillon
email: stephane.avrillon@univ-rennes1.fr

Bernard Uguen
email: bernard.uguen]@univ-rennes1.fr

Julien Keignart
email: julien.keignart@cea.fr

Julien Stéphan

Yu ⋆ Lei

Julien Stephan
email: jstephan@siradel.com

Performance Evaluation of Threshold -Based TOA Estimation Techniques Using IR-UWB Indoor Measurements

Keywords: TOA, Ranging techniques, Channel impulse response, IR-UWB, Measurements, Indoor positioning

I. INTRODUCTION

Ultra wide-band (UWB) is a viable technology for shortrange wireless indoor communication with a number of attractive features: high-rate transmission, low complexity, low cost, and low-power consumption [START_REF] Win | Impluse radio: How it works[END_REF], [START_REF] Molisch | UWB-based sensor networks and the IEEE 802.15.4a standard -a tutorial[END_REF]. This technology has generated considerable and increasing interest by many manufacturers since February 2002, when the Federal Communication Commission (FCC) opened up 7.5 GHz of spectrum (from 3.1 GHz to 10.6 GHz) for use by UWB devices. The traditional design approach for an UWB communication system uses narrow time-domain pulses of very short duration, typically on the order of a nanosecond, thereby spreading the energy of the radio signal quite uniformly over a wide frequency band ranging from extremely low frequencies to a few gigahertz [START_REF] Guvenc | Ultra-wideband range estimation: Theoretical limits and practical algorithms[END_REF], [START_REF] Gezici | Localization via ultra-wideband radios: a look at positioning aspects for future sensor networks[END_REF]. This method is usually called impulse radio UWB (IR-UWB). A great advantage of the short pulse modulation is the possibility to estimate the TOA with a fine resolution, which translates in ranging estimation with a less than one meter accuracy allowing for many location and tracking applications. The two main ranging techniques defined for IR-UWB are One Way Ranging (OWR) and Two Way Ranging (TWR) [START_REF] Gezici | Localization via ultra-wideband radios: a look at positioning aspects for future sensor networks[END_REF], [START_REF] Denis | Advanced bayesian filtering techniques for uwb tracking systems in indoor environments[END_REF], [START_REF] Dardari | Ranging with ultrawide bandwidth signals in multipath environments[END_REF].

Using channel (impulse) responses -C(I)R-, different techniques have been proposed for estimating TOA. The simplest and easiest technique estimates the TOA as the time of arrival of this strongest path [START_REF] Dardari | Ranging with ultrawide bandwidth signals in multipath environments[END_REF], [START_REF] Bellusci | A new approach to low complexity uwb indoor los range estimation[END_REF]. However, this assumption is not usually true in multipath conditions. In such conditions, we distinguish two cases: the Line-of-Sight (LOS) in which no obstacle separates the Tx and the Rx and the Non-Lineof-Sight (NLOS) if the obstacle exists. In the LOS case, the strongest path is usually the first path while in the NLOS case the first path may be more attenuated than indirect paths [START_REF] Li | A new two-step ranging algorithm in nlos environment for uwb systems[END_REF]. Hence, we need more advanced techniques to extract this first path and estimate the TOA. The reader can refer to [START_REF] Guvenc | Ultra-wideband range estimation: Theoretical limits and practical algorithms[END_REF], [START_REF] Dardari | Threshold-based time-of-arrival estimators in uwb dense multipath channels[END_REF] and references therein for more details about the techniques already proposed for TOA ranging within IR-UWB signals.

In that direction, this paper presents a contribution to the TOA estimation techniques based on IR-UWB channel responses. Four techniques are presented and studied using an IR-UWB measurements campaign. The first technique is typical and widely used. It is based on the setting of a threshold above the noise floor to detect the first ray. Based on this first technique, we derivate three different techniques. The second technique is a modified version of the first one and uses the cumulative CR instead of the CR. The third technique is based on the detection of the first strongest paths using a dichotomous search approach. The fourth and last technique is a combination of the first and third techniques.

The rest of the paper is organized as follows. We start in section II by giving the assumed channel model. Then, we details in section III the different techniques of TOA estimation. In section IV, the UWB measurement campaign is presented. This measurement campaign is used to tune, evaluate, and compare the different presented techniques. Finally, the results are discussed in section V and our concluding remarks are given in section VI.

II. UWB CHANNEL IMPULSE RESPONSE MODEL

For all the rest of the paper, we consider a multipath channel with a CIR modeled as the sum of all received pulses as follows:

c(t) = N n=1 a n δ(t -τ n ) (1)
where a n and τ n are, respectively, the amplitude and timedelay of the nth propagation path; τ 1 is the time of arrival of the first path (i.e. The TOA between the Tx and the Rx) which we seek to find out. The received signal can then be expressed as:

r(t) = N n=1 a n ω(t -τ n ) + n(t) = s(t -τ 1 ) + n(t) (2)
where ω(t) is the isolated ideal received pulse with duration T p (i.e. in the absence of multipath and noise) and n(t) is the additive white Gaussian noise (AWGN) with zero mean and spectral density N 0 /2 where N 0 is the noise power density. s(t) is the noise-free CIR defined as:

s(t -τ 1 ) = N n=1 a n ω(t -τ n ) (3)
In all the rest of this paper, we use the sampled form of r(t) with a sample rate 1/T s where T s is the sample duration. Let M be the number of samples which compose r(t). Hence, if the received signal is observed in the interval [0, T ], we get T = M T s . The mth sample occurs at the time t m = mT s (m ∈ (1, ..., M )).

Given a channel response modeled by ( 2), the goal is to estimate τ 1 , i.e. the TOA of the first path. In the next section, four different techniques for estimating TOA will be described. This approach is the most typical and has been proposed by Lee and Scholtz in [START_REF] Lee | Ranging in a dense multipath environment using an UWB radio link[END_REF]. This technique starts by defining a threshold γ th which must be above the noise level in order to limit as much as possible false alarm on noise peak while maintaining a sufficient level of detection. The implementation of this technique involves the following steps:

• Consider the squared channel response r 2 (t); • Compare the actual value of r 2 (t) to the appropriate threshold γ th ;

• Search the first crossing point and let m be the corresponding sample. The TOA estimate τ th 1 is then given by mT s . The choice of the threshold is the most challenging task in such technique. As shown in Fig. 1, which plots an example of measured CR, the probability of detecting noise peaks (false alarm) is higher with an underestimated threshold. Whereas, with an overestimated threshold, it is the probability of skipping the direct path which is higher. In [START_REF] Guvenc | Threshold-based TOA estimation for impulse radio UWB systems[END_REF], different methods for choosing the threshold are described and compared. In this paper, we have chosen to statistically define the threshold relatively to the maximum value of the signal using the available UWB measurements (see section V below).

B. T2: Setting a threshold above the cumulative noise floor

In this technique, we propose to apply a threshold on the cumulative received signal instead of the simple received signal in technique T1. For this, the ecdf (energy cumulative density function) c r (t) of the received signal r(t) is defined and it is given, at time τ by:

c r (τ ) = τ 0 r 2 (t)dt = τ τ1 s 2 (t -τ 1 )dt + τ 0 n 2 (t)dt +2 τ τ1 s(t -τ 1 )n(t)dt (4)
where s(t) is defined in [START_REF] Guvenc | Ultra-wideband range estimation: Theoretical limits and practical algorithms[END_REF]. Then, we obtain:

c r (τ ) = E s ([τ 1 , τ ]) + c n (τ ) + 2 τ τ1 s(t -τ 1 )n(t)dt (5)
where E s ([τ 1 , τ ]) represents the integrated energy of the useful signal between τ 1 and τ and c n (τ ) represents the integrated noise between 0 and τ . The last integral ( τ τ1 s(t -τ 1 )n(t)dt) can be neglected assuming independence between signal and noise. This leads to the following expression:

c r (τ ) ≈ E s ([τ 1 , τ ]) + c n (τ ) (6)
After the construction of this cumulative signal, the same steps presented for technique T1 are applied (see Fig. 2). That is to say:

• Compute the cumulative received signal c r ;

• Compare the actual value of c r to the appropriate threshold γ cum ;

• Search the first crossing point and let m be the corresponding sample. The TOA estimate τ cum 1 is then given by mT s .

C. T3: Dichotomous left interval selection

This technique seeks to estimate properly TOA values associated with situations where the strongest path is not the first path (but it is still valid in LOS situations). This technique ecdf(r) Time Fig. 2.

T2 -Setting a threshold above the cumulative noise floor-: the threshold is now applied on the cumulative channel response. The figure plots an example of an ecdf obtained from measurements.

proposes to consider the largest N max peaks of the received signal. A receiver can easily search these strongest paths. The TOA is then estimated as the time delay of the peak with the smallest index (see Fig. 3). In this technique, the key parameter is N max which is the number of the largest signal peaks. In this work, N max is chosen statistically using the UWB measurement campaign. The pseudo-code of this technique is given by Algorithm 1.

Algorithm 1 Dichotomous left interval selection

γ 0 ← max{r 2 (τ )}: compute the peak energy set N max : the key parameter γ ← γ 0 : initialize the threshold N int ← 1: initialize the number of current intervals ǫ ← 10 -2 : set the the decreasing factor while N int < N max do T γ ← GetIntervals(r 2 (τ ), γ): compute the valid time support N int ← NumberofIntervals(T γ ): update the number of intervals (strongest peaks) γ ← γ(1 -ǫ): decrease the threshold by ǫ end while τ max 1 ← min{T γ }: estimate the TOA T γ is a union of intervals which corresponds to the delay values where the squared received signal is above a threshold γ. This set of intervals is determined via a dichotomous algorithm which stops when the preassigned value of interval N max has been reached. The estimated delay is then chosen as the minimum value of this interval. This pseudo-code defines two elementary function GetIntervals and NumberofIntervals which respectively return the time support where r 2 (τ ) > γ and the number of disjoint intervals from a union of intervals given as an input. This approach is different in nature from both jump back and search forward (JBSF) and seek backward scheme (SBS) described in [START_REF] Guvenc | Ultra-wideband range estimation: Theoretical limits and practical algorithms[END_REF] and [START_REF] Falsi | Time of arrival estimation for uwb localizers in realistic environments[END_REF]. There is no threshold to be defined from a-priori knowledge of the channel parameters.

D. T4: Thresholded dichotomous left interval selection

This technique mixes the threshold-based technique (T1) and the left interval technique (T3) in a search-back window in order to detect the first arrival path (see Fig. 4). The estimator involves the following steps:

1) Find the strongest path and calculate the peak energy γ 0 ; 2) Find the peak energy γ noise in the noise part of the CR by defining a common time slot (0-5ns in our case); 3) Set a fixed size search-back window, from 0 to the strongest path, in order to estimate the TOA; 4) Decrease the threshold γ gradually from the peak energy γ 0 and calculate the number of intervals in the defined search-back window; 5) Calculate the ratio γ -γ noise /γ 0 ǫ and stop the algorithm when the ratio is relatively close to α which is the key parameter defined to best fit the measurements; 6) Search the first crossing point and let m be the corresponding sample. The TOA estimate τ win 1 is then given by mT s . The pseudo code of this technique is given by Algorithm 2. in the SIRADEL headquarter building in Rennes, France. The goal was to collect UWB channel responses in a same local area. In order to assess small-scale fading, channel response measurements are made on several square grids. This measurements campaign is dedicated for the evaluation and validation of localization techniques and algorithms.

The time-domain channel sounder is mainly composed of a pulse pattern generator, a wide band digital oscilloscope, and UWB antennas. The whole measurement setup is illustrated in Fig. 5 [START_REF] Keignart | UWB SIMO channel measurements and simulations[END_REF]. On the transmitter side, a Pulse Generator (Picosecond Pulse Lab 4050B) with two additional impulse forming networks and a power amplifier fit the desired UWB impulse shape in the 3-7 GHz bandwidth (see Fig. 6). On the receiver side, a wide-band Digital Oscilloscope (Tektronix TDS 6124C) is used with a sampling rate of 20 Gsps in real-time. In order to improve the time precision, a sinc interpolation is used in order to get a final time step of 5ps. Moreover, the signal is averaged over 16 snapshots for increasing the signal-tonoise ratio (SNR). For dynamic range consideration, it is also necessary to use Low Noise Amplifiers in front of oscilloscope input channels. On both Tx and Rx sides the same kind of antenna is used. The radiation pattern is omni-directional in azimuth with a bipolar radiation pattern in elevation [START_REF]Measurements of location-dependent channel features[END_REF]. During the campaign, four fixed receiver positions were defined and 302 measurement points were selected for the transmitter positions [START_REF]Measurements of location-dependent channel features[END_REF] with the transmitter and the four receivers at the same height (120cm between the floor and the antenna ground plan). Fig. 7 shows the different positions of transmitters and receivers. The most important pieces of furniture (metallic cupboards and tables) should be taken into consideration when modeling the channel propagation and estimating TOA in order to better understand the effects of radio propagation, channel characteristics, and environment components on extracted TOA. These furniture pieces are presented in Fig. 8. Nevertheless, many other small pieces of furniture (chairs, printers, refrigerator, etc) are present when performing measurements. Taken into consideration all these small furnitures in channel modeling is a hazardous task. Hence, the choice was been made not to consider these small furnitures. When performing channel sounding, it is necessary to extract exclusively the channel behavior (with or without antennas) by using appropriate calibration procedures based on deconvolution tools [START_REF] Denis | Post-processing framework for enhanced UWB channel modeling from band-limited measurements[END_REF]. These calibration procedures aim to eliminate the effects of all the elements involved in the link like PA, cable, and LNAs. For each Tx-Rx pair, we store the CR measured by the sounder. In addition to the CR, different parameters are saved in each profile mainly Tx and Rx positions accurately measured, date, and time [START_REF]Measurements of location-dependent channel features[END_REF]. We define also the link quality indicator (LQI) as the ratio between the maximum signal amplitude and the maximum noise amplitude estimated during the first five nanoseconds corresponding to a common time slot without any signal [START_REF]Measurements of location-dependent channel features[END_REF]. The LQI gives an indication about the SNR of the received signal. The ranging techniques will hence be evaluated for different values of the LQI (i.e. the SNR).

V. RESULTS AND DISCUSSIONS

The four presented techniques in section III are dependent on key-parameters which have to be adequately chosen in order for the technique to perform higher ranging accuracy. The determination of optimal key-parameters is not the object of this paper. In order to make a fair comparison between the four techniques, we set the key-parameters to the values which fit the best the available measurements. Nevertheless, these key parameters can be fixed in a more optimal way in order to guarantee more enhanced performances. These parameters can be chosen for example with respect to the SNR values or based on received signal statistics [START_REF] Guvenc | Ultra-wideband range estimation: Theoretical limits and practical algorithms[END_REF].

A. Tuning of different techniques using the measurement campaign

The figures (a) to (d) in Fig. 9 represent the average absolute ranging error as a function of key parameter values respectively for the four techniques. In each figure, the keyparameter which gives the best average ranging accuracy is chosen. These figures give a parametric evaluation of the different techniques and highlight the importance of choosing the best value for the key parameter in order to reach the highest ranging accuracy.

In the rest of this paper, the chosen key-parameters are:

• Technique T1: γ th /γ 0 = 0.14

• Technique T2: γ cum = 0.04 • Technique T3: N max = 16 • Technique T4: α = 13

B. Comparison of different techniques

In order to compare the four TOA ranging techniques, we consider the UWB measurement campaign described before and we apply the different techniques on the 302 Tx positions. In total, we got 302 × 4 = 1208 TOA estimates. First, we plot in Fig. 10 the evolution of the average ranging error with respect to the LQI values. This figure reveals that at higher SNR, the four techniques achieve close ranging accuracy which tends to 3cm. For lower SNR, the T4 technique achieves the best performances while the typical T1 technique is not reliable at all. The techniques T2 and T3 outperform the T1 technique at lower and medium SNR. These results outperform the results proposed in [START_REF] Hernandez | Accurate indoor wireless location with ir uwb systems a performance evaluation of joint receiver structures and toa based mechanism[END_REF] and approaches those presented in [START_REF] Falsi | Time of arrival estimation for uwb localizers in realistic environments[END_REF] where no real measurement campaign was used to evaluate the performances of ranging techniques. Indeed, these two papers used simulation models (CM1, ..., CM4), which are more or less simplified and do not accurately represent the reality of the radio channel. In our work, the goal was to evaluate the ranging techniques on a real measurements campaign in order to outcome the limits of such techniques.

In the rest of this section, we will present the performances for links with a LQI higher than 10dB. The overall comparison is given in Fig. 11 and Table I while the comparison between these techniques in LOS, NLOS, and NLOS 2 cases are given respectively in Table II. The LOS case is a situation where no obstacle is located between the Tx and the Rx. If an obstacle exists, we have no visibility between the Tx and the Rx and we differ two cases: the NLOS case where a direct path crosses the obstacle and reach the Rx and the NLOS 2 case where no direct path is crossing the obstacle. In each figure, we plot the cumulative density function (cdf) of the ranging error for the four different techniques. Fig. 11 shows that the T4 technique outperforms the three other techniques. Table I shows that the lower mean ranging error and standard deviation are performed by the fourth technique (T4) which is based on the fusion of T1 and T3 techniques. It benefits thus from the advantages of these two techniques to give the best ranging accuracy. With a real measurement campaign, we believe that the obtained accuracy of 13cm as a mean value and 50cm as a deviation value is very promising compared to results presented in [START_REF] Dardari | Ranging with ultrawide bandwidth signals in multipath environments[END_REF], [START_REF] Falsi | Time of arrival estimation for uwb localizers in realistic environments[END_REF], [START_REF] Hernandez | Accurate indoor wireless location with ir uwb systems a performance evaluation of joint receiver structures and toa based mechanism[END_REF], [START_REF] Dardari | Time-of-arrival estimation of uwb signals in the presence of narrowband and wideband interference[END_REF]. Notice also that the choice of the key parameter of each technique should be done in a more optimal way in order to enhance the ranging accuracy. In some NLOS and NLOS 2 situations, it occurs that the signal is obstructed by a metallic cabinet which makes the detection of the first ray very difficult and the ranging accuracy very poor. This is shown in Fig. 12 where we plot the distribution of ranging error for the four receivers using the T4 technique. In this figure, the positions obstructed by metallic cabinets show a low ranging accuracy. These metallic cabinets deeply affect the TOA ranging accuracy. In order to better model and exploit TOA within localization applications under the presence of such obstructing objects, TOA models should be spatially particularized as shown in [START_REF] Uguen | Extraction and characterization of location-dependent uwb radio features with practical implications for indoor positioning[END_REF].

VI. CONCLUSION

This paper presented a study of four different ranging techniques applied to IR-UWB technology. Using an IR-UWB measurements campaign, these four techniques are tuned, evaluated, and compared. The paper presented the typical threshold-based TOA estimation technique and proposed a modified version using the cumulative channel impulse response. We proposed also a dichotomous based technique which outperforms the cumulative CIR based technique. The fourth and last technique is a fusion of the two techniques: threshold based and dichotomous based. This technique benefits from the advantages of these two techniques and outperforms hence all the studied techniques. The main outcome of this paper was to study the performances of ranging techniques on a real UWB measurement campaign unlike the most of existing works which are based on simplified simulation models. The paper shows that the reached accuracy with this real measurements campaign is very promising compared to the state of the art.

ACKNOWLEDGMENT

This work has been performed in the framework of the ICT project ICT-248894 WHERE2, which is partly funded by the European Union.

  III. TECHNIQUES OF TOA ESTIMATION BASED ON UWB SIGNALS This section presents the different techniques for estimating TOA from the UWB signals. These techniques are numerated from 1 to 4 as follows: • T1: Setting a threshold above the noise floor • T2: Setting a threshold above the cumulative noise floor • T3: Dichotomous left interval selection • T4: Thresholded dichotomous left interval selection A. T1: Setting a threshold above the noise floor

Fig. 1 .

 1 Fig. 1. T1 -Setting a threshold above the noise floor-: the threshold must be fairly chosen in order to avoid under-and over-estimation of the TOA.

Fig. 3 .

 3 Fig. 3. T3 -Dichotomous left interval selection-: the technique estimates the TOA as the time of arrival of the first path among Nmax strongest paths determined using a dichotomous algorithm.

Algorithm 2 1 ←Fig. 4 .

 214 Fig. 4. T4 -Thresholded dichotomous left interval selection-: the technique searches the strongest paths in a predefined window going from zero to the strongest path.

Fig. 5 .

 5 Fig. 5. Overall measurement chain used to perform UWB measurements.

Fig. 6 .

 6 Fig.6. UWB impulse feeding the Tx antennas.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Rx and Tx locations defined in the SIRADEL environment.

Fig. 9 .

 9 Fig.9. Tuning of different ranging techniques using UWB measurements: the key-parameters are chosen to best fitting the measurements.

Fig. 10 .

 10 Fig. 10. Average Ranging error wrt. LQI for different techniques.

Fig. 11 .

 11 Fig. 11. CDF of ranging error performed by the four techniques for an LQI ≥ 10dB.

Fig. 12 .

 12 Fig. 12. Mapping of ranging error obtained with the T4 technique for the different receivers. The figure highlights the effect of metallic cupboards on the ranging accuracy.

TABLE I STATISTICAL

 I TOA BASED RANGING MODELS EXTRACTED FROM UWB INDOOR MEASUREMENTS CAMPAIGN FOR LQI> 10DB.TableIIpresents the ranging accuracy for different visibility conditions. The table reveals that the four techniques give the same performances in LOS conditions. This is obvious because the direct path (the strongest one) is easily distinguished in LOS conditions. In these conditions the ranging precision is up to 8cm. However, in the NLOS and NLOS 2 conditions which are the most common situations inside a building with furnitures, we can see different performances for different techniques.

	Technique Mean(m) STD(m)
	T1	0.22	0.44
	T2	0.33	0.55
	T3	0.36	0.64
	T4	0.13	0.50


Bernard Uguen
email: bernard.uguen@univ-rennes1.fr

Nicolas Amiot
email: nicolas.amiot@univ-rennes1.fr

Mohamed Laaraiedh
email: mohamed.laaraiedh@univ-rennes1.fr

Exploiting the Graph Description of Indoor Layout for Ray Persistency Modeling in Moving Channel

This paper proposes a technique based on description of the layout using different graphs to obtain a ray signature which is associated with path persistency observed for small displacement of radio link termination of a mobile channel. The algorithm used to derive the signature from the layout graph description and the position of Tx and Rx is described. The mathematical relationship between signature and rays is also presented. A comparison of simulated and measured IR-UWB channel impulse response over a pedestrian trajectory is shown.

I. INTRODUCTION

There is today a significant research effort in localization and tracking community for measuring and modeling the features of the channel [START_REF] Chong | A novel wideband dynamic directional indoor channel model based on a markov process[END_REF] for indoor human mobility. In particular, there is a growing interest for introducing channel modeling tools which respect spatial coherence of the channel w.r.t human mobility. For example semi deterministic model derived from the statistical model IEEE 802.15.4a have been proposed as e.g in [START_REF] Youssef | Dynamic ir-uwb channel model preserving ieee 802.15.4a statistics over large-scale trajectories[END_REF].

The propagation channel parameters are time varying due to the motion of the extremities of the radio link or because of motion of human or objects in the propagation environment. The human motion introduces small scale and large scale variations. This paper focuses on large scale variations that remain coherent over significant distances.

Path persistency has been defined in [START_REF] Chong | A novel wideband dynamic directional indoor channel model based on a markov process[END_REF] as the evolution of a particular path of the channel impulse response which exhibits a differential change of a given feature in accordance with its differential motion. In [START_REF] Akgul | Path persistency for high precision ranging in different building architectures[END_REF] the path persistency has been exploited in the context of indoor positioning systems employing high bandwidth time-of-arrival methods.

Otherwise, the graph structure has proven its relevance in describing the inner nature of the propagation channel. Stochastic propagation graphs have been introduced and developed in [START_REF] Pedersen | Radio channel modelling using stochastic propagation graphs[END_REF] for describing the reverberant nature of the channel and for explaining the exponential decay of the Power Delay Profile (PDP) as a function of delay.

This contribution aims at exploiting graph structure in order to determine in the channel impulse response, the part which remains persistent when the terminal is moving and can thus be exploited as a valuable observable for positioning and tracking.

All site specific tools have their own approach to describe the layout. This paper presents an approach based on a graph description of the layout which allows to capture the path persistency under the form of what is here defined as ray signature. The ray signature can remain stationary over short distances and consequently its knowledge can be exploited for accelerating the determination of rays when modeling the channel impulse response over pedestrian trajectories.

The first section introduces the proposed graph description of the layout suitable for the determination of ray signatures. The second section introduces the concept of ray signatures and describes how to derive the signature from the layout graphs. The third section provides the mathematical relationship between a ray and its signature which is used in an incremental ray tracing tool. The last section presents a comparison between channel impulse responses measured and simulated along a synthetic pedestrian trajectory in an office environment.

II. MULTIGRAPH DESCRIPTION OF THE LAYOUT

The data structure of the indoor layout is described through the definition of the following graphs.

• The structure graph G s • The visibility graph G v • The topological graph G t • The graph of rooms G r The adopted multi graph description contains meta information from the layout which can be exploited for both incremental identification of rays and simulation of indoor pedestrian mobility.

A. The structure graph G s

The first graph describing the layout is G s (V s , E s ). V s is the set of nodes and E s is the set of edges. This is illustrated in figure 1 for 4 vertices and 4 walls room. In this example:

V s = {-1, -2, -3, -4, 1, 2, 3, 4} card(V s ) = 8
Vertices can be associated with a diffraction interaction whereas the edge (positive index) are associated either with transmission or diffraction.

• A positive node (wall) is necessarily connected to a negative node (vertex)

• For a vertex to be a potential diffracting node, its degree has to be lower or equal to 2 Each node index allows to retrieve the associated constitutive properties of the wall.

B. The visibility graph G v

The second defined graph of the layout is the visibility graph G v . Nodes of this graph are the same as those of G s . Only edges are defined differently from G s . Two nodes are connected if they share an "optical" visibility relationship. A wall (id > 0) can be connected to a vertex (id < 0). Optical visibility means that the electromagnetic energy can flow from one node to another. The G v graph structure is sparse and well adapted to describe visibility relationships between layout and edges.

C. The topological (cycles) graph G t

The third defined graph of the Layout is the topological graph G t . It results from the determination of all cycles of the graph G s . G t contains a valuable topological information. Each cycle contains various attributes as for example the set of nodes and edges of the cycle. This information is exploited once the position of T x or R x is known in order to connect directly leaves of G v which are associated with a given cycle. This data organization accelerates search of walls and vertices to connect with. Graph G t is shown in Figure 4. The fourth defined graph is the graph of rooms G r . It is the subgraph of G t retaining only cycles which possess at least one door. An example of a graph of rooms is shown in Figure 5. This graph is used for fast extraction of the list of edges which belongs to a given room. This graph can also been used to build a state machine for inter-room mobility of pedestrian agents.

III. DEFINING A RAY SIGNATURE

A. Definition

Let first define a ray with N i interactions as an ordered list of N i + 2 points starting at t x and ending at r x .

R = {t x , p 0 , • • • , p Ni-1 , r x } = {t x , P, r x } (1)
where t x and r x are points associated with transmitter and receiver and the ordered list of N i interaction points is

P = {p 0 , • • • , p Ni-1 }.
The signature of R is defined as the sequence of structure ids of P. The structure id of a point is simply the identification number either of the diffraction point (id < 0) ot the segment number (id > 0), this is directly a node number from graph G s or G v defined previously. Id(p) is a function which returns the layout index number of p.

S(R) = S(P) = {Id(p 0 ), • • • , Id(p Ni-1 )} (2)
Conventionally, the signature of the LOS path is the empty set, S({t x , r x }) = ∅. Notice that when at least one ending point of the radio link is moving, all the points of P are moving correspondingly. This is not the case of the signature S which can remain stationary in the vicinity region of the moving point.

B. Algorithm to Determine Signature from G v

In a first step the algorithm seeks for the nodes V tx of G s which are visible from T x , and the set of nodes V rx of G s which are visible both from R x . This is a fast operation if the information of the room numbers where are lying T x and R x are maintained available along the simulated trajectory. The second step consists in exploiting the 2 subsets V tx and V rx for determining N t × N r first order signatures where card(V tx ) = N t and card(V rx ) = N r . The algorithm exploits the Dijkstra algorithm to determine the shortest path between 2 nodes in the graph G v . If a keyhole is detected, i.e a central node which is present in many discovered signatures, it is possible to remove this node and to iterate the algorithm in order to get new signatures which explore less direct paths. In scenarios where one extremity is moving continuously along a trajectory the set of signature L calculated at one point can be exploited for determining rays in its vicinity. L can be incrementally updated. Figure 6 and Algorithm 1 describe the principle of rays signatures determination.

Algorithm 1 Determination of signatures list Require:

t x ,r x Require: G s ,G v ,G r L = ∅ Initialize a list of signatures V t ← get visible nodes(G r , t x ) V r ← get visible nodes(G r , r x )
for nt ∈ V t do for nr ∈ V t do S it,ir = Dijkstra(G v , n t , n r ) L ← L.append(S it,ir ) end for end for

IV. RAY DETERMINATION FROM RAY SIGNATURE

The determination of a ray from its signature is a two steps process. The fist step consists in calculating a set of intermediate points starting from the transmitter. Once calculated those intermediate points can be used for any receiver position with the same signature. The signature can be either valid or not valid for a given receiver depending on its coordinates.

A. Determination of Image points

The transmitter is defined as

t x = [x t , y t ] T (3)
We consider a signature of length N which can contain three types of interaction: diffraction (D), reflection (R), transmission (T). From this signature, 2 ordered lists of points are retrieved.

p a = [a 0 , ..., a N -1 ] (4)
p b = [b 0 , ..., b N -1 ] (5)
a k = [x Ak , y Ak ] T , b k = [x Bk , y Bk ] T (6)
In the case of a diffraction the point appears identical in each list otherwise p a and p b contains respectively tail points and head points of the signature segments.

The sequence of intermediate points can be determined from the knowledge of the transmitter point, the sequence of segments and also importantly the type of interaction (R|T |D). This sequence of intermediate points is:

m = [m 0 , ..., m N -1 ] (7)
with:

m k = [x k , y k ] T (8)
Depending on the nature of the interaction the intermediate point is either the image of the current point w.r.t the segment (Reflection), the current point itself (Transmission), the diffraction (interaction) point itself (Diffraction).

m 0 depends on the type of the first interaction as:

• (R): m 0 = S 0 t x + v 0 • (T): m 0 = t x • (
D): m 0 = a 0 and similarly, m k depends on the type of the k th interaction:

• (R): m k = S k m k-1 + v k • (T): m k = m k-1 • (D): m k = a k
where S k (reflection matrix) and v k are defined as:

S k = a k -b k -b k -a k (9)
the translation vector is defined as

v k = c k b k (10)
with

a k = (x Ak -x Bk ) 2 -(y Ak -y Bk ) 2 (x Ak -x Bk ) 2 +(y Ak -y Bk ) 2 (11) b k = 2(x Bk -x Ak )(y Ak -y Bk ) (x Ak -x Bk ) 2 +(y Ak -y Bk ) 2 (12) c k = 2 x Ak (y Ak -y Bk ) 2 +y Ak (x Bk -x Ak )(y Ak -y Bk ) (x Ak -x Bk ) 2 +(y Ak -y Bk ) 2 (13) d k = 2 x Ak (y Ak -y Bk )(x Bk -x Ak )+y Ak (x Bk -x Ak ) 2 (x Ak -x Bk ) 2 +(y Ak -y Bk ) 2 (14)
The coordinates of intermediates points are obtained by solving Am = y (15)

A =       I 2 {-S 1 |O 2 |O 2 } I 2 . . . . . . {-S N -1 |O 2 |O 2 } I 2       (16) y =        {S 0 t x + v 0 |t x }|a 0 } {v 1 |z 2 |d 1 } . . . {v N-1 |z 2 |d N -1 }        (17)
where I 2 and O 2 are respectively identity matrix and zero matrix of dimension 2, z 2 is 2 × 1 zero column vector. The notation {R|T |D} stands for the possible matrix entries depending on the interaction type.

B. Determination of interaction points

The receiver is given by:

r x = [x r , y r ] T (18)
Interaction points are points which belong to the layout segments. They are obtained from the intersection between the segments indicated by the signature and the segments joining successively the previously obtained intermediate points m. The unknown interaction points are

p k = [x ′ k , y ′ k ] T (19)
By introducing a parameterisation on both the unknown 4× 1 column vector is:

x ′ k = p T k , Γ T k T (20)
with

Γ k = [α k , β k ] T (21)
Starting from the receiver and joining the last intermediate point m N -1

p 0 + α 0 (r x -m N -1 ) = r x (22) p 0 + β 0 (a N -1 -b N -1 ) = a N -1 (23)
We solve successively the following linear systems

T 0 x ′ 0 = y ′ 0 (24)
with:

T 0 = I 2 r x -m N -1 0 2×1 I 2 0 2×1 a N -1 -b N -1 (25)
and

y ′ 0 = r x T , a T N -1 T ( 26
)
For determination of interaction point p k it proceeds identically taking advantage of the knowledge of point p k-1 : This takes the forme of the linear equation:

p k + α k (p k-1 -m N -(k+1) ) = p k-1 (27) p k + β k (a N -(k+1) -b N -(k+1) ) = a N -(k+1) (28)
T k x ′ k = y ′ k (29)
with

T k = I 2 p k-1 -m N -(k+1) 0 2×1 I 2 0 2×1 a N -(k+1) -b N -(k+1) (30) and y
′ k = p T k-1 , a T N -(k+1) T (31)
The parameterization of the signature segment β k plays a very important role, if 0 < β k < 1 the interaction point p k is valid and the calculation can proceed otherwise the interaction point is out of the segment and the signature is rejected for the current receiver coordinates.

As an example Figure 7 shows a set of rays (in blue) which are all sharing the same signature, which contains 4 reflections. T x is static and is placed above-left the first segment.

The signature for all blue rays is S = {1, 2, 3, 4}. The figure has been produced by drawing randomly R x in the plane. There exists a validity region for R x for a ray being associated with the signature. It means that if one termination of the signature is static (e.g. an access point), either T x or R x , one can associate the couple (access point, signature) to a validity region where the signature is associated to valid rays. One other interesting features of ray signature which is illustrated in Figure 8, is that it is possible to derive higher order signatures from a lower order signature. The order of a signature being defined as the number of interactions N i involved in the signature. For example if we have a signature of order 4: S 0 = {1, 2, 3, 4} corresponding for example to the transmission through of 4 successive walls placed between T x and R x , one can derive those 3 new signatures of order 6, S 1 = {1, 2, 1, 2, 3, 4}, S 2 = {1, 2, 3, 2, 3, 4}, S 3 = {1, 2, 3, 4, 3, 4}

V. RELATING RAY PERSISTENCY TO RAY SIGNATURE Figure 9 presents the synthetic trajectory selected on the available measured link of an IR-UWB measurement campaign realized in the FP7-WHERE project [START_REF]Deliverable 4.1: Measurements of location-dependent channel features[END_REF]. Each trans-

VI. CONCLUSION

This paper has presented a technique for fast retrieving the ray signature from a graph description of the indoor layout. This signature is a precursor of rays and can be exploited to save computational time when evaluating the channel impulse response for example when studying indoor pedestrian localization or tracking scenario. In the last section ray persistency has been well observed in measurements data and well retrieved using an incremental ray tracing tool. A current line of investigation in tracking applications is to consider how to identify a ray signature from a sequential accumulation of channel impulse responses. This should be helpful in the context of map aided positioning and tracking scenarios.

Figure 2

 2 Figure 2 shows the G s graph of an indoor environment. Only edges are displayed, black lines are associated with doors and windows.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Gs representation of a 4 walls layout (nodes in red: vertices, nodes in blue: walls)

Fig. 3 .

 3 Fig. 3. Visibility graph Gv

Fig. 4 .

 4 Fig. 4. Topological (cycles) graph Gt

Fig. 5 .

 5 Fig. 5. Graph of rooms Gr

Fig. 6 .

 6 Fig. 6. Principle of signature determination, nodes subset Vtx (left) and Vrx (right)

Fig. 7 .

 7 Fig. 7. Rays in blue share the same signature

Fig. 8 .

 8 Fig. 8. Illustration of deriving higher order signatures from a signature containing at least a double transmission (TT)

Fig. 9 .

 9 Fig. 9. Measured CIR along indoor selected trajectory, (red points) 4 Tx (1 is bottom right), (blue points) 81 Rx (0 right -81 right)

Fig. 10 .

 10 Fig. 10. Measured CIR along an indoor selected trajectory

ACKNOWLEDGMENT

The work has been performed in the FP7 project ICT-248894 WHERE2, which is funded by the European Union


V La Tosa

B Denis

S Bories
email: serge.bories@cea.fr

B Uguen

Impact of Antennas on the Anchor-less Indoor Localization of a Static IR-UWB Pair

Keywords: Anchor-less Localization, Context-Awareness, Impulse Radio, Indoor Environments Characterization, Ultra Wide Band Antennas, Wireless Sensor Networks

This paper investigates the impact of realistic antennas on joint anchor-less localization and indoor characterization based on Impulse Radio (IR) Ultra Wideband (UWB) communications. In this frame, the Maximum Averaged Likelihood (MAL) algorithm and its extended version are considered, both relying on a tree approach consisting in two stages. The first part of the process exploits the cross-correlation between received and locally predicted paths and it is the same for both algorithms. The second stage calculates the averaged likelihood of measured path parameters obtained in the previous step, but different measurements are used for MAL and extended MAL (eMAL), as in the first case only the Angle of Incidence (AoI) and the Time of Arrival (ToA) are considered. Additionally, the eMAL tree algorithm also accounts for two couples of Angles of Departure (AoDs) and Angles of Arrival (AoAs). The estimation errors of both nodes coordinates and room dimension obtained with the two algorithms are compared for three realistic UWB antennas. Finally, the remaining algorithm-independent ambiguities (i.e. resulting from scenario and geometry) are discussed.

I. INTRODUCTION

For the last years, new emerging needs have caused an increasing interest in Wireless Sensor Networks. Indeed, multiple applications have been conceived for future daily life, for instance dealing with automation in indoor environments (e.g. [START_REF] Cook | Smart Environments: Technology, Protocols and Applications[END_REF]). In this framework, the intrinsic fine temporal resolution and the low power consumption make the Impulse Radio (IR) -Ultra Wide Band (UWB) technology (e.g. [START_REF] Kaiser | UWB communication systems[END_REF]) a relevant solution for joint short-range communication and localization.

Indoor localization based on reference nodes (e.g. [START_REF] Gezici | Localization via ultrawideband radios: a look at positioning aspects for future sensor networks[END_REF]) is one of the most successful and studied exploitation of IR-UWB, but joint opportunistic anchor-less localization and basic indoor environment characterization have been also investigated. The two main contributions in this field are the Indoor Mapping technique (e.g. [START_REF] Guo | 2D indoor mapping and locationsensing using an impulse radio network[END_REF]) and a radar-like channel sounding method called Imaging (e.g. [START_REF] Zetik | Modified cross-correlation back projection for UWB imaging: numerical examples[END_REF], [START_REF] Seitz | UWB feature localization for imaging[END_REF]). In robotics, several solutions have been proposed for the Simultaneous Localization and Mapping (SLAM) problem (e.g. [START_REF] Chang | P-SLAM: simultaneous localization and mapping with Environmental-Structure prediction[END_REF]), exploiting embedded cameras or laser rangers. Assuming a Conical Monopole Antenna (CMA) (e.g. [9]) at both transmitter and receiver, the previous work [START_REF] La Tosa | Maximum averaged likelihood estimation tree for Anchor-Less localization exploiting IR-UWB multipaths[END_REF] presented the Maximum Averaged Likelihood (MAL) tree algorithm, exploiting Angles of Incidence (AoIs) (i.e. on the reflecting surface) and Times of Arrival (ToAs) (i.e. taken with respect to the receiver local reference) measurements.

This paper presents an extension of MAL algorithm and shows the results of anchor-less positioning and basic room characterization obtained with three realistic UWB antennas increasingly portable (i.e. with respect to dimensions and weight). This work has two main objectives: assessing if the knowledge of Angle of Departure (AoD) and Angle of Arrival (AoA) can improve MAL performances and understand the relationship between algorithms and antennas radiation diversity.

The paper is organized as follows. Section II describes the multipath model, the related assumptions and the chosen scenario. Section III shows the formalism of the averaged likelihood approach. Then, Section IV presents the proposed algorithms, while Section V discusses their limits and suggests some possible solutions and Section VI surveys the three real antennas. Finally, Section VII shows algorithm performances in both localization and basic environment characterization and Section VIII concludes the paper.

II. SIGNAL MODEL AND SCENARIO

In the context of IR-UWB indoor communications, the tension signal ρ(t) at the receiver is generally described as a sum of paths, resulting from N int electromagnetic interactions:

ρ(t) = Nint n=0 r n (t -τ n ) + η(t) (1)
where r n (t) is the n-th filtered received path, η(t) is the noise affecting the communication filtered in the transmitted signal bandwidth and τ n is the n-th path delay. The deterministic model described in [START_REF] Tchoffo-Talom | A sitespecific tool for UWB channel modeling[END_REF] is assumed for a generic received tension in frequency domain R(f ). The generic path r n (t) can be obtained from R(f ) by an inverse Fourier transform.

For the sake of simplicity, only single-bounce reflections in the 2D plane are considered and a Line Of Sight (LOS) channel is assumed. The simplified 2D indoor scenario is a rectangular room which walls are made of brick with a known thickness (e.g. 7 cm). Therefore, referring to Figure 1, the largest room dimension is defined as D x and the transmitter is materialized as a grey spot while the receiver a dark grey spot, with coordinates (x t ,y t ) and (x r ,y r ) respectively.

III. PATH PARAMETERS MODEL

Four quantities will be associated to the n-th reflected path: AoD φ t,n , AoA φ r,n , AoI θ n and ToA τ n , the latter taken with respect to a local time reference. As a general remark, note that variables numbering is the same as that of interacting walls numbering, where walls are arbitrary numbered anticlockwise. As an example, θ 2 , φ t,2 , φ r,2 and τ 2 are respectively the AoI, AoD, AoA and ToA of the path that has been reflected on wall 2 (i.e. the wall on the right on Figure 1). As the direct path is not associated with a wall interaction, the corresponding ToA will be noted as τ 0 .

As in [START_REF] La Tosa | Maximum averaged likelihood estimation tree for Anchor-Less localization exploiting IR-UWB multipaths[END_REF], a Normal measurement error model will be assumed in the following for AoI θ n and ToAs τ n , with standard deviations σ θ and σ τ respectively. Therefore, according to the independence assumption of measurements for each n (e.g.

as in [START_REF] La Tosa | Maximum averaged likelihood estimation tree for Anchor-Less localization exploiting IR-UWB multipaths[END_REF]), the joint truncated Probability Density Function (PDF) f Θ1,Θ2,Θ3,Θ4 of θ 1 , θ 2 , θ 3 and θ 4 is the product of four independent truncated Normal densities, as follows:

f Θ1,Θ2,Θ3,Θ4 (θ 1 , θ 2 , θ 3 , θ 4 ) = 4 n=1 f Θn (θ n ) (2)
where

f Θn (θ n ) = exp -1 2 θn-µ θn σ θ 2 erf π 2 -µ θn √ 2σ θ -erf -µ θn √ 2σ θ (3)
and the normalization factor accounts for the truncation on interval 0, π 2 . Let us define the n-th ToA difference ∆τ n = τ n+1 -τ n , then the joint PDF f ∆T0,∆T1,∆T2,∆T3 of differences ∆τ 0 , ∆τ 1 , ∆τ 2 and ∆τ 3 is described by:

f ∆T0,∆T1,∆T2,∆T3 (∆τ 0 , ∆τ 1 , ∆τ 2 , ∆τ 3 ) = 1 (2π) 2 √ 5στ exp -1 2 ∆τ -µ ∆τ T D -1 ∆τ -µ ∆τ ( 4
)
where D is the covariance matrix written as follows:

D =     2σ 2 τ σ 2 τ 0 0 σ 2 τ 2σ 2 τ σ 2 τ 0 0 σ 2 τ 2σ 2 τ σ 2 τ 0 0 σ 2 τ 2σ 2 τ     (5)
Finally, like in [START_REF] La Tosa | Maximum averaged likelihood estimation tree for Anchor-Less localization exploiting IR-UWB multipaths[END_REF], the noise affecting range measurements is assumed to have a standard deviation σ d = cσ τ and follows the Normal PDF f D (d) below:

f D (d) = 1 √ 2πσ d exp - 1 2 d -µ d σ d 2 (6)
where µ d = (x r -x t ) 2 + (y r -y t ) 2 and c is light velocity.

The extended algorithm also considers φ t,n and φ r,n measurements, in order to assess if their approximate knowledge can reduce anchor-less positioning error in comparison with what obtained with MAL and presented in [START_REF] La Tosa | Maximum averaged likelihood estimation tree for Anchor-Less localization exploiting IR-UWB multipaths[END_REF]. Nevertheless, because of the unknown orientation of the peers, φ t,n and φ r,n can not be written as functions of peers coordinates. Indeed, the simple knowledge of directions φ t,n and φ r,n can not directly contribute to nodes anchor-less positioning although the difference of AoDs and AoAs does. In this context, AoDs differences will be called α and AoAs differences β. In the particular case of differences calculated with respect to direct path AoD φ t,0 and AoA φ r,0 , the following quantities can be defined:

α n,0 = φ t,n -φ t,0 β n,0 = φ r,n -φ r,0 (7)
where n ∈ {1, . . . , 4}. Therefore, using the simple geometrical equations linking α n,0 and β n,0 to nodes coordinates and room dimension D x is expected to improve estimation performances when these measurements are considered in the likelihood approach. Moreover, measurements θ n , φ t,n , φ r,n and τ n will be considered independent from each other and for each n.

Under the assumption of φ t,n and φ r,n as Normal independent measurements both characterized by standard deviations σ φ , the marginal PDFs f An,0 of α n,0 and f Bn,0 of β n,0 can be simply written as follows:

f An,0 (α n,0 ) = 1 √ π2σ φ exp -1 2 αn,0-µα n,0 √ 2σ φ 2 (8) f Bn,0 (β n,0 ) = 1 √ π2σ φ exp -1 2 βn,0-µ β n,0 √ 2σ φ 2 (9)
As an example, true values µ α1,0 and µ β1,0 of α 1,0 and β 1,0 can be respectively written as follows: [START_REF] Tchoffo-Talom | A sitespecific tool for UWB channel modeling[END_REF] showing explicitly the dependence of true values and nodes coordinates. An illustration of α 1,0 and β 1,0 is shown on Figure 1. IV. PROPOSED ALGORITHMS In the following two algorithms will be described and then compared by simulations, namely the MAL and a modified version called extended MAL (eMAL). Both algorithms rely on an estimation tree and use a path-by-path approach, which seems a natural choice given the intrinsic separability of IR-UWB received signal. As a common prior stage, a database containing the expected received paths in the time domain is synthesized once and for all, according to the deterministic model described in [START_REF] La Tosa | A preliminary investigation on angular parameters estimation in a simplified IR-UWB indoor multipath scenario[END_REF]. Indeed, the AoI domain [0, π 2 ] is considered as made up of N θ clusters indexing the waveforms database, as in [START_REF] La Tosa | A preliminary investigation on angular parameters estimation in a simplified IR-UWB indoor multipath scenario[END_REF].

A. Cross-correlation Stage

The cross-correlation between successively detected paths and the synthesized waveforms of the database is calculated, in order to exploit the intrinsic radiation diversity of UWB antennas. This stage enables to identify a set of alike waveforms and provides, for each of them, the corresponding measurements φ t , φ r , θ and τ . In order to reduce the overall complexity, the algorithm lets survive only the subset of the most correlated waveforms for each detected path. Like in [START_REF] La Tosa | Maximum averaged likelihood estimation tree for Anchor-Less localization exploiting IR-UWB multipaths[END_REF], ξ CC represents the percentage of waveforms rejected because of their lowest cross-correlation value. The rejection percentage 0 < ξ CC < 1 is a priori set according to the observed deformation of the received waveforms generated by antennas.

1) MAL policy: For each detected path identified as a reflected path, only a quartet φ t , φ r , θ, τ is chosen. Indeed, for a given AoI θ, the chosen couple (φ t , φ r ) corresponds to the maximum calculated cross-correlation value. So, recalling that N θ is the number of AoIs indexing the local database, the rejection factor ξ CC is applied to the N θ chosen quartets.

2) eMAL policy: For each reflected path detected in the received signal, up to 3 possible quartets φ t , φ r , θ, τ can be chosen. Given an AoI θ, the couples of selected φ t , φ r correspond to the 1% most correlated of waveforms, for which the mutual Euclidean distance in the 2D Cartesian system of coordinates (φ t , φ r ) is bigger than √ 2σ φ . Therefore, up to 3N θ couples make up the set on which a rejection factor ξ CC is applied.

B. Averaged Likelihood Stage

In order to limit the growth of the estimation tree, the path parameters surviving to the previous stage undergo a further rejection stage, based on the Maximum Averaged Likelihood.

Like in [START_REF] La Tosa | Maximum averaged likelihood estimation tree for Anchor-Less localization exploiting IR-UWB multipaths[END_REF], when n reflected paths has been detected at the l-th tree layer, the maximum AL max of the Averaged Likelihood Function (ALF) Ω n is evaluated for the l quartets of path parameters available on the current tree branch. Note that l = n+1 in the LOS case and l = n otherwise. Indeed, at the l-th tree layer, a branch corresponds to the first l detected path parameters, as follows:

{(φ t,j , φ r,j , θ j , τ j ) : j ∈ {1, . . . , l}} (11)
In the following, according to the likelihood approach, these path parameters will be considered as measurements of true path parameters. Like in [START_REF] La Tosa | Maximum averaged likelihood estimation tree for Anchor-Less localization exploiting IR-UWB multipaths[END_REF], Ω n is the mixture of likelihood functions accounting for n detected reflected paths and all possible labels mappings, weighting equally each possible label configuration. Indeed, the detection of a path does not on its own enable to estimate the path label (i.e. the numbering corresponding to the model described in Section III). By contrast, the mixture Ω n is a solution to the label mapping ambiguity above, as the component corresponding to the right label mapping is expected to dominate remaining components. Then, at each tree layer, a fixed number of candidates is eliminated because of their lowest AL max , with a rejection percentage 0 < δ LT,l < 1. For instance, δ LT,l = 0.70 means that, at the l-th layer, only the 30% of candidates having the highest values of AL max (i.e. among these that passed the cross-correlation rejection stage) are enabled to join the (l + 1)-th layer. Thus, all the surviving waveforms are treated in parallel, subtracted respectively from the received multipath signal when the first path has been detected and from the previous cleaned received signal otherwise. Therefore, at the end of this stage, N surv,l "cleaned" received signals and N surv,l sets of measurements φ t , φ r , θ and τ are available.

1) MAL policy: According to [START_REF] La Tosa | Maximum averaged likelihood estimation tree for Anchor-Less localization exploiting IR-UWB multipaths[END_REF], only the subset made up of N surv,l measurements (θ, τ ) is considered. As an example of ALF, Ω 1,LOS (i.e. used when n=1 reflected path has been detected in addition to direct path) can be written as follows:

Ω 1,LOS = 1 4 f D (d) f Θ1 (θ (1) )f ∆T1,0 (∆τ (1,0) )+ f Θ2 (θ (1) )f ∆T2,0 (∆τ (1,0) )+ f Θ3 (θ (1) )f ∆T3,0 (∆τ (1,0) )+ f Θ4 (θ (1) )f ∆T4,0 (∆τ (1,0) ) (12)
where ∆τ (u,v) is the ToA difference between the u-th received path ToA τ (u) and the v-th received path ToA τ (v) , with a PDF f ∆Tu,v (∆τ (u,v) ) defined as follows:

f ∆Tu,v (∆τ (u,v) ) = 1 2 √ πσ τ exp - ∆τ u,v -µ ∆τu,v 2σ τ 2 (13)
where ∆τ u,v = τ u -τ v and µ ∆τu,v = µ τu -µ τv , with u ∈ {1, . . . , 4} and v ∈ {0, . . . , 3} .

Given n reflected paths, the number of likelihood functions making up the mixture Ω n is 4! (4-n)! . As discussed in [START_REF] La Tosa | Maximum averaged likelihood estimation tree for Anchor-Less localization exploiting IR-UWB multipaths[END_REF], by construction, the MAL algorithm can not solve transmitter/receiver (Tx/Rx) ambiguity on its own.

2) eMAL policy: The eMAL algorithm tries to improve MAL performances by integrating two more measurements α n,0 and β n,0 in the ALFs, as defined in Section III. The main difficulty is that measured φ can not be a priori distinguished as corresponding to transmitter or receiver (i.e. as φ t or φ r ), because of the reciprocity of the propagation channel (i.e. Tx/Rx ambiguity). Moreover, as θ and τ , also φ measurements suffer from label mapping ambiguity. If the differences [START_REF] Chang | P-SLAM: simultaneous localization and mapping with Environmental-Structure prediction[END_REF] for all the n received paths were considered, the algorithm should manage 2 n+1 possibilities due to the Tx/Rx ambiguity, which would make Ω n maximization more complex. Therefore, for each Ω n component (i.e. paths combination), only one α and β is integrated into [START_REF] Bahreyni | A resonant micromachined magnetic field sensor[END_REF]. Indeed, let (q 1 , . . ., q n ) be the paths label combination of cardinality n for a given component of Ω n and q = min{q 1 , . . . , q n }, then measurements α q,0 and β q,0 are included in the considered Ω n component.

As measured φ can not be identified as AoDs or AoAs, the arrays of latter angles corresponding to the path labelled with q and to the direct path will be noted Φ q = φ q,1 φ q,2 and Φ 0 = φ 0,1 φ 0,2 respectively. Finally, let us define the set of quartets P playing as permutation indexes as follows:

P = {(1, 1, 2, 2), (1, 2, 2, 1), (2, 1, 1, 2), (2, 2, 1, 1)}
then, according to the independence hypothesis discussed in Section III, Ω 1,LOS can be written as in [START_REF] Roblin | Ultra compressed parametric modeling for symmetric or pseudo-symmetric UWB antenna[END_REF]. Note that eMAL Ω n are made by 4 4! (4-n)! terms, which means 2 2 = 4 times more than corresponding MAL Ω n . Indeed, the uniform probability of Tx/Rx role is integrated in eMAL Ω n , in addition to the uniform probability of mapping between detected paths and model paths already present in MAL Ω n . All the φ permutations (i.e Tx/Rx role) are considered in the eMAL version of Ω n , including the good one and the opposite of the good one, the latter inverting AoDs and AoAs roles, which does not solve Tx/Rx ambiguity as for MAL approach. Nevertheless, the additional measurements are expected to be rewarded with an improvement in estimation performances when a suitable antenna is used.

V. REMAINING AMBIGUITIES A. Mirror Ambiguity

The mirror ambiguity can be defined as the lack of capability in distinguishing the right geometrical configuration from other configurations obtained as mirror images of the right one. In the 2D scenario on Figure 1, the possible mirrors are the axis of x and the axis of y. Assuming that static peers do not have an a priori knowledge of the indoor environment (e.g. a map of the building) and are not equipped with absolute reference estimation devices (e.g. [START_REF] Bahreyni | A resonant micromachined magnetic field sensor[END_REF]), a mirror ambiguity in positioning nodes will always exist whatever the algorithm is (e.g. [START_REF] Guo | 2D indoor mapping and locationsensing using an impulse radio network[END_REF]). This resilient 4-image mirror ambiguity is represented on Figure 2.

B. Transmitter/Receiver Ambiguity

Given two 2D coordinates, the Tx/Rx ambiguity can be defined as the lack of capability in assessing which of the two is the transmitter and which is the receiver. As a possible solution, the Tx/Rx ambiguity is expected to be solved out with the mobility of one of the two nodes. Indeed, the spatial coherence between successively observed signals should be the key factor in avoiding Tx/Rx ambiguity. Another possible method could consist in using two different antennas for the two nodes, which should break the symmetry in AoDs and AoAs measurements.

The cumulative effect of mirror and Tx/Rx ambiguities makes eight possible configurations not distinguishable one from each other, as each of the four possibilities represented on Figure 2 must be multiplied by two different transmission and receiver roles.

Ω 1,LOS = 1 4 f D (d) f Θ 1 (θ (1) )f ∆T 1,0 (∆τ (1,0) ) (i 1 ,i 2 ,i 3 ,i 4 )∈P f A 1,0 (φ (1),i 1 -φ (0),i 2 )f B 1,0 (φ (1),i 3 -φ (0),i 4 )+ f Θ 2 (θ (1) )f ∆T 2,0 (∆τ (1,0) ) (i 1 ,i 2 ,i 3 ,i 4 )∈P f A 2,0 (φ (1),i 1 -φ (0),i 2 )f B 2,0 (φ (1),i 3 -φ (0),i 4 )+ f Θ 3 (θ (1) )f ∆T 3,0 (∆τ (1,0) ) (i 1 ,i 2 ,i 3 ,i 4 )∈P f A 3,0 (φ (1),i 1 -φ (0),i 2 )f B 3,0 (φ (1),i 3 -φ (0),i 4 )+ f Θ 4 (θ (1) )f ∆T 4,0 (∆τ (1,0) ) (i 1 ,i 2 ,i 3 ,i 4 )∈P f A 4,0 (φ (1),i 1 -φ (0),i 2 )f B 4,0 (φ (1),i 3 -φ (0),i 4 ) (14)

VI. ANTENNAS

Both described algorithms rely on the capability of locally reproducing the expected received waveforms but eMAL also accounts for the radiation spatial diversity of antennas in order to estimate AoDs and AoAs. Several works (e.g. [START_REF] Allen | Time-domain antenna characterizations[END_REF], [START_REF] Roblin | Ultra compressed parametric modeling for symmetric or pseudo-symmetric UWB antenna[END_REF]) investigated on appropriate UWB antenna indicators. Two of them seem to critically impact the performances of the described algorithms. Indeed, the space diversity of UWB antennas has been quantified in a distortion factor that takes into account the cross-correlation between transmitted/received pulses, as a function of the radiation directions. Moreover, the Mean Realized Gain (MRG) that is the antenna gain integrated over the signal bandwidth, should be constant with respect to radiating directions. Indeed, if the overall gain for each direction is almost constant, all paths are expected to be received.

A. Conical Monopole Antenna

The Conical Monopole Antenna (CMA) 118/A is the antenna shown on Figure 3. The omni-directional measured radiation in azimuth, reported on Figure 4, is guaranteed over the whole decade [START_REF] Cook | Smart Environments: Technology, Protocols and Applications[END_REF][START_REF] Tchoffo-Talom | A sitespecific tool for UWB channel modeling[END_REF] GHz thanks to its cylindrical symmetry structure. This UWB antenna provides a very low pulse distortion that is the same in all the horizontal angular directions. Consequently, the main application of CMA 118/A is the channel sounding (e.g. [START_REF] Keignart | Subnanosecond UWB channel sounding in frequency and temporal domain[END_REF], [START_REF] Pagani | Experimental analysis of the ultra wideband propagation channel over the 3.1 GHz -10.6 GHz frequency band[END_REF]). Indeed, CMA dimensions and weight (i.e. about 1 kg [9]) discourage its use in the context of WSNs.

B. Middle Alva Antenna

The Middle ALVA (MA) antenna illustrated on Figure 5 is a compact UWB antenna derived from [START_REF] Demeestere | A compact UWB antenna with a wide band circuit model and a time domain characterization[END_REF] for Body Area Network (BAN) applications (e.g. [START_REF] D'errico | Time-variant BAN channel characterization[END_REF]). This low cost, light weight (i.e. about 30 g) miniature antenna can be seen either as a short circuited printed folded dipole or as a notch antenna. The notch design has been modified in order to achieve wideband behavior with the elliptical shape of the dipole arms. As a consequence, the wideband impedance matching is obtained by combining two different antenna modes. In the band [3.5,5.5] GHz, the notch acts as an aperture antenna with small directive characteristics. The antenna gain obtained by simulation in azimuth plane is shown on Figure 6. The Monopolar Wire-Patch (MWP) (e.g. [START_REF] Keignart | Subnanosecond UWB channel sounding in frequency and temporal domain[END_REF]) is an UWB antenna with low profile design, whose dimensions are depicted on Figure 7 and which weights about 300 g. The antenna is well matched between 3 and 10 GHz and is mostly intended for indoor high data rate communications. The antenna radiation is quasi omni-directional in the azimuth plane, despite the non cylindrical symmetry of the monopole. A dipole-like pattern is stable over the first octave as the ground plane is still electrically small. Beyond 5 GHz, the omni-directionality in azimuth is slightly degraded due to the non cylindrical symmetry of the monopole. The antenna gain in azimuth plane obtained by simulation is depicted on Figure 8. The geometrical scenario associated with shown results is the same as that described in [START_REF] La Tosa | Maximum averaged likelihood estimation tree for Anchor-Less localization exploiting IR-UWB multipaths[END_REF]. As an example, on Figure 9 an observation of the received noisy signal is provided for CMA, MA and MWP antennas. According to the LOS hypothesis, the first received path is forced to be estimated as a direct path. Only two types of interactions are available in the local waveforms database: direct path (i.e. free space propagation) and reflection on brick.

The Power Spectral Density (PSD) of the transmitted signal complies with the FCC UWB mask (e.g. [START_REF] Kaiser | UWB communication systems[END_REF]). Moreover, as in [START_REF] Navarro | Low complexity frequency domain TOA estimation for IR-UWB communications[END_REF], the simulated system employs a Pulse Repetition Period (PRP) of 100 ns and the signal has a bandwidth of 2 GHz at -10 dB of the PSD maximum, centered around 4.5 GHz. The received signal is affected by thermal noise (i.e. Gaussian distributed, N 0 = -174 dBm/Hz) filtered in the signal band and a noise figure of 10 dB accounts for a more realistic receiver (e.g. [START_REF] Kaiser | UWB communication systems[END_REF]). The sampling frequency for the received signal is assumed to be 15 GHz, beyond Nyquist frequency.

According to simulation results, the best trade-off between execution time and estimation performances for the presented algorithms is obtained with the thresholds represented on Table I and II. The shown results have been obtained with this algorithm calibration. In addition, the standard deviations considered for the averaged likelihood computation are presented on Table III.

Positioning results for CMA, MA and MWP antennas are respectively on Figure 10, 11 and 12. For the CMA antenna, eMAL and MAL algorithms provide approximately the same estimation error, which is lower than 0.6 m for 90% of estimates and with a median value of about 0.55 m, as illustrated on Figure 10. On the contrary, a strong difference in positioning errors can be found between eMAL and MAL algorithms applied to MA antenna. Indeed, the positioning error obtained with the extended algorithm is lower than 0.6 m for 90% of estimates but with a median value of about 0.04 m, as illustrated on Figure 11a. Finally, the positioning error Cumulative Density Functions (CDFs) obtained with a MWP antenna are presented on Figure 12, highlighting a slight improvement obtained using eMAL in comparison with MAL.

These positioning results clearly show the tight relationship between antenna deformation properties and algorithm measurements. Accordingly, the antennas characterized by almost perfect omni-directional radiation pattern (e.g. CMA and MWP) can not take advantage of additional AoAs and AoDs information. Otherwise, the radiation diversity of MA antenna allows eMAL to better estimate nodes positions in comparison with MAL. The different reliability of measurements with respect to a given antenna is also illustrated by standard deviations on Table III. Therefore, the positioning estimation exploiting only AoIs and ToAs (i.e. with MAL algorithm, on Figure 11b) can not be satisfactorily achieved using MA antenna but it becomes possible, on the contrary, when AoD and AoA measurements are integrated, as illustrated on Figure 11a. The antinomy of radiation diversity and proneness of radiated waveforms to be signed by the AoI was hypothesized in [START_REF] La Tosa | Joint directions finding and material typecasting through IR-UWB communications[END_REF] and seems to be validated by the discussed results. It is also interesting to note that positioning error CDFs seems to be stepwise, particularly these corresponding to MA and MWP antennas. This shape is due to the presence of local maxima in the ALFs, which makes ALFs maximization not always correct. Therefore, bad positioning solutions are not continuous but discrete and corresponding to high but local maxima.

Finally, the CDFs of room dimension D x estimation errors expressed in percentage are displayed on Figure 13, 14 and 15 for CMA, MA and MWP antennas respectively. As for the positioning error, eMAL and MAL algorithms perform almost the same if a CMA or a MWP antenna is employed. On the contrary, a sharp improvement with respect to MAL algorithm can be observed using eMAL algorithm with MA, as the extended algorithm shows an error lower than 0.8% for 90% of estimates. Nevertheless, the observed D x errors can be generally considered very interesting for all the three antennas, as the error is always lower than 2.5%, whatever the algorithm and the antenna are.

VIII. CONCLUSION

This paper has compared the Maximum Averaged Likelihood (MAL) algorithm and its extension eMAL using three realistic antennas (i.e. Conical Monopole, Middle Alva and Monopolar Wire Patch). Both algorithms exploit the maximum averaged likelihood concept, using Angles of Incidence (AoIs) and Times of Arrival (ToAs) as measurements for MAL but Angles of Arrival (AoAs), Angles of Departure (AoDs), AoIs and ToAs measurements for eMAL. Simulations showed that the eMAL algorithm applied to a light, small and low power antenna like the Middle Alva can provide a positioning error lower than 0.6 m for 90% of estimates and even a median error of 0.04 m, after removing mirror and Tx/Rx ambiguities. Moreover, an error on room dimension lower than 0.8% for 90% of estimates is an acquired result for the Middle Alva in the chosen framework. Considering the context of use of the latter antenna, this main result may disclose new ways for BAN opportunistic localization. Even if a simplified scenario has been considered, it seems important to recall that the IR-UWB pair is static and that both algorithms do not need anchors, which makes obtained results potentially interesting.

Future works will investigate performances with relaxed technological constraints (e.g. lower frequency sampling) and introducing mobility.

IX. ACKNOWLEDGEMENT

This work has been partly carried out in the frame of the EUWB European Project [START_REF]EUWB, ICT-Project (Contract number 215669[END_REF].

µ

  α1,0 = arcsin 2 yr d sin arctan xr-xt yr+yt µ β1,0 = arcsin 2 yt d sin arctan yt-yr xt+xr-2Dx

Fig. 1 .

 1 Fig. 1. Simplified multipath indoor 2D scenario

Fig. 2 .

 2 Fig. 2. Real configuration (a) and mirror images (b), (c) and (d)

Fig. 3 .

 3 Fig. 3. Conical Monopole antenna 118/A

Fig. 5 .

 5 Fig. 5. Middle Alva antenna

Fig. 7 .

 7 Fig. 7. Monopolar Wire-Patch (MWP) antenna

Fig. 10 .

 10 Fig. 10. Positioning error CDFs using Conical Monopole antennas, after ambiguities solving, eMAL (a) and MAL (b) algorithm

Fig. 13 .Fig. 14 .Fig. 15 .

 131415 Fig. 13. Dx error CDFs expressed in percentage, using Conical Monopole antennas, eMAL and MAL algorithm