A game-theoretical approach for user allocation in edge computing environment

Qiang He, Guangming Cui, Xuyun Zhang, Feifei Chen, Shuiguang Deng, Hai Jin, Yanhui Li, Yun Yang

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Edge Computing provides mobile and Internet-of-Things (IoT) app vendors with a new distributed computing paradigm which allows an app vendor to deploy its app at hired edge servers distributed near app users at the edge of the cloud. This way, app users can be allocated to hired edge servers nearby to minimize network latency and energy consumption. A cost-effective edge user allocation (EUA) requires maximum app users to be served with minimum overall system cost. Finding a centralized optimal solution to this EUA problem is NP-hard. Thus, we propose EUAGame, a game-theoretic approach that formulates the EUA problem as a potential game. We analyze the game and show that it admits a Nash equilibrium. Then, we design a novel decentralized algorithm for finding a Nash equilibrium in the game as a solution to the EUA problem. The performance of this algorithm is theoretically analyzed and experimentally evaluated. The results show that the EUA problem can be solved effectively and efficiently.

LanguageEnglish
Article number8823046
Pages515-529
Number of pages15
JournalIEEE Transactions on Parallel and Distributed Systems
Volume31
Issue number3
DOIs
Publication statusPublished - Mar 2020
Externally publishedYes

Fingerprint

Application programs
Servers
Mobile computing
Distributed computer systems
Costs
Computational complexity
Energy utilization

Keywords

  • cost-effectiveness
  • edge computing
  • edge server
  • Edge user allocation
  • game theory
  • multi-tenancy
  • Nash equilibrium
  • pay-as-you-go

Cite this

He, Qiang ; Cui, Guangming ; Zhang, Xuyun ; Chen, Feifei ; Deng, Shuiguang ; Jin, Hai ; Li, Yanhui ; Yang, Yun. / A game-theoretical approach for user allocation in edge computing environment. In: IEEE Transactions on Parallel and Distributed Systems. 2020 ; Vol. 31, No. 3. pp. 515-529.
@article{6f359f8a23c145ee8c2638a782eb5e1c,
title = "A game-theoretical approach for user allocation in edge computing environment",
abstract = "Edge Computing provides mobile and Internet-of-Things (IoT) app vendors with a new distributed computing paradigm which allows an app vendor to deploy its app at hired edge servers distributed near app users at the edge of the cloud. This way, app users can be allocated to hired edge servers nearby to minimize network latency and energy consumption. A cost-effective edge user allocation (EUA) requires maximum app users to be served with minimum overall system cost. Finding a centralized optimal solution to this EUA problem is NP-hard. Thus, we propose EUAGame, a game-theoretic approach that formulates the EUA problem as a potential game. We analyze the game and show that it admits a Nash equilibrium. Then, we design a novel decentralized algorithm for finding a Nash equilibrium in the game as a solution to the EUA problem. The performance of this algorithm is theoretically analyzed and experimentally evaluated. The results show that the EUA problem can be solved effectively and efficiently.",
keywords = "cost-effectiveness, edge computing, edge server, Edge user allocation, game theory, multi-tenancy, Nash equilibrium, pay-as-you-go",
author = "Qiang He and Guangming Cui and Xuyun Zhang and Feifei Chen and Shuiguang Deng and Hai Jin and Yanhui Li and Yun Yang",
year = "2020",
month = "3",
doi = "10.1109/TPDS.2019.2938944",
language = "English",
volume = "31",
pages = "515--529",
journal = "IEEE Transactions on Parallel and Distributed Systems",
issn = "1045-9219",
publisher = "Institute of Electrical and Electronics Engineers (IEEE)",
number = "3",

}

A game-theoretical approach for user allocation in edge computing environment. / He, Qiang; Cui, Guangming; Zhang, Xuyun; Chen, Feifei; Deng, Shuiguang; Jin, Hai; Li, Yanhui; Yang, Yun.

In: IEEE Transactions on Parallel and Distributed Systems, Vol. 31, No. 3, 8823046, 03.2020, p. 515-529.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - A game-theoretical approach for user allocation in edge computing environment

AU - He, Qiang

AU - Cui, Guangming

AU - Zhang, Xuyun

AU - Chen, Feifei

AU - Deng, Shuiguang

AU - Jin, Hai

AU - Li, Yanhui

AU - Yang, Yun

PY - 2020/3

Y1 - 2020/3

N2 - Edge Computing provides mobile and Internet-of-Things (IoT) app vendors with a new distributed computing paradigm which allows an app vendor to deploy its app at hired edge servers distributed near app users at the edge of the cloud. This way, app users can be allocated to hired edge servers nearby to minimize network latency and energy consumption. A cost-effective edge user allocation (EUA) requires maximum app users to be served with minimum overall system cost. Finding a centralized optimal solution to this EUA problem is NP-hard. Thus, we propose EUAGame, a game-theoretic approach that formulates the EUA problem as a potential game. We analyze the game and show that it admits a Nash equilibrium. Then, we design a novel decentralized algorithm for finding a Nash equilibrium in the game as a solution to the EUA problem. The performance of this algorithm is theoretically analyzed and experimentally evaluated. The results show that the EUA problem can be solved effectively and efficiently.

AB - Edge Computing provides mobile and Internet-of-Things (IoT) app vendors with a new distributed computing paradigm which allows an app vendor to deploy its app at hired edge servers distributed near app users at the edge of the cloud. This way, app users can be allocated to hired edge servers nearby to minimize network latency and energy consumption. A cost-effective edge user allocation (EUA) requires maximum app users to be served with minimum overall system cost. Finding a centralized optimal solution to this EUA problem is NP-hard. Thus, we propose EUAGame, a game-theoretic approach that formulates the EUA problem as a potential game. We analyze the game and show that it admits a Nash equilibrium. Then, we design a novel decentralized algorithm for finding a Nash equilibrium in the game as a solution to the EUA problem. The performance of this algorithm is theoretically analyzed and experimentally evaluated. The results show that the EUA problem can be solved effectively and efficiently.

KW - cost-effectiveness

KW - edge computing

KW - edge server

KW - Edge user allocation

KW - game theory

KW - multi-tenancy

KW - Nash equilibrium

KW - pay-as-you-go

UR - http://www.scopus.com/inward/record.url?scp=85076917885&partnerID=8YFLogxK

U2 - 10.1109/TPDS.2019.2938944

DO - 10.1109/TPDS.2019.2938944

M3 - Article

VL - 31

SP - 515

EP - 529

JO - IEEE Transactions on Parallel and Distributed Systems

T2 - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

SN - 1045-9219

IS - 3

M1 - 8823046

ER -