Formulação de programação linear inteira para um problema de k-cobertura e m-conectividade em redes de sensores

José Ferreira Reis Fonseca; Iago A. Carvalho; Thiago Ferreira de Noronha

Please use this identifier to cite or link to this item: http://hdl.handle.net/1843/74108

Full metadata record

DC Field	Value	Language
dc.creator	José Ferreira Reis Fonseca	pt_BR
dc.creator	Iago A. Carvalho	pt_BR
dc.creator	Thiago Ferreira de Noronha	pt_BR
dc.date.accessioned	2024-08-14T20:56:26Z	-
dc.date.available	2024-08-14T20:56:26Z	-
dc.date.issued	2022	-
dc.citation.issue	54	pt_BR
dc.identifier.issn	29651476	pt_BR
dc.identifier.uri	http://hdl.handle.net/1843/74108	-
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.	pt_BR
dc.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.	pt_BR
dc.format.mimetype	pdf	pt_BR
dc.language	por	pt_BR
dc.publisher	Universidade Federal de Minas Gerais	pt_BR
dc.publisher.country	Brasil	pt_BR
dc.publisher.department	ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO	pt_BR
dc.publisher.initials	UFMG	pt_BR
dc.relation.ispartof	Simpósio Brasileiro de Pesquisa Operacional	pt_BR
dc.rights	Acesso Aberto	pt_BR
dc.subject	Otimização Combinatória	pt_BR
dc.subject	Pesquisa Operacional	pt_BR
dc.subject	Programação Linear	pt_BR
dc.subject.other	Otimização Combinatória	pt_BR
dc.subject.other	Pesquisa Operacional	pt_BR
dc.subject.other	Programação Linear	pt_BR
dc.title	Formulação de programação linear inteira para um problema de k-cobertura e m-conectividade em redes de sensores	pt_BR
dc.title.alternative	Integer linear programming formulation for a k-coverage and m-connectivity problem in sensor networks	pt_BR
dc.type	Artigo de Evento	pt_BR
dc.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	pt_BR
Appears in Collections:	Artigo de Evento

Files in This Item:

File	Description	Size	Format
Formulac¸ao de programac¸ ˜ ao linear.pdfA.pdf		139.43 kB	Adobe PDF	View/Open

Show simple item record