Algoritmos Heurísticos para formação de clusters em redes de sensores sem fio

• Ano de defesa: 2013
• Autor(a) principal: Matos, Victor de Oliveira
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Viçosa; BR; Metodologias e técnicas da Computação; Sistemas de Computação; Mestrado em Ciência da Computação; UFV
• Palavras-chave em Português: RSSF; Clusters; Heuristicas; GRASP; WSN; Heuristics; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://locus.ufv.br/handle/123456789/2663

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.