Selección de ruta en redes inalámbricas.

Un sistema para descubrir una ruta entre un nodo fuente (A) y un nodo destino (E) en una red inalámbrica,

quecomprende:

medios para recibir un mensaje de petición de ruta (RREQ) enviado por dicho nodo fuente (A);

medios para responder a dicho mensaje de petición de ruta ( 5 RREQ) con un mensaje de respuesta de ruta(RREP) por un primer nodo intermedio (B) que tiene una ruta válida a dicho nodo destino (E);

medios para actualizar dicho mensaje de petición de ruta (RREQ); y

medios para volver a inundar dicha red inalámbrica con dicho mensaje de petición de ruta actualizado;

caracterizado porque dicho primer nodo intermedio (B) comprende medios para responder a dicho mensaje depetición de ruta (RREQ) cuando está fijado un marcador (IR) en dicho mensaje de petición de ruta (RREQ) y porquedicho primer nodo intermedio (B) además comprende medios para volver a inundar dicha red inalámbrica con dichomensaje de petición de ruta (RREQ) con dicho marcador (IR) reiniciado.

Selección de ruta en redes inalámbricas

Campo de la invención La presente invención se refiere a redes inalámbricas y, en particular, a redes en malla inalámbricas. Muy específicamente la presente invención se refiere al procesamiento de mensajes de petición de ruta en protocolos de encaminamiento bajo demanda.

Antecedentes de la invención Los protocolos de encaminamiento bajo demanda, por ejemplo, el protocolo de encaminamiento de Vector de Distancia Bajo Demanda Ad Hoc (AODV) definido por el grupo de trabajo MANET en el IETF, usan un mecanismo de Petición de Ruta y Respuesta de Ruta para establecer rutas entre dos nodos en redes en malla/ad hoc inalámbricas. Cuando un nodo fuente quiere enviar paquetes/tramas de datos a un nodo destino, el nodo fuente descubre la ruta al destino inundando un mensaje de Petición de Ruta (RREQ) sobre la red si el nodo fuente no tiene y necesita una ruta válida al nodo destino. Se crea una ruta inversa de vuelta a la fuente por los nodos en la red según reciben y reenvían la RREQ. Cuando un nodo recibe una RREQ, el nodo de recepción responde a esta petición generando un mensaje de Respuesta de Ruta (RREP) si o bien: (1) el nodo de recepción es en sí mismo el destino, o bien (2) el nodo de recepción tiene una ruta válida al destino y el marcador “solamente destino” (‘D’) en la RREQ NO está fijado. La RREP se reenvía en unidifusión al nodo fuente a través de la ruta inversa establecida y de esta manera se crea una ruta hacia delante al destino en los nodos intermedios y eventualmente en el nodo fuente. Las rutas establecidas expiran si no se usan dentro de un tiempo de vida de ruta dado.

En el AODV, el marcador “solamente destino” del mensaje de RREQ se fija por el nodo fuente y no se cambia por los nodos intermedios. Si el marcador “solamente destino” se fija en la RREQ por el nodo fuente, los nodos intermedios no responden a la RREQ con un mensaje de RREP incluso si el nodo intermedio/de recepción tiene una ruta válida al nodo destino. Reenvía/vuelve a inundar la RREQ a sus vecinos. Solamente el nodo destino responde a esta RREQ. En este modo de operación, la latencia de descubrimiento de ruta puede ser grande aunque la mejor ruta hasta la fecha entre el nodo fuente y el nodo destino sea descubierta eventualmente en el proceso. La baja latencia es muy importante para aplicaciones en tiempo real tales como comunicaciones de voz y vídeo.

Si el marcador “solamente destino” no está fijado por el nodo fuente, entonces cualquier nodo intermedio con una ruta válida al nodo destino responde a la RREQ con un mensaje de RREP. El mensaje de RREP se envía de vuelta al nodo fuente en unidifusión y establece una ruta hacia delante al nodo destino. Si el marcador “RREP Gratuita” (‘G’) en la RREQ está fijado, este nodo intermedio también hace la unidifusión de una RREP gratuita al nodo destino de manera que el nodo destino aprende de las rutas al nodo fuente. No obstante, en el AODV, si un nodo intermedio genera una RREP (debido a que el nodo intermedio tiene una ruta válida al nodo destino) , entonces el nodo intermedio descarta la RREQ. Con este planteamiento, el nodo fuente puede descubrir una ruta al nodo destino más rápidamente debido a que el nodo fuente no tiene que esperar la respuesta del nodo destino. No obstante, la mejor ruta extremo a extremo puede no ser descubierta debido a que la ruta almacenada en caché en el nodo intermedio puede no ser la mejor ruta al nodo destino. Las métricas pueden haber cambiado debido a las dinámicas de las redes inalámbricas haciendo la ruta almacenada en caché menos deseable. Es decir, debido a los cambios en la topología de red, la métrica de encaminamiento, etc. es posible que la ruta almacenada en caché en el nodo intermedio pueda llegar a ser peor o que otras rutas con una métrica extremo a extremo mejor puedan llegar a estar disponible haciendo otras rutas más deseables.

