当前位置: 主页 > 学术动态 >

移动边缘计算中面向物联网批处理作业收益优化的任务调度和资源管理

点击数:   更新日期: 2021-01-14

论文标题Revenue-Optimal Task Scheduling and Resource Management for IoT Batch Jobs in Mobile Edge Computing

录用期刊:Peer-to-Peer Networking and Applications (SCIJCR Q2CCF C类)

作者列表:

1)黄霁崴 中国石油大学(北京) 信息科学与工程学院 教授

2)李松远 北京邮电大学 网络与交换技术国家重点实验室 2018级硕士

3    北京信息科技大学 计算机学院 副教授

原文DOI:  https://doi.org/10.1007/s12083-020-00880-y

基于边缘计算架构的QoS感知任务调度和资源管理方法



QoS感知的任务调度和资源管理方法针对移动边缘计算架构设计,如上图所示。边缘服务供应商将多个边缘服务器部署在各处基站的位置,基站负责和用户维持数据通信和任务交互,用户提交的任务请求在边缘服务器端处理。用户的任务请求通常被调度到邻近的边缘服务器,所以相较于将任务调度到远程云端,大幅减少了任务响应时间和任务传输带宽。在用户分布密度较大的区域(如城市中央商务区),与用户邻近的边缘服务器会有多个。本部分充分考虑如上情况的任务调度策略。同时,一个边缘服务器在相应基站的信号覆盖范围内通常被多个用户共享,而多个用户间达成对边缘服务器的资源竞争关系。用户在边缘服务器内分配得到更多计算资源,意味着更快的任务处理速度,即更高的QoS。因此,本部分也同时关注边缘服务器内的资源管理问题。

本部分的任务调度和资源管理充分了时间动态性,用户跨边缘基站的信号覆盖范围操作位置移动。任务调度和资源管理算法,在不同的时间槽下,根据当前各用户位置和边缘服务器计算资源使用情况,做出任务调度和资源管理的决策。决策结果满足多用户的QoS需求,并且最大化边缘供应商的总服务收益,维护边缘服务生态的可持续性发展。

具体地说,首先,建立关于移动边服务动态过程的数学模型,给出QoS指标(即任务响应时间)的计算解析式。其次,基于模型描述,设计最大化边缘服务供应商收益的优化模型,并以用户QoS需求作为优化模型的约束条件。然后,针对优化模型,设计高效的调度算法,分析算法时间复杂度。最后,基于边缘计算数据集,设计仿真实验,验证调度算法的有效性和高效性。

基于移动边缘架构的QoS感知任务调度和资源管理方法

1. 最大化边缘供应商收益的任务/资源优化模型

用户发起的任务请求允许跨边缘端地调度到多个边缘服务器。αi,j(t)表示于时间槽t分配给用户i的任务请求的、位于边缘服务器j的资源实例数量。任务/资源的优化决策在每个决策时间槽Γ执行。优化目标是最大化边缘供应商收益,收益来自各用户上报的服务预算Bi。任务/资源优化模型的形式化定义如下图所示,资源约束表示在每个时间槽t向所有用户分配的总资源数量不超过资源容量,而QoS约束表示对任务请求i的调度和资源决策仅在任务执行期限前操作。

任务/资源优化模型

2. 基于线性规划的任务/资源决策模型

上图定义的优化模型是整数规划(Integer Programming, IP)问题,属于NP难题。 因此,借助优化约束式的完全幺模性质,利用λ-优化求解技术,上图的整数规划问题可以通过线性规划技术等效地求解。线性规划问题可以使用高效算法(如单纯形算法,内点法)和求解器(如MOSEK,CPLEX)求解。基于线性规划的决策优化模型如下图所示。

线性规划决策模型

3. 跨边缘端的动态任务调度和资源管理算法

下图算法叙述了跨边缘端的任务调度和资源管理算法,实现了边缘供应商收益的最大化。当为用户的服务请求提供调度决策时,同时确定分配的边缘资源数量。对任务调度和资源管理的决策沿着决策时间槽Γ动态执行;在每一决策时间槽Γ,更新各移动用户的位置信息,收集新提出的任务请求,并依此操作决策。

任务调度和资源管理算法

实验结果

边缘供应商在不同算法下的服务收益

移动物联网设备在不同算法下的任务完成率

不同移动IoT设备规模下边缘供应商的服务收益

不同系统规模下的算法运行时(系统规模指,移动IoT设备/边缘服务器的数量)

经过实验验证,我们算法的有效性和效率得到充分验证。

作者简介

黄霁崴 博士,教授,博士生导师,石油数据挖掘北京市重点实验室主任,中国石油大学(北京)计算机科学与技术系主任。2015年度北京市优秀人才,2018年度中国石油大学(北京)优秀青年学者,2020年度北京市科技新星。分别在2009年和2014年于清华大学计算机科学与技术系获得工学学士和工学博士学位,2012-2013年国家公派赴美国佐治亚理工学院联合培养。研究方向包括:系统性能评价和优化、随机模型理论和应用、服务质量测量与保障技术、服务计算和物联网等。担任中国计算机学会(CCF)服务计算专委会委员,CCF高级会员,IEEE、ACM会员。已主持国家自然科学基金、北京市自然科学基金等科研项目13项,在国内外著名期刊和会议发表论文五十余篇,出版学术专著1部,获得国家发明专利5项、软件著作权3项,担任多个国际顶级期刊和知名会议审稿人。联系邮箱:huangjw@cup.edu.cn。