PaperlayerView exact revision on arXiv

Source-linked AI summary

UAV Trajectory Planning in Wireless Sensor Networks for Energy Consumption Minimization by Deep Reinforcement Learning

Botao Zhu, Ebrahim Bedeer, Ha H. Nguyen, Robert Barton, Jerome Henry

arXiv:2108.00354v1eess.SYcs.LG

TL;DR

The paper addresses total energy minimization for UAV data collection in clustered wireless sensor networks by jointly choosing cluster heads and their visiting order. It proposes Ptr-A*, which combines a pointer network with A* search and is trained through actor-critic reinforcement learning without labeled solutions. Models trained on 20 or 40 clusters generalize to networks with different cluster counts, and the method outperforms the two baseline techniques in reported energy-consumption evaluations.

  • Problem

    The paper investigates minimizing total UAV-WSN energy by jointly selecting cluster heads and planning the UAV’s visiting order in clustered WSNs.

  • Method

    Ptr-A* uses a pointer network to determine visiting order and A* search to select cluster heads, with parameters trained by actor-critic reinforcement learning.

  • Results

    The trained models generalize to different numbers of clusters without retraining and outperform two baseline techniques in reported energy-consumption evaluations.

  • Takeaways & Limitations

    The proposed DRL method produces better UAV trajectories across varied cluster counts while offering an appealing balance between performance and complexity.

Abstract

from arXiv · show

Unmanned aerial vehicles (UAVs) have emerged as a promising candidate solution for data collection of large-scale wireless sensor networks (WSNs). In this paper, we investigate a UAV-aided WSN, where cluster heads (CHs) receive data from their member nodes, and a UAV is dispatched to collect data from CHs along the planned trajectory. We aim to minimize the total energy consumption of the UAV-WSN system in a complete round of data collection. Toward this end, we formulate the energy consumption minimization problem as a constrained combinatorial optimization problem by jointly selecting CHs from nodes within clusters and planning the UAV's visiting order to the selected CHs. The formulated energy consumption minimization problem is NP-hard, and hence, hard to solve optimally. In order to tackle this challenge, we propose a novel deep reinforcement learning (DRL) technique, pointer network-A* (Ptr-A*), which can efficiently learn from experiences the UAV trajectory policy for minimizing the energy consumption. The UAV's start point and the WSN with a set of pre-determined clusters are fed into the Ptr-A*, and the Ptr-A* outputs a group of CHs and the visiting order to these CHs, i.e., the UAV's trajectory. The parameters of the Ptr-A* are trained on small-scale clusters problem instances for faster training by using the actor-critic algorithm in an unsupervised manner. At inference, three search strategies are also proposed to improve the quality of solutions. Simulation results show that the trained models based on 20-clusters and 40-clusters have a good generalization ability to solve the UAV's trajectory planning problem in WSNs with different numbers of clusters, without the need to retrain the models. Furthermore, the results show that our proposed DRL algorithm outperforms two baseline techniques.

I. INTRODUCTION

The paper targets total UAV-WSN energy minimization by jointly selecting cluster heads and planning the UAV’s trajectory in clustered WSNs. It proposes Ptr-A*, a pointer-network and A*-based deep reinforcement learning approach trained without labeled solutions.

  • UAVs can serve as mobile sinks that collect data from cluster heads, reducing ground-node energy compared with long-distance or multi-hop transmission.
  • The paper addresses total energy consumption of both UAVs and ground devices, a clustered-WSN objective that prior work had not well researched.
  • The optimization jointly selects one cluster head from each predetermined cluster and plans the UAV’s visiting order, because both choices affect energy consumption.
  • Ptr-A* uses a pointer network to determine cluster visiting order and A* search to select cluster heads, outputting the UAV trajectory.
  • The model is trained with self-driven reinforcement learning using reward calculation on small-scale cluster instances, avoiding expensive high-quality labels.
  • The proposed method is designed to generalize across different numbers of clusters without retraining and to improve energy consumption and computation-time performance against baselines.

II. SYSTEM MODEL AND PROBLEM FORMULATION

The system models one rotary-wing UAV collecting data from one selected cluster head per predetermined cluster and returning to its start position. The formulation accounts for channel, hovering, flight, and route constraints in the UAV’s energy model.

  • II. SYSTEM MODEL AND PROBLEM FORMULATION: The network contains K predetermined clusters with N nodes each; one node per cluster is selected as the cluster head, and the UAV visits the corresponding hovering positions.
  • II. SYSTEM MODEL AND PROBLEM FORMULATION: Each cluster head’s hovering position is directly above it, so the UAV trajectory is a permutation of the start/end position and K target hovering positions.
  • A. Channel Model: The channel model uses a line-of-sight probability depending on environment and elevation angle, with the non-line-of-sight probability defined as its complement.
  • A. Channel Model: Average path loss combines line-of-sight and non-line-of-sight excessive losses, and the data rate depends on bandwidth, noise spectral density, and cluster-head transmit power.
  • B. UAV’s Energy and Trajectory Model: The UAV operates in flying-hovering mode, with communication-related and hover-related energy at each hovering position.
  • B. UAV’s Energy and Trajectory Model: Hovering energy is modeled as hovering time multiplied by the sum of hovering and communication power, with hovering time set equal to data transmission time.
  • B. UAV’s Energy and Trajectory Model: Flight energy is determined by the UAV’s speed-dependent horizontal movement power and the total flight time over the closed route.
  • B. UAV’s Energy and Trajectory Model: Route constraints require the UAV to enter and leave each position once, eliminate sub-trajectories, and form one trajectory covering all cluster heads.

C. Ground Network and Energy Model

Ground-network energy comprises member-node communication with cluster heads and cluster-head transmission to the UAV. The model uses a first-order radio formulation for member-to-cluster-head transmission and aggregates energy over a complete collection task.

  • All nodes can act as cluster heads, remain static after deployment, and transmit periodically to their cluster head before cluster heads forward data to the UAV.
  • The UAV connects to at most one cluster head simultaneously, so neighboring cluster heads do not interfere.
  • Member-node transmission energy includes transmitter circuitry and a power amplifier modeled by free-space or multipath propagation according to a distance threshold.
  • The receiving cluster head also consumes energy when receiving each member node’s l-bit message.
  • Each cluster head consumes additional energy to transmit its aggregated data to the UAV.
  • Total ground-network energy sums member-to-cluster-head communication and cluster-head-to-UAV transmission across the complete data collection task.

D. Problem Formulation for UAV’s Trajectory

The formulation minimizes weighted UAV and ground-network energy by jointly selecting cluster heads and planning their visiting order. It is a constrained combinatorial optimization problem that is NP-hard.

  • D. Problem Formulation for UAV’s Trajectory: The objective combines total ground-network energy and UAV energy through an adjustable weighting coefficient ω.The first term represents ground-network consumption, while the second represents UAV consumption.
  • D. Problem Formulation for UAV’s Trajectory: The optimization jointly selects cluster heads from predetermined clusters and designs the UAV’s visiting order.
  • D. Problem Formulation for UAV’s Trajectory: The resulting problem is a constrained combinatorial optimization problem and is NP-hard.
  • D. Problem Formulation for UAV’s Trajectory: Exact methods can theoretically find optimal solutions, but their computation complexity becomes prohibitive for large-scale combinatorial problems.
  • D. Problem Formulation for UAV’s Trajectory: Heuristics provide problem-independent optimization guidelines but generally cannot guarantee globally optimal solutions.

2) Heuristics:

The trajectory decision is represented as a sequence-to-sequence problem, and a pointer network models cluster selection and visiting order. Its attention-based decoder assigns probabilities to unvisited input items.

  • 2) Heuristics:: Given the start position and all clusters, the model outputs a permutation representing the UAV’s visiting order.The output sequence T contains the indexed items placed at successive positions.
  • 2) Heuristics:: In the three-cluster example, the encoder receives the start position and clusters, and successive decoder outputs produce the visiting order.
  • 2) Heuristics:: The output-sequence probability is factorized into conditional probabilities, with a stochastic policy selecting the next cluster based on prior decisions.
  • 2) Heuristics:: The pointer network uses attention to choose items from its input sequence as outputs.
  • 2) Heuristics:: LSTM encoder cells transform the start position and clusters into high-dimensional vectors to capture useful features and long-term dependencies.
  • 2) Heuristics:: The decoder uses LSTM hidden states and attention scores to select the next visiting decision, while excluding previously visited items.

3) A* search:

A* converts the predicted cluster order into a layered search graph and finds a minimum-cost trajectory by evaluating accumulated and estimated energy costs.

  • 3) A* search:: The decoder sequence defines a layered graph whose layers correspond to clusters, with the start and end positions as boundary layers.
  • 3) A* search:: A* searches this graph for a path with the smallest total weighted UAV-WSN energy consumption.
  • 3) A* search:: For each candidate node, g(m) is the exact energy already consumed and h(m) estimates UAV energy needed to reach the end.
  • 3) A* search:: The next node is selected using the lowest f(m) value among candidate nodes.
  • 3) A* search:: The algorithm maintains OPEN and CLOSED lists, examines neighbors in adjacent layers, and stores parent pointers for path reconstruction.
  • 3) A* search:: The search algorithm takes T as input and returns the trajectory and its minimum energy consumption.

B. Parameters Optimization with Reinforcement Learning

The model parameters are trained with model-free actor-critic reinforcement learning rather than supervised learning because high-quality labeled trajectories are expensive to obtain. The environment state includes cluster coordinates, UAV location, and current energy consumption.

  • B. Parameters Optimization with Reinforcement Learning: Actor-critic reinforcement learning trains the Ptr-A* parameters from samples without requiring expensive high-quality labeled trajectories.
  • B. Parameters Optimization with Reinforcement Learning: The training procedure initializes actor and critic networks with random weights and samples problem instances from a training set.
  • B. Parameters Optimization with Reinforcement Learning: For each batch instance, Ptr-A* produces an energy value and trajectory while the critic estimates the instance value.
  • B. Parameters Optimization with Reinforcement Learning: The UAV is treated as an agent that takes a sequential action set in a given environment state.
  • B. Parameters Optimization with Reinforcement Learning: The state contains all cluster coordinates, the UAV’s current location, and current UAV-WSN energy consumption.

