A Robust Detection and Optimization Approach for Delayed Measurements in UWB Particle-Filter-Based Indoor Positioning

2.1 Channel Statistics-Based Methods

Channel statistics-based methods identify delayed signals by examining the CIR statistics or the received signal features such as maximum amplitude, signal-to-noise ratio, total power, kurtosis, mean excess delay, and root-mean-square delay spread. A description of these signal features can be found in Yu et al. (2018). Once the delayed signal is identified, it can be mitigated by either error statistics or a signal propagation path-loss model. As for the statistical model, Alavi and Pahlavan (2006) introduced a model for UWB TOA ranging errors in an indoor environment. This model relates the behavior of the TOA estimation error to the bandwidth of the signal. As for the path-loss model, Al-samman et al. (2017) present a UWB channel characterization considering stationary and mobility scenarios in an indoor environment based on the data collected through TOA measurements. Zhao et al. (2013) developed an empirical model to continuously determine the path loss inside a corridor for the case of transition between direct and delayed signals. In the following, other state-of-the-art channel statistics-based methods are reviewed.

In the method proposed by Heidari et al. (2007), the peak of the filtered CIR was selected as the first detected path of the signal. Then the time (mean excess delay) and power (total power) metrics from the first detected path were extracted. The delayed signal was then detected by a joint likelihood-ratio hypothesis test of the total power, mean excess delay, and hybrid of power/time metrics. The delay in the range measurement was then mitigated by subtracting the error from a delayed measurement based on the statistics of range errors associated with each class of receiver location. The ranging accuracy was improved by about 50% with the implementation of this method, and the residual range error was about 1.56 m.

Albaidhani et al. (2016) identified delayed signals by comparing the power difference between the first path and received signal with a receiver detection threshold. The delay was estimated by a statistical model which took into account the refractive index and width of a given obstruction. The test results obtained from a corridor environment showed that, for the channel mode CH3 (4.5 GHz), the residual range errors remain in the range of about 0.4 m to 1.2 m.

Wu et al. (2007) proposed a detection method by comparing the arrival time and received energy of all paths. The delay was then estimated based on a signal propagation path-loss model. This estimated delay was then used for calibrating the measured range. The test results obtained from a basement environment show that the residual range errors were in the range of 0.2 m to 0.8 m.

Maranò et al. (2010) developed a classification and regression method based on the support vector machine learning technique. Based on the features extracted from the CIR, this method detected the delayed signal and mitigated the delay without formulating statistical models for the features. The test results showed that different feature sets produced different levels of performance, and the best feature set could reduce the root-mean-square of residual range error from 3.589 m (without any implementation of error mitigation) to 1.419 m (error mitigation implemented).

Yu et al. (2018) proposed an identification method based on a fuzzy comprehensive evaluation. This method divided indoor propagation channels into multiple categories so that the channel identification results could be used to evaluate how serious the effect of delayed propagation would be. Given the signal features extracted from the CIR, this method could identify the specific delayed channel and predict its corresponding delay. The test results obtained from the tested real office environment showed that the root-mean-square of range errors had been reduced from 1.3 m (no error mitigation) to 0.651 m. In addition to the methods described above, more channel statistics-based methods are presented by Güvenç et al. (2008) and Wymeersch et al. (2012).

The channel statistics-based methods described can effectively improve individual range measurement accuracy. However, it is impossible to eliminate the delays completely, and the residual signal delays become delays in the range measurements. With the aforementioned state-of-the-art channel statistics-based methods, the residual delays in range measurements remained in the overall range from about 0.2 m to 1.0 m. These residual errors should be considered seriously because they degrade positioning accuracy. In order to mitigate such effects of residual delays on positioning, position estimate-based methods are required. With the hardware without any channel statistics-based methods, the need for position estimate-based methods becomes obvious and significant. In the next section, such state-of-the-art position estimate-based methods are described.

2.2 Position Estimate-Based Methods

According to Hammes and Zoubir (2010), position estimate-based methods generally can be divided into two categories. The first category is called robust estimation. The methods in this category estimate positions using all observed measurements, including delayed ones. They use specific strategies, such as those described below, to mitigate the effects of delayed measurements on position estimation.

One typical strategy is to provide weights or scale factors on the delayed measurements. The weight or scale factor can be determined by either the position estimation residual calculated by a residual weighting algorithm (Rwgh; Chen, 1999) or the geometry of the base stations (Venkatraman et al., 2002). The Rwgh calculates the weighted residuals of least squares (LS) estimates obtained from different sensor combinations. The final position estimate is the linear combination of these LS position estimates weighted inversely against their residuals.

In addition, Yousefi et al. (2014) proposed a two-stage robust distributed algorithm for sensor network positioning. In this algorithm, a Huber estimator is used for the robust position estimation against delayed range measurements. Yin et al. (2013) proposed another algorithm that iteratively estimates the probability distributions of range error and position. The methods in this category can always provide position estimates whatever the number of delayed range measurements is. However, most of the above methods are difficult for real-time applications due to the large computation load required (Yu et al., 2018). Moreover, these methods may be ineffective when the number of delayed measurements is large.

