HEURISTICS FOR ROUTING AND WAVELENGTH ASSIGNMENT BY PARTITION COLORING / HEURÍSTICAS PARA ROTEAMENTO E ATRIBUIÇÃO MÍNIMA DE COMPRIMENTOS DE ONDA POR COLORAÇÃO DE PARTIÇÕES

AUTOR(ES)

THIAGO FERREIRA DE NORONHA

DATA DE PUBLICAÇÃO

2004

RESUMO

Nas redes de fibras óticas, as informações são transmitidas na forma de um sinal luminoso através de uma fibra ótica. A tecnologia de multiplexação WDM permite a transmissão simultânea de vários sinais em um mesmo enlace. As conexões entre estações terminais são estabelecidas na forma de caminhos óticos, que são definidos em função de sua rota e do comprimento de onda no qual são multiplexados. Conversores de comprimentos de onda não são considerados neste trabalho. Conseqüentemente, os caminhos óticos devem permanecer com o mesmo comprimento de onda em todos os enlaces do transmissor ao receptor. O Problema de Roteamento e Atribuição Mínima de Comprimentos de Onda (min- RWA) consiste em estabelecer um conjunto de conexões entre pares de estações e atribuir um determinado comprimento de onda para cada uma delas, de forma que caminhos óticos que compartilhem algum enlace da rede tenham comprimentos de onda diferentes e que o número total de comprimentos de onda utilizados seja mínimo. Neste trabalho, uma nova heurística é proposta para min-RWA, onde k possíveis rotas são calculadas para cada conexão e, em seguida, uma rota (dentre as rotas pré-calculadas) e um comprimento de onda são atribuídos a cada conexão resolvendo-se um Problema de Coloração de Partições (PCP). O PCP é um problema de coloração em grafos particionados, ou seja, grafos onde os vértices estão particionados em subconjuntos disjuntos. O PCP consiste em selecionar e colorir um único vértice de cada subconjunto, de modo que dois vértices adjacentes, no grafo induzido pelos vértices selecionados tenham cores diferentes e que o número total de cores utilizadas seja mínimo. Nesta dissertação, são apresentadas e propostas novas heurísticas para PCP e min-RWA. Estas heurísticas são comparadas com as melhores conhecidas na literatura.

ASSUNTO(S)

otimizacao combinatoria coloracao de particoes routing comprimentos de onda combinatory optimization metaheuristic roteamento metaeuristica optical networks wavelength redes opticas partition coloring

Documentos Relacionados

• Heuristicas para roteamento e alocação de comprimentos de onda para comunicações multidifusão e comunicações com restrições de potencia em redes opticas
• ROTEAMENTO E ALOCAÇÃO DE COMPRIMENTO DE ONDA EM REDES ÓPTICAS
• Roteamento e Atribuição do Comprimento de Onda Dinâmicos Utilizando Colônia de Formigas em Redes Ópticas Comutadas Por Rajadas Fortaleza - Ceará 2010
• Desenvolvimento de algoritmos de roteamento e atribuição de comprimentos de onda para as redes opticas inteligentes e transparentes
• SMART WAVELENGTH ROUTING ASSIGNMENT ON WDM NETWORKS BY FUNCTIONALITY ON PHYSICAL LAYER