| 摘要: |
| 移动边缘计算技术为低时延要求、资源敏感的计算任务需求提供解决方案，通过研究任务请求特征以提高调度算法效率是边缘计算的重要研究方向。不同于现有研究将任务请求特征建模为单一随机变量的做法，提出基于任务请求生灭过程模型的边缘计算架构，将求解最优调度决策的过程建模为无限期平均成本马尔可夫决策过程。在使用贝尔曼方程分析问题的过程中，利用任务的生灭特性对未来的请求到达做出估计以判断当前决策对未来系统时延能耗成本的影响，进而辅助确定当前状态的最优决策，并结合任务相关性感知提出批处理任务调度控制算法。所提算法根据生灭状态信息对策略迭代的状态空间和决策空间进行剪枝以降低策略改进的复杂度，突破了策略迭代算法的复杂度瓶颈。仿真结果表明，所提算法相较于传统的策略迭代算法具有明显的低复杂度优势，且能在不同系统条件下保持低时延、能耗成本。 |
| 关键词: 边缘计算 生灭过程 批处理调度决策 马尔可夫决策过程 |
| DOI：10.20079/j.issn.1001-893x.220916002 |
|
| 基金项目:国家自然科学基金资助项目（61771307）；教育部-中国移动科研基金（MCM20180102）；上海市市级科技重大专项（2021SHZDZX0102） |
|
| Batched Scheduling for MEC Systems with Task Birth-Death Dynamics:Analysis and Optimization |
| LUO Yu,GU Yixiao,XIA Bin |
| (School of Electronic Information and Electrical Engineering,Shanghai Jiao Tong University,Shanghai 200240,China) |
| Abstract: |
| Mobile edge computing technology provides solutions for latency and resource sensitive computing tasks and it is important to improve the efficiency of scheduling algorithms through task features.Unlike existing researches that model task request characteristics as a single random variable,this paper proposes an edge computing architecture based on the birth-death feature of tasks,modeling an infinite horizon average cost Markov decision process(MDP).In the process of analyzing the problem using the Bellman equation,the birth-death characteristics of the task are used to estimate the future request arrivals to determine the impact of the current decision on the future system cost,and then assist in determining the optimal decision for the current state,and propose a batched scheduling control algorithm.The proposed algorithm prunes the state space and decision space of policy iteration based on the birth-death information to reduce the complexity of policy improvement,which breaks the complexity bottleneck of policy iteration algorithm.Through numerical results,it is inferred that the proposed algorithm has obvious low-complexity advantages over the traditional policy iteration algorithm and can maintain low latency and energy cost under different system conditions. |
| Key words: edge computing birth-death process batched scheduling Markov decision process |
