PaperlayerView exact revision on arXiv

Source-linked AI summary

Joint Task Assignment and Resource Allocation for D2D-Enabled Mobile-Edge Computing

Hong Xing, Liang Liu, Jie Xu, Arumugam Nallanathan

arXiv:1902.10017v1cs.IT

TL;DR

The paper asks how a local user can minimize latency when assigning tasks among multiple D2D helpers while jointly managing wireless and computation resources under TDMA. It develops a convex-relaxation-based algorithm for the resulting MINLP, compares it with fixed-frequency and greedy benchmarks, and reports that the proposed scheme outperforms the alternatives in the reported evaluations. The study remains bounded by assumptions identified for future work.

  • Problem

    The paper addresses latency minimization for task assignment and joint wireless/computation-resource allocation in a TDMA-based, D2D-enabled multi-helper MEC system.

  • Method

    The method relaxes the MINLP into a convex problem, constructs a suboptimal task assignment, and compares it with fixed-frequency and greedy-assignment schemes.

  • Results

    The proposed optimal scheme outperforms the other evaluated schemes, while the fixed-frequency and greedy schemes provide comparison points with lower implementation complexity.

  • Takeaways & Limitations

    Joint task assignment and wireless-resource allocation with controllable computation frequencies can be used to reduce latency in the studied D2D-enabled MEC setting.

  • Takeaways & Limitations

    The paper assumes all tasks cannot be further partitioned and identifies additional challenging issues for future work.

Abstract

from arXiv · show

With the proliferation of computation-extensive and latency-critical applications in the 5G and beyond networks, mobile-edge computing (MEC) or fog computing, which provides cloud-like computation and/or storage capabilities at the network edge, is envisioned to reduce computation latency as well as to conserve energy for wireless devices (WDs). This paper studies a novel device-to-device (D2D)-enabled multi-helper MEC system, in which a local user solicits its nearby WDs serving as helpers for cooperative computation. We assume a time division multiple access (TDMA) transmission protocol, under which the local user offloads the tasks to multiple helpers and downloads the results from them over orthogonal pre-scheduled time slots. Under this setup, we minimize the computation latency by optimizing the local user's task assignment jointly with the time and rate for task offloading and results downloading, as well as the computation frequency for task execution, subject to individual energy and computation capacity constraints at the local user and the helpers. However, the formulated problem is a mixed-integer non-linear program (MINLP) that is difficult to solve. To tackle this challenge, we propose an efficient algorithm by first relaxing the original problem into a convex one, and then constructing a suboptimal task assignment solution based on the obtained optimal one. Next, we consider a benchmark scheme that endows the WDs with their maximum computation capacities. To further reduce the implementation complexity, we also develop a heuristic scheme based on the greedy task assignment. Finally, numerical results validate the effectiveness of our proposed algorithm, as compared against the heuristic scheme and other benchmark ones without either joint optimization of radio and computation resources or task assignment design.

I. INTRODUCTION

The paper studies D2D-enabled multi-helper MEC, where a local user assigns independent tasks to nearby WDs and jointly allocates wireless and computation resources under TDMA. It addresses the resulting MINLP through convex relaxation and task-assignment construction, alongside benchmark and greedy schemes.

  • System motivation: Joint radio and computation-resource optimization is motivated by latency-critical applications and heterogeneous WD capabilities.The paper identifies transmission and computation resources as jointly relevant to energy consumption and computing latency.
  • Research gap: Prior multi-server task-assignment studies often fixed or estimated communication conditions and computation capacities, limiting dynamic resource management.The paper specifically highlights transmitting power, bandwidth, and computation frequency as resources whose dynamic management may improve performance.
  • System motivation: D2D-enabled multi-helper MEC lets a local user offload independent tasks to nearby WDs acting as helpers through direct D2D links.The helpers can include smart wearables, cellphones, tablets, and laptops.
  • System model: Under TDMA, tasks are assigned to helpers, offloaded, executed, and downloaded over orthogonal pre-scheduled slots while satisfying energy and computation-capacity constraints.Tasks are assumed nonpartitionable, and the objective is overall latency minimization.
  • Contributions: The paper jointly optimizes task assignment, offloading and downloading time/rates, execution time, and computation frequency, despite the formulation being an MINLP.Its claimed setting combines binary task offloading with wireless-resource allocation for multiple tasks in a single-user multi-helper MEC system.
  • Contributions: The proposed approach relaxes the difficult problem into an equivalent tractable form and constructs a task-assignment solution, complemented by fixed-frequency and greedy-assignment schemes.The fixed-frequency scheme serves as a benchmark, while the greedy scheme targets lower implementation complexity.

