PaperlayerView exact revision on arXiv

Source-linked AI summary

Reinforcement Learning in Multiple-UAV Networks: Deployment and Movement Design

Xiao Liu, Yuanwei Liu, Yue Chen

arXiv:1904.05242v2eess.SP

TL;DR

The paper addresses QoE-driven 3D deployment and movement of multiple UAVs serving mobile users, formulating sum-MOS maximization as a non-convex, NP-hard problem. It combines GAK-means clustering with Q-learning for deployment and movement, and reports fast convergence and better low-complexity deployment performance than K-means and IGK.

  • Problem

    The central problem is maximizing ground users’ sum MOS through joint multi-UAV 3D deployment and dynamic movement, an NP-hard task.

  • Method

    The method uses GAK-means for initial cell partitioning, followed by Q-learning for 3D deployment and roaming-user movement.

  • Results

    The proposed algorithms show fast convergence, and Q-learning-based deployment outperforms K-means and IGK with low complexity.

  • Takeaways & Limitations

    The framework provides a QoE-driven approach for deploying and dynamically moving multiple UAVs in 3D space while serving mobile users.

Abstract

from arXiv · show

A novel framework is proposed for quality of experience (QoE)-driven deployment and dynamic movement of multiple unmanned aerial vehicles (UAVs). The problem of joint non-convex three-dimensional (3D) deployment and dynamic movement of the UAVs is formulated for maximizing the sum mean opinion score (MOS) of ground users, which is proved to be NP-hard. In the aim of solving this pertinent problem, a three-step approach is proposed for attaining 3D deployment and dynamic movement of multiple UAVs. Firstly, genetic algorithm based K-means (GAK-means) algorithm is utilized for obtaining the cell partition of the users. Secondly, Q-learning based deployment algorithm is proposed, in which each UAV acts as an agent, making their own decision for attaining 3D position by learning from trial and mistake. In contrast to conventional genetic algorithm based learning algorithms, the proposed algorithm is capable of training the direction selection strategy offline. Thirdly, Q-learning based movement algorithm is proposed in the scenario that the users are roaming. The proposed algorithm is capable of converging to an optimal state. Numerical results reveal that the proposed algorithms show a fast convergence rate after a small number of iterations. Additionally, the proposed Q-learning based deployment algorithm outperforms K-means algorithms and Iterative-GAKmean (IGK) algorithms with a low complexity.

I. INTRODUCTION

UAV-assisted communication is positioned as a flexible response to demanding wireless-service scenarios, while prior work leaves multi-UAV 3D deployment, QoE optimization, and user-driven mobility insufficiently addressed. The paper introduces a QoE-driven framework using GAK-means and Q-learning for deployment and movement.

  • A. Related Works: UAV-assisted networks exploit agility, low deployment cost, line-of-sight propagation, and mobility for rapid, flexible wireless service.They are presented for service recovery after infrastructure damage, cellular offloading, and adapting positions to users’ real-time locations.
  • A. Related Works: Existing research has mainly emphasized static deployment, two-dimensional multi-UAV placement, or single-UAV mobility with static users.The paper contrasts this literature with mobile-user service scenarios requiring UAV movement without fixed destinations.
  • A. Related Works: Prior UAV-assisted communication studies often omit QoE and the specific requirements of different ground users.The paper uses QoE to represent user satisfaction rather than focusing only on communication-system objectives described in prior work.
  • B. Our New Contributions: The paper formulates multi-UAV 3D deployment and dynamic movement to improve users’ QoE, serving mobile users with MOS as the satisfaction measure.The framework jointly optimizes UAV placement and movement in three-dimensional space.
  • B. Our New Contributions: A three-step solution combines GAK-means cell partitioning, Q-learning-based 3D deployment, and Q-learning-based dynamic movement.The deployment algorithm addresses initially static users, while the movement algorithm addresses roaming users and learns policy through trial and mistake.
  • B. Our New Contributions: The proposed algorithms are reported to converge quickly, while Q-learning-based deployment outperforms K-means and IGK algorithms with low complexity.The paper presents this as a solution to the NP-hard 3D deployment and movement problem.

