PaperlayerView exact revision on arXiv

Source-linked AI summary

Latency Optimization for Resource Allocation in Mobile-Edge Computation Offloading

Jinke Ren, Guanding Yu, Yunlong Cai, Yinghui He

arXiv:1704.00163v1cs.IT

TL;DR

Traditional cloud computing cannot meet millisecond-scale latency needs, motivating joint communication and computation resource allocation in multi-user MECO. The paper analyzes three compression-offloading models and finds that partial compression offloading significantly reduces end-to-end latency compared with local and edge cloud compression.

  • Problem

    Traditional cloud computing is inadequate for achieving the ambitious millisecond-scale latency required by fifth-generation networks.

  • Method

    The paper derives closed-form solutions for local and edge cloud compression and develops a piecewise optimization algorithm for partial compression offloading.

  • Results

    Partial compression offloading efficiently reduces end-to-end latency compared with the other two compression models.

  • Takeaways & Limitations

    Partial compression offloading is an effective model for reducing end-to-end latency in the studied multi-user MECO system.

Abstract

from arXiv · show

By offloading intensive computation tasks to the edge cloud located at the cellular base stations, mobile-edge computation offloading (MECO) has been regarded as a promising means to accomplish the ambitious millisecond-scale end-to-end latency requirement of the fifth-generation networks. In this paper, we investigate the latency-minimization problem in a multi-user time-division multiple access MECO system with joint communication and computation resource allocation. Three different computation models are studied, i.e., local compression, edge cloud compression, and partial compression offloading. First, closed-form expressions of optimal resource allocation and minimum system delay for both local and edge cloud compression models are derived. Then, for the partial compression offloading model, we formulate a piecewise optimization problem and prove that the optimal data segmentation strategy has a piecewise structure. Based on this result, an optimal joint communication and computation resource allocation algorithm is developed. To gain more insights, we also analyze a specific scenario where communication resource is adequate while computation resource is limited. In this special case, the closed-form solution of the piecewise optimization problem can be derived. Our proposed algorithms are finally verified by numerical results, which show that the novel partial compression offloading model can significantly reduce the end-to-end latency.

I. INTRODUCTION

The paper addresses weighted-sum latency minimization in a multi-user MECO system with limited communication and computation resources by comparing local, edge-cloud, and partial compression offloading models. It derives closed-form solutions for the first two models and develops piecewise optimization and resource-allocation methods for partial compression offloading.

  • Research objective: The paper targets the latency-minimization problem for multi-user MECO with partial computation offloading under limited communication and computation resources.The objective is to minimize the weighted-sum delay of all devices.
  • Compression models: Three compression models are proposed: local compression, edge cloud compression, and partial compression offloading.They differ according to where data is compressed: locally, at the edge cloud, or at both locations.
  • Local compression: For local compression, a convex optimization problem yields closed-form optimal resource allocation and minimum weighted-sum delay.The formulation uses a communication resource constraint.
  • Edge cloud compression: For edge cloud compression, joint communication-and-computation resource allocation produces a closed-form solution and minimum weighted-sum delay.The solution is obtained using the Lagrange multiplier method.
  • Partial compression offloading: For partial compression offloading, the optimal data segmentation has a piecewise structure, enabling a piecewise convex reformulation and an optimal sub-gradient resource-allocation solution.The original model is first formulated as a piecewise optimization problem.
  • Special scenario: When communication resources are adequate and computation resources are limited, a closed-form solution is derived and verified to achieve near-optimal performance in general scenarios.In this specific scenario, each device’s delay expression can be simplified.

II. SYSTEM MODEL · A. Multi-user MECO System · B. Multiple-Access Model

