PaperlayerView exact revision on arXiv

Source-linked AI summary

Hierarchical Aerial Computing for Internet of Things via Cooperation of HAPs and UAVs

Ziye Jia, Qihui Wu, Chao Dong, Chau Yuen, Zhu Han

arXiv:2202.06046v1cs.NIeess.SP

TL;DR

The paper addresses how to serve delay-sensitive IoT computation demands through cooperating UAVs and HAPs despite limited aerial resources and an intractable integer-programming formulation. It develops matching, externality-elimination, heuristic, and adjustment algorithms for hierarchical offloading, and numerical evaluations report efficient near-optimal solutions.

  • Problem

    Remote and emergency IoT devices need intensive, delay-sensitive computation but have limited resources, while jointly optimizing UAV–HAP offloading is an intractable integer-programming problem.

  • Method

    The paper uses matching-game and externality-elimination algorithms for IoT–UAV offloading, a heuristic algorithm for UAV–HAP offloading, and an adjustment algorithm for residual aerial resources.

  • Results

    Numerical results verify that the proposed algorithms efficiently achieve near-optimal solutions compared with exhaustive searching, with MEHA obtaining a near-optimal solution at low complexity.

  • Takeaways & Limitations

    The hierarchical IoT–UAV–HAP offloading scheme and analyzed parameter effects support resource management for practical aerial computing applications.

Abstract

from arXiv · show

With the explosive increment of computation requirements, the multi-access edge computing (MEC) paradigm appears as an effective mechanism. Besides, as for the Internet of Things (IoT) in disasters or remote areas requiring MEC services, unmanned aerial vehicles (UAVs) and high altitude platforms (HAPs) are available to provide aerial computing services for these IoT devices. In this paper, we develop the hierarchical aerial computing framework composed of HAPs and UAVs, to provide MEC services for various IoT applications. In particular, the problem is formulated to maximize the total IoT data computed by the aerial MEC platforms, restricted by the delay requirement of IoT and multiple resource constraints of UAVs and HAPs, which is an integer programming problem and intractable to solve. Due to the prohibitive complexity of exhaustive search, we handle the problem by presenting the matching game theory based algorithm to deal with the offloading decisions from IoT devices to UAVs, as well as a heuristic algorithm for the offloading decisions between UAVs and HAPs. The external effect affected by interplay of different IoT devices in the matching is tackled by the externality elimination mechanism. Besides, an adjustment algorithm is also proposed to make the best of aerial resources. The complexity of proposed algorithms is analyzed and extensive simulation results verify the efficiency of the proposed algorithms, and the system performances are also analyzed by the numerical results.

I. INTRODUCTION

The paper proposes hierarchical aerial computing with UAVs and HAPs to serve computation-intensive IoT applications, especially where terrestrial services are unavailable. It formulates resource-constrained offloading as an intractable integer program and develops staged algorithms to obtain efficient near-optimal solutions.

  • IoT devices have intensive, delay-sensitive computation demands but limited computing and energy resources, motivating MEC support.
  • HAPs and UAVs provide aerial MEC connectivity for remote or emergency IoT, with HAPs offering greater coverage, payload, and computing capacity.HAPs can support UAVs and handle computation-intensive demands.
  • The framework lets IoT devices offload to UAVs, while UAVs relay heavy demands to HAPs when UAV processing cannot meet delay requirements.
  • The objective maximizes successfully computed IoT data under delay, resource, binary-contact, and integer-decision constraints.
  • A matching-game algorithm and externality-elimination mechanism handle IoT–UAV offloading, while heuristic and adjustment algorithms manage UAV–HAP offloading and residual resources.
  • Prior work studies UAV or HAP aerial computing separately, whereas this paper addresses their hierarchical cooperation and reports near-optimal performance with low-complexity algorithms.

III. SYSTEM MODEL AND PROBLEM FORMULATION

The system model describes a quasi-static hierarchical aerial network of IoT devices, UAVs, and HAPs, then models wireless links, computation, energy, and offloading variables for problem formulation.

  • III. SYSTEM MODEL AND PROBLEM FORMULATION: The section defines the system model, communication model, computing model, energy-cost model, and final optimization formulation.
  • A. Hierarchical Aerial Computing Scenario: The hierarchical scenario contains terrestrial IoT users, quasi-static rotary-wing UAVs, and stable HAP base stations equipped with edge servers.
  • A. Hierarchical Aerial Computing Scenario: HAPs have stronger load capacity than UAVs, while IoT devices have varied computation demands and limited local computing capability.
  • B. Communication Model: The IoT–UAV channel uses orthogonal frequency division and a line-of-sight model.
  • 1) Channel Model from IoT to UAV (I2U): The I2U channel gain depends on the reference gain, horizontal separation, and UAV altitude through the IoT–UAV distance.
  • 1) Channel Model from IoT to UAV (I2U): Transmission time is calculated from the available channel rate and IoT data size, with x_i^u indicating whether IoT i offloads to UAV u.
  • 1) Channel Model from IoT to UAV (I2U): The U2H channel rate is obtained using a Shannon-theoretic model for UAV-to-HAP transmission.

2) Channel Model from UAV to HAP (U2H):

The U2H model characterizes UAV-to-HAP transmission using a Shannon-based rate and accounts for propagation, bandwidth, antenna gain, loss, distance, frequency, and noise.

  • 2) Channel Model from UAV to HAP (U2H): The U2H achievable data rate is modeled with bandwidth, antenna power gain, line loss, transmit power, channel gain, and noise terms.
  • 2) Channel Model from UAV to HAP (U2H): The model defines free-space loss using the speed of light, UAV–HAP distance, center frequency, Boltzmann’s constant, and system noise temperature.
  • 2) Channel Model from UAV to HAP (U2H): The transmission time for IoT data forwarded from UAV u to HAP h is calculated from the U2H rate.
  • 2) Channel Model from UAV to HAP (U2H): A binary forwarding variable indicates whether IoT data is relayed from UAV u to HAP h.

C. Computing Model

The computing model lets IoT tasks execute on UAVs or be relayed to HAPs when UAV resources cannot support them, while accounting for transmission and computation delay.

  • IoT computation demands can be offloaded to a UAV for local execution or relayed by the UAV to a HAP for processing.
  • ρu represents the UAV computing resource required to process one bit of IoT data, measured in CPU cycles.
  • βi_u is a binary variable indicating whether IoT task i is computed by UAV u.
  • If a UAV lacks sufficient remaining computing resources, the task is relayed to a HAP, whose processing cost and capacity are represented by µh and Ch.
  • The total completion delay includes transmission and computation time, while result-transmission delay and energy are omitted because computation results are small.

D. Energy Cost Model

The energy-cost model accounts for operation, computation, and transmission consumption at IoT devices and UAVs, with processor-dependent computation coefficients.

  • 1) Energy Cost of IoT: IoT energy cost consists mainly of basic operation energy and transmission energy.
  • 1) Energy Cost of IoT: The IoT-to-UAV transmission power is denoted by P_tr_i.
  • 2) Energy Cost of UAV: UAV energy cost comprises basic operation, computation, and transmission energy, including hovering and UAV-to-HAP transmission.
  • 2) Energy Cost of UAV: ςu denotes the UAV processor’s energy-consumption coefficient, determined by chip structure.

3) Energy Cost of HAP:

The HAP energy model includes basic operation and computation costs, while the optimization maximizes computed IoT data under offloading, energy, delay, and integer constraints.

  • 3) Energy Cost of HAP: HAP energy cost is composed of basic operation energy and computation energy.
  • E. Problem Formulation: The optimization objective is to maximize total IoT data computed by UAVs and HAPs subject to resource and offloading constraints.
  • E. Problem Formulation: Each IoT device can connect to at most one UAV, UAV service is limited by quota, and data flow between UAV and HAP must be conserved.
  • E. Problem Formulation: Energy budgets constrain IoT devices, UAVs, and HAPs, while total transmission and computation time must remain within each IoT device’s tolerated delay.
  • E. Problem Formulation: The integer program has exhaustive-search complexity O(2^|I|·(2^|U|+|U|·|H|+|U|)) and becomes especially difficult in large networks.
  • IV. Algorithm Design: The proposed solution divides the problem among matching, externality elimination, heuristic offloading, and resource-adjustment algorithms.

A. Matching based Algorithm for IoT Data Offloading to UAV

IoT devices and UAVs are modeled as a many-to-one matching market, with preference lists encoding resources, capacity, data size, and delay; externality elimination addresses changing preferences.

  • IoT-to-UAV offloading is formulated as a two-sided many-to-one matching problem because each IoT selects at most one UAV while each UAV serves multiple IoTs.
  • Preference lists incorporate the original objective and constraints, allowing agents to rank feasible partners using resource and system information.
  • The matching algorithm initializes preference lists and an empty matching, then repeatedly assigns unmatched IoTs to preferred UAVs and replaces worse matches when quotas are full.
  • IoT devices prefer UAVs with greater residual computing capacity, residual energy, and available channel capacity, weighted by λ1, λ2, and λ3.
  • UAVs prefer IoT devices with larger data sizes and more tolerant delay requirements, matching the optimization objective.
  • A blocking pair is an unmatched IoT–UAV pair that both could improve upon under current service and preference conditions.
  • Because UAV resource consumption changes with other assignments, IoT preferences depend on the matching; externality elimination is therefore needed for a final stable matching.

B. Eliminating the Externality

