ES2409334T3 - Ad hoc predictivo - Google Patents

Abstract

Un método para el encaminamiento en una red de comunicación inalámbrica que comprende una pluralidad denodos, comprendiendo el método las etapas de: obtener información del estado del enlace entre nodos; actualizar un elemento de encaminamiento con la información del estado del enlace obtenida, comprendiendoel elemento de encaminamiento la información del estado del enlace previamente almacenada, caracterizadopor: terminar una ruta de acuerdo con un procedimiento predictivo, anticipando o extrapolando el procedimientopredictivo un estado de futuro cercano de la información del estado del enlace almacenada en el elemento deencaminamiento basándose en un parámetro de desvanecimiento o en un parámetro de velocidad devariación; y encaminar tráfico de acuerdo con la citada ruta determinada.

Description

Ad hoc predictivo.

Campo de la Invención

La presente invención se refiere a un sistema, método y aparato de encaminamiento en particular para una red basada en ad hoc en un entorno de telefonía móvil o estática utilizando un modelo de encaminamiento predictivo.

Antecedentes de la Invención

La comunicación inalámbrica entre usuarios de móviles se está haciendo cada vez más popular a medida que los dispositivos y la tecnología se desarrollan. El despliegue de la infraestructura se está expandiendo tanto dentro de los sistemas tanto de telecomunicación como de los sistemas de red de datos. Hoy en día también los sistemas de telecomunicación están utilizando cada vez más las redes de paquetes conmutados y la tendencia es clara hacia este esquema de encaminamiento basado en paquetes. Este sistema ha sido utilizado durante muchos años en los sistemas basados en red de datos y por ello existen muchos protocolos de encaminamiento estandarizados para este propósito. No obstante, no están preparados para topografías de red que cambian rápidamente como por ejemplo las llamadas redes ad hoc.

Las redes ad hoc inalámbricas se caracterizan porque no tienen la misma naturaleza estática que una infraestructura de red de cable ordinaria, sino que la red basada en ad hoc no tiene un control centralizado y se crea a menudo de una manera espontánea. Mantiene el control mediante un concepto descentralizado. Los nodos pueden ser conectados o desconectados de una manera no controlada en comparación con las arquitecturas de red fija estándar; los nodos pueden ir y venir rápidamente, lo que lleva a una topología de red que cambia dinámicamente. En algunos casos las redes ad hoc están formadas por los propios dispositivos de usuario/cliente como componentes de infraestructura. Estos componentes son entonces verdaderamente móviles en el sentido de que los usuarios se mueven de un sitio a otro, entran y salen de una celda de la red, y por lo tanto la infraestructura se moverá de un sitio a otro de manera correspondiente. Esta es una interesante manera de construir una infraestructura pero establece muy altas demandas en el protocolo de encaminamiento.

Otros problemas en un entorno inalámbrico son debidos a cuestiones específicas de radio que degradarán el rendimiento y la eficiencia del flujo en la red. Puede haber problemas de desvanecimiento debido al movimiento de los nodos de infraestructura o al movimiento de objetos en el entorno de radio, y puede haber problemas debido a interferencias de otras fuentes de radio dentro del alcance.

Estos tipos de topografías han sido utilizados en el entorno militar pero ahora están migrando también al área civil. Los sistemas inalámbricos se utilizan ahora para construir rápidamente áreas de infraestructura para, por ejemplo, acceso de banda ancha inalámbrico en áreas residenciales o en áreas comerciales. Pueden ser utilizados para construir infraestructura temporal, por ejemplo en una situación de emergencia, en un área catastrófica o en el campo de batalla con propósitos militares. También podrían ser utilizados para construir áreas de cobertura de acceso temporal durante eventos como, por ejemplo, conciertos, conferencias, reuniones o áreas turísticas en temporada. En estos tipos de áreas no es necesario tener cobertura todo el año, sino sólo durante periodos específicos.

Hoy en día, varios Proveedores de Servicios de Internet (ISP – Internet Service Providers, en inglés) ofrecen acceso inalámbrico en áreas públicas o semipúblicas tales como aeropuertos, restaurantes, cafeterías y hoteles utilizando sistemas de infraestructura inalámbrica fija. Estos sistemas se denominan a menudo hotspots (en inglés) (lugares con red inalámbrica).

Dado que la demanda de los usuarios para obtener acceso aumenta considerando cobertura y ancho de banda, una manera de expandir el área de cobertura inalámbrica o el ancho de banda es instalar más componentes de infraestructura; no obstante, hacer esto con componentes inalámbricos fijos normales resulta caro y por ello ha surgido la idea de construir redes utilizando encaminadores inalámbricos. En este caso pueden utilizarse protocolos de encaminamiento ad hoc para tener un procedimiento de instalación simplificado.

Existen básicamente dos tipos de usos de la red cuando se explican las redes ad hoc; el primero es la construcción de una red de área local sin ninguna puerta de enlace externa que proporcione acceso a una red externa, por ejemplo Internet. Este esquema puede ser encontrado en instalaciones relativas a áreas catastróficas o instalaciones militares en el campo de batalla. La otra y probablemente la de uso más común es cuando una o varias puertas de enlace proporcionan a la red conexiones externas hacia, por ejemplo, una red basada en IP (privada o pública, por ejemplo Internet). En tal configuración de red, los paquetes de datos pueden tomar diferentes rutas y/o utilizar diferentes puertas de enlace dependiendo, por ejemplo, del tipo de tráfico, de las congestiones o del coste de encaminamiento.

Los esquemas de encaminamiento basados en paquetes a menudo construyen sistemas de red de comunicación alrededor de un modelo de capas, por ejemplo, el modelo de referencia de OSI. El software o el hardware de comunicación se dividen en varias sub-unidades más pequeñas, capas, que trabajan de una manera jerárquica. Los parámetros de control de la información y de la comunicación son pasados hacia arriba y hacia abajo localmente y entre las mismas capas entre los extremos de emisión y de recepción. Cada una de tales capas es responsable de diferentes tareas en el orden de la comunicación. Por lo que respecta al encaminamiento las primeras tres capas de acuerdo con el modelo de referencia de OSI son las más importantes.

La Capa 1 es responsable de la transmisión física de bits de datos; ejemplos de medio físico pueden ser, por ejemplo, el enlace por cable en una red basada en Ethernet o un enlace inalámbrico en una Red de Área Local inalámbrica (WLAN – Wireless Local Area Network, en inglés).

La Capa 2 se denomina a menudo la capa de Enlace o la capa de MAC y es responsable de transmitir bloques de datos, detección de error y coordinación de recurso de red.

La Capa 3 se denomina a menudo la capa de Red; es responsable de permitir la comunicación entre cualquier par de nodos de la red. Esta capa, por ejemplo, se encarga de los cálculos de encaminamiento y del control de la congestión. Con este propósito se han desarrollado diferentes protocolos de encaminamiento dependiendo del tipo de red.

Los protocolos en las redes basadas en IP se basan generalmente en algoritmos de encaminamiento que utilizan un vector de distancia o información acerca del estado del enlace para encontrar y guardar una ruta para cada par de nodos de fuente y de destino de la red. En principio, en los algoritmos de encaminamiento de vector de distancia, cada encaminador transmite la distancia hasta todos los anfitriones a sus encaminadores vecinos, y cada encaminador que recibe la información calcula la ruta más corta hasta cada uno de los anfitriones de la red. En los algoritmos de encaminamiento de estado del enlace, cada encaminador transmite la información acerca del estado de cada uno de sus enlaces de red adyacentes a sus encaminadores vecinos, y cada encaminador que recibe la información mantiene la base de datos de toda la imagen de la red a partir de la información del estado de enlace y calcula la ruta más corta hasta cada anfitrión basándose en los costes del enlace en la base de datos. Estos algoritmos de encaminamiento están diseñados para redes relativamente estáticas, y así, deben diseñarse nuevos algoritmos de encaminamiento para redes ad hoc, cuya topología cambia frecuentemente.

Existen básicamente dos categorías de protocolos de encaminamiento existentes para redes ad hoc. Éstos son los protocolos de encaminamiento “proactivos” (dirigidos por una tabla) y “reactivos” (bajo demanda). También son posibles protocolos que tengan combinaciones de estos protocolos.

Los protocolos de encaminamiento proactivos calculan constante y periódicamente una ruta hasta todos los anfitriones de la red ad hoc, y así siempre hay una ruta disponible cuando un paquete necesita ser enviado a un anfitrión de destino particular. Los resultados se guardan en tablas de encaminamiento en todos los nodos.

Con el fin de mantener rutas hasta cada anfitrión, se intercambian mensajes de control entre los encaminadores para notificar cambios en la configuración de la red y en el estado del enlace. Los protocolos de encaminamiento de vector de distancia y de estado del enlace están clasificados ambos como protocolos proactivos. Debe observarse que los mensajes de control llevan a un sobrecoste y pueden resultar en una menor eficiencia de la red. También, los protocolos proactivos pueden tener dificultades en mantener rutas válidas cuando la topología de la red cambia frecuentemente.

