Parallel Meta-Heuristic Approaches for Deployment of Heterogonous Sensing Devices

摘要

Genetic Algorithms and Simulated Annealing have been used to solve many combinatorial problems. Their results are proven to be efficient in solving such problems. The running time of these techniques is generally less than the running time needed to find the optimal solution. However, in very large-scale problems such as sensor deployment, their running time is extremely high. In this paper, we introduce several parallelization methods to speedup the genetic and simulated annealing heuristics used for the deployment of sensing devices on a field with differential security/surveillance requirements. The parallelization methods are classified into two categories: slave based, and master based. We implemented these two categories using iteration division, and chromosome division. A large number of experiments were conducted on a PVM cluster with 14 nodes to show the speed up and efficiency of these parallelization techniques.