An Indoor Localization Approach Based on Fingerprint and Time-Difference of Arrival Fusion

Haoyu Yang, Yuanshuo Wang, Dongchen Li, Tiancheng Li

Abstract: In this paper, an effective target locating approach based on the fingerprint fusion positioning (FFP) method is proposed which integrates the time-difference of arrival (TDOA) and the received signal strength according to the statistical variance of target position in the stationary 3D scenarios. The FFP method fuses the pedestrian dead reckoning (PDR) estimation to solve the moving target localization problem. We also introduce auxiliary parameters to estimate the target motion state. Subsequently, we can locate the static pedestrians and track the the moving target.For the case study, eight access stationary points are placed on a bookshelf and hypermarket; one target node is moving inside hypermarkets in 2D and 3D scenarios or stationary on the bookshelf.We compare the performance of our proposed method with existing localization algorithms such as k-nearest neighbor, weighted k-nearest neighbor, pure TDOA and fingerprinting combining Bayesian frameworks including the extended Kalman filter, unscented Kalman filter and particle filter (PF). The proposed approach outperforms obviously the counterpart methodologies in terms of the root mean square error and the cumulative distribution function of localization errors, especially in the 3D scenarios. Simulation results corroborate the effectiveness of our proposed approach.

Keywords: 3D indoor localization; fingerprint fusion positioning; time-difference of arrival; pedestrian dead reckoning; received signal strength

1 Introduction

Since a realistic localization problem involves complicated terrains and different environments,the 3D localization is suitable to be applied in the real life. Location-based services [1, 2] have recently received widespread attention, especially in 3D indoor navigation scenarios [3, 4]such as hypermarkets, international airports,underground parking lots and so on. The indoor travelling sales man problem (TSP) means that customers who are not really familiar with the neighbors want to plan optimal (convenient and proximal) routes when they purchase desired brands inside hypermarkets. TSP requires primarily high-precision localization estimation. The indoor navigation is becoming a research hotspot with the fast-growing demand of location-based services in indoor environments. The most popular positioning system is the global positioning system (GPS) [5] which, however, is not a viable option in some areas, especially in indoor environments, due to the localization target that cannot acquire accurate signals in indoor environments with obstructions such as reinforced concrete. GPS also relies greatly on terminal performance, and that is, satellite scanning, acquisition and positioning operations are integrated into the terminal, which results in low positioning sensitivity and high power consumption of the terminal. The indoor positioning and navigation demands are imminent. Thus, a constellation of 2D indoor localization algorithms are proposed [6-8] including ranging-based [9, 10] and non-ranging-based positioning algorithms [11-13]for different localization scenarios. However,there exist some challenges for ranging-based positioning algorithms such as multipath fading,non-line-of-sight [14] and precise synchronization.In addition, some measurement methods including time of arrival (TOA), time-difference of arrival (TDOA), angle of arrival (AOA) and received signal strength (RSS) require extra hardware requirements as shown in Tab. 1,which is compared with positioning principle, the least number of base stations (BS) and main characteristics.

Tab. 1 The explicit contradistinction of TOA, TDOA, AOA,RSS methods

Although ranging-based localization algorithms are enable to locate precisely targets, it is high-demanding for the hardware of wireless sensor networks (WSN). This makes the hardware costly-consuming and energy-intensive. So nonranging-based positioning algorithms, e.g., DVHop [12], APIT [13], fingerprint localization methods and so on, are proposed, which can not measure distances or angles between nodes and reduce hardware requirements for nodes. Moreover, fingerprint localization methods which are prevailing in non-ranging-based positioning algorithm provide higher accuracy at the expense of extensive training in order to create an offline fingerprint database in advance. This method mainly depends on the RSS vectors at the reference points (RPs) and the physical coordinates of the RPs. In the online stage, the user measures the real-time RSS vector at the target point(TP) and compares the real-time RSS vector with the RSS vectors in the fingerprint database to obtain the location of the TP by means of a matching algorithm. Fingerprint matching can be carried out by clustering methods [16]. Classifiers are divided into three categories according to their different training processes: deterministic, probabilistic and artificial neural networkbased classifiers. The deterministic classifier is represented by k-nearest neighbor (KNN) and weighted k-nearest neighbor (WKNN), which is making a correspondence between the TP(unknown location) andNRPs (known location). The representative probabilistic classifier is Bayes classifier (BC), like Horus [17, 18]. The Horus localization system [17] models the signal strength distributions received from access points using parametric and non-parametric distributions. By exploiting the distributions, the Horus system reduces the effect of temporal variations.A new fingerprint localization algorithm based on the artificial neural network classifier is proposed in [19, 20]. In the offline training phase,deep learning is utilized to train all the weights of the deep network as fingerprints. Moreover, a greedy learning algorithm is used to train the weights layer by layer to reduce complexity. In the online localization phase, a probabilistic method is used by [20] based on the radial basis function to obtain the estimated location. In order to reduce the calibration efforts, sparse fingerprint and crowd-sourcing for localization are explored in [21]. However, these fingerprint methods provide coarse location resolution due to economizing the expense of extensive training.

