Este artículo describe la optimización de Lyapunov para sistemas dinámicos . Ofrece una aplicación de ejemplo para un control óptimo en las redes de cola .
Introducción
La optimización de Lyapunov se refiere al uso de una función de Lyapunov para controlar de manera óptima un sistema dinámico. Las funciones de Lyapunov se utilizan ampliamente en la teoría de control para garantizar diferentes formas de estabilidad del sistema. El estado de un sistema en un momento particular a menudo se describe mediante un vector multidimensional. Una función de Lyapunov es una medida escalar no negativa de este estado multidimensional. Normalmente, la función se define para crecer cuando el sistema se mueve hacia estados indeseables. La estabilidad del sistema se logra tomando acciones de control que hacen que la función de Lyapunov se desvíe en la dirección negativa hacia cero.
La deriva de Lyapunov es fundamental para el estudio del control óptimo en las redes de cola. Un objetivo típico es estabilizar todas las colas de la red mientras se optimiza algún objetivo de rendimiento, como minimizar la energía promedio o maximizar el rendimiento promedio. Minimizar la deriva de una función de Lyapunov cuadrática conduce al algoritmo de enrutamiento de contrapresión para la estabilidad de la red, también llamado algoritmo de peso máximo . [1] [2] Agregar un término de penalización ponderado a la deriva de Lyapunov y minimizar la suma conduce al algoritmo de deriva más penalización para la estabilidad de la red conjunta y la minimización de penalizaciones. [3] [4] [5] El procedimiento de deriva más penalización también se puede utilizar para calcular soluciones para programas convexos y programas lineales . [6]
Deriva de Lyapunov para las redes de cola
Considere una red de colas que evoluciona en un tiempo discreto con intervalos de tiempo normalizados. Supongamos que hay colas en la red, y definir el vector de retrasos en la cola en el momento por:
Funciones cuadráticas de Lyapunov
Para cada ranura definir:
Esta función es una medida escalar de la acumulación total de colas en la red. Se llama función de Lyapunov cuadrática en el estado de la cola. Defina la deriva de Lyapunov como el cambio en esta función de una ranura a la siguiente:
Limitando la deriva de Lyapunov
Suponga que los atrasos de la cola cambian con el tiempo de acuerdo con la siguiente ecuación:
dónde y ¿Hay llegadas y oportunidades de servicio, respectivamente, en cola? en la ranura Esta ecuación se puede utilizar para calcular un límite en la deriva de Lyapunov para cualquier intervalo t:
Reordenando esta desigualdad, sumando todo y dividir por 2 conduce a:
dónde:
Suponga que los segundos momentos de llegadas y servicio en cada cola están limitados, de modo que hay una constante finita tal que para todos y todos los posibles vectores de cola la siguiente propiedad tiene:
Tomar expectativas condicionales de (Ec. 1) conduce al siguiente límite en la deriva de Lyapunov esperada condicional :
Un teorema básico de la deriva de Lyapunov
En muchos casos, la red se puede controlar para que la diferencia entre llegadas y servicio en cada cola satisfaga la siguiente propiedad para algún número real :
Si lo anterior es válido para el mismo épsilon para todas las colas todas las ranuras y todos los vectores posibles entonces (Ec. 2) se reduce a la condición de deriva usada en el siguiente teorema de deriva de Lyapunov. El teorema siguiente puede verse como una variación del teorema de Foster para cadenas de Markov . Sin embargo, no requiere una estructura de cadena de Markov.
- Teorema (deriva de Lyapunov). [5] [7] Supongamos que hay constantes tal que para todos y todos los vectores posibles la deriva condicional de Lyapunov satisface:
- Entonces para todas las tragamonedas el tamaño medio de la cola en el tiempo en la red satisface:
Prueba. Tomando las expectativas de ambos lados de la desigualdad de deriva y usando la ley de expectativas iteradas se obtiene:
Sumando la expresión anterior sobre y usando la ley de las sumas telescópicas se obtiene:
Usando el hecho de que no es negativo y reorganizar los términos en la expresión anterior demuestra el resultado.
Optimización de Lyapunov para redes de cola
Considere la misma red de colas que en la sección anterior. Ahora definecomo una penalización de red incurrida en la ranura Suponga que el objetivo es estabilizar la red de colas mientras se minimiza el tiempo promedio de Por ejemplo, para estabilizar la red mientras se minimiza la energía promedio en el tiempo, se puede definir como la potencia total contraída por la red en la ranura t. [8] Para tratar problemas de maximizar el tiempo promedio de alguna recompensa deseable. la pena se puede definir Esto es útil para maximizar la utilidad de rendimiento de la red sujeto a la estabilidad. [3]
Para estabilizar la red minimizando el tiempo promedio de la penalización Los algoritmos de red se pueden diseñar para realizar acciones de control que minimicen codiciosamente un límite en la siguiente expresión de deriva más penalización en cada ranura.: [5]
dónde es una ponderación no negativa que se elige según se desee para afectar una compensación de rendimiento. Una característica clave de este enfoque es que normalmente no requiere conocimiento de las probabilidades de los eventos aleatorios de la red (como llegadas de trabajos aleatorios o realizaciones de canales). Elegirse reduce a minimizar un límite en la deriva en cada ranura y, para el enrutamiento en redes de colas de múltiples saltos, se reduce al algoritmo de enrutamiento de contrapresión desarrollado por Tassiulas y Ephremides. [1] [2] Usando y definiendo como el uso de energía de la red en la ranura conduce al algoritmo de deriva más penalización para minimizar la potencia promedio sujeta a la estabilidad de la red desarrollado por Neely. [8] Utilizando y usando ya que el negativo de una métrica de servicios públicos de control de admisión conduce al algoritmo de deriva más penalización para el control de flujo conjunto y el enrutamiento de red desarrollado por Neely, Modiano y Li. [3]
En este contexto, es importante una generalización del teorema de la deriva de Lyapunov de la sección anterior. Para simplificar la exposición, suponga está acotado desde abajo:
Por ejemplo, lo anterior se satisface con en los casos en que la pena siempre es no negativo. Dejar representan un objetivo deseado para el tiempo promedio de Dejar ser un parámetro utilizado para ponderar la importancia de alcanzar el objetivo. El siguiente teorema muestra que si se cumple una condición de deriva más penalización, entonces la penalización promedio de tiempo es como máximo O (1 / V) por encima del objetivo deseado, mientras que el tamaño promedio de la cola es O (V). La El parámetro se puede ajustar para hacer que la penalización promedio de tiempo esté tan cerca (o por debajo) del objetivo como se desee, con una compensación de tamaño de cola correspondiente.
- Teorema (Optimización de Lyapunov). Supongamos que hay constantes y tal que para todos y todos los vectores posibles Se cumple la siguiente condición de deriva más penalización:
- Entonces para todos la penalización promedio de tiempo y los tamaños de cola promedio de tiempo satisfacen:
Prueba. Tomando las expectativas de ambos lados de la deriva-más-penalización postulada y usando la ley de las expectativas iteradas, tenemos:
Sumando lo anterior sobre el primero ranuras y el uso de la ley de las sumas telescópicas da:
Dividiendo por y la reordenación de términos demuestra el límite de penalización promedio de tiempo. Un argumento similar demuestra el límite de tamaño de cola promedio de tiempo.
Enlaces relacionados
Referencias
- ^ a b L. Tassiulas y A. Ephremides, " Propiedades de estabilidad de los sistemas de colas restringidos y políticas de programación para un rendimiento máximo en redes de radio multisalto , transacciones IEEE sobre control automático , vol. 37, no. 12, págs. 1992.
- ^ a b L. Tassiulas y A. Ephremides, " Asignación dinámica de servidores a colas paralelas con conectividad que varía aleatoriamente ", IEEE Transactions on Information Theory, vol. 39, no. 2, págs. 466-478, marzo de 1993.
- ^ a b c MJ Neely, E. Modiano y C. Li, " Equidad y control estocástico óptimo para redes heterogéneas ", Proc. IEEE INFOCOM, marzo de 2005.
- ^ L. Georgiadis, MJ Neely y L. Tassiulas, " Asignación de recursos y control entre capas en redes inalámbricas ", Fundamentos y tendencias en redes , vol. 1, no. 1, págs. 1-149, 2006.
- ^ a b c M. J. Neely. Optimización de redes estocásticas con aplicación a sistemas de comunicación y colas , Morgan & Claypool, 2010.
- ^ MJ Neely, " Computación distribuida y segura de programas convexos en una red de procesadores conectados ", DCDIS Conf, Guelph, Ontario, julio de 2005
- ^ E. Leonardi, M. Mellia, F. Neri y M. Ajmone Marsan, " Límites en los retrasos promedio y promedios de tamaño de cola y variaciones en conmutadores basados en celdas en cola de entrada ", Proc. IEEE INFOCOM, 2001.
- ^ a b M. J. Neely, " Control óptimo de energía para redes inalámbricas que varían en el tiempo ", IEEE Transactions on Information Theory, vol. 52, no. 7, págs.2915-2934, julio de 2006.
Fuentes primarias
- MJ Neely. Optimización de redes estocásticas con aplicación a sistemas de comunicación y colas , Morgan & Claypool, 2010.