Loading...
Please wait, while we are loading the content...
Similar Documents
Heurísticas para o problema de cobertura em redes de sensores sem fio hierárquicas com sorvedouro móvel
| Content Provider | Semantic Scholar |
|---|---|
| Author | Araujo, Andre Ricardo Melo |
| Copyright Year | 2013 |
| Abstract | As Redes de Sensores Sem Fio (RSSFs) sao um tipo especial de redes ad hoc constituidas por dispositivos capazes de processar, armazenar, sensoriar o ambiente e transmitir dados via interface de comunicacao sem fio, denominados nos sensores. Os nos sensores possuem varias limitacoes, 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 nos sensores. Este trabalho tem como objetivo tratar o Problema de Cobertura, Agrupamento e Roteamento com Sorvedouro Movel (PCAR-SM) em RSSF com no sorvedouro movel, que consiste em: dado um conjunto de nos sensores e uma area de monitoramento, desenvolver algoritmos para encontrar o melhor subconjunto de nos sensores que cubra a area de monitoramento, junta-los no menor numero de grupos possiveis e encontrar a menor rota para um no sorvedouro movel percorrer. O PCAR-SM e uma estrategia utilizada para diminuir o consumo de energia dos nos sensores, a colisao de dados, as interferencias e os dados redundantes em redes com alta concentracao de nos sensores por area. A proposta deste trabalho e resolver cada problema separadamente e em conjunto, de modo a avaliar o impacto de cada problema na solucao do outro. O Problema de Cobertura foi resolvido com duas metaheuristicas: um Algoritmo Genetico (AG) e um algoritmo Greedy Randomized Adaptive Search Procedure (GRASP). Neste ultimo foram utilizadas duas representacoes de solucao: (a) representacao por sensor, onde cada elemento do vetor de solucao representa um no sensor que estara ligado ou desligado; (b) representacao por demanda, onde cada elemento do vetor de solucao representa um ponto de demanda no qual indicara qual o no sensor o cobre. O AG utiliza apenas a representacao por demanda. Os resultados computacionais para o Problema de Cobertura utilizaram o benchmark da Beasley s OR Library e foi possivel constatar que o GRASP com representacao por demanda obteve melhores resultados que o AG e o GRASP com representacao por sensor quando o criterio de otimizacao e minimizar a soma total dos custos de cada no sensor utilizado na solucao. Para o Problema de Agrupamento foi criada uma abordagem de grades virtuais. Nesta abordagem dividimos a area em grades e os grupos sao formados por um conjunto de grades adjacentes (no maximo 5 grades) formando um esquema de cruz. O objetivo do problema e minimizar o numero de grupos na area. A partir desta abordagem, pode-se modelar o Problema de Agrupamento como um Problema de Cobertura de Conjuntos (PCC) sem sobreposicao (um elemento nao pertence a mais de um conjunto), que foi tratada por uma heuristica gulosa denominada Greedy Clustering Algorithm (GCA). Os grades virtuais provou ser uma boa solucao por ser simples para um no identificar a qual grade ele pertence. Sua simplicidade ainda o torna uma metodo adequado para uma versao distribuida. O Problema de Roteamento do no sorvedouro foi modelado como o Problema do Caixeiro Viajante (PCV), onde o no sorvedouro movel parte de um canto da area de monitoramento, percorre a area visitando todos os grupos e retorna ao ponto inicial. Para isto, propomos duas abordagens gulosas baseadas no vizinho mais proximo, o Routing Greedy Algorithm - Center (RGA-C) e o Routing Greedy Algorithm - Border (RGA-B). A rota do no sorvedouro tambem foi resolvida por uma heuristica baseada no algoritmo Centralized Spatial Partitioning (CSP). Na abordagem CSP, a rota e fixa e lembra o movimento de uma cobra. Os resultados mostram que a rota fixa gera um percurso com tamanho menor em comparacao com as heuristicas gulosas para o PCV. Analisamos, ainda, o PCAR-SM, criando estrategias heuristicas. Auniao dos Problema de Agrupamento e Roteamento, provou ser mais benefica em relacao ao tamanho da rota do no sorvedouro, ja a uniao do Problema de Cobertura com o Problema de Agrupamento so mostrou ser benefica quando o raio de comunicacao era aproximadamente 3, 9 vezes maior que o raio de sensoriamento. Nossos resultados, mostram que resolver os problemas em conjunto permite que algumas mudancas nos algoritmos levem a melhores resultados. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://tede.ufam.edu.br/bitstream/tede/2906/1/Disserta%C3%A7%C3%A3o%20-%20Andr%C3%A9%20Ricardo%20Melo%20Ara%C3%BAjo.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
