SCIENTIA SINICA Informationis, Volume 50 , Issue 2 : 261-274(2020) https://doi.org/10.1360/N112019-00025

Fusion-partitioning genetic task scheduling algorithm based on deterministic annealing technology in DAG blockchains

More info
  • ReceivedJan 25, 2019
  • AcceptedSep 4, 2019
  • PublishedFeb 11, 2020


The traditional blockchain structure cannot adapt to large-scale and real-time-application scenarios because of its inherently slow response. To solve this problem, a theoretical framework of DAG (directed acyclic graph) blockchain is proposed, transforming the chain processing of a traditional blockchain into parallel processing. On this basis, the non-independent task-scheduling problem in the DAG blockchain environment is studied, and a fusion-partitioning genetic task-scheduling algorithm based on deterministic annealing technology in DAG blockchains is proposed. The experimental results show that the algorithm can adapt to the heterogeneity, dynamism, and wide area of DAG blockchain nodes, and its scheduling performance is better than that of the traditional scheduling algorithm. While optimizing the task-completion time, the algorithm takes account of the load-balancing problem and effectively improves the response speed. It is a feasible method for solving the non-independent task-scheduling problem in the DAG blockchain environment.

Funded by





[1] Ju C H, Zou J B, Fu X K. Design and application of big data credit reporting platform integrating blockchain technology. Comput Sci, 2018, 45: 522--526. Google Scholar

[2] He P, Yu G, Zhang Y F, et al. Survey on blockchain technology and its application prospect. Comput Sci, 2017, 44: 1--7. Google Scholar

[3] Chen W L, Zheng Z B. Blockchain data analysis: a review of status, trends and challenges. J Comput Res Dev, 2018, 55: 1853--1870. Google Scholar

[4] Yuan Y, Wang F Y. Parallel blockchain: concept, methods and issues. Acta Autom Sin, 2017, 43: 1703--1712. Google Scholar

[5] Yuan Y, Wang F Y. Blockchain and Cryptocurrencies: Model, Techniques, and Applications. IEEE Trans Syst Man Cybern Syst, 2018, 48: 1421-1428 CrossRef Google Scholar

[6] Novo O. Blockchain Meets IoT: An Architecture for Scalable Access Management in IoT. IEEE Internet Things J, 2018, 5: 1184-1195 CrossRef Google Scholar

[7] Makhdoom I, Abolhasan M, Abbas H. Blockchain's adoption in IoT: The challenges, and a way forward. J Network Comput Appl, 2019, 125: 251-279 CrossRef Google Scholar

[8] Andoni M, Robu V, Flynn D. Blockchain technology in the energy sector: A systematic review of challenges and opportunities. Renew Sustain Energy Rev, 2019, 100: 143-174 CrossRef Google Scholar

[9] Yu H, Zhang Z Y, Liu J W. Research on scaling technology of bitcoin blockchain. J Comput Res Dev, 2017, 54: 2390--2403. Google Scholar

[10] Banerjee M, Lee J, Choo K K R. A blockchain future for internet of things security: a position paper. Digital Commun Networks, 2018, 4: 149-160 CrossRef Google Scholar

[11] Pan C, Liu Z Q, Liu Z, et al. Research on scalability of blockchain technology: problems and methods. J Comput Res Dev, 2018, 55: 2099--2110. Google Scholar

[12] Liu A D, Du X H, Wang N, et al. Research progress of blockchain technology and its application in information security. J Softw, 2018, 29: 2092--2115. Google Scholar

[13] Shao Q F, Jin C Q, Zhang Z, et al. Blockchain: architecture and research progress. Chinese J Comput, 2018, 41: 969--988. Google Scholar

[14] Zheng Z, Xie S, Dai H, et al. An overview of blockchain technology: architecture, consensus, and future trends. In: Proceedings of IEEE International Congress on Big Data, 2017. 557--564. Google Scholar

