ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2020, Vol. 57 ›› Issue (9): 1810-1822.doi: 10.7544/issn1000-1239.2020.20200198

Special Issue: 2020边缘计算专题

Previous Articles     Next Articles

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).

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

CLC Number: