基于ILS-PSO算法的移动云计算DAG图的任务调度研究与应用

发布时间：2021-08-26 18:05

　　移动云计算已经深入到人们工作和生活的各个方面,同时也对移动设备的续航时间、计算能力,存储容量和安全性提出了更高的要求。移动云计算网络中的移动设备由于资源有限、通信受限,无法满足复杂应用的要求。为了解决移动云计算环境下复杂应用的有效使用问题,对移动设备网络和DAG任务图进行深入研究,将复杂应用分解成多个不相交的集合分配给移动设备并行执行,满足移动设备电池容量的约束下,提出了粒子群优化（PSO）算法求解最优调度方案的方法,并且应用迭代局部搜索（ILS）策略,保证了全局和局部搜索的平衡。 

【文章来源】：计算机与数字工程. 2020,48(03)

【文章页数】：7 页

【部分图文】：

实验1的结果475020406080100迭代次数340

递增到300，观察轮转算法（RR），贪心算法（Greedy）、PSO和ILS-PSO求解不同数目的任务调度问题的性能差异。本文采用文献［26］的方法，根据任务数随机生成DAG任务图，任务的长度为[20000?30000]上的随机整数。每个实验重复20次，实验结果取平均值来降低误差。实验1结果如图1所示。可以看出PSO具有优化性能好、快速收敛的优点，然而迭代进行到了40次左右的时候，优化陷入了局部最优解，随着迭代次数的增加，搜索性能不再有明显变化。实验2结果如图2所示。由实验1的结果可以，迭代次数到达45次左右时，PSO算法进入局部最优，所以最大迭代次数小于45的时候，随着最大迭代次数的增加，PSO搜索性能持续提升；当最大迭代次数接近并且超过45的时候，PSO搜索性能提升缓慢直到不再有明显变化。对于ILS-PSO算法，当PSO搜索陷入局部最优时，通过多次扰动到临近区间迭代求解更优解，求解出近似全局最优解。020406080100迭代次数480460440420400380360340适应度图1实验1的结果020406080100最大迭代次数475450425400375350325300最大完成时间图2实验2的结果050100150200250300任务数量17501500125010007505002500最大完成时间图3实验3的结果实验3的结果如图3所示。可知PSO和ILS-PSO在初期搜索优势并不明显，这是由于任务数量较少时，DAG图的复杂程度较低，可以使用Greedy算法求解出较好的结果。随着任务数量的增加，DAG图的复杂程度剧增，可以看出RR和Greedy的最大完成时间与任?

【参考文献】：
期刊论文
[1]分布式系统下的启发式任务调度算法[J]. 贾丽云,张向利,张红梅.  计算机工程与应用. 2017(12)
[2]移动云计算研究进展与趋势[J]. 崔勇,宋健,缪葱葱,唐俊.  计算机学报. 2017(02)
[3]5G网络架构设计与标准化进展[J]. 朱浩,项菲.  电信科学. 2016(04)
[4]基于自适应惯性权重的均值粒子群优化算法[J]. 赵志刚,林玉娇,尹兆远.  计算机工程与科学. 2016(03)
[5]求解RCPSP问题的迭代局部搜索算法研究[J]. 赵轩.  现代计算机(专业版). 2016(08)
[6]异构云环境多目标Memetic优化任务调度方法[J]. 李智勇,陈少淼,杨波,李仁发.  计算机学报. 2016(02)
[7]基于ILS-CS优化算法的个性化旅游线路研究[J]. 侯乐,杨辉华,樊永显,李灵巧,蒋淑洁.  计算机科学与探索. 2016(01)
[8]基于拟合与粒子群优化的VG方程参数估计[J]. 曹怀火,欧阳艾嘉,艾海男.  计算机工程与应用. 2013(11)
[9]基于粒子群优化的异构多处理器任务调度算法[J]. 李静梅,张博,王雪.  计算机应用研究. 2012(10)
[10]基于量子粒子群优化的DAG并行任务调度研究[J]. 张聪,沈惠璋.  计算机应用研究. 2010(07)



本文编号：3364711