Modelos e heurísticas para o problema de controle de densidade em redes de sensores sem fio planas
As Redes de Sensores Sem Fios (RSSFs) são redes compostas por um grande número de nós de sensores. Estas redes necessitam de controle de densidade para garantir um melhor funcionamento, pois a alta concentração de nós sensores gera colisão de dados, interferências e consequentemente retransmissão...
| Autor principal: | Penaranda, Adriana Gomes |
|---|---|
| Outros Autores: | http://lattes.cnpq.br/4084986262246373 |
| Grau: | Dissertação |
| Idioma: | por |
| Publicado em: |
Universidade Federal do Amazonas
2015
|
| Assuntos: | |
| Acesso em linha: |
http://tede.ufam.edu.br/handle/tede/2905 |
| id |
oai:https:--tede.ufam.edu.br-handle-:tede-2905 |
|---|---|
| recordtype |
dspace |
| spelling |
oai:https:--tede.ufam.edu.br-handle-:tede-29052016-05-11T14:30:33Z Modelos e heurísticas para o problema de controle de densidade em redes de sensores sem fio planas Penaranda, Adriana Gomes Nakamura, Fabíola Guerra http://lattes.cnpq.br/4084986262246373 http://lattes.cnpq.br/9615041048900531 Redes de sensores sem fios Problema de controle de densidade Relaxação lagrangeana Programação linear inteira Wireless sensor networks Density control problem Lagrangean relaxation Integer linear programming CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO As Redes de Sensores Sem Fios (RSSFs) são redes compostas por um grande número de nós de sensores. Estas redes necessitam de controle de densidade para garantir um melhor funcionamento, pois a alta concentração de nós sensores gera colisão de dados, interferências e consequentemente retransmissão de dados. Os nós sensores possuem limitações de energia, processamento e comunicação e por isto é interessante otimizar o consumo de energia da rede com o objetivo de estender seu tempo de vida. Esquemas de controle de densidade têm sido utilizados como recursos para prolongar o tempo de vida da rede. O Problema de Controle de Densidade em Redes de Sensores Sem Fios (PCD-RSSFs) consiste em minimizar a energia consumida pelos nós sensores ativos, escolhendo um subconjunto de nós que atenda os requisitos da aplicação e maximize a utilização dos recursos da rede. Este trabalho apresenta duas abordagens para tratar o PCD-RSSFs: Periódica e Multiperíodo. A Abordagem Periódica escolhe a melhor solução para um dado período, tendo uma visão local do tempo de vida da rede e repete este procedimento periodicamente. A Abordagem Multiperíodo consiste em definir um tempo esperado de vida da rede e dividí-lo em períodos. Para cada período a solução é escolhida levando em consideração os outros períodos, caracterizando uma visão global do tempo de vida da rede e dos períodos. Ambas as abordagens foram modeladas com Programação Linear Inteira e resolvidas por um software de otimização. Para a modelagem da Abordagem Periódica é proposta uma Relaxação Lagrangeana em conjunto com uma Heurística Lagrangeana onde a ideia é relaxar restrições difíceis com o intuito de deixar o problema mais simples de ser resolvido. Também é apresentado um Algoritmo Genético (AG) híbrido que utiliza Abordagem Periódica para gerar a solução de cada período e em seguida uma fase de refinamento baseada nos conceitos da Abordagem Multiperíodo. As heurísticas implementadas são comparadas com algoritmos da literatura e os resultados mostram que a combinação Relaxação Lagrangeana e Heurística Lagrangeana obtêm melhor desempenho tanto em consumo de energia quanto em tempo de solução. Além disso a Relaxação Lagrangeana gera limites inferiores para o PCD-RSSFs que podem ser utilizados para avaliação de outros algoritmos de controle de Densidade Wireless Sensor Networks (WSNs) are composed of a large number of sensor nodes. These networks require density control to ensure a better functioning because the high concentration of sensor nodes generates collision data, interference, and retransmittions. In addition, sensor nodes have limited energy, processing, and communication, therefore is interesting to optimize the energy consumption of the network in order to extend its lifetime. Density control schemes have been used to prolong the network lifetime. The Density Control Problem in Wireless Sensor Networks (DCP-WSNs) minimizes the energy consumed by the sensor nodes active, choosing a subset of sensor nodes that meets the application requirements and maximize the use of network resources. This paper presents two approaches to treat DCP-WSN: Periodic and Multiperiod. The Periodic Approach always chooses the best solution for a given period, having a local view of the network lifetime and repeats this proceduce periodically. The Multiperiod Approach defines an expected life time of the network and divide it into periods. For each period the solution is chosen taking into consideration the other periods, thus with an global view of the network lifetime and periods. Both approaches are modeled with Integer Linear Programming and solved by an optimization software. For the Periodic Approach model is proposed a Lagrangean Relaxation with a Lagrangean Heuristic which relax difficults constraints in order to make the problem easier to be solved. We also present a Genetic Algorithm Hybrid (GA) which uses the Periodic Approach to generate the solution of each period and execute a refinement stage based on concepts of the Multiperiod Approach. The proposed heuristics are compared with algorithms of the literature and results show that the Lagrangean Relaxation and Heuristic reach better energy consumption and solution time. Furthermore the Lagrangean relaxation generates lower bounds for the DCP-WSN that may be used to evaluate other algorithms Density Control. FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas 2015-04-11T14:02:46Z 2013-11-06 2013-03-01 Dissertação PENARANDA, Adriana Gomes. Modelos e heurísticas para o problema de controle de densidade em redes de Sensores sem fio planas. 2013. 70 f. Dissertação (Mestrado em Informática) - Universidade Federal do Amazonas, Manaus, 2013. http://tede.ufam.edu.br/handle/tede/2905 por Acesso Aberto application/pdf Universidade Federal do Amazonas Instituto de Computação BR UFAM Programa de Pós-graduação em Informática |
| institution |
TEDE - Universidade Federal do Amazonas |
| collection |
TEDE-UFAM |
| language |
por |
| topic |
Redes de sensores sem fios Problema de controle de densidade Relaxação lagrangeana Programação linear inteira Wireless sensor networks Density control problem Lagrangean relaxation Integer linear programming CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO |
| spellingShingle |
Redes de sensores sem fios Problema de controle de densidade Relaxação lagrangeana Programação linear inteira Wireless sensor networks Density control problem Lagrangean relaxation Integer linear programming CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Penaranda, Adriana Gomes Modelos e heurísticas para o problema de controle de densidade em redes de sensores sem fio planas |
| topic_facet |
Redes de sensores sem fios Problema de controle de densidade Relaxação lagrangeana Programação linear inteira Wireless sensor networks Density control problem Lagrangean relaxation Integer linear programming CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO |
| description |
As Redes de Sensores Sem Fios (RSSFs) são redes compostas por um grande número
de nós de sensores. Estas redes necessitam de controle de densidade para garantir um
melhor funcionamento, pois a alta concentração de nós sensores gera colisão de dados,
interferências e consequentemente retransmissão de dados. Os nós sensores possuem
limitações de energia, processamento e comunicação e por isto é interessante otimizar o
consumo de energia da rede com o objetivo de estender seu tempo de vida. Esquemas
de controle de densidade têm sido utilizados como recursos para prolongar o tempo de
vida da rede. O Problema de Controle de Densidade em Redes de Sensores Sem Fios
(PCD-RSSFs) consiste em minimizar a energia consumida pelos nós sensores ativos,
escolhendo um subconjunto de nós que atenda os requisitos da aplicação e maximize a
utilização dos recursos da rede. Este trabalho apresenta duas abordagens para tratar
o PCD-RSSFs: Periódica e Multiperíodo. A Abordagem Periódica escolhe a melhor
solução para um dado período, tendo uma visão local do tempo de vida da rede e repete
este procedimento periodicamente. A Abordagem Multiperíodo consiste em definir um
tempo esperado de vida da rede e dividí-lo em períodos. Para cada período a solução é
escolhida levando em consideração os outros períodos, caracterizando uma visão global
do tempo de vida da rede e dos períodos. Ambas as abordagens foram modeladas
com Programação Linear Inteira e resolvidas por um software de otimização. Para
a modelagem da Abordagem Periódica é proposta uma Relaxação Lagrangeana em
conjunto com uma Heurística Lagrangeana onde a ideia é relaxar restrições difíceis
com o intuito de deixar o problema mais simples de ser resolvido. Também é apresentado
um Algoritmo Genético (AG) híbrido que utiliza Abordagem Periódica para
gerar a solução de cada período e em seguida uma fase de refinamento baseada nos
conceitos da Abordagem Multiperíodo. As heurísticas implementadas são comparadas
com algoritmos da literatura e os resultados mostram que a combinação Relaxação
Lagrangeana e Heurística Lagrangeana obtêm melhor desempenho tanto em consumo
de energia quanto em tempo de solução. Além disso a Relaxação Lagrangeana gera
limites inferiores para o PCD-RSSFs que podem ser utilizados para avaliação de outros algoritmos de controle de Densidade |
| author_additional |
Nakamura, Fabíola Guerra |
| author_additionalStr |
Nakamura, Fabíola Guerra |
| format |
Dissertação |
| author |
Penaranda, Adriana Gomes |
| author2 |
http://lattes.cnpq.br/4084986262246373 |
| author2Str |
http://lattes.cnpq.br/4084986262246373 |
| title |
Modelos e heurísticas para o problema de controle de densidade em redes de sensores sem fio planas |
| title_short |
Modelos e heurísticas para o problema de controle de densidade em redes de sensores sem fio planas |
| title_full |
Modelos e heurísticas para o problema de controle de densidade em redes de sensores sem fio planas |
| title_fullStr |
Modelos e heurísticas para o problema de controle de densidade em redes de sensores sem fio planas |
| title_full_unstemmed |
Modelos e heurísticas para o problema de controle de densidade em redes de sensores sem fio planas |
| title_sort |
modelos e heurísticas para o problema de controle de densidade em redes de sensores sem fio planas |
| publisher |
Universidade Federal do Amazonas |
| publishDate |
2015 |
| url |
http://tede.ufam.edu.br/handle/tede/2905 |
| _version_ |
1831969069647003648 |
| score |
11.753735 |