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 la información de la 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 las 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 nodopuede determinar su propia ubicación y que la fuente conoce la ubicación del destino. Con esta información, un mensaje se puede enrutar al destino sin conocimiento de la topología de la red o un descubrimiento de ruta previo.
Enfoques
Hay 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 frontal . El reenvío codicioso intenta acercar el mensaje al destino en cada paso utilizando solo información local. Así, cada nodo reenvía el mensaje al vecino más adecuado desde un punto de vista local. El vecino más adecuado puede ser el que minimiza la distancia al destino en cada paso (Codicioso). 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 los nodos de una determinada constelación. Se sabe que la estrategia básica codiciosa y MFR están libres de bucles, mientras que NFP y Compass Routing no lo son. [5]
El reenvío codicioso puede conducir 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 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 se pueda entregar un mensaje al destino. La combinación de reenvío codicioso y enrutamiento facial se propuso por primera vez en 1999 con el nombre de 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 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]
Embebido codicioso
Aunque originalmente se desarrolló 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, no relacionado 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 que utiliza estas posiciones se denomina incrustación codiciosa . [9]
Ver también
Referencias
- ↑ a b Ruehrup, Stefan (2009). Liu; Chu; Leung (eds.). Teoría y práctica del enrutamiento geográfico (PDF) . Redes inalámbricas ad hoc y de sensores: arquitecturas, algoritmos y protocolos. Ciencia de Bentham.
- ^ Takagi, H .; Kleinrock, L. (marzo de 1984). "Rangos de transmisión óptimos para terminales de radio por paquetes distribuidos aleatoriamente". Transacciones IEEE sobre comunicaciones . 32 (3): 246–257. CiteSeerX 10.1.1.64.9747 . doi : 10.1109 / TCOM.1984.1096061 .
- ^ Finn, Gregory G. (marzo de 1987). "Problemas de enrutamiento y resolución de problemas en redes de gran escala metropolitana" (PDF) . Universidad del Sur de California, ISI / RR-87-180. Cite journal requiere
|journal=
( ayuda ) - ^ Stojmenovic, Ivan (2002). "Enrutamiento basado en posición en redes ad hoc". Revista de comunicaciones IEEE . 40 (7): 128-134. CiteSeerX 10.1.1.6.6012 . doi : 10.1109 / MCOM.2002.1018018 .
- ^ Stojmenovic, Ivan; Lin, Xu (2001). "Algoritmos de enrutamiento híbrido de ruta única / inundación sin bucles con entrega garantizada para redes inalámbricas". Transacciones IEEE en sistemas paralelos y distribuidos . 12 (10): 1023–1032. CiteSeerX 10.1.1.67.7527 . doi : 10.1109 / 71.963415 .
- ^ Bose, P .; Morin, P .; Stojmenovic, I .; Urrutia, J. (1999). "Enrutamiento con entrega garantizada en redes inalámbricas ad hoc". Proc. del 3er taller internacional sobre algoritmos y métodos discretos para la informática y las comunicaciones móviles (DIALM '99) . págs. 48–55. doi : 10.1145 / 313239.313282 .
- ^ Djenouri, Djamel; Balasingham, Ilangko (2011). "Enrutamiento localizado QoS modular basado en diferenciación de tráfico para redes de sensores inalámbricos". Transacciones IEEE sobre informática móvil . 10 (6): 797–809. doi : 10.1109 / TMC.2010.212 . S2CID 11139687 .
- ^ Kim, Y; Ramesh Govindan ; Karp, Brad .; Scott Shenker (2005). "Sobre las trampas del enrutamiento de caras geográficas". Actas del taller conjunto de 2005 sobre los fundamentos de la informática móvil . págs. 34–43. doi : 10.1145 / 1080810.1080818 .
- ^ Rao, Ananth; Ratnasamy, Sylvia; Papadimitriou, Christos H .; Shenker, Scott ; Stoica, Ion (2003), "Enrutamiento geográfico sin información de ubicación", Proc. Noveno ACM Mobile Computing and Networking (MobiCom) , págs. 96–108.