The paper removes externality from IoT–UAV matching by re-stabilizing matches through invalid-pair removal and Pareto-improving exchanges. The resulting procedure searches blocking pairs and exchanges partners until stability is restored, with worst-case complexity O(|I|^3·|U|).

  • Externality elimination: The externality elimination algorithm removes invalid IoT–UAV pairs and updates UAV preference lists before re-stabilizing the matching.It uses the matching from Algorithm 1 and its updated IoT preference lists as inputs, producing a re-stabilized matching M2.
  • Exchange process: The matching is Pareto optimal when no alternative matching benefits some IoT devices without making any IoT device worse off.This criterion defines the equilibrium sought by the externality elimination procedure.
  • Blocking pairs: A one-sided blocking pair consists of two IoT devices that would both improve their utilities by swapping matched UAVs.The exchange process evaluates whether IoT devices become better off under partner switching.
  • Exchange process: The algorithm repeatedly finds unstable IoT–IoT blocking pairs and selects an optimal pair for partner exchange.After each exchange, the matching is updated and the process continues toward Pareto optimality.
  • Complexity and convergence: O(|I|^3·|U|) is the worst-case time complexity of the externality elimination algorithm.The bound arises from traversing IoT–UAV preference lists and iteratively searching and swapping IoT blocking pairs; practical complexity may be lower.

C. Data Offloading from UAV to HAP

The heuristic UAV-to-HAP offloading algorithm redirects delay-infeasible IoT data to HAPs and then removes HAP assignments that still violate delay requirements. Its worst-case complexity is O((|U| + |H|) · |I|).

  • Heuristic offloading: The heuristic algorithm identifies IoT data whose delay requirements cannot be met by matched UAVs and places them in a ranked candidate set.Candidates are ranked in descending order using ι1σi + ι1Di.
  • Heuristic offloading: The algorithm offloads the first ranked IoT data to a HAP and repeatedly checks whether the remaining data can be served by the UAV.The candidate set is updated after each offload.
  • HAP feasibility: At the HAP, IoT data that still violate delay requirements are removed starting with the smallest data size.The HAP’s residual resources are updated after each deletion.
  • Complexity: O((|U| + |H|) · |I|) is the heuristic algorithm’s worst-case complexity.The two components correspond to checking IoT data at UAVs and at HAPs.

D. Adjustment Algorithm

The adjustment algorithm uses residual UAV resources after UAV-to-HAP offloading to serve additional IoT devices that remain unserved.

  • Adjustment procedure: The adjustment algorithm ranks unserved IoT devices by descending Di/σi after the heuristic offloading stage.It then attempts to offload the highest-ranked devices to UAVs when residual resources permit.

V. PERFORMANCE EVALUATION

The evaluation uses a simulated hierarchical aerial-computing scenario with one HAP, four UAVs, and randomly distributed terrestrial IoT users. The simulations assess the proposed mechanism and algorithm efficiency.

  • Evaluation setup: The simulations evaluate the hierarchical aerial computing mechanism and the proposed algorithms.The implementation uses MATLAB together with CVX and MOSEK optimization tools.
  • Coverage scenario: Fig. 3 depicts UAV and HAP coverage for 30 IoT devices.The caption identifies the figure as a coverage view for |I| = 30.
  • Evaluation setup: The scenario contains one HAP at 20 km, four UAVs at 2 km, and IoT users randomly distributed across a 10 km×10 km area.UAVs lie within HAP coverage, while terrestrial users lie within UAV coverage.
  • Parameters: The simulation parameters set u = 10W, Ei = 100J, Eu = 100KJ, and Eh = 1000KJ.The matching weights are λ1 = λ2 = 0.4, λ3 = 0.2, and ι1 = ι2 = 0.5.

B. Performance Evaluation

The proposed algorithms achieve near-optimal performance with low complexity, while hierarchical UAV–HAP computing outperforms single-platform modes. Computation capability affects both computed data and energy cost, with HAP capability having the stronger effect.

  • Algorithm performance: MEHA obtains a near-optimal solution with low complexity compared with the optimization-tool solution OP.MEH and MHA perform worse than MEHA, while MH and greedy offloading are especially undesirable as the number of IoT devices increases.
  • Aerial computing modes: Hierarchical UAV+HAP computing outperforms UAV-only and HAP-only modes in total computed data and served users.UAV-only computing performs better than HAP-only computing because UAVs are closer to IoT devices, transmission power is limited, and some IoT devices fall outside HAP coverage.
  • Computation capability: Decreasing HAP or UAV computation capability reduces total computed data, with HAP capability producing the more prominent effect.The stronger HAP effect is attributed to HAPs providing computation service for a larger amount of IoT data.
  • Energy cost: Increasing HAP or UAV computation capability increases total energy consumption, with HAP capability having the stronger effect.The reported trends agree with formulas (10) and (11), and HAPs serve more IoT devices because they combine large computing and energy capacity.
  • Overall evaluation: The study analyzes algorithm efficiency, hierarchical offloading benefits, and the influence of network parameters for practical resource management.The conclusion also identifies dynamic traffic, channel utilization, data rate, equipment utilization, and mutual UAV offloading as future issues.
Loading 2202.06046v1…