The second category of estimate-based methods is called identification-and-positioning. The methods in this category attempt to distinguish range measurements between delayed range measurements and direct range measurements (only contaminated by noise) first. A non-parametric approach for delayed range measurement identification was proposed by Gezici et al. (2003). It constructs the probability density functions (PDFs) of delayed- and direct-range measurement errors from training samples and uses the Kullback-Leibler divergence to quantify the distance between these PDFs and set decision threshold.

Borras et al. (1998) used the wide variance on a list of range measurements to identify delayed range measurements. This method is simple and straightforward but has the problem of time latency. Le et al. (2003) proposed using a Kalman filter for range measurement smoothing. The standard deviation estimated by Kalman filters is used for delayed measurement identification. Casas et al. (2006) identified the delayed range measurements using the least-median-of-squares (LMedS) in a technique that searches in the space of position estimations obtained from combinations of the minimum number of measurements.

A common drawback of the methods described here, however, is that they would be ineffective if redundant range measurements are unavailable; increasing the number of sensors would increase the cost. In addition, delayed range measurements can also be identified by combining the position estimate with constrained information such as its geometry (Liu & Fan, 2010) or a map (Djaja-Josko & Kolakowski, 2017). However, constrained information is not always available in practice, and the use of constrained information may increase computational complexity.

The identified delayed range measurements can then be either discarded or calibrated. The calibration methods in question are similar to the channel statistics-based methods, which can be based on either error statistics or the signal propagation path-loss model. Moreover, the method proposed by Le et al. (2003) would mitigate delays by using a biased Kalman filter to increase the values of the diagonal elements of the measurement noise covariance matrix. The identified direct range measurements as well as the calibrated measurements can be used for position estimation.

The existing position estimate-based methods described above have limitations such as the requirement of measurement redundancy and great dependence on prior knowledge (such as the known statistics of a sensor being delayed). In this paper, an outlier detection method is proposed for delayed range measurement identification. This method is less dependent on prior knowledge and has no requirement for measurement redundancy. A detailed description of the proposed outlier detection method is presented in Section 3.

2.3 TOA-Based Positioning Using Particle Filter

Various methods have been proposed for TOA-based positioning using particle filters. Savic and Larsson (2016) proposed an improved particle-filter-based positioning algorithm with a Gaussian process regression (GPR) based machine-learning method for correcting delayed range measurements. The positioning accuracy of the algorithm is highly dependent on the environment of the collected training data, and thus it has poor robustness to changes in a given positioning environment.

Wang and Li (2017) proposed an inertial measurement unit (IMU) and UWB data-fusion positioning algorithm based on a particle filter. This algorithm takes IMU calculation results (velocity and orientation) as the prior information for the particle filter and then uses UWB range measurements for particle weight updating. The test results show that the prior information derived by IMUs can mitigate the effect of delayed measurements on position estimate and thus improve positioning accuracy. However, the integration of an additional sensor into a UWB system may cause new problems, such as sampling synchronization between the two sensors and increased cost on equipment.

González et al. (2009) proposed an augmented state particle filter containing a set of random range offsets into the state vector. This operation seemed to improve the robustness against delay, but it simply attributed potential bias into another independent component in the state vector without identifying the cause of bias (noise or delay). Moreover, the increase of the parameter in the state vector could decrease the degrees of freedom in the filtering estimation and hence the reliability of the position estimate (Basiri et al., 2017). Therefore, the positioning accuracy of the algorithm might degrade significantly when measurement redundancy is unavailable.

For positioning using the Global Navigation Satellite System (GNSS) in urban environments, Suzuki (2019) proposed a particle-filter-based algorithm with GNSS delayed signal identification using pseudorange residuals. Based on the pseudorange residuals, the delayed measurements would be identified and discarded through a simple hypothesis test. However, this method assumes that there would always be a reference satellite that could receive direct signals and that the pseudorange it generated would not contain a delay. Such assumptions may be reasonable for outdoor positioning, in which there are a large number of measurement redundancies because of the many positioning satellites on the space. In contrast, the number of positioning sensors in indoor positioning is usually much less, and indoor environments are usually more complicated, thus such assumptions remain unreasonable for indoor environments. Therefore, this proposed algorithm is difficult to be widely applied in indoor positioning.

In this paper, for the purpose of achieving accurate position estimates in difficult environments, an outlier detection method is first proposed for delayed range measurement identification, and a range-constrained particle sampling method is proposed for generating prior particles. Both the proposed methods are integrated into a particle-filtering framework to form the proposed RCSPF algorithm. Different from the algorithms introduced, the proposed RCSPF algorithm does not need assistance from any additional sensors to be effective. Meanwhile, it has no requirements for prior training data or measurement redundancies. A detailed description of the proposed algorithm is given in the next section.

3.1 Step 1: Prior Position Determination

The state-space model used in the proposed algorithm needs, first, to be defined. We need a dynamic model for the moving tag which can provide its state information. We denote a state vector as , in which (x_k, y_k, z_k) is the 3D position and is the 3D velocity. The random-walk model (Pak et al., 2017) is used as the dynamic model without loss of generality, given by: 1

where:

and T is the sampling interval. w_k is the zero-mean Gaussian random process noise with known covariance Q_k. This state model assumes that the velocity is subject to an unknown acceleration value which is characterized by the motion process noise.

The prior position is determined by the noise-free equation of the dynamic model (i.e., x_k|k−1 = Ax_k−1|k−1, where x_k−1|k−1 is the known posterior position at time step k − 1, and x_k|k−1 is the prior position at time step k). This prior position is actually the mean value of the prior particles obtained using Equation (1) in the standard particle filter. This prior position will be used in the delayed measurement identification in the next step.

3.2 Step 2: Delayed Measurement Identification

For the purpose of avoiding delayed UWB range measurements degrading positioning accuracy, a delayed measurement identification should be performed beforehand. Cong and Zhuang (2005) proposed an outlier detection method for identifying the delayed time-difference-of-arrival (TDOA) range measurements. In this step, we revise this outlier detection method and use it for identifying the UWB delayed TOA range measurements.

The measurement model should be defined first. We denote the original measurement vector at time step k as y_k (i.e., y_k = [r_1,k, … r_M,k], where r_i,k, is the raw range measurement provided by the i-th sensor), and it can be expressed as (Abbasi & Kahaei, 2009): 2

where (x, y, z) is the unknown position of the target, and (x_i, y_i, z_i) is the known position of the i-th sensor. v_i,k is the measurement noise which is usually modeled as a zero-mean Gaussian variable, and e_i,k is the delay (i.e., NLOS error) resulting from delayed signal propagation. When the range is obtained in a line-of-sight scenario, the delay component e_i,k should be zero.

Consider that with a known reference position x_ref and its range measurement r_i (which may be contaminated by delay) to the i-th sensor, the conditional probability of a range being smaller than r_i in the line-of-sight case is given by: 3

where R is a random parameter that characterizes all possible range measurements; r_i,ref is the calculated Euclidean distance between the reference position x_ref and the i-th sensor; σ_i is the known standard deviation of the measurement noise of the i-th sensor; and erf(·) is the error function defined as: 4

Equation (3) indicates that the higher the conditional probability, the more likely that a range measurement is an outlier contaminated by a delay. Therefore, a hypothesis test can be deduced intuitively to identify the delayed/direct range measurement by comparing the calculated conditional probability with a predefined threshold λ, given by: 5

When the conditional probability in Equation (3) of a range measurement is greater than the threshold λ, it is considered as a delayed range measurement, and the corresponding UWB sensor is defined as the delayed sensor. On the contrary, when the conditional probability is less than the threshold λ, it is considered a direct range measurement, and the corresponding UWB sensor is defined as the direct sensor.

The result of Equation (4) is dependent on the reference position x_ref. Ideally, using true position as the reference position can obtain the best identification performance. However, true position is unachievable in practice. Hence, it is necessary to find an approximated value. When using this delayed measurement identification method in a static positioning problem, the reference position x_ref can be approximated by the Taylor Series Least Squares (TS-LS; Yu & Guo, 2007) estimated or the Rwgh (Chen, 1999) estimated positions.

Considering integrating this identification method into the particle-filtering framework, we use the prior position x_k|k−1 obtained in Step 1 (Section 3.1) as the reference position. The accuracy of the prior positioning will affect the delayed measurement identification accuracy. When the posterior position at a previous time step (i.e., x_k−1|k−1) is obtained in a line-of-sight environment or an environment in which delayed sensors account for a small portion of the whole sensors, the derived prior position is close to the true position. The bias between the prior position and true position in this case is negligible and would not affect the identification accuracy significantly (see test results in Section 4.4.3).

However, if x_k−1|k−1 is obtained in an extremely difficult environment, namely in a case in which delayed sensors account for a large portion of the whole sensors, the effect of the bias should be considered as it may degrade the resulting identification accuracy. In order to improve the accuracy of the prior position, AOA measurements can be integrated into the positioning system since it improves the robustness of positioning in difficult indoor environments (Lau et al., 2018). The test results given by Cong and Zhuang (2005) show that the integration of AOA measurements helps to obtain a more accurate reference position estimate and hence better delayed measurement identification accuracy. In this work, we use only UWB-range measurements for positioning; integration of AOA measurements into the current method is a subject for future work. The determination of the threshold λ is described in Section 4.2.

The proposed delayed measurement identification method has the advantage that it does not require any prior information about the delay but only the variance of the Gaussian noise of the range measurement. The variance of measurement noise can be obtained from the experimental data in practice. Moreover, it can work without measurement redundancy (i.e., using only four range measurements).

3.3 Step 3: Range-Constrained Particle Sampling (RCPS)