II. SYSTEM MODEL

The system models one local user with nearby helper WDs that cooperatively execute independent tasks through binary task assignment. Tasks may be computed locally or offloaded to one helper, under constraints including at least one assigned task per WD and no inter-helper task dependencies.

  • The MEC system contains one local user and K nearby single-antenna helper WDs.
  • The local user has L independent tasks, each of which is computed locally or offloaded to one of K helpers.Task input/output lengths are represented by T_l/R_l.
  • The model excludes interdependency among tasks and helper-to-helper data transmission because assignment over scheduled TDMA slots is already demanding to solve.
  • The binary assignment matrix π specifies whether task l is assigned to WD k, while L(k) collects tasks assigned to WD k.
  • Every WD, including the local user, is assigned at least one task, requiring L ≥ K + 1.
  • Each task requires C_l CPU cycles, and WD k executes at frequency f_k measured in cycles per second.

A. Local Computing

Local and remote computation are integrated with a three-phase TDMA protocol: tasks are assigned, offloaded, executed, and returned under energy and frequency constraints. The model uses fixed helper order and optimizes communication and computation quantities subject to these constraints.

  • Local Computing: Local tasks are executed at a local computation frequency constrained by the local user's maximum frequency and energy budget.The local computation energy depends on the effective capacitance coefficient κ_0.
  • TDMA Protocol: The protocol has task offloading, task execution, and results downloading phases using pre-scheduled TDMA slots.
  • TDMA Protocol: The local user offloads tasks to helpers in fixed order 1, 2, ..., K, and results return in the same order.The fixed order avoids frequent TDMA scheduling changes and their signaling overhead.
  • TDMA Protocol: Only one helper receives during each offloading slot and only one helper transmits during each downloading slot.
  • Phase I: Task Offloading: The achievable offloading rate depends on bandwidth, transmit power, channel gain, and AWGN power, determining each helper's offloading time.
  • Phase II: Task Execution: Each helper executes its assigned tasks at a computation frequency bounded by its maximum frequency and consumes computation energy determined by its capacitance constant.

3) Phase III: Results Downloading

Phase III models helpers transmitting computed results back to the local user through fixed-order TDMA slots. The resulting downloading delays contribute to total latency, which is minimized jointly with task assignment and resource variables under energy and computation constraints.

  • Results downloading: Helpers transmit their respective computation results to the local user over fixed-order TDMA slots.The helpers transmit in the fixed order 1,...,K after computing assigned tasks.
  • Results downloading: The downloading rate from helper k depends on its channel power gain and transmission power, with corresponding downloading time determined from the rate.The local-user noise power and helper-to-user channel gain enter the achievable downloading rate.
  • Scheduling dependencies: Helper k can transmit only after its computation finishes and preceding TDMA transmissions complete, creating waiting times for scheduled results.Helper 1 additionally waits for all task offloading to finish before results downloading begins.
  • Latency objective: Total latency combines local computation completion with the completion time for downloading all remote results.The objective is to minimize total latency for executing all L tasks while optimizing assignment, offloading time, and downloading time.
  • Constraints: The optimization enforces individual energy budgets, computation-frequency limits, unique task assignment, nonempty assignments, and binary offloading decisions.These constraints apply to the local user and helpers and include the energy and computation-capacity requirements.

B. Suboptimal Design

The reformulated problem is an MINLP that is generally NP-hard, so the paper develops two suboptimal approaches. One relaxes binary assignment variables and solves a convex problem before recovering an assignment; the other decouples assignment from wireless allocation using a greedy heuristic.

  • Problem complexity: The transformed problem is an MINLP with integer constraints and is generally NP-hard.Exhaustive search is computationally too expensive for practical implementation.
  • Relaxation-based approach: The first approach relaxes binary task-assignment variables into continuous ones and solves the resulting convex problem.The relaxed problem is convex because the relevant energy expressions are obtained through convex operations.
  • Greedy heuristic: The second approach decouples task assignment from wireless resource allocation through a greedy task-assignment heuristic.With assignment fixed, the remaining resource-allocation problem is convex.
  • Benchmark scheme: A benchmark fixes every helper's computation frequency at its maximum, eliminating computation allocation.This special case is presented as a benchmark scheme.
  • Relaxation-based approach: The relaxed solution is used to construct a suboptimal binary task assignment satisfying the assignment constraints.The continuous assignment variables are rounded into binary values, after which wireless resource allocation is handled for the resulting assignment.

