Efficient indoor localization using graphs

Detalhes bibliográficos
Ano de defesa: 2019
Autor(a) principal: Lima, Max Willian Soares
Outros Autores: http://lattes.cnpq.br/0426224695950806
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: eng
Instituição de defesa: Universidade Federal do Amazonas
Instituto de Computação
Brasil
UFAM
Programa de Pós-graduação em Informática
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://tede.ufam.edu.br/handle/tede/7308
Resumo: The main goal of an Indoor Positioning System (IPS) is to estimate the position of mobile devices in indoor environments. For this, the primary source of information is the signal strength of packets received by a set of routers. The fingerprint technique is one of the most used techniques for IPSs. By using supervised machine learning techniques, it trains a model with the received signal intensity information so it can be used to estimate the positions of the devices later in an online phase. Although the k-Nearest Neighbors (kNN) is one of the most widely used classification methods due to its accuracy, it has no scalability since a sample we need to classify must be compared to all other samples in the training database. In this work, we use a novel hierarchical navigable small world graph technique to build a search structure so the location of a sample can be efficiently found, allowing the IPSs to be used in large scale scenarios or run on devices with limited resources. To carry out our performance evaluation, we proposed a synthetic IPS dataset generator as well as implemented a complete real-world, high scale IPS testbed. We compared the performance of our graph-based solution with other known kNN variants, such as Kd-Tree and Ball-Tree. Our results clearly show the performance gains of the proposed solution at 96% when compared to the classic kNN and at least 77% when compared to the tree-based approaches.