El encaminamiento de DSDV (Destination Sequenced Distance Vector, en inglés – Vector de Distancia de Destinos Secuenciados) es un protocolo de encaminamiento proactivo basado en el algoritmo de vector de distancia, que adapta el Protocolo de Información de Encaminamiento (RIP – Routing Information Protocol, en inglés) a las redes ad hoc. Cada nodo mantiene una tabla de encaminamiento en la cual el nodo almacena el siguiente nodo de salto y la cuenta de saltos para cada uno de todos los anfitriones de destino alcanzables. En DSDV, cada nodo transmite o difunde actualizaciones de encaminamiento periódicamente, o cuando detecta cambios de la topología de la red. Se utilizan también actualizaciones incrementales, que actualizan sólo información acerca de cambios desde la última actualización, para reducir el tráfico de control.

Un protocolo reactivo solo lleva a cabo intercambio de mensajes de control para encontrar/actualizar una ruta cuando hay un paquete de datos que debe ser enviado. Cuando un nodo de fuente desea enviar paquetes de datos, inicia el protocolo de control para encontrar una ruta enviando un mensaje de solicitud de ruta a sus nodos vecinos. Mediante este principio, el planteamiento reactivo es bueno porque no se desperdician recursos de red cuando no hay paquetes para ser transportados. No obstante, lleva más tiempo enviar paquetes cuando tiene que formarse una ruta por primera vez. AODV y DSR son protocolos reactivos representativos.

El protocolo de encaminamiento de AODV (Ad hoc On Demand Vector, en inglés – Vector de Distancia Bajo Demanda Ad hoc) utiliza el algoritmo de DSDV y crea/actualiza rutas bajo demanda, esto es, sólo cuando un nodo de fuente desea enviar un paquete de datos. Esto lleva a una reducción del número de transmisiones requeridas para encontrar/actualizar una ruta.

En AODV, cada nodo mantiene una lista de nodos vecinos detectados. La lista de nodos vecinos es actualizada de una de las siguientes tres maneras: a) cuando se recibe un paquete desde el nodo vecino, b) recibiendo un anuncio local, esto es, un mensaje de saludo, desde el nodo vecino, o c) mediante retroalimentación desde la capa de enlace. Los mensajes de saludo son transmitidos periódicamente desde cada nodo a sus nodos vecinos para informarlos de su presencia.

En AODV, cada nodo mantiene una tabla de encaminamiento para todos los destinos, con cada uno de los cuales el nodo se está comunicando o le está enviando paquetes de datos a través de otros nodos. Para cada destino, existe una entrada en la tabla de paquetes que contiene información acerca del destino, tal como la dirección de IP, el número de secuencia para el nodo de destino, la cuenta de saltos hasta el destino, el siguiente nodo de salto hasta el destino, y la vida útil para la ruta.

Cuando un nodo desea comunicarse con un nodo de destino, esto es, enviar paquetes de datos al destino, entonces el nodo de fuente inicia un mecanismo de descubrimiento de ruta, en el que el nodo de fuente transmite una solicitud de ruta (RREQ – Route REQest, en inglés) a todos los nodos vecinos detectados. Cuando el nodo vecino recibe el mensaje de RREQ y tiene la entrada para una ruta suficientemente nueva para ese destino en su tabla de encaminamiento, entonces devuelve un mensaje de respuesta de ruta (RREP – Route REPly, en inglés) al nodo de fuente. Si el nodo de destino no encuentra una entrada de ruta para ese destino, entonces envía el mensaje de RREQ a sus propios nodos vecinos detectados. Cuando el nodo de destino recibe la RREQ, devuelve el mensaje de RREP al nodo de fuente.

En el proceso de enviar el paquete de RREQ, cada nodo intermedio registra la dirección de IP del nodo vecino desde el cual se recibe la primera copia de la RREQ transmitida, mediante la cual se establece una ruta inversa. Las copias de los mismos mensajes de RREQ recibidas más tarde son todas descartadas. Los nodos intermedios añaden una entrada a su tabla de encaminamiento para el destino, en la que el nodo vecino desde el cual fue recibida la RREP está registrado como el siguiente nodo de salto para ese destino. El número de secuencia de destino y la vida útil de la ruta son copiados desde la RREP y registrados en la entrada. Cuando el mensaje de RREP es devuelto finalmente al nodo de fuente, se forma una ruta de transmisión desde la fuente al destino.

Cuando un nodo detecta que una ruta ya no está disponible por fallo del enlace que incide en la ruta, envía un mensaje de error de ruta (RERR – Route ERRor, en inglés) a todos los nodos vecinos, que utilizan la ruta. El mensaje de RERR es enviado hacia sus nodos vecinos y de así sucesivamente hasta que alcanza el nodo de fuente. El nodo de fuente puede entonces decidir entre detener el envío de paquetes de datos o iniciar un nuevo descubrimiento de ruta.

El protocolo de DSR (Dynamic Source Routing, en inglés – Encaminamiento de Fuente Dinámico) utiliza un mecanismo de encaminamiento de fuente en el cual el nodo de fuente determina bajo demanda la secuencia completa de nodos a lo largo de la ruta y establece la lista de los nodos intermedios en la cabecera del paquete para indicar la secuencia de nodos para la ruta. De esta manera, cada paquete tiene que contener la cabecera para el encaminamiento del paquete. No obstante, los nodos intermedios no necesitan guardar ninguna información acerca de la ruta y pueden aprender rutas cuando están proporcionando paquetes de datos.

En DSR, cada nodo almacena (guarda en la memoria caché) las rutas que ha aprendido. Cuando un nodo de fuente desea enviar paquetes de datos a un nodo de destino y no tiene ninguna entrada en la memoria caché para ese destino, entonces inicia un mecanismo de descubrimiento de ruta transmitiendo un mensaje de RREQ en su capa de enlace. Cada nodo que está recibiendo el mensaje de RREQ adjunta sus direcciones de IP al mensaje de RREQ y a continuación las envía también. Este proceso se realiza hasta que la ruta hasta el destino se haya encontrado o hasta que otro nodo pueda proporcionar una ruta hasta el nodo de destino. A continuación, un mensaje de respuesta de ruta (RREP – Route REPly, en inglés) que contiene la secuencia de saltos de red al nodo de destino es devuelto al nodo de fuente.

En DSR, cuando se detecta un fallo de enlace en un nodo (por ejemplo, cuando el paquete ha sido retransmitido un número máximo de veces), ese nodo elimina el enlace de sus rutas de la caché y envía un mensaje de error de ruta (RERR – Route ERRor, en inglés) a cada uno de los nodos que han utilizado ese enlace desde que se recibió un reconocimiento por última vez. Esos nodos tienen que eliminar las rutas que incluyen ese enlace. La retransmisión del paquete de datos desde el nodo de fuente es entonces manejada por capas superiores tales como el Protocolo de control de Transmisión (TCP – Transmission Control Protocol, en inglés).

En protocolos de encaminamiento ad hoc que utilizan tiempo de expiración del enlace y carga de tráfico de nodos, el tiempo de expiración del enlace se define como el intervalo de tiempo durante el cual la distancia de dos nodos específicos se mantiene menor o igual a la distancia efectiva de radio. En este protocolo de encaminamiento, la métrica se utiliza como un coste de cada enlace, y el nodo trata de encontrar una ruta de coste mínimo, esperando que la vida útil de tal ruta sea mayor y así reduciría la frecuencia de actualización de la ruta y el sobrecoste debido al tráfico de control y aumentaría el caudal total de la transferencia de paquetes de datos.

En este protocolo, la carga de tráfico de un nodo es representada mediante una tasa de ocupación del nodo durante un periodo de tiempo dado. Una ruta que tenga al menos la carga de tráfico de los nodos se elige en un algoritmo de selección de ruta. Se espera que el algoritmo conduzca a un mejor equilibrio de carga en la red, esto es, evitaría la concentración de tráfico hacia nodos particulares en la red.

Cuando se utilizan los métodos de encaminamiento de red ad hoc convencionales en las redes de comunicación de radio de telefonía móvil, pueden surgir algunos problemas. Un problema es que puesto que los usuarios son móviles pueden desplazarse y el sistema experimentará cambios en la calidad de radio debido, por ejemplo, a desvanecimiento, pérdida de propagación y ensombrecimiento. Esto es cierto también si el sistema de infraestructura consiste en elementos de telefonía móvil, por ejemplo, si los equipos del cliente son parte de la infraestructura. Incluso en un sistema con componentes de infraestructura inalámbrica fija tales problemas pueden ocurrir, por ejemplo, debido a vehículos o a otros objetos que temporalmente bloqueen la ruta de la señal entre dos componentes de la infraestructura, lo que lleva a cambios en la calidad del enlace de radio. La principal preocupación para estos tipos de problemas aparece cuando cambian más rápido de lo que cambia la frecuencia de actualización de la tabla de encaminamiento o de la ruta de encaminamiento.

Si se tratan de resolver los problemas mencionados anteriormente aumentando la frecuencia de actualización de la información de encaminamiento en algún punto empezará a degradarse la eficiencia de la transmisión, debido a que la actualización de la información del encaminamiento se llevará una parte sustancial del posible volumen de transmisión de datos en el medio.

En la solicitud de patente de US 2003/0120809 se describe un sistema que detecta fuentes de interferencias en una red buscando señales no autorizadas en la banda de frecuencia de uso, en este caso la banda de ISM de 2,4 GHz. Este documento se centra principalmente en los problemas que surgen en la capa de red y menos en la capa de radio. El documento sólo describe una adaptación al estado actual y no tiene relevancia la posiblemente naturaleza entrante del estado del enlace. El sistema intenta adaptar la ruta del paquete de manera correspondiente para reducir los efectos de la interferencia. La solución se centra en detectar sólo interferencias y el problema se resuelve ajustando la posición de la antena y la dirección de los nodos cerca del interferidor con el fin de reducir la cobertura de radio hacia la fuente de las interferencias.

