基于联盟博弈的云任务调度及Shapley值法的收益分配模型  

CLOUD TASKS SCHEDULING BASED ON COALITION GAME AND PROFIT ALLOCATION MODEL WITH SHAPLEY VALUE METHOD

作　　者：张秋霞[1] 何留杰[1] 张来顺[2] Zhang Qiuxia;He Liujie;Zhang Laishun(Modern Education Technology Center,Huanghe Science and Technology College,Zhengzhou 450063,Henan,China;Institute of Electronic Technology,The PLA Information Engineering University of China,Zhengzhou 450004,Henan,China)

机构地区：[1]黄河科技学院现代教育技术中心,郑州河南450063 [2]中国人民解放军信息工程大学电子技术学院,郑州河南450004

出　　处：《计算机应用与软件》2020年第5期275-280,320,共7页Computer Applications and Software

基　　金：2019年度河南省高等学校青年骨干教师培养计划项目(2019GGJS275);2020年度河南省高等学校重点科研项目(20B520015)。

摘　　要：为了优化任务执行跨度及任务执行给资源方造成的代价所形成的总代价,提出一种云计算环境中基于联盟博弈的任务调度算法。建立联盟博弈下的云任务调度模型,定义博弈参与者、博弈策略以及效用函数。设计博弈参与者的支付方式,并证明联盟博弈中任务调度的核是非空的,表明任务调度的博弈解可以得到稳定的联盟结构。设计一种基于Shapley值的博弈参与者对于支付的分配方法,证明了该方法下的收益分配是公平合理的。通过仿真实验,证明了联盟博弈算法不仅可以为个体成员降低执行总代价,且与非合作博弈方法相比具有更高的调度效率。In order to optimize the total cost of task execution makespan and the cost of resource caused by task execution,this paper proposes a task scheduling method based on coalition game in cloud computing environment.We established the cloud tasks scheduling model based on coalition game,and defined the game participant,the game strategy and the utility function.Then,the payment method of game participants was designed,and the core of task scheduling in coalition game was proved to be non-empty,which showed that the game solution of task scheduling could get stable coalition structure.Meanwhile,we designed a distribution method for payment based on Shapley value,and proved that the income distribution under this method was fair and reasonable.Through the simulation experiment,it is proved that the coalition game algorithm can reduce the total execution cost for individual members.Compared with non-cooperative game algorithm,our algorithm has higher scheduling efficiency.

关 键 词：云计算 任务调度 联盟博弈 效用函数 代价优化 执行跨度 

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