ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2020, Vol. 57 ›› Issue (9): 1810-1822.doi: 10.7544/issn1000-1239.2020.20200198

所属专题: 2020边缘计算专题

• 网络技术 • 上一篇    下一篇

多层次算力网络中代价感知任务调度算法

刘泽宁1,4,5,李凯2,4,吴连涛2,4,王智3,7,杨旸1,2,4,6   

  1. 1(上海科技大学信息科学与技术学院 上海 201210);2(上海科技大学创意与艺术学院 上海 201210);3(浙江大学控制科学与工程学院 杭州 310027);4(上海雾计算实验室(上海科技大学) 上海 201210);5(紫金山实验室 南京 211111);6(鹏城实验室网络通信研究中心 广东深圳 518000);7(工业控制技术国家重点实验室(浙江大学) 杭州 310027) (liuzy1@shanghaitech.edu.cn)
  • 出版日期: 2020-09-01
  • 基金资助: 
    国家重点研发计划项目(2019YFB1803304);国家自然科学基金重点项目(61932014);华为项目(YBN2019125163)

CATS: Cost Aware Task Scheduling in Multi-Tier Computing Networks

Liu Zening1,4,5, Li Kai2,4, Wu Liantao2,4, Wang Zhi3,7, Yang Yang1,2,4,6   

  1. 1(School of Information Science and Technology, ShanghaiTech University, Shanghai 201210);2(School of Creativity and Art, ShanghaiTech University, Shanghai 201210);3(Department of Control Science and Engineering, Zhejiang University, Hangzhou 310027);4(Shanghai Institute of Fog Computing Technology (ShanghaiTech University), Shanghai 201210);5(Purple Mountain Laboratories, Nanjing 211111);6(Research Center for Network Communication, Peng Cheng Laboratory, Shenzhen, Guangdong 518000);7(State Key Laboratory of Industrial Control Technology (Zhejiang University), Hangzhou 310027)
  • Online: 2020-09-01
  • Supported by: 
    This work was supported by the National Key Research and Development Program of China (2019YFB1803304), the Key Program of the National Natural Science Foundation of China (61932014), and the Huawei Technologies (YBN2019125163).

摘要: 随着越来越多数据的产生以及更加强大的算力和算法的运用,物联网应用也变得越来越智能.典型的物联网应用也从简单的数据感知、收集和表示转向复杂的信息提取和分析.这一持续的趋势需要多层次算力资源及网络.多层次算力网络涉及云计算、雾计算、边缘计算和海计算等技术之间的相互协作,分别针对区域级别、本地级别和设备级别的物联网应用.但是,由于计算技术的不同特征以及任务的不同需求,如何有效地进行任务调度是多层次算力网络中的一个关键挑战.此外,如何激发多层次算力资源的积极性也是一个关键问题,这是多层次算力网络得以成形的前提.为解决上述挑战,提出了一个云雾混合多层次算力网络及计算卸载系统,定义了一个由时延、能耗及付费组成的加权代价函数,并建模了一个代价感知任务调度(cost aware task scheduling,CATS)问题.而且,为激发云和雾的积极性,提出了一个基于计算量的付费模型并将付费相关代价也考虑进总代价.具体来说,根据云和雾的不同特性和需求,分别提出了一个静态付费模型和动态付费模型,从而构建了一个混合付费模型.为解决上述CATS问题,提出了一个基于势博弈的分析框架,并设计了一个分布式任务调度算法——CATS算法.数值仿真结果表明,与集中式最优方法相比,CATS算法可以在系统平均代价方面提供近似最优的性能,并让更多用户受益.此外,与静态付费模型相比,动态付费模型可能可以帮助雾获得更多收入.

关键词: 多层次算力网络, 雾计算, 边缘计算, 计算卸载, 任务调度, 激励机制, 势博弈

Abstract: Due to more data and more powerful computing power and algorithms, IoT (Internet of things) applications are becoming increasingly intelligent, which are shifting from simple data sensing, collection, and representation tasks towards complex information extraction and analysis. The continuing trend requires multi-tier computing resources and networks. Multi-tier computing networks involve collaborations between cloud computing, fog computing, edge computing, and sea computing technologies, which have been developed for regional, local, and device levels, respectively. However, due to different features of computing technologies and diverse requirements of tasks, how to effectively schedule tasks is a key challenge in multi-tier computing networks. Besides, how to motivate multi-tier computing resources is also a key problem, which is the premise of the formation of multi-tier computing networks. To solve these challenges, in this paper, we propose a multi-tier computing network and a computation offloading system with hybrid cloud and fog, define a weighted cost function consisting of delay, energy, and payment, and formulate a cost aware task scheduling (CATS) problem. Furthermore, we propose a computation load based payment model to motivate cloud and fog, and include the payment related cost into the overall cost. To be specific, based on different features and requirements of cloud and fog, we propose a static payment model and a dynamic payment model for cloud and fog, respectively, which constitute the hybrid payment model. To solve CATS problem, we propose a potential game based analytic framework and develop a distributed task scheduling algorithm called CATS algorithm. Numerical simulation results show that CATS algorithm can offer the near-optimal performance in system average cost, and achieve more number of beneficial UEs (user equipment), compared with the centralized optimal method. Besides, it shows that the dynamic payment model may help fog obtain more income, compared with the static payment model.

Key words: multi-tier computing network, fog computing, edge computing, computation offloading, task scheduling, incentive mechanism, potential game

中图分类号: