Método y disposición para determinación de costes de enlace para enrutamiento en redes inalámbricas.

Un metodo de determinación de un coste de enlace para enrutamiento en una red (1) multi-salto inalambrica,

caracterizado por:

determinar un primer conjunto (15) de nodos (30, 50) que son bloqueados por un primer nodo (10) de un par de nodos que transmiten datos por un enlace (12) inalambrico hasta un segundo nodo (20) de dicho par de nodos;

determinar un segundo conjunto (25) de nodos (40, 50) que son bloqueados por el citado segundo nodo (20) que transmite datos por dicho enlace (12) inalambrico hasta dicho primer nodo (10), y

determinar un coste de enlace para dicho enlace (12) inalambrico en base al numero cardinal de la unión de dicho primer conjunto (15) de nodos (30, 50) y dicho segundo conjunto (25) de nodos (40, 50) .

Metodo y disposición para determinación de costes de enlace para enrutamiento en redes inalambricas Campo tecnico La presente invención se refiere en general a enrutamiento en redes de comunicación, tal como las redes multi-salto, 5 y mas en particular al hecho de determinar metricas apropiadas de costes de enlace para su uso en la determinación de ruta y en el enrutamiento en tales redes.

Antecedentes En las ultimas decadas se ha producido una explosión en cuanto al uso de comunicaciones inalambricas para la transmisión de datos entre estaciones o nodos comunicantes. Con este incremento en la comunicación inalambrica 10 de datos, se han desarrollado diferentes tipos de redes de comunicaciones que emplean, por ejemplo, diferentes medios o estandares de acceso al medio. Un esquema de ese tipo para acceso al medio desarrollado recientemente es el esquema de Acceso al Medio por Adquisición de Suelo (FAMA) . Esta tecnica de acceso al medio se implementa y se utiliza, por ejemplo, en Redes Inalambricas de Area Local (WLANs) IEEE 802.11 y en otras redes basadas en contención. En las redes basadas en FAMA, la comunicación de datos desde un nodo o estación de transmisión hasta un nodo de recepción, bloquea temporalmente cualquier transmisión de otros nodos de red que potencialmente pudieran llegar a oir la comunicación de datos. Esto significa que un nodo tiene primero que verificar la ausencia de otro trafico, antes de transmitir datos por el medio fisico compartido.

En la actualidad, el IEEE 802.11 facilita la comunicación de salto simple entre nodos o estaciones segun un modo establecido de servicio basico independiente. Sin embargo, el soporte multi-salto para el IEEE 802.11 y otras redes 20 basadas en contención, es una caracteristica deseable. Esto se debe a que en una red multi-salto, los nodos que esten entre si fuera de alcance pueden beneficiarse de los nodos situados en posiciones intermedias que puedan enviar sus mensajes desde la fuente hacia el destino. Un beneficio adicional con el soporte multi-salto consiste en que dividiendo una distancia en multiples saltos, cada salto experimentara una calidad de recepción de senal significativamente mejorada. Por consiguiente, esto puede ser aprovechado para el uso de una tasa de enlace mas alta que bajo determinadas condiciones puede reducir el retardo de extremo a extremo.

Tradicionalmente, las redes multi-salto han sido asociadas con frecuencia a las llamadas redes ad hoc, en las que los nodos son móviles en su mayor parte y no existe infraestructura de coordinación central. Sin embargo, la idea de realizar redes multi-salto puede ser aplicada tambien cuando los nodos son fijos. Adicionalmente, se puede prever tambien coordinación central, en particular cuando los nodos son fijos y los canales son robustos. Se pueden prever redes hibridas que incluyan enlaces alambricos adicionalmente a los enlaces inalambricos en redes multi-salto.

El enrutamiento, es decir, el acto de transportar la información desde una fuente hasta un destino a traves de uno o mas nodos intermedios en una red de comunicación, incluye en general dos tareas basicas: determinar trayectorias de enrutamiento adecuadas y transportar información a traves de la red. En el contexto del proceso de enrutamiento, la primera de esas tareas se menciona normalmente como determinación de ruta, y la ultima de esas tareas se menciona con frecuencia como envio de datos o de paquetes.

Para la determinación de ruta, una propuesta habitual consiste en extender lo que se conoce como arbol de enrutamiento. El arbol de enrutamiento se calcula normalmente en base a un algoritmo de trayectoria mas corta, lo que implica que las trayectorias mas cortas determinadas desde los diversos nodos del arbol hasta el nodo de destino, son las llamadas "trayectorias de minimo o menor coste". En la practica, el arbol puede ser construido continuamente y actualizado para gestionar las condiciones de movilidad y de cambio de enlace.

Cuando un nodo particular del arbol desea enviar un paquete en el proceso subsiguiente de envio de paquetes, el nodo se considera como un nodo fuente, y el paquete sigue la trayectoria de enrutamiento determinada desde la fuente hasta el destino. Diferentes nodos pueden enviar paquetes hasta el mismo destino en el tiempo, con lo que diferentes nodos actuaran como nodos fuente y los enviaran a lo largo de sus trayectorias respectivas mas cortas.

45 Adicionalmente, puesto que pueden existir multiples destinos, se pueden generar multiples arboles, cada uno de ellos implantado en un destino correspondiente.

El envio del paquete es por lo general relativamente directo, mientras que la determinación de la ruta o trayectoria puede ser muy compleja.

Los protocolos de enrutamiento utilizan por lo general lo que conoce como metrica de enrutamiento como base para 50 evaluar que trayectoria o ruta sera la mejor para un paquete dado, y determinar con ello la trayectoria óptima hasta el destino. En la tecnica anterior, muchas metricas diferentes han sido usadas por los algoritmos de enrutamiento para determinar la mejor ruta, o al menos una ruta adecuada.

Una metrica clasica de salto por cable resulta inadecuada en un entorno inalambrico, debido basicamente a que no refleja la dependencia de la calidad del enlace con respecto a la distancia. Un ejemplo de metrica por cable de

menos uso en situaciones inalambricas, encontrada aun de manera frecuente, es una metrica de conteo de salto simple, en la que el coste de enlace ΔCij desde el nodo νi hasta el νj se define como ΔCij = 1.

otra metrica que ha sido sugerida en la literatura investigada se basa en la distancia fisica entre dos nodos, por ejemplo ΔCij = Distanciaij.

Un mejor ejemplo adecuado para un entorno de radio consiste en utilizar la tasa de enlace media estimada y definir el coste de enlace como la inversa de la tasa media de enlace, es decir ΔCij = 1/fij, suponiendo capacidades de adaptación de tasa. Esta metrica puede ser apreciada de dos maneras. En primer lugar, para un paquete de tamano fijo, procura ofrecer trayectorias de retardo minimo (suponiendo que el retardo de cola de espera en la red sea despreciable) . Sin embargo, en el contexto de un esquema multi-salto con una fase de datos de tamano fijo (con un numero variable de paquetes en una fase de datos dependiendo de la adaptación de tasa) , ofrece la utilización de recurso de minimo tiempo a lo largo de una trayectoria. La metrica de enlace basada en tasa media puede ser estimada mediante la capacidad de Shannon clasica:

en la que B es el ancho de banda (puede ser despreciado si se utiliza solamente un ancho de banda comun en todo el sistema) , E{....} es el valor esperado, Pi es la potencia de transmisión del nodo νi (la cual puede ser fija o determinada mediante algun otro mecanismo) , σ2N es el nivel de ruido (en el nodo νj) y Gij es la ganancia media de enlace. El termino σ2N podria incluir tambien potencialmente interferencia media, modelada como ruido gaussiano complejo, aparte del ruido del receptor.

Segun otro ejemplo mas, resulta adecuada para un entorno de radio la inversa de la ganancia media de enlace, es decir, ΔCij = Gij-1. Esta metrica proporciona grandes valores (con potencia media fija) de SNR (Relación de Senal respecto a Ruido) del receptor, y rutas de minima potencia (con control de potencia) . Esta no es una mala metrica, pero puede conducir a una situación en la que los paquetes experimenten grandes retrasos (principalmente debido a que no reflejan la capacidad de un enlace apropiadamente) .