C. Organization

The paper organizes its system and signal model around multi-UAV aerial base stations serving clustered users in three-dimensional space. It then specifies propagation, resource allocation, connectivity constraints, and the document’s section sequence.

  • C. Organization: The paper is organized into problem formulation, static-user deployment, roaming-user movement, numerical results, and conclusions.Section II presents the model, Sections III and IV develop deployment and movement methods, and Section V reports results.
  • B. Signal Model: The service area is divided into N disjoint user clusters, with one UAV acting as an aerial base station in each cluster.Each user belongs to exactly one cluster, and UAVs connect to the core network through satellite or terrestrial infrastructure.
  • B. Signal Model: Each UAV position combines horizontal coordinates q_n(t) = [x_n(t), y_n(t)]^T with an altitude h_n(t) constrained to [h_min, h_max].The model represents UAV trajectories over the considered time horizon.
  • B. Signal Model: Bandwidth and transmit power are allocated uniformly among each UAV’s associated users, while different clusters use different spectrum.The received SNR must meet each user’s target γ_kn.
  • B. Signal Model: The signal model assumes constant UAV velocity, and the paper leaves changeable-velocity scenarios for future work.This is an explicit modeling boundary for the movement setting.
  • B. Signal Model: Higher altitude increases path loss but improves line-of-sight probability, creating a trade-off that affects reliable service and transmit-power requirements.The altitude bounds are linked to user distance, maximum transmit power, and environmental channel parameters.

C. Quality-of-Experience Model

The QoE model uses mean opinion score (MOS) to represent user satisfaction for web browsing, linking satisfaction to transmission rate and delay. The objective aggregates users’ MOS over the considered period.

  • C. Quality-of-Experience Model: The paper introduces QoE because users have different transmit-rate requirements, making a satisfaction-oriented model necessary.The QoE model is used in the UAV-assisted communication setting described by the paper.
  • C. Quality-of-Experience Model: QoE depends on preferences, expectations, experiences, behavior, cognitive abilities, service attributes, and environment.MOS is adopted as the measure of users’ QoE.
  • C. Quality-of-Experience Model: The MOS scale defines excellent, very good, good, fair, and poor states, with scores ranging from 1 to 4.5.The five ordinal QoE alternatives are assigned the paper’s stated score ranges.
  • C. Quality-of-Experience Model: For web browsing, the model ignores the delay-specific MOS component and expresses MOS as a function of transmission-rate-related delay.The constants C1 and C2 are set to 1.120 and 4.6746 from web-browsing experiments.
  • C. Quality-of-Experience Model: The objective sums each user’s MOS over period T_s, while the framework can accommodate other MOS models and applications.The paper also notes that moving toward some users can reduce MOS for users farther from the UAVs.

D. Problem Formulation

The optimization jointly selects UAV positions and associated-user assignments to maximize aggregate MOS under altitude, SINR, and transmit-power constraints. Because user mobility changes transmission rates and optimal positions, the formulation also embeds dynamic movement design.

  • D. Problem Formulation: The optimization chooses each UAV’s horizontal position and altitude at every timeslot to maximize users’ sum MOS.The decision variables include {x_n(t), y_n(t), h_n(t)} for all UAVs and timeslots.
  • D. Problem Formulation: Each user is assigned to one cluster, while the formulation enforces UAV altitude, minimum SINR, and transmit-power constraints.The constraints are interpreted after fixing bandwidth and power allocation.
  • D. Problem Formulation: User movement changes received transmission rates, requiring UAVs to travel according to real-time user locations to maintain QoE.Thus, the sum-MOS maximization inherently includes dynamic UAV movement design.
  • D. Problem Formulation: The deployment objective is non-convex over UAV horizontal coordinates and altitudes.This property is stated in Theorem 1.
  • D. Problem Formulation: Altitude affects sum MOS through its simultaneous effects on UAV-user distance, line-of-sight probability, path loss, and required transmit power.The sum MOS also depends on UAV transmit power, number, and horizontal and vertical positions.
  • D. Problem Formulation: The combined cell-partition and position-search problem is NP-hard, even when only user clustering is considered.The paper motivates efficient GAK-means and Q-learning methods instead of exhaustive search.

