Selección de ruta en redes inalámbricas.

Un método de localización de una ruta entre un nodo de origen (A) y un nodo de destino

(E), comprendiendo dicho método:

establecer un indicador (IR) de un mensaje de petición de ruta (RREQ) por dicho nodo de origen (A);

retransmitir dicho mensaje de petición de ruta (RREQ) sobre una red inalámbrica;

recibir un mensaje de respuesta de ruta (RREP) en respuesta a dicho mensaje de petición de ruta (RREQ) desde un primer nodo intermedio (B) que tiene una ruta válida a dicho nodo de destino (E) en el que dicho primer nodo intermedio (B) envía dicho mensaje de respuesta de ruta (RREP) cuando dicho indicador (IR) está establecido en dicho mensaje de petición de ruta (RREQ) y en el que dicho primer nodo intermedio (B) retransmite dicho mensaje de petición de ruta (RREQ) sobre dicha red inalámbrica con dicho indicador (IR) reseteado, en el que dicho nodo de destino es un proxy para los nodos adicionales; y

establecer una ruta temporal entre dicho nodo de origen (A) y dicho nodo de destino (E) en base a dicha respuesta;

recibir un mensaje de respuesta de ruta adicional (RREP) desde dicho nodo de destino (E), incluyendo dicho mensaje de respuesta de ruta adicional (RREP) una ruta, seleccionada por dicho nodo de destino (E) que tiene la mejor métrica de extremo a extremo; y

establecer las comunicaciones entre dicho nodo de origen (A) y dicho nodo de destino (E) usando dicha ruta, seleccionada por el nodo de destino (E), que tiene la mejor métrica de extremo a extremo.

Tipo: Patente Europea. Resumen de patente/invención. Número de Solicitud: E10189229.

Solicitante: THOMSON LICENSING.

Nacionalidad solicitante: Francia.

Dirección: 1-5, RUE JEANNE D'ARC 92130 ISSY-LES-MOULINEAUX FRANCIA.

Inventor/es: LIU,HANG.

Fecha de Publicación: .

