【作者】 张超；

【导师】 董燕； 胡梦兰；

【作者基本信息】 华中科技大学 ， 信息与通信工程， 2019， 硕士

【摘要】 作为下一代云计算系统的发展趋势,移动边缘计算(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%上下,且可扩展性和硬实时适应性更强、资源依赖性更低。更多还原

【Abstract】 As the development trend of next generation of cloud service system,a new computing paradigm called Mobile Edge Computing(MEC)can provide "edge cloud" services with high bandwidth and low latency near the edge of the network,which is expected to make up for many shortcomings of centralized mobile cloud computing.In the field of MEC,Computing Offloading refers to the process in which mobile users assign MEC systems to perform demanding tasks.As the core technical element,Computing Offloading technology,with both practical and theoretical significance,arouses many researchers’ enthusiasm for research.Despite the continuous emergence of relevant literature,there are still some deficiencies in this field,such as the lack of heterogeneous scenarios,the lack of interest independent task models,and the lack of attention to the dynamic non-dedicated environmental conditions.Given this,the research of this paper is based on dynamic and heterogeneous edge computing scenarios and consider the dependent tasks model.We focus on two phases of offloading decision and scheduling execution in the computing offloading process,and two problems are studied,namely,adaptive offloading decision-making on the client side and hard real-time online scheduling on the server side.Admittedly,this research faces numerous challenges,Firstly,the heterogeneous scenario inevitably leads to the difficulty of differentiating decision criteria.Secondly,the design of fine-grained decision-making algorithm under the model of tasks graph is quite tricky.Thirdly,the highly dynamic and non-dedicated environment is prone to make decision-making results fail.Facing the above challenges,we propose the following novel and efficient coping algorithms.Firstly,for the offloading decision-making phase,this paper proposes an adaptive computing offloading decision-making algorithm named ADaptive Computing Offloading(ADCO),which solves the problem of how to efficiently offload dependent tasks in dynamic and non-dedicated MEC system.To avoid the risk of single point failure,ADCO duplicates the same critical task to different servers at different times.It makes that ADCO not only adapts to the abnormal fluctuation of the system but also disperses the timing of offloading decision-making.Moreover,ADCO innovatively integrates many classical scheduling ideas,such as clustering and listing.The experimental results show that compared to the control group,ADCO makes the average makespan of tasks graph reduce by more than 50%,and the resource dependence of which is lower,but the scale extensibility of which is stronger.Secondly,for the scheduling and execution phase,we design an online and hard real-time scheduling algorithm named Spring SLideway Scheduling(SSLS),which solves the problem of how to efficiently schedule the tasks graphs which dynamically arrive the edge server under the hard-real-time constraint.SSLS regards the waiting queues for computational tasks as "spring slideways",and allows tasks to slide their actual start time without violating the hard real-time and dependency constraints.Benefiting from the iterative rather than constructive list scheduling and rescheduling mechanism,SSLS is not only highly flexible but also conducive to the long-term stable operation for online systems.Experiments show that the long-term average rate of denial-of-service of SSLS is less than 10% of the corresponding indicators of the control group.The extensibility and hard realtime adaptability of SSLS is stronger,and the resource dependence of SSLS is lower.更多还原