Ⅰ. INTRODUCTION
In WiFi-based localization, the estimated location is not always accurate and oscillates even when a user stays at a fixed location. Thus displaying the location of the user in a stable manner is one of challenging issues of WiFi-based indoor positioning systems. In particular, with single location estimation, there is little means to cope with this accuracy fluctuation problem without the help of additional sensors such as a gyroscope, a barometer, a compass, and a 3-axis accelerometer. However, in the case of navigation or real-time tracking, the current location estimation can be improved or stabilized to some degree by referring to previous signals and location information (i.e., historic data).
Basic Kalman Filter (BKF) [1] was developed to deal with similar problems for an object moving in linear dynamics. BKF predicts the next location of an object based on the previous location and velocity information of the object. Then it combines the predicted location with the measured location by computing the weighted average of the two locations.
However, BKF is not adequate for indoor positioning systems because the pedestrian does not always move on a straight line, and the accuracy of WiFi-based indoor localization fluctuates. In fact, applying BKF to indoor positioning could improve the prediction results on straight lines, but the results were worsened at corners and intersections by the corrections made by BKF.
There have been some attempts to overcome the constraints of BKF. For example, Extended Kalman Filter (EKF) [2, 3, 4] models an object moving on a nonlinear curve. EKF enables us to incorporate additional information from sensors like a gyroscope and a compass into the model with the assumption that the direction and the movement of the sensors are equivalent to those of the object. In car navigation, this assumption is quite reasonable because the sensors are usually installed at a fixed location with a constant orientation angle in the car. However, in indoor positioning, this assumption does not hold any more because the orientation angle of a handheld device is not stabilized during service. Note that there are many different ways of carrying the handheld device.
Another approach to enhance tracking accuracy is to use particle filters [5, 6]. Particle filters scatter numerous particles to a target area and let the particles move their locations according to the received signals. The predicted location is obtained by computing the weighted average of the particles. Since numerous particles participate in the prediction, the wrong estimation of each particle can be controlled to some degree. However the run time overhead of keeping track of numerous particles is a barrier for the particle filters to be practically used in real fields. As a result only a little work showing the effect of applying particle filters for localization especially using WiFi signals has been reported despite the potential of particle filters.
As BKF and EKF are not suitable for WiFi-based indoor navigation with a handheld device such as a smart phone, and particle filters may incur serious processing overhead, we propose a new location filter for indoor positioning. As the new filter operates in the same framework as that of BKF (i.e., it consists of prediction and update phases), and it borrows the key notion of particles filters adapting to the drastically changing accuracies, the propose filter was named as adaptive hybrid filter (AHF). Like BKF, AHF does not require any additional information from sensors like a gyroscope, a barometer, a compass, or a 3-axis accelerometer. But it does not mean that AHF cannot be integrated with them at all. Like EKF, if necessary, the information from the sensors can be used additionally by extending AHF.
AHF takes into consideration two aforementioned characteristics of WiFi-based indoor localization. The dynamically changing accuracy of WiFi-based localization, which is rooted in the fluctuation of WiFi signals, is one of characteristics. With the consideration of this characteristic, AHF adopts a new dynamic weighting scheme and substitutes it for the function of Kalman gain. Next, we assume that the pedestrians will move on a way network which consists of nodes and links derived respectively from intersections and hallways in indoor map. This assumption allows us to restrict the next possible locations predicted by the filter to be confined to only a small number of locations or particles. Thus AHF can be also considered as a variant of particle filters which use a very limited number of particles appearing only on a restricted area.
In this paper, the evaluation compared AHF, BKF, and a particle filter performed on two data sets collected from KAIST library, Daejeon, Korea, and E-mart discount store, Seoungsu, Seoul. From the evaluation, the comparison results showed that AHF achieved accuracy improvements of 18.0 % at the KAIST library and 25.0 % at the E-mart discount store. AHF achieved slightly better accuracy improvement than the particle filter, but it showed greatly improved performance in processing time compared with the particle filter. The processing time of AHF was about 80 times faster than that of the particle filter. When we applied AHF and integrated it with our indoor localization engine and navigation system, "myCoex," which is known as the first commercialized indoor navigation system, the effect of using AHF was apparently observed, especially in improving the accuracy and the stability of the system.
This paper is organized as follows. Section 2 introduces related work on various indoor navigation filters. Section 3 gives an explanation of AHF in a formal way. Experimental results are reported in section 4, and we draw conclusion in section 5.
Ⅱ. RELATED WORK
It is known that the BKF can make a significant contribution to the improvement of positioning in a linear system. However, there are still a plenty of rooms to further improve Kalman filter for indoor positioning. There were some studies to improve the BKF in its prediction model and weighting scheme. In the category of prediction model, there are two main research streams: utilizing additional sensors and utilizing map information. Digital compass and gyroscope are the examples to provide information on the direction for which pedestrians are heading. Map information allows us to figure out if the movement of a pedestrian is correctly predicted or not. Inertial Navigation System (INS) is a technique used for outdoor car navigation. It estimates the current location without external references but with velocity and orientation that are obtained by some sensors embedded into the system. Some attempted to use the INS for the indoor pedestrian navigation system as well to improve prediction model of Kalman filter. Frédéric et al. [7] proposed a method using a gyroscope. As gyroscope provides only angular rate, the filter estimates the orientation with cumulated angular rate. To track the orientation, this study applied additional Kalman filter to keep track of orientation. As the angular rate from gyroscope is cumulated, the error from gyroscope is also cumulated, so this study proposed a mechanism to periodically reset the sensor. Jirawimut et al. [8] proposed a method using a digital compass. In their method, since the digital compass may have bias, the filter keeps track of the bias in the state and uses it to correct the value of digital compass. Fang et al. [9], Davison et al. [10], and Tsai [11] also used digital compass or gyroscope to improve the accuracy of Kalman filter.
The methods using additional sensors, however, are not appropriate for indoor navigation system because the mobile device, that is our target device, is not carried in a fixed way. A pedestrian may hold his/her own mobile device in a hand, pocket, bag, etc, and the orientation angle of the device can be changed from time to time. Consequently, the estimated result is sometimes worse than not using the information from the additional sensors. Moreover, using additional sensors consume more battery to detect the orientation.
Particle filters are another approach to enhance the tracking accuracy by introducing numerous particles in prediction. The particle filters scatter numerous particles at a target area and use a Monte Carlo method to represent posterior distribution of the particles [5]. The location of the particles gradually changes according to received signals. The prediction is made by computing the weighted average location of the particles. Since there could be many different ways for assigning weights to particles and moving particles, many techniques can be developed in this category. The effect of using particle filters using infrared beacon and ultrasonic raging was reported in [6, 12]. But the effect of particle filters especially using WiFi signal was not reported yet. Moreover, the question if the computational overhead incurred by processing numerous particles can be accommodated in mobile phones, which are equipped with only limited computational and storage resources, are still remain unclear.
There are some researches using a map information for improving the prediction model. Anindya et al. [13] proposed a sophisticated prediction model using the map information. In the method, the layout of a building is divided into cells, and each cell is set to 0 or 1 according to the possibility if the pedestrian can walk through the cell. As a result, all the walls or obstacles are set to 1 and others are set to 0. In the prediction model, an imaginary repulsive force is exerted to pedestrian and all the cells set to 1, and the force can modify the velocity vector of state. This method works well at corners or dead-end corridors, but when all the forces exerted are symmetric and the resultant force is 0, it cannot modify the velocity vector.
There were some studies in the category of weighting improvement as well. Yim et al. [14] proposed a method which gives more weights to the measured location than predicted states at intersections. Since the accuracy varies as the density of AP changes or depending on the building layouts, the method cannot yield the results in a stable manner. Moreover, this method is effective only at intersections.
Ⅲ. STATE AND PREDICTION MODELS OF AHF
1. State Model
The state model represents an instance of a target object at a certain time. To distinguish the differences between AHF and BKF, we contrast the state models of the two filters. In BKF, the state model is specified using the location and the velocity vectors; that is, the state instance at time k, xk is represented by , where are coordinates of x, y at time k, and are the velocities at time k [15].
The state model of BKF has been slightly changed in AHF. The state model of AHF consists of a location vector, speed, and way link; that is, the state instance at time k, xk is represented by , where Sk is the speed, and , respectively, are the start and the end nodes of a way link corresponding to an link of a way network. In the model, the speed and the way link substitute for the velocity vectors of BKF's state model. Figure 1 shows the state models of AHF and BKF.
2. Prediction Model
Based on the state models defined above, the relation is established between the state instances xk , at time k, and xk - 1 at time k - 1. In BKF, the relation between the states at time k and k - 1 is defined by:
Contrary to BKF predicting one coordinate, AHF generates several candidates, each of which corresponds to a particle in particle filter. In AHF, the relation is defined by:
where, θ is the angle of the way link and the base line. The base line is shared by all the way links. Since there are two directions on a straight line, θ can have two possible values on the straight line: θ and θ + π. At a perpendicular four-way intersection, θ can have four possible values: θ, θ + π/2, θ + π,θ + 3π/2.
This means that for an instant on a straight line, there are two possible candidates for predictions: forward and backward directions. For an instant on a four-way intersection, there are four possible candidates for predictions. Among the candidates, the closest candidate to the measurement is chosen as the final prediction. As long as the angle of the way links connected to the intersections is known, the number and the angle of the way links do not matter in AHF. Note that the angle of each way link can be obtained once the way network is derived from a map.
The prediction model of AHF is described by:
where, wk is the process noises , and Qk is the process error covariance. In the observation model of AHF, the observation zk is defined by:
where, υk is the observation noise , and Rk is observation error covariance.
Unlike BKF, AHF does not use Kalman gain in the update. In AHF, instead of building an error covariance matrix, we compute the accuracy at each location, and then compute the relative error level at each location. Best Candidate Set (BCS) method [16] was used for the error estimation. After the relative error level is determined, the weights for a prediction and a measurement are defined by:
where, is the estimated error, is the weight for a prediction, is the weight for a measurement, and Nk is the normalizing factor which maps the weight into a real number in the range of 0 and 1. The weight increases as the average of estimated errors decreases. Once the weight is computed, the filter combines the predictions and measurements by:
where are the coordinates of a prediction, which are the results of a prediction phase, and are coordinates of an estimated location.
Ⅳ. EXPERIMENTAL RESULTS
1. Experiment Setup
The validity of AHF for indoor navigation was evaluated on two data sets: one collected from the 4th floor of a KAIST library, KAIST, Daejeon, Korea and one from the 1st floor of E-mart at Seongsu, Seoul, Korea. The 4th floor of KAIST library is an open space of 2232 m2 , and the space is divided by 67 bookshelves, making the way network complicated. The learning data was collected at 557 points, and 20 fingerprints were collected at each point. For the test data, 20 traces were collected, and each of the traces included 174 measure points.
E-mart is one of the biggest discount stores with 200 chains in Korea, and E-mart at Seongsu is the headquarters and main store of the chain. The data was collected on the 1st floor, which was 8800 m2 . E-mart is also an open space, and the area is divided by dozens of shelves. The learning data was collected at 725 points, and 14,500 fingerprints were collected in total. For the test data, like the case of the KAIST library, 20 traces were collected, and each of the traces included 188 measure points.
2. Accuracy Results
The evaluation compared the accuracy improvements achieved by AHF, a particle filter and BKF at the KAIST library and E-mart respectively. To measure the accuracy of each method, we implemented a WiFi fingerprint-based localization engine using weighted kNN algorithm. Then BKF, AHF, and a particle filter were developed and integrated with the localization engine for the measurement. The particle filter conducted its prediction with 5,000 particles. Since there are many different ways of assigning weights for AHF and particle filters, we used a uniform value in assigning weights to particles for a fair comparison. For the test set, 10 traces were prepared and the accuracies were obtained by computing the average of results from the 10 traces.
As shown in Table 1, AHF showed the best accuracy among the three methods both at the KAIST library and the E-mart. At the KAIST library, AHF achieved an accuracy improvement of 16.7% when compared it with the accuracy measured without filtering (from 3.42m to 2.85m in the average error distance), whereas BKF achieved an accuracy improvement of only 5.9% and the particle filter KK %. At the E-mart, as much as 25.0% accuracy improvement was made by AHF (from 4.88m to 3.66m), whereas BKF achieved only a 15.0% accuracy improvement and the particle filter 23.4 %.
The processing time of particle filter was about 80 times slower than that of AHF. If particle filter use the less number of particles, it could reduce the processing time. But instead, the accuracy was downed. For example, when particle filter used 1,000 particles, the processing time was reduced by 5 times. But the accuracy was downed about 7 - 8 % in both data sets. On the other hand, when the filter increased the number of particles to 10,000, only the processing time greatly increased without further improvement of accuracy.
The reason that filters could achieve more improvement at E-mart than at KAIST was because the length of straight lines at E-mart were usually longer than that at the KAIST library. Usually, we can expect a greater filtering effect on straight lines than at corners or intersections. The accuracy results of AHF was around 10% better than what was achieved by BKF and 2 - 6% better than the particle filter.
3. Contribution Results
In order to figure out how much restricting the prediction locations to the way network and dynamic weighting scheme contribute to the accuracy improvement, the accuracies were measured with/without incorporating each method. When we analyzed the results, in the improvement, the contributions of restricting the prediction locations to the way network was 7.93%, and dynamic weighting scheme was 3.23% at E-mart and 9.45% and 2.66%, respectively, at the KAIST library. The effect of dynamic weighting scheme was also observed in the particle filter because the particle filter using dynamic weighting scheme showed slightly better accuracy than the one using static weighting scheme. Table 2 is the summary of the evaluation results with/without incorporating way network-based prediction or dynamic weighting scheme at E-mart and at KAIST.
In both of the cases, the contribution of the way network-based prediction was greater than the contribution of the dynamic weighting scheme. We attribute this to the result of inaccurate error estimation because the correlation between true error distance and estimated error distance was 0.425, which is a weak correlation.
Figure 2 shows the change of the weights for measurements depending on the true error distance. The lower dotted line shows the change of the true error distances and the upper line shows the change of the weight values. The experiment was performed with a trace sequence. As depicted in Figure 2, when the true error distance was long, a relatively low weight was assigned to the measurement, whereas if the true error distance was short, a relatively high weight was assigned to the measurement. The correlation between the true error distance and the weight for the measurements was only −0.325 for the case of KAIST library. This means that, if a better error estimation method is devised, the contribution of the dynamic weighting scheme to the accuracy improvement will grow.
Since the ratio of corners and intersections to straight lines at the KAIST library is bigger than at the E-mart in the trace, the improvement made by restricting the prediction locations to the way network at the KAIST, 9.45%, is slightly higher than that at the E-mart, 7.93%. Note that AHF usually shows more improvement in accuracy than BKF at corners and intersections. The weighting scheme, however, works better at the E-mart, 3.23%, than at the KAIST, 2.66%, because the minus correlation between true error distance and weight for measurement of the E-mart dataset, −0.344, is slightly higher that of the KIAST dataset, −0.325. This indicates the contribution made by dynamic weighting scheme is heavily dependent on the accuracy of error estimation.
4. Accuracy of Error Estimation
Since the accuracy of error estimation is a critical factor deciding the accuracy of localization, we compared the true error with the error estimated by BCS method. Figure 3 shows the correlation between the true error distance and the error distance estimated by BCS method. The experiment was performed in N5 building of KAIST. Although the result is somewhat dependent on datasets, the overall correlation stayed in between 0.4 and 0.7. This indicates that, although error estimation of BCS method is not so accurate, the estimated result can still be used as an error indicator.
5. Application
In order to confirm the effect by the improved accuracy, we generated traces wi/wo applying AHF and then visualized the traces on the maps. As illustrated in Figure 3 the average error distance was a key factor for a generated trace to be close to the real trace. In the Figure 4, the red line represents the generated traces and the green line original user trace. As shown in figures in Figure 4, a), the generated traces were getting closer to the original traces as the error distance was getting smaller. This means that if the accuracy is improved by AHF, a more realistic trace would be generated.
Actually, AHF is applied for upgrading myCoex, a commercial WiFi-based indoor navigation system released by KTNET and KAIST on Oct. 2010 in Korea. Although AHF is just one of location filters equipped for myCoex, the contribution of AHF was apparent to the accuracy improvement of myCoex indoor navigation system. We could confirm the improvement through user experiences as well.
Ⅴ. CONCLUSION
We have proposed AHF for indoor navigation by extending BKF. AHF achieved considerable improvement in the accuracy for both data sets of KAIST and of E-mart. The improvement was due to the restriction of the movement of the target object to the way network and the dynamic weighting scheme based on error estimation. We can expect further improvement if we develop a more advanced and reliable error estimation technique, which is an open problem. Incorporating sensor information into the AHF is another source of improvement. In fact, AHF is just one of the filters used for an indoor navigation system. Signal filters and map matching are the typical filters that should be integrated together with AHF. The interrelations between the filters should be studied further, and analyzing the effect of applying AHF with the filters is our future work.
