基于多密度流聚类的UAV-NOMA用户分簇与功率分配算法

User Clustering and Power Allocation Algorithm for UAV-NOMA Based on Multi-Density Stream Clustering

摘要

针对无人机（Unmanned Aerial Vehicle，UAV）辅助非正交多址（Non-Orthogonal Multiple Access，NOMA）下行通信系统，提出了最大化和速率的用户动态分簇与功率分配方案.考虑用户服务质量与UAV位置约束，建立了和速率最大化的优化问题.由于目标函数的非凸性，将原问题解耦为三个子问题，分别优化UAV位置部署与用户连接、用户动态分簇、功率分配以提高系统性能.首先，基于K-means算法设计了UAV位置部署与用户连接方案，以减小路损为目的确定UAV最佳部署位置，同时选择其服务的最优用户群；其次，改进多密度流聚类（Multi-Density Stream Clustering， MDSC）算法，提出了单UAV下用户静态与动态分簇方案，静态分簇方案可自适应平衡簇数与簇用户数，并获得较大的簇内用户信道增益差异，动态分簇方案则针对用户移动属性，制定了即时更新策略；最后，使用分式规划（Fractional Programming，FP）二次变换的方法，引入辅助变量将原非凸问题变换为凸问题，交替优化辅助变量与功率分配因子，获得原非凸问题的次优解.仿真结果表明，与其他算法相比，本文分簇方案能获得更大的簇内信道差异与更小的簇内用户数标准差，同时用户系统性能也获得了显著提升.

Abstract

A user dynamic clustering and power alloction scheme is proposed for maximizing the sum rate in a downlink communication system employing non-orthogonal multiple access （NOMA） with unmanned aerial vehicles （UAVs） assistance. Considering the user quality of service and UAV position constraints， an optimization problem is formulated to maximize the sum rate.Due to the non-convexity of the objective function，the original problem is decoupled into three sub-problems to enhance system performance： UAV position deployment and user association， user dynamic clustering， and power allocation to improve system performance. Firstly， a UAV position deployment and user association scheme are designed based on the K-means algorithm， the objective is to minimize path loss， determining the optimal deployment position of the UAV with the simultaneous selection of the optimal user group to be served. Secondly， the multi-density stream clustering （MDSC） algorithm is improved， and a static and dynamic clustering scheme for users under a single UAV is proposed. The static clustering scheme can adaptively balance the number of clusters and the number of cluster users， and obtain a large difference in user channel gain within the cluster. The dynamic clustering scheme formulates an instant update strategy for user mobility attributes.Finally， by applying fractional programming （FP） and quadratic transformation， an auxiliary variable is introduced to transform the original non-convex problem into a convex problem. The auxiliary variable and power allocation are alternately optimized to obtain a suboptimal solution for the original non-convex problem. The simulation results show that compared with other algorithms， the clustering scheme in this paper can obtain larger intra-cluster channel difference and smaller standard deviation of the number of users in the cluster， and the performance of the user system is also significantly improved.

Graphical abstract

关键词

无人机 / 非正交多址 / 位置部署 / 动态分簇 / 功率分配

Key words

unmanned aerial vehicle（UAV） / non-orthogonal multiple access / position deployment / dynamic clustering / power allocation

由于无人机（Unmanned Aerial Vehicle， UAV）具有的高移动性、灵活性、部署方便、远程控制等诸多优点，近年来作为飞行基站或者中继基站，被广泛用于辅助应急通信、物联网、军事通信等无线通信领域^［1］.第五代通信技术（5G）的高速发展也给现有蜂窝通信带来了新的挑战，高数据传输、海量用户连接、低时延等成为用户的关键需求.非正交多址接入技术（Non-Orthogonal Multiple Access， NOMA）作为5G以及下一代无线通信系统的关键技术，不仅能满足大规模用户连接，显著提高传输速率和系统容量，而且在用户公平性方面也具备显著的优势^［2］.

NOMA通信通过分配不同的码或功率，为时间和频率上使用相同无线电资源的用户提供服务^［3］.对于功率域NOMA，发送端分配不同的功率给用户信号，并且将其叠加发送.接收端采用串行干扰消除（Successive Interference Cancellation， SIC）技术去除干扰并解码出期望信号^［4］.功率分配与SIC技术主要利用用户间不同的信道增益差异进行，但是随着用户数的增加，SIC技术的计算复杂度急剧上升，功率分配也将变得极其复杂.为降低系统的计算复杂度，通常会使用用户分簇算法将用户分到不同的簇中，并在每簇中进行资源的复用.用户分簇的主要目标是通过将信道增益不同的用户分为较小的NOMA簇，来降低SIC复杂度与用户间的交叉干扰，从而提升整个系统的通信速率^［5］.

当前针对UAV作为空中基站或者中继基站辅助NOMA通信的研究，主要集中在UAV的位置部署和NOMA通信的功率分配问题上.其中文献［6］通过联合优化移动用户与UAV基站的关联、资源分配、UAV放置以及更新间隔，最大化用户的和速率.文献［7］提出了基于UAV辅助NOMA的用户分组与资源分配联合优化算法，利用图论的最大割定理实现了组内用户与UAV最小相对距离，并利用辅助变量法求解了优化问题.文献［8］研究了UAV-NOMA网络中单UAV的部署和功率分配问题，通过最小化UAV到用户的总路径优化UAV的布局，利用UAV的最优位置最大化网络的总和速率.文献［9］研究了UAV辅助全双工NOMA通信系统在资源配置下的能效最大化问题，提出了一种自适应几何分布（Adaptive Geometric Distribution， AGD）的用户分簇算法，此算法能够保证簇用户数相等，但是对于非均匀分布的用户，会导致簇覆盖范围相差较大.文献［10］分别对改进的AGD算法、谱聚类算法、高斯混合模型（Gaussian Mixture Model， GMM）等进行了用户分簇研究，并给出了各聚类算法的性能研究.文献［11］研究了在总发射功率和用户预定速率要求约束下的毫米波NOMA系统的和速率最大化问题，提出了一个基于K-均值的在线用户聚类算法，以降低计算复杂度，与传统的用户聚类算法相比，所提出的机器学习框架增强了毫米波NOMA系统的性能.文献［12］根据用户的速率要求，通过联合优化IRS处的被动波束成形向量、解码顺序、功率分配系数向量和簇的数量来最大化所有用户的和速率，提出了一种基于K-均值的 高斯混合模型（K-GMM）用户聚类算法提升系统性能.文献［13］研究了NOMA辅助太赫兹网络的聚类问题，设计了基于机器学习的分簇方法，以确保可 以在不知道集群数量的情况下对用户进行集群.文献［14］通过研究用户的动态分簇、UAV的布局与功率分配提高系统的总吞吐量提出了两阶段的动态分簇算法，以降低多UAV辅助造成的交叉干扰，并分别使用了连续凸逼近与蛮力搜索算法解决了用户功率分配与UAV最优布局问题.

