PaperlayerView exact revision on arXiv

Source-linked AI summary

UAV-Assisted Relaying and Edge Computing: Scheduling and Trajectory Optimization

Xiaoyan Hu, Kai-Kit Wong, Kun Yang, Zhongbin Zheng

arXiv:1812.02658v2eess.SP

TL;DR

The paper addresses energy-efficient computation for UEs when direct AP access is impaired and relying only on a resource-limited UAV is risky. It introduces a UAV that both computes and relays, then jointly optimizes scheduling, bandwidth, and trajectory with an alternating algorithm. Simulations report significant performance gains over conventional schemes, with greater advantages for computation-intensive latency-critical tasks.

  • Problem

    The paper studies how to use UAV and AP computing resources together when UEs have degraded AP links and the UAV alone has limited resources for computation-intensive, latency-critical tasks.

  • Method

    An alternating optimization algorithm jointly optimizes computation resource scheduling, bandwidth allocation, and the UAV’s trajectory by iteratively solving decoupled subproblems.

  • Results

    Significant performance improvement and more stable performance are achieved over baseline schemes, with larger advantages for computation-intensive and latency-critical tasks.

  • Takeaways & Limitations

    The architecture combines UAV computing and relaying to exploit computing resources at both the UAV and AP while using the UAV’s energy-efficient LoS transmissions.

Abstract

from arXiv · show

In this paper, we study an unmanned aerial vehicle (UAV)-assisted mobile edge computing (MEC) architecture, in which a UAV roaming around the area may serve as a computing server to help user equipment (UEs) compute their tasks or act as a relay for further offloading their computation tasks to the access point (AP). We aim to minimize the weighted sum energy consumption of the UAV and UEs subject to the task constraints, the information-causality constraints, the bandwidth allocation constraints and the UAV's trajectory constraints. The required optimization is nonconvex, and an alternating optimization algorithm is proposed to jointly optimize the computation resource scheduling, bandwidth allocation, and the UAV's trajectory in an iterative fashion. Numerical results demonstrate that significant performance gain is obtained over conventional methods. Also, the advantages of the proposed algorithm are more prominent when handling computation-intensive latency-critical tasks.

I. INTRODUCTION

The paper proposes a UAV-assisted MEC architecture that combines UAV computing and relaying to use computing resources at both the UAV and AP. It formulates a joint energy-minimization problem and solves its coupled decisions iteratively.

  • Motivation and Prior Works: The architecture lets the UAV serve as a mobile computing server or relay UE tasks to the AP, combining computing resources at both nodes.This design uses the UAV’s energy-efficient LoS transmissions while supporting UEs whose direct AP links may be severely degraded.
  • Our Contributions: The paper minimizes the weighted sum energy consumption of the UAV and UEs under task, information-causality, bandwidth, and trajectory constraints.The optimization jointly covers computation resource scheduling, bandwidth allocation, and UAV trajectory design.
  • Our Contributions: The resulting problem is non-convex because its optimization variables are coupled.The objective also contains nonlinear couplings among task-offloading and bandwidth-related variables.
  • Our Contributions: An alternating optimization algorithm decouples the variables into three subproblems and solves them iteratively.Computation scheduling and bandwidth allocation parameters can be obtained in closed form using Lagrangian methods.
  • Our Contributions: Simulation results show significant performance improvement and more stable adaptation than baseline schemes, especially for computation-intensive, latency-critical tasks.The baselines include preset trajectories, task-offloading-only, equal-bandwidth, and local-computing schemes.

B. Computation Task Model and Execution Methods

