PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-user Multi-task Offloading and Resource Allocation in Mobile Cloud Systems

Meng-Hsi Chen, Ben Liang, Min Dong

arXiv:1803.06577v2cs.ITmath.IT

TL;DR

Jointly optimizing offloading decisions and shared computation and communication resources is challenging in multi-user, multi-task mobile cloud systems. The paper proposes MUMTO and MUMTO-C, which achieve nearly optimal performance against lower bounds across the evaluated settings.

  • Problem

    The paper addresses joint offloading and shared-resource allocation across users and tasks, where task scheduling involves a multi-machine flow-shop problem without a known optimal solution.

    Source: §I · pp. 1–2

  • Method

    MUMTO uses semidefinite relaxation and binary recovery, while MUMTO-C combines CAP-aware relaxation, alternating optimization, and sequential tuning.

    Source: 5) Overall MUMTO-C Algorithm · p. 10, §VII · p. 13

  • Results

    MUMTO and MUMTO-C achieve nearly optimal performance against lower bounds and substantially outperform existing alternatives across a wide range of parameter settings.

    Source: 1) Bounds of Remote-Processing Delay · p. 5, §VII · p. 14

  • Takeaways & Limitations

    The proposed algorithms provide near-optimal solutions across a wide range of parameter settings.

    Source: §VII · p. 14

    The model assumes all tasks are available at the start and link statistics remain unchanged during processing, reflecting a relatively static or low-mobility scenario.

    Source: A. Mobile Cloud Offloading with… · p. 3

Abstract

from arXiv · show

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.

I. INTRODUCTION … A. Mobile Cloud Offloading with Multiple Users and Tasks

The paper studies joint task offloading and resource allocation in multi-user, multi-task mobile cloud systems, both with a conventional access point and with a computing access point (CAP). It proposes algorithms and evaluates them against lower bounds, while defining a system model with explicit operating assumptions.

I. INTRODUCTION

  • The work jointly optimizes offloading decisions and shared computation and communication resources for multiple users’ independent tasks, accounting for energy, usage costs, and delays.The system may use a conventional AP that forwards tasks to a remote cloud or a CAP that can compute tasks itself.Source: §I · p. 1
  • MUMTO and MUMTO-C achieve nearly optimal performance against lower bounds across varied parameter settings, and CAP-based processing can improve system performance.MUMTO uses separable semidefinite relaxation (SDR), binary-decision recovery, and optimal communication allocation; MUMTO-C adds generalized SDR, alternating optimization, and sequential tuning, and computes a locally optimal solution.Source: §I · p. 2
  • For conventional MCC, MUMTO addresses an NP-hard non-convex QCQP; for CAP-enabled MCC, MUMTO-C adds CAP computation allocation and uses three algorithmic steps.The conventional case includes delay bounds, separable SDR, binary offloading recovery, and optimal communication allocation; MUMTO-C adds alternating optimization and sequential tuning.Source: §I · p. 2

A. Two-Tier Offloading System

  • Earlier two-tier studies treated whole applications or single-user tasks, or optimized offloading or resource allocation separately; this work jointly optimizes both for multiple users with multiple tasks.The cited multi-user studies –, – assumed one task per user, and used sequential optimization.Source: §I · p. 1, A. Two-Tier Offloading System · p. 2

B. Three-Tier Offloading System

  • Prior three-tier work often optimized offloading alone or used simplified task scenarios; joint offloading and resource allocation for general multi-user, multi-task systems remained unstudied.Earlier CAP scheduling work considered a single user or multiple users with one task each.Source: B. Three-Tier Offloading System · pp. 2–3

A. Mobile Cloud Offloading with Multiple Users and Tasks

  • The model has one cloud server, one AP, and N users with M independent tasks each; the AP either forwards tasks or computes some itself as a CAP.Equal task counts simplify notation; solutions extend to users with differing task counts, and the model does not specify a particular queueing discipline.Source: A. Mobile Cloud Offloading with… · p. 3
  • Tasks are assumed available in batches at the start, and wireless-link statistics remain unchanged during processing; mobility effects are left for future work.For tasks arriving dynamically, the model may be applied quasi-statically to collected batches.Source: A. Mobile Cloud Offloading with… · p. 3

B. Cost of Local Processing · C. Cost of Remote Cloud Processing

The sections define local task-processing costs and the components of remote-cloud offloading cost, including wireless transmission, AP-cloud transfer, cloud processing, and cloud usage charges.

B. Cost of Local Processing

C. Cost of Remote Cloud Processing

  • When a task is offloaded, the user incurs energy for wireless transmission and reception, with uplink and downlink transmission times defined for the AP connection.Source: C. Cost of Remote Cloud Processing · pp. 3–4
  • Uplink and downlink bandwidth allocated to each user are limited by the corresponding system bandwidths, and a total bandwidth constraint may also apply.Transmission between users and the AP is described using uplink and downlink spectral efficiencies.Source: C. Cost of Remote Cloud Processing · p. 4
  • AP-cloud transfer time is T_ac_ij=(Din_ij+Dout_ij)/r_ac, and cloud processing time is T_c_ij=Y_ij/f_c.The AP-cloud transmission rate and cloud processing rate are predetermined and independent of user count, so these times depend only on the task.Source: C. Cost of Remote Cloud Processing · p. 4
  • Cloud usage cost is denoted by Cc_ij and treated as given for every task; its detailed dependence on task and server costs is outside the study’s scope.Source: C. Cost of Remote Cloud Processing · p. 4

D. Cost of CAP Processing … B. Problem Formulation

The paper defines joint offloading and resource-allocation costs for conventional MCC and describes how CAP processing adds a constrained computation service. It formulates the conventional no-CAP optimization and addresses the difficulty of estimating remote-processing delay.

D. Cost of CAP Processing

  • CAP processing adds processing time and usage cost alongside communication energy and delay, with each assigned processing rate limited by the CAP’s total rate.Source: D. Cost of CAP Processing · p. 4

IV. MULTI-USER MULTI-TASK OFFLOADING WITHOUT CAP

  • Without a CAP, the AP forwards tasks to the remote cloud, and the system jointly optimizes task offloading and communication resources to minimize weighted energy, computation, and delay costs.Source: §IV · p. 4

A. Offloading Decision

B. Problem Formulation

  • The objective minimizes a weighted sum of total energy, task offloading and processing costs, and transmission and processing delays by jointly choosing task decisions and bandwidth allocations.Source: B. Problem Formulation · p. 4
  • The delay weight ρi can be adjusted to emphasize delay or energy consumption according to performance requirements.Source: B. Problem Formulation · p. 4
  • Remote-processing delay is difficult to calculate exactly because task transmission and processing may overlap according to offloading decisions, bandwidth allocation, and scheduling order; it resembles an open flowshop problem.Source: B. Problem Formulation · p. 5
  • Under MUMTO, upper and lower bounds on remote-processing delay yield total system costs that are close to each other.Source: B. Problem Formulation · p. 5

C. Multi-user Multi-task Offloading (MUMTO) Algorithm · 1) Bounds of Remote-Processing Delay:

MUMTO approximates the joint offloading problem using delay bounds and separable SDR; its worst-case-delay formulation is reported to give nearly optimal performance against the bounds.

C. Multi-user Multi-task Offloading (MUMTO) Algorithm

1) Bounds of Remote-Processing Delay:

2) QCQP Transformation and Semidefinite Relaxation:

The original optimization is reformulated as an equivalent homogeneous separable QCQP, which is NP-hard. The proposed approach relaxes it to a separable SDP, then recovers binary offloading decisions and allocates communication resources.

2) QCQP Transformation and Semidefinite Relaxation:

  • The equivalent reformulation yields a homogeneous separable QCQP with one-to-one correspondence between its constraints and those of the original problem.The transformation uses auxiliary variables and vectorized decision variables.Source: 2) QCQP Transformation and… · p. 6
  • The separable QCQP is NP-hard: fixing resource allocations reduces it to linear integer programming, and fixing the auxiliary variables can yield a 0-1 knapsack problem.The knapsack reduction is given for fixed t_i values, for example t_i = sum_j T_ij.Source: 2) QCQP Transformation and… · p. 6
  • Separable SDR drops the rank(Z_i) = 1 constraint to obtain a separable SDP relaxation.The SDP optimum is only a lower bound when the relaxed solution matrices do not have rank 1.Source: 2) QCQP Transformation and… · pp. 6–7
  • The recovery algorithm rounds relaxed offloading values to binary decisions, optimizes resource allocation, and selects the lowest-cost option among the rounded, local-only, and cloud-only solutions.It recovers binary offloading decisions and corresponding optimal communication-resource allocations for the original problem.Source: 2) QCQP Transformation and… · p. 7

3) Binary Offloading Decisions and Resource Allocation:

MUMTO recovers feasible binary offloading decisions from the relaxed SDP solution, then optimally allocates communication resources for those decisions. It also compares the recovered decisions with local-only and cloud-only processing to select the lowest-cost option.