目前，在UAV-NOMA下行网络研究中，关于UAV群辅助密集移动用户的资源分配问题尚未得到理想的研究成果.在此动态场景中，用户的移动性使得其与UAV之间的信道状态不断改变，资源分配也变成了难以解决的问题.穷举或者启发式算法虽然可以得到很好的效果，但是极高的时间计算复杂度并不适用于动态场景.为此，本文研究了多UAV辅助NOMA下行通信的资源配置方案.具体创新工作如下：

1）基于经典K-means算法^［12］设计了UAV位置部署与用户连接算法；

2）基于UAV的位置信息，改进了流聚类算法，提出了基于密度的用户静态与动态分簇方案，使得用户可以实现自适应分簇与更新；

3）使用FP二次变换的方法引入辅助变量，将原非凸问题转化为凸问题，求解得到功率分配的次优解.

仿真结果显示，用户分簇算法能获得更理想的分簇效果，FP二次变换方法也具有良好的收敛性能，相比之下，此方案用户总和速率高于相同场景下K-means算法.

1 系统模型和问题描述

本文考虑一个多无人机辅助NOMA的下行通信系统，系统模型如图1所示.网络中随机分布着N个移动用户与M架无人机，无人机工作在固定高度，作为空中基站为用户提供通信服务.假设用户与无人机的位置已知并定义第i个用户与第m个无人机的二维笛卡尔坐标分别为w_i=[x_i,y_i],i\in \{\mathrm{1,2},\cdots ,N\}，u_m=[x_{um},y_{um}],m\in \{\mathrm{1,2},\cdots ,M\}.此外，无人机与用户都配备一根天线.

由上所述，第i个用户从第m架无人机接收到的信号为：

\begin{array}{l}{y}_i^m=h_i^m\sqrt[]{p_i^m}{s}_i^m+\sum _{\tilde{i}\in N/\{i\}}{h}_i^m\sqrt[]{p_{\tilde{i}}^m}{s}_{\tilde{i}}^m+\\ \sum _{\tilde{m}\in M/\{m\}}{h}_m^{\tilde{m}}{x}_i^{\tilde{m}}+n_i^m\end{array}（1）

式中：p_i^m表示第m架无人机分配给第i个用户的功率；s_i^m表示第i个用户从第m架无人机接收到的传输信号；\tilde{i}\in N/\{i\}表示除去用户i的其他用户；\tilde{m}\in M/\{m\}表示除去无人机m的其他无人机；x_i^{\tilde{m}}={\displaystyle \sum _{i=\mathrm{1}}^N}\sqrt[]{p_i^{\tilde{m}}}{s}_i^{\tilde{m}}表示无人机\tilde{m}发送给用户的传输信号；h_i^m表示用户i与无人机m之间的信道增益；h_m^{\tilde{m}}表示无人机m与无人机\tilde{m}之间的信道增益；n_i^m表示高斯白噪声，n_i^m\sim \mathrm{C}\mathrm{N}\left(\mathrm{0},{\sigma }_j^{\mathrm{2}}\right).

假设用户与第m架UAV的直线距离排序为，则用户的信道增益排序为{\left|h_{\mathrm{1}}^m\right|}^{\mathrm{2}}>{\left|h_{\mathrm{2}}^m\right|}^{\mathrm{2}}>\cdots >{\left|h_N^m\right|}^{\mathrm{2}}.NOMA下行通信网络在发送端根据用户信道增益分配功率，使得信道增益弱的用户始终比信道增益强的用户分配到更大的功率，以保证成功的SIC与通信公平性.

基于上述条件，假设UAV的最大发射功率为P，则第i个用户接收其传输信号时信干噪比可表示为：

{\gamma }_i^m=\frac{p_i^m{\left|h_i^m\right|}^{\mathrm{2}}}{{\displaystyle \sum _{j=\mathrm{1}}^{i-\mathrm{1}}}{p}_j^m{\left|h_i^m\right|}^{\mathrm{2}}+\sum _{\tilde{m}\in M/\{m\}}{h}_m^{\tilde{m}}{x}_i^{\tilde{m}}+n_i^m}（2）

用户i的有效信息传输速率可表示为：

r_i^m=B^m\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}(\mathrm{1}+{\gamma }_i^m)（3）

式中：B^m为第m架UAV的带宽.因此用户从UAV接收信息的和速率可表示为：

R_{\mathrm{s}\mathrm{u}\mathrm{m}}^{}={\displaystyle \sum _{m=\mathrm{1}}^M}{\displaystyle \sum _{i=\mathrm{1}}^N}{r}_i^m（4）

为了提升本通信模型的通信性能，提出了和速率最大化的UAV位置部署与功率分配优化问题，此问题表述为：

\begin{array}{l}\mathrm{P}\mathrm{1}:\underset{p_i^m,u_m}{\mathrm{m}\mathrm{a}\mathrm{x}}{\displaystyle \sum _{m=\mathrm{1}}^M}{\displaystyle \sum _{i=\mathrm{1}}^N}{B}^m\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}(\mathrm{1}+{\gamma }_i^m)\\ \mathrm{s}.\mathrm{t}.\mathrm{C}\mathrm{1}:{\displaystyle \sum _{i=\mathrm{1}}^N}{p}_i^m\le P,\forall m\in \{\mathrm{1,2},\dots ,M\}\\ \mathrm{C}\mathrm{2}:{\gamma }_i^m\ge {\gamma }^{\mathrm{m}\mathrm{i}\mathrm{n}},\forall m\in \{\mathrm{1,2},\dots ,M\},\forall i\in \{\mathrm{1,2},\dots ,N\}\\ \mathrm{C}\mathrm{3}:\mathrm{m}\mathrm{i}\mathrm{n}\left\{x_i\right\}\le x_{\mathrm{u}\mathrm{m}}\le \mathrm{m}\mathrm{a}\mathrm{x}\left\{x_i\right\},\forall m\in \{\mathrm{1,2},\dots ,M\},\\ \forall i\in \{\mathrm{1,2},\dots ,N\}\\ \mathrm{C}\mathrm{4}:\mathrm{m}\mathrm{i}\mathrm{n}\left\{y_i\right\}\le y_{\mathrm{u}\mathrm{m}}\le \mathrm{m}\mathrm{a}\mathrm{x}\left\{y_i\right\},\forall m\in \{\mathrm{1,2},\dots ,M\},\\ \forall i\in \{\mathrm{1,2},\dots ,N\}\end{array}（5）

式中：约束条件C1保证用户总功率小于等于UAV最大发射功率；C2保证用户满足服务质量（Quality of Service，QoS）需求；C3，C4为UAV二维平面坐标的位置约束.

问题\mathrm{P}\mathrm{1}是一个混合整数非线性规划问题，难以求解，因此将原问题解耦为三个子问题降低求解的复杂度.首先对UAV与用户的连接问题进行优化，建立UAV服务用户组，使得UAV服务特定用户，以此减少UAV对用户造成的交叉干扰；其次设计用户分簇算法对单UAV下的用户进行分簇，尽可能增大簇内用户间的信道增益差异，降低SIC复杂度与簇内用户的干扰；最后使用FP二次变换的方法求解功率分配问题.

2 UAV位置部署与用户连接

假设无人机与用户之间是视距链路（LOS），由此第m架UAV与用户i的路径损耗模型可以表示为：

L_i^m=\mathrm{10}\xi \mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{10}}{d}_i^m+\mathrm{10}\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{10}}\lambda（6）

式中：\xi为路径损耗指数；\lambda为视距链路对应的衰减因子；d_i^m为第m架UAV与第i个用户的距离，表示为：

d_i^m=\sqrt[]{H^{\mathrm{2}}+{\left(x_{\mathrm{u}\mathrm{m}}-x_i\right)}^{\mathrm{2}}+{\left(y_{um}-y_i\right)}^{\mathrm{2}}}（7）

其中H为无人机的飞行高度.

用户i收到来自UAVm的功率可以表示为：

{\tilde{p}}_i^m=p_i^m-L_i^m（8）

因此，可以通过最小化UAV与用户的路径损耗找出UAV最佳的水平位置，如下所示

\begin{array}{l}\mathrm{P}\mathrm{2}:\underset{L_i^m}{\mathrm{m}\mathrm{i}\mathrm{n}}{\displaystyle \sum _{m=\mathrm{1}}^M}{\displaystyle \sum _{i=\mathrm{1}}^N}{L}_i^m\\ \mathrm{s}.\mathrm{t}.\mathrm{m}\mathrm{i}\mathrm{n}\left\{x_i\right\}\le x_{\mathrm{u}\mathrm{m}}\le \mathrm{m}\mathrm{a}\mathrm{x}\left\{x_i\right\},\forall m\in \{\mathrm{1,2},\dots ,M\},\\ \forall i\in \{\mathrm{1,2},\dots ,N\}\\ \mathrm{m}\mathrm{i}\mathrm{n}\left\{y_i\right\}\le y_{\mathrm{u}\mathrm{m}}\le \mathrm{m}\mathrm{a}\mathrm{x}\left\{y_i\right\},\forall m\in \{\mathrm{1,2},\dots ,M\},\\ \forall i\in \{\mathrm{1,2},\dots ,N\}\end{array}（9）

路径损耗模型L_i^m中除距离d_i^m以外都是定值，且\mathrm{l}\mathrm{o}\mathrm{g}函数是单调的，因此最小化路径损耗等价于最小化UAV到用户的距离，优化问题\mathrm{P}\mathrm{2}可以改写为：

\begin{array}{l}\underset{x_{\mathrm{u}\mathrm{m}},y_{\mathrm{u}\mathrm{m}}}{\mathrm{m}\mathrm{i}\mathrm{n}}{\displaystyle \sum _{m=\mathrm{1}}^M}{\displaystyle \sum _{i=\mathrm{1}}^N}{\left(x_{\mathrm{u}\mathrm{m}}-x_i\right)}^{\mathrm{2}}+{\left(y_{\mathrm{u}\mathrm{m}}-y_i\right)}^{\mathrm{2}}\\ \mathrm{s}.\mathrm{t}.\mathrm{m}\mathrm{i}\mathrm{n}\left\{x_i\right\}\le x_{\mathrm{u}\mathrm{m}}\le \mathrm{m}\mathrm{a}\mathrm{x}\left\{x_i\right\},\forall m\in \{\mathrm{1,2},\dots ,M\},\\ \forall i\in \{\mathrm{1,2},\dots ,N\}\\ \mathrm{m}\mathrm{i}\mathrm{n}\left\{y_i\right\}\le y_{\mathrm{u}\mathrm{m}}\le \mathrm{m}\mathrm{a}\mathrm{x}\left\{y_i\right\},\forall m\in \{\mathrm{1,2},\dots ,M\},\\ \forall i\in \{\mathrm{1,2},\dots ,N\}\end{array}（10）

