Sistemas de localización geográfica en entornos de interior basados en tecnologías de comunicación inalámbricas

Antonio Jesús Ruiz Ruiz

[email protected]

Director: Óscar Cánovas Reverte

MEMORIA TESIS DE MÁSTER

Master en “Tecnologías de la Información y Telemática Avanzadas” − Curso 2008/09 Dpto. Ingeniería de la Información y las Comunicaciones Dpto. Ingeniería y Tecnología de Computadores Facultad de Informática. Universidad de Murcia. Campus de Espinardo. 30100 Murcia. Spain.

ÍNDICE Resumen........................................................................................................................................ 3 1. Introducción .............................................................................................................................. 3 2. Estado del arte ........................................................................................................................... 5 2.1 Sistemas de navegación por satélite (GPS y Galileo) ........................................................ 5 2.1.1 Introducción ................................................................................................................. 5 2.1.2 Aplicación a sistemas de localización. ......................................................................... 6 2.2 IEEE 802.11 ........................................................................................................................ 7 2.2.1 Introducción ................................................................................................................. 7 2.2.2 Aplicación a sistemas de localización .......................................................................... 9 2.2.3 Problemas en la propagación de señales ...................................................................... 9 2.2.4 Calculo de la localización .......................................................................................... 10 2.2.4.1 Mapas de huellas de radiación............................................................................. 10 2.2.4.2 Modelos de propagación de señales .................................................................... 11 2.2.4.3 Modelos bayesianos ............................................................................................ 11 2.3 RFID.................................................................................................................................. 12 2.3.1 Introducción ............................................................................................................... 12 2.3.2 Aplicación a sistemas de localización ........................................................................ 13 2.4 ZigBee ............................................................................................................................... 13 2.4.1 Introducción ............................................................................................................... 13 2.4.2 Aplicación a los sistemas de localización .................................................................. 14 2.5 Conclusiones ..................................................................................................................... 15 3. Diseño ..................................................................................................................................... 15 3.1 Escenario ........................................................................................................................... 16 3.2 Arquitectura del sistema.................................................................................................... 17 3.3 Técnicas aplicadas para localización................................................................................. 20 3.3.1 Punto de control más cercano, con cuatro orientaciones:........................................... 20 3.3.2 Punto de control más cercano, con una orientación: .................................................. 21 3.3.3 K-vecinos más cercanos (1 orientación): ................................................................... 22 3.4 Pruebas reales.................................................................................................................... 23 4. Conclusiones ........................................................................................................................... 23 5. Bibliografía ............................................................................................................................. 25

2

Resumen En esta tesis de máster se ha llevado a cabo un estudio sobre la situación actual de los sistemas de localización para entornos de interior basados en comunicaciones inalámbricas. Su desarrollo se ha llevado a cabo en respuesta a las necesidades que hoy en día existen de creación de nuevas aplicaciones que sean capaces de determinar la posición de un objeto móvil en el interior de un edificio. La utilidad de estas aplicaciones puede ser muy amplia a la vez que puede resultar de vital importancia en ciertas situaciones de emergencia. Sistemas de localización ya desarrollados como GPS han tenido una aplicación y relevancia muy importante en la sociedad ya que ha permitido diseñar aplicaciones capaces de localizar dispositivos a lo largo de todo el mundo, llegando incluso a ser utilizado en sistemas de emergencias que han servido para salvar muchas vidas. Si bien este es un sistema diseñado para exteriores, su utilización ha servido para demostrar la importancia de los sistemas de localización. El desarrollo de sistemas similares pueden ser de especial utilidad en el interior de edificios como museos, hospitales, centros comerciales, aeropuertos, etc., donde tener localizado un aparato o a una persona puede ser muy importante en determinadas circunstancias, además de poder ofrecer servicios de valor añadido que hagan uso de la localización. Se va a realizar un análisis de las distintas tecnologías que se han aplicado en la creación de sistemas de localización para interiores durante los últimos años. Este análisis nos permitirá tener una visión más clara de cuáles son los recursos con los que hoy en día contamos y cuáles son las ventajas e inconvenientes que cada uno de ellos tiene a la hora de ser aplicados en estos entornos. Entre las tecnologías que se verán están aquellas basadas en satélites, las basadas en el estándar IEEE 802.11, las redes de sensores y las basadas en RFID. Cada una de ellas tiene cualidades que las hace interesantes para ser aplicadas en ciertos aspectos del funcionamiento de un sistema de localización. Finalmente mostraremos el diseño de un sistema de localización que se ha desarrollado. No se trata de un sistema de localización completo, sino de un prototipo que nos va a ayudar a sentar las bases necesarias para el posterior desarrollo de un sistema de localización que realmente muestre mejoras con respecto a los que ya han sido propuestos. Palabras clave: 802.11, sistema de localización, RFID, sensor, GPS, señal radio frecuencia

1. Introducción Durante los últimos años se han experimentado importantes avances en el desarrollo de tecnologías que permiten nuevas formas de comunicación, sobre todo en el medio inalámbrico, como son las tecnologías definidas por los estándares IEEE 802.11[1] (Wifi), IEEE 802.16 [3] (Wimax), Bluetooth [8], etc. Al mismo tiempo, también se han llevado a cabo trabajos que han permitido mejorar el rendimiento de los dispositivos de una forma espectacular, aumentando su capacidad de cómputo y los servicios que estos son capaces de ofrecer. Todo ello unido a la mejora en el consumo energético y al incremento del rendimiento de las baterías, ha hecho que los dispositivos móviles como ordenadores portátiles, PDAs o teléfonos móviles, estén cada vez más presentes en nuestra vida cotidiana y sean utilizados para una mayor cantidad de propósitos. De forma natural, la utilización de nuevas tecnologías y la mejora de capacidades por parte de los dispositivos llevan a la aparición de nuevas necesidades por parte de los usuarios. A lo largo

3

de esta tesis de máster nos vamos a centrar en el estudio de una de estas nuevas necesidades como son los sistemas de localización y seguimiento para interiores. En el entorno inalámbrico muchas de las aplicaciones que se pueden desarrollar para cubrir estas nuevas necesidades, o que ya se han desarrollado, requieren el uso de capacidades de localización y seguimiento. Por ejemplo, desde el servicio de emergencias 112 se hace uso de una aplicación que permite localizar a cualquier usuario que haya realizado una llamada y que se encuentre en una situación de emergencia. También en otros entornos, como pueden ser los museos, estos sistemas de localización pueden ser especialmente útiles para el desarrollo de aplicaciones de video-audio guías para los clientes del museo, de forma que en cada momento se les ofrezca información sobre las obras de arte que, por su posición, estén más cercanas. Otra situación en la que tener controlados los recursos puede ser importante es en el caso de los hospitales, ya que es importante saber donde se encuentra un médico en un momento de extrema urgencia o localizar algún aparato móvil que pueda ser necesario para realizar una prueba médica a algún paciente. Si nos paramos a pensar detenidamente, muchas son las posibles aplicaciones que puede tener un sistema de localización. En el caso de sistemas para exteriores, existe el conocido sistema GPS [4] que es capaz de situar un dispositivo en cualquier punto del planeta con una posibilidad de error no superior a unos pocos metros de distancia. Como veremos en las siguientes secciones, esta tecnología está muy limitada para llevar a cabo localizaciones en interiores de edificios debido a que las señales que emiten los satélites de posicionamiento, usadas por los dispositivos GPS para calcular su localización, no son capaces de traspasar los materiales con los que están construidos. Debido a ello nos tenemos que centrar en otras tecnologías que complementen a la anterior o que por sí solas, o mediante combinación de ellas, sean capaces de ofrecernos una buena precisión en localización en interiores. El principal objetivo de esta tesis de máster es realizar un estudio de la situación actual de los sistemas de localización y las diferentes propuestas que se han hecho a lo largo de los últimos años. Analizaremos dichas propuestas, observando las ventajas que cada una de ellas ofrece y también los inconvenientes con los que nos podemos encontrar. Veremos que se han realizado numerosos estudios sobre sistemas de localización basados en tecnologías de naturaleza muy distinta, desde redes inalámbricas basadas en IEEE 802.11, hasta sistemas basados en redes de sensores. Es necesario evaluar los trabajos realizados desde el punto de vista de las tecnologías que en cada uno de ellos se aplican, ya que de esta forma entenderemos mejor su funcionamiento y seremos capaces de sacar mejores conclusiones que nos puedan ayudar en el desarrollo futuro de sistemas de localización. En algunos de los casos estudiados, los sistemas desarrollados han sido capaces de obtener buenos resultados en cuanto a su precisión a la hora de estimar una posición dentro de un escenario de pruebas. Un problema que detectamos en muchos casos, es que se trata de soluciones demasiado específicas, es decir, encaminadas a solucionar el problema de la localización en un escenario concreto. Esto se produce porque en la mayoría de los casos los autores se centran en conseguir buenos resultados para su escenario de pruebas, dejando de lado el que ese escenario pueda sufrir algún cambio que provoque que todo el sistema desarrollado se vuelva inservible, o simplemente que el sistema no pueda ser utilizado en otro entorno. Para ello una vez que analizamos el estado del arte, se ha procedido al desarrollo de una primera versión de un sistema de localización. Como se verá en el apartado de diseño, en el que se describirá el trabajo práctico que hemos realizado, nuestra idea fue la de empezar a trabajar con las tecnologías que tenemos disponibles, redes 802.11 en este caso, desarrollando algoritmos basados en los ya propuestos en la literatura. Esto nos permitirá observar por nosotros mismos los problemas con los que nos podemos encontrar y, analizando los resultados obtenidos de las pruebas realizadas, sacar nuestras propias conclusiones. El trabajo futuro se concentrará en poder llevar a cabo el desarrollo de un potente, robusto y adaptable sistema de localización que 4

pueda ser usado como base para aplicaciones de alto nivel que necesiten hacer uso de las capacidades que ofrezca. No pretendemos en este documento ofrecer una solución perfecta al problema de la localización, ya que es algo que requiere un estudio mucho más profundo, lo que queremos es sentar una base y proponer una línea de investigación que desarrollar en una futura tesis doctoral, que ayude a mejorar la precisión de los sistemas de posicionamiento ya desarrollados y su adaptabilidad a diferentes escenarios disminuyendo el coste de esta, tanto en tiempo como en carga de trabajo.

2. Estado del arte Como en todo trabajo de investigación que se precie, en primer lugar se debe llevar a cabo un análisis exhaustivo de las distintas propuestas hechas sobre el campo de estudio en el que se va a trabajar. En este apartado vamos a mostrar un análisis de las principales tecnologías usadas en el diseño de sistemas de localización, señalando detalles interesantes de cada una de ellas y comentando algunos de los desarrollos reales estudiados que las han utilizado. Algunos de los sistemas desarrollados, de los que todo el mundo ha escuchado hablar o incluso ha utilizado como son los basados en satélites de posicionamiento, han demostrado ser de gran utilidad a campo abierto o en entornos urbanos no muy densos. Sin embargo, su precisión de algunas decenas de metros es insuficiente para algunos tipos de aplicaciones en las cuales se requiere un ajuste más fino de la posición geográfica. En los últimos años son varias las tecnologías base que están siendo utilizadas para intentar proporcionar, por un lado, una mayor precisión a la localización de personas u otros bienes de interés y, por otro lado, para extender los servicios de localización a entornos de interior donde propuestas como el GPS [4] o Galileo [5] no son capaces de proporcionar cobertura. Consecuentemente, nuestro primer objetivo ha sido centrarnos en el estudio de las distintas técnicas basadas en las tecnologías 802.11 [1], RFID [7] o Zigbee [6], que han sido propuestas por la comunidad científica hasta el momento, con el fin de identificar sus ventajas y sus limitaciones. Entre ellas encontramos varias tendencias distintas, como las basadas en modelos de propagación de la señal, huellas de radiación, modelos probabilísticos y de predicción de movimiento, por citar sólo algunas.

2.1 Sistemas de navegación por satélite (GPS y Galileo) 2.1.1 Introducción El sistema de navegación Galileo [5], que actualmente está en fase de desarrollo, está siendo creado por la Unión Europea en colaboración con la Agencia Espacial Europea. El objetivo de este proyecto es el de ofrecer un sistema de posicionamiento público, que sea capaz de localizar un dispositivo en todo el mundo, con un error de estimación de posición de unos pocos metros. Seguro que con las características comentadas nos viene a la mente otro proyecto muy similar, el GPS, con la peculiaridad de que en este caso, Galileo cuenta con su propia red de satélites distribuidos de forma distinta a como lo hace GPS, lo cual permitirá una mayor precisión en aquellas zonas de la Tierra más cercanas a los polos. Entre sus principales características podemos destacar que Galileo está pensado para ofrecer diferentes tipos de servicios: servicio abierto, para aplicaciones críticas, comercial, regulado o servicios de búsqueda y salvamento. Actualmente el proyecto está en fase de desarrollo debido a los continuos retrasos que ha

5

sufrido en cuanto a las fechas previstas para su publicación. Se espera la comercialización de sus primeros servicios para el año 2011. Por otro lado nos encontramos con la tecnología Global Positioning System (GPS) [4], ampliamente conocida, la cual fue desarrollada para maximizar la cobertura en sistemas de localización, ya que es capaz de abarcar toda la superficie terrestre. Hoy en día existen multitud de dispositivos dotados de este tipo de conexión. Además existen dispositivos externos que pueden ser añadidos para dotar de conexión GPS a aquellos que por defecto no cuentan con esta capacidad. El esquema básico de GPS provee una precisión de unos 10 metros de media, lo cual ha ido siendo refinado por los sucesivos avances que se han llevado a cabo en el desarrollo de algoritmos para el cálculo de la posición y en los dispositivos receptores. Para el funcionamiento de GPS se hace uso de una red de 27 satélites en órbita (24 operativos y 3 de respaldo), a unos 20.200 km de altura, con trayectorias sincronizadas para cubrir toda la superficie de la Tierra y que no interfieran unos con otros. A la hora de calcular una posición, el dispositivo utilizado para ello deberá tener visibles al menos tres satélites de los cuales recibirá señales indicando la posición del satélite y una marca de tiempo (reloj). La distancia al satélite se obtiene mediante el cálculo del retraso de las señales, para lo que es necesaria la sincronización del reloj del dispositivo GPS con base en la información contenida en las señales recibidas. Conocidas las distancias, se determina fácilmente la propia posición relativa respecto a los tres satélites. Conociendo además las coordenadas o posición de cada uno de ellos por la señal que emiten, se obtiene la posición absoluta o coordenadas (latitud, longitud y altitud) reales del punto de medición.

2.1.2 Aplicación a sistemas de localización. Un problema que nos encontramos al usar esta tecnología viene cuando se utiliza en zonas en las que por la gran densidad de edificios altos, como pueden ser las calles de grandes ciudades, no hay una buena disponibilidad por parte del dispositivo GPS para recibir las señales emitidas por el número suficiente de satélites que son necesarias para calcular su posición. El problema anterior surge debido a que las ondas emitidas por los satélites no son capaces de atravesar los materiales con los que están construidos los edificios o sufren importantes desviaciones que perjudican la buena recepción de las mismas. Este inconveniente implica que en el interior de los edificios no puede ser usada esta tecnología, y por tanto no es de gran ayuda ya que no nos sirve para calcular la posición de objetos o personas, las cuales se pasan la mayor parte de su tiempo en el interior de edificios, ya sea en su oficina de trabajo durante su jornada laboral o en el interior de su hogar en sus momentos de tiempo libre. GPS fue concebida y se ha aplicado de forma satisfactoria en entornos de navegación, turismo y en la búsqueda y rescate de personas desaparecidas o en peligro, pero como podemos observar son situaciones que se desarrollan en exteriores. En estos casos, la precisión que se requiere a la hora de obtener una localización concreta no es demasiado exigente. Con ello nos referimos a que una media de error de precisión de unos 5 ó 10 metros no supone un grave error, por ejemplo cuando se trata de localizar a un coche en una carretera. Sin embargo en situaciones en el interior de edificios, 10 metros de distancia puede implicar estar en varias estancias distintas, lo cual si puede ser perjudicial para la aplicación de nivel superior que esté haciendo uso del sistema de localización. Aún así ha habido investigadores que han sacado partido de estas técnicas basadas en satélites a la hora de poder aplicarlas para la realizar sistemas de localización para interiores como se puede ver en [19][20]. En estos casos se ha utilizado la tecnología GPS como apoyo a otras como WIFI o Bluetooth, en el sentido de que ha sido usado para generar mapas de posiciones absolutas en un punto de la tierra, en el que se refleja la potencia recibida de las señales de redes de distintas tecnologías. 6

El objetivo fundamental que se pretende alcanzar en [19] es el desarrollar un sistema de posicionamiento global tanto para interiores como para exteriores, en el que se puedan utilizar para calcular una posición todas las señales que un dispositivo reciba, sea cual sea su naturaleza (un dispositivo 802.11, bluetooth, una estación GSM, o un hasta incluso un sensor RFID). Tal y como se comenta en, para conseguir ese objetivo es necesario contar con una gran base de datos en la que tengamos almacenados puntos conocidos en los cuales somos capaces de localizar un dispositivo. Para ayudar en la recopilación de esta información se creó la comunidad ‘wardrinving’, cuyos integrantes sen encargan de recorrer aquellas zonas de interés, que se desea que formen parte del escenario de localización, equipados con un dispositivo GPS y otros dispositivos capaces de capturar señales de radio 802.11, GSM o bluetooth, para crear un mapa de recepción de señales. Cada traza ‘war-driving’ capturada contendrá una secuencia de valores formada por una huella de tiempo (que indicará cuando fue tomada esa traza), una posición (que vendrá dada por una latitud, longitud y altitud, capturadas por el dispositivo GPS) y una lista de fuentes de señales (Wifi, GSM, etc.) con las correspondientes potencias con las que cada señal es recibida en ese punto. Todas estas tramas son almacenadas en bases de datos disponibles al público, actualizadas periódicamente y pueden ser usadas, como lo han hecho en [19] para el cálculo de la posición de un dispositivo. Aunque realmente la información recopilada será usada por sistemas de localización basados en otras tecnologías, sin la utilización de GPS no podríamos formar un escenario global, debido a que habría muchos puntos en los que no se recibiría suficiente cantidad de señales de otra naturaleza como para poder calcular la posición en la que nos encontramos. El uso de que se hace de GPS en estos casos está pensado sobre todo para calcular posiciones de referencia aproximadas cuando el dispositivo inicia su aplicación de localización, de forma que sea capaz de situarse nada más comenzar su funcionamiento en una posición lo más cercana posible a su posición real. Además podemos utilizar este tipo de sistemas para estudiar el comportamiento de los usuarios, trayectos que suelen hacer diariamente, zonas que suelen visitar en su tiempo de ocio, etc. También es útil cuando el escenario interior que tenemos que controlar está formado por varios edificios, pudiendo decirnos cuando el usuario ha salido del edificio y ha entrado a otro, de forma que pueda servir de apoyo a los sistemas de posicionamiento que se estén usando en el interior de cada uno de los edificios. El hecho de apoyarnos en la tecnología GPS para la generación de mapas de cobertura tiene sus ventajas pero también sus inconvenientes. La principal ventaja que podemos encontrar es que es una tecnología tan extendida que mediante ella podríamos ser capaces de crear mapas de cobertura de prácticamente todo el mundo. Sin embargo, para nuestros propósitos, esta tecnología no puede ser utilizada más que como simple apoyo o en situaciones en las que no haya disponible ninguna otra tecnología, y pensemos que más vale saber algo aunque sea impreciso a no saber nada, debido a que por su naturaleza no es capaz de definir una posición con demasiada precisión y menos cuando se trata de localizar un dispositivo en el interior de un edificio.

