Multi-User Multi-Task Offloading and Resource Allocation in Mobile Cloud Systems

Meng-Hsi Chen, Ben Liang, Min Dong

TL;DR

This paper tackles the complex challenge of deciding which tasks a mobile device should process locally versus offloading to the cloud or a "Computing Access Point" (CAP). By jointly optimizing offloading decisions and resource allocation (bandwidth and CPU) for multiple users with multiple tasks, the authors propose algorithms that achieve near-optimal performance in reducing the combined cost of energy, delay, and service fees.

What Problem Does This Paper Address?

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.

The authors identify a significant gap: how to manage 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:

  1. Offloading Decision: Should task $j$ from user $i$ be done locally, at the CAP, or in the remote cloud?
  2. Communication Allocation: How much bandwidth should each user get?
  3. Computation Allocation: How should the CAP’s limited CPU be shared among users?

Mathematically, this results in a non-convex quadratically constrained quadratic program (QCQP), which is NP-hard to solve exactly.

Methods

The authors propose two primary algorithmic frameworks:

  • MUMTO (Multi-User Multi-Task Offloading): Designed for the conventional two-tier (Mobile-Cloud) setup. It uses Separable Semidefinite Relaxation (SDR) to turn the difficult binary (0 or 1) offloading decisions into a continuous, solvable convex problem. It then "recovers" the binary decisions and optimizes the communication resources.
  • MUMTO-C: An enhanced three-step algorithm for the three-tier (Mobile-CAP-Cloud) setup:
  • SDR-C: An initial offloading solution using a generalized version of the SDR approach.
  • Alternating Optimization (AO): Iteratively refines the offloading decisions and resource allocations to lower the total cost.
  • Sequential Tuning (ST): A final pass that checks each task individually to see if changing its location further reduces cost, guaranteeing a locally optimal solution.

To handle the "flow-shop" problem (where overlapping transmission and processing make exact delay hard to calculate), the authors utilize mathematical upper and lower bounds to sandwich the true cost.

Datasets

The paper relies on computer simulations rather than a static dataset. To ensure realism, they adopted parameters from established hardware profiles:

  • Device Specs: Based on a Nokia smart device (500 MHz CPU, specific energy-per-cycle values).
  • Application Model: The x264 CBR encode application, requiring 1900 cycles/byte.
  • Task Data: Input sizes were uniformly distributed between 10–30 MB, with output sizes between 1–3 MB.
  • Network: A 40 MHz total bandwidth and a 15 Mbps CAP-to-cloud link.

Key Insights and Ideas

  • The CAP Advantage: The CAP is a game-changer. It reduces the high latency of the remote cloud while providing more power than the local device. The results show that efficient CAP utilization brings "substantial cost benefit."
  • Interdependence: Offloading and resource allocation cannot be solved in isolation. A decision to offload more tasks is only beneficial if the system also allocates enough bandwidth to move that data quickly.
  • Relaxation and Recovery: The transition from a discrete "0/1" problem to a continuous one via SDR is highly effective. Even though SDR is an approximation, the subsequent "tuning" steps (AO and ST) ensure the final result is robust.
  • Scalability: MUMTO-C is shown to be scalable, with run-times that increase nearly linearly with the number of tasks, making it practical for real-world systems.

Key Results

  • Near-Optimality: The proposed algorithms perform remarkably close to the theoretical numerical lower bounds across various parameter settings (weight of delay, cloud CPU speed, etc.).
  • Cost Reduction: MUMTO-C can reduce the total system cost by up to 20% compared to simpler SDR-only approaches.
  • Robustness: The algorithm consistently outperforms "local-only" or "cloud-only" strategies, especially when the cost of using the CAP is low or the cloud link is congested.
  • Convergence: The three-step process is guaranteed to converge to a locally optimal solution, providing a reliable benchmark for system designers.

Limitations and Future Work

  • Task Independence: The current model assumes tasks are independent. In many apps, tasks have dependencies (e.g., Task B cannot start until Task A finishes), which would require modeling the system as a Directed Acyclic Graph (DAG).
  • Static Environment: The study assumes a "quasi-static" environment where user mobility and channel statistics don't change during processing.
  • Future Directions: The authors suggest extending this work to include dynamic task arrivals (tasks appearing over time), user mobility (handing off between different CAPs), and strict delay constraints for real-time applications like AR/VR.

Summary updated

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.
BibTeX
@article{chen2018multi,
  author = {Meng-Hsi Chen and Ben Liang and Min Dong},
  title = {{Multi-User Multi-Task Offloading and Resource Allocation in Mobile Cloud Systems}},
  journal = {IEEE Trans. Wireless Communications},
  year = {2018},
  url = {https://openreview.net/forum?id=vLCT1pDmQG},
}

Loading related content...

Figure