Extended Kalman Filter for Real Time Indoor Localization by Fusing WiFi and Smartphone Inertial Sensors

Abstract

Indoor localization systems using WiFi received signal strength (RSS) or pedestrian dead reckoning (PDR) both have their limitations, such as the RSS fluctuation and the accumulative error of PDR. To exploit their complementary strengths, most existing approaches fuse both systems by a particle filter. However, the particle filter is unsuitable for real time localization on resource-limited smartphones, since it is rather time-consuming and computationally expensive. On the other hand, the light computation fusion approaches including Kalman filter and its variants are inapplicable, since an explicit RSS-location measurement equation and the related noise statistics are unavailable. This paper proposes a novel data fusion framework by using an extended Kalman filter (EKF) to integrate WiFi localization with PDR. To make EKF applicable, we develop a measurement model based on kernel density estimation, which enables accurate WiFi localization and adaptive measurement noise statistics estimation. For the PDR system, we design another EKF based on quaternions for heading estimation by fusing gyroscopes and accelerometers. Experimental results show that the proposed EKF based data fusion approach achieves significant localization accuracy improvement over using WiFi localization or PDR systems alone. Compared with a particle filter, the proposed approach achieves comparable localization accuracy, while it incurs much less computational complexity.

1. Introduction

Locating mobile objects enables various location based services [1] including object finding, human tracking, and emergency management, etc. In outdoor environments, Global Navigation Satellite Systems (GNSS) have been widely used in mobile devices and provided reasonable localization accuracy performance. Unfortunately, due to the GNSS signal attenuations, they are incapable of tracking indoors, where people spend the majority of their time. Though various indoor localization systems, such as WiFi localization using received signal strength (RSS) [2], ultra-wideband [3], radiofrequency identification (RFID) [4], and inertial sensors [5], have been developed, it is still a challenging task to provide accurate indoor localization with low cost.

WiFi localization systems using RSS have been considered as the most popular indoor localization approach due to its cost effectiveness. RSS readings can be easily collected by common smartphones with WiFi modules installed under the pervasively available WiFi infrastructures. The most widely used method for WiFi localization is a fingerprinting [6,7] based architecture. It collects RSS data from access points (APs) on predefined reference points to construct a database called radio map during offline phase, while it matches real time collected RSS with radio map to estimate the location during online phase. However, accurate localization results cannot be guaranteed by WiFi localization due to the severe RSS fluctuations [8,9] caused by complex indoor radio propagation conditions.

On the other hand, more and more smartphones with inertial sensors built in, including gyroscopes and accelerometers, make it feasible to deploy pedestrian dead reckoning (PDR) systems [10,11] in our daily lives. PDR systems estimate relative displacement by step detection and user heading estimation. If the initial user location is known, accurate absolute location estimation may be achieved when a pedestrian travels a short distance. In addition, PDR systems on smartphones are self-contained without requiring any external infrastructures. However, PDR systems incur drift error accumulations [12,13,14] along walking distances, especially for inexpensive but noisy inertial sensors built in smartphones.

Both systems mentioned above have their limitations and complementary strengths. WiFi localization systems provide necessary corrections for PDR systems to bind the accumulative drift errors, while PDR systems enable continuous tracking and smooth the localization results. Therefore, it is essential for indoor localization to fuse WiFi localization and PDR, which will obtain more significant performance improvement rather than deploying them alone.

Even though a lot of work [15,16,17,18,19,20,21,22] has been done in fusing both systems, some critical problems still need to be addressed to enhance accuracy and feasibility. On the one hand, previous data fusion approaches mainly focus on deploying a particle filter [18,19,20,21], which is computationally expensive and should be run on a server. However, rather than in a server, the localization system runs on a smartphone and is preferred due to its ability to protect the user’s privacy. Furthermore, the server based approaches involve a time consuming communication process, which is unsuitable for real time applications. On the other hand, light computation algorithms including Kalman filter and its variants cannot be directly deployed, since an explicit measurement equation and related noise statistics are not available. Therefore, it is a crucial task for real time indoor localization to develop a light computation fusion system run on resource-limited smartphones. In this paper, a novel data fusion framework based on extended Kalman filter (EKF) is firstly designed and implemented. In order to make EKF applicable, we develop a measurement model using kernel density estimation (KDE), which accurately characterizes the RSS-location relationship and adaptively measures the related noise statistics. For the PDR system, we accomplish another EKF for user heading estimation by fusing gyroscopes and accelerometers. In order to avoid singularity problems and reduce computation cost, we describe the device orientation by quaternions rather than Euler angles and direction cosine matrix (DCM). Experiments in a realistic indoor environment show that, the proposed EKF based fusion approach achieves significant accuracy improvement with respect to the individual approaches. Compared with a particle filter, the proposed EKF based fusion approach obtains comparable accuracy performance, while it reduces computation cost greatly.

2. Related Works

For indoor environments, though various localization approaches have been proposed, the optimal strategy is still an open issue. Recently, with the pervasive availabilities of WiFi infrastructures and low-cost inertial sensors built in smartphones, both WiFi localization and PDR systems have been considered as promising solutions for indoor localization. Consequently, due to their complementary strengths, fusing both systems has been paid increasing attention.

The earliest work fusing WiFi signals and inertial data is found in [18]. A particle filter is used to combine the pedestrian motion model, WiFi signals, and building maps. When the user’s current step is detected by an accelerometer, the estimated walking direction and step length are fed into the particle filter as a motion model to predict the new positions of particles. Then, the weight of a particle is updated by computing a Gaussian function of the Euclidean distance between the particle and the WiFi localization result, which is achieved by K-nearest neighborhood algorithm [23]. For PDR system, heading estimation is derived from the integration of gyroscope data, which are collected by a sensing box attached to the belt of a pedestrian. To compensate the integration drift error of heading estimation, a Kalman filter is deployed by fusing angles of the trajectory delivered in the WiFi localization system. Similar work can be found in [19], where a sequential importance resampling particle filter is applied to fuse a low-cost accelerometer, compass, and WiFi signals. Vertical acceleration signals are deployed to detect steps, while the user heading is obtained from a compass. In contrast to the particle updating scheme in [18], the weight of a particle is updated by the inverse Euclidean distance between real time collected RSS and RSS signals in the radio map.

In [20], Rai et al., propose an augmented particle filter, which simultaneously estimates location, step length, and user heading. For the PDR system, the user heading is firstly estimated by a compass, and then updated by the user’s trajectory in the measurement model of the augmented particle filter. For the WiFi localization system, the probability of observing real time RSS vector at the location of particles is computed as in [24], and then used to update the weight of particles. The key idea is that regular indoor layout information such as straight corridors may be exploited to correct the user’s path and related orientations. However, for a spacious indoor environment, there is always not enough layout information available, thus significantly degrading the performance of the augmented particle filter. In order to make the system as simple as possible to the user, instead of dedicated specific procedures, an auto-calibration procedure is further adopted in [21] to reduce the magnetic measurement errors. Though significant performance improvement is obtained, the calibration procedure model is founded on the two-dimensional horizontal plane and is inapplicable for the more common three-dimensional case.

Recently, a light computation approach based on Kalman filter is proposed in [22] to fuse PDR and WiFi localization. In real experiments, the proposed approach achieved significant improvements over individual approaches, while it reduced computation cost greatly. This approach formulates PDR as a linear function and considers the user heading estimated per step as known input vector without noise being introduced. As a result, significant estimation bias happens when Kalman filter computes the a priori error covariance of the state vector, thus degrading the performance of Kalman filter. For the WiFi localization system, the user location is estimated by the weighted coordinates of APs. The weights are normalized inverse physical distances between device and APs, which are computed by the RSS signal propagation model. Due to complex indoor radio propagation environment, the signal propagation model may be so inaccurate that little location information is obtained to correct PDR, especially when the number of APs available is limited and sparsely distributed in a large scale region.

Due to the heavy computational burden, the particle filter based approach should be run on a server and is unsuitable for real time applications. We propose a light computation fusion approach based on EKF. For heading estimation in the PDR system, instead of using a compass, we only deploy a gyroscope, since severe magnetic perturbations render poor performance of the compass in most indoor environments [25,26]. The perturbations are caused by universally available electromagnetic devices and magnetization of intricate modern structures, which include steel walls and concrete floors. Therefore, the perturbations always show complex patterns in terms of changing magnitudes and directions at different locations [26], and are difficult to be modeled and calibrated. Since gyroscopes can only provide relative heading change estimation, we assume that the user’s initial orientation is known as a priori in this paper. In fact, it can be obtained by various methods, such as Global Positioning System (GPS) tracking when pedestrians enter buildings [16], landmarks [27], and WiFi localization [28]. Furthermore, in order to guarantee accurate heading estimation from gyroscope data, a self-calibration procedure called “zero attitude updates” [29,30] is deployed to calibrate and compensate the gyroscope bias errors effectively. In our experiments, a zero attitude update, similar to the one implemented in [30], is performed just at the beginning of each experiment.

For device orientation representations of gyroscopes, there are mainly three kinds of descriptors: Euler angles [5], DCM [31], and quaternions [29]. The Euler angle based method is conceptually easy to understand, but it is computationally expensive and incurs singularity problems [32]. Both DCM and quaternion based methods may avoid the singularity problems. However, the quaternion based method requires much less computations than DCM, since it is easier to be normalized and needs only four variables updated during state propagating procedure. Therefore, we deploy quaternions for device orientation representations. Furthermore, to compensate the heading estimation drift caused by the tilt of hand-held smartphones, we develop an EKF to fuse the three dimensional gyroscope and accelerometer signals, which may infer tilt angles of smartphones.

For the WiFi localization system, due to various factors, such as obstacles, human body attenuations, and multi-path effects, it is impossible to construct an explicit equation for characterizing RSS-location relationship [24]. In [33], a stochastic model is developed to characterize the RSS-location relationship, with the posterior density approximated by a particle filter. In this paper, we deploy KDE [34] for density estimation to develop a RSS-location measurement model. The developed model may adaptively measure the noise statistics of WiFi localization, which cannot be achieved by previous fusion approaches. Besides, we further reduce the computation cost by restricting WiFi localization into the vicinity of the estimated location of the previous user step. Therefore, as shown in our experimental results, the proposed EKF based fusion approach obtains comparable accuracy in comparison to a particle filter, while it reduces computational complexity greatly.

3. Methodology

Figure 1 presents the architecture of the proposed EKF based fusion approach on smartphones. The proposed approach includes two EKFs. The first EKF is used to integrate gyroscope with accelerometer for heading estimation of PDR. The second EKF achieves the location estimation by fusing the WiFi localization system and PDR system. The measurement model of the second EKF is the developed RSS fingerprinting algorithm based on KDE. In addition, a spatial filtering process is introduced to restrict the WiFi localization into a sub-region. The state model of the second EKF is the PDR system, which comprises step detection, step length estimation, and quaternion based heading estimation modules.

Figure 1. Architecture of the proposed extended Kalman filter (EKF) based fusion approach.

Figure 1. Architecture of the proposed extended Kalman filter (EKF) based fusion approach.

3.1. Pedestrian Dead Reckoning

We deploy the smartphone inertial sensors, including an accelerometer and a gyroscope, for pedestrian dead reckoning. Theoretically, the pedestrian walking distance can be obtained by the double integration of acceleration signals. However, this approach suffers from unbounded error growth due to sensor noises. An effective solution is the PDR approach, which detects the walking step, estimates the step length and user heading. Thus, the position of the current step can be determined by the position of a previous step as follows:

$$L_i\text{ = }{L}_{i-1}\text{ + }{d}_i\left[\begin{array}{c}\text{ cos(}{\tilde{\psi }}_i\text{)}\\ \text{sin(}{\tilde{\psi }}_i\text{)}\end{array}\right]$$