The system model comprises one edge cloud serving K single-antenna mobile devices that compress and store data, with computation shared between devices and the cloud. Channel access uses TDMA, assigning each device a normalized time slot and modeling its achievable rate from channel gain, transmission power, bandwidth, and AWGN.

  • A. Multi-user MECO System: The MECO system contains one edge cloud platform and K single-antenna mobile devices connected through wireless channels.The devices are indexed by K = {1, 2, · · · , K}.
  • A. Multi-user MECO System: Each device has data, such as raw video, that must be compressed and stored in the edge cloud.The framework uses video compression as its example data-analytic application.
  • A. Multi-user MECO System: Device k is characterized by raw-video size L_k and local CPU compression capacity V_k^d, while the cloud provides total capacity V^c allocated across devices.The allocation satisfies V_k^c ≤ V^c.
  • A. Multi-user MECO System: The centralized scheduler is assumed to know all channel gains and video sizes, while segmentation, stitching, and storage delays are neglected.These operations are considered much shorter than communication and computational delays.
  • A. Multi-user MECO System: All devices and the edge cloud use the same compression technology, with compression ratio β ∈ (0, 1).One bit of raw video is compressed into β bit, enabling simultaneous cloud compression across devices.
  • B. Multiple-Access Model: TDMA divides one time frame into K time slots allocated to the K devices, with device k receiving normalized duration t_k ∈ [0, 1].The time frame is short enough to be ignored when calculating each device’s end-to-end delay.
  • B. Multiple-Access Model: For device k, channel gain h_k(i) is i.i.d. across time slots, transmission power is p_k, and the achievable rate depends on bandwidth B and AWGN variance N_0.The achievable data rate is defined separately for each time slot i.

C. Local Compression Model · D. Edge Cloud Compression Model · E. Partial Compression Offloading Model

The paper defines local and edge-cloud compression models with distinct computation and transmission delays, then proposes partial compression offloading to balance both resources. The partial model partitions each video between local and edge compression and motivates joint resource allocation for weighted-sum delay minimization.

  • C. Local Compression Model: Local compression first compresses each raw video at its device, then transmits the compressed video to the edge cloud for storage.The model includes local compression and compressed-video transmission delays.
  • C. Local Compression Model: The local model separately accounts for compressing Lk bits at device k and transmitting βLk compressed bits to the edge cloud.Transmission rates depend on random channel gains and are characterized using average data rates.
  • D. Edge Cloud Compression Model: Edge-cloud compression uploads each raw video without compression, after which the edge cloud compresses all received videos in parallel using allocated computation resources.The edge-cloud model likewise separates raw-video transmission and cloud-compression delays.
  • E. Partial Compression Offloading Model: Local compression can be unfavorable when device CPU speed is limited, whereas edge-cloud compression can be unfavorable when channel bandwidth is limited.These conditions motivate splitting compression between the mobile device and edge cloud.
  • E. Partial Compression Offloading Model: Partial compression offloading partitions each raw video into two parts, compressing one locally and offloading the other for edge compression.The locally compressed proportion is λk ∈[0, 1].
  • E. Partial Compression Offloading Model: The partial model includes local compression, local-compressed transmission, uncompressed-part transmission, and edge-cloud compression delays.Because each device has one transmission channel, the two transmitted parts cannot be sent simultaneously, producing two possible transmission orderings.
  • E. Partial Compression Offloading Model: The paper develops optimal joint communication and computation resource allocation algorithms minimizing the weighted-sum delay across devices for all three models.The partial model’s transmission ordering determines its end-to-end delay expression.

III. OPTIMAL SOLUTION TO THE LOCAL COMPRESSION MODEL · A. Problem Formulation · B. Optimal Solution

The local compression model formulates weighted-sum latency minimization under fairness weights and an overall communication-resource constraint. Its convex optimization admits a closed-form optimal allocation and minimum system delay derived through KKT conditions.

  • III. OPTIMAL SOLUTION TO THE LOCAL COMPRESSION MODEL: The section formulates latency minimization for the local compression model and derives closed-form optimal allocation and minimum weighted-sum delay.
  • A. Problem Formulation: The objective is to minimize the weighted-sum delay of all devices.
  • A. Problem Formulation: Weight factors {αk} represent device fairness in the optimization.
  • A. Problem Formulation: Problem 1, labeled Local Compression, includes an overall communication resource constraint across all devices.
  • B. Optimal Solution: Problem 1 is convex and satisfies Slater’s condition, so strong duality permits solution through Karush-Kuhn-Tucker conditions.
  • B. Optimal Solution: Theorem 1 gives the optimal solution for Problem 1 in the local compression model.
  • B. Optimal Solution: The optimal time-slot allocation depends on each device’s weight factor, raw-video size, and channel capacity.
  • B. Optimal Solution: The minimum system delay, defined as the weighted-sum delay of all devices, is obtained in closed form.

