[1] Huang Bonan, Xia WeiweiZhang Yueyue, Zhang JingZou Qian, Yan FengShen Lianfeng, et al. Dependent task assignment algorithm based on particle swarmoptimization and simulated annealing in ad-hoc mobile cloud [J]. Journal of Southeast University (English Edition), 2018, 34 (4): 430-438. [doi:10.3969/j.issn.1003-7985.2018.04.003]

Copy

Dependent task assignment algorithm based on particle swarmoptimization and simulated annealing in ad-hoc mobile cloud()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

34

Issue:

2018 4

Page:

430-438

Research Field:

Information and Communication Engineering

Publishing date:

2018-12-20

Info

Title:

Dependent task assignment algorithm based on particle swarmoptimization and simulated annealing in ad-hoc mobile cloud

Author(s):

Huang Bonan;  Xia WeiweiZhang Yueyue;  Zhang JingZou Qian;  Yan FengShen Lianfeng

National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China

Keywords:

ad-hoc mobile cloud;  task assignment algorithm;  directed acyclic graph;  particle swarm optimization;  simulated annealing

PACS:

TN929.5

DOI:

10.3969/j.issn.1003-7985.2018.04.003

Abstract:

In order to solve the problem of efficiently assigning tasks in an ad-hoc mobile cloud(AMC), a task assignment algorithm based on the heuristic algorithm is proposed. The proposed task assignment algorithm based on particle swarm optimization and simulated annealing(PSO-SA)transforms the dependencies between tasks into a directed acyclic graph(DAG)model. The number in each node represents the computation workload of each task and the number on each edge represents the workload produced by the transmission. In order to simulate the environment of task assignment in AMC, mathematical models are developed to describe the dependencies between tasks and the costs of each task are defined. PSO-SA is used to make the decision for task assignment and for minimizing the cost of all devices, which includes the energy consumption and time delay of all devices. PSO-SA also takes the advantage of both particle swarm optimization and simulated annealing by selecting an optimal solution with a certain probability to avoid falling into local optimal solution and to guarantee the convergence speed. The simulation results show that compared with other existing algorithms, the PSO-SA has a smaller cost and the result of PSO-SA can be very close to the optimal solution.

References:

