Formulação de programação linear inteira para um problema de k-cobertura e m-conectividade em redes de sensores
| dc.creator | José Ferreira Reis Fonseca | |
| dc.creator | Iago A. Carvalho | |
| dc.creator | Thiago Ferreira de Noronha | |
| dc.date.accessioned | 2024-08-14T20:56:26Z | |
| dc.date.accessioned | 2025-09-08T23:53:32Z | |
| dc.date.available | 2024-08-14T20:56:26Z | |
| dc.date.issued | 2022 | |
| dc.description.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. | |
| dc.format.mimetype | ||
| dc.identifier.issn | 29651476 | |
| dc.identifier.uri | https://hdl.handle.net/1843/74108 | |
| dc.language | por | |
| dc.publisher | Universidade Federal de Minas Gerais | |
| dc.relation.ispartof | Simpósio Brasileiro de Pesquisa Operacional | |
| dc.rights | Acesso Aberto | |
| dc.subject | Otimização Combinatória | |
| dc.subject | Pesquisa Operacional | |
| dc.subject | Programação Linear | |
| dc.subject.other | Otimização Combinatória | |
| dc.subject.other | Pesquisa Operacional | |
| dc.subject.other | Programação Linear | |
| dc.title | Formulação de programação linear inteira para um problema de k-cobertura e m-conectividade em redes de sensores | |
| dc.title.alternative | Integer linear programming formulation for a k-coverage and m-connectivity problem in sensor networks | |
| dc.type | Artigo de evento | |
| local.citation.issue | 54 | |
| local.description.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. | |
| local.publisher.country | Brasil | |
| local.publisher.department | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO | |
| local.publisher.initials | UFMG | |
| local.url.externa | https://proceedings.science/sbpo/sbpo-2022/trabalhos/formulacao-de-programacao-linear-inteira-para-um-problema-de-k-cobertura-e-m-con?lang=pt-br |