Combinatorial Auction-Based Mechanism for Task Offloading in Edge Computing

doi:10.3778/j.issn.1673-9418.2001043

Abstract

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%。

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

LI Yinghao, SONG Tian, YANG Yating. Combinatorial Auction-Based Mechanism for Task Offloading in Edge Computing[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(1): 73-83.

李颖浩, 嵩天, 杨雅婷. 面向边缘计算的组合拍卖式任务卸载机制[J]. 计算机科学与探索, 2021, 15(1): 73-83.

References

[1] ORSINO A, ARANITI G, MILITANO L, et al. Energy effi-cient IoT data collection in smart cities exploiting D2D com-munications[J]. Sensors, 2016, 16(6): 836.
[2] SCHULZ P, MATTHE M, KLESSIG H, et al. Latency criti-cal IoT applications in 5G: perspective on the design of radio interface and network architecture[J]. IEEE Communi-cations Magazine, 2017, 55(2): 70-78.
[3] MAO Y, YOU C, ZHANG J, et al. A survey on mobile edge computing: the communication perspective[J]. IEEE Com-munications Surveys & Tutorials, 2017, 19(4): 2322-2358.
[4] Cisco annual Internet report (2018-2023) white paper[EB/OL]. [2020-03-09]. https://www.cisco.com/c/en/us/solutions/ collateral/executive-perspectives/annual-internet-report/white- paper-c11-741490.html.
[5] SHI W, CAO J, ZHANG Q, et al. Edge computing: vision and challenges[J]. IEEE Internet of Things Journal, 2016, 3(5): 637-646.
[6] SATYANARAYANAN M. The emergence of edge comput-ing[J]. Computer, 2017, 50(1): 30-39.
[7] MAHMUD R, KOTAGIRI R, BUYYA R. Fog computing: a taxonomy, survey and future directions[M]//MARTINO B D, LI K C, YANG L, eds. Internet of Everything. Berlin, Hei-delberg: Springer, 2018: 103-130.
[8] BAHREINI T, BADRI H, GROSU D. An envy-free auction mechanism for resource allocation in edge computing sys-tems[C]//Proceedings of the 2018 IEEE/ACM Symposium on Edge Computing, Seattle, Oct 25-27, 2018. Piscataway: IEEE, 2018: 313-322.
[9] SUN W, LIU J J, YUE Y L, et al. Double auction-based resource allocation for mobile edge computing in industrial Internet of things[J]. IEEE Transactions on Industrial Infor-matics, 2018, 14(10): 4692-4701.
[10] ZHOU B W, SRIRAMA S N, BUYYA R. An auction-based incentive mechanism for heterogeneous mobile clouds[J]. Journal of Systems and Software, 2019, 152: 151-164.
[11] SONG W, ZHAO Y M. A randomized reverse auction for cost-constrained D2D content distribution[C]//Proceedings of the 2016 IEEE Global Communications Conference, Wash-ington, Dec 4-8, 2016. Piscataway: IEEE, 2016: 1-6.
[12] JI G J, ZHANG B X, YAO Z, et al. A reverse auction based incentive mechanism for mobile crowdsensing[C]//Proceed-ings of the 2019 IEEE International Conference on Comm-unications, Shanghai, May 20-24, 2019. Piscataway: IEEE, 2019: 1-6.
[13] WANG Q Y, GUO S T, WANG Y, et al. Incentive mechanism for edge cloud profit maximization in mobile edge comput-ing[C]//Proceedings of the 2019 IEEE International Confe-rence on Communications, Shanghai, May 20-24, 2019. Pis-cataway: IEEE, 2019: 1-6.
[14] AUMANN R J. Lectures on game theory[M]. Boca Raton: CRC Press, 2019.
[15] ZHANG F, LIU G M, FU X M, et al. A survey on virtual machine migration: challenges, techniques, and open issues[J]. IEEE Communications Surveys & Tutorials, 2018, 20(2): 1206-1243.
[16] HARTER T, SALMON B, LIU R, et al. Slacker: fast distri-bution with lazy docker containers[C]//Proceedings of the 14th USENIX Conference on File and Storage Technologies, Santa Clara, Feb 22-25, 2016. Berkeley: USENIX, 2016: 181-195.
[17] SHAUKAT U, AHMED E, ANWAR Z, et al. Cloudlet dep-loyment in local wireless networks: motivation, architec-tures, applications, and open challenges[J]. Journal of Net-work and Computer Applications, 2016, 62: 18-40.
[18] MANI A, DOURNOV P, IRUN-BRIZ L, et al. Coordinated upgrades in distributed systems: U.S. Patent 9753713[P]. 2017-09-05.
[19] MACE J, ROELKE R, FONSECA R. Pivot tracing: dynamic causal monitoring for distributed systems[J]. ACM Transac-tions on Computer Systems, 2018, 35(4): 1-28.
[20] LU R, LIANG X, LI X, et al. EPPA: an efficient and privacy-preserving aggregation scheme for secure smart grid com-munications[J]. IEEE Transactions on Parallel and Distribu-ted Systems, 2012, 23(9): 1621-1631.
[21] DWORK C, ROTH A. The algorithmic foundations of diff-erential privacy[J]. Foundations and Trends? in Theoretical Computer Science, 2014, 9(3/4): 211-407.
[22] NAKAMOTO S. Bitcoin: a peer-to-peer electronic cash sys-tem[R]. Manubot, 2019.
[23] ANDROULAKI E, BARGER A, BORTNIKOV V, et al. Hyperledger fabric: a distributed operating system for per-missioned blockchains[C]//Proceedings of the 13th EuroSys Conference, Porto, Apr 23-26, 2018. New York: ACM, 2018: 1-15.
[24] MARTELLO S, PISINGER D, VIGO D. The three-dimen-sional bin packing problem[J]. Operations Research, 2000, 48(2): 256-267.