Formulação Linear Inteira e Heurísticas para o problema da K-Cobertura e M-Conectividade em Redes de Sensores Sem Fio

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.