Optimization of Clustering and Trajectory for Minimizing Age of Information in Unmanned Aerial Vehicle-Assisted Mobile Edge Computing Network

Huicong Shen, Die Wang, Zhen Huang, Yunjian Jia2024 · DOI

TL;DR

This paper tackles the challenge of keeping data fresh in drone-assisted mobile edge computing networks. They propose a novel algorithm that optimizes how drones group ground sensors and plan their flight paths to minimize the "age of information" – the time it takes for data to reach its destination. This is crucial for real-time applications like disaster monitoring where timely data is critical.

What Problem Does This Paper Address?

In the era of the Internet of Things (IoT), devices generate massive amounts of data. For applications like fire monitoring, this data needs to be processed quickly to enable rapid decision-making. Traditional ground-based networks can struggle with this, especially in remote areas, leading to an "energy hole" phenomenon and delayed data. Unmanned Aerial Vehicles (UAVs), or drones, offer a promising solution as mobile data collectors, especially when equipped with Mobile Edge Computing (MEC) capabilities for on-the-fly processing.

However, simply flying a drone around to collect data isn't optimal. The drone's flight path and how it groups sensors significantly impact how "fresh" the data is when it arrives. The "Age of Information" (AoI) is a key metric for data freshness, representing the time elapsed since the data was generated. Minimizing the peak AoI (the worst-case AoI across all collected data) is critical for applications where even a single piece of stale data can lead to wrong decisions. Existing approaches often struggle to balance data collection time, flight time, and the complexity of optimizing both sensor grouping (clustering) and the drone's trajectory simultaneously, especially with a large number of sensors.

Methods

The authors propose an iterative two-step algorithm called AoI-MATP (Age of Information-Minimized Association and Trajectory Planning).

  1. Clustering and CP Optimization:
    • They first formulate a complex mixed-integer non-convex optimization problem to minimize peak AoI by jointly optimizing collection points (CPs), sensor-to-CP associations, and the UAV trajectory.
  2. To tackle this, they employ the Affinity Propagation (AP) clustering algorithm to group ground sensors and determine the optimal locations for the collection points. A key innovation here is controlling the number of clusters (K) by varying a clustering parameter ($\epsilon$), allowing for a trade-off between data collection time and flight time.
  3. The AP algorithm iteratively updates "responsibility" and "availability" messages between sensors to find stable clusters and their representative CPs. The center of gravity method is then used to determine the precise CP locations.
  4. UAV Trajectory Optimization:
    • Once the CPs are established, the problem reduces to finding the optimal flight path for the UAV to visit these CPs. This is framed as a variation of the Traveling Salesperson Problem (TSP).
  5. An improved elite Genetic Algorithm (eGA) is used to find a near-optimal UAV trajectory. This algorithm uses a sequence coding approach, where the visiting sequence of CPs is represented as a chromosome. It incorporates elitist preservation, binary tournament selection, ordered crossover, shuffle indexes mutation, and a 2-OPT local optimization step to efficiently search for good solutions.

The AoI-MATP algorithm iteratively runs these two steps, adjusting the clustering parameter $\epsilon$ until the minimum peak AoI is achieved.

Datasets

Not discussed in the paper. The paper focuses on a simulated scenario with randomly distributed sensors.

Key Insights and Ideas

  • The importance of joint optimization: The paper highlights that optimizing sensor-CP associations, CP locations, and UAV trajectory simultaneously is crucial for minimizing peak AoI, rather than optimizing them in isolation.
  • Controlling cluster count via $\epsilon$: Using the $\epsilon$ parameter in AP clustering to dynamically determine the number of clusters (K) is a clever way to balance the trade-off between data collection time and flight time, directly impacting AoI.
  • eGA for efficient trajectory planning: For the TSP-like trajectory problem, the eGA provides a computationally efficient way to find near-optimal paths, which is essential for real-time applications.
  • The impact of K on AoI: The results show a non-monotonic relationship between the number of clusters (K) and peak AoI. Too few clusters lead to long collection times, while too many can increase flight time, suggesting an optimal K exists.

Key Results

  • The proposed AoI-MATP algorithm effectively minimizes the peak Age of Information in UAV-assisted MEC networks.
  • The algorithm demonstrates an excellent balance between data collection time and flight time, leading to superior performance compared to other schemes.
  • For a scenario with M=50 sensors, the optimal peak AoI was achieved with K=6 clusters, resulting in a peak AoI of 393.20 s.
  • When comparing with other schemes for M=20 sensors, the proposed algorithm achieved results comparable to exact methods (like BC and DP) but with significantly lower computational complexity and running time, especially as the number of sensors increases. For M=30, the proposed algorithm provided a good solution in an acceptable time, whereas more complex methods became infeasible.

Limitations and Future Work

  • Computational Complexity: While the proposed algorithm is more efficient than exact methods, it still relies on heuristic algorithms (AP and eGA), meaning it finds near-optimal solutions rather than guaranteed optimal ones. The computational complexity can still be a factor for very large numbers of sensors.
  • Simulation-based: The results are based on simulations, and real-world deployment might introduce additional complexities.
  • Future Work: The authors suggest extending their work to scenarios where the UAV acts as the MEC server for computation-intensive tasks, focusing on optimizing communication resource allocation to further reduce AoI and energy consumption.

Summary updated

BibTeX
@misc{shen2024optimization,
  author = {Huicong Shen and Die Wang and Zhen Huang and Yunjian Jia},
  title = {{Optimization of Clustering and Trajectory for Minimizing Age of Information in Unmanned Aerial Vehicle-Assisted Mobile Edge Computing Network}},
  year = {2024},
  doi = {10.3390/s24061742},
}
Figure