III. THREE-DIMENSIONAL DEPLOYMENT OF THE UAVS

The deployment problem is reduced to user-region segmentation and UAV placement, with NP-hardness established even for user clustering. GAK-means addresses clustering while K-means provides a low-complexity baseline but is sensitive to initialization and may reach only a local minimum.

  • Three-Dimensional Deployment of the UAVs: The considered static-user setting allows UAV altitude to vary while bandwidth and transmit power are allocated uniformly among each UAV’s users.
  • The deployment problem is NP-hard even when only user clustering is considered.
  • Initial Algorithm for Cell Partition of Ground Users: User clustering partitions users into N clusters, each served by one UAV, and is the first step toward deployment.K-means assigns users by nearest-neighbor barycenters and recalculates cluster centers.
  • Initial Algorithm for Cell Partition of Ground Users: K-means minimizes squared clustering error for a fixed number of clusters but can converge only to a local minimum.Its squared error decreases as the number of clusters increases, so the cluster count must be fixed.
  • Initial Algorithm for Cell Partition of Ground Users: GAK-means is invoked to obtain global-optimum clustering because K-means is highly sensitive to its initial center.The procedure initializes a population, selects cluster centers genetically, deploys UAVs at those centers, and partitions users by Euclidean distance.

B. Q-learning Algorithm for 3D Deployment of UAVs

The Q-learning deployment algorithm models each UAV as an agent that learns 3D placement and movement decisions from states, actions, rewards, and Q-values. It maximizes long-term MOS-based rewards using seven-direction actions and an ε-greedy policy, although convergence depends on initial positions.

  • Q-learning Objective: The algorithm seeks UAV deployment and subsequent movement that maximize long-term rewards over the learning horizon.The three-step framework first partitions users, then learns initial deployment, and finally learns movement for roaming users.
  • Agent, State, and Actions: Each UAV acts as an agent whose state is its 3D position and whose actions represent horizontal, vertical, or stationary movement.The model uses seven directions to balance performance and complexity, while allowing arbitrary directions in principle.
  • Q-learning Update: Q-values are updated after each action using the observed reward, next state, learning rate, discount factor, and the maximum next-action value.The procedure repeats action selection, state transition, Q-table updates, and terminal-state evaluation.
  • Rewards: Rewards are positive when an action increases users’ sum MOS and negative when it decreases it.The reward values are 1 for MOS_new > MOS_old and −1 for MOS_new < MOS_old.
  • Policy: An ε-greedy policy selects the highest-Q action with probability 1−ε while exploring other actions to avoid local maxima.
  • Convergence: The deployment algorithm’s convergence rate varies with the UAVs’ initial positions.

C. Analysis of the Proposed Algorithms

The proposed Q-learning approach matches K-means complexity while offering convergence toward the optimal value under sufficient training and learning-rate conditions.

  • Complexity: GAK-means has total complexity O(TN(U^2 + U + 1)), combining square-error evaluation, mutation, and K-means operations.
  • Complexity: O(TUN) is the stated complexity for both Q-learning and K-means algorithms.
  • Stability and Convergence: With sufficiently many trials, Q-learning converges to the optimal value with probability 1 when its learning rate satisfies the convergence-theorem conditions.
  • Stability and Convergence: After Q-table updates, the UAVs’ positions and altitudes are determined, supporting stable algorithm behavior.

IV. DYNAMIC MOVEMENT DESIGN OF UAVS

