When considering localization systems, one of the most commonly employed reference parameters is the so-called two-way ranging. To obtain this parameter, technologies such as ultra-wideband (UWB) exploit the signal propagation time between two devices: a target and an anchor. However, this parameter is not immune to propagation phenomena such as shadowing, re ections, and di ractions frequently found in indoor environments, leading to a loss of line-of-sight (LOS) conditions between the target and the anchor (i.e., non-line-of-sight (NLOS) conditions), hence degrading the ranging estimations and, consequently, the performance of the algorithms used for the localization. This work studies how the prior knowledge about LOS and NLOS conditions allows for improving considerably the nal position estimations. Results based on UWB measurements are considered to evaluate the performance of di erent positioning algorithms with and without this prior information.
Location-based services (LBS) are becoming more popular and demanding with the accuracy of locating users and objects, especially inside buildings, where it is well known that satellite tracking systems have no coverage. The demand for these services requires the use of the so-called sub-meter location systems (i.e., positioning errors below one meter).
Ultra-wideband (UWB) is one of the most used technologies in recent years to achieve sub-meter localization. This technology is based on obtaining the propagation time (time of arrival (ToA) or time di erence of arrival (TDoA), depending on the variant of the technology considered) between a reference element (anchor) with a xed and known location and the target to be located (tag). From such a propagation time, it is possible to determine the distance between the two elements (anchor and tag). Using multiple anchors, trilateration algorithms can be employed to estimate the position of the tag.
Although the propagation times provided by UWB have a much higher precision and accuracy than those obtained by received signal strength (RSS)-based technologies, they are still a ected by di erent propagation phenomena, especially in indoor environments. Multiple and varied obstacles (walls, ceilings, people, furniture, ...), shields and signal blockages, re ections, refractions, and di ractions cause the appearance of multipath propagation between anchors and tags. Each of these paths presents di erent propagation times, deteriorating the ranging precision and accuracy and, therefore, the tag estimated position.
These phenomena are di erent depending on the visibility between anchors and tags. Basically, there are two possible path types: line-of-sight (LOS) and non-line-of-sight (NLOS). In the case of LOS, the shortest path is the one that provides a good distance estimation between an anchor and a tag. However, when NLOS appears, the aforementioned phenomena produce secondary paths that predominate over the shortest one, degrading the distance estimation. If the di erent propagation conditions (LOS or NLOS) between anchors and tags is not taken into account, the positioning algorithms will use noisy or erroneous information that will cause a poor estimation of the nal position of the tag.
This work analyzes the bene ts of taking into account the propagation
conditions (LOS or NLOS) between the tag and each anchor as prior knowledge
for the location algorithms. Employing a UWB-based system, we carried out a
measurement campaign considering a set of anchors combining LOS and NLOS
propagation conditions with respect to a tag. The obtained measurement data
are available for public use [
The article is structured as follows: Section 2 presents the environment where the measurements have been carried out, explaining how LOS and NLOS propagation conditions are obtained. Section 3 introduces the location algorithms considered to assess the impact of the prior knowledge about the propagation conditions (LOS and NLOS). Section 4 details how the experimental data are used to simulate a more complex scenario. The results are shown and discussed in Section 5. Finally, Section 6 is dedicated to the conclusions. 2
UWB
To analyse the e ect of LOS/NLOS conditions on the performance of a location algorithm, ranging measurements in a real environment with unambiguous identi cation of these conditions are required. The measurement campaign goal is just to obtain a real distance-measurement database. These measurements were obtained in a campaign carried out inside the Scienti c Area building, located in the Campus of Elvin~a, at the University of A Corun~a, Spain.
The hardware used consists of UWB devices manufactured by Pozyx [
To obtain the ranging measurements, an anchor was considered in a xed and
known position, whereas a tag was placed at di erent known locations. Thus, in
the LOS scenario, both the tag and the anchor were placed without obstacles
between them. However, in the NLOS scenario, both devices were placed in such
a way that it is impossible to nd a direct path between them, hence the only
path for the UWB signal to reach the receiver is through one or more re ections.
The measurements were obtained at di erent distances between an anchor and
a tag, ranging from 3 m to 16 m spaced 0:2 m apart. Therefore, multiple actual
ranging measurements between a tag and an anchor were obtained at di erent
distances and with both LOS and NLOS conditions. Notice that the measured
data are publicly available in [
Pozyx devices are able to obtain an estimation of the distance between a tag and an anchor based on the round-trip ToA of the signal traveling from the tag to the anchor. When there are multiple anchors in xed positions and one tag in an unknown location, the ranging estimations can be used to estimate the coordinates of this tag: rTOA;l = q (x xl)2 + (y yl)2 + (z zl)2 + nTOA;l; where (x; y; z)) are the coordinates of the tag, (xl; yl; zl) are the coordinates of each anchor, rTOA;l are the ranging measurements between the tag and the anchor l and nTOA;l is an error component modelled as AWGN. If several ranging measurements are available, the previous equation can be used to estimate the location of the tag.
Di erent location algorithms were chosen to test the e ects of considering
or not the prior knowledge of the LOS / NLOS condition between a tag and
several anchors. The algorithms were selected among the many of them available
in the literature taking into account their nature. All of them used the ranging
estimations between the tag and the anchors as an information source for their
operations. Sections 3.1 to 3.3 describe these algorithms.
The linear least squares (LLS) algorithm performs the location task in two steps:
rst, (1) is approximated by means of a linearization and, second, a least squares
method is used to nd the position that provides the minimum error. There are
several methods to approximate the nonlinear equation in (1) such as those
described in [
Nonlinear Least Squares
The nonlinear least squares (NLS) is an approach to solve the problem
starting from (1) without performing a rst linear approximation [
Iterative Extended Kalman Filter
The Kalman lter is a well-known algorithm to estimate the hidden state of
a system given some observation variables and is widely applied to positioning
problems. The original Kalman algorithm provides an exact solution for this
estimation problem in systems where the observations are linear on the state
together with Gaussian-distributed noise sources. However, when some of these
assumptions do not hold, numerous variations were proposed to overcome these
limitations, such as the Extended Kalman lter [
To test the e ects of using NLOS measurements in location algorithms, a set of experiments were designed. The aim of these experiments was to study the e ect on the nal position estimation provided by the algorithms described in Section 3 when using a certain number of anchors with di erent probability of being in NLOS with respect to the tag. In order to make this study as realistic as possible, we use the ranging measures obtained in the measurement campaign described in Section 2.
Before carrying out the experiments, some common tasks were implemented. Firstly, a method to generate a virtual scenario with an arbitrary number of UWB anchors was considered. In a virtual 3D environment, we placed anchors at di erent xed and known spatial positions. The coordinates of each anchor were selected to avoid having two anchors at the same height, whereas the values of x and y coordinates were selected to equally distribute the anchors on the sides of a cube.
Secondly, the movement of a tag inside the scenario along a trajectory was simulated. To perform this task, we used the waypointTrajectory method from the Sensor Fusion and Tracking toolbox in Matlab™. With this function, we could de ne a trajectory based on a sorted set of waypoints.
Thirdly, given a position from the tag trajectory, a ranging measurement between the tag and each anchor is produced. Since this data is extracted from a repository obtained from the UWB measurement campaign described in Section 2, not all possible distances are available. Therefore, for each anchor in the virtual environment, we consider the closest distance between the tag and the anchor which is available in the repository. Consequently, in order to maintain the coherence between the distance extracted from the repository and that of the virtual environment, we move the a ected anchor slightly around the position initially indicated. For instance, suppose that a tag is located at the position (Px; Py; Pz) and the distance between this point and the anchor A1, placed at (A1x; A1y; A1z), is 3:16 m. Given that in the ranging measurements repository only distances spaced 0:2 m apart are recorded (i.e., , 3 m, 3:2 m, 3:4 m, ), the distance 3:16 m has to be approximated. To solve this problem, we need to round the distance value to the closest one available from the measurements (3:2 m in this case). After this rounding, it is necessary to move the position of the anchor A1 around its original position, so that the distance to the tag is consistent with this new distance of 3:2 m (exactly as if the anchor had been placed at a distance of 3:2 m to the tag from the beginning).
Finally, in order to decide if an anchor is in LOS or NLOS with respect to the tag for a given point of the trajectory, we designed a script that returned a LOS or NLOS measurement according to a given probability (note that, for each distance value between the tag and the anchor, there is a LOS and an NLOS ranging measurement). This was done using a randomised process with an appropriate probability distribution.
Once the previous elements were completed, the following experiments were performed: 1. Execution of the algorithms described in Sections 3.1 and 3.2 for the estimation of the positions of a trajectory in a virtual scenario with a xed number of anchors. Both LOS and NLOS conditions of each anchor, for the di erent tag positions within the trajectory, were determined according to the given probability. In this experiment, the algorithms consider all ranging estimates from all anchors, regardless of whether they were in LOS or NLOS. 2. Execution of the algorithms as in the previous case, but now the NLOS ranging estimates are discarded. Therefore, for each position of the tag, the number of anchors that provide ranging estimations is variable, depending on the probabilities of having NLOS situations. 5
Linear Least Squares Nonlinear Least Squares IEKF Linear Least Squares Ignore NLOS Nonlinear Least Squares Ignore NLOS
IEKF Ignore NLOS 0.1 In this study we have con rmed with measurements captured with real UWB devices how the presence of values obtained from anchors in NLOS can cause large errors in the nal estimation of position, and how prior information about the type of propagation condition (LOS or NLOS) can help to improve the performance of the positioning algorithms. In order to do this under practical conditions, a system has been created capable of generating a trajectory in a 3D space and calculating the corresponding ranging estimates from a series of virtually placed anchors around it, but always based on data coming from a real-world measurement campaign. Di erent classic location algorithms have been considered to analyze how the prior information can be used. Three different experiments were carried out in which the algorithms are fed with 1) the measurements of all anchors without any additional information about the propagation conditions, and 2) only the measurements corresponding to the anchors with LOS propagation conditions.The results show the importance of incorporating the knowledge about LOS/NLOS propagation conditions of UWB ranging measurements before feeding them to the positioning algorithms.
This work has been funded by the Xunta de Galicia (ED431C 2016-045, ED431G/01), the Agencia Estatal de Investigacion of Spain (TEC2016-75067-C4-1-R) and ERDF funds of the EU (AEI/FEDER, UE).