2.2 IEEE 802.11 2.2.1 Introducción El estándar IEEE 802.11, comúnmente llamado Wifi, que define la tecnología de comunicación basada en ondas de radio frecuencia, es uno de los más utilizados para el desarrollo de sistemas de localización para interiores. El gran avance tecnológico de los últimos años nos permite ver 7

hoy en día dispositivos con conectividad Wifi y redes de esta naturaleza en prácticamente todos los lugares, ya sea en nuestros hogares, oficinas, centros comerciales, edificios oficiales e incluso algunas zonas exteriores. Esto supone una gran ventaja de cara a la integración de sistemas de localización basados en esta tecnología, ya que en la mayoría de los escenarios de implantación la infraestructura necesaria, puntos de acceso, está prácticamente a nuestra disposición, sin necesidad de tener que invertir grandes cantidades de dinero en su implantación. Aún teniendo que realizar la instalación de una red 802.11, se trata de una tecnología barata, ya que los dispositivos necesarios para montar una infraestructura de este tipo no tienen un precio de mercado elevado. Entrando un poco en detalle, vamos a comentar algunas características que resulta interesante saber a la hora de trabajar con esta tecnología. Para ello vamos a empezar describiendo a un nivel muy alto de abstracción como son las señales de comunicación WIFI y cómo podemos analizarlas para obtener información de ellas. El estándar IEEE 802.11 subdivide el espectro de radio en un conjunto de canales. El número de canales disponibles depende de donde se esté usando esta tecnología y la sub-especificación seleccionada de la misma. Así bien, en Estados Unidos según la sub-especificación 802.11b tan sólo hay disponibles 11 canales de radio, mientras que la misma sub-especificación en Europa consta de 13 canales. En contraste con eso, en el caso de 802.11a se cuenta con 12 canales de radio en Europa, pero en algunos otros países esta banda de frecuencia es aún utilizada para otros propósitos. En IEEE 802.11, la forma típica de realizar mediciones de potencia de señal es mediante escaneo [2] [25], activo o pasivo, de los puntos de acceso que hay disponibles en el rango de cobertura del dispositivo móvil. Un dispositivo móvil conectado a una red 802.11 va cambiando de canal periódicamente dentro de la frecuencia en la que está conectado a la red para detectar los posibles puntos de acceso que pueda haber a su alcance. Dependiendo de la carga que se esté haciendo es ese momento de la tarjeta de red, un cambio de canal puede implicar un coste de entre 5 y 19 milisegundos. En el escaneo activo, el dispositivo móvil, durante el tiempo que está conectado a un canal, enviará tramas que deberán ser respondidas por parte de los puntos de acceso alcanzables que operan también en ese canal. Las tramas enviadas a los puntos de acceso reciben el nombre de Probe Request, a las cuales los puntos de acceso responden con una trama Probe Response. Examinando las tramas Probe Response, un dispositivo móvil es capaz de identificar los puntos de acceso que tiene a su alrededor y de medir la fuerza de la señal que le llega de cada uno de ellos. Entre otra mucha información, estas tramas contienen el identificador de la red inalámbrica a la que pertenece el punto de acceso (ESSID – Extended Service Set IDentifier) y la potencia de recepción de la señal (RSSI – Received Signal Strength Identification). En el otro extremo tenemos el caso del escaneo Pasivo, el cual fue introducido con la idea de reducir la carga de trabajo por parte de los dispositivos móviles, lo que también conlleva a un ahorro de batería. En el escaneo Pasivo, durante el tiempo que el dispositivo móvil está conectado a un canal, permanece a la escucha de posibles tramas que puedan llegar. Si existe algún punto de acceso dentro de ese canal, éste enviará tramas que reciben el nombre de Beacon, las cuales serán examinadas por el dispositivo móvil y se podrá extraer la potencia de recepción de la señal con respecto a ese punto de acceso. Teniendo en cuenta que un punto de acceso envía una trama Beacon cada 100 milisegundos, un dispositivo móvil deberá permanecer al menos ese tiempo a la escucha en cada canal. En total, un escaneo pasivo completo de la red requerirá al menos 1,3 segundos para llevarse a cabo, tiempo que hay que tener en cuenta dependiendo de las restricciones o requisitos que tengamos.

8

2.2.2 Aplicación a sistemas de localización En los sistemas de localización para interiores basados en Wifi se pueden emplear diversos atributos físicos del medio para el cálculo de la posición. Las características típicas que pueden ser usadas son: la potencia de recepción de la señal (RSSI – Received Signal Strength Indication), el ángulo de llegada de la señal y el tiempo de llegada. Aunque sería deseable poder contar con todos estos datos, lo cierto que es la mayoría de los dispositivos comerciales de hoy en día no cuenta con los suficientes recursos como para poder medir todos ellos, teniéndonos que conformar con la medida de la potencia de la señal recibida. En 802.11 podemos hacer uso de distintas alternativas para medir la potencia de recepción de señales por parte de los dispositivos. Dependiendo del dispositivo que se vaya a utilizar para realizar dicha medida, de los recursos que ofrezca ese dispositivo y de los puntos de acceso que formen nuestra red, nos podemos encontrar con las siguientes alternativas: -

Obtener la información suministrada por el accounting de los puntos de acceso. La frecuencia de actualización de esta información depende de la frecuencia con la que en el punto de acceso se registren los datos accounting. Respecto a la precisión que se tiene con este método, sólo somos capaces de averiguar a qué punto de acceso se está conectado, por lo que el margen de error puede ser amplio, del orden de decenas de metros.

-

Obtener la relación de intensidades de potencia con las que escuchan los puntos de acceso a los dispositivos móviles. En estos casos y dependiendo del firmware que hubiera instalado en el punto de acceso, sería posible obtener la potencia de la señal mediante protocolos como SNMP. En función de la potencia de distintos puntos de acceso se podría afinar la precisión obtenida por estos sistemas.

-

Obtener la intensidad de las señales radio en los propios dispositivos. Esto es posible gracias a la funcionalidad ofrecida por el controlador de las tarjetas de red inalámbricas. La potencia de la señal se calcula a través del análisis de las tramas de beacon recibidas de los puntos de acceso. El tiempo de respuesta entre medición y medición de potencia de señal depende del controlador y del sistema operativo que se esté utilizando. Normalmente, dependiendo del modelo de las tarjetas de red y de las antenas utilizadas se obtendrán resultados de medición de potencia distintos para una misma posición, de ahí que haya que tomar medidas para solucionar ese problema, por ejemplo normalizando los valores recibidos mediante el establecimiento de un umbral máximo y mínimo de recepción para cada tipo de tarjeta.

2.2.3 Problemas en la propagación de señales Debido a la movilidad de los dispositivos y a la diversidad de elementos que nos podemos encontrar dentro de un edificio, se plantean ciertos problemas a la hora de estimar con precisión y certeza la potencia de recepción de una señal. Las potencias recibidas por los dispositivos móviles desde los puntos de acceso pueden variar debido a múltiples factores como son los materiales de construcción utilizados en el edificio, los objetos y personas que haya en su interior. Estos pueden hacer que la señal sea reflejada, absorbida, dispersada o difractada. En estos casos, que suelen ocurrir en la mayoría de los escenarios, la señal llega al receptor a través de varios caminos, lo que recibe el nombre de fenómeno de propagación multitrayectoria. Esto provoca que la señal llegue distorsionada al receptor y se obtengan diferentes medidas de 9

potencia para una misma señal por cada uno de los caminos que ha seguido. La solución a este problema es todo un reto entre los desarrolladores de sistemas de localización. En [9] [10], se discute sobre otro factor que afecta claramente a la hora de localizar un dispositivo en un escenario, es la orientación. Aunque no lo creamos, la orientación del dispositivo a localizar es importante debido a que en función de ello, las señales llegarán por caminos diferentes y por tanto la potencia de recepción variará de una posición a otra. En el caso de que un dispositivo sea transportado por un usuario, como puede ocurrir con una PDA o un ordenador portátil, la persona que lo lleva hace de obstáculo e impide la recepción correcta de la señal. Esto es así porque el agua influye sobre la propagación de las señales de RF, y si pensamos que el ser humano está compuesto en un 70% de agua, también afecta negativamente a la recepción de la señal. Esto provoca que en lugar de recibir la señal en el dispositivo de forma directa, lo tengamos que hacer mediante un camino alternativo, lo que conlleva a obtener potencias de recepción diferentes.

