PaperlayerView exact revision on arXiv

Source-linked AI summary

Joint Task Offloading and Resource Allocation for Multi-Server Mobile-Edge Computing Networks

Tuyen X. Tran, Dario Pompili

arXiv:1705.00704v1cs.NI

TL;DR

The paper addresses joint task offloading and resource allocation in multi-cell, multi-server MEC networks, where the problem is NP-hard. It decomposes the problem into resource allocation and task offloading, solving the former with convex methods and the latter with a polynomial-time heuristic. Simulations show performance close to optimal and significantly higher offloading utility than traditional approaches.

  • Problem

    Most existing work does not jointly optimize task offloading, radio resources, and computing resources in multi-cell, multi-server MEC systems.

  • Method

    The paper decomposes JTORA into fixed-decision resource allocation and task offloading, solving allocation with quasi-convex and convex optimization and offloading with a polynomial-time heuristic.

  • Results

    Simulations show the heuristic performs closely to the optimal solution and significantly improves average system offloading utility over traditional approaches.

  • Takeaways & Limitations

    A holistic multi-cell, multi-server strategy can provide a practical suboptimal solution for jointly improving MEC offloading utility.

Abstract

from arXiv · show

Mobile-Edge Computing (MEC) is an emerging paradigm that provides a capillary distribution of cloud computing capabilities to the edge of the wireless access network, enabling rich services and applications in close proximity to the end users. In this article, a MEC enabled multi-cell wireless network is considered where each Base Station (BS) is equipped with a MEC server that can assist mobile users in executing computation-intensive tasks via task offloading. The problem of Joint Task Offloading and Resource Allocation (JTORA) is studied in order to maximize the users' task offloading gains, which is measured by the reduction in task completion time and energy consumption. The considered problem is formulated as a Mixed Integer Non-linear Program (MINLP) that involves jointly optimizing the task offloading decision, uplink transmission power of mobile users, and computing resource allocation at the MEC servers. Due to the NP-hardness of this problem, solving for optimal solution is difficult and impractical for a large-scale network. To overcome this drawback, our approach is to decompose the original problem into (i) a Resource Allocation (RA) problem with fixed task offloading decision and (ii) a Task Offloading (TO) problem that optimizes the optimal-value function corresponding to the RA problem. We address the RA problem using convex and quasi-convex optimization techniques, and propose a novel heuristic algorithm to the TO problem that achieves a suboptimal solution in polynomial time. Numerical simulation results show that our algorithm performs closely to the optimal solution and that it significantly improves the users' offloading utility over traditional approaches.

I. INTRODUCTION

The paper develops a holistic JTORA solution for multi-cell, multi-server MEC networks, where offloading decisions and resource allocation jointly maximize users’ offloading gains. It decomposes the NP-hard problem into tractable resource-allocation subproblems and a polynomial-time heuristic task-offloading algorithm.

  • Motivation: MEC places computing capabilities near users, supporting latency-sensitive services while reducing end-to-end delay and backhaul burden.The paper motivates MEC through applications including augmented reality, IoT, autonomous vehicles, image processing, and face recognition.
  • Problem: Offloading creates communication delay and energy overhead, while finite MEC computing capacity can increase task-execution delay.These coupled effects make offloading decisions and resource allocation critical to efficient computation offloading.
  • Vision: The proposed multi-server design jointly optimizes task offloading and resource allocation to maximize users’ offloading gains in a multi-cell network.Each base station is equipped with a MEC server, enabling users to select nearby servers and allowing coordination across neighboring cells.
  • Vision: Multi-server MEC can relieve overloaded servers, exploit favorable uplink channels, and mitigate interference and resource contention.These mechanisms support lower transmission energy and improved offloading gains when multiple users offload simultaneously.
  • Challenges and Contributions: Inter-cell interference makes radio allocation nonconvex, while offloading must select both whether to offload and which BS or server to use.The model also accounts for heterogeneous device capabilities, task requirements, and server resources.
  • Challenges and Contributions: JTORA is formulated as an MINLP jointly optimizing offloading decisions, uplink transmit power, and MEC computing-resource allocation.The objective is a weighted sum of improvements in task-completion time and device energy consumption.
  • Challenges and Contributions: The NP-hard problem is decomposed into resource allocation with fixed offloading and task offloading over the resource-allocation optimal-value function.The resource-allocation problem further separates into uplink power allocation and computing-resource allocation, solved using quasi-convex and convex optimization.
  • Challenges and Contributions: The polynomial-time heuristic produces a suboptimal task-offloading solution whose simulations are near-optimal and significantly improve users’ offloading utility over traditional approaches.The paper reports this outcome through extensive numerical simulations.