Perkins et al. en “Ad-hoc On-Demand Vector Routing” (en las ACTAS del WMCSA, el 25 de febrero de 1999, XP002173721) describe un algoritmo de “Encaminamiento de Vector Bajo Demanda Ad hoc” (AODV) para la operación de encaminamiento en una red inalámbrica sin punto de acceso centralizado. Este algoritmo se basa en entradas de tabla de establecimiento de ruta de manera dinámica en nodos intermedios y usa un mecanismo de Petición de Ruta (RREQ) y una Respuesta de Ruta (RREP) . Este algoritmo reduce el retardo en encontrar una ruta al nodo destino no obstante, a diferencia del mecanismo de encaminamiento de fuente extremo a extremo, el sistema no es adecuado para descubrir la mejor (es decir con la métrica más baja) ruta extremo a extremo. Debido a que el mensaje de RREQ no se propaga al nodo destino cuando se encuentra una ruta válida en un nodo intermediario, la métrica de ruta extremo a extremo no se notifica sistemáticamente en mensajes de RREP al nodo fuente y la ruta válida almacenada en caché en el nodo intermedio no puede ser la mejor ruta al nodo destino.

La WO 01/41375 describe un algoritmo para el protocolo de encaminamiento de red ad hoc, o bien en base a encaminamiento de fuente o bien encaminamiento de vector de distancia. Según la WO 01/41375, o bien los mensajes de petición de encaminamiento de fuente ordinario o bien de petición de encaminamiento actualizado, identificados por un marcador, se inundan en la red tras la aparición de un suceso predeterminado tal como una expiración del temporizador, un enlace roto… No obstante, la WO 01/41375 falla al describir un sistema adecuado tanto para descubrir rápidamente una ruta entre un nodo fuente y un nodo destino como para descubrir la mejor ruta entre una fuente y un nodo destino en respuesta a una petición de la fuente mientras que limita los mensajes de petición/respuesta en la red.

La EP1467524 describe un algoritmo para un protocolo de encaminamiento de red ad hoc adecuado para consideración de calidad de servicio entre la cual están el retardo y el ancho de banda en comunicaciones. Según la EP1467524, además del más bajo coste del enlace, y el número de secuencia, se consideran otros criterios tales como el ancho de banda del enlace para establecer la mejor ruta entre nodos. No obstante, como para la citada técnica anterior, la EP1467524 falla al describir un sistema adecuado tanto para descubrir rápidamente una ruta entre una fuente y un nodo destino como para descubrir la mejor ruta entre una fuente y un nodo destino.

El problema resuelto por la presente invención es cómo usar el mecanismo de RREQ y RREP para descubrir rápidamente la mejor ruta entre un nodo fuente y uno o más nodos destino.

Compendio de la invención La presente invención describe un método y sistema para procesar/reenviar mensajes de Petición de Ruta (RREQ) y generar mensajes de Respuesta de Ruta (RREP) en protocolos de encaminamiento bajo demanda, de los cuales el AODV es un ejemplo, de manera que la mejor ruta se pueda descubrir sin incurrir en retardo/latencia de descubrimiento de ruta significativo en redes en malla/ad hoc inalámbricas. Específicamente, cuando un nodo fuente quiere descubrir la ruta a un nodo destino, el nodo fuente inunda la red con un mensaje de RREQ con el nodo destino especificado en la lista de destinos y el campo de métrica inicializado a 0. El mensaje de RREQ contiene un nuevo marcador de “Respuesta Intermedia (IR) ” para cada nodo destino. El nodo fuente fija el marcador correspondiente al nodo destino en la RREQ cuando inicia la inundación de la RREQ para descubrir una ruta al (a los) nodo (s) destino. Durante la inundación de RREQ, el primer nodo intermedio con una ruta válida al nodo destino responde a la RREQ con un mensaje de RREP. El mensaje de RREP se envía en unidifusión hacia el nodo fuente y por ello establece rápidamente una ruta hacia delante temporal al destino. De esta manera, el nodo fuente puede usar esta ruta hacia delante temporal para enviar paquetes/tramas de datos con un retardo/latencia de descubrimiento de ruta bajo. El primer nodo intermedio reinicia/borra el marcador “IR” en el mensaje de RREQ y reenvía el enlace descendente del mensaje de RREQ actualizado hacia el nodo destino. Dado que el marcador “IR” en la RREQ ha sido reiniciado, los nodos intermedios de enlace descendente no responderían a esta RREQ y solamente propagarían la RREQ incluso si los nodos intermedios de enlace descendente tienen una ruta válida al (a los) nodo (s) destino. Las RREQ eventualmente alcanzan el (los) nodo (s) destino. El (los) nodo (s) destino pueden seleccionar la mejor ruta/camino en base a las métricas extremo a extremo y enviar una nueva RREP de vuelta al nodo fuente para establecer la mejor ruta... [Seguir leyendo]

