Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/1843/BUBD-9K9MK5
Tipo: | Dissertação de Mestrado |
Título: | Modelo e algoritmos para a definição da densidade, cobertura e conectividade em uma rede de sensores sem fio |
Autor(es): | Gutavo Campos Menezes |
Primeiro Orientador: | Geraldo Robson Mateus |
Primeiro membro da banca : | Mauricio Cardoso de Souza |
Segundo membro da banca: | 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 |
Idioma: | Português |
Editor: | Universidade Federal de Minas Gerais |
Sigla da Instituição: | UFMG |
Tipo de Acesso: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/BUBD-9K9MK5 |
Data do documento: | 13-Ago-2004 |
Aparece nas coleções: | Dissertações de Mestrado |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
dissertacao_gustavocamposmenezes.pdf | 1.75 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.