针对移动云计算任务迁移的快速高效调度算法

摘要：

计算量较大的应用程序由于需要大量的能耗,因此在电池容量有限的移动设备上运行时十分受限.云计算迁移技术是保证此类应用程序在资源有限的设备上运行的主流方法.针对无线网络中应用程序任务图的调度和迁移问题,提出了一种快速高效的启发式算法.该算法将能够迁移到云端的任务都安排在云端完成这种策略作为初始解,通过逐次计算可迁移任务在移动端运行的能耗节省量,依次将节省量最大的任务迁移到移动端,并依据任务间的通讯时间及时更新各个任务的能耗节省量.为了寻找全局最优解,构造了适用于此问题的禁忌搜索算法,给出了相应的编码方法、禁忌表、邻域解以及算法终止准则.构造的禁忌搜索算法以提出的启发式解为初始解进行全局搜索,并实现对启发解的进一步优化.通过实验将所提方法与无迁移、随机迁移、饱和迁移3类算法进行对比,结果表明提出的启发式算法能够快速有效地给出能耗更小的解.例如,在宽度为10的任务图上,当深度为8时,无迁移、随机迁移与饱和迁移的能耗分别为5461、3357和2271能量单位,而给出的启发解对应的能耗仅为2111.在此基础上禁忌搜索算法又将其能耗降低到1942,这进一步说明了提出的启发式算法能够产生高质量的近似解.

关键词：移动云计算、任务迁移、调度、启发式算法

所属期刊栏目：45

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61672171;广东省教育厅重大科研项目2016KZDXM052;广东省应用型科技研发专项重点2015B010129014

在线出版日期：2018-06-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：94-99,116