II. RELATED WORKS

Prior MEC and mobile-cloud studies address selected offloading, radio, computing, or collaboration problems, but commonly simplify computing capacity or use a single server. This paper targets holistic joint optimization in multi-cell, multi-server MEC systems.

  • MEC Applications: MEC research has explored collaboration, caching, transcoding, adaptive video streaming, connected vehicles, and low-latency roadside services.These studies position MEC as a platform for network-edge processing and application support.
  • Mobile Cloud Computing: Many mobile-cloud studies assumed effectively unlimited cloudlet computing resources, reducing offloading scheduling to radio-resource allocation.Under that assumption, offloaded tasks could execute with negligible delay.
  • Computation Offloading: Existing MEC work studied joint offloading and allocation in specialized settings, including energy-harvesting devices and multi-cell systems where server congestion was omitted.Other work considered limited edge resources but focused on a single-server MEC system.
  • Research Gap: Most existing studies did not jointly determine task offloading, radio allocation, and computing allocation in a multi-cell, multi-server system.This missing combination defines the scope of the article’s contribution.

III. SYSTEM MODEL

The system models multiple MEC-equipped base stations serving users that either execute one atomic task locally or offload it to a nearby server. Offloading delay and energy depend on uplink transmission, MEC computation, wireless interference, and allocated resources.

  • Network Model: The network contains multiple cells, with each BS equipped with a MEC server that serves resource-constrained mobile users over wireless channels.Users can offload tasks to a server at one of the nearby BSs they can connect to.
  • User Computation Tasks: Each user has one atomic computation task characterized by input size d_u and computational workload c_u, and can execute it locally or offload it.The workload is measured in CPU cycles, while input size is measured in bits.
  • User Computation Tasks: Local execution is modeled through the user’s CPU capability, task-completion time, and energy consumption per computing cycle.The energy-per-cycle model uses E = κf^2, where κ depends on chip architecture and f is CPU frequency.
  • Task Offloading: Offloaded-task delay includes uplink input transmission, MEC execution, and output transmission, although output-transfer delay is omitted because outputs are smaller and downlink rates are higher.This omission follows the paper’s stated modeling assumption.
  • Task Uploading: OFDMA divides bandwidth B into N equal sub-bands, assigning users associated with the same BS to distinct sub-bands and limiting simultaneous service to N users.Inter-cell interference remains because users on the same sub-band may transmit from different cells.
  • Task Uploading: Binary offloading variables encode whether user u sends its task to BS s on sub-band j, with each task offloaded to at most one MEC server.The policy incorporates both server selection and uplink sub-band scheduling.
  • Task Uploading: Uplink transmission power is bounded by each user’s maximum budget, and achievable rates depend on SINR under inter-cell interference.Users associated with the same BS avoid intra-cell interference through distinct sub-bands, but still experience inter-cell interference.

C. MEC Computing Resources

The MEC servers share computing resources among associated users, while offloading utility reflects task-completion time and energy trade-offs. Joint optimization is motivated by the interaction between radio access and computation and by resource-induced delay.

  • Each base station’s MEC server provides computing offloading service to multiple users concurrently.
  • Computing resources are quantified by the server’s computational rate in CPU cycles/s and allocated through policy F.
  • Each offloaded task receives positive computing resources from its serving base station, subject to the server’s total capacity constraint.
  • Offloading utility captures relative improvement in task-completion time and energy consumption, allowing users to trade longer completion time for lower energy use.
  • Excessive offloading can create delay from limited bandwidth and MEC computation resources, potentially degrading some users’ QoE relative to local execution.
  • The resulting interaction between radio access and computation motivates jointly optimizing offloading scheduling, radio resources, and computing resources.

IV. PROBLEM FORMULATION

The paper formulates JTORA as a weighted system-utility maximization problem over offloading, uplink power, and computing-resource decisions. Constraints enforce feasible task assignment, transmission, and server-resource allocation, while the MINLP formulation is NP-hard and motivates a practical suboptimal approach.

  • IV. PROBLEM FORMULATION: The section introduces the joint task offloading and resource allocation problem and outlines its decomposition approach.
  • A. Joint Task Offloading and Resource Allocation Problem: JTORA maximizes system utility over task-offloading decisions, uplink power allocation, and computing-resource allocation.
  • A. Joint Task Offloading and Resource Allocation Problem: System utility is defined as the weighted sum of users’ offloading utilities, with λu representing the resource provider’s preference for user u.
  • A. Joint Task Offloading and Resource Allocation Problem: Each task is executed locally or offloaded to at most one server on one sub-band, and each base station serves at most one user per sub-band.
  • A. Joint Task Offloading and Resource Allocation Problem: User transmission powers obey individual budgets, while associated users receive positive computing resources whose total cannot exceed server capacity.
  • A. Joint Task Offloading and Resource Allocation Problem: The JTORA formulation is a Mixed Integer Nonlinear Program that is NP-hard, so optimal solutions usually require exponential time complexity.
  • A. Joint Task Offloading and Resource Allocation Problem: Because the number of variables scales with users, MEC servers, and sub-bands, the paper targets a low-complexity suboptimal solution with competitive performance.

B. Problem Decomposition

The decomposition fixes the offloading decision, solves the resulting resource-allocation problem, and then optimizes the resulting value function over task offloading. Resource allocation further separates into uplink power and computing-resource subproblems, enabling low-complexity optimization.

  • The high complexity of JTORA arises from the combinatorial nature of task-offloading decisions.
  • The method temporarily fixes offloading decision X to form the Resource Allocation problem, then uses its solution to derive the Task Offloading solution.
  • Decoupled constraints make the original problem equivalent to a Task Offloading problem that optimizes the optimal-value function of resource allocation.
  • For a fixed offloading decision, the resource-allocation objective can be recast as minimizing total offloading overhead.
  • The resource-allocation problem separates into Uplink Power Allocation and Computing Resource Allocation because their objectives and constraints are decoupled.
  • Inter-cell interference couples users’ uplink powers across base stations, so the method approximates interference to obtain separable power-allocation subproblems.
  • The approximated uplink power problem remains non-convex but is strictly quasi-convex, allowing a bisection method based on derivative evaluations.
  • The proposed bisection method evaluates the derivative-related function each iteration and terminates in ⌈log2(Pu/ǫ)⌉ iterations when Ωs(Pu)>0.

B. Computing Resource Allocation (CRA)

The CRA subproblem optimizes the computing-resource term after decomposition. Its convexity follows from a convex constraint and a positive-definite Hessian, enabling solution through KKT conditions.

  • The Computing Resource Allocation problem optimizes the second term on the right-hand side of the decomposed objective.
  • The CRA constraint is convex, and the objective’s Hessian is diagonal with strictly positive elements.
  • Because the CRA problem is convex, its optimal computing-resource allocation and objective value can be obtained using Karush-Kuhn-Tucker conditions.

C. Joint Task Offloading Scheduling and Resource Allocation

The task-offloading problem is decomposed into resource allocation and task-offloading subproblems, then solved with optimization and a polynomial-time heuristic. The resulting joint solution is locally optimal and performs closely to exhaustive search.

  • Problem decomposition: The approach fixes the task-offloading decision to solve resource allocation, then optimizes the resulting optimal-value function over offloading decisions.The resource-allocation solutions include uplink power and computing-resource allocation.
  • Problem formulation: The task-offloading problem maximizes a set function over a ground set subject to two matroid constraints.Its NP-hardness makes efficient algorithms guaranteeing optimality difficult to design.
  • Heuristic algorithm: The proposed heuristic starts from an empty set and repeatedly applies improving remove or exchange operations while respecting the two matroid constraints.An exchange can add one outside element and drop up to two current elements.
  • Complexity and solution: The heuristic runs in polynomial time and returns a local-optimal task-offloading decision with corresponding power and computing-resource allocations.The final JTORA solution is formed by combining the heuristic decision with the resource-allocation solutions.
  • Performance: The heuristic performs closely to the optimal solution obtained by exhaustive search in numerical comparisons.The paper notes that characterizing the degree of suboptimality is non-trivial because of combinatorial decisions and nonconvexity.

VI. PERFORMANCE EVALUATION

