异构动态边缘计算系统中任务图自适应卸载与在线实时调度算法研究

发布时间：2020-10-27 04:35

　　 作为下一代云计算系统的发展趋势,移动边缘计算(Mobile Edge Computing,MEC)能够在网络边缘就近地提供高带宽、低时延的“边缘云”服务,弥补了移动云计算的不足。其中,用户委派MEC系统执行计算任务的过程,称为计算卸载。作为MEC领域的核心技术,计算卸载的研究成果虽不断涌现,但依然存在不足:首先,现有算法研究针对异构场景的考虑相对匮乏,但未来该场景将随着异构组网技术的普及而广泛存在;其次,生产环境下诸多服务多由相互依赖的细粒度子任务构成,而针对子任务的卸载研究虽然能够大幅提升性能表现,但却鲜少有人问津;另外,非专用系统中普遍真实存在的动态性问题,更因其复杂性而缺乏关注。鉴于此,本文立足于动态且异构的Het-MEC系统,考虑了任务图模型,着眼于计算卸载中指派决策和调度执行两个阶段,分别研究了用户端自适应计算卸载和服务端在线实时调度两个问题。诚然,本研究面临众多挑战,如异构场景下决策标准的差异化难题、任务图模型下细粒度算法设计的较大难度、动态环境中决策结果的偏差或失效等。在并存的机遇与挑战下,本文提出了下述新颖且高效的应对算法:一是针对卸载决策阶段,本文提出了自适应卸载决策算法(ADaptive Computing Offloading,ADCO),旨在为动态Het-MEC系统中的移动用户,解决如何决策指派使任务图总体完工时间最短的问题。ADCO算法的关键思想在于在分散的时机将关键任务重复卸载至不同服务器中同时执行,从而高效地自适应于系统异常波动,并有效地规避了单点失效风险。ADCO算法还在决策前对待卸载任务图进行聚类预处理,减小了问题规模,降低了卸载过程的通信开销。此外,依托于列表调度的迭代框架,ADCO算法能够以较低的时间开销实现较高的卸载性能表现。实验表明,同比对照组,ADCO算法下任务图总体完工时间最高下降超过50%,且资源依赖性更低、规模扩展性更强。二是针对调度执行阶段,本文设计了在线链表调度算法(名为弹簧滑轨调度,Spring SLideway Scheduling,SSLS),旨在为硬实时任务图动态到达的边缘服务器,解决如何在线调度使长期平均拒绝服务率最低的问题。为了健壮地自适应于异常请求激增,SSLS通过将任务时序约束定义为其弹性指标,允许任务开始时刻在弹性限度内任意变动,以充分利用资源碎片扩充调度空间。为了实现高度灵活性,SSLS创新地将等待队列建模为线性链表,以迭代而非构造的插入式链表操作进行调度。同时,得益于失败任务的重调度调整机制,SSLS不仅拒绝率低而且长期稳定,具有在线运行适用性。实验表明,SSLS算法的长期拒绝服务率最高仅为对照组相应指标的10%上下,且可扩展性和硬实时适应性更强、资源依赖性更低。
【学位单位】：华中科技大学
【学位级别】：硕士
【学位年份】：2019
【中图分类】：TN929.5;TP301.6
【部分图文】：

裹挟于移动互联风起云涌的洪流，移动云计算技术（MobileCloudComputing, MCC）迎来了高速发展。因可靠性高、扩展性佳、运算力强，从龙头巨擘至初创小微，莫不以该技术作为移动应用的基础支撑。譬如国际电商巨头亚马逊的专业云服务（AmazonWebServices,AWS）通过部署在全球各地数据中心、数量超过200 万台的云服务器，为 190 多个国家和地区的成千上万家企业提供云平台支持[1]。如今，站上工业 4.0 时代的新业态风口，移动应用面临愈发严苛的服务质量（Quality-of-Service, QoS）要求[2]；大数据 2.0 的时代演进为海量数据的井喷式增长推波助澜[3]；而 5G 承载技术的成熟与落地，势必使核心网络罹受更为苛刻的考验[4]。如此形势下，提供中心式服务的 MCC 恐将身陷囹圄，难以实现毫秒级响应的宏大愿景[3]：一方面，涌向数据中心的海量请求造成的网络拥堵使实时通信难以实现；另一方面，数据中心的繁重负载使其极易成为延缓响应的服务瓶颈；更甚者，数据中心的高昂扩容成本显然不相适应于指数级飙升的需求规模。因此，下一代云服务系统的设计需求迫在眉睫、呼之欲出，激发了国内外研究者踊跃研究的热忱[5]。

