Formulação Linear Inteira e Heurísticas para o problema da K-Cobertura e M-Conectividade em Redes de Sensores Sem Fio
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Primeiro orientador
Membros da banca
Fernanda Sumika Hojo de Souza
Márcio Costa Santos
Márcio Costa Santos
Resumo
Um sensor sem fio é um dispositivo capaz de coletar dados de um ou mais pontos de interesse (points of interest - POIs) e transmitir os dados coletados para outros sensores sem o uso de fios. Uma rede de sensores sem fio (wireless sensor network - WSN) pode ser estruturada de forma que seus sensores continuamente coletem dados de um conjunto de POIs e os transmitam de sensor em sensor até um subconjunto de sensores base denominados sinks. Por vezes, a cobertura em algum POI só pode ser garantida se vários sensores estiverem posicionados de forma a coletar seus dados. A propriedade de K-Cobertura é atribuída a WSNs em que cada POI tem seus dados coletados por K ou mais sensores e transmitidos para algum sensor base. Sensores estão sujeitos a falhas que podem impedi-los de transmitir ou coletar dados de POIs. WSNs robustas são capazes de coletar dados de todos os POIs mesmo após falhas em vários de seus sensores. Uma WSN tem a propriedade de M-Conectividade quando seus sensores são capazes de coletar dados de todos os POIs e transmiti-los para algum sensor base mesmo após M − 1 sensores sofrerem falhas.
O problema da K-Cobertura e M-Conectividade (KCMC) consiste em determinar o menor subconjunto de sensores de uma WSN que sejam suficientes para garantir as propriedades de K-Cobertura e M-Conectividade. Neste trabalho são apresentados dois programas lineares inteiros (integer linear programs - ILPs) que formulam o KCMC. Também são apresentadas quatro heurísticas para esse mesmo problema. As quatro heurísticas apresentadas neste trabalho são baseadas na meta-heurística fix-and-optimize, em que um método heurístico é utilizado para reduzir o problema original. O sub-problema resultante é então resolvido por um algoritmo exato.
As heurísticas apresentadas são diferenciadas pelo método heurístico empregado, mas todas utilizam o algoritmo branch-and-bound com um dos ILPs como método exato. O desempenho de cada heurística foi avaliado por meio de experimentos computacionais, permitindo comparação estatística para determinar a heurística que produz os melhores resultados.
Abstract
A wireless sensor is a device capable of collecting data from one or more Points of Interest (POIs) and wirelessly transmitting the collected data. A wireless sensor network (WSN) may be deployed in such a way that each sensor continuously collects data from a set of POIs, and all data is transmitted to a subset of sensors called sinks. In some situations, the coverage of a POI can only be assured if several sensors collect its data. The property of K-Coverage is attributed to WSNs in which each POI may have its data collected by at least K sensors, with all data being transmitted to one or more sinks. A sensor may suffer failures that compromise its capabilities for data collection and transmission. The property of M-Connectivity is attributed to robust WSNs, in which data can be collected in all POIs and transmitted to sinks even if M −1 sensors suffer failures simultaneously. The K-Coverage M-Connectivity (KCMC) problem consists of computing the minimal subset of sensors in a WSN that suffice for the K-Coverage and M-Connectivity problems. In this master’s thesis, two Integer Linear Programs (ILPs) and four heuristics are presented for the KCMC. The four heuristics presented are based on fix-and-optimize meta-heuristics, when an heuristic method is used to reduce the original problem.
The resulting subproblem is then solved by an exact algorithm. Each heuristic differs by the heuristic method employed, but all use the branch-and-bound algorithm with one of the presented ILPs as the exact method. Computational experiments were used to evaluate the heuristics and determine the one that more often yields the best results.
Assunto
Computação – Teses, Redes de sensores sem fio – Teses, Programação linear – Teses, Programação heurística – Teses
Palavras-chave
redes de sensores sem fio, programação linear inteira, cobertura, conectividade, fix-and-optimize