Método para localizar una ruta entre un nodo de origen (A) y un nodo de destino (E) en una red inalámbrica,

comprendiendo dicho método: La diseminación a través de dicha red inalámbrica de un mensaje de petición de ruta (RREQ) por parte de dicho nodo de origen (A); y La recepción de un mensaje de respuesta de ruta (RREP) a dicho mensaje de petición de ruta (RREQ) procedente de un primer nodo intermedio (B) que tiene una ruta válida hacia dicho nodo de destino (E) caracterizado porque dicho primer nodo intermedio (B) responde a dicho mensaje de petición de ruta (RREQ) cuando se establece una bandera (IR) en dicho mensaje de petición de ruta (RREQ) y porque dicho primer nodo intermedio (B) disemina de nuevo en dicha red inalámbrica dicho mensaje de petición de ruta (RREQ) con dicha bandea (IR) reinicializada.

CAMPO DE LA INVENCIÓN

La presente invención se refiere a redes inalámbricas, y más concretamente, a las redes en malla. Más concretamente, la presente invención se refiere al procesamiento de mensajes de petición de ruta en protocolos de asignación de ruta previa petición.

ANTECEDENTES DE LA INVENCIÓN

Los protocolos de asignación de ruta previa petición, como por ejemplo, el protocolo ad hoc de asignación de ruta de Vector de Distancia previa petición (AODV) definido por el grupo de trabajo MANET del IETF utilizan un mecanismo de Petición de ruta y de Respuesta de Ruta para el establecimiento de rutas entre dos nodos, en redes inalámbricas en malla ad hoc. Cuando un nodo de origen desea enviar paquetes/tramas de datos a un nodo de destino, el nodo de origen descubre la ruta hacia el destino mediante la dispersión de un mensaje de petición de Ruta (RREQ) a través de la red si el nodo de origen carece y necesita una ruta válida hacia el nodo de destino. Los nodos de la red crean una ruta inversa de retorno al origen a medida que reciben y remiten el RREQ. Cuando un nodo recibe un RREQ, el nodo receptor responde a esta solicitud generando un mensaje de respuesta de ruta (RREP) si se da cualquiera de las siguientes situaciones: (1) el propio nodo receptor es el de destino, o (2) el nodo receptor dispone de una ruta válida hacia el destino, y la bandera de “solo destino” (“D”) del RREQ NO0 se encuentra activada. El RREP se envía en modo unidifusión al nodo de origen a través de la ruta inversa establecida y de una ruta directa al destino en los nodos intermedios, y eventualmente, se crea en el nodo de origen. Las rutas establecidas expiran en el caso de que no utilizarse dentro de un período de vida útil de la ruta determinado.

En el protocolo AODV, la bandera de “sólo destino” del mensaje RREQ es fijada por el nodo origen, y no se ve alterada por los nodos intermedios. Si el nodo origen ha fijado en el RREQ la bandera de “sólo destino”, el nodo intermedio no responde al RREQ con un mensaje RREP, aun cuando el nodo intermedio/receptor disponga de una ruta válida hacia el nodo de destino. En cambio, reenvía/difunde el RREQ entre los nodos adyacentes. Tan sólo el nodo de destino responde a este RREQ. En este modo de funcionamiento, la latencia de descubrimiento de la ruta puede ser amplia, aunque eventualmente se descubra en el transcurso del proceso la mejor ruta encontrada hasta el momento entre el nodo de origen y el nodo de destino. Una latencia baja resulta muy importante para las aplicaciones en tiempo real, como las comunicaciones de voz y vídeo.

Si el nodo de origen no ha seleccionado la bandera de “sólo destino”, cualquier nodo intermedio con una ruta válida hacia el nodo de destino responderá al RREQ con un mensaje RREP. El mensaje RREP se devolverá al nodo de origen en modo unidifusión y establecerá una ruta de avance hacia el nodo de destino. Si se fija la bandera “RREP gratuito” (“G”) en el RREQ, este nodo intermedio también transmite en unidifusión un RREP gratuito al nodo de destino, de forma que el nodo de destino aprenda las rutas hacia el nodo de origen. No obstante, en el AODV, si un nodo intermedio no genera un RREP (debido a que el nodo intermedio carece de una ruta válida hacia el nodo de destino) el nodo intermedio descartará entonces el RREQ. Mediante este método, el nodo de origen puede descubrir una ruta hacia el nodo de destino con mayor rapidez, debido a que el nodo de origen no precisa esperar la respuesta del nodo de destino. No obstante, la mejor ruta de extremo a extremo podría no llegar descubrirse, ya que la ruta captada en el nodo intermedio podría no ser la mejor ruta hacia el nodo de destino. Las métricas podrían haber cambiado a causa de la dinámica de las redes inalámbricas, haciendo que la ruta captada resulte menos deseable. Es decir, que debido a los cambios en la topología de la red, la métrica de asignación de ruta, etc. Es posible que la ruta captada en el nodo intermedio pueda ser peor, o que puedan aparecer otras rutas con una mejor métrica de extremo a extremo, haciendo que otras rutas resulten más deseables.

