Journal of Frontiers of Computer Science and Technology ›› 2021, Vol. 15 ›› Issue (1): 73-83.DOI: 10.3778/j.issn.1673-9418.2001043

• Science Researches • Previous Articles     Next Articles

Combinatorial Auction-Based Mechanism for Task Offloading in Edge Computing

LI Yinghao, SONG Tian, YANG Yating   

  1. School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China
  • Online:2021-01-01 Published:2021-01-07

面向边缘计算的组合拍卖式任务卸载机制

李颖浩嵩天杨雅婷   

  1. 北京理工大学 计算机学院,北京 100081

Abstract:

In the era of the Internet of everything, the rapid increase in data volume and computation demand has prompted the evolution of application deployment mode from cloud computing to edge computing in order to reduce bandwidth consumption and response delay. However, there is a two-way selection problem between the application service provider (ASP) and the edge computing provider (ECP) in the process of task offloading. To solve this pro-blem, this paper proposes a combinatorial auction-based mechanism for task offloading in edge computing. First, this paper establishes a system model, explains the key issues of model implementation, proposes a heuristic task sel-ection algorithm for ECPs based on the analysis of their bidding process where choosing tasks to maximize resource utilization is proven to be an NP-complete problem, and then designs two auction algorithms, single-winner auction and multi-winner auction to fit trust-first and efficiency-first scenarios respectively. The experimental results show that compared with the single auction mechanism, the proposed scheme improves the utilization of ECP resources by 13%, and increases the utility of ASP by 37%.

Key words: edge computing, task offloading, combinatorial auction, bidding

摘要:

在万物互联的时代,数据量与计算需求飞速增长,促使应用部署方式由云计算模式向边缘计算模式演进,以解决带宽消耗严重和响应时延过高等问题。为推进面向边缘网络的任务卸载,需要解决应用服务提供商(ASP)与边缘计算提供商(ECP)之间的双向选择问题。针对这一问题,提出一种面向边缘计算的组合拍卖式任务卸载机制。首先建立系统模型,并对模型落地的关键问题进行说明,然后分析ECP的投标决策过程,证明选择最大化资源利用率的任务组合是NP完全问题,进而提出一种启发式任务选择算法。在此基础上,设计两种拍卖算法,单胜者拍卖和多胜者拍卖,分别适用于可信度优先和效率优先的场景。实验结果表明,相较于单项拍卖机制,所提出的方案提高ECP资源利用率达13%,同时增加ASP收益达37%。

关键词: 边缘计算, 任务卸载, 组合拍卖, 竞价