1. Un sistema para descubrir una ruta entre un nodo fuente (A) y un nodo destino (E) en una red inalámbrica, que comprende:

medios para recibir un mensaje de petición de ruta (RREQ) enviado por dicho nodo fuente (A) ;

medios para responder a dicho mensaje de petición de ruta (RREQ) con un mensaje de respuesta de ruta (RREP) por un primer nodo intermedio (B) que tiene una ruta válida a dicho nodo destino (E) ;

medios para actualizar dicho mensaje de petición de ruta (RREQ) ; y

medios para volver a inundar dicha red inalámbrica con dicho mensaje de petición de ruta actualizado;

caracterizado porque dicho primer nodo intermedio (B) comprende medios para responder a dicho mensaje de petición de ruta (RREQ) cuando está fijado un marcador (IR) en dicho mensaje de petición de ruta (RREQ) y porque dicho primer nodo intermedio (B) además comprende medios para volver a inundar dicha red inalámbrica con dicho mensaje de petición de ruta (RREQ) con dicho marcador (IR) reiniciado.

2. El sistema según la reivindicación 1, en donde dichos medios para actualización además comprenden medios para borrar un marcador (IR) y medios para actualizar una métrica (MÉTRICA) en dicho mensaje de petición de ruta (RREQ) con una métrica acumulativa de dicha ruta entre dicho nodo fuente (A) y dicho nodo destino (E) de dicha red inalámbrica.

3. El sistema según cualquiera de las reivindicaciones 1 a 2, en donde dichos medios para responder establecen por ello una ruta hacia delante temporal entre dicho nodo fuente (A) y dicho nodo destino (E) de dicha red inalámbrica.

4. El sistema según la reivindicación 3, en donde la ruta hacia delante temporal está disponible para transmisión de datos tras la recepción de dicho mensaje de respuesta de ruta (RREP) por dicho nodo fuente (A) , en donde dicha ruta es una ruta de respuesta a métricas extremo a extremo y además en donde dicho mensaje de respuesta de ruta (RREP) es un primer mensaje de respuesta de ruta.

5. El sistema según la reivindicación 4, que además comprende medios para recibir un mensaje de respuesta de ruta adicional desde dicho nodo destino, dicho mensaje de respuesta de ruta adicional que incluye dicha ruta de respuesta a métricas extremo a extremo entre dicho nodo destino y dicho nodo fuente en base a métricas acumulativas en mensajes de petición de ruta recibidos por dicho nodo destino, en donde si dicha ruta hacia delante es dicha ruta de respuesta a métricas extremo a extremo entonces dicho mensaje de respuesta de ruta adicional sirve como una confirmación y si dicha ruta hacia delante temporal no es una ruta de respuesta a métricas extremo a extremo entonces dicho mensaje de respuesta de ruta adicional sirve para establecer dicha ruta de respuesta a métricas extremo a extremo tras la recepción de dicho mensaje de respuesta de ruta adicional por dicho nodo fuente.

6. El sistema según cualquiera de las reivindicaciones 1 a 5, en donde dicha red inalámbrica es una red en malla inalámbrica, en donde dicho mensaje de respuesta de ruta de dichos medios para responder es unidifusión a dicho nodo fuente, en donde una dirección de dicho nodo destino es una de una dirección del protocolo de internet y una dirección de control de acceso al medio, en donde dicho nodo destino incluye nodos destino que están asociados con uno de un intermediario y un punto de acceso.