A. Dual-Optimal Solution to (P1)

The paper solves the convex relaxation through Lagrangian dual decomposition. Given dual variables, the problem separates into independent helper and local-user subproblems whose solutions determine rates, computation frequencies, and assignment decisions.

  • Subproblem structure: Given dual variables, the optimization decomposes into K+1 independent subproblems that can be solved in parallel.There is one subproblem for each helper and one for the local user.
  • Optimal solutions: Proposition 4.1 gives the optimal task assignment and associated rate and computation-frequency solutions for fixed dual variables.The assignment variables are obtained through a related linear-programming problem.
  • Interpretation: Better offloading or downloading channel gains produce larger optimal rates through the non-decreasing Lambert W function.The optimal rates are interpreted as offloading and results-downloading rates for each helper.
  • Interpretation: A larger local-user energy multiplier reduces optimal offloading and lengthens local computation time, thereby reducing local-user energy consumption.This behavior occurs when the local user's total-energy constraint is violated.
  • Dual decomposition: Lagrangian dual decomposition is used to solve the convex problem and obtain optimal rate and computation-frequency allocations.The method updates dual variables with a subgradient-based procedure until a prescribed accuracy threshold is reached.

B. Primal-Optimal Solution to (P1)

After solving the dual problem, the paper recovers a primal-optimal solution for the convex relaxation and then constructs a feasible binary assignment. The resulting suboptimal algorithm modifies the assignment, resolves resource allocation, and outputs a solution to the reformulated problem.

  • Primal recovery: The primal-optimal solution is recovered from the dual-optimal variables and then used to solve a linear program for the assignment.The resulting LP is solved with a standard algorithm such as the simplex method.
  • Proposed scheme: The proposed scheme jointly optimizes task assignment and wireless resource allocation through the resulting feasible assignment.After assignment modification, the remaining problem is solved by Lagrangian dual decomposition.
  • Assignment construction: Continuous assignment values are rounded by assigning each task to the worker with the largest relaxed assignment value.The assignment is further adjusted so every helper receives at least one task.
  • Algorithm 1: Algorithm 1 solves the dual problem, retrieves the primal assignment, modifies it, and then solves the remaining resource-allocation problem.Its output is a solution to the transformed problem, including time and power allocation.
  • Complexity: The algorithm's complexity is dominated by solving the convex relaxation through ellipsoid-method iterations and simplex-based linear programs.The paper estimates complexity using the ellipsoid method's worst-case iterations and the simplex algorithm's expected complexity.

V. LOW-COMPLEXITY BENCHMARK SCHEMES

This section develops two lower-complexity alternatives to the joint optimization: a fixed-frequency benchmark and a greedy task-assignment heuristic.

  • Fixed-frequency benchmark: The fixed-frequency benchmark assigns helpers their maximum computation frequencies, simplifying the joint resource-allocation problem.With computation frequencies fixed, the scheme becomes a special case in which the relevant frequency constraints are active.
  • Fixed-frequency benchmark: The fixed-frequency formulation can become infeasible under restrictive energy budgets, even though its simplified solution has lower complexity.Its approximate complexity is O(2(2K + γH/ǫ)P(L(K + 1))).
  • Greedy task assignment: The greedy heuristic constructs task assignments incrementally by selecting the helper that causes the smallest increase in the resource-allocation cost.It applies two task-selection criteria, compares their resulting total latencies, and retains the lower-latency assignment.
  • Greedy task assignment: For the first K tasks, the heuristic assigns each task to the currently unoccupied helper with the best channel condition, which minimizes transmission energy.The task with the longest input/output data flow is executed locally to save data-transmission time.
  • Complexity: The greedy algorithm has lower worst-case complexity than the proposed convex-relaxation algorithm when 2(L − K − 1)(K + 1) < P(L(K + 1)).The paper states that this condition is easily satisfied in most cases.

VI. NUMERICAL RESULTS

