Autores

6564
2956,883,163
6565
2956,883,163
6566
2956,883,163

Informações:

Publicações do PESC

Título
Fractional Edge Coloring for Wireless Link Scheduling In the Physical Interference Model
Linha de pesquisa
Redes de Computadores
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
29/3/2018
Resumo

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 ecient 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 o ers 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 eciently building such models are introduced. Finally, a considerable amount of experiments were run in order to assess the technique's practical applicability and performance.

Arquivo
Topo