The reason why the Wi-Fi fingerprint localization method becomes the mainstream is that RSS measurements from the Wi-Fi access points(APs) provide a cost-effective positioning method and smartphones are convenient for everyone. However, the RSS signal is attenuated and fluctuates randomly over time and space due to transmitter/receiver antennas, the material of walls/floors, movement of pedestrians and obstacles. In this respect [22, 23], pedestrian dead reckoning (PDR) [7, 24] becomes a widely used indoor positioning method for moving targets.PDR can be used to estimate the movement of a person, by detecting steps, estimating stride lengths and the directions of motion. It can provide good performance only when a reasonable initialization of localization is available. But the PDR method accumulates estimation errors over time [25] if there is not the other auxiliary localization approach.

The information fusion between collaborative sensors provides a systematic means to compensate for deficiencies with the local sensors, to extend their fields of view and to improve the estimation accuracy and robustness, and so has been intensively studied [26-28]. Nonlinear filters,including extended Kalman filter(EKF) [29],unscented Kalman filter(UKF) [30], and particle filter(PF) [31], have been applied to indoor positioning methods, which use PDR as the equation of motion and WiFi fingerprint positioning as measurement data. State transition updates under Markov assumption. Researchers have proposed new methods fusing PDR and fingerprint localization algorithms [32-35] to solve the 2D moving target problem indoors. A fusion algorithm which integrates PDR approach and Wi-Fi fingerprinting method based on the improved WKNN algorithm is proposed in [32] to acquire accurate and continuous positioning trajectory. A hybrid solution is proposed in [33] through the exploitation of the unique characteristics of existing technologies and compensating each other’s drawbacks. Wi-Fi Fingerprinting is implemented to perform localization when a position of the pedestrian is completely unknown. After narrowing down with the Wi-Fi positioning results, a particle filter, powered by Magnetic Field Fingerprints, is utilized to provide a maintainable and accurate tracking system. A hybrid algorithm which integrates PDR approach with WiFi fingerprinting approach is proposed in [34] to further improve positioning accuracy. A novel fusion-based indoor positioning system (IPS) is presented in [35] that fuses the sensory data of three popular smartphone sensor technologies,i.e., WiFi, bluetooth low energy (BLE) and PDR to achieve a superior indoor localization accuracy. For the 3D scenarios, the robustness [3] of 3D indoor localization based on fingerprint technique is analyzed in a simple scenario. Due to high dimensional localization, the fingerprint method not only requires impractically extensive training to establish an offline 3D fingerprint database, but also can not guarantee the localization stability. So this paper presents an 3D effective target locating approach based on the fingerprint fusion positioning method which fuses the time-difference of arrival (TDOA) and RSS.

The main contributions of the paper are enumerated herein.

1) The fingerprint fusion positioning (FFP)method is proposed in the 3D indoor scenarios.The key of FFP approach is fusing the 3D fingerprint and TDOA methods to improve the estimated accuracy.

2) For static and dynamic scenarios, our 3D indoor FFP method is distinguished between the space-based and time-based position fusion algorithm. The former is our FFP method applied in 3D stationary scenarios, while the later combines FFP results and PDR estimations in each time interval to solve dynamic localization problem.

3) According to the target acceleration, two above fusion methods are converted alternatively,which is a systemic localization mode.

The rest of this paper is organized as follows.Section 2 introduces three basic indoor localization approaches based on the improved fingerprint positioning method, TDOA and PDR,respectively. Section 3 describes two versions of our fusion algorithms for static and dynamic scenarios, and presents a systemic localization mode.Section 4 provides simulation results and compares it with other traditional localization methods in 2D or 3D scenarios. Section 5 concludes our work.

2 Preliminaries

2.1 Wi-Fi Fingerprint Positioning

The Wi-Fi fingerprinting method is the most widely used and practical algorithm in all indoor positioning algorithms. The method comprises primarily two phases: training and testing. During the training phase, the RSS radio map is generated at each of the fingerprint localization, as follows