Utilizando la capacidad de Shannon para el caso de metrica de ganancia inversa que se ha descrito en lo que antecede, se aprecia que corresponde a enrutamiento de minima potencia con una tasa de enlace objetivo fij (objetivo) dada. La potencia minima se determina entonces como:

Aunque los costes de enlace y las metricas de enrutamiento de la tecnica anterior trabajan bastante bien para diversas redes de comunicaciones inalambricas, no estan adaptados a las caracteristicas especificas de bloqueo de nodos presentes en IEEE 802.11 y en otras redes de comunicaciones basadas en contención o en FAMA.

El documento Wo 03/071751 A1 presenta una verdadera integración de funciones de capa cruzada sobre varias capas de protocolo dentro de una red, proporcionando una propuesta unificada al aprovisionamiento de QoS en una red multi-salto. Las conexiones se determinan mediante optimización integrada de una función objetivo dada con respecto a parametros de conexión... [Seguir leyendo]

1. Un metodo de determinación de un coste de enlace para enrutamiento en una red (1) multi-salto inalambrica, caracterizadoºpor:

determinar un primer conjunto (15) de nodos (30, 50) que son bloqueados por un primer nodo (10) de un par de nodos que transmiten datos por un enlace (12) inalambrico hasta un segundo nodo (20) de dicho par de nodos;

determinar un segundo conjunto (25) de nodos (40, 50) que son bloqueados por el citado segundo nodo (20) que transmite datos por dicho enlace (12) inalambrico hasta dicho primer nodo (10) , y determinar un coste de enlace para dicho enlace (12) inalambrico en base al numero cardinal de la unión de dicho primer conjunto (15) de nodos (30, 50) y dicho segundo conjunto (25) de nodos (40, 50) .

2. Un metodo para determinación de ruta en base a un coste de enlace en una red (1) multi-salto inalambrica, caracterizadoºpor:

determinar un coste de enlace para un enlace (12) inalambrico entre un primer nodo (10) de un par de nodos y un segundo nodo (20) de dicho par de nodos de acuerdo con la reivindicación 1, y realizar determinación de ruta al menos parcialmente en base a dicho coste de enlace determinado.

3. Un metodo para enrutamiento de datos en base a un coste de enlace en una red (1) multi-salto inalambrica, caracterizadoºpor:

realizar determinación de ruta de acuerdo con la reivindicación 2, y enviar datos desde un nodo (ν0) dado hasta al menos un nodo (ν2) contiguo por la trayectoria hasta un nodo (ν13) de destino dado de acuerdo con la citada determinación de ruta.

4. El metodo de a cuerdo con la reivindicación 2 6 3, caracterizado porque dicha etapa de realización comprende realizar determinación de ruta basada al menos parcialmente en el citado coste de enlace determinado y en un algoritmo de tipo de trayectoria mas corta.

5. El metodo de acuerdo con cualquiera de la reivindicaciones 1 a 4, caracterizado porque dicho primer conjunto (15) comprende tambien el citado segundo nodo (20) , y dicho segundo conjunto (25) comprende tambien el citado primer nodo (10) .

6. El metodo de acuerdo con cualquiera de las reivindicaciones 1 a 5, caracterizado porque dicha etapa de determinación de dicho segundo conjunto (25) comprende las etapas de:

recibir en dicho primer nodo (10) , desde dicho segundo nodo (20) , información de los nodos (10, 40, 50) que estan capacitados para comunicar directa e inalambricamente con el citado segundo nodo (20) , y determinar en dicho primer nodo (10) el citado conjunto (25) en base a dicha información recibida.

7. El metodo de acuerdo con cualquiera de las reivindicaciones 1 a 6, caracterizado porque dicha etapa de determinación de dicho segundo conjunto (25) comprende las etapas de:

oir en dicho primer nodo (10) las transmisiones de datos a, y desde, dicho segundo nodo (20) , y determinar en dicho primer nodo (10) que el citado segundo conjunto (25) comprende los nodos (40, 50) involucrados en dichas transmisiones de datos oidas.

