|Home | About | Journals | Submit | Contact Us | Français|
Particle filters (PFs) are widely used for nonlinear signal processing in wireless sensor networks (WSNs). However, the measurement uncertainty makes the WSN observations unreliable to the actual case and also degrades the estimation accuracy of the PFs. In addition to the algorithm design, few works focus on improving the likelihood calculation method, since it can be pre-assumed by a given distribution model. In this paper, we propose a novel PF method, which is based on a new likelihood fusion method for WSNs and can further improve the estimation performance. We firstly use a dynamic Gaussian model to describe the nonparametric features of the measurement uncertainty. Then, we propose a likelihood adaptation method that employs the prior information and a belief factor to reduce the measurement noise. The optimal belief factor is attained by deriving the minimum Kullback–Leibler divergence. The likelihood adaptation method can be integrated into any PFs, and we use our method to develop three versions of adaptive PFs for a target tracking system using wireless sensor network. The simulation and experimental results demonstrate that our likelihood adaptation method has greatly improved the estimation performance of PFs in a high noise environment. In addition, the adaptive PFs are highly adaptable to the environment without imposing computational complexity.
With the advancement of wireless sensor network (WSNs) and RFID technologies, the demands for indoor location information have promoted the extensive study of indoor localization methods over the past few years . There are increasing requirements of location-based services (LBS) in practical applications, such as indoor navigation systems, location-based social networks, indoor robot and healthcare . The reliability of the location accuracy is a major concern when providing the location information. Additionally, the target position can be obtained via range-based measurement, such as time-of-arrival (TOA), time-difference-of-arrival (TDOA) and received signal strength (RSS), by using WSNs or RFID. In a dynamic high noise environment, the multi-path and non-line-of-sight (NLOS) effects cause high interference during the signal transmission, and the range measurement contains high error. In this case, the PF is a promising estimation method in the nonlinear non-Gaussian environment due to its high accuracy and is widely applied in the indoor localization systems.
A particle filter (PF), which is a typical Bayesian estimation method, has drawn much attention in the fields of state estimation and signal processing for many years . Many applications employ the PF to process the collected data, such as target tracking [4,5] and localization systems . Based on Bayes’ theorem, PFs generate random samples, which are called particles with associated weights to represent the posterior PDF of the state. The associate weights are proportional to the prior PDF and the likelihoods and updated recursively.
However, the estimation accuracy of the PF can also be degraded due to the range measurement uncertainty. A traditional way is to generate high quality particles, since the PF is introduced to the localization problem . The bootstrap particle filter (BPF) is applied to generate and re-sample the particles during the recursive position estimation . Farahmand et al. proposed a set-membership constraint particle filter (CPF) to select particles within the constrains [8,9]. Kwok et al. introduce an adaptable sampling method based on the Kullback–Leibler divergence (KLD) . The Gaussian particle filter (GPF) generates the particles according to the Gaussian distributions and also approximates the estimated distribution as the Gaussian distributions . The accuracy of the GPF is widely evaluated in RFID and WSN-based indoor tracking [12,13]. Ristic et al. proposed probability hypothesis density (PHD) and cardinalised PHD (CPHD) filters for target tracking . The other solution is to use an efficient wireless model to overcome the NLOS and multipath effects. The NLOS channel is believed to introduce additional bias error rather than the LOS ranging error. Thus, NLOS path identification and bias reduction methods are widely applied in the PF designs. Jung et al. identify the NLOS path for the TOA ranging and use PFs to estimate the target according to the biased error model . Youssef et al. provide the biased model of the RSS NLOS ranging error . In addition, the map information can also help to indicate the NLOS path . The problem is that the NLOS error cannot be simply modeled as an LOS error model plus a bias. A typical error model is required for the NLOS channel. The Markov state-space model for NLOS error is usually introduced into the PF-based indoor localization. Nicoli et al. developed a recursive Bayesian estimator that combines the Markov transition model and the NLOS propagation in the indoor environment . Wang et al. introduce the NLOS error model to the Markov model of the PF based on 802.15.4a . Papa et al. proposed adaptive Bayesian methods to track the target using a sensor network . In addition, more information is employed to reduce the measurement error. The hybrid information of TOA and RSS is exploited for likelihood calculation in . Further, the combination of TOA/RSS with NLOS and the multipath mitigation method is introduced in . Bargshady et al. also use the PF to process the hybrid WiFi and ultra wideband (UWB) measurements to reduce the NLOS effect .
The PF achieves high estimation accuracy by using the prior probability and likelihood based on the Bayesian method. The likelihood relies on the measurement error distribution. However, there is no exact distribution to represent the measurement noise in the complicated indoor environment. Even if the distribution fitting or wireless propagation modeling methods can derive the model parameters, these parameters should be reset when the environment is changed, such as an infrastructure change or the target moves to another area. Thus, the indoor measurement noise shows nonparametric features , which requires that the PF is robust to the unknown error models. In this paper, we propose a novel method to design the PF in order to achieve more accurate estimation in a complicated environment. We firstly analyze the measurement uncertainty for the likelihood function (LF) in the PF. The LF, which relies on the measurement and noise distribution, has a large proportion in determining the particle weights. Since the error model is unknown to the LF calculation, the posterior PDF of the state estimation is unreliable. We divide the measurement error model into two parts: the pre-assumed distribution and the unknown model, and use a dynamic Gaussian model (DGM) to comprehensively describe both parts . The DGM assumes that the real-time measurement error follows the pre-assumed distribution, which is dynamically deviated by the instantaneous unknown error. Then, the likelihood function (LF) in the PF, which relies on the measurement function and noise distribution, is calculated based on the DGM.
Our goal is to reduce the instantaneous unknown noise in LF according to our analysis, and the major contributions of our work are four-fold: (1) We propose a likelihood adaptation method, which is based on the DGM. The method combines the prior information and a tuning parameter to reduce the instantaneous unknown error: the prior information is the predicted measurement based on the predicted state; and the belief factor is the tuning parameter, which adapts the likelihood function to a more accurate one. By tuning , the impact of unknown error for likelihood calculation is reduced; (2) In order to obtain the optimal performance, we use the Kullback–Leibler divergence (KLD), which is an efficient metric to compare two distributions, to derive the optimal . The optimal can achieve the minimum KLD and attain the lowest estimation error of the PF; (3) We formulate the optimal performance of the adaptive method by using the Cramér–Rao lower bound (CRLB) analysis. The analytical results indicate that our method outperforms the conventional PF for the nonparametric measurement error models; (4) Three versions of PFs are improved based on our adaptation method, which are the BPF, the GPF and the CPF. The improved PFs are evaluated in the simulations and the real-world WSN indoor localization experiments. The results demonstrate that the proposed algorithms effectively reduce the estimation error and have robust performance in a high noisy wireless environment.
The rest of the paper is organized as follows: Section 2 analyzes the measurement uncertainty effect of the likelihood function in the PF algorithms. Section 3 describes a dynamic Gaussian modeling method for the uncertainty and outlier measurement errors. Section 4 proposes the likelihood adaptation method, and the adaptive PFs are designed in Section 5. The theoretical analysis based on CRLB is described in Section 6. Section 7 presents the simulation and real experiment results of adaptive PFs in the indoor localization systems. Finally, Section 8 concludes this paper.
In general, the state-space model is applied to describe the nonlinear estimation problem based on the hidden Markov process. The estimated state vector is evolved from the current observation and the previous state , which are defined as the prediction equation and the update equation. The prediction equation is:
where is the prediction function, is the previous state and is the prediction noise, which implies the prediction error of . Here, we assume that is additive to the prediction.
At time t, the system obtains a noisy measurement vector . The relationship between and follows:
where is the measurement function and is the measurement noise at time t. In this paper, we employ the TOA measurement for range information. The TOA is a simple and straightforward range measurement method for indoor localization. The distance is proportional to the transmission delay, and the noise comes from the additive delay, which is introduced by the multi-path, NLOS and unsynchronized distributed clock within the sensors. The TOA is generally formulated as:
where τ is the transmission delay, c is the microwave speed, is the position vector of the anchor and indicates the distance between the target and the anchor. Considering the noise, the range measurement for each anchor j can be formulated as:
where is the target position and is the position of anchor j. For a 2D positioning system, the distance measurement function can be expressed as:
then, , where N indicates the number of anchors. Accordingly, is defined as the measurement likelihood for , which is essential to the whole estimation.
PF consists of three parts: the first part is to generate a set of state samples, which are called particles; the second part is to calculate the associated weight for each particle; the final part is to re-sample the particles and to eliminate the unimportant particles. The estimated state is obtained by calculating the weighted average values of the particles. PF first generates a particle set according to the importance density function , where is the sample set with associate weights ; i and denote the particle number and the total number, respectively. The purpose of using is to generate high quality particles and then to attain the accurate estimation. Since the particles represent the possible state in the state space, it is necessary to sample a finite particles with high probability that can represent the state due to the limited computational overhead. Thus, the high quality particles are the samples with a high probability generated and calculated from . Based on , most particles are drawn only in the interested area, and a few particles are sampled on the other places. Thus, the posterior PDF of state can be approximated by using the delta function:
For the Bayesian estimation in a non-Gaussian environment, it hardly provides the analytical formulation. Thus, the approximation is used with the set of particles, which is the main advantage of the PF . Additionally, the weight of each particle can be calculated based on the Bayes rule :
where is the transition probability for particle and is the measurement likelihood of for . The importance density function draws new samples , which evolves from the previous samples , and denotes the time sequence from the initial state to the previous state.
The PF estimation relies on the high quality particles and associated weight calculations. The weight is obtained via Bayes’ rule, which considers the prior probability and the measurement likelihood. The likelihood relates to the measurement and the noise distributions. A proper error distribution can lead to an accurate estimation not only for the PF, but also for other probability-based algorithms, e.g., maximum likelihood (ML) and maximum a posterior (MAP) algorithms.
In PFs, the measurement likelihood for each particle is calculated as :
where and is the PDF of measurement noise with variables of . The additive measurement noise is assumed to be zero mean and follows a Gaussian distribution. However, the statistical results indicate that the noise is not zero mean due to heavy outlier values . Thus, other PDFs are applied for measurement noise modeling, e.g., exponential, Rayleigh, Weibull or Gamma distribution . If such a PDF is known to the system, the PF can obtain an accurate estimation, which approaches the optimal estimation with an increasing number of particles, as CRLB indicates. However, the PDF is not always known or precise for real applications. In real applications, the measurement error is modeled by statistical methods based on the sample dataset. On the one hand, the parameters of the error model can be changed if the sample dataset is changed. On the other hand, the outlier values can deviate from the error distribution, which makes the error model inaccurate for the PF estimation.
For instance, we construct an experiment to collect all of the ranging measurement noise throughout the whole building. During such an experiment, we employ a robot moving automatically through every possible position of the building, including the hallway, the office room and classroom in a building at Freie University Berlin. Then, all of the ranging errors are collected, and the histogram is constructed. The error data can be attained freely via the website of . The large positive noise, which may contribute a heavy tail for a histogram, is shown in Figure 1. In Figure 1, the histogram can be divided into two parts: the left part is similar to a Gaussian distribution, for which the mean and variance can be calculated; the right part is a kind of heavy tail, which represents the outlier values. To describe the histogram, researchers use an arbitrary assumed error model or a combined model to approach the real application. However, this makes the estimation algorithms sensitive to the environment. If the environment is changed, the model should be adapted accordingly; otherwise, it can lead to the wrong estimation.
To address the measurement uncertainty problem and to make the PF robust to environmental change, we firstly introduce a dynamic Gaussian model (DGM) to the likelihood calculation. The main idea of the DGM is to classify the measurement error distribution into two parts: the first part is the expected parametric distribution (EPD), which is a pre-assumed distribution and known to the system. The EPD is obtained based on the knowledge or experiences of the system design, and the parameters can be attained via the system model or some pre-assumptions. The most popular EPD is the normal distribution. The second part is the non-parametric distribution (NPD), which is unknown to the system and for which it is hard to get the parameters. The conventional PFs only use EPD as the pre-assumed distribution model for estimation. The NPD is the compensation for the EPD when the PFs are in the dynamic environment without the knowledge of the noise model. The histogram of the EPD and the NPD is depicted in Figure 1. In Figure 1, the error value between −5 and 5 can mainly be modeled as the normal distribution, which is the EPD and denoted by the solid curve. For the outlier values, another Gaussian distribution NPD attempts to cover such values, which is depicted by the dashed curve.
The DGM is the drifted EPD, which is deviated by the instantaneous NPD value. Here, we use , where is the EPD error and is the NPD error. Then, follows the EPD, but deviated by . The DGM is different from the Gaussian mixture model. The Gaussian mixture model uses different Gaussian distributions to fit the non-Gaussian distributions. The results are still a static distribution model. However, DGM is dynamic and does not attempt to fit the error histogram, because the NPD part is not an exact model to fit the outlier values. It is rather a fuzzy function to cover such values. In addition, the Gaussian mixture model is a parametric model for the entirety of the error samples, and the DGM only contains a single instantaneous value of the NPD instead of the entirety of the data samples. In general, if , follows the EPD. However, for a typical measurement, consists of a drift value that deviates from the pre-assumed normal distribution to a certain distance. Then, the EPD should be adapted dynamically according to the instantaneous value of the NPD.
The DGM for a typical NPD error is depicted in Figure 2. In Figure 2, the solid curve represents the EPD, which is a zero mean normal distribution. When the instantaneous value of the NPD is introduced into the measurement noise, the EPD is deviated. Then, we obtain the likelihood calculation:
where an unpredictable instantaneous noise is introduced into the likelihood function.
Equation (9) is illustrated as the dashed curve in Figure 2, which is a biased non-zero mean Gaussian distribution. It is deviated from the original assumption due to considering the instantaneous value, . If is zero, the likelihood function is the exact EPD of measurement noise:
where represents the actual assumed probability; then, we would have optimal filtering with the increasing number of particles. However, in most real cases, is not zero, and is deviated by in Equation (10), which leads to inaccurate estimation. When becomes larger, the gap between the two curves is increasing, as shown in Figure 2b, which degrades the estimation accuracy significantly. Therefore, our goal is to develop an adaptation method to mitigate and approach the likelihood calculation of the exact assumed distribution.
We attempt to reduce the impact of the NPD and calculate the LF based on the DGM in order to improve the estimation accuracy. Our adaptation method consists of two steps: the first step is to obtain a predicted measurement according to the previous state; the second step is to adapt the LF based on and a belief factor , which is a tuning parameter for adaptation. The structure of the adaptive PF, which integrates with the predicted measurement and , is illustrated in Figure 3. In the original PF, the LF is determined by the EPD, whereas in our algorithm, the likelihood calculation is based on the DGM. Belief factor is used to adapt the value between and .
The predicted measurement is derived based on the prediction state and is the reference for the real measurement. The calculation steps are as follows: denotes the prediction value of :
where is the estimation at previous time . When considering the processing noise , we denote as:
where is assumed to be the additive noise and follows normal distribution ; is the covariance at time t. Then, we obtain a predicted measurement for: sensors:
in which indicates the prediction of measurement derived from . The predicted measurement is not the actual measurement, but is used as prior information for measurement likelihood adaptation.
Belief factor is the tuning parameter for , and it is used to adapt the measurement to reduce . Note that our goal is to achieve Equation (10). Since Equation (10) can not be achieved directly, we use and to approach Equation (10) with . Then, the adaptive likelihood function is constructed as:
where indicates the adaptive likelihood, is the measurement vector, is the predicted measurement and . The notation in Equation (14) is the Hadamard operator, which is used to expressed as , and is the vector of ones whose size corresponds to that of . Note that , which should be interpreted as the elements in , are non-negative. The belief factor indicates how much trust assigns to the . If , , which equals the measurement likelihood; whereas when , , which only trusts the predicted measurement.
Here, two problems remains: (1) with introducing , the measurement error in is suppressed, but the error of is involved, which raises a question: in what condition can our method reduce ? (2) If our method can reduce this effect, a proper is required. Therefore, is there an optimal that can achieve the best performance?
Since we intend to compare our adapted DGM to the EPD, the effective evaluation method is KLD . KLD, which also is denoted as relative entropy, quantifies the difference between two distributions. If and indicate two different distributions, KLD is formulated as:
where denotes the KLD. The KLD is a non-negative distance between two different distributions, which is . It can be shown that . Additionally, small indicates that is similar to . In addition, KLD is a convex function .
We employ the KLD as a metric to find optimal , which minimizes the distance between and . Here, we use as the objective distribution and employ as the tuning distribution with parameter . Then, the KLD function is constructed as:
Then, optimal is attained with minimum :
If and are based on the same Gaussian distribution function, then Equation (16) is expressed as :
where is the covariance of . Since is independent of , the objective function is simplified as:
which turns out to be a least-squares approximation problem . Since is the nonlinear functions of the prediction noise according to Equation (13), it is difficult to obtain an analytical optimal result. Besides, the computational complexity is increased accordingly to obtain an optimal solution. Thus, linearizing the object function is preferred. We use first order Taylor series expansion at to linearize Equation (13):
where is the partial differential of with respect to . Additionally, substitute Equation (20) and Equations (2) into (19); we obtain:
Therefore, the problem is converted into a linear optimization problem, which is solvable analytically by expressing the objective as the convex quadratic function :
where is the covariance of and is the covariance of based on the assumed NPD model.
Then, the optimal can be obtained if and only if:
Then, the unique is derived:
Since is the belief factor for the predicted measurement, Equation (24) indicates that when NPD error is high with a large , offers more contribution than the noisy measurement. In other words, when the prediction covariance is larger than , our method should assign more belief to . In this case, is useless and can introduce more estimation error. Thus, when the measurement error is quite small and the prediction error exceeds the measurement error, using our method will introduce extra estimation error. Then, the conventional methods can outperform our algorithms. This means that our method is useful when the measurement uncertainty is higher than the predicted state uncertainty, and the optimal exists. Fortunately, in the indoor wireless tracking system, the measurement uncertainty and outlier values are always high. In addition, if the measurement noise is low, the prediction error is also small, due to the performance of the Bayesian filtering estimation. Therefore, our method can effectively improve the estimation accuracy in the noisy environment.
According to the architecture in Figure 3, we integrate our adaptation method with three main PFs, which are BPF, GPF and CPF, and design new PF versions: adaptive BPF (A-BPF), adaptive GPF (A-GPF) and adaptive CPF (A-CPF).
In A-BPF, the prediction state is obtained through:
where the previous state is calculated based on: . Then, we obtain the predicted measurement according to Equation (13).
When the measurement is available, the adapted measurement likelihood for each particle is calculated as Equation (14). Additionally, then, the particle weight is calculated and normalized as , which determines the posterior PDF of the estimated state . Finally, is attained: . The importance sampling and resampling parts are still the same, and the predicted measurement and optimal is easy to obtain based on the analytical formulation. Therefore, our likelihood adaptation does not introduce much computational complexity to the original PFs. The algorithm of A-BPF is presented in Algorithm 1. Our adaptation method is implemented in the importance sampling part and the weight adaptation part of PF.
The GPF approximates the estimated PDF by Gaussian distributions using the PF method. The GPF assumes that PDF of the state follows a Gaussian distribution, and it samples particles according to the estimated PDF . Therefore, only the mean and covariance of the estimated PDF are calculated and propagated. Due to the simplicity, the GPF is widely used in distributed PF applications .
Particles are drawn from the Gaussian distribution functions, , where is the mean value of estimated state and is the covariance of PDF. The Gaussian PDF evolves according to the transition model: . Thus, the covariance is assumed to propagate to the next time step, which is . Then, the initial weight for each particle is calculated as:
When the measurements are available, the weight for each particle updates:
where is the likelihood.
|Algorithm 1 Adaptive bootstrap particle filter (A-BPF).|
In the A-GPF, the LF fuses both the prior information and current data based on the DGM. The optimal is derived based on the previous estimated and current NPD covariance . Thus, calculating the optimal is a recursive procedure in A-GPF. The procedure of A-GPF is illustrated in Algorithm 2.
|Algorithm 2 Adaptive Gaussian particle filter (A-GPF).|
The difference between A-BPF and A-GPF is: the prediction error in A-BPF follows an arbitrary assumed distribution, whereas A-GPF uses the Gaussian distribution to indicate such a distribution. The assumed distribution in A-BPF is obtained based on the statistical analysis, and the estimation of A-BPF can be accurate if the assumed distribution is correct.
The CPF randomly samples particles not only based on both the assumed distribution and some constraint conditions, e.g., , where is the constraint functions . The constraint conditions guarantee the particle generated in the target region with a very high probability by allocating a higher previous weight. In this case, both the previous weight and adaptive parameters are maintained during the estimation, where the complexity is still high. Thus, we use the constraint conditions only to sample the particles, and the weights are calculated according to the adaptive likelihoods. Then, the complexity of A-CPF is reduced.
The constraint conditions can be set up according to different applications. We will detail the conditions for the range-based target tracking in the next section. After sampling the particles, the prediction is obtained based on the prediction function. Then, our adaptation method is used, and the weight calculation follows the same procedure as A-BPF, which is illustrated in Algorithm 3. The major difference between A-BPF and A-CPF is the additional constrains for particles, which can improve the performance of BPF with additional information.
|Algorithm 3 Adaptive constraint particle filter (A-CPF).|
Note that the performances of the proposed APFs are different and suitable for different scenarios. In general, all of the APFs can effectively reduce the estimation error in the high noise environment, which will be proven in Section 6. The A-BPF reduces the estimation error by using arbitrary prior information. Such information is set up since the initial sampling scheme. If the sampling scheme and prior information are accurate, the estimation results can be good. However, the system cannot adjust the prior information at every time step. Thus, the A-BPF cannot further reduce the error if the measurement error is small. The A-GPF is quite suitable for adjusting itself during the recursive estimation. At each time step, A-GPF calculates the estimation covariance using the current particles and propagates to the next time step as the prior information. This is quite flexible for a dynamic environment. However, the disadvantage of the A-GPF is that there is some error in the covariance calculation. Thus, if the measurement error is too high, the performance of the A-GPF is not as good as A-BPF. The most robust feature for the dynamic environment is A-CPF, which employs constraint conditions to restrict error. In a high noise environment, the estimation error of the A-CPF can be controlled. However, the A-CPF has an inherent error from the constraint condition. Thus, it is still not as good as the A-BPF if the measurement error is small.
In this section, we provide the benefits of the adaptive PFs by deriving the CRLB. The CRLB, which is given by the inverse of the Fisher information matrix (FIM), sets the lower limit for the variance (or covariance matrix) of any unbiased estimators of an unknown parameter (or unknown parameters) .
For the adaptive PFs, the prior information is integrated into the likelihood function. If the measurement noise also follows a Gaussian distribution, we can easily derive the covariance of adapted measurement:
If the measurement noises are independent of each anchor, the covariance matrix can be simplified as , where can be derived independently in each anchor. Then, is formulated as:
for the detailed formulation, please refer to the Appendix.
We set up several simulations to evaluate the performance improvement of the adaptive PF. The playing field is m. We randomly deploy 100 sensors. The target chooses a random path walking through the playing field. The range data are obtained through the TOA technique, whose range information is formulated according to Equation (4). The EPD for each sensor follows zero mean Gaussian distribution , where m. Additionally, set the NPD of each sensor as , where m. Root mean square error (RMSE) is mainly compared in the simulation as the estimation accuracy metric. For the CRLB analysis, the RMSE indicates the root value of the unbiased covariance. To compare with our proposed method, we use the common recursive CRLB form in , where the measurement noise vector is the combination of the EPD and NPD . It should be noted that the the measurement noise in the simulation is not simply the sum of two distribution. EPD is the general error distribution, which is added during the whole simulation. However, NPD is applied to represent outlier values of the simulation. Thus, during each time step, we randomly add an NPD error or not. In this case, the NPD error is a few outlier values that can influence the measurement, and DGM must be applied for the PF estimation. The sequential estimation results are illustrated in Figure 4.
We also adapt the measurement noise environment to examine the performance change for each process. The NPD covariance for each anchor changes from to . The root mean squared error (RMSE) results of the two CRLBs are depicted in Figure 5. When the NPD covariance is small, the adaptive method cannot improve estimation, but increases the estimation error. In this case, it would rather use only the measurement data to obtain the estimation. However, with increasing the NPD covariance, the adaptive method improves the estimation gradually and outperforms the recursive Bayesian method when the error is quite high. Thus, our method is feasible for a harsh environment with high uncertainty.
Our scheme is evaluated in the simulation of target tracking using the wireless sensor networks. We randomly deploy 100 sensors in a two-dimensional square m region. One target runs through a random path with a constant speed. The target periodically broadcasts the request signals to the sensors, and the sensors respond to the request. Then, the ranging values are calculated according to the time-of-arrival (TOA) of the responses. Each sensor node j is assigned coordinations , and the target state at time t is , where is the position vector, is the velocity vector and T is the transpose operator. In the simulation, we assume that the measurement noise consists of the EPD and the NPD values, and the measurement noise for each sensor node is identical independent distributed (i.i.d). The EPD noise follows the zero mean Gaussian distribution, where and m. Additionally, the NPD noise also follows a Gaussian distribution, where and m. Then, the DGM can be illustrated as shown in Figure 6.
We employ a linear model as the prediction function, and Equation (1) can be expressed as:
where is the linear transition matrix:
where indicates the time interval.
In the particle sampling stage, the samples are initially randomly generated and propagated according to the linear transition model in BPF and A-BPF. In GPF and A-GPF, the particles are sampled based on the updated PDF. In CPF, the particles are constrained to some conditions. For range-based localization systems, the constraint region can be drawn by the bounding box algorithm, which is demonstrated to be robust to measurement noise . Using to denote the j-th range measurement for node j with the position in the two-dimensional playing field, then the geometric constraint region is: and , where N is the number of sensor nodes. Then, the particles are sampled within this region.
First, we compare the estimation accuracy of BPF to our algorithm, A-BPF, to analyze the relationship between and the estimation accuracy. We implement A-BPF and vary from to to verify whether has an optimal value with minimum estimation error. The algorithms are tested in the different measurement noise scenarios, in which the NPD noise variance is tuned from to . The results of our simulation are averaged by over 1000 Monte-Carlo trials. We randomly deploy sensor nodes in every trial. In this simulation, all algorithms generate 1000 particles at each time step t. Figure 7 illustrates the root mean square error (RMSE) of each algorithm with some different measurement noise scenarios.
In Figure 7, the solid line represents the RMSE of BPF, and the dashed line indicates the RMSE of A-BPF with different , in which changes from to with an interval of 0.05. When , A-BPF totally believes the noisy measurement and has the same accuracy as BPF. The RMSE of A-BPF is decreasing when increases from , which indicates that our adaptation method can improve the measurement likelihood and estimation accuracy. As indicated in each figure in Figure 7, A-BPF has a minimum RMSE with optimal in different measurement noise scenarios. When is larger than the optimal value, the RMSE of A-BPF begins to increase. Additionally, when approaches , it is over tuned and causes high estimation error.
When the measurement nose is low, e.g., in Figure 7a, A-BPF does not improve much, even with the optimal . However, when the measurement noise is quite large, e.g., in Figure 7b, A-BPF can effectively reduce the RMSE with the optimal . Additionally, the gap between A-BPF and BPF is much larger in Figure 7b than in Figure 7a. Besides, the optimal increases when the NPD noise rises, e.g., in Figure 7a, is 0.3, and it becomes 0.8 in Figure 7b.
The comparison of obtained in the simulation and derived in A-BPF is depicted in Figure 8. The solid curve is the optimal in the simulations, and the dashed curve is the optimal based on Equation (24) with different measurement noise. As shown in Figure 8, the optimal based on our calculation in Equation (24) is slightly different from the simulation results, because the optimal is derived according to the approximation in Equation (20). Since the optimal is approaching the simulation results, it is still suitable for implementation. Figure 8 also depicts that the optimal increases with the rise of measurement noise. It testifies for Equation (24) that rises when the measurement noise becomes larger. In this case, A-BPF assigns more belief for the predicted measurement for adaptation.
Figure 9 illustrates the RMSE comparison for BPF, A-BPF, GPF, A-GPF, CPF and A-CPF, and the CRLB for the adaptive filters is also depicted as the optimal indicator. The measurement noise covariance varies from to , and we use the optimal based on Equation (24) as the belief factor in the adaptive PFs. When the measurement error is small, the performances of the PFs are similar. Furthermore, we can find that the adaptive PFs have slightly higher error than the original PFs when the noise is too low. This is due to the inherent sampling method, which generate samples with higher statistical covariance than the measurement noise. In this case, our adaptation method relies on such covariance and causes extra error in the final estimation, which is as illustrated in the previous sections. When the error increases, the estimation errors of BPF, GPF and CPF rise accordingly. Especially, CPF has the highest RMSE due to the imprecise likelihood calculation, although it has constraints. This indicates that the measurement noise is the major impact that influences the estimation performance of PFs. The adaptive PFs have better performance. A-BPF and A-GPF have similar estimation accuracy. The RMSE of A-CPF is the lowest and mostly approaching the CRLB.
We also compare the estimation performance of PFs with varying the particle numbers. As Crisan et al. indicate, the estimation error should converge to zero with the increasing number of particles . However, simulation results show that the estimation accuracy is corrupt with high measurement noise. When the error is small, as illustrated in Figure 10a, the RMSEs of PFs can converge to a very low value with the increased particle number, except BPF and CPF, which illustrates that the measurement noise can influence the convergence of PFs, although not much. In this case, our adaptive method does not improve much, and A-GPF even has a higher RMSE than GPF. When the measurement noise begins to rise, increasing the particle number of the original PFs cannot improve the estimation accuracy. In Figure 10b, the RMSEs of BPF and CPF begin to rise when the number of particles exceed 100, and GPF does not improve either. This implies that high measurement error leads to a significantly inaccurate likelihood calculation, which degrades the estimation. In addition, CPF outperforming BPF, which is mentioned in , only occurs in the low noise case. However, our adaptive method can improve the estimation accuracy and make PFs converge to a low RMSE. In Figure 10, RMSEs of three adaptive PFs decrease with the rising particle number. RMSEs can converge to a very low value even when the measurement error is high. Therefore, our method can reduce the imprecise measurement effect and achieve a better performance.
We also employ a reference system for indoor localization test-beds to examine our proposed algorithms. In this system, we deployed 17 wireless sensor nodes, either along the corridor or in the offices of the research building. A robot carrying a sensor node as a target moved along the corridor of the building with constant speed while recording its own positions . In the previous simulations, we assume that the noise follows an independent identical distribution. However, in the real indoor environment, the wireless signals are propagated through complicated channels. The LOS and NLOS range measurements are mixed for a single target. Thus, a specific distribution for each sensor or anchor is necessary to derive accurate estimation. We still use the DGM to model the measurement noise. All sensors are integrated with the nanoPAN 5375 RF module with a 2.4-GHz transceiver and a 1-Mbps data rate for range measurement, LPC 2387 as the micro-controller and a CC1101 900-MHz transceiver as the radio transceiver for communication. The data collected from sensor nodes are also range measurement values, which are based on TOA. There is an inherent error when the 3D localization is projected into the 2D map, due to the height difference between the sensors and target . We adapt the heights of the sensors to be the the same as the robot to reduce the impact of the height difference in the 3D world. In this case, we can draw an exact 2D trajectory within the map. Figure 11 depicts the map of our experimental building. The triangles, which are randomly deployed, mark the sensor node positions.
We also implement the six algorithms mentioned above to compare their performance. Each algorithm maintains 200 particles, and several trajectories are examined. In Figure 12, we present one estimated trajectory. We compare the estimation performance by evaluating the RMSE. The RMSE results of the six algorithms are listed in Table 1. As shown in Table 1, the mean average errors (MAE), which are the average performance, for adaptive PF are less than the original PFs. Additionally, the adaptive PFs have about 1 m less than the original PFs in the RMSE. The max error, which is the worst case for estimation, in the original PFs is more than 6 m and even 8 m in CPF. However, adaptive PFs have about less than 6.91 m, and the max error can even reach 4.0649 m in A-BPF in Table 1, which is much more precise than the original PFs. The overall cumulative distribution functions (CDF) for both trajectories are plotted in Figure 13. Based on the comparison, our adaptive PFs generally outperform the original PFs and show robust performance in the dynamic indoor environment.
In this paper, we use a DGM, which combines the EPD and NPD, to describe the hybrid LOS/NLOS ranging noise in the indoor environment. Based on this model, we propose an adaptation method by introducing the predicted measurement and its belief factor . The optimal is derived and implemented into our proposed adaptive algorithms, A-BPF, A-GPF and A-CPF. The estimation performance of the adaptive PFs is proven by the CRLB analysis. In the simulation, we observed that some analytical conclusion for PFs are not suitable for the high measurement noise scenarios, and we verify that the adaptive PFs improve the estimation accuracy with different measurement noise environments and that the optimal derived in our method approaches the actual value. The real indoor localization experimental results indicate that, comparing to the original PFs, our algorithms can effectively reduce the estimation error, especially in a high measurement noise environment. Besides, A-CPF is more accurate for target tracking than the other filters.
This work is partially supported by Major Project of Chinese National Programs for Fundamental Research and Development (973 Program, No. 2015CB352400), National Nature Science Foundation of China (Grand No. 61501443, U1401258, 61202416), Science and Technology Planning Project of Guangdong Province (2015B010129011), Shenzhen Overseas High-Caliber Personnel Innovation Funds (KQCX20140521115045446), Shenzhen-Hong Kong Innovative Technology Cooperation Funding (Grant No. SGLH20131009154139588), Shenzhen Fundamental Research Project (Grant No. JCYJ20150630151329298, JCYJ20150401145529029).
The CRLB, which is given by the inverse of the Fisher information matrix (FIM), sets the lower limit for the variance (or covariance matrix) of any unbiased estimators of an unknown parameter (or unknown parameters) .
If denotes the joint PDF of observations and the state , then the score function is defined as the gradient of its log-likelihood:
The FIM, , is the variance of the score function:
and CRLB is just the inverse of FIM; the estimation covariance cannot be lower than it:
Note that the CRLB relies on the system model and the noise distribution. In general, using different information can lead to different results. For instance, if the system only applies the measurement model, the CRLB is higher than the recursive CRLB, which applies the previous information iteratively. In our work, we combine the previous information into the measurement model. When the model and related error distribution are changed, a new CRLB is derived accordingly.
Since based on the Bayesian theorem, it is easily seen that can be decomposed into two parts:
where represents the information obtained from measurement data and represents the prior information.
Firstly, we decompose using the chain rule as:
where is the Jacobian matrix of :
where N indicates the dimension of vector , . Note that we employ the measurement function according to Equation (4), then we have:
and is the FIM conditioned on :
which is the measurement covariance :
then the for conventional CRLB is:
then, we derive the FIM of the adaptive likelihood and recursive formulation based on Equation (A10).
For the adaptive PFs, the prior information is integrated into the likelihood function. Since the measurement is adapted by the prior information, is changed by using the adapted measurement , which is the combination of predicted measurement and observed data. Then, the error covariance does not follow the original error distribution, but changes accordingly. If the measurement noise also follows a Gaussian distribution, we can easily derive the covariance of adapted measurement:
If the measurement noise is independent of each anchor, the covariance matrix can be simplified as , where can be derived independently in each anchor. Similar to Equation (A10), is formulated as:
The FIM of recursive Bayesian estimation has been initially formulated by Petr et al. . The formulation of the FIM, which indicates the estimation procedure of the conventional PFs, is similar to Equation (A4). The FIM of measurement data can be attained according to Equation (A11). Taking the prior information in into account, the prior probability is the transition probability . However, both and should be estimated during the process. Thus, the information about is also not accurate. Then, the estimated parameters for Fisher information is , and the related FIM including and should be reformulated.
For computation, it is extended to be a matrix, which is:
Since the current probability is independent of the previous state, . Then, we obtain:
where is a zero matrix.
For the recursive process, is calculated recursively, which involves as the previous FIM. Then, is expressed as:
then, is given:
where is a part of ; , and are parts of , which represents the previous and current information . Then, is given based on Schurcompletion:
Xiaofan Li and Yubin Zhao proposed the likelihood adaptation method for particle filters. Sha Zhang derived the optimal belief factor and designed the adaptive particle filters. Xiaofan Li and Yubin Zhao constructed the simulation and experiments. Sha Zhang analyzed the performance, both based on the CRLB and experimental results.
The authors declare no conflict of interest.