En la patente de US nº 5.537.394 se introduce una función de predicción de estado para una solución de red fija. La solución implica grandes cálculos estadísticos de información a partir de una función de monitorización del estado. Los cálculos estadísticos se realizan para la interpretación de las implicaciones del sistema de toda la red y no pueden ser fácilmente ajustados para una red ad hoc, y en particular no para una red ad hoc inalámbrica.

La solicitud de Patente Internacional Nº WO 03/094028 describe una red ad hoc para móviles que incluye una pluralidad de nodos de telefonía móvil inalámbricos y una pluralidad de enlaces de comunicación inalámbricos que conectan la pluralidad de nodos entre sí. El método de hacer un seguimiento del tráfico incluye que cada nodo monitorice el tráfico comunicado entre los nodos de la red, generando cada nodo información relativa al tráfico basándose en cuánto tráfico se está comunicando entre varios nodos de la red, y almacenando cada nodo la información de tráfico en una base de datos de tráfico. La información de tráfico puede basarse en el ancho de banda y puede incluir al menos una tasa de error, retardo de extremo a extremo, variación del retardo de extremo a extremo, cuenta de saltos, durabilidad de ruta esperada, y prioridad. Cada nodo puede descubrir y seleccionar rutas de tráfico basándose en la información de tráfico almacenada.

Compendio de la Invención

Es un objeto de la presente invención proporcionar un método de encaminamiento ad hoc que reduzca alguno de los problemas mencionados anteriormente, introduciendo un control de encaminamiento predictivo que utiliza la información del estado del enlace entre los nodos de infraestructura.

Tomando periódicamente medidas de la propiedad del canal de radio, calidad del enlace u otros importantes parámetros del enlace es posible analizar el estado de la red/enlace. Esta información se pasa a un elemento de procesamiento de encaminamiento que utiliza esta información para decidir sobre el tipo de calidad de la señal y monitoriza en tiempo los cambios del estado del enlace. El elemento de procesamiento puede extrapolar tendencias y predecir los cambios de la calidad de la señal, y responder de este modo de una manera apropiada correspondiente para utilizar eficientemente los recursos de red disponibles.

La información de la propiedad del canal obtenida de la capa 1 así como el modelo de referencia de la red OSI es transportada, junto con la información acerca de la calidad del enlace obtenida de la capa 2, a la capa 3, en la que el control de encaminamiento y la planificación del tráfico están situados. La información medida y la obtenida son almacenadas y analizadas para obtener tendencias en la calidad/estado del enlace entre nodos vecinos disponibles y nodos dentro del área de la red que es parte del esquema de encaminamiento actual del nodo. A partir de esto, el parámetro de encaminamiento ad hoc decide sobre rutas apropiadas para enviar paquetes de datos.

Información acerca de las propiedades del canal y de la calidad del enlace puede ser obtenida mediante la medición de varios parámetros diferentes. Ejemplos de estos tipos de parámetros pueden ser la dispersión de Doppler de la señal de radio debido al desvanecimiento de la señal de radio, un planteamiento diferente para esto es reducir el tiempo de coherencia de la señal de radio, la velocidad de Variación de la señal recibida o relación de señal a ruido de interferencia.

El uso de este tipo de comportamiento predictivo es independiente del tipo de protocolo de encaminamiento ad hoc utilizado.

En una realización de ejemplo, se proporciona un método para el encaminamiento en una red de comunicación inalámbrica que comprende una pluralidad de nodos. El método comprende la etapa de obtener información del estado del enlace entre nodos. El método comprende también actualizar un elemento de encaminamiento con la información del estado del enlace obtenida, comprendiendo el elemento de encaminamiento información del estado del enlace almacenada previamente, caracterizado por determinar una ruta de acuerdo con un procedimiento predictivo, anticipando o extrapolando el procedimiento predictivo un estado en el futuro cercano de la información del estado del enlace almacenada en el elemento de encaminamiento basándose en un parámetro de desvanecimiento o en un parámetro de velocidad de variación. El método comprende también encaminar tráfico de acuerdo con la citada ruta determinada.

El método está también caracterizado porque el procedimiento predictivo comprende un protocolo de encaminamiento ad hoc reactivo.

El método está también caracterizado porque el procedimiento predictivo comprende un protocolo de encaminamiento ad hoc proactivo.

El método está también caracterizado porque el procedimiento predictivo comprende una combinación de los protocolos de encaminamiento ad hoc reactivo y proactivo.

El método está también caracterizado porque la etapa de obtención obtiene información del estado del enlace inalámbrico a partir de las mediciones de al menos uno de difusión dispersión de Doppler, tiempo de coherencia, duración media del desvanecimiento, potencia de señal o relación de señal a ruido de interferencia.

El método está también caracterizado porque el procedimiento predictivo para el protocolo de encaminamiento ad hoc reactivo comprende la etapa de obtener información acerca del estado del enlace a partir de la RREP modificada, mensajes de Saludo, Reconocimientos o mensajes de RERR.

El método está también caracterizado porque el procedimiento predictivo para el citado protocolo de encaminamiento ad hoc proactivo comprende la etapa de modificar una tabla de encaminamiento con un campo de estado de la ruta con información acerca del estado del enlace.

El método está también caracterizado porque la información del estado del enlace comprende el estado de energía de los nodos de la red.

El método está también caracterizado porque la información del estado del enlace comprende un número de señales NACK o ACK (de ACKnowledgement, en inglés – Reconocimiento) entre nodos de la red.

El método está también caracterizado porque la información del estado del enlace comprende un número de errores de bit en una comunicación entre nodos de la red.

El método está también caracterizado porque la información del estado del enlace comprende información acerca de la propiedad de los nodos de la red.

El método está también caracterizado porque la comunicación inalámbrica se basa en la radiación electromagnética con una frecuencia en el intervalo de 100 kHz a 100 PHz.

El método está también caracterizado porque la comunicación inalámbrica es una o varias de IEEE 802.11, IEEE 802.15, IEEE 802.16, HiperLAN, HomeRF, Bluetooth, IR, UWB, JTRS, 3G, GPRS y EDGE.

El método está también caracterizado porque cuando se detecta un fallo de encaminamiento de un paquete de datos, se retransmite el citado paquete de datos a través de una ruta diferente determinada utilizando un procedimiento predictivo que utiliza la información del estado del enlace de los nodos de infraestructura en la red inalámbrica, anticipando o extrapolando el procedimiento predictivo un estado de futuro cercano de la información del estado del enlace almacenada en el elemento de encaminamiento basándose en un parámetro de desvanecimiento o un parámetro de velocidad de variación.

En otra realización, se proporciona un nodo para encaminamiento en una red de comunicación inalámbrica de multisalto. El nodo comprende un medio para obtener el estado del enlace para obtener información del estado del enlace desde otros nodos de la red. El nodo comprende también un medio de monitorización del estado del enlace, para transmitir la información del estado del enlace a un medio de encaminamiento; donde el nodo comprende también un medio de encaminamiento, caracterizado porque el medio de encaminamiento para determinar una ruta de acuerdo con la citada información de la calidad del enlace utiliza un procedimiento predictivo, anticipando o extrapolando el procedimiento predictivo un estado de futuro cercano de la información del estado del enlace basándose en un parámetro de desvanecimiento o en un parámetro de velocidad de variación. El encaminamiento significa encaminar tráfico de acuerdo con la ruta determinada.

El nodo está también caracterizado porque la comunicación inalámbrica está basada en la radiación electromagnética con una frecuencia en el intervalo de 100 kHz a 100 PHz.

El nodo está también caracterizado porque la comunicación inalámbrica es una o varias de IEEE 802.11, IEEE 802.15, IEEE 802.16, HiperLAN, HomeRF, Bluetooth, IR, UWB, JTRS, 3G, GPRS y EDGE.

El nodo está también caracterizado porque el procedimiento predictivo comprende un protocolo de encaminamiento ad hoc reactivo.

El nodo está también caracterizado porque el procedimiento predictivo comprende un protocolo de encaminamiento ad hoc proactivo.

El nodo está también caracterizado porque el procedimiento predictivo comprende una combinación de los protocolos de encaminamiento ad hoc reactivo y proactivo.

El nodo está también caracterizado porque la información del estado del enlace es información del estado del canal de radio dada mediante la medición de al menos uno de dispersión de Doppler, tiempo de coherencia, duración media del desvanecimiento, potencia de la señal o relación de señal a ruido de interferencia.

El nodo está también caracterizado porque el procedimiento predictivo para el citado protocolo de encaminamiento ad hoc reactivo obtiene información acerca del estado del enlace y del estado del canal de radio a partir de la RREP modificada, mensajes de Saludo, Reconocimientos o mensajes de RERR.

El nodo está también caracterizado porque el procedimiento predictivo para el citado protocolo de encaminamiento ad hoc proactivo tiene una tabla de encaminamiento modificada que contiene un campo de estado de la ruta con información acerca del estado del enlace de radio.

El nodo está también caracterizado porque la información del estado del enlace comprende el estado de energía de los nodos de la red.

El nodo está también caracterizado porque la información del estado del enlace comprende un número de señales de NACK o ACK (de ACKnowledgement, en inglés – Reconocimiento) entre los nodos de la red.

