Defensa Tesis Licenciatura Guillermo Picardi
Título: Un algoritmo Tabu Search para el problema del cubrimiento de redes por ciclos acotados. Directora: Irene Loiseau
| Qué |
|
|---|---|
| Cuándo |
20/10/2009 de 06:00 pm a 07:00 pm |
| Dónde | Aula 12 |
| Agregar evento al calendario |
vCal
iCal
|
- Título: Un algoritmo Tabu Search para el problema del cubrimiento de redes por ciclos acotados"
- Alumno: Guillermo Picardi
- Directora: Irene Loiseau
- Jurados: Esteban Mocskos, Francisco Soulignac
RESUMEN
En sus diversas fases de diseño, construcción y mantenimiento, las redes de comunicación traen aparejados grandes desafíos tecnológicos, logísticos, económicos y algorítmicos, entre otros. Debido a la demanda a la que están sometidas permanentemente; al grado de dependencia creciente en su uso, manifiesta en las miles de actividades e intercambios que estas posibilitan; y a la continuidad del servicio a la que están sometidas, se requiere diseñar y/o configurar redes seguras, que además minimicen sus costos operativos. Entendiendo por una red segura, una que ante eventuales fallas en algunos de sus enlaces, tenga la capacidad de seguir trasmitiendo a través de sus enlaces restantes.
Nuestro trabajo tiene por objeto proponer un algoritmo para el problema de Cubrimiento por Ciclos Limitados o Bounded Cycle Cover Problem (BCCP). Esto es, dada una red física, se requiere construir subredes de manera tal que cubran toda la red original, minimizando los costos involucrados de esta. Cada subred tiene forma de anillo o ciclo y, asimismo, cada uno de estos ciclos no deberá superar un cierto tamaño preestablecido. Estos ciclos modelan el problema de los Self healing ring (SHR). Los mismos son bidireccionales y muy utilizados en comunicaciones de fibra óptica.
La estructura de un SHR, hace que si se cae un enlace del mismo, se pueda seguir transmitiendo información en los enlaces restantes. Entonces, si se garantiza la comunicación dentro de cada ciclo, se garantiza la comunicación en toda la red.
Dada una red, nuestra solución propone, en una primera etapa, generar ciclos de tamaño menor o igual al máximo preestablecido. Cada uno de ellos tiene un costo asociado. Ulteriormente, en una segunda etapa, aplicamos un algoritmo de Tabú Search con el objeto de decidir qué ciclos seleccionaríamos, de manera tal que estos cubran todos los ejes de la red original, minimizando la cantidad y/o los costos de los ciclos involucrados. Los resultados obtenidos fueron muy buenos comparados con los disponibles en la literatura.
