Formulação de programação linear inteira para um problema de k-cobertura e m-conectividade em redes de sensores
Carregando...
Data
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Artigo de evento
Título alternativo
Integer linear programming formulation for a k-coverage and m-connectivity problem in sensor networks
Primeiro orientador
Membros da banca
Resumo
Neste trabalho apresentamos um programa linear de inteiros (Integer-Linear program, ILP) para o problema K-Cobertura e M-Conectividade (K-Coverage M-Connectivity, KCMC). O problema de otimização KCMC pertence a categoria NP-Difícil e aparece em aplicações de redes de sensores sem fio (Wireless Sensor Networks, WSN) onde se deseja minimizar o número de sensores da rede enquanto garantindo dadas expectativas de qualidade de serviço e resistência à falhas de sensores. Nossa principal contribuição consiste numa formulação ILP para o problema KCMC que aprimora descrições encontradas em trabalhos relacionados ao garantir resistência a falhas em quaisquer sensores na rede. Apresentamos também testes de desempenho de uma implementação de nossa formulação ILP.
Abstract
In this paper, we present a linear integer program (ILP) for the K-Coverage M-Connectivity
(KCMC) problem. This NP-Hard optimization problem is recurrent in applications of wireless sensor networks (WSN) where it is desirable to minimize the number of sensors while guaranteeing
expectations of quality of service and resistance to sensor failures. Our main contribution consists
of an ILP formulation for the KCMC problem that improves upon the descriptions of the problem
found on related works by guaranteeing resistance to failures in any of the sensors in the WSN. We
also present performance tests of our ILP implementation.
Assunto
Otimização Combinatória, Pesquisa Operacional, Programação Linear
Palavras-chave
Otimização Combinatória, Pesquisa Operacional, Programação Linear
Citação
Departamento
Curso
Endereço externo
https://proceedings.science/sbpo/sbpo-2022/trabalhos/formulacao-de-programacao-linear-inteira-para-um-problema-de-k-cobertura-e-m-con?lang=pt-br