How to Stabilize a Competitive Mobile Edge Computing Environment: A Game Theoretic Approach

There are two fundamental purposes in mobile edge computing, i.e., performance enhancement and cost reduction. By offloading computation tasks to a mobile edge cloud (MEC), a user equipment (UE), also called mobile user, mobile subscriber, or mobile device, can possibly reduce its average response time, which is the main performance measure, and can possibly reduce its average power consumption. Optimizing both performance and cost may be conflicting requirements. In this paper, we optimize the cost performance ratio (CPR), i.e., the power-time product, which combines performance (average response time) and cost (average power consumption) into one quantity. A unique feature in mobile edge computing is the competitiveness of mobile users, who are selfish in competing for resources in a mobile edge cloud. We take a game theoretic approach to the stabilization of a competitive mobile edge computing environment. The main contributions of the paper are summarized as follows. 1) We consider a mobile edge computing environment with multiple UEs and a single MEC. We establish an M/G/1 queueing model for the UEs and an M/G/m queueing model for the MEC. The UEs are entirely heterogeneous in terms of task characteristics, computation and communication speeds, and power consumption models for both computation and communication. 2) We analytically derive the average response time and the average power consumption of each UE and the MEC, so that cost-performance ratio optimization can be studied mathematically and rigorously. 3) We establish a non-cooperative game framework to systematically study the stabilization of a competitive mobile edge computing environment. Our framework includes a set of seven non-cooperative games among the UEs and the MEC, each attempts to minimize its payoff function, i.e., its cost-performance ratio. These games are different in terms of the number of variables to play and which variables to play. 4) We develop efficient algorithms for each player to find the best response in each game. All these algorithms are the poly-log time in the length of an initial search interval and the accuracy requirement. We also develop an iterative algorithm to find the Nash equilibrium of the games. 5) We demonstrate the numerical examples of our algorithms and performance data of our games for the idle-speed model and the constant-speed model respectively.