2.2.4 Calculo de la localización Una de las técnicas clásicas para el cálculo de la localización se basa en el uso de la triangulación, mediante la cual es posible calcular la posición de un dispositivo con relativa precisión. La triangulación se basa en la medición de la potencia de las señales recibidas por un dispositivo procedentes de los distintos puntos de acceso que tenga accesibles. Con esas potencias se puede calcular la distancia entre el dispositivo y el punto de acceso que emite la señal. Una vez obtenida esa distancia para todos los puntos de acceso visibles, se podrá estimar un punto del espacio de trabajo en el que se localizará el dispositivo. Para poder obtener esa posición dentro de un escenario es necesario saber la localización de los puntos de acceso. La utilización de triangulación de forma individual para el cálculo de la posición de un dispositivo, sólo podría ser aplicada con una cierta garantía de éxito en aquellos escenarios en los que no existan demasiados elementos que puedan interferir en la transmisión de las señales, de forma que se cumpla en todo momento un mismo patrón de flujo de señal que nos permita calcular distancias en función de la potencia de recepción en los dispositivos. Por desgracia no nos vamos a encontrar con esta situación tan trivial, sino que normalmente trabajaremos sobre escenarios en los que por su construcción, las ondas no se transmitirán de igual manera a lo largo de toda su superficie. Además habrá elementos dinámicos como pueden ser las personas que haya trabajando en su interior, que se mueven de una dependencia del edificio a otra, que mueven objetos de lugar u otras circunstancias que pueden suceder. Por tanto, tenemos que recurrir a otros métodos que nos permitan obtener la localización de un dispositivo de forma más precisa. Entre estos métodos podemos destacar los mapas de huellas de radiación, los modelos de propagación de señales o los modelos bayesianos.

2.2.4.1 Mapas de huellas de radiación Las técnicas basadas en mapas de huellas de radiación, véase [9] [10] [23], se basan, como su propio nombre indica, en la creación de mapas de los escenarios en los que se va a utilizar el sistema de localización. Estos mapas están compuestos por una serie de huellas de radiación que indican la potencia de las señales recibidas en un punto concreto del escenario. Será necesario establecer una serie de puntos a lo largo de todo el escenario en los que se llevará a cabo la medida de recepción de las señales. Por este motivo los sistemas de posicionamiento basados en esta tecnología suelen estar divididos en dos fases: -

Fase Offline: en la que esencialmente se construye el mapa de huellas de radiación de las señales emitidas por los puntos de acceso del escenario. Esta fase puede llevarse a cabo de forma manual (por un usuario del sistema), como ocurre en [9] [10] o de forma 10

automática (mediante técnica de autogeneración o self-mapping) [22]. Estás técnicas de autogeneración son muy útiles en escenarios que suelen cambiar de forma continua. -

Fase Online: en la cual el sistema está disponible para evaluar su funcionamiento mediante el cálculo de posiciones. Los dispositivos se pueden mover a lo largo del escenario y se puede comprobar la precisión que tiene nuestro sistema a la hora de localizar dichos dispositivos.

Estos sistemas se basan simplemente en una comparación entre las coordenadas obtenidas por un dispositivo durante la fase Online con las potencias almacenadas en una base de datos durante la fase Offline. En estos casos realmente no se realiza ningún cálculo de posición a partir de las señales recibidas, sino que se utiliza algún método de cálculo de distancias entre dos puntos, como puede ser la distancia euclídea o la distancia de Manhattan. Cada huella del mapa estará formada por un vector de coordenadas, que en este caso serán los valores de potencia de señal recibidos. Este vector será comparado con los almacenados en la base de datos y aquella posición almacenada cuyos valores de potencia de señal sean los más cercanos a los tomados actualmente, se entenderá que es la posición en la que actualmente se encuentra el dispositivo. Como se puede intuir, la precisión de estos sistemas sería mejor cuantos más puntos de referencia se tengan en el mapa de huellas, aunque como se indica en [9], existe un momento a partir del cual el aumento del número de puntos de medición no implica una mejora significativa en los resultados que se puedan obtener.

2.2.4.2 Modelos de propagación de señales En las técnicas basadas en la propagación de señales, se intenta obtener una ecuación que sea capaz de simular el comportamiento real de las señales cuando estas se propagan por el interior de edificios. Se tienen en cuenta factores como la atenuación de la señal conforme la distancia se hace más grande o el número de paredes que tienen que atravesar para llegar hasta el receptor. De esta forma, se puede calcular la distancia existente entre un dispositivo y los puntos de acceso que tiene visibles. Sabiendo la posición de los puntos de acceso, seriamos capaces de localizar un dispositivo en el escenario. Estas técnicas basadas en modelos de propagación de señal son, por lo general, peores a los métodos basados en huellas de radiación, en cuanto a la precisión obtenida a la hora de calcular una posición en un mapa. Sin embargo, ofrecen ventajas importantes a la hora de la adaptación del sistema de localización a diferentes escenarios, ya que evita tener que llevar a cabo la fase Offline de medición de potencias para crear el mapa de huellas del escenario, lo que supone un ahorro importante tanto el tiempo como en esfuerzo. En [9] se hace uso de modelos de propagación de señales, obteniendo resultados ligeramente peores a los obtenidos mediante huellas.

2.2.4.3 Modelos bayesianos Por últimos vamos a comentar los modelos bayesianos, los cuales, aplicados a los sistemas de localización proporcionan un potente marco probabilístico general para estimar la posición de un dispositivo móvil en un escenario a partir de la observación de las señales recibidas de los puntos de acceso alcanzables y las acciones realizadas anteriormente. De esta forma se pueden obtener los desplazamientos realizados por el dispositivo y, por tanto, la trayectoria seguida. Un buen ejemplo de aplicación de este tipo de técnica de cálculo de posicionamiento la podemos encontrar en [11]. El sistema de localización descrito en este documento llega a obtener resultados muy buenos, en torno a 1,5 metros de error teniendo en cuenta el 80% de las 11

pruebas realizadas y llegando a obtener una precisión de tan solo 1 metro de error considerando el 50% de las pruebas realizadas.

2.3 RFID 2.3.1 Introducción Otra de las tecnologías que ha sido ampliamente utilizada en los sistemas de localización es RFID (Radio Frecuency Identification). Como su nombre indica, en estos sistemas la comunicación entre sus componentes se realiza haciendo uso de señales de radio frecuencia, sin necesidad de existir visión directa entre emisor y receptor. La arquitectura de un sistema RFID esta formada principalmente por dos tipos de componentes, lectores y etiquetas (tags). Las etiquetas RFID son dispositivos pequeños, similares a una pegatina, que están formadas principalmente por una antena y chip, además de otros componentes. El propósito de la antena es permitir al chip, el cual contiene la información, transmitir la información de identificación de la etiqueta. El chip posee una memoria interna con una capacidad que depende del modelo y varía de una decena a millares de bytes. En el mercado nos podemos encontrar con dos tipos básicos de etiquetas, las pasivas y las activas, aunque se han desarrollado otras que mezclan las características más ventajosas de ambas. En primer lugar vamos a describir las etiquetas RFID pasivas, las cuales carecen de ningún tipo de batería y como su nombre indica están a la espera de que ocurra algún evento que las haga actuar. Su funcionamiento se basa simplemente en reflejar la señal transmitida por un lector RFID hacia él mismo, pudiendo modificar la señal reflejada mediante modulación de la misma. El tiempo de vida de este tipo de dispositivos es muy amplio, ya que no dependen de ninguna batería que se pueda agotar con el paso del tiempo. Sin embargo, hay que destacar que los rangos de lectura son muy limitados, alcanzando sólo unos pocos centímetros, teniendo que estar muy próximo el lector con el que se necesite interaccionar. Una ventaja muy importante es su bajísimo coste, de ahí que una de las principales aplicaciones que tienen este tipo de tags, es el sustituir a los códigos de barras de los productos. Por otro lado nos encontramos con las etiquetas RFID activas, que al contrario de las anteriores si que son capaces de transmitir datos y cuentan con una batería que determina su ciclo de vida. El hecho de contar con alimentación propia, permite que su rango de alcance sea mucho mayor que en el caso de las etiquetas pasivas. Además, su alcance puede ser mejorado mediante la instalación de antenas que amplifiquen su señal. Estos dispositivos suelen ser más usados para controlar el movimiento de productos o de otros aparatos. Los otros dispositivos importantes dentro de los sistemas RFID son los lectores, los cuales envían periódicamente señales para ver si hay alguna etiqueta en sus inmediaciones. Cuando capta una señal de una etiqueta (la cual contiene la información de identificación de esta), extrae la información y se la pasa al subsistema de procesamiento de datos, que le dará el tratamiento adecuado. Como ya se comentó al inicio de este apartado, los sistemas RFID han sido utilizados en muchos sistemas de localización, algunos de los cuales podemos encontrar en [12] [28]. Entre las características que estos sistemas tienen y que los hace interesantes para su utilización en aplicaciones de localización podemos destacar su capacidad para emitir señales de radio frecuencia desde posiciones conocidas, lo cual permite calcular la posición de un dispositivo que contenga un lector RFID. Esto es así debido a que cada etiqueta RFID tiene un identificador único, transmitido en la señal reflejada o enviada por la propia etiqueta, que hace que se pueda saber con exactitud de donde proviene la señal recibida. 12

