Please use this identifier to cite or link to this item: http://hdl.handle.net/1843/ESBF-AAYNSS
Type: Tese de Doutorado
Title: Algoritmos para controle de densidade em redes de sensores sem fio
Authors: Fabiola Pereira da Silva Guerra
First Advisor: Geraldo Robson Mateus
First Referee: Luiz Satoru Ochi
Second Referee: Markus Endler
Third Referee: Ricardo Hiroshi Caldeira Takahashi
metadata.dc.contributor.referee4: Antonio Alfredo Ferreira Loureiro
Abstract: O Controle de Densidade Dinâmico em Redes de Sensores sem Fio é uma das maneiras mais exploradas para se utilizar os recursos escassos dessas redes de forma eficiente e contribuir para aumentar seu tempo de vida. Neste trabalho os modelos e algoritmos propostos para controle de densidade devem garantir a cobertura da área demonitoramento e a conectividade entre os nós ativos, minimizando aenergia consumida pelos nós. O problema é abordado de duas maneiras: multi-período e periódica. As duas abordagens se complementam e contribuem para o desenvolvimento de uma ou mais soluções que melhor se adaptem à realidade das redes de sensores. Entre as estratégias utilizadas no trabalho destacam-se modelos de Programação Linear Inteira, Relaxação e Heurística Lagrangeanas e Heurísticas.
Abstract: Density Control is an effective way towards the efficient resource usage and lifetime extension in wireless sensor networks. In this work, the models and algorithms proposed for density control aims at guaranteeing coverage and connectivity, while minimizing the overall energy consumption and takes into account the battery capacity of the nodes. The Density Control Problem (DCP) is addressed by using two different approaches: Multiperiod and Periodic. The Multiperiod Approach is a density control scheme that primarily divides the expected network lifetime in time periods, which may or may not have the same duration.The approach calculates, in a global way, a solution for the density control problem at each period, respecting the battery capacity of the node. Given the global aspect of the approach regarding the available nodes and the network lifetime, the optimal solution provides a network configuration that has the best coverage possible with the minimum overall energy consumption. Hence, a multiperiod solution could provide a lower bound for periodic density control schemes. TheMultiperiod Density Control Problem (MDCP) is modeled as a Integer Linear Programming (ILP) Problem and is solved by a commercial optimization package. However, the MDCP is a combinatorial problem which means large instances may not be solved at reasonable time. Then, we use different optimization techniques, such as Lagrangian Relaxation and Lagrangian Heuristics to address the problem. Results show that the Lagrangian Relaxationderives good lower bounds. The Lagrangian Heuristics is a good choice to generates aviable solution, that in some cases is very close the optimal solution, regarding the objectivefunction. The Periodic Approach is proposed as an alternative to the MDCP and consists infinding the optimal solution for the DCP in a given time and to repeat this procedure periodically.We model the Periodic Density Control Problem (PDCP) as a ILP problem withtwo objective functions, one that minimizes the energy consumption and other that minimizesthe ratio between the energy consumption and the residual energy of the nodes. Giventhe combinatorial nature of the model, for small instances, we generate the solutions witha commercial optimization package and for large instances we propose a Hybrid Algorithm(HA), that combines global and local strategies, to derive the solutions. Results show that,compared to the optimal solution of the model, the HA generates good solutions, consideringboth the quality of the solution and the execution time. Additional results include analysisof the sink node position into the network lifetime, advantages and disadvantages of eachobjective function, and compare the two density control approaches.
Subject: Computação
language: Português
Publisher: Universidade Federal de Minas Gerais
Publisher Initials: UFMG
Rights: Acesso Aberto
URI: http://hdl.handle.net/1843/ESBF-AAYNSS
Issue Date: 4-Feb-2010
Appears in Collections:Teses de Doutorado

Files in This Item:
File Description SizeFormat 
fabiolaguerranakamura.pdf2.41 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.