Modelos e heurísticas para o problema de controle de densidade em redes de sensores sem fio planas - Penaranda, Adriana Gomes (Universidade Federal do Amazonas, 2015)
As Redes de Sensores Sem Fios (RSSFs) são redes compostas por um grande número de nós de sensores. Estas redes necessitam de controle de densidade para garantir um melhor funcionamento, pois a alta concentração de nós sensores gera colisão de dados, interferências e consequentemente retransmissão de dados. Os nós sensores possuem limitações de energia, processamento e comunicação e por isto é interessante otimizar o consumo de energia da rede com o objetivo de estender seu tempo de vida. Esquemas de controle de densidade têm sido utilizados como recursos para prolongar o tempo de vida da rede. O Problema de Controle de Densidade em Redes de Sensores Sem Fios (PCD-RSSFs) consiste em minimizar a energia consumida pelos nós sensores ativos, escolhendo um subconjunto de nós que atenda os requisitos da aplicação e maximize a utilização dos recursos da rede. Este trabalho apresenta duas abordagens para tratar o PCD-RSSFs: Periódica e Multiperíodo. A Abordagem Periódica escolhe a melhor solução para um dado período, tendo uma visão local do tempo de vida da rede e repete este procedimento periodicamente. A Abordagem Multiperíodo consiste em definir um tempo esperado de vida da rede e dividí-lo em períodos. Para cada período a solução é escolhida levando em consideração os outros períodos, caracterizando uma visão global do tempo de vida da rede e dos períodos. Ambas as abordagens foram modeladas com Programação Linear Inteira e resolvidas por um software de otimização. Para a modelagem da Abordagem Periódica é proposta uma Relaxação Lagrangeana em conjunto com uma Heurística Lagrangeana onde a ideia é relaxar restrições difíceis com o intuito de deixar o problema mais simples de ser resolvido. Também é apresentado um Algoritmo Genético (AG) híbrido que utiliza Abordagem Periódica para gerar a solução de cada período e em seguida uma fase de refinamento baseada nos conceitos da Abordagem Multiperíodo. As heurísticas implementadas são comparadas com algoritmos da literatura e os resultados mostram que a combinação Relaxação Lagrangeana e Heurística Lagrangeana obtêm melhor desempenho tanto em consumo de energia quanto em tempo de solução. Além disso a Relaxação Lagrangeana gera limites inferiores para o PCD-RSSFs que podem ser utilizados para avaliação de outros algoritmos de controle de Densidade