Un método para la configuración de la conexión en una red de comunicación inalámbrica multisalto,

dicho método que comprende los pasos de: - determinar, para una conexión solicitada entre un nodo fuente y un nodo destino, un conjunto de parámetros de conexión que incluyen el camino, el canal y al menos un parámetro de enlace físico expandiendo un árbol dirigido con los caminos preliminares para la conexión pendiente originada en el nodo fuente y que realiza un procedimiento de búsqueda para encontrar al menos el coste Ki para cada nodo i, en un conjunto dado, desde el nodo fuente de acuerdo con el siguiente algoritmo anidado: **Fórmula** donde i ≠ ID Fuente, N(i) es el conjunto de vecinos actuales del nodo i que a su vez es un conjunto de todos los nodos Ω en la red, j es un nodo vecino que pertenece a N(i), m es un conjunto de al menos un canal en un conjunto de M canales ortogonales en total, Ψ es uno o una multitud de parámetros de capa física, ki (j, m, Ψ), también indicado kij (m, Ψ), es el coste desde el nodo j al nodo i, en el que el coste kij (m, Ψ) incluye la potencia de transmisión del enlace Pj(m) para el nodo j y el canal m como un parámetro de la capa física Ψ, y la potencia de transmisión del enlace Pj(m) está sujeta a restricciones que restringen la potencia de transmisión del enlace para un intervalo predeterminado, y el término K(j), también indicado Kj, es el coste acumulado desde el nodo fuente al nodo j, y KID Fuente es el coste inicial en el nodo fuente, en el que el nivel de anidamiento más interior de dicho algoritmo anidado sintoniza dicho(s) parámetro(s) de la capa física Ψ, el siguiente nivel de anidamiento es una elección de un conjunto de canal(es) m para cada vecino, y el tercer nivel de anidamiento proporciona una elección entre vecinos j, de ahí que elige el camino en la capa de encaminamiento; y - establecer la conexión requerida en base al conjunto determinado de parámetros de conexión

CAMPO TÉCNICO DE LA INVENCIÓN

La presente invención se refiere generalmente al soporte de Calidad de Servicio (QoS) en redes de comunicaciones tales como redes inalámbricas multisalto, y más concretamente a la determinación de los parámetros de conexión, la configuración de conexión así como el control de admisión de la conexión en tales redes.

ANTECEDENTES

Cuando se aplica encaminamiento en una red inalámbrica, tal red es indicada a menudo una red multisalto. En una red multisalto, los nodos fuera del alcance entre ellos pueden beneficiarse de los nodos situados intermedios que pueden enviar sus mensajes desde la fuente hacia el destino. Tradicionalmente, las redes multisalto se han asociado con las denominadas redes ad hoc en las que los nodos son mayoritariamente móviles y no existe infraestructura de coordinación central. No obstante, la idea de conexión de redes multisalto también se puede aplicar cuando los nodos son fijos. Uno de tales escenarios apunta al acceso de Internet de área rural y usa nodos fijos unidos a la parte alta de los tejados de las casas, farolas o similares.

Aunque alguna investigación ha estado en curso en el área de multisalto desde los inicios de los 1970, se han dirigido relativamente pocos de esos esfuerzos de investigación hacia el aprovisionamiento de la QoS para las redes multisalto. La razón es que ese soporte de QoS en redes multisalto se considera que es de inmensa complejidad. La movilidad impredecible, los patrones de tráfico que cambian aleatoriamente aparentemente, los canales inalámbricos poco fiables, la complejidad de cálculo así como otros efectos perjudiciales son la causa de este panorama. Con todo algunos investigadores han intentado hacer frente al reto de la QoS para redes multisalto. La investigación más interesante y prometedora en este área se ha enfocado en usar algún tipo de TDMA (Acceso Múltiple por División en el Tiempo) espaciado como la estructura MAC (Control de Acceso al Medio) como base.

El estado de la técnica con respecto a las redes multisalto que proporciona canales libres de colisiones, que permiten rutas de QoS a ser establecidas entre un nodo fuente y un nodo destino, se describirá ahora más abajo. Estas clases de protocolos a menudo se conocen como protocolos de encaminamiento de la QoS. A diferencia de los protocolos de encaminamiento generales, el encaminamiento de la QoS no solamente requiere encontrar una ruta desde una fuente a un destino, sino que la ruta también debe satisfacer los requerimientos de la QoS extremo a extremo, dada a menudo en términos de ancho de banda y/o retardo, por ejemplo para soportar la comunicación multimedia en tiempo real. El estado de la técnica de los protocolos de encaminamiento de la QoS se podría dividir en dos grupos distintos, a partir de ahora conocidos como esquemas de encaminamiento y acceso al canal separado y esquemas de encaminamiento y acceso al canal integrado. En el primer grupo, la tarea de encaminamiento y asignación del canal se separa en dos algoritmos distintos, es decir primero se encuentra una ruta y a partir de entonces se realiza la asignación del canal, mientras que el segundo grupo adopta un planteamiento más o menos integrado para el encaminamiento y asignación del canal.

