How to Get the Best Out of Your Fingerprint Database: Hierarchical Fingerprint Indoor Positioning for Databases With Variable Density

In this paper, we consider wireless positioning using Received Signal Strength (RSS) fingerprinting. To obtain good accuracy, this technique requires a database containing a high density of up-to-date fingerprints. However, as acquiring fingerprints through training is labor intensive and the indoor topology is subject to changes, a high density fingerprint database cannot always be obtained. On the other hand, the time to retrieve data from a database with high density can be too high for real-time positioning. To tackle these issues, we introduce the Hierarchical Positioning Algorithm (HPA). In this algorithm, we divide the database into a number of sub-databases with different densities, each containing a sufficiently small number of fingerprints to reduce the data retrieval time. The algorithm starts with a coarse estimate at the highest level, and gradually improves the accuracy in going to the lowest level. This HPA technique requires the construction of sub-databases containing fingerprints that are properly selected to obtain the wanted level of accuracy. This paper considers two algorithms to construct the database: the Minimum Distance Algorithm (MDA) to select the reference points, and the Local Gaussian Process (LGP) algorithm to determine the RSS values at the selected reference points. Simulation results show that the hierarchical algorithm, combined with MDA and LGP to construct the sub-databases, is a fast algorithm that can achieve high accuracy, even with a database having a variable density of fingerprints.