Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10071/24243
Autoria: | Gomes, Inês Ferreira |
Orientação: | Cancela, Luís Gonçalo Lecoq Vences e Costa Rebola, João Lopes |
Data: | 17-Dez-2021 |
Título próprio: | Exploring optimal solutions for planning optical networks with graph coloring techniques |
Referência bibliográfica: | Gomes, I. F. (2021). Exploring optimal solutions for planning optical networks with graph coloring techniques [Dissertação de mestrado, Iscte - Instituto Universitário de Lisboa]. Repositório do Iscte. http://hdl.handle.net/10071/24243 |
Palavras-chave: | Graph coloring Greedy Programação linear inteira -- Integer linear programming Rede ótica -- Optical network Tabu Search Wavelength assignment Atribuição de comprimentos de onda Coloração de grafos |
Resumo: | Optical networks are crucial in today’s communications, so their planning is of paramount
importance. Routing and Wavelength Assignment (WA) are essential planning
functions to transport the data in these networks. This work aims to study different
graph coloring techniques for WA in static optical networks.
We analyze and compare different graph coloring algorithms such as the Greedy heuristic,
an exact algorithm based on Integer Linear Programming (ILP) and the Tabu Search
meta-heuristic, for WA in optical networks. The studies are performed considering several
real network scenarios, different logical and path topologies, and the number of colors and
computation time of each one of the studied algorithms is analysed.
We have concluded that the exact algorithm based on ILP, although giving always the
optimum number of colors, is only applicable to networks with less than 20 nodes, due to
its higher computation time. It was also concluded that the Tabu Search algorithm gives
always the same results as the exact algorithm, for the real networks studied, but in a much
faster computation time. Finally, we have concluded that the common Greedy algorithm
performs as well as the Tabu Search algorithm, for all the real networks studied, but in
some scenarios, with random path matrices, the Tabu Search gives a lower number of
colors than the Greedy algorithm. For example, the Tabu Search gives less 35 colors than
the Greedy algorithm for a random path matrix with 1000 paths and a 50% probability
that each path has one or more links being used by the other paths. As redes óticas são fundamentais para as comunicações atuais, tendo o seu planeamento uma grande importância. O encaminhamento e a atribuição de comprimentos de onda são funções essenciais no planeamento do transporte de dados nestas redes. Este trabalho pretende estudar diferentes técnicas de coloração de grafos para a atribuição de comprimentos de onda nas redes óticas. Analisamos e comparamos diferentes algoritmos de atribuição de comprimentos de onda, como a heurística Greedy, um algoritmo exato baseado em Programação Linear Inteira (PLI) e um algoritmo de procura meta-heurístico, o Tabu Search. Estudaram-se estes algoritmos para diferentes redes reais, diferentes topologias lógicas e de caminhos, com o objetivo de analisar o número de cores e o tempo computacional obtidos por cada algoritmo estudado. Concluímos que o algoritmo exato baseado em PLI, embora devolva sempre um número de cores ótimo, aplica-se apenas a redes com menos de 20 nós, devido ao seu tempo computacional elevado. Também se concluiu que o Tabu Search devolve sempre os mesmos resultados que o algoritmo exato, para as redes reais, mas com mais rapidez computacional. Concluiu-se também para as redes reais, que o Greedy estima o mesmo número de cores que o Tabu Search. No entanto, com matrizes geradas aleatoriamente, nalguns casos, o Tabu Search retorna menos cores que o Greedy. Por exemplo, o Tabu Search devolve menos 35 cores que o Greedy para uma matriz de 1000 caminhos e 50% de probabilidade de cada caminho ter uma ou mais ligações pertencentes aos restantes caminhos. |
Designação do grau: | Mestrado em Engenharia de Telecomunicações e Informática |
Arbitragem científica: | yes |
Acesso: | Acesso Aberto |
Aparece nas coleções: | T&D-DM - Dissertações de mestrado |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
master_ines_ferreira_gomes.pdf | 2,26 MB | Adobe PDF | Ver/Abrir |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.