Abstract
We consider a general multi-user Mobile Cloud Computing (MCC) system where each mobile user has multiple independent tasks. These mobile users share the computation and communication resources while offloading tasks to the cloud. We study both the conventional MCC where tasks are offloaded to the cloud through a wireless access point, and MCC with a computing access point (CAP), where the CAP serves both as the network access gateway and a computation service provider to the mobile users. We aim to jointly optimize the offloading decisions of all users as well as the allocation of computation and communication resources, to minimize the overall cost of energy, computation, and delay for all users. The optimization problem is formulated as a non-convex quadratically constrained quadratic program, which is NP-hard in general. For the case without a CAP, an efficient approximate solution named MUMTO is proposed by using separable semidefinite relaxation (SDR), followed by recovery of the binary offloading decision and optimal allocation of the communication resource. To solve the more complicated problem with a CAP, we further propose an efficient three-step algorithm named MUMTO-C comprising of generalized MUMTO SDR with CAP, alternating optimization, and sequential tuning, which always computes a locally optimal solution. For performance benchmarking, we further present numerical lower bounds of the minimum system cost with and without the CAP. By comparison with this lower bound, our simulation results show that the proposed solutions for both scenarios give nearly optimal performance under various parameter settings, and the resultant efficient utilization of a CAP can bring substantial cost benefit.
1. Introduction
Mobile Cloud Computing (MCC) allows resource-constrained devices to offload heavy tasks to the cloud. However, most existing research focuses on a single user or a single task per user. In reality, multiple users compete for limited wireless bandwidth and cloud processing power, and their applications consist of multiple independent tasks. This paper addresses the challenge of managing this competition when there is an additional "middle tier"—a Computing Access Point (CAP). A CAP is essentially a local base station with built-in computing power, similar to Edge Computing. The challenge is a "triple-threat" optimization problem involving offloading decisions, communication allocation (bandwidth), and computation allocation (CAP CPU sharing).
2. System Model and Problem Formulation
The system model considers $N$ mobile users, each with $M$ tasks, interacting with an Access Point and a Remote Cloud. The optimization aims to minimize a weighted sum of energy consumption, processing delay, and usage costs.
Mathematically, this results in a non-convex quadratically constrained quadratic program (QCQP), which is NP-hard to solve exactly. The variables involved in this formulation, including local processing energy, transmission times, and bandwidth allocations, are detailed in the following notation summary.
3. Proposed Methodology
The authors propose two primary algorithmic frameworks to solve the resource allocation problem:
- MUMTO (Multi-User Multi-Task Offloading): Designed for the conventional two-tier (Mobile-Cloud) setup. It uses Separable Semidefinite Relaxation (SDR) to turn difficult binary offloading decisions into a continuous, solvable convex problem. It then "recovers" the binary decisions and optimizes communication resources.
- MUMTO-C: An enhanced three-step algorithm for the three-tier (Mobile-CAP-Cloud) setup. It involves a generalized SDR-C for initial offloading, Alternating Optimization (AO) to iteratively refine decisions, and Sequential Tuning (ST) to check each task individually, guaranteeing a locally optimal solution.
4. Performance Evaluation
The paper relies on computer simulations using parameters from hardware profiles like Nokia smart devices and the x264 CBR encode application. Key results include:
- Near-Optimality: The proposed algorithms perform remarkably close to theoretical numerical lower bounds across various parameter settings.
- Cost Reduction: MUMTO-C can reduce total system cost by up to 20% compared to simpler SDR-only approaches. The CAP acts as a game-changer, reducing remote cloud latency while providing more power than local devices.
- Robustness and Scalability: The algorithm consistently outperforms "local-only" or "cloud-only" strategies. Furthermore, MUMTO-C run-times increase nearly linearly with the number of tasks, making it practical for real-world systems.
5. Conclusion and Future Work
This study demonstrates that offloading and resource allocation cannot be solved in isolation; a decision to offload is only beneficial if sufficient bandwidth is allocated. While the current model assumes task independence and a quasi-static environment, future work will extend these findings to include dynamic task arrivals, user mobility, and task dependencies modeled as Directed Acyclic Graphs (DAGs).
Summary updated