Clasificación Internacional de Patentes:

  • SECCION H — ELECTRICIDAD > TECNICA DE LAS COMUNICACIONES ELECTRICAS > TRANSMISION DE INFORMACION DIGITAL, p. ej. COMUNICACION... > Redes de datos de conmutación (interconexión o... > H04L12/70 (Sistemas de conmutación de paquetes)

PDF original: ES-2472691_T3.pdf

 

google+ twitter facebook

Fragmento de la descripción:

Selecciïn de ruta en redes inalïmbricas Campo de la invenciïn La presente invenciïn se refiere a las redes inalïmbricas y, en particular a las redes inalïmbricas de malla. Muy especialmente la presente invenciïn se refiere al procesamiento de los mensajes de peticiïn de ruta en protocolos de enrutamiento a demanda.

Antecedentes de la invenciïn Los protocolos de enrutamiento a demanda, por ejemplo el protocolo de enrutamiento del Vector de Distancia a Demanda Ad Hoc (AODV) definido por el grupo de trabajo MANET en IEFT, usa un mecanismo de Peticiïn de Ruta y Respuesta de Ruta para establecer las rutas entre dos nodos en las redes inalïmbricas de malla / ad hoc. Cuando un nodo de origen quiere enviar paquetes / tramas de datos a un nodo de destino, el nodo de origen descubre la ruta al destino inundando sobre la red un mensaje de Peticiïn de Ruta (RREQ) si el nodo de origen no tiene una ruta vïlida al nodo de destino y la necesita. Se crea una ruta de vuelta inversa al origen por los nodos en la red a medida que reciben y retransmiten el mensaje RREQ. Cuando un nodo recibe un mensaje RREQ, el nodo receptor contesta a esta peticiïn generando un mensaje de Respuesta de Ruta (RREP) si: (1) o bien el nodo receptor es el propio destino, o (2) el nodo receptor tiene una ruta vïlida al destino y no estï establecido el indicador de "solo destino" ('D') en el mensaje RREQ. El mensaje RREP se retransmite con destinatario ïnico al nodo de origen a travïs de la ruta inversa establecida y de este modo se crea una ruta directa al destino en los nodos intermedios y eventualmente en el nodo de origen. Las rutas establecidas expiran si no se usan durante un tiempo de vida de la ruta determinado.

En el AODV, el indicador de "solo destino" del mensaje RREQ se establece por el nodo de origen y no se cambia por los nodos intermedios. Si el indicador de "solo destino" estï establecido en el mensaje RREQ por el nodo de origen, el nodo intermedio no responde al mensaje RREQ con un mensaje RREP incluso si el nodo intermedio / receptor tiene una ruta vïlida al nodo de destino. Este retransmite / re-inunda el mensaje RREQ a sus vecinos. Solo el nodo de destino responde a este mensaje RREQ. En este modo de operaciïn, la latencia del descubrimiento de ruta puede ser grande aunque eventualmente se descubre en el proceso la mejor ruta actualizada entre el nodo de origen y el nodo de destino. Una baja latencia es muy importante para las aplicaciones de tiempo real tales como las comunicaciones de voz y de video.

Si no estï establecido el indicador de "solo destino" por el nodo de origen, entonces cualquier nodo intermedio con una ruta vïlida al nodo de destino responde al mensaje RREQ con el mensaje RREP. El mensaje RREP se envïa de vuelta al nodo de origen como ïnico destino y establece una ruta directa al nodo de destino. Si estï establecido el indicador "RREP Gratuito" ('G') en el mensaje RREQ, este nodo intermedio tambiïn transmite un mensaje RREP gratuito al nodo de destino como ïnico destino de modo que el nodo de destino aprende de las rutas al nodo de origen. Sin embargo, en el AODV, si un nodo intermedio genera un mensaje RREP (porque el nodo intermedio tiene una ruta vïlida al nodo de destino) , entonces el nodo intermedio descarta el mensaje RREQ. Con este enfoque, el nodo de origen puede descubrir una ruta al nodo de destino mïs rïpidamente porque el nodo de origen no tiene que esperar la respuesta del nodo de destino. Sin embargo, puede que no se descubra la mejor ruta de extremo a extremo porque la ruta capturada en el nodo intermedio puede no ser la mejor ruta al nodo de destino. Las mïtricas pueden haber cambiado debido a la dinïmica de las redes inalïmbricas haciendo la ruta capturada menos deseable. Esto es, debido a los cambios en la topologïa de la red, las mïtricas de enrutamiento, etc. es posible que la ruta capturada en el nodo intermedio pueda empeorar o que otras rutas con una mejor mïtrica de extremo a extremo se conviertan en disponibles haciendo otras rutas mïs deseables.

El documento de Perkins y otros "Ad-hoc On-demand Vector Routing" (en PROCEEDINGS WMCSA, del 25 de febrero de 1999, XP002173721) desvela un algoritmo de "Enrutamiento del Vector de distancia a demanda Ad-hoc" (AODV) para la operaciïn de enrutamiento en una red inalïmbrica sin un punto de acceso centralizado. Este algoritmo se basa en el establecimiento dinïmico de entradas a la tabla de rutas en los nodos intermedios y usa un mecanismo de Peticiïn de Ruta (RREQ) y Respuesta de Ruta (RREP) . Este algoritmo reduce el retardo en la bïsqueda de una ruta al nodo de destino sin embargo, a diferencia del mecanismo de enrutamiento de origen de extremo a extremo, el sistema no estï adaptado para descubrir la mejor ruta de extremo a extremo (es decir, con la menor mïtrica) . Debido a 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 informa sistemïticamente en los mensajes RREP al nodo de origen y la ruta vïlida capturada en el nodo intermedio puede que no sea la mejor ruta al nodo de destino.

El documento WO 01/41376 desvela un algoritmo para el protocolo de enrutamiento de la red ad-hoc, bien basado en el enrutamiento de origen o el enrutamiento del vector de distancia. De acuerdo con el documento WO 01/41375, bien el mensaje de peticiïn de enrutamiento de origen ordinario o el mensaje de peticiïn de enrutamiento actualizado, identificado por un indicador, se inundan en la red cuando ocurre un evento predeterminado tal como una expiraciïn de un temporizador, una ruptura de enlace… Sin embargo, el documento WO 01/41375 falla al

desvelar un sistema adaptado tanto para descubrir rïpidamente una ruta entre un nodo de origen y un nodo de destino como para descubrir la mejor ruta entre un nodo de origen y un nodo de destino en respuesta a una peticiïn del origen al tiempo que limita los mensajes de peticiïn / respuesta en la red.

El documento EP 1467524 desvela un algoritmo para el protocolo de enrutamiento de la red ad hoc adaptado para la consideraciïn de la calidad del servicio entre ellos el retardo y el ancho de banda en las comunicaciones. De acuerdo con el documento EP 1467524, ademïs del menor coste del enlace, y el nïmero de secuencia, se consideran otros criterios tales como el ancho de banda del enlace para el establecimiento de la mejor ruta entre nodos. Sin embargo, al igual que la tïcnica anterior citada, la EP 1467524 falla al revelar un sistema adaptado tanto para descubrir rïpidamente una ruta entre un nodo de origen y un nodo de destino como descubrir la mejor ruta entre un nodo de origen y un nodo de destino.

El problema resuelto por la presente invenciïn es cïmo usar el mecanismo de los mensajes RREQ y RREP para descubrir rïpidamente 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 desvela un mïtodo y un sistema para procesar / retransmitir mensajes de Peticiïn de Ruta (RREQ) y generar mensajes de Respuesta de Ruta (RREP) en protocolos de enrutamiento a demanda, de los cuales el AODV es un ejemplo, de modo que se puede descubrir la mejor ruta sin incurrir en un retardo / latencia significativo de descubrimiento de la ruta en redes inalïmbricas de malla / ad hoc. Especïficamente, cuando un nodo de origen quiere descubrir la ruta a un nodo de destino, el nodo de origen inmunda la red con un mensaje RREQ con el nodo de destino especificado en la lista de destinos y el campo de la mïtrica inicializado a 0. El mensaje RREQ contiene un nuevo indicador "Respuesta Intermedia (IR) " para cada uno de los nodos de destino. El nodo de origen establece el indicador correspondiente para el nodo de destino en el mensaje RREQ cuando inicia la inundaciïn del mensaje... [Seguir leyendo]

 


Reivindicaciones:

1. Un mïtodo de localizaciïn de una ruta entre un nodo de origen (A) y un nodo de destino (E) , comprendiendo dicho mïtodo:

establecer un indicador (IR) de un mensaje de peticiïn de ruta (RREQ) por dicho nodo de origen (A) ;

retransmitir dicho mensaje de peticiïn de ruta (RREQ) sobre una red inalïmbrica;

recibir un mensaje de respuesta de ruta (RREP) en respuesta a dicho mensaje de peticiïn de ruta (RREQ) desde un primer nodo intermedio (B) que tiene una ruta vïlida a dicho nodo de destino (E) en el que dicho primer nodo intermedio (B) envïa dicho mensaje de respuesta de ruta (RREP) cuando dicho indicador (IR) estï establecido en dicho mensaje de peticiïn de ruta (RREQ) y en el que dicho primer nodo intermedio (B) retransmite dicho mensaje de peticiïn de ruta (RREQ) sobre dicha red inalïmbrica con dicho indicador (IR) reseteado, en el que dicho nodo de destino es un proxy para los nodos adicionales; y

establecer una ruta temporal entre dicho nodo de origen (A) y dicho nodo de destino (E) en base a dicha respuesta;

recibir un mensaje de respuesta de ruta adicional (RREP) desde dicho nodo de destino (E) , incluyendo dicho mensaje de respuesta de ruta adicional (RREP) una ruta, seleccionada por dicho nodo de destino (E) que tiene la mejor mïtrica de extremo a extremo; y

establecer las comunicaciones entre dicho nodo de origen (A) y dicho nodo de destino (E) usando dicha ruta, seleccionada por el nodo de destino (E) , que tiene la mejor mïtrica de extremo a extremo.

2. El mïtodo de acuerdo con la reivindicaciïn 1, que comprende ademïs establecer dicho indicador (IR) de un mensaje de peticiïn ruta de mantenimiento (RREQ) por dicho nodo de origen (A) ;

retransmitir dicho mensaje de peticiïn de ruta de mantenimiento sobre dicha red inalïmbrica en el que la retransmisiïn comprende ademïs inundar dicha red inalïmbrica con dicho mensaje de peticiïn de ruta de mantenimiento entre dicho nodo de origen y dicho nodo de destino.

3. El mïtodo de acuerdo con la reivindicaciïn 2, que comprende ademïs recibir una respuesta a dicho mensaje de peticiïn de ruta de mantenimiento como si dicho mensaje de peticiïn de ruta de mantenimiento fuese dicho mensaje de peticiïn de ruta (RREQ) , e inundar dicha red inalïmbrica con dicho mensaje de peticiïn de ruta de mantenimiento para mantener una ruta que responde a las mïtricas de extremo a extremo entre nodos y para adaptarse a los cambios en las condiciones de la red.

4. El mïtodo de acuerdo con cualquier de las reivindicaciones 1 a 3, en el que dicho mensaje de respuesta de ruta (RREP) se recibe desde un primer nodo intermedio (B) con una ruta vïlida al nodo de destino (E) .

5. Un aparato de localizaciïn de una ruta entre un nodo de origen (A) y un nodo de destino (E) , comprendiendo ademïs dicho aparato:

medios para establecer un indicador (IR) de un mensaje de peticiïn de ruta (RREQ) por dicho nodo de origen (A) ;

medios para retransmitir dicho mensaje de peticiïn de ruta (RREQ) sobre una red inalïmbrica;

medios para recibir un mensaje de respuesta de ruta (RREP) en respuesta a dicho mensaje de peticiïn de ruta (RREQ) desde un primer nodo intermedio (B) que tiene una ruta vïlida a dicho nodo de destino (E) en el que dicho primer nodo intermedio (B) envïa dicho mensaje de respuesta de ruta (RREP) cuando dicho indicador (IR) estï establecido en dicho mensaje de peticiïn de ruta (RREQ) y en el que dicho primer nodo intermedio (B) retransmite dicho mensaje de peticiïn de ruta (RREQ) sobre dicha red inalïmbrica con dicho indicador (IR) reseteado, en el que dicho nodo de destino es un proxy para nodos adicionales.

medios para establecer una ruta temporal entre dicho nodo de origen (A) y dicho nodo de destino (E) en base a dicha respuesta:

medios para recibir un mensaje de respuesta de ruta adicional (RREP) desde dicho nodo de destino (E) , incluyendo dicho mensaje de respuesta de ruta adicional (RREP) una ruta, seleccionada por dicho nodo de destino (E) , que tiene la mejor mïtrica de extremo a extremo; y

medios para establecer comunicaciones entre dicho nodo de origen (A) y dicho nodo de destino (E) usando dicha ruta, seleccionada por dicho nodo de destino (E) , que tiene la mejor mïtrica de extremo a extremo.

6. El aparato de acuerdo con la reivindicaciïn 5, que comprende ademïs medios para establecer un indicador (IR) de un mensaje de peticiïn de ruta de mantenimiento (RREQ) por dicho nodo de origen (A) ;

medios para retransmitir dicho mensaje de peticiïn de ruta de mantenimiento sobre dicha red inalïmbrica en el que 5 dicho medio para retransmitir comprende ademïs inundar dicha red inalïmbrica con dicha peticiïn de ruta de mantenimiento entre dicho nodo de origen y dicho nodo de destino.

7. El aparato de acuerdo con la reivindicaciïn 6, que comprende ademïs medios para recibir una respuesta a dicho mensaje de peticiïn de ruta de mantenimiento como si dicho mensaje de peticiïn de ruta de mantenimiento fuese dicho mensaje de peticiïn de ruta (RREQ) , y medios para inundar dicha red inalïmbrica con dicho mensaje de peticiïn de ruta de mantenimiento para mantener una ruta que responde a la mïtrica de extremo a extremo entre nodos y para adaptarse a cambios en las condiciones de la red.

8. El aparato de acuerdo con cualquiera de las reivindicaciones 5 a 7, en el que dicho mensaje de respuesta de ruta (RREP) se recibe desde un primer nodo intermedio (B) con una ruta vïlida al nodo de destino (E) .

9. El aparato de acuerdo con cualquiera de las reivindicaciones 5 a 8, que comprende ademïs:

medios para recibir un mensaje de respuesta de ruta adicional (RREP) desde dicho nodo de destino (E) , incluyendo dicho mensaje de respuesta de ruta adicional (RREP) una ruta, seleccionada por dicho nodo de destino (E) , que tiene la mejor mïtrica de extremo a extremo; y

medios para establecer comunicaciones entre dicho nodo de origen (A) y dicho nodo de destino (E) usando dicha ruta, seleccionada por dicho nodo de destino (E) , que tiene la mejor mïtrica de extremo a extremo.