The proposed dynamic-movement design uses Q-learning to adapt UAV positions to roaming users, beginning from a learned 3D deployment and operating under a selected mobility model. Simulations evaluate QoE, algorithm comparisons, and convergence.

  • Dynamic movement motivation: Q-learning adapts UAV movement to changing user positions because each cluster’s optimal UAV position changes as users roam.The movement algorithm is designed for a non-convex problem and selects actions at each time slot based on user mobility.
  • Scope and complexity: User association is not updated across clusters in this study, although reassociation could enhance service when users move between initially assigned areas.The paper limits its short-time trajectory study by assuming users cannot roam into other clusters; larger association action spaces would greatly increase complexity.
  • User mobility model: The random-walk mobility model assigns each user a uniformly distributed direction among left, right, forward, and backward.The paper notes that other mobility models can also be accommodated.
  • State and training design: The movement algorithm’s state combines dynamic 3D UAV positions with dynamic 2D user positions.UAV state depends on current positions and the actions taken in the previous time slot, while user state follows initial positions and movement.
  • State and training design: The proposed movement procedure trains through exploratory actions, observed rewards, state updates, and Q-table updates, then selects maximum-Q actions during testing.Testing begins from the deployment algorithm’s initial UAV positions and updates user positions at each time slot.
  • Numerical results: Q-learning outperforms K-means and IGK in the reported QoE comparisons and approaches exhaustive search as transmit power increases.Offline Q-table training makes the Q-learning and K-means algorithms have the same complexity when the Q-table is updated.
  • Numerical results: Convergence depends on UAV initial positions, but convergence is achieved after about 450000 episodes despite those initial positions.The convergence rate also varies with the simulation timespan, which creates a tradeoff between QoE improvement and model complexity.

B. Numerical Results of Dynamic Movement Problem

The proposed Q-learning movement algorithm adapts UAV trajectories to roaming users, improving QoE over static UAVs and IGK-based movement while trading movement accuracy against convergence effort.

  • When users follow a random walk, UAVs must move with them to prevent the sum MOS from decreasing.The comparison includes static UAVs, IGK-derived movement, and Q-learning-derived movement.
  • The Q-learning algorithm achieves better performance than the IGK algorithm for dynamic UAV movement.Unlike IGK, each UAV gradually learns its movement, avoiding IGK’s nontrivial computational complexity.
  • The movement simulation lasts 100s with constant UAV speed and seven directional actions available at each time slot.The timespan can be adjusted to improve movement accuracy, but longer spans require more iterations for convergence.
  • The overall framework combines GAK-means partitioning with Q-learning deployment for static users and Q-learning movement for roaming users.

APPENDIX A: PROOF OF LEMMA 1

The appendix develops the received-SINR and altitude relationships used to establish a UAV altitude constraint under transmit-power and channel conditions.

  • The received SINR Γ_kn(t) is formulated for user k_n connected to UAV n at time t.The derivation rewrites the SINR using line-of-sight and non-line-of-sight channel components.
  • The weighted LoS/NLoS path-loss term is bounded by the NLoS loss, with equality under a 100% NLoS connection.
  • The derivation bounds user-UAV distance using maximum transmit power, SINR requirements, noise, channel parameters, and path-loss terms.The resulting distance bound is then used to constrain UAV altitude.

APPENDIX C: PROOF OF THEOREM 1

The appendix proves that the sum-MOS optimization is non-convex because its spatial variables jointly affect distance, altitude, and probabilistic channel-loss terms.

  • The sum MOS is expressed through the users’ achievable rates and channel-dependent quantities.
  • The logarithmic rate expression is convex in its auxiliary variable, so non-convexity is attributed to the distance and channel-loss factor.
  • Although the distance-loss term is convex over UAV altitude alone, varying horizontal coordinates and altitude across time makes it non-convex jointly.

APPENDIX D: PROOF OF THEOREM 2

The appendix proves NP-hardness by reducing the formulation to planar K-means under fixed altitudes and unit LoS probability, showing the original problem contains an NP-hard special case.

  • The NP-hardness proof requires selecting an NP-complete decision problem, constructing a polynomial transformation, and preserving objective values.
  • The deployment problem remains NP-hard even with identical user QoE requirements and a LoS probability of one.
  • With unit LoS probability, the overall achievable sum rate depends only on the sum Euclidean distance.
  • Fixing UAV altitudes reduces the problem to planar K-means, whose known NP-hardness transfers to the original deployment problem.
Loading 1904.05242v2…