Research on improved indoor positioning algorithm based on WiFi–pedestrian dead reckoning

Development status and main techniques of interior positioning

With the application and popularization of smart phones, its functions are gradually expanding and its performance is constantly improving. Now the rhythm of life changes, and also constantly the mobile phone function changes. At present, people’s life learning is more done indoors, so research based on location services is also deepening. As a result, the positioning result is not ideal. Therefore, more indoor positioning technology is needed to meet people’s requirements. In Du’s paper, ²¹ an indoor PDR algorithm based on received signal strength indicator (RSSI) ranging and positioning is proposed. The step detection is based on dynamic window, peak detection, and zero-crossing method. ²² The advantage is that, it can improve the positioning accuracy and reduce the positioning error range. The amount of calculation is complex, and the implementation time of this algorithm is too long. In the literature, ²³ the adaptive linear feedback process is added in the fusion algorithm, which also improves the positioning accuracy to some extent, but the change is neither obvious nor easy to achieve. ²⁴ In Qin and Xin’s paper, ²³ the support vector machine (SVM) classification and regression analysis are combined into the WiFi positioning algorithm. The state transition is used to identify the walking cycle for the step counting, but the cumulative error of the PDR algorithm cannot be reduced. ²³ In the literature, ²⁵ an indoor positioning algorithm based on inertial measurement is proposed. By measuring the step size and acceleration of the movement to judge the movement state of pedestrians, the measurement of the step size and frequency is disturbed by external signals. ²⁵ The measurements suffer from low precision, and the error area is expanded. Although the above literature improves the performance of a single positioning system through a fusion algorithm, there are still problems such as unreasonable WiFi matching weights and excessive PDR accumulation errors. The indoor positioning algorithm based on K-means clustering proposed in the literature ²⁶ is proposed to reduce the computational complexity, but the clustering algorithm is too absolute and the result is not ideal. ²⁶ Based on WiFi-PDR algorithm which puts forward the improved WiFi indoor positioning method, this article improves the matching algorithm based on the original K-nearest neighbor (KNN) algorithm, thereby reducing the amount of calculation, and then adding the weight to obtain the final WiFi positioning result. The result obtained by the WiFi positioning is used as the initial coordinates of the PDR positioning, and then the two results are fused by the Kalman filtering. ²⁷ Finally, the final positioning result is output by the post-correction module, which can reduce the accumulated errors of PDR positioning while discarding the points whose errors exceed the positioning accuracy.

WiFi positioning algorithm and improvement

The WiFi positioning method adopted in this article is KNN algorithm. The principle of KNN algorithm is, first, the fingerprint database is established in the offline phase. ²⁸ Several reference points are selected in the positioning area, and the signal strength and position information of the reference point are recorded. An AP anchor is placed in each of the four corners of the room, and the number of selected reference points is n, then the offline fingerprint library is stored in the form (x₁, y₁; RSS₁₁; RSS₁₂; RSS₁₃; RSS₁₄) … (x_n, y_n; RSS_n1; RSS_n2; RSS_n3; RSS_n4). In the online phase, by real-time acquisition of signal intensity at the undetermined point, the results obtained by the localization algorithm are matched and compared with the database, and then the position estimation at the undetermined point is obtained.

At present, the research on WiFi positioning technology mainly focuses on improving the positioning accuracy. The methods for enhancing the positioning accuracy are generally divided into two types, one is to change the positioning algorithm and the other is to filter the points in the fingerprint library to improve the fingerprint library. The accuracy of the fingerprint can narrow the error range of the positioning. If there are more points in the fingerprint database, the computation of the algorithm will be increased and the time consumption of the algorithm will be increased in the process of location. Therefore, it is necessary to filter and process these points in the fingerprint database. The implementation of KNN algorithm is to calculate the Euclidean distance between RSS samples measured in real time and RSS mean values corresponding to fingerprints in fingerprint database, and then find K fingerprints nearest to real-time sample signals. ²⁹ Finally, the position coordinates of each fingerprint are averaged or weighted averaged and the position of the target to be measured is estimated. The formula for calculating the Euclidean distance is as follows:

D = ∑ i = 1 z ( RS S i + RS S i ¯ )

(1)

where z represents the number of AP in the real scene and the number of AP selected in this article is 4. RS S i represents the signal intensity of the first point to be measured, while RS S i ¯ represents the average signal intensity of a total of k points to be measured in the fingerprint library. D stands for Euclidean distance, which is also called Euclidean metric. It is a widely used method to calculate distance in real life. Its basic meaning is the real distance between two points in m-dimensional space or the natural length of vectors between two points. The specific value is obtained by accumulating the square of the difference between the signal intensity value and the signal intensity average value of each point, and then the second root of the value is obtained, that is, the value of D. We usually discuss Euclid distance in two-dimensional or three-dimensional cases as the real distance between highlights.