The numerical study evaluates joint optimization against fixed-frequency, greedy-assignment, random-assignment, local-execution, and optimal benchmarks under simulated D2D channel conditions.

  • Evaluation setup: The simulations compare joint optimization with fixed-frequency, greedy-assignment, random-assignment, local-execution, and optimal schemes.The optimal MINLP solution is obtained by exhaustive search over feasible task assignments.
  • Evaluation setup: The optimal benchmark has exponential complexity and is therefore too costly for practical implementation.It is provided for only one numerical example.
  • Simulation parameters: The simulated helpers are uniformly distributed between 0 and 500 m from the local user, with pathloss and Rayleigh fading in the channel model.The reported latency is averaged over 300 channel realizations.
  • Simulation parameters: The default task parameters use input and output sizes uniformly distributed over [0, 10^4] bits and computation requirements over [0, 5×10^6] cycles.The default energy constraints are E0 = −30 dB for the local user and Ek = −20 dB for every helper.

A. The Effect of Wireless Resource on the Total Latency

The numerical results examine how energy budgets, helper computation frequency, data size, computation load, and task count affect total latency across competing schemes.

  • Wireless-resource effects: Average latency decreases as the local-user energy budget increases, with the sharpest reduction when E0 is below about −34 dB.Beyond −34 dB, the decrease becomes slight because the bottleneck mainly lies in the helpers’ energy constraints.
  • Wireless-resource effects: When helper energy is scarce, joint optimization and greedy assignment substantially outperform fixed frequency, while local execution becomes preferable below roughly −38 dB helper energy.The joint optimization achieves the second-lowest total latency with little gap to the optimal solution.
  • Wireless-resource effects: As helper maximum computation frequency increases, joint optimization suppresses helper frequencies below their limits to preserve energy for result downloading.When the maximum frequency is below about 1.32 GHz, joint optimization is nearly equivalent to fixed frequency and outperforms greedy assignment.
  • Computation-load effects: Effective task assignment becomes increasingly important as input and output data lengths grow, while local execution becomes favorable beyond about 5.5 × 10^3 bits under limited helper energy.With helper energy increased to 0 dB, all offloading schemes considerably outperform local execution.
  • Computation-load effects: As the number of tasks increases, joint optimization, greedy assignment, and fixed frequency rise steadily in average latency, while local execution grows faster.Greedy assignment balances performance and complexity, whereas random assignment is nearly the worst-performing scheme.

VII. CONCLUDING REMARKS

The paper jointly optimizes task assignment, communication, and computation resources in a D2D multi-helper MEC system, using convex relaxation and lower-complexity alternatives. Numerical results support the proposed design, while the authors identify mobility, multiple-access, cooperation, and multi-user extensions as open issues.

  • Contributions: Numerical results verify that the proposed design reduces the local user’s computation latency through D2D collaboration.The conclusion describes it as an effective solution for the considered system.
  • Contributions: The proposed algorithm relaxes the MINLP into a convex problem and constructs a suboptimal task assignment from the relaxed optimum.Fixed-frequency and greedy task-assignment schemes provide lower-complexity alternatives.
  • Limitations and future work: The model assumes fixed WD locations and static wireless channels, so mobility-induced channel fluctuations and dropped D2D links remain outside its scope.The authors identify online algorithms with long-term objectives as a direction for addressing mobility.
  • Limitations and future work: The TDMA assumption leaves OFDMA subcarrier allocation and NOMA joint message decoding as challenging extensions.These alternatives would add resource-allocation and decoding challenges to the mixed-integer task-assignment problem.
  • Limitations and future work: The framework assumes helpers agree to cooperate and considers one local user, leaving incentive mechanisms and multi-user scheduling for future work.The paper identifies multi-user, multi-helper scheduling as an extension of the current model.

APPENDIX A

Appendix A proves intermediate results using monotonicity arguments, case analysis, substitutions, and optimality conditions. It also reduces a subproblem to a linear program solved by the simplex method and states conditions preventing infeasibility.

  • The proof establishes monotonicity by evaluating a first-order partial derivative and using (1 − x)e^x − 1 < 0 for x > 0.
  • Case analysis shows that helper downloading can be slowed while preserving I_k and reducing the preceding helper's transmitting energy.
  • Several substitutions and recursive relations simplify helper waiting times, completion time, and total latency expressions.
  • Given dual variables, the subproblems are solved, and minimization over the primal variables is formulated as LP1 and solved using the simplex method.
  • KKT conditions imply the stated optimal solutions, while feasibility requires D_k > 0, A_k > 0, B_k > 0, and β_0 − ζ_0 > 0.
Loading 1902.10017v1…