Budget-Aware User Satisfaction Maximization on Service Provisioning in Mobile Edge Computing

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

View graph of relations


  • Jing Li
  • Wenzheng Xu
  • Zichuan Xu
  • Albert Y. Zomaya
  • Song Guo

Related Research Unit(s)


Original languageEnglish
Journal / PublicationIEEE Transactions on Mobile Computing
Publication statusOnline published - 9 Sep 2022


Mobile Edge Computing (MEC) promises to provide mobile users with delay-sensitive services at the edge of network, and each user service request usually is associated with a Service Function Chain (SFC) requirement that consists of Virtualized Network Functions (VNFs) in order. The satisfaction of a user on his requested service is heavily impacted by the service reliability. In this paper, we study user satisfaction on services provided by an MEC network through introducing a submodular function based metric to measure user satisfaction. We first formulate a novel user satisfaction problem with the aim to maximize the accumulative user satisfaction, assuming that all available computing resource in the MEC network can be used for service reliability enhancement. We show that the problem is NP-hard, and devise an approximation algorithm with a provable approximation ratio for it. We then consider the problem under a given computing resource budget constraint, for which we devise an approximation algorithm with a provable approximation ratio, at the expense of moderate budget violations. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms outperform the comparison baseline algorithms, improving the performance by more 16.1% in comparison with the baseline algorithms.

Research Area(s)

  • Approximation algorithms, budget-aware generalized assignment problem, approximation algorithms, resource allocation and optimization, Computer network reliability, Delays, Heuristic algorithms, Mobile computing, Mobile Edge Computing (MEC), Reliability, reliable virtual service provisioning, Service Function Chain (SFC), Service function chaining, user service satisfaction, Virtualized Network Function (VNF), VNF instance placement