IV. OPTIMAL SOLUTION TO THE EDGE CLOUD COMPRESSION MODEL … B. Optimal Segmentation Strategy and Problem Transformation

The paper derives optimal joint communication and computation resource allocation for edge cloud compression, then extends the analysis to partial compression offloading through piecewise segmentation and convex problem transformation.

  • IV. OPTIMAL SOLUTION TO THE EDGE CLOUD COMPRESSION MODEL: The edge cloud compression section formulates latency minimization and devises joint optimal communication and computation resource allocation.
  • A. Problem Formulation: Problem 2 minimizes the weighted-sum delay of all devices under communication and computation resource limitations.
  • B. Optimal Solution: Because each component is convex, Problem 2 is optimally solved using KKT conditions, yielding the optimal solution stated in Theorem 2.
  • B. Optimal Solution: The edge cloud compression model allocates cloud compression capacity according to each device’s weight factor and video size, with minimum system delay expressed accordingly.
  • V. OPTIMAL SOLUTION TO THE PARTIAL COMPRESSION OFFLOADING MODEL: The partial compression offloading model jointly allocates communication and computation resources because each raw video is compressed partly at the mobile device and partly at the edge cloud.
  • A. Problem Formulation: Problem 3 formulates latency minimization for partial compression offloading using the piecewise delay expression D_k.
  • B. Optimal Segmentation Strategy and Problem Transformation: Lemma 1 shows that, given {t_k} and {V^c_k}, the optimal video segmentation strategy has a piecewise structure determined by average communication and compression capacities.
  • B. Optimal Segmentation Strategy and Problem Transformation: Substituting the optimal segmentation converts Problem 3 into equivalent Problem 4, which Theorem 3 establishes as a piecewise convex optimization problem.

C. Optimal Resource Allocation Algorithm

The paper develops a sub-gradient algorithm for Problem 4 because its continuous, piecewise delay expression has quartic partial derivatives that prevent direct use of classical KKT conditions. The algorithm iteratively updates communication and computation resources, converges linearly to the optimum as ǫ → 0, and has polynomial complexity.

  • Problem formulation: Quartic partial derivatives make classical KKT conditions unsuitable for directly solving Problem 4.The delay expression is continuous but piecewise, and its partial derivatives with respect to t_k have quartic forms.
  • Sub-gradient solution: The proposed solution uses a sub-gradient method to optimally solve Problem 4.The method is designed for the non-differential convex structure of the problem.
  • Sub-gradient solution: Theorem 4 solves Problem 4 through an iterative update governed by a step size and sub-gradient function.The resource constraints are incorporated as obstacle functions during the iteration.
  • Algorithm 1: Algorithm 1 iteratively updates the communication and computation resource allocation from a feasible initial vector.The procedure initializes tolerance, iteration index, and a resource allocation satisfying constraints (21b) and (21c).
  • Convergence and complexity: The allocation vector x(n) linearly converges to the optimal solution x∗ when ǫ →0.The convergence result is established in Appendix C.
  • Convergence and complexity: The proposed algorithm has polynomial computational complexity, supporting practical implementation.The required iteration count until convergence is determined by the maximum tolerance ǫ.

D. A Special Case

