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.
| Identifer | oai:union.ndltd.org:IBICT/oai:http://localhost:tede/2906 |
| Date | 01 March 2013 |
| Creators | Araújo, André Ricardo Melo |
| Contributors | Nakamura, Fabíola Guerra |
| Publisher | Universidade Federal do Amazonas, Programa de Pós-graduação em Informática, UFAM, BR, Instituto de Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFAM, instname:Universidade Federal do Amazonas, instacron:UFAM |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | -312656415484870643, 600 |
Page generated in 0.0071 seconds