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

Detalhes bibliográficos
Ano de defesa: 2019
Autor(a) principal: José Maurício Costa
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
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
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://hdl.handle.net/1843/31229
Resumo: 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.