Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/74108| Type: | Artigo de Evento |
| Title: | Formulação de programação linear inteira para um problema de k-cobertura e m-conectividade em redes de sensores |
| Other Titles: | Integer linear programming formulation for a k-coverage and m-connectivity problem in sensor networks |
| Authors: | José Ferreira Reis Fonseca Iago A. Carvalho Thiago Ferreira de Noronha |
| Abstract: | 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. |
| Subject: | Otimização Combinatória Pesquisa Operacional Programação Linear |
| language: | por |
| metadata.dc.publisher.country: | Brasil |
| Publisher: | Universidade Federal de Minas Gerais |
| Publisher Initials: | UFMG |
| metadata.dc.publisher.department: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
| Rights: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/74108 |
| Issue Date: | 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 |
| 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 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.