Efficient Distributed Threshold-Based Offloading for Large-Scale Mobile Cloud Computing

—Mobile cloud computing enables compute-limited mobile devices to perform real-time intensive computations such as speech recognition or object detection by leveraging powerful cloud servers. An important problem in large-scale mobile cloud computing is computational ofﬂoading, where each mobile device decides when and how much computation should be uploaded to cloud servers by considering the local processing delay and the cost of using cloud servers. In this paper, we develop a distributed threshold-based ofﬂoading algorithm where it uploads an incoming computing task to cloud servers if the number of tasks queued at the device reaches the threshold and processes it locally otherwise. The threshold is updated iteratively based on the computational load and the cost of using cloud servers. We formulate the problem as a symmetric game, and characterize the sufﬁcient and necessary conditions for the existence and uniqueness of the Nash Equilibrium (NE) assuming exponential service times. Then, we show the convergence of our proposed distributed algorithm to the NE when the NE exists. Further, we characterize the performance gap between cost under our proposed distributed algorithm and the minimum cost in terms of Price of Anarchy (PoA) when the cost of using cloud servers is high. Finally, we perform extensive simulations to validate our theoretical ﬁndings, demonstrate the efﬁciency of our proposed distributed algorithm under various scenarios such as hyperexponential service times, imperfect server utilization estimation, and asynchronous threshold updates, and reveal the superior performance of threshold-based policies over their probabilistic counterpart.