Made available in DSpace on 2015-04-11T14:02:47Z (GMT). No. of bitstreams: 1 Andre Ricardo Melo Araujo.pdf: 3722790 bytes, checksum: 1876d821e1e927795304f1c1ee7bbb67 (MD5) Previous issue date: 2013-03-01 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / Wireless Sensor Network (WSN) is a special kind of ad hoc networks composed of devices capable of processing, storing, sensing the environment, and transmitting data via wireless communication interface. The sensor nodes have several limitations, among them the capacity of energy because to the reduced size. For this reason, many searches have been done with a view to improving the energy consumption of sensor nodes. This work aims to address the Problem of Coverage, Clustering and Routing with Mobile Sink (PCAR-SM, in portuguese Problema de Cobertura, Agrupamento e Roteamento com Sorvedouro Móvel) in WSN with mobile sink consisting of: given a set of sensor nodes and a monitoring area, develop algorithms to find the best subset of sensor nodes to cover the monitoring area, group them in a smaller number of clusters and find the shortest route to mobile sink navigate. The PCAR-SM is a strategy used to reduce the energy consumption of sensor nodes, data collisions, interference and redundant data in networks with high concentration of sensor nodes per area. The purpose of this paper is to solve each problem separately and together, in order to evaluate the impact of each problem on the other. The Coverage Problem has been solved with two metaheuristics: an Genetic Algorithm (GA) and a Greedy Randomized Adaptive Search Procedure (GRASP) algorithm. In the latter we used two representations of solution: (a) representation by sensor, where each element of the solution vector represents a sensor node that must be switched on or off; (b) representation by demand, where each element of the solution vector represents a demand point will indicate which sensor node cover it. The AG uses only the representation by demand. The computational results for Coverage Problem used the benchmark of Beasley s OR Library and it was possible seen that the GRASP with representation by demand achieved better results than the GA and the GRASP with representation by sensor when the optimization criterion is to minimize the total cost of each sensor node used in the solution. For Clustering Problem was created approach of virtual grids. In this approach, we divide the area into grids and clusters are formed by a set of adjacent grids (maximum 5 grids in group) forming a cross schematic. The aim of the problem is to minimize the number of clusters in the area. With this approach, we can model the Clustering Problem as a Set Cover Problem (SCP) without overlapping (an element does not belong to more than one set), which was treated by a greedy heuristic called Greedy Clustering Algorithm (GCA). The virtual grids proved to be a good solution because it is simple to identify a node which grid it belongs. Its simplicity also makes it a appropriate method for a distributed version. The Routing Problem of sink was modeled as the Travelling Salesman Problem (TSP), where the mobile sink part of a corner of the monitoring area, runs through the area visiting all clusters and returns to the starting point. For this, we propose two greedy approaches based on nearest neighbor, the Routing Greedy Algorithm - Center (RGA-C) and Routing Greedy Algorithm - Border (RGA-B). The route of the sink was also solved by a heuristic based on algorithm Centralized Spatial Partitioning (CSP). In CSP approach, the route is fixed and reminds the movement of a snake. The results show that fixed route produces a path with smaller size compared to the greedy heuristic for TSP. We analyze also the PCAR-SM, creating heuristic strategies. The union of the Clustering Problem and Routing Problem proved more beneficial in relation to the size of the sink s route. The union of Coverage Problem and Clustering Problem only proved beneficial when the communication radius was about 3,9 times greater than the sensing radius. Our results show that solve problems together allows some changes in the algorithms will lead to better results. / As Redes de Sensores Sem Fio (RSSFs) são um tipo especial de redes ad hoc constituídas por dispositivos capazes de processar, armazenar, sensoriar o ambiente e transmitir dados via interface de comunicação sem fio, denominados nós sensores. Os nós sensores possuem várias limitações, dentre elas, a capacidade de energia devido ao tamanho reduzido. Por isto, muitas pesquisas foram feitas tendo em vista a melhoria no consumo de energia dos nós sensores. Este trabalho tem como objetivo tratar o Problema de Cobertura, Agrupamento e Roteamento com Sorvedouro Móvel (PCAR-SM) em RSSF com nó sorvedouro móvel, que consiste em: dado um conjunto de nós sensores e uma área de monitoramento, desenvolver algoritmos para encontrar o melhor subconjunto de nós sensores que cubra a área de monitoramento, juntá-los no menor número de grupos possíveis e encontrar a menor rota para um nó sorvedouro móvel percorrer. O PCAR-SM é uma estratégia utilizada para diminuir o consumo de energia dos nós sensores, a colisão de dados, as interferências e os dados redundantes em redes com alta concentração de nós sensores por área. A proposta deste trabalho é resolver cada problema separadamente e em conjunto, de modo a avaliar o impacto de cada problema na solução do outro. O Problema de Cobertura foi resolvido com duas metaheurísticas: um Algoritmo Genético (AG) e um algoritmo Greedy Randomized Adaptive Search Procedure (GRASP). Neste último foram utilizadas duas representações de solução: (a) representação por sensor, onde cada elemento do vetor de solução representa um nó sensor que estará ligado ou desligado; (b) representação por demanda, onde cada elemento do vetor de solução representa um ponto de demanda no qual indicará qual o nó sensor o cobre. O AG utiliza apenas a representação por demanda. Os resultados computacionais para o Problema de Cobertura utilizaram o benchmark da Beasley s OR Library e foi possível constatar que o GRASP com representação por demanda obteve melhores resultados que o AG e o GRASP com representação por sensor quando o critério de otimização é minimizar a soma total dos custos de cada nó sensor utilizado na solução. Para o Problema de Agrupamento foi criada uma abordagem de grades virtuais. Nesta abordagem dividimos a área em grades e os grupos são formados por um conjunto de grades adjacentes (no máximo 5 grades) formando um esquema de cruz. O objetivo do problema é minimizar o número de grupos na área. A partir desta abordagem, pode-se modelar o Problema de Agrupamento como um Problema de Cobertura de Conjuntos (PCC) sem sobreposição (um elemento não pertence a mais de um conjunto), que foi tratada por uma heurística gulosa denominada Greedy Clustering Algorithm (GCA). Os grades virtuais provou ser uma boa solução por ser simples para um nó identificar a qual grade ele pertence. Sua simplicidade ainda o torna uma método adequado para uma versão distribuída. O Problema de Roteamento do nó sorvedouro foi modelado como o Problema do Caixeiro Viajante (PCV), onde o nó sorvedouro móvel parte de um canto da área de monitoramento, percorre a área visitando todos os grupos e retorna ao ponto inicial. Para isto, propomos duas abordagens gulosas baseadas no vizinho mais próximo, o Routing Greedy Algorithm - Center (RGA-C) e o Routing Greedy Algorithm - Border (RGA-B). A rota do nó sorvedouro também foi resolvida por uma heurística baseada no algoritmo Centralized Spatial Partitioning (CSP). Na abordagem CSP, a rota é fixa e lembra o movimento de uma cobra. Os resultados mostram que a rota fixa gera um percurso com tamanho menor em comparação com as heurísticas gulosas para o PCV. Analisamos, ainda, o PCAR-SM, criando estratégias heurísticas. Aunião dos Problema de Agrupamento e Roteamento, provou ser mais benéfica em relação ao tamanho da rota do nó sorvedouro, já a união do Problema de Cobertura com o Problema de Agrupamento só mostrou ser benéfica quando o raio de comunicação era aproximadamente 3, 9 vezes maior que o raio de sensoriamento. Nossos resultados, mostram que resolver os problemas em conjunto permite que algumas mudanças nos algoritmos levem a melhores resultados.