Efficient indoor localization using graphs

Autor: Lima, Max Willian Soares
Přispěvatelé: edleno@icomp.ufam.edu.br, Moura, Edleno Silva de, Oliveira, Hor??cio Antonio Braga Fernandes de, Balico, Leandro Nelinho
Jazyk: angličtina
Rok vydání: 2019
Předmět:
Zdroj: Biblioteca Digital de Teses e Dissertações da UFAM
Universidade Federal do Amazonas (UFAM)
instacron:UFAM
Popis: Submitted by Max Lima (mw_ac@icomp.ufam.edu.br) on 2019-08-12T20:35:24Z No. of bitstreams: 3 Disserta__o_Max___Final.pdf: 11925926 bytes, checksum: c56c59d1d8ba86a906d53caeb1294546 (MD5) Carta de Autoriza????o de Encaminhamento[3541].pdf: 101848 bytes, checksum: d5bb66cf363d0839e55823484241e402 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Approved for entry into archive by Secretaria PPGI (secretariappgi@icomp.ufam.edu.br) on 2019-08-12T21:05:48Z (GMT) No. of bitstreams: 3 Disserta__o_Max___Final.pdf: 11925926 bytes, checksum: c56c59d1d8ba86a906d53caeb1294546 (MD5) Carta de Autoriza????o de Encaminhamento[3541].pdf: 101848 bytes, checksum: d5bb66cf363d0839e55823484241e402 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Approved for entry into archive by Divis??o de Documenta????o/BC Biblioteca Central (ddbc@ufam.edu.br) on 2019-08-15T12:46:08Z (GMT) No. of bitstreams: 3 Disserta__o_Max___Final.pdf: 11925926 bytes, checksum: c56c59d1d8ba86a906d53caeb1294546 (MD5) Carta de Autoriza????o de Encaminhamento[3541].pdf: 101848 bytes, checksum: d5bb66cf363d0839e55823484241e402 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Made available in DSpace on 2019-08-15T12:46:08Z (GMT). No. of bitstreams: 3 Disserta__o_Max___Final.pdf: 11925926 bytes, checksum: c56c59d1d8ba86a906d53caeb1294546 (MD5) Carta de Autoriza????o de Encaminhamento[3541].pdf: 101848 bytes, checksum: d5bb66cf363d0839e55823484241e402 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2019-08-05 CAPES - Coordena????o de Aperfei??oamento de Pessoal de N??vel Superior 68999532640 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. 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.
Databáze: OpenAIRE
Externí odkaz: