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

录用期刊：Peer-to-Peer Networking and Applications (SCI，JCR Q2，CCF 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。