[15] Zhang F, Shi B X, Jiang W B. Review of key technology and its application of blockchain. Chinese J Netw Inform Secrity, 2018, 4: 22--29. Google Scholar

[16] Jawhar I, Mohamed N, Al-Jaroodi J. Communication and networking of UAV-based systems: Classification and associated architectures. J Network Comput Appl, 2017, 84: 93-108 CrossRef Google Scholar

[17] Li Z, Barenji A V, Huang G Q. Toward a blockchain cloud manufacturing system as a peer to peer distributed network platform. Robotics Comput-Integrated Manufacturing, 2018, 54: 133-144 CrossRef Google Scholar

[18] Kotilevets I D, Ivanova I A, Romanov I O. Implementation of directed acyclic graph in blockchain network to improve security and speed of transactions. IFAC-PapersOnLine, 2018, 51: 693-696 CrossRef Google Scholar

[19] Munsing E, Mather J, Moura S. Blockchains for decentralized optimization of energy resources in microgrid networks. In: Proceedings of IEEE Conference on Control Technology and Applications, 2017. 108--122. Google Scholar

[20] Cao H H, Yu Z W, Wang Y Y. Research on grid task scheduling algorithm based on communication and computing cost. Comput Eng Appls, 2006, 42: 132--134. Google Scholar

[21] Topcuoglu H, Hariri S, Min-You Wu S. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans Parallel Distrib Syst, 2002, 13: 260-274 CrossRef Google Scholar

[22] Zhou X G, Liang L, Huang X Z, et al. On-line scheduling and placement of real-time tasks for recongfigurable computing system. Chinese J Comput, 2007, 30: 1903--1909. Google Scholar

[23] He X, Huang T W, Yu J Z, et al. A continuous-time algorithm for distributed optimization based on multiagent networks. IEEE Trans Syst Man Cybern Syst, 2017. doi: 10.1109/TSMC.2017.2780194. Google Scholar

[24] Guggilam S S, Dall'Anese E, Chen Y C. Scalable Optimization Methods for Distribution Networks With High PV Integration. IEEE Trans Smart Grid, 2016, 7: 2061-2070 CrossRef Google Scholar

[25] Yang G W, Li X M, Wang Y H, et al. Deterministic annealing. Chinese J Computers, 1998, 21: 765--768. Google Scholar

[26] Fedak G, Germain C, Neri V, et al. Xtrem web: a generic global computing system. In: Proceedings of the 1st IEEE/ACM International Symposium on Cluster Computing and the Grid, 2001. 452--460. Google Scholar

[27] Li P, Duan H. A potential game approach to multiple UAV cooperative search and surveillance. Aerospace Sci Tech, 2017, 68: 403-415 CrossRef Google Scholar

[28] Sedjelmaci H, Senouci S M, Ansari N. Intrusion Detection and Ejection Framework Against Lethal Attacks in UAV-Aided Networks: A Bayesian Game-Theoretic Methodology. IEEE Trans Intell Transp Syst, 2017, 18: 1143-1153 CrossRef Google Scholar

[29] Hussein A F, ArunKumar N, Ramirez-Gonzalez G. A medical records managing and securing blockchain based system supported by a Genetic Algorithm and Discrete Wavelet Transform. Cognitive Syst Res, 2018, 52: 1-11 CrossRef Google Scholar

[30] Bu T, Towsley D. On distinguishing between Internet power law topology generators. In: Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies, 2002. 638--640. Google Scholar

[31] Cao H H, Zhu J M, Pan Y. Context-Aware P2P Mobile Social Network Structure and Discovery Algorithm. Chin J Comput, 2012, 35: 1223-1234 CrossRef Google Scholar

Copyright 2020  CHINA SCIENCE PUBLISHING & MEDIA LTD.  中国科技出版传媒股份有限公司  版权所有

京ICP备14028887号-23       京公网安备11010102003388号