Método y sistema para enrutamiento eficiente en redes Ad Hoc.

Un método para enrutamiento eficiente en una red de comunicación inalámbrica de salto múltiple,

en donde son enrutados paquetes de datos por trayectorias de transmisión usando las siguientes etapas:

adquirir información de enlace que comprende estado de enlace y calidad de enlace entre nodos de la red; actualizar un elemento (101) de enrutamiento con la citada información de enlace;

caracterizado por:

determinar rutas posibles con información de enlace esencialmente similar para dichos paquetes de datos basada en un estado de enlace futuro cercano pronosticado entre nodos de la red, en donde dicho estado de enlace futuro cercano pronosticado comprende características de estado de enlace para una gama de tiempo larga que cubre varias tramas de tráfico y una gama de tiempo corta que cubre varios símbolos o bits transmitidos, y enrutar dichos paquetes de datos a través de las rutas determinadas.

Método y sistema para enrutamiento eficiente en redes Ad Hoc

Campo de la Invención La presente invención se refiere a un sistema, un método y un aparato de enrutamiento, en particular para una red basada en ad hoc en un entorno móvil o estático que utiliza diversidad de rutas junto con un modelo de enrutamiento predictivo.

Antecedentes de la Invención La comunicación inalámbrica entre usuarios móviles está resultando cada vez más popular según se desarrollan los dispositivos y la tecnología. La implantación de la infraestructura se está expandiendo tanto dentro de los sistemas de telecomunicación como de los sistemas de red de datos. También en la actualidad, los sistemas de comunicación que utilizan redes conmutadas por paquetes son cada vez más numerosos y la tendencia es clara hacia este esquema de enrutamiento basado en paquetes. Este sistema ha sido usado durante muchos años en los sistemas basados en red de datos y por lo tanto existen muchos protocolos de enrutamiento estandarizados para este propósito. Sin embargo, no están preparados para cambiar rápidamente las topografías de las redes como por ejemplo las llamadas redes ad hoc.

Las redes ad hoc inalámbricas se caracterizan porque la red no tiene la misma naturaleza estática que una infraestructura de red alámbrica ordinaria pero la red basada en ad hoc no tiene un control centralizado y se crea con frecuencia de una manera espontánea. Ésta mantiene el control a través de un concepto descentralizado. Los nodos serán instalados o desconectados de una manera no controlada en comparación con arquitecturas de red estándar fijas; los nodos pueden ir y venir rápidamente, lo que conduce a una topología de red que cambia de forma dinámica. En algunos casos, tales redes ad hoc son formadas por los propios dispositivos de usuario/cliente como componentes de la infraestructura. Estos componentes son entonces verdaderamente móviles en el sentido de que los usuarios se desplazan, dentro y fuera de la célula de red, y por lo tanto la infraestructura se moverá consiguientemente. Ésta es una forma excitante de construcción de una infraestructura pero supone demandas muy altas sobre el protocolo de enrutamiento.

Otros problemas de un entorno de infraestructura inalámbrica son debidos a cuestiones específicas de radio que degradarán el comportamiento y la eficiencia del flujo de la red. Pueden existir problemas de desvanecimiento debido al movimiento de los nodos de la infraestructura o al movimiento de objetos en el entorno de radio, y pueden existir problemas debido a la interferencia de otras fuentes de radio dentro del alcance.

Estas clases de topografías de red han sido usadas en el entorno militar pero en la actualidad han migrado también hacia el área civil. Los sistemas inalámbricos son usados en la actualidad para construir rápidamente áreas de infraestructura, por ejemplo acceso inalámbrico de banda ancha en áreas residenciales o en áreas comerciales. Se pueden usar para construir una infraestructura temporal, por ejemplo en situación de emergencia, en una zona de desastre, o en el campo de batalla con propósitos militares. También se pueden usar para construir zonas de cobertura de acceso temporal durante eventos tales como, por ejemplo, conciertos, conferencias, reuniones, o zonas de turismo estacional. En estas clases de áreas, no es necesario tener cobertura durante todo el año, sino solamente durante períodos específicos.

En la actualidad, varios Proveedores de Servicio de Internet (ISP) ofrecen acceso inalámbrico a áreas públicas o semi-públicas tales como aeropuertos, restaurantes, cafeterías y hoteles, usando sistemas fijos de infraestructura inalámbrica. Estos sistemas son denominados con frecuencia puntos calientes.

Puesto que la demanda de los usuarios por ganar acceso se incrementa considerando la cobertura y el ancho de banda, una forma de expansionar el área de cobertura inalámbrica o el ancho de banda consiste en instalar más componentes de infraestructura; sin embargo, hacer esto con componentes inalámbricos normales fijos es caro y por ello ha surgido la idea de construir redes usando enrutadores inalámbricos. En este caso, se pueden usar protocolos de enrutamiento ad hoc para disponer de un procedimiento de instalación simplificado.

Existen básicamente dos clases de usos de red cuando se discute de redes ad hoc; la primera consiste en la construcción de una red de área local sin ninguna puerta de acceso externa que proporcione acceso a una red externa, por ejemplo Internet. Este esquema puede ser encontrado en instalaciones relacionadas con zonas de desastre o en instalaciones militares en el campo de batalla. El otro uso, y probablemente el más común, se refiere a cuando una o varias puertas de acceso proporcionan a la red conexiones externas a, por ejemplo, una red (privada o pública, por ejemplo Internet) basada en IP. En tal configuración de red, los paquetes de datos pueden tomar rutas diferentes y/o usar diferentes puertas de acceso dependiendo de, por ejemplo, el tipo de tráfico de datos, las congestiones o los costes de enrutamiento.

Los esquemas de enrutamiento basados en paquetes construyen con frecuencia sistemas de redes de comunicación en torno a un modelo por capas, por ejemplo el modelo de referencia OSI (Interconexión de Sistemas Abiertos) . El software o el hardware de comunicación se dividen en varias capas, subunidades más pequeñas, trabajando de manera jerárquica. Los parámetros de control de información y de comunicación se hacen pasar arriba y abajo localmente y entre las mismas capas entre los extremos de envío y de recepción. Cada una de tales capas es responsable de diferentes tareas en el orden de comunicación. Con respecto al enrutamiento, las tres primeras capas según el modelo de referencia OSI son las más importantes.

La Capa 1 es responsable de la transmisión física de bits de datos; ejemplos de medios físicos pueden ser, por ejemplo, el enlace alámbrico de una red basada en Ethernet o en un enlace inalámbrico en una Red Inalámbrica deÁrea Local (WLAN) .

La Capa 2 se denomina con frecuencia Capa de Enlace, y es responsable de la transmisión de bloques de datos, detección de error, y coordinación de recursos de red.

La Capa 3 se denomina con frecuencia Capa de Red o a veces capa MAC; es responsable de habilitar comunicación entre cualquier par de nodos de una red. Esta capa se encarga, por ejemplo, de los cálculos de enrutamiento y del control de congestión. A este efecto, se han desarrollado diferentes protocolos de enrutamiento dependiendo del tipo de red.

Los protocolos de enrutamiento de paquetes en las redes basadas en IP se basan por lo general en algoritmos de enrutamiento que utilizan información de vector de distancia o de estado de enlace para encontrar y mantener una ruta para cada par de nodos fuente y destino en la red. En principio, en los algoritmos de enrutamiento de vector de distancia, cada enrutador emite la distancia a todos los anfitriones a sus enrutadores contiguos, y cada enrutador que recibe la información calcula la ruta más corta a cada uno de los anfitriones de la red. En los algoritmos de enrutamiento de estado de enlace, cada enrutador emite la información de estado de cada uno de sus enlaces de red adyacentes hasta sus enrutadores contiguos, y cada enrutador que recibe la información mantiene la base de datos de la imagen completa de la red a partir de la información de estado de enlace y calcula la ruta más corta a cada anfitrión en base a los costes de enlace en la base de datos. Estos algoritmos de enrutamiento están diseñados para redes relativamente estáticas y de ese modo se deben diseñar nuevos algoritmos de enrutamiento para redes ad hoc cuya topología cambia con frecuencia.

Se conocen básicamente dos categorías de protocolos de enrutamiento existentes para redes ad hoc. Éstos son protocolos de enrutamiento “proactivo” (basados en tabla) y “reactivo” (bajo demanda) . También son posibles protocolos que tienen combinaciones de estos ‘protocolos.

Los protocolos de enrutamiento proactivo calculan constante y periódicamente una ruta para todos los anfitriones de una red ad hoc, y por tanto se encuentra siempre disponible una ruta cuando un paquete de datos necesita ser enviado a un anfitrión con destino particular. Estos resultados se mantienen en tablas de enrutamiento en todos los elementos de la infraestructura.

Con el fin de mantener rutas a cada anfitrión, se intercambian mensajes de control entre los enrutadores para notificar cambios en la configuración de red y en el estado de enlace. Los protocolos de enrutamiento de vector de distancia y de estado de enlace, son ambos clasificados en... [Seguir leyendo]

1. Un método para enrutamiento eficiente en una red de comunicación inalámbrica de salto múltiple, en donde son enrutados paquetes de datos por trayectorias de transmisión usando las siguientes etapas:

adquirir información de enlace que comprende estado de enlace y calidad de enlace entre nodos de la red; actualizar un elemento (101) de enrutamiento con la citada información de enlace; caracterizado por:

determinar rutas posibles con información de enlace esencialmente similar para dichos paquetes de datos basada en un estado de enlace futuro cercano pronosticado entre nodos de la red, en donde dicho estado de enlace futuro cercano pronosticado comprende características de estado de enlace para una gama de tiempo larga que cubre varias tramas de tráfico y una gama de tiempo corta que cubre varios símbolos o bits transmitidos, y enrutar dichos paquetes de datos a través de las rutas determinadas.

2. El método según la reivindicación 1, que comprende además la etapa de combinar dichos paquetes de datos una vez que los paquetes de datos han alcanzado un nodo de destino a través de las rutas determinadas.

3. El método según cualquiera de las reivindicaciones anteriores, que comprende además la etapa de enrutar bits de paridad a efectos de detección de error y de corrección de error, en donde los bits de paridad son introducidos en uno de dichos paquetes de datos a efectos de detección de error y de corrección de error.

4. El método según cualquiera de las reivindicaciones anteriores, que comprende además la etapa de usar un sistema de transmisión basado en radiación electromagnética con una frecuencia comprendida en la gama de 100 KHz a 100 PHz dentro de la red de comunicaciones inalámbricas.

5. El método según la reivindicación 4, que comprende además la etapa de usar dicho sistema de transmisión a partir de uno o de varios de los estándares de radio siguientes dentro de la red de comunicaciones inalámbricas: IEEE 802.11, IEEE 802.15, IEEE 802.16, HiperLAN, HomeRF, Bluetooth, IR, UWB, JTRS, 3G, GPRS y EDGE.

6. Un nodo (800) en una red de comunicación que tiene una pluralidad de nodos, comprendiendo dicho nodo:

medios (801) de procesamiento para procesar información de control de red recibida; medios (802) de almacenamiento para almacenar la información de control de red; medios (805) de transmisión para transmitir paquetes de datos, y medios (3001) de adquisición de estado de enlace para adquirir información de enlace que comprende estado de enlace y calidad de enlace entre nodos contiguos; en donde el nodo comprende además medios de determinación, caracterizado por:

medios (3002) de determinación que utilizan la información de enlace adquirida y la información de control de red para determinar al menos dos rutas hasta un destino para el enrutamiento de un paquete de datos en base a un estado de enlace futuro cercano pronosticado entre nodos de la red, en donde dicho estado de enlace futuro cercano pronosticado comprende características de estado de enlace para una gama de tiempo larga que cubre varias tramas de tráfico y una gama de tiempo corta que cubre varios símbolos o bits transmitidos, y medios de enrutamiento para enrutar dichos paquetes de datos a través de dichas rutas determinadas.

7. El nodo (800) según la reivindicación 6, en donde la comunicación entre nodos es inalámbrica.

8. El nodo (800) según la reivindicación 7, en donde dicha red de comunicación es una red ad hoc.

9. El nodo (800) según la reivindicación 6, que comprende la etapa de enrutar bits de paridad con fines de detección de error y de corrección de error, en donde los bits de paridad son introducidos en uno de dichos paquetes de datos a efectos de detección de error y de corrección de error.

10. El nodo (800) según la reivindicación 6, en donde dichos medios de transmisión utilizan radiación electromagnética con una frecuencia comprendida en la gama de 100 KHz a 100 PHz dentro de la red de comunicaciones inalámbricas.

11. El nodo (800) según la reivindicación 10, en donde dichos medios de transmisión utilizan uno o varios de los estándares de radio siguientes dentro de la red de comunicaciones inalámbricas: IEEE 802.11, IEEE 802.15, IEEE 802.16, HiperLAN, HomeRF, Bluetooth, IR, UWB, JTRS, 3G., GPRS y EDGE.

12. Una red de comunicación inalámbrica que comprende uno o varios nodos según cualquiera de las reivindicaciones 6-11.

13. Un programa de ordenador en un nodo de una red de comunicación inalámbrica, comprendiendo el programa:

un primer conjunto de instrucciones para adquirir información de enlace entre nodos de la red, y

un segundo conjunto de instrucciones para actualizar un elemento (101) de enrutamiento con la citada información de enlace, en donde dicha información de enlace comprende estado de enlace y calidad de enlace entre nodos de la red; caracterizado porque el programa comprende además:

un tercer conjunto de instrucciones para determinar posibles rutas con información de enlace sustancialmente similar en base a estado de enlace futuro cercano pronosticado entre nodos de la red, en donde dicho estado de enlace futuro cercano pronosticado comprende características de estado de enlace para una gama de tiempo larga que cubre varias tramas de tráfico y una gama de tiempo corta que cubre varios símbolos o bits transmitidos, y un cuarto conjunto de instrucciones para enrutar un paquete de datos a través de dichas rutas determinadas.