PaperlayerView exact revision on arXiv

Source-linked AI summary

Energy Efficient Resource Allocation in UAV-Enabled Mobile Edge Computing Networks

Zhaohui Yang, Cunhua Pan, Kezhi Wang, Mohammad Shikh-Bahaei

arXiv:1902.03158v2cs.IT

TL;DR

The paper addresses sum-power minimization in UAV-enabled MEC under latency and coverage constraints while jointly optimizing association, power, computation capacity, and locations. It proposes an iterative low-complexity solution and reports better sum-power performance than conventional algorithms, especially under demanding conditions.

  • Problem

    The paper formulates sum-power minimization in UAV-enabled MEC by jointly optimizing association, power, computation capacity, and locations under latency and coverage constraints.

  • Method

    The paper proposes an iterative low-complexity algorithm that decomposes the nonconvex problem and uses closed-form allocation, location search, and clustering-based initialization.

  • Results

    The proposed algorithm achieves better sum-power performance than conventional algorithms, especially at low maximal latency, low maximal computation capacity, high task CPU cycles, and high data rate.

  • Takeaways & Limitations

    The algorithm’s reported advantage over conventional approaches is most pronounced under low-latency, low-capacity, high-computation, and high-data-rate conditions.

Abstract

from arXiv · show

In this paper, we consider the sum power minimization problem via jointly optimizing user association, power control, computation capacity allocation and location planning in a mobile edge computing (MEC) network with multiple unmanned aerial vehicles (UAVs). To solve the nonconvex problem, we propose a low-complexity algorithm with solving three subproblems iteratively. For the user association subproblem, the compressive sensing based algorithm is accordingly is proposed. For the computation capacity allocation subproblem, the optimal solution is obtained in closed form. For the location planning subproblem, the optimal solution is effectively obtained via one-dimensional search method. To obtain a feasible solution for this iterative algorithm, a fuzzy c-means clustering based algorithm is proposed. Numerical results show that the proposed algorithm achieves better performance than conventional approaches.

I. INTRODUCTION

The paper formulates sum power minimization in a multiple-UAV MEC network by jointly optimizing association, power, computation capacity, and locations under latency and coverage constraints. It proposes iterative and specialized optimization methods for the resulting nonconvex problem.

  • Problem formulation: The study targets sum power consumption minimization for UEs and UAVs in a UAV-enabled MEC network with multiple UAVs.The formulation includes latency and coverage constraints.
  • Problem formulation: The nonconvex problem jointly optimizes user association, power control, computation capacity allocation, and location planning.The proposed algorithm solves three subproblems iteratively and includes complexity analysis.
  • User association: For user association with ℓ0-norm, a compressive sensing based algorithm provides a closed-form solution in each iteration.This method addresses the user association subproblem.
  • Computation and location optimization: The original computation capacity allocation and location planning problem is decomposed into multiple small optimization problems.This decomposition supports the specialized solutions for both subproblems.
  • Computation and location optimization: The optimal computing capacity allocation is derived in closed form, while optimal location planning is obtained via one-dimensional search.These are the respective solution methods for the two decomposed subproblems.

II. SYSTEM MODEL

The system model describes a multi-UAV MEC network where each UE executes its task locally or offloads it to one UAV. It formulates sum-power minimization while jointly accounting for association, computation, power, UAV placement, beamwidth, altitude, battery, latency, coverage, and capacity constraints.

  • Network and task execution: The network contains N UEs and M UAVs, and each UE task can execute locally or be offloaded to a UAV.The execution-location set is M′ = {0, 1, · · · , M}, where 0 denotes local execution.
  • Network and task execution: Each UE either executes its task locally or uploads it to one unique UAV, subject to the task’s latency requirement T.All tasks are assumed to have the same latency requirement T.
  • Optimization problem: The optimization minimizes the weighted sum power of UEs and UAVs, including transmission, execution, and propulsion power.The decision variables include association A, computation allocation F, transmission power P, and UAV location and beamwidth variables Z.
  • Optimization problem: The formulation enforces UAV battery and computation limits, UE and UAV power limits, latency, coverage, and maximum associated-UE constraints.The model also includes feasible regions for UAV altitude and antenna half-beamwidth.
  • Model distinctions: Unlike well-known MEC formulations, the model supports multiple UAVs with per-UAV battery energy limits and optimizes all UAV beamwidths and altitudes.These are identified as two major differences from prior MEC problems in the literature.