2.3.2 Aplicación a sistemas de localización En el análisis del estado del arte que se ha realizado, se ha podido comprobar la gran aceptación que la tecnología RFID ha tenido a la hora de desarrollar sistemas de localización. Una de las principales causas de su extendida utilización es el hecho de que se trata de una tecnología muy barata en comparación con las anteriormente estudiadas. Además por sus características, es capaz de ofrecer una buena precisión a la hora de localizar un dispositivo en un escenario. Existen propuestas en las que la tecnología RFID es usada como apoyo a arquitecturas 802.11, por ejemplo, para la creación o adaptación de mapas de huellas de radiación en entornos dinámicos. La idea es utilizar una serie de etiquetas RFID para calcular de forma sencilla y rápida la posición de los puntos de acceso colocados en el escenario, y a partir de esto generar un mapa del mismo. En este caso se parte de que la posición de las etiquetas es conocida, por lo que es relativamente sencillo obtener la localización de los puntos de acceso con un gran nivel de precisión. Estos sistemas permiten que en cualquier momento se pueda reestructurar el mapa de forma dinámica cuando se interprete que el entorno ha cambiado y que se ha perdido precisión en el cálculo de la posición de dispositivos o usuarios. Esta tecnología puede ser usada, y se pueden obtener buenos resultados, en escenarios donde el número de dispositivos que se quieren controlar es muy grande y el tamaño de los mismos es pequeño, ya que mediante la instalación de muchas etiquetas se puede llegar a obtener una precisión bastante buena. Un ejemplo de este tipo de aplicación puede ser una audio-video guía de museos, en los cuales suele haber expuestos muchos objetos y a una distancia muy pequeña los unos de los otros. Otra aplicación propuesta, dentro de los sistemas de localización, es el uso de RFID para complementar a los sistemas de posicionamiento basados en satélites, en lugares en los que estos sistemas no ofrecen servicio, como pueden ser los túneles. Estos sistemas se basan en la colocación de etiquetas RFID enterradas bajo el pavimento (radiobalizas) o situadas en los laterales de la carretera, las cuales son leídas por una unidad que lleva el vehículo (OBU, onboard unit). Su principal ventaja en comparación con los sistemas basados en satélite es que las radiobalizas no necesitan de mapeado digital ya que proporcionan la información de su posición por sí mismas.

2.4 ZigBee 2.4.1 Introducción Dentro de las propuestas de sistemas de localización estudiadas, nos hemos encontrado con otro tipo de tecnologías muy usadas como son las redes de sensores. Un sensor es un dispositivo que es capaz de recibir información de su entorno (medir temperatura, humedad, etc.) y transmitirla bien a otros sensores o a un dispositivo central que se encargue de almacenar dicha información y tratarla adecuadamente. Por lo general los sensores no suelen ser dispositivos con gran capacidad de almacenamiento, a causa de las limitaciones que tienen en cuanto a consumo energético. Debido a las limitaciones de batería que suelen tener, los sensores tampoco suelen emitir de forma continua señales. Por ello utilizan algoritmos de sincronización que les permitan enviar su información sin que esta pueda colisionar con la enviada por otro sensor, evitando así tener que realizar retransmisiones de datos que supongan un gasto energético adicional.

13

Este tipo de sistemas son útiles cuando no se dispone de ninguna infraestructura en el escenario sobre el que se quiere actuar. Con ello nos referimos a que, cuando no se cuenta con una red 802.11 ya desplegada, el menor coste que tienen las redes de sensores, las hace ideales para su implantación. Además, por su naturaleza, las redes de sensores pueden desplegarse haciendo uso de distintas topologías que permitan comunicar unos sensores con otros, y con un posible sistema central, de la forma más adecuada según las necesidades que se tenga. Una de las principales propuestas dentro de las redes de sensores es ZibBee, un estándar basado en el IEEE 802.15.4. Se trata de un conjunto de protocolos de alto nivel capaces de utilizar los recursos ofrecidos por las capas del nivel inferior, tanto física (PHY) como de control de acceso al medio (MAC), de las comunicaciones de radio frecuencia. Este estándar define su propio software y hardware, y está diseñado para soportar un diverso mercado de aplicaciones cuyos requisitos, tanto de coste como de consumo, son limitados. Está pensado para ser utilizado principalmente en entornos de domótica (la automatización de edificios y hogares), la atención sanitaria, control de alumbrado y control comercial, entre otros. ZigBee ha sido utilizado en propuestas como [21], como tecnología para el desarrollo de sistemas de localización o como apoyo a otras tecnologías [15]. Una de las principales características de las redes ZigBee en la que se basa esta propuesta es el concepto de calidad del enlace (LQI: Link Quality Indicador), que según el estándar IEEE 802.15.4 se define como: “una caracterización de la fuerza y/o cantidad del paquete recibido. La medida puede ser implementada usando una estimación de la potencia recibida, la señal a ruido o una combinación de ambos métodos”. Según [21], aunque teóricamente y en condiciones ideales se podrían alcanzar precisiones de alrededor de los 2,6 metros de error, el uso esta técnica puede lleva a alcanzar resultados aceptables, entorno a los 5 metros de error medio, a la hora de localizar una posición en un escenario real.

2.4.2 Aplicación a los sistemas de localización En el análisis que se ha realizado previo al desarrollo del presente documento, hemos podido constatar que son varias las propuestas que se han hecho, dentro del mundo de los sistemas de localización, en las que se ha hecho uso de redes de sensores. Las redes de sensores son especialmente útiles cuando el entorno en el que se quiere trabajar no cuenta con una infraestructura o red de otra naturaleza, por ejemplo Wifi, ya que su instalación no implica un gran desembolso de dinero. Hay propuestas que utilizan las redes de sensores como un recurso independiente para desarrollar un sistema de localización, véase [21]. En estos sistemas de localización, en los que la red de sensores es el único recurso para el cálculo de la posición de un determinado dispositivo, los autores juegan con la potencia de emisión de señales desde el dispositivo emisor, que es configurable, y con la potencia con la que se reciben esas señales en los dispositivos receptores. De forma idealizada, y según la ecuación de transmisión en espacio libre de Friss, a partir del conocimiento de estos dos datos, se puede obtener la distancia a la que está el receptor del emisor. Sin embargo, en los escenarios reales, la distribución que ofrece dicha fórmula no es aplicable, debido a que la propagación de la señal de radio interfiere con muchos elementos de nuestro alrededor, como pueden ser cristales, elementos metálicos, paredes de hormigón, agua, e incluso las personas humanas también pueden suponer un obstáculo a la hora de la transmisión de señales. En [21] se propone el algoritmo WCL (Weighted Centroid Location), que tiene en cuenta estos problemas que se pueden dar, y que debido a su baja complejidad, su velocidad de cálculo y sus requisitos mínimos en cuanto a recursos necesarios, lo hacen ideal para localización mediante redes de sensores.

14

2.5 Conclusiones Una vez que se ha llevado a cabo el análisis del estado del arte de los sistemas de localización y de las distintas tecnologías aplicables a ellos, vamos a comentar las conclusiones que hemos obtenido. Por un lado, hemos podido observar que los sistemas de localización basados en satélites, aunque obtienen buenos resultados en exteriores, no suponen una buena solución cuando se trata de entornos de interiores de edificios, debido a que se pierde la capacidad de recibir señales de los satélites y por lo tanto no se pueden realizar cálculos de posicionamiento. La tecnología que bajo nuestro punto de vista nos puede parecer más interesante es 802.11, debido a la multitud de opciones que ofrece y a su amplia implantación hoy en día tanto en edificios públicos como privados. Aunque hay propuestas que obtienen buenos resultados usando esta tecnología, todavía no se ha desarrollado un sistema capaz de adaptarse dinámicamente a entornos cambiantes. Por lo tanto, a pesar de las múltiples propuestas que se han hecho, creemos que todavía hay mucho que investigar en este campo. Finalmente hemos evaluado tanto la tecnología RFID como las redes de sensores, en especial las basadas en ZigBee. Los sistemas de localización estudiados que hacen uso de estas tecnologías, reflejan resultados aceptables en cuanto a precisión, el problema está en el gran número de dispositivos que tienen que ser usados para llegar a obtener una buena precisión en estos sistemas. Aunque por otro lado, estas tecnologías pueden ser el complemento perfecto a otras como puede ser la 802.11 de cara a crear sistemas dinámicos y aplicables a diferentes escenarios. Creemos que la tecnología 802.11 puede ser el punto de partida para establecer la base de un sistema de localización para interiores, sin descartar, el poder apoyarnos en otras para hacer que este sistema se más fiable y extensible. Por ello, en el siguiente apartado vamos a comentar el diseño que hemos realizado de un sistema de localización basado en esta tecnología. No se trata de un sistema completo, simplemente hemos dado los primeros pasos que nos ayudaron a definir una línea a seguir en el desarrollo de un sistema de localización que pueda surgir como fruto de una futura tesis doctoral.

