Algoritmos probabilísticos para WiFi Fingerprinting

Abstract

A técnica Wi-Fi Fingerprinting é uma técnica amplamente utilizada no posicionamento em interiores. Através desta técnica é possível determinar a posição do dispositivo, combinando os valores da intensidade do sinal recebidos com os valores da intensidade do sinal pré-adquiridos, presentes numa base de dados. O grande problema desta técnica é que, ao longo do tempo o cenário vai sofrendo várias alterações, condicionando a estimativa do posicionamento. Já foram propostos vários algoritmos de localização baseados em fingerprinting, sendo o mais popular o algoritmo k Nearest Neighbors (KNN). O propósito desta dissertação centra-se em construir novos algoritmos que permitam estimar o posicionamento, baseados na técnica Wi-Fi fingerprinting. São abordados nesta dissertação dois tipos de algoritmos, algoritmos determinísticos e algoritmos probabilísticos, com o intuito de avaliar o desempenho de cada um deles em ambientes indoor. Entre os algoritmos determinísticos, foi escolhido e implementado um algoritmo hierárquico já existente. Este algoritmo inclui três etapas distintas, nomeadamente a identificação do edifício, depois do respetivo piso e finalmente a estimativa da localização. Tendo em conta o ambiente em estudo, este algoritmo hierárquico apresenta resultados satisfatórios, sendo utilizado como referência na análise de desempenho dos restantes algoritmos aqui apresentados. Ainda nos algoritmos determinísticos, são efetuadas propostas de alteração ao algoritmo hierárquico de forma a melhorar os resultados. Relativamente aos algoritmos probabilísticos, são descritas e implementadas três variantes. Estas três variantes calculam a probabilidade de uma fingerprint pertencer a um determinado local, utilizando diferentes metodologias. A primeira variante, faz uso de uma distribuição baseada em histogramas. É construído um histograma de valores da intensidade do sinal para cada ponto de acesso de uma fingerprint. A segunda variante recorre à probabilidade de um ponto de acesso ter sido observado numa determinada posição. A terceira variante utiliza a função gaussiana de Kernel para cada ponto de acesso. Todos estes algoritmos, tanto os determinísticos como os probabilísticos foram testados recorrendo a datasets de dados reais, que permitiram obter os resultados descritos neste documento.

Wi-Fi Fingerprinting is a widely used technique in interior positioning systems. Due to this technique it is possible to determine the position of a device, combining the values of the received signal intensity with the values of the signals intensity pre-acquired from a database. The main problem of this technique is that, over the time the scenario suffer several changes conditioning the estimated position. There have been proposed several localization algorithms based in fingerprinting in which the most popular is the k Nearest Neighbors algorithm. This dissertation focuses on developing new algorithms that permit the estimation of the positioning, based in the Wi-Fi fingerprint technique. In this dissertation we make two approaches, deterministic algorithms and probabilistic algorithms, with the aim to evaluate the performance of each one in indoor environments. Between the deterministic algorithms, an existent hierarchical algorithm was chosen and then implemented. This algorithm includes three different steps, the building identification, the floor identification and finally the estimated localization. Taking into account the study environment, this hierarchical algorithm shows decent results, so it is used as a reference in the performance analyses of the other algorithms presented here. Still in the deterministic algorithms, it is made several proposals to modify the hierarchical algorithm in order to improve the results. Relatively to the probabilistic algorithms it is described and implemented three variants. These three variants calculate the probability of a fingerprint belong to a particular location, using several methodologies. The first uses distribution histograms. It is built an histogram of the signal intensity values for each access point of a fingerprint. The second resorts on the probability of an access point being observed in a certain position. The third uses the Kernel’s gaussian function for each access point. All of these algorithms, both deterministic as probabilistic were tested using datasets of real data, that permitted to obtain the results described in this document.