图 1.2 计算卸载技术的概念与流程计算卸载技术具有重要价值：对于移动用户而言，计算卸载技术扩展了移动设备的计算能力，节约了能耗开销，其运行时间得以延长[9]，用户体验得以提升；对于运营商和服务提供商而言，计算卸载技术使网络资源得以充分利用，生产效率得以提高，能够创造巨大效益。在 MEC 研究领域中，计算卸载技术更因其较高的研究价值而备受高度关注。Mach 等人[8]在全面考察了多种 MEC 系统后明确指出：计算卸载技术是 MEC 系统的三大设计要素之首，是最关键的核心技术要素。故可言，MEC 系统的服务质量高低直接取决于计算卸载算法的性能表现好坏，因而具备重大的理论意义。综上可知，本文针对计算卸载领域的研究选题兼具实用和理论双重意义。1.2.2 现有计算卸载研究的不足近年来，计算卸载技术研究领域已涌现出大量相关文献和成果[30-53]。然而，虽然

4图 1.3 Het-MEC 系统的部署环境源丰富的同构服务器集群构成。图 1.3 展示了 Het-MEC 系统典型的部署网络环境及其地理分布特性。由此可见，基于 Het-MEC 场景的计算卸载研究因更为贴合实际而具有实用价值。然而，目前大多的计算卸载研究集中在单用户模型或多用户单服务器模型[33-35,48-51]，而基于 Het-MEC 模型的相关研究较为匮乏。二是任务图模型下细粒度算法少人问津。生产环境下的服务和应用通常由多个相互依赖的任务、模块构成。例如，图 1.4 展示了智能家居监控系统的依赖性模块结构[3]。通常，上述依赖性结构可被建模为有向无环图[58]（DirectedAcyclicGraph,DAG）。图 1.4 智能家居监控系统的依赖性模块结构研究任务图模型下的细粒度计算卸载决策算法意义卓著：除了更为贴合真实的应用场景，细粒度卸载算法通常还更为精密高效，不仅能提升系统资源利用率，而且能大幅增加计算并行度、减少响应时间[3]，更具场景通配性以及性能卓越性，拥有广阔的实用价值和市场前景。然而
【相似文献】

相关期刊论文 前10条

1 张春开;;基于任务图示的写作生成实践[J];英语教师;2013年01期

2 张德富，吴巧泉;基于任务图的一种并行程序设计方法（Ⅰ）──任务图的设计[J];软件学报;1995年06期

3 周本海;乔建忠;林树宽;;多核处理平台上任务图模型的并行调度策略研究[J];小型微型计算机系统;2012年11期

4 周军;张强;于晓洲;;利用层次任务图和多种群遗传算法的可重构计算任务划分[J];计算机辅助设计与图形学学报;2011年03期

5 刘键,张静;含过程任务图的调度[J];计算机工程与科学;1997年01期

6 郭兆阳;;基于遗传算法的软硬件协同设计探索[J];集成电路应用;2005年01期

7 郭兆阳;基于遗传算法的软硬件协同设计探索[J];真空电子技术;2005年02期

8 杨峰;张建军;;广义Fork-Join任务图的调度问题研究[J];兵工自动化;2009年12期

9 李庆华,阮幼林,刘干,蒋盛益,杨世达;一个调度Fork-Join任务图的最优算法(英文)[J];软件学报;2005年05期

10 杨峰;张建军;;一个新的Fork任务图的调度算法[J];兵工自动化;2010年03期

相关博士学位论文 前2条

1 张建军;基于Fork-Join任务图的调度算法研究[D];华中科技大学;2010年

2 马天义;低功耗软硬件划分算法研究[D];哈尔滨工业大学;2009年

相关硕士学位论文 前10条

1 翟金亭;“神威·太湖之光”上某流体力学应用的任务图并行化研究[D];山东科技大学;2018年

2 张超;异构动态边缘计算系统中任务图自适应卸载与在线实时调度算法研究[D];华中科技大学;2019年

3 郭强;“神威·太湖之光”上tend_lin应用的任务图并行优化研究[D];山东科技大学;2018年

4 高希然;“神威·太湖之光”上任务图并行调度优化研究[D];山东科技大学;2018年

5 马啸;基于任务图分割与膜计算的仿生阵列自组织方法[D];国防科学技术大学;2016年

6 杨俊;多核系统静态任务调度问题研究[D];合肥工业大学;2016年

7 Mohammed Ali Hasan Al-towayti;Chombo中的AMRPossion应用的DAG并行化[D];山东科技大学;2017年

8 孔德华;基于Petri网的并行分布计算中的调度问题的研究[D];山东科技大学;2006年

9 周湖广;P2P环境下基于任务图的感知模型的优化与实现[D];广西大学;2014年

10 王雷;片上网络映射优化算法研究[D];电子科技大学;2010年

本文编号：2858046