A simple way to mitigate the effects of identified delayed measurements is to discard them directly. However, this may cause the remaining number of available sensors and their geometry to not be suitable for achieving an accurate estimate of a given tag’s position. In this step, we propose a range-constrained particle sampling method that makes use of the positive effect of the identified delayed range measurements to optimize the distribution of predicted particles.

In a standard particle-filtering algorithm, the particles in the prediction phase are generated by adding random process noise to the prior position (Chen, 2003). Then each particle is set with the same importance weight, which is the reciprocal of the total number of particles. This generic sampling method is optimal for positioning with measurements contaminated by Gaussian random noise only. However, when the delayed range measurements appear, this sampling method becomes suboptimal.

As any delay in the TOA range measurement is always positive and much larger than the absolute value of measurement noise (Shen et al., 2010), the true range between the tag and the delayed sensor should always be less than the delayed range measurement. In this sense, the position of the tag should be located within the sphere with the delayed sensor as the center and the corresponding delayed range measurement as the radius. When there are more than one identified delayed sensor, multiple such spheres can be obtained. The tag should be located within the intersection region of all spheres. Motivated by this constraint condition, the RCPS method is proposed. The detailed steps of the RCPS method are described as follows:

1. Based on the prior position, as well as the known covariance matrix of motion process noise, generate a predicted particle using the generic sampling method (i.e., adding Gaussian random process noise to the prior position obtained in Step 1 [see Section 3.1]).

2. With the states of each sensor (delayed or direct) identified by Equations (3) and (5), calculate the distances between the generated particle and identified delayed sensors.

3. If each calculated distance is less than the corresponding delayed range measurement, this particle is kept. Otherwise, this generated particle should be discarded and a new one should be regenerated according to the operations in Steps 1 and 2.

4. Repeat the above three operations until a predefined number of particles is obtained.

Different from the traditional sampling method, this RCPS method is the novelty of the proposed algorithm because it makes full use of the positive effects of the identified delayed measurements for particle sampling. The integration of the RCPS method into a particle-filtering (PF) framework contributes to optimizing the distribution of the prior particles and hence improving positioning accuracy. This is generally unavailable for the other estimation algorithms in the Bayesian framework (such as Kalman filters and subsequent variants) because these algorithms represent the estimated state with an exact Gaussian probability density function (mean and covariance), but not a set of independent particles.

For clarity, a schematic of the RCPS method in a 2D case is presented in Figure 1. The proposed RCPS method is only used in the case that there exists delayed sensors in the system. When all sensors are identified as direct sensors, the generic particle sampling method is used directly.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 1

Schematic of generating a particle using the RCPS method in 2D case; the ellipse is determined by the covariance of process noise.

3.4 Step 4: Posterior Position Estimation and Update

In the update phase of a PF algorithm, the predicted particles generated by the RCPS method are required to be evaluated. A simple and straightforward way to do this is to remove the identified delayed measurements and evaluate the predicted particles using the remaining identified direct range measurements. However, Savic and Larsson (2016) point out that the particle filter using the range measurements with the rejection of identified delayed measurements may still suffer from serious accuracy degeneration due to the accumulation of positioning error over time.

Removing the delayed measurements can lead to reduced measurement redundancy, and it may result in the loss of positioning accuracy. Insufficient measurements can sometimes even lead to filtering divergence. Moreover, a special case that may happen is that all the range measurements are identified as delayed measurements, so no direct range measurement can be used.

In order to improve the availability of the proposed algorithm (i.e., making sure the algorithm can still work when all measurements are identified as delayed measurements), we replace the identified delayed range measurements r_i with the calculated ranges . The calculated range is obtained by calculating the Euclidean distance between the prior position and the identified delayed sensor, which is equivalent to r_i,ref in Equation (3). The accuracy of the calculated range is dependent on the accuracy of the posterior position at the previous time step as well as the process noise at the current time step. When the posterior position in the previous time step is obtained in a line-of-sight scenario (i.e., no delayed measurements occur in the positioning) and the process noise at the current time step is small, the prior position at the current time step derived by the noise-free dynamic model can be close to the true position. In this case, the calculated range may be closer to the true range, especially when the delay is large (Yu & Guo, 2007).

On the contrary, if the accuracy of the posterior position at the previous time step is low and the process noise at the current time step is large, the accuracy of the derived calculated range can be reduced. In order to mitigate the effect of the latter case on positioning accuracy, a solution is to increase the measurement noise of the calculated range. For robustness purposes, the standard deviation of the measurement noise of the recalculated range is set to 2σ_i, where σ_i is the standard deviation of the raw measurement noise.

In summary, using this calculated range to replace the delayed measurement instead of discarding it directly can not only improve the positioning availability, but also contribute to improving positioning accuracy and robustness. If a range measurement is identified as direct range measurement, it can be used for particle evaluation directly with the measurement noise set to σ_i. Consider that there are M UWB sensors in a positioning system; we denote a revised measurement vector as z_k = [d_1,k, …, d_M,k], where d_i,k (i = 1, …, M) is the range measurement of the i-th sensor used for particle evaluation, and it is given by: 6

