Trajectory Design and Access Control for Air-Ground Coordinated Communications System with Multi-Agent Deep Reinforcement Learning

基于多智能体深度强化学习的空地协同通信系统轨迹设计与访问控制

Ruijin Ding, Yadong Xu, Feifei Gao, Fellow, IEEE and Xuemin (Sherman) Shen, Fellow, IEEE

Keywords:Air-ground coordinated communications, user access control, UAV trajectory design,fair communication,multi-agent deep reinforcement learning

Abstract

空中无人机基站的轨迹和地面用户访问控制联合优化(air-ground coordinated communications system, in which trajectories of air UAV base stations (UAV-BSs) and access control of ground users (GUs) are jointly optimized

问题形式化为“混合的合作竞争博弈”模型(mixed cooperative-competitive game)，GU以竞争UAV-BS的有限资源，通过访问合适的无人机基站来最大化自身吞吐量。UAV-BSs合作设计自身轨迹来最大化定义的公平吞吐量，以此在提高总吞吐量的同时并保持公平性。GU动作空间是离散的（选取连接的UAV），UAV-BSs是连续的（移动空间）。GU的移动是随机游走，不属于决策范围。

To tackle this hybrid action space issue, we transform the discrete actions into continuous action probabilities and propose a multi-agent deep reinforcement learning (MADRL) approach, named AG-PMADDPG (air-ground probabilistic multi-agent deep deterministic policy gradient).

为了解决混合行动空间的问题，把离散行动转化为连续动作概率（continuous action probabilities)，提出多智能体深度强化学习方法（命名为AG-PMADDPG)，通过精心设计的rewards，AG-PMADDPG可以协调两类的agent，以实现agent在自己的本地视野下的目标。仿真结果表明，AG-PMADDPG算法在吞吐量和公平性方面优于基准算法。

1 Introduction

文中提到的应用：凭借3D飞行能力，UAV-BSs can offload burst data traffic for GUs in hotspot areas, such as stadium, cinemas, theaters, etc. and provide flexible capacity for QoS guaranty during rush hours and special events

UAV-assisted communications system的有点也很显然：

（1）UAV-BS可以飞，所以更高的LoS（视距）（2）UAV-BS可以移动来改善QoS（3）on-board calculation and caching modules可以让UAV执行计算任务

难点

UAV-BSs的轨迹优化问题是序列决策问题：（1）tremendous decision variables and is non-convex （2）difficult to be solved directly

过去的做法

过去的做法：（1）把原非凸问题简化成多个凸的子问题， solve the subproblems iteratively until reaching the convergency，（这种方法算法复杂度是关于UAVs和GUs指数增长的）。（2）并且这种方法当环境改变时，需要重新计算优化过程。（3）基于优化的方法需要global information来找到global optima，但在实际情况global information很难保证

本文的方法优点和主要贡献

（1）同时优化UAV-BSs路径和GU，过去的works一般优化二者之一。从非凸优化问题变成mixed cooperative-competitive game 混合合作竞争博弈。GU竞争，UAV-BSs合作，mixed指决策动作有连续有离散。

（2）基于MADDPG,提出了PMADDPG，probabilistic multi-agent deep deterministic policy gradient，解决hybrid action space的问题， transforms the discrete actions into continuous probabilities，samples an action according to the distribution。并且 prove the existence of policy gradient，因此DNN可以被这种方法优化。

