@MASTERSTHESIS{ 2013:1443729735,
 	title = {Heur?sticas para o problema de cobertura em redes de sensores sem fio hier?rquicas com sorvedouro m?vel},
 	year = {2013},
 	url = "http://tede.ufam.edu.br/handle/tede/2906",
 	abstract = "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.",
 	publisher = {Universidade Federal do Amazonas},
 	scholl = {Programa de P?s-gradua??o em Inform?tica},
 	note = {Instituto de Computa??o}
}