Repositorio Institucional de Documentos

Autor: Miguel Eguizábal Alonso Director: Juan Chóliz Muniesa Ponente: Ángela Hernández Solana Curso 2009/2010 1 de Septiembre de 2010 Ingeniería Superior de Telecomunicación Departamento de Ingeniería Electrónica y Comunicaciones Centro Politécnico Superior Universidad de Zaragoza Sistemas de localización avanzados en entornos interiores basados en tecnología UWB Miguel Eguizábal Alonso 2 Sistemas de localización avanzados en entornos interiores basados en tecnología UWB Resumen El presente proyecto fin de carrera, se ha realizado en el marco del proyecto integrado EUWB dentro del VII Programa Marco de la Unión Europea, en el que participa la Universidad de Zaragoza a través del Grupo de Tecnologías de las Comunicaciones (GTC) del Instituto de Investigación en Ingeniería de Aragón (I3A). La localización de los terminales móviles se ha convertido en un requisito importante para las redes inalámbricas comerciales. Mientras que en entornos exteriores la tecnología GPS está ampliamente extendida, en entornos interiores no existe ninguna tecnología predominante. La tecnología Ultra WideBand (UWB) se caracteriza por la utilización de pulsos de muy corta duración, lo que le permite localizar terminales móviles con un error del orden de las decenas de centímetros, midiendo el retardo de un pulso desde que es emitido por el transmisor hasta que llega al receptor. Además, otras ventajas como su bajo consumo, su inmunidad frente al efecto multi-camino, o la posibilidad de simultanear transmisión de información y localización, hacen de UWB una tecnología prometedora para aplicaciones de sistemas de localización en interiores. Este PFC se centra en la implementación y evaluación de diferentes algoritmos avanzados de localización, de diversas complejidades y en particular de los propuestos en el proyecto EUWB. Para ello se ha empleado un simulador de localización en entornos interiores en C++ ya existente, realizando modificaciones para adaptarlo a los requisitos de este proyecto. Algunas modificaciones que se han realizado para tratar de mejorar el comportamiento de los algoritmos de localización son el prefiltrado y la ponderación de las distancias estimadas. Para la evaluación de los algoritmos se han llevado a cabo simulaciones en diferentes escenarios y situaciones. Además, se plantea también la mejora de algunos de los algoritmos considerados a través de la utilización de información geográfica y estadística, de cara a optimizar el compromiso entre precisión y recursos utilizados. En particular, estas mejoras se centran en dos aspectos, que son la detección de situaciones NLOS y la utilización de información acerca de las rutas de los targets. Sistemas de localización avanzados en entornos interiores basados en tecnología UWB 3 Índice 1. Descripción del proyecto ......................................................................................................... 5 1.1 Introducción ........................................................................................................................ 5 1.1.1 La tecnología UWB ....................................................................................................... 5 1.2 Marco del proyecto ............................................................................................................. 6 1.3 Descripción del proyecto ..................................................................................................... 7 1.4 Objetivos del proyecto ........................................................................................................ 8 1.5 Documentación del proyecto .............................................................................................. 8 2. Análisis del sistema de localización ...................................................................................... 10 2.1 Descripción del Sistema .................................................................................................... 10 2.1.1 Topología de la red ..................................................................................................... 10 2.1.2 Descripción de la capa MAC ....................................................................................... 11 2.1.3 Distribución en la red de la función de tracking ........................................................ 12 2.1.4 Adquisición y distribución de la información de localización .................................... 12 2.1.5 Implementación de la función de seguimiento .......................................................... 13 2.2 Descripción de los algoritmos de localización ................................................................... 13 2.2.1 Trilateración ............................................................................................................... 13 2.2.2 Filtro de Kalman ......................................................................................................... 14 2.2.3 Filtro de partículas ...................................................................................................... 15 2.2.4 MDS (MultiDimensional Scaling) ................................................................................ 16 2.2.5 Distance Contraction .................................................................................................. 17 2.2.6 SMACOF ...................................................................................................................... 18 2.3 Simulador C++ ................................................................................................................... 18 2.3.1 Fichero de entrada: parameters ................................................................................ 18 2.3.2 Ficheros de salida: error y resources ......................................................................... 19 2.3.3 Clase CTarget_node .................................................................................................... 19 2.3.4 Clase CAnchor_node .................................................................................................. 20 2.3.5 Clase CLocation_manager .......................................................................................... 20 2.3.6 Clase CPicocell_manager ............................................................................................ 20 2.3.7 Clase CNetwork .......................................................................................................... 20 2.3.8 Implementación de los algoritmos de localización .................................................... 20 2.4 Requisitos del sistema ....................................................................................................... 22 2.4.1 Adaptación a escenario basado en paredes............................................................... 23 Miguel Eguizábal Alonso 4 2.4.2 Implementación de algoritmos avanzados ................................................................ 23 2.4.3 Utilización de información geográfica ........................................................................ 24 3. Diseño del proyecto ............................................................................................................... 26 3.1 Descripción del diseño ...................................................................................................... 26 3.1.1 Adaptación a escenario basado en paredes............................................................... 26 3.1.2 Implementación de algoritmos avanzados ................................................................ 28 3.1.3 Utilización de información geográfica ........................................................................ 29 3.2 Herramientas utilizadas .................................................................................................... 31 3.3 Proceso de desarrollo ........................................................................................................ 31 3.3.1 Ciclo de vida ............................................................................................................... 31 3.3.2 Planificación ............................................................................................................... 32 4. Resultados .............................................................................................................................. 35 4.1 Comparativa de algoritmos básicos .................................................................................. 35 4.1.1 Modelo estadístico ..................................................................................................... 35 4.1.2 Modelo basado en paredes y rutas ............................................................................ 37 4.1.3 Filtro de partículas ...................................................................................................... 40 4.2 Prefiltrado ......................................................................................................................... 41 4.3 Ponderación ...................................................................................................................... 43 4.4 Uso de información geográfica ......................................................................................... 44 4.4.1 WLS-MDS y WLS-DC ................................................................................................... 44 4.4.2 Filtro de partículas ...................................................................................................... 46 4.4.3 Filtro de Kalman ......................................................................................................... 48 5. Conclusiones .......................................................................................................................... 50 5.1 Conclusiones del proyecto ................................................................................................ 50 5.2 Mejoras del proyecto ........................................................................................................ 51 5.3 Consideraciones personales .............................................................................................. 51 6. Referencias bibliográficas ..................................................................................................... 52 ANEXO A: Descripción de los algoritmos de localización .................................................... 53 ANEXO B: Descripción del simulador .................................................................................... 64 ANEXO C: Resultados ............................................................................................................. 85 Sistemas de localización avanzados en entornos interiores basados en tecnología UWB 5 1. Descripción del proyecto 1.1 Introducción El conocimiento acerca de la localización de los terminales móviles se ha convertido en un requisito importante para las redes inalámbricas comerciales, de servicio público y militares. Mientras que en entornos exteriores, la tecnología GPS está ampliamente extendida con aplicaciones como los sistemas de navegación para automóviles, la gestión de flotas o la localización de llamadas de emergencia, las potenciales aplicaciones de la localización en interiores no se están explotando debido a la incapacidad de GPS para operar en entornos interiores. Esta situación ha dado lugar a la aparición de numerosas tecnologías que tratan de cubrir esas aplicaciones de localización en interiores. La precisión y el alcance son aspectos importantes en los sistemas de localización y dependen en gran medida de las señales y por tanto, de la tecnología utilizada. Algunas de las tecnologías utilizadas para proporcionar localización en interiores son UWB, ZigBee, WLAN, Bluetooth o redes de acceso celular como GSM. En general, la localización se compone de dos fases, la estimación de las distancias, también denominada ranging, y el cálculo de la posición. La estimación de las distancias se basa en la medida de distintos parámetros como pueden ser el ángulo de llegada (AOA, Angle of Arrival), el nivel de señal recibida (RSSI, Received Signal Strength Indication) o el tiempo de llegada (TOA, Time of Arrival) de señales de referencia transmitidas entre el elemento a localizar y los nodos de referencia. Por otro lado, para el cálculo de la posición existen multitud de algoritmos, desde los más sencillos basados en cálculos geométricos hasta algoritmos de seguimiento que tienen en cuenta la posición anterior del usuario y su trayectoria. 1.1.1 La tecnología UWB Ultra wideband (UWB) es una tecnología que nació durante la década de 1960, y cuyo nombre fue acuñado por el Departamento de Defensa de los Estados Unidos en 1989. Se desarrolló para radar, localización y aplicaciones de comunicaciones. Se definen como tecnología UWB aquellos sistemas en los que el ancho de banda de la transmisión ocupa más de un 20% de la frecuencia central o más de 500 MHz. En general los sistemas UWB usan señales basadas en trenes de pulsos de corta duración. El intervalo entre los pulsos individuales puede ser uniforme o variable y existen diferentes métodos para modular el tren de pulsos con datos para comunicaciones. Otro punto importante en los sistemas UWB es que los pulsos individuales son muy cortos de duración, normalmente mucho más cortos que el intervalo correspondiente a la duración de un bit, por lo que la señal resultante tiene un ancho de banda grande. Debido a sus características, esta tecnología permite localizar los terminales móviles con un error del orden de las decenas de centímetros. Debido a que UWB está basada en pulsos ultracortos, el receptor puede determinar el tiempo de llegada con precisión de picosegundos y, por tanto, estimar la posición con precisión de centímetros. La distancia al Miguel Eguizábal Alonso 6 móvil se calcula midiendo el retardo de un pulso desde que es emitido por el transmisor hasta que llega al receptor. Posteriormente, utilizando algoritmos de posicionamiento se determina con gran exactitud la posición del terminal. Algunas ventajas que presenta UWB son:  Estimación de posición con precisión de centímetros.  Grandes velocidades de transmisión con una baja potencia transmitida ya que emplea un gran ancho de banda.  Señal inmune al efecto multi-camino ya que, debido a su corta duración, es posible distinguir entre la señal directa y las señales reflejadas en los obstáculos. Centrándose en las aplicaciones de la tecnología UWB, cabe distinguir entre dos tipos fundamentales de sistemas UWB:  HDR/VHDR (High/Very High Data Rate): Presentan tasas de transmisión elevadas, hasta centenares de Mbps, y alcances cortos, hasta 5 metros. No se basan en sistemas pulsados, sino en modulaciones como Multiband-OFDM y DS-SS (Direct Sequence Spread Spectrum). Se estudiaron en el grupo IEEE 802.15.3a, y la propuesta basada en MB-OFDM ha sido estandarizada por la WiMedia Alliance.  LDR/LDR-LT (Low Data Rate with Location Tracking): Presentan tasas de transmisión inferiores, hasta la decena de Mbps, pero con mayores alcances, del orden de decenas de metros. Además permiten una gran resolución en la estimación de la distancia, por lo que son apropiadas para la localización y seguimiento. El uso de UWB en redes inalámbricas de área personal (WPANs) de baja tasa se contempla en el estándar 802.15.4a. A modo de documentación se utilizaron las referencias [1], [2] y [3]. 1.2 Marco del proyecto El presente proyecto fin de carrera, se ha realizado en el marco del proyecto integrado EUWB dentro del VII Programa Marco de la Unión Europea, en el que participa la Universidad de Zaragoza a través del Grupo de Tecnologías de las Comunicaciones (GTC) del Instituto de Investigación en Ingeniería de Aragón (I3A). Dentro del proyecto EUWB, la participación del grupo investigador de la Universidad de Zaragoza se focaliza en dos grupos de trabajo: el grupo de trabajo 4, centrado en la investigación de sistemas de localización y seguimiento avanzados, y el grupo de trabajo 6, centrado en la integración de UWB y otras tecnologías en redes heterogéneas. Uno de los posibles escenarios dentro del grupo de trabajo de redes heterogéneas es la integración de la tecnología LDR-LT UWB en dispositivos de usuario en redes de acceso inalámbricas tales como UMTS o WiMAX. El objetivo de integrar UWB en estos dispositivos es el de proporcionar información de localización en entornos interiores, complementando la Sistemas de localización avanzados en entornos interiores basados en tecnología UWB 7 información de posicionamiento en exteriores proporcionada por GPS. Los principales escenarios de aplicación identificados son áreas de interiores relativamente grandes y con una alta densidad de usuarios tales como centros comerciales, palacios de congresos, aeropuertos, etc. La disponibilidad de información de posicionamiento es fundamental para el desarrollo de servicios basados en localización, además de poder ser aprovechada por la propia red de acceso celular para mejorar la gestión de recursos radio. Dentro del grupo de trabajo 4, una de las tareas desarrolladas por el grupo investigador de la Universidad de Zaragoza es el desarrollo de una herramienta de simulación que permita analizar las prestaciones reales de un sistema de localización UWB en un entorno interior de área relativamente grande, evaluando las posibles alternativas de diseño (arquitecturas, algoritmos, etc.). Para ello se utilizan las especificaciones reales tanto a nivel físico como de acceso al medio de los dispositivos LDR-LT UWB que se han desarrollado dentro del propio proyecto. El presente PFC se enmarca dentro de esta línea de trabajo. 1.3 Descripción del proyecto La disponibilidad de información de la localización del usuario y de los elementos de su entorno es uno de los elementos clave en el ámbito de la inteligencia ambiental. En entornos exteriores, la tecnología GPS está ampliamente extendida con los sistemas de navegación de vehículos como aplicación más destacada. Por el contrario, en entornos interiores la implantación de los sistemas de localización es escasa y se reduce a aplicaciones específicas, sin que ninguna tecnología concreta se haya impuesto. En particular, la tecnología UWB (Ultra WideBand) es una de las más prometedoras de cara a su uso en sistemas de localización y seguimiento. Algunos escenarios posibles para un sistema de localización en interiores serían por ejemplo centros comerciales, estaciones de tren, aeropuertos, hospitales, estadios deportivos, etc. Un ejemplo de aplicación para los clientes de un centro comercial sería poderlos situar en un mapa, de manera similar a los sistemas de navegación de los coches, encontrarles la ruta a una determinada tienda, buscarles los restaurantes más próximos y enviarles información de las tiendas cercanas como ofertas o descuentos. Existen diferentes algoritmos para obtener la posición a partir de las distancias estimadas. Los algoritmos complejos ofrecen una gran precisión, sin embargo requieren un mayor tiempo de computación que algoritmos más sencillos, capaces de calcular la posición consumiendo pocos recursos computacionales, pero con una precisión más limitada. En función de la situación se deberá escoger entre desarrollar dispositivos potentes, capaces de implementar algoritmos complejos o por el contrario desarrollar dispositivos menos potentes que implementen algoritmos menos complejos. Sin embargo, el corto alcance de los sistemas UWB hace que sean necesarios grandes despliegues si el área de interés es relativamente grande. Además, el posicionamiento requiere unos recursos debido a los intercambios que deben realizarse entre los nodos para estimar las distancias (ranging) y para transmitir las distancias estimadas. Por ello, además de Miguel Eguizábal Alonso 8 la precisión del posicionamiento, uno de los objetivos de todo sistema de localización debe ser minimizar la cantidad de recursos (tanto de infraestructura como de comunicación) necesarios. Una posible mejora de los algoritmos existentes consiste en incorporar información acerca del entorno y de esta forma mejorar su precisión, manteniendo los recursos necesarios o por el contrario, disminuir los recursos consumidos, manteniendo la precisión del sistema. Puede tratarse de información acerca de paredes u obstáculos, o de información estadística acerca de las rutas de los usuarios. Otra posible solución puede consistir en detectar las situaciones de NLOS, de tal forma, que se trate de corregir la desviación introducida por el obstáculo en la distancia estimada. También se pueden mejorar las prestaciones de los algoritmos realizando un filtrado previo de las estimaciones o mediante una ponderación de las estimaciones en base a su variabilidad. Para poder evaluar las prestaciones de estos algoritmos avanzados de localización se necesita una herramienta de simulación. Sobre esta herramienta de simulación se analizarán diferentes modificaciones realizadas en los algoritmos de localización. 1.4 Objetivos del proyecto El principal objetivo de este PFC se centrará en el diseño y evaluación, mediante simulación, de algoritmos avanzados de localización que optimicen el compromiso entre precisión y recursos utilizados mediante el uso de información geográfica y estadística. Para que se pueda utilizar esta información será necesario modificar el simulador ya existente. Otro de los objetivos del proyecto es la evaluación de distintos algoritmos de localización, y en particular de los propuestos dentro del proyecto EUWB. Para la evaluación de los algoritmos se realizarán simulaciones en diferentes escenarios y situaciones. Además del uso de información geográfica, también se evaluarán otras mejoras a los algoritmos como el prefiltrado y la ponderación de las distancias estimadas en base a su variabilidad. 1.5 Documentación del proyecto En este apartado se realiza un breve resumen de la documentación presentada en este PFC. La información está compuesta de una memoria y de varios anexos.  Memoria: En este documento se explica la tecnología UWB, los algoritmos utilizados, el simulador empleado, las decisiones tomadas para el diseño del proyecto así como se muestran los resultados y las conclusiones del proyecto. Los puntos principales de la memoria se resumen a continuación: Descripción del proyecto: En esta parte de la memoria, se realiza una introducción a los sistemas de localización y a la tecnología UWB. Además se expone el marco del proyecto, una descripción resumida del mismo y se marcan los objetivos a realizar. Análisis del sistema de localización: En este apartado se hace una descripción del sistema, de los algoritmos de localización implementados y del simulador. Además se Sistemas de localización avanzados en entornos interiores basados en tecnología UWB 9 exponen las mejoras que se van a realizar analizando los requisitos que deben cumplir cada una de ellas. Diseño del proyecto: Aquí se explican las mejoras realizadas de una forma más detallada, así como se muestran las herramientas utilizadas para el desarrollo de este proyecto. En la última parte, se describe el ciclo de vida y la planificación. Resultados: En esta parte se muestra un resumen de los resultados obtenidos en las simulaciones. Se muestran gráficas para evaluar las prestaciones de los diferentes algoritmos en términos del error de posicionamiento. Conclusiones: Se exponen las conclusiones del proyecto. También se proponen posibles mejoras futuras para el proyecto. Referencias bibliográficas: En este apartado aparecen los libros o documentos que se han utilizado como referencia para realizar este PFC.  ANEXO A. Descripción de los algoritmos de localización: En este anexo se explican al detalle los algoritmos de localización implementados en el simulador.  ANEXO B. Descripción del simulador: En este anexo se realiza una descripción completa del simulador.  ANEXO C. Resultados: En este anexo se analizan la totalidad de los resultados de las simulaciones realizadas. Miguel Eguizábal Alonso 16 las medidas observadas, y una fase de remuestreo donde se reemplazan una fracción de las partículas, para evitar que unas pocas partículas concentren toda la probabilidad. 2.2.4 MDS (MultiDimensional Scaling) MDS es un método que proporciona una representación espacial de los datos. Dada una matriz que contenga todas las semejanzas-desemejanzas ij ∂ entre Npuntos, MDS mapea esa configuración en un espacio tal que la diferencia entre ij ∂ y las distancias relativas ij d es mínima. Se llama X a la matriz []N µ × que contiene las coordenadas de Nobjetos en un espacio de µ dimensiones y se escoge el conjunto { } ij ∂ como el conjunto de distancias euclídeas entre dos objetos i y j del escenario { } ij d , donde 2()() T ij ij ij d xx xx=− ⋅− . De esta forma el problema MDS puede resolverse algebraicamente como la solución de mínimos cuadrados de la matriz T B XX= ⋅ . La solución clásica es construir la siguiente matriz de Gram: º2 1 2 G JD J=−⋅⋅ ⋅ donde 11 / T N NN JI N= − es la “centering matrix”, que es una matriz simétrica e idempotente, la cual, cuando se multiplica por un vector tiene el mismo efecto que restarle la media de los componentes del vector a cada componente, con 1N el vector unitario [ 1]N× , N I la matriz identidad []NN× y º indica el producto elemento por elemento. D es la matriz de distancias euclídeas( [] ij ij Dd= ). La matriz G es equivalente a B (para X centrada en el origen). Por lo tanto, la técnica MDS permite recuperar la localización Y de todos los nodos de la red a partir de la matriz de distancias euclídeas: 1/2 1: 1: [] []YV µµ = ⋅Λ T GV V= ⋅Λ⋅ donde V contiene en sus columnas los vectores propios de G y Λ es una matriz diagonal cuyos elementos de la diagonal son los valores propios de G . Por lo tanto, para poder calcular la matriz Y se debe obtener la matriz de Gram G y después aplicarle la descomposición en valores propios. La configuración de los nodos que nos devuelve el algoritmo MDS, está mapeada en un sistema de coordenadas diferente al original. Para trasladar las localizaciones Y y obtener las localizaciones reales X , es necesario aplicar una transformación a Y llamada Procrustes. De tal forma que conociendo las coordenadas A X de al menos A µ > anchors, la solución Y puede reorientarse mediante esta transformación, obteniendo X . La transformación Sistemas de localización avanzados en entornos interiores basados en tecnología UWB 17 Procrustes es una transformación geométrica lineal involucrando únicamente traslación, reflexión, rotación ortogonal y escalado. Se ha utilizado la referencia [7] para la explicación. 2.2.5 Distance Contraction Como se ha comentado anteriormente al explicar el modelo de ranging, la distancia estimada está sesgada debido al error introducido por el canal (multicamino, NLOS) que es siempre positivo. Una posible estrategia consiste en “contraer” las distancias estimadas para tratar de mitigar el sesgo de la estimación. Mediante el algoritmo distance contraction se contraen las distancias estimadas, que posteriormente se utilizarán en un algoritmo de optimización como por ejemplo SMACOF para hallar la solución óptima. Se ha utilizado la referencia [8] para la explicación del DC. Se dispone del conjunto de distancias medidas del target a cada anchor i : { } i d  . El primer paso del algoritmo es verificar la existencia de la región de viabilidad (feasibility region). Esta región de viabilidad se define como: { } ˆ ˆ| ii I xd d i≤∀   donde ˆi d es la distancia del punto ˆ x a cada anchor i . Si la región de viabilidad no existe, no se puede aplicar el algoritmo de contracción de distancias. Una vez verificada la existencia de la región de viabilidad, se pueden calcular las distancias contraídas i d . Para ello se evalúa la siguiente expresión para cada uno de los anchors: 2 ˆ ˆ argmax( ) ii xI x dd ∈ = −  Para cada anchor obtenemos el punto i x , que es el punto de tangencia entre la región de viabilidad y la circunferencia con centro la posición del anchor y con radio i d , que es la distancia del anchor al punto i x . Es necesario conseguir un punto inicial 0 ˆ x dentro de la región, para que después el algoritmo sea capaz de encontrar el punto que maximiza la expresión anterior. Para calcular el punto inicial se utiliza la siguiente expresión: ( ) 2 0ˆ1 ˆ ˆargmin max 0, A n N ii xi x dd ∈= = − ∑   donde A N es el número de anchors utilizados en la medida. Finalmente, se sustituyen las distancias medidas i d  por las distancias contraídas i d y se ejecuta un algoritmo de optimización, como por ejemplo SMACOF, para obtener la solución óptima Miguel Eguizábal Alonso 18 2.2.6 SMACOF El algoritmo SMACOF sirve para optimizar la matriz de coordenadas de los anchors y del target, X de dimensiones []n µ × , a partir de una solución inicial obtenida mediante otro algoritmo como MDS o distance contraction, de forma que la matriz de distancias derivada de la matriz X sea lo más parecida a la matriz de distancias medidas. Se ha seguido la referencia [9]. Se quiere encontrar la matriz X , tal que () ij ij dX≈∂ , donde: 2 1 () ( ) ij is js s dX x x µ = = − ∑ El índice 1,...,s µ = indica el número de dimensiones del espacio. Se define la función stress ()X σ de la siguiente forma: 2 11 () ( ()) nn ij ij ij ij X w dX σ = = = ∂− ∑∑ La matriz W es la matriz []nn× de pesos ij w , para ponderar las estimaciones en base a su variabilidad. Se asume sin pérdida de generalidad que 2 11 1 nn ij ij ij w = = ∂= ∑∑ . Para minimizar la función de stress se deriva e iguala a cero, obteniendo la configuración X que la minimiza: † ()X VBYY= donde los elementos de la matriz ()BY son 1 () y () 0 0 y ( ) 0 ij ij ij ij ij ij ik ki w d Yi j dY b i j dY b ij δ − ≠ − ≠≠   = ≠=  −=   ∑ y † V es la matriz pseudo-inversa “Moore-Penrose”. En el simulador se implementa como un procedimiento iterativo, en el paso 0t= , se ajusta (0) YX= , donde (0) X es la configuración inicial. En cada iteración se calcula ()t X y después se obtiene () () t X σ y se para de iterar si se cumple la condición: ( ) ( 1) ()( ) tt XX σσ ε − −< o si se supera un determinado límite de iteraciones. 2.3 Simulador C++ 2.3.1 Fichero de entrada: parameters Parameters.txt es uno de los ficheros de entrada del simulador, mediante el cual configuramos su funcionamiento. Los parámetros más importantes que se pueden configurar se muestran a continuación: Sistemas de localización avanzados en entornos interiores basados en tecnología UWB 19 • Modelo del simulador: Statistic o Based on wall & routes plan. El modelo estadístico es el que estaba implementado previamente en el simulador, en el que las distancias estimadas se obtienen en base al modelo estadístico de ranging, de manera independiente en cada iteración y los targets se pueden desplazar en cualquier dirección. El modelo Based on wall & routes plan es el que se va a desarrollar en este proyecto, en el que las distancias estimadas vendrán determinadas por la existencia o no de paredes, de acuerdo al plano definido y el movimiento de los targets vendrá determinado por las rutas definidas. • Número de targets y velocidad máxima y mínima de los targets. • Tamaño del area y distancia de separación entre anchors. • Algoritmos de seguimiento y número de anchors utilizados para el seguimiento. • Nivel de error residual en la estimación de la distancia (residual ranging noise). 2.3.2 Ficheros de salida: error y resources Con los ficheros de salida se puede comprobar y evaluar el funcionamiento del simulador, en términos del error de posicionamiento y de los recursos consumidos. En el fichero error.txt se muestran los resultados de la simulación relacionados con el error de posicionamiento. Se muestran tanto los resultados individuales para cada target, como el resultado global. En este fichero se puede observar el número de procesos de posicionamiento y la media, varianza y distribución del error de posicionamiento. En el otro fichero de salida resources.txt se pueden observar los recursos empleados para la localización, tales como, el número de tramas utilizadas para localización clasificadas en tramas para el envío de distancias medidas, para actualización de la posición, ranging request y ranging response. También se puede observar el tiempo utilizado para localización en segundos y en porcentaje respecto al tiempo total de simulación, así como la tasa de datos usada para localización en bps. 2.3.3 Clase CTarget_node Esta clase implementa los nodos target a localizar. En esta clase se actualiza la posición real de los targets. En el caso del modelo estadístico, la dinámica de los targets se modela por direcciones y velocidades aleatorias que son constantes durante un periodo de tiempo determinado, después del cual se calcula una nueva velocidad y dirección. El modelo dinámico se define mediante unas velocidades máxima y mínima y la tasa de cambio de dirección. En esta clase se implementan también la función para estimar las distancias a cada anchor y las funciones que recogen las estadísticas del error de posicionamiento. Miguel Eguizábal Alonso 20 2.3.4 Clase CAnchor_node Esta clase define los nodos anchor, que son los nodos con posiciones fijas y conocidas. Los anchors se encargan de transmitir la información de localización de los target al location manager y sirven de referencia para el posicionamiento de los targets. 2.3.5 Clase CLocation_manager Este elemento es el encargado de estimar la posición de los target, a partir de las distancias estimadas a los anchors. Puede estar implementado en los target o en los anchors, en función de la estrategia seleccionada. Para estimar la posición necesita conocer las posiciones de los anchors, las distancias estimadas, la última posición estimada del target y el algoritmo que se ha de utilizar. Esta clase también implementa la función que selecciona los anchors que se van a utilizar en la medida y la función que indica cuando es necesario actualizar la posición del target. 2.3.6 Clase CPicocell_manager El picocell manager controla la transmisión de tramas y el uso de los slots. Se encarga de los procesos de ranging, de transmisión de información y de actualización de las relaciones de vecindad entre los targets y los anchors. Están implementadas las colas de transmisión y de ranging, que almacenan las solicitudes de transmisión y de ranging respectivamente, para ser procesadas posteriormente. Este elemento se encarga también de recoger las estadísticas relacionadas con los recursos consumidos. 2.3.7 Clase CNetwork Esta clase es la encargada de implementar la topología de la red, incluyendo los elementos: nodos anchor, nodos target, location manager y picocell manager. También realiza la carga de los parámetros, y en el caso del modelo de simulador basado en paredes y rutas, también se encarga de cargar los diferentes escenarios y las probabilidades de los targets de seguir recto, girar o darse la vuelta cuando llegan a un nodo del plano. Además, realiza la distribución geográfica de los nodos anchor y de los location managers, la asignación de los targets a cada location manager y el cálculo del número de saltos de cada nodo anchor al location manager más cercano. 2.3.8 Implementación de los algoritmos de localización Trilateración El algoritmo de trilateración está implementado en la clase CLocation_manager, dentro de la función: Calculate_position. En diferentes variables estarán almacenadas las posiciones de los tres anchors escogidos, así como las tres distancias medidas, para poder desarrollar el algoritmo y obtener la posición del target. Sistemas de localización avanzados en entornos interiores basados en tecnología UWB 21 Filtro de Kalman El Filtro de Kalman se ha implementado utilizando la librería kfilter. El filtro está desarrollado en la clase CPlane_EKF. Esta clase dispone de las funciones: makeA, makeH, makeV, makeR, makeW y makeQ para construir las matrices A , H , V , R , Wy Q . También dispone de las funciones makeProcess, en la que se almacena en un vector temporal el nuevo vector de estado, y makeMeasure, donde se actualiza el vector de medidas. La posición y la velocidad inicial del target se obtienen mediante trilateración. Se ejecuta la trilateración las dos primeras veces, para así obtener dos posiciones consecutivas del target y poder hacer una estimación de la velocidad inicial del target. En la clase CLocation_manager, dentro de la función Calculate_position, se inicializa el filtro de Kalman y en cada estimación se llama a la función Step, que ejecuta el filtro de Kalman. Filtro de Partículas El filtro de partículas se ha desarrollado utilizando la librería smctc [10]. El filtro está implementado en el fichero fuente pffuncs.cc. Para desarrollar el filtro, este fichero incluye la clase cv_state, que almacena la posición y velocidad, tanto en el eje x como en el eje y, para cada partícula. También existe la clase cv_obs, para almacenar la posición y la distancia medida de cada anchor. Las funciones realizadas por el fichero son: • fInitialise: Inicializa las partículas, obteniendo una posición y una velocidad aleatorias con distribución normal, de media la posición inicial del target y la velocidad inicial del target respectivamente. La posición inicial y la velocidad inicial se obtienen mediante trilateración, de la misma forma que en el filtro de Kalman. • fMove: Obtiene una aceleración para el eje x y otra para el eje y de forma aleatoria y actualiza las particulas, actualizando la posición(con la velocidad y la aceleración) y la velocidad(con la aceleración). • logLikelihood: Calcula el logaritmo de la probabilidad para todas las partículas. Se dispone de tres modelos para calcularla, basados en una gaussiana, en la suma de dos gaussianas y en la suma de tres gaussianas respectivamente. Para calcular la probabilidad se tienen en cuenta las posiciones de la particula, de los anchors y las distancias medidas. • integrand_mean_x: Calcula la posición en el eje x del target, a partir de las partículas. • integrand_mean_y: Calcula la posición en el eje y del target, a partir de las partículas. En la clase CLocation_manager, dentro de la función Calculate_position, se inicializa el filtro de partículas y en cada estimación se llama a la función Iterate, que ejecuta el filtro de partículas. Miguel Eguizábal Alonso 22 WLS-MDS (propuesta PULSERS PHASE II) Este algoritmo es el propuesto en el marco del proyecto PULSERS PHASE II [11] y se basa en el uso de MDS para obtener una estimación inicial de la posición y en SMACOF para la optimización de la solución. El WLS-MDS se ha adaptado del desarrollo en C# realizado por otro socio dentro del proyecto EUWB y está implementado en la clase CMDSalgorithm. Dentro de esta clase, la función Centralized_Algorithm es la que genera la matriz de distancias, a partir de las distancias entre anchors y de las distancias medidas, y la matriz de pesos para ponderar las estimaciones en base a su variabilidad, mediante la función LINK_Weight. Una vez obtenidas ambas matrices, se llama a la función MDSMAP, que lleva a cabo el algoritmo MDS. Con este algoritmo obtenemos las posiciones del target y de los anchors que mejor se ajustan a la matriz de distancias calculada previamente. La solución obtenida del MDS se puede optimizar mediante el algoritmo SMACOF, implementado por la función smacofEUWBW. Se utiliza la librería Altaxo para obtener la matriz pseudo-inversa necesaria para el algoritmo. Para obtener la posición válida del target, se debe reorientar la solución mediante el algoritmo Procrustes. Para realizar las operaciones con matrices se ha utilizado la clase CGeneralMatrix, que se ha adaptado del desarrollo en C# realizado en el proyecto EUWB. La transformación Procrustes tambien se ha adaptado del desarrollo en C# y está desarrollada en la clase CProcrustes. WLS-DC (propuesta EUWB) Este algoritmo es el propuesto en el marco del proyecto EUWB y se basa en el uso de MDS para obtener una estimación inicial de la posición, distance contraction para contraer las distancias estimadas y SMACOF para la optimización de la solución. Está implementado en la clase CMDSalgorithm. Como en el caso anterior, este algoritmo se ha adaptado del desarrollado en C# por otro socio dentro del proyecto EUWB. La función Centralized_Algorithm_EUWB genera la matriz de distancias y la matriz de pesos de la misma forma que la función Centralized_Algorithm, y llama a la función MDSMAP, para realizar el MDS. La solución obtenida del MDS se optimiza mediante los algoritmos Distance Contraction y SMACOF. Con el algoritmo Distance Contraction, implementado en la función DistContrPos, se obtiene la matriz de distancias contraidas. Las funciones de minimización y maximización que se realizan dentro del algoritmo Distance Contraction se realizan mediante la librería DotNumerics. Con esa matriz de distancias, y con las posiciones del target y de los anchors obtenidas en el MDS, se ejecuta el algoritmo SMACOF. Para obtener la posición válida del target, se reorienta la solución mediante el algoritmo Procrustes, desarrollado por la clase CProcrustes. 2.4 Requisitos del sistema En este apartado se analizan los requisitos que tiene que cumplir el proyecto y las mejoras que se deben implementar en el simulador C++ ya existente. Debido a que se parte de Sistemas de localización avanzados en entornos interiores basados en tecnología UWB 23 un simulador previo, el principal requisito consiste en que todos los cambios introducidos deben ser compatibles con el simulador previo. 2.4.1 Adaptación a escenario basado en paredes Esta primera modificación consiste fundamentalmente en modelar los escenarios, modificar el movimiento de los targets para que se adapten a esos escenarios y modificar la estimación de las distancias. Modelado de escenarios Esta modificación consiste en diseñar una serie de escenarios de simulación. Los escenarios se compondrán de un listado de paredes, así como de las posibles rutas de los móviles definidas por nodos (intersecciones) y segmentos (pasillos). El principal requisito de esta modificación es conseguir cargar la información del escenario en el simulador y que esa información esté disponible para los algoritmos de localización. Movimiento de los targets La siguiente mejora consiste en modificar el movimiento de los target, para que se ajuste a los pasillos del escenario cargado. El target se desplazara de un nodo a otro del escenario siguiendo los segmentos definidos en el plano. Se escogerá un nodo destino aleatoriamente en base a las probabilidades definidas para el nodo actual y se escogerá una velocidad aleatoria que se mantendrá constante hasta que el target alcance el nodo destino. Un requisito de esta modificación es permitir que el modelo de movimiento anterior y el nuevo puedan coexistir, de tal forma que según qué modelo de simulador escojamos, los targets se muevan de una forma u otra. Estimación de las distancias En el simulador existente, la estimación de las distancias se realiza en base al modelo estadístico de ranging, de manera independiente en cada iteración. Se modificará la estimación de las distancias, de tal forma que se calculará el número de paredes existentes entre el anchor y el target de acuerdo al plano definido. Si no existen paredes entre el anchor y el target se estará en condiciones de LOS. Y si existen paredes se estará en condiciones de NLOS. El principal requisito de esta modificación es poder calcular el número de paredes existentes entre el target y cada anchor utilizado. 2.4.2 Implementación de algoritmos avanzados En esta segunda modificación se adaptarán los algoritmos WLS-MDS y WLS-DC, propuestos en PULSERS PHASE II y EUWB respectivamente, al simulador C++ existente. Además se implementarán un prefiltrado y una ponderación de las distancias estimadas. Miguel Eguizábal Alonso 24 Adaptación de los algoritmos propuestos en PULSERS PHASE II (WLSMDS) y EUWB (WLS-DC) Esta modificación consiste en adaptar al simulador existente en C++ los algoritmos WLS-MDS y WLS-DC del desarrollo en C# realizado por otro socio dentro del proyecto EUWB. Además de adaptar estos algoritmos, se comprobará su correcto funcionamiento y se optimizarán algunos parámetros. Prefiltrado de las medidas La mejora del prefiltrado consiste en filtrar las distancias estimadas, antes de pasárselas al algoritmo de localización. En el simulador se implementara un filtro paso bajo, realizado mediante una ponderación de la distancia estimada actual y las distancias estimadas anteriores. Después esa nueva distancia se envía al algoritmo de localización para que estime la posición del target. Un requisito del prefiltrado es que nos permita elegir con cuantas muestras queremos realizar la ponderación, y nos permita elegir también cuales son los pesos de cada distancia en la ponderación. Si elegimos una única muestra para el prefiltrado, se utilizará la distancia estimada actual sin ningún prefiltrado. Otro requisito de esta modificación es que necesitamos almacenar las distancias estimadas anteriores, para poder realizar la ponderación. En concreto se almacenan la distancia actual y las cuatro distancias anteriores, con lo que siempre se tienen cinco distancias estimadas para realizar el prefiltrado. Ponderación de las medidas En esta modificación se trata de implementar en los algoritmos de localización una ponderación de las distancias medidas en base a su variabilidad, de tal forma que aquellas medidas cuya varianza sea elevada tendrán poco peso en la ponderación. Mientras que las que tengan poca varianza, serán las que tengan mayor peso. El requisito más importante de esta modificación es que se necesitan almacenar las distancias estimadas anteriores, para poder obtener la varianza de la medida, y poder obtener los pesos de la ponderación. 2.4.3 Utilización de información geográfica Esta mejora consiste en modificar alguno de los algoritmos de localización presentes en el simulador, para que utilicen información geográfica de los planos del escenario y de esta forma optimizar el compromiso entre precisión y recursos utilizados. Fundamentalmente esta modificación consta de dos bloques que son: Identificar situaciones NLOS y utilizar información acerca de las rutas de los targets. Un requisito de esta mejora es añadir estas modificaciones a los algoritmos, manteniendo la posibilidad de utilizar las versiones no mejoradas de los algoritmos. A través del fichero de parámetros es donde se selecciona el algoritmo de localización deseado. Sistemas de localización avanzados en entornos interiores basados en tecnología UWB 25 Identificación de situaciones NLOS Esta modificación consiste fundamentalmente en identificar situaciones de NLOS e utilizar dicha información para mejorar las prestaciones del algoritmo, bien a través del modelo de las observaciones en el caso de los algoritmos paramétricos, o a través de la ponderación en el caso de los algoritmos WLS-MDS y WLS-DC. Para identificar las situaciones NLOS se requiere detectar la existencia de paredes entre el target y los anchors. Utilización de información acerca de las rutas de los targets Con esta mejora se pretende que los algoritmos utilicen información sobre las rutas que suelen seguir los targets, para así mejorar la precisión de la estimación de la posición o para disminuir los recursos necesarios. Esta mejora será aplicable a los algoritmos que utilizan el modelo dinámico de los targets, concretamente el filtro de Kalman y el filtro de partículas. Se requiere un modelado de las rutas que siguen los targets en los planos, para poder extraer de ahí la información. En base a la información disponible de las rutas, se modificará el modelo dinámico utilizado en los algoritmos. Miguel Eguizábal Alonso 32 Las cuatro fases principales en este tipo de ciclo de vida son: • Determinar objetivos: En esta fase se fijan los objetivos, las alternativas y las restricciones del proyecto. • Análisis de riesgos: En la segunda etapa, se identifican los riesgos del proyecto y las estrategias alternativas para resolverlos. • Desarrollar (Ingeniería): En esta tercera fase, se desarrolla el proyecto. • Evaluación y Planificación: En la cuarta fase se revisa y evalúa todo lo realizado, y con ello se decide sí se continúa y se planifica la siguiente actividad. 3.3.2 Planificación En este apartado se presenta la planificación de las tareas del proyecto, en la que se estiman las horas a invertir en cada tarea. La planificación es el primer paso en un proyecto, ya que esta planificación aborda desde el inicio hasta la finalización del proyecto. Se realizó una planificación inicial y en este punto vamos a compararla con la planificación final, que son las horas invertidas realmente en cada tarea. De esta forma se podrán analizar las posibles causas de los desfases entre la planificación inicial y la planificación real o final. Planificación inicial En la figura 8 se muestra el diagrama de Gantt de la planificación inicial del proyecto. Más adelante se discutirán las diferencias con la planificación realizada al finalizar el proyecto. Figura 7. Diagrama modelo en espiral Sistemas de localización avanzados en entornos interiores basados en tecnología UWB 33 Figura 8. Diagrama de Gantt planificación inicial Figura 9. Diagrama de Gantt planificación final Miguel Eguizábal Alonso 34 Hitos del proyecto Se propusieron los siguientes hitos para este proyecto: Modificación 1 22 de Marzo de 2010 Modificación 2 15 de Abril de 2010 Modificación 3 17 de Mayo de 2010 Simulaciones 15 de Junio de 2010 Planificación final El diagrama de Gantt de la planificación final del proyecto se muestra en la figura 9. En la planificación inicial no se contemplaba la adaptación del algoritmo WLS-DC, aunque mientras se realizaba la adaptación del WLS-MDS se vio que podría ser interesante implementarlo. Desajuste entre planificación inicial y final Observando ambas planificaciones se puede observar que el primer desajuste se produjo en la etapa de Documentación que duró algo más de lo esperado, ya que tenía que aprender a programar un lenguaje nuevo para mí; Además también tenía que entender la estructura del simulador ya existente. Para el aprendizaje de C++ utilice la referencia [12]. La primera modificación, se realizó en menos tiempo del esperado, ya que no surgieron demasiados problemas en la programación y se consiguió que funcionara todo bastante rápido. De esta forma, se consiguió comenzar la segunda modificación prácticamente cuando estaba previsto. La segunda modificación duró bastante más tiempo del previsto, ya que no se había pensado realizar la adaptación del algoritmo WLS-DC como se ha comentado antes. Además, esta adaptación llevó mucho tiempo ya que la implementación que se disponía del algoritmo Distance Contraction era bastante confusa y costó bastante tiempo conseguir corregir todos los errores y que el algoritmo funcionase correctamente. La tercera modificación se implementó algo más rápido de lo esperado, ya que la programación de este bloque no ocasionó excesivos problemas. Por lo tanto la parte de programación se consiguió terminar relativamente en el tiempo que se había establecido inicialmente. Las simulaciones llevaron más tiempo del esperado, ya que se han simulado más situaciones y algoritmos de los que se pensaba simular en un comienzo. La realización de la memoria se ha llevado a cabo en algo menos de dos meses, que era más o menos el tiempo previsto inicialmente. Sistemas de localización avanzados en entornos interiores basados en tecnología UWB 35 4. Resultados En este apartado se muestra un resumen de los resultados obtenidos en las simulaciones realizadas. En el anexo C, se muestran los resultados completos. 4.1 Comparativa de algoritmos básicos 4.1.1 Modelo estadístico En primer lugar se van a evaluar los algoritmos de localización para el modelo estadístico del simulador. La evaluación de los algoritmos de localización se va a realizar en función del número de anchors utilizados para la estimación de la posición. En la figura 10, se muestra el error medio de posicionamiento de los algoritmos, para una distancia entre anchors de 10 metros, lo que significa que el área está cubierta por 36 nodos anchor, y para un error residual de ranging de 0.7 n σ = . Como puede observarse en la figura 10, los mejores resultados se obtienen con el filtro de partículas. Para calcular la probabilidad de cada partícula se dispone de tres modelos, basados en una gaussiana, en la suma de dos gaussianas y en la suma de tres gaussianas respectivamente. Con la notación “3c” y “2c”, se hace referencia al modelo usado, siendo “3c” el modelo basado en la suma de 3 gaussianas y “2c” el basado en la suma de dos gaussianas. No obstante, los resultados conseguidos con el filtro de partículas no son realistas, debido a que en el simulador las distancias estimadas se obtienen mediante un modelo de ranging estadístico. Y el filtro de partículas utiliza también un modelo estadístico del error de medida para obtener los pesos de las partículas. Además, ese modelo se ha optimizado mediante simulaciones, de tal forma que se comporta de manera similar al modelo de ranging. En un sistema real, una caracterización tan precisa del modelo de ranging especifico del escenario requeriría unas fases de medida y de calibración muy costosas. Y el uso de un modelo genérico no proporcionará resultados tan buenos. Por lo tanto, los resultados del filtro de partículas se deberan considerar como una referencia más que como una implementación realista. El 0,4 0,45 0,5 0,55 0,6 0,65 0,7 0,75 345678910 Average error(m) Number of anchors for positioning Trilateration Kalman Filter LS-MDS Particle Filter(3c) Particle Filter(2c) LS-DC Figura 10. Error medio de posicionamiento. Distancia entre anchors = 10 m. n σ = 0.7. Miguel Eguizábal Alonso 36 modelo de ranging estadístico tiene 3 componentes, por eso,el filtro de partículas utilizando el modelo de 3 componentes obtiene mejores resultados que utilizando solo dos componentes. Los algoritmos LS-MDS, LS-DC y filtro de Kalman presentan una evolución similar, sin embargo los mejores resultados se obtienen con LS-MDS y LS-DC. En particular, con LS-MDS se obtienen mejores resultados para 3 y 4 anchors y con LS-DC para más de 4 anchors. En los tres algoritmos, el número óptimo de anchors es 5. Si se utilizan más anchors, los nuevos anchors estarán más lejos del target y tendrán mayor desviación de ranging, provocando que el error de posicionamiento aumente. Por último, la trilateración es el algoritmo que peores resultados ofrece y es independiente del número de anchors escogido, ya que únicamente se emplean los tres anchors más cercanos al target en el algoritmo. Para todos los algoritmos hay un incremento del error cuando solo se utilizan tres anchors y el error se mantiene constante para más de 7 anchors, debido a que no es probable que el target esté en cobertura de más de 7 anchors. Los resultados cuando se aumenta la distancia entre anchors a 12.5 metros, por lo que el área estará cubierta por 25 anchors, y se mantiene el error residual de ranging de 0.7 n σ = , se muestran en la figura 11. Debido a que la distancia entre anchors es elevada, los anchors utilizados para el posicionamiento estarán bastante lejos del target. El filtro de partículas presenta los mejores resultados ya que se beneficia de su preciso modelo del error de medida. El algoritmo LS-DC obtiene mejores resultados que el LS-MDS, ya que el algoritmo Distance Contraction funciona correctamente cuando la mayoría de las distancias estimadas a los anchors presentan una desviación positiva. Por lo tanto, cuanto mayor sea la distancia entre anchors, mayor será la desviación de las distancias estimadas y mejores serán los resultados frente al uso únicamente del MDS, es decir, frente al algoritmo LS-MDS. La trilateración y el LS-MDS tienen un comportamiento muy similar mientras que, los peores resultados se obtienen con el filtro de Kalman, ya que su simple modelo de error Gaussiano no puede tratar con las elevadas desviaciones de las distancias estimadas para anchors muy alejados. 0,5 0,55 0,6 0,65 0,7 0,75 0,8 0,85 345678910 Average error(m) Number of anchors for positioning Trilateration Kalman Filter LS-MDS Particle Filter(3c) Particle Filter(2c) LS-DC Figura 11. Error medio de posicionamiento. Distancia entre anchors = 12.5 m. n σ = 0.7. Sistemas de localización avanzados en entornos interiores basados en tecnología UWB 37 Para todos los algoritmos el error se mantiene constante para más de 5 anchors, ya que no es probable que el target tenga cobertura con más de 5 anchors. No se consideran distancias mayores entre anchors, ya que se podría perder la cobertura entre los nodos anchor. Ahora se muestran los resultados cuando el error residual de ranging disminuye a 0.3 n σ = , para una distancia entre anchors de 10 m, en la figura 12. Como podría esperarse, el comportamiento de todos los algoritmos es mejor que en el caso de utilizar la misma configuración con un error residual de ranging de 0.7 y puede obtenerse un error medio de posicionamiento entorno a 15-30 cm. La mejora más remarcable es la del algoritmo de trilateración, que obtiene resultados comparables al LS-MDS, LS-DC y filtro de partículas de 2 componentes para un número de anchors igual a 4. Esto significa que la trilateración requiere unas estimaciones del TOA precisas para proporcionar buenos resultados, ya que siempre utiliza tres medidas para calcular la posición y no puede beneficiarse de la diversidad de las medidas. Como el error residual ha disminuido, las desviaciones del ranging tienen mayor importancia y por ello los anchors cercanos proporcionan estimaciones mucho más precisas que anchors alejados. Como consecuencia, el número óptimo de anchors es de 3 para el LS-MDS y de 4 para el filtro de Kalman, LS-DC y filtro de partículas de 2 componentes, empeorando mucho el comportamiento cuando se aumenta el número de anchors utilizados en el cálculo de la posición. 4.1.2 Modelo basado en paredes y rutas En este punto se van a evaluar los algoritmos de localización para el modelo basado en paredes y rutas del simulador. Al igual que en el anterior apartado, la evaluación de los algoritmos de localización se va a realizar en función del número de anchors utilizados para el cálculo de la posición. 0,1 0,15 0,2 0,25 0,3 0,35 0,4 0,45 0,5 345678910 Average error(m) Number of anchors for positioning Trilateration Kalman Filter LS-MDS Particle Filter(3c) Particle Filter(2c) LS-DC Figura 12. Error medio de posicionamiento. Distancia entre anchors = 10 m. n σ = 0.3. Miguel Eguizábal Alonso 38 En la figura 13, se muestran los resultados para una distancia entre anchors de 10 m y un error residual de ranging de 0.7 n σ = . En la figura 5 se muestra el escenario modelado para esta configuración. Los algoritmos LS-MDS, LS-DC y filtro de Kalman presentan un comportamiento muy similar, aunque el LS-MDS con un error mayor para 5 o más anchors. El filtro de partículas de 3 componentes obtiene mejores resultados que el de dos componentes para más de 4 anchors, ya que los anchors que se añaden están alejados y las desviaciones del ranging son mayores. La trilateración es el algoritmo con peores resultados, mientras que el filtro de partículas es el que ofrece los mejores resultados. Para todos los algoritmos el error se mantiene constante para más de 7 anchors, debido a que no es probable que el target esté en cobertura de más de 7 anchors. Por lo tanto el número óptimo de anchors utilizados para el cálculo es 7. Si se observa la figura 10, se puede ver que en el modelo estadístico para la misma configuración, el filtro de partículas obtiene mejores resultados respecto al resto de algoritmos que en el caso del modelo basado en paredes y rutas. Esto se debe a que se ha modificado el modelo de ranging y ya no se calcula la probabilidad de que el enlace entre target y anchor sea LOS, NLOS o NLOS severo sino que se calcula el número de paredes existentes entre el target y los anchors utilizados en la medida, y en base al número de paredes se determina la componente de error que se utiliza. El modelo estadístico del error de medida del filtro de partículas sigue ofreciendo muy buenos resultados, aunque en este caso se diferencia algo más del modelo de ranging. En la figura 14 aparecen los resultados si se aumenta la distancia entre anchors a 12.5 m y se mantiene el error residual de ranging 0.7 n σ = . En la figura 6 se puede observar el plano modelado, para esta distancia entre anchors. 0,3 0,35 0,4 0,45 0,5 0,55 0,6 0,65 0,7 345678910 Average error(m) Number of anchors for positioning Trilateration Kalman Filter LS-MDS Particle Filter(3c) Particle Filter(2c) LS-DC Figura 13. Error medio de posicionamiento. Distancia entre anchors = 10 m. n σ = 0.7. Sistemas de localización avanzados en entornos interiores basados en tecnología UWB 39 Ahora la distancia entre anchors es mayor, así que las desviaciones del ranging son mayores ya que los anchors están más alejados. Los algoritmos LS-MDS, LS-DC y filtro de Kalman presentan una evolución similar aunque el LS-MDS con un error mayor para más de 4 anchors. El LS-DC mejora más respecto al LS-MDS que en la configuración anterior, ya que como se explicó, el algoritmo DC funciona mejor cuando todas las distancias estimadas presentan un error positivo. El filtro de partículas de 3 componentes es el que mejor resultados ofrece, ya que es capaz de compensar las grandes desviaciones del ranging para anchors alejados. El filtro de partículas de 2 componentes presenta una evolución similar aunque con un error bastante superior. La trilateración es el algoritmo que peores resultados ofrece. Para todos los algoritmos el error se mantiene constante para más de 6 anchors, ya que no es probable que el target esté en cobertura de más de 6 anchors. Para esta configuración el número óptimo de anchors utilizados para el cálculo de la posición es 6. Al igual que en el modelo estadístico no se consideran distancias mayores entre anchors, ya que se podría perder la cobertura entre los nodos anchor. Ahora se presentan los resultados reduciendo el error residual de ranging a 0.3 n σ = . En la figura 15, se muestran los resultados para una distancia de 10 m entre anchors. 0,4 0,45 0,5 0,55 0,6 0,65 0,7 0,75 0,8 345678910 Average error(m) Number of anchors for positioning Trilateration Kalman Filter LS-MDS Particle Filter(3c) Particle Filter(2c) LS-DC Figura 14. Error medio de posicionamiento. Distancia entre anchors = 12.5 m. n σ = 0.7. Miguel Eguizábal Alonso 40 El comportamiento de todos los algoritmos es mejor que en la situación de utilizar la misma configuración para un error residual de ranging de 0.7. Como ya se vio en el modelo estadístico del simulador, como el error residual ha disminuido, las desviaciones del ranging tienen mayor importancia y por ello los anchors cercanos proporcionan estimaciones mucho más precisas que anchors alejados. Debido a esto, como la trilateración solo utiliza los tres anchors más cercanos, es el que mejor resultados ofrece para 4 o más anchors, ya que los anchors que se añaden proporcionan estimaciones mucho peores y hacen que el error de posicionamiento aumente, incluso para el filtro de partículas. Los algoritmos LS-MDS, LS-DC y filtro de Kalman tienen una evolución similar, aunque el LS-DC ofrece mejores resultados. El número óptimo de anchors para los tres algoritmos es 5. Para los dos modelos del filtro de partículas el número óptimo de anchors es 6. 4.1.3 Filtro de partículas Como se ha comentado previamente, los parámetros del filtro de partículas tanto para el modelo de 3 componentes como para el de 2 componentes se optimizaron mediante simulaciones. Sin embargo, en un sistema real los parámetros se fijarán mediante una fase de calibración que no ofrecerá resultados tan óptimos como mediante simulación. Por ello, en este apartado se van a comparar los resultados obtenidos por el filtro de partículas de 2 componentes optimizado, con el filtro de partículas de 2 componentes sin optimizar. La optimización se realizó para situaciones con un error residual de ranging de 0.7 n σ = y una distancia entre anchors de 10 m. En la figura 16 se muestran los resultados de los filtros de 2 componentes con y sin optimización para el modelo basado en paredes y rutas del simulador en función del número de anchors utilizado para el cálculo de la posición. 0,15 0,2 0,25 0,3 0,35 345678910 Average error(m) Number of anchors for positioning Trilateration Kalman Filter LS-MDS Particle Filter(3c) Particle Filter(2c) LS-DC Figura 15. Error medio de posicionamiento. Distancia entre anchors = 10 m. n σ = 0.3. Sistemas de localización avanzados en entornos interiores basados en tecnología UWB 41 Como puede observarse, la evolución de ambos filtros de partículas es la misma, pero el optimizado obtiene mejores resultados. La diferencia entre los errores del filtro optimizado y del filtro sin optimizar se mantiene constante en torno a los 5 cm. Por lo tanto, para disponer de un filtro de partículas perfectamente optimizado, se deberán optimizar los parámetros específicamente para el escenario en que se pretenda utilizar. Como ya se comentó, para conseguir una buena optimización, se requerirían unas fases de medida y de calibración muy costosas. Y si se utiliza un modelo genérico sin optimizar, se pierde precisión respecto a un modelo optimizado como se ha observado anteriormente en la figura 16. 4.2 Prefiltrado A continuación se van a mostrar los resultados del prefiltrado de las estimaciones para la configuración de 10 m entre anchors y error residual de ranging 0.7 n σ = . Para evaluar el comportamiento de esta mejora se van a comparar diferentes estrategias de filtrado en función de la velocidad del target. Hay que tener en cuenta que la tasa de actualización de las distancias entre el target y los anchors es de 1 segundo. Los resultados se muestran en la figura 17. 0,35 0,4 0,45 0,5 0,55 0,6 345678910 Average error(m) Number of anchors for positioning Particle Filter(2c) Particle Filter(2c) sin optimizar Figura 16. Error medio de posicionamiento. Distancia entre anchors = 10 m. n σ = 0.7. Miguel Eguizábal Alonso 48 4.4.3 Filtro de Kalman En este punto se van a observar los resultados de las modificaciones de detección de situaciones NLOS y de utilización de información acerca de las rutas de los targets para el filtro de Kalman. La detección de situaciones NLOS consiste en multiplicar por 1.5 el valor de covarianza cuando se construye la matriz de covarianza del ruido de medida R . En cuanto a la utilización de información acerca de las rutas, consiste en que cuando el target está en un nodo, se multiplica el valor de la aceleración por 5 cuando se construye la matriz Q . Se van a analizar varias configuraciones del modelo basado en planos y rutas del simulador, en función del número de anchors utilizados para el cálculo de la posición. En la figura 24 se muestran los resultados obtenidos para una distancia de 10 m entre anchors y un error residual de ranging de 0.7 n σ = . Los cuatro algoritmos siguen una evolución similar, aunque para más de 5 anchors, el filtro con la modificación de detección de NLOS y el filtro con ambas modificaciones consiguen errores más pequeños. La modificación de las rutas no modifica apenas el funcionamiento del filtro de Kalman, ya que obtiene prácticamente los mismos errores que el filtro de Kalman convencional. La modificación de la detección de situaciones NLOS funciona mejor al aumentar el número de anchors, ya que aumenta el número de anchors que se encuentran en situación de NLOS. Como la modificación de las rutas apenas modifica el funcionamiento, el filtro con la modificación de NLOS obtiene los mismos resultados que el filtro con ambas modificaciones. A continuación se presentan los resultados obtenidos disminuyendo el error residual de ranging. En la figura 25 se muestran los resultados para una distancia entre anchors de 10 m y un error residual de 0.3. 0,4 0,45 0,5 0,55 0,6 0,65 3 4 5 6 7 8 9 10 Average error(m) Number of anchors for positioning Kalman Filter Kalman Filter & NLOS Kalman Filter & routes Kalman Filter & NLOS & routes Figura 24. Error medio de posicionamiento. Distancia entre anchors =10 m. n σ = 0.7. Sistemas de localización avanzados en entornos interiores basados en tecnología UWB 49 Como se ha reducido el nivel de error residual, los anchors cercanos ofrecen estimaciones mucho más precisas que los anchors lejanos, por ello el número óptimo de anchors es 5 para todos los algoritmos, ya que añadiendo más de 5 anchors, se añaden anchors alejados y sus estimaciones tienen una gran desviación de ranging, provocando que el error medio de posicionamiento aumente. Al igual que en la misma configuración para error residual de 0.7 (figura 24), la modificación de las rutas no mejora el funcionamiento del filtro de Kalman convencional, obteniendo los mismos errores. La modificación de la detección de situaciones NLOS mejora el error del filtro de Kalman convencional para más de 3 anchors. A modo de resumen, se puede concluir que la mejora de utilización de información acerca de las rutas apenas modifica el funcionamiento del filtro de Kalman y no consigue mejorar el error. Sin embargo la modificación de detección de situaciones NLOS consigue mejorar el funcionamiento del filtro de Kalman. Esta modificación funciona mejor para un número elevado de anchors. El filtro con ambas modificaciones implementadas obtiene los mismos resultados que el filtro con detección de situaciones NLOS, lo cual es lógico, ya que la modificación de las rutas no produce cambios en el comportamiento del filtro convencional. 0,2 0,22 0,24 0,26 0,28 0,3 0,32 0,34 345678910 Average error(m) Number of anchors for positioning Kalman Filter Kalman Filter & NLOS Kalman Filter & routes Kalman Filter & NLOS & routes Figura 25. Error medio de posicionamiento. Distancia entre anchors =10 m. n σ = 0.3. Miguel Eguizábal Alonso 50 5. Conclusiones 5.1 Conclusiones del proyecto El objetivo de este proyecto era evaluar distintos algoritmos de localización para su uso en un sistema de seguimiento en interiores basado en tecnología UWB, además de proponer diversas mejoras basadas en el uso de información geográfica y estadística. Con el fin de observar el funcionamiento de los algoritmos, se han realizado simulaciones para diferentes situaciones y se han valorado y comentado en el apartado de resultados. Para poder implementar y evaluar las mejoras de los algoritmos fue necesario adaptar el simulador ya existente, basado en información estadística, a un escenario basado en paredes y rutas preestablecidas. En base a ambos escenarios se han evaluado los algoritmos considerados. La trilateración y el filtro de Kalman son algoritmos sencillos aunque presentan bastantes limitaciones, en particular la trilateración es muy sensible al error de ranging residual, por lo que requiere una elevada resolución en la estimación del TOA, mientras que el filtro de Kalman es muy sensible a las desviaciones en la estimación que se producen en anchors alejados o en situaciones de NLOS, por lo que presenta malos resultados para distancias entre anchors elevadas o niveles de error residual bajo. El filtro de partículas presenta por lo general los mejores resultados, aunque esto es debido a la gran similitud del modelo de error en las observaciones utilizado en el filtro y el modelo utilizado para generar el error de ranging, especialmente en el caso del modelo de 3 componentes optimizado mediante simulaciones. Sin embargo, en una situación real el modelo debería caracterizarse a través de una fase de calibración cuyos resultados no serán óptimos, con lo que su precisión real será menor, como puede observarse cuando se utiliza el modelo de 2 componentes sin optimizar. Los algoritmos propuestos en el marco de los proyectos PULSERS y EUWB, basados en MDS y DC respectivamente, presentan buenos resultados en todos los escenarios, con la ventaja añadida en el caso de DC de que es capaz de corregir en cierta medida los errores debido a desviaciones en caso de NLOS, por lo que tiene un mejor comportamiento en casos con distancia entre anchors elevada o error residual bajo. Un primer bloque de mejoras implementadas, propuestas en el proyecto EUWB para MDS y DC, fueron el prefiltrado y la ponderación de las estimaciones. El prefiltrado permite mejorar la precisión en el caso de que la velocidad de los móviles sea inferior a 1 m/s para el caso de tomar una medida por segundo, aunque se degrada de manera importante para velocidades superiores, por lo que no resulta muy adecuado para el seguimiento de targets móviles. Por lo que respecta a la ponderación, consiste en la aplicación de una serie de pesos en el algoritmo de optimización utilizado (SMACOF) calculados en base a la varianza de las estimaciones, con lo que se consigue ponderar en mayor medida las estimaciones más precisas, correspondientes a los anchors más cercanos y en visión directa. El uso de ponderaciones mejora en gran medida las prestaciones de MDS, con lo que el algoritmo WLSMDS presenta un mejor comportamiento que el DC. Sin embargo, en el caso de DC, el algoritmo WLS-DC no presenta ninguna mejora frente a LS-DC, ya que el propio algoritmo DC se encargaba de compensar las desviaciones de los anchors alejados o en NLOS. Sistemas de localización avanzados en entornos interiores basados en tecnología UWB 51 La principal aportación del proyecto se centra en la utilización de información geográfica, con el objetivo de mejorar la precisión de los algoritmos. La primera mejora consiste en identificar cuándo un enlace entre el target y uno de los anchors está en condiciones de NLOS y en aprovechar esa información. Esta información se utiliza para modificar el modelo de error de las observaciones en el caso del filtro de partículas y del filtro de Kalman, y la ponderación en el caso de WLS-MDS y WLS-DC. Esta modificación obtuvo bueno resultados especialmente en el filtro de partículas, ya que permite identificar la componente de error a utilizar (LOS/NLOS/NLOS2) en lugar de utilizar una suma ponderada de todas, además de que simplificaría la fase de calibración. Por otro lado, en los algoritmos WLSMDS y WLS-DC no supuso ninguna mejora, ya que la ponderación ya identificaba las situaciones de NLOS. La segunda mejora consiste en utilizar información acerca de las rutas de los targets. De cara a aprovechar esta información, se modificaron los modelos dinámicos en el filtro de Kalman y en el filtro de partículas. En el filtro de partículas se consiguió mejorar la precisión en algunas situaciones, mientras que en el filtro de Kalman no supuso ninguna mejora. 5.2 Mejoras del proyecto En este punto se van a exponer diversos proyectos que se podrían llevar a cabo en un futuro como continuación de este proyecto fin de carrera. Una posible vía de trabajo sería probar los algoritmos propuestos en este proyecto en dispositivos físicos reales, para poder evaluar el comportamiento de los mismos en una situación real. Habría que montar una red de anchors en un determinado escenario y posteriormente modelar ese escenario para poder aprovechar la información geográfica, como se ha hecho con los modelos utilizados en este PFC. También se debe disponer de nodos que actúen como targets, para moverlos por el escenario y realizar medidas para comprobar el comportamiento de los diferentes algoritmos. Otra vía de trabajo sería evaluar la carga computacional de los algoritmos. Un aspecto muy importante a la hora de evaluar algoritmos es la precisión obtenida, pero tampoco nos podemos olvidar de la carga computacional que tiene cada uno, ya que estos algoritmos se van a implementar en dispositivos portátiles, que tendrán una capacidad computacional limitada. Se trataría de evaluar el tiempo de ejecución de los diferentes algoritmos y comprobar que los dispositivos son capaces de computar la posición del target, antes de que se estimen de nuevo las distancias con los anchors. Para este estudio sería necesario conocer en profundidad la arquitectura de los dispositivos que se van a emplear. 5.3 Consideraciones personales La realización de este PFC me ha aportado mucha experiencia, tanto desde el punto de vista de aprender un nuevo lenguaje de programación como es C++, como desde el punto de vista de trabajar en el I3A, que ha sido una experiencia muy enriquecedora para mi futuro laboral. Por último, para poner el punto final a esta memoria, quiero agradecer a Juan, director del proyecto, por su disponibilidad, por su experiencia y por su forma de dirigir este proyecto, que me ha parecido perfecta. También quiero agradecer a Toni y a Ángela, por su confianza depositada en mí y por su ayuda prestada. Miguel Eguizábal Alonso 52 6. Referencias bibliográficas [1] J. Chóliz, A. Hernández, A. Valdovinos, “Architectures for Location Data Acquisition and Distribution in UWB Indoor Tracking Systems”, In Proc. 7th Workshop on Positioning, Navigation and Communications (WPNC’10), Marzo 2010. [2] J. Chóliz, A. Hernández, A. Valdovinos, “Evaluation of Algorithms for UWB indoor tracking”, sin publicar. [3] M. C. Almolda “Evaluación de algoritmos y estrategias de localización en sistemas UWB”, Proyecto Fin de Carrera, Universidad de Zaragoza, Febrero 2010. [4] G. Welch, G.Bishop, “An Introduction to the Kalman Filter”, University of North Carolina at Chapel Hill, Julio 2006. [5] F. Gustafsson, F. Gunnarsson, N. Bergman, U. Forssell, J. Jansson, R. Karlsson, P. Nordlund, “Particle Filters for Positioning, Navigation, and Tracking”, IEEE Transactions on signal processing, Vol. 50, Nº 2, Febrero 2002. [6] P. Nordlund, F. Gunnarsson, F. Gustafsson, “Particle Filters for Positioning in Wireless Networks”, In Proceedings of the XI European Signal Processing Conference (EURSIPCO’02), Septiembre 2002. [7] G. Destino, D. Macagnano, G. Abreu, R. Zeltik, W. Kotterman, R. Thomae, S. Severi, D. Dardari, V. Latosa, “Initial Localization and Tracking Algorithm”, Integrated Project EUWB, Deliverable D4.1.1, Junio 2009. [8] G. Destino, D. Macagnano, G. Abreu, J. Chóliz, A. Hernández, R. Zeltik, G. Shen, V. Latosa, “Enhanced LT algorithms with heterogeneous information – initial”, Integrated Project EUWB, Deliverable D4.1.2a, Mayo 2010. [9] J. de Leeuw, P.Mair, “Multidimensional Scaling Using Majorization: SMACOF in R”, Septiembre 2008. [10] A. M. Johansen, “SMCTC: Sequential Monte Carlo in C++”, Journal of Statistical Software, 30(6):1-41, Abril 2009. [11] A. Álvarez, L. de Celis, G. Destino, D. Xu, S. Wang, R. Zeltik, “Implementation of the enhanced LT engine with mobility management (LDR and HDR)”, Integrated Project EUWB, Deliverable D4.3.2a, Octubre 2009. [12] H. Schildt, “The complete reference C++”, McGraw-Hill, 1998.