Algoritmos de otimização para roteamento e agrupamento em redes de sensores sem fio com sorvedouros móveis

Abstract

In this work, we introduce models and optimization algorithms to improve the Quality of Service in Wireless Sensor Networks with multiple mobile sinks. A discrete event simulator that integrates the proposed optimization methods into a realistic model of the network dynamics over the time is also implemented and tested computationaly. The main Optimization Problem considered here, that of defining routes to each mobile sink, allowing them to collect sensed information thoughout the network, is modeled as a variant of the uncapacitated Vehicle Routing Problem. In this variant, the fleet size is known beforehand, not all clients need to be visited and the goal is to minimize the length of the longest vehicle route. To model the problem, two Integer Programs are introduced. The first one is a compact formulation based on Network Flow models. A Branch-and-Bound algorithm is presented for this formulation. The second Integer Program is based in Generalized Subtour Elimination Constraints. To tackle this model, we developed a Branch-and-Cut algorithm. A third algorithm, a Local Branching that used the Branch-and-Cut as inner solver, was also proposed and implemented. Due to the difficulty found in terms of computational time in solving the problem to optimality, we also proposed several Metaheuristic based heuristics to find (hopefully) good solutions in practical times. Our simulation results indicate that the optimization algorithms allowed significantimprovements in message delay rates and other important Quality of Service parameters.