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

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.