延迟敏感型边缘计算平台中基于分簇的半在线调度方法研究

作     者：冯南之 

作者单位：西安电子科技大学 

学位级别：硕士

导师姓名：赵辉

授予年度：2023年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 080402[工学-测试计量技术及仪器] 0804[工学-仪器科学与技术] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：边缘计算 任务调度 QoS保障 任务最大完成时间优化 

摘      要：边缘计算利用边缘计算节点来分布式处理数据并将它们传给云端,或通过靠近用户端的节点快速响应请求,能较好满足网络应用对于数据处理能力和响应速度的要求。在软件层面,这种高效性很大程度依赖于任务的调度策略。一般的任务调度问题可以分为在线和离线调度,而半在线调度作为一种在线和离线调度方法的折中能在充分规划调度的同时考虑到任务的动态变化。本文讨论了一种半在线调度情景,其中任务的动态变化主要来自于网络通信延迟(下称延迟)对边缘节点性能的影响。以往的大多数工作通常会忽略延迟或将其作为高斯噪声处理,但在地理跨度较大、存在特殊干扰或要求服务实时性等情况下,延迟对于系统工作效率的影响需要被更谨慎地考虑。本文将这类受延迟影响较大的边缘计算平台称为延迟敏感型边缘计算平台,将所讨论的半在线调度情景定义为:在延迟敏感型边缘计算平台中存在部分由延迟引起的性能不确定的节点。 该情景中对变化延迟的预测是一般的在线和离线调度算法难以解决的重点问题,大多情况下它们都无法适应延迟变化为调度过程带来的波动,从而影响提供的服务质量。因此本文以保障服务质量(QoS)和最小化任务完成时间为目标,提出了一种基于分簇的半在线调度方法。该方法包括了一种双目标优化模型、基于分簇的边缘计算平台模型和一个半在线调度算法。各部分的主要工作如下: (1)建立了双目标优化模型。对于QoS保障来说,本文将其定义为不同服务等级的任务在对应时限内的完成情况,如果超出了时限则认为该次请求的服务质量未能得到保障。在任务调度前后的队列中,按照任务服务等级分别进行两次粗细粒度的排序,避免对时间优化目标的影响,同时又能最大程度地保障QoS。对于时间优化模型,本文通过引入节点“模糊度的概念,将节点分类处理,尽可能减少模糊度为系统带来的影响。 (2)提出了基于分簇的边缘计算平台模型。首先在边缘计算平台中设置多个调度器协同管理任务调度,每个调度器负责一个节点簇。其次在每个簇内进一步按照模糊度将节点划分为性能已知、不定、未知三类分别进行处理,以尽能减少延迟变化对于任务调度的影响。最后,在任务调度过程中根据簇之间的负载状况动态地调整簇容量,从而应对更复杂的现实情况。 (3)提出基于映射的半在线调度算法MSSA。该方法通过两个阶段实现对独立非抢占式任务的批调度。第一阶段:对于等待调度的某个任务生成3个候选节点,其中的2个使用完全随机过程挑选,1个是固定选择的本地节点,之后再从3个候选节点中剔除1个路由距离最大的节点;第二阶段:在当前大小为2的候选集合中挑选排队延迟最短的节点作为最终的分配目标。重复以上过程直到一批任务都绑定了各自被分配的节点。在调度过程中,如果遇到性能未知的节点则查询性能映射表获取该节点性能。在调度结束后,根据本批次调度结果更新性能映射表。MSSA以O(n)的复杂度实现双目标优化,大幅度降低调度算法自身开销的同时有效调度任务。 最后本文使用Cloud Sim仿真平台并引入来自真实系统的数据集进行更真实的模拟仿真,与经典启发式调度算法和其他算法进行对比。最终,实验结果表明本文所提出的调度方法能有效提升延迟敏感型边缘计算平台的工作效率,在QoS保障度方面高出其他方法19%,任务完成耗时平均降低了26%。