3. Diseño En este punto vamos a describir cuales han sido nuestros primeros pasos en la construcción de un primer prototipo de sistema de localización. Éste nos va a permitir sacar nuestras propias conclusiones acerca del funcionamiento de estos sistemas en el interior de un edificio, así como sentar una base sobre la que poder seguir investigando de cara a obtener una solución más refinada, con mayor nivel de precisión y adaptable a situaciones cambiantes. La idea que perseguimos al inicio del proyecto fue la de crear un sistema de localización utilizando los recursos de los que se disponían. Por ello, la tecnología usada para desplegar nuestro sistema ha sido 802.11. Debe quedar claro que, con la elección de esta tecnología no estamos dando por supuesto que sea la más adecuada para el desarrollo de un sistema de este tipo, sino que simplemente es la base de la que partimos. Tal y como se ha explicado en el capítulo anterior, en el que se ha analizado distintas tecnologías aplicables a los sistemas de localización, cada una de ellas puede aportar ciertos beneficios y se pueden combinar para obtener mejoras tanto a nivel de precisión como a nivel de adaptabilidad del sistema. Vamos a continuar en este capítulo con una breve descripción del escenario elegido para implantar y posteriormente evaluar nuestro sistema de localización. Seguidamente se va a 15

explicar nuestra arquitectura, indicando cuáles son los principales componentes y sus funciones. Una vez vista la arquitectura, pasaremos a comentar los algoritmos implementados para llevar a cabo el cálculo de la localización y cuáles son los resultados obtenidos mediante su uso en simulaciones de localización. Finalmente se mostrarán los resultados de las pruebas reales que se han llevado a cabo en el escenario.

3.1 Escenario Nuestro escenario de pruebas ha sido la Facultad de Informática del campus universitario de Espinardo de la Universidad de Murcia, en concreto una parte de la tercera planta de dicho edificio, en la que se encuentra principalmente despachos de profesores y algún laboratorio de investigación, figura 1. Se instalaron cuatro puntos de acceso en distintas dependencias del escenario, cuya situación se puede ver la imagen indicada como puntos azules. Estos puntos de acceso se intentaron colocar de forma que en todo momento, un usuario que se mueva por el escenario sea capaz de recibir señal de al menos tres de ellos. Durante la fase offline, o de creación del mapa de huellas de radiación, se tomaron medidas de la potencia de recepción de señal de los cuatro puntos de acceso instalados (puntos amarillos), en distintos puntos del escenario. En total, se establecieron 78 posiciones de toma de muestras (puntos azules), distanciados unos de otros en 2’75 metros.

Figura 1. Escenario de pruebas

Como se señaló y argumentó en el estado del arte cuando se describió la tecnología 802.11, un aspecto importante que influye a la hora de localizar un dispositivo en un escenario es su orientación. Por ello, cuando creamos el mapa de huellas, se tomaron muestras con cuatro orientaciones. En cada punto y por cada orientación se tomaron 15 muestras, lo que hace un total de 4680 muestras para nuestro escenario. Cada una de las muestras estaba formada por un vector de cuatro elementos, uno por cada punto de acceso. Los valores almacenados no se correspondían con la potencia recibida medida en dBm, sino que dichas medidas son normalizadas, en porcentaje, a valores entre 0 y 100. Esta normalización, tal y como se explicará en su momento, se lleva a cabo para minimizar las posibles diferencias existentes entre las medidas tomadas por distintos dispositivos.

16

El escenario de pruebas cuenta con grandes cristaleras en los pasillos, indicadas con líneas rojas, y con un gran número de puertas (que abiertas o cerradas influyen en la transmisión de las señales) debido a la gran cantidad despachos que hay. Esto implica que se trata de un escenario delicado para poder probar nuestro sistema y por tanto hay que ser cauto a la hora de tomar muestras y de realizar las pruebas. Por todo ello las muestras fueron tomadas en tres días distintos en el mismo intervalo horario, para intentar que las condiciones del escenario fueran similares en todas y cada una de la muestras, de forma que los resultados de las pruebas que posteriormente se realizaran fueran fiables para poder sacar conclusiones de la precisión alcanzada por nuestra aplicación.

3.2 Arquitectura del sistema A la hora de diseñar la arquitectura de un sistema, primero hay que estudiar las posibles alternativas que puede haber, y cuáles son las ventajas que cada una ofrece. Al igual que ocurre con otros tipos de aplicaciones, en los sistemas de localización nos encontramos principalmente con dos topologías diferentes: -

Por un lado tenemos los modelos distribuidos, tal y como se definen en [9] [31], en el cual a cada dispositivo se le dota del software necesario para poder llevar a cabo dichos cálculos. Por ejemplo, en el caso de tratarse de un sistema basado en huellas, está claro que todos los dispositivos no van a tener replicado el mapa de huellas de radiación, debido al costo que puede llevar el realizar alguna actualización del mismo. Se podría realizar acceso remoto a dicho mapa de huellas pero el gasto en cuanto a consumo energético, en este caso, y de almacenamiento, en el caso anterior, que conllevaría sería muy elevado y en la mayoría de los casos estos recursos están muy limitados. Otro problema que este sistema puede acarrear es el hecho de que todos los dispositivos que quieran ser usados en el sistema deben ser compatibles con el software a usar. Además, el cálculo que es necesario realizar para obtener la localización implica también un consumo energético que en algunos casos puede no ser viable.

-

En el lado opuesto nos encontramos los modelos centralizados, en los cuales una aplicación instalada en un servidor central es la que se encarga de calcular la posición en tiempo real de todos y cada uno de los dispositivos que pertenezcan al sistema. En estos casos los dispositivos clientes no tienen que ejecutar ninguna aplicación en modo local, sino que son los propios puntos de acceso los encargados de medir la potencia con la que dichos dispositivos reciben las señales. El servidor central será el encargado de comunicarse con el punto de acceso o la base de datos, para recuperar dicha información y poder realizar los cálculos de posicionamiento. Una de las principales ventajas que tiene esta arquitectura es que se puede hacer uso de cualquier dispositivo con conectividad 802.11 para calcular su posición. Puede que la localización de un número muy grande de dispositivos llegue a saturar el servidor, pero siempre se podrá acudir a técnicas de balanceo de carga para evitar estas situaciones.

Con el objetivo de aprovechar las ventajas que una topología y otra nos ofrece, hemos realizado un diseño basado en una mezcla de ambas. Por un lado nuestro sistema de localización va a hacer uso de técnicas de recogida de datos basadas en la obtención de las potencias de recepción de señales en los propios dispositivos móviles. Sin embargo, para el cálculo de la posición de un dispositivo, se ha diseñado un modelo centralizado, encargado de recopilar la información facilitada por los clientes y de calcular la posición de cada uno de ellos. En la figura 2, se puede observar cuales son los componentes de nuestra arquitectura y la relación existente entre cada uno de ellos.

17

Figura 2. Arquitectura del sistema

•

Red 802.11: formada por 4 puntos de acceso Linksys WRT54G, que emiten de forma periódica tramas Beacon, mediante las cuales se anuncia a los distintos usuarios a su alcance la disponibilidad de una red Wifi. Estos puntos de acceso no está conectados unos con otros, ni de forma inalámbrica ni mediante red cableada, simplemente tienen configurado un mismo ESSID (Received Signal Strength Identification) para que los dispositivos clientes entiendan que todos estos puntos de acceso pertenecen a la misma red. Además de no estar conectados entre sí, estos puntos de acceso no ofrecen conectividad hacia Internet ni hacia la intranet de la propia Universidad, aunque se podría haber ofrecido esta capacidad. Para evitar problemas de cobertura, y haciendo uso de los recursos disponibles, el dispositivo cliente se conectará a otra red WIFI con acceso a la intranet de la universidad para poder comunicarse con el resto de elementos del sistema.

•

Aplicación dispositivo móvil (cliente): capaz de analizar las tramas beacon que llegan desde los puntos de acceso para calcular la potencia con la que dichas tramas son recibidas. Esta aplicación ha sido creada de forma que sea compatible para los sistemas operativos Windows y Windows Mobile. En la figura 3 se puede observar el esquema básico de funcionamiento de esta aplicación cliente. o

En primer lugar, la aplicación debe recuperar toda la información que la controladora de red inalámbrica recibe por parte de los puntos de acceso que tenemos a nuestro alcance. Esta información constará de un listado formado por los identificadores de las redes a las que pertenezcan dichos puntos de acceso (ESSID), junto con la dirección MAC (BSSID- Basic Service Set IDentifier) de cada uno de ellos y la potencia con la que se recibe la señal (RSSI).

o

Seguidamente, y como se especifica en la figura 3, en el paso 2 debemos realizar un filtrado de todos los datos que nos lleguen desde la controladora de red inalámbrica, debido a que esta nos devolverá información relativa a todos lo puntos de acceso visibles, y puede que no todos ellos pertenezcan a la red creada para nuestro sistema de localización. Por lo tanto, nos quedaremos con aquella información que se corresponda con los puntos de acceso cuyo ESSID sea de nuestro interés.

18

o

El tercer paso que se debe llevar a cabo es el de la normalización de las potencias con las que se reciben las señales desde los puntos de acceso. Un problema que vamos a encontrarnos es que, dependiendo del dispositivo con el que se realicen las medidas, y más concretamente, dependiendo de la tarjeta de red inalámbrica utilizada, van a existir diferencias importantes en los valores obtenidos para una misma posición. Esto se debe a que cada tarjeta de red, en conjunto con la antena que utilice, puede tener una ganancia distinta y por tanto las medidas realizadas no serán absolutas. Para solventar este problema se establecen unos umbrales mínimo y máximo que indican cual es la potencia máxima y mínima que puede llegar a recibir una tarjeta de red. A partir de estos umbrales se lleva a cabo una normalización de las medidas de potencia realizadas, lo que nos va a devolver valores absolutos de recepción de señal en porcentajes de 0 a 100.

