Mechanisms for Resource Allocation and Pricing in Mobile Edge Computing Systems

• Published in: IEEE transactions on parallel and distributed systems 2022-03, Vol.33 (3), p.667-682
• Main Authors: Bahreini, Tayebeh, Badri, Hossein, Grosu, Daniel
• Format: Article
• Language: English
• Subjects: approximation algorithm; Cloud computing; Computational modeling; Cost accounting; Edge computing; envy-free mechanism; Mixed integer; Mobile computing; Performance evaluation; Pricing; Resource allocation; Resource management; Servers
• ISSN: 1045-9219; 1558-2183
• DOI: 10.1109/TPDS.2021.3099731

In this article, we address the resource allocation and monetization challenges in Mobile Edge Computing (MEC) systems, where users have heterogeneous demands and compete for high quality services. We formulate the Edge Resource Allocation Problem ({{\sf ERAP}} ERAP ) as a Mixed-Integer Linear Program ({{\sf MILP}} MILP ) and prove that {{\sf ERAP}} ERAP is {{\sf NP}} NP -hard. To solve the problem efficiently, we propose two resource allocation mechanisms. First, we develop an auction-based mechanism and prove that the proposed mechanism is individually-rational and produces envy-free allocations . We also propose an {{\sf LP}} LP -based approximation mechanism that does not guarantee envy-freeness, but it provides solutions that are guaranteed to be within a given distance from the optimal solution. We evaluate the performance of the proposed mechanisms by conducting an extensive experimental analysis on {{\sf ERAP}} ERAP instances of various sizes. We use the optimal solutions obtained by solving the {{\sf MILP}} MILP model using a commercial solver as benchmarks to evaluate the quality of solutions. Our analysis shows that the proposed mechanisms obtain near optimal