where r_i is the raw observed range measurement; is the calculated range obtained by ; and l_i denotes the 3D position of the i-th sensor which is identified as a delayed sensor.

The rest of processes in the update phase are the same as any other standard PF algorithm. Each predicted particle is evaluated by the revised measurement vector z_k and assigned an importance weight which characterizes the quality of the particle. Then, the posterior position can be obtained by calculating the weighted sum of the particles. Finally, a resampling operation is implemented. The resampling optimizes the distribution of the particles in each recursion for the purpose of eliminating the particles with low importance weights which have negligible contributions to the position estimation. The particles with high importance weights are copied and those with low importance weights are discarded.

Systematic resampling is used in our proposed algorithm since it can perform with the lowest resampling variance and is computationally more efficient than the other resampling methods (Hol et al., 2006). In order to avoid the sample impoverishment problem introduced from resampling, the Gaussian jitter noises (Gordon et al., 1993) are added to the over-centralized particles obtained from resampling. The resampled particles are then used in the position estimation at the next time step. The full procedure of the proposed RCSPF algorithm is presented in Algorithm 1.

• Download figure
• Open in new tab
• Download powerpoint

ALGORITHM 1

The Procedure of the Proposed RCSPF Algorithm

4.1 Experimental Setup and Data Collection

The experiment was performed in the atrium of the Sir Peter Mansfield Building at the University of Nottingham Ningbo China (UNNC). There were six Ubisense UWB sensors installed on the walls of the building. Before the test, a closed traverse survey was carried out to obtain the coordinates of the UWB sensors in the Universal Transverse Mercator (UTM) reference system, and a leveling survey was carried out to determine the heights of the traversing stations. The coordinates of the two traversing stations in the atrium (i.e., C1 and C2 [see Figure 2]) were determined through traverse and leveling. In order to minimize the errors in traverse and leveling propagation into the coordinates of UWB sensors, the coordinates of the six UWB sensors were determined through total station survey from the C1 and C2 stations. The calculations of the traverse were performed by a MicroSurvey software called Star*Net. The basic concepts of traversing, leveling, and the total station survey method were initially presented by Uren and Price (2010).

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 2

Locations of the known UWB sensors and test points; the red dots are UWB sensors, and the green dots are test points. The black dashed line is the rectangular track that the trolley travels on.

A trolley was used in this test. As shown in Figure 3, two ranging rods were tightly attached to the trolley, and a UWB tag was fixed on the top of a ranging rod. A rectangular track with dimensions of 9.6 m × 6.4 m was set in the middle of the atrium. The trolley and track helped to obtain the well-controlled tag position and height for the algorithm validation. Twenty test points at 1.6-m intervals were distributed on the rectangular track (see Figure 2). These test points were used for the positioning accuracy assessment. The horizontal coordinates of all the test points were known from the total station survey from C1 and C2, and the heights of the test points were determined using a leveling survey.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 3

The trolley and UWB tag used in the experiment

The raw direct UWB range measurements were collected by moving the trolley between the twenty test points with a stop-and-go method. Stop-and-go here means to start the trolley at rest at a test point and move toward and ultimately stop at the next test point for five seconds. When the trolley stopped, the measurements at that point were used to estimate the position, and this position estimate was compared with the truth values for the purpose of evaluation. This rigorous stop-and-go test allowed us to get UWB measurements at each test point accurately, because it was free from the effects of the residual UWB time synchronization, dynamic of the moving trolley platform, and the accuracy of visiting test points at a particular time.

In our measurement collection, the trolley started from the test point P1, moved steadily on the track in a clockwise direction and stopped (with the tip of the ranging rod pointed at the known test point on the track) at each test point in turn. Finally, the trolley moved back to P1. We obtained a total of 1,458 groups of direct range measurements from the loop, which corresponded to 1,458 different time steps. These direct range measurements were used for the simulation of delayed measurements in the following two sections.

4.2 Determination of the Optimal Threshold for Delayed Range Measurement Identification

The hypothesis test result in the delayed measurement identification (i.e., Step 2 in Section 3.2) is dependent on the threshold λ. A threshold that is too small or too large would affect positioning accuracy. Therefore, it is necessary to find out the optimal threshold value beforehand.

The threshold is generally a function of both the probability of false alarm (i.e., Type I error, denoted as P_false) and the probability of missed detection (i.e., Type II error, denoted as P_missed). False alarm here refers to a situation in which there is no delayed measurement but a delayed measurement identification warning is given, often because the threshold is set too low. Missed detection refers to a situation in which there exists at least one delayed measurement but the proposed algorithm fails to give the appropriate warning, often because the threshold is set too high.

It is desirable to have a threshold that minimizes both the values of P_false and P_missed. Therefore, the optimal threshold λ_opt can be determined by calculating λ_opt = arg min_λ(P_false + P_missed), i.e., the value that minimizes the total error probability (Wu et al., 2014). In this sense, the changes of P_false and P_missed with respect to λ need to be investigated, and from there we can determine the optimal threshold λ_opt based on the rule described above. A simulation test was carried out for the investigation in the following.

