Use este identificador para citar ou linkar para este item: https://locus.ufv.br//handle/123456789/2663
Tipo: Dissertação
Título: Algoritmos Heurísticos para formação de clusters em redes de sensores sem fio
Título(s) alternativo(s): Heuristic algorithms for cluster formation in wireless sensors network
Autor(es): Matos, Victor de Oliveira
Primeiro Orientador: Arroyo, José Elias Cláudio
Primeiro avaliador: Gonçalves, Luciana Brugiolo
Segundo avaliador: Bastos, Leacir Nogueira
Terceiro avaliador: Santos, André Gustavo dos
Quarto avaliador: Soares, Stênio Sã Rosário Furtado
Abstract: 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.
Wireless sensor networks (WSN s) are a type of ad hoc network characterized by a large amount of sensors that have limited resources and are responsible for monitoring the enviroment and sending the collected data to a base-station. The sensors are usually small devices, inexpensive and have finite amount of energy. Thus, it is important to develop energy aware routing protocols. There are several ways to send the collected information to the base station. Routing techniques based on clusters will be the main focus of this work. Clustering consist of grouping the sensors, where some of them act as leader, known as cluster heads, which are responsible for managing the group communication. As the formation of optimal clusters in a WSN is a problem known to be NP-Hard, this paper proposes the use of the meta-heuristic GRASP to obtain efficient topologies in sensor networks based on clustering. We developed two versions of the GRASP algorithm. A version for single level topology and another version that considers multilevel topology. The algorithm for single level topology, was also tested with an intensification procedure based on the Path Relinking technique. To evaluate the performance of the algorithms, we develop a simulator that runs in cycles (or rounds). Each round determines a configuration of the network and the data transmission is made over the network. The results were compared to literature protocols, LEACH LEACH-C and EEM.
Palavras-chave: RSSF
Clusters
Heuristicas
GRASP
WSN
Clusters
Heuristics
GRASP
CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Idioma: por
País: BR
Editor: Universidade Federal de Viçosa
Sigla da Instituição: UFV
Departamento: Metodologias e técnicas da Computação; Sistemas de Computação
Programa: Mestrado em Ciência da Computação
Citação: MATOS, Victor de Oliveira. Heuristic algorithms for cluster formation in wireless sensors network. 2013. 73 f. Dissertação (Mestrado em Metodologias e técnicas da Computação; Sistemas de Computação) - Universidade Federal de Viçosa, Viçosa, 2013.
Tipo de Acesso: Acesso Aberto
URI: http://locus.ufv.br/handle/123456789/2663
Data do documento: 25-Jul-2013
Aparece nas coleções:Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
texto completo.pdf1,31 MBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.