o

El último paso realizado por nuestra aplicación cliente es la el de envío de los datos de potencias medias al repositorio a través de un servidor web. En esta fase, una vez que tenemos normalizadas las potencias recibidas de los puntos de acceso de nuestro interés, hacemos uso de uno de los servicios que nuestro servidor web pone a nuestra disposición. A través de este servicio, somos capaces de enviar los datos recopilados y almacenarlos en la base de datos, de donde serán recuperados para su posterior análisis.

Figura 3. Cliente de localización

•

Base de datos: en la que se almacenan tanto el mapa de huellas de radiación creado durante la fase offline, como los vectores de señales capturados por los clientes durante la fase online. Para la creación de este repositorio se ha hecho uso del gestor de bases de datos MySQL, por tratarse de un software de licencia libre y por cumplir con los requisitos de acceso que teníamos en nuestro sistema. Esta base de datos va a estar formada por dos tablas principales. Una de estas tablas va a guardar el mapa de huellas de radiación creado durante la fase Offline. En ella van a estar guardadas las potencias recibidas en un punto concreto del escenario junto con la 19

orientación en la que se capturó. La otra tabla almacenará las medidas de potencia que un usuario va enviando durante la fase Online. Esta tabla será consultada por la aplicación de control para obtener los datos de un usuario y, a partir de ellos calcular su posición. •

Servidor Web: ofrece servicios encargados de recibir los datos desde la aplicación cliente y de almacenarlos en la base de datos. También se encarga de ofrecer los servicios necesarios a la aplicación de control para que esta pueda consultar la base de datos. El servidor web has sido montado sobre la plataforma Apache Axis, y dentro del mismo se han insertado los servicios correspondientes implementados en Java. No vamos a entrar a definir detalladamente los servicios ofrecidos ya que se trata de simples implementaciones para gestionar la información de una base de datos remota.

•

Aplicación de control: cuya utilización sirve para monitorizar los cambios de posición de los clientes durante la fase de pruebas del sistema. En la figura 7 se puede observar un mapa, creado por la aplicación de control en el que se puede hacer seguimiento del recorrido hecho por un usuario en el escenario. Al tratarse de un primer prototipo, esta aplicación no ha sido desarrollada completamente, sólo se ha creado la funcionalidad básica necesaria para realizar las pruebas del sistema.

3.3 Técnicas aplicadas para localización. De los distintos tipos de técnicas que se vieron anteriormente como son las basadas en modelos de propagación o las basadas en mapas de huellas de radiación, nos hemos decantado por éstas últimas para la realización de algunas pruebas de funcionamiento de nuestro sistema. En concreto se han diseñado tres algoritmos distintos basados en áreas de cobertura (o puntos del mapa de huellas). Dos de ellos se basan en la búsqueda del punto de control más cercano, es decir, de encontrar el punto del mapa de huellas cuya información de recepción de potencia de señales más se asemeja con las medidas reales tomadas. El otro algoritmo se basa en encontrar un número k de puntos de control cuyas potencias más se parezcan a las medidas tomadas, y devolver como solución una posición equidistante a los k puntos seleccionados.

3.3.1 Punto de control más cercano, con cuatro orientaciones: En este algoritmo en primer lugar se obtiene la mediana de las muestras. Para un punto de control p y una orientación o, se obtiene un vector de 4 elementos (s1,s2,s3,s4) donde el valor de si es la mediana de las señales recibidas del punto de acceso APi. Nos quedamos con 312 vectores de 4 elementos (78 puntos y 4 orientaciones). Dada una muestra m = (s1,s2,s3,s4) se busca el punto de control más cercano los 312 que forman el mapa de huellas formado durante la fase offline (usando la distancia euclídea), obteniendo como resultado de localización las coordenadas del punto de control más cercano. Los resultados obtenidos en las pruebas llevadas a cabo mediante simulación se puede observar en la figura 4. En dicha figura cada unidad del eje de ordenadas equivale a una distancia de 2,75 metros, es decir, la distancia que hay entre dos puntos del mapa de huellas. Como se ha comentado, estás pruebas se han realizado mediante simulación, es decir, se seleccionaba un punto del mapa de muestras y el vector de potencias que había asignado a dicho punto se le pasaba al algoritmo para que nos dijera de qué punto se trataba. Tal y como se desprende del gráfico, aproximadamente el 50% de las ocasiones el algoritmo acertaba en la localización del punto del que se trataba. Aunque hay situaciones en las que el error cometido es bastante grande, por lo general el error medio está rondando los 2’75 metros de distancia, es decir, que 20

por término medio se equivoca en un punto de distancia con respecto a la posición real que se quería obtener. 16

14

12

10

8 Percentil 4-O 6

4

2

0

Percentil

Figura 4. Resultados punto control más cercano con 4 orientaciones

3.3.2 Punto de control más cercano, con una orientación: Al igual que el caso anterior, en primer lugar se obtiene la mediana de las muestras, es decir, para un punto de control p y una orientación o, se obtiene un vector de 4 elementos (s1,s2,s3,s4) donde el valor de si es la mediana de las señales recibidas del APi. Nos quedamos con 312 vectores de 4 elementos (78 puntos y 4 orientaciones) y a continuación elegimos la orientación donde la señal de los puntos de acceso es mayor. Para hacer esto nos basamos en que las señales más fuertes son más fiables de cara a poder localizar un dispositivo. Esta selección nos permite reducir el espacio de búsqueda a 78 puntos de control distintos, lo cual implica una mayor rapidez en obtener la repuesta, aunque teóricamente también deberíamos obtener peores resultados. El ejemplo sería, dada una muestra m = (s1,s2,s3,s4) se busca el punto de control más cercano de esos 70 del mapa de huellas reducido (usando la distancia euclídea), devolviendo como resultado de localización las coordenadas del punto de control más cercano. Se han realizado las mismas pruebas que en caso anterior, y como se puede observar en la figura 5, los resultados, aunque muy parecidos, son ligeramente peores a los anteriores, alrededor de un 40% de las ocasiones el error cometido es nulo, mientras que en otro 50% de las ocasiones el error está rondando los 3 metros. En aproximadamente un 10% de los casos, el error de estimación que se comete es de distancias considerables, por encima de los 5 metros. Estos resultados reafirman la teoría expuesta en [9] y comentada anteriormente, de que la orientación es importante a la hora de crear un sistema de localización.

21

14

12

10

8

Percentil 1-O 6

4

2

0

Percentil

Figura 5. Resultados punto control más cercano con 1 orientación

3.3.3 K-vecinos más cercanos (1 orientación): En este caso se ha utilizado una técnica de clasificación muy usada en entornos de inteligencia artificial. En la técnica de k-vecinos más cercanos, la localización se determina usando los k puntos de control con un peso inversamente proporcional a la distancia obtenida. En primer lugar se obtiene la mediana de las muestras, a continuación elegimos la orientación donde la señal de los puntos de acceso es mayor. Dada una muestra m = (s1,s2,s3,s4) se buscan los k puntos de control más cercanos (usando la distancia euclídea), y haciendo uso también de dicha distancia euclídea se calcula una posición en base a los k puntos seleccionados, ponderada por la distancia euclídea, la cual es devuelta como solución. De las pruebas realizadas se puede deducir que, aunque no se obtenga normalmente la posición exacta que se quiere localizar, el error medio cometido en todas las pruebas es menor que con los dos algoritmos anteriores. En la figura 6, que aparece a continuación, se puede ver una gráfica que expresa los resultados obtenidos de las pruebas realizadas. 14

12

10

8 Percentil K

6

4

2

0

Percentil

Figura 6. Resultados k-vecinos con 1 orientación

22

3.4 Pruebas reales Haciendo uso de las dos mejores técnicas que se han comentado, punto más cercano con cuatro orientaciones y k-vecinos, se han realizado pruebas reales sobre el escenario comentado. Dichas pruebas han consistido en el recorrido de un camino por parte de un usuario que transportaba consigo un ordenador portátil. En la figura 7, se puede observar el resultado obtenido por el método del punto más cercano haciendo uso de las cuatro orientaciones. En estas pruebas reales, los resultados no son tan buenos como en las simulaciones, debido a que el estado del escenario puede cambiar debido al movimiento de personas u objetos. Aún así, existen posiciones en las que el error cometido está rondando los 3 metros de distancia. Las situaciones en las que peor resultados se obtienen son aquellas que se corresponden con puntos cercanos a los ventanales de cristal situados en el pasillo (posiciones 1, 2, 13, 14, 15). En el caso de las pruebas reales realizadas haciendo uso de la técnica de k-vecinos, los resultados obtenidos son por término medio, como ya vaticinaban las simulaciones anteriores, mejores que en el caso de la técnica del punto más cercano. En la figura 8 podemos observar los resultados obtenidos en el escenario de pruebas.

Figura 7. Resultados prueba real punto más cercano 4 orientaciones

Figura 8. Resultados prueba real k-vecinos