(1)

where $L_i\text{ = }\left(x_i,y_i\right)$ is the estimated coordinates of the $i\text{th}$ step, $d_i$ is the estimated step length of the $i\text{th}$ step, and ${\tilde{\psi }}_i$ is the estimated user heading. In this paper, we assume that the initial user’s location and walking direction are known, which can be obtained by various methods, such as the user’s input [11] and GPS tracking when a pedestrian enters a building [16].

3.1.1. Step Detection and Step Length Estimation

Steps can be detected based on periodic acceleration fluctuation patterns during walking. To avoid the negative effect of the accelerometer unit tilt, we deploy the norm of measured three dimensional acceleration signals for step detection, since the pattern of acceleration signal norm is insensitive to different device orientations. To reduce the acceleration signal noise, a smoothing function [22] is deployed to average the raw acceleration data. After smoothing the raw data, a peak detection algorithm is applied to identify a distinct step, as shown in Figure 2. Two thresholds are used to filter out false peaks caused by acceleration jitters with too small magnitude or too short time intervals,

$$\{\begin{array}{l}\Delta T\ge T_{\text{Th}}\hfill \\ \left|AccNorm-g\right|\ge A_{\text{Th}}\hfill \end{array}$$

(2)

where $\Delta T$ is the time interval between adjacent peaks, $AccNorm$ is the norm of the measured three dimensional acceleration signal, $g$ is the value of local gravity, $T_{\text{Th}}$ and $A_{\text{Th}}$ represent the time threshold and the magnitude threshold for peak detection, respectively. Practically, the time threshold is set around two-thirds of the walking period. The false peak with a small magnitude will be easily filtered out by the magnitude threshold $A_{\text{Th}}$. For the false peak with a magnitude exceeding $A_{\text{Th}}$, the motion law of the pedestrian walking makes the time interval between it and true peak within one step much shorter than the time threshold, and thus they can be easily distinguished between each other [11,12]. As shown in Figure 2, the marked false peak exceeding $A_{\text{Th}}$ will be firstly considered as a peak for a new step, if the time interval between it and the previous peak exceeds the time threshold. Then, this will be corrected by the following true peak with bigger magnitude and shorter time interval than the time threshold.

Figure 2. Peak detection based on periodic patterns of the acceleration norm.

Figure 2. Peak detection based on periodic patterns of the acceleration norm.

The step lengths are determined by various factors, including height, attitude, and walking frequency [11,35]. Since step length models for different pedestrians vary a lot, it is difficult to develop a generic model that is accurate for all pedestrians. For the same person, the step length mainly depends on the walking speed. Therefore, we apply the empirical model [36] to estimate the step length in Equation (1) as follows:

$$d_i=C_1\sqrt[C]{Ac{c}_{\max }^i\text{-}Ac{c}_{\min }^i}$$

(3)

where $Ac{c}_{\max }^i$ and $Ac{c}_{\min }^i$ represent the maximum and minimum of acceleration signal norms for step $i$, C and $C_1$ are the personalized coefficients for different pedestrians. The coefficients can be easily estimated by counting steps when pedestrians travel a known distance.

3.1.2. First EKF: Quaternion Based Heading Estimation

All inertial data, including three dimensional accelerations and angular velocities, are measured in a right-handed body frame $B$ attached to the smartphone by axes $X_B$, $Y_B$ and $Z_B$. Define the front face of the screen as a plane $FR$. The $X_B$ axis is parallel to $FR$ and points to the right; The $Y_B$ axis is parallel to $FR$ and points forward; The $Z_B$ axis is perpendicular to $FR$ and points outside of $FR$. Thus, the orientation of a smartphone is determined when the axis orientation of the frame $B$ is specified with respect to the absolute coordinate system called navigation frame $NA$. Note that, during walking, the user heading may be different from the smartphone forward when a smartphone is put in a pocket or a bag. This paper only considers the most common hand-held situation [17,18,19], in which the smartphone is held in a hand faced in front. The smartphone’s forward axis is always the same as the user’s walking direction at the horizontal level frame. Therefore, we assume that the smartphone forward and the user heading are aligned in the same direction.

We apply rotation quaternion to describe the time model of smartphone orientations, since it can avoid the singularity problems and require the least computations [32]. First, we construct the relationship between a quaternion and the smartphone orientation. The transformation from frame $NA$ to $B$ can be represented as follows:

$$h^b\left(t\right)=C_n^b\left(q\left(t\right)\right)h^n\left(t\right)$$

(4)

where $C_n^b\left(q\left(t\right)\right)$ is the direction cosine matrix (DCM), $h^b\left(t\right)$ and $h^n\left(t\right)$ is the $3\times 1$ column-vector at time $t$ relative to $B$ and $NA$. For the sake of simplicity, the argument $t$ will be omitted. We deploy the rotation quaternion to describe the DCM,

$$C_n^b\left(q\right)\text{= }\left[\begin{array}{ccc}{q}_0^2+q_1^2-q_2^2-q_3^2& 2\left(q_1{q}_2+q_0{q}_3\right)& 2\left(q_1{q}_3-q_0{q}_2\right)\\ 2\left(q_1{q}_2-q_0{q}_3\right)& q_0^2-q_1^2+q_2^2-q_3^2& 2\left(q_0{q}_1+q_2{q}_3\right)\\ 2\left(q_1{q}_3+q_0{q}_2\right)& 2\left(q_2{q}_3-q_0{q}_1\right)& q_0^2-q_1^2-q_2^2+q_3^2\end{array}\right]$$

(5)

where $q\text{= }{\left[\begin{array}{cc}{q}_0& \begin{array}{ccc}{q}_1& q_2& q_3\end{array}\end{array}\right]}^T$ is the normalized orientation quaternion, $q_0$ is the scalar part and $q_1,q_2,q_3$ is the vector part of the quaternion. Therefore, the orientation of a smartphone with respect to navigation frame $NA$ is described by three angles as follows:

$$\{\begin{array}{l}yaw=\arctan \left(2\left(q_0{q}_3-q_1{q}_2\right)/\left(q_0^2-q_1^2+q_2^2-q_3^2\right)\right)\\ pitch=\arcsin \left(2\left(q_2{q}_3+q_0{q}_1\right)\right)\\ roll=\arctan \left(2\left(q_0{q}_2-q_1{q}_3\right)/\left(q_0^2-q_1^2-q_2^2+q_3^2\right)\right)\end{array}$$

(6)

Secondly, according to the rigid body kinematic equations [32], the discrete-time model of orientation quaternions can be given as:

$$q_{k+1}\text{ = }\exp \left(0.5\times \Omega \left(w_k{T}_{\text{s}}\right)\right)q_k=\left(I\cos \left(0.5\times \Delta {\text{θ}}_k\right)+\Omega \left(w_k{T}_{\text{s}}\right)\sin \left(0.5\times \Delta {\text{θ}}_k\right)/\Delta {\text{θ}}_k\right)q_k$$

(7)

where $T_s$ is the system interval, $w_k={\left[\begin{array}{ccc}{w}_k^x& w_k^y& w_k^z\end{array}\right]}^T$ is the output of gyroscope at time instants $k{T}_s$, $I$ is an identity matrix, $\Delta {\text{θ}}_k=T_s\sqrt{{\left(w_k^x\right)}^2+{\left(w_k^y\right)}^2+{\left(w_k^z\right)}^2}$, $q_k$ and $q_{k+1}$ are the quaternions at time instants $k{T}_s$ and $\left(k+1\right)T_s$ respectively, $\Omega \left(w_k{T}_s\right)$ is given as follows:

$$\Omega \left(w_k{T}_s\right)=T_s\left[\begin{array}{cccc}0& -w_k^x& -w_k^y& -w_k^z\\ w_k^x& 0& w_k^z& -w_k^y\\ w_k^y& -w_k^z& 0& w_k^x\\ w_k^z& w_k^y& -w_k^x& 0\end{array}\right]$$

(8)

The quaternion at time instants $\left(k+1\right)T_s$ is determined, starting from initial conditions $q_0$ that may be calculated by initial known orientation of the smartphone.

Finally, the EKF is applied to fuse gyroscopes with accelerometers for heading estimation. We deploy the rotation quaternion of a smartphone as the state vector, and thus the state transition vector equation is:

$$q_{k+1}\text{ = }{F}_k{q}_k+w_k^q$$

(9)

where state transition matrix $F_k=\exp \left(\Omega \left(w_k{T}_{\text{s}}\right)\right)$, and

$$w_k^q={\Xi }_k{w}_k^{gyro}=-\frac{T_s}{2}\left[\begin{array}{c}[e_k\times ]+q_0^{k}I\\ -e_k^T\end{array}\right]w_k^{gyro}$$

(10)

where $q_0^k$ is the scalar part of the quaternion $q_k\text{= }{\left[\begin{array}{cc}{q}_0^k& \begin{array}{ccc}{q}_1^k& q_2^k& q_3^k\end{array}\end{array}\right]}^T$ at time instants $k{T}_s$, $e_k\text{= }{\left[\begin{array}{ccc}{q}_1^k& q_2^k& q_3^k\end{array}\right]}^T$ is the vector part of $q_k$, $I$ is the $3\times 3$ identity matrix, $w_k^{gyro}$ is the white Gaussian measurement noise vector for Gyroscope at time instants $k{T}_s$, and $[e_k\times ]$ is a standard vector cross-product operator:

$$[e_k\times ]=\left[\begin{array}{ccc}0& -q_3^k& q_2^k\\ q_3^k& 0& -q_1^k\\ -q_2^k& q_1^k& 0\end{array}\right]$$

(11)

Equations (9) and (10) are derived from Equation (7) and can be considered as a first order approximation of the “noisy” transition matrix. The gyroscope measurement noise vector $w_k^{gyro}$ is assumed small enough in the application area, thus the first order approximation always performs well. Therefore, the process noise covariance matrix $Q_k$ can be given as follows:

$$Q_k\text{ = }{\Xi }_k{Q}_k^{gyro}{\Xi }_k^T$$

(12)

where $Q_k^{gyro}={\sigma }_{gyro}^{2}I$ is the covariance matrix for $w_k^{gyro}$.

The measurement model is constructed by observed acceleration vectors,

$$a_{k+1}\text{ = }{C}_n^b\left(q_{k+1}\right)g+v_{k+1}^a$$

(13)

where $a_{k+1}$ is the acceleration vector of the smartphone, $g$ is the local gravity vector relative to $NA$, and $v_{k+1}^a$ is the white Gaussian measurement noise of the accelerometer. Note that Equation (13) is true only when the human body is not affected by any acceleration. Assume that the covariance matrix of the measurement noise $v_{k+1}^a$ is ${\tilde{R}}_{k+1}$. To filter out the disturbance of significant human motions, we construct adaptive measurement covariance matrix ${\tilde{R}}_{k+1}={}^R\sigma _a^{2}I$,

$${}^R\sigma _a^2=\{\begin{array}{cc}{\text{σ}}_a^2,& {\Vert a_{k+1}-g\Vert }_2<{\text{ε}}_a\\ \infty ,& \text{otherwise}\end{array}$$

(14)

Because of the nonlinearity of Equation (13), the EKF approach linearizes the first part on the right side of Equation (13) by computing the Jacobian matrix:

$$H_{k+1}={\frac{\partial }{\partial q_{k+1}}{a}_{k+1}|}_{q_{k+1}=q_{k+1}^{-},v_{k+1}^a=0}$$

(15)

where the true state $q_{k+1}$ is not known; it is reasonable to replace the true state with the best estimate of the state available, namely the a priori state estimate $q_{k+1}^{-}$. Thus, the measurement model can be approximated as a linearized formula:

$$a_{k+1}\approx H_{k+1}{q}_{k+1}-H_{k+1}{q}_{k+1}^{-}+C_n^b\left(q_{k+1}^{-}\right)g+v_{k+1}^a$$

(16)

Based on the state model in Equation (9) and the linearized formula of the measurement model in Equation (16), the a posteriori estimation of the quaternion ${\widehat{q}}_{k+1}$ and the corresponding covariance matrix $P_q^{k+1}$ may be obtained by the first EKF. The detailed procedures for the first EKF are given as follows:

Firstly, compute the a priori state estimation and related error covariance matrix:

$$q_{k+1}^{-}=F_k{\widehat{q}}_k$$

(17)

$$P_{q-}^{k+1}=F_k{P}_q^k{F}_k^T+Q_k$$

(18)

where ${\widehat{q}}_k$ is the a posteriori estimation of the quaternion at time instants $k{T}_s$, and $P_q^k$ is the related error covariance matrix.

Then, compute the Kalman gain:

$$K_{k+1}=P_{q-}^{k+1}{H}_{k+1}^T{\left(H_{k+1}{P}_{q-}^{k+1}{H}_{k+1}^T+{\tilde{R}}_{k+1}\right)}^{-1}$$

(19)

Finally, compute the a posteriori state estimate and related error covariance matrix:

$${\widehat{q}}_{k+1}=q_{k+1}^{-}+K_{k+1}\left(a_{k+1}-C_n^b\left(q_{k+1}^{-}\right)g\right)$$

(20)

$$P_q^{k+1}=P_{q-}^{k+1}-K_{k+1}{H}_{k+1}{P}_{q-}^{k+1}$$

(21)

After obtaining ${\widehat{q}}_{k+1}$, the user heading at time instants $\left(k+1\right)T_s$ is ultimately determined as in Equation (6). More detailed descriptions about the EKF process can be found in [37].

3.2. WiFi Localization Based on Kernel Density Estimation

In this section, we propose the KDE based WiFi localization for measurement update. Due to the lack of explicit measurement equation and related noise statistics, WiFi localization cannot be directly deployed for measurement update in EKF. Instead of an explicit measurement equation, we note that the density function may accurately characterize the RSS-location relationship. Assume that $r$ is the real time RSS vector collected by the user, $l$ is the user’s coordinate vector, and the posterior density of the user’s location is $f\left(l|r\right)$. If we know $f\left(l|r\right)$, Minimum Mean Squared Error (MMSE) [37] location estimation and its covariance matrix can be given as follows:

$$\widehat{l}={\displaystyle \int l}f\left(l|r\right)\text{d}r$$

(22)

$$P_r={\displaystyle \int \left(l-\widehat{l}\right){\left(l-\widehat{l}\right)}^T}f\left(l|r\right)\text{d}r$$

(23)

However, the posterior density is unavailable in WiFi localization. To solve this problem, we propose KDE for approximating the posterior density due to its success in probability density distributions estimation. Given the radio map storing RSS training pairs $\left\{\left({\overline{r}}_i,l_i\right)|i=1,\dots ,N\right\}$ with mean RSS vector ${\overline{r}}_i$ at the reference point $l_i$, and a Gaussian kernel $\wp$, the posterior density estimation [34] is given as follows:

$$\widehat{f}\left(l|r\right)=\frac{\widehat{f}\left(l,r\right)}{\widehat{f}\left(r\right)}=\frac{{\displaystyle {\sum }_{i=1}^N\wp \left(r;{\overline{r}}_i,{\Sigma }_r\right)\wp \left(l;l_i,{\Sigma }_l\right)}}{{\displaystyle {\sum }_{i=1}^N\wp \left(r;{\overline{r}}_i,{\Sigma }_r\right)}}={\displaystyle {\sum }_{i=1}^N{\tilde{w}}_i\left(r\right)\wp \left(l;l_i,{\Sigma }_l\right)}$$

(24)

$${\tilde{w}}_i\left(r\right)=\frac{\wp \left(r;{\overline{r}}_i,{\Sigma }_r\right)}{{\displaystyle {\sum }_{i=1}^N\wp \left(r;{\overline{r}}_i,{\Sigma }_r\right)}}$$

(25)

where $N$ is the number of reference points at the target region, ${\overline{r}}_i$ and $l_i$ are mean vector of the Gaussian kernels, and diagonal matrices ${\Sigma }_r$ and ${\Sigma }_l$ are the related covariance matrices, respectively. Essentially, the estimated probability density is a Gaussian mixture, whose first two moments [34] are:

$$\widehat{l}={\displaystyle {\sum }_{i=1}^N{\tilde{w}}_i\left(r\right)l_i}$$

(26)

$$P_r={\displaystyle {\sum }_{i=1}^N{\tilde{w}}_i\left(r\right)\left({\Sigma }_l+\left(l_i-\widehat{l}\right){\left(l_i-\widehat{l}\right)}^T\right)}$$

(27)

Equations (26) and (27) can be used for measurement update and the corresponding covariance of the second EKF, respectively.

Besides, to reduce the number of reference points involved in WiFi localization for measurement update, we deploy a spatial filtering process. The spatial filtering assumes that the pedestrian walking distance between adjacent steps cannot exceed a predefined distance threshold. Thus, we restrict the reference points involved in WiFi localization into a sub-region, whose centre is the localization result of the previous step and the radius is the distance threshold. Define that ${\widehat{L}}_{i-1}$ is the localization result by the proposed fusion approach at the $i-1\text{ th}$ step, $D_{\text{Th}}$ is the distance threshold between adjacent steps, then a set of reference points involved in WiFi localization at the $i\text{th}$ step can be given as follows:

$$S_{i\_step}=\left\{\left({\overline{r}}_i,l_i\right)|{\Vert l_i-{\widehat{L}}_{i-1}\Vert }_2\le D_{\text{Th}};i=1,\dots ,N\right\}$$

(28)

Denote the cardinality of $S_{i\_step}$ as $N_{i\_step}$, which is much smaller than N. Then, the spatial filtering process may effectively reduce the computation cost for measurement update of the second EKF by reducing the number of reference points involved.

3.3. Second EKF: Fusing PDR and WiFi Localization

PDR and WiFi Localization systems both have their limitations and advantages. The PDR system can obtain relative displacement with high accuracy in a short period, while it suffers from cumulative drift errors during walking. The WiFi localization system can provide the absolute location estimation, while it incurs the inaccurate localization results when significant RSS fluctuations happen. Fusing both systems will exploit their complementary advantages. PDR enhances the accuracy of WiFi localization, while WiFi localization is useful for binding the cumulative PDR drift errors.

The most widely used fusion approach is a particle filter, which incurs substantial computation cost. It is unsuitable for real time indoor localization on resource-limited smartphones. Moreover, Kalman filter and its variants cannot be directly used since an explicit measurement equation and RSS noise statistics are unavailable. To make the proposed light computation EKF based approach applicable, Section 3.2 proposes a measurement model based on KDE. This section describes the detailed process of the proposed fusion approach. The complete summary of the second EKF is shown in Figure 3.

First, we give the formula of state model. Assume ${\text{ψ}}_{i\_step}$ is the yaw angle estimated at the $i\text{th}$ step from Equation (6) in the navigation frame NA, and ${\text{ψ}}_{x\text{\_axis}}$ is the yaw angle of a predefined positive x-axis, whose definition is shown in Figure 4 in our experiments. Define ${\widetilde{\text{ψ}}}_i$ as the anticlockwise rotation angle from the predefined positive x-axis to the user walking direction. Then, PDR model can be rewritten by substituting ${\widetilde{\text{ψ}}}_i={\text{ψ}}_{i\_step}-{\text{ψ}}_{x\text{\_axis}}$ into Equation (1):

$$L_i\text{ = }{L}_{i-1}\text{ + }{d}_i\left[\begin{array}{c}{\text{ cos(ψ}}_{i\_step}{\text{)cos(ψ}}_{x\text{\_axis}}{\text{)+sin(ψ}}_{i\_step}{\text{)sin(ψ}}_{x\text{\_axis}}\text{)}\\ {\text{sin(ψ}}_{i\_step}{\text{)cos(ψ}}_{x\text{\_axis}}\text{)}-{\text{sin(ψ}}_{x\text{\_axis}}{\text{)cos(ψ}}_{i\_step}\text{)}\end{array}\right]$$

(29)

where ${\text{ψ}}_{i\_step}$ is obtained at the acceleration peak time of the $i\text{th}$ step. Note that if the navigation frame NA is aligned with the predefined coordinate, the PDR model will be simplified and the same as Equation (1), since ${\widetilde{\text{ψ}}}_i$ is equal to ${\text{ψ}}_{i\_step}$. We give the more general PDR model, because the predefined coordinate system may be different for different pedestrians according to the personalized requirements, especially for a large scale localization region. For $\text{cos(}{\psi }_{i\_step}\text{)}$ and $\text{sin(}{\psi }_{i\_step}\text{)}$, they can be obtained from Equation (6):

$$\{\begin{array}{l}\cos \left({\text{ψ}}_{i\_step}\right)=\left(1-2{\left(q_1^{i\_step}\right)}^2-2{\left(q_3^{i\_step}\right)}^2\right){\left(1-4{\left(q_0^{i\_step}{q}_1^{i\_step}+q_2^{i\_step}{q}_3^{i\_step}\right)}^2\right)}^{-0.5}\\ \sin \left({\text{ψ}}_{i\_step}\right)=\left(2q_0^{i\_step}{q}_3^{i\_step}-2q_1^{i\_step}{q}_2^{i\_step}\right){\left(1-4{\left(q_0^{i\_step}{q}_1^{i\_step}+q_2^{i\_step}{q}_3^{i\_step}\right)}^2\right)}^{-0.5}\end{array}$$

(30)

where $q_{i\_step}={\left[\begin{array}{cccc}{q}_0^{i\_step}& q_1^{i\_step}& q_2^{i\_step}& q_3^{i\_step}\end{array}\right]}^T$ is the quaternion estimated by the first EKF at the acceleration peak time of the $i\text{th}$ step. Then, we rewrite Equation (29) as:

$$L_i\text{ = }{L}_{i-1}\text{ + }\tilde{f}\left(q{d}_i\right)$$

(31)

where $\tilde{f}(\cdot )$ is the relative displacement function of $q{d}_i={[\begin{array}{cc}{q}_{i\_step}^T& d_i\end{array}]}^T$, and can be obtained by substituting Equation (30) into the second part on the right side of Equation (29).

Secondly, compute the a priori state estimation $L_i^{-}$ and the a priori error covariance matrix $P_i^{-}$,

$$L_i^{-}\text{ = }{\widehat{L}}_{i-1}\text{ + }\tilde{f}\left(q{d}_i\right)$$

(32)

$$P_i^{-}=P_{i-1}+{\tilde{F}}_i{P}_{q{d}_i}{\tilde{F}}_i^T$$

(33)

where ${\widehat{L}}_{i-1}$ is the a posteriori location estimation at the $i-1\text{ th}$ step, ${\tilde{F}}_i=\partial \tilde{f}/\partial qd$ is the Jacobian matrix computed at $qd=q{d}_i$, $P_{i-1}$ is the a posteriori error covariance matrix at the $i-1\text{ th}$ step,

$$P_{q{d}_i}=\left[\begin{array}{cc}{P}_q^{i\_step}& 0_{4,1}\\ 0_{1,4}& {\sigma }_d^2\end{array}\right]$$

(34)

where $0_{i,j}$ is the $i\times j$ all-zeros matrix, $P_q^{i\_step}$ is the a posteriori error covariance matrix of $q_{i\_step}$, and ${\sigma }_d^2$ is the covariance of the estimated step length.

Thirdly, we apply the KDE based RSS measurement model proposed in Section 3.2,

$$L_i\text{ = }{L}_i^r$$

(35)

where $L_i^r$ is the WiFi localization result using RSS vector $r_{i\_step}$, which is the averaged RSS vector of samples collected during the $i\text{th}$ step. Similar to Equations (26) and (27),

$$L_i^r={\displaystyle {\sum }_{i=1}^{N_{i\_step}}{\tilde{w}}_i\left(r_{i\_step}\right)l_i}$$

(36)

$$R_i={\displaystyle {\sum }_{i=1}^{N_{i\_step}}{\tilde{w}}_i\left(r_{i\_step}\right)\left({\Sigma }_l+\left(l_i-L_i^r\right){\left(l_i-L_i^r\right)}^T\right)}$$

(37)

where $R_i$ is the measurement noise covariance matrix, $\left({\overline{r}}_i,l_i\right)\in S_{i\_step}$ is the training pairs involved at the $i\text{th}$ step derived from Equation (28), $N_{i\_step}$ is the number of reference points used.

Finally, the location at the $i\text{th}$ step can be estimated by fusing state model in Equation (31) and measurement model in Equation (35). The Kalman gain can be given as follows:

$$K_i=P_i^{-}{\left(P_i^{-}+R_i\right)}^{-1}$$

(38)

Then, the a posteriori location estimation at the $i\text{th}$ step is given as follows:

$${\widehat{L}}_i=L_i^{-}+K_i\left(L_i^r-L_i^{-}\right)$$

(39)

The corresponding a posteriori error covariance matrix is given as follows:

$$P_i=P_i^{-}-K_i{P}_i^{-}$$

(40)

Figure 3. Summary of the second EKF for fusing WiFi localization and PDR.

Figure 3. Summary of the second EKF for fusing WiFi localization and PDR.

4. Evaluation

4.1. Experimental Setup

Experiments were carried out in a 43.5 m × 11.2 m indoor office area, part of the second floor of our department, as seen in Figure 4. The ground is laid with square floor tiles, whose sizes are 0.6 m × 0.6 m. We deploy a Huawei Mate smartphone running the Android 4.1 operation system as the experimental device. For the WiFi localization system, there are total 8 APs (indicated by blue squares) available and 50 reference points (indicated by red circles) deployed. The distance between neighbor reference points in the hall and corridor are 1.2 m and 1.34 m, which is the length and diagonal distance of two floor tiles, respectively. During offline phase, we collected 100 RSS training samples per reference point to build the radio map. During online phase, the user collected real time RSS vectors at about 2 Hz sampling rate. We define the reference point in the lower-left corner as the coordinate origin; the x-axis points to the right, being parallel to the corridor, and the y-axis points upward. The proposed fusion approach is compared with individual approaches of WiFi localization and PDR, the particle filter [19] using 1000 particles. To test the effectiveness of the proposed KDE based WiFi localization, we develop and test an improved particle filter (PF). Compared with the particle filter in [19], the only difference of the improved one is the particle weight update scheme, which is achieved by computing the Gaussian kernel function between the location of particles and WiFi localization results. As shown in Equations (26) and (27), the WiFi localization results are obtained by deploying KDE, while the kernel width of the Gaussian kernel function is adaptively adjusted by the related covariance. For the PDR system, we use the gyroscope module and accelerometer module built in the Huawei Mate smartphone to track the user. The gyroscope and accelerometer sensing rates are set to 100 Hz and 50 Hz, respectively. To make the gyroscope output more precise and robust, we do the necessary calibration process before carrying out experiments. Note that we only consider the common hand-held situation, and assume that the misalignment angle between the device forward and user heading is zero. The other situations, such as when the smartphone is put in a pocket or a bag, will be considered in our future works. As in much of the literature [11,16], we assume that the user’s initial location and orientation is known as a priori. To label the ground truth, we place some tags on the ground and apply a camera to record the entire walking process. Then, we manually label the coordinates of each step carefully. The localization error is calculated as the Euclidean distance between the estimated coordinates per step and the labeled coordinates per step along the true path.

Figure 4. Experimental environment includes a hall and a long corridor.

Figure 4. Experimental environment includes a hall and a long corridor.

4.2. Performance Analysis

First, since the tracking performance is greatly affected by the heading estimation bias, we evaluate the heading estimation performance of the developed PDR system. Figure 5 shows the true path of the user. According to the different user heading, the whole path is divided into seven sub-paths. Figure 6 compares the heading estimation performance between approaches using gyroscope only (Gyro) and combining gyroscope with accelerometer (Gyro + Acc). One can clearly see that the estimated user headings of both approaches are close to the ground truth. Particularly, from path 1 to path 4, both approaches have approximate estimated user heading. However, from path 5 to path 7, the Gyro + Acc approach obtains better heading estimation performance than Gyro approach. The Gyro approach assumes the initial inclination angle of the hand-held smartphone is known and remains stable along the walking path. This assumption may be corrupted temporarily when drastic body swinging happens. In contrast, the EKF based Gyro + Acc approach may fuse the acceleration information well, which contains real time tilt angle information, and thus may decrease the negative effect caused by drastic body swinging.

Figure 5. True path in the experimental environment.

Figure 5. True path in the experimental environment.

Figure 6. Yaw angle estimation performance comparison between approaches using gyroscope only and combining gyroscope with accelerometer.

Figure 6. Yaw angle estimation performance comparison between approaches using gyroscope only and combining gyroscope with accelerometer.

Secondly, we compare the tracking performance between the proposed approach and the individual approaches of WiFi localization and PDR. Figure 7 shows the trajectories of the true path, PDR (Gyro), PDR (Gyro + Acc), WiFi localization and the proposed approach. PDR has comparable tracking accuracy with the proposed approach from path 1 to path 3, while it performs progressively worse with the tracking error accumulated. Particularly, from path 5 to path 7, PDR (Gyro + Acc) performs better than PDR (Gyro), since the former has a smaller heading estimation error than the latter, as can be seen in Figure 6. Though WiFi localization obtains inaccurate tracking results along the whole path, it also provides useful localization information, especially along path 4 and path 5, whose y-axis coordinates are restricted into a small region. Clearly, the proposed approach, whose estimated trajectories match the ground truth closest, performs best. This may be contributed to the effective corrections of the drift errors of PDR by fusing WiFi localization.

Figure 7. Comparisons between the true path, trajectories of PDR using gyroscope only, PDR with Gyro + Acc, WiFi localization and the proposed EKF based fusion approach.

Figure 7. Comparisons between the true path, trajectories of PDR using gyroscope only, PDR with Gyro + Acc, WiFi localization and the proposed EKF based fusion approach.

Thirdly, we compare the localization accuracy between various approaches. As seen in Table 1, compared with PDR (Gyro), PDR (Gyro + Acc), WiFi localization and the particle filter, the proposed EKF reduces mean localization errors by 54.5% (0.85 m), 42.7% (0.53 m), 74.9% (2.12 m), and 12.3% (0.10 m), while it reduces standard deviations by 65.4% (0.70 m), 30.2% (0.16 m), 86.7% (2.42 m), and 7.5% (0.03 m), respectively. Compared with the improved particle filter, little performance degradation is achieved by the proposed EKF. The corresponding cumulative error distributions are shown in Figure 8. Clearly, the proposed EKF performs much better than the individual approaches, while it achieves comparable accuracy with that of the two particle filter based approaches. Particularly, the particle filter performs a little worse than both the improved particle filter and the proposed EKF, since its particle weight update scheme may incur the adverse effect caused by some RSS observations with severe fluctuations. In contrast, the improved particle filter and the proposed EKF may mitigate the adverse effect by giving a smaller weight to the noisy RSS observation, which renders a larger WiFi localization error covariance. The related error covariance may be adaptively estimated by deploying KDE during particle weight update or EKF filtering process.

Finally, we compare the calculation time of the location estimation per step between a particle filter and the proposed EKF, as shown in Figure 9. The calculation time is obtained by running the compared approaches in Matlab and averaging calculation time per step of ten traces along the true path. The calculation time required by the proposed EKF takes 0.185 s. It is mainly caused by two modules: first EKF for heading estimation takes 0.119 s; and second EKF for location estimation takes 0.064 s. The calculation time for step detection and step length estimation only takes 0.002 s. For a particle filter with 1000 particles, it takes 11.3 s and thus is unsuitable for real time applications. The proposed EKF based fusion approach greatly reduces calculation time in comparison to the particle filter in two ways. First, except for computing Jacobian matrix, EKF requires the same computation cost as that of a Kalman filter, while the particle filter needs to calculate and update the states of a great number of particles whenever implementing a new location estimation. Secondly, the computation cost for measurement update is reduced significantly by a spatial filtering process, which reduces the number of reference points involved in Equations (36) and (37). In summary, the proposed approach achieves comparable accuracy performance to that of a particle filter, while maintaining a low computation cost comparable to that of a Kalman filter. It is more suitable than the particle filter for real time indoor localization on resource-limited smartphones.

Table 1. Comparisons of mean localization errors (m) and standard deviations (m).

Compared Approach	Proposed EKF	PDR (Gyro + Acc)	PDR (Gyro)	WiFi Localization	Particle Filter	Improved PF
Mean error	0.71	1.24	1.56	2.83	0.81	0.65
Standard deviation	0.37	0.53	1.07	2.79	0.40	0.33

Table 1. Comparisons of mean localization errors (m) and standard deviations (m).

Compared Approach	Proposed EKF	PDR (Gyro + Acc)	PDR (Gyro)	WiFi Localization	Particle Filter	Improved PF
Mean error	0.71	1.24	1.56	2.83	0.81	0.65
Standard deviation	0.37	0.53	1.07	2.79	0.40	0.33

Figure 8. Accuracy comparisons between the proposed EKF based fusion approach, improved particle filter, particle filter, PDR with Gyro + Acc, PDR using gyroscope only and WiFi localization.

Figure 8. Accuracy comparisons between the proposed EKF based fusion approach, improved particle filter, particle filter, PDR with Gyro + Acc, PDR using gyroscope only and WiFi localization.

Figure 9. Comparisons of the calculation time for location estimation per step between a particle filter and the proposed EKF based approach, whose two main modules are: first EKF for heading estimation; and second EKF for location estimation.

Figure 9. Comparisons of the calculation time for location estimation per step between a particle filter and the proposed EKF based approach, whose two main modules are: first EKF for heading estimation; and second EKF for location estimation.

5. Conclusions and Future Work

The main contributions of this work are three-fold. First, we design a novel data fusion framework for combing PDR and WiFi localization by using an extended Kalman filter. The proposed fusion approach reduces mean localization errors by 42.7% and 74.9% as compared to using PDR and WiFi localization alone, respectively. Compared with a particle filter, the comparable accuracy is achieved, while the computation cost is reduced greatly.

Secondly, to adapt the unknown measurement equation and related noise statistics, we propose a RSS-location measurement model by using KDE. Unlike previous approaches setting measurement noise covariance manually, we adaptively and accurately estimate it by approximating the probability density using KDE. In addition, a spatial filtering process is combined to reduce the computation cost by restricting localization into a vicinity of the localization result of previous step.

Finally, we develop a quaternion based heading estimation method by using another EKF to fuse gyroscopes and accelerometers. Instead of using the most widely used Euler angles and DCM based orientation descriptors, we use the quaternion descriptor, since it can both avoid the singularity problems and require the least computations simultaneously.

In future works, we will further expand the proposed approach to the situation when the placement of a smartphone is unconstrained, such as in a pocket or a handbag. This situation has been paid little attention, and may present critical challenges for heading estimation in PDR systems. In addition, building maps and related landmarks will also be combined to correct the heading estimations and improve the localization accuracy.