（3）将PMADDPG应用到空地协同通讯系统，提出AG-PMADDPG(该算法具体于AG场景的算法）。

（4）从博弈论视角分析性能，计算了GUs的竞争博弈下的POA，结果说明如果GUs独立learning，会让结果遭遇严重的性能损失。

注意：后面公式中标量小写字母表示，向量黑体字母表示

2 REALTED WORK

2.A UAV Trajectory Design and GU Access Control

很多做无人机轨迹优化来改善AG通讯系统性能的工作。

(Reference对应的去原文附录查询，感觉本文idea base REF.17+REF.32）

UAV Trajectory Design

REF[10]：推导了固定翼无人机轨迹的能量消耗模型，提出基于序列凸优化的轨迹设计算法。最大化energy-efficiency。

REF[11]： 旋翼无人机的closed-form（猜测是悬停时的）能效模型，一种基于连续凸逼近(SCA)的算法来优化无人机的悬停位置。

REF[12]：基于TSP和凸优化让UAV通过轨迹优化来从分布式传感器节点中获取数据

REF[13]： 通过联合轨迹（joint trajectory design）设计和资源分配（resource allocation） 基于penalty dual-decomposition (PDD)算法 来最大化GUs的最小速率

REF[17]： 基于block coordinate descent (BCD) mechanism 来设计multi-DBS (drone base station) 多无人机基站的3D轨迹规划和调度算法来改善公平性和网络性能

GU Access Control

REF[32]：UAV辅助通讯中GU访问控制的分布式DRL框架

The GUs share a common neural network to make their own access decision independently according to local network state

REF[35]：基于 optimal transport theory，提出了最小化网络平均延迟的a cell-association algorithm

Given the locations of BSs and UAVs as well asthe distributions of GUs, the optimal cell partitions of the UAVs and terrestrial BSs are determined

这些工作的问题：要么固定GU access，优化UAV Trajectory；要么已知UAV Trajectory，解决GU access问题。

2.B UAV-assisted Communications Enabled by DRL

REF[24]：基于DRL方法让UAVs为GUs提供节能、公平的通信覆盖while preserving their connectivity，使无人机能够为GU提供节能和公平的通信覆盖，同时保持其连通性。

考虑了connectivity, fairness, energy consumption, and communication coverage。

REF[25]：无人机最佳定位方案 to find the optimal links between UAV nodes and fine-tune UAV positions 基于DQN处理动态群体拓扑结构和时变链路条件

REF[26]：动态分配多架无人机的资源， agent-independent method，所有的agents分享一个基于Q-Learning的structure但独立决策。无人机有 communicating GU, power level and subchannel信息，但是没有UAV之间的信息交互。

REF[27]：基于DRL，UAV可以调整flight speed、direction来为GUs提供更节能的服务，分配频带资源（ frequency band resources）来提高GUs的公平性。

这些工作的问题：要么处理离散动作空间，要么处理连续动作空间。

3 SYSTEM MODEL AND PROBLEM FORMULATION

3.A System Model

【阅读笔记：本篇文章没有考虑UAV垂直移动的通信情况，对于GUs应该也是假设在同一水平面上的，同时在划分的时间间隔内，GUs只能access一个UAV-BS】

符号记号：M架无人机基站，相同高度H，速度V。无人机m在t时刻的坐标表示为 u m ⃗ ( t ) \vec{u_m}(t) um​ ​(t)，T表示UAV-BSs的最大服务时间。K个GUs在地面随机游走。第k个GU的坐标： w k ⃗ ( t ) \vec{w_k}(t) wk​ ​(t)。M个UAV-BSs共享频带B，B被平均分配给UAV-BSs。每个GU在每个时间段内可以请求一个UAV-BS访问。

对时间的处理（微分）：

UAV-BSs飞行方向： e m ⃗ ( t ) \vec{e_m}(t) em​ ​(t)在微小时间段近似认为是常量。

UAV-BSs和GUs之间通讯采用LoS channel。不考虑UAV移动中多普勒效应的影响。

ρ 0 \rho_0 ρ0​表示： channel power gain at the reference distance 1 m

假设UAV-BSs发射功率 P t P_t Pt​相同，GU k从UAV-BS m中的接收功率:

信噪比：

n 0 n_0 n0​: the noise power spectral density

access indicator变量： η k , m ( t ) ∈ { 0 , 1 } \eta_{k,m}(t)\in \{0,1\} ηk,m​(t)∈{0,1}， GU k在t时刻请求UAV-BS m则 η \eta η=1

如果多个GU连接同一个UAV-BS，UAV-BS采用 time division multiple access (TDMA)技术来为GUs服务。（原本划分的time slot继续细分）。因此时刻t的可达下行吞吐量：

3.B Problem Formulation

（1）GUk在时刻t的吞吐量： d k ( t ) = ∑ m ∈ M c k , m ( t ) d_k(t)=\sum_{m\in{M}}c_{k,m}(t) dk​(t)=∑m∈M​ck,m​(t),GU k的目标：

GU k的优化目标：

（2）UAV-BSs：引入Jain’s fairness index来评估公平性

考虑公平性的总吞吐量：fair throughput

因此无人机m的优化目标：

还有一个假设： UAV-BSs can communicate with each other on anextra narrow channelfor exchanging some necessitate information（ In other words, the available information for the UAV-BSs are the same）

传统优化问题很难解决，但是MADRL可以很好解决。

4 PRELIMINARY OF MADRL

MADRL可以很好的解决markov game问题。N agents的markov game形式化为 ( S , A , R , P , γ ) (S,A,R,P,\gamma) (S,A,R,P,γ),S-描述环境的状态集，A是agents的action集合的集合，R是每个agent的Rewards functions的集合，P是状态转移概率(策略)，S执行 A ⃗ \vec{A} A 变到S’。 γ是rewards的discount。许多markov game是部分可观测的（POMDP）。所有agents的观测集表示为O。

在t时段，环境状态为s(t)、每个agent有一个自身的观察集： o i ( t ) = b i ( s ( t ) ) o_i(t)=b_i(s(t)) oi​(t)=bi​(s(t))，根据观察结果选择动作： a i ( t ) = π i ( o i ( t ) ) a_i(t)=\pi_i(o_i(t)) ai​(t)=πi​(oi​(t)), b i b_i bi​代表观察函数、 π i \pi_i πi​代表策略。

o ⃗ ( t ) = { o 1 ( t ) , . . . . , o n ( t ) } ， a ⃗ ( t ) = { a 1 ( t ) , . . . . a n ( t ) } ， r ⃗ ( t ) = { r 1 ( t ) , . . . . r n ( t ) } \vec{o}(t)=\{ o_1(t),....,o_n(t) \}，\vec{a}(t)=\{a_1(t),....a_n(t)\}，\vec{r}(t)=\{r_1(t),....r_n(t)\} o (t)={o1​(t),....,on​(t)}，a (t)={a1​(t),....an​(t)}，r (t)={r1​(t),....rn​(t)}

算法基于MADDPG（centralized training and decentralized execution），属于集中式训练分布式执行的架构，也是Actor-Critic架构。

每个agent有一个actor network π i ( o i ; θ i π ) \pi_i(o_i;\theta_i^{\pi}) πi​(oi​;θiπ​)，带有 θ i π \theta_i^{\pi} θiπ​权重用来去中心化的执行，actor network输入local observation输出action。每个agent的critic network Q i ( o ⃗ , a ⃗ ; θ i Q ) Q_i(\vec{o},\vec{a};\theta_i^Q) Qi​(o ,a ;θiQ​)可以评估actor network的输出价值，在中心化训练时采用了所有agents的observations和actions作为输入。

MADDPG采用了避免训练振荡和不收敛的两种技术：经验重放和目标网络。

在每个时刻t，agent存储 ( o ( t ) ⃗ , a ( t ) ⃗ , r ( t ) ⃗ , o ( t + 1 ) ⃗ ) (\vec{o(t)},\vec{a(t)},\vec{r(t)},\vec{o(t+1)}) (o(t) ​,a(t) ​,r(t) ​,o(t+1) ​)到容量为B的经验池中。如果重放缓冲区已满，则新生成的经验元组将替换旧的经验元组。从重放缓冲区中对actor和critic网络的训练数据进行批量采样。随机样本打破了序列间的相关性，减少了振荡。

Actor、critic networks都有相关的target actor π i ′ ( o i ; θ i π ’ ) \pi_i^{'}(o_i;\theta_i^{{\pi}’}) πi′​(oi​;θiπ’​)、target critic Q i ′ ( o ⃗ , a ⃗ ; θ i Q ′ ) Q_i^{'}(\vec{o},\vec{a};\theta_i^{Q'}) Qi′​(o ,a ;θiQ′​)共享相同的参数 θ i π \theta_i^{\pi} θiπ​、 θ i Q \theta_i^Q θiQ​

critic network由MSE loss来跟新：

y i ( j ) y_i(j) yi​(j)是更新目标， N b N_b Nb​是batch size

actor network最小化loss：

此时， a i = π i ( o i ( j ) ; θ i π ) a_i = \pi_i(o_i(j);\theta_i^\pi) ai​=πi​(oi​(j);θiπ​)

target network的更新基于现实网络

θ ′ ← ϵ θ + ( 1 − ϵ ) θ ′ ， ϵ < < 1 \theta' ← \epsilon\theta+(1-\epsilon)\theta'，\epsilon<<1 θ′←ϵθ+(1−ϵ)θ′，ϵ<<1

5 MULTI AGENT DEEP REINFORCEMENT LEARNING FOR AIR-GROUND COORDINATED COMMUNICATIONS SYSTEM

提出AG-PMADDPG算法，1~M代表的是UAV-BSs，M+1~M+K代表的是GUs。

5.A Observation Space

1）UAB-BSs

3-A提到下行吞吐量(downlink throughput)与UAV-BSs和GU之间的channels有关。由于UAV-BSs有很高的移动性，精确的信道状态信息（ accurate channel state information）很难观测。这里用GPS传感器来获得UAV-BSs和GUs的位置信息。

GUs在与选定的UAV进行数据交换前先报告其坐标。然后该无人机与其他基站交换信息。这样可以可以了解所有UAV-BSs和GUs的坐标信息。

因此：每个UAV-BS的observation包括：所有UAV-BSs和GUs的坐标，即一个长度为2*(M+K)的向量

2）GUs

由于隐私原因，each GU k只包含如下observation：

所有UAV-BSs的接受信号功率（ received signal power） { P k , m r ( t ) } m ∈ M \{ P_{k,m}^r(t) \}_{m\in{M}} {Pk,mr​(t)}m∈M​outdated received signal power { P k , m r ( t − 1 ) } m ∈ M \{ P_{k,m}^r(t-1) \}_{m\in{M}} {Pk,mr​(t−1)}m∈M​GU k在t-1时刻连接的UAV-BS： { η k , m ( t − 1 ) } m ∈ M \{ \eta_{k,m}(t-1) \}_{m\in{M}} {ηk,m​(t−1)}m∈M​每个UAV-BSs在t-1时刻连接的GUs的数量 { N m ( t − 1 ) } m ∈ M \{ N_{m}(t-1) \}_{m\in{M}} {Nm​(t−1)}m∈M​吞吐量 d k ( t − 1 ) d_k(t-1) dk​(t−1)

神经网络可以学习接收信号功率、连接的无人机基站与吞吐量之间的关系。

GUs有4M+1个观测值：

5.B Action Space

1）UAV-BS：选择飞行方向，提供公平的通信服务。我们使用极角 φ m ( t ) ∈ ( − π , π ) \varphi_m(t)\in{(-\pi,\pi)} φm​(t)∈(−π,π)描述飞行方向。

方便起见，归一化处理： λ φ ( t ) ∈ ( − 1 , 1 ) \lambda_\varphi(t)\in{(-1,1)} λφ​(t)∈(−1,1)

2）GU：每个时刻GU选一个UAV-BSs来access

传统的DRL算法只能解决所有动作都是连续或离散的问题，而不能处理混合动作空间。本文在MADDPG上提出了PMADDPG来解决混合动作决策空间的问题。具体应用到AG协同通信得到了AG-PMADDPG算法。

actor network of GU k：

outputs the probability distribution：

表示GU k access UAV-BS i的概率。

action of GU k： φ ( ⋅ ) \varphi(·) φ(⋅)表示根据概率分布进行抽样

因此actor network总输出是：

（与上面MADDPG的公式相比，把这里GU的 a ˉ \bar{a} aˉ代替MADDPG公式中的 a a a）

5.C Reward Design

1）UAV-BSs：

k r k_r kr​： 奖励与公平吞吐量之间的比率系数；UAV-BSs如果违反边界约束则扣除 r b r^b rb的奖励。如果违反了安全距离约束扣除 r d r^d rd的奖励。

边界违反指标 ξ m b ( t ) \xi_m^b(t) ξmb​(t)，当指标=1时表示UAV飞出边界。

安全距离违反指标 ξ m d ( t ) \xi_m^d(t) ξmd​(t)，指标=1时表示飞进其他UAV的安全区。

2) GUs: reward directly defined as the achievable throughput

5.D Neural Networks

（1) Actor Network： local observation of agent as input and then outputs the action

（1.a）UAV-BS：

tanh容易造成梯度消失。

因此添加了一个 pre-activation penalty to the actor loss：

上图中的是权重因子； ζ \zeta ζ是 saturation value of tanh

Minimizing the actor loss prevents the pre-activation value from staying in the saturation area and thus eliminates gradient vanishing.

(1.b) GU：The output of a GU’s actor network is the probability of selecting each UAV-BS to access. Thus the activation function in the output layer is softmax.

5.E Training Algorithm

算法有T个episode，每个episode开始，UAV-BS位于初始位置，GU随机分布在地面上。在每个时刻t，GU以固定速率、随机方向游走。

在训练阶段，每个UAV-BS输入他自己的观测值 O m ( t ) O_m(t) Om​(t)给actor network π m ( o m ( t ) ; θ m π ) \pi_m(o_m(t);\theta_m^\pi) πm​(om​(t);θmπ​)输出飞行方位。GU以本地观测值 o M + k ( t ) o_{M+k}(t) oM+k​(t)作为输入，输出动作概率分布 a ˉ M + k \bar{a}_{M+k} aˉM+k​。

6 SIMULATION RESULTS

6.A Simulation Settings

UAV-BSs

service region：假设为2kmx2km（坐标原点在中心）；

飞行高度：100m；

speed: V=10m/s；

（无人机之间的安全距离是5m）

total frequency bandwidth：B=1MHz； 发射功率: Pt=10dBm；

噪声功率谱密度 noise power spectral density：−170 dBm/Hz；

参考信道功率增益 reference channel power gain：ρ0 = −50 dB；

每个episode开始前：UAV-BSs均匀分布在R=500m的圆上。(eg. n=2,则u1=(500,0),u2=(-500,0) )

GUs

随机分布并且随机游走。

速度：均匀分布在[1m/s,5m/s]

service time: T=200s

time slot size δt=0.2s

Learning参数

ADAM optimizers，learning rate=0.001

6.B Performance Analysis

benchmark algorithms:

AC-PMADDPG,access control PMADDPG， only optimize the GU access control based on mon Deep Q Network (DQN)：REF[32]， GU access control，All GUs share a common network， The experiences of all GUs are shared as the training dataDistributed DQN： Inspired by [32], each GU has its own network to train in distributed DQN, and the training data of each GU is private.

2UAV-BSs+2GUs

前5k时效果不好，原因： At the very beginning, the UAV-BSs fly around for exploration and may fly far away from the GUs, which leads to small throughput. The UAVBSs may even violate the boundary constraint (12c) and receive corresponding penalty.

oscillates significantly（震荡明显）原因：DRL没有label

仅考虑access control的AC-PMADDPG算法性能也好于DQN，原因： The centralized critic in PMADDPG can utilize the observations of all agents

distributed DQN converges（收敛） much faster，原因：common DQN needs to learn a common policy for all agents, which is much more complex than the distributed way

distributed DQN converges faster than AG-PMADDPG，原因： searching policy in the discrete action space is simpler than in the continuous probability action space

7 CONCLUSION

AG-PMADDPG can achieve much better performance than the existing benchmarks in terms offairness index,total throughputandminimum throughput

For the future work, we will investigate thefrequency band allocation of the UAV-BSsto further improve the system performance.

名词注释

coordinated：协调、协同

base stations 基站，公用移动通信基站，是移动设备接入互联网的接口设备，是指在一定的无线电覆盖区中，通过移动通信交换中心，与移动电话终端之间进行信息传递的无线电收发信电台。

UAV-BS：无人机基站

cooperative-competitive game：合作竞争博弈

throughput ：吞吐量，每秒比特数 bps，bits per second

Deterministic Policy Gradient，DPG：确定性行为策略梯度，DPG每一步的行为通过函数μ直接获得确定的值。之前业界普遍认为，环境模型无关的确定性策略是不存在的，而D.Silver等通过严密的数学推导证明了DPG的存在。根据DPG论文的证明，当概率策略的方差趋近于0的时候，就是确定性策略。

DDPG（Deep Deterministic Policy Gradient），利用 DQN 扩展 Q 学习算法的思路对DPG方法进行改造得到的（Actor-Critic，AC）框架的算法该算法可用于解决连续动作空间上的 DRL 问题。相对于DPG的核心改进是采用卷积神经网络作为策略函数μ和Q函数的函数近似，即策略网络和Q网络；然后使用深度学习的方法来训练上述神经网络。

Ref: DPG\DDPG

terrestrial communications：地面通讯

wireless transceivers：无线收发器

offload burst data traffic：卸载突发数据流量

QoS guaranty： Quality of Service，服务质量, 网络服务质量保证

无线通信系统的传播条件分成视距(LOS)和非视距(NLOS)两种环境，视距条件下，无线信号无遮挡地在发信端与接收端之间直线传播，而在有障碍物的情况下，无线信号只能通过反射，散射和衍射方式到达接收端，我们称之为非视距通信。此时的无线信号通过多种途径被接收，而多径效应会带来时延不同步、信号衰减、极化改变、链路不稳定等一系列问题。

line-of-sight：LoS，视距，指发射天线和接收天线能互相“看见”对方

视距传播（LOS propagation）：在发射天线和接受天线间能相互“看见”的距离内，电波直接从发射点传播到接收点（一般要包括地面的反射波）的一种传播方式，其空间波在所能直达的两点间的传播。视距传播的距离一般为20～50Km，同在地面上人的视线能及的距离相仿，主要用于超短波及微波通信。

Ref:视距无线传输 (Line of Sight，LOS)

sequential optimization problem：序列优化问题

convergency：收敛

price of anarchy,POA

在一个game中，全局最优解，一般来说不可能达到，一般都是达到纳什均衡解，均衡解可能不止一个，也有好有坏，那么为了反映这个纳什均衡的解的情况到底好不好，好到什么程度？坏到什么程度？就有学者提出了POA和POS。POA等于这个game中的全局最优解 比 纳什均衡解中的最小值，也就是说，POA越大，意味着纳什均衡解中差的那一面越差。POS等于这个game中的全局最优解 比 纳什均衡解中的最大值，POS越接近1，代表这个纳什均衡解好的那一面越好。

fixed-wing UAV：固定翼无人机

rotary-wing UAV：旋翼无人机

successive convex approximation，SCA：连续凸近似方法。successive: 连续的含义，就是通过不断的迭代去完成的，convex: 就是说在迭代的过程中采用的是凸函数来代替非凸函数；approximation: 怎么去采用凸函数来代替非凸函数呢，这就需要去近似。

dynamic swarm topology：群体动态拓扑结构

time-varying link conditions 时变链路条件

signal-to-noise ratio,SNR:信噪比

time division multiple access (TDMA)：时分多址接入