Two extreme cases are considered in the simulated test. First, an extreme case is considered in which all the sensors provided direct range measurements at each time step when investigating the relations between the threshold and false alarm probability P_false. The direct range measurements obtained by the stop-and-go method (see Section 4.1) were used directly in this case. The missed detection probability P_missed in this case should have been zero, theoretically. Second, an extreme case was considered in which there was always at least one delayed measurement at each time step when investigating the relations between the threshold and missed detection probability P_missed. The false alarm probability P_false in this case should have been zero, theoretically. At each time step in this case, we randomly selected a certain number (at least one) of sensors to be delayed sensors and introduced positive delays to their raw measurements.

The magnitude of delays was set to the range of 0.2 m (the lower bound) to 1.0 m (the upper bound) in our investigation. This is because the errors with a magnitude less than 0.2 m are more likely caused by measurement noise and they can be addressed with the filtering algorithm (Pak et al., 2017), and those higher than 1.0 m can be identified and mitigated by the channel statistics-based methods described in Section 2.1. The delays within the range of 0.2 m to 1.0 m are likely the hardware residual errors affecting the accuracy of range measurements and hence positioning accuracy. The proposed algorithm aims to tackle these practical delays.

If the magnitude of the error due to measurement noise is in the range of 0.2 m to 1.0 m, then our proposed algorithm would treat it as delay and tackle it using the proposed identification and mitigation methods. In order to simulate the delays in the range of 0.2 m to 1.0 m, we modeled the delay as a mean-shifted Gaussian distribution (Jiang et al., 2010) with the expectation of 0.5 m (which is approximately the mean value of the residual errors) and a standard deviation of 0.3 m. Then, the simulated delays were added to the direct range measurements obtained in the real data collection. The number of sensors used for positioning was taken into account in our simulation. Each simulation was performed by 10,000 independent runs. The relations between λ and P_false with a different number of sensors are presented in Figure 4(a); the relations between λ and P_missed with a different number of sensors are presented in Figure 4(b).

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 4

(a) Comparison of false alarm probability (mean-shifted Gaussian distribution); (b) comparisons of a missed detection probability (mean-shifted Gaussian distribution); (c) optimal threshold determination by investigating the total error probability (mean-shifted Gaussian distribution); (d) comparison of false alarm probability (Rayleigh distribution); e) Comparison of missed detection probability (Rayleigh distribution); and (f) optimal threshold determination by investigating the total error probability (Rayleigh distribution)

The simulation results in (a) and (b) of Figure 4 show there is a trade-off between the false alarm probability and missed detection probability when using different values of the threshold λ. According to the determination criterion of the optimal threshold described, the optimal threshold for each test scenario can be determined by finding out the value which minimizes the total error probability. Figure 4(c) presents the relations between λ and total error probability with different numbers of sensors. When four, five, and six UWB sensors were used for positioning, the total error probabilities were minimized at λ = 0.84, λ = 0.87, and λ = 0.90, respectively (see each black dot in Figure 4[c]).

A similar simulation was carried out by modeling the delay as a Rayleigh distribution (Yu & Guo, 2007). For the purpose of matching the expectation of the Rayleigh model with the mean value of the residual errors (0.5 m), the parameter sigma in the Rayleigh distribution was set to 0.4. The results obtained are presented in Figure 4(d), 4(e), and 4(f). It was found that the results remain similar to those of a Gaussian distribution with negligible difference. Namely, the total error probabilities were minimized at λ = 0.84, λ = 0.87, and λ = 0.90 when four, five, and six UWB sensors were used in the positioning. Therefore, these three values were used as the optimal threshold λ_opt. These values were used for the positioning performance assessment of the proposed algorithm in the next section.

4.3 Simulation of Test Scenarios with Delayed Measurements

For the purpose of simulating the test scenarios with different numbers of sensors, not all the measurements from the six UWB sensors were used. When positioning with four sensors (i.e., no measurement redundancy), the measurements from Sensors A and F were excluded from data processing. When positioning with five sensors (i.e., one measurement redundancy), the measurements from Sensor F was excluded from data processing. In order to obtain the delays with different magnitudes, the mean-shifted Gaussian model (the mean is positive) and Rayleigh model were used in the test. The parameters in the mean-shifted Gaussian model and Rayleigh model were the same as those in Section 4.2 (i.e., expectation of 0.5 m and standard deviation of 0.3 m in the mean-shift Gaussian model, and parameter sigma of 0.4 in the Rayleigh model). Six test scenarios with respect to different numbers of sensors and models of delay are listed in Table 1.

We divided the total 1,458 time steps into five time periods to evaluate the robustness of the proposed algorithm to the number of delayed measurements. In each time period, different numbers of sensors were set to be delayed sensors which provided delayed range measurements. The signal propagation state (delayed/direct) with respect to the six UWB sensors are shown in Figure 5. This setting was used in the six test scenarios listed in Table 1. The advantage of the above setting for evaluation purposes is that it can clearly show the identification accuracy rate of the proposed delayed measurement identification method by comparing its identification results with the known signal states of the sensors at each time step.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 5

