Modelo e algoritmos para a definição da densidade, cobertura e conectividade em uma rede de sensores sem fio
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Primeiro orientador
Membros da banca
Mauricio Cardoso de Souza
Ricardo Hiroshi Caldeira Takahashi
Ricardo Hiroshi Caldeira Takahashi
Resumo
As Redes de Sensores Sem Fio (RSSF) vêm propondo grandes desafios. Um destes desafios é o problema de cobertura, que consiste na garantia de uma qualidade de monitoramento para uma determinada área ou ambiente. Outro desafio, é o problema de controle da densidade dos nós sensores. Este problema consiste em determinar o menornúmero de nós sensores ativos dispostos em uma área de monitoramento de forma a garantir a cobertura e conectividade da rede. Este trabalho apresenta um modelo de programação linear inteira mista que tem por objetivo resolver estes problemas. Além do modelo de otimização, é proposta uma heurística baseada na utilização da Relaxação Lagrangeana e do método de sub-gradientes. Os resultados computacionais mostram que a heurística utilizada é capaz de fornecer soluções ótimas para um grande número de instâncias, além de fornecer soluções com um esforço computacional muito menor que o utilizado por pacotes de otimização como o CPLEX.
Abstract
The Wireless Sensor Networks have being carrying great challenges. One of them is the coverage problem which consists in assuring the monitoring quality for a specific area or environment. Another challenge, is to control the density of sensors. That is, from a set of sensors deployed in an area of monitoring, determine the less number of sensors that must be activated in order to guarantee the coverage and connectivity in the network. This paper presents a mixed integer linear programming model which aims to solve these problems. Besides the optimization model, it is also proposed a heuristic based on Lagrangean Relaxation and sub-gradient methods. The computational results show that the heuristic used is able to provide optimal solutions to a large range of instances. Moreover, a significant reduction in computational effort is achieved, as compared to optimization packages such as CPLEX.
Assunto
Sensores Processamento de dados, Redes de computadores Protocolos, Redes ATM, Análise de redes (Planejamento), Computação, Redes de computadores
Palavras-chave
Ciência da Computação