Red ad hoc móvil.

Un método para proporcionar datos de encaminamiento que se usarán para encaminar un mensaje desde un nodo (102) de origen a los nodos (100-116) de destino disponibles a través de una red (10) ad hoc móvil,

comprendiendo el método:

proporcionar una lista de nodos y la posición de cada nodo;

obtener, a partir de la lista de nodos, una lista de los nodos (101-106) vecinos correspondientes a los nodos de la lista que se encuentran dentro de la cobertura de comunicación directa con el nodo de origen;

proporcionar una función (223) de coste;

y caracterizado por:

usar, para cada nodo vecino, la función de coste para calcular los costes más bajos del envío de mensajes a los nodos de destino disponibles respectivos; y

generar datos de encaminamiento que se ordenen de acuerdo con una dirección del nodo de destino disponible, y asociar las entradas con cada dirección del nodo de destino disponible correspondiente a una lista respectiva de los nodos vecinos ordenados por el aumento de coste más bajo calculado del envío de mensajes a ese nodo de destino, donde los datos de encaminamiento generados excluyen una descripción de la ruta entre los nodos vecinos y los nodos de destino que proporcionan el coste más bajo calculado en cada caso.

Red ad hoc móvil

Campo de la invención La presente divulgación se refiere a las redes ad hoc móviles, y en particular a las redes ad hoc que usan las aeronaves. Las realizaciones de la invención se refieren al encaminamiento de mensajes desde un nodo de origen en la red ad hoc en base a su destino seleccionado, y al mantenimiento de una configuración de enlaces activos e inactivos hacia y desde un nodo de origen en la red ad hoc a sus nodos vecinos.

Antecedentes Se conocen bien las redes ad hoc. Comprenden una serie de nodos correspondientes a transmisores/ receptores individuales. Para cualquier nodo, habrá algunos nodos cercanos que estén en la cobertura de comunicación directa, y éstos se denominan como nodos vecinos. Otros nodos estarán fuera de la cobertura de comunicación directa y por eso solo pueden contactarse indirectamente con múltiples saltos a través de los nodos intermedios. La naturaleza ad hoc de la red significa que, para cualquier mensaje específico, pueden haber muchas rutas posibles a través de diversos nodos intermedios que conectan un nodo de origen con un nodo destino. Dirigir un mensaje a lo largo de una ruta específica necesita de una comparación de las rutas disponibles para seleccionar la mejor disponible. Para este fin, pueden asociarse los costes con cualquier ruta específica en base a, por ejemplo, el número de saltos entre los nodos, la longitud de cada salto, la velocidad de un nodo, etc. Son bien conocidos los algoritmos para determinar los costes relativos de las rutas disponibles, siendo un ejemplo el algoritmo de Dijkstra.

Se conocen las redes ad hoc móviles que usan los nodos móviles, y se han propuesto usando automóviles o aeronaves como nodos (normalmente en combinación con algunos nodos fijos tales como estaciones base o estaciones terrestres) . Puede encontrarse un ejemplo de una red ad hoc de automóviles en el documento EP-A

1.964.318. Puede encontrarse un ejemplo de una red ad hoc de aeronaves en el documento W02007/059560. Como los nodos son móviles y se mueven rápidamente por su propia naturaleza, la red tiene que reconfigurarse de forma continua para reflejar el hecho de que los pares de nodos respectivos se moverán dentro y, a continuación, fuera de la cobertura de la comunicación directa entre sí.

Implementar dicha red ad hoc para las aeronaves tiene un problema específico en que la velocidad relativa de la aeronave puede ser demasiado alta. Esto tiene un impacto adverso en la duración posible de un enlace de comunicación directa entre dos nodos, específicamente donde los nodos se corresponden con un par de aeronaves que vuelan en direcciones opuestas. El documento WO2007/059560 aborda este problema modificando cómo se calculan los costes de las rutas. Por ejemplo, cuando se solicitan datos de un destino desconocido (por ejemplo, solicitando datos del tiempo en una zona específica de cualquier otra aeronave que tiene dichos datos) , las rutas potenciales para la solicitud de salida se ponderan de acuerdo con las velocidades relativas de los nodos sucesivos en la ruta, recompensándose con velocidades relativas bajas. Esto maximiza la duración potencial de un enlace entre los nodos. Por otro lado, cuando se conocen el nodo de destino y su posición, el documento WO2007/059560 propone enviar el mensaje a lo largo de una trayectoria radial, es decir, a través de la aeronave localizada lo más cerca posible a unos nodos de origen y de destino de unión de arco y que están volando radialmente desde el centro de ese arco.