The principle of Bayesian estimation is that in the online positioning stage, the posterior probability p ( L i | R ) of the point can be calculated from the signal strength R(RSS₁, RSS₂, …, RSS_n) received at each reference point; then, according to Bayes’ theorem, the formula is as follows

p ( L i | R ) = p ( R | L i ) p ( L i ) p ( R ) = p ( R | L i ) p ( L i ) ∑ i = 1 k p ( R | L k ) p ( L k )

(2)

where p ( L i | R ) is the conditional probability of the location fingerprint sample R corresponding to the real-time RSS at a known location. p ( L i ) is the prior probability at the location on the location area, the user has the same probability of appearing at all locations on the location area, and therefore, it is generally considered to be subjected to uniform distribution. In addition, the algorithm assumes that it is from an AP at a certain location. RSS is independent of each other and irrelevant. Finally, the point at which the posterior probability is the largest is the anchor point.

The KNN algorithm is relatively simple to implement, but the accuracy is low and cannot meet the requirements of precise positioning. Bayesian estimation is also difficult to use because of the cumbersome calculation and large amount of data. Therefore, this article proposes a method that not only reduces the Bayesian calculation but also improves the KNN positioning accuracy. First, K location points with a small distance from the point to be fixed are selected by the KNN algorithm, and then the Bayesian estimation is used to calculate the matching probability of each point. The obtained matching probabilities are arranged in descending order, and these points whose probabilities are below the intermediate value are discarded. Then, the remaining points are weighted according to the Euclidean distance, and finally, the positioning result is obtained as

Q i = 1 / D i ∑ i = 1 k 1 / D i

(3)

where D i is the Euclidean distance between the point to be measured and the data of the i neighbors.

PDR positioning algorithm

The principle of pedestrian track estimation is to use the initial position information and motion state of the pedestrian and to calculate the position, velocity, and direction angle at a certain moment according to the changing state of the walking direction and the position to complete the positioning. ³⁰ In this article, the WiFi positioning result is the initial value of PDR positioning, which is recorded as ( x t , y t ), b is the step size at time t, and α t is the direction angle at time t, and then the position coordinates of the time t + 1. By analogy, the state information of each step can be obtained. It can be seen that the key of PDR algorithm is how to calculate the step frequency, length, and direction angle.

In this article, the peak detection method is used to detect the number of steps. ³¹ With the built-in accelerometer of smart phone, the three-axis accelerometer can be used to measure the accelerometer, which can better adapt to the change of the mobile phone at any time and position. In order to better restore the original signal, a low-profile finite impulse response (FIR) digital filter is added in the front of the algorithm to filter out interference noise and spikes. The cut-off frequency can be adjusted according to the actual situation. After smoothing the raw acceleration data, the algorithm will search for the peaks and troughs of the waveform to identify different steps. Two thresholds, ACC and TIME, are set to filter false peaks caused by acceleration jitter that are too small or too short in duration. For the step count detection, it is expected that a similar waveform will be repeated at every other step in consideration of the user’s alternate left and right feet during normal walking. Based on this feature, we design a dynamic time warping (DTW) verification algorithm to determine whether the steps detected by peak value are real steps. DTW verification works as follows: ³² assume that peak detection produces a series of detected steps [ P 1 , P 2 , …, P n ]. Then, for P i (i < n), the DTW distance between P i and P i − 2 is calculated. If P i is below a given threshold, both P i and P i − 2 are considered to be actual steps. Otherwise, after calculating the distance between P i + 2 and P i , when P i has another chance to be verified, P i will be temporarily marked as false until P i + 2 . The distance is calculated on the normalized accelerometer waveform to reduce the effect of the amplitude.

The step detection has a great influence on the accuracy of PDR positioning. The traditional step calculation method is based on the linear model. The coefficients in the linear model are obtained through offline learning.^33,34 However, the training samples do not take the differences between many individuals into account, so the scope of application is limited. In this article, a non-linear model is used to estimate the step size. The formula is as follows

SL = K * AC C max − AC C min 4

(4)

where AC C max and AC C min are the maximum and minimum values of acceleration, respectively, and K is the coefficient. In order to get a better positioning result, it is necessary to measure K value several times, and achieve the best K value by analyzing and comparing different samples.