The signal propagation state of each sensor along the path; the test point numbers listed on the top mean the test points being positioned within the corresponding time period.

The positioning performance assessment of the proposed algorithm was carried out by comparing the positioning accuracy and computation time of the proposed algorithm with those of five advanced positioning algorithms, TS-LS (Yu & Guo, 2007), Rwgh (Chen, 1999), EKF, standard particle filter, and robust particle filter (RPF). The RPF is a variant of a standard particle filter. The difference from our proposed RCSPF algorithm is that it uses the outlier detection method proposed in Section 3 for delayed measurement identification, but still generates the prior particles in the traditional way. We define this variant for the purpose of assessing the effectiveness of the RCPS method. Besides, for the purpose of evaluating the effectiveness of using the strategy of generating the calculated range in the Step 4 (see Section 3.4), we carried out a comparison between the proposed RCSPF algorithm and the RCSPF algorithm using the range measurements with the rejection of identified delayed measurements. The coordinates of the twenty test points determined by each algorithm were compared with the truth values that were determined by the total station survey; the root-mean-square error (RMSE) was used as the main accuracy assessment metric for evaluating the positioning accuracy in 3D space: 7

where n is the number of test points, i is the sample from 1 to n. x_i, y_i, and z_i are the estimated easting, northing, and height, respectively of sample i. x, y, and z are the truth value coordinates determined by the total station survey. The computation time of each positioning algorithm is determined through the function of tic and toc in MATLAB. The computer system configuration and software version used for data processing in our test are given in Table 2. Moreover, the identification accuracy rate of the proposed delayed measurement identification method was assessed by comparing the identification results with the known signal propagation states of the sensors at the 1,458 time steps.

The initial position (i.e., position at time step k = 0) would affect the accuracy of the prior position used for the delayed measurement identification at the next time step as well as the speed of filtering convergence. In this test, the initial positions of all the particle-filter-based positioning algorithms were determined by the Rwgh as it can mitigate the effects of the possible delayed measurements on the position estimate. Then, the initial particles could be generated according to the Rwgh derived position estimate and covariance. These particles were regarded as the posterior particles at time step k = 0.

Considering the computation efficiency, the number of particles for each particle-filter-based algorithm was set to 5,000. The standard deviation of process noise was determined by tuning. It is assumed that the process noise in the three directions (i.e., easting, northing, and height) were independent, and it was set to 0.1 m/s² in each direction. The direct range measurement noise in the test was modeled as zero-mean Gaussian variables and mutually independent. Its standard deviation was obtained from the raw measurement data collected in Section 4.1, and it was set to 0.15 m. Note that the conditions of the data sets in this positioning performance assessment were independent of the conditions of the data sets used in the optimal threshold determination in Section 4.2.

4.4 Results and Analyses

In this section, we present the assessment results of the proposed algorithm according to four aspects: positioning accuracy, computation time, identification accuracy of delayed range measurement, and robustness to parameters. The results of each factor is described in the following.

4.4.1 Positioning Accuracy

Table 3 presents the RMSEs of the seven positioning algorithms in different test scenarios. Regarding the RCSPF with delayed measurement rejection, we found that the RMSEs of twenty test points were unavailable in some positioning scenarios due to filtering divergence. Those details are analyzed later. Regarding the other six positioning algorithms, the results show that in both delayed measurement models, the proposed RCSPF can always outperform the other five algorithms. Compared to the positioning accuracies of the TS-LS, EKF, and standard particle filter (all of which do not use any strategies for delayed measurement mitigation), the proposed algorithm improves accuracy by about 29.8%, 27.6%, and 13.2% on average, respectively.

View this table:

• View inline
• View popup

TABLE 3

RMSEs of the Six Positioning Algorithms (PF: particle filter)

Positioning accuracy improvements are attributed to the two methods used in the proposed algorithm—the outlier detection method for delayed measurement identification and the RCPS method for optimization of prior particles. This can be verified by the following two pairs of comparisons. First, by comparing the standard particle filter with the robust particle filter, the effectiveness of the proposed delayed measurement identification method can be evaluated. The results show that the positioning accuracies of the robust particle filter (with the implementation of the identification method) are 3.6% to 12.8% higher than those of the standard particle filter (without the implementation of the identification method) in the six test scenarios. Second, by comparing the proposed RCSPF with the robust particle filter, the effectiveness of the proposed RCPS method can be evaluated. The results show that the positioning accuracies of RCSPF (with the implementation of the RCPS method) are 4.2% to 7.6% higher than those of robust particle filter (without the implementation of the RCPS method) in the six test scenarios. Therefore, the two methods are effective for positioning accuracy improvement.