El nodo está también caracterizado porque la información del estado del enlace comprende el número de errores de bit entre los nodos de la red.

El nodo está también caracterizado porque la información del estado del enlace comprende información acerca de la propiedad de los nodos de la red.

En otra realización más, se proporciona un sistema para encaminamiento en una red de comunicación inalámbrica de multi-salto que comprende una pluralidad de nodos de red. Al menos un nodo de la pluralidad de nodos de red es un nodo de acuerdo con cualquiera de los nodos descritos anteriormente.

En otra realización, se proporciona un programa de ordenador para controlar el encaminamiento en una red de comunicación inalámbrica de multi-salto. El programa de ordenador comprende un primer conjunto de instrucciones para obtener información del estado del enlace entre nodos, caracterizado porque el programa de ordenador

comprende también un segundo conjunto de instrucciones para determinar una ruta utilizando la información del estado del enlace obtenida en un procedimiento predictivo, anticipando o extrapolando el procedimiento predictivo un estado del futuro cercano basándose en un parámetro de desvanecimiento o en un parámetro de velocidad de variación. El programa de ordenador también comprende un tercer conjunto de instrucciones que encamina tráfico de acuerdo con la citada ruta determinada.

En una realización, un sistema para el encaminamiento eficiente en una red de comunicación inalámbrica de multisalto que comprende una pluralidad de nodos de red, caracterizado porque el sistema comprende un medio para obtener información de la calidad indicando el estado del enlace entre los nodos de infraestructura, un medio para utilizar la información de la calidad del enlace en un proceso de determinación de ruta en los nodos de infraestructura que utiliza un procedimiento predictivo; conteniendo la información de la calidad del enlace información acerca de una información que varia con el tiempo del estado del enlace, y el modelo predictivo utiliza la información variable con el tiempo del estado del enlace en el procedimiento predictivo; y un medio de encaminamiento para encaminar paquetes de datos de acuerdo con una ruta determinada.

El sistema está también caracterizado porque el enlace inalámbrico es un sistema de transmisión basado en la radiación electromagnética con una frecuencia en el intervalo de 100 KHz a 100 PHz. El sistema está también caracterizado porque el sistema de transmisión es uno o varios de IEEE 802.11, IEEE 802.15, IEEE 802.16, HiperLAN, HomeRF, Bluetooth, IR, UWB, JTRS, 3G, GPRS o EDGE.

En otro aspecto, el sistema comprende un protocolo de encaminamiento ad hoc reactivo, un protocolo de encaminamiento ad hoc proactivo o una combinación de los protocolos de encaminamiento ad hoc reactivo y proactivo.

De acuerdo con otro aspecto, el sistema está caracterizado porque la información del estado del enlace es una información del estado del canal de radio dada mediante la medición de al menos uno de dispersión de Doppler, tiempo de coherencia, duración media del desvanecimiento, potencia de la señal o relación de señal a ruido de interferencia.

El sistema está caracterizado porque el procedimiento predictivo para un protocolo de encaminamiento ad hoc utiliza la información del estado del enlace obtenida y la información del canal de radio obtenidas en una comparación con determinados criterios de anticipación del encaminamiento.

El sistema está caracterizado porque el modelo predictivo para el protocolo de encaminamiento ad hoc reactivo obtiene información acerca del estado del enlace y un estado del canal a partir de la RREP modificada, mensajes de Saludo, Reconocimientos o mensajes de RERR.

El sistema está también caracterizado porque el modelo predictivo para el protocolo de encaminamiento ad hoc proactivo comprende una tabla de encaminamiento modificada que contiene un campo de estado de la ruta con información acerca del estado del enlace.

El sistema está también caracterizado porque la información del estado del enlace comprende el estado de energía de los nodos de la red.

El sistema está también caracterizado porque la información del estado del enlace comprende un número de señales de NACK o ACK (de ACKnowledgement, en inglés – Reconocimiento) entre nodos de la red.

El sistema de acuerdo con otro aspecto, caracterizado porque la información del estado del enlace comprende el número de errores de bit en una comunicación entre nodos de la red.

El sistema está también caracterizado porque la información del estado del enlace comprende información relativa a la propiedad de los nodos de la red.

En otra realización, un protocolo de encaminamiento utilizado en un sistema de acuerdo con la descripción anterior.

Siendo también el protocolo de encaminamiento uno de un protocolo de encaminamiento ad hoc proactivo, protocolo de encaminamiento ad hoc reactivo o una combinación de un protocolo de encaminamiento ad hoc proactivo y reactivo.

En otra realización, un método para el encaminamiento eficiente en una red de comunicación inalámbrica que comprende una pluralidad de nodos, comprendiendo el método las etapas de: obtener el estado del enlace entre nodos, actualizar un elemento de encaminamiento con la información del estado del enlace, determinar una ruta eficiente de acuerdo con un modelo predictivo que utiliza la información del estado del enlace y encaminar el tráfico de acuerdo con la ruta determinada.

La etapa de determinación de la ruta comprende la etapa de utilizar un protocolo de encaminamiento ad hoc reactivo, un protocolo de encaminamiento ad hoc proactivo o una combinación de los protocolos de encaminamiento ad hoc reactivo y proactivo.

En otro aspecto, el método obtiene información del estado del enlace inalámbrico a partir de mediaciones de al menos uno de dispersión de Doppler, tiempo de coherencia, duración media del desvanecimiento, potencia de la señal o relación de señal a ruido de interferencia.

El procedimiento predictivo para un protocolo de encaminamiento ad hoc comprende la etapa de utilizar la información del estado del enlace obtenida en comparación con determinados criterios de anticipación de encaminamiento.

El procedimiento predictivo para el protocolo de encaminamiento ad hoc reactivo comprende la etapa de obtener información acerca del estado del enlace a partir de RREP modificada, de mensajes de Saludo, de Reconocimientos

o de mensajes de RERR.

El procedimiento predictivo para el protocolo de encaminamiento ad hoc proactivo comprende la etapa de modificar una tabla de encaminamiento con un campo de estado de la ruta con información acerca del estado del enlace.

La información acerca del estado del enlace puede ser el estado de la energía de los nodos de la red, señales de ACK (de ACKnowledgement, en inglés – Reconocimiento) entre nodos de la red, el número de errores de bit en una comunicación entre nodos de la red o información acerca de la propiedad de los nodos de la red.

El método está también caracterizado porque la comunicación inalámbrica es un sistema de transmisión basado en la radiación electromagnética con una frecuencia en el intervalo de 100 kHz a 100 PHz. El nodo incluso está también caracterizado porque el sistema de transmisión es uno o varios de IEEE 802.11, IEEE 802.15, IEEE 802.16, HiperLAN, HomeRF, Bluetooth, IR, UWB, 3G, GPRS y EDGE.

En otra realización, un nodo para el encaminamiento eficiente en una red de comunicación inalámbrica de multi-salto caracterizado porque el aparato comprende: un medio de obtención de la calidad del enlace, un medio para monitorizar el estado del enlace que proporciona la información del estado del enlace al medio de encaminamiento, determinando una ruta apropiada de acuerdo con la información de la calidad del enlace utilizando un procedimiento predictivo.

El nodo caracterizado también porque el enlace inalámbrico es un sistema de transmisión basado en la radiación electromagnética con una frecuencia en el intervalo de 100 kHz a 100 PHz. El nodo incluso está también caracterizado porque el sistema de transmisión es uno o varios de IEEE 802.11, IEEE, 802.15, IEEE 802.16, HiperLAN, HomeRF, Bluetooth, IR, UWB, JTRS, 3G, GPRS y EDGE.

El nodo comprende un protocolo de encaminamiento ad hoc reactivo, un protocolo de encaminamiento ad hoc proactivo o una combinación de los protocolos de encaminamiento ad hoc reactivo y proactivo.

En otro aspecto, el nodo está caracterizado porque la información del estado del enlace es información del estado del canal de radio dada por la medición de al menos uno de dispersión de Doppler, tiempo de coherencia, duración media del desvanecimiento, potencia de la señal o relación de señal a ruido de interferencia.

El nodo caracterizado también porque el modelo predictivo para un protocolo de encaminamiento ad hoc utiliza la información del estado del enlace obtenida y la información del canal de radio en una comparación con determinados criterios de anticipación del encaminamiento.

El nodo caracterizado también porque el modelo predictivo para el protocolo de encaminamiento ad hoc reactivo obtiene información acerca del estado del enlace y del estado del canal de radio a partir de RREP modificada, mensajes de Saludo, Reconocimientos o mensajes de RERR.

El nodo está también caracterizado porque el modelo predictivo para el protocolo de encaminamiento ad hoc proactivo tiene una tabla de encaminamiento modificada que contiene un campo de estado de la ruta con información acerca del estado del enlace de radio.

El nodo está también caracterizado porque la información del estado del enlace comprende el estado de energía de los nodos de la red, el número de señales de NACK o ACK (de ACKnowledgement, en inglés – Reconocimiento) entre nodos de la red, el número de errores de bit entre los nodos de la red o información acerca de la propiedad de los nodos de la red.

En otra realización, una coordinación entre capas para su uso en una red de comunicación inalámbrica que comprende: una primera capa que comprende un medio de obtención de información del canal de radio, una segunda capa que comprende un medio de obtención de información del estado del enlace y una tercera capa que comprende un medio para monitorizar el estado del enlace que obtiene información del canal de radio y del estado del enlace a partir de las capas primera y segunda, un medio de determinación de ruta que utiliza la información del estado del enlace y un medio de encaminamiento para encaminar datos a través de la ruta determinada.

En otra realización, un programa de ordenador para controlar el encaminamiento en una red de comunicación inalámbrica de multi-salto que comprende: un primer conjunto de instrucciones para la obtención de información del estado del enlace entre nodos de infraestructura; un segundo conjunto de instrucciones para determinar una ruta eficiente utilizando la información del estado del enlace obtenida en un procedimiento predictivo; y un tercer conjunto de instrucciones que encamina el tráfico de acuerdo con la ruta determinada.

En otra realización, un artículo de fabricación que comprende un programa de ordenador para controlar el encaminamiento en una red de comunicación inalámbrica de multi-salto que comprende: un primer conjunto de instrucciones para obtener la información del estado del enlace entre nodos de infraestructura; un segundo conjunto de instrucciones para determinar una ruta eficiente utilizando la información de estado del enlace obtenida en un procedimiento predictivo; y un tercer conjunto de instrucciones de encaminamiento del tráfico de acuerdo con la ruta determinada.

Un método para el encaminamiento eficiente en una red inalámbrica caracterizado porque los paquetes de datos están encaminados utilizando las siguientes etapas: proporcionar información del estado de un enlace midiendo la calidad del estado del enlace entre nodos de infraestructura de la red; actualizar un elemento de encaminamiento con la información del estado del enlace; determinar una ruta utilizando la información del estado del enlace; encaminar el paquete de datos a través de la ruta determinada; y cuando se detecta un fallo de encaminamiento de un paquete de datos, retransmitir el paquete de datos a través de una ruta diferente determinada utilizando un procedimiento predictivo que utiliza la información del estado del enlace de los nodos de infraestructura de la red inalámbrica.

Este y otros objetos, características, funciones y beneficios de la presente invención resultarán evidentes con referencia a la descripción detallada que sigue.

Breve descripción de los dibujos

La Fig. 1 es un diagrama de bloques esquemático de algunos de los componentes y de su respectiva función en un concepto de capas intercaladas de una realización preferida de la invención. La Fig. 2 es un diagrama de la potencia de la señal y de un parámetro de velocidad de variación en función del tiempo con un nivel de umbral que gobierna la lenta o rápida determinación de categoría. La Fig. 3 es una ilustración esquemática de cómo se devuelven la información del estado del canal y la información de la calidad del enlace al sistema para un protocolo de encaminamiento reactivo. La Fig. 4 es una ilustración esquemática de cómo se devuelven las predicciones del estado del canal al sistema para un protocolo reactivo. La Fig. 5 es una representación esquemática de una pequeña red ad hoc y las posibles rutas entre dos nodos de esta red. La Fig. 6 es una ilustración esquemática de una topología de red ad hoc inalámbrica. La Fig. 7 es un diagrama de bloques esquemático que ilustra parte del proceso de encaminamiento y de determinación de ruta para un protocolo ad hoc de encaminamiento reactivo (Fig. 7A) y un protocolo de encaminamiento ad hoc proactivo (Fig. 7B). La Fig. 8 es un diagrama de bloques esquemático que ilustra un nodo de la red.

Descripción detallada de la Invención

En la Fig. 6, se muestra el concepto básico de una red ad hoc inalámbrica de multi-salto de telefonía móvil de la presente invención. Una pluralidad de nodos o elementos de infraestructura 601, 602, 603, 604… 60n construye una red ad hoc 610 conjunta comunicándose entre sí y enviando tráfico de datos y tráfico de control para cada uno, con el fin de mantener el tráfico de red entre los nodos de extremo y nodos intermedios que se comunican. A veces una

o varias puertas de enlace 601 están presentes en una red ad hoc 610. La puerta de enlace 601 actúa como un enlace entre, por ejemplo, una red ad hoc 610 inalámbrica y una red de IP 620 fija estándar (por ejemplo, Internet). La conexión 600 a la red de IP estándar puede ser una línea fija, que utiliza por ejemplo una red Ethernet o una conexión inalámbrica fija que utiliza por ejemplo, sistemas LMDS o de “Mini-enlace” o una tecnología similar.

No mostrados explícitamente en la Fig. 6 existen terminales de usuario clientes/finales que pueden comunicarse a través de estos nodos de infraestructura 601, 602, 603, 604… 60n; no obstante, la infraestructura puede realmente ser construida utilizando los propios terminales de usuario clientes/finales. También puede ser construida mediante encaminadores dedicados o una red puede ser construida sobre una combinación de estos dos elementos. Los terminales de usuario clientes/finales de hoy en día tienen la potencia de cálculo para manejar aplicaciones de red,

incluso en un entorno ad hoc. Los terminales clientes pueden incluir equipos tal como ordenadores de sobremesa, estaciones de trabajo, ordenadores portátiles, PDAs (Personal Digital Assistant, en inglés – Asistente Digital Personal), teléfonos móviles u otros equipos de procesamiento de datos con comunicación o medios de red.

Un elemento o nodo de infraestructura 601, 602, 603, 604… 60n, 800 comprende al menos un medio de procesamiento (801), un medio de almacenamiento (802), un medio de comunicación 805 y un medio de encaminamiento 101, 803. El medio de comunicación 805 puede ser inalámbrico 806 ó utilizar una conexión de cable 806, no obstante en una realización de preferencia el medio de comunicación 805 es inalámbrico. El medio de encaminamiento 101, 803 es implementado en un algoritmo de encaminamiento, que a menudo utiliza un programa de software, y normalmente tanto el medio de encaminamiento 101, 803 como/o el medio de comunicación 805 están a menudo incluidos en el elemento de infraestructura 800, pero pueden estar también situados en un dispositivo externo conectado a un elemento de infraestructura 601, 602, 603, 604… 60n, 800 a través de un conector 804. Un ejemplo de esta disposición puede ser una PDA que tenga un dispositivo externo conectado a la PDA; este dispositivo externo maneja el encaminamiento y/o el medio de comunicación para habilitar la PDA para ser parte de una red ad hoc 610 ó una red inalámbrica en general.

En la Fig. 1 los componentes clave en el elemento de encaminamiento 800 y sus respectivas funciones se muestran junto con los patrones de flujo de datos y de tráfico de control dentro de un modelo de referencia de red en capas, por ejemplo, el modelo de OSI. La primera capa 104 (L1) es responsable de la transmisión física de bits de datos y en esta capa puede haber una funcionalidad para medir y obtener el estado y la calidad de las propiedades del medio físico, por ejemplo, el estado del canal de radio inalámbrico. Esta información es devuelta a la tercera capa 106 (L3) a un monitor de estado del enlace 102.

Existen varios parámetros diferentes que pueden ser medidos con el fin de obtener el estado de los enlaces de radio entre los nodos de infraestructura. Uno de tales parámetros es la dispersión de Doppler. La dispersión de Doppler, la duración media del desvanecimiento y el tiempo de coherencia (proporcional a la duración media del desvanecimiento) son ambos parámetros que describen la naturaleza variable con el tiempo del canal de radio. Si existe un movimiento relativo entre una estación de telefonía móvil y el nodo de infraestructura habrá problemas de desvanecimiento asociados con el mismo. Lo mismo aplica si hay un objeto en movimiento en la ruta de radio entre dos nodos de infraestructura o un nodo de infraestructura y una estación de telefonía móvil. Cuando cada nodo envía y recibe periódicamente señales de aviso, por ejemplo, “mensajes de saludo”, o monitoriza de alguna otra manera las señales de radio de nodos vecinos, es posible medir la llamada desviación de Doppler fD, que puede proporcionar una indicación de la calidad del canal de radio, la desviación de Doppler es una medida del ancho de la dispersión de Doppler. Esta medida es comparada con un límite superior para la desviación de Doppler fDUL (DUL – Doopler Upper Limit, en inglés) que establece el límite en el cual el algoritmo de encaminamiento ad hoc todavía podrá adaptarse sin degradar la eficiencia de la transmisión. Si el ancho de banda de la señal es mucho mayor que el límite de umbral determinado de la dispersión de Doppler los efectos son despreciables y esta situación se define como desvanecimiento lento y por ello no es un problema para que el algoritmo de encaminamiento ad hoc se adapte a él aumentando la frecuencia de actualización. No obstante, si la dispersión de Doppler es mayor de un nivel de umbral determinado, el desvanecimiento está en la llamada región rápida, y entonces, en el caso de que el algoritmo de encaminamiento aumente la frecuencia de actualización de la ruta, esto en algún momento empezará a degradar la eficiencia del flujo de tráfico, puesto que el tráfico de control tendrá una porción cada vez mayor de las capacidades de transmisión disponibles. Debe observarse que a medida que la dispersión de Doppler aumenta también, el efecto de FEC (Forward Error Correction, en inglés – Corrección de Error de Transmisión) aumenta también, proporcionando así una calidad del enlace de L2 mucho mayor.

La duración media del desvanecimiento <τD> se calcula a partir del modelo de desvanecimiento de Rayleigh. A partir de estos cálculos es posible deducir la duración media del desvanecimiento y comparar ésta con un límite de umbral <τDUL>, que puede ser comparada con su contrapartida fDUL. <τD> puede ser calculada a partir de la siguiente ecuación:

