Hiper-heurística de geração aplicada ao problema do posicionamento automático de pontos de acesso de redes sem fio em ambientes internos

Abstract

O projeto de redes sem fio tem se tornado cada vez mais relevante nos últimos anos. Com o advento da popularização de dispositivos de Internet das Coisas e 5G, este assunto tem tomado ainda mais relevância, devido aos custos relacionados à instalação deste tipo de projeto. Ao modelar o projeto destas redes como o Problema de Posicionamento de Pontos de Acesso, pode-se verificar que é um problema de natureza NP-Difícil e, portanto, ainda não possui um algoritmo que resolva o problema em tempo polinomial. Este trabalho propõe uma solução para o problema baseada em uma hiper-heurística de geração, na qual cada solução é acompanhada de uma heurística nova que pode ser reutilizada para novas instâncias. São utilizadas instâncias randômicas para redes sem fio com dimensões relevantes para o trabalho. É realizada uma comparação dos resultados das execuções destas instâncias com uma abordagem de meta-heurística. Os experimentos computacionais apontam excelentes resultados para dimensões maiores, de maneira a demonstrar que esta abordagem consegue ser mais escalável e produzir soluções razoáveis para o problema.