采用遗传-谐振算法求解网格依赖任务安全调度问题  

Using genetic-harmonic algorithm to solve security scheduling problem of dependent tasks in heterogeneous grid system

作　　者：王洪峰[1,2] 朱海[2] 

机构地区：[1]华中科技大学计算机科学与技术学院,湖北武汉430079 [2]周口师范学院计算机科学与技术学院,河南周口466001

出　　处：《陕西师范大学学报（自然科学版）》2015年第2期15-23,共9页Journal of Shaanxi Normal University：Natural Science Edition

基　　金：国家自然科学基金资助项目(61103143;70890081);中国博士后科学基金资助项目(2012M512008);河南省科技厅科技发展计划基础与前沿技术研究项目(142300410402);河南省教育厅高校创新人才支持计划项目(2012HASTIT032);河南省教育厅科学技术研究重点项目指导计划基础前沿项目(14B520057)

摘　　要：针对异构网格环境下任务调度面临的安全性问题,考虑网格节点的系统安全控制策略与历史行为表现,构建了网格节点安全评估模型,并在此基础上提出了一种安全可信的网格依赖任务调度优化模型。为求解该模型,结合遗传算法全局寻优能力较强的特性,同时克服其局部寻优不足的缺点,引入谐振算法,从而设计了一种新的遗传-谐振算法(GASHO)。首先,针对DAG任务图基于启发式思想设计遗传进化算子和量子谐振算子等操作以产生任务调度优先队列,解决离散解非法的问题;然后,采用安全约束下的最早完成时间算子操作实现任务集到网格节点的映射,提高算法收敛效率;最后,对算法的时间复杂度和收敛性进行分析证明。仿真实验结果表明,在同等条件下与同类算法相比,GASHO算法在收敛性、调度长度、安全效益值等方面具有明显的优势。Aimed at the security problem of tasks scheduling in heterogeneous grid system,a se-curity evaluation model is presented based on security control strategy and history behavior of grid nodes,and on this basis a kind of safe and trusted optimization model for dependent tasks scheduling is put forward under grid environment.To solve the model,a new genetic-harmonic algorithm called GASHO is designed,which taks full advantage of the characteristic of global op-timization of genetic algorithm and introduces the harmonic operator to overcome the shortage of local optimization.Based on the dependencies of a DAG task graph,the heuristic method is em-ployed to design the operator of genetic and quantum harmonic,thus the GASHO produces a bet-ter task scheduling queue to avoid the occurence of illegal solutions in discrete spaces.Then,to improve the convergence efficiency,the earliest finish time operator which is constrained to secur-ity factors is used to map from task set to grid nodes.At last,the convergence property and time complexity is analyzed.Compared with other similar algorithm under the same condition,the simulation results show that the proposed algorithm has the advantages on the convergence prop-erty,scheduling length and security efficiency.

关 键 词：网格计算 依赖任务 安全调度 遗传-谐振算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]