8. El metodo de acuerdo con cualquiera de las reivindicaciones 1 a 7, caracterizadoºporquº cada nodo (30, 40, 50) de dicho primer conjunto (15) y de dicho segundo conjunto (25) esta asociado a un valor de tiempo de vida, comprendiendo ademas dicho metodo borrar un nodo (30, 40, 50) de dicho primer conjunto (15) o de dicho segundo conjunto (25) si dicho valor de tiempo de vida asociado a dicho nodo (30, 40, 50) ha expirado.

9. El metodo de acuerdo con cualquiera de las reivindicaciones 1 a 8, caracterizado por estimar una calidad de enlace real para el citado enlace (12) inalambrico, y dicha etapa de determinación de coste de enlace comprende determinar el citado coste de enlace en base a dicho primer conjunto (15) de nodos (30, 50) y a dicho segundo conjunto (25) de nodos (40, 50) y en base a una diferencia entre la citada calidad de enlace real estimada y una calidad minima de enlace requerida para el citado enlace (12) inalambrico.

10. El metodo de acuerdo con cualquiera de las reivindicaciones 1 a 9, caracterizado porque dicha etapa de determinación de coste de enlace comprende determinar el citado coste de enlace en base a dicho primer conjunto (15) de nodos (30, 50) y a dicho segundo conjunto (25) de nodos (40, 50) y en base a una duración de transmisión esperada por bit para enrutamiento de datos desde uno nodo (10, 20) de dicho par de nodos hasta el otro nodo (10, 20) de dicho par de nodos.

11. El metodo de acuerdo con la reivindicación 10, caracterizadoºpor:

estimar una tasa de enlace esperada para el citado enlace (12) inalambrico, y determinar la citada duración de transmisión por bit en base a dicha tasa de enlace esperada estimada.

12. El metodo de acuerdo con cualquiera de las reivindicaciones 1 a 11, caracterizadoºporque un nodo (30, 40, 50) se considera como bloqueado si dicho nodo (30, 40, 50) esta capacitado para detectar un nivel de potencia de senal originado por la transmisión de datos por parte de al menos un nodo (10, 20) de dicho par de nodos que exceda de un umbral minimo de potencia de senal.

13. El metodo de acuerdo con cualquiera de las reivindicaciones 1 a 12, caracterizado porque un paquete de datos (70, 71, 72) incluye un valor (75) de duración que indica un tiempo esperado durante el que el medio de comunicación inalambrica esta localmente reservado para dicho paquete de datos (70, 71, 72) y su posterior comunicación (71, 72, 73) inducida, siendo considerado un nodo (30, 40, 50) que oye la transmisión de dicho paquete de datos (70, 71, 72) como bloqueado hasta que dicho tiempo esperado haya expirado.

14. El metodo de acuerdo con cualquiera de las reivindicaciones 1 a 13, caracterizado porque dicha red (1) inalambrica es una red inalambrica basada en contención.

15. Una disposición (300) para determinar un coste de enlace para enrutamiento en una red (1) multi-salto inalambrica, caracterizadaºpor:

medios (322) para determinar un primer conjunto (15) de nodos (30, 50) que son bloqueados por un primer nodo (10) de un par de nodos que transmiten datos por un enlace (12) inalambrico hasta un segundo nodo (20) de dicho par de nodos;

medios (324) para determinar un segundo conjunto (25) de nodos (40, 50) que son bloqueados por dicho segundo nodo (20) que transmite datos por dicho enlace (12) inalambrico hasta el citado primer nodo (10) , y medios (320) para determinar un coste de enlace para dicho enlace (12) inalambrico en base al numero cardinal de la unión de dicho primer conjunto (15) de nodos (30, 50) y dicho segundo conjunto (25) de nodos (40, 50) .

16. Una disposición (300, 400) para determinación de ruta en base a coste de enlace en una red (1) multi-salto inalambrica, caracterizadaºpor:

una disposición (300) de acuerdo con la reivindicación 15 para determinar un coste de enlace para un enlace (12) inalambrico entre un primer nodo (10) de un par de nodos y un segundo nodo (20) de dicho par de nodos, y medios (410) para realizar determinación de ruta basada al menos parcialmente en dicho coste de enlace determinado por la citada disposición (300) de acuerdo con la reivindicación 15.

17. Una disposición (100) para enrutamiento de datos en base a coste de enlace en una red (1) multi-salto inalambrica, caracterizadaºpor:

