El enrutamiento geográfico (también llamado geoenrutamiento [1] o enrutamiento basado en la posición ) es un principio de enrutamiento que se basa en la información de la posición geográfica . Se propone principalmente para redes inalámbricas y se basa en la idea de que el origen envía un mensaje a la ubicación geográfica del destino en lugar de utilizar la dirección de red . En el ámbito de las redes de radio por paquetes , la idea de utilizar información de posición para el enrutamiento se propuso por primera vez en los años 80 [2] para redes de interconexión. [3] El enrutamiento geográfico requiere que cada nodo pueda determinar su propia ubicación y que el origen conozca la ubicación del destino. Con esta información, se puede enrutar un mensaje al destino sin conocer la topología de la red ni descubrir la ruta previamente.
Existen varios enfoques, como estrategias de ruta única, de ruta múltiple y basadas en inundaciones (ver [4] para una encuesta). La mayoría de las estrategias de ruta única se basan en dos técnicas: reenvío codicioso y enrutamiento facial . El reenvío codicioso intenta acercar el mensaje al destino en cada paso utilizando únicamente información local. Así, cada nodo reenvía el mensaje al vecino que sea más adecuado desde el punto de vista local. El vecino más adecuado puede ser aquel 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 fuente-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 de una determinada constelación. Se sabe que la estrategia codiciosa básica y MFR no tienen bucles, mientras que NFP y Compass Routing no lo son. [5]
El reenvío codicioso puede llevar a un callejón sin salida, donde no hay ningún vecino más cerca del destino. Luego, el enrutamiento facial ayuda a recuperarse de esa situación y a encontrar un camino a otro nodo, donde se puede reanudar el reenvío codicioso. Es necesaria una estrategia de recuperación, como el enrutamiento facial, para garantizar que un mensaje pueda entregarse al destino. La combinación de reenvío codicioso y enrutamiento facial se propuso por primera vez en 1999 con el nombre GFG (Greedy-Face-Greedy). [6] Garantiza la entrega en el llamado modelo de red de gráficos de disco unitario. Varias variantes, que se propusieron más tarde [7] , también para gráficos de discos no unitarios, se basan en los principios de GFG. [1]
El enrutamiento de caras depende de un subgrafo plano en general; sin embargo, la planarización distribuida es difícil para redes de sensores inalámbricos reales y no se adapta 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 con un punto en un espacio virtual, sin relación con su posición física. El proceso de encontrar un conjunto de posiciones virtuales para los nodos de una red de modo que se garantice el éxito del enrutamiento geográfico utilizando estas posiciones se denomina incrustación codiciosa . [9]