Ver registro no DEDALUS
Exportar registro bibliográfico

Algoritmos para o problema da cobertura por sensores (2011)

  • Authors:
  • USP affiliated authors: BARBOSA, RAFAEL DA PONTE - IME
  • USP Schools: IME
  • Subjects: OTIMIZAÇÃO COMBINATÓRIA
  • Language: Português
  • Abstract: 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.
  • Imprenta:
  • Data da defesa: 12.12.2011

  • Exemplares físicos disponíveis nas Bibliotecas da USP
    BibliotecaCód. de barrasNúm. de chamada
    IME31000068119QA845.T B238a e.2
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      BARBOSA, Rafael da Ponte; WAKABAYASHI, Yoshiko. Algoritmos para o problema da cobertura por sensores. 2011.Universidade de São Paulo, São Paulo, 2011.
    • APA

      Barbosa, R. da P., & Wakabayashi, Y. (2011). Algoritmos para o problema da cobertura por sensores. Universidade de São Paulo, São Paulo.
    • NLM

      Barbosa R da P, Wakabayashi Y. Algoritmos para o problema da cobertura por sensores. 2011 ;
    • Vancouver

      Barbosa R da P, Wakabayashi Y. Algoritmos para o problema da cobertura por sensores. 2011 ;

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI: