A parallel algorithm with enhancements via partial objective value cuts for cluster-based wireless sensor network design

摘要

In this paper, we develop a parallel algorithm for the solution of an integrated topology control and routing problem in Wireless Sensor Networks (WSNs). After presenting a mixed-integer linear optimization formulation for the problem, for its solution, we develop an effective parallel algorithm in a Master-Worker model that incorporates three parallelization strategies, namely low-level parallelism, domain decomposition, and multiple search (both cooperative and independent) in a single Master-Worker framework. For improved algorithmic efficiency, we introduce three reduced subproblems and devise partial objective value cuts from these reduced models. We utilize both the reduced models, for which we suggest efficient approaches for their solution, and the associated cuts in our parallel algorithm. We observe that the reduced models provide valuable information on the optimal design variables for the original model and we exploit this fact in our parallel algorithm. Our overall parallelization scheme utilizes exact optimization models and solutions as its components and allows cooperation among multiple worker processors via communication of partial solution and cut information. Computational study shows that our approach is very effective in addressing this complex problem. Parallel implementation not only achieves a speed-up of the computations, but also yields better solutions as it can explore the solution space more effectively.