ES2361301T3 - Encaminamiento de camino libre de colisión integrado en capas cruzadas. - Google Patents

Abstract

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.

Description

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 decidir si se produce interferencia. Tal planteamiento no captura la interferencia total en la red. En su lugar, en el(los) esquema(s) de [8] y [9], la generación de programas STDMA se basa en el valor de la SIR para cada enlace.

STDMA y sus descendientes se diseñan más o menos para el cálculo centralizado o fuera de línea de los conjuntos de transmisión. En redes ad hoc, este no es un planteamiento sensato.

Un esquema de capa 2 particular, que asegura el funcionamiento distribuido y libre de colisiones, llamado Topología Libre de Colisiones Dependiente de la Programación de Acceso al Canal o CTMA se presenta en breve en [7].

Esquemas de encaminamiento y acceso al canal “integrados”

Los algoritmos de encaminamiento de la QoS “integrados” se basan en la suposición de que la red ad hoc se puede modelar como un gráfico, y todos ellos son protocolos bajo demanda, es decir la búsqueda de la ruta se hace solamente después de que ha sido solicitada una ruta desde un protocolo de capa más alta. Adicionalmente, los algoritmos de encaminamiento de la QoS integrados generalmente suponen TDMA, potencia de transmisión fija y antenas omnidireccionales. En un gráfico, dos nodos se llaman vecinos si son capaces de comunicar el uno con el otro y esto se representa conectando los dos nodos con un enlace en el modelo gráfico. Dos nodos están conectados si la distancia entre ellos no excede de algún valor predeterminado; es decir los paquetes se reciben sin error en ausencia de interferencia externa desde otros nodos. También se supone que solamente los vecinos están interfiriendo los unos con los otros. En una red de radio de paquetes multisalto modelada con gráficos, las transmisiones se modelan a menudo para interferir de dos formas, de ahora en adelante conocidas como interferencia primaria e interferencia secundaria. La interferencia primaria sucede cuando el nodo se supone que hace más de una cosa en un intervalo de tiempo único, por ejemplo transmitir y recibir en el mismo intervalo de tiempo. La interferencia secundaria sucede cuando un receptor R sintonizado a un transmisor particular T está dentro del alcance de otro transmisor cuya transmisión, aunque no destinada a R, interfiere con la transmisión de T a

R. Cuando se usa un modelo gráfico, es suficiente impedir transmitir a todos los vecinos de R en el mismo intervalo de tiempo que T para evitar la interferencia secundaria. Cuando se describen varios protocolos de encaminamiento de la QoS integrados más adelante, se han clasificado de acuerdo con qué nivel de interferencia están considerando

- el canal libre de interferencia, solamente considerada la interferencia primaria y consideradas tanto la interferencia primaria como secundaria, dado que esto afecta sumamente la forma que se diseña el protocolo.

La mayoría de los protocolos ad hoc existentes solamente se refieren a la existencia una ruta de camino más corto entre dos nodos en la red ad hoc sin garantizar su calidad. Como se describió previamente, el propósito para los protocolos de encaminamiento de la QoS ad hoc es configurar un canal/camino desde un nodo fuente a un destino que cumpla algunos requerimientos con respecto al ancho de banda y/o el retardo para ser capaz de soportar comunicación multimedia en tiempo real. Para hacer esto, los protocolos de encaminamiento de la QoS integrados convencionales normalmente consideran el ancho de banda en un enlace cuando se busca una ruta desde la fuente al destino. El requerimiento de ancho de banda se realiza entonces reservando intervalos de tiempo en los enlaces en el camino. La principal ventaja de este planteamiento, cuando se compara con los protocolos de encaminamiento ad hoc ordinarios, es que se pueden cumplir los requerimientos de la QoS. Comparado con los protocolos de encaminamiento de la QoS completamente separados, esto supone que el aprovisionamiento de la QoS se puede lograr con una mejor utilización de la red.

Para calcular el ancho de banda disponible en este entorno, es incorrecto calcular simplemente el ancho de banda mínimo de los enlaces a lo largo del camino como se hace en redes cableadas. La causa de esto es que el ancho de banda disponible se comparte entre los nodos colindantes. Un ejemplo simple de esto es el siguiente donde solamente se considera la interferencia primaria: Supongamos que el nodo A quiere comunicar con el nodo C a través del nodo B. Los intervalos libres disponibles para A comunicar con B son 1, 2, 3 y 4 y lo mismo se mantiene para el enlace desde B a C. Si ésta hubiera sido una red cableada (o un canal libre de interferencias) la capacidad disponible habría sido de 4 intervalos, mientras que en este caso la capacidad es de 2 intervalos. La razón para esto es que la intersección de los intervalos libres comunes en los enlaces A a B y B a C no es un conjunto vacío y un nodo no es capaz tanto de transmitir como de recibir en el mismo intervalo. Además, suponemos que los intervalos libres disponibles para comunicar desde A a B y de B a C son 1, 2, 3 y 4 así como 3 y 4 respectivamente. Si los intervalos 1 y 2 se reservan para la comunicación desde A a B y los intervalos 3 y 4 para la comunicación desde B a C, el ancho de banda disponible desde A a C es 2. Por otra parte si los intervalos 3 y 4 se reservan para la comunicación desde A a B supondrá que no puede tener lugar ninguna comunicación desde B a C y el ancho de banda disponible desde A a C habría sido 0 en este caso. Los protocolos que son capaces de identificar este problema y resolverlo se dirá que son capaces de realizar programación óptima de aquí en adelante. Hay dos problemas implicados en este proceso de cálculo del ancho de banda del camino. El primer problema es cómo la estación B (aquí se supone que B es responsable de reservar capacidad en el enlace desde A a B) conoce el conjunto de intervalos libres comunes de dos enlaces adyacentes, y el segundo problema es cómo compartir esta información con sus vecinos. Para resolver estos problemas, la estación tiene que intercambiar algunos mensajes entre ellas.

Canal Libre de Interferencias

La referencia [16] describe un protocolo de encaminamiento de la QoS multicamino que se basa en el planteamiento basado en billetes presentado en [4]. La expresión “multicamino” se refiere al caso donde la capacidad reservada desde la fuente al destino se puede dividir en varios subcaminos, cada uno que sirve a parte de la capacidad requerida original. No obstante, este trabajo está suponiendo bastante un modelo ideal en el que el ancho de banda de un enlace se puede determinar independientemente de sus enlaces colindantes. Para soportar esta suposición, se supone que cada ordenador central tiene múltiples transceptores que pueden trabajar independientemente uno del otro y que a cada enlace se le asigna un código que es distinto de aquellos códigos usados por sus vecinos de dos saltos para evitar la colisión. Un vecino de dos saltos es un vecino de un vecino – en el ejemplo anterior A y C son vecinos de dos saltos.

Considerada Solamente la Interferencia Primaria

Una suposición menos estricta que el canal libre de interferencias se hace en [12], [13] y [15], donde se supone un modelo de canal CDMA sobre TDMA, que implica que el uso de un intervalo de tiempo en un enlace es dependiente solamente del estado de sus enlaces colindantes (es decir solamente consideran la interferencia primaria). El enfoque en estas tres referencias es el cálculo del ancho de banda disponible en el camino desde la fuente al destino pero difiere la forma en que se recoge la información requerida.

El funcionamiento general de [12] y [13] se describirá ahora brevemente. Al recibir una RREQ (Petición de Recursos) se calcula el ancho de banda desde la fuente a este nodo. El ancho de banda se puede calcular de una forma óptima dado que la información se intercambia con sus vecinos sobre los intervalos libres disponibles previos al cálculo del ancho de banda disponible y que el mensaje RREQ incluye los intervalos usados para el enlace previo en el camino desde el nodo a la fuente. La RREQ se cae si el resultado no satisface el requerimiento de QoS. Como es de esperar el destino recibirá más de una RREQ cada una indicando un camino factible único desde la fuente al destino. El destino elegirá uno de los caminos y expedirá un mensaje RREP (Respuesta de Ruta). Como el mensaje RREP atraviesa de vuelta a la fuente, cada nodo a lo largo del camino reserva esos intervalos libres que se calcularon por adelantado.

En [5], se presenta un protocolo para el encaminamiento de la QoS en una red IEEE 802.11 que utiliza los algoritmos de cálculo de ancho de banda descritos anteriormente.

En [15], en lugar de calcular el ancho de banda disponible salto a salto, cada paquete RREQ graba toda la información del estado del enlace de la fuente al destino. De esta forma el destino es capaz de calcular el mejor camino desde la fuente al destino y expide un mensaje RREP a lo largo del camino elegido. Una opción para el encaminamiento multitrayecto se presenta también en la referencia y se logra fácilmente dado que el destino tiene toda la información de todos los caminos disponibles desde la fuente al destino. El algoritmo propuesto en [15] apunta a una red de flujos; es decir soporta múltiples flujos distintos. Es la tarea del nodo destino determinar la red de flujos desde la fuente que cumple el requerimiento de ancho de banda. Aunque tal solución tiene el potencial de proporcionar un cierre a la ruta óptima, siendo omitida la interferencia, también pone inmensa carga de cálculo en el nodo destino.

Considerada tanto la Interferencia Primaria como Secundaria

Basada en Grupos

En las redes basadas en grupos descritas en [10], [11], [14] y [18], un nodo podría ser una cabeza del grupo, una pasarela o solo un nodo usual. Una vez que se elige un nodo como una cabeza del grupo, todos sus vecinos pertenecen al mismo grupo. Un nodo que pertenece a dos o más grupos juega el papel de una pasarela. Se usa CDMA para dividir el grupo asignando distintas secuencias de código a distintos grupos, y TDMA se fuerza dentro de un grupo. Haciéndolo así demandan que la interferencia secundaria solamente tenga que ser considerada dentro del grupo, dado que se supone que la interferencia entremedias de los grupos es insignificante. Para esparcir la información de los intervalos disponibles dentro del grupo cada nodo transmite periódicamente un mensaje de “intervalo libre” que contiene su estado de reserva de intervalo. Dado que la cabeza del grupo puede oír a todos los otros nodos en el grupo, tiene conocimiento completo del estado de reserva en el grupo. Dado que la cabeza del grupo, como todos los nodos en el grupo, está obligada a transmitir el mensaje de “intervalo libre” todos los nodos conocerán en definitiva la reserva de intervalos dentro del grupo entero. Esto hace simple el cálculo del ancho de banda disponible. La señalización y el cálculo del ancho de banda disponible se llevan a cabo entonces independientemente en cada nodo de una forma salto a salto.

