Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/13016
Type: Dissertação
Title: Fractional edge coloring for wireless link scheduling in the physical interference mode
Other Titles: Coloracão fracionária de arestas para o escalonamento de enlaces sem fio no modelo físico de interferência
Author(s)/Inventor(s): Ricardo, Guilherme Iecker
Advisor: Rezende, José Ferreira de
Co-advisor: Barbosa, Valmir Carneiro
Abstract: A popularidade de aplicações para Redes de Sensores Sem Fio (WSN) e Internet of Things (IoT) tem aumentado bastante nos últimos e, com ela, a demanda por redes mesh sem fio (WMN) mais eficientes e econômicas em termos de utilização de recursos. O problema de Escalonamento de Enlaces tem por objetivo melhorar a capacidade das redes por meio da adoção de uma estratégia inteligente de ativação dos enlaces sem fio. Essa estratégia garante a correta comunicação entre dispositivos, respeitando as restrições do Modelo de Interferência Física adotado. O presente trabalho oferece uma abordagem para encontrar o escalonamento ótimo por meio da redução do problema de Escalonamento de Enlaces ao problema de Coloração Fracionária de Arestas. Uma formulação de Programação Linear com complexidade exponencial no tamanho do grafo e um algoritmo para auxiliar uma construção mais eficiente dos modelos são apresentados. Finalmente, uma grande quantidade de experimentos foram realizados objetivando verificar a aplicabilidade e o desempenho da técnica na prática.
Abstract: The popularity of Wireless Sensor Networks (WSN) and Internet of Things (IoT) applications is experiencing an unprecedent increase in the last few years. Along with it, the demand for more efficient and economic Wireless Mesh Networks (WMNs) in terms of resource management. The Link Scheduling problem aims to improve network capacity and the resource usage of WMNs through adopting a smart strategy for wireless links activation. This strategy guarantees the strict communication between network devices, satisfying the adopted Physical Interference Model (PIM) constraints. The current work offers an approach to find the optimal scheduling by modeling the Link Scheduling problem as a Fractional Edge-Coloring problem. A Linear Programming (LP) formulation with exponential complexity on the graph size and an algorithm to aid efficiently building such models are introduced. Finally, a considerable amount of experiments were run in order to assess the technique’s practical applicability and performance.
Keywords: Wireless Networks
Link Scheduling
Operational Research
Subject CNPq: CNPQ::ENGENHARIAS
Program: Programa de Pós-Graduação em Engenharia de Sistemas e Computação
Department : Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
Publisher: Universidade Federal do Rio de Janeiro
Issue Date: Mar-2018
Publisher country: Brasil
Language: eng
Right access: Acesso Aberto
Appears in Collections:Engenharia de Sistemas e Computação

Files in This Item:
File Description SizeFormat 
GuilhermeIeckerRicardo.pdf1,98 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.