Algoritmos de localização com informação histórica e realimentação dos utilizadores

Abstract

Atualmente, a capacidade de localizar qualquer dispositivo móvel é uma questão de elevada importância, dado que tal informação pode ser usada num vasto conjunto de aplicações, como por exemplo, navegação, orientação de apoio ao turismo, monitorização ou segurança. Com o elevado aumento do número de serviços ou aplicações dependentes da localização, faz sentido pensar em novas formas de localização, preferencialmente mais exatas e precisas. Em ambientes outdoor a localização de dispositivos já é assegurada, principalmente pelos sistemas de localização baseados em GPS (Global Positioning System). Em ambientes indoor podem ser utilizadas várias tecnologias sem fios para localizar-se dispositivos móveis, como por exemplo, RFID (Radio-Frequency IDentication), Bluetooth, UWD (Ultra- Wide-Band) ou WLAN (Wireless Local Area Network). Recentemente, tem-se investido muito em localizar dispositivos móveis numa WLAN, devido a várias razões: já é usada massivamente noutros serviços (principalmente para acesso à Internet), os equipamentos de rede são baratos e, na maioria dos casos, a sua implementação é facilitada através da utilização de uma infraestrutura já existente. Uma das formas de localização usada nas redes sem fios baseia-se no mapeamento da potência do sinal recebido (RSS - Received Signal Strength), utilizando a técnica fingerprinting. Esta técnica tem como modo de funcionamento recolher, previamente, amostras de valores de RSS que serão usadas, pelos algoritmos de localização, nas estimativas de posicionamento dos dispositivos. Muitos algoritmos de localização baseados em fingerprinting já foram propostos e o mais popular é o algoritmo KNN (K Nearest Neighbors). Este algoritmo tem mostrado uma boa exatidão e precisão em vários cenários. No entanto, devido à existência de vários obstáculos dentro dos edifícios, como por exemplo, paredes, mobiliário, pessoas em movimento ou aberturas e fechos de portas e janelas, os sinais eletromagnéticos estão suscetíveis a vários fatores que os degradam. Além disso, em ambientes indoor existe maior probabilidade de ocorrerem interferências entre vários sinais eletromagnéticos e, como consequência, provocar uma maior degradação dos mesmos. Com a utilização de informação histórica neste tipo de algoritmos pode-se minimizar, ou mesmo eliminar estes problemas. Para isso, é necessário sumariar e guardar o histórico dos dispositivos. Outra solução capaz de evitar os problemas referidos é utilizar-se o feedback dado pelos utilizadores do sistema. Nada melhor do que eles para avaliar os resultados calculados pelos algoritmos e, através dessa avaliação, melhorar os atuais e futuros resultados. Este documento descreve todo o trabalho realizado no desenvolvimento e implementação de algoritmos de localização que utilizam essa informação, bem como os resultados obtidos.

Nowadays, being able to locate any mobile device is a major and important issue since localization information can be used for a broad range of applications such as navigating, tracking and monitoring applications. With the high increase of location services and applications it is pertinent to devise new ways to locate devices, more accurate and precise. For outdoor localization, almost all solutions are GPS based. For indoor localization several technologies are used such as, RFID, UWD and WLAN. The use of WLANs to locate devices has been subject of research in recent times and has increasing importance due to several reasons. It is already widely deployed for other services (being the Internet Access the most important), the equipment is cheap and also the deployment, since it is facilitated by the use of a pre-existing infrastructure. One of the strategies that can be used to perform Indoor Localization using WLANs is based on the Received Signal Strength (RSS) using the Fingerprinting technique. Fingerprinting can be divided into two phases: an offline phase and an online phase. In the first phase, called the offline phase, RSS values are measured at each point of a given set of locations distributed inside the localization area. The information collected in this phase is afterwards used in the online phase to estimate a device location. In the online phase, RSS values obtaining by the device are compared with those previously observed in the offline phase in order to infer the device's position. Many algorithms, such as deterministic and probabilistic methods and even neural networks, have been proposed to compute device's location in online phase. KNN algorithm is the most popular deterministic one. In this algorithm, the position of mobile user is estimated by averaging the position of the K nearest points in fingerprinting map. The algorithm begins to compute de distance between the current state of the device and each point in fingerprinting map, using the measured RSSs. Then the K points with the lowest distance are chosen and the mean distance between then is computed and presented as the device's position. This algorithm has proven good accuracy in several scenarios, however due to the existence of obstacles in indoor environments, like walls and furniture, the signal propagation in an indoor environment is subject to reflection and diffraction, and usually the K nearest neighbors found are scattered and not dose to each other. This causes some significant errors in the algorithm results in some situations. The use of historical information may minimize or even eliminate this problem. This requires summarize and keep historical information of the devices. Another possible solution to avoid the mentioned problems is to use the users feedback. Nothing better than the system users themselves to evaluate the results provided by the algorithms and through this evaluation improve the current and future results. This document describes all the work done, building and developing several localization algorithms that use this information, as well as the results obtained.