Student: Diego Rodrigues Moreira Totte
Title: Comparison between Exact and Heuristic Methods for Sensor Allocation Problem in Wireless Sensor Network
Advisors: Laura Assis and Felipe Henriques
Committee: Laura Assis (CEFET/RJ), Felipe Henriques (CEFET/RJ), Pedro González (CEFET/RJ), Michel Tcheou (UERJ)
Day/Time: May 23, 2023 / 1:30p.m.
Abstract: Wireless Sensor Networks (WSNs) are increasingly present in society, whether in homes, cars, factories or in support for rescues and environmental preservation. Several optimization methods have been proposed to allocating the sensor nodes in order to improve the network performance, considering one or more objectives. However, most studies on this subject are carried out with heuristic methods, which do not have the guarantee of optimality, since exact approach generally do not solve large instances due to the complexity involved in guaranteeing the optimal solution. In this research, two approaches are proposed to solve the Sensor Allocation Problem (SAP) to minimize the overall energy cost of the network: the first is an exact method using Mixed Integer Linear Programming (MILP), and the second is a heuristic method based on the concepts of Genetic Algorithms (GAs). The results showed that the exact approach achieved optimal solutions for the PAS considering small, medium, and large instances. In turn, the GA generated sub-optimal results for almost twice as many instances as the exact approach, in the same period. Instances of regular, semi-regular, and irregular shapes were used.