The model represents each UE task by input size, computation intensity, output ratio, and latency, then supports local computing, UAV computing, and UAV-relayed AP computing. TDMA, FDD bandwidth separation, buffering, and information-causality constraints organize these operations over time.

  • Task model: Each UE task is characterized by input size I_k, required CPU cycles per input bit C_k, output ratio O_k, and latency limit T_k.The paper sets T_k = T for all UEs and permits bit-wise partial offloading.
  • Local computing: UEs can simultaneously perform local computing and offloading, using DVFS to adjust local CPU frequency and energy consumption.Local computing does not require radio bandwidth.
  • UAV-assisted execution: Remaining input data is first sent to the UAV, where it is either computed or forwarded to the AP for computation.UE offloading uses TDMA, with each UE assigned an equal duration in every slot.
  • UAV execution and delivery: The UAV computes received UE tasks with DVFS and later downloads generated outputs to the corresponding UEs.UAV-computed data produces O_k times the processed input bits as output.
  • Radio and buffering assumptions: Separate FDD bandwidths are allocated for UE reception, AP forwarding, and output downloading under a total-bandwidth constraint.The UAV is assumed to have a sufficiently large data buffer.
  • Causality and timing: Information-causality constraints prevent the UAV from computing, forwarding, or transmitting data before the corresponding data has arrived.Processing delay at the UAV is modeled as one time slot, while AP processing and AP-to-UAV transmission delays are assumed negligible.

C. Problem Formulation

The paper formulates weighted sum energy minimization for the UAV and UEs over task completion, jointly controlling computation, communications, and UAV movement. The formulation includes task, causality, bandwidth, and trajectory constraints.

  • Objective: The objective minimizes the weighted sum energy consumption of the UAV and all UEs over the task completion interval T.The energy model includes offloading, downloading, computation, and UAV propulsion consumption.
  • Decision variables: The optimization jointly selects UE and UAV CPU frequencies, task-bit allocations, communication bandwidths, and the UAV trajectory.These variables cover local computing, UAV computing, forwarding to the AP, and output downloading.
  • Trajectory constraints: The formulation enforces endpoint and maximum-speed constraints on the UAV trajectory.The UAV starts at uI, ends at uF, and its slot-to-slot displacement is bounded by Vmaxτ.
  • Feasibility constraints: The problem includes information-causality, bandwidth-allocation, and task-related constraints alongside the energy objective.These constraints coordinate when data can be processed or transmitted and how communication resources are shared.

III. ALGORITHM DESIGN

The algorithm design addresses a non-convex joint optimization whose variables are strongly coupled through offloading, bandwidth, and UAV position. It alternates among three subproblems and solves their resource components using convex optimization and dual-search procedures.

  • Problem structure: The original problem is non-convex because offloading bits, bandwidth variables, and the UAV trajectory are nonlinearly coupled.This coupling motivates decomposing the optimization into alternating subproblems.
  • Alternating optimization: The three-step algorithm successively optimizes computation scheduling, bandwidth allocation, and UAV trajectory while fixing the other variables.The third step uses the optimized computation and bandwidth variables to design the trajectory.
  • Computation scheduling: With trajectory and bandwidth fixed, the computation-resource scheduling subproblem becomes convex and admits a Lagrange-based optimal solution.The solution covers offloading, downloading, and CPU-frequency variables.
  • Interpretation: Positive task transfers are favored by larger channel-related priority indicators and bandwidths, and by smaller energy-consumption weights.The stated intuition applies to offloading and downloading quantities when they are positive.
  • Scheduling structure: The optimal scheduling structure indicates that offloading decreases while UAV downloading increases over time.This reflects progressively decreasing UE offloading resources and increasing UAV downloading resources across slots.
  • Dual solution: The scheduling solution is obtained through dual variables, using subgradient updates for inequality constraints and bisection searches for equality-constraint multipliers.The optimal dual variables are obtained when the subgradient iterations converge and the bisection searches terminate.

B. Bandwidth Allocation with Fixed UAV Trajectory and Computation Resource Scheduling

With the UAV trajectory and computation schedule fixed, bandwidth allocation is formulated as a convex subproblem and solved through its Lagrangian structure. The resulting allocation uses Lambert W expressions and bisection-based multiplier searches, with exclusive occupation in single-active-transfer cases.

  • Subproblem: The bandwidth-allocation subproblem optimizes bandwidth variables while keeping the UAV trajectory and computation-resource schedule fixed.Its objective and constraints are convex.
  • Closed-form structure: The optimal bandwidth allocation is expressed using the principal branch W0 of the Lambert W function.W0(x) is defined by W0(x)e^W0(x) = x.
  • Exclusive allocation: The entire bandwidth is exclusively occupied when only one of the considered task-transfer quantities is positive for a UE and slot.This result follows from combining the optimal allocation expressions with the total-bandwidth equality constraint.
  • Bisection search: When bandwidth is shared among multiple positive transfers, the relevant dual multiplier can be found by bisection because the allocation expressions vary monotonically with it.Tight search ranges are available from the positive-transfer cases.

C. UAV Trajectory Design With Fixed Computation Resource Scheduling and Bandwidth Allocation

With computation scheduling and bandwidth fixed, the UAV trajectory subproblem is nonconvex because propulsion energy depends nonconvexly on the trajectory. The paper upper-bounds this energy and applies SCA to obtain a convex approximation solved with CVX.

  • The UAV trajectory design problem (P1.3) fixes computation resource scheduling z and bandwidth allocation B at previously optimized values.
  • Propulsion energy Efly^U[n] is not a convex function of the UAV trajectory u.
  • Introducing e_v[n] and v[n] ≥ e_v[n] transforms the speed relation into ∥u[n] − u[n − 1]∥^2 ≥ e_v^2[n]τ^2, which remains nonconvex.
  • SCA linearizes the convex left-hand side around a local point u^i, producing a convex approximation of the additional constraint.
  • The approximated trajectory problem is convex in u and {e_v[n]}, but coupled UAV locations prevent a closed-form solution, so CVX solves it numerically.

D. Algorithm, Convergence and Complexity

Algorithm 1 alternates among computation scheduling, bandwidth allocation, and trajectory optimization, using closed-form or numerical subproblem solutions. Its lower-bounded objective decreases monotonically, guaranteeing convergence, although the nonconvex problem prevents theoretical optimality.

  • Algorithm 1 alternately optimizes computation scheduling z, bandwidth allocation B, and UAV trajectory u to solve the original problem (P1).
  • Step 1 iteratively updates dual variables and obtains computation scheduling through theorem- and lemma-based solutions until convergence.
  • Step 2 uses bi-section search for the bandwidth-related multipliers, while Step 3 solves the SCA-based approximated trajectory problem with CVX.
  • The algorithm evaluates WSEC after each outer iteration and stops when |E^ζ − E^(ζ−1)| < ε for ζ > 2.
  • The lower-bounded objective monotonically decreases under alternating optimization, which guarantees convergence.
  • The proposed method is not theoretically optimal because the original problem is nonconvex, although simulations verify performance gains.
  • The algorithm’s complexity includes subgradient and bisection searches plus CVX solution of the approximated trajectory problem.

IV. SIMULATION RESULTS

The simulations evaluate the proposed algorithm against benchmark schemes while varying AP location, task size, completion time, output-input ratio, UAV energy weight, and iteration count.

  • The simulations compare the proposed algorithm with benchmarking schemes and analyze key system and algorithm parameters.The parameters include AP location, UE task sizes, completion time, output-input data ratio, UAV energy weight, and iteration index.

A. Trajectory of the UAV

UAV trajectories depend strongly on AP location and UE task-size allocation. The trajectory balances proximity to high-task UEs, proximity to the AP, and UAV flying energy to minimize WSEC.

  • The total UE task size is 1400 Mbits in cases (a), (c), (d), and (f), versus 1800 Mbits in cases (b) and (e).
  • Fig. 2 compares UAV trajectories for two AP locations and three UE task-size allocations.The AP positions are v0 = (0, 0) and v0 = (10, 5), while task allocations are [6, 2, 4, 2], [6, 4, 6, 2], and [2, 2, 6, 4] × 10^2 Mbits.
  • When the AP is centered among UEs, the UAV approaches UEs with large tasks for moderate total loads but stays nearer the AP under larger, more evenly distributed loads.
  • Changing the AP location has a more prominent effect on trajectories in this setting, as shown by comparisons between (a)/(d), (b)/(e), and (c)/(f).
  • The trajectory balances UE proximity, which reduces UE offloading and UAV downloading energy, against AP proximity, which reduces UAV offloading energy, while accounting for flying energy.

B. Performance Improvement

The proposed solution consistently reduces WSEC relative to baseline schemes across task size, completion time, output-input ratio, UAV-energy weighting, and operating scenarios. Its advantages are especially pronounced for computation-intensive or latency-critical tasks, while the iterative solution nearly converges after two optimization iterations.

  • Task size: The proposed solution achieves substantial WSEC reductions versus all baselines, with gaps widening as uniform task size increases.Its WSEC is almost one thousandth of Local Computing, less than half of Equal Bandwidth, and almost one quarter lower than Direct Trajectory.
  • Completion time: All schemes consume less WSEC when total completion time increases, while the proposed solution performs best in both scenarios.Its improvement is more prominent under strict time limits, indicating a better energy-delay tradeoff for latency-critical tasks.
  • Output-input ratio: The proposed scheme outperforms the baselines as output-input ratio O varies, whereas Local Computing remains constant and other schemes generally increase with O.The gap over Offloading Only grows with O because partial local computing can save energy when output data is large.
  • UAV-energy weighting: The proposed scheme remains best as UAV-energy weight wU changes, while Direct Trajectory degrades faster because UAV propulsion contributes more without trajectory optimization.Separate UAV energy decreases with wU even as weighted objectives increase, reflecting the weighted-sum optimization.
  • Operating scenarios: The proposed scheme is more stable across AP–UE relative locations, although WSEC is higher when the initial AP location is farther from the UEs.The comparison uses v0 = (0, 0) and v0 = (10, 5).
  • Convergence: The proposed solution almost converges at iteration ζ = 3, after twice optimizing computation scheduling, bandwidth allocation, and trajectory.This behavior holds across different UE task sizes and AP positions.

APPENDIX A: PROOF OF THEOREM 1

Appendix A derives the optimal computation-resource scheduling solution through Lagrangian duality, KKT conditions, monotonicity, and bisection searches. The resulting UE-specific subproblems can be solved in parallel.

  • Dual formulation: The partial Lagrange function and dual formulation convert the computation-scheduling subproblem into a dual optimization framework.The dual variables correspond to the subproblem’s constraints, and optimal dual variables yield the optimal scheduling solution.
  • Problem decomposition: The scheduling problem decomposes into K independent UE-specific subproblems, enabling parallel execution.This decomposition follows from the structure of the Lagrangian and constraints (17h)–(17l).
  • Dual-variable solution: The optimal dual variables are obtained iteratively, with η and ρ derived from λ and µ and β constrained to [0, βk,max).The bound is βk,max = 3Ckwkκk(IkCk/T)^2.
  • Numerical search: Monotonic relationships among η, ρ, and β enable bisection searches to determine the optimal dual variables.The termination condition is formed by combining equations (B.1) and (B.4) for each UE.

APPENDIX C: PROOF OF THEOREM 2

Appendix C derives the optimal bandwidth allocation solution for the offloading subproblem using Lagrangian duality and KKT conditions. The allocation decomposes by UE and admits closed-form expressions involving the Lambert function.

  • Dual formulation: The bandwidth subproblem is formulated through a partial Lagrange function and its associated dual function.The optimal bandwidth allocation is obtained by solving the dualized problem with optimal dual variables.
  • Problem decomposition: The bandwidth optimization decomposes into K UE-specific subproblems, allowing parallel solution of the allocation variables.The decomposition follows from the structure of the dualized problem.
  • Optimality conditions: KKT conditions provide necessary and sufficient conditions for the optimal offloading bandwidth allocation.The derivation uses the equality constraint to identify the optimal allocation.
  • Closed-form solution: The closed-form offloading-bandwidth solution is derived through logarithmic and exponential transformations and the Lambert function.The corresponding UAV-to-UE bandwidth solution has a similar structure.
  • Case integration: The final bandwidth solutions for offloading and UAV transmission are obtained by integrating the relevant cases.The UAV-to-UE solution is derived analogously to the offloading-bandwidth solution.
Loading 1812.02658v2…