DAG区块链中基于确定性退火技术的融合分割遗传任务调度算法  

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

作　　者：曹怀虎[1] 张艳梅[1] 王坚[1] 李海峰[1] 崔丽欣[1] Huaihu CAO;Yanmei ZHANG;Jian WANG;Haifeng LI;Lixin CUI(School of Information,Central University of Finance and Economics,Beijing 100081,China)

机构地区：[1]中央财经大学信息学院

出　　处：《中国科学：信息科学》2020年第2期261-274,共14页Scientia Sinica(Informationis)

基　　金：北京市社会科学基金重点项目(批准号:16YJA001);国家自然科学基金项目(批准号:61602536,61671030);中央高校基本科研业务费专项资金;中央财经大学科研创新团队支持计划资助项目

摘　　要：传统的区块链结构,由于其固有的响应速度慢,不能适应大规模实时响应的应用场景,本文针对这一问题,提出了一种DAG (directed acyclic graph)区块链理论架构,将传统区块链的链式处理过程转变为并行的处理过程,使得快速响应成为可能.在此基础上,面向DAG区块链环境中非独立任务调度问题,提出了基于确定性退火技术的混合分割遗传任务调度算法.实验结果显示,该算法能够适应DAG区块链节点的异质性、动态性和广域性,其调度的性能也比传统的调度算法有所改善,在优化任务完成时间的同时,兼顾了负载均衡问题,有效地提高了响应速度,是解决DAG区块链环境中非独立任务调度问题的可行方法.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.

关 键 词：有向图 遗传算法 并行 任务调度 优化 负载均衡 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论] TP18[自动化与计算机技术—计算机科学与技术]