Publicado no Encontro de Saberes 2015
Evento: XXIII Seminário de Iniciação Científica
Área: ENGENHARIAS
Subárea: Engenharia de Computação
Título |
HEURÍSTICAS PARA O PROBLEMA DE ROTEAMENTO E ALOCAÇÃO DE COMPRIMENTOS DE ONDA EM REDES ÓTICAS |
Autores |
MARINA FERREIRA CUNHA (Autor) ALEXANDRE XAVIER MARTINS (Orientador) |
Resumo |
O problema conhecido como Roteamento e Alocação de Comprimentos de Onda (RWA - Routing and Wavelength Assignment) visa atender às demandas definidas na etapa do projeto de topologia virtual, em geral minimizando recursos como a quantidade de comprimentos de onda utilizados ou maximizando a quantidade de requisições atendidas com um número limitado de comprimentos de onda disponíveis. Neste projeto a ideia é testar novos tipos de classificação para as requisições. Dado uma rede de comunicação que utiliza fibras óticas e um conjunto de requisições por comunicação entre os pares de vértices da rede, o objetivo é definir qual caminho cada requisição irá seguir da origem até o destino e qual comprimento de onda a requisição irá usar. Primeiramente, foram definidas as instâncias para cada qual possui suas característica próprias de quantidade de nós, comunicação e a demanda. No caso, além do caminho mínimo utilizamos também o fluxo máximo entre a origem e o destino de cada requisição. Consideramos que requisições entre um par de nós, origem e destino, com pouca possibilidade de fluxo são mais difíceis de alocar sendo assim devem ser alocadas primeiro. Foram testadas então 2 tipos de classificação: 1 - Preferência para as requisições com maior caminho mínimo, em caso de empate, preferência para requisições com menor fluxo máximo, em caso de empate ordena aleatoriamente. 2 - Preferência para requisições com menor fluxo máximo, em caso de empate, preferência para requisições com maior caminho mínimo, em caso de empate ordena aleatoriamente. O restante do algoritmo funciona como o BFD da literatura.Para as instâncias testadas os resultados obtidos até então não foram conclusivos na medida em que o BFD da literatura encontra as melhores soluções iniciais para um conjunto de instâncias, enquanto o método proposto encontra as melhores soluções iniciais para outro conjunto. |