Para una mejor comprensión de los esquemas de encaminamiento de la QoS de la técnica previa, puede ser útil comenzar con una breve descripción del modelo OSI (Interconexión de Sistemas Abiertos) para las conexiones en red. El modelo OSI incluye siete capas de protocolo distintas: la capa física (1), la capa de enlace (2), la capa de red (3), la capa de transporte (4), la capa de sesión (5), la capa de presentación (6) y la capa de aplicaciones (7). La capa física, que se refiere a los aspectos físicos de las conexiones en red tal como los medios de transmisión, los dispositivos de transmisión y las señales de datos, no es vista algunas veces como una capa de protocolo. Por simplicidad no obstante, todas las capas se conocerán como capas de protocolo. Entre otras cosas, la capa de enlace establece y mantiene los enlaces entre los dispositivos de comunicación y controla el acceso al medio de la red. Las principales responsabilidades de la capa de red incluyen los servicios de conmutación, encaminamiento y pasarela. La capa de transporte es responsable de distribuir las tramas entre los servicios en distintos dispositivos. La capa de sesión gestiona el control del diálogo y la administración de las sesiones. La capa de presentación es responsable de la presentación de los datos y la capa de aplicaciones se refiere al aprovisionamiento de servicios en la red y proporciona un interfaz para las aplicaciones para el acceso a la red.

Esquemas de encaminamiento y acceso al canal separado

Los protocolos de encaminamiento de la QoS separados usan mediciones de la QoS genéricas y no se sintonizan a una capa MAC particular, es decir la capa 2. Para ser capaz de garantizar que los requerimientos de QoS se cumplen, estos protocolos tienen que ser mejorados con un protocolo MAC que proporciona acceso al canal libre de colisiones.

INSIGNIA

INSIGNIA [1] es un entramado de señalización en banda basada en IP extremo a extremo para proporcionar QoS en redes ad hoc. La señalización en banda supone que cada paquete transporta toda la información necesaria para establecer una reserva. El mecanismo de QoS es independiente tanto del protocolo de encaminamiento ad hoc usado (se hace referencia a por ejemplo [2] o [3]) como de la tecnología de la capa de enlace, aunque la QoS recibida final dependerá fuertemente de estos rasgos. La operación del entramado se puede describir como sigue: Una ruta desde la fuente al destino se encuentra por el protocolo de encaminamiento ad hoc en la capa 3. Dado que cada paquete transporta la información necesaria para reservar el ancho de banda necesario, los paquetes de datos pueden empezar a atravesar la ruta tan pronto como se ha establecido lo cual conduce a la rápida reserva. Cuando un nodo en una ruta desde la fuente al destino recibe un paquete desde un flujo para el que no ha reservado capacidad (indicado por un bit en la cabecera), reserva si es posible la capacidad requerida.

Exploración Basada en Billetes

Como fue el caso de INSIGNIA, la Exploración Basada en Billetes (TBP) [4] es un protocolo de capa 3 puro en el que se realiza toda la señalización sobre esta capa y que necesita el soporte de la capa 2 (MAC) para decidir si una reserva se puede aceptar o se debería rechazar. TBP no obstante es un verdadero protocolo de encaminamiento ad hoc. El principal propósito en la referencia [4] es localizar la búsqueda de caminos factibles entre la fuente y el destino para solo una parte de la red en lugar de inundar la red entera como es usual en los protocolos de encaminamiento ad hoc. Más específicamente, quieren buscar solamente un pequeño número de caminos desde la fuente al destino, en lugar de hacer una búsqueda exhaustiva costosa. Esto se logra expidiendo billetes. Un billete es el permiso para buscar un camino y de ahí, el número máximo de caminos buscados se limita por el número de billetes. Cuando un nodo intermedio en el camino desde la fuente al destino recibe un billete tiene que decidir a qué nodo(s) se debería de enviar el billete. Para hacer esto, el nodo usa la información de estado para guiar los paquetes limitados a lo largo de las mejores rutas. Se usa un protocolo de vector de distancia para recoger esta información de estado que consta de retardo extremo a extremo, ancho de banda y coste.

