Algoritmos de coloração de grafos para o escalonamento em redes sem fio

• Ano de defesa: 2018
• Autor(a) principal: Gomes, Francisco Gleyson da Silva
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Estadual do Ceará
• Palavras-chave em Português: Ciência da computação; Rede sem Fio; Teoria dos grafos
• Link de acesso: https://siduece.uece.br/siduece/trabalhoAcademicoPublico.jsf?id=83189

<div style="">Uma rede sem fio consiste em um conjunto de nós que compartilham um canal de difusão para a transmissão e recepção de informações. Em um canal compartilhado, as transmissões estão sujeitas à colisões por causa dos problemas de interferências. Uma forma de resolver esses problemas é através de um escalonamento usando a técnica TDMA, que atribui aos nós ou enlaces da rede intervalos de tempo de um quadro TDMA. Uma rede pode ser modelada como um digrafo e o escalonamento TDMA de enlaces ser encontrado com o modelo de coloração PRN. O modelo de coloração PRN é usado na coloração dos arcos do digrafo da rede, para evitar as interferências primárias e secundárias. Este trabalho propõe algoritmos e uma modelagem para o problema de coloração BPRN. O modelo de coloração BPRN é uma extensão do modelo de coloração PRN, pois considera apenas à coloração de um subconjunto de arcos do digrafo da rede, denominado de digrafo backbone. Um digrafo backbone pode representar diferentes topologias de redes, mas neste trabalho, ele é representado por uma árvore geradora orientada em direção a um vértice raiz. Os algoritmos propostos, denominados de Bsatur e Bswap, adaptam os conceitos de grau e grau de saturação de um vértice usados no algoritmo Dsatur, para grau de conflitos e grau de saturação de um arco. As informações de grau de conflitos e grau de saturação de um arco são usadas por esses algoritmos para determinar à ordem de coloração dos arcos de um digrafo backbone. O algoritmo Bswap incorpora um mecanismo de reutilização de cores a ser utilizado quando é preciso criar uma nova cor para colorir um arco. Os algoritmos foram avaliados em cenários com instâncias de baixa, média e alta densidade. Os resultados mostraram que em instâncias com maior densidade, os algoritmos propostos obtiveram resultados melhores em relação aos resultados dos algoritmos BF e DFOr usados para comparação. O tempo de execução do algoritmo Bswap é maior do que o tempo de execução do algoritmo Bsatur devido ao mecanismo de reutilização de cores adotado por esse algoritmo. Os algoritmos BF e DFOr apresentaram o mesmo tempo de execução, pois a principal diferença entre esses algoritmos está na ordem em que os vértices do digrafo backbone são visitados. Palavras-chave: Teoria dos Grafos. Modelo de Coloração BPRN. Algoritmos de Coloração BPRN. Redes Sem Fio. Intervalos de Tempo.</div>