The paper analyzes partial compression offloading when communication capacity greatly exceeds device computation capacity. In this case, transmission delay for locally compressed video is negligible, enabling an explicit segmentation strategy and closed-form optimal allocation.

  • Scenario: The special case assumes adequate communication resources but limited computation resources, with channel capacity much greater than device computation capacity.The paper identifies sensor networks and machine-type communications as examples of this scenario.
  • Scenario: Transmission delay for locally compressed video can be neglected relative to the delay for compressing its local-compression portion.This simplification follows from the scenario’s high channel capacity and small locally compressed video size.
  • Optimal Segmentation: Lemma 2 gives the optimal video segmentation strategy for each device in the specific partial compression offloading scenario.The lemma provides the segmentation structure after applying the detailed delay expressions to the optimization problem.
  • Optimal Allocation: The resulting convex problem can be solved using KKT conditions, yielding the optimal solution stated in Theorem 5.Theorem 5 characterizes the specific scenario’s optimal partial compression offloading solution through optimal Lagrange multipliers satisfying active resource constraints.
  • Allocation Insights: Theorem 5’s allocation depends on each device’s weight factor, raw-video size, channel capacity, and local compression capacity.Larger video size leads to more communication and computation resources, whereas larger communication capacity leads to less communication allocation.

VI. NUMERICAL RESULTS · A. Performance Comparison among Three Models

Numerical results validate the proposed algorithms and compare local compression, edge cloud compression, and partial compression offloading. Partial compression offloading performs best overall, while the relative performance of local and edge cloud compression depends on device count and available local compression capacity.

  • A. Performance Comparison among Three Models: The simulations first compare minimum system delays for local compression, edge cloud compression, and partial compression offloading.The comparison examines delay as the number of mobile devices and average device compression capacity vary.
  • A. Performance Comparison among Three Models: Edge cloud compression and partial compression offloading delays increase with device count, whereas local compression delay remains approximately invariant because communication resources are relatively adequate.The increasing delays of the two offloading models result from limited computation resources.
  • A. Performance Comparison among Three Models: Edge cloud compression outperforms local compression only when the number of devices is small; with more devices, local compression performs better.Cloud allocation per device exceeds local capacity at small device counts but falls below it as the number of devices grows.
  • A. Performance Comparison among Three Models: Partial compression offloading achieves the best performance among the three models by jointly using communication and computation resources.Its advantage over edge cloud compression becomes more evident as the number of devices grows, reducing system delay and improving users’ QoE.
  • A. Performance Comparison among Three Models: Theorem 5’s closed-form solution achieves near-optimal performance while outperforming both local compression and edge cloud compression models.This result is attributed to mobile-device compression capacity being much smaller than the corresponding communication capacity under the simulation settings.

B. Optimal Resource Allocation in Partial Compression Offloading Model · VII. CONCLUSION

The partial compression offloading model reallocates communication and computation resources according to video size and local compression capacity, while numerical results show it reduces end-to-end latency. The paper derives closed-form or efficiently solvable allocations and identifies extensions to non-orthogonal access and energy efficiency.

  • B. Optimal Resource Allocation in Partial Compression Offloading Model: As device 1’s video size increases, its optimal time-slot and cloud computation allocations increase, while allocations to other devices decrease.The simulation uses five devices and varies device 1’s parameters while holding devices 2–5 fixed.
  • B. Optimal Resource Allocation in Partial Compression Offloading Model: Optimal communication and computation allocations follow nearly identical trends because both resources similarly affect each device’s end-to-end delay.This behavior is illustrated in Fig. 4(a) and Fig. 4(b).
  • B. Optimal Resource Allocation in Partial Compression Offloading Model: As device 1’s local compression capacity increases, its optimal time-slot and cloud compression allocations decrease, while other devices receive more resources.The additional resources prioritize devices with lower compression capacity to reduce the weighted-sum delay.
  • B. Optimal Resource Allocation in Partial Compression Offloading Model: Communication and computation allocations vary approximately linearly with local compression capacity because the relevant capacities have comparable effects on end-to-end delay.The trend is shown in Fig. 5(a) and Fig. 5(b).
  • VII. CONCLUSION: The paper minimizes weighted-sum delay in a TDMA multi-user MECO system to improve users’ QoE, studying local, edge-cloud, and partial compression models.The three models are studied and compared.
  • VII. CONCLUSION: Closed-form optimal solutions are obtained for local and edge-cloud compression, while partial offloading uses closed-form segmentation and a piecewise convex problem solved by a sub-gradient method.When communication capacity greatly exceeds device compression capacity, the partial-offloading problem also has a closed-form solution.
  • VII. CONCLUSION: Numerical results demonstrate that partial compression offloading efficiently reduces end-to-end latency compared against local and edge-cloud compression.Future work includes non-orthogonal channel access with co-channel interference and joint communication-computation energy-efficiency optimization.

