Formulações e heurísticas para duas variantes do problema do escalonamento em redes sem fio

Abstract

Novos protocolos de rede sem fio, a exemplo do IEEE 802.11ax (Wi-Fi~6), permitem que o espectro eletromagnético seja particionado em um ou mais canais de comunicação cuja largura de banda pode variar de 20~MHz a 160~MHz. Esse particionamento permite conexões com interferências menores e velocidades de transmissão maiores. Entretanto, particionar o espectro de forma ótima ou até mesmo de forma factível, em casos extremos, é visto como um desafio no campo de projeto de algoritmos, uma vez que pode existir uma quantidade exponencial de maneiras que tal particionamento pode ser realizado. Tendo em vista o contexto de algoritmos de escalonamento, esse presente trabalho aborda dois problemas considerados $\NP$-difícil que visam otimizar o escalonamento de conexões Wi-Fi. O primeiro, intitulado de \textit{Variable Rate Variable Scheduling Problem}~(VRBSP), é o problema de selecionar um subconjunto de conexões, um subconjunto de canais de comunicações e escalonar os links nos respectivos canais tal que o \textit{throughput} da rede seja o maior possível. O segundo problema, intitulado de \textit{Minimum-Delay Variable Rate Variable Scheduling Problem}~(MD-VRBSP), busca associar um conjunto de conexões em um subconjunto de canais de comunicação para que todas conexões sejam satisfeitas utilizando o menor tempo possível. Técnicas exatas, tais como formulações de programação misto-inteira, e meta-heurísticas como \textit{Variable Neighborhood Search}~(VNS), foram utilizadas para buscar soluções ótimas ou quase ótimas para instâncias de tamanho médio e grande, respectivamente. Esse presente trabalho adotou metodologias já conhecidas na literatura para criar um conjunto de instâncias de testes para a análise dos algoritmos propostos. Tais instâncias simulam redes sem fio que podem possuir até 2048 conexões a serem escalonadas. Os experimentos computacionais sugerem que, observando os tempos de execução de cada algoritmo, a formulação mista-inteira para o VRBSP encontrou \textit{gaps} de otimalidade 19\% menores, em média, quando comparada com outros algoritmos existentes na literatura. A heurítisica VNS, que teve uma performance superior à heurísticas da literatura, atingiu limites inferiores 250,63\% melhores, em média, na maior instância, quando comparada com formulações misto-inteira da literatura. Além disso, os algoritmos exatos para o MD-VRBSP foram capazes de encontrar escalonamento ótimo para redes com até 64~conexões. Finalmente, os resultados observados para as heurísticas do MD-VRBSP sugerem que elas não foram efetivas quando comparadas com os algoritmos exatos, produzindo resultados 17,17\% piores, em média.