Genetic Algorithm optimization and characterization of noise, clock and Non-Line-of-Sight uncertainties in time-based positioning systems

Zusammenfassung

El desarrollo e implementación de futuras aplicaciones construidas sobre tecnologías de navegación autónoma está fuertemente conectado a sistemas de posicionamiento de altas prestaciones que puedan localizar objetivos con gran exactitud, estabilidad y robustez en entornos con condiciones de operación severas. Los Sistemas de Posicionamiento Locales (LPS) se erigen como tecnologías prometedoras para acometer estos requerimientos, gracias a la implementación adaptable de múltiples sensores de la arquitectura de posicionamiento seleccionada en las proximidades de los objetos a los que proporcionar el servicio de localización, disminuyendo con ello los efectos adversos sobre las señales de posicionamiento y maximizando el rendimiento global del sistema. Sin embargo, el comportamiento de los LPS es directamente dependiente de la ubicación de los sensores de las arquitecturas de posicionamiento, estando este problema de optimización caracterizado dentro de la categoría NP-Hard, siendo imposible alcanzar soluciones exactas en tiempo polinómico. La tecnología de posicionamiento implementada en los LPS también afecta masivamente al rendimiento global del sistema. Los sistemas basados en mediciones temporales se han extendido universalmente gracias a su solución de compromiso entre exactitud, efectividad, estabilidad, flexibilidad, robustez y ratio entre coste y comportamiento del sistema deseado. Se han utilizado predominantemente las arquitecturas TOA, TDOA y TDOA asíncronas. No obstante, no existen modelos para establecer comparativas entre el rendimiento de cada arquitectura para aplicaciones de altos requerimientos en LPS. El objetivo y motivación de esta tesis doctoral es el desarrollo de un procedimiento novedoso para optimizar la colocación de sensores de sistemas de posicionamiento basados en mediciones temporales para aplicaciones de LPS de altas prestaciones en entornos tridimensionales complejos. Unido a ello, en esta disertación se aborda la generación de nuevos modelos para caracterizar las principales fuentes de error en los sistemas basados en mediciones temporales. A partir de la metodología propuesta, se establecen comparativas entre las arquitecturas de posicionamiento, maximizando el rendimiento de cada una de ellas en el entorno en cuestión, y permitiendo el diseño bajo demanda de LPS y la estimación de sus capacidades con anterioridad a su implementación real. Para completar este objetivo, el primer paso fue el desarrollo de una herramienta heurística basada en Algoritmos Genéticos (GA) para optimizar distribuciones de sensores de sistema de posicionamiento de acuerdo a un conjunto de requerimientos predefinidos. En esta tesis se presenta un nuevo GA con una codificación de tipo “scaling” capaz de realizar optimizaciones tridimensionales en entornos complejos, con independencia de la definición de las posibles localizaciones de los sensores de la arquitectura de posicionamiento (NLE) y de los objetivos a ubicar (TLE). El segundo paso es la creación de modelos de exactitud basados en la CRLB para estimar las máximas capacidades de sistemas de posicionamiento basados en mediciones temporales, independientemente del algoritmo de posicionamiento utilizado. La principal ventaja de este método es su cimentación sobre la flexibilidad a la hora de caracterizar comportamientos heterocedásticos en las varianzas asociadas a los factores que componen el problema de estimación. Este factor es especialmente importante en LPS, donde cada sensor de la arquitectura está sometido a condiciones de operación diferentes. Inicialmente, se presenta una nueva adaptación de la CRLB para incertidumbres introducidas por ruido en las mediciones temporales para arquitecturas TDOA asíncronas. Convencionalmente, los modelos de ruido han sido aplicados a sistemas TOA y TDOA, donde los trayectos de las señales de posicionamiento son directos entre objetivos y sensores. Para sistemas TDOA asíncronos, las técnicas de retransmisión deben ser embebidas dentro del modelo, junto con la caracterización de las pérdidas de propagación introducidas. Entre los sistemas asíncronos, las simulaciones demuestran que las arquitecturas A-TDOA superan en rendimiento al resto en términos de exactitud. A continuación, los errores de los relojes presentes en los instrumentos de medición y las incertidumbres generadas por el ruido fueron modelizados conjuntamente en base a una nueva caracterización de la CRLB. Con este modelo y la optimización mediante GA con codificación mediante Escalamiento se estableció un banco de pruebas para comparar las arquitecturas TOA, TDOA y A-TDOA en entornos tridimensionales. Después de las optimizaciones, la arquitectura A-TDOA superó considerablemente al resto de sistemas debido a la eliminación de los errores relacionados con el sincronismo –desviación inicial de sincronización y lapso temporal desde la última sincronización– y la reducción de las incertidumbres inducidas por trayectos de las señales más extensos que en el resto de sistema, convirtiéndose en la única arquitectura candidata para ser implementada en LPS de altas prestaciones. Finalmente, las condiciones de operación NLOS fueron modelizadas en la CRB para estimación de exactitud. La nueva propuesta utiliza un nuevo algoritmo de rastreo para cuantificar las condiciones NLOS en cada uno de los enlaces de comunicación para las diferentes arquitecturas de posicionamiento en entornos complejos tridimensionales. Adicionalmente, se desarrolló un novedoso enfoque para detectar y cuantificar los efectos adversos del multipath debido a la presencia de objetos en la zona de Fresnel y la zona de Minimum Line-of-Sight path para cada enlace de comunicaciones. La combinación de las todas técnicas propuestas permite la realización de optimizaciones multiobjetivo para exactitud, multipath, y coste en estos sistemas de posicionamiento.