问题（10）是凸优化问题，文献［8］中给出了此问题的最优解：

x_{\mathrm{u}\mathrm{m}}={\displaystyle \sum _{i=\mathrm{1}}^N}\frac{x_i}{N},y_{\mathrm{u}\mathrm{m}}={\displaystyle \sum _{i=\mathrm{1}}^N}\frac{y_i}{N}（11）

因此，UAV的最佳平面位置在用户群二维坐标的质心.

多无人机提供通信的网络模型中，多架UAV水平位置相同并不合理，并且由第一节可知，用户在接收其中一架UAV的信息时，会受到剩余UAV的干扰.因此为了解决UAV水平位置重叠与无人机间的相互干扰问题，本文根据UAV与用户的位置信息，提出了基于K-Means算法的UAV位置与用户连接优化算法.具体步骤如下：

Step 1：计算每架UAV与N个用户的距离，用户被距离最近的UAV选定并标记；

Step 2：分别计算每架UAV选定用户的质心，计算结束后，UAV移动到选定用户的质心处；

Step 3：重复迭代以上两个步骤，直到每架UAV选定用户保持不变.

算法流程见算法1

其中\left|U_m\right|表示UAVm服务的用户数.

在无人机自组网内，UAV间共享信息使用同一频段，为用户提供通信时工作在不同频段，以此降低多无人机通信模型中UAV间相互干扰^［11］.为了进一步提升系统通信性能，下一节将对每个UAV服务的用户进行分簇，以降低下行NOMA通信的SIC复杂度与簇内用户间的同信道干扰.

3 用户分簇算法

在NOMA下行通信中，NOMA技术在发送端将用户信号叠加在相同的时频域资源上，通过对用户分配不同的发射功率，在功率域实现不同用户信号的区分；接收端采用基于用户解码顺序的串行干扰消除技术进行用户数据分离，将信道增益比目标用户弱的信号消除，信道增益比目标用户强的用户则成为干扰.因此，对用户进行分簇，并将信道增益差异大的用户分在同一簇的思想，能有效降低SIC技术的复杂度与簇内用户的同信道干扰，继而提升系统通信性能.

针对本文模型下的移动用户，本节将从静态与动态两个方面考虑用户的分簇问题.

3.1 用户静态分簇

本文使用的分簇算法基于数据分析中的蚁群流聚类（Ant Colony Stream Clustering， ACSC）^［15］与多密度流聚类（Multi-Density Stream Clustering， MDSC）算法^［16］改进而来，更加贴合NOMA的用户分簇思想.

3.1.1 创建微簇

微簇的概念由Cao等人在文献［17］中首次提出，用于用户的初步分簇.以生物学作为比喻，网络中的每位用户相当于一只“蚂蚁”，微簇相当于一群相似蚂蚁组成的“巢”.随机选取一只“蚂蚁”作为第一个“巢”，随后的“蚂蚁”加入现有“巢”，或者创建一个新“巢”.每只“蚂蚁”依次访问每个“巢”，并通过比较当前“巢”与其相异性来评估“巢”的适合性，“蚂蚁”a与“巢”k的相异性定义如下：

\mathrm{d}\mathrm{i}\mathrm{v}\left(a,k\right)=\frac{\mathrm{1}}{\left|C_k\right|}{\displaystyle \sum _{f=\mathrm{1}}^{\left|C_k\right|}}\left(\mathrm{1}-\mathrm{c}\mathrm{o}\mathrm{s}(a,f)\right)（12）

式中：\left|C_k\right|表示“巢”k目前的“蚂蚁”数；\mathrm{1}-\mathrm{c}\mathrm{o}\mathrm{s}(a,f)表示“蚂蚁”a与“巢”k内“蚂蚁”f的余弦距离.在本文模型下，为达到更好的分簇效果，使用用户与通信UAV的相对坐标{\tilde{w}}_a^m计算余弦距离，{\tilde{w}}_a^m=w_a^m-u_m.余弦距离可表示为：

\mathrm{1}-\mathrm{c}\mathrm{o}\mathrm{s}(a,f)=\mathrm{1}-\frac{{\tilde{w}}_a^m·{\tilde{w}}_{kf}^m}{{‖{\tilde{w}}_a^m‖}_{\mathrm{2}}{‖{\tilde{w}}_{kf}^m‖}_{\mathrm{2}}}（13）

式中：{\tilde{w}}_{kf}^m为UAVm服务的第k个微簇第f个用户与UAV的相对坐标.\mathrm{1}-\mathrm{c}\mathrm{o}\mathrm{s}(a,f)\in \left[\mathrm{0,2}\right]，余弦距离的值越小，表示两个用户越相似.

如果“蚂蚁”与“巢”的相异性小于或等于所设定的阈值\delta，“蚂蚁”便加入“巢”，若“蚂蚁”与多个 “巢”相似，则加入相异性最小的“巢”（最相似的“巢”）.否则令“蚂蚁”创建一个新“巢”，当所有“蚂蚁”都有自己的“巢”时，每个“巢”的“蚂蚁”合并为一个微簇.算法2给出了本步骤的伪代码.

算法2中，用户是否被纳入微簇中主要由相异性阈值\delta决定，可以通过改变阈值\delta的大小调整分簇结果.

3.1.2 完善用户簇

使用算法2后，用户被分成了众多微簇，但是由于实际场景中用户的分布情况复杂，可能会导致微簇间用户数差异过大.本节将对微簇群中的两种极端情况进行优化，使得用户分簇情况更加合理.

1） 单用户微簇

在NOMA网络中，一个用户享用一条链路的时频域资源会造成通信资源的浪费，因此单用户微簇并不合理.本部分通过将单用户微簇与相异性最小的微簇进行合并，以提升分簇效果.具体步骤如算法3所示：

2） 密集微簇

与1）同理，当用户移动时或用户分布不均时，易产生用户数过多的密集微簇，密集微簇会增加SIC复杂度与同信道干扰，因此将密集微簇细化为多个微簇能有效提升系统通信性能.

初始创建的微簇由于用户位置变化会导致各微簇用户数不一，定义\rho为平均微簇用户密度，用作评定微簇是否密集的标准，其中：\rho =\mathrm{c}\mathrm{e}\mathrm{i}\mathrm{l}\frac{\left|U_m\right|}{K}，即用户总数与现有用户微簇数的向上取整.当\left|C_k^m\right|>\rho时，该微簇将进一步细化.

具体步骤如算法4所示：

通过算法4的细化，使得密集微簇划分为多个用户数近似的小簇，平衡了簇间用户数差异，降低了簇内用户SIC计算复杂度，至此静态用户分簇结束.

用户分簇后，UAV依照簇内用户远近距离进行排序，使得同一簇内，第一个用户离UAV最近，最后一个用户离UAV最远，信道增益排序为{\left|h_{k\mathrm{1}}^m\right|}^{\mathrm{2}}>{\left|h_{k\mathrm{2}}^m\right|}^{\mathrm{2}}>\cdots >{\left|h_{k\left|C_k\right|}^m\right|}^{\mathrm{2}}，以保证SIC成功.

3.2 用户动态分簇

本文考虑的通信模型中，用户是移动的，用户的移动导致UAV与用户间的信道条件不断改变.为保证用户在移动后能够获得最佳的通信性能，UAV位置、用户连接情况与用户分簇需要不断更新，这带来了极高的计算复杂度.

为了降低更新的复杂度，本节定义T_{\mathrm{u}\mathrm{p}\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{e}}为更新间隔.时间经过T_{\mathrm{u}\mathrm{p}\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{e}}，UAV位置、用户连接情况与用户分簇进行一次迭代更新， T_{\mathrm{u}\mathrm{p}\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{e}}的大小可根据用户实际动态频率进行调整.具体步骤如算法5所示：

其中T_{\mathrm{n}\mathrm{e}\mathrm{w}}为当前时间，T_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}为上一次更新的时间.通过算法5，UAV能根据用户的移动动态更新水平位置、用户连接与分簇情况，从而使得用户位置发生改变后，依然能够保证良好的通信性能.

4 功率分配

通信模型经过无人机位置与用户连接优化后，UAV仅服务与自己关联的用户组，同时单UAV下用户由第3节用户分簇算法进行分簇与更新.因此优化后UAVm服务的第k个簇第s个用户的信干噪比可表示为：

{\gamma }_{ks}^m=\frac{p_{ks}^m{\left|h_{ks}^m\right|}^{\mathrm{2}}}{{\displaystyle \sum _{e=\mathrm{1}}^{s-\mathrm{1}}}{p}_e^m{\left|h_{ks}^m\right|}^{\mathrm{2}}+n_{ks}^m\frac{B^m}{K^m}}（14）

该用户有效信息速率可改写为：

r_{ks}^m=\frac{B^m}{K^m}\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}(\mathrm{1}+{\gamma }_{ks}^m)（15）

式中：K^m为UAVm服务用户的总簇数.

所有用户的和速率可以表示为：

R_{\mathrm{s}\mathrm{u}\mathrm{m}}={\displaystyle \sum _{m=\mathrm{1}}^M}{\displaystyle \sum _{k=\mathrm{1}}^{K^m}}{\displaystyle \sum _{s=\mathrm{1}}^{\left|C_k\right|}}{r}_{ks}^m（16）

总和速率最大化问题可表述为：

\mathrm{P}\mathrm{3}:\underset{p_{ks}^m}{\mathrm{m}\mathrm{a}\mathrm{x}}{\displaystyle \sum _{m=\mathrm{1}}^M}{\displaystyle \sum _{k=\mathrm{1}}^{K^m}}{\displaystyle \sum _{s=\mathrm{1}}^{\left|C_k\right|}}{r}_{ks}^m

\mathrm{s}.\mathrm{t}.\mathrm{C}\mathrm{1}:{\displaystyle \sum _{k=\mathrm{1}}^K}{\displaystyle \sum _{s=\mathrm{1}}^{\left|C_k\right|}}{p}_{ks}^m\le P,

\mathrm{C}\mathrm{2}:{\gamma }_{ks}^m\ge {\gamma }^{\mathrm{m}\mathrm{i}\mathrm{n}},\forall k\in \{\mathrm{1,2},\dots ,K^m\},

\forall s\in \{\mathrm{1,2},\dots ,\left|C_k\right|\}（17）

约束条件C1保证用户总功率小于等于UAV最大发射功率；C2保证用户满足服务质量（QoS）需求.

问题\mathrm{P}\mathrm{3}是一个非凸问题，难以直接求解.常用的求解办法有连续凸逼近（Successive Convex Approximation， SCA）^［18］、经典FP^［19］等，但是传统的FP方法大多数用以求解单比率问题，本文优化问题中信干噪比\gamma中多个分数参数来自多个用户的干扰，此类多比率问题使用经典FP技术解决非常复杂.因此，为降低求解复杂度，本节将采用文献［20］中提出的二次变换的方法进行求解.

二次变换利用类似于丁克尔巴赫^［20］ （Dinkelbach）的方法，将每个比率项的分子与分母解耦，不同之处在于丁克尔巴赫方法主要用于求解单一比值问题，而二次变换适用于多比率问题.

问题\mathrm{P}\mathrm{3}使用二次变换可重构为：

\mathrm{P}\mathrm{4}:{\displaystyle \sum _{m=\mathrm{1}}^M}{\displaystyle \sum _{k=\mathrm{1}}^{K^m}}{\displaystyle \sum _{s=\mathrm{1}}^{\left|C_k\right|}}\underset{V_{ks}^m,p_{ks}^m}{\mathrm{m}\mathrm{a}\mathrm{x}}f(p,V)

