FastGraph - unsupervised location and mapping in wireless networks

Abstract

Wi-Fi Based Indoor Positioning solutions normally require complex and time-consuming deployment processes or have limited accuracy. Fingerprinting Matching is one of most used techniques for indoor positioning, which relies on a radio map that is normally created offline in a calibration phase by manual site survey. Wi-Fi Fingerprint can be used to locate regular mobile devices, such as smartphones, using only software and can be used in any indoor environment without being necessary to deploy additional infrastructure, relying only on the existing Wi-Fi infrastructure. However, in most cases the manual site survey is unpractical and involves a significant effort, even for small scale spaces. Moreover, due to the dynamic nature of radio environments, to maintain the system performance, the site survey has to be repeated often to keep the radio map updated. This process is not feasible in large spaces, and compromises the scalability of this type of approach. Solutions have been proposed to reduce the calibration effort, using collaborative site survey to create and maintain the radio maps, or by using Model-Based methods to approximate a radio map. However, the reduced calibration effort usually implies a lower positioning accuracy and higher computational requirements. In this context, FastGraph is proposed as a new solution able to provide unsupervised positioning using different devices, such as smartphones or autonomous machines, while automatically creating and maintaining a Radio Map. A 3D Force-Directed Graph is used to rapidly model the radio environment. The 3D Graph is iteratively constructed with data collaboratively collected by several devices. Orientation and motion information, obtained from different sensors, can be used to improve the Graph constrains. FastGraph is able to operate shortly after its deployment, without previous knowledge about the environment. The proposed solution uses a novel algorithm to automatically provide location while simultaneously updating the radio map; and estimate the position of the Access Points (APs) and location-specific radio propagation parameters. In addition, FastGraph does not rely on expensive hardware or requires high computational effort. The FastGraph approach may be used in different contexts. In addition to the indoor positioning, the radio maps created by FastGraph include supplementary information that can be used to automatically map the interference in Wi-Fi networks and even to automatically map the physical space. The described solution was deployed and evaluated in two very distinct real world spaces, an industrial environment and a regular office building. The experiments, in these two spaces, evaluated the several aspects of FastGraph, and considered scenarios where only Wi-Fi data is available and when the Wi-Fi can be combined with data from other sensors. The results suggest that the proposed solution has potential to provide interference information in wireless networks and provide positioning in different indoor scenarios, from regular buildings, to autonomous vehicles in industrial environments, with the possibility of being also extended to outdoor spaces using data from cellular networks, especially considering the characteristics of the upcoming 5G networks.

Os sistemas de posicionamento indoor baseados em Wi-Fi normalmente implicam processos de implementação complexos e longos, ou são limitados em termos de exactidão. Fingerprinting Matching é uma das técnicas mais utilizadas para posicionamento indoor, utilizando mapas de rádio normalmente criados offline, numa fase de calibração, através de mapeamento manual do ambiente rádio. O Wi-Fi fingerprinting dispensa a instalação de uma infra-estrutura (usa a infra-estrutura Wi-Fi existente) e pode ser utilizado para localizar dispositivos móveis comuns só com recurso a software. No entanto, na maioria dos casos o mapeamento rádio manual não é prático e envolve um esforço significativo, mesmo em espaços pequenos. Além disso, devido à natureza dinâmica dos ambientes rádio, para manter a desempenho do sistema, a fase de calibração tem de ser repetida frequentemente para manter o mapa de rádio atualizado. Por estes motivos, este processo não é praticável em espaços de grandes dimensões, comprometendo a escalabilidade deste tipo de abordagem. Por este motivo têm vindo a ser propostas soluções para reduzir o esforço de calibração, recorrendo a mapeamento colaborativo do ambiente rádio para criar e manter os mapas de rádio, ou utilizando métodos baseados em modelos para obter um mapa de rádio aproximado. Contudo, a redução do esforço de calibração normalmente traduz-se numa redução da precisão no posicionamento, ou no aumento dos requisitos computacionais. Neste contexto é proposto o FastGraph, um novo sistema capaz de fornecer automaticamente posicionamento utilizando diferentes dispositivos, como por exemplo smartphones ou veículos autónomos, e capaz de em simultâneo criar e manter um mapa de rádio. É utilizado um Grafo 3D (3D Force-Directed Graph) para rapidamente modular o ambiente de rádio. O Grafo 3D é criado iterativamente com os dados recolhidos colaborativamente por múltiplos dispositivos. Dados de orientação e movimento, obtidos através de diferentes sensores, podem ser usados para melhorar as restrições espaciais do Grafo. O sistema FastGraph é capaz de operar rapidamente após ser instalado, sem necessitar de qualquer informação prévia sobre o ambiente rádio ou espaço. A solução proposta implementa um algoritmo original para fornecer posicionamento enquanto automaticamente mantêm o mapa de rádio atualizado; estima a posição dos Pontos de Acesso Wi-Fi e parâmetros de propagação específicos para cada local do espaço. Além disso, a solução FastGraph não se baseia em hardware dispendioso e não implica elevado esforço computacional. A solução FastGraph pode ser utilizada em diferentes contextos. Além do posicionamento indoor, os mapas de rádio criados pelo FastGraph incluem informação suplementar que pode ser utilizada para mapear automaticamente a interferência em redes Wi-Fi, e até para mapear automaticamente o espaço físico. A solução descrita foi instalada e testada em dois espaços reais com características muito distintas, um espaço industrial e um edifício de escritórios. As experiências nestes dois espaços avaliaram os diferentes aspetos da solução e consideraram cenários onde apenas é possível utilizar dados Wi-Fi, e cenários onde os dados Wi-Fi podem ser combinados com dados de outros sensores. Os resultados sugerem que a solução proposta tem potencial para fornecer informação relativa à interferência em redes sem fios assim como posicionamento em diferentes ambientes indoor, com aplicações desde do posicionamento em edifícios comuns à navegação de veículos autónomos em ambientes industriais, podendo também ser possível a extensão da solução para ambientes exteriores utilizando dados das redes celulares, em especial considerando as características das novas redes 5G.