A Cyclic Game for Service-Oriented Resource Allocation in Edge Computing

Shiheng Ma, Song Guo, Kun Wang, Weijia Jia, Minyi Guo

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

Existing works adopt the Edge-Oriented Resource Allocation (EORA) scheme, in which edge nodes cache services and schedule user requests to distribute workload over cloud and edge nodes, so as to achieve high quality services and low latency. Unfortunately, EORA does not fully take into account the fact that service providers are sometimes independent from the edge operators with their own objectives. To deal with the conflict and cooperation between service providers and edge nodes, we devise a service-oriented resource allocation (SORA) scheme, where edge nodes and service providers adjust their resource allocations to provide requested services. We first prove that such resource allocation problem is NP-hard. We then propose a three-sided cyclic game (3CG) involving users, edge nodes, and service providers who make their individual decisions by choosing respectively high-quality services, high-value users, and cost-effective edge nodes for service deployment. Based on 3CG, we prove the existence and approximation ratio of pure-strategy Nash equilibriums (NEs). We also develop both centralized and distributed approximate algorithms for resource allocation. Finally, extensive experimental results validate the effectiveness and convergence of the proposed algorithms.

Original languageEnglish
JournalIEEE Transactions on Services Computing
DOIs
Publication statusAccepted/In press - 2020

Keywords

  • Approximation algorithms
  • Computational modeling
  • Edge computing
  • Edge Computing
  • Game Theory
  • Games
  • Numerical models
  • Quality of experience
  • Resource Allocation
  • Resource management

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computer Science Applications
  • Computer Networks and Communications
  • Information Systems and Management

Cite this