Operadores geométricos para otimização dinâmica com aplicação ao problema de cobertura e conectividade em redes de sensores sem fionão-hierárquicas

Abstract

Some recent works raised the hypothesis that the assignment of a geometry to the decision variable space of a combinatorial problem could be useful both for providing meaningful descriptions of the fitness landscape and for supporting the systematic construction of evolutionary operators (the geometric operators) that make a consistent usage of the space geometric properties in the search for problem optima. This paper introduces some new geometric operators which constitute the realization of searches along the combinatorial space versions of the geometric entities {\\em descent directions} and {\\em subspaces}. The new geometric operators are stated in the specific context of the {\\em Wireless Sensor Network Dynamic Coverage and Connectivity Problem} (WSN-DCCP). The WSN have shown a very promising area in which several researchers seek an energy-efficient network, in an attempt to obtain a long network lifetime. In order to extend the network lifetime, a new model that captures the dynamics of the WSN-DCCP is proposed. For its solution, a genetic algorithm in both single-objective and multiobjective versions is developed for the WSN-DCCP, using the proposed geometric operators. An interesting comparison is performed against a single-objective formulation stated as an integer linear programming (ILP) problem, which is solved with exact methods. That ILP formulation adopts a {\\em proxy} objective function based on the minimization of energy consumption in the network, in order to approximate the objective of network lifetime maximization, and a greedy approach for dealing with system dynamics, solving a ILP static problem for each stage, to approach the dynamic problem. Up to the authors\ knowledge, the proposed GAs are the first algorithms to outperform the lifetime of resulting networks as synthesized by the ILP formulation, also running in much smaller computational times. Although they are obtained in a fully controllable environment, the solutions developed can serve as reference for the design of a WSN. Online approaches were built with the intention of bringing the solutions presented in more real situations. Such approaches use as a reference network designed for solving the new model proposed for the WSN-DCCP. Simulations to analyze the performance of the approaches were performed in an environment with unexpected failures. The results were compared with the reference design, obtaining results very encouraging. Besides the introduction of two geometric entities in geometric context for combinatorial problems, one of the major contributions of this paper is to present a new truly dynamic model for the WSN-DCCP, along with algorithms that can solve such a model. Differently of approaches in the literature, this paper proposes a new optical design for WSN, in which all periods of the network operation are treated simultaneously rather than individually.