The positioning errors at the twenty test points of the six algorithms (except the RCSPF with delayed measurement rejection) with two delay models are shown in Figure 6. As demonstrated in the figures, the greater the number of range measurements and the lesser the number of delayed range measurements, the more accurate the position estimate is. The increase of the number of delayed measurements resulted in positioning accuracy reductions in the six algorithms. When the number of direct range measurements was less than the minimum number required for accurate positioning (i.e., four), their positioning accuracies reduced significantly. This is probably because fewer direct sensors in the positioning system reduced the chance of delays canceling each other.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 6

Positioning errors at the twenty test points when the delays were simulated based on a mean-shifted Gaussian model (a) and a Rayleigh model (b)

Nevertheless, the RCSPF algorithm still performed the best among all six algorithms. When there exists delayed measurements in positioning (see Test Points 6–17 in the horizontal axis of Figure 6), the accuracy reduction of the RCSPF algorithm was much less than those of the other five algorithms, especially the EKF algorithm. This shows that the outlier detection and RCPS strategies adopted in the RCSPF algorithm are effective in positioning accuracy improvement. The RCSPF algorithm has better robustness to delayed measurements than the other five algorithms.

Although our proposed RCSPF algorithm can cope with any number of delayed measurements, in theory, since the delayed measurement identification for each range measurement is independent, the positioning accuracy would suffer from significant degradation when the number of delayed measurements was equal to or larger than half the number of all sensors. For example, as shown in Figure 6, when there are four sensors with three of them acting as delayed sensors, the maximum positioning error at a test point is almost 0.9 m. Such accuracy is generally not good enough for most indoor positioning applications.

Figure 7 presents the positioning errors of the RCSPF algorithm using the range measurements with the rejection of identified delayed measurements. By comparing the results with results of the RCSPF algorithm in Figure 6, it shows that when discarding the identified delayed measurements directly in positioning, the proposed RSCSPF algorithm suffered from filtering failure or divergence. The filtering failure is more likely to happen when there is no measurement redundancy (i.e., the number of remained measurement sensors is less than four).

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 7

Positioning errors of the RCSPF algorithm with the rejection of identified delayed measurements: (a) depicts delays that are simulated based on a mean-shifted Gaussian model and (b) depicts delays that are simulated based on a Rayleigh model.

For example, considering using four sensors for positioning when the delay is simulated by a mean-shifted Gaussian model and Rayleigh model, we found that filtering stops at the time step k = 526 and k = 488, respectively. Therefore, Figure 7(a) only shows the positioning errors up until Test Point 8, and Figure 7(b) only shows the positioning errors up to Test Point 7. After that, there is no position estimation due to the filtering failure.

An explanation for the filtering failure is that the remaining three measurements could not effectively correct and update the prior particles, causing the derived posterior position to have a large bias. This bias would be propagated into the prior position at the next time step and cause the accuracy of the prior position to be degraded. Such a degraded prior position could cause a misidentification when used for delayed measurement identification.

One possible cause of misidentification is when all of the measurements are identified as delayed measurements. When these delayed measurements are discarded, no measurements can then be used for particle updating, hence the filtering stops and fails. It should be noted that even if the filtering could keep working, the positioning errors due to the lack of measurement redundancy would accumulate over time. For example, in the positioning scenario with six sensors and Gaussian delay model (see Figure 7[a]), the positioning did not fail. However, the filtering suffered from divergence. The positioning errors at Test Points 18–20 could not be decreased even if the measurements collected at these test points were direct measurements. Therefore, it can be concluded that using a strategy of calculated ranges not only can improve the positioning availability and robustness against filtering divergence, but also actively contributes to improving positioning accuracy.

4.4.4 Robustness to Parameters λ and N_p

We further investigate the robustness of the proposed algorithm to the parameters used for the algorithm implementation, including the threshold λ used in delayed range measurement identification and the particle number N_p used for filtering. Figure 8 shows the RMSEs of the proposed algorithm with respect to the delayed measurement identification threshold λ. The results show that the RMSEs generally achieve the minimum values at or near the optimal thresholds (determined in Section 4.2). In practice, the number of sensors is the only factor that is known, so the changes of the number of delayed measurements as well as the magnitude of delays might cause the optimal thresholds given in Section 4.2 to become suboptimal.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 8

RMSEs of the proposed RCSPF algorithm with different threshold values

Nevertheless, Figure 8 shows that the positioning accuracy of the RCSPF algorithm is always better than that of the standard particle filter (in which λ = 1) even if a suboptimal threshold is selected. This reflects that the proposed algorithm is robust to the threshold value. When using the proposed algorithm in practice, users could directly choose the suggested values presented in Figure 4(c) or use the values obtained through tuning around these suggested values as the thresholds for delayed measurement identification.

Figure 9 shows the RMSEs of the proposed algorithm with respect to the particle number N_p. The RMSEs achieve the minimum values when N_p = 5,000. Beyond using 5,000 particles, there is no significant positioning accuracy improvement. This is because the prior densities have enabled the predicted particles to be distributed closer to the mean of the posterior densities.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 9

RMSEs of the proposed RCSPF algorithm with different particle values