PaperlayerView exact revision on arXiv

Source-linked AI summary

UAV Trajectory Planning for AoI-Minimal Data Collection in UAV-Aided IoT Networks by Transformer

Botao Zhu, Ebrahim Bedeer, Ha H. Nguyen, Robert Barton, Zhen Gao

arXiv:2401.02425v1cs.NIcs.AI

TL;DR

The paper seeks to minimize total AoI in UAV-assisted, cluster-based IoT data collection, where freshness depends on flight and collection times. It jointly optimizes hovering points and visiting order using a transformer with weighted A*, and reports strong generalization across network sizes without retraining. The proposed methods achieve lower total AoI than comparison algorithms, including 13134 seconds versus 13431 seconds for Ptr-A* at M = 25 and a 6.3% gain at M = 45.

  • Problem

    Time-sensitive IoT applications require fresh information, but UAV data collection must account jointly for flight time, collection time, and cluster-level trajectory decisions.

  • Method

    The paper transforms the joint hovering-point and visiting-order optimization into a GTSP and uses a transformer with weighted A* trained by reinforcement learning.

  • Results

    At M = 25, TWA*-sampling achieves 13134 seconds total AoI versus 13431 seconds for Ptr-A*, while at M = 45 it achieves a 6.3% performance gain over Ptr-A*.

  • Takeaways & Limitations

    The learned policy generalizes to IoT networks with different numbers of clusters without retraining and achieves lower total AoI than the comparison algorithms.

Abstract

from arXiv · show

Maintaining freshness of data collection in Internet-of-Things (IoT) networks has attracted increasing attention. By taking into account age-of-information (AoI), we investigate the trajectory planning problem of an unmanned aerial vehicle (UAV) that is used to aid a cluster-based IoT network. An optimization problem is formulated to minimize the total AoI of the collected data by the UAV from the ground IoT network. Since the total AoI of the IoT network depends on the flight time of the UAV and the data collection time at hovering points, we jointly optimize the selection of hovering points and the visiting order to these points. We exploit the state-of-the-art transformer and the weighted A*, which is a path search algorithm, to design a machine learning algorithm to solve the formulated problem. The whole UAV-IoT system is fed into the encoder network of the proposed algorithm, and the algorithm's decoder network outputs the visiting order to ground clusters. Then, the weighted A* is used to find the hovering point for each cluster in the ground IoT network. Simulation results show that the trained model by the proposed algorithm has a good generalization ability to generate solutions for IoT networks with different numbers of ground clusters, without the need to retrain the model. Furthermore, results show that our proposed algorithm can find better UAV trajectories with the minimum total AoI when compared to other algorithms.

I. INTRODUCTION

The paper addresses freshness-aware UAV data collection in cluster-based IoT networks by minimizing total AoI through joint trajectory and hovering-point optimization. It models the optimization as a GTSP and uses a transformer-based learning framework with weighted A* to generate trajectories.

  • Motivation: AoI measures elapsed time since the latest data update was generated, making freshness important for time-sensitive IoT applications.Outdated information can cause incorrect control and major disasters.
  • Motivation: Cluster-based collection reduces UAV energy consumption by having the UAV visit cluster-level collection points instead of every ground device.Ground sensors forward sampled data to cluster heads, which aggregate data for UAV collection.
  • Problem formulation: Hovering-point selection and visiting order jointly affect flight time, data collection time, and the total AoI of collected data.The paper transforms this continuous optimization into a generalized traveling-salesman problem using sampling-based hovering-point candidates.
  • Proposed approach: The proposed framework treats the UAV-IoT network as a source language and the minimum-AoI UAV trajectory as a target language.A transformer generates the visiting order, while weighted A* determines hovering points; reinforcement learning trains the policy using reward calculation.
  • System model: The UAV starts above the base station, visits one hovering point per ground cluster, collects data, and returns to the start point.Each hovering point lies at the UAV flight height and corresponds to one ground cluster.
  • Data collection model: At each hovering point, a beacon activates the corresponding cluster head, whose member sensors transmit sequentially using pre-allocated TDM slots.The collection process uses generate-at-will sampling for ordinary sensor nodes and accounts for both LoS and NLoS ground-to-air links.

B. UAV’s Mobility Model

The UAV trajectory is represented as an ordered tour beginning and ending at the start hovering point. Flight time depends on distances between consecutive hovering points, while movement and hovering have distinct power models.

  • The UAV visits M mission hovering points in a permutation and returns to the initial hovering point c0.The ordered route includes the start point before and after the mission points.
  • 21?
  • The UAV flies horizontally between consecutive hovering points along their connecting line segment.
  • Horizontal-movement power is modeled as a function of UAV speed, with blade-profile, induced, rotor-tip, drag, solidity, air-density, and rotor-disk parameters.
  • In hovering, UAV power is constant and equals Phov = P0+P1.

C. Age of Information Model in a UAV-IoT System

The AoI model measures packet freshness at the base station when the UAV returns with collected data. Each packet’s AoI combines ground-side collection and forwarding time with UAV flight and subsequent collection delays.

  • AoI is the elapsed time from packet generation until the UAV returns with the collected data to the base station.
  • AoI increases with time, and packets from different clusters satisfy ordering relations determined by their collection sequence.
  • For a node in a visited cluster, packet AoI is divided into ground-side collection and forwarding time plus UAV transport time.The first component covers collection by the cluster head and forwarding to the UAV; the second covers the UAV’s remaining route.
  • During each transition, packet AoI increases by the flight time to the next hovering point and the data collection time there.

D. Problem Formulation

The paper formulates UAV trajectory planning as a total-AoI minimization problem that jointly selects hovering points and their visiting order. Sampling converts the continuous hovering-point choice into a combinatorial GTSP-like problem addressed with learning-based methods.

  • The total AoI is a weighted sum of UAV flight time and data collection time at hovering points, determined by hovering-point locations and visiting order.
  • The objective jointly selects one hovering point from each cluster and plans the UAV visiting order to minimize total data AoI.
  • The formulated problem is a TSPN combining continuous hovering-point optimization with combinatorial trajectory planning.
  • Sampling changes the task into selecting hovering points from M sampled clusters and visiting the selected points exactly once.
  • The sampled formulation is a combinatorial optimization problem and is NP-hard.
  • Transformer, weighted A*, and reinforcement learning are adopted to solve the transformed problem efficiently.

III. TRANSFORMER-WEIGHTED A* ALGORITHM

The proposed TWA* algorithm casts total-AoI trajectory planning as sequence-to-sequence translation: a transformer encodes the UAV-IoT network and decodes a visiting order, while weighted A* selects the route’s hovering points.

  • A. Encoder: The TWA* algorithm translates the UAV-IoT network into a UAV trajectory using an encoder, decoder, and weighted A* search.
  • A. Encoder: The encoder input includes the UAV start point, every cluster head, node counts, and sampling points from each hovering disk.
  • A. Encoder: The input represents each cluster with sampling-point coordinates, a three-dimensional cluster-head vector, and a constant node count.
  • A. Encoder: A learnable embedding maps input elements into dem-dimensional vectors, using separate parameters to distinguish the UAV start point from clusters.
  • A. Encoder: The transformer encoder uses six identical layers, each combining eight-head self-attention with a pointwise feed-forward network, residual connections, and normalization.
  • A. Encoder: Self-attention compares projected queries and keys, applies row-wise softmax scores, and merges the eight head outputs through a learnable projection.

B. Decoder

The decoder autoregressively produces an ordered visiting sequence from encoder outputs, positional information, and previously decoded elements. Attention mechanisms mask visited elements and assign probabilities to possible next outputs.

  • B. Decoder: The decoder generates the visiting order one element at a time, beginning and ending with the UAV start point.Each output depends on encoder information and previously generated decoder outputs.
  • B. Decoder: The decoder aims to find the visiting sequence π that maximizes P(π|H(in)).The sequence probability is modeled using the probability chain rule.
  • B. Decoder: Two decoder layers and a single-head attention layer use positional encoding to represent the order of decoded elements.The decoder input combines encoder outputs with sinusoidal positional encoding.
  • B. Decoder: The second multi-head attention sub-layer matches encoder inputs to decoder inputs so the decoder can select among non-visited elements.Visited-element masks are added to the scaled attention scores.
  • B. Decoder: A single-head attention layer converts decoder and encoder outputs into probability scores over the non-visited elements.The resulting distribution is used to select the next output by sampling or decoding methods.

1) Greedy:

Greedy decoding selects the next element with the largest conditional probability at each decoding step.

  • 1) Greedy:: Greedy decoding selects the element with the largest conditional probability at every step.The selected element becomes the next item in the visiting order.

2) Random Sampling:

The described sampling and beam-search procedures generate or retain candidate visiting orders according to decoder probabilities, then use the resulting order to construct the UAV path.

  • 2) Random Sampling:: Random sampling generates Wsampling complete visiting orders and chooses the one with the highest probability.Each sampled solution contains a full visiting order.
  • 2) Random Sampling:: Beam search retains the top Wbeam partial solutions at each step and expands them iteratively.The sequence with the highest overall probability is selected from the resulting solution tree.
  • 2) Random Sampling:: Greedy decoding maps the highest-probability index to an encoder input element and appends it with positional encoding for the next step.This process produces the visiting order π over encoder inputs.
  • 2) Random Sampling:: Given the visiting order, the method constructs a layered graph of hovering-point clusters and searches for a minimum-total-AoI path.The path starts at the designated start point, traverses each cluster, and ends at its clone.

3: CAME

Weighted A* searches directed connections between possible hovering points in consecutive clusters to construct a path with minimum total AoI. The proposed transformer and search stages have quadratic complexity in the input or search-graph size.

  • 3: CAME: Weighted A* selects hovering points across consecutive clusters according to the decoder-produced visiting order.Edges between possible hovering points are directed by π.
  • 3: CAME: The search expands the neighbor with minimum f(s), combining accumulated movement cost g(s) with heuristic cost h(s) scaled by ω > 1.The heuristic estimates the cost from the current point to the endpoint.
  • 3: CAME: COST, FRONTIER, and CAME FROM track path costs, expansion, and parent pointers during weighted A* search.Parent pointers reconstruct the minimum-AoI path from the start to the endpoint.
  • 3: CAME: The transformer encoder, decoder, and final attention layer each retain quadratic complexity O((M + 1)^2d_em) in input-sequence length.The number of network layers is treated as constant.
  • 3: CAME: Weighted A* visits at most M L_sub^2 search points, yielding an estimated complexity O(M L_sub^2 log(M L_sub^2)).The logarithmic factor comes from extracting points from a min heap.

E. Training

The transformer is trained with policy-gradient reinforcement learning, using network and visitation information as state and decoder operations as actions. Sampling and greedy decoding are evaluated through weighted A*, while architectural and training choices support parallel processing and variance reduction.

  • The state combines the encoder’s environment representation with clusters visited before the current decoder step.
  • The decoder operations define the action, and the transformer policy selects the next action from the current state.
  • The training objective uses the negative total AoI as reward and applies REINFORCE with a greedy rollout baseline.
  • Sampling and greedy decoding produce candidate trajectories, whose total AoIs are obtained through weighted A* before parameter updates with Adam.
  • The greedy baseline uses deterministic decoding to reduce training variance, and updates occur only when improvement is significant under a 5% paired t-test.
  • Compared with Ptr-A*, TWA* uses multi-head self-attention and processes sequence elements in parallel rather than relying on recurrent hidden states.

IV. NUMERICAL RESULTS

Experiments evaluate TWA* across network sizes, decoding strategies, AoI components, energy consumption, and inference time. The results show strong generalization and improved AoI, energy, and computational performance relative to comparison algorithms.

  • Experimental setup: The model is trained with random cluster instances and evaluated using greedy, sampling, and beam-search decoding, alongside genetic, SA, and Ptr-A* baselines.Sampling uses W_sampling = 5120 and beam search uses W_beam = 100 at inference.
  • Total AoI: The trained model generalizes to IoT networks with different cluster counts without retraining, and TWA*-sampling consistently achieves the lowest total AoI.At M = 25, TWA*-sampling and TWA*-beam search obtain 13134 seconds, while genetic and SA obtain 15205 and 15452 seconds, respectively.
  • Total AoI: At M = 45, TWA*-sampling achieves 42803 seconds versus 45663 seconds for Ptr-A*, a 6.3% performance gain.TWA*-sampling, beam search, and greedy decoding all outperform genetic and SA at this cluster count.
  • Oldest-packet AoI: TWA*-sampling also obtains the best AoI for the oldest packet among the evaluated decoding methods and Ptr-A*.The proposed methods reduce oldest-packet AoI relative to genetic and SA in the reported comparison.
  • Energy consumption: The proposed decoding methods use less effective UAV energy than genetic and SA, while TWA*-sampling performs best among the three TWA* variants.Effective energy includes consumption from the first visited hovering point through completion of data collection.
  • Inference time: TWA*-greedy has the shortest inference time, whereas TWA*-sampling trades longer runtime for better AoI; Ptr-A* takes 11.9 times longer at M = 20 and 16.8 times longer at M = 45.The paper attributes TWA*'s speed advantage over Ptr-A* to parallel sequence processing.
  • Threshold and AoI components: For fixed cluster size, total AoI increases as γ_th decreases because lower thresholds enlarge hovering disks and alter hovering-point positions.When M = 10, flying time exceeds hovering time across thresholds, while increasing γ_th increases the flying-time portion.
  • Threshold and AoI components: As the number of ground nodes increases, the hovering-time percentage of oldest-packet AoI rises because data collection requires more time.This trend is reported for all evaluated algorithms in the 20-cluster network.

V. CONCLUSIONS

The paper formulates AoI-oriented UAV data collection as a GTSP and solves it with a transformer-based framework combining visiting-order generation and hovering-point search. Experiments report generalized solutions, lower AoI and energy consumption than competing algorithms, and lower computation time.

  • The trajectory optimization problem jointly selects UAV hovering points and their visiting order by formulating AoI minimization as a GTSP.The objective is to minimize the total AoI of collected data in cluster-based IoT networks.
  • The proposed framework treats trajectory planning as a translation problem from the UAV-IoT network to a minimum-total-AoI UAV trajectory.The transformer generates the visiting order, while weighted A* finds hovering points.
  • Reinforcement learning trains the model to learn a trajectory planning policy.The trained policy is evaluated through comprehensive experiments.
  • The learned policy generalizes to IoT networks with different numbers of ground clusters without retraining.
  • Compared with other algorithms, three decoding methods reduce total AoI, oldest-packet AoI, effective UAV energy consumption, and computation time.

APPENDIX A PROOF OF LEMMA 1

The appendix proves that, for fixed UAV altitude, the relevant received-signal expression decreases with horizontal distance. Therefore, the SNR threshold defines a maximum feasible communication distance for each cluster-device pair.

  • For fixed altitude H, the path-loss-related term increases with R(c_m,b_m), while the elevation angle decreases with horizontal distance.
  • Because ξ_LoS < ξ_NLoS, the combined expression is monotonically decreasing with respect to R(c_m,b_m) for fixed H.
  • When the SNR γ_c_m reaches threshold γ_th, the maximum feasible distance R* is obtained.
  • A UAV can successfully receive data from b_m for cluster c_m whenever R(c_m,b_m) ≤ R*.
Loading 2401.02425v1…