A Proposal of Parallelization of Local Search Procedures Applied to the Minimum Cost Hop-and-Root Constrained Forest Problem

• D. L. Pereira Universidade Federal de Minas Gerais
• A. S. Cunha Universidade Federal de Minas Gerais
• W. Meira Jr. Universidade Federal de Minas Gerais

Resumo

In this work, we present two parallel heuristics that coordinate the application of many local search procedures to the Minimum Cost Hop-and-root Constrained Forest Problem (MCHCFP), a Combinatorial Optimization problem in which the minimization of the communication costs in a wireless sensor network with constrained delay and number of hops is desired. The coordinated application of local search procedures in parallel must take into account that these search procedures may have different goals, since the MCHCFP requires the minimization of trees and routes. The presented ideas can be generalized to other problems in which a similar situation occurs.

Palavras-chave: Search problems, Minimization, Optimization, Hardware, Proposals, Wireless sensor networks, Delay