III. PROPOSED ALGORITHM

The proposed algorithm addresses the nonconvex problem with an iterative joint optimization scheme that obtains a suboptimal overall solution while solving each subproblem globally. It first handles discrete user association, then uses optimal UE transmission-power conditions to simplify and decouple computation allocation and location planning.

  • Algorithm overview: The nonconvex objective and discrete constraints make global optimization difficult, motivating an iterative joint optimization algorithm for a suboptimal solution.The algorithm obtains a globally optimal solution for each subproblem.
  • User association: User association is solved first because its decision variables are discrete.The subsequent steps use the obtained user association.
  • Transmission power: Optimal conditions for UE transmission power are derived from the fixed user association, simplifying the original problem.These conditions enable the remaining subproblems to be treated more efficiently.
  • Remaining subproblems: Computation capacity allocation and location planning decouple into multiple small-size problems with closed-form optimal solutions, and complexity is analyzed.The decoupling follows from the optimal UE transmission-power conditions.

A. Optimal User Association

With fixed (F, P, Z), the user-association problem approximates its non-smooth ℓ0-norm objective through iterative weighted ℓ1-norm minimization. The resulting convex formulation is solved by dual decomposition, yielding an algorithm that converges.

  • Compressive-sensing approximation: The non-smooth ℓ0-norm is approximately solved through a sequence of weighted ℓ1-norm minimizations from compressive sensing.The weighted terms are iteratively updated during the approximation.
  • Problem reformulation: After approximating the ℓ0-norm and relaxing integer constraints, Problem (24) with fixed (F, P, Z) is reformulated as Problem (29).An auxiliary vector t supports the Lagrangian dual decomposition used to obtain integer solutions.
  • Dual solution: Problem (29) is convex with respect to (A,t) and can be effectively solved via the dual method.Iteratively optimizing the association variables and updating the Lagrange multipliers obtains the optimal solution with zero duality gap.
  • Algorithm 1: Algorithm 1 solves Problem (24) with fixed (F, P, Z) using compressive sensing and is equivalent to a convergent majorization-minimization algorithm.Its convergence follows by the same method used in [51, Appendix A].

B. Optimal Power Control · C. Optimal Computing Capacity Allocation

With fixed user association, the optimal power control satisfies the relevant constraints with equality, reducing the problem to joint computation-capacity and UAV-location optimization. With fixed association and location, the computing-capacity allocation is formulated as a convex problem and decomposed into UAV-specific subproblems.

  • B. Optimal Power Control: The optimal power-control solution satisfies constraint (24b) with equality for a given user association A.This equality characterizes the optimal power p∗_ij.
  • B. Optimal Power Control: The optimal power p∗_ij depends on computing capacity F and 3D UAV location Z.The solution is substituted into Problem (24) for subsequent optimization.
  • B. Optimal Power Control: After substituting optimal power into Problem (24), the fixed-association problem is solved by optimizing computation capacity and 3D UAV location.The associated-user set for UAV j is N_j = {i ∈ N | a_ij = 1}.
  • C. Optimal Computing Capacity Allocation: Problem (39) is convex because its objective function and all constraints are convex.The convexity argument uses the convexity of g(x) = e^x for x > 0 and of the second and third objective terms.
  • C. Optimal Computing Capacity Allocation: The computing-capacity allocation problem decouples into M UAV-specific subproblems because its objective and constraints decouple.For each UAV j, the allocation is obtained from the corresponding single-UAV problem, with the inverse function of h_ij(f_ij) used in the solution.

D. Optimal Location Planning · E. Iterative Algorithm and Analysis

With fixed association and computation capacity, location planning decomposes into UAV-specific convex subproblems solved through interior-point optimization and one-dimensional beamwidth search. Algorithm 3 iteratively optimizes association, computation capacity, location, and power, with proven convergence and quantified complexity.

  • D. Optimal Location Planning: With optimized association and computation capacity, the location-planning problem decouples into M UAV-specific subproblems.The decoupling follows from the objective function and constraints.
  • D. Optimal Location Planning: For fixed beamwidth θ_j, the three-dimensional location problem is convex and can be solved using an interior-point method.The optimal beamwidth θ_j is then obtained by one-dimensional search with stepsize ξ.
  • E. Iterative Algorithm and Analysis: Algorithm 3 updates user association, computation capacity, location, and power sequentially while fixing the other variables at each subproblem.Power is determined from the current association, computation capacity, and location according to (38).
  • E. Iterative Algorithm and Analysis: Algorithm 3 always converges while iteratively optimizing the three coupled design components and deriving transmission power from them.The convergence guarantee is stated as Theorem 3.
  • E. Iterative Algorithm and Analysis: O(L1L2MN) is the complexity of solving the user-association problem with fixed computation capacity, power, and location.L1 and L2 denote the outer-layer and dual-method iteration counts in Algorithm 1.
  • E. Iterative Algorithm and Analysis: O(MN log2(1/ε1) log2(1/ε2)) is the complexity of solving the computation-capacity allocation problem.The problem decomposes into M subproblems, each solved using bisection-based procedures.
  • E. Iterative Algorithm and Analysis: O(L0L1L2MN + L0M(θmax/ξ)MN log2(1/ε1) log2(1/ε2)) is the total complexity of Algorithm 3.Location planning decomposes into M subproblems, and the fixed-θ_j convex solve has three variables with negligible complexity.

F. Fuzzy C-Means Clustering Based Algorithm for Initial Solution

Because Problem (24) has a nonconvex feasible set and lacks a standard initialization method, the paper proposes an FCM clustering based algorithm to obtain a feasible initial solution. The method jointly addresses user association and UAV 2D location planning, then assigns computing capacity and power control.

  • Motivation and objective: The proposed fuzzy c-means (FCM) clustering based algorithm obtains a feasible solution for nonconvex Problem (24).The paper motivates the method by noting that no standard approach can even obtain an initial feasible solution.
  • Joint association and location planning: All M UAVs are deployed at low altitude and narrow beamwidth, after which their 2D locations are optimized through alternating association and location updates.Shorter UAV–UE distances provide higher channel gains and lower transmission latency.
  • Joint association and location planning: The FCM formulation solves the joint user association and 2D UAV location planning problem by minimizing summed squared UE–UAV distances.This distance objective is regarded as the UEs’ sum transmission power.
  • Feasible initialization: After association and location optimization, the algorithm assigns feasible computing capacities and determines power control for the resulting initial solution.UEs are associated with UAVs according to optimized association values when UE-number and computing-capacity constraints are satisfied.

IV. NUMERICAL RESULTS

Numerical results show that IACL rapidly reduces network sum power and consistently outperforms conventional schemes across latency, computation-capacity, task-size, and data-size settings. IACL approaches exhaustive-search performance with much lower computational complexity.

  • Latency performance: Sum power decreases with maximal latency because relaxed latency constraints allow UEs and UAVs to transmit with lower power.IACL outperforms SCAEAH and ECC, while EXH performs best at higher computational complexity.
  • Algorithm comparison: IACL outperforms SCAEAH and ECC, approaches EXH for long maximal latency, and benefits from jointly optimizing altitude, beamwidth, and computation capacity.The gap between IACL and EXH is small especially for long maximal latency.
  • Computation capacity: Sum power decreases as UAV maximal computation capacity increases because more UEs can offload traffic, reducing local task-computation power.IACL always outperforms SCAEAH, especially at low maximal computation capacity.
  • Task CPU cycles: Sum power increases with the total number of task CPU cycles because higher computation capacity is required to satisfy latency constraints, increasing execution power.IACL performs better than SCAEAH, especially under larger task CPU-cycle requirements.
  • Data size: Sum power increases with data size for all algorithms, but IACL grows more slowly than SCAEAH because optimized altitude and beamwidth limit additional UE transmission power.More data requires additional computation and UE transmission power to satisfy latency constraints.

V. CONCLUSIONS

The paper formulates sum power minimization in UAV-enabled MEC networks and addresses its nonconvexity with an iterative algorithm solving three subproblems. Numerical results show improved sum power consumption over conventional algorithms, while UAVs serving as UEs remain future work.

  • Algorithm: The proposed low-complexity algorithm iteratively solves user association, computation capacity allocation, and location planning subproblems.It addresses the nonconvex sum power minimization problem in an UAV-enabled MEC network.
  • Algorithm: User association with ℓ0-norm uses compressive sensing, computation capacity allocation uses decoupled convex problems with closed-form solutions, and location planning uses one-dimensional search.The search obtains the optimal 3D location and beamwidth.
  • Numerical results: The proposed algorithm achieves better sum power consumption performance than conventional algorithms, especially under low maximal latency, low maximal computation capacity, high CPU cycles, and high data rate.The cited comparison concerns sum power consumption across these operating conditions.
  • Future work: The optimization problem for UAV-enabled MEC networks in which UAVs serve as UEs is left for future work.This identifies the paper’s stated limitation and future research direction.

APPENDIX A PROOF OF THEOREM 1 · APPENDIX B PROOF OF LEMMA 1 · APPENDIX C PROOF OF THEOREM 2

The appendices establish closed-form or uniquely computable solutions for association, computation allocation, transmit power, and capacity-related KKT variables. The proofs rely on objective monotonicity, convexity, and bisection-based uniqueness arguments.

  • APPENDIX A PROOF OF THEOREM 1: For each user, assigning association to the UAV with the smallest h_ij minimizes the linear objective, yielding solution (30).
  • APPENDIX A PROOF OF THEOREM 1: The convex computation-capacity subproblem is solved by setting the objective derivative to zero and applying its constraints, yielding solution (31).
  • APPENDIX B PROOF OF LEMMA 1: Because the objective increases with p_ij, the optimal transmit power p*_ij for fixed association A is given by (38).
  • APPENDIX C PROOF OF THEOREM 2: The proof of Theorem 2 formulates the Lagrangian and KKT conditions for Problem (42), using h_ij(f_ij) defined in (44).
  • APPENDIX C PROOF OF THEOREM 2: Since h_ij(f_ij) is monotonic, the relevant equation has a unique positive τ_j obtainable by bisection, after which optimal f_ij follows from (43).
  • APPENDIX C PROOF OF THEOREM 2: The positive-solution requirement for τ_j is explicitly imposed to ensure equation (45) has one positive solution.
  • APPENDIX C PROOF OF THEOREM 2: Substitution produces equation (47); its left term decreases monotonically with ν_j, so ν_j is uniquely obtained through bisection.

APPENDIX D PROOF OF LEMMA 2 · APPENDIX E PROOF OF THEOREM 3

Appendix D establishes that Problem (49) is convex, while Appendix E proves that the iterative updates make sum power nonincreasing and ensure Algorithm 3 converges.

  • APPENDIX D PROOF OF LEMMA 2: The function ζ(Xj, Yj) and constraints (49b) are convex, supporting the convexity of Problem (49).The objective function (49a) and constraints (48b) are also convex.
  • APPENDIX E PROOF OF THEOREM 3: Theorem 3 is proved by showing that sum power (24a) is nondecreasing when sequence (x, d, p) is updated.This follows the IULP algorithm’s update sequence.
  • APPENDIX E PROOF OF THEOREM 3: Inequality (a) follows because A(t) is a suboptimal user association for Problem (24) with fixed computing capacity, power, and location.The fixed values are F (t−1), P (t−1), and Z (t−1).
  • APPENDIX E PROOF OF THEOREM 3: Inequality (b) follows because F (t) is the optimal computing capacity for Problem (24) with fixed user association A(t) and location Z (t−1).The update optimizes computing capacity while holding the other specified variables fixed.
  • APPENDIX E PROOF OF THEOREM 3: Inequality (c) follows because Z (t) is the optimal location for Problem (24) with fixed user association A(t) and computing capacity F (t).The resulting optimal power function is P ∗(F ,Z).
Loading 1902.03158v2…