Busca avançada
Ano de início
Entree


Algoritmos para o problema da cobertura por sensores

Texto completo
Autor(es):
Rafael da Ponte Barbosa
Número total de Autores: 1
Tipo de documento: Dissertação de Mestrado
Imprenta: São Paulo.
Instituição: Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI)
Data de defesa:
Membros da banca:
Yoshiko Wakabayashi; Gordana Manic
Orientador: Yoshiko Wakabayashi
Resumo

Neste trabalho estudamos aspectos algorítmicos do Problema da Cobertura por Sensores. Em linhas gerais, este problema a entrada consiste em uma região a ser monitorada por um conjunto de sensores previamente posicionados, cada qual dotado de bateria com duração limitada, e o objetivo é atribuir a cada sensor um tempo de início, de modo que toda a região seja coberta o maior tempo possível. Focamos nosso estudo no caso unidimensional do problema, chamado Problema da Cobertura de Faixa Restrita, no qual a região a ser monitorada é um intervalo (da reta real). Estudamos diversas variantes, de acordo com os subintervalos que os sensores cobrem (se de tamanhos fixos ou variados), e de acordo com a duração das baterias (se uniformes ou não). Estudamos também o caso preemptivo: quando os sensores podem ser ligados mais de uma vez. Para este último caso, projetamos um algoritmo polinomial bem simples. O Problema da Cobertura de Faixa Restrita é NP-difícil no caso não-preemptivo em que os sensores têm bateria de duração variável. Para este caso, em 2009 Gibson e Varadarajan apresentaram um algoritmo polinomial que provaram ser uma 5-aproximação. Provamos que este algoritmo tem fator de aproximação 4, e mostramos que este fator é justo. Apresentamos também formulações lineares inteiras para este caso, e os resultados computacionais obtidos. (AU)

Processo FAPESP: 09/03589-0 - Algoritmos para problemas sobre cobertura por sensores.
Beneficiário:Rafael da Ponte Barbosa
Modalidade de apoio: Bolsas no Brasil - Mestrado