Ejemplos de algoritmos de programación libre de conflictos

En [6], Nelson y Kleinrock introdujeron el concepto de TDMA (STDMA) Espacial, donde los intervalos de tiempo (TS) se reutilizan espacialmente. Este trabajo se puede considerar como el padre de todos los otros algoritmos de programación con el propósito de proporcionar programaciones libres de conflictos. La idea es determinar los conjuntos de enlaces no interferentes (o no colisionantes). Esto supone una red estacionaria, y los conjuntos necesitan ser recalculados si la red cambia suficientemente. Esos conjuntos se seleccionan preferentemente tales que se permite a cada nodo en la red transmitir al menos una vez. A cada intervalo de tiempo en una trama TDMA se le asigna entonces un conjunto de enlaces (conjuntos de transmisión) que pueden transmitir sin interferir entre ellos. La misma programación se repite más tarde cada trama STDMA.

El(los) esquemas presentados en [8] y [9] se podrían ver como un descendiente directo de STDMA. En trabajos previos sobre STDMA, la conectividad del gráfico de la red se usa para... [Seguir leyendo]

1. Un método para la configuración de la conexión en una red de comunicación inalámbrica multisalto, dicho método que comprende los pasos de:

- determinar, para una conexión solicitada entre un nodo fuente y un nodo destino, un conjunto de parámetros de conexión que incluyen el camino, el canal y al menos un parámetro de enlace físico expandiendo un árbol dirigido con los caminos preliminares para la conexión pendiente originada en el nodo fuente y que realiza un procedimiento de búsqueda para encontrar al menos el coste Ki para cada nodo i, en un conjunto dado, desde el nodo fuente de acuerdo con el siguiente algoritmo anidado:

**(Ver fórmula)**

  KID Fuente = constante,

donde i ≠ ID Fuente, N(i) es el conjunto de vecinos actuales del nodo i que a su vez es un conjunto de todos los nodos Ω en la red, j es un nodo vecino que pertenece a N(i), m es un conjunto de al menos un canal en un conjunto de M canales ortogonales en total, Ψ es uno o una multitud de parámetros de capa física, ki (j, m, Ψ), también indicado kij (m, Ψ), es el coste desde el nodo j al nodo i, en el que el coste kij (m, Ψ) incluye la potencia de transmisión del enlace Pj(m) para el nodo j y el canal m como un parámetro de la capa física Ψ, y la potencia de transmisión del enlace Pj(m) está sujeta a restricciones que restringen la potencia de transmisión del enlace para un intervalo predeterminado, y el término K(j), también indicado Kj, es el coste acumulado desde el nodo fuente al nodo j, y KID Fuente es el coste inicial en el nodo fuente, en el que el nivel de anidamiento más interior de dicho algoritmo anidado sintoniza dicho(s) parámetro(s) de la capa física Ψ, el siguiente nivel de anidamiento es una elección de un conjunto de canal(es) m para cada vecino, y el tercer nivel de anidamiento proporciona una elección entre vecinos j, de ahí que elige el camino en la capa de encaminamiento; y

- establecer la conexión requerida en base al conjunto determinado de parámetros de conexión.

2. El método de acuerdo con la reivindicación 1, en el que dicho al menos un parámetro de enlace físico se selecciona a partir del grupo de:

- la potencia de transmisión;

- los parámetros de la antena adaptativa (AA);

- los parámetros de entrada múltiple salida múltiple (MIMO);

- los parámetros de modulación;

- el ancho de banda;

- la velocidad de transmisión de datos; y

- los parámetros de corrección de errores.

3. El método de acuerdo con la reivindicación 1, en el que un procedimiento de búsqueda local se ejecuta en cada nodo i para evaluar el coste kij (m, Ψ) desde el nodo j al nodo i para todos los nodos j en dicho conjunto N(i) de vecinos, y el menor coste Ki para cada nodo i desde el nodo fuente se determina en base a dicha evaluación junto con la información sobre Kj recibida desde cada nodo j.

4. El método de acuerdo con la reivindicación 1, en el que el coste kij (m, Ψ) incluye un canal que depende del parámetro de enlace físico Ψ(m).

5. El método de acuerdo con la reivindicación 1, en el que la potencia de transmisión del enlace máxima permitida y mínima requerida desde el nodo j se define como:

**(Ver fórmula)**

**(Ver fórmula)**

