Smallest enclosing circle-based fingerprint clustering and modified-WKNN matching algorithm for indoor positioning

Abstract

Methods to cluster fingerprints based on Smallest-Enclosing-Circle (SEC) and to modify Weighted-K-Nearest-Neighbor (WKNN) matching algorithm for indoor fingerprint positioning system are proposed. Based on the approach to computing the smallest k-enclosing circle, the method proposed clusters fingerprints in database by introducing reference points' coordinates, instead of their received signal strength (RSS). This approach performs higher accuracy of positioning areas compared to conventional clustering algorithms, which are based on RSS. Meanwhile, this paper analyses the transmission characteristics of wireless signals in dense cluttered environments, and derives a novel path-loss-model-based weight computational method for WKNN matching algorithm. A modified-WKNN (M-WKNN) matching algorithm for indoor fingerprint positioning system is proposed and experiments are implemented in China National Grand Theatre. Results show that the location area accuracy using the proposed clustering algorithm is improved by 30% compared to that using K-means algorithm, and the positioning accuracy of M-WKNN is 11.9% and 29.1% higher than that of WKNN and KNN, respectively.