skip to main content
research-article

Distributed Task Offloading and Resource Purchasing in NOMA-Enabled Mobile Edge Computing: Hierarchical Game Theoretical Approaches

Published: 10 January 2024 Publication History

Abstract

As the computing resources and the battery capacity of mobile devices are usually limited, it is a feasible solution to offload the computation-intensive tasks generated by mobile devices to edge servers (ESs) in mobile edge computing (MEC). In this article, we study the multi-user multi-server task offloading problem in MEC systems, where all users compete for the limited communication resources and computing resources. We formulate the offloading problem with the goal of minimizing the cost of the users and maximizing the profits of the ESs. We propose a hierarchical EETORP (Economic and Efficient Task Offloading and Resource Purchasing) framework that includes a two-stage joint optimization process. Then we prove that the problem is NP-complete. For the first stage, we formulate the offloading problem as a multi-channel access game (MCA-Game) and prove theoretically the existence of at least one Nash equilibrium strategy in MCA-Game. Next, we propose a game-based multi-channel access (GMCA) algorithm to obtain the Nash equilibrium strategy and analyze the performance guarantee of the obtained offloading strategy in the worst case. For the second stage, we model the computing resource allocation between the users and ESs by Stackelberg game theory, and reformulate the problem as a resource pricing and purchasing game (PAP-Game). We prove theoretically the property of incentive compatibility and the existence of Stackelberg equilibrium. A game-based pricing and purchasing (GPAP) algorithm is proposed. Finally, a series of both parameter analysis and comparison experiments are carried out, which validate the convergence and effectiveness of the GMCA algorithm and GPAP algorithm.

References

[1]
Waleed Ahsan, Wenqiang Yi, Zhijin Qin, Yuanwei Liu, and Arumugam Nallanathan. 2021. Resource allocation in uplink NOMA-IoT networks: A reinforcement-learning approach. IEEE Transactions on Wireless Communications 20, 8 (2021), 5083–5098.
[2]
Suzhi Bi and Ying Jun Zhang. 2018. Computation rate maximization for wireless powered mobile-edge computing with binary computation offloading. IEEE Transactions on Wireless Communications 17, 6 (2018), 4177–4190.
[3]
Daniel Casini, Paolo Pazzaglia, Alessandro Biondi, Marco Di Natale, and Giorgio Buttazzo. 2020. Predictable memory-CPU co-scheduling with support for latency-sensitive tasks. In Proceedings of the 2020 57th ACM/IEEE Design Automation Conference (DAC’20). 1–6.
[4]
Chandra Chekuri and Sanjeev Khanna. 2005. A polynomial time approximation scheme for the multiple knapsack problem. SIAM Journal on Computing 35, 3 (2005), 713–728.
[5]
Lixing Chen, Sheng Zhou, and Jie Xu. 2018. Computation peer offloading for energy-constrained mobile edge computing in small-cell networks. IEEE/ACM Transactions on Networking 26, 4 (2018), 1619–1632.
[6]
Xianfu Chen, Honggang Zhang, Celimuge Wu, Shiwen Mao, Yusheng Ji, and Medhi Bennis. 2019. Optimized computation offloading performance in virtual edge computing systems via deep reinforcement learning. IEEE Internet of Things Journal 6, 3 (2019), 4005–4018.
[7]
Y. Chen, W. Gu, J. Xu, and G. Min.2023. Dynamic task offloading for digital twin-empowered mobile edge computing via deep reinforcement learning. China Communications. Early access, May 10, 2023.
[8]
Y. Chen, J. Hu, J. Zhao, and G. Min. 2023. QoS-aware computation offloading in LEO satellite edge computing for IoT: A game-theoretical approach. Chinese Journal of Electronics XX (2023), XX–XX.
[9]
Y. Chen, H. Xing, Z. Ma, X. Chen, and J. Huang. 2022. Cost-efficient edge caching for NOMA-enabled IoT services. China Communications XX (2022), XX–XX.
[10]
Y. Chen, J. Zhao, Y. Wu, et al.2022. QoE-aware decentralized task offloading and resource allocation for end-edge-cloud systems: A game-theoretical approach. IEEE Transactions on Mobile Computing. Early access, November 18, 2022. DOI:https://doi.org/10.1109/TMC.2022.3223119
[11]
Guangming Cui, Qiang He, Feifei Chen, Yiwen Zhang, Hai Jin, and Yun Yang. 2022. Interference-aware game-theoretic device allocation for mobile edge computing. IEEE Transactions on Mobile Computing 11 (2022), 4001–4012.
[12]
Guangming Cui, Qiang He, Xiaoyu Xia, Phu Lai, Feifei Chen, Tao Gu, and Yun Yang. 2022. Interference-aware SaaS user allocation game for edge computing. IEEE Transactions on Cloud Computing 10, 3 (2022), 1888–1899.
[13]
Yan Ding, Kenli Li, Chubo Liu, and Keqin Li. 2022. A potential game theoretic approach to computation offloading strategy optimization in end-edge-cloud computing. IEEE Transactions on Parallel and Distributed Systems 33, 6 (2022), 1503–1519.
[14]
Jianbo Du, Wenjie Cheng, Guangyue Lu, Haotong Cao, Xiaoli Chu, Zhicai Zhang, and Junxuan Wang. 2021. Resource pricing and allocation in MEC enabled blockchain systems: An A3C deep reinforcement learning approach. IEEE Transactions on Network Science and Engineering 9, 1 (2021), 33–44.
[15]
Tao Fang, Feng Yuan, Liang Ao, and Jiaxin Chen. 2021. Joint task offloading, D2D pairing, and resource allocation in device-enhanced MEC: A potential game approach. IEEE Internet of Things Journal 9, 5 (2021), 3226–3237.
[16]
Di Han, Wei Chen, and Yuguang Fang. 2019. A dynamic pricing strategy for vehicle assisted mobile edge computing systems. IEEE Wireless Communications Letters 8, 2 (2019), 420–423.
[17]
Zhu Han, Dusit Niyato, Walid Saad, and Tamer Başar. 2019. Game Theory for Next Generation Wireless and Communication Networks: Modeling, Analysis, and Design. Cambridge University Press.
[18]
Junyan Hu, Kenli Li, Chubo Liu, and Keqin Li. 2020. Game-based task offloading of multiple mobile devices with QoS in mobile edge computing systems of limited computation capacity. ACM Transactions on Embedded Computing Systems 19, 4 (July 2020), Article 29, 21 pages.
[19]
Jiwei Huang, Han Gao, Shaohua Wan, and Y. Chen.2023. AoI-aware energy control and computation offloading for industrial IoT. Future Generation Computer Systems 139 (2023), 29–37.
[20]
Jiwei Huang, Jiangyuan Wan, Bofeng Lv, Qiang Ye, and Ying Chen.2023. Joint computation offloading and resource allocation for edge-cloud collaboration in Internet of Vehicles via deep reinforcement learning. IEEE Systems Journal. Early access, March 13, 2023.DOI:https://doi.org/10.1109/JSYST.2023.3249217
[21]
Phu Lai, Qiang He, Guangming Cui, Xiaoyu Xia, Mohamed Abdelrazek, Feifei Chen, John Hosking, John Grundy, and Yun Yang. 2019. Edge user allocation with dynamic quality of service. In Proceedings of the International Conference on Service-Oriented Computing.86–101.
[22]
Yanwen Lan, Xiaoxiang Wang, Dongyu Wang, Zhaolin Liu, and Yibo Zhang. 2019. Task caching, offloading, and resource allocation in D2D-aided fog computing networks. IEEE Access 7 (2019), 104876–104891.
[23]
Keqin Li. 2021. Heuristic computation offloading algorithms for mobile users in fog computing. ACM Transactions on Embedded Computing Systems 20, 2 (Jan. 2021), Article 11, 28 pages.
[24]
Lingxiang Li, Marie Siew, Zhi Chen, and Tony Q. S. Quek. 2021. Optimal pricing for job offloading in the MEC system with two priority classes. IEEE Transactions on Vehicular Technology 70, 8 (2021), 8080–8091.
[25]
Giorgos Mitsis, Eirini Eleni Tsiropoulou, and Symeon Papavassiliou. 2022. Price and risk awareness for data offloading decision-making in edge computing systems. IEEE Systems Journal 16, 4 (2022), 6546–6557.
[26]
Dov Monderer and Lloyd S. Shapley. 1996. Potential games. Games and Economic Behavior 14, 1 (1996), 124–143.
[27]
Paolo Pazzaglia, Daniel Casini, Alessandro Biondi, and Marco Di Natale. 2023. Optimizing inter-core communications under the LET paradigm using DMA engines. IEEE Transactions on Computers 72, 1 (2023), 127–139.
[28]
Zhijin Qin, Xinwei Yue, Yuanwei Liu, Zhiguo Ding, and Arumugam Nallanathan. 2018. User association and resource allocation in unified NOMA enabled heterogeneous ultra dense networks. IEEE Communications Magazine 56, 6 (2018), 86–92.
[29]
Kaustabha Ray and Ansuman Banerjee. 2021. Horizontal auto-scaling for multi-access edge computing using safe reinforcement learning. ACM Transactions on Embedded Computing Systems 20, 6 (Oct. 2021), Article 109, 33 pages.
[30]
Jinke Ren, Guanding Yu, Yinghui He, and Geoffrey Ye Li. 2019. Collaborative cloud and edge computing for latency minimization. IEEE Transactions on Vehicular Technology 68, 5 (2019), 5031–5044.
[31]
Fatema Vhora and Jay Gandhi. 2020. A comprehensive survey on mobile edge computing: Challenges, tools, applications. In Proceedings of the 2020 4th International Conference on Computing Methodologies and Communication (ICCMC’20). IEEE, Los Alamitos, CA, 49–55.
[32]
Chenmeng Wang, Chengchao Liang, F. Richard Yu, Qianbin Chen, and Lun Tang. 2017. Computation offloading and resource allocation in wireless cellular networks with mobile edge computing. IEEE Transactions on Wireless Communications 16, 8 (2017), 4924–4938.
[33]
Chenmeng Wang, F. Richard Yu, Chengchao Liang, Qianbin Chen, and Lun Tang. 2017. Joint computation offloading and interference management in wireless cellular networks with mobile edge computing. IEEE Transactions on Vehicular Technology 66, 8 (2017), 7432–7445.
[34]
Can Wang, Sheng Zhang, Yu Chen, Zhuzhong Qian, Jie Wu, and Mingjun Xiao. 2020. Joint configuration adaptation and bandwidth allocation for edge-based real-time video analytics. In Proceedings of the 2020 IEEE Conference on Computer Communications(IEEE INFOCOM’20). IEEE, Los Alamitos, CA, 257–266.
[35]
Pengfei Wang, Zijie Zheng, Boya Di, and Lingyang Song. 2019. HetMEC: Latency-optimal task assignment and resource allocation for heterogeneous multi-layer mobile edge computing. IEEE Transactions on Wireless Communications 18, 10 (2019), 4942–4956.
[36]
Qihui Wu, Ducheng Wu, Yuhua Xu, and Jinlong Wang. 2014. Demand-aware multichannel opportunistic spectrum access: A local interaction game approach with reduced information exchange. IEEE Transactions on Vehicular Technology 64, 10 (2014), 4899–4904.
[37]
Xiaoyu Xia, Feifei Chen, Qiang He, Guangming Cui, John C. Grundy, Mohamed Abdelrazek, Xiaolong Xu, and Hai Jin. 2021. Data, user and power allocations for caching in multi-access edge computing. IEEE Transactions on Parallel and Distributed Systems 33, 5 (2021), 1144–1155.
[38]
Qing Zhang, Kai Luo, Wei Wang, and Tao Jiang. 2019. Joint C-OMA and C-NOMA wireless backhaul scheduling in heterogeneous ultra dense networks. IEEE Transactions on Wireless Communications 19, 2 (2019), 874–887.

Cited By

View all
  • (2025)DELTA: Deadline aware energy and latency-optimized task offloading and resource allocation in GPU-enabled, PiM-enabled distributed heterogeneous MEC architectureJournal of Systems Architecture10.1016/j.sysarc.2025.103335(103335)Online publication date: Jan-2025
  • (2024)An Intelligent Privacy Protection Scheme for Efficient Edge Computation Offloading in IoVChinese Journal of Electronics10.23919/cje.2023.00.11133:4(910-919)Online publication date: Jul-2024
  • (2024)A Deep Deterministic Policy Gradient-Based Method for Enforcing Service Fault-Tolerance in MECChinese Journal of Electronics10.23919/cje.2023.00.10533:4(899-909)Online publication date: Jul-2024
  • Show More Cited By

Index Terms

  1. Distributed Task Offloading and Resource Purchasing in NOMA-Enabled Mobile Edge Computing: Hierarchical Game Theoretical Approaches

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Transactions on Embedded Computing Systems
      ACM Transactions on Embedded Computing Systems  Volume 23, Issue 1
      January 2024
      406 pages
      EISSN:1558-3465
      DOI:10.1145/3613501
      • Editor:
      • Tulika Mitra
      Issue’s Table of Contents

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Journal Family

      Publication History

      Published: 10 January 2024
      Online AM: 16 May 2023
      Accepted: 24 April 2023
      Revised: 23 February 2023
      Received: 10 October 2022
      Published in TECS Volume 23, Issue 1

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. Task offloading
      2. MEC
      3. game theory
      4. resource purchasing
      5. resource pricing

      Qualifiers

      • Research-article

      Funding Sources

      • National Natural Science Foundation of China
      • Project of Cultivation for Young Top-Notch Talents of Beijing Municipal Institutions
      • Beijing Nova Program
      • Young Elite Scientists Sponsorship Program by BAST
      • Key Project of Shenzhen City Special Fund for Fundamental Research

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)871
      • Downloads (Last 6 weeks)46
      Reflects downloads up to 26 Jan 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2025)DELTA: Deadline aware energy and latency-optimized task offloading and resource allocation in GPU-enabled, PiM-enabled distributed heterogeneous MEC architectureJournal of Systems Architecture10.1016/j.sysarc.2025.103335(103335)Online publication date: Jan-2025
      • (2024)An Intelligent Privacy Protection Scheme for Efficient Edge Computation Offloading in IoVChinese Journal of Electronics10.23919/cje.2023.00.11133:4(910-919)Online publication date: Jul-2024
      • (2024)A Deep Deterministic Policy Gradient-Based Method for Enforcing Service Fault-Tolerance in MECChinese Journal of Electronics10.23919/cje.2023.00.10533:4(899-909)Online publication date: Jul-2024
      • (2024)DenMerD: a feature enhanced approach to radar beam blockage correction with edge-cloud computingJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-024-00607-x13:1Online publication date: 7-Feb-2024
      • (2024)A Transformer-based network intrusion detection approach for cloud securityJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-023-00574-913:1Online publication date: 2-Jan-2024
      • (2024)Traffic prediction for diverse edge IoT data using graph networkJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-023-00543-213:1Online publication date: 10-Apr-2024
      • (2024)Towards Efficient Task Offloading With Dependency Guarantees in Vehicular Edge Networks Through Distributed Deep Reinforcement LearningIEEE Transactions on Vehicular Technology10.1109/TVT.2024.338754873:9(13665-13681)Online publication date: Sep-2024
      • (2024)Dynamic Task Offloading and Resource Allocation for NOMA-Aided Mobile Edge Computing: An Energy Efficient DesignIEEE Transactions on Services Computing10.1109/TSC.2024.337624017:4(1492-1503)Online publication date: Jul-2024
      • (2024)Efficient Distributed Edge Computing for Dependent Delay-Sensitive Tasks in Multi-Operator Multi-Access NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.346889235:12(2559-2577)Online publication date: 1-Dec-2024
      • (2024)PoPeC: PAoI-Centric Task Offloading With Priority Over Unreliable ChannelsIEEE/ACM Transactions on Networking10.1109/TNET.2024.335019832:3(2376-2390)Online publication date: 1-Jun-2024
      • Show More Cited By

      View Options

      Login options

      Full Access

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Full Text

      View this article in Full Text.

      Full Text

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media