3) Binary Offloading Decisions and Resource Allocation:

  • The relaxed SDP solution is used to recover feasible binary offloading decisions for each user’s tasks.The first M elements correspond to offloading decisions, and the recovery uses entries of the relaxed solution that lie in [0, 1].Source: 3) Binary Offloading Decisions and… · p. 7
  • With offloading decisions fixed, communication-resource allocation is a convex problem that standard solvers can optimize globally.The energy term becomes constant once the decisions are given.Source: 3) Binary Offloading Decisions and… · p. 7
  • MUMTO selects its final decision by comparing the recovered decisions with local-only and cloud-only processing and choosing the minimum-cost option.The comparison uses the total system cost objective of problem (44).Source: 3) Binary Offloading Decisions and… · p. 7

D. Lower Bound on the Optimal Solution … B. Problem Formulation

The paper develops a lower bound for benchmarking the original no-CAP optimization problem, then formulates CAP-enabled offloading across local, CAP, and cloud processing with joint resource allocation.

D. Lower Bound on the Optimal Solution

V. MULTI-USER MULTI-TASK OFFLOADING WITH CAP

  • With a CAP, each task may be processed locally, at the CAP, or at the remote cloud, and the problem jointly optimizes offloading and communication and CAP processing resources.Source: §V · p. 8

A. Offloading Decision

  • The offloading decisions encode whether each task is processed locally, at the CAP, or at the cloud, with only one placement indicator allowed to equal 1.Source: A. Offloading Decision · p. 8

B. Problem Formulation

  • The CAP-case objective weights total energy, offloading and processing costs, and transmission and processing delays, while jointly optimizing task placements and communication and CAP resources.Source: B. Problem Formulation · p. 8
  • The CAP formulation is more complicated than the no-CAP problem because it adds CAP processing cost and delay terms and a placement constraint.Source: B. Problem Formulation · p. 8
  • Overlapping transmissions or processing make overall CAP and cloud delays intractable, so the solution and benchmarking use upper and lower delay bounds.Source: B. Problem Formulation · p. 8
  • With MUMTO-C, the upper and lower bounds estimate total system cost closely.Source: B. Problem Formulation · p. 8

C. Multi-user Multi-task Offloading with CAP (MUMTO-C) Algorithm · 1) Bounds of CAP-Processing and Cloud-Processing Delays:

MUMTO-C uses delay bounds to formulate and solve the CAP offloading problem, with worst-case delays supporting an approximate solution and best-case delays supporting performance benchmarking. The reported actual system cost is close to the lower bound and hence close to the optimal system cost.

C. Multi-user Multi-task Offloading with CAP (MUMTO-C) Algorithm

  • The CAP formulation transforms the optimization problem into a separable QCQP and corresponding SDR to obtain offloading decisions and communication and processing allocations.Source: C. Multi-user Multi-task Offloading… · p. 8

1) Bounds of CAP-Processing and Cloud-Processing Delays:

2) Step 1: QCQP Transformation and Semidefinite Relaxation: · 3) Step 2: Improvement to SDR-C by Alternating Optimization (AO):

For MCC with a CAP, the method transforms the problem for separable semidefinite relaxation and modifies binary-decision recovery to handle the placement constraint. Alternating optimization then refines the feasible solution by updating offloading decisions and resource allocations.

2) Step 1: QCQP Transformation and Semidefinite Relaxation:

  • The CAP problem is rewritten into a non-convex separable QCQP and solved through a relaxed separable SDP using the separable SDR approach.The transformed optimization vector includes auxiliary variables for delay.Source: 2) Step 1: QCQP Transformation and… · p. 9
  • The CAP formulation introduces auxiliary variables for uplink transmission, downlink transmission, and CAP processing times, with corresponding constraints.The CAP processing-time variable also introduces a new constraint.Source: 2) Step 1: QCQP Transformation and… · p. 9
  • MUMTO SDR with CAP (SDR-C) modifies binary offloading-decision recovery to handle the additional placement constraint and obtain corresponding communication-resource allocations.The earlier MUMTO reconstruction cannot be directly applied because of that constraint.Source: 2) Step 1: QCQP Transformation and… · p. 9
  • Once binary offloading decisions are recovered, the remaining computation and communication resource-allocation problem is convex and can be solved optimally.The fixed offloading decisions make the energy term constant in this allocation problem.Source: 2) Step 1: QCQP Transformation and… · pp. 9–10

3) Step 2: Improvement to SDR-C by Alternating Optimization (AO):

  • AO alternates between the integer offloading-decision problem and the convex resource-allocation problem, with the decision problem separable into one subproblem per user.The resource-allocation problem is convex for any fixed offloading decision.Source: 3) Step 2: Improvement to SDR-C by… · p. 10
  • AO repeats decision and allocation updates, accepts only lower-cost solutions, and converges because system cost is lower bounded.It stops when total system cost cannot be further decreased.Source: 3) Step 2: Improvement to SDR-C by… · p. 10
  • The alternating-optimization solution is better than or at least as good as the feasible SDR-C starting solution.AO starts from the SDR-C offloading decisions and resource allocation.Source: 3) Step 2: Improvement to SDR-C by… · p. 10