donde M es el número de duraciones de desvanecimiento monitorizadas, τm es la duración de desvanecimiento mésima, N(RS) es el número de cruces de nivel desvanecido en el nivel Rs por segundo y T es el tiempo de medida.

Otro parámetro que describe la calidad del enlace de radio es la llamada velocidad de variación VS 201 (de Variation Speed, en inglés), como se ilustra en la Fig. 2, que es una medida de con qué rapidez están cambiando la potencia

de señal 202 recibida o la relación de señal a ruido de interferencia 202. VS 201 puede ser calculada diferenciando la potencia de canal 202 instantánea. Cuando VA 201 es menor que un nivel de umbral VSUL 203, el algoritmo de encaminamiento ad hoc es todavía capaz de adaptarse sin degradar la eficiencia de la red. No obstante, cuando VS 201 es mayor que VSUL 203 aparecerá el mismo problema que para la dispersión de Doppler mencionada anteriormente, donde la frecuencia de adaptación 204 de la tabla de encaminamiento llevará a la degradación de la eficiencia de la transmisión debido a que el tráfico de control absorbe una porción mayor de las capacidades de transmisión disponibles.

La segunda capa 105 (L2) maneja el control de la transmisión de trozos de información mayores y se encarga del manejo del error, de la detección y de las respuestas apropiadas a los errores. También puede proporcionar a la tercera capa 106 información acerca de la calidad del enlace puesto que maneja la detección de errores. Por ejemplo, la información acerca del número de las señales NACK o ACK 408, 409 y 410 puede ser transmitida al monitor del estado del enlace 102. Una interpretación de estos parámetros puede ser que un aumento del número de señales NACK indicaría que el enlace está reduciendo su calidad, mientras que un incremento de las señales ACK indicaría que el canal de radio está mejorando de calidad.

También, el número de errores de bit que son detectados y corregidos por un elemento de Corrección de Error de Transmisión (FEC – Forward Error Correction, en inglés) situado en L2 105 puede ser reportado al monitor del estado del enlace 102. Este parámetro puede reflejar la calidad del enlace que no aparece explícitamente a partir de la señalización ACK/NACK mencionada anteriormente.

El monitor del estado del enlace 102 monitoriza la información de la propiedad del canal y de la calidad del enlace obtenida a partir de la primera capa de red 104 L1 y la segunda capa de red 105 L2. El monitor del estado del enlace 102 determina la calidad, con respecto a criterios predeterminados, del canal de radio y lo clasifica en uno de dos tipos diferentes de categorías de desvanecimiento; desvanecimiento lento o rápido si se mide la dispersión de Doppler o en categorías de VS lenta o rápida si se mide la VS.

El monitor del estado del enlace 102 puede recibir también información desde una capa de aplicación o desde el hardware del nodo que es relevante en un proceso de determinación de ruta. Tal información puede ser, por ejemplo, el nivel de batería o el estado de energía de los nodos de la red, con el fin de excluir tales nodos de la ruta de encaminamiento o al menos reducir la cantidad de uso de estos nodos. Esta exclusión se realiza con el fin de preservar el nivel de batería de estos nodos, puesto que pueden ser terminales de cliente y los usuarios clientes/finales no desean que sus equipos se queden sin alimentación de batería por varias razones. Existe también un riesgo mayor de que los nodos con bajos niveles de batería puedan dejar de funcionar en un futuro cercano. Otro parámetro de encaminamiento igual de relevante puede ser la información de propiedad de los nodos de infraestructura, con el fin de poder implementar un método de encaminamiento con el menor coste económico en una red de multi-propietario. En tal método pueden encaminarse paquetes a través de elementos de infraestructura en los que el operador del cliente tiene un acuerdo con el propietario. Este planteamiento resulta útil si existen costes de encaminamiento monetarios implementados en cada nodo de infraestructura y resulta de interés mantener los costes monetarios lo más bajos posible. Este planteamiento no está limitado a redes ad hoc inalámbricas, sino que puede ser implementado en cualquier red de comunicación en la que se encaminen paquetes de IP.

El monitor del estado del enlace 102 transmite la información de estado obtenida y analizada a un elemento de encaminamiento 101. Este elemento 101 lleva a cabo cálculos de encaminamiento para determinar una ruta para que el paquete de datos actual sea enviado, también determina cuándo y cómo debe actualizar la tabla de encaminamiento. El elemento de encaminamiento maneja el envío y la recepción tanto de datos de tráfico como de tráfico de control. Maneja el procesamiento de las actualizaciones del encaminamiento e inicia las actualizaciones del encaminamiento de acuerdo con las planificaciones predeterminadas o a partir de la información del estado obtenida del monitor del estado del enlace 102.

El método o el procedimiento de determinación de ruta que utiliza un modelo o un procedimiento predictivo que consiste en tomar la información del estado del enlace obtenida de las mediciones de la calidad de radio y/o del enlace, monitoriza las variaciones de enlaces, y anticipa o extrapola el estado del futuro cercano de cada enlace almacenado en la tabla de encaminamiento, así que el elemento de encaminamiento 101 puede actualizar la configuración de encaminamiento antes del fallo de los enlaces. Esto tiene la ventaja de reducir el flujo de tráfico innecesario debido a la pérdida de paquetes.

El método o procedimiento de determinación de ruta puede ser resuelto en un programa de software que reside en los nodos de infraestructura.

En L3 106 se almacena información acerca de medidas previas durante una cierta cantidad de tiempo con el fin de comprender las tendencias y cambios de la calidad del enlace. Esto se almacena con técnicas estándar dependiendo del hardware utilizado en los nodos de infraestructura.

La Tabla 1 muestra algunos escenarios y su interpretación considerando la potencia de la señal junto con un parámetro de desvanecimiento o parámetro VS de velocidad de variación.

Tabla 1: Características del estado del enlace

Potencia media de la señal o calidad del L2

FD alta o VS alta FD baja o VS baja

Baja

Errores continuos y aleatorios Errores en ráfaga durante algún tiempo

Alta

Condiciones continuas y buenas En ráfaga y buenas condiciones durante algún tiempo

A partir de la Tabla 1 es posible obtener los siguientes ejemplos de criterios de anticipación junto con asunciones que se listan a continuación sobre las tendencias de potencia:

10 1. En caso de baja fD o baja VS:

Si la potencia de la señal va de baja a alta, va a aparecer una nueva ruta. Si la potencia de la señal va de alta a baja, la ruta actual desaparecerá.

15 2. En caso de alta fD o alta VS:

Si la potencia de la señal va de baja a alta, una nueva ruta continua va a aparecer lentamente. Si la potencia de la señal va de alta a baja, la ruta continua actual va a desaparecer lentamente.

20 La potencia de la señal o la calidad de la L2 en la Tabla 1 se refieren a valores medios, lo que significa que representan la calidad del canal durante un intervalo de tiempo relativamente largo, mientras que fD o VS se definen en el intervalo de tiempo corto. La definición de largo y corto a este respecto depende del sistema en el que esta invención se implemente. Intervalo de tiempo largo puede definirse como que cubre el intervalo de varias tramas de tráfico, mientras que un intervalo de tiempo corto puede definirse como que cubre el intervalo de varios símbolos o

25 bits transmitidos. Por lo tanto variaciones rápidas de canal en un tiempo corto pueden provocar errores de bit que pueden ser recuperados mediante técnicas de FEC (Forward Error Correction, en inglés – Corrección de Error de Transmisión). Puesto que la FEC lleva una parte de información (a veces llamada bits sistemáticos) y su parte de paridad utilizando diferentes instantes del tiempo. Si los instantes de tiempo están suficientemente separados, de manera que no hay ninguna correlación de tiempo frente a canal entre dos instantes, la FEC puede proporcionar un

30 efecto de tiempo-diversidad; en el cual la parte de información o la parte de paridad pueden sobrevivir al desvanecimiento. La función de FEC puede entonces recuperar la información correcta.

A partir de estos casos resulta evidente cómo es posible modificar el parámetro de encaminamiento ad hoc de una manera predictiva, en actualizaciones de ruta afectadas en particular.

35 Se darán ahora algunos ejemplos de utilización de este método para protocolos de encaminamiento ad hoc tanto reactivos como proactivos.

Si el encaminamiento se basa en un protocolo proactivo la tabla de encaminamiento es actualizada periódicamente

40 mediante procedimientos normales dependiendo del protocolo utilizado. Uno de tales protocolos puede ser DSDV, que mantiene una tabla de encaminamiento de los nodos de la red. Este protocolo de encaminamiento se modifica de acuerdo con la medida del estado y por consiguiente se añade un listado extra en la tabla de encaminamiento, indicando el estado del enlace. La información del estado del enlace es distribuida utilizando técnicas normales dependiendo del protocolo de encaminamiento elegido, por ejemplo utilizando “mensajes de saludo” y/o mensajes

45 de topología.

Si, por ejemplo, un paquete de datos debe ser enviado al nodo C 503 desde el nodo A 501 como se indica en la Fig. 5A, el paquete de datos es transmitido a través del nodo B 502. No obstante, puesto que el estado actual del enlace entre el nodo B 502 y el nodo C 503 en este ejemplo se sabe que se está cerrando (es decir, la potencia de la señal

50 se está reduciendo con el tiempo) y el comportamiento es en ráfagas (es decir, el parámetro de desvanecimiento o VS ha sido medido tan bajo como el valor de umbral), y el sistema también sabe a partir de las medidas que una ruta que pasa a través del nodo D 504 tiene una calidad mejor, el elemento de encaminamiento 101 decide entonces que el siguiente paquete será enviado a través del nodo D 504 en lugar de utilizar la antigua ruta 505 y 506 a través del nodo B 502, este cambio de ruta se indica en la Fig. 5B.

55 Un método de encaminamiento de acuerdo con un protocolo de encaminamiento proactivo puede ser ilustrado en el algoritmo que se describe a continuación (véase también la Fig. 7B):

1.

Todos los nodos de la red ad hoc inalámbrica miden su respectiva calidad de enlace hacia los vecinos de una manera regular.

2.

Toda la información de calidad del enlace es distribuida a todos los nodos en la red ad hoc inalámbrica y actualizados y almacenados en sus respectivas tablas de encaminamiento de acuerdo con determinadas frecuencias de actualización de encaminamiento.

3.

Un nodo de fuente desde el cual se originan los paquetes de datos determina una ruta apropiada utilizando la información de la calidad del enlace y el modelo predictivo.

4.

El paquete de datos en consideración es encaminado a un nodo de destino de acuerdo con la ruta determinada.

Si el encaminamiento se basa en un protocolo de encaminamiento reactivo se utiliza un método ligeramente diferente. La determinación de la ruta no se actualiza de la misma manera periódica que para el protocolo proactivo, sino que por el contrario se actualiza a demanda; el protocolo de encaminamiento reacciona bajo la demanda del envío de un paquete y de ahí la necesidad de conocer al menos parte de la ruta para enviar el paquete.

Como se ve en la Fig. 3, que ilustra un ejemplo de descubrimiento de ruta modificado en un protocolo de encaminamiento reactivo, la información del estado del enlace 304, 305 y 306 se incluye en el mensaje de respuesta de ruta (RREP – Route REPly, en inglés) normal que define la información de descubrimiento de la ruta devuelta al nodo de fuente 300. Con esta información el elemento de encaminamiento 101 puede cambiar la ruta del paquete de datos dependiendo de la información obtenida acerca de la ruta activa actual. La información del estado incluida proporciona un mensaje de RREP 313, 314 y 315 modificado que proporciona al elemento de encaminamiento 101 información para obtener el estado actual del enlace y predecir el estado del enlace en un futuro cercano de todos los enlaces de la cadena entre el nodo de fuente 300 y de destino 303. La información del estado del enlace acerca de cada nodo de la cadena de encaminamiento es añadida al mensaje de respuesta de ruta (RREP – Route REPly, en inglés) modificado. En la Fig. 3 cuatro nodos de ejemplo están implicados en una transacción de paquetes. Un paquete es transferido de un nodo de fuente 300 a un nodo de destino 303 a través de dos nodos intermedios 301 y

302. Cuando el paquete es transferido al nodo de destino 303 el último nodo intermedio 302 devuelve un mensaje de RREP 313 modificado. Este mensaje de RREP 313 modificado contiene información acerca de la información del enlace 304 entre el último nodo intermedio 302 y el nodo de destino 303. El mensaje de RREP es transferido de nuevo a la cadena hasta un nodo intermedio 301 previo (en el ejemplo de la Fig. 3, éste es el nodo intermedio 1 301) y este nodo 301 añade información acerca del estado del enlace entre el enlace entre sí mismo y el siguiente nodo 302 hacia arriba en la cadena (nodo intermedio 2 302). Cuando el mensaje de RREP 315 finalmente vuelve al nodo de fuente 300 contendrá información acerca de todos los enlaces de la cadena de encaminamiento de la red entre el nodo de fuente 300 y el nodo de destino 303. Este tipo de esquema puede ser utilizado independientemente del número de nodos de la red, no obstante en la Fig. 3 sólo se representa cuatro nodos, pero se comprenderá que éste no es un número limitativo. El número de nodos puede ser menor o mayor. Sólo la información de L1 en la RREP ha sido ilustrada en la Fig. 3, no obstante también la información de L2 de cada nodo implicado puede estar incluida y/u otra información, de otras partes de los nodos de infraestructura, relevantes para el encaminamiento puede ser también incluida. Este método puede ser utilizado por un protocolo de encaminamiento reactivo basado en ad hoc como, por ejemplo, AODV o DSR.

Un método de encaminamiento de acuerdo con un protocolo de encaminamiento reactivo puede ser ilustrado en el algoritmo que se describe a continuación (véase también la Fig. 7A):

1.

Todos los nodos de la red ad hoc inalámbrica miden su respectiva calidad del enlace hacia los vecinos de una manera regular.

2.

Toda la información de la calidad del enlace se distribuye a todos los nodos participantes en la ruta de la red ad hoc inalámbrica y es actualizada y clasificada en sus respectivas tablas de encaminamiento cuando se ha emitido una solicitud de ruta.

3.

El nodo de fuente determina una ruta apropiada utilizando la información de la calidad del enlace y el modelo predictivo.

4.

El paquete de datos en consideración es encaminado de acuerdo con la ruta determinada.

También es posible modificar la señal de RERR estándar enviada en los protocolos de encaminamiento reactivos basados en ad hoc y esto se ilustra en la Fig. 4. Esta modificación se realiza enviando un mensaje de RERR modificado desde un nodo 402 y ha detectado que puede aparecer un fallo hacia el siguiente salto 406. Este RERR modificado contiene información acerca del estado del enlace 404 de este enlace 406 de interés y es devuelto al nodo de fuente 400. Los nodos intermedios anteriores en la cadena de la red 401 transmiten esta información 404 al nodo de fuente 400. El elemento de encaminamiento 101 en el nodo de fuente 400 utiliza esta información y puede cambiar la ruta de manera correspondiente.

Utilizando este planteamiento de RERR 404 modificado es posible reducir drásticamente las retransmisiones de paquetes debido a fallos en el enlace posteriormente en la cadena de la red. Normalmente pasa algún tiempo hasta que el protocolo de encaminamiento detecta un fallo en el enlace y el elemento de encaminamiento 101 intentará

reenviar el paquete de datos varias veces antes de decidir que el fallo en el enlace ha ocurrido y cambiar la configuración del encaminamiento. Con el presente método es posible cambiar la ruta antes de que un enlace falle y por lo tanto que el número de retransmisiones debido a fallos en el enlace puede ser reducido o incluso eliminado.

Con información acerca del estado del enlace entre nodos el modelo predictivo puede ser utilizado para cambiar la ruta mediante la detección de un fallo del enlace antes de la retransmisión de datos a través de la misma ruta se dé, como es el procedimiento normal para protocolos de encaminamiento estándar. El paquete enviado que falló es retransmitido utilizando una nueva ruta puesto que el elemento de ruta 101 conoce el fallo del enlace mediante el método de obtención del estado del enlace, específicamente a través de los mensajes de RERR modificados. Las Figs. 5A y 5B se utilizan para ilustrar este ejemplo de diversidad de encaminamiento, donde un paquete es enviado desde el nodo A 501 al nodo C 503 primero a través del nodo B 501 y cuando se produce el fallo del enlace la retransmisión del mismo paquete va por el contrario a través del nodo D 504.

El modelo de encaminamiento inteligente que utiliza el modelo predictivo puede ser utilizado en muchas áreas de aplicación tales como, por ejemplo, por la policía en general o durante eventos especiales, fuerzas de rescate durante un desastre o un accidente, fuerzas militares en el campo de batalla o en el entrenamiento, o para áreas de acceso inalámbrico en edificios con el propósito de comunicación tanto para acceso a red residencial como comercial. Por ejemplo es posible utilizar estas redes ad hoc para construir acceso de banda ancha utilizando equipos de corto alcance, bajo coste, inalámbricos en áreas residenciales donde otra tecnología de acceso de banda ancha es escasa o demasiado cara para conectarla. Pueden ser también utilizadas en distritos comerciales para proporcionar acceso de banda ancha a empresas o pequeñas compañías, o para conexiones inalámbricas en los llamados puntos hotspot (en inglés) (lugares con red inalámbrica). Los hotspots se caracterizan porque proporcionan acceso a comunicación dentro de una cierta área, por ejemplo en la sala de espera de un aeropuerto o en hoteles, para clientes de pago o de manera gratuita dependiendo del modelo de negocio.

Debe observarse que aunque en una realización preferida se utiliza un monitor de estado del enlace 102, esta función podría también ser incorporada en el elemento de encaminamiento 101.

El protocolo de encaminamiento es independiente del esquema de codificación de radio utilizado y puede utilizarse cualquier tipo de radio. Por ejemplo, se pueden mencionar estándares de radio como los de la serie IEEE 802.11 (por ejemplo, IEEE 802.11a, IEEE 802.11b, IEEE 802.11g y así sucesivamente), IEEE 802.15, IEEE 802.16, HiperLAN, HomeRF, Bluetooth, IR (InfraRojo), UWB (Ultra WideBand, en inglés - Ultra Banda Ancha), JTRS (Joint Tactical Radio System, en inglés – Sistema de Radio Táctica Conjunta), 3G (Comunicación mediante telefonía móvil de Tercera Generación), GPRS (General Packet Radio Service, en inglés - Servicio de Radio en Paquetes General)

o EDGE (Enhanced Data Rate for Global Evolution, en inglés – Velocidad de Datos Mejorada para Evolución Global). No obstante los posibles estándares de radio no están limitados a los mencionados anteriormente. Puede ser cualquier esquema de transmisión basado en la radiación electromagnética adecuado que opere dentro de la banda de frecuencia de 100 kHz a 100 PHz; esto incluye frecuencias de radio, frecuencias de microondas y frecuencias en los regímenes infrarojo, visible y ultravioleta.