indican la potencia de transmisión y recepción preliminar, respectivamente, para el nodo r dentro del conjunto R que denota los nodos a lo largo del camino preliminar conectados al nodo j, Pv(m) y Cu(m) por otra parte indican la potencia de transmisión y recepción, respectivamente, para los nodos con tráfico establecido, γ M es un factor de mitigación, G(m) es una matriz de ganancia del canal respectivo, γ R es un factor de recepción, y W es un nivel de ruido que usa un factor γ W para asegurar que ese está generalmente limitado por la interferencia más que limitado por el ruido.

6. El método de acuerdo con la reivindicación 1, en el que la potencia de transmisión del enlace máximo permitido y mínimo requerido desde el nodo j se definen como:

**(Ver fórmula)**

**(Ver fórmula)**

indican la potencia de transmisión y recepción estimada (o más bien preliminar), respectivamente, para el nodo r dentro del conjunto R que indica que los nodos a lo largo del camino preliminar 15 conectados al nodo j, Pv(m) y Cu(m) por otra parte indican la potencia de transmisión y recepción, respectivamente, para los nodos con tráfico establecido, G(m) es una matriz de ganancia del canal respectivo, ΓM es un umbral de la CIR (Relación Portadora a Interferencia), que supone que cada parte del receptor de un enlace existente o camino

**(Ver fórmula)**

preliminar experimenta el nivel de interferencia J(m), es la interferencia esperada en el nodo x desde los nodos a lo largo del camino preliminar, γ R es un factor de recepción, W es un nivel de ruido que usa un factor γ W

20 para asegurar que ese está generalmente limitado por la interferencia más que limitado por el ruido.

7. El método de acuerdo con la reivindicación 1, que además comprende el paso de determinar un camino más corto preliminar previo a dicho procedimiento de búsqueda, y seleccionar dicha región de búsqueda de nodos vecinos N(i) en base al conocimiento de dicho camino más corto preliminar.

25 8. El método de acuerdo con la reivindicación 1, en el que se despliega el encaminamiento bajo demanda, que tiene una Petición de Recursos (RREQ) que transporta el camino, el canal y los parámetros de enlace físico para una conexión preliminar solicitada y que tiene una Respuesta de Ruta (RREP) que confirma una conexión seleccionada a lo largo de un camino correspondiente.

30 9. El método de acuerdo con la reivindicación 1, en el que se despliega el encaminamiento bajo demanda, que tiene una Petición de Recursos (RREQ) que coteja la información en las conexiones existentes cuando dicha RREQ se envía a través de la red, y determinando, en un nodo destino, una nueva conexión que cumple un requerimiento de Calidad de Servicio (QoS) como contenida en dicha RREQ en base a dicha información cotejada.

35 10. Un sistema de control (110) para la configuración de la conexión en una red de comunicación inalámbrica multisalto, dicho sistema de control que comprende:

- medios (113) para determinar, para una conexión solicitada entre un nodo fuente y un nodo destino, un

40 conjunto de parámetros de conexión que incluyen el camino, el canal y al menos un parámetro de enlace físico expandiendo un árbol dirigido con los caminos preliminares para la conexión pendiente originada en el nodo fuente y que ejecuta un procedimiento de búsqueda para encontrar un menor coste Ki para cada nodo i,

45  KID Fuente = constante,

**(Ver fórmula)**



donde i ≠ ID Fuente, N(i) es un conjunto de vecinos actuales del nodo i que a su vez es un conjunto de todos los nodos Ω en la red, j es un nodo vecino que pertenece a N(i), m es un conjunto de al menos un canal en un conjunto de M canales ortogonales en total, Ψ es uno o una multitud de parámetros de capa física, ki (j, m, Ψ),5 también indicado kij (m, Ψ), es el coste desde el nodo j al nodo i, en el que el coste kij (m, Ψ) incluye la potencia de transmisión del enlace Pj(m) para el nodo j y el canal m como un parámetro de la capa física Ψ, y la potencia de transmisión del enlace Pj(m) está sujeta a restricciones que restringen la potencia de transmisión del enlace a un intervalo predeterminado, y el término K(j), también indicado Kj, es el coste acumulado desde el nodo fuente al nodo j, y KID Fuente es el coste inicial en el nodo fuente, en el que el nivel de anidamiento más interior de dicho algoritmo anidado sintoniza dicho(s) parámetro(s) de la capa física Ψ, el siguiente nivel de anidamiento es una elección de un conjunto de canal(es) m para cada vecino, y el tercer nivel de anidamiento proporciona una elección entre vecinos j, de ahí eligiendo el camino en la capa de encaminamiento; y

- los medios para establecer la conexión requerida en base al conjunto determinado de parámetros de 15 conexión.