The evaluation uses a multi-cell MEC network simulation with specified channel, computing, task, and transmission settings. The setup models multiple cells, users, and MEC servers under randomized user placement.

  • Evaluation setup: The simulations evaluate the performance of the proposed task-offloading and resource-allocation strategy.The strategy is referred to as hJTORA.
  • Network model: The simulated network contains multiple hexagonal cells, each with a base station, while neighboring base stations are separated by 1 km.Users and base stations use single antennas for uplink transmission.
  • Wireless parameters: Channel gains follow a distance-dependent path-loss model with 8 dB log-normal shadowing variance.The path-loss expression is L [dB] = 140.7 + 36.7log10d[km].
  • Simulation parameters: The default simulations use 7 cells, 20 dBm maximum user transmit power, 20 MHz bandwidth, and background noise power of -100 dBm.These are the stated default wireless settings unless otherwise specified.

RUNTIME COMPARISON AMONG COMPETING SCHEMES

The evaluation compares hJTORA with exhaustive search and three baseline schemes across runtime and system utility scenarios. hJTORA stays near the optimum while substantially outperforming the baselines, with runtime far below exhaustive search.

  • Compared schemes: The comparison includes Exhaustive, GOJRA, IOJRA, and DORA schemes alongside hJTORA.Exhaustive searches all 2^n offloading decisions but is evaluated only in a small network because of its high complexity.
  • Experimental design: The exhaustive-search comparison uses 6 users, 4 cells, and 2 sub-bands per cell with 500 shadowing realizations.Average utilities are reported with 95% confidence intervals for two computation workloads.
  • System utility: hJTORA achieves average system utility within 2% of Exhaustive and gains up to 13%, 17%, and 47% over DORA, GOJRA, and IOJRA, respectively.These results characterize hJTORA against the optimal method and competing baselines.
  • Runtime comparison: Exhaustive takes about 100× longer than hJTORA in the small-network runtime comparison.DORA is slightly faster than hJTORA, while IOJRA and GOJRA have the lowest runtimes.
  • Effect of number of users: Across uniform and non-uniform workload distributions, hJTORA consistently performs best as the number of users varies.The user-count study varies users per cell from 1 to 10 and sets the number of sub-bands equal to users per cell.
  • Workload and contention: System utility increases with workload because tasks requiring more computation resources benefit more from MEC offloading.With enough users, utility decreases because competition raises transmission and MEC execution overheads.

C. Effect of Task Profile

Task profiles and network conditions shape offloading utility and resource costs, while hJTORA remains close to optimal and improves utility over traditional approaches. The approximation is accurate within practical transmit-power limits.

  • C. Effect of Task Profile: Average system utility increases with task workload but decreases with task input size.Tasks with small input sizes and high workloads benefit more from offloading than tasks with large input sizes and low workloads.
  • C. Effect of Task Profile: hJTORA’s performance gains over baselines increase with task workload and decrease with task input size.The relative advantage follows the same task-profile trend as average system utility.
  • D. Effect of Number of Users: When U = 21, users experience larger average time and energy consumption than when U = 14.More users compete for limited resources, lowering the probability that a user benefits from offloading.
  • E. Effect of Inter-cell Interference Approximation: Approximation-based system utility is almost identical to the exact-expression result when maximum transmit power is below 25 dBm.An increasing gap appears above 25 dBm; because LTE specifies a maximum UE transmit power of 23 dBm, the approximation can work well in practical systems.
  • Method and Conclusions: Simulation results show that hJTORA performs closely to the optimal solution and significantly improves average system offloading utility over traditional approaches.The heuristic is described as a low-complexity, suboptimal solution intended to remain practical.
  • Method and Conclusions: The proposed hJTORA strategy decomposes the MINLP into resource allocation and task offloading components, using quasi-convex and convex optimization techniques plus a polynomial-time heuristic.The resource-allocation problem is handled with fixed offloading decisions, while the task-offloading problem optimizes its corresponding optimal-value function.

APPENDIX

The appendix verifies that Γs(pu) is strictly quasi-convex on (0, Pu] by checking differentiability and the required second-order condition.

  • Γs(pu) is twice differentiable on R.
  • The proof checks the second-order condition required for strict quasi-convexity.
  • The first- and second-order derivatives of Γs(pu) are calculated explicitly.
  • Substituting ¯pu into the second-order expression yields s(¯pu) > 0.
  • Therefore, Γs(pu) is strictly quasi-convex in (0, Pu].
Loading 1705.00704v1…