La asignación de recursos de OFDMA derivados de la formulación y solución de un modelo de optimización con variables continuas y variables booleanas

Resumo

Esta Tesis Doctoral aborda el problema de la asignación dinámica de recursos (frecuencia y potencia) en el enlace de bajada de un sistema de comunicaciones móviles que utiliza multiplexión por división de frecuencia ortogonal en su nivel físico. El problema se resuelve en el contexto de un sistema multi-usuario, multi-celda, multi-servicio con arquitectura homogénea o heterogénea. El enfoque utilizado para resolver el problema divide a la tarea de asignación de recursos en dos componentes: el componente local/distribuido, responsable por la selección de los usuarios que reciben servicio y por la asignación de recursos en la perspectiva de corto-plazo (milisegundos)"; y el componente global/centralizado, responsable por la asignación global de los recursos del sistema en la perspectiva de mediano-plazo (segundos). El trabajo doctoral establece la arquitectura y la funcionalidad del programador global de recursos, este componente del sistema de comunicaciones móviles (SCM) determina la asignación de recursos que satisface las demandas de servicio de los usuarios utilizando la relación señal a ruido más interferencia (SINR, por “Signal-to-Noise plus Interference Ratio”) en la perspectiva media de tiempo (segundos). Para lograrlo, el autor usa un enfoque inédito, en lugar de buscar la configuración del sistema que ofrece la mejor relación SINR, asume su cumplimiento, y encuentra la asignación de recursos que satisface la demanda de servicio de cada usuario. Como no siempre puede obtenerla, incluye un conjunto de variables de holgura que aseguran la factibilidad del modelo y cuyo valor suma permite determinar si los requerimientos de servicio pueden o no pueden ser plenamente satisfechos. Cuando logra el objetivo propuesto, alcanza un nivel de cumplimiento del 100% en el caudal de datos requerido. Sin embargo, en muchos sistemas reales no es posible hacerlo, en este caso, lo detecta, lo informa y obtiene prestaciones de alta valía. En este caso, la evidencia experimental muestra que se alcanzan altos niveles de satisfacción plena del servicio entre los usuarios (del orden del 97%), bajos niveles de negación del servicio (inferiores al 3%), una utilización eficiente de la potencia disponible (del orden del 30%) y una asignación justa de la capacidad de transmisión del sistema para los diferentes servicios ofrecidos (del orden del 88%, según el cálculo del índice de equidad de Jain). Frente a propuestas previas, el enfoque se aparta de la necesidad de contar con información de estado de los canales. En su lugar, las terminales de usuario reportan la posición del usuario y el servicio que demandan al componente central. Por lo tanto, el volumen de información generado, y la sobrecarga de comunicaciones y de procesamiento impuestas, son significativamente menores. El modelo de optimización formulado considera un conjunto de variables booleanas y contínuas con un conjunto de restricciones cuadráticas establecidas entre ellas. Por tal motivo, puede ser clasificado como un modelo de optimización no lineal mixto que puede ser resuelto exactamente utilizando herramientas comerciales como CPLEX, MINOS y otras. Sin embargo, encontrar la solución óptima requiere de una significativa sobrecarga computacional porque el número de iteraciones necesarias para obtener la solución crece de forma exponencial con el tamaño del problema. El conjunto de variables de holgura considerado, suministra información al administrador del sistema acerca de la cantidad de mejoramiento necesaria para lograr la satisfacción plena de los requerimientos. Dependiendo del valor de la variable de holgura asociada con el recurso asignado, cada usuario del sistema puede estar en uno de tres posibles estados: plenamente satisfecho, parcialmente satisfecho y con negación del servicio. La posibilidad de ofrecer servicio degradado, en lugar de considerarlo un estado no factible del modelo, mejora los niveles de utilización de los recursos y permite aprovechar el carácter elástico de algunos de los servicios ofrecidos. La estrategia de solución tiene en cuenta la caracterización del modelo, la cantidad de recursos de cómputo (procesamiento y memoria) requeridos para obtenerla; la imprecisión de la información disponible; la limitación temporal para la obtener la solución; y que en este caso, el proveedor del servicio se declara satisfecho cuando obtiene una solución suficientemente buena (no requiere obtener el óptimo global). Por estas razones, se utiliza un enfoque aproximado para la obtención de la solución. El algoritmo de solución modelo desacopla el espacio de búsqueda en variables booleanas y continuas, asigna valores a las variables booleanas usando una estrategia de asignación de recursos de frecuencia y las convierte en constantes, transformando el modelo original en uno lineal y continuo. Además, utiliza una estrategia iterativa para mejorar la condición del sistema buscando mayores niveles de satisfacción de los usuarios. Para lograrlo, considera el valor de la función objetivo como métrica agregada para evaluar la bondad de cada asignación de recursos de frecuencia propuesta. En el modelo de optimización formulado, se renuncia a la obtención del mínimo global cuando se descompone el espacio de búsqueda. Luego, cuando se adopta el método de búsqueda local como estrategia de exploración del espacio de búsqueda y se define una estructura de vecindad aminorada, se renuncia también a la obtención del mínimo local porque el algoritmo de solución no puede revisar la totalidad del conjunto de vecinos. En este caso, la solución obtenida corresponde con la mejor solución obtenida en el intervalo de tiempo disponible cuando se evalúan un promisorio conjunto de vecinos en la estructura de vecindad aminorada definida. Esta solución resulta aceptable para el administrador del sistema. El algoritmo de solución puede ser aplicado en diversos escenarios prácticos, con diferente arquitectura (homogénea/heterogénea), configuración de las celdas que componen el sistema, distribución de los usuarios y variedad de los servicios ofrecidos a los usuarios. Además, permite la configuración de la estrategia de asignación de los bloques de frecuencias a los usuarios; del factor de reutilización de la frecuencia, del enfoque de exploración del espacio de búsqueda; del punto de vista del administrador del sistema y de la condición de terminación del ciclo iterativo. La flexibilidad para la configuración del sistema de comunicaciones móviles lo convierte en un marco de trabajo de propósito general, en el cual, resulta posible resolver el modelo de optimización mixta no lineal configurando la programación de recursos con diferentes criterios y con una baja complejidad computacional. En los escenarios propuestos, se utilizaron hasta once diferentes versiones del algoritmo de solución. Cada una ellas utilizó una configuración, un factor de reutilización de la frecuencia, una estrategia de asignación de recursos y un enfoque de exploración del espacio de búsqueda diferente, sin que resultara necesario efectuar cambio alguno sobre el modelo de optimización. En el trabajo, se comparan tres estrategias para la exploración del espacio de búsqueda: las estrategias de intensificación y diversificación, que ignoran las condición del sistema y dejan al azar la posibilidad de generar mejores estados para el sistema;" y la estrategia basada en un heurístico formulado, que considera la condición de interferencia en el sistema para explorar un conjunto promisorio de estados en la vecindad aminorada guiados por un criterio objetivo de calidad (el valor de la función objetivo) buscando la mejor condición para el sistema en el intervalo de tiempo disponible. La aplicación de este criterio, permite explorar consistentemente el espacio de búsqueda, con una baja carga computacional. El índice de efectividad definido, permite evaluar la capacidad del heurístico para explorar el espacio de búsqueda y para encontrar mejores estados para el sistema. El índice permite establecer el número promedio de iteraciones que realiza el algoritmo antes de alcanzar un mejor estado para el sistema y determinar el lugar donde tuvo lugar la exploración. Los resultados obtenidos muestran altos niveles de cumplimiento de las métricas definidas y una exploración más efectiva y consistente del espacio de búsqueda cuando se utilizó la estrategia basada en el heurístico formulado.