Perkins et al., en el documento “Ad-hoc On-Demand Vector Routing” (en PROCEEDINGS WMCSA, 25 de febrero de 1999, XP002173721) describen un algoritmo de asignación de ruta ad hoc del vector previa petición (AODV) para la operación de asignación de ruta en una red inalámbrica sin un punto de acceso centralizado. Este algoritmo se basa en entradas de tabla de establecimiento dinámico de la ruta en los nodos intermedios, y utiliza un mecanismo de Petición de ruta (RREQ) y de respuesta de ruta (RREQ). Este algoritmo reduce la demora en el hallazgo de una ruta hacia el nodo del destino, pero sin embargo, a diferencia del mecanismo de asignación de rutas de extremo a extremo en origen, el sistema no resulta adecuado para descubrir la mejor ruta (es decir, la que tiene la métrica más baja) de extremo a extremo. Dado que el mensaje RREQ no se propaga al nodo de destino cuando se encuentra una ruta válida en un nodo intermedio, la métrica de la ruta de extremo a extremo no se comunica sistemáticamente en mensajes RREP al nodo de origen, y la ruta válida captada en el nodo intermedio puede no ser la mejor ruta hacia el nodo de destino.

El documento WO 01/41375 describe un algoritmo para protocolos de asignación de rutas ad hoc, bien basado en la asignación de rutas en origen o la asignación de vector de distancia. De acuerdo con WO 01/41375, se diseminan por la red solicitudes ordinarias de asignación de rutas en origen o mensajes actualizados de solicitud de asignación de ruta, identificados mediante una bandera, cuando se produce un evento predeterminado, como la expiración de un contador, un enlace roto …. Sin embargo, WO 01/41375 no consigue revelar un sistema adecuado para descubrir con rapidez una ruta entre un nodo de origen y un nodo de destino y descubrir la mejor ruta entre un nodo de origen y un nodo de destino en respuesta a una petición del origen, limitando al mismo tiempo los mensajes de petición/respuesta de la red.

El documento EP1467524 describe un algoritmo para el protocolo ad-hoc de asignación de rutas de red adecuado en materia de calidad del servicio, comprendiendo las demoras y el ancho de banda de comunicaciones. De acuerdo con el documento EP1467524, además del menor coste del enlace, y del número de secuencia se tienen en cuenta otros criterios, tal como el ancho de banda del enlace, a la hora de establecer la mejor ruta entre nodos. No obstante, en lo que respecta a la técnica anterior citada, EP1467524 no describe un sistema adecuado para descubrir con rapidez una ruta entre un nodo de origen y un nodo de destino y para descubrir la mejor ruta entre un nodo de origen y un nodo de destino.

El problema que resuelve la presente invención es cómo utilizar el mecanismo RREQ y RREP para descubrir con rapidez la mejor ruta entre un nodo de origen y uno o más nodos de destino.

SUMARIO DE LA INVENCIÓN

La presente invención describe un método y un sistema para procesar y enviar mensajes de petición de ruta (RREQ) y para la generación de mensajes de respuesta de ruta (RREP) en protocolos de asignación de ruta previa petición, de los cuales constituye un ejemplo el AODV, de forma que se pueda descubrir la mejor ruta sin incurrir en demoras/latencia importantes en el descubrimiento de la ruta en redes inalámbricas en malla/ad hoc. Concretamente, cuando un nodo de origen desea descubrir la ruta hacia un nodo de destino, el nodo de origen disemina a través de la red un mensaje RREQ con el nodo de destino especificado en la lista de destinos y el campo correspondiente a la métrica inicializado a 0. El mensaje RREQ contiene una nueva bandera “respuesta Intermedia” (IR)” para cada nodo de destino. El nodo de origen establece la bandera correspondiente al modo de destino en el RREQ cuando inicia la diseminación del RREQ para descubrir una ruta hacia el nodo de destino. Durante la diseminación del RREQ, el primer nodo intermedio con una ruta válida hacia el nodo de destino responde al RREQ con un mensaje RREP. El mensaje RREP se envía en modo unidifusión hacia el nodo de origen, y por tanto, establece con rapidez una ruta temporal de envío hacia el destino. De este modo, el nodo de origen puede utilizar esta ruta de envío provisional para el envío de paquetes/tramas de datos con una baja latencia/demora en el descubrimiento de la ruta. El primer nodo intermedio reinicializa/borra la bandera “IR” en... [Seguir leyendo]

1. Método para localizar una ruta entre un nodo de origen (A) y un nodo de destino (E) en una red inalámbrica, comprendiendo dicho método: La diseminación a través de dicha red inalámbrica de un mensaje de petición de ruta (RREQ) por parte de dicho nodo de origen (A); y La recepción de un mensaje de respuesta de ruta (RREP) a dicho mensaje de petición de ruta (RREQ) procedente de un primer nodo intermedio (B) que tiene una ruta válida hacia dicho nodo de destino (E) caracterizado porque dicho primer nodo intermedio (B) responde a dicho mensaje de petición de ruta (RREQ) cuando se establece una bandera (IR) en dicho mensaje de petición de ruta (RREQ) y porque dicho primer nodo intermedio (B) disemina de nuevo en dicha red inalámbrica dicho mensaje de petición de ruta (RREQ) con dicha bandea (IR) reinicializada.

