Use este identificador para citar ou linkar para este item: http://repositorio.roca.utfpr.edu.br/jspui/handle/1/5974
Título: Análise de filas de prioridades para o algoritmo de Dijkstra em redes de malhas sem fio
Autor(es): Gonçalves, Diogo Machado
Orientador(es): Almeida, Sheila Morais de
Palavras-chave: Algorítmos computacionais
Sistemas de comunicação sem fio
Roteadores (Redes de computadores)
Rede de computador - Protocolos
Computer algorithms
Wireless communication systems
Routers (Computer network)
Computer network protocols
Data do documento: 10-Nov-2015
Editor: Universidade Tecnológica Federal do Paraná
Câmpus: Ponta Grossa
Referência: GONCALVES, Diogo Machado. Análise de filas de prioridades para o Algoritmo de Dijkstra em redes de malhas sem fio. 2015. 110 f. Trabalho de Conclusão de Curso (Graduação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2015.
Resumo: Garantir a escalabilidade de um protocolo de roteamento de redes de malha sem fio contribui para a manutenção da qualidade da conexão oferecida pela rede com a adição de novos clientes. Otimizar o Algoritmo de Dijkstra utilizado pelo protocolo OLSRD para calcular as rotas que os pacotes de dados da rede devem seguir contribui significativamente para o aumento do desempenho da rede. Este trabalho apresenta um estudo empírico acerca do impacto de diferentes filas de prioridades na complexidade do Algoritmo de Dijkstra. Com base nas avaliações teóricas e práticas de desempenho da fila de prioridade do protocolo de redes de malha sem fio OLSRD, outras estruturas de dados foram selecionadas na literatura para uma avaliação de desempenho. Filas de prioridades em cenários característicos de redes de malha sem fio apresentaram um grande número de itens com prioridades repetidas inseridos nestas estruturas de dados, prejudicando a árvore AVL, estrutura presente no protocolo e contribuindo para a escolha do heap binário e Van Emde Boas como as melhores filas de prioridade para grandes redes neste contexto.
Abstract: A scalable wireless mesh network protocol helps to keep a good quality of service when new clients are added. An improvement on Dijkstra's Algorithm used by the OLSRD protocol to find the shortest paths for the data packages through the network, increases the performance of the network. This work shows an empirical analysis about the Dijkstra's performance with different priority queues. On the basis of theoretical and practical performance evaluations in the OLSRD's priority queue, other data structures were selected to be compared with it. In a mesh network scenario, Dijkstra's Algorithm inserts a big amount of items with the same key in the priority queue, which reduces AVL tree performance. Based on this fact, this work shows that the binary heap and Van Emde Boas tree are a better choice compared to the AVL tree, current priority queue used in OLSRD.
URI: http://repositorio.roca.utfpr.edu.br/jspui/handle/1/5974
Aparece nas coleções:PG - Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
PG_COCIC_2015_2_01.pdf2,84 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.