1) State:

The method formulates action selection and energy minimization within an actor–critic DRL framework, using Ptr-A* as the actor and a critic to stabilize training. Experiments use controlled clustered-WSN settings and specified implementation parameters.

  • Each action selects the next cluster and its cluster head, with A* determining the cluster-head choice.
  • The reward is defined as the negative total energy consumption, directing DRL toward lower-energy solutions.
  • The actor network is Ptr-A*, while the critic estimates reward baselines to reduce gradient variance and accelerate learning.
  • Policy gradients optimized with stochastic gradient descent use REINFORCE, with Monte Carlo sampling approximating the gradient.
  • Critic parameters are trained by stochastic-gradient descent on mean squared prediction error, and Adam updates actor and critic parameters iteratively.
  • Experiments use a 2 km × 2 km ground network, a UAV start point at (0 m, 0 m), minibatches of 512, and 128-unit LSTM encoder and decoder cells.
  • Cluster nodes follow Gaussian distributions, with models trained separately on 20-cluster and 40-cluster instances.

B. Decoding Search Strategies at Inference

At inference, Ptr-A* searches over feasible cluster access sequences using greedy, sampling, or active-search decoding. These strategies trade search effort and parameter refinement against solution quality.

  • B. Decoding Search Strategies at Inference: The decoder outputs cluster access sequences at inference, and three search strategies explore feasible alternatives.
  • Greedy search: Greedy search selects the highest-probability cluster at each decoding step and is labeled DRL-greedy.
  • Sampling search: Sampling draws M candidate solutions from Pθ(·|G) and selects the candidate with minimum expected energy; simulations use M = 51200.
  • Active search: Active search samples candidate solutions for one test instance and refines Ptr-A* parameters with policy gradients during inference.
  • Active search: Active search is implemented through repeated solution sampling, energy evaluation, comparison with the current solution, and final return of the selected trajectory and energy.

C. Small-Scale Clusters

The proposed DRL method reduces UAV-WSN energy consumption across small- and large-scale cluster tests, with active search generally producing the strongest results. Performance improves over NN and genetic baselines as cluster count grows, although stronger active search requires longer inference time.

  • Small-scale trajectory comparison: DRL-active-10240 produced the shortest trajectory, 8693 m, versus 9241 m for DRL-greedy on a 25-cluster instance.The comparison uses ω = 0, so the objective reflects UAV flying distance.
  • Generalization and runtime: The trained models generalized across cluster counts, but DRL-active-10240 achieved the best energy results at the cost of the longest inference time.Its longer runtime results from additional parameter-update iterations during active search.
  • Small-scale energy comparison: At K = 30, NN and genetic consumed about 11% more energy than DRL-active-10240, while DRL-sampling and DRL-greedy reduced the gaps to 8% and 7%.
  • Small-scale energy comparison: At K = 50, genetic consumed around 33% more energy than DRL-active-10240, while NN consumed around 21% more.
  • Large-scale clusters: On large-scale instances, the 40-clusters model outperformed the 20-clusters model, with the advantage increasing as the number of clusters grew.The 40-clusters model was therefore more suitable for large-scale trajectory planning.

APPENDIX A EXAMPLE OF ATTENTION MECHANISM

The appendix illustrates how the pointer-network decoder converts latent memory states into an output sequence by selecting the element with the highest conditional probability at each decoding step. Repeating this process produces the complete decoded sequence.

  • Attention mechanism: The input sequence G is transformed into latent memory states E, which are then provided to the decoder network.The example uses G = {b0, G1, G2, G3} and E = {e0, e1, e2, e3}.
  • Attention mechanism: At decoding step 0, the decoder computes correlations between all elements of E and the start tag vgo.These correlations are used to derive conditional probabilities for the candidate elements.
  • Attention mechanism: The softmax function normalizes the decoder scores into conditional probabilities for the available elements.The illustrative probabilities at the first step are 0.6, 0.1, 0.1, and 0.2.
  • Attention mechanism: Because e0 has the highest conditional probability at step 0, the decoder outputs the first element b0.The next decoding step evaluates b0 against the remaining latent states.
  • Attention mechanism: At step 1, the same procedure assigns probabilities to the remaining elements, selecting G3 because e3 has the maximum conditional probability.The example assigns probabilities 0.2, 0.1, and 0.7 to the remaining candidates.
  • Attention mechanism: Repeating the selection process yields the full decoder output sequence {b0, G3, G1, G2}.The sequence is also represented as {π0, π1, π2, π3}.
Loading 2108.00354v1…