Heurísticas mono e multiobjetivo para o problema de cobertura econectividade de redes de sensores sem fio planas

Abstract

This work deals with the Problem of Coverage and Connectivity in Wireless Sensor Networks (WSN), formulating it in different ways as mono-objective and multiobjective optimization problems. The issue of dynamic reconfiguration of the network to be performed as soon as some failures occur in the network nodes is considered here in allthe cases. In the case of mono-objective formulation, the proposed heuristics is based on a Genetic Algorithm (GA) that performs the initial choice of the nodes to be activated and that also performs an update of this choice in some moments, when the network is significantlyfar from the optimal configuration. This heuristics is compared with an exact formulation of the same problem, which is stated as an Integer Linear Program and solved with a commercial optimization package. Although, as expected, the proposed heuristics has not been able to solve the problem up to the exact optimality, it has been found that thegains in the computation time obtained by the heuristics make its application to practical problems feasible, even in situations involving a large number of sensor nodes. The results presented in this part of this dissertation are related to algorithms that have been developed earlier, with the participation of this author, and that have been enhancedspecifically in the context of this work. The main contribution of this dissertation is the proposition of a multiobjective formulationfor the RSSF coverage and connectivity problem, associated to a corresponding heuristics for dealing with it. This formulation is based on the observation that it is possible to perform a trade-off between the duration of working time of the network and the percentage of its coverage area. A multiobjective GA, based on the NSGA (Non-dominated Sorting Genetic Algorithm), has been developed in order to replace themono-objective GA, allowing the parallel computation of a set of solutions which is nondominated in relation to such objectives. A simple decision-making algorithm is employed in order to choose the configuration to be adopted in each moment by the network. Simulationresults show that the introduction of rather small relaxations in the coverage allow significant gains in the network working time. The computational time of the proposed multiobjective heuristics is similar to the one of the mono-objective heuristics, for networks of similar size.