Desenvolvimento e Avaliac¸a˜ o de um Servic¸o de Posicionamento Baseado em IEEE 802.11 ∗ Fernando Ney Nascimento, Vagner Sacramento, Gustavo Baptista, Hana Rubinsztejn e Markus Endler 1
Departamento de Inform´atica, PUC-Rio R. Marquˆes de S˜ao Vicente 225 22453-900, Rio de Janeiro, Brazil
{ney,vagner,gustavo,hana}@lac.inf.puc-rio.br,
[email protected]
Abstract. In this paper, we present the features and the architecture of a location service, called Location Inference Service (LIS), which infers the approximate location of mobile devices, measuring the radio-frequency signal strength obtained from Access Points of IEEE 802.11 wireless networks. Resumo. Neste trabalho, apresentamos as caracter´ısticas e a arquitetura de um servic¸o de localizac¸a˜ o, chamado Location Inference Service (LIS), que infere a localizac¸a˜ o aproximada de dispositivos m´oveis, medindo a intensidade de sinais de r´adio-freq¨ueˆ ncia obtidos de Access Points de redes sem-fio IEEE 802.11.
1. Introduc¸a˜ o Apesar do aumento da demanda por servic¸os e aplicac¸o˜ es LBS (Location Based Services), tais como guias tur´ısticos ub´ıquos e servic¸os de emergˆencia, o desenvolvimento de tais servic¸os ainda e´ uma tarefa complexa, tanto conceitualmente como tecnicamente. Parte desta complexidade decorre do fato de que o processamento da informac¸a˜ o de localizac¸a˜ o e´ na maioria das vezes responsabilidade da aplicac¸a˜ o. Como um meio de resolver este problema, parece existir uma clara tendˆencia a` separac¸a˜ o de tarefas, i.e. que a inferˆencia e o processamento da localizac¸a˜ o tornem-se transparentes ao desenvolvedor da aplicac¸a˜ o, sendo estas tarefas tratadas dentro de uma camada de middleware [Schiller and Voisard 2004]. Neste artigo, descrevemos o Location Inference Service (LIS), um servic¸o de localizac¸a˜ o para dispositivos m´oveis baseado na intensidade de sinais de r´adio-freq¨ueˆ ncia (RSSI - Received Sinal Strength Indicator) em redes IEEE 802.11, que foi desenvolvido como parte de nossa arquitetura de middleware para provisionamento de informac¸o˜ es de contexto para aplicac¸o˜ es m´oveis, chamada Mobile Collaboration Architecture (MoCA) [Sacramento et al. 2004]. As principais caracter´ısticas do LIS incluem: uma API para acesso s´ıncrono e ass´ıncrono; detecc¸a˜ o da localizac¸a˜ o em termos de localizac¸o˜ es/regi˜oes simb´olicas ao inv´es de coordenadas; consultas espec´ıficas por regi˜ao (i.e. todos os dispositivos encontrados em uma determinada regi˜ao simb´olica); definic¸a˜ o de topologias hier´arquicas de localizac¸o˜ es e a inferˆencia da localizac¸a˜ o de dispositivos em diferentes ∗
Trabalho parcialmente financiado pelos projetos CNPq 55.2068/02-2(ESSMA) e 479824/04-5(Ed. Universal).
granularidades (i.e. diferentes n´ıveis da hierarquia); arquitetura modular que facilita a implementac¸a˜ o e experimentac¸a˜ o com diferentes algoritmos de inferˆencia; e parˆametros bem definidos utilizados para o ajuste dos algoritmos em termos de precis˜ao e tempo de resposta.
2. Location Inference Service O Location Inference Service (LIS) e´ respons´avel por inferir e disponibilizar a localizac¸a˜ o simb´olica de dispositivos m´oveis em a´ reas cobertas por Access Points (APs) de redes IEEE 802.11. Para isso, utiliza a intensidade de sinais, coletados pelo servic¸o de contexto da MoCA, de todos os dispositivos m´oveis. Basicamente, a id´eia e´ comparar o vetor corrente de RSSI (onde cada elemento do vetor corresponde ao sinal de um AP “aud´ıvel” ao dispositivo) com o vetor medido anteriormente em pontos pr´e-definidos em um pr´edio ou ambiente externo. Portanto, em uma primeira etapa (fase de calibrac¸a˜ o) amostras de vetores RSSI s˜ao coletadas em pontos de referˆencia bem definidos na(s) a´ rea(s) de interesse, e armazenadas no banco de dados do LIS. Durante esta calibrac¸a˜ o, em cada ponto de referˆencia, amostras de vetores RSSI s˜ao coletadas com o dispositivo voltado para v´arias direc¸o˜ es. Considerando que sinais de r´adio s˜ao suscet´ıveis a intensa variac¸a˜ o e interferˆencia, a precis˜ao da inferˆencia da localizac¸a˜ o depende fortemente do n´umero de APs, do n´umero de pontos de referˆencia escolhidos e do n´umero de vetores RSSI coletados. Ap´os a fase de calibrac¸a˜ o, o LIS e´ capaz de realizar a inferˆencia da localizac¸a˜ o de um dispositivo. Isto e´ feito atrav´es da comparac¸a˜ o (estimativa da “distˆancia” entre) o vetor RSSI corrente do dispositivo e os vetores RSSI coletados nos pontos de referˆencia na a´ rea de interesse. Para o c´alculo da inferˆencia, dois algoritmos distintos foram implementados, um determin´ıstico (MNN [Bahl et al. 2002]) e outro probabil´ıstico (Histogram [Youssef and Agrawala 2005]). 2.1. Regi˜oes Simb´olicas Ao inv´es de coordenadas f´ısicas (e.g. latitude/longitude), v´arias aplicac¸o˜ es sens´ıveis a` localizac¸a˜ o necessitam apenas saber a localizac¸a˜ o simb´olica de usu´arios e dispositivos. A noc¸a˜ o de uma localizac¸a˜ o simb´olica (ou semˆantica) n˜ao e´ nova [Roth 2003], mas cada autor utiliza uma definic¸a˜ o levemente diferente. Em nosso trabalho, definimos regi˜ao simb´olica como qualquer a´ rea geogr´afica com semˆantica ou identificac¸a˜ o bem definida, tal como uma sala espec´ıfica, corredor, andar de um pr´edio, rua, distrito, etc. Outro requisito comum de aplicac¸o˜ es baseadas em localizac¸o˜ es simb´olicas e´ a capacidade de se obter informac¸o˜ es de localizac¸a˜ o em diferentes n´ıveis de granularidade. Para isso, implementamos um modelo hier´arquico de localizac¸o˜ es, semelhante aos encontrados em outros trabalhos [Ranganathan et al. 2004, Roth 2003]. Por exemplo, dada a hierarquia “PUC-Rio/Pr´edio RDC/5o Andar/Sala 501”, o LIS pode inferir que um dado dispositivo se encontra no “Pr´edio RDC” caso a localizac¸a˜ o corrente desse dispositivo seja “Sala 501”. O LIS oferece uma interface onde cada aplicac¸a˜ o pode criar e gerenciar sua pr´opria topologia de regi˜oes simb´olicas, baseada nas regi˜oes atˆomicas definidas pelo administrador do servic¸o.
2.2. Arquitetura do LIS A arquitetura do LIS, ilustrada na Figura 1, foi projetada para ser flex´ıvel em relac¸a˜ o a integrac¸a˜ o com servic¸os de provisionamento de contexto e extens´ıvel em relac¸a˜ o a` implementac¸a˜ o de novos algoritmos de inferˆencia. Entretanto, um requisito essencial para que o LIS possa ser integrado a outros middlewares de provis˜ao de contexto, al´em da MoCA, e´ que esses disponibilizem informac¸o˜ es de RSSI dos APs no raio de cobertura dos dispositivos. A1 A3
CIS Client API
Data Repository
Location Inference Engine
A2
A4
Scan Cache
A5 C1
Symbolic Region Manager
Location Cache Manager B2
B2
Event Manager
C2
B4
Controller B3,C3
B1
Figura 1. Principais componentes da arquitetura do LIS˙
Como mencionado anteriormente, o LIS provˆe interfaces para modos de comunicac¸a˜ o s´ıncrono e ass´ıncrono. No modo s´ıncrono, os clientes podem realizar requisic¸o˜ es atrav´es de um protocolo simples da forma request/reply. No modo ass´ıncrono os clientes se subscrevem no LIS para receber eventos ass´ıncronos relativos a mudanc¸as na localizac¸a˜ o de dispositivos. Nos dois modos de acesso, consultas (ou subscric¸o˜ es) podem se referir a um dispositivo (e.g. recuperar a localizac¸a˜ o do dispositivo) ou a uma regi˜ao (e.g. recuperar a localizac¸a˜ o de um conjunto de dispositivos dentro de uma regi˜ao). De fato, o acesso espec´ıfico por regi˜oes provou ser bastante u´ til para diversas aplicac¸o˜ es sens´ıveis a` localizac¸a˜ o. De fato, o LIS foi projetado de uma forma modular, com fraco acoplamento e separac¸a˜ o clara de responsabilidades entre seus componentes, tais como a entrada de dados RSSI, inferˆencia, gerenciamento de regi˜oes e comunicac¸a˜ o. Para melhorar a confiabilidade1 da inferˆencia o LIS guarda os u´ ltimos n vetores RSSI recebidos de cada dispositivo m´ovel (scans de inferˆencia). Ao inv´es de utilizar apenas o vetor RSSI mais recentemente recebido de cada AP, o LIS utiliza o hist´orico de vetores com o objetivo de reduzir o erro induzido pelas variac¸o˜ es de RSSI. Para acomodar diversos algoritmos o LIS define uma interface gen´erica que pode ser implementada de acordo com um dado algoritmo. Assim, qualquer algoritmo de localizac¸a˜ o baseado em RSSI pode ser facilmente inclu´ıdo no LIS implementando sua interface gen´erica. Avaliamos o LIS com o objetivo de ressaltar diversas quest˜oes que possuem influˆencia direta em sua usabilidade: a precis˜ao da inferˆencia, a eficiˆencia, escalabilidade 1
Confiabilidade neste caso significa a probabilidade de se inferir a localizac¸a˜ o correta de um dispositivo que est´a im´ovel por ao menos um certo per´ıodo de tempo
e robustez do servic¸o. Atrav´es dos testes, podemos concluir que a fase de calibrac¸a˜ o e´ extremamente importante para a precis˜ao dos algoritmos. Al´em disso, quanto maior for o n´umero de scans nesta fase, melhor ser´a a inferˆencia da localizac¸a˜ o. Os testes tamb´em demonstraram que o algoritmo Histogram e´ definitivamente mais robusto que o MNN. Para uma descric¸a˜ o completa sobre o LIS e os testes realizados veja [Nascimento 2005].
3. Conclus˜oes Neste trabalho, realizamos o projeto, implementac¸a˜ o e avaliac¸a˜ o de um servic¸o para localizac¸a˜ o de dispositivos m´oveis utilizando redes sem-fio 802.11. Implementamos v´arias aplicac¸o˜ es baseadas em localizac¸a˜ o para testar a efic´acia e usabilidade do servic¸o. Maiores informac¸o˜ es sobre os prot´otipos dessas aplicac¸o˜ es est˜ao dispon´ıveis em http://www.lac.inf.puc-rio.br/moca/applications.html
Experimentos confirmaram que a inferˆencia de localizac¸a˜ o baseada em RSSI em redes 802.11 e´ uma soluc¸a˜ o vi´avel para ambientes internos e externos, oferecendo precis˜ao satisfat´oria (i.e. < 4 metros de erro) para um grande conjunto de aplicac¸o˜ es sens´ıveis a localizac¸a˜ o. Tamb´em conclu´ımos que algoritmos probabil´ıstico provaram ser mais confi´aveis que os determin´ısticos, i.e. foi menos afetado pelas normais variac¸o˜ es da intensidade do sinal em redes 802.11 determinadas por interferˆencias e reflex˜oes [Hashemi 1993]. Entretanto, confiabilidade ainda e´ um problema, e futuros trabalhos necessitam ser realizados para o desenvolvimento de filtros de sinais, ou outros m´etodos para a atenuac¸a˜ o de erros [Youssef and Agrawala 2005].
Referˆencias Bahl, P., Balachandran, A., Miu, A., Russell, W., Voelker, G. M., and Wang, Y.-M. (2002). PAWNs: Satisfying the Need for Secure Ubiquitous Connectivity and Location Services. IEEE Wireless Communications Magazine, Special Issue on Future Wireless Applications, pages 40–48. Hashemi, H. (1993). The indoor radio propagation channel. Proceedings of the IEEE, 81(7):943–968. Nascimento, F. N. C. (2005). Um servic¸o para inferˆencia de localizac¸a˜ o de dispositivos m´oveis baseado em redes IEEE 802.11. Dissertac¸a˜ o de mestrado, PUC-Rio. Ranganathan, A., J.Al-Muhtadi, Chetan, S., Campbell, R., and Mikunas, D. (2004). MiddleWhere: A Middleware for Location Awareness. In Jacobsen, H., editor, Proc. of the International Middleware Conference, Toronto, volume 3231 of LNCS, pages 397– 416. Roth, J. (2003). Flexible positioning for location-based services. IADIS International Journal of WWW/Internet, I(2):18–32. Sacramento, V., Endler, M., Rubinsztejn, H. K., Lima, L. S., Goncalves, K., Nascimento, F. N., and Bueno, G. A. (2004). Moca: A middleware for developing collaborative applications for mobile users. IEEE Distributed Systems Online, 5(10):2. Schiller, J. and Voisard, A. (2004). Location-Based Services. Morgan Kaufmann. Youssef, M. and Agrawala, A. (2005). The horus wlan location determination system. In MobiSys 2005: Proceedings of the Third International Conference on Mobile Systems, Applications, and Services.