where TPk=[xk,yk,zk] denotes thek-th target position, RSSk=[s1,k,s2,k,s3,k,...,sm,k] denotes thek-th Wi-Fi signal fingerprint vector, which is correspondingMAPs,fRSS(·) denotes the mapping function between T Pkand R SSk.

The fingerprinting database is built and updated in the RSS framework which is labourintensive and time-consuming, especially in the 3D scenarios. Subsequently, the position can be determined by the minimum distance between test RSS vector and fingerprint RSS data. Clusters are used to match the current signal information with the corresponding position in the database. Deterministic classifiers, like KNN,WKNN are used in the rest of this paper. Without loss of generality, the distancedibetween NOkand R SSi,kcomplies with

where NOkrepresents the fingerprint signal vector of the targetk, RSSi,krepresents the nearest neighbor RPs matched by the WKNN algorithm.Parametersp=1 andp=2 represent the Manhattan and Euclidean distance, respectively.When thepnorm is introduced, the relationship between values ofpand the positioning accuracy can be analyzed in Fig. 1 about the Case 1 simulation, according to the cumulative distribution function (CDF) and root mean square errors(RMSE) with WKNNpnorm with repeatedly position 1 000 times.

Asp=1 is the most accurate WKNN positioning estimation, hereafter we adoptp=1.Subsequently, the distancedibetween the reference point position andKRPs are selected as the weightWi. The coordinate of test target positions can boil down to

Fig. 1 Case 1 of CDF with differentp

whereWiis the weigh ofKRPs according to the distancedi,εis a positive minor to prevent the divisor from zero in the formula.

The indoor Wi-Fi fingerprint method has obvious instability, which can be manifested as:On the one hand, the instability of Wi-Fi signal,on the other hand, accuracy fluctuation caused by the positioning weightWi. It is worth pointing out that, when the target is located on a reference point or in the center of several reference points, the weight corresponds well; but when the target is at a non-special point, since the real weight cannot be obtained, the TP can be approximated by the weightWi. Therefore, the farther from the special point the position is, the greater the approximated error is. Fluctuations are more obvious for the moving target than stationary targets.

2.2 RSS Geometric Positioning

According to the Wi-Fi propagation model, the distancedbetween APs and the target can be estimated. The localization estimation is performed through the ranging-based positioning algorithm. We suppose that the Wi-Fi propagation model can be

Assuming that there areMAPs distributed arbitrarily, the distancedihas been calculated by Eq.(6). For simplicity, the indexiis presumed to run from 2 toMin the sequel unless otherwise specified. Let the TP be at the unknown location (x,y,z) and the APs at known locations(xi,yi,zi). The squared distance between the TP and APsiis

2.3 Pedestrian Dead Reckoning

A modern smartphone is typically equipped with inertial measurement unit (IMU), which measures the phone mobility. IMU [36] is an electronic device composed by an accelerometer, a gyroscope, and a magnetometer that measure gravity, orientation, and velocity, respectively.Step detection, stride length and heading direction estimation are three indispensable procedures during PDR. The position can be estimated in each localization interval, according to the three procedures. If we simply use PDR, the error will be accumulated [32].

1) Step Detection: The accelerator exhibits periodically repetitive patterns that represent the behavior of human walking. It can provide step counting and achieve a highly accurate value about 98% [40]. When the user is walking, the generated changes in the acceleration across all three axes are recorded asX-Y-Zacceleration data. To convertX-Y-Zacceleration data into the step count, it is used to find the local maxima of its magnitude. With a predefined thresholdϱ, the peak with a minimum height aboveϱis considered as a step. The value ofϱshould be learned from experiments to match the user’s movement behavior.

2) Orientation Reckoning: This information is obtained from the gyroscope and the magnetometer to provide an absolute direction with respect to the Earth coordinate system and the relative direction changes with respect to the phone platform. We employ the gyroscope to monitor moving direction, while incorporating with the compass in the magnetometer to support the direction of the moving trajectory. Then by transforming the coordinate system, we can obtainθandφwhich represent the azimuth and the pitch angle, respectively.

3) Stride Estimation: By multiplying user stride lengths, we can convert a number of steps into a physical distance in meters. For instance,assuming that the user’s stride length is about 0.43 m and the number of footstep counts is 100,the user has moved a distance about 43 m. To obtain an accurate walking distance, the characteristics of the stride length are necessary. A pedestrian may exhibit different stride lengths due to the variety of walking speed and style.[41]

PDR [24, 42] uses inertial sensors to measure the acceleration and direction of motion,which combines the two parameters mathematically to obtain the trajectory of the pedestrian as shown in Fig. 2. The relationship between thenth step and the (n+1)-th step is as follows

