Repositorio Institucional de Documentos

INGENIER´ IA SUPERIOR EN TELECOMUNICACI´ ON Proyecto de fin de carrera: Dise˜no de secuencias y filtro para localizaci´on cooperativa Autor: David Aguilar P´erez Director: Satyam Dwivedi Post-doc in KTH School of Electrical Engineering Department of Signal Processing Ponente: Antonio Valdovinos Bardaj´ı Diciembre 2012 Agradecimientos A mi supervisor, Satyam Dwivedi, por darme la oportunidad de realizar mi proyecto final de carrera en el Departamento de Procesado de Se˜nal de la Escuela de Ingenier´ıa Electrica del Instituto Real de la Tecnolog´ıa de Estocolmo, y por su excelente guiado y asesoramiento dirante toda la duraci´on del proyecto. Tambi´en mencionar su disponibilidad y flexibilidad, permiti´endome trabajar a mi manera, incluso trabajar desde Espa˜na. A toda la gente de Kista y de Norrt¨alje que han estado a mi lado durante el desarrollo del proyecto. Han sido realmente muy buenos compa˜neros de trabajo y han sido de una enorme ayuda y apoyo. Tambi´en a David Sim´on, por las muchas horas trabajando juntos durante todo el a˜no. A Diego y Juan Carlos por hacer que el tramo final del proyecto, y la traducci´on del mismo, fuera menos tedioso gracias al buen ambiente de trabajo. A Loreto por todo su apoyo y sus buenos consejos. Y en general, a todos mis compa˜neros de clase y amigos por estar ah´ı e interesarse por el proyecto. Finalmente, mi mayor agradecimiento a mis padres, Javier y Pilar, y a mi hermana, Nerea, por darme todas las facilidades y el apoyo necesario para realizar el proyecto en Suecia, con todas las dificultades que ello conllevaba. iii Abstract Dise˜no de secuencias y filtro para localizaci´on cooperativa En sistemas de localizaci´on cooperativa, los dispositivos de una red transmiten pulsos en un determinado orden preestablecido. Cada dispositivo (nodo) realiza mediciones del tiempo de llegada de los distintos pulsos recibidos para localizar a los otros nodos de la red. Este proyecto ha tratado algunos aspectos de la localizaci´on cooperativa basada en secuencias. La primera parte del proyecto define el sistema propuesto y las secuencias de transmisi´on de pulsos. Despu´es se discuten las restricciones que el mismo sistema impone y se propone un algoritmo de generaci´on de una secuencia que se adapte al n´umero de nodos de una red. Una vez expuesto este algoritmo, se extiende para que sea capaz de generar todas las secuencias posibles para cualquier red. La segunda parte trata sobre el dise˜no del filtro que va a procesar las mediciones que los nodos toman, para estimar las distancias entre todos los nodos de la red. Cada nodo ejecuta un filtro de Kalman. Se muestran varias simulaciones para este modelo. Se discute tambi´en coste computacional requerido por el filtro, proponiendo diversas formas de reducirlo. Se realiza una comparaci´on entre varios m´etodos de descomposici´on de matrices, descomposici´ones QR y Cholesky. Finalmente, se discute la relaci´on del coste computacional con el n´umero de nodos que compone la red. v ´ Indice general 1 Introducci´on 1 1.1 La localizaci´on, perspectiva hist´orica . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 Introducci´on hist´orica . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Localizaci´on cooperativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Estado del arte: ’3-way ranging’ . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Plandelproyecto................................ 7 2 Localizaci´on cooperativa programada 9 2.1 Elconcepto ................................... 9 2.2 Lasecuencia................................... 11 2.3 M´ınimo n´umero de transmisiones de pulsos . . . . . . . . . . . . . . . . . 13 2.4 Generador de secuencias: una secuencia . . . . . . . . . . . . . . . . . . . 15 2.5 Generador de secuencias: todas las posibles secuencias . . . . . . . . . . . 17 2.6 Tiempodeprocesado.............................. 20 2.7 Resumen..................................... 20 3 El filtro de Kalman y las secuencias 21 3.1 Redde3nodos................................. 23 3.2 Escenarios de 4 y 5 nodos . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2.1 4nodos ................................. 28 3.2.2 5nodos ................................. 30 4 Complejidad computacional en cada nodo 35 4.1 Filtro ...................................... 35 4.1.1 Establecimiento del problema . . . . . . . . . . . . . . . . . . . . . 35 4.1.2 Innovaciones .............................. 36 4.1.3 Estimaci´on del estado . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.1.4 GananciaKalman ........................... 39 i ii ´ INDICE GENERAL 4.1.5 Matriz de correlaci´on del error de predicci´on de estado . . . . . . . 39 4.1.6 Condiciones iniciales . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.1.7 Resumen ................................ 41 4.2 Complejidad del filtro de Kalman . . . . . . . . . . . . . . . . . . . . . . . 41 4.3 Inversi´on de la matriz de la ganancia Kalman . . . . . . . . . . . . . . . . 43 4.3.1 Sustituci´on hacia adelante y hacia atr´as . . . . . . . . . . . . . . . 44 4.3.2 Complejidad de la sustituci´on hacia atr´as . . . . . . . . . . . . . . 45 4.3.3 Descomposici´on e inversi´on . . . . . . . . . . . . . . . . . . . . . . 46 4.3.3.1 Inversi´on mediante la descomposici´on QR . . . . . . . . . 46 4.3.3.2 Inversi´on con la descomposici´on de Cholesky . . . . . . . 47 4.3.3.3 Complejidad de la descomposici´on de Cholesky . . . . . . 48 4.4 Coste computacional total del filtro . . . . . . . . . . . . . . . . . . . . . . 50 4.5 Complejidad del sistema con el aumento de nodos en la red . . . . . . . . 52 5 Conclusiones 55 5.1 L´ıneasfuturas.................................. 56 Referencias 59 ´ Indice de figuras 1.1 Escenario con cuatro anclajes y cuatro agentes . . . . . . . . . . . . . . . 3 1.2 Transmisiones de pulsos en un escenario compuesto de dos nodos . . . . . 6 2.1 Diagrama temporal de un escenario compuesto por tres nodos . . . . . . . 10 2.2 Conexiones en un escenario formado por cuatro dispositivos . . . . . . . . 13 2.3 Comparaci´on del n´umero de transmisiones de pulsos entre ’3-way ranging’ y localizaci´on cooperativa programada . . . . . . . . . . . . . . . . . . . . 14 2.4 ´ Arboldelalgoritmo............................... 19 2.5 ´ Arboldelalgoritmo............................... 20 3.1 Diagrama temporal de transmisiones para tres nodos con secuencia 1-2- 3-2-1-3...................................... 22 3.2 Escenario con tres nodos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3 Movimiento de tres nodos . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.4 Evoluci´on de las distancias en 250 s medidas en el nodo 1 . . . . . . . . . 27 3.5 Evoluci´on de las distancias en 250 s . . . . . . . . . . . . . . . . . . . . . 27 3.6 Movimiento estimado de los tres nodos . . . . . . . . . . . . . . . . . . . . 29 3.7 Diagrama temporal de una red de cuatro nodos . . . . . . . . . . . . . . . 29 3.8 Movimiento estimado de los cuatro nodos . . . . . . . . . . . . . . . . . . 30 3.9 Distancias estimadas de los cuatro nodos . . . . . . . . . . . . . . . . . . . 31 3.10 Diagrama temporal de una red de cinco nodos . . . . . . . . . . . . . . . . 31 3.11 Movimiento estimado de los cuatro nodos . . . . . . . . . . . . . . . . . . 32 3.12 Distancias estimadas de los cinco nodos . . . . . . . . . . . . . . . . . . . 33 4.1 Complejidad con el aumento de los nodos en una red . . . . . . . . . . . . 53 iii 21.1. La localizaci´on, perspectiva hist´orica Con la aparici´on de las radioayudas, diversos sistemas de posicionamiento fueron desarrollados. El primer sistema que empleaba ondas de radio como medio para calcular la posici´on fue la radiogoniometr´ıa. Estaba basado en una antena cuadrada que era capaz de calcular la direcci´on de la se˜nal entrante debido a su diagrama de radiaci´on. Las referencias eran balizas situadas en tierra firme en posiciones conocidas. Sabiendo la distancia a dos balizas, la posici´on pod´ıa ser calculada. M´as adelante, varias versiones de este sistema fueron apareciendo. Algunos empleaban antenas rotatorias, otros usaban entramados de antenas, y algunos otros inclu´ıan alguna ayuda electr´onica para mejorar la precisi´on. A d´ıa de hoy, este tipo de sistemas se utiliza en sistemas de seguridad. La siguiente generaci´on de sistemas de transmisi´on la formaban los sistemas hiperb´olicos (1). LORAN (LOng RAnge Navigation) es el sistema que sigue este principio m´as conocido. Est´a basado en la medida de la diferencia entre tiempos de llegada de distintas se˜nales procedentes de diversas balizas situadas en posiciones conocidas. La diferencia de tiempos crea lugares geom´etricos en el espacio (hiperboloides) de posibles posiciones. Mediante la intersecci´on de un m´ınimo de tres hiperboloides la posici´on puede ser conocida. Por lo tanto, se necesitan un m´ınimo de tres balizas de referencia para realizar la localizaci´on. El sistema LORAN se sigue utilizando en la actualidad para navegaci´on ya que aun existen balizas situadas en las costas para su utilizaci´on. El sistema de posicionamiento m´as reciente lo componen los sistemas satelitales. GPS (Global Positioning System), perteneciente a los Estados Unidos es el m´as conocido. En Europa, un sistema similar (Galileo) est´a siendo desarrollado, siguiendo los mismos principios (1). Se tratan de sistemas donde la comunicaci´on se produce entre un dispositivo en la superficie terrestre, y diversos sat´elites, siendo todos estos enlaces descendentes. Se basan en estimaci´on esf´erica. Cada dispositivo, con cada se˜nal que recibe de cada sat´elite, crea un lugar geom´etrico (esfera) de posibles posiciones. De esta forma, mediante la intersecci´on de un m´ınimo de cuatro esferas, la posici´on es calculada. Un m´ınimo de cuatro sat´elites han de estar visibles en el momento de realizar el posicionamiento, aunque, tal y como est´an distribuidos los sat´elites, entre 27 y 28 a lo largo de la ´orbita geoestacionaria, los sat´elites con visi´on directa oscilan entre cinco y ocho. A d´ıa de hoy, existen muchos sistemas de posicionamiento y localizaci´on diferentes, cada uno con sus propias propiedades y aplicaciones, todos ellos basados en las referencias. Algunos sistemas emplean referencias est´aticas con posiciones fijas y conocidas, llamadas anclajes, y algunos otros se ayudan de referencias m´oviles con posiciones que no son fijas, conocidas como agentes. Algunos sistemas utilizan s´olo anclajes, s´olo agentes, o una combinaci´on de ambos. Por ejemplo, anclajes pueden ser los astros en navegaci´on astron´omica, las balizas en los sistemas hiperb´olicos, o los sat´elites en GPS o Galileo, mientras que los agentes pueden ser cada dispositivo a posicionar, como puede ser un receptor GPS que se comunique con otros receptores. La figura 1.1 muestra un escenario con varios anclajes y agentes que se comunican entre ellos para Cap´ıtulo 1. Introducci´on 3 1 2 3 t12 t13 t23 Node 1 Node 2 Time t12 t12 t12 RTT D 1 2 t12 1 2 3 4 1 3 2 1 4Schedule: Node 1 Node 2 Node 3 Node 4 1 2 4 35 6 12 43 5 6 1 3 4 25 6 12 43 5 6 Node 1 Node 2 Node 3 T31 T32 T33 Time 1 3 3 2 3 1 3 2 Schedule 1 1 3 2 Schedule 2 2 3 1 2 Schedule 6 ··· 100 0 0 0 0 1 1 110 0 0 0 0 1 1 101 0 0 0 0 1 1 1 1 0 1 0 0 0 1 1 110 0 1 0 0 1 1 110 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 111 1 0 0 1 1 1 111 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 111 10 0 0 1 1 101 0 0 0 1 1 1 101 0 1 0 1 1 1 101 0 1 1 1 1 1 111 0 1 1 1 1 1 101 0 1 01 1 1 1 0 1 0 1 1 1 1 1 1 2 3 4 2 1 2 4 1Schedule: Node 2 Node 3 1 3 4 25 5 12 43 6 7 Anchors Agents Communication Movement Figura 1.1: Escenario con cuatro anclajes y cuatro agentes llevar a cabo el posicionamiento. La comunicaci´on entre agentes para llevar a cabo la localizaci´on y el posicionamiento es conocida como localizaci´on cooperativa, ya que cada agente coopera con los dem´as compartiendo con ellos algunas medidas realizadas con el mismo. De esta forma, se permite de alguna manera que agentes con posiciones desconocidas tomar y compartir mediciones con otros dispositivos con posiciones tambi´en desconocidas (2). 1.2 Localizaci´on cooperativa La principal caracter´ıstica de la localizaci´on cooperativa es la existencia de comunicaci´on entre agentes en una red. En esta comunicaci´on, varios datos relevantes relacionados con cada agente son transmitidos a los dem´as agentes para llevar a cabo el posicionamiento. Existen principalmente dos tipos de sistemas de localiaci´on cooperativa. El primero se compone de sistemas formados por anclajes y agentes donde existen dos tipos de comunicaci´on, anclaje - agente y agente - agente. El segundo lo forman las redes formadas exclusivamente por agentes, donde todos los componentes son dispositivos m´oviles que se comunican entre ellos. La localizaci´on cooperativa presenta varias ventajas comparada con los sistemas de localizaci´on est´andar. La principal ventaja es su buen funcionamiento en entornos hostiles, donde es imposible obtener informaci´on externa. Por ejemplo, en el interior de una cueva o edificio, donde se˜nales externas no pueden penetrar hasta los nodos de la red. Otra ventaja importante es la reducci´on del consumo de energ´ıa. Estas redes de nodos suelen emplearse en escenarios de reducido tama˜no, luego las distancias entre los nodos es peque˜na y la potencia de transmisi´on requerida se ve reducida comparada con la necesaria para establecer contacto con un sat´elite o una baliza. La localizaci´on cooperativa puede ser empleada en diversas aplicaciones. Este tipo de sistemas pueden utilizarse en seguimiento de animales o log´ıstica (2). Se pueden emplear para localizar maquinaria, veh´ıculos, mercanc´ıas . . . Tambi´en puede emplearse en el seguimiento de las condiciones de almacenaje en grandes almacenes, o en redes de almacenes. Otra situaci´on donde la localizaci´on cooperativa puede ejercer un papel 41.2. Localizaci´on cooperativa importante es en equipos de rescate, ya sean bomberos, polic´ıa, ej´ercito . . . El proceso de localizaci´on consiste en dos fases: la fase de medida, durante la cual los agentes toman mediciones itra-nodo o inter-nodo utilizando sensores, y la fase de actualizaci´on, durante la cual los agentes, o nodos, infieren sus propias posiciones conociendo su posici´on previa, y varias mediciones. La precisi´on durante el posicionamiento depende fuertemente de la calidad de las mediciones que son afectadas por el medio, la topolog´ıa, propagaci´on multicamino, ruidos, deriva de reloj, etc (3). En el caso de la localizaci´on, la posici´on de cada agente ha de ser conocida. Una forma de conocerla es midiendo la distancia entre cada nodo y los dem´as que componen la red, y complementarlo con la medici´on del ´angulo de llegada de cada se˜nal entrante a cada agente. A continuaci´on se introducen diversas t´ecnicas de medici´on de estas dos magnitudes. Medici´on de distancias: potencia de la se˜nal recibida (RSS: Received Signal Strength) La potencia de la se˜nal recibida en cada agente depende de la potencia inicial de la se˜nal en el agente transmisor, o posici´on de referencia, P0, y de la distancia entre los dos agentes, o entre el agente y el anclaje. La potencia de la se˜nal decae cuadr´aticamente con la distancia. Midiendo esta potencia en el receptor, y conociendo P0, la distancia puede ser calculada. La ecuaci´on 1.1 permite calcular esa distancia: P(d) = P0−10nplog d d0 (1.1) Siendo npel coeficiente de perdidas del medio, y d0la distancia de referencia del nodo transmisor donde se ha medido P0. Esta t´ecnica no es compleja, pero no es muy precisa y cualquier variaci´on en el medio afecta de forma muy significativa al coeficiente de p´erdidas y, por lo tanto, a la potencia recibida. Otro aspecto que modifica la potencia de la se˜nal son las bater´ıas del transmisor. La se˜nal de referencia ser´a menor de la esperada si el transmisor tiene poca bater´ıa, y ello influir´a a la potencia recibida. Para corregir estos aspectos, se ha de transmitir m´as informaci´on entre nodos para que estos la procesen y el posicionamiento sea correcto. Medici´on de distancias: Tiempo de llegada (TOA: Time of arrival) TOA es una t´ecnica m´as precisa que RSS para calcular distancias entre dos agentes. Se basa en calcular el tiempo entre que se emite la se˜nal en el transmisor y llega al receptor. La metodolog´ıa es la siguiente. Un nodo transmite una se˜nal al medio. Los dem´as nodos de la red reciben esa se˜nal y retransmiten una respuesta a la misma. Para que la reciba el primer nodo. El nodo transmisor durante este tiempo ha estado esperando hasta la llegada de las respuestas. Con un temporizador interno, mide el tiempo que ha Cap´ıtulo 1. Introducci´on 5 transcurrido desde la transmisi´on hasta la recepci´on de las respuestas. Una vez obtenidos estos tiempos, calcula las distancias con la ecuaci´on 1.2. t=2d−D c(1.2) Donde tes el tiempo que mide el nodo, des la distancia entre nodos, Des el retardo que se produce entre la recepci´on del broadcast y el env´ıo de la respuesta en cada nodo, magnitud que es conocida, y ces la velocidad de la propagaci´on de la se˜nal en el medio. Esta t´ecnica presenta el problema de la propagaci´on multicamino. Generalmente la primera se˜nal recibida es la correspondiente a la trayectoria directa entre nodos, pero puede haber situaciones en las que la velocidad de propagaci´on de la se˜nal en la trayectoria directa sea menor que en alguna otra trayectoria provocada por alguna reflexi´on. Si este caso ocurre, la se˜nal reflejada llega antes al nodo receptor, provocando una falsa medici´on. Se˜nales de banda ancha pueden ser empleadas para reducir este aspecto (2; 3; 4). Las se˜nales de banda ancha presentan mejor resoluci´on temporal y entonces, la componente de trayectoria directa puede ser separada de otras contribuciones. A pesar de esto, es muy dif´ıcil tratar con se˜nales tempranas multicamino. Existe una modificaci´on de esta t´ecnica llamada diferencia de tiempos de llegada (TDOA: Time diference of arrival). Se basa en el mismo principio que TOA pero con la variante de que la medida que toman ahora los nodos es la diferencia de tiempos entre las llegadas de las respuestas procedentes de los otros agentes de la red, y a partir de ah´ı, calcular las distancias. Medici´on del ´angulo: ´ Angulo de llegada (AOA: Angle of arrival) Conocer la distancia entre nodos no es suficiente para saber la posici´on exacta de los mismos. Con una distancia conocida, d, un agente puede ser situado a lo largo de una circunferecia centrada en su posici´on y de radio d. Medir el ´angulo por el que llegan las se˜nales al dispositivo receptor permite saber la posici´on exacta en esa circunferencia. Si el receptor est´a compuesto por un entramado de msensores, ser´a capaz de obtener el ´angulo por el que se recibe la se˜nal debido a su diagrama de radiaci´on. El sistema es similar al aparato auditivo humano. EL cual, mediante dos sensores, una persona puede saber el ´angulo por donde le llega cada sonido. Este principio, trasladado a este problema, permite a los dispositivos estimar el ´angulo de llegada. Una breve introducci´on a la localizaci´on cooperativa se ha expuesto. La siguiente secci´on presenta el estado del arte del sistema que va a ser discutido durante este proyecto. 61.3. Estado del arte: ’3-way ranging’ 1 2 3 t12 t13 t23 Node 1 Node 2 Time t12 t12 t12 RTT D 1 2 t12 1 2 3 4 1 3 2 1 4Schedule: Node 1 Node 2 Node 3 Node 4 1 2 4 35 6 12 43 5 6 1 3 4 25 6 12 43 5 6 Node 1 Node 2 Node 3 T31 T32 T33 Time 1 3 3 2 3 1 3 2 Schedule 1 1 3 2 Schedule 2 2 3 1 2 Schedule 6 ··· 100 0 0 0 0 1 1 110 0 0 0 0 1 1 101 0 0 0 0 1 1 110 1 0 0 0 1 1 110 0 1 0 0 1 1 110 1 0 0 0 1 1 111 1 0 0 0 1 1 111 1 0 0 1 1 1 111 1 0 1 0 1 1 1 111 1 1 0 1 1 1 111 10 0 0 1 1 101 0 0 0 1 1 1 101 0 1 0 1 1 1 101 0 1 1 1 1 1 111 0 1 1 1 1 1 101 0 1 01 1 1 101 0 1 1 1 1 1 1 2 3 4 2 1 2 4 1Schedule: Node 2 Node 3 1 3 4 25 5 12 43 6 7 Figura 1.2: Transmisiones de pulsos en un escenario compuesto de dos nodos 1.3 Estado del arte: ’3-way ranging’ Uno de sistemas de localizaci´on cooperativa mas extendidos es el conocido ’3-way ranging’. Este sistema se basa en la t´ecnica de tiempo de llegada (TOA) para calcular las distancias entre dispositivos. ’3-way ranging’ est´a dise˜nado para funcinar en redes de nnodos los cuales est´an en comunicaci´on directa en un determinado escenario. Esta metodolog´ıa se basa en la transmisi´on de pulsos por parte de cada nodo hacia los dem´as componentes de la red, y esperar a recibir los pulsos de respuesta de los mismos. Se supone un escenario que contiene dos nodos. Cuando el sistema empieza a funcionar, el nodo etiquetado como nodo 1 transmite un pulso broadcast a la espera que lo reciban los dem´as componentes de la red, en este caso, el nodo etiquetado como nodo 2. Una vez el segundo nodo recibe el pulso, lo procesa, con un tiempo de procesado conocido por ambos nodos, y env´ıa otro pulso de respuesta. Esta vez, es el nodo 1 el que lo recibe. El nodo 1 mide el tiempo transcurrido entre el env´ıo y la recepci´on y calcula la distancia entre ambos. De esta forma, el primer nodo ya conoce su distancia con el segundo, pero el segundo no, luego es necesario que el nodo 1 vuelva a transmitir de nuevo otro pulso, tras un tiempo de procesado conocido, para que, mediante el mismo proceso anterior, el segundo nodo tambi´en conozca su distancia con el primero. Esto es, tres transmisiones de pulsos son necesarias para un completo conocimiento de cada nodo de las distancias de todos los dem´as componentes de la red con s´ı mismo. El nombre de esta t´ecnica proviene de este hecho. La figure 1.2 muestra gr´aficamente el proceso entre dos nodos. D es el restardo de procesado, t12 es el tiempo de propagaci´on entre nodos, y RTT Cap´ıtulo 1. Introducci´on 7 (Round Trip Time) es el tiempo entre la transmisi´on y la recepci´on en cada nodo. Este procedimiento puede ser trasladado a escenarios con un mayor n´umero de nodos. La metodolog´ıa es la misma que en el escenario con dos nodos para cada enlace directo entre cada pareja de agentes. En un escenario con tres nodos, el proceso debe ser realizado tres veces, dado que el n´umero de enlaces directos entre nodos aumenta hasta tres. Con cuatro dispositivos, los enlaces directos suben a seis, y as´ı sucesivamente. El n´umero de veces que se ha de realizar el ’3-way ranging’ depende del n´umero de nodos, y puede ser calculado mediante la ecuaci´on 1.3: cn 2=n! 2! (n−2) =n(n−1) 2(1.3) De este modo, como son necesarios tres tranmisiones para tener conocimiento completo de las distancias por cada enlace, el n´umero total de transmisiones necesarias es: Ntx = 3cn 2=3 2n(n−1) (1.4) Realizando ’3-way ranging’ solamente la distancia es calculada. Para tener un completo conocimiento de la posici´on de los dem´as dispositivos del escenario se requiere dotar a los mismos con alguna caracter´ıstica extra, como la ya mencionada anteriormente, un entramado de antenas para permitir medir el ´angulo de llegada de las se˜nales. Conociendo el ´angulo y la distancia la posici´on ya es conocida. Otra forma de solucionar esta cuesti´on es dotar a los nodos de cierta capacidad de procesado de se˜nal y de este modo ser capaz de realizar un seguimiento de cada nodo. Una forma de obtener todas las distacias se propone en (5). M´as adelante, diversos aspectos de este m´etodo van a ser discutidos. 1.4 Plan del proyecto Durante los siguientes cap´ıtulos se propone una mejora de este m´etodo de posicionamiento. El primer cap´ıtulo trata sobre la secuencia y su aplicaci´on al sistema. Despu´es, un algoritmo basado en varias restricciones dadas por el mismo sistema es propuesto para generar una secuencia dependiendo del tama˜no de la red. Una vez obtenido este algoritmo, se propone otro, basado en el mismo principio, para calcular todas las posibles secuencias para cada n´umero de dispositivos. El siguiente cap´ıtulo habla sobre el procesado de se˜nal necesario en cada dispositivo. Se introduce la implementaci´on de un modelo adaptado al problema del filtro de Kalman en cada nodo de la red. Varias simulaciones han sido realizadas para escenarios de tres, cuatro, y cinco nodos, mostrando los resultados en diversas gr´aficas. El posterior cap´ıtulo. La parte final de este proyecto trata sobre la complejidad computacional que soporta cada 81.4. Plan del proyecto dispositivo, y se discuten maneras eficientes de la implementaci´on del filtro de Kalman en cada uno de ellos. Por ´ultimo, se realiza un estudio sobre el incremento de la carga computacional con respecto al tama˜no de la red. Cap´ıtulo 2 Localizaci´on cooperativa programada 2.1 El concepto En el cap´ıtulo anterior se ha introducido una idea b´asica de posicionamiento basada en la transmisi´on de tres pulsos por par de dispositivos en una determinada red de nodos. Este sistema trabaja correctamente tanto en entornos interiores como en entornos exteriores. La simplicidad es la principal caracter´ıstica del sistema, esta simplicidad tiene como consecuencia que otros aspectos del mismo puedan ser mejorables. En este caso, mediante el procedimiento del ’3-way ranging’, cada nodo es capaz solamente de conocer la distancia entre s´ı mismo y los dem´as, desconociendo por completo las distancias existentes entre los dem´as dispositivos. Este aspecto puede ser mejorado de tal forma que cada nodo tenga un conocimiento completo de todas las distancias asociadas a todos los enlaces directos entre los dispositivos de la red, dotando a cada nodo de una mayor informaci´on del escenario. Otro aspecto a mejorar es la reducci´on del n´umero de emisiones de pulsos con el fin de obtener una reducci´on del gasto de energ´ıa. La transmision de tres pulsos por enlace directo es inviable en redes con un alto n´umero de componentes, con lo cual es importante que este n´umero de transmisiones se vea reducido considerablemente para redes de gran tama˜no. Para satisfacer estos dos aspectos, se propone fijar una secuencia de transmisiones de pulsos programada adaptada al n´umero de dispositivos, esto es, fijar un orden de transmisi´on de se˜nales por parte de cada nodo. Esta secuencia de transmisi´on es conocida por todos ellos y, aplicando cierto procesado de se˜nal, se obtienen los resultados. Al dotar a cada dispositivo de un procesamiento de se˜nal, la simplicidad se ve reducida, pero por contra, mejores resultados son obtenidos y, como se ver´a m´as adelante, el n´umero de transmisiones totales se ver´a disminuido considerablemente en redes grandes. La figura 2.1 muestra un diagrama temporal b´asico de un escenario compuesto por tres nodos. La secuencia empleada en esta figura es 1,2,3,2,1,3. Esta secuencia se 9 10 2.1. El concepto Node 1 Node 2 Node 3 Time D D D D D T14 T13 T12 T11 T21 T22 T23 T31 T32 T33 t12 t23 t13 Figura 2.1: Diagrama temporal de un escenario compuesto por tres nodos repite c´ıclicamente. En este caso, los nodos ya no miden el tiempo de propagaci´on de los pulsos en cada enlace, sino que miden la diferencia de tiempo entre llegada de los diferentes pulsos procedentes de cada nodo. Esta diferencia de tiempos se muestra en la figura 2.1 como Tij, donde ies el n´umero del nodo en la secuencia, y jes el n´umero de medida durante la misma. En este ejemplo, i, j = 1,2,3. Otro aspecto a tener en cuenta es el tiempo de procesado en cada nodo, dado que tiene que ser incluido en el procesado de se˜nal de cada dispositivo para evitar resultados err´oneos. Esa configuraci´on propuesta va a ser usada durante toda la memoria. Una vez medidas estas diferencias de tiempos de llegada de los distintos pulsos procedentes de los dem´as nodos, cierto procesamiento de datos ha de llevarse a cabo para que cada dispositivo conozca los tiempos de propagaci´on de los pulsos en la totalidad de los enlaces directos, que es en lo que se basa el ’3-way ranging’. De las medidas tomadas en este sistema, se obtienen distintos sistemas de ecuaciones, teniendo como inc´ognitas estos tiempos de propagaci´on. La tabla 3.1 contiene los sistemas de ecuaciones correspondientes a cada nodo, en el escenario expuesto anteriormente. Pueden ser deducidas observando la figura 2.1 con detenimiento. Las inc´ognitas tij corresponden a los tiempos de propagaci´on entre los pulsos transmitidos por el nodo iy el nodo j,D corresponde al tiempo de procesado en cada nodo. Estos sistemas pueden ser reescritos en forma matricial como: Tm=Cmt+Dm(2.1) Cap´ıtulo 2. Localizaci´on cooperativa programada 11 Node 1 Node 2 Node 3 T11 = 2t12 +D T12 = 2t23 + 2D T12 =t12 +t23 −t13 +D T21 =t23 +t13 −t12 +D T22 =t13 +t12 −t23 +D T23 = 2t13 + 2D T31 = 2t13 + 2D T32 =t13 +t23 −t12 +D T33 = 2t23 + 2D Tabla 2.1: Sistemas de ecuaciones en cada nodo Donde Tmes el vector de medici´on en el nodo m,Cmes la matriz de medici´on asociada al nodo m,Dmes el tiempo de procesado en el nodo m, y t= [t12, t13, t23]Tes el vector de inc´ognitas. Por lo tanto, en el nodo 1: T1=   T11 T12 T13   C1=   2 0 0 −111 1−1 1   T1=   1 1 1   (2.2) En el nodo 2: T2=   T21 T22 T23   C2=   0 0 2 2 0 0 −111   T2=   2 2 1   (2.3) En el nodo 3: T3=   T31 T32 T33   C3=   1−1 1 0 0 1 1 1 −1   T3=   1 2 1   (2.4) Mediante este set de ecuaciones el sistema est´a definido para tres nodos. Este concepto puede ser extendido a escenarios con mn´umero de nodos, increment´andose la complejidad computacional en cada uno. Como el tama˜no de la red aumenta, lo mismo sucede con la secuencia de transmisi´on de pulsos y, por lo tanto, el n´umero de mediciones y ecuaciones. El concepto est´a ya pr´acticamente definido. Para tener una completa definici´on del mismo es necesario saber dise˜nar una secuencia de transmisi´on de pulsos. El siguiente subapartado trata sobre este aspecto. 2.2 La secuencia Crear la secuencia es un aspecto muy importante del sistema, ya que no todas son v´alidas. Como puede observarse en la tabla 3.1, se obtiene un sistema lineal para cada dispositivo, por lo tanto, la secuencia ha de ser dise˜nada de forma que estos sistemas sean compatibles y determinados, esto es, que las ecuaciones obtenidas no sean linealmente 18 2.5. Generador de secuencias: todas las posibles secuencias r´apido con el tama˜no de la red. La tabla 2.5 muestra una aproximaci´on de la cantidad de secuencias que se obtendr´ıan dependiendo del n´umero de nodos. Nschd ≤n(Ntx−1) (2.7) La ecuaci´on 2.7 devuelve el n´umero total de combinaciones que se deber´ıan probar empleando el m´etodo de fuerza bruta, es decir, probar todas las posibles combinaciones. nes el n´umero de componentes en la red y Ntx es el n´umero de transmisiones necesarias en la secuencia, su longitud. Nodes Transmissions Combinations to prove 3 6 243 4 9 65536 5 14 1,22 ×109 6 19 1,01 ×1014 Tabla 2.5: N´umero de combinaciones a probar con respecto al n´umero de nodos Nodes Number of schedules 2 1 3 6 4 498 5 438144 Tabla 2.6: N´umero de secuencias v´alidas seg´un el n´umero de nodos La tabla 2.6 indica el n´umero de secuencias v´alidas para cada n´umero de nodos. La idea de este nuevo algoritmo es escanear las posibilidades en un diagrama de tipo ´arbol. Inicializar la secuencia con el 1, e ir a˜nadiendo posibles nodos. La idea puede verse gr´aficamente en la figura 2.5 para un ejemplo de un escenario con 3 nodos. Cada c´ırculo representa un nodo, las l´ıneas negras las ramas del ´arbol y la l´ınea roja, el proceso de escaneo. Primero, el algoritmo a˜nade la subsecuencia 2,1,3,2,3 al 1 inicial, uno a uno. Cuando alcanza el n´umero ´optimo de transmisiones, retrocede una posici´on y prueba con el 1 en la ´ultima posici´on. Esta rama tambi´en llega a su final, luego esta vez retrocede dos veces y prueba con la siguiente rama superior. Mediante este proceso se escanean las posibilidades. Primero, se inicializa la secuencai a 1 y se crea la checkmatrix identidad asociada. En este caso, cada rama va a tener su propia checkmatrix asociada, cada vez que se crean nuevos niveles en el ´arbol, la checkmatrix se divide en tantas ramas como sean necesarias. Una vez inicializado todo, se ejecuta una funci´on recursiva que escanee el ´arbol, y a˜nada el nodo oportuno a la secuencia. El primer deber de esta funci´on es realizar una comprobaci´on de la checkmatrix asociada a la rama que se est´a ejecutando, para buscar nodos posibles nodos. Si no hay Cap´ıtulo 2. Localizaci´on cooperativa programada 19 1 3 1 3 2 3 1 2 3 2 1 Figura 2.4: ´ Arbol del algoritmo nodos posibles, o la longitud de la secuencia es la ´optima, se alcanza el final de la rama y la funci´on termina sin a˜nadir ning´un nodo. Si hay nodos posibles, se a˜nade el primer nodo disponible y la checkmatrix se actualiza. Se ha creado en estos momentos una nueva rama, con su checkmatrix actualizada. En este momento la funci´on se llama a s´ı misma para continuar a˜nadiendo nodos. Viendo el ejemplo de la figura, la primera llamada a la funci´on devuelve como nodos posibles {2,3}. Entonces, a˜nadir´a el nodo 2 a la secuencia, actualizar´a la checkmatrix y volver´a a llamarse a s´ı misma. Ahora devolver´a como posibles nodos {1,3}, a˜nadir´a el 1 a la secuencia, actualizar´a de nuevo la checkmatrix, y se volver´a a llamar. Este proceso contin´ua hasa la ´ultima rama. En la ´ultima rama del ejemplo, el nodo 2 ha transmitido y devuelve {3,1}. Seleccionar´a el nodo 3 y, como se ha llegado al final, retornar´a a la funci´on madre, y esta funci´on madre a˜nadir´a el siguiente nodo al a˜nadido anteriormente y continuar´a el proceso. Siguiendo este proceso al final se obtienen todas las secuencias posibles. Con esta funci´on, se obtienen muchas secuencias, pero no todas son v´alidas ya que no se ha tenido en cuenta la propiedad de la uniformidad. Para seleccionar las secuencias correctas, se cuenta cu´antas veces ha participado cada nodo. Si la diferencia entre transmisiones del m´as activo al menos activo es mayor que 1, no se alcanza uniformidad en las mismas, y la secuencia no es v´alida. Se ha de tener en cuenta el hecho de que el nodo 1 puede participar una vez m´as ya que la primera transmisi´on genera ecuaci´on. Con todo esto, todas las posibles secuencias son obtenidas. Ha de tenerse muy en cuenta a la hora de ejecutar este algoritmo que para redes mayores de 5 nodos, su tiempo de ejecuci´on se hace muy largo dado que la cantidad de secuencias es enorme. 20 2.6. Tiempo de procesado Figura 2.5: ´ Arbol del algoritmo 2.6 Tiempo de procesado El ´ultimo aspecto a definir en el problema de la localizaci´on cooperativa programada es el tiempo de procesado de los pulsos en cada dispositivo. Este valor es conocido por todos los miembros de la red y ha de cumplir: D > tmax (2.8) Donde tmax es el tiempo de propagaci´on del pulso si dos nodos se encuentran situados en los puntos m´as alejados del escenario. Si la ecuaci´on 2.8 no se cumple, los pulsos podr´ıan recibirse en un orden distinto al de la secuencia y, por lo tanto, el sistema no funcionar´ıa adecuadamente. Con lo cual, es muy importante dise˜nar este par´ametro conforme al escenario donde va a ser empleado el sistema. 2.7 Resumen En este cap´ıtulo se ha expuesto un nuevo sistema de localizaci´on cooperativa basada en la transmisi´on de pulsos en orden programado. Se ha demostrado que, aunque la complejidad aumenta comparado con el sistema ’3-way ranging’, la cantidad de transmisiones necesarias disminuye considerablemente, y con ellas, la energ´ıa gastada. Adem´as, se consigue un conocimiento completo por parte de todos los dispositivos de la red de las distancias entre ellos. Despu´es, se han propuesto algoritmos para generar estas secuencias de trasnmisi´on de pulsos, basadas en las restricciones que el propio sistema impone. Se han propuesto algoritmos para generar una secuencia, o todas las posibles secuencias. Al final, el problema del tiempo de procesado por parte de cada nodo se ha introducido como un aspecto importante para el correcto funcionamiento del sistema. Cap´ıtulo 3 El filtro de Kalman y las secuencias Una vez se tiene generada la secuencia de transmisi´on de pulsos por parte de los nodos de la red, se necesita de un algoritmo capaz de procesar las mediciones realizadas en cada uno de ellos. Como el sistema est´a funcionando en un entrono ruidoso y cambiante, se requiere que el algoritmo sea adaptativo. Este algoritmo adaptativo debe ser capaz de calcular las distancias a pesar del movimiento de los dispositivos y de las perturbaciones. El algoritmo escogido es el filtro de Kalman. Este filtro se basa en dos principales ecuaciones. •Ecuaci´on de procesado: xk+1 =Fkxk+mk(3.1) Donde xes el vector de estado del escenario, Fes la matriz de transiciones entre estados, y mes el ruido de procesado, el cual es un ruido blanco gaussiano de media cero. •Ecuaci´on de medici´on zk=Hkxk+nk(3.2) Donde xkes el vector de estado, Hes la matriz de medici´on, y nes el ruido de medici´on, cuyas caracter´ısticas se exponen m´as adelante. Para adaptar estas ecuaciones al problema, lo primero es definir qu´e representa cada una de las variables de las mismas en el sistema propuesto. La variable a estimar es la distancia entre todos los nodos de la red, por lo tanto, el vector de estado estar´a compuesto por este conjunto de valores, x= [d12, d13, . . . , d1N, d23, d24, . . . , dN−1,N ], donde Nes el n´umero de nodos presentes en el sistema. Este vector de distancias est´a altamente relacionado con los tiempos de propagaci´on de los pulsos entre dispositivos. El tama˜no de este vector de estado depende 21 22 Node 1 Node 2 Node 3 Time D D D D D T14 T13 T12 T11 T21 T22 T23 T31 T32 T33 t12 t23 t13 Figura 3.1: Diagrama temporal de transmisiones para tres nodos con secuencia 1-2-3-2- 1-3 del tama˜no de la red, y es igual al n´umero de enlaces directos entre ellos. Este tama˜no Mpuede calcularse mediante la expresion 3.3. M=n(n−1) 2(3.3) El vector de medici´on zes el tiempo transcurrido entre la recepci´on de dos pulsos en cada nodo zi= [Ti1, Ti2,...TiN ]. Donde el sub´ındice ies el n´umero de nodo en la secuencia, y Nes el n´umero total de ecuaciones. Este n´umero puede calcularse mediante la ecuaci´on 2.6. N= 1 + n(n−1) 2+ln 2m Como no hay dependencias entre el presente estado y el pr´oximo, la matriz de transiciones entre estados es la matriz identidad del tama˜no acorde al tama˜no del vector de estado, FM=IM×M, donde Mes el tama˜no del vector de estado x. La matriz de mediciones se extrae del sistema, ya que depende de la secuencia. Esta matriz Hcoincide con la matriz Cmen la ecuaci´on 2.1. Para ilustrar el problema, se han realizado varias simulaciones con distinto n´umero de nodos. Cap´ıtulo 3. El filtro de Kalman y las secuencias 23 1 2 3 t13 t23 t12 Figura 3.2: Escenario con tres nodos 3.1 Red de 3 nodos En un escenario con tres nodos, tres son los rangos a ser calculados, por lo tanto, el vector de estado es x= [t12, t13, t23]. Se han escogido tiempos para el vector de estado en lugar de distancias por simplicidad. Para transformar el vector de tiempos en distancias tan solo hay que multiplicarlo por la velocidad de propagaci´on de los pulsos, la velocidad de la luz en este caso. El vector de medici´on es zi= [Ti1, Ti2, Ti3]. Como puede observarse, en este sistema, M=N= 3. La figura 3.2 muestra un escenario est´andar con tres nodos. Mirando la figura 3.1, las ecuaciones de cada nodo son obtenidas. Las ecuaciones se almacenan en la tabla 3.1. Node 1 Node 2 Node 3 T11 = 2t12 +D T21 = 2t23 + 2D T31 =t12 −t13 +t23 +D T12 =−t12 +t13 +t23 +D T22 = 2t12 + 2D T32 =t23 + 2D T13 =t12 −t13 +t23 +D T23 =−t12 +t13 +t23 +D T33 =t12 +t13 −t23 +D Tabla 3.1: Conjunto de ecuaciones en cada nodo Donde Des el tiempo de procesado en cada dispositivo, el cual es conocido por toda la red. Si se escriben las ecuaciones de forma m´as general: Ti=Hit+Di+ni(3.4) Donde Dies el vector que contiene todos los tiempos de procesado en el nodo i, y nies el ruido de medici´on en el nodo i. Mirando a la tabla 3.1, las matrices de medici´on y los vectores de tiempos de procesado pueden obtenerse. 24 3.1. Red de 3 nodos H1=   2 0 0 −111 1−1 1   D1=   1 1 1    H2=   0 0 2 2 0 0 −1 1 1   D1=   2 2 1    H1=   1−1 1 0 0 1 1 1 −1   D1=   1 2 1    El sistema est´a ya definido. El siguiente paso es generar el escenario donde se va a realizar la simulaci´on. Ser´a un escenario 2D de 1000 ×1000 metros con tres dispositivos colocados de forma aleatoria en ´el. Una vez el escenario ha sido generado, un movimiento aleatorio es aplicado a cada uno de los nodos. La forma de generar este movimiento aleatorio es aplicar una aceleraci´on aleatoria en una direcci´on aleatoria a cada uno, partiendo de una posici´on inicial est´atica, o con una velocidad inicial prefijada. Dada la posici´on inicial del nodo, la velocidad inicial, la aceleraci´on, el tiempo de muestreo, el tiempo total de la simulaci´on y el tiempo que el nodo est´a en reposo antes de que el movimiento comience, el movimiento total del nodo puede ser calculado. Como puede verse en la figura 3.3, cada nodo parte de una posici´on inicial y se mueve a lo largo del escenario aleatoriamente. Ahora que el escenario est´a completamente creado, se requiere generar las mediciones en cada nodo. EL tiempo de propagaci´on de los pulsos es necesario que sea conocido para generar las mediciones, por lo tanto, es necesario calcular la distancia eucl´ıdea entre nodos y posteriormente dividir por la velocidad de propagaci´on. Despu´es, estos tiempos de propagaci´on obtenidos se multiplican por la matriz de mediciones Hy despu´es, se le a˜naden los tiempos de procesado. De esta forma, se han creado las mediciones en cada nodo, mediciones libres de ruido. ziclean =Hit+Di(3.5) Donde el sub´ındice ies el n´umero del nodo en la secuencia. El siguiente paso es definir los par´ametros del filtro. Como la red se compone de tres nodos y son necesarias tres mediciones, el tama˜no del vector de estado x,M, es igual al vector de medici´on z,N, tres. La matriz de medici´on considerado es la matriz de secuenciaci´on Hidefinida anteriormente y la matriz de transicion de estados ser´a la Cap´ıtulo 3. El filtro de Kalman y las secuencias 25 Scenario 200 400 600 800 1000 100 200 300 400 500 600 700 800 900 1000 Initial position node 1 Initial position node 2 Initial position node 3 Actual trajectory node 1 Actual trajectory node 2 Actual trajectory node 3 Figura 3.3: Movimiento de tres nodos matriz identidad de tama˜no M. El ruido de procesado es gaussiano de media 0. El ruido de medici´on es algo m´as complejo. Es tambi´en de distribuci´on gaussiana de media 0, pero la desviaci´on t´ıpica aumenta de forma exponencial con la distancia. El modelo escogido es n(t) = N(0, σ0et 2), donde tes el tiempo de propagaci´on del pulso entre los nodos. (6) Una vez se ha generado el ruido, las medidas ruidosas pueden generarse a˜nadiendo el ruido de medici´on a las medidas limpias previamente calculadas, y crear el vector zi. Antes de poner en marcha el filtro, es necesario inicializar el vector de estado y la matriz de covarianzas del error de predicci´on. x0=   0 0 0   P0=   1 0 0 0 1 0 0 0 1    En este punto, el filtro est´a listo para ser ejecutado en los nodos. Un aspecto importante a tener en cuenta es que el ruido de medici´on no es estacionario, por lo tanto, la matriz de covarianzas del ruido de medici´on es necesario calcularla en cada iteraci´on del filtro, tiene que ser actualizada cada vez que las distancias cambian. Esto implica que dentro del bucle del filtro, una parte se dedicar´a a actualizar esta matriz antes de ejecutar las ecuaciones del filtro en s´ı. Despu´es de actualizar la matriz de covarianzas del ruido de medici´on, se computan las ecuaciones del filtro: 26 3.1. Red de 3 nodos x+ k=Fkxk(3.6) P+ k=FkPkFk+QM(3.7) Kk=FkP+ kHTHP+ kHT+QN−1(3.8) xk+1 =x+ k+Kk(zk−Hx+ k−d) (3.9) Pk+1 = [I−KkH]P+ k+QM(3.10) Las ecuaciones 3.6 y 3.10 se utilizan para computar el filtro cada Nmediciones, esto es, cada vez que la secuencia termina. Lo recomendable es dise˜nar un filtro que se actualice cada vez que un pulso llega al nodo, es decir, en cada medida tomada. Teniendo en cuenta este hecho, puede redise˜narse el filtro obteni´endose el siguiente conjunto de ecuaciones: h=Hj(3.11) x+ k=Fkxk(3.12) P+ k=FkPkFk+QM(3.13) Kk=FkP+ khThP+ khT+QN−1(3.14) αk=zk−hx+ k−d(3.15) xk+1 =zk−Kkα(3.16) Pk+1 = [I−KkH]P+ k+QM(3.17) Donde hes el vector fila jde Hel cual corresponde con la medici´on Tij siendo i el nodo correspondiente. αes la innovaci´on escalar relacionada con esta medici´on. La ganancia de kalman Kse mantiene como una matriz M×Npero solo adaptada a una medici´on, no a toda la secuencia. Esta segunda versi´on es ejecutada durante 250 segundos y actualizada cada segundo. Los resultados se muestran en la figura 3.4. En la figura 3.4, se muestra la distancia real y la distancia estimada en la misma gr´afica. Puede verse que el tiempo de convergencia es relativamente bajo, y que las distancias son seguidas correctamente. Ejecutando el filtro en cada uno de los tres nodos, cada uno con su propia matriz de mediciones y sus propias medidas, se obtiene la figura 3.5. Se observa que cada nodo obtiene el mismo resultado, y que se obtiene un completo conocimiento de las distancias. Llegado a este punto, es conveniente transformar estas distancias calculadas a posiciones con el fin de comparar las trayectorias reales con las estimadas representando ambas en una misma figura. La posici´on ha de ser calculada en cada escal´on de tiempo, de forma que es necesario incluir c´odigo extra dentro del bucle del filtro una vez el vector distancias ha sido actualizado. Estas distancias actualizadas se guardan en un Cap´ıtulo 3. El filtro de Kalman y las secuencias 27 0 50 100 150 200 250 0 100 200 300 400 500 600 700 Time d12 d13 d23 Figura 3.4: Evoluci´on de las distancias en 250 s medidas en el nodo 1 0 50 100 150 200 250 0 200 400 600 800 Time Distances measured at node 1 d12 d13 d23 0 50 100 150 200 250 0 200 400 600 800 Distances measured at node 2 Time 0 50 100 150 200 250 0 200 400 600 800 Distances measured at node 3 Time Figura 3.5: Evoluci´on de las distancias en 250 s Cap´ıtulo 4 Complejidad computacional en cada nodo El filtro de Kalman es un algoritmo empleado en muchos sistemas de procesado de se˜nal que se caracteriza por realizar estimaciones que minimizan el error cuadr´atico medio (MMSE) del mismo. El MMSE se define como la esperanza del cuadrado de la diferencia entre el valor real de una variable aleatoria desconocida y el valor estimado de la misma, la cual es generalmente una funci´on de un varable aleatoria conocida. MSE =EX−ˆ X 2 Donde Xes una realizaci´on de una variable aleatoria desconocida y ˆ Xes el valor predicho de X. El filtro de Kalman emplea el concepto de estado del sistema. El estado es el conjunto de variables que definen el sistema donde el filtro est´a siendo ejecutado . Contiene toda la informaci´on y, dado el estado actual y un conjunto de valores de entrada, es posible estimar estados futuros. Un aspecto importante es que, como el filtro es ejecutado de forma iterativa, tan solo es necesario almacenar el estado actual, no todos los estados previos. Este hecho implica un menor uso de memoria y una mayor idoneidad para dispositivos digitales. 4.1 Filtro 4.1.1 Establecimiento del problema Se denota el estado de un sistema dinamico como x(n), el cual es un vector columna M-dimensional que contiene el conjunto de Mvariables que definen el sitema en su totalidad. El ´ındice kdenota el tiempo donde el estado es observado. Se define el vector de medici´on, o medidas, como z(n), el cual es un vector columna N-dimensional donde las 35 36 4.1. Filtro medidas son almacenadas. Una vez definidos estos dos vectores, el problema del filtrado puede ser expuesto. El problema se describe mediante dos ecuaciones principales, la ecuaci´on de proceso, que computa el estado siguiente bas´andose en el comportamiento del sistema, y la ecuaci´on de medida, que emplea informaci´on externa para calcular el estado siguiente. Estas ecuaciones son: •Ecuaci´on de proceso: xk+1 =Fkxk+mk(4.1) Donde Fkes la matriz de transici´on de estados entre el instante kyk+ 1 conocida, de tama˜no M×M, y el vector columna de tama˜no Mmkes el ruido de proceso que se modela como un ruido blanco Gaussiano. •Ecuaci´on de medida: zk=Hkxk+nk(4.2) Donde Hkes la matriz que relaciona el estado con las medidas externas, y el vector columna de tama˜no Nnkes el ruido de de medidas, el cual es modelado como un proceso Gaussiano con varianza variable. 4.1.2 Innovaciones Se conoce como innovaci´on a la diferencia entre las observaciones reales, o medidas del sistema, con las predichas o estimadas. Se define el vector ˆzkcomo las estimaciones de las medidas en el instante k, dadas las observaciones previas zdesde 1 hasta k−1. El proceso de innovaci´on se define mediante la ecuaci´on 4.3. αk=zk−z+ k, k = 1,2, . . . (4.3) El siguiente paso es determinar la matriz de correlaci´on de este proceso de innovaci´on. Definiendo x+ kyn+ kcomo el estado predicho y el error de medici´on predicho dadas las k−1 observaciones previas, la siguiente expresi´on denota la estimaci´on MMSE del vector de observaciones. z+ k=Hkx+ k+n+ k Como n+ kes ortogonal a todas las observaciones pasadas, el t´ermino puede omitirse. Por lo tanto, la expresion puede reescribirse como: z+ k=Hkx+ k(4.4) Y 4.3 puede ser reescrita como: Cap´ıtulo 4. Complejidad computacional en cada nodo 37 αk=zk−Hkx+ k(4.5) Empleando la ecuaci´on de medici´on, la expresi´on del proceso de innovaci´on queda: αk=Hkxk+nk−Hkx+ k αk=Hkεk,k−1+nk(4.6) Donde εk,k−1es el error de predicci´on de estado y es igual a: εk,k−1=xk−x+ k(4.7) Ahora, la matriz de correlaci´on del proceso de innovaci´on, por definici´on es: Σk=E[αkαH k] (4.8) Introduciendo 4.6, en 4.8, se obtiene la ecuaci´on: Σk=HkPk,k−1HH k+QN(4.9) Donde Pk,k−1es la matriz de correlaci´on del error de predicci´on de estado definida como: Pk,k−1=E[εk,k−1εH k,k−1] (4.10) Este error de predicci´on de estado se calcula adaptativamente y el proceso se expone m´as adelante. 4.1.3 Estimaci´on del estado La estimaci´on del estado puede calcularse mediante combinaciones lineales de los procesos de innovaci´on desde el instante k= 1 hasta k=k. x+ k= k X j=1 Bijαk(4.11) Siendo Bij un conjunto de matrices M×N. El principio de ortogonalidad dice que los procesos de innovaci´on y los errores de predicci´on de estado son ortogonales, por lo tanto: E[εikαH m] = 0(4.12) 38 4.1. Filtro Sustituyendo 4.7 y 4.11 en 4.12, puede obtenerse una expresi´on del conjunto de matrices Bik: E[εinαH m] = E[(xi−x+ iαH m] =E (xi− k X j=1 Bijαj)αH m  =E[xiαH m]−BimΣm Bim =E[xiαH m]Σ−1 m(4.13) Una vez se tiene esta expresi´on para Bim, la estimaci´on del estado se obtiene siguiendo el siguiente procedimiento: x+ i= k X j=1 E[xiαH j]Σ−1 jαj = k−1 X j=1 E[xiαH j]Σ−1 jαj+E[xiαH k]Σ−1 kαk Para i=k+ 1 la expresi´on se escribe como: x+ k+1 = k−1 X j=1 E[xk+1αH j]Σ−1 jαj+E[xk+1αH k]Σ−1 kαk(4.14) Ahora, empleando la ecuaci´on de proceso: E[xk+1αHj] = E(Fkxk+mk)αH j E[xk+1αH j] = FkE[xkαH j] (4.15) Sustituyendo 4.15 en 4.14: x+ k+1 = k−1 X j=1 FkE[xkαH j]Σ−1 jαj+E[xk+1αH k]Σ−1 kαk x+ k+1 =Fkx+ k+E[xk+1αH k]Σ−1 kαk(4.16) De esta forma, la ecuaci´on final de actualizaci´on de estados es: x+ k+1 =Fkx+ k+Kkαk(4.17) Kk=E[xk+1αH k]Σ−1 k(4.18) Cap´ıtulo 4. Complejidad computacional en cada nodo 39 Donde Kkes una matriz M×Nconocida como ganancia Kalman. 4.1.4 Ganancia Kalman La ganancia Kalman se expresa como: Kk=E[xk+1αH k]Σ−1 k Expandiendo la esperanza: E[xk+1αH k] = FkE[xkαH k] =FkE[xk(Hkεk,k−1+nk)H] =FkE[xkεH k,k−1]HH k =FkE[xkxk−x+ kH]HH k Como x+ kyεk,k−1est´an incorreladas, la esperanza puede escribirse como: E[xk+1αH k] = FkE[εk,k−1εH k,k−1]HH k E[xk+1αH k] = FkPk,k−1HH k(4.19) De esta forma, la expresi´on de la ganancia Kalman es: Kk=FkPk,k−1HH kΣ−1 k(4.20) 4.1.5 Matriz de correlaci´on del error de predicci´on de estado El problema ahora reside en computar la matriz de correlaci´on del error de predicci´on de estado. Este c´alculo se hace de forma adaptativa. El proceso parte de las siguientes ecuaciones: εk,k−1=xk−x+ k εk+1,k =xk+1 −x+ k+1 xk+1 =Fkxk+mK x+ k+1 =Fkx+ k+Kkαk 40 4.1. Filtro Ahora, expandiendo εk+1,k: εk+1,k =Fkxk+mk−Fkx+ k +Kk(zk−Hkx+ k) =Fkxk+mk−Fkx+ k) +Kk(Hkxk−Hkx+ k)) εk+1,k = (Fk−KkHk)εk,k−1−Kknk+mk(4.21) Y calculando la matriz del error de predicci´on de estado mediante la definici´on: Pk+1,k =E[εk+1,kεH k+1,k] = (Fk−KkHk)Pk,k−1(FH k−KH kHH k) +KkQNKH k+QM Finalmente la ecuaci´on que permite calcular esta matriz de forma adaptativa es: Pk+1,k =FkPkFH k+QM(4.22) Pk=Pk,k−1−FkKkHkPk,k−1(4.23) 4.1.6 Condiciones iniciales Para obtener las condiciones iniciales hay que observar el caso k= 0. La expresi´on es: x+ 1=F0x+ 0 Como x+ 0es la estimaci´on sin ning´un dato previo, es igual a cero, por eso la primera condici´on inicial es: x0=0(4.24) La otra variable que ha de ser inicializada es la matriz de correlaci´on del error de predicci´on de estados. Siguiendo el procedimiento anterior se deduce que: P1,0=E[ε1,0εH 1,0)] =E[x1−x+ 0x1−x+ 0H] =E[x1xH 1] Cap´ıtulo 4. Complejidad computacional en cada nodo 41 P1,0=E[x1xH 1] (4.25) 4.1.7 Resumen La tabla 4.1 guarda todas las medidas, ecuaciones, par´ametros y condiciones iniciales necesarias para ejecutar el filtro. Kalman filter Inputs: zk Known parameters: State transition matrix: Fk Measurement matrix: Hk Correlation matrix of process noise vector: QM Correlation matrix of measurement noise vector: QN Initial conditions: x0=0 P1,0=E[x1xH 1] Computation loop: Time update: x+ k=Fkxk P+ k=FkPkFH k+QM Measurement update: Kk=FkP+ kHH kHkP+ kH+ k+QN−1 αk=zk−Hkxk xk+1 =x+ k+Kkαk Pk+1 = [I−KkHk]P+ k+QM Tabla 4.1: El filtro de Kalman 4.2 Complejidad del filtro de Kalman Una vez introducido el filtro de Kalman, es conveniente analizar su complejidad computacional calculando el n´umero de multiplicaciones y sumas. Como es un filtro adaptativo, no tiene un n´umero fijo de multiplicaciones y sumas, ya que el bucle se est´a ejecutando continuamente. Para medir la complejidad se tendr´a en cuenta una iteraci´on del filtro. Primero, dos variables deben ser definidas. Mdenota el tama˜no del vector de estados, y Nel tama˜no del vector de medidas. Mse relaciona con el n´umero de nodos mediante la expresi´on: M=Nnodes! 2!(Nnodes −2)! (4.26) La metodolog´ıa es la misma que la empleada en el anexo ??. Tomar una ecuaci´on del bucle y analizarla paso por paso. Las tablas desde 4.2 hasta 4.8 almacenan los resultados. 42 4.2. Complejidad del filtro de Kalman Variable Size zk(N×1) xk(M×1) Fk(M×M) Hk(N×M) QM(M×M) QN(N×N) Kk(M×N) αk(N×1) x+ k(M×1) Pk(M×M) P+ k(M×M) Tabla 4.2: Tama˜no de las variables del filtro de Kalman x+ k=Fkxk Step Sizes Products Additions x+ k=Fkxk(M×M)(M×1) M2M(M−1) Total −M2M2−M Tabla 4.3: Complejidad de la estimaci´on del estado P+ k=FkPkFH k+QM Step Sizes Products Additions FkPk(M×M)(M×M)M3M2(M−1) [FkPk]FH k(M×M)(M×M)M3M2(M−1) [···] + QM(M×M)(M×M)−M2 Total −2M32M3−M Tabla 4.4: Complejidad de la matriz de correlaci´on del error de predicci´on Kk=FkP+ kHH k[HkP+ kHH k+QN]−1 Step Sizes Products Additions HkP+ k(N×M)(M×M)NM2NM(M−1) [HkP+ k]HH k(N×M)(M×N)N2M N2(M−1) [···] + QN(N×N)(N×N)−N2 [···]−1(N×N)multsinv addsinv FkP+ k(M×M)(M×M)M3M2(M−1) [FkP+ k]HH k(M×M)(M×M)M2N MN(N−1) [···][···]−1(M×N)(N×N)MN2MN(N−1) Total −M3+2M2N M3+2M2+2MN2 +2MN2−M2−3MN +multsinv +addsinv Tabla 4.5: Complejidad de la ganancia Kalman Cap´ıtulo 4. Complejidad computacional en cada nodo 43 αk=zk−Hkx+ k−dk Step Sizes Products Additions Hkx+ k(N×M)(M×1) NM N(M−1) zk−[Hkx+ k] (N×1) −(N×1) −N αk= [zk−Hkx+ k]−dk(N×1) −(N×1) −N Total −NM NM +M Tabla 4.6: Complejidad de las innovaciones La ecuaci´on de las innovaciones ha sido adaptada a este problema de localizaci´on cooperativa, restando el retardo de procesado d. xk+1 =x+ k+Kkαk Step Sizes Products Additions Kkαk(M×N)(N×1) MN M(N−1) x+ k+Kkαk(M×1) + (M×1) −M Total −MN MN Tabla 4.7: Complejidad de la estimaci´on del estado actualizado Pk+1 = [I−KkHk]P+ k+QM Step Sizes Products Additions KkHk(M×N)(N×M)M2N M2(N−1) I−KkHk(M×M)+(M×M)−M2 [I−KkHk]P+ k(M×M)(M×M)M3M2(M−1) [I−KkHk]P+ k+QM(M×M)+(M×M)−M2 Total −M3+M2N M3+M2N Tabla 4.8: Complejidad de la matriz de correlaci´on del error de predicci´on actualizada Teniendo todos estos resultados, se puede calcular la complejidad global de una iteraci´on del filtro de Kalman sumando las contribuciones de cada ecuaci´on. Un aspecto importante a tener en cuenta es que la mayor contribuci´on al coste computacional viene dado por la ganancia Kalman y la matriz de correlaci´on del error de predicci´on de estado. M´as importante es implementar un algoritmo eficiente de inversi´on de matrices dado que la matriz a invertir el muy grande, y la inversi´on de matrices es conocida por ser muy costosa computacionalmente. La tabla 4.9 almacena el resultado total de una iteraci´on. 4.3 Inversi´on de la matriz de la ganancia Kalman Calcular la ganancia Kalman requiere una inversi´on de una matriz de tama˜no N×N por iteraci´on. La inversi´on de matrices es una operaci´on con un alto coste computacional y dif´ıcil de implementar en hardware. El n´umero de operaciones necesarias crece exponencialemnte con el tama˜no de la matriz. Hablando sobre costes computacionales, la inversi´on de matrices suele ser siempre el punto cr´ıtico del sistema. 50 4.4. Coste computacional total del filtro Complexity of Cholesky Number of operations Multiplications 1 3N3+ 2N2+5 3N Additions 1 6N3+N2−1 6N Divisions 1 2N2−1 2N Square roots 0 Tabla 4.19: Complejdad de la descomposici´on de Cholesky Complexity of inversion with Cholesky Number of operations Order Multiplications 8 3N3+ 2N2+4 3NO8 2N3 Additions 5 2N3−N2−1 2NO5 2N3 Divisions 3 2N2+3 2NO3 2N2 Square roots 0 O(0) Tabla 4.20: Complejidad de la inversi´on usando la descomposici´on de Cholesky 4.4 Coste computacional total del filtro La tabla 4.21 congrega la complejidad de todo el filtro. En general, el tama˜no del vector de estados Mes mucho mayor que el n´umero de medidas N. Al calcular el orden de complejidad se ha tenido en cuenta este hecho. En el caso M=N, el orden de complejidad cambia dado que Ntoma m´as importancia. La tabla 4.22 guarda los resultados. Cap´ıtulo 4. Complejidad computacional en cada nodo 51 Total complexity of Kalman filter, (M > N) KF + Gram Schmidt Number of operations Order Multiplications 13 6N3+ 2MN2+3M2+ 2M−1 6N+ 4M3+M2O4M3 Additions 13 6N3+2M−3 2N2+M2−M−2 3N+ 4M3+ 2M2−MO4M3 Divisions 3 2N2+1 2NO2N2 Square roots NO(N) KF + Householder Number of operations Order Multiplications 5 2N3+ 2MN2+3M2+ 2M+5 2N+ 4M3+M2−8O4M3 Additions 5 2N3+ (2M+ 1) N2+M2−M−23 6N+ 4M3+ 2M2−M−3O4M3 Divisions N2+N−1ON2 Square roots 2N−2O(2N) KF + G.Rotations Number of operations Order Multiplications 1 2N5+2 3N3+ 2MN2+3M2+ 2M−7 6N+ 4M3+M2O1 2N5 Additions 1 2N5−N4+5 3N3+2M−1 2N2+O1 2N5 +M2−M−1 6N+ 4M3+ 2M2−M Divisions 3 2N2−1 2NO3 2N2 Square roots 1 2N2−1 2NO1 2N2 KF + Cholesky Number of operations Order Multiplications 8 3N3+ (2M+ 2) N2+3M2+ 2M+4 3N+ 4M3+M2OM3 Additions 5 2N3+ (2M−1) N2+M2−M−1 2N+ 4M3+ 2M2−MO4M3 Divisions 3 2N2+3 2NO3 2N2 Square roots 0O(0) Tabla 4.21: Coste computacional total del filtro de Kalman Order of complexity of Kalman filter, (M=N) KF + Gram Schmidt Order Multiplications O67 6M3 Additions O55 6M3 Divisions O3 2M2 Square roots O(M) KF + Householder Order Multiplications O23 2M3 Additions O19 2M3 Divisions OM2 Square roots O(2M) KF + G.Rotations Order Multiplications O1 2M5 Additions O1 2M5 Divisions O3 2M2 Square roots O1 2M2 KF + Cholesky Order Multiplications O35 3M3 Additions O35 3M3 Divisions O3 2M2 Square roots O(0) Tabla 4.22: Orden de complejidad cuando M=N 52 4.5. Complejidad del sistema con el aumento de nodos en la red Orders KF + Gram Schmidt KF + Householder KF + Cholesky Multiplications O(11.16 N3)O(11.5 N3)O(11.66 N3) Additions O(9.16 N3)O(9.5 N3)O(11.66 N3) Divisions O(1.5 N2)O(N2)O(1.5 N3) Square roots O(N)O(2 N)O(0.5 N) FLOPs O(20.33 N3)O(21 N3)O(23.33 N3) Tabla 4.23: Orden de operaciones con el n´umero de medidas Method Order KF + Gram-Schmidt O(2.54 n6) KF + Householder O(2.63 n6) KF + Cholesky O(2.92 n6) Tabla 4.24: Orden de operaciones con el n´umero de nodos 4.5 Complejidad del sistema con el aumento de nodos en la red Finalmente, una vez que la complejidad del filtro es conocida, es hora de discutir c´omo afecta el n´umero de dispositivos de la red a la misma. Lo primero, se van a considerar las operaciones como operaciones de punto flotante (flops). La tabla 4.23 muestra el n´umero de flops requerido para cada caso en t´erminos del n´umero de medidas tomadas por cada nodo. En la tabla 4.23 no se han tenido en cuenta las rotaciones de Givens. El n´umero de mediciones es igual al n´umero de enlaces directos entre nodos, luego se relacionan mediante la ecuaci´on 2.5. N=cn 2=n(n−1) 2 La tabla 4.24 muestra el orden de flops en t´erminos del n´umero de nodos n, empleando la ecuaci´on 2.5 en las expresiones en la tabla 4.23. Puede verse que el coste computacional aumenta con un orden de 6 con el n´umero de nodos, esto significa que a˜nadir un nuevo nodo a una red peque˜na tiene menos impacto que a˜nadirlo a una red grande. Esta complejidad creciente tiene un efecto en la tasa de actualizaci´on. Las expresiones de la tabla 4.24 son ´utiles para calcular el m´aximo tama˜no de una red en concreto. Dependiendo de la tasa de actualizaci´on de la posici´on deseada, y de la velocidad de procesado de los nodos, este n´umero puede ser calculado. Cap´ıtulo 4. Complejidad computacional en cada nodo 53 •Being N the number of ranges: KTH 2012: Electrical Engineering – Department of Signal Processing 21 Rising complexity with nodes Method Order KF + Gram Schmidt 𝒪 2.54𝑛6 KF + Householder 𝒪 2.63𝑛6 KF + Cholesky 𝒪 2.92𝑛6 KTH 2012: Electrical Engineering – Department of Signal Processing 21 010 20 30 40 50 102 104 106 108 1010 1012 Gram-Schmidt Householder Cholesky 𝑁 = 1 2𝑛2−1 2𝑛 Figura 4.1: Complejidad con el aumento de los nodos en una red Cap´ıtulo 5 Conclusiones Varias conclusiones pueden sacarse una vez realizado el proyecto. El principal objetivo era dise˜nar un sistema de localizaci´on cooperativa en una red de dispositivos basada en una secuencia de transmisi´on de pulsos con el objetivo de mejorar el sistema existente 3-way ranging. El primer aspecto a ser mejorado era la cantidad de distancias conocidas por cada nodo, esto es, que cada nodo no solo fuera capaz de medir la distancia entre ´el mismo y los dem´as sino tambi´en conocer las dem´as distancias entre los dem´as nodos entre s´ı. Otro aspecto secundario, pero tambi´en importante, a mejorar, era la cantidad de transmisiones de pulsos necesarios. Ambos aspectos han sido mejorados mediante este nuevo sistema. Las ventajas de esta aproximaci´on son significantes por lo tanto este m´etodo es apto para ser desarrollado. Una vez definido el sistema, el problema del dise˜no de secuencias aparece. Una secuencia v´alida debe satisfacer diversas restricciones que el propio sistema impone. Despu´es de estudiar todas estas restricciones, se ha desarrollado un algoritmo. Este algoritmo ha de ser simple y eficiente debido a que la longitud de la secuencia aumenta factorialmente con el n´umero de nodos, y este n´umero puede llegar a ser muy grande. Una vez dise˜nado este algoritmo, puede concluirse que la idea de la checkmatrix es una buena herramienta que hace que el algoritmo sea eficiente, reduce el n´umero de iteraciones comparado con la fuerza bruta. Otra buena caracter´ıstica de la checkmatrix es que muestra c´omo se va formando la secuencia de una forma clara si se ejecuta el algoritmo paso a paso. El segundo algoritmo propuesto se basa en el primero. La simplicidad aqu´ı toma mayor peso dado el gran n´umero de posibles secuencias v´alidas para redes grandes. Es conveniente guardar en un fichero lo obtenido para usar los datos en el futuro, ya que ejecutar este algoritmo cada vez lleva un tiempo excesivo. Despu´es del tema de las secuencias, el siguiente paso era dise˜nar un filtro para procesar todos los datos medidos en cada nodo. Se ha escogido el filtro de Kalman debido a su capacidad de seguimiento. La idea inicial era dise˜nar un filtro de Kalman capaz de calcular rangos en la red. Puede concluirse que el filtro de Kalman es una herramienta v´alida para este sistema y funciona perfectamente. Despu´es de probar que el 55 56 5.1. L´ıneas futuras filtro elegido era el correcto, la idea era reducir el coste computacional en cada nodo, esto es, dise˜nar el filtro minimizando el n´umero de operaciones. Despu´es de analizar el filtro paso a paso, la conclusi´on es que la mayor contribuci´on al coste computacional la aporta la inversi´on de la matriz de la ganancia Kalman. Para reducir las operaciones, varias formas de descomposici´on de matrices se han estudiado, siendo la descomposici´on QR la estudiada con m´as detalle. La conclusi´on obtenida es que la forma m´as ´optima de invertir la matriz es emplear la descomposici´on QR mediante el m´etodo de la ortogonalizaci´on de Gram-Schmidt. La transformaci´on de Householder y la descomposici´on de Cholesky son algoritmos m´as estables pero dada la gran estabilidad del problema, este aspecto puede ser descartado. Las rotaciones de Givens se descartaron enseguida debido a su alto coste computacional. Finalmente, para invertir la matriz, se ha escogido descomponerla mediante la ortogonalizaci´on de Gram-Schmidt e invertir mediante la sustituci´on hacia atr´as. Despu´es de calcular la complejidad en cada nodo, se ha discutido c´omo afecta el tama˜no de la red a la misma. Despu´es de discutirlo, la conclsi´on es que el n´umero de operaciones en cada nodo se relaciona con el n´umero de nodos a la sexta potencia. Una vez estudiada esta propuesta de secuencias de transmisi´on de pulsos, otra mejora fue propuesta. En vez de estimar rangos, estimar la posici´on en un escenario bidimensional. Para poder hacerlo, el filtro de Kalman fue modificado dado que esta propuesta requiere de un filtrado no lineal, de este modo, el filtro propuesto fue el filtro de Kalman extendido (EKF). El EKF emplea derivadas y Jacobianos para linearizar las no linealidades. El EKF deber´ıa poder estimar las posiciones, pero despu´es de realizar varias simulaciones, la conclusi´on obtenida es que la linearizaci´on de las medidas introduce errores severos en el sistema y no funciona correctamente. Esto es, el EKF no es v´alido para este sistema. 5.1 L´ıneas futuras La primera sugerencia es estudiar otro tipo de filtro para lograr estimar la posici´on. Como el EKF no es v´alido se propone el estudio del Unscented Kalman filter (UKF), que en lugar de emplear linearizaciones, trabaja con estad´ıstica. El UKF se comporta mucho mejor con las no linealidades. Otra sugerencia es desarrollar un protocolo de comunicaciones entre nodos. En vez de transmitir solo pulsos, enviar tambi´en, identificadores, errores u otro tipo de datos para a˜nadir robustez al sistema. Tambi´en puede estudiarse la forma de juntar varias redes de forma autom´atica. Un ejemplo ser´ıa nombrar un nodo maestro en cada red. Otra forma ser´ıa realizar un rec´alculo de la secuencia si se detectan nuevos nodos en el sistema. La ´ultima sugerencia es mejorar el sistema para mejorar su funcionamiento en entornos adversos, que sea capaz de lidiar con propagaciones multicamino, ca´ıdas de Cap´ıtulo 5. Conclusiones 57 enlaces, ca´ıdas de nodos, desvanecimientos, etc. Referencias [1] G. de Tecnolog´ıas de las Comunicaciones, Introducci´on a los sistemas de radionavegaci´on. De las notas del curso 18117, Sistemas de radionavegaci´on, Universitdad de Zaragoza. [2] N. Patwari, J. N. Ash, S. Kyperountas, A. O. H. III, R. L. Moses, and N. S. Correal, “Locating the nodes: cooperative localization in wireless sensor networks,” IEEE Signal Processing magazine, vol. 22, pp. 54–69, jul. 2005. [3] M. Z. Win, A. Conti, S. Mazuelas, Y. Shen, W. M. Gifford, D. Dardari, and M. Chiani, “Network localization and navigation via cooperation,” IEEE Communications magazine, vol. 49, pp. 56–62, may. 2011. [4] H. Wymeersch, J. Lien, and M. Z. Win, “Cooperative localization in wireless networks,” Proceedings of the IEEE, vol. 97, pp. 427–450, feb. 2009. [5] S. Dwivedi, A. D. Angelis, and P. H¨andel, “Scheduled uwb pulse transmission for cooperative localization,” IEEE ICUWB, 2012. [6] J.-O. Nilsson, A. D. Angelis, I. Skog, P. Carbone, and P. H¨andel, “Signal processing issues in indoor positioning by ultra wide band radio aided inertial navigation,” 17th European Signal Processing Conference (EUSIPCO 2009), Glasgow, aug. 2009. [7] S. Haykin, Adaptive Filter Theory. Prentice Hall, 4 ed., 2001. [8] P. G. Kaminski, A. E. Bryson, and S. F. Schmidt, “Discrete square root filtering: A survey of current techniques,” Automatic control, IEEE Transactions, vol. 16, pp. 727–736, dec. 1971. [9] H. W. Sorenson, “Least-squares estimation: from gauss to kalman,” Spectrum,IEEE, vol. 7, pp. 63–68, jul. 1970. [10] W. Gander, “Algorithms for qr-decomposition,” tech. rep., Eidgenoessische Technische Hochschule, 1980. [11] T. Lacey, Tutorial: The Kalman filter. De las notas del curso CS7322 en Georgia Tech. 59