una disposición (300, 400) de acuerdo con la reivindicación 16 para realizar determinación de ruta, y medios (200, 500) para enviar datos desde un nodo (ν0) dado hasta al menos un nodo (ν2) continuo por la trayectoria hasta un nodo (ν13) de destino dado de acuerdo con la citada determinación de ruta realizada mediante dicha disposición (300, 400) de acuerdo con la reivindicación 16.

18. La disposición de acuerdo con la reivindicación 16 6 17, caracterizada porque dichos medios (410) de realización estan dispuestos para realizar determinación de ruta en base al menos parcialmente a dicho coste de enlace determinado por los citados medios (320) de determinación y por un algoritmo de tipo de trayectoria mas corta.

19. La disposición de acuerdo con cualquiera de las reivindicaciones 15 a 18, caracterizada porque dicho primer conjunto (15) comprende el citado segundo nodo (20) y dicho segundo conjunto (25) comprende el citado primer nodo (10) .

20. La disposición de acuerdo con cualquiera de las reivindicaciones 15 a 19, caracterizadaºporque dichos medios

(324) para la determinación de dicho segundo conjunto estan al menos parcialmente dispuestos en el citado primer nodo (10) para determinar dicho segundo conjunto (25) en base a la información, recibida desde el citado segundo nodo (20) , de los nodos (40, 50) que estan capacitados para comunicar directa e inalambricamente con dicho segundo nodo (20) .

21. La disposición de acuerdo con cualquiera de las reivindicaciones 15 a 20, caracterizadaºporque dichos medios

(324) de determinación de dicho segundo conjunto (25) estan al menos parcialmente basados en dicho primer nodo

(10) para determinación de dicho segundo conjunto (25) al comprender los nodos (40, 50) involucrados en las transmisiones de datos a, y desde, dicho segundo nodo (20) y oidas por dicho primer nodo (10) .

22. La disposición de acuerdo con cualquiera de las reivindicaciones 15 a 20, caracterizadaºporque cada nodo (30, 40, 50) de dicho primer conjunto (15) y de dicho segundo conjunto (25) esta asociado a un valor de tiempo de vida, comprendiendo ademas dicha disposición (100; 300; 400) medios (310) para borrar un nodo (30, 40, 50) de dicho primer conjunto (15) o de dicho segundo conjunto (25) si dicho valor de tiempo de vida asociado a dicho nodo (30, 40, 50) ha expirado.

23. La disposición de acuerdo con cualquiera de las reivindicaciones 15 a 22, caracterizada por un estimador (350) para estimar una calidad de enlace real para dicho enlace (12) inalambrico, y dichos medios (320) para 10 determinación del citado coste de enlace estan dispuestos para determinar dicho coste de enlace en base al citado primer conjunto (15) de nodos (30, 50) y al citado segundo conjunto (25) de nodos (40, 50) , y en base a una diferencia entre dicha calidad de enlace real estimada y una calidad minima de enlace requerida para dicho enlace (12) inalambrico.

24. La disposición de acuerdo con cualquiera de las reivindicaciones 15 a 23, caracterizadaºporque dichos medios (320) para determinar el citado coste de enlace estan dispuestos para determinar dicho coste de enlace en base a dicho primer conjunto (15) de nodos (30, 50) y a dicho segundo conjunto (25) de nodos (40, 50) , y en base a una duración de transmisión esperada por bit para enrutar datos desde un nodo (10, 20) de dicho par de nodos hasta el otro nodo (10, 20) de dicho par de nodos.

25. La disposición de acuerdo con la reivindicación 24, caracterizadaºpor:

un estimador (340) para estimar una tasa de enlace esperada para el citado enlace (12) inalambrico , y medos (340) para determinar la citada duración de transmisión por bit en base a dicha tasa de enlace esperada estimada.

26. La disposición de cualquiera de las reivindicaciones 15 a 25, caracterizadaºporque dicha disposición (100; 300; 400) se implementa en al menos un nodo (10, 20) de dicha red (1) inalambrica.

27. Un nodo (10, 20) de red que comprende una disposición (100; 300; 400) de acuerdo con cualquiera de las reivindicaciones 15 a 25.