Algoritmos Heurísticos para formação de clusters em redes de sensores sem fio - Matos, Victor de Oliveira (2013)
Redes de sensores sem fio (RSSF) são um tipo de rede ad-hoc caracterizada por sensores que possuem recursos limitados e são responsáveis por monitorar diversos tipos de ambientes e enviar os dados coletados para uma estação-base. Os sensores geralmente são dispositivos pequenos, baratos e possuem energia limitada. Desta forma, ́é importante utilizar protocolos de roteamento que gerenciam de maneira eficiente a energia dos sensores. Existem diversas maneiras para transmitir as informações coletadas para a estação-base. As técnicas de roteamento baseadas em clusters serão o foco principal deste trabalho. Clusterização consiste em agrupar os sensores, onde alguns agem como líder, conhecido como cluster head, que são responsáveis por gerenciar a comunicação do grupo. Como a formação de clusters em uma RSSF ́é um problema NP-Difícil, neste trabalho ́é proposto o uso da meta-heurística GRASP para obter configuraações eficientes de redes de sensores baseados em clusterização. Foram desenvolvidos duas versões do algoritmo GRASP, uma versão para topologia de de um único nível e a outra versão que considera uma topologia multinível. No algoritmo para topologia de nível simples, foi testado também um procedimento de intensificação baseada na técnica Path Relinking. Para avaliar o desempenho dos algoritmos, foi desenvolvido um simulador que ́ e executado em ciclos (ou rounds). A cada round determina-se uma configura ̧ c ̃ ao da rede e em seguida ́ e feita a transmissão de dados pela rede. Os resultados obtidos foram comparados com os protocolos da literatura, LEACH, LEACH-C e EEMC.