Resumen: Ad hoc Positioning system

Ad hoc Positioning system

Dragos Niculescu, Badri Nath

Computer Science Department

Rutgers University

Encontrar las localizaciones de cada nodo en una red ad hoc sin la ayuda de GPS es importante en los casos en los que el GPS no este accesible o no sea práctico de usar debido a limitaciones energéticas u otras condiciones. Conociendo la localización, sería posible realizar ruteo suficientemente isotrópico (uniforme en todas las direcciones), sin el uso de grandes tablas de ruteo.

El método que se propone en el paper es un algoritmo de posicionamiento de brinco a brinco distribuido, que funciona como una extensión de tanto el ruteo con posicionamiento GPS para proveer una localización aproximada para todos los nodos de una red donde solo una fracción limitada de nodos tienen capacidad para conocer su localización por sí mismos.

Existen algunos requerimientos que debe satisfacer un algoritmo de posicionamiento.

• Tiene que ser distribuido. En una red muy grande con poca memoria y nodos de banda ancha baja, diseñados para operación intermitente, ir y venir por una topología entera a un servidor en brinco por brinco pondría una carga alta en los nodos cercanos al servidor. Áreas particionadas harían la centralización imposible, y las redes antisotrópicas pondrían aún más carga en los nodos que tienen que soportar más reenvío de tráfico que los demás. Cambiar las topologías haría también que la solución centralizada sea no deseable.
  
• Debe minimizar la catidad de comunicación de nodo a nodo y el poder de cómputo, ya que la comunicación por radio y el procesador son las principales fuentes de gasto de energía de la batería. También es deseable tener una baja complejidad en el envío de señales en caso de que la red cambie de topología.
  
• El sistema de posicionamiento debería de funcionar aún cuando la red esté desconectada. En el contexto de redes sensoras, la información puede ser recolectada más adelante por una estación base que esté sobre volando.
  
• Finalmente debe proveer un posicionamiento absoluto, en el sistema de coordenadas global del GPS, opuesto a las coordenadas relativas debido a las siguientes razones: el posicionamiento relativo puede incurrir a altos costos en el envío de señales en el caso de que la topología cambie, y el posicionamiento absoluto permite un espacio de nombres único, el de las coordenadas GPS.

Algoritmo APS

No es eficiente tener "landmarks" que emitan señales usando gran cantidad de energía para cubrir toda la red por diferentes razones: colisiones con comunicación local, alto uso de energía, y problemas de cobertura al moverse. También, no es aceptable asumir ciertas posiciones para los landmarks, debido a que las aplicaciones que pueden existir puede estar en vuelo sobre áreas inaccesibles, o posiblemente dependiendo de la reconfiguración de la red. 

En el algoritmo algunos nodos (landmarks) conocen sus posiciones, otros nodos infieren los rangos a por lo menos 3 de estos landmarks para estimar sus distancias y calcular su distancia estimada a los vecinos. Los  nodos usan:

•  Medición de fuerza de señal
• Conteo de saltos, un híbrido entre GPS y enrutamiento vector distancia
• Como en el vector distancia, las distancias hacia los landmarks son propagadas brinco a brinco.
• Como en GPS, cada nodo estima su propia localización.

Propagación

Como en el vector de distancia, los vecinos intercambian estimados de las distancias a los landmarks. Para ello se utilizan cuatro métodos posibles:

• "DV-hop": Distancia al landmark, en saltos (vector de distancia estándar)
• Nunca mide la distancia entre vecinos por ser insensible a errores. 
• Cada nodo mantiene una tabla con ${X_{i}, Y_{i}, j_{i}}$  utilizando vector de distancia.
• Cada landmark ${X_{i}, Y_{i}}$ computa una corrección y la inunda en la red, usando la fórmula:
  

• Cada nodo usa la corrección del landmark más cercano y multiplica sus distancias de brincos por la corrección.

                                       

• "Propagación con Distancia DV": 
• Utiliza distancia de viaje, en metros.
• Cada nodo mantiene una tabla ${X_{i}, Y_{i}, d_{i}}$
• Cada landmark ${X_{i}, Y_{i}}$
• Computa una corrección y la inunda en la red, usando:

• Cada nodo usa la corrección de su landmark más cercano y multiplica sus distancias por la corrección.

• "Euclideano": Distancia euclideana al landmark.

• El nodo A mide la distancia a sus vecinos inmediatos B y C.
• Aprende la distancia BC de cualquiera de los dos o posiblemente la infiere, mapeando todos uss vecinos
• B y C conocen sus distancias euclideanas a el landmark L
• A necesita encontrar la diagonal AL.

• "Coordenada": Cordenadas propias de los nodos en un sistema de coordenadas basado en los landmarks.
• Cada landmark $i$ escoge un sistema de coordenadas aleatorios en el cual las coordenadas son ciertas ($XL_i ;  YL_i $), obtenidas por GPS.
• Un nodo N
• Mantiene una tabla ${(X_{i}, Y_{i}), (X_{Li}, Y_{Li}) }$
• Mide distancias a sus nodos vecinos
• Cuanto tiene las coordenadas de hasta 3 nodos computa su propia localización usando el procedimiento GPS.

Conclusión

Un sistema de posicionamiento global utilizando redes adhoc proveen una buena alternativa a un GPS (en cuestiones energéticas y de precisión, siendo mejor APS). 

Básicamente, los nodos en una red adhoc deberían saber su localización en coordenadas globales, tener bajo costo para movilidad, precisión comparable con el rango de comunicación del  del nodo, regiones desconectadas que puedan operar independientemente.  El recalculo de las posiciones de los nodos se hace entonces solo en los nodos en movimiento.

Referencia:

• Niculescu, D. and Nath, B. (2001) Ad hoc positioning system (APS). [PDF], San Antonio, TX: p.2926-2931.
  Disponible en: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=965964
  [Fecha de acceso: 14 de Mayo de 2013].