\mathrm{s}.\mathrm{t}.\mathrm{C}\mathrm{1},\mathrm{C}\mathrm{2}

\mathrm{C}\mathrm{3}:V_{ks}^m\in R（18）

其中新目标函数f(p,V)表示为：

f(p,V)=\frac{B^m}{K^m}\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\left(\begin{array}{l}\mathrm{1}+\mathrm{2}{V}_{ks}^m\sqrt[]{p_{ks}^m{\left|h_{ks}^m\right|}^{\mathrm{2}}}-\\ {\left(V_{ks}^m\right)}^{\mathrm{2}}\left({\displaystyle \sum _{e=\mathrm{1}}^{s-\mathrm{1}}}{p}_{ke}^m{\left|h_{ks}^m\right|}^{\mathrm{2}}+n_{ks}^m\frac{B^m}{K^m}\right)\end{array}\right)（19）

式中：V_{ks}^m为第k簇第s个用户二次变换引入的辅助变量.

目标函数二次变换为以上形式后，以迭代的方式优化变量V_{ks}^m,p_{ks}^m.当变量p_{ks}^m固定时，f(p,V)对V_{ks}^m求偏导可得到最优的V_{ks}^m为：

{\left(V_{ks}^m\right)}^{\mathrm{*}}=\frac{\sqrt[]{p_{ks}^m{\left|h_{ks}^m\right|}^{\mathrm{2}}}}{\left({\displaystyle \sum _{e=\mathrm{1}}^{s-\mathrm{1}}}{p}_{ke}^m{\left|h_{ks}^m\right|}^{\mathrm{2}}+n_{ks}^m\frac{B^m}{K^m}\right)}（20）

当V_{ks}^m固定时，f(p,V)是关于p_{ks}^m的凸函数.问题\mathrm{P}\mathrm{4}中，约束条件C2仍然是一个非凸约束，因此将原非凸约束转化为：

\widetilde{\mathrm{C}\mathrm{2}}:p_{ks}^m{\left|h_{ks}^m\right|}^{\mathrm{2}}\ge {\gamma }^{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\displaystyle \sum _{e=\mathrm{1}}^{s-\mathrm{1}}}{p}_e^m{\left|h_{ks}^m\right|}^{\mathrm{2}}+n_{ks}^m\frac{B^m}{K^m}\right)（21）

问题\mathrm{P}\mathrm{4}重写为：

\begin{array}{l}\widetilde{\mathrm{P}\mathrm{4}}:{\displaystyle \sum _{m=\mathrm{1}}^M}{\displaystyle \sum _{k=\mathrm{1}}^{K^m}}{\displaystyle \sum _{s=\mathrm{1}}^{\left|C_k\right|}}\underset{V_{ks}^m,p_{ks}^m}{\mathrm{m}\mathrm{a}\mathrm{x}}f(p,V)\\ \mathrm{s}.\mathrm{t}.\mathrm{C}\mathrm{1},\widetilde{\mathrm{C}\mathrm{2}},\mathrm{C}\mathrm{3}\end{array}（22）

通过求解凸问题\widetilde{\mathrm{P}\mathrm{4}}来更新p_{ks}^m，直至总和速率达到收敛.算法6给出了求解的具体步骤.

文献［20］中，作者给出了算法6详细的收敛性证明.简单来说，该算法本质上是重构问题的块坐标上升算法，重构问题\widetilde{\mathrm{P}\mathrm{4}}是一个凸优化问题，因此收敛于驻点.由于二次变换的性质，在最优的V_{ks}^m值下，\widetilde{\mathrm{P}\mathrm{4}}中p_{ks}^m的一阶条件与原问题\mathrm{P}\mathrm{3}相同，因此本算法也收敛到\mathrm{P}\mathrm{3}的稳定点，并且保证每次更新V_{ks}^m后，系统和速率的值不降低.

5 算法分析

5.1 算法流程

为了更清晰地展示本文方案的具体流程，本节给出了算法的整体流程图.如图2所示，首先确定UAV位置与服务用户，然后将用户分簇，接着进行功率分配求解优化问题，最后根据用户的移动情况动态调整UAV位置与用户分簇.本文算法详细流程图详见附录.

5.2 计算复杂度

本节主要描述UAV用户连接优化算法与分簇算法的计算复杂度.算法1主要基于K-means聚类算法，因此时间复杂度为O(\mathrm{2}MN{t}^{\mathrm{m}\mathrm{a}\mathrm{x}})，其中M为UAV数量，N为总用户数量，t^{\mathrm{m}\mathrm{a}\mathrm{x}}为最大迭代次数，本文只涉及用户的水平坐标，因此数据维度为2；算法2为非迭代算法，时间复杂度为O(K{n}^{\mathrm{2}})，其中K为最终总簇数，n为当前UAV的用户数；算法3复杂度主要取决于单用户微簇的个数，时间复杂度为O(v(K-\mathrm{1}))，v表示单用户微簇的个数；算法4主要由密集簇数量决定，时间复杂度为O(zc\mathrm{l}\mathrm{o}\mathrm{g}c)，z表示密集簇数量，c表示密集簇内用户数量.文献［21］利用粒子群优化（Particle Swarm Optimization，PSO）算法解决多UAV位置部署问题，PSO算法时间复杂度为O(\mathrm{2}l{T}_{\mathrm{P}\mathrm{S}\mathrm{O}})，其中l为粒子数目，T_{\mathrm{P}\mathrm{S}\mathrm{O}}为迭代次数，与本文算法1相比，PSO算法需要更多的迭代次数T_{\mathrm{P}\mathrm{S}\mathrm{O}}搜索更广泛的解空间，且涉及每个粒子的速度更新、位置更新等复杂计算，导致复杂度较大.文献［22］利用改进的遗传算法解决用户动态分簇问题，遗传算法复杂度为O(N^{\mathrm{2}})，本文通过优化UAV连接用户，分簇方案复杂度远低于遗传算法.同时，对于用户位置多变的动态场景，本文解决方案更具有可操作性.

