Optimización metaheurística para la planificación de redes WDM

Abstract

Las implementaciones actuales de las redes de telecomunicaciones no permiten soportar el incremento en la demanda de ancho de banda producido por el crecimiento del tráfico de datos en las últimas décadas. La aparición de la fibra óptica y el desarrollo de la tecnología de multiplexación por división de longitudes de onda (WDM) permite incrementar la capacidad de redes de telecomunicaciones existentes mientras se minimizan costes. En este trabajo se planifican redes ópticas WDM mediante la resolución de los problemas de Provisión y Conducción en redes WDM (Provisioning and Routing Problem) y de Supervivencia (Survivability Problem). El Problema de Conducción y Provisión consiste en incrementar a mínimo coste la capacidad de una red existente de tal forma que se satisfaga un conjunto de requerimientos de demanda. El problema de supervivencia consiste en garantizar el flujo del tráfico a través de una red en caso de fallo de alguno de los elementos de la misma. Además se resuelve el Problema de Provisión y Conducción en redes WDM con incertidumbre en las demandas. Para estos problemas se proponen modelos de programación lineal entera. Las metaheurísticas proporcionan un medio para resolver problemas de optimización complejos, como los que surgen al planificar redes de telecomunicaciones, obteniendo soluciones de alta calidad en un tiempo computacional razonable. Las metaheurísticas son estrategias que guían y modifican otras heurísticas para obtener soluciones más allá de las generadas usualmente en la búsqueda de optimalidad local. No garantizan que la mejor solución encontrada, cuando se satisfacen los criterios de parada, sea una solución óptima global del problema. Sin embargo, la experimentación de implementaciones metaheurísticas muestra que las estrategias de búsqueda embebidas en tales procedimientos son capaces de encontrar soluciones de alta calidad a problemas difíciles en industria, negocios y ciencia. Para la solución del problema de Provisión y Conducción en Redes WDM, se desarrolla un algoritmo metaheurístico híbrido que combina principalmente ideas de las metaheurísticas Búsqueda Dispersa (Scatter Search) y Búsqueda Mutiarranque (Multistart). Además añade una componente tabú en uno de los procedimiento del algoritmo. Se utiliza el modelo de programación lineal entera propuesto por otros autores y se propone un modelo de programación lineal entera alternativo que proporciona cotas superiores al problema, pero incluye un menor número de variables y restricciones, pudiendo ser resuelto de forma óptima para tamaños de red mayores. Los resultados obtenidos por el algoritmo metaheurístico diseñado se comparan con los obtenidos por un procedimiento basado en permutaciones de las demandas propuesto anteriormente por otros autores, y con los dos modelos de programación lineal entera usados. Se propone modelos de programación lineal entera para sobrevivir la red en caso de fallos en un único enlace. Se proponen modelos para los esquemas de protección de enlace compartido, de camino compartido con enlaces disjuntos, y de camino compartido sin enlaces disjuntos. Se propone un método de resolución metaheurístico que obtiene mejores costes globales que al resolver el problema en dos fases, es decir, al resolver el problema de servicio y a continuación el de supervivencia. Se proponen además modelos de programación entera para resolver el problema de provisión en redes WDM con incertidumbres en las demandas.