APPENDIX A PROOF OF LEMMA 1 · APPENDIX B PROOF OF THEOREM 3

Appendix A proves Lemma 1 by analyzing a critical delay-balancing case and the resulting dependence on the segmentation variable. Appendix B proves Theorem 3 by establishing convexity of the piecewise objective and its sum over users.

  • APPENDIX A PROOF OF LEMMA 1: The critical case is converted into a condition by substituting detailed delay expressions into (34).The proof then proceeds through case analysis.
  • APPENDIX A PROOF OF LEMMA 1: In the critical case, local-part compression delay equals transmission delay, while edge-cloud compression delay equals transmission delay of locally compressed data.These equalities define the delay-balancing case used in the proof.
  • APPENDIX A PROOF OF LEMMA 1: As λk increases, the device-k delay decreases until reaching its minimum, and the optimal video segmentation strategy is λ∗.The supplied proof identifies the minimizing segmentation through this monotonicity analysis.
  • APPENDIX A PROOF OF LEMMA 1: For Case B, tkRk (1 + (β −1) λk) decreases with λk because 0 < β < 1, whereas another delay term increases with λk.This opposing monotonicity supports the subsequent segmentation analysis.
  • APPENDIX B PROOF OF THEOREM 3: Problem 4 is convex if its objective function is convex because all of its constraints are affine.Appendix B therefore focuses on proving convexity of the objective.
  • APPENDIX B PROOF OF THEOREM 3: The component bDk,1 is shown strictly convex on tk and V c by proving that its Hessian is positive-definite.The proof uses positivity of the leading principal minors of the Hessian.
  • APPENDIX B PROOF OF THEOREM 3: The component bDk,2 is convex on tk and V c, including because it does not change over V c.The proof establishes convexity using its second-order partial derivative and its constant behavior on the other region.
  • APPENDIX B PROOF OF THEOREM 3: Because bDk is continuous and piecewise and can be rewritten as max{ bDk,1, bDk,2}, it is convex; summing these convex functions keeps the objective convex.The proof invokes preservation of convexity under pointwise maximum and summation.

APPENDIX C PROOF OF THEOREM 4 · APPENDIX D PROOF OF THEOREM 5

Appendix C proves that the iterative method in Theorem 4 converges to the optimal resource allocation, while Appendix D derives a closed-form solution using strict convexity and KKT conditions.

  • APPENDIX C PROOF OF THEOREM 4: Theorem 4’s iterative method is shown to converge to the optimal resource allocation solution x∗.The proof compares the distance between the (n + 1)th iterate and x∗.
  • APPENDIX C PROOF OF THEOREM 4: The convergence argument uses the Euclidean norm and the transpose of g(n) to characterize the iteration-to-optimum relationship.The relevant inequality relies on the convexity of PK.
  • APPENDIX C PROOF OF THEOREM 4: The upper-bound difference between F(n) and the optimum decreases until Fbest − F(x∗) converges to zero.This establishes convergence of the objective value to the optimum.
  • APPENDIX C PROOF OF THEOREM 4: A Polyak step size φn = F… can be selected to accelerate convergence toward the optimal solution x∗.The passage introduces this step-size choice specifically to improve convergence speed.
  • APPENDIX D PROOF OF THEOREM 5: Appendix D establishes that the end-to-end delay expression (32) is strictly convex on tk and k.The derivation follows the method used in Appendix B.
  • APPENDIX D PROOF OF THEOREM 5: Because of strict convexity, KKT conditions are used to derive a closed-form optimal resource allocation solution.The proof formulates the Lagrange function and identifies the optimal solution for the specific scenario.
  • APPENDIX D PROOF OF THEOREM 5: The KKT conditions provide necessary and sufficient conditions for the optimal allocation.Applying those conditions yields the resource allocation solution and completes the proof.
Loading 1704.00163v1…