Title: Crowdsourced Fingerprint Database Update for Indoor Localization
Author(s): Boseon Yu, Taikjin Lee
Published in: Proceedings of the 29th International Technical Meeting of The Satellite Division of the Institute of Navigation (ION GNSS+ 2016)
September 12 - 16, 2016
Oregon Convention Center
Portland, Oregon
Pages: 2335 - 2356
Cite this article: Yu, Boseon, Lee, Taikjin, "Crowdsourced Fingerprint Database Update for Indoor Localization," Proceedings of the 29th International Technical Meeting of The Satellite Division of the Institute of Navigation (ION GNSS+ 2016), Portland, Oregon, September 2016, pp. 2335-2356.
Full Paper: ION Members/Non-Members: 1 Download Credit
Sign In
Abstract: The primary goal of this work is to minimize the maximum error rate with time leveraging range query and crowdsourced update strategy for fingerprints database which still remains challenging. For last several years, a lot of studies have been conducted to achieve highly accurate indoor localization. Especially, indoor localization approaches based on the signal strength of WiFi have been attracting more and more interests since the approaches require no more infrastructural costs beyond the existing WiFi infrastructure. Many researches that make use of WiFi signal strength for the indoor location estimation have been reported in the literature but fingerprint based approaches have become one of the most popular approaches since it is able to achieve more accurate localizations comparing to triangulation based approaches. Many variations for the fingerprint based approach have been made for more precise localizations. For example, some of the variations cluster the fingerprints according to coordinates or RSS signatures and apply the kNN estimation. Some other variations alter the k in kNN estimation according to their own conditions. These variations differ from each other in detail but share the following methodology: create a database that consists of coordinates and received signal strength (RSS) signatures of reference points (RPs), which are so called fingerprints; and then, to estimate the location, find the k most similar fingerprints in the database to RSS read observed by user’s device such as smart phone, and return the estimated location as a result. However, despite the variations, achieving more precise indoor localization still remains challenging. Major factors that pose such a challenge on indoor localization are two folds as shown below. - The unstable WiFi signal strength fluctuating against environmental conditions such as temperature, humidity and human blocking. - Increased location ambiguities due to distant reference points that have similar RSS signatures. One main factor that makes the indoor localization challenging is that WiFi signal strength changes even at the same location with environmental conditions such as temperature, humidity and human blocking. We observed that the RSS of WiFi signals can change up to 30% in only a few dozen seconds and the RSS of WiFi depends heavily on whether objects including humans are in the line of sight. This indicates that fingerprints database may be no longer capable of providing accurate location estimations even if the current RSS reads are reliable because the environmental conditions including human blocking of when the fingerprints database had been made are different from those of when a user requests a location. Thus, frequent reconstructions of fingerprints database are necessary. However, constructing fingerprints database is not only time-consuming but also labor intensive. Surveyors have to walk from room to room, gaining RSS signatures to all areas of a building to create the required fingerprint database. For a moderately-sized office building, the process may take several days. Another factor that poses fundamental limits on WiFi localization accuracy is distant reference points that have similar RSS signatures. Especially, the distant reference points have a critical impact on the result of kNN estimations since distant reference points involved in kNN estimations increase location ambiguities. This is one of the most critical reasons for poor performance of indoor localization in hall area. In order to address these problems, we propose a crowdsourcing strategy for updating fingerprints database and a novel approach for indoor localization that leverages range query to minimize the maximum error rate. Please note that constructing fingerprints database is beyond the scope of this work, rather, we focus more on updating fingerprints database. The primary goal of our update strategy is to minimize the maximum error rate with time. The maximum error rate increases with time due to changes in environmental conditions such as APs, walls and furniture and thus, for supporting long-term localization service, it is necessary to devise a crowdsourcing-based update strategy that can facilitate the catch-ups. The performance of fingerprint database, i.e., the capability of selecting the most relevant k RPs to the observed RSS read, is highly dependent on filtering noisy data. In order for a fingerprint database to support robust long-term location estimations, we first determine that the pair of the RSS read and the resulting coordinate is good enough for the update. If not, the pair should be dropped from the update. Generally, it is hardly possible to guarantee the correctness due to physical limits on WiFi signal strength and thus many studies simply insert the new pairs without considerations on the correctness or employ other facilities such as short range beacons to guarantee certain level of accuracy. In this work, we propose a PDR-aware update strategy on fingerprint database. The overall procedures are as follows. We build a histogram for each RSS value of a RP and the update is allowed only when location estimations from PDR and WiFi localization agree with each other. PDR-based systems might be not reliable for long-term services due to the accumulated errors but are highly reliable for short-term services. One may think that the accumulated errors of PDR will eventually make the update less effective but we expect to alleviate the error through WiFi-based localization estimations. More details will be given later in this abstract. Thus, if the both agree, we can determine that the RSS read and the resulting coordinate involve less error rates. The histograms of RPs involved in kNN estimations are updated with given RSS read. The histograms are used for selecting k most similar RPs in a probabilistic manner. We build a histogram for each RSS value for a RP. For example, if a RSS signature consists of t RSS values, we build t histograms for the RP. This may occupy huge memories but the memory usage is stable since the usage is not dependent on how many people use the system and can efficiently cope with frequent update without additional memory requirements. With this strategy, we can keep the size of fingerprint database and the computational burden for location estimations manageable under any circumstances. For location estimation, we propose a kNN based approach that leverages range query. Usually, kNN-based location estimations are computationally expensive because they need to measure the distance between the given RSS read and all of the fingerprints in a database and select the most similar RPs of k for all the location estimations. Furthermore, if there are distant reference points that have similar RSS signatures to the given RSS read, the resulting coordinates may have severe error rate as we mentioned earlier. In order to address these problems, clustering based approaches have been proposed. The approaches first cluster the fingerprint database according to their coordinates or RSS signatures and once a RSS signature for location estimation arrives, they find the closest cluster and the k fingerprints are chosen inside the cluster. Clustering-based approaches report much less computational burden and much more competitive maximum error rate since they measure the distance only with fingerprints that reside in the cluster not with every fingerprint and thus computational burden and maximum error rate are limited by the size of the cluster. However, their accuracies are highly dependent on the cluster structure and the chosen cluster might be incorrect. On the other hand, our proposed approach is independent on the cluster structure and reports much less maximum error rate because the approach leverages the range query. The range query, which is frequently used in many fields such as spatial database, is to fetch interesting things that lie in a given range. We leverage the range query in order to limit the maximum error rate. Once a location is determined, we can expect that possible locations for the next movement are around the immediate location. The key idea beyond the proposed approach is to simply fetch RPs that fall in a rectangle centered by immediate location with radius, R, and then perform kNN estimation with only these RPs and thus, the maximum error rate is limited by the rectangle. This approach reports much less computations as well since the rectangle is quite small comparing to a cluster. Overall procedures are as follows. We first generate clusters based on the coordinates of reference points and perform kNN to estimate the initial location, Linit. For the next location estimation (Lt), before kNN, we perform range query with a rectangle whose center and radius are Linit and R respectively, to fetch the most reasonable RPs for the next location and then, perform kNN estimation only with the RPs. The overall procedures are repeated with Lt to estimate the next location, Lt+1. In this manner, we can achieve more accurate localizations as well as more competitive response time. In addition, this approach makes the fingerprints database more robust by diminishing the maximum error rate. The most critical reason that increases the maximum error rate of database is location ambiguities resulting from distant reference points with similar RSS signature involved in kNN estimations. The proposed approach alleviates the ambiguities by not allowing reference points outside the rectangle, which is much smaller than a cluster, to join location estimations. The main contributions of our work are two folds. - We propose a PDR-aware crowdsourcing strategy that not only can provide high level of correctness for updating fingerprints database without additional facilities but also can efficiently cope with massive update by keeping the size of database and computational burden manageable. - We achieved more accurate location estimations for indoor systems by leveraging the range query with much less computational burden. As future work, we are planning to combine the proposed approach with PDR-based location tracking system for indoor localization as well as database updates because the approach is quite suitable for an accommodation with PDR-based location systems. The most straightforward approach for the accommodation is to simply change the rectangle used in range query according to sensor data from PDR. For example, we can narrow down the rectangle toward the direction reported by PDR or we can modify the R by the number of steps measured by PDR. Furthermore, we expect that our approach may be helpful for PDR based long-term location tracking system because the accumulated error might be alleviated or nullified by the result of the proposed approach.