Formulações e heurísticas para o problema de escalonamento de conexões com múltiplas velocidades de transmissão e em canais com largura de banda variável

• Ano de defesa: 2019
• Autor(a) principal: José Maurício Costa
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Minas Gerais; Brasil; ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO; Programa de Pós-Graduação em Ciência da Computação; UFMG
• Palavras-chave em Português: Problema de escalonamento em redes sem fio; Programação inteira; Heurísticas; Otimização; Combinatória
• Link de acesso: http://hdl.handle.net/1843/31229

The IEEE 802.11ac standard enables a higher transmission speed than the previous IEEE 802.11 standards, because it implements several improvements like the adoption of the MU-MIMO (Multi-User Mutiple-Input Multiple-Output) method and the increasing of the number of spatial streams to send data, as well the utilization of larger communication channels. The IEEE 802.11ac allows the network frequency spectrum to be divided into communication channels with different bandwidths, varying from 20 MHz to 160 MHz. In this work, we introduce the Variable Rate and Variable Bandwidth Scheduling Problem (VRBSP), which is a generalization of the classical Variable Rate Scheduling Problem (VRSP) on wireless networks. We propose two Mixed Integer Linear Programming (MILP) formulations to model the VRBSP. These two formulations are used within a MILP solver to seek optimal VRBSP schedules for small-sized networks. This approach can also be used to solve VRSP. As VRBSP is NP-Hard, we also propose a Biased Random-Key Genetic Algorithm (BRKGA) and a Variable Neighborhood Search (VNS) heuristic to find near optimal VRBSP solutions for medium-sized and large-sized networks. The computational experiments were carried out on classical network instances from the literature with up to 2048 links. They show that the best heuristic results were obtained by VNS, and that the MILP-based exact algorithms were able to find optimal VRBSP schedules for networks with up to 256 links and optimal VRSP schedules for networks with up to 1024 links.