[1] Chen M, Hao Y X, Li Y, et al. On the computation offloading at ad hoc cloudlet: Architecture and service modes[J]. IEEE Communications Magazine, 2015, 53(6):18-24. DOI:10.1109/mcom.2015.7120041.
[2] Wang S, Chan K, Urgaonkar R, et al. Emulation-based study of dynamic service placement in mobile micro-clouds[C]//Military Communications Conference. Tampa, FL, USA, 2015:1046-1051.
[3] Gotoda S, Ito M, Shibata N. Task scheduling algorithm for multicore processor system for minimizing recovery time in case of single node fault[C]//International Symposium on Cluster, Cloud and Grid Computing. Ottawa, Canada, 2012:260-267.
[4] Darbha S, Agrawal D P. Optimal scheduling algorithm for distributed-memory machines[J]. IEEE Transactions on Parallel and Distributed Systems, 1998, 9(1): 87-95. DOI:10.1109/71.655248.
[5] Xu Y, Li K, Khac T T, et al. A multiple priority queueing genetic algorithm for task scheduling on heterogeneous computing systems[C]//International Conference on High Performance Computing and Communication. Exeter, UK, 2012:639-646.
[6] Li L, Li D, Song Y, et al. An effective list scheduling algorithm for homogeneous multi-core processor[C]//IEEE International Conference on Anti-Counterfeiting. Xiamen, China, 2014:1-5.
[7] Geng X, Xu G, Wang D, et al. A task scheduling algorithm based on multi-core processors[C]//International Conference on Mechatronic Science. Amsterdam, the Netherlands, 2011:942-945.
[8] Cheng H. A High efficient task scheduling algorithm based on heterogeneous multi-core processor[C]//International Workshop on Database Technology and Applications. Xiamen, China, 2010:1-4.
[9] Rahman A, Jin J, Cricenti A, et al. A cloud robotics framework of optimal task offloading for smart city applications[C]//Global Communications Conference. Singapore, 2017:1-7.
[10] Xu A, Yang Y, Mi Z, et al. Task scheduling algorithm based on PSO in cloud environment[C]//International Conference on Scalable Computing and Communications and ITS Associated Workshops. Beijing, China, 2016:1055-1061.
[11] Truonghuu T, Tham C K, Niyato D. A stochastic workload distribution approach for an ad hoc mobile cloud[C]//International Conference on Cloud Computing Technology and Science. Huangshan, China, 2015:174-181.
[12] Monoyios D, Vlachos K. Multiobjective genetic algorithms for solving the impairment-aware routing and wavelength assignment problem[J]. Journal of Optical Communications and Networking, 2010, 3(1):40-47. DOI:10.1364/jocn.3.000040.
[13] Hajjem L, Benabdallah S. An MMAS-GA for resource allocation in multi-cloud systems[C]// Internet Technology and Secured Transactions. Cambridge, UK, 2017:421-426.
[14] Mandal S, Bhattacharyya S. Secret data sharing in cloud environment using steganography and encryption using GA[C]//International Conference on Green Computing and Internet of Things. Xi’an, China, 2016:1469-1474.
[15] Angeline P J. Evolutionary optimization versus particle swarm optimization: Philosophy and performance differences[C]//International Conference on Evolutionary Programming. Berlin, Heidelberg:Springer, 1998:601-610.
[16] Robinson J, Rahmat-Samii Y. Particle swarm optimization in electromagnetics[J]. IEEE Transactions on Antennas and Propagation, 2004, 52(2): 397-407. DOI:10.1109/tap.2004.823969.
[17] Poli R. Analysis of the publications on the applications of particle swarm optimisation[M]. Hindawi Publishing Corp., 2008.
[18] Omran M, Engelbrecht A P, Salman A. Particle swarm optimization method for image clustering[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2005, 19(3):297-321. DOI:10.1142/s0218001405004083.
[19] Hettenhausen J, Lewis A, Mostaghim S. Interactive multi-objective particle swarm optimization with heatmap-visualization-based user interface[J]. Engineering Optimization, 2010, 42(2): 119-139. DOI:10.1080/03052150903042632.
[20] Mudjihartono P, Jiamthapthaksin R, Tanprasert T. Parallelized GA-PSO algorithm for solving job shop scheduling problem[C]// International Conference on Science in Information Technology. Zhuhai, China, 2017:103-108.
[21] Sujan S, Devi R K. A batchmode dynamic scheduling scheme for cloud computing[C]//IEEE Communication Technologies. Thuckalay, India, 2015:297-302.
[22] Gabi D, Ismail A S, Zainal A, et al. Cloud scalable multi-objective task scheduling algorithm for cloud computing using cat swarm optimization and simulated annealing[C]// IEEE International Conference on Information Technology. Thuckalay, India, 2017:1007-1012.
[23] Guo W, Li J, Chen G, et al. A PSO-optimized real-time fault-tolerant task allocation algorithm in wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(12):3236-3249.
[24] Lu H, Cao J, Lv S, et al. A case study of task priority effects in GA for cluster based DAG scheduling[C]//International Conference on Information Society. London, UK, 2016:157-162.

Memo

Memo:

Biographies: Huang Bonan(1993—), male, graduate; Xia Weiwei(corresponding author), female, doctor, associate professor, wwxia@seu.edu.cn.
Foundation items: The National Natural Science Foundation of China(No.61741102, 61471164, 61601122), the Fundamental Research Funds for the Central Universities(No.SJLX_160040).
Citation: Huang Bonan, Xia Weiwei, Zhang Yueyue, et al. Dependent task assignment algorithm based on particle swarm optimization and simulated annealing in ad-hoc mobile cloud[J].Journal of Southeast University(English Edition), 2018, 34(4):430-438.DOI:10.3969/j.issn.1003-7985.2018.04.003.

Common functions