Use este identificador para citar ou linkar para este item:
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 |
| 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 |
| Idioma: | por |
| País: | Brasil |
| Editor: | Universidade Federal de Minas Gerais |
| Sigla da Instituição: | UFMG |
| Departamento: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
| Tipo de Acesso: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/74108 |
| Data do 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 nas coleções: | Artigo de Evento |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| Formulac¸ao de programac¸ ˜ ao linear.pdfA.pdf | 139.43 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.