6 仿真结果分析

现有聚类算法大多需要预设簇数，并且基于欧式距离的算法无法满足NOMA下行增大簇内信道增益差异的要求，可能导致系统性能降低.因此，本节通过大量仿真实验，将本文算法与文献［9］中的AGD算法，文献［10］中的GMM算法在NOMA分簇效果与和速率方面作出了对比，以验证本文算法的有效性.仿真参数设置如表1所示.

图3给出了用户位置分布以及UAV连接优化后的效果图.经过算法1后，UAV与用户建立了一对多的连接关系，图中相同标记的用户由同一UAV提供通信服务.

图4分别给出了UAV4服务用户经过4种不同算法分簇的结果.由于K-means算法与GMM算法的簇数需要预设，且AGD算法的分簇效果主要取决于设置的每簇最大人数n^{\mathrm{m}\mathrm{a}\mathrm{x}}，为保证对比的有效性，本文通过调整三种算法的预设参数，将簇数控制为本文算法自适应划分的簇数.从分簇结果图可知，本文算法与AGD算法分簇后，同一簇的用户与UAV位置呈线性，簇内用户间距离更远，簇内信道增益差异更大；K-means算法与GMM算法的同簇用户则相距较近，分布散乱，无法获得较大的信道增益差异.仿真表明，本文方案分簇结果与AGD算法近似，均优于K-means算法与GMM算法.

接收端对接收信号进行干扰消除时，SIC的计算复杂度会随着同簇用户数的增加而增加.一般来说，簇内用户SIC的时间复杂度为O({\left|C_k^m\right|}^{\mathrm{2}})，空间复杂度同理.随着簇内用户数\left|C_k^m\right|的增加，计算复杂度会呈现指数级别的增长.因此合理的簇数与簇内用户数对系统的性能与用户公平性有很大的影响.图5给出了4种算法簇间用户数的标准差，以此分析簇间用户数的差异程度.由图可知，本文算法簇间用户数的标准差远低于K-means算法与GMM算法，略高于AGD算法， 主要原因在于AGD算法依靠n^{\mathrm{m}\mathrm{a}\mathrm{x}}值，获得的簇用户数大致相等，但是n^{\mathrm{m}\mathrm{a}\mathrm{x}}需要近似于穷举的搜索算法才能找出最佳值，本文为了保证对比有效性，跳过了n^{\mathrm{m}\mathrm{a}\mathrm{x}}的求解过程，这使得AGD算法获得了更优的分簇效果.

图6展示了不同相异性阈值时，本文算法与其他3种算法的性能对比.由于相异性阈值的改变会影响本文算法的分簇结果，所以此次仿真依然通过调整预设参数使得其他3种算法分簇的簇数与本文算法保持一致.从图中可以看出，当相异性阈值较小时，本文算法自适应分出更多的簇数，通信性能与AGD算法相差不多，相比K-means和GMM算法提升较大；随着阈值逐渐增大，簇数减少，四种算法间的性能差异逐渐减小直至近似.主要原因在于，当簇数少到一定数量时，4种算法的分簇结果基本无明显区别. 同时，本文算法性能在阈值变化过程中相对稳定，也说明了算法受相异性阈值的影响较小.

图7为FP功率分配算法迭代图.其中P=15 dB，T^{\mathrm{m}\mathrm{a}\mathrm{x}}=50.从图中可以看出，二次变换重构的凸问题，在CVX工具箱辅助下，大约能在10次迭代以内趋于稳定，在10次之后，和速率仍以较小增长率逐步递增，验证了FP二次变换处理原非凸问题的收敛性.

图8为不同发射功率下4种分簇算法与正交多址接入（Orthogonal Multiple Access，OMA）的总和速率对比.由图可知，本文算法在和速率性能上均优于其他3种算法，且随着发射功率的增大，分簇对系统带来的影响逐渐减弱.当发射功率为15 dB时，与AGD、GMM和K-means算法相比，分别提升大约2%、18%和31%；发射功率为40 dB时，减小为1%、10.4%和16%.实验表明，本文算法由于其合理的用户数和较大的簇内信道增益差异，使得同簇用户之间的干扰较低，最终在和速率性能上优于其他分簇算法.

图9展示了不同UAV数量时，四种算法的用户性能对比，其中总人数为100人，每个UAV的发射功率为15 dB.由图可知，当UAV数量少时，每个UAV服务用户数量较多，4种算法性能差异不大；随着UAV数量的增多，整体性能逐步上升，同时4种分簇算法带来的差异也逐渐增大 ，而本文算法的性能较其他3种算法更优.仿真结果表明，当UAV数量发生改变时，本文算法也能获得稳定的性能提升.

图10展示了不同用户数量时，四种算法的用户性能对比，其中UAV数量为5.由图可知，随着用户数量增多，4种算法的性能均呈下降趋势，主要原因在于用户数量的增多导致用户间的干扰增大，造成了部分性能损失.在性能下降过程中 ，本文算法较其他3种算法带来的提升基本稳定，没有出现因用户数量变化导致性能不佳的情况出现.仿真结果表明，本文算法对用户数量的变化不敏感，可适应不同用户数量的应用场景.

7 结 论

针对多无人机辅助NOMA下行通信的网络模型，制定了和速率最大化的优化问题.由于目标函数的强耦合性与非凸性，本文将原问题解耦为UAV位置部署、用户分簇与功率分配3个子问题分别求解.仿真实验表明：

1） 与其他算法相比，本文分簇算法能获得更均匀的簇用户数、更大的簇内信道增益差异，在和速率性能上具有明显提升.

2） 在用户数与UAV数量发生改变时，所提算法和速率均能保持稳定.

