November 4, 2019 feature
Designing unmanned aerial vehicle trajectories for energy minimization
A team of researchers at the University of Luxembourg and the Ontario Tech University have recently proposed a new approach to design trajectories for energy-efficient unmanned aerial vehicle (UAV)-enabled wireless communications. Their paper, prepublished on arXiv, specifically focuses on cases in which an UAV acts as a flying base station (BS) to serve ground users (GSs) within some predetermined latency constraints.
"Our goal is to design the UAV trajectory to minimize the total energy consumption while satisfying the RT requirement and energy budget, which is accomplished via jointly optimizing the trajectory and UAV's velocities along subsequent hops," the researchers wrote in their paper.
Optimizing a UAV's trajectory and its velocities together can be somewhat difficult to achieve. To do so, the researchers developed an approach that carries out two consecutive steps.
Their approach entails the use of two distinct algorithms, a heuristic search and a dynamic programming (DP) algorithm. Heuristic search methods work by evaluating all available information at every step and deciding what path to follow by ranking options available.
Dynamic programming, on the other hand, is an approach for solving problems with overlapping 'sub-problems." It works by tackling individual sub-problems only once and saving the results of these analyses, in order to use them again if the same sub-problem is encountered in the future.
The researchers used their heuristic search and dynamic programming algorithms to attain a feasible set of trajectories for UAVs that do not violate the ground user's latency constraints. The task of finding these trajectories is solved as if it were a so-called traveling salesman problem with time windows (TSPTW). TSPTW is an algorithmic problem used in computer science that entails finding a minimum-cost path for a salesman who wants to travel and visit each of a set of cities exactly once within a specific time window.
The trajectories suggested by the algorithms were subsequently compared to those attained using exhaustive search techniques and when approaching the task as the traveling salesman problem (TSP); an algorithmic problem in which one needs to come up with the optimal routes for a salesman who wants to visit a specific set of cities without any specific time requirements.
"While the exhaustive algorithm achieves the best performance at a high computation cost, the heuristic algorithm exhibits poorer performance with low complexity," the researchers explained in their paper. "As a result, the DP is proposed as a practical trade-off between the exhaustive and heuristic algorithms."
In addition to the two algorithms for finding optimal UAV trajectories, the researchers also proposed a technique for energy minimization. This method works by jointly optimizing the UAV's velocities and subsequent hops.
When the researchers evaluated their algorithms they found that they are highly effective, outperforming existing state-of-the-art techniques both in terms of energy consumption and outage performance. In the future, the new approach they proposed could help to design better trajectories for energy minimization in applications that involve UAV-enabled wireless communications with latency constraints. In addition, their work could pave the way for future studies aimed at developing new tools to enhance the performance of UAV communication networks.
© 2019 Science X Network