Title: Comparison of Parallel Simulated Annealing on SMP and Parallel Clusters for Planning a Drone’s Route for Military Image Acquisition

Issue Number: Vol. 8, No. 1
Year of Publication: March - 2018
Page Numbers: 21-32
Authors: Eman Alsafi, Soha S. Zaghloul
Journal Name: International Journal of New Computer Architectures and their Applications (IJNCAA)
- Hong Kong
DOI:  http://dx.doi.org/10.17781/P002376

Abstract:


Drones are vastly used in many civil and military applications. However, there are many factors to be highly considered in military applications. Such factors should ensure the sensitivity and the secrecy of the mission. In order to send a military drone with the aim of acquiring images from multiple sites, the mission time should be the least possible. Therefore, the minimum route plan is required. Simulated annealing (SA) algorithm is one of the metaheuristics selected to generate a feasible solution to solve this problem. However, the time complexity is too high. Therefore, this research exploits the parallelism in the simulated annealing with the aim of accelerating the time to find a suitable solution. Parallel programming divides the problem into smaller independent tasks, and then executes the sub-tasks simultaneously. Two parallel versions are therefore developed on different environment: synchronous SA on SMP, and asynchronous SA Complete Search Space (CSS) on parallel clusters. Experiments are conducted on the parallel clusters environment of the SANAM supercomputer. This research details the CSS, and compares it with the SMP SA developed in our previous study. Comparison is made in terms of speedup, efficiency, scalability, and quality of solution.