Use este identificador para citar o ir al link de este elemento:
http://hdl.handle.net/1843/74108
Tipo: | Artigo de Evento |
Título: | Formulação de programação linear inteira para um problema de k-cobertura e m-conectividade em redes de sensores |
Título(s) alternativo(s): | Integer linear programming formulation for a k-coverage and m-connectivity problem in sensor networks |
Autor(es): | José Ferreira Reis Fonseca Iago A. Carvalho Thiago Ferreira de Noronha |
Resumen: | 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. |
Asunto: | Otimização Combinatória Pesquisa Operacional Programação Linear |
Idioma: | por |
País: | Brasil |
Editor: | Universidade Federal de Minas Gerais |
Sigla da Institución: | UFMG |
Departamento: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
Tipo de acceso: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/74108 |
Fecha del documento: | 2022 |
metadata.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 |
metadata.dc.relation.ispartof: | Simpósio Brasileiro de Pesquisa Operacional |
Aparece en las colecciones: | Artigo de Evento |
archivos asociados a este elemento:
archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
Formulac¸ao de programac¸ ˜ ao linear.pdfA.pdf | 139.43 kB | Adobe PDF | Visualizar/Abrir |
Los elementos en el repositorio están protegidos por copyright, con todos los derechos reservados, salvo cuando es indicado lo contrario.