Aplicaciones en paralelo para resolver la planificación del tráfico y la diversidad de ruta ad hoc:

1.

”Diversidad de ruta ad hoc”

2.

”Planificación de tráfico ad hoc”

por los mismos inventores han sido presentadas simultáneamente.

Debe observarse también que aunque la red ad hoc inalámbrica ha sido ilustrada en la realización preferida los mismos conceptos pueden ser aplicables a una red de cable o a una red inalámbrica fija.

Aunque la invención ha sido descrita con detalle con el propósito de ilustración, debe entenderse que tal detalle es únicamente con ese propósito y que los expertos en la materia pueden realizar variaciones en la misma sin apartarse de la invención excepto como puede estar limitada por las reivindicaciones.

Claims (23)

1. REIVINDICACIONES

   1. Un método para el encaminamiento en una red de comunicación inalámbrica que comprende una pluralidad de nodos, comprendiendo el método las etapas de:

   5 obtener información del estado del enlace entre nodos; actualizar un elemento de encaminamiento con la información del estado del enlace obtenida, comprendiendo el elemento de encaminamiento la información del estado del enlace previamente almacenada, caracterizado por:

   10 determinar una ruta de acuerdo con un procedimiento predictivo, anticipando o extrapolando el procedimiento predictivo un estado de futuro cercano de la información del estado del enlace almacenada en el elemento de encaminamiento basándose en un parámetro de desvanecimiento o en un parámetro de velocidad de variación; y encaminar tráfico de acuerdo con la citada ruta determinada.
2. 2. El método de acuerdo con la reivindicación 1, en el que el citado procedimiento predictivo comprende un protocolo de encaminamiento ad hoc reactivo.
3. 3. El método de acuerdo con la reivindicación 1, en el que el citado procedimiento predictivo comprende un protocolo 20 de encaminamiento ad hoc proactivo.
4. 4. El método de acuerdo con la reivindicación 1, en el que el procedimiento predictivo comprende una combinación de los protocolos de encaminamiento ad hoc reactivo y proactivo.

   25 5. El método de acuerdo con la reivindicación 1, en el que la citada etapa de obtener obtiene información del estado del enlace inalámbrico a partir de medidas de al menos uno de dispersión de Doppler, tiempo de coherencia, duración media del desvanecimiento, potencia de la señal o relación de señal a ruido de interferencia.
5. 6. El método de acuerdo con la reivindicación 2, en el que el citado procedimiento predictivo para el citado protocolo

   30 de encaminamiento ad hoc reactivo comprende la etapa de obtener información acerca del estado del enlace a partir de RREP modificada, mensajes de Saludo, Reconocimientos o mensajes de RERR.
6. 7. El método de acuerdo con la reivindicación 3, en el que el citado procedimiento predictivo para el citado protocolo

   de encaminamiento ad hoc proactivo comprende la etapa de modificar una tabla de encaminamiento con un campo 35 de estado de la ruta con información acerca del estado del enlace.
7. 8. El método de acuerdo con la reivindicación 1, en el que la citada información del estado del enlace comprende el estado de energía de los nodos de la red.

   40 9. El método de acuerdo con la reivindicación 1, en el que la citada información del estado del enlace comprende un número de señales NACK o ACK entre nodos de la red.
8. 10. El método de acuerdo con la reivindicación 1, en el que la citada información del estado del enlace comprende

   un número de errores de bit en una comunicación entre nodos de la red. 45
9. 11. El método de acuerdo con la reivindicación 1, en el que la citada información del estado del enlace comprende información acerca de la propiedad de los nodos de la red.
10. 12. El método de acuerdo con la reivindicación 1, caracterizado porque la citada comunicación inalámbrica está 50 basada en la radiación electromagnética con una frecuencia en el intervalo de 100 kHz a 100 PHz.
11. 13. El método de acuerdo con la reivindicación 13, en el que la citada comunicación inalámbrica es una o varias de IEEE 802.11, IEEE 802.15, IEEE 802.16, HiperLAN, HomeRF, Bluetooth, IR, UWB, JTRS, 3G, GPRS y EDGE.

    55 14. Un nodo (800) para el encaminamiento en una red de comunicación inalámbrica de multi-salto, comprendiendo el citado nodo:

    un medio de obtención del estado del enlace (3001) para obtener la información del estado del enlace de otros nodos de la red;60 un medio para monitorizar el estado del enlace (102), para transmitir la información del estado del enlace a un medio de encaminamiento; en el que el nodo comprende también un medio de encaminamiento,

    caracterizado por

    un medio de encaminamiento (101) para determinar una ruta de acuerdo con la citada información de la calidad del enlace utilizando un procedimiento predictivo, anticipando o extrapolando el procedimiento predictivo un estado en el futuro cercano de la información del estado del enlace basándose en un parámetro de desvanecimiento o en un parámetro de velocidad de variación; y que el citado medio de encaminamiento (101) encamine el tráfico de acuerdo con la ruta determinada.

    5 15. El nodo (800) de acuerdo con la reivindicación 14, caracterizado porque la citada comunicación inalámbrica está basada en la radiación electromagnética con una frecuencia en el intervalo de 100 kHz a 100 PHz.
12. 16. El nodo (800) de acuerdo con la reivindicación 15, caracterizado porque la citada comunicación inalámbrica es

    una o varias de IEEE 802.11, IEEE 802.15, IEEE 802.16, HiperLAN, HomeRF, Bluetooth, IR, UWB, JTRS, 3G, 10 GPRS y EDGE.
13. 17. El nodo (800) de acuerdo con la reivindicación 14, en el que el citado procedimiento predictivo comprende un protocolo de encaminamiento ad hoc reactivo.

    15 18. El nodo (800) de acuerdo con la reivindicación 14, en el que el citado procedimiento predictivo comprende un protocolo de encaminamiento ad hoc proactivo.
14. 19. El nodo (800) de acuerdo con la reivindicación 14, en el que el citado procedimiento predictivo comprende una

    combinación de los protocolos de encaminamiento ad hoc reactivo y proactivo.20
15. 20. El nodo (800) de acuerdo con la reivindicación 15, caracterizado porque la citada información del estado del enlace es la información del estado del enlace de radio dada por la medida de al menos uno de dispersión de Doppler, tiempo de coherencia, duración media del desvanecimiento, potencia de la señal o relación de señal a ruido de interferencia.
16. 21. El nodo (800) de acuerdo con cualquiera de las reivindicaciones 17 ó 20, caracterizado porque el citado procedimiento predictivo para el citado protocolo de encaminamiento ad hoc reactivo obtiene información acerca del estado del enlace y del estado del canal de radio a partir de RREP modificada, mensajes de Saludo, Reconocimientos o mensajes de RERR.
17. 22. El nodo (800) de acuerdo con cualquiera de las reivindicaciones 18 ó 20, caracterizado porque el citado procedimiento predictivo para el citado protocolo de encaminamiento ad hoc proactivo tiene una tabla de encaminamiento modificada que contiene un campo del estado de la ruta con información acerca del estado del enlace de radio.
18. 23. El nodo (800) de acuerdo con la reivindicación 14, caracterizado porque la citada información del estado del enlace comprende el estado de energía de los nodos de la red.
19. 24. El nodo (800) de acuerdo con la reivindicación 14, caracterizado porque la citada información del estado del 40 enlace comprende un número de señales NACK o ACK entre nodos de la red.
20. 25. El nodo (800) de acuerdo con la reivindicación 14, caracterizado porque la citada información del estado del enlace comprende el número de errores de bit entre los nodos de la red.

    45 26. El nodo (800) de acuerdo con la reivindicación 14, caracterizado porque la citada información del estado del enlace comprende información acerca de la propiedad de los nodos de la red.
21. 27. Un sistema para el encaminamiento en una red de comunicación inalámbrica de multi-salto que comprende una

    pluralidad de nodos de red, en el que al menos un nodo de la pluralidad de nodos de la red es un nodo de acuerdo 50 con cualquiera de las reivindicaciones 14-26.
22. 28. Un programa de ordenador para controlar el encaminamiento en una red de comunicación inalámbrica de multisalto que comprende:

    55 un primer conjunto de instrucciones para obtener información del estado del enlace entre nodos, caracterizado porque el programa de ordenador comprende también un segundo conjunto de instrucciones para determinar una ruta utilizando la citada información del estado del enlace obtenida en una procedimiento predictivo, anticipando o extrapolando el procedimiento predictivo un estado de futuro cercano de la información del estado del enlace almacenada en el elemento de

    60 encaminamiento basándose en un parámetro de desvanecimiento o en un parámetro de velocidad de variación; y un tercer conjunto de instrucciones que encamina tráfico de acuerdo con la citada ruta determinada.
23. 29. El método de la reivindicación 1, que comprende también, cuando se detecta un fallo de encaminamiento de un paquete de datos, retransmitir el citado paquete de datos a través de una ruta diferente determinada utilizando un procedimiento predictivo que utiliza información del estado del enlace de los nodos de infraestructura en la red inalámbrica, anticipando o extrapolando el procedimiento predictivo un estado de futuro cercano del estado del enlace almacenado en el elemento de encaminamiento basándose en un parámetro de desvanecimiento o en un parámetro de velocidad de variación.