SISTEMA Y PROCEDIMIENTO DE LOCALIZACIÓN BASADOS EN MEDIDAS PASIVAS DE DIFERENCIAS TEMPORALES PARA EL POSICIONAMIENTO CONJUNTO DE NODOS EN REDES COLABORATIVAS.

Sistema y procedimiento de localización basados en medidas pasivas de diferencias temporales para el posicionamiento conjunto de nodos en redes colaborativas.

Procedimiento destinado a obtener la localización conjunta de nodos en una red colaborativa de forma pasiva, basado en la existencia de un nodo (pasivo) que se posiciona a partir de las peticiones de localización realizadas por un subconjunto de nodos de la misma red (nodos activos), que emplean una técnica de localización basada en la estimación del tiempo de ida y vuelta. El procedimiento permite la estimación de los tiempos de propagación de los nodos activos en el nodo pasivo, pudiéndose calcular la posición de los nodos activos y la del nodo pasivo de forma conjunta en éste último. El procedimiento está basado en "Sistema y procedimiento de localización basados en medidas pasivas de diferencias temporales tomadas a partir de escuchas de tiempo de llegada de otros nodos", donde se transforman las medidas de tiempo con las que operan los nodos activos, en diferencias temporales en los nodos pasivos.

Sistema y procedimiento de localización basados en medidas pasivas de diferencias temporales para el posicionamiento conjunto de nodos en redes colaborativas.

Sector de la técnica Comunicaciones móviles. Geolocalización. Ingeniería telemática.

Estado de la técnica

Actualmente, son muchos los sistemas de localización propuestos para su uso en redes ad hoc. Dichos sistemas, se estructuran de acuerdo a tres etapas. La primera de ellas comprende la captura u observación de las métricas empleadas en el posicionamiento. Por sus características, en redes ad hoc las métricas que con mayor frecuencia se emplean son los ángulos de incidencia, los tiempos de propagación y el nivel de señal recibido, especialmente éstos dos últimos. En la segunda etapa, se toman las medidas capturadas y procede al cálculo de la posición de los nodos capaces de realizar dicha tarea por sí mismos, es decir, aquellos con capacidades de localización y con información local suficiente como para proceder con el cálculo de la posición. Estas dos etapas son comunes a todos los sistemas de localización [BON07]: OTDOA (multilateración basada en diferencias temporales en redes UMTS) , GPS (multilateración basada en tiempos de propagación en la red NAVSTAR) , etc.

La tercera etapa de un sistema de localización ad hoc es la encargada de definir el algoritmo de localización empleado. Dicho algoritmo se encarga de determinar la forma en la que obtienen su posición, todos aquellos nodos sin conocimiento suficiente como para proceder a su localización en una primera instancia. Son múltiples los algoritmos propuestos para sistemas de localización en redes ad hoc. Una de las primeras fue propuesta en [DPG01], donde el posicionamiento es resuelto como si fuera un problema de optimización-convexa. Para ello se propone que un servidor central recoja toda la información de localización de la red y procesa de esta forma al cálculo de la solución óptima para todas las posiciones involucradas. La principal ventaja de este sistema radica en su optimalidad. Sin embargo, tiene como contrapartida el hecho de ser un sistema centralizado, lo que redunda en un pobre balanceo del tráfico de localización (que impacta directamente sobre la vida útil de la red ad hoc) , potenciales problemas de integridad en la red (si el centro de localización cae o se congestiona) y una escasa capacidad para escalar (el coste del algoritmo es cúbico respecto al número de conexiones) .

Debido a las deficiencias anteriormente mencionadas, la mayoría de soluciones actuales optan por algoritmos distribuidos, como por ejemplo los presentados en [SHS01]. De entre todas las soluciones destacan las integrantes del Ad hoc Positioning System (APS) , presentado en [NN03]: DV-Hop, DV-distance, Euclidean y DV-Coordinate.El primero de ellos, los nodos mantienen tablas con la posición y la distancia (en número de saltos) para cada uno de los nodos de referencia (es decir, aquellos que obtienen su propia posición de forma ajena al algoritmo de localización ad hoc) bajo cobertura. Esa información se difunde de forma controlada por la red, de forma que todos los nodos llegan a conocer su distancia a los nodos de referencia. A su vez, los landmarks difunden la distancia media vinculable a un salto. Con toda esta información, los nodos proceden al cálculo de su posición mediante multilateración. La principal ventaja de este algoritmo es que no es especialmente sensible a los errores del canal radio, lo que le hace muy recomendable en entornos altamente ruidosos. Su principal inconveniente radia en que la precisión obtenida depende directamente de la densidad de nodos en la red y cuanto mayor sea ésta mayor es el tráfico de localización requerido para difundir la información que permite el posicionamiento. El algoritmo de DV-distance es similar al DV-Hop, si bien transmite distancias reales en lugar de salto, lo que lo hace más robusto frente a distribuciones no homogéneas de nodos en la red (escenario habitual) . Sin embargo, al utilizar la distancia real como métrica, el algoritmo pasa a ser más sensible a los errores del canal radio sobre las medidas observadas, lo que redunda en la precisión obtenida. El algoritmo Euclidean, extiende la información de distancia a dos saltos, en lugar de uno como las propuestas anteriores. De esta forma, se crean cuadriláteros que involucran un nodo de referencia, dos nodos vecinos y un nodo a posicionar. La principal ventaja de esta propuesta multisalto es que se permite la estimación del error esperado, pudiéndose almacenar y difundir al resto de vecinos; por el contrario, la principal desventaja es que, por el hecho de ser multisalto, este algoritmo implica mayor gasto de recursos en los nodos (memoria para almacenar el error esperado) así como trafico de localización adicional, el cual redunda en una menor capacidad en la red. El último de los algoritmos propuestos en [NN03] extiende el APS de forma que opere con sistemas de coordenadas locales.

Otro algoritmo similar a APS es el propuesto en [NSB03], donde el autor calcula la distancia (en saltos) de los nodos a posicionar a distintos nodos de referencia. La diferencia principal radica en el hecho de que la longitud de un salto se calcula en una etapa previa al despliegue de la red, en función de la densidad de nodos en la misma. Esa etapa requiere de una recalibración siempre que se alteren las condiciones de operación, lo que redunda negativamente en la escalabilidad del algoritmo. Otro ejemplo de algoritmo distribuido se puede encontrar en [FLQ06], donde los autores proponen un mecanismo para propagar el reloj de un nodo a otro y así habilitar un sistema de localización virtualmente síncrono.

En la actualidad, la tendencia de los sistemas de localización en redes ad hoc parece ser hacia algoritmos colaborativos. Dichos algoritmos se basan en la colaboración entre nodos adyacentes para la consecución de un posicionamiento en situaciones en las que los algoritmos tradicionales, basados en nodos de referencia, no son capaces de afrontar con éxito. Un primer ejemplo de algoritmo colaborativo se presenta en [SHS01], donde se presenta una solución colaborativa que identifica situaciones no resolubles con algoritmos tradicionales y procede al cálculo de la posición de forma colaborativa. Un ejemplo de este tipo de soluciones se puede encontrar en [US20080268873], donde los autores presentan un sistema de localización ad hoc colaborativo, es decir, en el que los nodos colaboran entre ellos para la obtención de posiciones en situaciones en las que no hay suficientes nodos de referencia a la vista. Sin embargo este tipo de algoritmos tienden a penalizar la escalabilidad del sistema de localización, pues habitualmente incurren en un mayor tráfico de localización durante la etapa del cálculo de posiciones. Esto es especialmente grave en situaciones en las que se requiere del posicionamiento conjunto de múltiples nodos en la red, en la actualidad uno de los mayores retos desde el punto de vista de localización. Son muchos los servicios de localización que requieren del posicionamiento de un subconjunto de nodos. Un caso especialmente crítico es el que involucra tareas de operación y mantenimiento de la red ad hoc, como puede ser el caso de protocolos de encaminamiento basado en la posición de los nodos de la red [STO02]. Este tipo de tareas requieren de sistemas de localización con características singulares. Normalmente, éstas se resumen en una alta precisión, una baja latencia, escasos requerimientos computacionales y una alta escalabilidad.

El procedimiento presentado tiene por objetivo el posicionamiento conjunto de nodos en redes ad hoc, manteniendo un compromiso adecuado entre precisión y escalabilidad del sistema de localización. Para ello se basa en el procedimiento reivindicado en [ESP200800454] y presentado y evaluado en [MB08] y [MB08B], que permite el posicionamiento de un nodo en una red ad hoc de forma pasiva. En la presente, dicho procedimiento se mejora proporcionando un mecanismo que permite extender el posicionamiento pasivo de un nodo (objetivo habitual del sistema de localización) , a un conjunto de nodo.

Referencias [ESP200800454] Francisco Barceló, Israel Martín. Sistema y procedimiento de localización basados en medidas pasivas de diferencias temporales tomadas a partir de escuchas de tiempo de llegada de otros nodos. Patente solicitada el 11 de febrero de 2008.

[MB08] I. Martin-Escalona, F. Barcelo-Arroyo, “A New Time-Based Algorithm for Positioning Mobile Terminals in Wireless Networks, ” EURASIP Journal on Advances in Signal Processing, vol. 2008, no. 17, pp. 1-10, Enero 2008.

[MB08B] I. Martin-Escalona, F. Barcelo-Arroyo, “Impact of geometr y on the accuracy of the passive-TDOA algorithm”,...

1. Procedimiento empleado en nodos pasivos de redes colaborativas para el cálculo de medidas de distancias (diferencias y distancias absolutas) entre pares de nodos pertenecientes a la red de forma pasiva, es decir escuchando el medio radio, y caracterizado por el hecho de que comprende las siguientes etapas:

A) Escuchar el medio compartido a la espera de dos ciclos de mensajes de localización de ida (E1 (1) yE1 (2) ) y vuelta (R1 (1) yR1 (2) ) emitidos por un nodo activo sobre el mismo nodo de referencia.

B) Calcular los tiempos en los que se reciben los mensajes de ida (T1 yT2) y vuelta (T3 yT4) en función de la información extraída a partir de los mensajes E1 (1) , E1 (2) , R1 (1) yR1 (2) captados por el nodo pasivo.

C) Generar diferencias temporales con los tiempos extraídos en la etapa (B) : T3-T1 yT4-T2.

D) Obtener la diferencia temporal de tránsito entre los ciclos como T2-T3-τ, donde τ es un valor temporal fijo y conocido por todos los nodos de la red, calculado como el tiempo entre la recepción del mensaje R1 (1) en el nodo activo y la emisión del mensaje E1 (2) por parte de ese mismo nodo.

E) Calcular en el nodo pasivo la distancia del nodo activo al nodo de referencia, a partir de los tiempos obtenidos en las etapas (C) y (D) .

2. Procedimiento según reivindicación 1 caracterizado por el hecho de que comprende en el nodo pasivo una etapa posterior (F) de obtención de la posición del nodo activo a partir de las diferencias temporales calculadas según procedimiento descrito en reivindicación 1, empleando para ello cualquier técnica TOA.

3. Procedimiento según reivindicaciones 1 o 2, caracterizado por el hecho de que comprende una etapa posterior (G) en el nodo pasivo para el cálculo de su propia localización a partir de las medidas temporales calculadas, empleando para ello cualquier técnica TDOA.

4. Sistema de localización pasiva en redes colaborativas, es decir que requiere únicamente de la escucha de paquetes que circulan por el medio radio, y caracterizado por el hecho de que un nodo de la red (nodo pasivo) calcula de forma conjunta su posición y la de otro nodo de la red (nodo activo) , y utilizando los procedimientos descritos en las reivindicaciones2y3.