Paper Info
Title
Efficient and Robust WiFi Indoor Positioning Using Hierarchical Navigable Small World Graphs
Abstract
Indoor positioning systems consist of identifying the physical location of devices inside buildings. They are usually based on the signal strength of a device packet received by a set of WiFi access points. Among the most precise solutions, are those based on machine learning algorithms, such as kNN (k-Nearest Neighbors). This technique is known as fingerprint positioning. Even though kNN is one of the most used classification methods due to its high precision results, it lacks scalability since an instance we need to classify must be compared to all other instances in the training base. In this work, we use a novel hierarchical navigable small world graph technique to fit the training database so that the samples can be efficiently classified in the online phase of the fingerprint positioning, allowing it to be used in large-scale scenarios and/or to be executed in resource-limited devices. We evaluated the performance of this solution using both synthetic and real-world training data and compared its performance to other known kNN variants such as kd-tree and ball-tree. Our results clearly show the performance gains of the graph-based solution, while still being able to maintain or even reduce the positioning error.
Year
DOI
Venue
2018
10.1109/NCA.2018.8548076
2018 IEEE 17th International Symposium on Network Computing and Applications (NCA)
Keywords
Field
DocType
indoor positioning systems,k-nearest neighbors,hierarchical small world graphs
Training set,Graph,Computer science,Network packet,Fingerprint,Artificial intelligence,Signal strength,Computer engineering,Machine learning,Scalability
Conference
ISBN
Citations 
PageRank 
978-1-5386-7660-8
1
0.35
References 
Authors
12
6
Name
Order
Citations
PageRank
Max Willian Soares Lima110.35
Horacio A.B.F. Oliveira2213.25
Eulanda M. Dos Santos314316.03
Edleno Silva de Moura498875.44
Rafael Kohler Costa510.35
Marco Levorato646449.51