Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/15911| 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 |
| Citação: | 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.utfpr.edu.br/jspui/handle/1/15911 |
| Aparece nas coleções: | PG - Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| PG_COCIC_2015_2_01.pdf | 2,84 MB | Adobe PDF |  Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.