4. Conclusiones A lo largo de esta tesis de máster, hemos podido comprobar que existe una amplia rama de investigación que está trabajando de forma continua para alcanzar el objetivo de diseñar un sistema de localización para interiores preciso, adaptable dinámicamente y al mismo tiempo intentando minimizar costes, tanto a nivel de implantación de infraestructura como a nivel de usuario.

23

Durante el periodo de investigación previo, se ha podido comprobar la diversidad de tecnologías aplicables a los sistemas de localización. En algunos casos hemos visto que se han obtenido muy buenos resultados gracias a la adecuación de la tecnología usada al entorno en el que se aplicaba, y en otros casos gracias a la aplicación de distintas tecnologías de forma conjunta, para llevar a cabo ciertas funcionalidades dentro el sistema de localización. Esta fase de estudio nos ha llevado a la conclusión de que no existe ninguna tecnología que se pueda calificar como la panacea del mundo de la localización para interiores, es decir, no existe ninguna tecnología (802.11, RFID, Bluetooth, ZigBee, etc.), que pueda ser aplicable con cierta garantía de precisión en cualquier escenario. Nuestro desarrollo basado en 802.11, no implica que tengamos la convicción de que esta tecnología vaya a ser la que alcance mejores resultados, ya que somos conscientes de que en otro escenario, con características distintas, los resultados podrían haber sido mejores usando otras tecnologías. Tal y como se comentó en su momento, el desarrollo de nuestro sistema ha estado influido por las características del escenario de aplicación. La elección de la tecnología usada se llevó a cabo con el fin de aprovechar los recursos de los que disponíamos, evitando así tener que hacer un desembolso de dinero tanto en la compra como instalación de dispositivos de otra naturaleza. No podemos decir que hayamos creado el sistema de localización más adecuado a nuestro entorno, pero es cierto, que hemos obtenidos buenos resultados conforme al tiempo de investigación y desarrollo del que hemos dispuesto. De la misma forma, la utilización de la tecnología 802.11, nos ha permitido implementar el software de localización para diferentes tipos de dispositivos, ordenadores portátiles y PDAs, con sistemas operativos distintos, que lo hace compatible con la mayoría de los dispositivos portátiles del mercado. Uno de los principales inconvenientes que tienen los sistemas de localización es su adaptabilidad a entornos cambiantes, o su aplicación a diferentes escenarios sin tener que realizar trabajos de adaptación a cada uno de esos escenarios. Este es un reto que nos marcamos en nuestra línea de investigación, el poder diseñar una arquitectura que sea capaz de adaptarse a los continuos cambios que pueda sufrir un escenario. Para ello ya vimos como se puede hacer uso de redes de sensores. Estudiaremos como de buena es esta solución para resolver este problema y se realizaran las investigaciones y desarrollos necesarios para ponerla en funcionamiento. Con esta tesis de máster, se ha pretendido, y creemos que lo hemos conseguido, sentar la base de una posible investigación a largo plazo que posibilite el estudio, diseño e implementación de un sistema de posicionamiento, que englobe tantas tecnologías sean necesarias, con el objetivo de mejorar los desarrollos creados y estudiados hasta el momento. Creemos que esta línea de investigación está hoy en día muy abierta, las exigencias del mercado y las nuevas aplicaciones que están surgiendo entorno a ofrecer servicios personalizados, y de valor añadido, a cada usuario, pasa sin duda por tener detrás un sistema de localización y seguimiento que sea capaz de situar de forma correcta a un usuario dentro de un entorno cambiante.

24

5. Bibliografía [1] IEEE 802.11 Wireless local area network. http://ieee802.org/11/ [2] IEEE Wireless LAN Medium Control (MAC) and Phyical Layer (PHY) Specifications. Website: http://standards.ieee.org/getieee802/, 99 [3] WIMAX, http://www.ieee802.org/16/ [4] GPS , http://www.gps.gov/, Public information about the Global Positioning System (GPS) and other space-based positioning, navigation, and timing (PNT) systems [5] Galileo, http://www.esa.int/esaCP/Spain.html, Portal de la agencia especial europea. [6] Zigbee, IEEE 802.15.4, http://standards.ieee.org/getieee802/download/802.15.4-2006.pdf [7] RFID, Standard definition: ISO 11784, ISO 11785, ISO 14443, ISO 15693, ISO 18047, ISO 18046. [8] Bluetooth, estándar IEEE 802.15.1 , http://www.ieee802.org/15/pub/TG1.html [9] P. Bahl and V. N. Padmanabhan, “RADAR: An in-building RF-based user location and tracking system”. Microsoft Research. Publication: IEEE INFOCOM 2000 – March 2000. [10] T. King, S. Kopf, T. Haenselmann, C. Lubberger and W. Effelsberg, “Compass: A probabilistic indoor positioning system based on 802.11 and digital compasses”. 1st international workshop on Wireless network testbeds, experimental evaluation & characterization 2006, Los Angeles, CA, USA September, 2006, pages 34-40. [11] A. M. Ladd, K. E. Bekris, A. Rudys,, L. E. Kavraki and D. S. Wallach, “Robotics based location sensing using wireless ethernet”. Wireless Networks, Ed. Springer Netherlands, February 2005, pages 189-204. [12] L. M. Ni, Y. Liu, Y. C. Lau and A. P. Patil, “LANDMARC: Indoor Location Sensing Using Active RFID”. Wireless Networks, Ed. Springer Netherlands , January 2005, pages 701-710. [13] R. Lobillo, J. M. Maestre, E. F. Camacho, “Sistema de localización mediante tecnología ZigBee: Aplicaciones a domótica”. Comité español de automática, XXIX Jornadas de automática, Septiembre 2008. [14] P. Krishman, A. S. Krishnakumar, Wen-Hua Ju, C. Mallows and S. Ganu, “A System for LEASE: Location estimation assisted by stationary emitters for indoors RF wireless networks”. INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, March 2004, pages 1001-1011. [15] Y. Chen, J. Chiang, H. Chu, P. Huang and A. Wen Tsui, “Sensor-Assisted Wi-Fi indoor location system for adapting to environmental dynamics Proceedings of the 8th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, 2005, pages 118-125. [16] B. Ferris, D. Hähnel and D. Fox, “Gaussian processes for signal strength-based location estimation”. Proc. of Robotics Science and Systems, 2006. [17] J. Hightower and G. Borriello, “Location system for ubiquitous computing”. University of Washington. Computer, August 2001, pages 57-66. [18] G. Borriello, M. Chalmers, A. LaMarca and P. Nixon, “Delivering Real-World ubiquitous location systems”. Communications of the ACM - Volume 48, March 2005, pages 36-41.

25

[19] A. LaMarca, Y. Chawathe, S. Consolvo, j. Hightower, I. Smith, T. Sohn, J. Howard, J. Hughes, F. Potter, J. Tabert, P. Powledge, G. Borriello and Bill Schilit, “Place Lab: Device positioning using radio beacons in the wild”. Lecture Notes in Computer Science, Pervasive Computing, Ed. Springer Berlin, May 2005, pages 116-133. [20] B. N. Schilit, A. LaMaca, G. Borriello, W. G. Griswold, D. McDonald, E. Lazowska, A. Balachandran, J. Hong and V. Iverson, “Challenge: Ubiquitous location-aware computing and the ‘Place Lab’ initiative”. Proceedings of the 1st ACM international workshop on Wireless mobile applications and services on WLAN hotspots, September 2003, pages 29-35. [21] J. Blumenthal, R. Grossmann, F. Golatowski, D. Timmermann, “Weighted centroid localization in Zigbee-based sensor networks”. IEEE International Symposium on Intelligent Signal Processing (WISP 2007). [22] A. LaMarca, J. Hightower, I. Smith and S. Consolvo, “Self-mapping in 802.11 location systems”. Lecture Notes in Computer Science, Ed. Springer Berlin, August 2005, pages 87-104. [23] K. Kaemarungsi and P. Krishnamurthy, “Modeling of infoor positioning system based on location fingerprinting”. IEEE INFOCOM 2004, Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies. November 2004. Pages 1012 – 1022. [24] M. Youssef and A. Agrawala, “The Horus WLAN location determintation system”. International Conference On Mobile Systems, Applications And Services, 2005, pages 205-218. [25] T. King, T. Haenselmann, S. Kopf and W. Effelsberg, “Overhearing the wireless interface for 802.11-based positioning system”. Pervasive Computing and Communications, 2007. March 2007, pages 145-150. [26] R. Chandra, J. Padhye, A. Wolman and B. Zill, “A location-based management system for enterprise wireless LANs”. Microsoft Research. INFOCOM 2004, March 2004, pages 10011011. [27] Y. Chen, Y. Chan and C. She, “Enabling location-base services in wireless LAN hotspots”. International journal of network management, May 2005, pages 163-175. [28] O. Rashid. W. Bamford, P. Coulton and R.Edwards, “PAC-LAN: Mixed-Reality gamming with RFID-enabled mobile phones”. Computers in Entertainment (CIE), October 2006. [29] P. Castro, P. Chiu, T. Kremenek and R. Muntz, “A probabilistic room location service for wireless networked environments”. Lecture Notes in Computer Science, Ed. Springer Berlin, 2001, pages 18-34. [30] R. Battini, T. Le Nhat and A. Villani, “Location-aware computing: a neural network model for determining location in wireless LANs”. Tech. Rep. DIT-02-0083, February 2002. [31] Ekahau, www.ekahau.com

26