Made available in DSpace on 2015-04-11T14:02:46Z (GMT). No. of bitstreams: 1
Adriana Gomes Penaranda.pdf: 2772639 bytes, checksum: e4d23c72018fc1400d20f9996f6aacc1 (MD5)
Previous issue date: 2013-03-01 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / 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. / 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
| Identifer | oai:union.ndltd.org:IBICT/oai:http://localhost:tede/2905 |
| Date | 01 March 2013 |
| Creators | Penaranda, Adriana Gomes |
| 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.0025 seconds