Discente: Diego Rodrigues Moreira Totte
Título: Comparação entre Métodos Exato e Heurístico para o Problema de Alocação de Sensores em Redes de Sensores Sem Fio
Orientadores: Laura Assis e Felipe Henriques
Banca: Laura Assis (CEFET/RJ), Felipe Henriques (CEFET/RJ), Pedro González (CEFET/RJ), Michel Tcheou (UERJ)
Dia/hora: 23 de maio de 2023, às 13:30h.
Resumo: Redes de Sensores Sem Fio (RSSFs) estao cada vez mais presentes na sociedade, sejam em casas, carros, fabricas ou em apoio a resgates e preservação ambiental. Varios métodos de otimização ao propostos na literatura a fim de alocar os nós sensores de forma a melhorar o desempenho da rede, considerando um ou mais objetivos. Contudo, grande parte dos estudos neste tema sao realizados com métodos heuríısticos, os quais nao possuem garantia de otimalidade, fato previsto dado que abordagens exatas, devido à complexidade envolvida na garantia da solução ótima, geralmente não resolvem instância de grande porte. Nesta pesquisa, sao propostas duas abordagens de solução para o Problema de Alocação de Sensores (PAS) com objetivo de minimizar o custo energético geral da rede: a primeira e um método exato usando Programação Linear Inteira Mista (PLIM), e a segunda um metodo heurístico baseado nos conceitos de Algoritmos Geneticos (AGs). Os resultados obtidos mostraram que a abordagem exata alcançou resultados ótimos para o PAS considerando instancias de pequeno, médio e grande portes. Por sua vez, o AG gerou resultados sub-otimos para quase o dobro de instâncias que a abordagem exata, no mesmo período de tempo. Foram utilizadas instancias de formatos regulares, semirregular e irregulares.
