Source-linked AI summary
Distributionally Robust Optimization for Aerial Multi-access Edge Computing via Cooperation of UAVs and HAPs
Ziye Jia, Can Cui, Chao Dong, Qihui Wu, Zhuang Ling, Dusit Niyato, Zhu Han
TL;DR
The paper tackles energy-efficient aerial MEC under imperfect CSI, heterogeneous latency demands, and limited UAV resources. It combines hierarchical UAV–HAP service, weighted deployment, DRO/CVaR reformulation, decomposition, and BWOA, with simulations reporting robust and near-optimal solutions at lower complexity.
Problem
Imperfect CSI, heterogeneous latency demands, limited aerial resources, and UAV–HAP coordination make energy-efficient aerial MEC optimization difficult.
Method
The paper combines weighted K-means UAV deployment with DRO/CVaR reformulation, primal decomposition, and BWOA for binary offloading optimization.
Results
Simulations report robust and efficient proposed schemes, including near-optimal BWOA solutions with lower time complexity and lower energy use than random deployment and connection.
Takeaways & Limitations
The proposed UAV–HAP framework supports robust aerial MEC resource allocation under CSI estimation errors while improving deployment and offloading efficiency.
Abstract
from arXiv · showhide
With an extensive increment of computation demands, the aerial multi-access edge computing (MEC), mainly based on unmanned aerial vehicles (UAVs) and high altitude platforms (HAPs), plays significant roles in future network scenarios. In detail, UAVs can be flexibly deployed, while HAPs are characterized with large capacity and stability. Hence, in this paper, we provide a hierarchical model composed of an HAP and multi-UAVs, to provide aerial MEC services. Moreover, considering the errors of channel state information from unpredictable environmental conditions, we formulate the problem to minimize the total energy cost with the chance constraint, which is a mixed-integer nonlinear problem with uncertain parameters and intractable to solve. To tackle this issue, we optimize the UAV deployment via the weighted K-means algorithm. Then, the chance constraint is reformulated via the distributionally robust optimization (DRO). Furthermore, based on the conditional value-at-risk mechanism, we transform the DRO problem into a mixed-integer second order cone programming, which is further decomposed into two subproblems via the primal decomposition. Moreover, to alleviate the complexity of the binary subproblem, we design a binary whale optimization algorithm. Finally, we conduct extensive simulations to verify the effectiveness and robustness of the proposed schemes by comparing with baseline mechanisms.
I. INTRODUCTION
The paper addresses aerial MEC challenges from heterogeneous task QoS demands, limited aerial resources, UAV–HAP coordination, and imperfect CSI. It proposes a hierarchical UAV–HAP framework and optimization methods for deployment, robust latency constraints, offloading, and resource allocation.
- Motivation: Heterogeneous QoS demands, limited communication, computing, and energy resources, and imperfect CSI complicate reliable aerial MEC resource allocation.The paper identifies UAV–HAP cooperation as an additional challenge for efficient offloading and resource optimization.
- Problem formulation: The optimization minimizes total energy consumption over UAV positions, user–UAV connections, offloading strategies, and resource allocation under latency and multi-resource constraints.The formulated problem is a mixed-integer nonlinear program with uncertain parameters and chance constraints for task latency.
- System model: The hierarchical model uses flexibly deployed UAVs and an HAP providing stable, strong computing services for remote ground users.Each ground user connects to one UAV, while tasks that exceed UAV capacity or delay limits can be forwarded to the HAP.
- Proposed methods: Weighted K-means deployment incorporates task importance into UAV placement, while DRO and CVaR reformulate the chance constraint as a mixed-integer second-order cone program.The weighted deployment method addresses multi-UAV placement before solving the robust optimization problem.
- Proposed methods: Primal decomposition separates the reformulated problem into resource-allocation and binary offloading subproblems, with CVX solving the convex part and BWOA reducing binary-search complexity.BWOA uses a penalty mechanism to handle infeasible candidate solutions in the constrained binary problem.
- Evaluation: Simulations report robustness to CSI estimation errors, lower energy use and better resource utilization than random deployment and connection, and near-optimal BWOA performance with lower time complexity.The reported comparisons include exhaustive search, greedy offloading, simulated annealing, and random deployment and connection.
B. Communication Model
The communication model describes imperfect GU-to-UAV channel knowledge using CSI errors and an uncertainty set, while modeling simultaneous uplinks with OFDMA. It contrasts this uncertain G2U link with a more stable UAV-to-HAP link.
- The G2U channel is modeled as large-scale fading and can be regarded as a line-of-sight channel.
- Environmental obstacles, terrain, and electromagnetic interference make the actual G2U channel differ from its ideal estimate.
- The CSI error is treated as unmeasurable, with historical statistical data supplying moment information for an uncertainty set of possible distributions.
- OFDMA enables ground users to transmit simultaneously while ignoring mutual interference in the communication model.
- The G2U uplink rate follows the Shannon formula, and its transmission delay is then calculated from that rate.
- The U2H link is assumed to be estimated precisely because it has fewer obstacle and environmental reflection disturbances than the G2U link.
2) U2H Channel Model:
The U2H communication model characterizes UAV-to-HAP transmission using free-space loss and rain attenuation, then incorporates transmission latency and energy into task processing. It also defines computation-resource variables and UAV CPU limits.
- U2H Channel Model: The U2H rate model accounts for free-space path loss, total line loss, system noise temperature, bandwidth, and center frequency.
- U2H Channel Model: Transmission latency and energy consumption are calculated for tasks sent from UAVs to the HAP.
- U2H Channel Model: Backhaul delay is ignored because backhaul data is much smaller than uplink data.
- Computation Model: Task computation uses CPU frequency f_m, data size L_m, and required CPU cycles c_m per bit.
- Computation Model: The model includes task energy consumption and constrains each UAV MEC server's CPU frequency by its maximum CPU cycle frequency.
- Computation Model: A binary variable is introduced for the task-computing decisions in the model.
2) HAP-based Computing Model:
The formulation models HAP-assisted computing alongside UAV resources and imposes latency, energy, flow, deployment, and mixed-integer constraints. Because the problem contains uncertain parameters and exponential complexity, it is difficult to solve directly.
- HAP-based Computing Model: The HAP supplements resource-limited UAVs by providing computing capacity, with task computing delay and energy consumption modeled explicitly.
- HAP-based Computing Model: Total task delay combines transmission and computation components across the aerial MEC system.
- Energy Model: After deployment, UAV energy is consumed by transmission and computation because hovering energy is constant.
- Energy Model: The HAP's remaining energy consumption is attributed to computation because it hovers at a quasi-position.
- Problem Formulation: The chance-constrained problem minimizes total aerial-platform energy under UAV deployment, task offloading, and resource limitations.
- Problem Formulation: The chance constraint requires each task's total latency to stay within its maximum delay with a specified probability under uncertain CSI errors.
- Problem Formulation: The resulting MINLP contains random parameters, binary decisions, continuous variables, and exponential time complexity as problem size grows.
IV. ALGORITHM DESIGN
The algorithm design separates UAV deployment from computation offloading. It uses weighted K-means for low-complexity deployment, then applies a CVaR-based reformulation and decomposition, with BWOA addressing integer offloading decisions.
- Algorithm Overview: The solution process is divided into UAV deployment and computation-offloading phases.
- UAV Deployment: The WKD algorithm determines UAV positions and GU-UAV connections with low time complexity before offloading optimization.
- Computation Offloading: After deployment, the CVaR mechanism conservatively reformulates the chance-constrained problem, while primal decomposition separates resource allocation from integer offloading.
- Computation Offloading: BWOA is designed to reduce the complexity of the binary offloading subproblem.
- UAV Deployment: UAVs are deployed near GU clusters, with task characteristics and load influencing weighted positions to reduce transmission delay and satisfy QoS.
- UAV Deployment: WKD repeatedly assigns GUs to nearest clusters and updates UAV positions toward weighted cluster centers until convergence.
- UAV Deployment: The deployment algorithm has time complexity O(MNImax_1) and outputs UAV locations together with GU-UAV connections.
B. CVaR-based Mechanism for Chance Constraint
The paper uses DRO and CVaR to conservatively reformulate the latency chance constraint under uncertain CSI-error distributions, yielding an MISOCP representation. A first-order latency approximation and moment-based uncertainty information support a tractable robust formulation.
- DRO reformulation: DRO replaces the chance constraint with a distributionally robust chance constraint over an uncertainty set without distribution information.The uncertainty set represents possible CSI-error distributions, while the resulting formulation seeks a worst-case solution.
- CVaR approximation: CVaR provides a conservative approximation of the distributionally robust chance constraint for resource allocation and offloading decisions.The paper describes CVaR as the conditional expectation of losses exceeding a probability level and uses it to improve reliability while reducing energy consumption.
- MISOCP transformation: The worst-case CVaR formulation is converted into a second-order cone program using auxiliary variables and the mean and standard deviation of the CSI-error parameter.The resulting constraints include auxiliary variables such as η, e, q, z, and s, with μ and σ representing the random parameter's moments.
- Latency approximation: A first-order Taylor expansion approximates latency because the CSI estimation error is assumed much smaller than the theoretical channel gain.This approximation is used before reformulating the robust chance constraint into the MISOCP.
- Robustness and complexity: The resulting MISOCP solution is conservative under the worst-case distribution and is intended to enhance robustness against CSI-error fluctuations.The formulation remains a mixed-integer problem involving binary and continuous variables.
C. Primal Decomposition for P2
Primal decomposition separates the reformulated problem into a convex resource-allocation subproblem and a binary offloading subproblem. The two subproblems are solved iteratively, with the convex component handled by a standard optimization toolkit.
- Resource allocation subproblem: Fixing the binary offloading variable λ yields a resource-allocation subproblem over f, β, e, q, z, and s.This subproblem retains the relevant convex constraints, including the MISOCP constraint.
- Resource allocation subproblem: The resource-allocation subproblem is formulated as an SOCP and can be solved using a convex optimization toolkit such as CVX.
- Offloading subproblem: With resource variables fixed, the offloading decision subproblem depends only on the binary variable λ.Its constraints include the binary offloading and system constraints inherited from the reformulated problem.
- Iterative decomposition: The decomposed problem is handled by iteratively solving the resource-allocation and offloading subproblems, but the binary subproblem remains intractable to solve directly.The difficulty arises from the binary variables in the offloading decision problem.
D. BWOA for P4
The paper applies a binary whale optimization algorithm to the offloading subproblem, replacing exponentially complex exhaustive search with a penalty-based meta-heuristic search for feasible quasi-optimal solutions.
- Motivation: Exhaustive search can obtain the optimal offloading solution, but its complexity grows exponentially with problem scale.
- Penalty-based formulation: BWOA represents candidate binary offloading solutions as search agents and evaluates them through a penalized fitness function Γ(λ).The penalty function combines the original objective with penalties for constraint violations.
- Penalty-based formulation: Constraint-violating agents receive higher fitness values through an index-based penalty mechanism, discouraging infeasible solutions during exploration.The penalty factor is set to 10^5, and the index function activates when a constraint is violated.
- Binary whale optimization: BWOA updates agents iteratively using whale-inspired exploration and exploitation behaviors while retaining the best observed binary offloading solution.Agent quality is evaluated with Γ(λ), and the best position is updated across iterations.
1) Encircling Prey:
The BWOA update process alternates between spiral movement and encircling or exploratory updates, using probability-controlled binary position changes until the iteration limit is reached.
- Initialization: The algorithm initializes a population of K agents, evaluates their fitness, and records the best search agent before iterative updates.
- Update selection: Each iteration updates the coefficients A, C, and a, then selects an update strategy using a random probability.The algorithm branches on a randomly generated parameter before updating agent positions.
- Encircling and exploration: The alternative branch uses either a random-agent exploration update or an optimal-agent encircling update depending on the magnitude of A.The condition |A| ≥ 1 selects random-agent exploration; otherwise the agent follows the current optimum.
- Termination: The algorithm repeatedly evaluates Γ and updates the best agent until i2 exceeds Imax2, then outputs the best fitness and offloading decision.
2) Spiral Updating:
The spiral updating procedure uses step-size and position-update rules, while search for prey adds random exploration to reduce local-optimum risk in BWOA. Algorithm 2 initializes agents and iteratively updates parameters, fitness, and agent positions using probabilistic strategies.
- 2) Spiral Updating:: The step size Äsu is calculated using updated vectors A and D′ within the spiral updating procedure.
- 2) Spiral Updating:: Search for prey lets some agents perform random searches instead of moving toward the current optimum, enhancing global search capacity.
- 2) Spiral Updating:: The search-for-prey position update compares PBWOA with Äsp and either retains the current position or applies the calculated update.
- 2) Spiral Updating:: The random-search rule uses Xrand, defined as the position of a randomly selected agent.
- 2) Spiral Updating:: Algorithm 2 initializes K agents randomly, evaluates Γ(λ), updates a, A, and C each iteration, and applies probabilistic position-update strategies.
4) Algorithm Design:
The proposed algorithms optimize UAV deployment, offloading, and energy use under imperfect CSI, while simulations assess performance across network scales, UAV deployments, resource loads, and CSI conditions.
- Deployment optimization: The WKD algorithm deploys UAVs at the centers of GU clusters.In the illustrated setting, 30 GUs and 6 UAVs are distributed across a 1km×1km area.
- Offloading optimization: BWOA achieves near-optimal performance with lower time complexity than exhaustive search, greedy offloading, and SAA as network scale increases.The optimal solution uses exhaustive search, whose time cost becomes unacceptable in large-scale situations.
- Resource scalability: Increasing UAV count can improve the number of served GUs when limited resources or QoS constraints leave users unserved.With the same number of served GUs, energy consumption is almost unchanged when the UAV count simply increases.
- Deployment optimization: WKD consumes less energy than random deployment and random GU-UAV connections for the same number of served GUs.Compared with R&R, WKD also increases the number of GUs accommodated and avoids UAV overloading or underutilization.
- Robustness evaluation: CSI estimation errors increase energy consumption relative to ideal CSI conditions because MEC servers allocate more computing resources.This comparison evaluates the robustness of the CVaR-based DRCC mechanism under imperfect CSI.
- Parameter effects: Higher UAV transmission power increases UAV energy use but reduces CPU frequency consumption by increasing transmission rates and leaving more MEC processing time.The resulting trade-off is evaluated through energy and CPU-frequency behavior.
APPENDIX A
Appendix A derives a tractable convex reformulation of the worst-case CVaR by introducing auxiliary and dual variables, applying saddle-point interchange and strong duality.
- The CVaR formulation represents loss exceeding an auxiliary threshold through the maximum of ϕ(·) − η and 0.
- Saddle-point interchange and strong duality transform the worst-case CVaR problem into an equivalent dual formulation.
- The inner-layer optimization is expressed over decision variables and nonnegative Borel measures associated with the uncertainty set.
- The uncertain quantity has mean Θµξ and variance Θ^2Ã^2ξ under the specified uncertainty set.
- Introducing Ç1, Ç2, and Ç3 for the constraints yields a reformulation in terms of auxiliary quantities that leads to tractable convex programming.