A common feature often found in most buildings is that buildings are constructed in a manner similar to squares or rectangles, or both. Moreover, the rooms and corridors inside these buildings tend to be aligned with the exterior of the building.^35,36 Although not all buildings are constructed in this way, many buildings are like this. Therefore, most people walking in such buildings are restricted to only follow this characteristic. Therefore, in the PDR algorithm, we make the following provisions: suppose the heading angle of the pedestrian at time t is Θ t and the heading angle at time t− 1 is Θ t − 1 , set the heading angle threshold to Θ and the heading angle variation δ , if

δ = Θ t − Θ t − 1 ⩽ Θ

(5)

It is considered that there is no change in the walking direction, and the pedestrian walks in a straight line. If δ > Θ, the pedestrian heading is considered to be in the same direction as the building.

Principle of extended Kalman filter algorithm

Because the system model in this article is non-linear, extended Kalman filter (EKF) is used for processing. The core idea of EKF is to linearize the non-linear system and then perform Kalman filtering. EKF is a suboptimal filter.^37,38 Subsequently, the proposed application of a variety of second-order generalized Kalman filtering methods further improves the estimation performance of Kalman filtering for non-linear systems. The second-order filtering method considers the quadratic term of Taylor series expansion, thus reducing the estimation error caused by linearization, but the amount of computation is greatly increased. Therefore, the first-order EKF is not widely used in practice. In summary, the first order of state estimates for non-linear models is to be obtained.^39,40 Taylor expands and applies the linear Kalman recursion formula. Thus, the local optimal solution is obtained. The EKF algorithm flow is as follows: ⁴¹ set the state equation and measurement equation of the non-linear system to

X k = g ( X k − 1 , U k − 1 ) + W k − 1

(6)

and

Z k = h ( X k ) + V k

(7)

The non-linear function g ( X k − 1 , U k − 1 ) is expanded around the filtered value X ~ k by Taylor series, and the second order or higher is omitted

X k = g ( X ~ k − 1 ) + g ′ ( X ~ k − 1 ) ( X k − 1 − X ~ k − 1 ) + W k − 1

(8)

Expanded to

X k = g ( X ~ k − 1 ) + g ′ ( X ~ k − 1 ) X k − 1 − g ′ ( X ~ k − 1 ) X ~ k − 1 + W k − 1

(9)

if

A k , k − 1 = g ′ ( X ~ k − 1 ) = ∂ g ( X ~ k − 1 ∂ X k − 1 | X k − 1 = X ~ k − 1

(10)

B k − 1 = g ( X k − 1 ) − X ~ k − 1 ∂ g ( X ~ k − 1 ∂ X k − 1 | X k − 1 = X ~ k − 1

(11)

then the formula can be converted to

X k − 1 = A k , k − 1 X k − 1 + B k − 1 + W k − 1

(12)

in the same way

Z k = X k ∂ h ∂ X ~ k | X ~ k , k − 1 + h ( X ~ k , k − 1 ) − X k , k − 1 ∂ h ∂ X ~ k | X ~ k , k − 1

(13)

Fusion algorithm and post-correction module

The EKF fusion algorithm flow is shown in Figure 1. The WiFi positioning result is used to set the initial value of the filter start value and PDR positioning. Gait detection is used to judge whether the pedestrian walks one step according to the acceleration, and the orientation is obtained according to the gyroscope, the direction sensor, and the map information. When the pedestrian completes the one-step walking action, the WiFi processing module is notified by the synchronization control module to perform the WiFi positioning solution, the iterative calculation of the measurement update, and the status update is started. In the post-correction module, the input information is the positioning result obtained by fusion, and then the matching probability of this point is calculated using Bayesian algorithm. If the matching probability is higher than the maximum matching probability of WiFi positioning alone, the fusion positioning result is the final positioning result. If the matching probability is lower than the maximum matching probability of WiFi location, the positioning result shall be saved first and the secondary positioning should be carried out. If the secondary positioning result is higher than the maximum probability, it shall be the final result, otherwise, the mean value of this result and last saved result shall be taken as the final result. The maximum matching probability is the maximum posterior probability. According to the posterior probability formula, we need to know the signal strength of the location point and the prior probability of the point. The prior probability generally obeys the uniform distribution. In the post-correction module, the result of fusion positioning is input. After obtaining the fixed-point coordinates, the corresponding K points with the smallest Euclidean distance are found in the fingerprint database. These K points have corresponding RSS values in the fingerprint database, and the point with the smallest Euclidean distance is found. The signal intensity value of fusion position is replaced by its RSS value, and the fusion position is calculated by Bayesian formula. Posterior probability is the matching probability. The positioning flow chart is shown in Figure 1.

OPEN IN VIEWER

Figure 1.

Structure flow chart of EKF-based fusion correction positioning algorithm.