多层次算力网络集中式不可分割任务调度算法

巩宸宇 舒洪峰 张昕

摘要：根据算力网络不同层次的特性和各种应用的不同需求，提出一种多层次算力网络模型和计算卸载系统，并定义一个由时延、能耗组成的加权代价函数以建模一个任务调度问题。为解决这一问题，提出一个基于交叉熵的集中式不可分割任务调度（CUTS）算法。数值仿真结果表明，与其他基线算法相比，该算法在系统平均代价方面拥有较好的性能。

关键词：多层次算力网络；交叉熵；集中式；任务调度；不可分割

Abstract： According to the characteristics of different layers of computing power network and different requirements of various applications， a multi-tier computing power network model and computation offloading system are proposed. Specifically， a cost function consisting of latency and energy consumption to model a task scheduling problem is defined. To solve the problem， a centralized unsplittable task scheduling （CUTS） algorithm based on cross-entropy is introduced. Simulation results show that the algorithm provides superior performance in terms of the average system cost compared with other baseline solutions. Keywords： multi-tier computing power network； cross-entropy； centralized； task scheduling； unsplittable

近年来，随着深度学习的不断发展，人工智能服务和应用大量涌现，比如人脸识别、自然语言处理、虚拟现实、增强现实等。这些应用通常都是计算密集型任务，将消耗大量的终端资源（如算力和能耗）。然而，由于计算能力和能量供应有限，终端设备（例如手机）可能无法提供良好的服务质量。为此，研究者们提出云计算的概念。

云计算[1-2]是由分布式计算、并行处理、网格计算发展而来的新型计算模型。通过虚拟化技术建立强大的资源池，云计算使各种应用和服务能够按需获取算力、存储资源及各种软件资源。云计算为海量数据的处理提供了可能，同时也为计算密集型的人工智能应用提供了强大的算力。然而，端与云之间的传输时延使得云计算无法满足时延敏感型应用的需求。因此，雾计算和边缘计算[3-4]的概念被提出，以解决云计算传播时延大的问题。

边缘计算是指，在靠近物或者数据源头的一侧部署设备，提供计算、存储等软件服务，并通过算力和通信资源的联合分配，满足应用的时延需求。经典的边缘计算网络由雾节点和本地用户共同组成。其中，本地用户通过任务拆分和任务卸载决策，来达到全局时延和能耗最小的最优效果。此前，学者们的研究主要集中在单用户多节点[5-6]和多用户单节点[7-8]。文献[9]研究了多用户多节点这一应用场景。研究表明，边缘计算可以降低传输时延。但是对于一些对算力和时延都有较高要求的应用来说，边缘计算网络将不再适用，比如自动驾驶、虚拟现实等。因此，算力网络[10]的概念被提出。

算力网络涉及云计算、雾计算、边缘计算等。算力网络是由云边端等设备构成的多层次资源网络，它能够将云边端进行统一调配，但是如何实现系统的最优性能仍是一个难题。原因主要有两点：（1）云边端各有其特性。云距离端较远但算力强，多用于处理全局任务；边距离端较近但算力弱，多处理本地实时任务。（2）用户任务的需求不同。计算密集型任务可能更多地需要云的参与，时延敏感型任务可能更多地需要边的参与，对算力和時延同时有较高要求的任务则需要联合进行调度。基于以上原因，文献[11]研究了多层次算力网络，并提出一种分布式调度算法。但是该模型是边端混合的两层算力网络，并未考虑云的作用。

试想存在如下场景：一座办公大楼内有多个楼层，每层都有多间办公室，且每间办公室都有多个用户和不同性质的任务。由于职能划分不同，不同部门通常所需要的算力不尽相同。这就容易造成算力资源的不合理利用，甚至造成任务中断。如果我们按照办公室和楼层的位置，将其构造成一个多层次算力网络，进行任务的调度和算力分配，那么就能够更好地满足计算密集型和时延敏感型应用的需求。

1计算卸载系统建模

1.1系统概述

本节将详细介绍一个多层次算力网络和计算卸载系统，定义一个由时延、能耗组成的加权代价函数，并建模一个任务调度问题。

算力网络一共有多层。第1层为用户节点，其他层为雾节点。雾节点的算力随层数的增加而上升。通常，距离用户较远的高层雾节点算力比较强大，但是往返时延较长；距离用户较近的低层雾节点往返时延较短，但是算力有限。在考虑时延和能耗的基础上，用户可以将不可拆分的任务卸载到某层的某个雾节点，也可以选择将任务在本地执行。因此，如何根据时延和能耗帮助用户做出卸载决策，是解决任务调度问题并获取全局最优解的核心。

3实验与结果

3.1仿真设置

我们假设存在这样一个多层次算力网络（参数设置如表1所示）。该网络为3层算力网络：第1层有多个用户，第2层有10个雾节点，第3层有1个雾节点。用户的任务不可拆分。用户先将任务卸载到第2层雾节点，其他层的雾节点之间通过有线进行连接。假设雾节点的初始状态都为无其他任务在运行。

與CUTS算法相对比的几种基准方法为：

（1）本地计算：每个用户都在本地运行任务；

（2）云计算：每个用户都将任务卸载到云端；

（3）随机卸载：每个用户做出的卸载决策是随机的。

本文以下仿真结果均为400次仿真结果的平均值。

3.2系统平均代价

如图2所示，随着用户数的变化，CUTS算法总是能够取得最优的系统平均代价。本地计算通信时延较小，然而总代价却高于多层算力网络，这说明引入算力网络有效解决了本地计算算力较小的问题。图3展示了当用户的任务性质不同时，不同算法的效果。当α值较大时，任务性质偏向时延敏感型。因为云端距离用户较远，通常具有比较大的时延，从图3中我们可以看出，引入多层算力网络可以有效解决云计算网络存在的延迟大的问题。

3.3受益用户数

图4展示了在不同算法下的受益用户数。受益用户是指，在当前卸载策略下降低自身处理任务代价的用户。除随即卸载算法外，其他算法的受益用户数都与总用户数呈正相关。由图4可知，CUTS算法依然表现出最优性能。

3.4时延及能耗成本分布

图5展示了随着用户数目的增加，时延和能耗的对比情况。可以看出，随着总用户数的增加，总的代价也在增加，但是增加幅度在减缓。此外，时延产生的代价要略高于能耗产生的代价。

3.5本地计算、雾计算和云计算用户分布

图6展示了随着用户数增加，各用户的卸载决策分布。可以看出，选择本地用户和云计算的用户数目逐渐增多，而选择雾节点的用户数却几乎不变。这是因为雾节点的算力资源接近饱和。

4结束语

本文中，我们提出一种多层次算力网络模型和计算卸载系统，定义一个由时延、能耗组成的加权代价函数，并建模一个任务调度问题。为解决这一问题，我们提出CUTS算法，即将一个确定性问题转化成了一个估计问题，通过重要性采样和交叉熵的方法来求解问题的最优解。数值仿真结果表明，CUTS算法能够在系统平均代价和受益用户数方面提供最优性能。算力网络可以有效解决单层网络带来的算力小或时延大的问题。

致谢

本研究得到上海科技大学杨旸老师、吴连涛老师的帮助，谨致谢意！

参考文献

[1] REN J K， HE Y H， YU G D， et al. Joint communication and computation resource allocation for cloud-edge collaborative system [C]// 2019 IEEE Wireless Communications and Networking Conference （WCNC）. Marrakesh， Morocco： IEEE， 2019： 1-6. DOI： 10.1109/ WCNC.2019.8885877

[2] MOURADIAN C， NABOULSI D， YANGUI S M， et al. A comprehensive survey on fog computing： state-of-the-art and research challenges [J]. IEEE communications surveys & tutorials， 2018， 20（1）： 416-464. DOI： 10.1109/ COMST.2017.2771153

[3] LIU Z N， YANG Y， CHEN Y， et al. A multi-tier cost model for effective user scheduling in fog computing networks [C]//IEEE INFOCOM 2019 - IEEE Conference on Computer CommunicationsWorkshops（INFOCOMWKSHPS）. Paris， France： IEEE， 2019： 1-6. DOI： 10.1109/INFCOMW.2019.8845252

[4] MAO Y Y， YOU C S， ZHANG J， et al. A survey on mobile edge computing： the communication perspective [J]. IEEE communications surveys & tutorials， 2017， 19（4）： 2322-2358. DOI： 10.1109/COMST.2017.2745201

[5] YANG Y， WANG K L， ZHANG G W， et al. MEETS： maximal energy efficient task scheduling in homogeneous fog networks [J]. IEEE Internet of Things journal， 2018， 5（5）： 4076-4087. DOI： 10.1109/JIOT.2018.2846644

[6] DINH T Q， TANG J H， LA Q D， et al. Offloading in mobile edge computing： task allocation and computational frequency scaling[J]. IEEE transactions on communications， 2017，65（8）：3571-3584.DOI： 10.1109/ TCOMM.2017.2699660

[7] CHEN X， JIAO L， LI W Z， et al. Efficient multiuser computation offloading for mobile-edge cloud computing [J]. IEEE/ACM transactions on networking， 2016， 24（5）： 2795-2808. DOI： 10.1109/TNET.2015.2487344

[8] NOWAK D， MAHN T， AL-SHATRI H， et al. A generalized Nash game for mobile edge computation offloading [C]//2018 6th IEEE International Conference on Mobile Cloud Computing， Services， and Engineering （MobileCloud）. Bamberg， Germany： IEEE， 2018： 95-102. DOI： 10.1109/MobileCloud.2018.00022

[9] YANG Y， LIU Z N， YANG X M， et al. POMT： paired offloading of multiple tasks in heterogeneous fog networks [J]. IEEE Internet of Things journal， 2019， 6（5）： 8658-8669. DOI： 10.1109/JIOT.2019.2922324

[10] YANG Y. Multi-tier computing networks for intelligent IoT [J]. Nature electronics， 2019， 2（1）： 4-5. DOI： 10.1038/s41928-018-0195-9

[11] LIU Z N， YANG Y， ZHOU M T， et al. A unified cross-entropy based task scheduling algorithm for heterogeneous fog networks[C]//Proceedings of the 1st ACM International Workshop on Smart Cities and Fog Computing. New York， NY， USA： ACM， 2018： 1-6. DOI： 10.1145/3277893.3277896

[12] SHAH-MANSOURI H， WONG V W S. Hierarchical fog-cloud computing for IoT systems： a computation offloading game [J]. IEEE Internet of Things journal， 2018， 5（4）： 3246-3257. DOI： 10.1109/JIOT.2018.2838022

作者簡介

巩宸宇，上海科技大学信息与技术学院在读硕士研究生；研究领域主要包括物联网与无线通信、雾计算等。

舒洪峰，深圳市智慧城市科技发展集团有限公司副总经理，曾担任深圳市盐田港集团有限公司办公室副主任，深圳市特区建设发展集团有限公司办公室主任、董事会秘书；主要研究领域包括大数据与云计算、5 G及城域物联专网、数字经济等。

张昕，教授级高级工程师，深圳市智慧城市科技发展集团有限公司解决方案部部长，深圳市智能交通标准化技术委员会委员、深圳市政府采购中心资深专家、深圳市后备级领军人才；从事智慧城市、智能交通等政府信息化工作，主持并完成综合交通运行指挥中心、智慧宝安总体规划、路边停车系统、侨香路智慧道路、智慧国资管理展示中心及智慧国资大数据中心等项目；获华夏建设科学技术奖一等奖、中国智能交通协会一等奖、深圳市科技创新奖等省部级奖励（7项）；发表论文与专著2 0余篇，申请发明专利3项，参与编制深圳市地方标准9项。