Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/ESBF-AE7N9X| Type: | Dissertação de Mestrado |
| Title: | The robust shortest path tree problem: formulations and algorithms |
| Authors: | Iago Augusto de Carvalho |
| First Advisor: | Thiago Ferreira de Noronha |
| First Co-advisor: | Luiz Filipe Menezes Vieira |
| First Referee: | Luiz Filipe Menezes Vieira |
| Second Referee: | Christophe Duhamel |
| Third Referee: | Geraldo Robson Mateus |
| Abstract: | 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. |
| Subject: | Otimização matemática Internet das Coisas Computação Otimização robusta |
| language: | Inglês |
| Publisher: | Universidade Federal de Minas Gerais |
| Publisher Initials: | UFMG |
| Rights: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/ESBF-AE7N9X |
| Issue Date: | 15-Feb-2016 |
| Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| iagoaugustodecarvalho.pdf | 981.46 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.