高级检索
    刘泽宁, 李凯, 吴连涛, 王智, 杨旸. 多层次算力网络中代价感知任务调度算法[J]. 计算机研究与发展, 2020, 57(9): 1810-1822. DOI: 10.7544/issn1000-1239.2020.20200198
    引用本文: 刘泽宁, 李凯, 吴连涛, 王智, 杨旸. 多层次算力网络中代价感知任务调度算法[J]. 计算机研究与发展, 2020, 57(9): 1810-1822. DOI: 10.7544/issn1000-1239.2020.20200198
    Liu Zening, Li Kai, Wu Liantao, Wang Zhi, Yang Yang. CATS: Cost Aware Task Scheduling in Multi-Tier Computing Networks[J]. Journal of Computer Research and Development, 2020, 57(9): 1810-1822. DOI: 10.7544/issn1000-1239.2020.20200198
    Citation: Liu Zening, Li Kai, Wu Liantao, Wang Zhi, Yang Yang. CATS: Cost Aware Task Scheduling in Multi-Tier Computing Networks[J]. Journal of Computer Research and Development, 2020, 57(9): 1810-1822. DOI: 10.7544/issn1000-1239.2020.20200198

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

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

    • 摘要: 随着越来越多数据的产生以及更加强大的算力和算法的运用,物联网应用也变得越来越智能.典型的物联网应用也从简单的数据感知、收集和表示转向复杂的信息提取和分析.这一持续的趋势需要多层次算力资源及网络.多层次算力网络涉及云计算、雾计算、边缘计算和海计算等技术之间的相互协作,分别针对区域级别、本地级别和设备级别的物联网应用.但是,由于计算技术的不同特征以及任务的不同需求,如何有效地进行任务调度是多层次算力网络中的一个关键挑战.此外,如何激发多层次算力资源的积极性也是一个关键问题,这是多层次算力网络得以成形的前提.为解决上述挑战,提出了一个云雾混合多层次算力网络及计算卸载系统,定义了一个由时延、能耗及付费组成的加权代价函数,并建模了一个代价感知任务调度(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.

       

    /

    返回文章
    返回