El documento EP 1.134.939 describe un método de encaminamiento en base a la localización de redes ad-hoc.

La presente divulgación se preocupa de los mensajes de encaminamiento que se envían desde un nodo de origen a un nodo de destino seleccionado en una red ad hoc móvil. La presente divulgación se preocupa también del mantenimiento de una configuración de enlaces activos e inactivos hacia y desde un nodo de origen a sus nodos vecinos en una red ad hoc móvil. Las redes ad hoc que usan aeronaves son de una preocupación específica.

Sumario Con estos antecedentes, la presente invención reside en un método para proporcionar datos de encaminamiento de acuerdo con la reivindicación 1.

Una primera realización de la invención divulga un método para proporcionar datos de encaminamiento para su uso en encaminar un mensaje desde un nodo de origen a los nodos de destino disponibles a través de una red ad hoc móvil. El método comprende proporcionar una lista de nodos y la posición de cada nodo, y obtener a partir de esta lista, una lista de los nodos vecinos correspondientes a los nodos de la lista que están dentro de la cobertura de comunicación directa con el origen. El método comprende además proporcionar una función de coste y usar, para cada nodo vecino, la función de coste para calcular los costes más bajos del envío de mensajes a los nodos de destino disponibles respectivos. El método también comprende generar datos de encaminamiento que comprenden, para cada nodo vecino, el coste más bajo para cada nodo de destino de acuerdo a como se ha calculado anteriormente.

La lista de nodos y la posición de cada uno de los nodos pueden proporcionarse de diferentes maneras. Por ejemplo, el método anterior puede implementarse en un ordenador, opcionalmente por un ordenador proporcionado en el nodo de origen. La lista de nodos y sus posiciones puede recuperarse de la memoria asociada con un ordenador. Como alternativa, la lista puede transmitirse al nodo de origen (que puede almacenarse en la memoria cuando se reciba) . Puede proporcionarse información adicional, por ejemplo, la cobertura de comunicación de cada nodo y/o la velocidad de cada nodo.

La lista de nodos y sus posiciones se usan para determinar los nodos vecinos. Esto puede basarse en la cobertura de comunicación del nodo de origen. También puede determinarse con respecto a la cobertura de comunicación de cada nodo (es decir, se usa la cobertura más corta del nodo de origen y del nodo vecino potencial) .

Pueden usarse diferentes maneras para obtener la función de coste. Opcionalmente, la función de coste se almacena en la memoria, por ejemplo, en una implementación de ordenador de una realización de la invención. La función de coste puede usarse a continuación en un algoritmo para encontrar el coste más bajo entre cada nodo vecino y los nodos de destino disponibles. Los nodos de destino disponibles pueden corresponder a todos los otros nodos o solo a un subconjunto de los mismos. Encontrar el menor coste puede comprender la evaluación del coste de todas las rutas posibles que enlazan un nodo vecino a otro nodo, y el registro de los costes más bajos encontrados, o puede usarse un algoritmo que busque de forma activa la trayectoria de coste más bajo.

Los datos de encaminamiento pueden comprender la información de cada nodo vecino. Específicamente, para cada nodo vecino se ha encontrado el coste más bajo de una ruta para cada nodo de destino. Los datos de encaminamiento no necesitan incluir los datos que describan las rutas reales determinadas para tener las puntuaciones más bajas. En algunas realizaciones, no se incluye el propio coste. Por ejemplo, los datos de encaminamiento pueden comprender datos ordenados de acuerdo con las direcciones del nodo de destino disponibles. Para cada dirección de nodo de destino disponible, pueden proporcionarse datos adicionales correspondientes a una lista de los nodos vecinos con un fin de coste, por ejemplo, ordenados por el aumento del coste. Opcionalmente, los costes más bajos pueden incluirse para cada nodo vecino. Los datos pueden presentarse y, opcionalmente, almacenarse como una tabla (o un archivo legible por ordenador cuya estructura corresponde efectivamente a una tabla) .

Como alternativa, los datos de encaminamiento comprenden una tabla que contiene entradas para cada nodo vecino correspondiente a un nodo de destino disponible y el coste más bajo calculado para ese nodo de destino.

La función de coste proporciona un medio para calcular el coste de cualquier ruta entre dos nodos. La función de coste se usa para permitir que se encuentre el coste de las diferentes rutas entre los nodos vecinos y los nodos de destino disponibles. Estos costes pueden compararse para determinar el coste más bajo de la mejor ruta que enlaza un nodo vecino a un nodo de destino. La función de coste puede incluir múltiples factores a tener en cuenta de diversas influencias en la bondad de una ruta entre los nodos. Cada factor puede combinarse con una ponderación relativa, de tal manera que algunos factores se vuelven más influyentes que otros. Pueden usarse los siguientes factores, o solos o en combinación (incluyendo en combinación con otros factores que no se describen... [Seguir leyendo]

1. Un método para proporcionar datos de encaminamiento que se usarán para encaminar un mensaje desde un nodo (102) de origen a los nodos (100-116) de destino disponibles a través de una red (10) ad hoc móvil, comprendiendo el método:

proporcionar una lista de nodos y la posición de cada nodo; obtener, a partir de la lista de nodos, una lista de los nodos (101-106) vecinos correspondientes a los nodos de la lista que se encuentran dentro de la cobertura de comunicación directa con el nodo de origen; proporcionar una función (223) de coste; y caracterizado por:

usar, para cada nodo vecino, la función de coste para calcular los costes más bajos del envío de mensajes a los nodos de destino disponibles respectivos; y generar datos de encaminamiento que se ordenen de acuerdo con una dirección del nodo de destino disponible, y asociar las entradas con cada dirección del nodo de destino disponible correspondiente a una lista respectiva de los nodos vecinos ordenados por el aumento de coste más bajo calculado del envío de mensajes a ese nodo de destino, donde los datos de encaminamiento generados excluyen una descripción de la ruta entre los nodos vecinos y los nodos de destino que proporcionan el coste más bajo calculado en cada caso.

2. El método de la reivindicación 1, donde las entradas asociadas con cada dirección del nodo de destino disponible comprenden además, incluir el coste asociado de cada nodo vecino a la lista de los nodos vecinos.

3. El método de la reivindicación 1 o la reivindicación 2, donde la función de coste comprende una combinación de factores.

4. El método de la reivindicación 3, donde cada factor tiene una ponderación asociada en la combinación.

5. El método de la reivindicación 3 o la reivindicación 4, donde la función de coste incluye cualquier combinación de:

(a) un factor que representa una cantidad fija para cada salto entre los nodos; (b) un factor que representa una cantidad para cada salto entre los nodos que varíe en proporción con las velocidades relativas de los nodos; (c) un factor que representa una cantidad para cada salto entre los nodos que varíe inversamente con una duración predicha de un tiempo de enlace entre los nodos; (d) un factor que representa una cantidad para cada salto entre los nodos que varíe de acuerdo con la distancia entre los nodos; y (e) un factor que representa una cantidad para cada salto entre los nodos que varíe inversamente con la distancia del enlace entre los nodos y el borde del agujero.

6. El método de cualquier reivindicación anterior, que comprende además proporcionar un tiempo, una lista de los nodos de la red ad hoc en ese tiempo, la posición de cada nodo en ese tiempo, y la velocidad de cada nodo en ese tiempo; calcular la posición actual de los nodos usando el tiempo proporcionado, las posiciones proporcionadas y las velocidades proporcionadas; y donde la etapa de obtención de una lista de nodos vecinos correspondientes a los nodos de la lista que están dentro de la cobertura de comunicación directa con el origen se basa en las posiciones calculadas.

7. Un método de encaminamiento de un mensaje desde un nodo (102) de origen que se debe enviar a un nodo de destino seleccionado a través de una red ad hoc móvil, comprendiendo el método:

el método de proporcionar datos de encaminamiento de acuerdo con una cualquiera de las reivindicaciones 1-6; y la etapa de enviar un mensaje desde un nodo de origen a un nodo de destino seleccionado a través de una red ad hoc móvil, incluyendo, la red ad hoc que comprende unos nodos, los nodos (101-106) vecinos que corresponden a los nodos dentro de la cobertura de comunicación directa con el nodo de origen, comprendiendo el método:

hacer referencia a los datos de encaminamiento; identificar (560) el mejor nodo vecino para encaminar el mensaje buscando los datos de encaminamiento del nodo de destino seleccionado del mensaje y determinar qué nodo vecino tiene el coste más bajo para el nodo de destino seleccionado; e intentar (570) reenviar el mensaje al mejor nodo vecino.

8. El método de la reivindicación 7, que comprende además una comprobación para ver si el intento de reenviar el mensaje al mejor nodo vecino falla y, si lo hace, intentar reenviar el mensaje al siguiente mejor nodo vecino, y así sucesivamente.

9. Un método de proporcionar datos de encaminamiento y mantener enlaces de datos que comprende:

el método de proporcionar datos de encaminamiento de acuerdo con la reivindicación 2 o cualquiera de las reivindicaciones 3 a 6, cuando depende de la reivindicación 2; y la etapa de mantenimiento de los enlaces de datos hacia y desde un nodo (102) de origen en una red (10) ad hoc móvil, donde la red comprende además unos nodos que incluyen los nodos (101-106) vecinos correspondientes a los nodos dentro de una cobertura (40) de comunicación directa con el nodo de origen, comprendiendo los nodos vecinos unos nodos vecinos activos y unos nodos vecinos inactivos, conectándose los nodos vecinos activos al nodo de origen a través de los enlaces de datos activos respectivos y teniendo los nodos vecinos inactivos unos enlaces de datos inactivos respectivos al nodo de origen, formando los enlaces de datos activos e inactivos una configuración actual de enlaces de datos, comprendiendo la etapa de mantenimiento de los enlaces de datos:

(1) identificar (1410) uno o más nodos vecinos perdidos correspondientes a los nodos vecinos de la configuración actual que han salido de la cobertura de comunicación directa con el nodo de origen y/o están a punto de salir de la cobertura de comunicación directa;

(2) determinar (1411) las configuraciones revisadas de los enlaces de datos en las que cualquiera de los enlaces activos a los nodos vecinos perdidos se considera inactivo y, para al menos una configuración revisada, un enlace inactivo se considera activo y/o un enlace activo adicional se considera inactivo;

(3) determinar (1411) un valor de configuración general para cada configuración revisada en base a, al menos en parte, los mejores costes del envío de mensajes desde el nodo de origen usando la configuración revisada de los enlaces de datos, donde los mejores costes del envío de mensajes se determinan con referencia a los datos de encaminamiento;

(4) seleccionar (1411) una nueva configuración de los enlaces de datos a partir de las configuraciones revisadas de acuerdo con los valores de configuración generales determinados; y

(5) formar (1414) la nueva configuración de los enlaces de datos rompiendo los enlaces de datos con los nodos vecinos que están activos en la configuración actual de los enlaces de datos pero inactivos en la nueva configuración de los enlaces de datos, y formar los enlaces de datos con cualquiera de los nodos vecinos que esté inactivo en la configuración actual de los enlaces de datos y activo en la nueva configuración de los enlaces de datos.

10. El método de la reivindicación 9, donde la etapa (3) comprende atribuir puntos al valor de configuración general considerando los mensajes enviados por el nodo de origen durante un período anterior.

11. El método de la reivindicación 9 o la reivindicación 10, que comprende además identificar nuevos nodos vecinos que han entrado en la cobertura de comunicación directa con el nodo de origen o están a punto de entrar en la cobertura de comunicación directa y la etapa (2) incluye determinar al menos una configuración revisada en la que se considera un enlace activo a un nuevo nodo vecino.

12. El método de cualquiera de las reivindicaciones 9 a 11, donde la selección de la nueva configuración en la etapa

(4) comprende seleccionar la configuración revisada con el mejor valor de configuración general.

13. El método de cualquiera de las reivindicaciones 9 a 12, donde si no puede enviarse un mensaje desde el nodo de origen debido a que un nodo vecino requerido es un nodo vecino inactivo, el método comprende además:

(i) determinar (1431) las configuraciones revisadas de los enlaces de datos en las que un enlace inactivo se considera activo y/o un enlace activo se considera inactivo;

(ii) determinar (1431) un valor de configuración general para cada configuración revisada en base a, al menos en parte, los mejores costes del envío de mensajes desde el nodo de origen usando la configuración revisada de los enlaces de datos, donde los mejores costes del envío de mensajes se determinan con referencia a los datos de encaminamiento;

(iii) seleccionar (1431) una nueva configuración de los enlaces de datos de las configuraciones revisadas de acuerdo con los valores de configuración generales determinados; y

(iv) formar (1434) la nueva configuración de los enlaces de datos rompiendo los enlaces de datos con los nodos vecinos que están activos en la configuración actual de los enlaces de datos pero inactivos en la nueva configuración de los enlaces de datos, y formar los enlaces de datos con cualquiera de los nodos vecinos que esté inactivo en la configuración actual de los enlaces de datos y activo en la nueva configuración de los enlaces de datos.

14. El método de la reivindicación 13, donde la etapa (i) comprende determinar una configuración revisada de los enlaces de datos en la que el enlace inactivo al nodo vecino requerido se considera activo.

15. El método de cualquiera de las reivindicaciones 9 a 12, donde si no puede enviarse un mensaje desde el nodo de origen debido a que un nodo vecino requerido es un nodo vecino inactivo, el método comprende además:

(I) poner (1265) el mensaje dentro de una cola y aumentar la puntuación de la cola;

(II) determinar (1430) cuándo la puntuación de la cola supera un límite, y cuándo se supera el límite;

(III) determinar (1431) las configuraciones revisadas de los enlaces de datos en las que un enlace inactivo se considera activo y/o un enlace activo se considera inactivo;

(IV) determinar (1431) un valor de configuración general para cada configuración revisada en base a, al menos en parte, los mejores costes del envío de mensajes desde el nodo de origen usando la configuración revisada de los enlaces de datos, donde los mejores costes del envío de mensajes se determinan con referencia a los datos de encaminamiento;

(V) seleccionar (1431) una nueva configuración de los enlaces de datos a partir de las configuraciones revisadas de acuerdo con los valores de configuración generales determinados; y

(VI) formar (1434) la nueva configuración de los enlaces de datos rompiendo los enlaces de datos con los nodos vecinos que están activos en la configuración actual de los enlaces de datos pero inactivos en la nueva configuración de los enlaces de datos, y formar los enlaces de datos con cualquiera de los nodos vecinos que esté inactivo en la configuración actual de los enlaces de datos y activo en la nueva configuración de los enlaces de datos.

16. El método de cualquiera de las reivindicaciones 9 a 15, donde cada nodo vecino tiene una puntuación de nodo vecino asociada, comprendiendo el método además asignar puntos a las puntuaciones de nodo vecino de acuerdo con el tráfico que ve ese nodo vecino.

17. El método de la reivindicación 16, donde si una puntuación de nodo vecino cae por debajo de un límite, el método comprende además:

(a) determinar (1421) las configuraciones revisadas de los enlaces de datos en las que un enlace inactivo se considera activo y/o un enlace activo se considera inactivo;

(b) determinar (1421) un valor de configuración general para cada configuración revisada en base a, al menos en parte, los mejores costes del envío de mensajes desde el nodo de origen usando la configuración revisada de los enlaces de datos, donde los mejores costes del envío de mensajes se determinan con referencia a los datos de encaminamiento;

(c) seleccionar (1421) una nueva configuración de los enlaces de datos a partir de las configuraciones revisadas de acuerdo con los valores de configuración generales determinados; y

(d) formar (1424) la nueva configuración de los enlaces de datos rompiendo los enlaces de datos con los nodos vecinos que están activos en la configuración actual de los enlaces de datos pero inactivos en la nueva configuración de los enlaces de datos, y formar los enlaces de datos con cualquiera de los nodos vecinos que esté inactivo en la configuración actual de los enlaces de datos y activo en la nueva configuración de los enlaces de datos.

18. El método de la reivindicación 16 o la reivindicación 17, que comprende además asignar puntos a las puntuaciones de nodo vecino para cada mensaje enviado de acuerdo con el coste de envío de ese mensaje a través de ese nodo vecino.