3） 利用FP二次变换的方法，重构原非凸问题，交替优化辅助变量与功率分配因子，和速率具有良好的收敛性.

参考文献

[1] WANG L Y， ZHANG H X， GUO S S，et al ．3D UAV deployment in multi-UAV networks with statistical user position information［J］．IEEE Communications Letters，2022，26（6）：1363-1367．

[2] NEW W K， LEOW C Y， NAVAIE K，et al ．Aerial-terrestrial network NOMA for cellular-connected UAVs［J］.IEEE Transactions on Vehicular Technology，2022，71（6）：6559-6573．

[3] TRAN T N， NGUYEN T L， VOZNAK M ．Approaching K-means for multiantenna UAV positioning in combination with a max-SIC-min-rate framework to enable aerial IoT networks［J］．IEEE Access，2022，10：115157-115178．

[4] YADAV A， QUAN C， VARSHNEY P K，et al ．On performance comparison of multi-antenna HD-NOMA，SCMA，and PD-NOMA schemes［J］．IEEE Wireless Communications Letters，2021， 10（4）： 715-719．

[5] MOUNI N S， KUMAR A， UPADHYAY P K ．Adaptive user pairing for NOMA systems with imperfect SIC［J］．IEEE Wireless Communications Letters，2021，10（7）：1547-1551．

[6] PEER M， BOHARA V A， SRIVASTAVA A，et al ．User mobility-aware UAV-BS placement update with optimal resource allocation［J］．IEEE Open Journal of the Communications Society，2022，3：1853-1866．

[7] 李国权，林金朝，徐勇军，等 ．无人机辅助的NOMA网络用户分组与功率分配算法［J］．通信学报，2020，41（9）：21-28．

[8] LI G Q， LIN J Z， XU Y J，et al ．User grouping and power allocation algorithm for UAV-aided NOMA network［J］．Journal on Communications，2020，41（9）：21-28．（in Chinese）

[9] LIU X N， WANG J J， ZHAO N，et al ．Placement and power allocation for NOMA-UAV networks［J］．IEEE Wireless Communications Letters，2019，8（3）：965-968．

[10] KATWE M， SINGH K， SHARMA P K，et al ．Energy efficiency maximization for UAV-assisted full-duplex NOMA system：user clustering and resource allocation［J］．IEEE Transactions on Green Communications and Networking，2022，6（2）：992-1008．

[11] 彭艺，吴桐，杨青青 ．下行RIS-NOMA的用户集群方法［J］．中山大学学报（自然科学版），2024，63（1）：128-136．

[12] PENG Y， WU T， YANG Q Q ．User clustering method for downlink RIS-NOMA［J］．Acta Scientiarum Naturalium Universitatis Sunyatseni，2024，63（1）：128-136．（in Chinese）

[13] CUI J J， DING Z G， FAN P Z，et al ．Unsupervised machine learning-based user clustering in millimeter-wave-NOMA systems［J］．IEEE Transactions on Wireless Communications，2018，17（11）：7425-7440．

[14] GAO X Y， LIU Y W， LIU X，et al ．Machine learning empowered resource allocation in IRS aided MISO-NOMA networks［J］．IEEE Transactions on Wireless Communications，2022，21（5）：3478-3492．

[15] LIN Y S， WANG K D， DING Z G ．Unsupervised machine learning-based user clustering in THz-NOMA systems［J］．IEEE Wireless Communications Letters，2023，12（7）：1130-1134．

[16] KATWE M， SINGH K， SHARMA P K，et al ．Dynamic user clustering and optimal power allocation in UAV-assisted full-duplex hybrid NOMA system［J］．IEEE Transactions on Wireless Communications，2022，21（4）：2573-2590．

[17] FAHY C， YANG S X， GONGORA M ．Ant colony stream clustering：a fast density clustering algorithm for dynamic data streams［J］．IEEE Transactions on Cybernetics，2019，49（6）：2215-2228．

[18] FAHY C， YANG S X ．Finding and tracking multi-density clusters in online dynamic data streams［J］．IEEE Transactions on Big Data，2022，8（1）：178-192．

[19] CAO F， ESTERT M， QIAN W， et al. Density-based clustering over an evolving data stream with noise［C］//Proceedings of the 2006 SIAM international conference on data mining. Society for industrial and applied mathematics， 2006： 328-339.

[20] LIU A， LAU V K N， KANANIAN B ．Stochastic successive convex approximation for non-convex constrained stochastic optimization［J］．IEEE Transactions on Signal Processing，2019，67（16）：4189-4203．

[21] ZAPPONE A， BJÖRNSON E， SANGUINETTI L，et al ．Globally optimal energy-efficient power control and receiver design in wireless networks［J］．IEEE Transactions on Signal Processing，2017，65（11）：2844-2859．

[22] SHEN K M， YU W ．Fractional programming for communication systems：Part I：power control and beamforming［J］．IEEE Transactions on Signal Processing，2018，66（10）：2616-2630．

[23] DUONG THI THUY N， NAM BUI D， DUONG PHUNG M，et al ．Deployment of UAVs for optimal multihop ad-hoc networks using particle swarm optimization and behavior-based control［C］//2022 11th International Conference on Control，Automation and Information Sciences （ICCAIS）．Hanoi，Vietnam． IEEE，2022：304-309．

[24] 周宇超，杨洁，曹雪虹 ．自适应遗传算法下的NOMA用户动态分簇［J］．信号处理，2021，37（5）：835-842．

[25] ZHOU Y C， YANG J， CAO X H ．User dynamic clustering in downlink NOMA based on adaptive genetic algorithm［J］．Journal of Signal Processing，2021，37（5）：835-842．（in Chinese）

基金资助

国家自然科学基金资助项目(61761025)

National Natural ScienceFoundation of China(61761025)

云南省计算机技术应用重点实验室开放基金资助项目(2021102)

Development Fund of Key Laboratory of Computer Technology Application in Yunnan Province(2021102)