Flight Time Minimization of UAV for Data Collection Over Wireless Sensor Networks

Jie Gong, Tsung-Hui Chang, Chao Shen, Xiang ChenIEEE JSAC 2018 · DOI

TL;DR

This paper tackles the challenge of minimizing a UAV's flight time for data collection from a linear array of sensors, considering both the UAV's energy constraints and the sensors' data upload requirements. They propose a dynamic programming approach that breaks down the problem into single-sensor subproblems, optimizing UAV speed, sensor transmission power, and data collection intervals.

What Problem Does This Paper Address?

Unmanned Aerial Vehicles (UAVs) are increasingly being explored for data collection in wireless sensor networks (WSNs). Traditional WSNs often rely on multi-hop communication, which can quickly drain sensor batteries and lead to network failures. UAVs can act as mobile data collectors, offering direct communication links with potentially higher data rates due to line-of-sight channels. However, UAVs themselves are energy-constrained, and their limited flight time is a critical bottleneck. This paper addresses the problem of minimizing the total flight time for a UAV to collect a specified amount of data from a series of sensors arranged linearly, while ensuring each sensor can successfully upload its data within its energy budget. The challenge lies in jointly optimizing the UAV's trajectory, speed, and the sensors' transmission strategies.

Methods

The authors formulate the problem as a flight time minimization objective subject to data upload and energy constraints. They first analyze the single-sensor case, where they derive an optimal "water-filling" policy for sensor transmission power and use bisection search to find the optimal UAV speed. For the multi-sensor case, they cleverly reformulate the problem as a dynamic programming (DP) problem. Each stage of the DP corresponds to a sensor, and the subproblem at each stage leverages the solution from the single-sensor case. This DP approach allows for the optimization of data collection intervals, UAV speeds, and sensor transmission powers across all sensors.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Water-filling for sensors: In the single-sensor scenario, the optimal power allocation for a sensor follows a water-filling policy, a common concept in information theory, adapted here for energy and data constraints.
  • DP for sequential optimization: The problem's sequential nature (collecting from sensors one by one) makes it amenable to dynamic programming, allowing for efficient optimization across multiple sensors.
  • Interplay of speed, distance, and data: The UAV's optimal speed is found to be proportional to sensor energy budgets and inter-sensor distance, but inversely proportional to the data upload requirement. This highlights a trade-off between covering distance and efficiently transmitting data.
  • Feasibility condition: A crucial insight is the derivation of a feasibility condition for data collection, ensuring that a sensor can actually upload its required data given its energy budget and the communication channel.
  • Hovering vs. Flying: The paper distinguishes between data collection while hovering (optimal for challenging channel conditions or high data rates) and while flying (more time-efficient for longer distances). The optimal strategy dynamically chooses between these modes.

Key Results

  • The proposed DP algorithm effectively minimizes the UAV's total flight time for data collection.
  • Numerical results demonstrate that when sensors have sufficient energy, the UAV can fly at maximum speed. However, with limited energy, the UAV's speed adjusts proportionally to energy budgets and inter-sensor distance, and inversely to data requirements.
  • The paper shows that collecting data during flight can save time compared to a "hovering only" policy, even if the data rate is lower.
  • A performance gap exists between the proposed algorithm and a "hovering only" policy, with the proposed algorithm generally outperforming it, especially for larger data amounts.

Limitations and Future Work

  • Linear sensor arrangement: The current model assumes sensors are arranged in a line. Extending this to a 2D space with optimized sensor visit order is suggested as future work.
  • Ignored acceleration/deceleration: For analytical tractability, the UAV's acceleration and deceleration phases are ignored.
  • No mobility or fading: The paper assumes static sensors and does not explicitly model sensor mobility or complex channel fading effects, which are identified as interesting directions for future research.

Summary updated

BibTeX
@article{gong2018flight,
  author = {Jie Gong and Tsung-Hui Chang and Chao Shen and Xiang Chen},
  title = {{Flight Time Minimization of UAV for Data Collection Over Wireless Sensor Networks}},
  journal = {IEEE J. Sel. Areas Commun.},
  year = {2018},
  doi = {10.1109/jsac.2018.2864420},
}
Figure