The importance of the indoor positioning applications and services in many elds such as health and safety motivated the researchers to develop accurate and cost effective localization systems. In wireless positioning techniques, the position of the mobile node (MN) can be estimated by measuring the distances between the MN and the access points (APs) using ranging techniques such as Time-of-Arrival (TOA), Time-Di erenceof-Arrival (TDOA) and Received Signal Strength (RSS). However, due to dense indoor environments, multipath propagation and Non-Line-of-Sight (NLOS) introduce biases to the range measurements causing inaccurate position estimation. This paper proposes a recursive NLOS bias estimator algorithm, which corrects the range measurements by removing the estimated biases. The proposed algorithm is non-parametric and it doesn't require a priori information about the environment. Simulation results show that the proposed algorithm has higher positioning accuracy compared to the other state of the art algorithms and it outperforms them by at least 137%.
These NLOS biases are variables and their values depend on the obstacle's pro le. Where
light objects such as the glass introduce small values of the biases while heavier objects such
as metals introduce severe biases in the range estimates [
The rest of this paper is organized as follows: In section 2, the problem formulation is presented. Section 3 describes the proposed NLOS bias estimator algorithm. Section 4 describes the simulation setup and the results. Finally, the conclusions are drawn in the last section. 2
For a general indoor localization scenario and to localize the MN in a 2D plane, assume that there are N APs and a MN with a position that needs to be estimated. The range measurement ri between the AP and the MN at time ti is given by:
ri = di + bi + ni;
where di is the true distance between the MN and the AP, bi is the positive bias which follows
Rayleigh distribution or exponential distribution [
)40 m t(e35 s n m e r u s a e30 M d e t c rre25 o C s v ted20 p u rr o C15 s v e u rT100 2 4 6 (a) 20 15 10 5 00 30 20 10 0
di;1 Estimation Fig. 1b shows the e ect of the skew di;1 on the estimated biases which can be estimated by tracking the minimum (baseline) of the estimated biases ^bi as follows: Mi = min ^bj : j 2 [i j
W + 1; i]; where a controllable sliding window of length W is used to nd the minimum value of ^bi in each window. Fig. 2a illustrates the minimum baseline Mi.
2 4 6 (12) (13) (14)
Estimation The o set in Eq. 10 depends on the channel condition at t1. If the estimated bias was initialized under a NLOS condition where ^b1 = 0 and b1 6= 0, a signi cant o set will be added to the estimated biases ^bi. The o set can be estimated from the minimum baseline Mi which depends on the propagation environment, as the value of Mi drops when the channel condition improves whether by transitioning from a NLOS condition to a LOS condition or when the obstacle pro le changes. Fig. 2b plots the minimum baseline Mi which shows the bias drops resulted from LOS and NLOS transitions. Clearly, Mi and di are equivalent at the second bias drop where the magnitude of the bias drop is equal to . Therefore, is estimated by using the magnitudes of the bias drops. Consider the rst order di erence of the minimum baseline Mi given by:
Mi;i 1 = Mi
Mi 1;
BDi: The o set can be estimated by passing the bias drops BDi through a running minimum as: ^i = min j
BDj : j 2 [1; :::i] The bias drops BDi and the estimated o set ^i are shown in Fig. 3b. It is clear from Fig. 3b that the estimated o set ^i improves when the magnitude of the bias drop increases indicating an improvement in the channel condition. Speci cally, a transition from a NLOS condition to a LOS condition. Finally, the corrected estimated biases equation is given by: bci = ^bi ^ (Mi
BDi + ^i)
The true distance di and the estimated distance d^i are illustrated in Fig. 1a where d^i was obtained
by:
(18)
where its initial position starts at (1,10) and Ts = 0.001s. Recall that the range measurement
between the MN and the AP is modeled by Eq.1. The bias bi follows Rayleigh distribution [
Simulation Analysis
In this section, the state of-the-art algorithms [
The algorithms are simulated in a dynamic random environment where the MN moves with di erent speeds and mixed NLOS errors for 20s as it is shown in Fig. 4 which plots the time evolution of the true and the corrupted range measurements relative to AP1. The MN's velocity was 1m=s for the rst 10s and 0:2m=s for the next 10s. The performance of the algorithms was evaluated by calculating the absolute distance error as follows: where di denotes the true distance and d^i is the distance estimate obtained by the algorithms. Then, the error samples are used to plot the empirical CDFs to evaluate the performance of the algorithms. Moreover, the mean absolute error is given as: ei = jdi ^ dij E = 1 XN ei
N i=1
where N is the number of samples. In the polynomial tting algorithm [
Table 1 summarizes the simulation results of the algorithms where the results were obtained after changing the parameters W and R. Moreover, the minimum and the maximum E of each algorithm is recorded in the table. The error percentage relative to the minimum recursive estimator is obtained by ((E(algorithm) 0:16) 100) where 0.16 is the minimum E of the recursive estimator.
The mean absolute error E of the recursive estimator was obtained after changing the window sizes W . The algorithm achieves the highest accuracy of 0:16m when W = 600 and it achieves the lowest accuracy when W = 300. Moreover, since the PNMC uses windowing and it depends on the NLOS error distribution for the correction, the parameters W and R were changed to obtain E. The PNMC achieves the highest accuracy of 2:54m when W = 200 and R = 4.
Simulation results show that the recursive bias estimator achieved the highest accuracy compared to the polynomial tting and the PNMC algorithms without a priori knowledge of the environment by at least 137%. This is evident from Table 1 where the maximum E corresponding (19) (20) 35 30 s te25 n m e r u s a e20 M d e t c rre15 o C 10 50 to the recursive estimator is much less than the minimum E of the other algorithms. In addition, the tting in the polynomial tting algorithm was negatively a ected by the speed of the MN and the varying NLOS errors.
45 40 35 s ten30 m e r u sa25 e M 20 15 10 di ri
v = 1 m/s then v = 0.2 m/s
NLOS 0 2 4 6 8 12 14 16 18 20 10
In this paper, a NLOS bias estimator is proposed that estimates and removes the biases recursively based on the range measurements. The algorithm can be implemented in di erent indoor environments since it is non-parametric and a priori information about the channel is not required.
In addition, the algorithm was compared with two state of the art algorithms in a dynamic random environment where the MN moves with di erent speeds and experiences di erent severity of NLOS errors. Simulation results show that the proposed algorithm outperforms the analyzed state of the art algorithms by at least 137%.