El esquema propuesto en [18] no es realmente un planteamiento integrado. En su lugar, se propone un esquema jerárquico – la primera asignación de capacidad se hace tanto en a nivel de nodo (enlace) como a nivel de flujo (en ambos de estos pasos se supone encaminamiento fijo), entonces se usa una versión distribuida del algoritmo Bellman-Ford para la selección de la ruta final. Se supone que todos los intervalos asignados del nodo se asignan a la parte adecuada de la trama temporal mediante algún mecanismo, pero la capa MAC no se considera. Además, se requiere que una entidad central recoja toda la información, realice los cálculos y a continuación distribuya el resultado final, es decir es un planteamiento centralizado.

En las referencias [17] y [19] mencionadas más adelante, se supone una estructura TDMA/espaciada ordinaria y de ahí que los protocolos tendrán que considerar tanto la interferencia primaria como la secundaria con respecto a todos los nodos en la red.

Liao

El esquema presentado en [17] requiere que un nodo primero de todo tenga que conocer el gráfico parcial de su propia ubicación (esto supone que un nodo tiene que conocer cómo se interconectan sus vecinos y los vecinos de los vecinos (normalmente conocidos como vecinos de 2 saltos). Además, un nodo también tiene que tener conocimiento completo de los intervalos en los que los vecinos están recibiendo y transmitiendo (señalar, no es bastante conocer si el nodo está ocupado o no). Esto también se mantiene para sus vecinos de 2 saltos. Para crear estas estructuras de datos, un ordenador central necesita difundir periódicamente esta información a sus vecinos y estos tienen que redifundir ésta a sus vecinos. Con esta información es posible realizar el encaminamiento y la asignación de intervalos. La regla es (como en la mayoría de otros documentos) que un intervalo se puede asignar solamente si los dos nodos indican comúnmente un intervalo como libre y que el nodo de envío no interfiere con ninguno de sus vecinos. Señalar que este esquema no es capaz de calcular el ancho de banda del camino óptimo.

Zhu

El esquema presentado en [19] se parece a alguno de los planteamientos que consideran solamente la interferencia primaria, pero no es capaz de calcular óptimamente el ancho de banda disponible. Nada se dice sobre cómo sabe un nodo en qué intervalos se permiten enviar con respecto a la interferencia secundaria con otros nodos no en el camino desde la fuente al destino. Se fija meramente que es el trabajo del protocolo de asignación de intervalos subyacentes en la capa MAC determinar cómo negocian los nodos entre ellos para asegurar que los intervalos se asignan a los transmisores correspondientes y se respetan por sus vecinos.

Soluciones adicionales del estado de la técnica

En [20], se construye un modelo gráfico suponiendo que se conectan dos nodos si la distancia entre ellos no excede de algún valor predeterminado, es decir los paquetes se reciben sin error en ausencia de interferencia externa desde otros nodos. Se usa un modelo relativamente realista sobre la interferencia secundaria. Dos o más estaciones pueden transmitir en el mismo intervalo de tiempo estipulado que la Relación Señal a Interferencia (SIR) en todos los nodos de recepción está por encima de un cierto umbral. La decisión de encaminamiento se basa en mínimas conexiones de salto entre las parejas fuente-destino. Dada una topología de red (representada por el modelo gráfico) el número de saltos y caminos posibles se puede encontrar difundiendo un paquete a través de la red y contando el número de nodos visitados. Cuando múltiples caminos con igual número de saltos entre la fuente y el destino se encuentran las asignaciones de intervalos previos y la carga de tráfico relativa se usan como criterios de decisión, para consumar el balanceo de carga en la red. Haciéndolo así la congestión es menos probable y el flujo de datos se puede aumentar. En resumen, se puede describir el algoritmo que sigue cinco pasos de la siguiente manera. En el primer paso, se usa el modelo gráfico para deducir la topología de la red. A continuación, se usa una decisión de encaminamiento para producir tráfico balanceado entre enlaces teniendo en cuenta la capacidad disponible. Dado que se requiere capacidad para cada enlace para esta decisión de encaminamiento, se considera la capacidad del enlace igual en este paso. En el tercer paso, cualquier algoritmo de programación libre de conflictos, tal como por ejemplo [8], se puede usar para generar el programa. Después de esto, se toma de nuevo la decisión de encaminamiento (cuarto paso), pero esta vez en base a la capacidad real dada por el programa. En el paso final, se elige la decisión de encaminamiento (paso dos o cuatro) que produce el flujo de datos máximo para la red entera. La referencia [20] se basa realmente en encaminamiento secuencial y de esta manera separado y programación/reserva. Se debería apuntar también que este esquema requiere un camino centralizado y la determinación de asignación de recursos.

Las referencias [21-22] no se relacionan con el tema de encaminamiento en la capa de red, sino más bien conciernen a la comunicación inalámbrica adaptativa, con los parámetros en la capa física y la capa MAC que se modifican adaptativamente por un controlador de estación base.

El artículo Encaminamiento de Control de Potencia para la Red Ad-hoc Inalámbrica Multisalto por K. Tsudaka y otros describe un planteamiento para controlar la potencia de transmisión para mejorar el rendimiento de los protocolos de encaminamiento.

Problemas asociados con las soluciones del estado de la técnica

Los esquemas de encaminamiento y de acceso separado al canal están generalmente lejos del óptimo. La razón es simplemente que el problema de la asignación de rutas y recursos del canal se ha subdividido en dos problemas más simples. Además, los esquemas separados a menudo suponen determinación centralizada y fuera de línea del camino y las asignaciones de los recursos. Esto supone que son relativamente pobres al manejar la movilidad, ya que la información se debe recoger, procesar y diseminar los resultados consecutivos a los nodos implicados.

Aunque se han presentado varias buenas ideas para alguna forma de encaminamiento y acceso al canal “integrado”, aspectos importantes de radio se descuidan completamente. Por lo tanto, se puede cuestionar la utilidad de los algoritmos. Por ejemplo, una suposición excesivamente simplista de que los nodos usan códigos ortogonales de manera que ningún nodo de transmisión interfiere con ningún otro nodo de recepción es usada en varios de los documentos. Ello no es solo incorrecto, ya que en la práctica los códigos no son perfectamente ortogonales debido por ejemplo a la difusión del retardo y de ahí provocará interferencia perjudicial, sino que es también un uso ineficiente de valiosos recursos. La ortogonalidad de las señales es un resultado de una expansión del ancho de banda (BW), y el ancho de banda se podría usar probablemente mejor a través de enviar los datos a velocidades más altas. El procedimiento de asignación de recursos y caminos propuesto en los esquemas convencionales de encaminamiento y de acceso al canal “integrado” también está muy simplificado y puede anunciar algunas veces rutas que no son factibles en la práctica.

SUMARIO DE LA INVENCIÓN

La presente invención supera estas y otras desventajas de las adaptaciones de la técnica previa.

Es un objeto general de la presente invención mejorar la utilización de los recursos disponibles en una red de comunicación.

También es un objeto de la invención proporcionar un mecanismo robusto y eficiente para el soporte de la QoS en redes de comunicaciones tales como las redes inalámbricas multisalto. A este respecto, es deseable explotar el potencial completo de la red, a la par que se asegura la calidad de servicio.

Otro objeto de la invención es proporcionar comunicación considerablemente libre de colisiones o no interferente para cada conexión individual, al menos en un subconjunto dado de la red.

Aún otro objeto de la invención es proporcionar un método mejorado y el sistema de control correspondiente para la configuración de la conexión en una red de comunicación tal como una red inalámbrica multisalto.

Todavía otro objeto de la invención es proporcionar un método mejorado y el sistema de control correspondiente para la determinación de una conexión en una red de comunicación tal como una red inalámbrica multisalto.

Es también otro objeto de la invención es proporcionar un método mejorado y el sistema de control correspondiente para el control de admisión de la conexión en una red de comunicación tal como una red inalámbrica multisalto.

Otro objeto de la invención es proporcionar una red de comunicación que tiene una pluralidad de nodos de red, al menos uno de los cuales incluye los medios para la determinación mejorada de una conexión.

También es un objeto de la invención encontrar formas de controlar la complejidad de cálculo implicada en la determinación de los parámetros de conexión adecuados.

La invención básicamente propone una integración de cruce de capas de las funciones en varias capas de protocolo de la red en un mecanismo unificado único por medio de la optimización integrada de una función objetivo única con respecto a los parámetros de conexión en al menos tres capas de protocolo.

Preferentemente, las capas de protocolo implicadas incluyen la capa de red, la capa de enlace y la capa física. Sin embargo se debería entender que se pueden usar otras capas de protocolo en la optimización integrada. También es posible usar más de tres capas de protocolo en la optimización, por ejemplo considerando los tres niveles más bajos en combinación con una aplicación adaptativa en la capa de aplicaciones. En efecto, el planteamiento unificado de la invención elimina parcialmente o completamente la necesidad de una representación por capas. En lugar de tener varios algoritmos de optimización separados ejecutándose más o menos independientemente en las distintas capas de protocolo, se realiza una optimización unificada única.

En una realización preferente de la invención, las funciones de la capa física, acceso al canal, encaminamiento y opcionalmente también control de admisión están integradas en un mecanismo unificado, único usando los parámetros de conexión que incluyen el camino, canal y uno o más parámetros de capa/enlace físico en la optimización integrada. En este caso, cada conexión se define consecuentemente por al menos un triplete que comprende un camino seleccionado, un canal seleccionado y uno o más parámetros de capa/enlace físico.

Para proporcionar comunicación libre de colisiones o no interferente, la optimización se somete a una o más restricciones diseñadas para asegurar la comunicación considerablemente sin colisiones con respecto a las conexiones existentes así como la conexión requerida.

Incorporando los parámetros de conexión de la capa física en la optimización integrada y realizando la optimización bajo una o más restricciones relacionadas con la interferencia, el tema de la interferencia se puede considerar cuidadosamente también en un planteamiento unificado para el aprovisionamiento de la QoS en redes tales como las redes inalámbricas multisalto. Esto supone que es posible determinar los parámetros de conexión que aseguran los enlaces considerablemente no interferentes, incluyendo también los enlaces de la conexión requerida.

En la práctica, la función objetivo puede incluir términos tales como la potencia de transmisión del enlace, el retardo, la carga local, la potencia de la batería y el margen del enlace. Los parámetros de la capa física típicamente definen el funcionamiento del enlace e incluyen uno o más parámetros de enlace físico tales como la potencia de transmisión, los parámetros de modulación, el ancho de banda, la velocidad de transmisión de datos, los parámetros de corrección de errores, y así sucesivamente. Otros parámetros de enlace físico incluyen los parámetros de configuración de entrada múltiple-salida múltiple (MIMO), antena adaptativa (AA) y otros de múltiples antenas, en el lado de transmisión, el lado de recepción o ambos.

Ventajosamente, la optimización integrada se realiza por medio de un algoritmo heurístico. Los parámetros de conexión pueden ser determinados por ejemplo en un procedimiento de búsqueda local. A este respecto, también ha resultado ser útil trabajar con un algoritmo anidado, en el que cada nivel de anidamiento representa una capa de protocolo de la red.

En una realización especial de la invención, el horizonte sobre el que actúa el algoritmo se hace seleccionable para proporcionar rendimiento óptimo para un nivel aceptable de complejidad de cálculo dado.

Además de una implementación centralizada, en la que una única unidad predefinida determina las conexiones bajo petición, también es posible distribuir el algoritmo de optimización a una pluralidad de nodos de red en la red, usando señalización de RREQ (Petición de Recursos) y RREP (Respuesta de Ruta) para la transferencia de la información requerida. En el escenario distribuido, para una petición de conexión dada, el algoritmo de optimización se puede ejecutar en los nodos de red relevantes de una forma nodo a nodo, o ejecutar enteramente en el nodo destino usando la información cotejada en una RREQ que se ha enviado a través de la red.

Las redes consideradas principalmente son redes inalámbricas (radio, ópticas, etc.) multisalto, pero la invención también se puede aplicar en otras redes tales como redes de acceso múltiple formadas como híbridas de tecnologías inalámbricas y cableadas.

Se debería entender que el término “canal” incluye intervalos de tiempo, bandas de frecuencia, códigos ortogonales,

o cualquier otro canal ortogonal o combinaciones de los mismos, incluso canales no espaciados.

En resumen, la presente invención concierne al aprovisionamiento de la QoS en redes de comunicaciones tales como las redes inalámbricas multisalto, pero también apunta al uso eficiente del medio inalámbrico a la par que asegura el uso de algoritmos de descubrimiento del camino de baja complejidad. Los algoritmos propuestos no se limitan al caso estacionario de un escenario de nodos fijos, sino que pueden manejar bajo ciertas circunstancias baja

o moderada movilidad.

La invención ofrece las siguientes ventajas:

-Alta utilización de la red;

-Eficiente aprovisionamiento y soporte de QoS, incluyendo retardo y flujo de datos garantizado;

-Comunicación considerablemente libre de colisiones;

-Baja complejidad de cálculo dados los aumentos de rendimiento y la complejidad combinatoria de la solución óptima;

-Control flexible de la complejidad de cálculo;

-

Reducido consumo de potencia, cuando la potencia de transmisión se usa en la función objetivo;

-

Reducido retardo extremo a extremo, cuando se usa el retardo en la función objetivo;

-Tanto las implementaciones distribuidas como centralizadas son factibles; y

-Permite la selección del camino más corto cercano o, a muy baja carga, real.

Otras ventajas ofrecidas por la presente invención se apreciarán en la lectura de la descripción posterior de las realizaciones de la invención.

BREVE DESCRIPCIÓN DE LOS DIBUJOS

La invención, junto con otros objetos y ventajas de la misma, se entenderá mejor con referencia a la siguiente descripción tomada junto con los dibujos adjuntos, en los que:

La Fig. 1 es un diagrama esquemático que ilustra los esquemas de encaminamiento y acceso al canal de acuerdo con la técnica previa; La Fig. 2 es un diagrama esquemático que ilustra el planteamiento unificado de acuerdo con la invención; La Fig. 3 es un diagrama esquemático de una red inalámbrica multisalto ejemplar; La Fig. 4 es un diagrama de flujo de la configuración, rechazo y desmontaje de la conexión; La Fig. 5 ilustra la notación usada para una configuración del camino de conexión preliminar en una red inalámbrica multisalto ejemplar; La Fig. 6 ilustra una configuración del camino de conexión preliminar en una red inalámbrica multisalto ejemplar para un canal y pareja de nodos específicos; Las Fig. 7-12 son diagramas esquemáticos que ilustran un ejemplo del funcionamiento de un mecanismo unificado inventivo para el aprovisionamiento de la QoS en una red dada; y La Fig. 13 es un diagrama esquemático que ilustra un gráfico de la CIR CDF resultante para todos los receptores activos correspondientes al ejemplo de la Fig. 12; y La Fig. 14 es un diagrama esquemático de un nodo de red en el cual se implementa un algoritmo CFPR de acuerdo con la invención; La Fig. 15 es un diagrama esquemático que ilustra un ejemplo de reserva del canal no espaciada.

DESCRIPCIÓN DETALLADA DE LAS REALIZACIONES DE LA INVENCIÓN

Para una mejor comprensión de la invención, se resumirá primero la técnica previa con respecto a los esquemas de encaminamiento y acceso al canal con referencia a la Fig. 1. En los esquemas convencionales para encaminamiento y acceso al canal, cada capa de protocolo se asocia generalmente con su propio algoritmo independiente A1, A2, A3. Algunas veces los datos de extracción se pueden enviar desde una capa más baja a una capa más alta para proporcionar alguna forma de integración de cruce de capas secuencial o “suave”. Los datos de extracción de la capa más baja simplemente se transfieren a la capa más alta para usar por el algoritmo de capa más alta, sin realimentación hacia la capa más baja para la adaptación. Por ejemplo, los datos de extracción que conciernen al ancho de banda del enlace se pueden transferir desde la capa de enlace, L2, al algoritmo de encaminamiento A3 en la capa de red L3. La información del ancho de banda se puede usar a continuación por el algoritmo de encaminamiento, el cual por ejemplo puede cambiar la asignación del camino si el ancho de banda es demasiado bajo. Este planteamiento de usar varios algoritmos independientes, cada uno que concierne a su propia función objetivo, representa una forma relativamente simple de integración de cruce de capas que solamente proporciona resultados subóptimos, si los caminos factibles se pueden producir en absoluto. Un análisis cuidadoso de los esquemas convencionales para el encaminamiento y el acceso al canal integrado también revela que todos funcionan solamente en dos capas de protocolo y que a menudo omiten completamente el tema de la interferencia y por lo tanto proporcionan rutas subóptimas y no explotan el pleno potencial de las redes.

Las referencias [23-25] son todas Publicaciones de Solicitudes de Patentes de U.S publicadas después de la fecha de presentación de la Solicitud de Patente Provisional U.S. Nº 60/358.370 en la que se basa la presente solicitud de patente.

La referencia [23] describe el encaminamiento para el interfuncionamiento ad hoc en base a las medidas de la calidad del enlace transferidas desde la capa de enlace.

La referencia [24] describe una red celular con la asignación de recursos de canal adaptativo basada en un criterio de mínima distorsión o mínima potencia, teniendo en cuenta las características de transmisión inalámbrica que varían con el tiempo.

La referencia [25] describe el uso de una unidad de extracción multimedia para la integración de la gestión de la capa de enlace con la gestión de la capa de red. Se modifican varios parámetros de transmisión en respuesta a los factores ambientales cambiantes, y esta modificación cambia el ancho de banda del enlace disponible, el cual a su vez se usa en la gestión del tráfico de la capa de red.

Las referencias [23-25] representan meramente distintas variantes de integración de cruce de capas “suave”, que implica como mucho a dos capas de protocolo a la vez con los datos de extracción que se transfieren desde una capa más baja a una capa más alta.

Como se ilustra esquemáticamente en la Fig. 2, la invención propone un algoritmo unificado para la optimización integrada de una función objetivo única con respecto a los parámetros de conexión en al menos tres capas de protocolo, incluyendo preferentemente las capas L1, L2, L3, proporcionando de esta manera un planteamiento verdaderamente integrado y unificado para el encaminamiento, la asignación de los canales y la adaptación de los parámetros del enlace físico. En lugar de tener algoritmos de optimización separados que se ejecutan más o menos independientemente, se realiza una optimización unificada única de acuerdo con la invención. Como se mencionó previamente, el planteamiento unificado de la invención puede eliminar realmente la necesidad de una representación de capas, aunque no hay nada que impida que otras funciones opcionales, representadas por las cajas de líneas discontinuas en la Fig. 2, todavía residan en la capa de red L3, la capa de enlace L2, y la capa física L1. Estas funciones pueden ser o no cooperantes con el algoritmo unificado de acuerdo con la invención.

La invención se describirá ahora con referencia a una red de comunicación particular, a saber una red inalámbrica (radio, óptica, etc.) multisalto. Sin embargo se debería entender que la invención no se limita a la misma, sino que también se puede aplicar en otras redes tales como redes de acceso múltiple formadas como híbridas de tecnologías inalámbricas y cableadas.

Principios básicos y descripción de la red

Como se mencionó anteriormente, la invención representa generalmente una integración de cruce de capas verdadera de las funciones en varias capas de protocolo en la red, que proporcionan de esta manera un planteamiento unificado para el aprovisionamiento de la QoS en una red multisalto. En el planteamiento unificado de acuerdo con la invención, las conexiones se determinan preferentemente por la optimización integrada de una función objetivo dada con respecto a los parámetros de conexión en al menos tres capas de protocolo dentro de la red.

Para una mejor compresión de la invención, será útil comenzar con una breve descripción de una red inalámbrica multisalto ejemplar. La Fig. 3 es un diagrama esquemático de una red inalámbrica multisalto ejemplar que ilustra algunos conceptos importantes. Se supone que tenemos una red que comprende múltiples nodos. La red funciona en un medio inalámbrico en el que las transmisiones pueden interferir potencialmente entre ellas. El tráfico enviado entre dos nodos en la red se llama flujo. El remitente de los datos en tal flujo se llama nodo fuente y el receptor se llama nodo destino. En cada instante, la red transporta cero, uno o una multitud de flujos de tráfico. Cada flujo se transporta en una conexión (también conocida como un circuito desde la conexión de redes clásica). Por simplicidad, solamente se muestra una única conexión en la Fig. 3. En la práctica, por supuesto, pueden existir varias conexiones simultáneas.

Se define una conexión desde un nodo fuente a un nodo destino mediante una serie de parámetros de conexión, que incluyen el camino, así como los parámetros del canal y los parámetros de la capa física a lo largo del camino. Puede haber varios caminos distintos desde la fuente al destino. Cada camino se monta por un conjunto de enlaces, y cada enlace entre dos nodos adyacentes i y j puede usar varios canales de comunicación distintos y ajustes de parámetros de enlace físico. Un camino se puede caracterizar por las identidades de los nodos.

Los parámetros de la capa física, también conocidos como parámetros de enlace físico, se pueden asociar con el lado de transmisión y/o el lado de recepción de cada nodo a lo largo del camino. Los parámetros del enlace físico para la transmisión pueden ser por ejemplo la potencia de transmisión, la modulación y así sucesivamente. Los parámetros del enlace para la recepción pueden incluir la sintonización de los grupos de antenas. La comunicación en canales separados se supone que es enteramente ortogonal y de ahí que no puede interferir entre ellos. El cambio de un canal a otro en un nodo de retransmisión se llama conmutación de canal. Una conexión típicamente tiene un límite superior de la velocidad de transmisión de datos, y un flujo puede usar una fracción de la velocidad de transmisión de datos disponible o el ancho de banda completo. Los nodos dentro del alcance entre ellos generalmente se dice que son vecinos. Obviamente, son posibles varias definiciones del término “dentro del alcance”. Preferentemente, la condición de estar dentro del alcance de un nodo es que la Relación Señal a Ruido (SNR) media en recepción exceda un nivel predeterminado cuando se usa la potencia máxima de transmisión permitida en la estación de envío y no existen estaciones interferentes.

5

15

25

35

45

Es deseable determinar los parámetros de conexión que son óptimos en algún sentido. Para ser capaces de hablar sobre optimalidad de una manera bien definida, se introduce una función objetivo f. En general, la función objetivo f se selecciona cuidadosamente y se hace dependiente de los parámetros de conexión tales como el camino, el canal y los parámetros de la capa física. Incluso aunque los parámetros de la capa/enlace físico normalmente forman parte de la función objetivo, otros factores de la capa/enlace no física, tales como la carga local o la batería restante, se podrían incorporar en la función objetivo. La función objetivo se optimiza entonces con respecto a los parámetros de conexión relevantes, determinando conjuntamente por ello los parámetros de conexión óptima para una conexión. El término parámetro se usa tanto para representar un parámetro variable como tal, como un valor del parámetro variable, como se entiende rápidamente por las personas expertas.

Cuando se formaliza la optimización, se pueden usar las siguientes notaciones:

Ω indica todos los nodos en la red (o la parte considerada de la red).

M indica el conjunto de canales ortogonales en total.

Ψ indica uno o una multitud de parámetros de la capa física, y de esta manera puede ser multidimensional con respecto a los parámetros de la capa física, cada parámetro variable como tal teniendo un espacio de definición en el que puede asumir valores continuos o discretos.

En la optimización la función objetivo f, que usa los parámetros de entrada de los conjuntos anteriores Ω, M, y Ψ, se obtienen los parámetros de conexión reales que definen la conexión, incluyendo el camino, el canal y los parámetros de la capa física:

R define los nodos reales entre la fuente y el destino:

imagen1

Su define el conjunto de canales que el nodo u utiliza para la transmisión:

imagen1

donde M(u) es el conjunto de canales óptimos para el nodo u, y el nodo u pertenece al camino R, excepto el nodo destino.

Tu,v define el conjunto de valores de los parámetros para el nodo u en el canal v, y puede incluir los parámetros de transmisión y/o recepción, excepto para el nodo fuente (solamente los parámetros de transmisión) y el nodo destino (solamente los parámetros de recepción):

imagen1

donde Ψ(u,v) es el conjunto óptimo de parámetros en el nodo u para el canal v, y v pertenece a M(u), y el nodo u pertenece al camino R.

El hecho de que una función objetivo única se optimice con respecto al camino, canal y los parámetros de la capa física realmente provoca una integración de cruce de capas verdadera de encaminamiento en la capa de red, la asignación del canal en la capa de enlace así como las funciones de la capa física en un mecanismo unificado único.

Cuando se somete a restricciones de diseño adecuadas, la optimización de cruce de capas propuesta por la invención provoca una red que tiene una o una multitud de conexiones asignadas de tal manera que se garantiza la comunicación considerablemente libre de colisiones para cada flujo individual. En realidad, la comunicación completamente libre de colisiones no es posible. No obstante, la inmunidad a colisiones se puede definir prácticamente como mantener cualquier medida relevante de rendimiento tal como la PER (Relación de Error de Paquetes), la CIR (Relación Portadora a Interferencia, supuesto que se incluye el ruido) o la SNR (Relación a Señal a Ruido) por debajo de ciertos valores objetivo o dentro de intervalos objetivo predeterminados. Por ejemplo, la comunicación libre de colisiones se puede definir como que se cumple en tanto en cuanto las pérdidas de los paquetes causadas por la interferencia y otros efectos radio perjudiciales se mantienen arbitrariamente pequeñas.

La solución óptima a tal integración de cruce de capas es muy compleja computacionalmente. Por ejemplo, solo la selección del camino y los canales en un esquema de acceso múltiple tal como TDMA o FDMA es bien conocido que es un problema denominado NP completo (el tiempo de ejecución no es polinomial, es decir a menudo se indica como exponencial, en el tamaño de la entrada). La incorporación de funciones adicionales tales como la optimización de parámetros del enlace físico complica el asunto incluso a peor.

La estrategia global es gestionar el aprovisionamiento de la QoS y el control de admisión de una forma por flujo, similar a la que se ha descrito para esquemas convencionales de encaminamiento integrado y acceso al canal. No obstante, también se tienen en cuenta aquí varios nuevos aspectos adicionales.

La estrategia general se describirá ahora con referencia al diagrama de flujo de la Fig. 4. Cuando el primer flujo se va a establecer en una red sobre una petición de configuración (S1), se debería seleccionar una conexión que es óptima en algún sentido. Preferentemente, esto implica seleccionar un camino, canal y un conjunto de parámetros físicos tales que la conexión está libre de colisiones (es decir no afectada por su propia transmisión) y optimiza una métrica predeterminada (S2). El control de admisión de la conexión se puede ejercer usando información sobre si se encuentra o no un camino factible (S3). Si se encuentra un camino factible, se establece la conexión (S4) y se envían los datos (S5). Para cada flujo adicional que se establece, se repite el procedimiento, pero también se asegura, con alta probabilidad, que la nueva conexión no causa colisiones para o experimenta colisiones desde las conexiones existentes. En el caso de que una conexión requerida no se pueda configurar debido a las restricciones a las que está sujeta la optimización, el flujo no se admitirá en la red (S6). La acción del usuario en tal caso no es el principal foco de la invención, pero podría implicar típicamente una configuración de la conexión reiniciada con requerimientos de QoS más bajos (es decir velocidad de transmisión de datos reducida si se soporta) o un aplazamiento de la configuración a un momento posterior cuando la carga de la red pueda ser más baja. Una alternativa adicional es que el destino puede haber sido capaz de deducir la información sobre la máxima QoS disponible durante la fase de configuración. Esta información se puede enviar entonces a la fuente para guiarla en una nueva configuración. Si se permite por la fuente, el destino también podría reservar un camino que no satisfaga plenamente los requerimientos de QoS óptimos.

Tras una petición de liberación de datos (S7), se termina el envío de datos (S8). Cuando se terminan los flujos, se liberan los recursos de red correspondientes y el medio inalámbrico (S9), dejando por ello espacio en el medio e incrementando la probabilidad de que se puedan establecer nuevas conexiones siempre que se necesiten.

En el proceso de determinación de una conexión, los parámetros de la capa física se seleccionan de esta manera preferentemente de manera que se puede mantener un margen suficiente para el funcionamiento fiable, a la par que se asegura que las conexiones existentes así como la parte preliminar de la nueva conexión no se interfieren. Preferentemente, los parámetros de la capa física son parámetros de la capa física, que seleccionan los parámetros de transmisión y/o recepción para cada enlace. De ahí, la adaptación de los parámetros de transmisión y/o recepción pueden afectar por lo tanto al camino tomado. Recíprocamente, el camino tomado afecta la adaptación de los parámetros de transmisión y recepción.

Se configura de esta manera una conexión bajo demanda siempre que se requiera, con todos los parámetros de conexión tales como {el camino, el canal, y los parámetros del enlace físico} que se seleccionan sabiamente para asegurar los enlaces no interferentes y no colisionantes, que incluyen la propia cadena de enlaces de la conexión preliminar. En otras palabras, en esta realización de la invención estamos tratando con la configuración de la conexión accionada por eventos con selección del camino, canal y parámetros del enlace.

También se pueden soportar varias velocidades de transmisión de datos en la red así como mecanismos que permiten el ajuste de las velocidades de transmisión de datos. Una ventaja importante es la utilización eficiente de los recursos, la cual se puede interpretar como probabilidad de bloqueo reducida para cualquier carga dada.

Dependiendo de la función objetivo seleccionada, la optimización puede ser una minimización o maximización. En una realización preferente de la invención, el objetivo general de la optimización es minimizar una función de coste objetivo.

Ventajosamente, la optimización se realiza por medio de un algoritmo heurístico, por ejemplo determinando los parámetros de la conexión en un procedimiento de búsqueda local. Más específicamente, el problema de la función objetivo se puede formular como un acoplamiento de las funciones objetivas específicas del nodo. También ha resultado ser útil trabajar con un algoritmo anidado.

La invención se describirá ahora con referencia a un ejemplo particular de un algoritmo de optimización anidado dirigido a minimizar el coste.

Ejemplo de algoritmo para la determinación del camino, el canal y los parámetros del enlace

La idea es abarcar un árbol dirigido con los caminos preliminares para la conexión pendiente originados en el nodo fuente. Una vez que se ha estabilizado el algoritmo, se selecciona la ruta que conecta el nodo fuente y destino. El algoritmo por lo tanto incluye un procedimiento de búsqueda para encontrar el menor coste Ki para cada nodo i, en un conjunto dado, desde el nodo fuente designado de acuerdo con el siguiente algoritmo, generalmente indicado algoritmo CFPR (Encaminamiento de Camino Libre de Colisión):

imagen1

KID Fuente = constante

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 uno o más canales en un conjunto de M canales ortogonales en total, Ψ es uno o una multitud de parámetros de la capa física, ki (j, m, Ψ) es el coste del nodo j al nodo i, y el término K(j) es el coste acumulado del nodo fuente al nodo j. El coste ki (j, m, Ψ) supone un valor para cada canal y alguno(s) parámetro(s) de los enlaces físicos. KID Fuente es el coste inicial en el nodo fuente y asume un valor constante que se ajusta típicamente a cero. El conjunto N(i) es un conjunto seleccionable de los vecinos actuales del nodo i, y no necesariamente tienen que incluir todos los vecinos

El conjunto m de canales puede incluir uno o más canales, dependiendo del ancho de banda requerido. Para conexiones de banda estrecha, puede ser suficiente con un único canal. Para conexiones de banda ancha, se pueden requerir varios canales.

Dado que es comúnmente aceptado escribir índices de los nodos, tales como i y j, como subíndices indicaremos simplemente ki (j, m, Ψ) como kji (m, Ψ) y K(j) como Kj. Con esta notación, el algoritmo CFPR, orientado a encontrar el menor coste Ki desde el nodo fuente, se puede resumir como sigue:

imagen1

KID Fuente = constante

Cada nivel de anidación en la ecuación representa aproximadamente una capa de protocolo. El argumento más interior sintoniza los parámetros de la capa física, tales como la potencia de transmisión. De ahí kji es típicamente un coste que depende del valor que asumen los parámetros de la capa física (Ψ), pero también se podrían incorporar otros factores de la capa no física. Tales factores podrían ser por ejemplo la carga local, o incluso la capacidad de batería restante. El siguiente nivel de selección es una elección del mejor conjunto de canal(es) (m) para cada vecino individual. Este representa el acceso al canal o nivel MAC. El tercer nivel proporciona una elección entre los vecinos, de ahí eligiendo un camino en la capa de encaminamiento.

En general, la optimización puede ser completamente centralizada a una unidad predefinida única, estipulado que la información requerida o bien se conoce o bien se puede recoger con la unidad de ejecución. No obstante, también es posible distribuir el algoritmo a una pluralidad de nodos de red, preferentemente todos los nodos de red dentro de la red multisalto. En el escenario distribuido, la implementación detallada depende de si está disponible la información completa o solamente la información local. En el último caso, el algoritmo se puede ejecutar en los nodos de red relevantes de una forma nodo a nodo, usando preferentemente señalización RREQ y RREP para el intercambio de la información requerida, como se describirá con más detalle más adelante. Por otra parte, si la información requerida se recoge en el camino al nodo destino, el algoritmo CFPR junto con un procedimiento de control de admisión correspondiente se puede ejecutar enteramente en el nodo destino en base a la información recogida.

El algoritmo CFPR definido anteriormente es particularmente adecuado para la implementación distribuida, en la que el algoritmo de optimización se distribuye a una pluralidad de nodos de red, y se ejecuta consecutivamente en los nodos de red implicados de una forma nodo a nodo. Esto generalmente supone que un procedimiento de búsqueda local se realice en cada nodo i para evaluar el coste kji (m, Ψ) desde el nodo j al nodo i para todos los nodos j en un conjunto seleccionado N(i) de vecinos, y se determina el menor coste Ki para cada nodo i desde el nodo fuente en base a esta evaluación junto con la información sobre Kj recibido desde cada nodo colindante j. El procedimiento de búsqueda continúa nodo por nodo hasta que se ha extendido el árbol entero de los nodos relevantes.

Señalar que el algoritmo CFPR muestra alguna similitud al algoritmo del camino más corto de Bellman Ford. No

5

10

15

20

25

30

35

40

45

50

obstante, allí existen varias diferencias. El algoritmo CFPR se generaliza a múltiples dimensiones (canales), proporciona una optimización integrada de los parámetros de la capa física, el canal y el camino, garantiza la inmunidad a colisiones y proporciona un cierre al camino más corto. En situaciones de baja carga, el camino tomado será normalmente el camino más corto real. La Fig. 5 intenta visualizar alguna terminología y notación usada en conexión con el algoritmo CFPR.

Ahora, cuando se configura un nuevo camino es deseable considerar los enlaces de las conexiones existentes y evitar interferir con aquéllos. Del mismo modo, también es deseable estar seguros de que los enlaces de las conexiones existentes no interfieren con los enlaces en la nueva conexión. Por lo tanto es útil dividir los nodos en cuatro conjuntos, centrados solamente en dos nodos en este momento, es decir el nodo i y j. Los primeros dos conjuntos son simplemente el nodo que se piensa recibir, es decir el nodo i y el nodo que se piensa transmitir, es decir el nodo j. Un tercer conjunto es un conjunto de vecinos del nodo j, N(j) pero excluido el nodo i. Los nodos dentro de este conjunto se indican u. El cuarto conjunto incluye los vecinos del nodo i, N(i) pero excluido el nodo j. Los nodos dentro de este conjunto se indican v. Típicamente, los conjuntos colindantes tienen aproximadamente el mismo conjunto de nodos.

Como se indicó anteriormente, se puede usar cualquier función de costes adecuada en la optimización, y el tipo de parámetro(s) de conexión física seleccionado(s) puede variar dependiendo del objetivo detallado de la optimización. No obstante, para una mejor comprensión, será ahora descrito un ejemplo ilustrativo de una optimización que implica parámetros del enlace físico.

Ejemplo de optimización que implica los parámetros de enlace físico tales como potencia de transmisión

De acuerdo con una realización preferente de la invención, la inmunidad a colisiones se asegura seleccionando la potencia de transmisión para el nodo j tal que se pueden conceder suficientes márgenes de recepción γ para los nodos implicados. Para la recepción en el nodo i, el nodo j debería usar una potencia de transmisión Pj(m) tal que la potencia de recepción resultante Ci(m) excede el nivel de interferencia, generado por los nodos v (alternativamente, los otros nodos en Ω también se pueden usar en los cálculos) dentro del conjunto N(i)\{j} y visto en el nodo i, con un factor de mitigación γ M. Del mismo modo, el nodo j debería usar una potencia de transmisión Pj(m) tal que es al menos un factor de recepción γ R menor que la potencia de recepción Cu(m) en cualquiera de los nodos u dentro del conjunto N(j)\{i}. Aquí, la matriz de ganancia del canal G(m) se supone conocida y con eso es posible relacionar las potencias de recepción y transmisión entre ellas. Además, el nivel de ruido W usa un factor γ W para asegurar que uno está generalmente limitado por la interferencia más que limitado por el ruido. Una condición adicional e importante que se debe cumplir es que el nodo j no interfiera con los enlaces a lo largo de su propia ruta preliminar hacia el nodo fuente. R indica el conjunto de nodos a lo largo de la ruta preliminar conectados al nodo j y r indexa los nodos con R. Por último, el nivel de ruido del receptor se supone que es W. La potencia de transmisión máxima permitida y mínima requerida desde el nodo j se puede definir ahora como:

imagen2

respectivamente para un nodo dentro del conjunto R. Pv(m) y Cu(m) por otra parte indican la potencia de transmisión y de recepción respectivamente para los nodos con tráfico establecido. Más tarde, cuando el algoritmo ha convergido, el camino preliminar que conecta la fuente y el destino se seleccionará y establecerá como un camino activo hasta que expire su validez. Todas las potencias de transmisión así como los niveles de potencia de recepción se actualizarán para reflejar la conexión nuevamente establecida. imagen1

Señalar aquí que la formulación de es tal que no garantiza que la CIR resultante en un nodo de enlaces de recepción existente no se deteriore por debajo de un cierto nivel de la CIR. En su lugar representa una simplificación en la que es poco probable que la CIR se degradase significativamente por debajo de imagen1 γ R, estipulado el

margen de mitigación γ M > margen de recepción γ R. La situación cuando

se selecciona tal que la CIR se garantiza que no se degrada por debajo de un nivel de la CIR deseado se describirá más tarde.

Como algunos canales no se usan para transmitir ni recibir, la formulación del algoritmo requiere que la potencia de transmisión se ajuste a 0 y la potencia de recepción a ∞. En la práctica, uno no necesita considerar tales canales cuando se realizan los cálculos del coste y consecuentemente puede saltarse los mismos.

5

10

15

20

25

30

35

40

45

50

55

Una métrica del coste razonable para kji es la potencia de transmisión del enlace. Tal métrica opta por minimizar la potencia de transmisión acumulativa usada sobre un camino entero. Esto es bueno para la reducción del consumo de la batería, pero también reduce el nivel de interferencia en el sistema dejando espacio para incorporar nuevas conexiones. De esta manera el sistema puede funcionar a una carga de red más alta. La métrica se selecciona como:

imagen1

donde imagen1 C es una constante seleccionada en el intervalo entre 0 y 1. Esto supone que imagen1 kjiimagen1 se restringe por

imagen1

y . Para C = 0, kji es igual a . Para C = 1, kji es igual a . La razón para ajustar el coste a ∞ es que el coste kji(m) solamente asumiría un valor útil cuando ello es factible.

Para la convergencia correcta y rápida, siempre que Ki = ∞, el nodo i descartará el camino preliminar que conduce desde la fuente y establecerá la potencia de transmisión relevante a 0 y la potencia de recepción relevante a ∞. Cualquier nodo que tiene el nodo i en su camino preliminar repetirá el procedimiento.

La Fig. 6 muestra un camino preliminar que sale desde el nodo 3 (el nodo fuente) en el ch 2 → nodo 6, conmutación de canal ch 2 → ch 3, nodo 6 en el ch 3 → nodo j. La situación mostrada refleja la prueba de si el nodo i y el nodo j pueden comunicar en el ch 1. Esto necesita un conmutador de canal ch 3 → ch 1 en el nodo j así como asegurar que el nodo j no interfiere por ejemplo con el nodo 1 y 2 en el ch 1. Del mismo modo, se asegura que el nodo j puede enviar con suficiente potencia para alcanzar el nodo i bajo interferencia desde el nodo 4 y 5 en el ch 1.

El procedimiento anterior se ejecuta hasta que los caminos y canales no cambian. Entonces, cuando se establece la nueva conexión, los datos pueden empezar a fluir. Después de algún tiempo cuando no hay necesidad de conexión, se elimina. Se puede soportar baja movilidad estipulado que los tiempos de vida de las conexiones son relativamente pequeños en relación con la movilidad del nodo y/o las variaciones del canal.

El algoritmo funciona incluso cuando no es posible el ajuste dinámico de la potencia. En este caso, la adaptación del enlace físico es una selección entre transmitir con una potencia de transmisión del enlace fija Pfij (ENCENDIDO) y no transmitir del todo (APAGADO). Preferentemente la potencia de transmisión del enlace se selecciona que sea Pfij en

tanto en cuanto Pfij está en el intervalo entre , de otro modo la potencia de transmisión del enlace se ajusta a cero.

Para asistir al lector en la comprensión de los conceptos básicos de la invención así como del algoritmo CFPR, se describirá ahora un ejemplo del funcionamiento del algoritmo CFPR con referencia a las Fig. 7-13, las cuales representan una red que tiene 36 nodos distribuidos sobre un área cuadrada y que usan 14 intervalos de tiempo (TS). Cada nodo se representa como un círculo sin relleno. El nodo fuente se indica por una estrella negra dentro del círculo mientras que el nodo destino se indica por una estrella gris. Cada nodo tiene un ID que se escribe justo a la derecha del nodo. Las conexiones entre nodos se muestran con enlaces en distintas escalas de grises, donde la escala de grises representa el número de TS. El número de TS se representa también dentro de paréntesis junto con el enlace, a medio camino entre los nodos que interconecta el enlace.

La Fig. 7 muestra un árbol originado en la fuente con el ID 5. Esta representa la fase de la configuración de la conexión de un primer flujo cuando el algoritmo CFPR ha generado las conexiones preliminares que constan de caminos, canales y parámetros del enlace adaptados. En esta particular implementación del algoritmo CFPR, el número de TS más bajo se elige siempre si allí existen intervalos de tiempo igual de buenos. Este es el por qué los números de intervalos se asignan en orden de número desde el nodo fuente.

La Fig. 8 muestra el camino seleccionado al nodo destino con el ID 31. De ahí, todos los otros caminos preliminares se han descartado excepto el óptimo CFPR entre la pareja fuente destino.

Cuando se va a establecer un segundo flujo y conexión, uno puede ver intuitivamente que los enlaces se seleccionan tal que no están interfiriendo perjudicialmente con la conexión existente y al revés. En la Fig. 9, el ID del nodo 7 es la fuente y el ID del nodo 30 es el destino.

Cuando se ha establecido la segunda conexión, se advierte que los TS 1, 13, 12, 2 y 3 han sido reutilizados. Además, se usan dos intervalos concurrentemente entre el nodo 22 y 23. La Fig. 10 ilustra los canales y los caminos resultantes para el primer y segundo flujo.

imagen3

Finalmente, el establecimiento de un tercer flujo y la conexión asociada se representa en las Fig. 11 y 12.

Se debería señalar que las Fig. 7-12 solamente muestran el establecimiento, pero no la liberación de las conexiones. No obstante, la última es trivial y por lo tanto se deja fuera.

En el ejemplo anterior, γ M = 8dB, γ R = 5dB y γ W = 8dB. La CIR CDF resultante para todos los receptores activos se muestra en la Fig. 13.

Aunque los túneles o recursos libres de colisiones desde la fuente al destino naturalmente hacen que uno piense en las conexiones de circuitos conmutados, se debería entender que también los circuitos virtuales pueden explotar estos recursos libres de colisiones. En este caso, la capacidad sobre un enlace generalmente se comparte entre múltiples conexiones. Esto requiere normalmente el uso de un programador en cada nodo para dar a cada conexión su capacidad negociada.

Asuntos adicionales/opcionales

Comentarios sobre los márgenes y el comportamiento del canal

En caso de línea de vista (LOS), como puede ser a menudo el caso en una red en lo alto de un tejado, el canal será relativamente estable. Por lo tanto, los distintos márgenes γ pueden ser relativamente pequeños. No obstante, cuando la fortaleza del canal fluctúa en una escala de tiempo más grande que la duración del paquete o la profundidad de interpolación, los márgenes γ se deberían seleccionar con suficiente margen para asegurar que la interferencia a la conexión existente o propia no causará mayores problemas.

Direccionalidad del coste

Señalar que se permite permutar el orden del índice i y j de kij en la ecuación dada, de manera que se considera el coste desde el nodo i al nodo j en lugar de al revés. De ahí, el coste desde el nodo fuente no se determina, sino más bien el coste hacia el nodo fuente. En este caso, el nodo fuente se puede apuntar más adecuadamente como el nodo destino. Como el algoritmo preferente es heurístico, no siempre proporciona un camino con la métrica de menor coste posible. Una forma de manejar esto es para determinar el camino dos veces – una vez con la fuente como el origen y una segunda vez con el destino como el origen. Uno entonces necesita usar una métrica que considera que el flujo se dirige desde la fuente hacia el destino:

imagen1

Complejidad

Para reducir la complejidad, se pueden adoptar una serie de medidas. Primero se debería seleccionar una cantidad razonable de vecinos N(i) para asegurar el grado razonable de conectividad de la red. Un valor de 6-10 vecinos debería ser suficiente. La región de búsqueda de un camino adecuado para la conexión se puede limitar. Una forma de consumar esto es buscar alguna distancia o saltos alrededor del camino más corto entre los nodos fuente y destino. Esto exige que sea establecido un camino más corto previo a la búsqueda y esos nodos en la vecindad del camino son informados de que pertenecen a la región de búsqueda. Señalar que también son posibles otras elecciones de regiones de búsqueda. Una restricción sensata en la región de búsqueda incluye la consideración de aquellos vecinos que están más cercanos a la fuente. Una forma de determinar que los nodos están más cercanos a la fuente es ejecutar un algoritmo ordinario de camino más corto como un primer paso antes de que se aplique el algoritmo CFPR. Si el algoritmo CFPR usa la potencia de transmisión como métrica, tiene sentido usar una métrica similar tal como la pérdida del camino acumulada desde la fuente. Como se indicó anteriormente, se pueden descartar muchos términos en los cálculos anteriores cuando suponen valores como 0 o ∞.

Creación de Rutas Sensatas

No todas las rutas que se generan por un algoritmo heurístico tienen que verse como sensatas. Por ejemplo, la necesidad de canales a cargas altas puede provocar un camino que va en una línea de zigzag grande. Hay al menos tres mecanismos que manejan esto en parte, si esto se considerase como un problema principal. Primero, explotando el control de carga, la reducción del canal será menos probable que ocurra. Esto a su vez proporciona rutas que son más cercanas a un camino más corto, estipulado que se usa la misma métrica como en el algoritmo CFPR. Un segundo método se proporciona limitando el alcance de la búsqueda de la ruta como se describe bajo la sección de complejidad anterior. Una forma de lograr esto es usando los vecinos con menos coste Bellman-Ford hacia la fuente.

5

10

15

20

25

30

35

40

45

50

55

Potencia de transmisión máxima permitida en base al límite de la CIR

Más que limitar la potencia de transmisión a un margen γ menor que la potencia recibida para cualquier parte receptora de un enlace existente, una condición alternativa es limitar la potencia de transmisión de manera que la CIR para cualquier parte receptora de un enlace existente no es menor que un umbral de la CIR ΓM. La potencia de transmisión máxima permitida es:

imagen1

donde cada parte receptora de un enlace existente o camino preliminar experimenta el nivel de interferencia I(m) e îx(m) es la interferencia esperada en el nodo x desde los nodos a lo largo del camino preliminar. Esto pone un límite más bajo en el nivel de la CIR experimentado. El resultado es que el tráfico se rechazará más que permitir que el nivel de la CIR de los enlaces existentes caiga por debajo del umbral de CIR ΓM.

Balanceo de la CIR

Cuando los niveles de potencia de transmisión se han determinado durante la optimización, puede ocurrir que, en la práctica, los niveles de la CIR reales se desvíen de todas formas de los niveles de la CIR deseada. Esto se puede compensar realizando un balanceo de la CIR convencional, tanto distribuido como centralizado, de los niveles de la potencia de transmisión en la red. En otras palabras, una vez que se ha configurado una nueva conexión, es posible balancear los niveles de transmisión para obtener los niveles de la CIR deseados (u otra medida de la QoS) en la red.

Alternativamente, en particular para el caso centralizado, el balanceo de la CIR se usa como un paso adicional de la fase de CAC. En caso de que el balanceo de la CIR falle, la conexión se rechaza. Señalar que la CIR CDF en la Fig. 13 será entonces una función del paso. La ventaja de este planteamiento particular es un rendimiento general mejorado.

Algoritmo extendido a un horizonte mayor

Como es posible que el funcionamiento básico de CFPR determine un canal que es inadecuado por así decir más abajo en la carretera, se describe aquí una extensión al algoritmo CFPR. Como ejemplo, suponemos que los canales 1+2, 1+2, 1 están libres para el nodo k, j e i respectivamente, k e i no son vecinos mientras que j es vecino tanto de k como de i. Si el nodo j seleccionase usar el canal 1 desde el nodo k porque tiene menor coste que el canal 2, eso provocaría que el nodo j e i no puedan crear un enlace. Obviamente, habría sido más inteligente asignar el canal 2 entre k y j, pero usando el canal 1 desde j a i.

La forma en que esto se maneja aquí es permitir al nodo i determinar las propiedades del enlace (por ejemplo el canal y los parámetros del enlace) desde k a j, restringido a que se pueda crear un enlace desde j a i. De ahí, el nodo i busca la combinación de coste más baja para dos enlaces al mismo tiempo. No obstante, incluso aunque se han determinado dos enlaces compatibles, solamente se mantiene el enlace más próximo a la fuente. En el paso sucesivo, otro nodo puede decidir usar el enlace entre el nodo j a i cuando busca la combinación del enlace más prometedora, pero descarta el enlace desde i a sí mismo. La excepción a esta regla de rechazar el enlace más lejano desde el nodo fuente es para la estación destino, la cual determina los dos últimos enlaces pero no descarta ninguno de los dos enlaces.

En el algoritmo CFPR básico, solamente se considera un enlace a la vez. En esta versión del algoritmo CFPR, uno más bien tiene en cuenta dos enlaces consecutivos a la vez. El concepto de horizonte se introduce aquí para indicar hasta qué punto funciona el algoritmo. El CFPR básico tiene el horizonte=1, mientras que la versión CFPR en esta sección tiene horizonte=2. El horizonte se puede extender a cualquier valor más grande, no obstante potencialmente con un aumento tremendo en la complejidad cuando están implicados muchos nodos y canales.

Soporte de velocidad de transmisión de datos más alta

Dado que distintas aplicaciones pueden tener distintos requerimientos en velocidad de transmisión de datos, es importante proporcionar algún soporte para las distintas velocidades de transmisión de datos. Se pueden utilizar dos métodos para variar el flujo de datos extremo a extremo. En el primer método, los márgenes γ R junto con γ M y γ W se seleccionan para soportar un modo de enlace comprendido de una velocidad de código y una constelación de señal. Se pueden manejar velocidades de transmisión distintas y simplificadas especificando distintos requerimientos de la CIR (solicitando una CIR que corresponde a una cierta velocidad de transmisión de datos). Típicamente la constelación de señal puede variar desde 2-BPSK a 64-QAM. Esto también se considera preferentemente en el ajuste condicional de la potencia de transmisión para Pmin y Pmax. En el segundo método, se establecen múltiples caminos y se usan conjuntamente para proporcionar la velocidad de transmisión de datos deseada. Las combinaciones de los dos métodos también se pueden usar.

Integración de la capa de aplicaciones

Como se mencionó previamente, es posible usar otras capas de protocolo así como más de tres capas de protocolo en la optimización. Por ejemplo, la capa de aplicaciones se puede incluir en la optimización, preferentemente en combinación con las tres capas de protocolo más bajas. Por ejemplo, la capa de aplicaciones puede alojar una aplicación adaptativa, capaz de funcionar bajo distintas velocidades de transmisión de datos pero con una calidad de aplicación asociada y compatible con la velocidad de transmisión de datos usada. Muchas aplicaciones basadas en vídeo y voz son buenos ejemplos de aplicaciones adaptativas que permiten múltiples velocidades de datos. Más concretamente, cuando se intenta una nueva configuración de conexión, se realiza la optimización de la función objetivo (o el algoritmo) con respecto a múltiples requerimientos de velocidad de transmisión de datos (dados por la capa de aplicaciones). Se pueden soportar por ejemplo varias velocidades de transmisión de datos, como se indicó previamente, usando una combinación de múltiples canales (por ejemplo múltiples intervalos de tiempo) entre los nodos, a través de la adaptación del enlace (varias combinaciones de la constelación de señal y las velocidades de codificación del error sin canal de retorno) o una combinación de ambas. En la optimización integrada de dichas cuatro funciones de capa, la factibilidad de una gama de velocidades de transmisión permisibles se evalúa bajo restricciones dadas. En una realización ejemplar de la invención, en cada paso de optimización, se elimina cualquier velocidad de transmisión de datos alta deseada pero no factible de los pasos de optimización adicionales.

La capa de aplicaciones se puede usar alternativamente en una optimización integrada junto con solamente dos de las tres capas de protocolo más bajas.

Algoritmo extendido para antenas adaptativas y MIMO

El algoritmo se puede extender para incorporar tanto comunicación MIMO como antenas adaptativas. Para el caso de antenas adaptativas, se seleccionan los parámetros de la capa física, tales como los pesos de las antenas en antenas de recepción y transmisión a la par que se minimiza la potencia de transmisión. Esta se limita a no perturbar el tráfico en curso y asegura que el receptor deseado tiene suficiente calidad (relación señal a interferencia y ruido).

Cuando se despliega una cantidad suficiente de antenas (en el grupo de antenas adaptativas) y se puede lograr elevada directividad, la interferencia dejará de ser el factor limitante para la red. En su lugar, son los recursos del canal los que limitarán la carga que se puede transportar por la red. En el caso extremo, es decir la interferencia se puede desatender enteramente, se adoptan otros criterios de optimización, intentando minimizar el número de saltos. También se pueden añadir restricciones para balancear los recursos libres en cada nodo, para aumentar la probabilidad de encontrar un camino libre en cada caso.

MIMO funciona de una manera similar seleccionando los parámetros del enlace incluyendo los pesos MIMO del transmisor y receptor. La selección de parámetros se limita a minimizar la potencia de transmisión del enlace mientras que también cumple un flujo de datos MIMO del enlace deseado.

Aspectos de implementación

En general, el algoritmo de optimización junto con el procedimiento de control de admisión de la conexión (CAC) correspondiente se puede implementar como componentes físicos, componentes lógicos, microprogramas o cualquier combinación adecuada de los mismos, usando por ejemplo tecnología de microprocesadores, procesamiento digital de la señal o tecnología ASIC (Circuitos Integrados de Aplicaciones Específicas). Por ejemplo, el algoritmo se puede implementar como programas informáticos para la ejecución por un sistema informático. Los programas informáticos se pueden escribir en casi cualquier tipo de lenguaje informático, tal como C, C++, Java o incluso lenguajes propietarios especializados. En efecto, en una implementación basada en programas informáticos, el algoritmo se asigna en un programa informático, que cuando se ejecuta por el sistema informático determina las conexiones y maneja el control de admisión. Preferentemente, no obstante, el algoritmo CFPR y el procedimiento CAC correspondiente se implementan más o menos en componentes físicos, usando ASIC u otra tecnología submicrónica de circuitos.

La Fig. 14 es un diagrama esquemático de un nodo de red en el cual se implementa un algoritmo CFPR de acuerdo con la invención. Solamente aquellos componentes del nodo de red que son relevantes para la invención se ilustran en la Fig. 14. El nodo de red 100 comprende un sistema de control 110 y una unidad de transmisión/recepción radio general 120 que tiene un módulo de procesamiento en banda base 121 así como un módulo de radiofrecuencia (RF)

122. El sistema de control 110 preferentemente comprende una unidad de control de admisión de la conexión (CAC) 112 y una unidad de encaminamiento 114, así como una base de datos 116 para mantener la información de la red. La unidad de encaminamiento 114 incluye la funcionalidad para encaminar el tráfico por medio de una tabla de encaminamiento 115. En esta realización particular, se implementa una unidad CFPR 113 en la unidad CAC 112 para determinar un conjunto de parámetros de conexión, si es posible. La unidad CFPR 113 recupera la información relevante sobre las conexiones existentes así como la propia cadena de enlaces de la conexión preliminar desde la base datos 116 y/o directamente desde la señalización de control entre nodos, y ejecuta un algoritmo CFPR con una función objetivo adecuada. La unidad CAC 112 se configura para tomar una decisión CAC basada en los resultados de la ejecución del algoritmo CFPR. Si se puede determinar el conjunto no factible de parámetros de conexión por la unidad CFPR 113 a la vista de los requerimientos de la QoS dados, la unidad CAC 112 rechaza la petición de configuración de la conexión. Por otra parte, si el algoritmo CFPR produce un conjunto de parámetros de conexión factibles, se establece la conexión requerida. Esto se consuma normalmente actualizando la tabla de encaminamiento 115 en la unidad de encaminamiento 116 con los nuevos parámetros de conexión, y enviando los parámetros de conexión a los nodos de red implicados usando “inundación”, envío del árbol de extensión, encaminamiento de la fuente o cualquier otro mecanismo convencional. Esto concierne en primer lugar a una implementación centralizada. A continuación, no obstante, se tratarán los aspectos de implementación que conciernen a una implementación distribuida.

Implementación bajo demanda de CFPR

CFPR se puede implementar de una manera distribuida. Esto se puede hacer utilizando el concepto de encaminamiento bajo demanda, como se mencionó previamente. Aunque el encaminamiento bajo demanda es conocido a partir de algunos esquemas del estado de la técnica, hay varias correcciones al planteamiento de encaminamiento bajo demanda tradicional.

El primer asunto es que cada RREQ (Petición de Recursos) en la red lleva no solo a una lista de nodos a lo largo de una ruta preliminar, sino también detalles específicos en las asignaciones de recursos. Por ejemplo, cada intervalo de recepción para una conexión preliminar se puede asociar con un nivel de potencia de recepción. En caso de que se use la potencia de transmisión máxima permitida basada en el límite de la CIR, también se puede incluir el nivel de interferencia y de ruido.

La razón para transportar esta información es asegurar que las asignaciones del intervalo y la potencia de transmisión no interfieran con los recursos asignados a lo largo de una conexión preliminar. Por consiguiente, los niveles de potencia de transmisión de los recursos en una conexión preliminar también se distribuyen con la RREQ. La razón para esto es que un nodo i debería ser capaz de determinar si cualquier nodo a lo largo de la conexión preliminar interferirá cuando el nodo i se está recibiendo.

La lista de la conexión preliminar (ID de los nodos) y la información asociada tal como los canales usados, la potencia de transmisión potencialmente usada, la potencia de recepción potencialmente experimentada (y la interferencia experimentada) se puede limitar a alguna longitud fija. Esta lista entonces actúa de una manera FIFO cuando la lista está llena. La razón para esto es que uno no quiere gastar los recursos enviando información inútil. Obviamente, un nodo en la lista preliminar será de baja importancia cuando está suficientemente lejos del nodo i, y no se perjudica por la interferencia desde el nodo i o el nodo de interferencia i.

Un campo para la métrica de coste, que no es simplemente una métrica de salto, también se transporta en la RREQ. Una métrica particular tratada anteriormente se basó en la potencia de transmisión, dando el nivel de la potencia de transmisión acumulada a lo largo de una ruta.

Cuando el nodo destino recibe la RREQ, selecciona un camino de menor coste de acuerdo con la ejecución distribuida del algoritmo CFPR y responde con una RREP que se retransmite a lo largo del camino seleccionado hacia atrás al nodo fuente. La RREP se envía preferentemente con potencia suficientemente alta en un canal que está esencialmente libre de colisiones en un área más grande tal que los nodos adyacentes oyen por casualidad la información RREP. Los nodos que oyen por casualidad la información RREP posteriormente actualizan sus bases de datos de asignación de recursos. Los detalles del protocolo para RREQ y RREP se conocen de la técnica previa y por lo tanto no se tratan más.

Cada mensaje de control tal como RREQ y RREP también incorpora la potencia de transmisión usada, tal que el nodo de recepción puede determinar las pérdidas del camino. Esto es factible, cuando el canal es más o menos recíproco en el sentido de la ganancia media del trayecto. En el caso no recíproco, se pueden explotar otros métodos bien conocidos para estimar la ganancia del trayecto.

Los esquemas de reducción de la complejidad descritos anteriormente se pueden usar en conjunto con la determinación de la ruta bajo demanda.

Finalmente, la RREQ puede indicar dependiendo del requerimiento de ancho de banda los márgenes deseados γR junto con γM y γW también, o el modo de enlace deseado o ambos. De igual manera, la RREP anuncia los parámetros de conexión relevantes tales como la potencia de transmisión, la potencia recibida, los márgenes deseados, los intervalos de tiempo relevantes (canales) y así sucesivamente.

Reducción de la complejidad del funcionamiento bajo demanda

La construcción de una completa estructura en árbol con múltiples caminos preliminares, incurre en procesamiento innecesario en última instancia, meramente se usará un camino. Esta sección sugiere otra versión de funcionamiento bajo demanda adecuado para mitigar el procesamiento innecesario de los caminos redundantes.

Supongamos que el nodo fuente tiene una idea aproximada de donde se puede encontrar el nodo destino. Esto se podría dar por ejemplo por un protocolo de camino más corto proactivo tal como DSDV que se actualiza de una forma lenta, siendo conocido a priori (es decir nodos fijos) o incluso bajo demanda. Una RREQ se puede enviar ahora hacia el destino a lo largo del camino más corto o a lo largo de una región que sigue el camino más corto. Al hacerlo así, la RREQ recoge la información del enlace de las conexiones existentes a lo largo del camino más corto. Esta información contiene la misma información requerida para el algoritmo CFPR para calcular una conexión más tarde, tal como los canales usados, la potencia de transmisión usada, la potencia de recepción experimentada y así sucesivamente. Cuando el nodo destino recibe la RREQ, procesa la información recogida por la RREQ a través del algoritmo CFPR y sus derivados. Señalar que la RREQ puede contener una petición de un ancho de banda que no se puede soportar por una conexión única. En ese caso, el nodo destino puede determinar múltiples conexiones para un flujo. Posteriormente, una (o más) RREP se envía(n) de vuelta para reservar los recursos. La RREP contendrá entonces los ID de los nodos, el canal que va a ser usado y los parámetros del enlace (por ejemplo la potencia de transmisión).

La ventaja con este planteamiento es que el cálculo se realiza solamente en el nodo destino y se limita la inundación de las RREQ. Como no se realiza el cálculo durante el envío de las RREQ, las RREQ se enviarán rápido a través de la red. Otra ventaja es que el nodo destino puede asegurar la inmunidad del bucle, ejecutar el algoritmo CFPR tanto hacia delante como hacia atrás (como se indica en conexión con la direccionalidad del coste), e implementar algoritmos arbitrarios (específicos del proveedor).

Una desventaja es que la información contenida en las RREQ puede llegar a ser muy grande para muchas rutas largas. Una forma de resolver este problema es incorporar puntos de terminación intermedios entre la fuente y el destino, por ejemplo cada nodo 20º o así.

Por supuesto, también se puede usar el planteamiento basado en árbol previamente descrito sobre una región limitada con un conjunto limitado de nodos.

Algoritmo extendido para acceso al canal no espaciado

El algoritmo CFPR se puede extender para incorporar técnicas de acceso al canal es decir que no dependen de dividir el medio en canales de tamaño igual con límites de canal predecibles. Ejemplos de tal esquema de acceso al canal es el protocolo 802.11 DCF. Señalar que el funcionamiento actual de DCF no permite asignar recursos repetitivamente en el futuro.

En este caso, el coste kij puede implicar retardo, posiblemente en combinación con la potencia de transmisión. Cada nodo intenta encontrar una ventana de transmisión entre o después de las transmisiones en curso para un paquete de tamaño predeterminado. La velocidad del enlace se puede adaptar para comprimir las transmisiones de paquetes de datos en el tiempo. Dado que se usa la máxima velocidad del enlace siempre que sea posible, la potencia de transmisión se puede adaptar (minimizar) a la par que se asegura que la recepción está un factor γ por encima de la interferencia más el ruido. La Fig. 15 ilustra cómo se usan varias velocidades de enlace en distintos enlaces. Esto provoca una duración distinta para enviar los paquetes, el denominado retardo de duración de la transmisión. Efectivamente, la ruta, el retardo de acceso al medio y los parámetros de la capa de enlace (tales como la velocidad del enlace y/o potencia de transmisión) se determinan de manera que la comunicación considerablemente no interferente con respecto a las conexiones existentes así como que se asegura la propia cadena de enlaces de la conexión preliminar.

Seleccionando adecuadamente el retardo de petición de transmisión, y la velocidad del enlace (que afecta al retardo de transporte) para cada nodo, es posible de esta manera minimizar el retardo de transporte extremo a extremo total desde la fuente al destino. Una vez que se usa el modo de enlace más rápido, la potencia de transmisión del enlace se puede reducir tanto como sea posible, mientras que todavía se cumple el requerimiento de la CIR para el modo de enlace. Esto supone realmente que tanto el retardo como la potencia de transmisión se pueden combinar en la función objetivo, preferentemente de una manera ponderada. Si es más importante minimizar el retardo (o la potencia de transmisión) en la red, el coeficiente de peso correspondiente simplemente se aumenta.

Las realizaciones descritas anteriormente se dan meramente como ejemplos, y se debería entender que la presente invención no está limitada a las mismas. Modificaciones, cambios y mejoras adicionales que conserven los principios básicos subyacentes revelados y reivindicados aquí dentro están dentro del alcance de la invención según se define por las reivindicaciones adjuntas.

REFERENCIAS

[1] S. Lee y A. T. Campbell, “INSIGNIA: Soporte de señalización en banda para QoS en redes ad hoc móviles”, en las Actas del 5º Taller Internacional de Comunicación Móvil Multimedia, 1999.

[2] C. Perkins, E. M. Royer y S. R. Das, “Encaminamiento del vector de distancia bajo demanda ad hoc”, en el Borrador de Internet, draft-ietf-manet-aodv-06.txt, julio de 2000

[3] D. Johnson y D. Maltz, “Encaminamiento dinámico de la fuente en redes inalámbricas ad hoc”, en Informática Móvil, Publ. Académica Kluwer, 1996.

[4] S. Chen y K. Nahrstedt, “Calidad de Servicio Distribuida en redes ad hoc”, JSAC del IEEE, SAC-17(8), 1999.

[5] C. R. Lin, “Transporte multimedia en redes inalámbricas multisalto”, en Actas de Comunicaciones del IEEE, vol. 145, Nº 5, octubre de 1998.

[6] R. Nelson y L. Kleinrock, “TDMA espacial: Un protocolo multisalto de acceso al canal libre de colisiones”, Trans. Comun. del IEEE, vol. COM-33, nº 9, páginas 934-944, septiembre de 1985.

[7] Lichun Bao y J.J. García-Luna-Aceves, “Topología Libre de Colisiones Dependiente de la Programación de Acceso al Canal”,

[8] Grönkvist, J., “TDMA Espacial Controlado por Tráfico en redes radio multisalto”, PIMRC 98, octubre de 1998.

[9] Grönkvist, J., “Métodos de Asignación para Reutilización de TDMA Espacial” MobiCom 00, Boston, MA, agosto de 2000.

[10] Y. -C. Hsu y T.-C. Tsai, “Encaminamiento de Ancho de Banda en Entorno Radio de Paquetes Multisalto”, en las Actas del 3º Taller Internacional de Informática Móvil, marzo de 1997.

[11] Y. -C. Hsu, T.-C. Tsai e Y. -D. Lin, “Encaminamiento de la QoS en Entorno Radio de Paquetes Multisalto”, en el Simposio Internacional sobre Comunicaciones Informáticas del IEEE, Atenas, Grecia, junio de 1998.

[12] C. -R. Lin y J. -S. Liu, “Encaminamiento de la QoS en Redes Inalámbricas ad hoc”, en JSAC del IEEE, SAC17(8), 1999.

[13] C. -R. Lin, “Encaminamiento de la QoS Bajo Demanda en Redes Móviles Multisalto”, en las Actas del INFOCOM del IEEE, 2001.

[14] T. -W. Chen, J. -T. Sai y M. Gerla, “Rendimiento de Encaminamiento de la QoS en Redes Inalámbricas Multimedia, Multisalto”, en las Actas de ICUPC del IEEE, 1997.

[15] Y. -S. Chen y otros, “Encaminamiento de la QoS Mutitrayecto, de Enlace de Estado, Bajo Demanda en una Red Ad Hoc Móvil Inalámbrica”, a aparecer en Inalámbrico Europeo del IEEE 2002; 26-28 de febrero, Florencia, Italia (disponible previamente en Internet).

[16] W. -H. Liao y otros, “Un Protocolo de Encaminamiento de la QoS Multitrayecto en una Red Ad Hoc Móvil Inalámbrica”, Conferencia Internacional sobre Conectividad de Redes (ICN) del IEEE, Vol. 2, páginas 158-167, 2001.

[17] W. -H. Liao, Y. -C. Tseng y K. -P. Shih, “Un Protocolo de Reserva de Ancho de Banda Basado en TDMA para Encaminamiento de la QoS en una Red Ad Hoc Móvil Inalámbrica”, a aparecer en ICC, 2002 (disponible previamente en Internet).

[18] A. Michail, “Encaminamiento y Programación de Algoritmos en Redes Multisalto Inalámbricas de Recursos limitados”, Tesis Doctoral, Universidad de Maryland, College Park, 2000.

[19] C. Zhu, “Control de Acceso al Medio y Encaminamiento de la Calidad de Servicio para Redes Ad Hoc Móviles”, Tesis Doctoral, Universidad de Maryland, College Park, 2001.

[20] M. Sánchez, J. Zander, “Reutilización de Encaminamiento Adaptativo para Redes Radio de Paquetes Multisalto”, distribuido a través del Programa de Cooperación Industrial organizado por el grupo de Sistemas de Comunicaciones Radio del Real Instituto de Tecnología KTH, Estocolmo.

[21] Solicitud de Patente Internacional con Nº de Publicación Internacional WO 02/05493 A2, 17 de enero de 2002.

[22] Solicitud de Patente Internacional con Nº de Publicación Internacional WO 01/50669 A1, 12 de julio de 2001.

[23] Publicación de la Solicitud de Patente de U.S. Nº US 2002/0049561 A1, 25 de abril de 2002.

[24] Publicación de la Solicitud de Patente de U.S. Nº US 2002/0054578 A1, 9 de mayo de 2002.

[25] Publicación de la Solicitud de Patente de U.S. Nº US 2002/0075869 A1, 20 de junio de 2002.

Claims (7)

1. REIVINDICACIONES

   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:

   imagen1

     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. 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. 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. 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. 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:

   imagen2

   imagen3

   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

   5 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. 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:

   10

   imagen2

   imagen3

   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 imagen2

   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. 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,

   imagen4

   

   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

   10 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.