Fractional Edge Coloring for Wireless Link Scheduling In the Physical Interference Model

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.