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.
|