where (xn,yn,zn) and (xn+1,yn+1,zn+1) represent the position coordinate of then-th and of (n+1)-th steps,respectively,lrepresents the estimated step length,snrepresents thenth estimation the number of steps,θrepresents the azimuth angle andφrepresents the pitch angle.

Fig. 2 Schematic diagram of PDR positioning method

3 Proposed Fusion Approach

In this section, the space-based fusion method integrates the TDOA estimation into the fingerprint localization result, which is our FFP method applied in 3D stationary scenarios. The time-based fusion method combines PDR time series prediction into former estimation results for moving targets because of unknown statistical variances. Then we propose a systematic indoor positioning mode, which distinguishes the motion scenario and adopts different positioning methods according to distinctive demands.

3.1 Space-Based Position Fusion

In the stationary scenarios, the Wi-Fi fingerprint methond is labour-intensive and time-consuming.So we propose the FFP method, which fuses the Wi-Fi fingerprint and TDOA method for 3D localization. This approach can not only avoid the instability of RSS clusters, but also weaken

Fig. 3 Space-based position fusion algorithm flowchart

3.2 Time-Based Position Fusion

Dynamic indoor positioning problem has always been the difficult in the field of indoor localization. According to the Bayesian filter [43], the fusion result between the above positioning results and PDR estimations has been performed for moving targets. Simulations show that the positioning accuracy is better than the fusion result of pure Wi-Fi fingerprint and PDR.

We consider CartesianX-Y-Zcoordinates,namely the state vectorx¯=[x,y,z,s,θ,φ]T, where(x,y,z)denotes the position coordinates calculated by the track,sdenotes the number of pedestrian steps.θandϕdenote the azimuth angle and the pitch angle, respectively. Set the measurement vector asz¯ =[xwf,ywf,zwf,spd,θpd,φpd]T,where (xwf,ywf,zwf) denotes the localization coordinates obtained by Wi-Fi fingerprint fusion positioning, (spd, θpd,φpd) denotes parameters given by PDR, according to accelerometers, magnetometers and gyroscopes, respectively.

Consider the following state space model as

We make the following assumptions:

1) The probability density function of the initial statep(x¯0) is known;

2) The system state applies a hidden firstorder Markov model;

3)wkandvkare the i.i.d. additional Gaussian white noise.

Predicting and updating equations are given as

whereC=∫p(z¯t|x¯t)pˆ(x¯t-1)dx¯tis the normalization coefficient. The FFP and PDR results are fused by the Bayesian framework as the extended Kalman filter (EKF), unscented Kalman filter(UKF), particle filter (PF) [31] derived by Eq.(14), respectively.

Sequential importance sampling (SIS) is a method based on Monte Carlo estimation, which

A ∝Bdenotes thatAis proportional toB.

However, there exists the particle degeneracy problem for the SIS algorithm. Degradation not only weakens the diversity of particles, but also spends most of the computation on useless particles, which seriously affects the computational efficiency of particle filtering. To solve this problem, resampling may be applied in certain or all filtering steps [44], leading to the sequential importance resampling (SIR). A benchmark to measure the degree of particle degeneracy is given as

3.3 Systematic Indoor Positioning Mode

We propose a systematic indoor positioning mode, which distinguishes the motion scenario and adopts different positioning methods. We define the auxiliary parameterJaas

4 Simulation Results

The simulation scenarios are that eight access stationary points are placed on a bookshelf and hypermarket; one target node is moving inside hypermarkets in 2D and 3D scenarios or stationary on the bookshelf. We evaluate the performance of our FFP algorithm and compare it with the KNN, WKNN fingerprint approach and the TDOA method [39] in the 3D stationary scenario. Meanwhile, the time-based position fusion algorithm is compared with the fingerprint approach, the TDOA method and EKF fused WKNN and PDR. Blue stars denote the position of APs in every simulation scenarios for 200 Monte Carlo runs. Our simulations are based on MATLAB (R2018a) implementations on an AMD R7-4800H CPU.

4.1 Case Study 1: 3D Stationary Target

We consider a simple example of a stationary target placed on a bookshelf, which is similar to[3]. In this respect, the bookshelf is deployed as the area of interest that has the dimension of 10 m× 10 m× 5 m as shown in Fig. 4. There are 10×10×20reference nodes for the fingerprint localization method. The red circle denotes our target position at [8 m, 8 m, 1 0 m]. The positioning error is the difference between the estimated position and the actual position. In other words,the positioning error and CDF are calculated as

