采用遗传-退火算法的网格依赖任务可信调度

doi:10.11896/j.issn.1002-137X.2015.06.056

摘要/Abstract

摘要： 针对异构网格环境下的依赖任务调度问题面临的安全性挑战,综合考虑网格资源节点的固有安全性和行为安全性,构建一个网格资源节点身份可靠性度量函数和行为表现信誉度评估策略；同时为了确立任务安全需求与资源节点安全属性之间的隶属关系,定义了安全效益隶属度函数,从而建立了一个网格任务调度的安全可信模型。以此为基础,定义任务需求表示模型和网格资源拓扑模型,提出一种安全可信的网格任务调度新模型。为求解该模型,在遗传算法的基础上,设计新的进化算子即改进的交叉算子、内部交叉算子及作为变异的迁移算子,同时引入模拟退火算法增加搜索精度,从而提出了一种新的遗传-退火算法。仿真实验表明,在相同条件下, 该算法比同类算法在调度长度、安全可信值及收敛性等方面具有更好的综合性能。

关键词: 网格计算,任务调度,安全可信模型,进化算子,遗传-退火算法

Abstract: Given the security challenges faced for the dependent task-scheduling problem under heterogeneous grid environment,considering grid nodes’ inherent security and behavioral security,we built a function to measure each node’s identical reliability and a strategy to assess its behavioral credibility.Meanwhile,in order to establish the affiliation between the security requirement and security attributes of each task,an affiliation function of security benefits was defined.Thus,a security trusted task-scheduling model under grid environment was built in this paper.On this basis,with the task’s requirement model presented and grid resources’ topology model introduced,a new security trusted grid task-scheduling model was proposed.To solve this model by using genetic algorithm,we designed several new genetic operators,including improved crossover operator,crossover operator within each individual and migration operator which is taken as mutation operator,and at the same time,with a view to increase search precision,the simulated annealing algorithm was introduced,by which we further proposed a new genetic-annealing algorithm.The simulation results show that compared with similar algorithms under the same conditions,the proposed algorithm has a better overall performance in terms of scheduling length,security trusted value,convergence and other aspects.

Key words: Grid computing,Task-scheduling,Security trusted model,Evolution operator,Genetic-annealing algorithm

王洪峰,朱海. 采用遗传-退火算法的网格依赖任务可信调度[J]. 计算机科学, 2015, 42(6): 268-275. https://doi.org/10.11896/j.issn.1002-137X.2015.06.056

WANG Hong-feng and ZHU Hai. Trusted Scheduling of Dependent Tasks Using Genetic-annealing Algorithm under Grid Environment[J]. Computer Science, 2015, 42(6): 268-275. https://doi.org/10.11896/j.issn.1002-137X.2015.06.056

参考文献

[1] L Shin-Yeu,H Shih-Cheng,L Cheng-Zih.Expanding service capacities and increasing service reliabilities for the grid-based utili-ty computing[J].IEEE Transactions on Systems,man,and cybernetics-Part A,2011,41(1):149-160
[2] Sarkar V,Khaparde S A.Improving Demand Response and Bid-Consistency of Price Outcome in the Security-Constrained Dispatch Scheduling[J].IEEE Transactions on Power Systems,2013,8(8):2433-2445
[3] Song S S,Hwang Kai,Kwok Yu-Kwong.Risk-resilient heuristics and genetic algorithms for security-assured grid job scheduling[J].IEEE Transactions on Computers,2006,55(6):703-719
[4] Gong Chen,Wang Xiao-dong,Xu Wei-qiang,et al.DistributedReal-Time Energy Scheduling in Smart Grid Stochastic Model and Fast Optimization[J].IEEE Transactions on Smart Grid,2013,4(9):1476-1489
[5] Yuan L L,Zeng G S,Jiang L L,et al.Dynamic level scheduling based on trust model in grid computing[J].Chinese Journal of Computers,2006,29(7):1217-1224
[6] Zhang W Z,Liu X R,Hu M Z,et al.Trust-driven job scheduling heuristics for computing grid[J].Journal on Communication,2006,7(2):73-79
[7] Braun T D,Slegel H J,Becj N.A comparison of eleven staticheuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems[J].Journal of Parallel and Distributed Computing,2001,61(6):810-837
[8] Xiao P,Hu Z G.Co-Scheduling Model for Independent Tasks with Deadline Constraint in Computational Grid[J].Acta Electronic Sinica,2011,9(8):1852-1857
[9] 马艳,龚斌,邹立达.网格环境下基于复制的能耗有效依赖任务调度研究[J].计算机研究与发展,2013,50(2):420-429 Ma Yan,Gong Bin,Zou Li-da.Duplication Based Energy-Efficient Scheduling for Dependent Tasks in Grid Environment[J].Journal of Computer Research and Development,2013,0(2):420-429
[10] 阎朝坤,胡志刚,李玺,等.面向可靠性-费用优化的网格任务调度模型及算法研究[J].计算机科学,2013,40(5):136-141 Yan Chao-kun,Hu Zhi-gang,Li Xi,et al.Reliability-Cost Optimization Scheduling Model and Algorithm in Grid[J].Journal of Computer Science,2013,0(3):136-141
[11] Du X L,Jiang C J,Xu G R.A grid DAG scheduling algorithm based on fuzzy clustering[J].Journal of Software,2006,17(11):2277-2288
[12] Xu Jin,Lam A Y S,Li V O K,et al.Chemical Reaction Optimization for Task Scheduling in Grid Computing[J].IEEE Tran-sactions on Parallel and Distributed Systems,2011,22(10):1624-1631
[13] Sun W F,Qin Z Q,Li M C,et al.QIACO:An Algorithm forGrid Task Scheduling of Multiple QoS Dimensions[J].Acta Electronic Sinica,2011,9(5):1115-1120
[14] He X,Sun X,Laszewski G V.QoS guided min-min heuristic for grid task scheduling[J].Journal of Computer Science and Technology,2003,18(4):442-451
[15] Martino V D,Mililotti M.Scheduling in a grid computing environment using genetic algorihms[C]∥The 16th Int’1 Parallel and Distributed Processing Symp,2002.USA:IEEE Press,2002
[16] Abraham A,Buyya R,Nath B.Nature’s Heuristics for Scheduling Jobs on Computational Grids[C]∥The 8th Int’1 Conference on Advanced Computing and Communication,2000.India:IEEE Press,2000
[17] Xie T,Qin X.Scheduling security-critical real-time applications on clusters[J].IEEE Transactions on Computers,2006,55(7):864-879
[18] Zhu H,Wang Y P.Grid Dependent Tasks Security SchedulingModel and DPSO Algorithm[J].Journal of Networks,2011,6(6):850-857
[19] Hou E S H,Ansari N.Genetic algorithm for multi-processor scheduling[J].IEEE Transactions on Parallel and Distributed Systems,1994,5(2):113-120
[20] Ricardo C C,Afonso F,Pascal R.Scheduling multiprocessortasks with genetic algorithm[J].IEEE Transactions on Parallel and Distributed Systems,1999,10(8):825-837
[21] 徐雨明,朱宁波,欧阳艾嘉,等.异构系统中DAG任务调度的双螺旋结构遗传算法[J].计算机研究与发展,2014,51(6):1240-1252 Xu Yu-ming,Zhu Ning-bo,Ouyang Ai-jia,et al.A Double-Helix Structure Genetic Algorithm for Task Scheduling on Heterogeneous Computing Systems[J].Journal of Computer Research and Development,2014,1(6):1240-1252

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed