PaperlayerView exact revision on arXiv

Source-linked AI summary

Joint Task Offloading and Resource Allocation in Aerial-Terrestrial UAV Networks with Edge and Fog Computing for Post-Disaster Rescue

Geng Sun, Long He, Zemin Sun, Qingqing Wu, Shuang Liang, Jiahui Li, Dusit Niyato, Victor C. M. Leung

arXiv:2309.16709v2eess.SPcs.GTcs.NI

TL;DR

Post-disaster rescue requires rapid deployment, real-time information collection, and low-latency processing despite damaged infrastructure and complex terrain. The paper proposes a three-layer MEC-VFC architecture and the MVTORA approach for jointly optimizing task offloading and resource allocation, achieving superior performance over benchmark schemes, particularly under heavy workloads.

  • Problem

    Post-disaster rescue needs rapid deployment, real-time information collection, and low-latency processing, while damaged terrestrial infrastructure and complex terrain impede these requirements.

  • Method

    The paper combines a three-layer UAV edge, UAV client, and vehicle fog architecture with JTRAOP and an MVTORA decomposition using game theory, convex optimization, and evolutionary computation.

  • Results

    MVTORA achieves superior time-average system utility, average task completion delay, and total energy consumption compared with benchmark schemes, with significant improvement under heavy workloads.

  • Takeaways & Limitations

    The aerial-terrestrial architecture combines UAV MEC and vehicle VFC to offset unstable fog availability and alleviate limited edge-UAV computing resources.

  • Takeaways & Limitations

    Selecting the best Nash equilibrium is NP-hard, so the proposed real-time task-offloading procedure uses a sub-optimal equilibrium bounded by the price of anarchy.

Abstract

from arXiv · show

Unmanned aerial vehicles (UAVs) play an increasingly important role in assisting fast-response post-disaster rescue due to their fast deployment, flexible mobility, and low cost. However, UAVs face the challenges of limited battery capacity and computing resources, which could shorten the expected flight endurance of UAVs and increase the rescue response delay during performing mission-critical tasks. To address this challenge, we first present a three-layer post-disaster rescue computing architecture by leveraging the aerial-terrestrial edge capabilities of mobile edge computing (MEC) and vehicle fog computing (VFC), which consists of a vehicle fog layer, a UAV client layer, and a UAV edge layer. Moreover, we formulate a joint task offloading and resource allocation optimization problem (JTRAOP) with the aim of maximizing the time-average system utility. Since the formulated JTRAOP is proved to be NP-hard, we propose an MEC-VFC-aided task offloading and resource allocation (MVTORA) approach, which consists of a game theoretic algorithm for task offloading decision, a convex optimization-based algorithm for MEC resource allocation, and an evolutionary computation-based hybrid algorithm for VFC resource allocation. Simulation results validate that the proposed approach can achieve superior system performance compared to the other benchmark schemes, especially under heavy system workloads.

1 INTRODUCTION

The paper addresses resource and latency constraints in UAV-assisted post-disaster rescue by combining aerial MEC and terrestrial VFC in a three-layer architecture. It formulates a joint optimization problem and proposes MVTORA, which outperforms benchmark schemes, particularly under heavy workloads.

  • Post-disaster rescue requires rapid deployment, real-time information collection, and low-latency processing despite damaged infrastructure and complex terrain.
  • UAVs support rescue missions through flexible deployment and LoS communication, but their limited battery and computing resources constrain endurance and task efficiency.
  • The proposed three-layer architecture combines a UAV edge layer, UAV client layer, and vehicle fog layer to exploit aerial and terrestrial computing resources.
  • JTRAOP maximizes time-average system utility by jointly optimizing task offloading and resource allocation, with utility synthesizing task delay and UAV energy consumption.
  • MVTORA separates task offloading from resource allocation using game theoretic, convex optimization-based, and evolutionary computation-based algorithms.
  • MVTORA achieves superior time-average utility, task delay, and energy performance relative to benchmark schemes, with significant improvement under heavy workloads.

2 RELATED WORKS

Prior work studies UAV communications, cloud/MEC/VFC offloading, and resource allocation, but rarely addresses their joint use in multi-UAV post-disaster rescue. This paper combines UAV-enabled MEC and vehicle-enabled VFC to exploit heterogeneous resources in that setting.

  • Related research has examined UAV-enabled connectivity and computing, including aerial relaying, UAV base stations, and image-sensing-driven tasks.
  • Cloud offloading provides abundant resources but can incur unacceptable delay and heavy backhaul utilization because cloud servers are distant from end users.
  • MEC places cloud-computing resources near users, while VFC extends fog computing through idle resources in vehicles and other devices.
  • Existing resource-allocation studies variously optimize radio resources, computing resources, or their joint allocation in non-rescue settings.
  • Few prior works study task offloading and resource allocation for multi-UAV post-disaster rescue under unpredictable demand, unstructured networks, and stringent QoS requirements.
  • This work addresses that gap with a three-layer architecture combining UAV-enabled MEC and vehicle-enabled VFC to jointly exploit heterogeneous computing resources.

3 SYSTEM ARCHITECTURE AND PROBLEM FOR-

The system comprises vehicle fog, UAV client, and UAV edge layers, with small UAVs generating delay-sensitive tasks and selecting local, aerial MEC, or terrestrial VFC execution. Vehicle mobility is modeled with PPP and Gauss-Markov processes, while UAV trajectories remain fixed.

  • System Architecture: The architecture contains rescue vehicles, small client UAVs, and a large edge UAV serving as terrestrial fog, UAV client, and UAV edge entities.
  • System Architecture: Rescue vehicles share idle computing resources with client UAVs to alleviate possible overload at the edge UAV.
  • System Architecture: Client UAVs follow preset trajectories, generate computation-intensive and latency-sensitive tasks, and can process them locally or offload them to the edge UAV or vehicles.
  • System Architecture: The edge UAV provides communication coverage, computing resources, disaster information reporting, and regional control for the system.
  • Basic Models: The system timeline is divided into equal time slots, and the current work does not optimize UAV trajectories.
  • Basic Models: Rescue vehicles are modeled as a PPP spatial distribution with Gauss-Markov mobility capturing temporal dependence in their movement.
  • Basic Models: Each client UAV generates at most one task per time slot, with task data size, computation intensity, and maximum acceptable delay represented in the task model.

3.2 Communication Model

The communication model supports C-UAV offloading through U2V links to vehicle fog nodes and U2U links to E-UAVs, using OFDMA and directional antennas. U2V channels include probabilistic LoS/NLoS effects, while U2U links use a free-space path-loss model.

  • Communication links: C-UAVs offload tasks to vehicle fog nodes through U2V links or to E-UAVs through U2U links, with OFDMA providing orthogonal sub-channels.Each C-UAV has K_n orthogonal wireless sub-channels.
  • Antenna model: The directional antenna uses equal azimuth and elevation half-power beamwidths, with beamwidth parameter Ψ defining its main coverage region.The antenna gain is modeled as G0/Ψ^2 inside the beamwidth and approximately zero outside it.
  • U2V communication: U2V communication uses a probabilistic LoS channel model combining small-scale fading with large-scale fading from path loss and shadowing.The LoS probability is modeled as a logistic function of the elevation angle.
  • U2V communication: The expected U2V communication rate depends on sub-channel bandwidth, transmission power, and noise power spectral density.The model also assumes LoS probability changes negligibly within a time slot.
  • U2U communication: U2U communication is characterized by free-space path loss because the links are dominated by line-of-sight propagation.The rate depends on transmission power, reference-distance channel gain, and the C-UAV-to-E-UAV distance.

3.3 Service Delay and Energy Consumption

The model evaluates each task’s service delay and energy consumption under local computing, MEC offloading, or VFC-assisted offloading. These metrics are combined with computation-resource cost to construct C-UAV utility.

  • Service models: Task service delay and energy consumption depend on the selected offloading strategy.The modeled strategies are local computing, MEC-assisted offloading, and VFC-assisted offloading.
  • Local computing: Local computing incurs a local execution delay and energy consumption determined by the task and C-UAV computation model.The energy expression includes the effective switched capacitance coefficient k, which depends on hardware architecture.
  • MEC-assisted offloading: MEC-assisted delay includes transmission and E-UAV execution, while C-UAV energy consumption is mainly induced by task transmission.F_n(t) denotes the E-UAV computing resource allocated to task Φ_n(t).
  • VFC-assisted offloading: VFC-assisted offloading divides a task into independent subtasks processed in parallel by selected in-range rescue vehicles.The model accounts for transmission delay, vehicle execution delay, task-division proportions, available vehicle resources, and transmission energy.
  • Modeling assumption: Propulsion energy is omitted because preset C-UAV trajectories make it constant and irrelevant to offloading decisions.This assumption isolates energy associated with task processing and transmission.

3.5 Problem Formulation

The formulation maximizes time-average system utility by jointly selecting offloading, MEC allocation, vehicle selection, and task division. Its mixed-integer non-linear structure is non-convex and NP-hard, motivating a real-time-oriented solution approach.

  • Optimization objective: The JTRAOP maximizes time-average system utility through joint optimization of task offloading and resource-allocation decisions.The decision variables include offloading decisions A, MEC allocation F, vehicle selection S, and task division λ.
  • Constraints: Each C-UAV selects one offloading strategy, while MEC allocations, vehicle selections, and task divisions are constrained by system resources and connectivity.Vehicle fog nodes are selected for individual C-UAV service and must remain within communication range.
  • Problem reformulation: Tasks are assumed to complete within one time slot because rescue-mission tasks are delay-sensitive.This assumption enables reformulation of the problem as a per-time-slot optimization.
  • Problem complexity: The resulting problem is a mixed-integer non-linear programming problem that is non-convex and NP-hard.Its binary and continuous variables create computational overhead for seeking an optimal real-time solution.

4 MEC-VFC-AIDED TASK OFFLOADING AND RESOURCE ALLOCATION APPROACH

MVTORA separates task offloading from computing-resource allocation to solve the joint problem. It uses game theory for offloading, convex optimization for MEC allocation, and evolutionary computation for VFC allocation.

  • Approach design: MVTORA decomposes the joint optimization into task offloading and computing-resource allocation components.The two components are solved separately to address the original problem structure.
  • Task offloading: Game theory determines C-UAV task-offloading decisions.This component optimizes which execution destination each C-UAV selects.
  • Resource allocation: Convex optimization determines aerial MEC resource allocation for the E-UAV.The allocation concerns computing resources assigned to C-UAV tasks.
  • Resource allocation: Evolutionary computation determines terrestrial VFC resource allocation for vehicular fog nodes.This component addresses resource allocation on the vehicle-enabled fog layer.

4.1 Task Offloading

The task offloading problem is modeled as a game among multiple C-UAVs because each UAV’s decision depends on other UAVs’ decisions. The game is shown to be an exact potential game, enabling Nash-equilibrium computation through better-response updates.

  • Game Formulation: Each C-UAV’s offloading decision depends on the decisions of other C-UAVs, motivating a game-theoretic formulation.
  • Game Formulation: The offloading game is defined by players, a joint strategy space, and utility functions mapping strategy profiles to real numbers.
  • Game Formulation: Each C-UAV selects an offloading strategy to maximize its own utility given the strategies of the other players.
  • Nash Equilibrium: The game uses Nash equilibrium and exact potential-game concepts to characterize stable offloading decisions and utility changes from unilateral deviations.
  • Nash Equilibrium: Because finite exact potential games have the finite improvement property, better-response updates terminate at a Nash equilibrium.
  • Solution Procedure: Theorem 1 establishes that the multi-C-UAV task offloading game is an exact potential game, and Algorithm 1 iteratively updates strategies until equilibrium.

4.2 Resource Allocation

Resource allocation is decomposed into aerial MEC and terrestrial VFC sub-problems. MEC allocation uses convex optimization, while VFC allocation selects vehicle fog nodes and divides tasks using preference ordering and evolutionary computation.

  • Overview: Resource allocation is decomposed into MEC and VFC sub-problems for the aerial E-UAV and terrestrial vehicle nodes.
  • MEC Resource Allocation: The MEC problem maximizes the total utility of C-UAVs offloading to the E-UAV by optimizing its computation-resource allocation.
  • MEC Resource Allocation: Problem P1 is convex, so KKT conditions and a bisection method are used to obtain the optimal MEC computation-resource allocation.
  • VFC Resource Allocation: VFC allocation first selects vehicle fog nodes according to C-UAV preferences to minimize completion delay for heterogeneous, delay-sensitive tasks.
  • Vehicle Fog Node Selection: Sorting vehicles by increasing preference and selecting the top K_n vehicles yields the optimal candidate set for task Φ_n.
  • VFC Resource Allocation: Because vehicle selection and task division are sequential and the resulting problem is MINLP, VFC allocation is solved through a two-step procedure.
  • Task Division: The task-division algorithm uses a genetic algorithm with population evolution, constraint normalization, fitness evaluation, selection, crossover, mutation, and elitism.

4.3 Main Steps of MVTORA and Analysis

MVTORA executes task offloading and resource allocation in each time slot using the E-UAV’s collected system information. Its analysis addresses equilibrium quality and computational complexity, with polynomial complexity per slot.

  • Main Steps: Algorithm 5 uses state information from the E-UAV, rescue vehicles, and C-UAVs to output the time-average system utility.
  • Performance Analysis: The price of anarchy quantifies the gap between the worst-case Nash equilibrium and the centralized optimal solution, bounding the game solution’s sub-optimality.
  • Main Steps: In each slot, the E-UAV obtains vehicle information, computes local utility, and invokes the vehicle-selection and task-division algorithms for VFC allocation.
  • Main Steps: The E-UAV obtains the initial offloading decision, calls the task-offloading game and MEC allocation procedures, and applies the resulting decisions.
  • Complexity Analysis: MVTORA has polynomial computational complexity in each time slot, with complexity parameters including Nash-equilibrium iterations, UAV count, search bounds, and accuracy.

5 SIMULATION RESULTS

Simulations evaluate MVTORA’s convergence, time-varying utility, and performance under changes in edge resources, task computation density, and vehicle density. Across these settings, MVTORA generally provides superior utility, delay, and energy performance, particularly as workloads or available vehicle resources increase.

  • Convergence and Performance: MVTORA converges to a Nash equilibrium as iterations increase, reaching a stable state within limited iterations across varying C-UAV densities.Each C-UAV updates its offloading strategy until no unilateral change further improves its utility.
  • Convergence and Performance: MVTORA outperforms ELC, EMC, VTO, MTO, TODO, NGTO, and DATORA in system utility over time slots.System utility fluctuates irregularly because task arrivals, communication links, and vehicle-fog resources vary over time.
  • Impact of Parameters: As E-UAV computation resources increase, MVTORA maintains slightly steadier trends in time-average utility, average completion delay, and total energy consumption than benchmark algorithms.The approach integrates aerial and terrestrial edge resources to alleviate C-UAV overload.
  • Impact of Parameters: For task computation densities below 300 cycles/bit, ELC, MTO, VTO, TODO, NGTO, DATORA, and MVTORA achieve similar performance across the three reported metrics.At low computation density, local computing can avoid additional transmission delay and energy consumption.
  • Impact of Parameters: With increasing vehicle distribution density, MVTORA achieves significantly superior utility and completion delay with low energy consumption, indicating better scalability.VTO also improves as vehicle-fog resources become more available, whereas DATORA may underutilize those resources because of heuristic simplifications.

6 DISCUSSION

The discussion examines whether MVTORA generalizes across vehicle distributions and mobility models and whether its offloading decisions are rational relative to mixed offloading. These checks use additional simulations and comparisons described in the supplementary material.

  • Generalizability: MVTORA is evaluated under random distribution with random walk, mobile traffic, and Poisson cluster with Markovian waypoint mobility models.The corresponding simulation results are reported in Fig. 1 of Appendix E in the supplemental material.
  • Offloading Strategy: The proposed task offloading scheme is compared with mixed local, MEC, and VFC offloading to assess the rationale of its decisions.The analysis and performance comparison are provided in Appendix F of the supplementary material.

7 CONCLUSION

The work integrates aerial and terrestrial computing in a three-layer rescue architecture and formulates joint task offloading and resource allocation to maximize time-average system utility. Because the optimization is NP-hard, the proposed MVTORA approach separates offloading and resource allocation, achieving superior utility, delay, and energy performance in simulations.

  • The proposed architecture integrates UAV edge, UAV client, and vehicular fog layers to combine aerial and terrestrial computing capabilities.It is designed for post-disaster rescue and leverages MEC and VFC resources.
  • The JTRAOP maximizes time-average system utility by jointly optimizing task offloading and computing resource allocation.
  • Because JTRAOP is NP-hard, MVTORA decomposes it into task offloading and resource allocation components solved with game-theoretic, convex optimization, and evolutionary computation algorithms.
  • Simulation results show MVTORA's superiority in time-average system utility, average task completion delay, and total energy consumption.
Loading 2309.16709v2…