whereTn=1000,x=[x,y,z] is the true position of the static node andxˆi=[xˆi,yˆi,zˆi] is the position estimate for thei-th Monte Carlo run,‖·‖2denotes thel2-norm.

whereri=‖x-xˆi‖2,‖·‖2denotes thel2-norm andεis the positioning error in Fig. 5(a).

Fig. 4 Illustration of the experiment environment

Fig. 5 CDF and RMSE compared with different methods:(a)CDF; (b)RMSE and SD

The target is independently located 1 000 times compared with the KNN, WKNN fingerprint methods [3], the TDOA approach [39] and our method. The CDF and RMSE can be illustrated as Fig. 5(a) and Fig. 5(b). Our proposed method outperforms obviously the existing methods in terms of localization RMSE and its standard deviation. The details are given in Tab. 2.In this subsection, we detail a 2D example of a moving pedestrian in a hypermarket. Fig. 6 shows the pedestrian trajectory and the second floor map which is a 500 m× 500 m area in the hypermarket. The trajectory and performance are compared the EKF fused WKNN with PDR as W-EKF [32] and our methods (we propose the EKF, UKF, PF fused the FFP and PDR estimation as F-EKF, F-UKF, F-PF). In this case, the mean absolute error (MAE) and RMSE are defined respectively as

Tab. 2 Specific values of RMSE and standard deviations(SD)for the stationary scenario

4.2 Case Study 2: 2D Moving Target

Fig. 6 The trajectory of 2D moving pedestrian

andxˆi(k)=[xˆ(k),yˆ(k)] is the position estimate at time stepkfor thei-th Monte Carlo run,‖·‖denotes thel1-norm.

Fig. 7(a) shows the accuracy fluctuation of the traditional fingerprint method for moving pedestrians, especially KNN. The performance of TDOA is worse when the target is far from APs near 92 s, 144 s and 175 s. Average RMSE is given by bars and standard deviations are depicted by black line, which is illustrated as Fig. 7(b).

Fig. 7 2D scenario of RMSE for 200 runs:(a)RMSE of every instance;(b)RMSE and SD of different methods

In the nutshell, we can evaluate the performance and find our proposed approach is slightly better than other traditional methods in the 2D scenarios regardless of RMSE and standard deviations. So, our proposed method outperforms slightly the counterpart methodologies. But our method increases the computational complexity in the 2D scenarios as shown in Tab. 3.

Tab. 3 Specific values of RMSE and standard deviations for the 2D scenario

4.3 Case Study 3: 3D Moving Target

In order to achieve indoor localization without blind spots, we consider a more complex example of a moving pedestrian going down stairs in the hypermarket as shown in Fig. 8.

Fig. 8 The trajectory of 3D moving pedestrian

Fig. 9(a) shows the accuracy fluctuation of the traditional fingerprint method with 3D KNN for moving pedestrians. It is worthy pointing out that the performance of the 3D TDOA is better than the 2D scenarios because the height information weakens the multi-path effect. The estimation of W-EKF is worse than our proposed method. We illustrate the effectiveness of the proposed method in comparison with KNN,WKNN [11], TDOA, W-EKF [32] in Fig. 9(b).

Thus, our proposed method outperforms obviously the counterpart methodologies in terms of localization error and its standard deviation.The proposed method is suitable for 3D indoor localization scenarios such as hypermarkets,international airports and so on. Tab. 4 gives the specific values of RMSE and standard deviations for the 3D scenario.

Fig. 9 3D scenario of RMSE for 200 runs:(a)RMSE of every instance;(b)RMSE and SD of different methods

Tab. 4 Specific values of RMSE and standard deviations for the 3D scenario

5 Conclusion

In this paper, we propose new positioning fusion algorithms based on space and time. The former fuses the TDOA estimation and an improved fingerprint positioning result in the 3D stationary scenario. This method overcomes the Wi-Fi signal fluctuations yielding a satisfactory localization accuracy. At the same time, the later named a time-based positioning fusion algorithm combines the space-based result and PDR data,which can eliminate the PDR error-accumulating problem and improve positioning accuracy in the 3D dynamic scenarios. The simulation experiments were analyzed more comprehensively compared to the conference version [46]. It can be confirmed our proposed approaches outperform the traditional counterpart methodologies in terms of the MAE, RMSE and CDF, especially in the 3D scenarios. Simulation results corroborate the effectiveness of our approaches.

Future work includes developing physical experiments to further verify the feasibility and robustness of methods and a real-time positioning system that localize as we go. The indoor localization without blind spots can be achieved.The fingerprint location can slightly differ with untrained labours, and it of course affects the localization performance.