4) Step 3: Sequential Tuning (ST) to Reach Local Optimum: · 5) Overall MUMTO-C Algorithm:

Sequential tuning (ST) iteratively improves MUMTO-C’s solution until no task-level offloading change can reduce system cost, yielding a locally optimal solution. In the overall algorithm, SDR-C supplies AO’s starting point, AO prepares a better starting point for ST, and ST improves the solution and guarantees local optimality.

4) Step 3: Sequential Tuning (ST) to Reach Local Optimum:

  • ST starts from the AO solution and iteratively seeks lower system cost to improve the solution.The procedure is intended to further reduce system cost and eventually reach a local optimum of problem (47).Source: 4) Step 3: Sequential Tuning (ST) to… · p. 10
  • For each task, ST tests its three offloading decisions while holding other tasks fixed, solving problem (57) to evaluate each choice.When a choice lowers total cost, ST updates the offloading decision and corresponding resource allocation.Source: 4) Step 3: Sequential Tuning (ST) to… · p. 10
  • ST converges because the offloading decisions have finitely many possible values, and its output is locally optimal for problem (47).At convergence, no user’s offloading decision and corresponding resource allocation can further reduce system cost.Source: 4) Step 3: Sequential Tuning (ST) to… · p. 10

5) Overall MUMTO-C Algorithm:

  • SDR-C provides AO a suitable starting point; without it, AO may converge to a highly sub-optimal solution from a random starting point.The paper points to Section VI-C for this result.Source: 5) Overall MUMTO-C Algorithm · p. 10
  • AO moves the solution closer to the optimum and provides ST a suitable starting point, helping reduce ST’s iteration count.ST iterations can be computationally expensive because they may require searching over many tasks.Source: 5) Overall MUMTO-C Algorithm · p. 10
  • Together, SDR-C, AO, and ST each play an important role: ST further improves the solution and guarantees that the final solution is a local optimum.The paper says further numerical evaluation of these steps’ roles and contributions is given in Section VI-C.Source: 5) Overall MUMTO-C Algorithm · p. 10

D. Lower Bound on the Optimal Solution · VI. PERFORMANCE EVALUATION · A. Simulation Setup

The paper derives an SDR-based lower bound for MUMTO-C and reports that the method performs nearly optimally against it. Simulations evaluate MUMTO and MUMTO-C under varying parameter settings.

D. Lower Bound on the Optimal Solution

VI. PERFORMANCE EVALUATION

  • Simulations study the performance of MUMTO and MUMTO-C under different parameter settings.Source: §VI · p. 11

A. Simulation Setup

  • The setup uses Nokia-derived device characteristics and x264 CBR tasks requiring 1900 cycles/byte, with 10–30 MB inputs and 1–3 MB outputs.Source: A. Simulation Setup · p. 11
  • User-CAP bandwidth is 40 MHz without separate uplink or downlink limits; transmit and receive energy is 1.42 × 10^-7 J/bit, ηu_i is 3.5 b/s/Hz, and CAP-cloud transmission is 15 Mpbs.Source: A. Simulation Setup · p. 11
  • Other parameters use the defaults in Table II, and results average 100 realizations of task input and output sizes.Source: A. Simulation Setup · p. 11

B. Performance Evaluation for MUMTO without CAP … VII. CONCLUSION

MUMTO and MUMTO-C are reported to achieve nearly optimal performance against lower bounds and to outperform alternatives across varied settings. The evaluation also describes algorithm-component benefits and scalability, while the conclusion outlines the methods and future research directions.

B. Performance Evaluation for MUMTO without CAP

1) Contribution of the Algorithm Components:

2) Comparison with Further Alternatives:

  • MUMTO-C is near-optimal and substantially outperforms the alternatives, especially when CAP-use cost is small or cloud-use cost is large.The CAP lower bound converges to the local-cloud lower bound as α grows; the latter converges to local-only processing as β grows.Source: 2) Comparison with Further Alternatives · p. 13

VII. CONCLUSION

  • The study formulates joint offloading and communication-resource allocation as a non-convex separable QCQP, uses SDR and binary recovery for MUMTO, and proposes three-step MUMTO-C, which computes a locally optimal solution.Future directions include strict delay constraints, user mobility, dynamically arriving tasks, and systems with multiple CAPs.Source: §VII · pp. 13–14
  • Both MUMTO and MUMTO-C give nearly optimal performance and substantially outperform existing alternatives over a wide range of parameter settings.Source: §VII · p. 14
Loading 1803.06577v2…