2. Método según la reivindicación 1, caracterizado porque dicha etapa de recepción establece una ruta temporal entre dicho nodo de origen (A) y dicho nodo de destino (E) de dicha red inalámbrica.

3. Método según la reivindicación 1, caracterizado porque dicho mensaje de respuesta de ruta (RREP) de dicha etapa de recepción se envía en modo unidifusión a dicho nodo de origen (A).

4. Método según la reivindicación 1, que comprende adicionalmente la diseminación a través de dicha red inalámbrica de un mensaje de petición de ruta de mantenimiento a fin de mantener una ruta correspondiente a la métrica de extremo a extremo entre nodos y se adapte a cambios de condiciones de red.

5. Método según la reivindicación 4, que también comprende la recepción de una respuesta a dicho mensaje de petición de ruta de mantenimiento como si fuese dicho mensaje de petición de ruta (RREQ).

6. Método según la reivindicación 1, que comprende adicionalmente: La recepción en modo unidifusión de un mensaje adicional de respuesta de ruta (RREP (1), RREP (2)) procedente de dicho nodo de destino (E), comprendiendo dicho mensaje adicional de respuesta de ruta (RREP (1), RREP (2)) una ruta correspondiente a la métrica de extremo a extremo seleccionada por dicho nodo de destino (E), en el que dicha métrica de extremo a extremo se recibe en los mensajes de petición de ruta (RREQ) recibidos por dicho nodo de destino (E).

7. Método según la reivindicación 6, caracterizado porque cuando dicha ruta temporal es dicha ruta de respuesta a la métrica de extremo a extremo, dicho mensaje adicional de respuesta de ruta (RREP (1)) sirve como confirmación, y si dicha ruta temporal no es la ruta de respuesta a la métrica de extremo a extremo, dicho mensaje adicional de respuesta de ruta (RREP (2)) sirve para establecer dicha ruta correspondiente a la métrica de extremo a extremo, cuando dicho nodo de origen (A) recibe dicho mensaje adicional de respuesta de ruta.

8. Método para localizar una ruta entre un nodo de origen (A) y un nodo de destino (E) en una red inalámbrica, comprendiendo dicho método: Recibir un mensaje de petición de ruta (RREQ) procedente de dicho nodo de origen (A); y Responder a dicho mensaje de petición de ruta (RREQ) mediante un mensaje de respuesta de ruta (RREP) procedente de un primer nodo intermedio (B) que tiene una ruta válida hacia dicho nodo de destino (E) caracterizado porque dicho nodo intermedio (B) responde a dicho mensaje de petición de ruta (RREQ) cuando se establece una bandera (IR) en dicho mensaje de petición de ruta (RREQ) y porque dicho primer nodo intermedio (B) disemina de nuevo en dicha red inalámbrica dicho mensaje de petición de ruta (RREQ) con dicha bandera (IR) reinicializada.

9. Método según la reivindicación 8, que comprende asimismo: Actualizar dicho mensaje de petición de ruta (RREQ); y Diseminar a través de dicha red inalámbrica dicho mensaje de petición de ruta (RREQ).

10. Método de acuerdo con la reivindicación 8, caracterizado porque dicha etapa de respuesta establece una ruta temporal entre dicho nodo de origen (A) y dicho nodo de destino (E) de dicha red inalámbrica.

11. Método de acuerdo con la reivindicación 9, caracterizado porque dicha fase de actualización comprende asimismo actualizar una métrica (METRIC) en dicho mensaje de petición de ruta (RREQ) con una métrica acumulada de dicha ruta entre dicho nodo de origen (A) y dicho nodo intermedio (B).

12. Método de acuerdo con cualquiera de las reivindicaciones 1 a 11, caracterizado porque dicha red inalámbrica es una red inalámbrica mallada.

13. Método de acuerdo con la reivindicación 8, caracterizado porque dicho mensaje de respuesta de ruta (RREP) de dicha etapa de respuesta se envía mediante unidifusión a dicho nodo de origen (A).

14. Método de acuerdo con cualquiera de las reivindicaciones 1 a 11, caracterizado porque una dirección de dicho nodo de destino (E) es una dirección del protocolo de Internet y una dirección de control de acceso al soporte.

15. Método de acuerdo con cualquiera de las reivindicaciones 1 a 11, caracterizado porque dicho nodo de destino

(E) incluye nodos de destino asociados a un servidor mandatario y a un punto de acceso.

16. Método de acuerdo con la reivindicación 8, que comprende igualmente la respuesta a un mensaje de petición de ruta de mantenimiento como si fuese dicho mensaje de petición de ruta (RREQ).

17. Método según la reivindicación 2 a 10, caracterizado porque dicha ruta temporal está disponible para la

transmisión de datos al recibir dicho mensaje de respuesta de ruta (RREP) remitido por dicho nodo de origen (A). 10