Distributed Service Placement in Ultra-Dense Edge Computing: A Game-Theoretical Approach

Junyi He, Di Zhang, Xishuo Li, Yuezhi Zhou, Yaoxue ZhangHPCC/DSS/SmartCity/DependSys 2021 · OpenReview

Abstract

Ultra-dense mobile edge computing (MEC) is expected as an effective approach to provide services with ultra-low latency and massive connectivity, which is extremely important for delay-sensitive applications. In this paper, we study service instance (SI) placement for delay-sensitive applications in ultra-dense MEC, which decides where to place applications and the required data (programming codes and datasets). In general, the SI placement problem is a combinatorial optimization and usually does not have low-complexity optimal solutions. Existing centralized policies are difficult to implement due to the high complexity, especially when edge servers are densely deployed in the ultra-dense network (UDN). To design an approach that can make SI placement decisions quickly and efficiently, this paper investigates a distributed strategy for multi-user multi-server edge systems in UDN. We first formulate the SI placement problem as a non-linear combinatorial optimization, which is proven to be NP-hard to compute a centralized optimal solution. Then, we propose an uncooperative game to design a low-complexity distributed algorithm. We further analyze the properties of the game and prove the existence of pure strategy Nash Equilibrium. A polynomial-complexity distributed algorithm is proposed to get the Nash Equilibrium. Theoretical analysis shows the algorithm's convergence and the bound of the price of anarchy (PoA), which serves as a performance guarantee in the worst-case scenarios compared to the global optimum. Numerical results validate the convergence and near-optimal performance of the proposed distributed algorithm.
BibTeX
@inproceedings{he2021distributed,
  author = {Junyi He and Di Zhang and Xishuo Li and Yuezhi Zhou and Yaoxue Zhang},
  title = {{Distributed Service Placement in Ultra-Dense Edge Computing: A Game-Theoretical Approach}},
  booktitle = {HPCC/DSS/SmartCity/DependSys},
  year = {2021},
  url = {https://openreview.net/forum?id=kqYHu6EpjB},
}

Loading related content...

Figure