martes, 21 de mayo de 2013

Ubicación en redes ad hoc inalámbricas de sensores distribuidos

Resumen del documento " Location in distributed ad-hoc wireless sensor networks" de los autores Beutel J,  Rabaey J.M., Savarese C.

Introducción

En la evolución de las redes ad-hoc, los nodos de sensores inalámbricos han dependido en gran medida de la capacidad de establecer la información de su posición. Los algoritmos que se presentan en este documento se basan en mediciones de alcance entre pares de nodos y las coordenadas a priori de baja densidad. Una vez establecidas, estas posiciones se propagan a los nodos más distantes, lo que cubre la entera red para crear un mapa exacto de sí mismo. Los principales obstáculos son la superación de las inexactitudes en las mediciones tan grande como 50%, así como el desarrollo de aproximaciones iniciales para las ubicaciones del nodo en grupos con pocos o ningún nodos de anclaje. Las soluciones a estos problemas se presentan y discuten, con error de posición como principal indicador. Los algoritmos se comparan de acuerdo a la posición error, la escalabilidad y la comunicación y necesidades de cálculo.Los primeros simulaciones producen errores de posición media de 5% en la presencia tanto de gama y de inexactitudes de posición inicial.

La red inalámbrica Ad-hoc de sensores y actuadores tiene muchos atractivos de aplicaciones, por ejemplo Control ambiental y monitoreo, habitaciones inteligentes, control de robots, sistemas de inventarios,juguetes interactivos y mundos virtuales. El posicionamiento es un factor clave para muchas de estas aplicaciones. Los datos del sensor sin coordenadas completas (esto es indicación de la hora y la ubicación xyz) es casi inútil. Si bien el Sistema de Posicionamiento Global (GPS) es una solución para la localización en un entorno al aire libre, no existe la opción para ambiente interior.

Problema de posicionamiento de una red multihop

Una red de sensores consiste típicamente en un gran número de nodos con una distribución densa. Para reducir el consumo de energía atribuido para la comunicación y para minimizar la interferencia, todos los nodos sólo pueden comunicarse con sus vecinos inmediatos resultantes en una malla de conexiones. El agotamiento de un área local se puede producir cuando los nodos móviles se mueven.



A veces puede ocurrir que una partición de una red pierde contacto al resto de la red debido al movimiento o obstáculos que bloquean las señales de radio. Para evitar que esto suceda, el rango de potencia de las radios se ajusta adaptativamente para que cada nodo tenga un razonable número de nodos vecinos en cualquier punto en el tiempo. En otras palabras, se asegura que el gráfico de la red es generalmente bien conectado.
La actividad de la red en las redes de sensores es baja y al azar.Muchos nodos serán estacionarios para la mayoría de las veces, lo que permite largos períodos de iteración. Dentro de este marco estático, algunos nodos pueden moverse con movilidad limitada.

Navegación

La navegación con técnicas de radiolocalización consta de dos componentes:mediciones de distancia y la triangulación. Distancia o rango las mediciones se pueden basar en diferentes variables físicas: por la intensidad de la señal (RSSI), ángulo de llegada (AOA), el tiempo de llegada(TOA) o la distancia-tiempo de llegada (TDOA) de una señal. Los nodos se pueden utilizar para resolver un problema 3D-triangulación, si estos nodos se encuentran en una ubicación conocida, la posición absoluta puede darse en referencia a este sistema inercial, como se hace para el sistema GPS.
En general, el problema de triangulación se puede formular de la siguiente manera:dado un conjunto de referencias X,, Y, Z, y un conjunto de rango medir Ri, un sistema de ecuaciones lineales necesita resolverse para la U desconocida.


Las soluciones de navegación pueden ser clasificados en base a la exactitud,disponibilidad y costo (hardware, ciclos de cálculo, la latencia y consumo de energía). Por otra parte, se puede diferenciar entre y absoluta posicionamiento relativo, donde los medios absolutos con respecto a un punto de referencia y un mapa, mientras que la relativa no implica ninguno de ellos y se centra en el descubrimiento de topología.

Desafíos de localización en redes de sensores

Cuando es aplicada una red de sensores ad-hoc, esta radiolocalización se enfrenta a nuevas complicaciones: referencias dispersas que no son directamente visibles por todos los nodos en la red, limitada precisión en las mediciones de distancia, y la necesidad de implementación en recursos limitados. Nodos de anclaje o nodos con un conocimiento previo de sus ubicaciones con respecto a una coordenada global del sistema, se supone que es escasa y se encuentra al azar. Al igual que otros nodos de sensores, el rango de comunicación se limita a su vecindad inmediata. Esto hace que sea difícil, si no es que imposible,para los nodos que soliciten, o nodos que intentan calcular sus posiciones,para adquirir suficientes puntos de referencia para llevar a cabo la tradicional triangulación. Sólo se supone que habrá al menos cuatro nodos de anclaje en una red conectada.

La precisión obtenida mediante la triangulación depende en gran medida en la geometría de las referencias de posición, la configuración de los nodos de red, y la exactitud de las mediciones de alcance. Los rangos de transmisión cortos de 1 a 10 m resultan en un inaceptablemente numero de altas demandas de sincronización de 3pseg por cm de resolución, cuando las técnicas TDOA son empleadas. Enfoques AOA requieren costosas redes de antenas en cada nodo. Estos detalles hacen estas solución es poco atractivas, dejando la intensidad de señal recibida (RSSI o)como el candidato ideal para mediciones de distancia. Dado una conocida potencia de transmisión y un buen modelo de canal inalámbrico,la distancia entre el transmisor y el receptor se puede estimar sobre la base de la potencia recibida. Por desgracia, la exactitud de estos mediciones de alcance de RSSI es altamente sensible a la multi-ruta, la decoloración,sin línea de vista, y otras fuentes de interferencia,que pueden dar lugar a grandes errores. Estos errores se pueden propagara través de todos los cálculos de triangulación posteriores, dando lugar a inútil información.

Afortunadamente, las redes de sensores poseen dos propiedades que pueden ayudar a superar estas inquietudes: la interconexión densa conduce a la redundancia en las mediciones de distancia, la movilidad limitada lo que permite tiempos de observación largos y la eliminación de algunos de los efectos de desvanecimiento rápido a través de la integración.

Posicionamiento local

Triangulación

Considerando el siguiente escenario: un nodo con una posición desconocida recibe mediciones de distancia (con baja precisión) de una gran número (> 3) de los nodos vecinos. Usando un mínimo de media cuadrados se acercan a la solución de la triangulación, el problema produce una solución con una precisión que es sustancialmente superior a lo que podría esperarse de las mediciones de distancia confiables.Las figuras siguientes muestran los resultados de posicionamientos simulados.




Descubrimiento de la topología

También vale la pena considerar el problema inverso: un nodo (con una posición conocida) recibe mediciones de alcance de un gran número de nodos vecinos con posición desconocida. Esta información una vez más, se puede utilizar para resolver un problema de posicionamiento local. Sin embargo,lo mejor que se puede lograr en estas condiciones es una resolución de los ángulos entre los nodos, o, en otras palabras, la topología de la red. Sólo el posicionamiento relativo se puede derivar.Pero, de nuevo, la redundancia en la información ayuda a aumentar la resolución de los ángulos obtenidos. Mientras que una formulación LMS puede una vez más, ser construido, se presenta en cambio un algoritmo constructivo que sólo requiere cómputo limitado. El algoritmo Coordenadas base (ABC) determina las ubicaciones de los nodos desconocidos de una en una en el orden que establecen la comunicación, haciendo suposiciones donde es necesario, y compensar los errores a través de correcciones y cálculos redundantes a medida que más información esté disponible.Se necesitan estos supuestos al principio con el fin de hacer frente al conjunto de ecuaciones que presentan los primeros nodos.Esta descripción del algoritmo general asume la perspectiva de nodo n0.

El algoritmo comienza con el supuesto de que n0 se encuentra en (0,0,0). El primer nodo para establecer la comunicación con n0, n1, se supone que se encuentra en (r01, 0, 0), donde r01es la RSSI determinada distancia entre n0 y nl.La ubicación del siguiente nodo, n2, entonces puede ser resuelto de forma explícita,dados dos supuestos:se supone que la raíz cuadrada encuentra y2 para producir un resultado positivo,z2 y se supone que es 0.


Posicionamiento global

Mientras que los enfoques anteriores ayudan a mejorar los problemas en la precisión de posicionamiento local en la presencia de mediciones no fiables,no abordan el reto de posicionamiento global que plantea el ad-hoc de redes de sensores inalámbricos. Esta red representa una carga innecesaria en lo que respecta a la implementación simple,el consumo de energía, y la arquitectura de red, la única opción es participar en un enfoque cooperativo que van explote la alta conectividad de la red para traducir el reto de posicionamiento global en una serie de problemas locales distribuidos de optimización iterativa que convergen a una solución global mediante la interacción con los demás. La ventaja de este enfoque es que no se necesitan los recursos mundiales o comunicaciones. La desventaja es que la convergencia puede tardar algún tiempo y que los nodos con una alta movilidad pueden ser difíciles de cubrir. Afortunadamente, esto no es un problema real en redes de sensores, donde los nodos rara vez se mueven y los tiempos de descubrimiento largos son aceptables dada la larga vida útil de la red. Este enfoque de cooperación es, a nuestro entender,bastante original. Enfoques existentes para la localización en redes de sensores tienden a confiar en un motor de cálculo global que recibe las mediciones de distancia y los convierte en un problema de optimización global. La desventaja de este enfoque inteligente es que se necesita un recurso global que desafíe la naturaleza ad-hoc de la red, y que toda la gama y la información de la posición tenga que ser enviado de ida y vuelta al nodo, dando lugar a cuellos de botella de enrutamiento y la disipación de la energía necesaria.

En las metodologías propuestas, cada nodo juega el mismo papel, y ejecuta varias veces y al mismo tiempo las siguientes funciones:

  • Recibe alcance y la información de ubicación de la vecina
  • Resolver un problema de localización local
  • Transmite los resultados obtenidos a los nodos vecinos

Después de que el sistema ha encontrado una solución, las actualizaciones sólo rara vez necesitadas y se activarán por un nodo móvil en una área localizada de la red.El modo de actualización se invoca después del inicio y nodos en movimiento,actualizan la información de posición como nodos móviles cambiando su ubicación física. Aquí se presenta brevemente una serie de posibles enfoques y algunos principios.

Descubrimiento de la topología global

En este enfoque, cada nodo asume inicialmente estar en el centro del sistema de coordenadas y realiza una detección local de la topología (utilizando el algoritmo ABC). La información resultante se envía a los nodos vecinos. Cada nodo elimina un grado de libertad en el espacio de coordenadas,y las fuerzas de los nodos vecinos para transformar linealmente su propio sistema de coordenadas (tanto a partir de una transposición y la perspectiva de rotación).La información se propaga a través del sistema y, finalmente, hace que el sistema coincida en un solo espacio de coordenadas global. Las primeras simulaciones mostró que este enfoque era insuficiente para superar la propagación de errores iniciales a distancia, produciendo grandes errores de posición.

El enfoque terreno

El algoritmo proporciona una solución inicial de cada nodo de la red haciendo una expedición multi-hop de las posiciones. En el inicio, el algoritmo ABC se inicia en cada nodo de anclaje. Los nodos solicitantes esperan para propagar a ellos a partir de al menos cuatro nodos. Una triangulación estándar se puede realizar en ese momento. A medida que el número de nodos utilizados por cada nodo solicitante en este procedimiento se incrementa, la exactitud de la posición estima mejora. Teniendo en cuenta que no hay necesidad de llevar a cabo la transformación lineal al final de cada algoritmo ABC que debe corregir la orientación, una topología correcta proporcionará la estimación de la distancia necesaria. En la siguiente figurase muestra la mejora obtenida a partir del algoritmo en comparación con el enfoque global de detección de la topología, que ya explique.



Triangulación local interactiva

Una vez que se obtiene una estimación inicial, la precisión de la localización puede ser mejorada a través de un proceso de refinamiento iterativo. Cada nodo utiliza las coordenadas más recientes calculadas de cada nodo vecino y las mediciones de distancia para volver a calcular sus propias coordenadas.Este proceso se repite varias veces hasta que las posiciones de todos los nodos de la red han coincidido. En la siguiente figura se muestran los resultados de este procedimiento después de 25 iteraciones de un clúster de la red de 10 nodos. Estos resultados sugieren que la exactitud final de estimaciones de posición está influenciadas más por los errores de gama que por errores de posición. Los resultados que se muestran en la figura pasada dan un promedio de error de posición inicial de alrededor de 39% para el terreno en el rango de error del 5%.Aplicando el algoritmo iterativo se reduce después el error a aproximadamente 5%,una mejora de aproximadamente 34%. A pesar de la posición media los errores son bajos después de la etapa de perfeccionamiento,las simulaciones muestran una gran varianza en los valores de error de posición. En un número de casos, el algoritmo iterativo tiende a no coincidir. La tendencia de no coincidir tiene relación con los dos estimaciones de posición inicial y errores.Es necesaria más investigación para determinar técnicas para descubrir y eliminarlas divergencias (por ejemplo, eliminar soluciones improbables desde el principio).La fiabilidad de los resultados producidos es un requisito indispensable de cualquier colocación de redes de sensores.

Conclusiones

Los algoritmos para el posicionamiento de nodos en una red de sensores ad-hoc que explique, demostraron que los errores de posicionamiento resultante a partir de mediciones de alcance inexactas se puede reducir significativamente si se utilizan 7 o más puntos de referencia en una triangulación de 3D. Y es posible ver en las simulaciones que es capaz de producir estimaciones de posición con errores de sólo el 5%.Aunque es necesario realizar y repetir mas experimentos para poder decir con certeza que es un mejor método para el posicionamiento.

Referencias

Beutel, J.; Rabaey, J.M.; Savarese, C. "Acoustics, Speech, and Signal Processing ." , INFOCOM 2004. IEEE International Conference on Salt Lake City, UT (Volumen:4 ), 7-11 Mayo 2001
Resumen | Texto entero: PDF (755KB)

1 comentario: