PaperlayerView exact revision on arXiv

Source-linked AI summary

Age-Optimal Trajectory Planning for UAV-Assisted Data Collection

Juan Liu, Xijun Wang, Bo Bai, Huaiyu Dai

arXiv:1804.09356v1cs.IT

TL;DR

The paper asks how to plan UAV routes that keep sensed information fresh when collecting data from wireless sensor nodes. It formulates maximum- and average-AoI objectives, maps both to shortest Hamiltonian path problems, and solves them with DP and GA methods. Simulations show that the algorithms find age-optimal or near-optimal trajectories and that the chosen AoI metric affects route design.

  • Problem

    The paper studies how to design UAV collection trajectories that minimize either the oldest sensed information or the average information age across sensor nodes.

  • Method

    The paper models collection as a weighted complete-graph routing problem, derives shortest Hamiltonian path formulations, and applies dynamic programming and genetic algorithms.

  • Results

    Simulations show that DP finds the age-optimal trajectories, while GA finds near-optimal trajectories, and AoI metrics affect UAV trajectory design.

  • Takeaways & Limitations

    UAV trajectory design can use maximum or average AoI as the optimization criterion to keep sensed data fresh in wireless sensor networks.

Abstract

from arXiv · show

Unmanned aerial vehicle (UAV)-aided data collection is a new and promising application in many practical scenarios. In this work, we study the age-optimal trajectory planning problem in UAV-enabled wireless sensor networks, where a UAV is dispatched to collect data from the ground sensor nodes (SNs). The age of information (AoI) collected from each SN is characterized by the data uploading time and the time elapsed since the UAV leaves this SN. We attempt to design two age-optimal trajectories, referred to as the Max-AoI-optimal and Ave-AoI-optimal trajectories, respectively. The Max-AoI-optimal trajectory planning is to minimize the age of the `oldest' sensed information among the SNs. The Ave-AoI-optimal trajectory planning is to minimize the average AoI of all the SNs. Then, we show that each age-optimal flight trajectory corresponds to a shortest Hamiltonian path in the wireless sensor network where the distance between any two SNs represents the amount of inter-visit time. The dynamic programming (DP) method and genetic algorithm (GA) are adopted to find the two different age-optimal trajectories. Simulation results validate the effectiveness of the proposed methods, and show how the UAV's trajectory is affected by the two AoI metrics.

I. INTRODUCTION

The paper studies how AoI metrics affect UAV trajectory design for sequential data collection from wireless sensor nodes. It introduces Max-AoI and Ave-AoI objectives and develops DP and GA approaches after relating the trajectories to shortest Hamiltonian paths.

  • I. INTRODUCTION: UAV mobility and low-altitude LoS links support energy-saving data collection from ground sensor nodes.The paper situates trajectory design within prior work on efficiency, fairness, reliability, and energy-efficient UAV-assisted collection.
  • I. INTRODUCTION: AoI measures the time elapsed since the freshest delivered information and is important for delay-sensitive applications.Prior studies mainly analyzed or optimized AoI-based scheduling, transmission, and update policies.
  • I. INTRODUCTION: The paper designs trajectories that minimize either the oldest sensed information or the average age across sensor nodes.These objectives are named the Max-AoI-optimal and Ave-AoI-optimal trajectories, respectively.
  • I. INTRODUCTION: The illustrative UAV route visits five sensor nodes sequentially before returning to the data center.The example trajectory is v0 →v1 →v4 →v3 →v5 →v2 →v0.
  • I. INTRODUCTION: Each age-optimal trajectory maps to a shortest Hamiltonian path, with inter-node distances represented by elapsed collection time.The paper uses dynamic programming for recursive optimization and a genetic algorithm for near-optimal search in larger networks.

II. SYSTEM MODEL

The system models a UAV that visits every sensor node once, collects timestamped packets over LoS links, and returns to the data center. AoI is determined by each node’s collection time and the elapsed flight and uploading intervals along the trajectory.

  • II. SYSTEM MODEL: The network is a complete graph containing the data center and M sensor nodes, with edge weights equal to Euclidean inter-node distances.The UAV returns to the data center after collecting data from all sensor nodes.
  • II. SYSTEM MODEL: The UAV flies at fixed altitude and constant velocity along a prescheduled route that visits each sensor node exactly once.The route has the form v0 →v(1) →v(2) →···→v(M) →v0.
  • II. SYSTEM MODEL: Each visited node immediately establishes a LoS link, timestamps a sensed packet, and transmits it to the UAV.The packet has length Lp, and sensing time is assumed negligible.
  • II. SYSTEM MODEL: The UAV’s collection time depends on packet length and uploading rate, while travel time between nodes equals distance divided by velocity.The channel gain and transmission rate are determined by altitude, bandwidth, noise power, and node transmit power.
  • II. SYSTEM MODEL: A node’s information age is zero before its visit and equals elapsed time after sampling, so its final AoI is a function of the trajectory.The paper formulates separate optimization problems for maximum and average sensing-information age.

III. AOI-OPTIMAL TRAJECTORY PLANNING

The paper shows that both Max-AoI-optimal and Ave-AoI-optimal UAV trajectories can be formulated as shortest Hamiltonian path problems.

  • III. AOI-OPTIMAL TRAJECTORY PLANNING: Max-AoI-optimal and Ave-AoI-optimal flight trajectories are two shortest Hamiltonian paths in the wireless sensor network.The result follows from analyzing the properties of the two AoI optimization problems.

A. Max-AoI-optimal Trajectory

For any route, the first visited sensor has the largest AoI, reducing Max-AoI optimization to finding a shortest Hamiltonian path measured by inter-visit times.

  • A. Max-AoI-optimal Trajectory: The AoI values decrease monotonically with visit order: X1(u) > X2(u) > ··· > XM(u).Therefore, the first visited node always determines the maximum AoI.
  • A. Max-AoI-optimal Trajectory: The Max-AoI-optimal trajectory is a shortest Hamiltonian path whose edge distances equal the elapsed times ηi,j between successive data collection actions.A Hamiltonian path visits every sensor exactly once before returning to the data center.
  • A. Max-AoI-optimal Trajectory: Minimizing the maximum AoI is equivalent to minimizing the first node’s AoI, which equals the length of the corresponding Hamiltonian path.The path starts at the first sensor, visits every other sensor once, and returns to the data center.

B. Ave-AoI-optimal Trajectory Planning

The Ave-AoI-optimal trajectory minimizes average information age by reformulating the problem as a stage-weighted shortest Hamiltonian path.

  • The Ave-AoI-optimal trajectory is a stage-weighted shortest Hamiltonian path returning to the data center.Its minimum average AoI equals the stage-weighted length of that path.
  • The average AoI is re-expressed as the stage-weighted length of the UAV’s trajectory.The weighting reflects the position of each inter-node segment in the visitation sequence.
  • The resulting optimization problem seeks the minimum weighted path cost over trajectories that visit every sensor node exactly once.The trajectory starts at the first sensor node and ends at the data center after visiting the remaining nodes.
  • Each distance between consecutive nodes is multiplied by a stage factor determined by the node’s position in the trajectory.The factor is expressed using k and M, with η(k),(k+1) representing the corresponding time parameter.

IV. ALGORITHM DESIGN FOR AOI-OPTIMAL TRAJECTORY PLANNING

The algorithm-design section presents a unified procedure for computing both age-optimal trajectories using dynamic programming and genetic algorithms.

  • The proposed algorithm design uses DP and GA to find the Max-AoI-optimal and Ave-AoI-optimal trajectories.Algorithm 1 is identified as the DP-based age-optimal trajectory-planning procedure.
  • The DP procedure takes the network topology and system parameters as inputs, then computes elapsed collection times between every pair of nodes.The parameters include flight velocity, altitude, channel, bandwidth, transmit power, and noise terms.
  • For each candidate starting node and subset of unvisited nodes, DP calculates minimum path costs recursively and then traces back the optimal trajectory.The procedure evaluates subset states, computes the minimum AoI, selects the first node, and reconstructs the route.

A. DP-based AoI-Optimal Trajectory Planning

The DP method solves both AoI objectives through recursive path-cost calculations, using ordinary costs for maximum AoI and weighted costs for average AoI.

  • Max-AoI-optimal case: For the Max-AoI case, f(i, S) is the minimum cost of a path starting at node vi, visiting every node in S once, and returning to v0.The recurrence uses ηi,0 for an empty set and minimizes ηi,k + f(k, S −{k}) otherwise.
  • Max-AoI-optimal case: The Max-AoI-optimal trajectory is exactly the shortest Hamiltonian path achieving the minimum maximum-age cost.The cost function f(i, V −{vi}) is computed recursively by the DP recurrence.
  • Ave-AoI-optimal case: For the Ave-AoI case, g(i, S) denotes the minimum weighted cost of a path that visits all nodes in S once and returns to v0.The weighting depends on the number of nodes remaining unvisited.
  • Ave-AoI-optimal case: The Ave-AoI-optimal trajectory is the shortest Hamiltonian path under stage-weighted distances.The stage weight is represented by 1−|S|/M, where |S| is the number of remaining unvisited nodes.
  • Algorithm implementation: The DP algorithm computes ηi,j, records minimum path costs and successor nodes, and reconstructs both optimal trajectories by table traceback.The Ave-AoI solution uses weighted costs g(i, S) rather than the unweighted costs f(i, S).
  • Algorithm implementation: The DP method has computational complexity about O(M · 2^M), which becomes intolerable as the number of sensor nodes grows.A genetic algorithm is introduced to address large-scale networks.

B. GA-based AoI-Optimal Trajectory Planning

The GA-based method searches over feasible Hamiltonian paths using fitness evaluation, selection, crossover, mutation, and iterative population replacement.

  • Each GA chromosome represents a feasible Hamiltonian path, and the initial population contains Nc such chromosomes.The generation index starts at zero.
  • The fitness of each chromosome is evaluated from its path length, defined by maximum age or average age depending on the optimization objective.The path-length quantities are normalized using the maximum and minimum lengths in the current population.
  • Parent chromosomes are selected proportionally, while partially mapped crossover exchanges path segments and mutation swaps two nodes.Higher-fitness chromosomes, corresponding to shorter paths, have greater selection probability.
  • The population is repeatedly replaced with new chromosomes until the generation count reaches Ng.Otherwise, fitness evaluation and genetic operations continue for another generation.
  • The final chromosome with maximum fitness is selected as the optimal flight trajectory for either AoI objective.The same GA framework is used for both Max-AoI-optimal and Ave-AoI-optimal trajectories.

V. SIMULATION RESULTS

Simulations compare DP, GA, and greedy methods for Max-AoI- and Ave-AoI-optimal UAV trajectories under specified network settings. DP achieves the best overall AoI, while GA closely approaches minima and greedy is weakest, with metric-specific trajectory differences.

  • Simulation setup: The simulations use randomly located SNs within a 1000m-radius area, with UAV altitude 50m and velocity 20m/s.The network includes one data center, one UAV, and M SNs; the UAV visits each SN exactly once.
  • Algorithm comparison: For M = 14, DP performs best for the minimum AoI X∗, while GA finds near-optimal trajectories and greedy produces the largest AoIs.DP compares candidate Hamiltonian paths, whereas GA searches intelligently and greedy selects locally nearest nodes.
  • Max-AoI trajectory: For Max-AoI optimization, DP may not minimize every individual node age because globally optimal Hamiltonian paths need not have locally optimal parts.The DP solution has larger X∗_i than GA for i = 4, · · · , 12 and larger than greedy for i = 10, · · · , 14.
  • Ave-AoI trajectory: For Ave-AoI optimization, GA and DP produce closely matched node ages that remain below those obtained by the greedy algorithm.This contrasts with the individual-node behavior observed for the Max-AoI-optimal trajectory.
  • Metric-specific effects: Under GA, the Max-AoI-optimal trajectory has smaller X∗_1, whereas the Ave-AoI-optimal trajectory has much smaller average AoI.Under greedy, both optimized trajectories are identical because nearest-neighbor selection is used for either metric.

VI. CONCLUSIONS

The paper formulates Max-AoI and Ave-AoI trajectory planning for UAV-enabled data collection and represents both solutions as shortest Hamiltonian paths. DP and GA algorithms efficiently seek these trajectories, while simulations compare them with greedy search.

  • The study formulates Max-AoI-optimal and Ave-AoI-optimal trajectory planning for UAV-enabled wireless sensor data collection.
  • Both age-optimal trajectories correspond to shortest Hamiltonian paths in a weighted complete graph.
  • DP and GA algorithms find the two trajectory types in a unified way, with simulations comparing their efficiency against a greedy baseline.
  • The proposed trajectory designs help keep sensed data fresh in wireless sensor networks under the two AoI metrics.
Loading 1804.09356v1…