Joint Task Offloading and Resource Allocation for Mobile Cloud with Computing Access Point

Mobile Cloud Computing (MCC) extends the capabilities of mobile devices to improve user experience. Mobile users can offload tasks to the cloud, using abundant cloud resources to help them gather, store, and process data. In this dissertation, we consider a general three-tier multi-user MCC system consisting of mobile users, a computing access point (CAP), and a remote cloud server. The CAP serves both as the network access gateway and a computation service provider to the mobile users, so that each task may be processed locally, at the CAP, or at a remote cloud server. In a multi-user scenario, to offload tasks, we need to further allocate communication and computation resources among competing users. The existing works either optimize only the offloading decisions of tasks without the resource allocation for three-tier systems, or consider only the two-tier systems with mobile users and the remote (or nearby) processor. Instead, for a general three-tier system, we jointly consider both the offloading decision and resource allocation among all users, with an aim to conserve energy and maintain service quality for all of them. We first consider the scenario where each user has a single task, with an aim to minimize the overall cost of energy consumption, computation, and maximum delay among users. The joint optimization problem is formulated as a mixed-integer program, which is NP-hard in general. An efficient heuristic algorithm using semidefinite relaxation (SDR) and a new randomization mapping approach is proposed. For the case with strict delay constraints for each task, we propose a three-step algorithm to obtain a feasible solution that is locally optimal. We further investigate a more general mobile cloud network where each user has multiple independent tasks. Both cases with and without a CAP are studied, and corresponding nearly optimal solutions are obtained. In addition to the centralized optimizations above, we also study the interaction between selfish mobile users and the CAP. We use a game theoretic approach by letting mobile users distributively compute their own offloading decisions based on their respective cost function, while the CAP decides the allocation of communication and computation resources. We show that a Nash equilibrium (NE) exists in our formulated game, and we propose an algorithm which leads to an NE in finite steps. In all cases above, we show that the proposed methods provide nearly optimal performance. Furthermore, by exploiting the CAP efficiently, we can significantly reduce the energy and computation costs of mobile cloud computing over traditional two-tier systems where offloaded tasks are only processed at the remote cloud center.Ph.D