面向最大化服务用户数的无人机基站3D部署方法*

2023-11-25曾晓婉王海军马东堂

电讯技术 2023年11期

曾晓婉,王海军,马东堂,周力

(国防科技大学电子科学学院,长沙 410073)

0 引言

无人机具有体积较小、隐蔽性强、灵活机动、可提供视距链路等优点,对极端环境和复杂地理条件具有较强的适应能力和生存能力,特别是在地面基础设施损毁、卫星信号拒止、灾情瞬息万变等恶劣环境中,无人机辅助通信的作用尤为突出[1]。应急环境下,无人机可作为空中基站为地面用户提供信号覆盖。然而,搭建无人机网络不仅要考虑地面用户的不均匀分布,使能量有限的无人机为尽可能多的地面用户提供信号覆盖,还要使无人机之间形成稳健的骨干网,以实现无人机内部的信息交互。因此,研究一种适应用户分布特点、满足用户服务质量(Quality of Service,QoS)要求、保持无人机之间的连通并减少能耗的无人机基站部署方法,具有重要现实意义。

信道建模是无人机优化部署的基础。文献[2]提出了一种空对地(Air to Ground,A2G)信道的概率路径损耗模型,其中通信链路可以是视距(Line-of-Sight,LoS)链路或非视距(Non-Line-of-Sight,NLoS)链路,其发生概率是环境参数、建筑物高度以及地面设备和无人机之间仰角的函数。大多数关于无人机通信网络部署的研究均采用此概率路径损耗模型[3-6]。现有的无人机基站部署工作,按优化目标的不同,大致可分为最大化服务用户数或用户覆盖率[7-9]、最小化无人机数量[10]、最大化传输速率[11]、最小化无人机和用户的发射功率[12]、最大化用户能量效率[13]等。其中,文献[7]通过优化无人机位置和路径损耗补偿因子以最大化无人机的上行链路服务用户数;文献[8]推导出无人机覆盖用户的中断概率闭合表达式,并求得最大覆盖半径和最佳高度;文献[9]使用Q-learning算法来最大化无人机的用户覆盖率;文献[10]研究了无人机的数量和位置优化问题,以确保用户QoS;文献[11]以最大化网络总传输速率为目标,使用深度确定性策略梯度(Deep Deterministic Policy Gradient,DDPG)算法求出无人机最优悬停位置和功率分配;文献[12]以最小化无人机网络上行链路总发射功率为目标,设计了一种基于用户位置统计信息的无人机水平部署和用户关联方案;文献[13]联合优化无人机水平位置、用户关联和地面用户的发射功率以最大化地面用户的能量效率。然而,上述研究大部分是在二维平面对无人机进行部署,且未考虑无人机之间的连通。

本文综合考虑无人机之间的连通、用户QoS和无人机的服务公平性,以最大化服务用户数为目标,对无人机的三维坐标和覆盖半径进行优化。本文主要贡献如下:

一是将无人机部署问题建模为最大化服务用户数的同时保证无人机之间的连通、用户QoS和服务公平性的问题。经分析,该问题是非确定性多项式难题(Non-deterministic Polynomial Hard,NP-hard)。

二是将部署问题分解为水平部署和高度优化两个子问题。提出了一种融合了遗传算法和粒子群算法的启发式方法(A Heuristic Algorithm Combining Genetic Algorithm and Particle Swarm Optimization Algorithm,GAPSO),以较低的时间复杂度获得最优部署结果。另外,通过高度微调算法进一步降低无人机与服务用户之间的路径损耗。

三是分别在用户随机分布和分簇分布模式下进行仿真,结果验证了所提算法能以较低的时间复杂度和无人机平均发射功率获得最优部署结果。

需要特别说明的是,本文中无人机服务用户数指地面用户中无人机能为其提供有效通信的用户数量,用户覆盖率指无人机服务用户数占地面用户数的比例,服务公平性指不同无人机之间服务用户数的公平性。

1 系统模型和问题描述

1.1 场景介绍

图1描述了无人机通信网络模型。网络共有3类实体:无人机、地面用户和控制中心。数量有限的无人机基站悬停在一定高度,形成空中骨干网的同时,为尽可能多的地面用户提供有效通信。场景中共有无人机与核心控制器(UAV-BS to Core Controller,U2C)通信、无人机与无人机(UAV to UAV,U2U)通信以及无人机与所服务的用户(UAV-BS to Device,U2D)通信。在U2C通信中,控制中心用来与无人机网络交互控制指令,或实现无人机网络与其他网络的互通。在U2U通信中,无人机使用独立的通信链路,与其他通信类型之间不存在干扰。在U2D通信中,无人机可周期地获取地面节点的位置信息并更新位置。基站内用户采用频分多址(Frequency Division Multiple Access,FDMA)的方式,不同无人机基站采用正交频段,它们之间不存在干扰。

图1 无人机通信网络模型

本文主要考虑U2U通信和U2D通信。

1.2 信道模型

对于空对空信道,无人机i和无人机k之间的信道路径损耗可采用自由空间传播损耗(Free Space Propagation Loss,FSPL)模型计算,表示为

(1)

式中:di,k表示无人机i和无人机k之间的距离;f0表示无人机之间通信的载波频率;c是光速。因此,给定无人机之间的发送功率和通信带宽,由香农公式,在保证最低传输速率的前提下,无人机之间的最大通信距离是确定的,用dmax表示。

对于空对地信道,采用文献[2]推导的空对地信道概率模型,将信道损耗建模为LoS和NLoS分量的概率加权和。无人机i和用户j的平均路径损耗表示为

(2)

A=ηLoS-ηNLoS

(3)

(4)

(5)

(6)

式中:α和β是由环境(例如农村、城市、密集城市等)决定的常量因子;θi,j是无人机i和用户j的俯仰角;di,j表示无人机i和用户j之间的距离;hi是无人机的高度;ri,j是无人机i和用户j之间的水平欧氏距离;ηLoS和ηNLoS分别是LoS和NLoS下的平均附加路径损耗(与环境有关);fc是载波频率。

图2直观展示了城市环境中不同路径损耗下无人机的高度和覆盖半径之间的关系,图中θopt表示无人机取最大覆盖半径时的仰角。

图2 城市环境中不同下覆盖半径和高度的关系

由公式(2)～(6)和图2可得出以下结论:

结论1:在给定环境中,θopt是常量,由下列方程计算得出[2]:

(7)

结论2:在给定环境中,路径损耗越大,无人机的最大覆盖半径越大。

结论3:对于给定的路径损耗,无人机在仰角为θopt时,覆盖半径最大。

结论4:当无人机与地面用户的水平距离固定时,只有当无人机仰角为θopt时,路径损耗最小。

1.3 信号覆盖质量情况衡量

由于不同无人机基站采用正交频段,小区间不存在互干扰,因此可用信噪比(Signal-to-Noise Ratio,SNR)来衡量信号覆盖质量情况。鉴于此,当用户j收到来自无人机i的信噪比γi,j大于阈值Λth时,可认为无人机i可为用户j提供有效通信。SNR计算如下:

(8)

(9)

式中:pi,j表示无人机i对用户j的发射功率;Ngw是高斯白噪声功率。

1.4 问题描述和建模

已知地面用户的数量和位置,无人机数量固定,综合考虑无人机之间的连通、用户QoS和服务公平性,以最大化无人机服务用户数为目标优化无人机的3D坐标和覆盖半径。具体来说,部署的无人机在最大化服务用户数的同时,应满足如下要求:

①在U2U通信中,每个无人机应至少存在两个邻居节点;

②为避免碰撞,任意两架无人机之间的距离应不小于dmin;

⑤每个用户最多与1架无人机建立通信,位于多架无人机覆盖半径重叠区域的用户优先与服务用户数最少的无人机建立通信;

⑥考虑到地形和功耗,无人机的飞行高度应在合理区间[hmin,hmax]内。

基于上述分析,将无人机部署问题建模如下:

地温传感器的使用过程当中常常会受到天气状况的影响，在阴雨天气当中，低温传感器会由于地表的雨水较多，导致出现传感器的对接线发生故障。阴雨天气时，地表的积水随着传感器的外管壁进行渗透，这种故障产生时，表现为传感器的传送数值不准确或者是短路，因此一旦发现故障，就需要马上开展检查，并且针对外管壁进行加固，防止雨水的渗透，做好密封防水工作。

(10a)

(10b)

(10c)

(10d)

C4:hmin≤hi≤hmax。

(10e)

式中:约束条件C1保证了U2U通信时无人机至少有2个邻居节点;C2定义了无人机服务用户的上限;C3表示每个用户最多由一个无人机提供服务;C4表示无人机的高度在一定范围内。

经分析,该问题属于NP-hard问题,针对大规模无人机的部署,很难在可接受的时间内求出最优解[14]。遗传算法是解决多变量复杂优化问题的有效方案,广泛应用于各领域优化问题。本文将部署问题分解为水平部署和高度优化两个子问题,采用一种将遗传算法和粒子群算法相结合的GAPSO算法和高度微调法实现无人机的部署优化。

2 算法设计

2.1 GAPSO算法

粒子群优化算法(Particle Swarm Optimization Algorithm,PSO)受二维空间中的鸟群运动的启发而产生,后被推广到解决N维空间优化问题。在粒子群优化算法中,问题可能的解等价于搜索空间中的一个位置(称为“粒子”),算法初始化形成一群随机粒子,即随机的初始解。所有粒子皆有一个由被优化的函数决定的适应度,除了当前位置外,还记录了迄今为止该粒子达到过的适应度最好的位置(历史最优粒子)和种群中所有粒子达到过的适应度最好的位置(全局最优粒子)。粒子们参照最优粒子的位置在解空间中搜索,并多次迭代找到最优解。

设D维搜索空间中有m个粒子,第i个粒子的历史最优粒子和全局最优粒子分别表示为Pi=[pi1,…,piD]T和Pg=[pg1,…,pgD]T,其飞行速度和位置向量分别表示为Vi=[vi1,…,viD]T和Xi=[xi1,…,xiD]T,则粒子i第t+1次的飞行速度和位置可按如下公式计算:

vid(t+1)=c1·r1·[pid(t)-xid(t)]+

c2·r2·[pgd(t)-xid(t)]+ω·vid(t),

(11)

xid(t+1)=xid(t)+vid(t+1) 。

(12)

式中:1≤i≤m;1≤d≤D;ω为惯性因子;c1,c2为加速因子;r1,r2为[0,1]之间的随机数。在迭代过程中,为降低粒子飞出搜索空间的概率,粒子的速度向量被限制在[-Vmax,Vmax],位置向量被限制在[-Xmax,Xmax]。

遗传粒子群算法融合了遗传算法强大的全局搜索性能和粒子群的位置转移思想,其基本思想是:首先,进行种群初始化,计算个体适应度,并按适应度降序的顺序排序;然后,对前50%的优秀个体采用PSO算法进行提高并遗传到下一代,淘汰剩余个体;接着,对已提高的优秀个体通过交叉和变异得到完整的下一代;最后,多次迭代直至达到迭代次数或当前种群满足预设条件。具体流程如图3所示。

图3 GAPSO算法流程

2.2 算法设计

2.2.1 设计思路

图4 算法设计思路

2.2.2 算法具体步骤

表1列出了算法中使用的符号和定义。

表1 算法符号定义

无人机基站部署方法具体步骤如下:

输入:地面用户数据库

输出:全局最优个体及其适应度λ

1 仰角优化:由公式(7)计算无人机的最优仰角θopt;

3 种群初始化

5 选择:个体按适应度降序的顺序排序,保留前50%的个体;

7 提高:设置c1,c2和ω,用PSO算法更新个体水平坐标;

8 建立U2U连接图

9 判断坐标合理性

10 建立U2D连接图

11 计算适应度

12 比较新旧个体的适应度,更新每个个体的历史最优个体;

13 比较全部个体的适应度,更新全局最优个体;

14 end for

16 从已提高个体中随机选择2个个体,从中选择适应度大的个体作为父体,再以相同的方法选出母体;

17 生成2个位于区间(0,1)的随机数;

18 交叉:当第一个随机数小于等于pc时,将父母染色体的水平坐标对半交叉;

19 变异:当第二个随机数小于等于pm时,将父母染色体的水平坐标随机变异,若变异后坐标超出无人机部署区域的边界,则将坐标约束在边界上;

20 建立U2U连接图

21 判断坐标合理性

22 建立U2D连接图

23 计算适应度

24 比较新旧个体的适应度,更新每个个体的历史最优粒子;

25 比较全部个体的适应度,更新全局最优粒子;

26 end for

27 end for

28 高度微调

因篇幅所限,种群初始化、建立U2U连接图、判断坐标合理性、建立U2D连接图、计算适应度、高度微调的具体步骤和算法,请用微信扫描本文OSID码,在“开放科学数据与内容”中查看。

3 仿真验证和结果分析

3.1 仿真设置

本节通过Matlab仿真所提算法,动态展示部署过程,并评估算法性能。详细的部署演示视频可通过微信扫描本文OSID码,在“开放科学数据与内容”中查看。在本文的仿真中,300个用户分别以用户分簇分布和随机分布两种模式分布在4 000 m×4 000 m的区域内。仿真的主要参数如表2所列。

表2 主要仿真参数

3.2 部署示例

3.2.1 用户随机分布

图5(a)展示了用户在区域内随机分布,图5(b)显示了100次迭代后得到的无人机3D位置、无人机之间的链路及其与服务用户的连接情况,图5(c)和图5(d)分别是其水平部署结果和高度部署结果的展示。由图可见,无人机之间形成了稳定的连通,每个无人机至少有两个邻居节点,无人机服务用户数达到理论最大值,每个无人机服务的用户数不超过25。

(a)用户随机分布

3.2.2 用户分簇分布

图6(a)展示了用户分簇分布的一种典型场景,其中,有的簇与其他簇分界明显,有的簇与其他簇界线不明显;属于不同簇的用户分布方式不一,有的零散程度大,有的较为密集,有的呈“一”字型分布。图6(b)显示了100次迭代后的无人机3D位置、无人机之间的链路及其与服务用户之间的连接情况,图6(c)和图6(d)分别是其水平部署结果和高度部署结果的展示。由图可见,分簇场景下,无人机在寻求服务用户数最大化的同时尽量聚拢以确保无人机之间的连通。

3.3 算法性能评估

3.3.1 迭代收敛性

进化算法的收敛性分析主要研究在迭代时间趋于无穷的假设下,算法能否最终找到并保留问题的全局最优解[15-16],或者全局最优解能否占据整个种群[17]。仿真结果表明,K-means初始化、Voronoi Diagram初始化和随机初始化三种方式均能收敛到用户覆盖率的理论最大值(即全局最优解)。GAPSO算法的首要步骤是对初始种群中的100个个体进行水平位置初始化,那么,种群初始化如何影响算法的收敛性呢?图7展示了K-means初始化、Voronoi Diagram初始化和随机初始化三种方式下用户覆盖率随迭代次数的变化情况,所示结果为算法收敛到全局最优解的5 000次仿真结果的平均值。

图7 三种初始化方式下的收敛性

由图7可知,在用户分簇分布下,三种初始化方式迭代10次以内均可收敛到全局最优解。这是因为分簇分布时用户较为紧密,所有的簇基本能被无人机的最大覆盖半径覆盖。值得注意的是,K-means初始化方式虽然能以较快速度收敛,但却极易早熟性收敛。具体来说,在用户随机分布模式下,种群在初始化过程中虽然每产生一个个体就要重新分簇且每次分簇的簇心都不尽相同,但由于随机分布下用户比较疏散,因此对覆盖用户数的影响不大,这会造成种群的多样性降低,从而使整个群体基本丧失进化能力,出现算法较早收敛于局部最优解的现象。即使通过增加分簇的个数减轻“早熟”现象,但随着分簇个数的增加,K-means初始化的算法收敛情况将与随机初始化的算法收敛情况类似。在用户分簇模式下,K-means初始化也存在“早熟”现象,但由于用户紧密,生成的初始种群的适应度值接近全局最优解,因此相比随机分布模式,“早熟”现象对其影响较小。在用户随机分布模式下,Voronoi Diagram初始化和随机初始化的算法在运行过程中的收敛情况相似,平均在迭代75次左右时收敛。但Voronoi Diagram初始化方式下的算法收敛到全局最优解的概率比随机初始化要高,这是因为Voronoi Diagram初始化以Voronoi Diagram顶点坐标作为无人机水平位置,可使无人机不偏离用户。

3.3.2 时间复杂度

算法的时间复杂度是输入规模的函数,表述了算法在一定输入规模下完成相应计算任务所花费的基本操作数[18]。一般来说,进化算法的时间复杂度是用算法找到问题的最优解或近似解所需的适应度值评估次数或者迭代的次数来衡量[19-21]。因此,可认为GAPSO算法的时间复杂度与种群大小K和最小迭代次数τmin有关,两个参数的乘积越小,算法的效率越高。本文将最小迭代次数定义为当适应度收敛到某个最优解的次数占全部迭代次数的20%时所需的全部迭代次数。

表3给出了种群大小K与所需的最小迭代次数τmin之间的关系,所示数据从5 000次仿真结果的平均值中分析得出(迭代次数向上取整,统一取10的整数倍),其中初始化方式选择Voronoi Diagram初始化。由于种群的多样性越高,算法收敛到全局最优解的概率越大。由表3,为提高算法的效率并增大种群找到全局最优解的概率,在用户随机分布模式下可将种群大小和迭代次数分别设置为100和100,在用户分簇分布模式下可将种群大小和迭代次数分别设置为20和20。

表3 种群大小与最小迭代次数的关系

3.3.3 用户覆盖率和服务公平性

本文用简氏公平指数(Jain’s fairness)来衡量服务公平性,定义为

(13)

式中:Si表示无人机i的服务用户数。可见,Ψc取值在1/N～1之间变化,当所有无人机的服务用户数相等时达到最大值1。

考虑到无人机的最大通信距离dmax对整个网络的连通有一定影响,因此探索它如何影响用户覆盖率和服务公平性。图8显示了用户覆盖率和服务公平性随无人机最大通信距离的变化趋势,所示结果为5 000次仿真结果的平均值。可以看出,用户覆盖率随着无人机最大通信距离的增大而增大,且均能收敛到理论最大值(250÷300≈83.33%)附近;服务公平性随着无人机最大通信距离的增大而增大,且均能收敛到理论最大值1的附近。这是因为当无人机最大通信距离较小时,为满足U2U通信中无人机至少有两个邻居节点的约束条件,无人机之间的重叠覆盖区域较多。当无人机最大通信距离足够大时,无人机可在保持相互通信的同时,分散到不同区域以最大化服务用户数和服务公平性。

图8 用户覆盖率和服务公平性随dmax的变化情况

3.3.4 无人机的平均发射功率

假设地面用户所需的接收功率pr为-74 dBm,则无人机i对用户j的发射功率可计算为

(14)

图9将GAPSO算法在高度固定和高度同时优化(GAPSO算法在高度同时优化时的高度初始化采用随机初始化)两种方式下所需的无人机平均发射功率与本算法使用的高度微调法进行对比,所示结果为5 000次仿真结果的平均值。图9(a)基于用户分簇分布场景,图9(b)基于用户随机分布场景。

如图9(a)所示,在分簇模式下,本文所提算法不能以最低的无人机平均发射功率获得最大的用户覆盖率。原因在于,无人机的初始高度为可获得理论最大覆盖半径的对应高度,这使得算法在运行过程中,为使每个无人机至少有2个邻居节点,个别无人机可能被部署在簇间空白区域,若此时仍有个别地面用户位于覆盖半径内,无人机则需要更多的发射功率以保证用户的通信质量。对于高度固定法部署的无人机,由于其覆盖半径有限,为覆盖更多用户,在算法运行过程中,无人机极有可能在每个簇内形成闭环的U2U通信(此时每个无人机有2个邻居节点)。此外,由于本文分簇场景中用户较为集中,因此,当高度固定法设置的高度较低时,部署的无人机能以较小的覆盖半径、较低的平均发射功率获得较大的覆盖率。

在随机分布模式下,用户间距没有分簇分布时密集,因此也更具普遍性。如图9(b)所示,比起高度固定和高度同时优化的情况,高度微调法部署的无人机用户覆盖率最高,平均发射功率最低。这是因为,高度微调法的原理是结论5,即当无人机与地面用户的水平距离固定时,只有当无人机悬停于hopt(本文仿真场景下为334.37 m)时,其路径损耗最小,若无人机高度增高或者降低,路径损耗将随之增大,为满足用户QoS要求,无人机的发射功率也将增大。