El enrutamiento geográfico (también llamado georouting [1] o enrutamiento basado en la posición ) es un principio de enrutamiento que se basa en información de posición geográfica . Se propone principalmente para redes inalámbricas y se basa en la idea de que la fuente envía un mensaje a la ubicación geográfica del destino en lugar de utilizar la dirección de red . En el área de redes de radio por paquetes , la idea de utilizar información de posición para el enrutamiento se propuso por primera vez en la década de 1980 [2] para redes de interconexión. [3] El enrutamiento geográfico requiere que cada nodo pueda determinar su propia ubicación y que la fuente conozca la ubicación del destino. Con esta información, se puede enrutar un mensaje al destino sin conocimiento de la topología de la red o un descubrimiento de ruta previo.
Existen varios enfoques, como estrategias de ruta única, de ruta múltiple y basadas en inundación (consulte [4] para una encuesta). La mayoría de las estrategias de ruta única se basan en dos técnicas: reenvío codicioso y enrutamiento de cara . El reenvío codicioso intenta acercar el mensaje al destino en cada paso utilizando solo información local. Por lo tanto, cada nodo reenvía el mensaje al vecino que sea más adecuado desde un punto de vista local. El vecino más adecuado puede ser el que minimice la distancia al destino en cada paso (Greedy). Alternativamente, se puede considerar otra noción de progreso, a saber, la distancia proyectada en la línea de origen-destino (MFR, NFP), o el ángulo mínimo entre el vecino y el destino (Compass Routing). No todas estas estrategias están libres de bucles, es decir, un mensaje puede circular entre nodos en una determinada constelación. Se sabe que la estrategia básica greedy y MFR están libres de bucles, mientras que NFP y Compass Routing no lo están. [5]
El reenvío codicioso puede llevar a un callejón sin salida, donde no hay ningún vecino más cercano al destino. Entonces, el enrutamiento de caras ayuda a recuperarse de esa situación y encontrar una ruta a otro nodo, donde se puede reanudar el reenvío codicioso. Una estrategia de recuperación como el enrutamiento de caras es necesaria para asegurar que un mensaje pueda ser entregado al destino. La combinación de reenvío codicioso y enrutamiento de caras fue propuesta por primera vez en 1999 bajo el nombre GFG (Greedy-Face-Greedy). [6] Garantiza la entrega en el llamado modelo de red de gráfico de disco unitario. Varias variantes, que se propusieron más tarde [7] , también para gráficos de disco no unitario, se basan en los principios de GFG. [1]
El enrutamiento de caras depende de un subgrafo planar en general; sin embargo, la planarización distribuida es difícil para las redes de sensores inalámbricos reales y no se escala bien a entornos 3D. [8]
Aunque originalmente se desarrollaron como un esquema de enrutamiento que utiliza las posiciones físicas de cada nodo, los algoritmos de enrutamiento geográfico también se han aplicado a redes en las que cada nodo está asociado a un punto en un espacio virtual, no relacionado con su posición física. El proceso de encontrar un conjunto de posiciones virtuales para los nodos de una red de manera que se garantice el éxito del enrutamiento geográfico que utiliza estas posiciones se denomina incrustación voraz . [9]