The robust shortest path tree problem: formulations and algorithms
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Primeiro orientador
Membros da banca
Luiz Filipe Menezes Vieira
Christophe Duhamel
Geraldo Robson Mateus
Christophe Duhamel
Geraldo Robson Mateus
Resumo
IPv6 Low Wireless Personal Area Networks} (6LoWPAN) é a mais promissora tecnologia para a implementação da chamada Internet das Coisas. Para que esta tecnologia torne-se uma realidade, protocolos de roteamento precisam ser resilientes a variações na qualidade da transmissão, devido a constantes mudanças nos enlaces. O mais promissor destes protocolos é o IPv6 Routing Protocol for Low-Power and Lossy Networks} (RPL). Nesta dissertação, o protocolo RPL é extendido de forma a considerar a incerteza na qualidade dos enlaces. O problema de roteamento do RPL Robusto é modelado como um problema de otimização robusta derivado do Problema da Árvore de Caminhos Mais Curtos, denominado Árvore de Caminhos Mais Curtos Robusta (RSPT). São propostas três heurísticas para o RSPT, além de duas diferentes formulações matemáticas e um algoritmo exato baseado em uma das formulações propostas. Além disso, dois algoritmos aproximativos da literatura para problemas de Otimização Robusta foram extendidos para o RSPT, e uma prova de seus fatores de aproximação foi desenvolvida. Os algoritmos propostos são comparados com os algoritmos da literatura. Experimentos computacionais demonstraram que o algoritmo exato proposto resolveu todas as instâncias propostas com 100 vértices na otimalidade. Entretanto, ele não conseguiu resolver instâncias com 200 vértices na otimalidade em um tempo de 24 horas. Uma das heurísticas propostas apresentou resultados melhores que os algoritmos aproximativos extendidos da literatura, sendo que obteve um gap relativo próximo ao gap do algoritmo exato proposto com um tempo computacional muito inferior. Duas das heurísticas propostas podem ser implementadas como protocolos de roteamento para 6LoWPANs.
Abstract
IPv6 Low Wireless Personal Area Networks (6LoWPAN) is the most promising technology for implementing the so called Internet of Things. In order for this technology to become a reality, routing protocols need to be resilient to variations in the links quality, due the constantly changes in the channels. The most promising of these protocols is the IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL). In this work, the RPL routing protocol was extended to consider the uncertainty in the link quality. The RPL Robust routing problem is modeled as a Robust Shortest Path Tree problem (RSPT). Three heuristics for the RSPT are developed, besides two different mathematical formulations, and an exact algorithm based on one of the proposed formulations. The proposed algorithms are compared with two algorithms from the literature. One of the proposed heuristics has presented better results that the literature algorithms, and its can be implemented as a routing protocol for 6LoWPANs.
Assunto
Otimização matemática, Internet das Coisas, Computação, Otimização robusta
Palavras-chave
Internet das Coisas, Otimização robusta, Programação matemática, Heurísticas, RPL