基于谱聚类的异构蜂窝超密集网络高能效资源分配算法

王雪，刘京，孙佳妮，张继真，钱志鸿

（1.吉林大学通信工程学院，吉林 长春 130012；2.中国科学院长春光学精密机械与物理研究所，吉林 长春 130033）

1 引言

随着5G 通信系统的发展，越来越多的智能连接设备带来了指数级的网络流量增长。传统的频谱管理方案和蜂窝结构已经不能满足激增的流量需求[1-2]。传统蜂窝结构通过宏基站覆盖通信用户，针对宏基站的占地面积大、部署基建成本高昂且不能保障小区边缘用户的服务质量等难题，超密集异构蜂窝网络（UDN，ultra-dense heterogeneous cellular network）在这种背景下应运而生[3]。5G 关键技术的目标之一是使移动数据量达到当前长期演进（LTE，long term evolution）系统的1 000 倍，而UDN正是实现此目标的关键技术之一[4]。UDN 通常由大量不同类型的低功率小型基站（BS，base station）组成，其部署密度远高于当前的移动通信网络，遍布车站、商场和办公楼等热点区域，或信号难以到达的阴影区域，可以大幅提高流量容量和数据的传输速率[5]。但是，UDN 不断增加的网络规模势必会带来越来越严重的小区干扰，因此缓解干扰并寻找有效的资源分配方案来提高系统性能，逐渐成为UDN 的关键问题之一，且受庞大的计算复杂度限制，传统有效的资源分配难以直接利用在UDN 之中[6-8]。

为了解决UDN 场景资源紧缺的问题，文献[9]提出了一种基于服务质量的UDN 跨层合作传输方案，定义了宏基站和微基站的发射功率之比的协作信噪比阈值，并利用随机几何理论分析了其对信号数目的影响，从而优化了子载波分配和功率分配，减轻了干扰并提高整个网络的吞吐量。除此之外，采用聚类分析的资源分配方案逐渐展现出优势，可以通过把微基站分簇成数个子网络，大大简化网络拓扑，从而有效降低UDN 资源分配的复杂度[10]，同时也更方便研究降低基站间干扰的问题，提高了算法的可行性。文献[11]提出了一种基于图着色的集群资源分配算法，将控制平面和用户计划分开，有效地利用宏基站节点向用户分配资源。文献[12]考虑实际场景中的邻域关系，提出了一种图聚类方案，并将每个小区簇中的用户设备分组，为每个用户组分配子信道实现干扰降低。文献[13]使用改进的基站聚类算法，根据基站的密度动态调整聚类的数量，同样将用户设备划分为多个组，通过资源分配使用户集群内干扰最小。文献[14]则在通过构建用户冲突图提出一种低复杂度的用户聚类将用户分组，并考虑在用户簇间的干扰提出一种子信道分配算法，可以进一步减少频谱复用带来的干扰。文献[15]提出一种新颖聚类算法，可以通过甄别信道独特的特点，将二级用户分组进行资源分配来提高集群的吞吐量。虽然聚类分析方案具有一定优势，但是现阶段基于聚类分析的资源分配方案研究大多是从地理位置上进行基站分簇，并且很少抓住用户之间的干扰关系进行用户分组来进行信道划分。因此，十分有必要改进聚类分析模型，实现在频率资源分配阶段弱化同频干扰，提高系统性能。

超密集异构蜂窝网络不仅面临频率资源紧张的问题，而且庞大数量的通信设备所带来的功耗问题也变得更加严重，绿色通信已成为下一代网络的主要追求目标[16]，因此需要将研究重点从追求提高数据速率和容量转移到提高能量效率上，能量效率也逐渐成为新的系统性能指标。文献[17]推导验证了以用户为中心的异构蜂窝网络中整个网络的能量效率表达式，为提高网络的能量效率、达到绿色通信的网络部署提供了理论指导。文献[18]提出了一种基于聚类的节能资源管理方案来减轻干扰，基于两步子信道分配和基于非合作博弈的功率分配方案来最大化网络能量效率。文献[19]提出应用两级子信道分配算法和基于对数函数的功率控制方案在保证系统能效的同时，有助于提高系统的吞吐量和频谱效率。但是受限于庞大的基站数目，这些能量效率优化方法在异构超密集网络下并不具备良好的适应性。

因此，面对超密集异构网络亟待解决的能量效率问题，在密集部署的基站场景中，需要结合聚类分析资源分配方案简化模型的优势，改进聚类分析模型，削弱同频干扰，合理进行功率分配来有效提高系统能效。基于此，本文在下行两层异构蜂窝超密集网络模型下，研究非凸、非线性、多变量耦合的能效优化问题，主要的创新性工作如下。

1) 建立频率资源分配子问题模型，从频率资源分配过程中基站、用户、资源块3 个层面改进聚类分析模型，分别对应提出了改进的k-means 算法对通信网络内的微基站分簇，定义了局部基站分布密度概念，自适应动态划分基站簇大小和聚类中心的位置，极大降低簇间干扰；结合信道损失构建用户干扰关系权重图，提出了基于谱聚类算法的基站簇内用户分组策略，快速高效地得到同频干扰差异用户组；结合贪婪资源块分配算法为不同的用户组分配正交的频率资源，有效削弱了簇内干扰。

2) 针对较大基站数量模型下的功率适配问题，以优化能效为目标建立功率资源分配子问题模型，利用Dinkelbach 方法将分式非凸问题转换为凸函数约束寻优问题，结合拉格朗日乘子数学理论算法的精确高效等优势，创新性应用于UDN 多基站模型，推导并解决多基站模型下的功率迭代表达式，得到各基站各资源块下的最佳功率，对每个基站簇内的功率进行合理分配。仿真结果表明，本文算法具有很好的收敛性，并且在提升异构蜂窝超密集网络的能效方面具有良好的性能。

2 系统模型

本文考虑两层异构蜂窝下行超密集网络，即在网络中含有一个中心宏蜂窝基站（MBS,macro base station）和多个微蜂窝基站（FBS,femto base station），如图1 所示。宏基站节点和所有的微基站节点全部连接到一个局域网关服务器中，通过这个服务器作为中心控制器管理调度整个网络的资源分配任务。所有微基站用集合F 表示，即F={1,…,f,…,F}，为了模拟实际的应用场景，微基站被随机地分布在二维欧氏空间A 中，构造密度为λf的齐次泊松点过程（HPPP,homogeneous poisson point process）[2]，同样，户外的用户设备（UE,user equipment）按照密度为λout的HPPP 随机分布在空间A 中，其中MBS 直接覆盖范围Rmac内的宏用户，用集合Im表示，其余的UE 把距离最近的微基站作为各自提供通信服务的基站，所有由微基站服务的UE 用集合If表示，即 I={1,…,i,…,I}。

图1 异构蜂窝超密集网络模型

考虑异构蜂窝下行链路所有的FBS 复用同一个频谱，基站节点到UE 建立瑞利信道衰落模型，可以将每个频谱均分成K个正交的资源块（RB,resource block），资源块的集合可以表示为K={1,…,k,…,K}。假设一个RB 最多被安排给一个UE 使用，并且在信号覆盖区域内，复用同资源块的UE 在通信中会产生干扰，而采用不同资源块的UE 由于资源块之间是正交的，故在通信中不会产生干扰。

针对下行链路的通信过程，对于小区中的每一个宏基站用户i来说，其通信业务由宏基站直接提供服务，并且单独复用一个频段，不与微基站频段产生重叠，因此，用户i在宏基站m服务下资源块k上的信号与干扰加噪声比（SINR,signal to interference plus noise ratio）可以表示为

对于复用另外频段的微基站的用户i，其在微基站f服务下资源块k上的SINR 为

其中，表示微基站f在资源块k上的发射功率，Gf,i表示从微基站f到用户i之间的信道增益，If,k表示由微基站f提供服务且采用资源块k的用户。

进一步地，可以得到宏基站用户和微基站用户的在资源块k上的传输速率为

其中，B表示每个资源块上的带宽。定义二进制布尔变量表示用户i是否复用宏基站m或微基站f的资源块k，即

整个网络的吞吐量可以表示为

其中，P 表示每个基站的功率可行域。

对于每个基站的功率消耗问题，可以分为2 个部分，即传输功率和电路功率[20]，在下行传输过程中，系统的总功率消耗可以定义为

其中，Pcir,m和Pcir,f分别代表单个宏基站和单个微基站的电路功率。

因此，整个网络的能量效率可以定义为网络总吞吐量与总功率消耗的比值，通过优化资源块和功率的分配方案，可以将最大化能量效率的优化问题表示为P1。

其中，约束条件C1、C2、C6、C7 表示资源块仅能分配给一个用户，且一个用户只能被分配一个资源块；约束条件C3、C4 表示被分配的功率不能是负值；约束条件C5 表示分配给所有用户的功率总和不能超过当前基站的负荷。

3 基于谱聚类分析的UDN 资源分配方案

通过分析异构超密集蜂窝模型可以看出，寻找解决数量更多的微基站的资源分配问题的方案，是提高系统网络能量效率的重点，因此本文主要以微基站资源分配算法分析为主。

从式(8)可以看出，同时优化频率资源块X和功率P的分配方案是一个难以直接解决的NP-hard 问题[21]。为了在合理的复杂度内解决资源分配的问题，原问题可以分解为资源块分配和功率分配2 个子问题。尽管如此，从超密集异构蜂窝网络的大量微基站中搜集分析资源分配的策略和信息仍旧是一个很大工作量的难题，因此，本文针对性地提出基于能效的聚类分组的资源分配方案，该方案可从聚类分组层面和资源分配层面进行分析。

由现状分析可知，改进并利用聚类分析模型可简化网络拓扑，从而有效降低UDN 的资源分配的复杂度，本文从基站分簇和用户分组两部分改进聚类分组层面模型，首先，针对现有常用k-means 聚类算法难以确定聚类中心数目及位置的不足，本文采用改进的k-means 算法，引入密度筛选前置过程，对蜂窝小区中的微基站进行自适应分簇，将相互间干扰最大的基站分成一个簇，使簇间干扰尽可能降至最小，甚至忽略不计。接着，为了降低基站簇内的干扰，针对现有基于聚类分析的资源分配方案研究多从地理位置上进行基站分簇，很少抓住用户之间的干扰关系进行用户分组来进行信道划分的不足，本文利用谱聚类算法，在发挥降维分组优势的同时，结合用户之间的干扰关系，对基站簇内的用户进行分组，将相互影响较小的用户分为一组，为其分配同一资源块，而不同的用户组则分配正交的频率资源块，避免不同用户组之间产生干扰。通过提出改进k-means 基站分簇与谱聚类用户分组策略，从物理位置与个性化干扰关系上详尽分析并区分了干扰类别，尽可能地降低簇间干扰与簇内干扰。资源分配层面包含频率资源分配和功率资源分配。首先，在基站分簇与用户分组之后，正如用户分组的目的，将正交的资源块按照贪婪算法分配顺序分给不同的用户组，降低簇内干扰。频率资源块分配完成后，在功率分配阶段，以能量效率为目标，采用Dinkelbach 方法将能量效率的非凸优化问题转化为凸问题，同时结合聚类方法，利用拉格朗日乘子法迭代求解大数量基站功率分配的约束寻优问题。

由此，通过执行改进的k-means 微基站分簇算法、谱聚类的用户分组算法、正交资源块分配以及基于Dinkelbach 和拉格朗日乘子法联合功率分配算法四步顺序性过程，实现了网络能效最优的UDN资源分配方案。

3.1 基站分簇问题

传统的k-means 算法简单易行，收敛速度快，且常以欧几里得距离作为相似性度量，从而基于一些预定聚类中心获得最佳分类聚类[22]。通常情况下，微基站往往会对邻近的其他微基站产生较强的干扰，因此将这些基站分到同一个基站簇内，然后给它们安排正交的资源块从而减少簇内干扰。鉴于存在相互干扰的基站之间往往距离很小，为了准确地对微基站进行聚类，本文引入局部分布密度代替距离来评估微基站的靠近程度。首先定义微基站j的分布密度λj为所有微基站两两距离之和与微基站f到所有其他基站的距离之和的比值，即

其中，dj,k和dm,n皆表示2 个微基站之间的距离，显然，越多的微基站位于微基站j附近，其分布密度就越大。

特别地，为了避免区域边界较远的基站之间距离的值对分布密度计算产生的误差，本文引入截断距离dtr，可依据区域范围、仿真分簇结果以及经验数据设置，忽略超过截断距离的基站间距离，即，则局部分布密度可以更新为

在局部分布密度的基础上，利用本文提出的改进k-means 基站聚类算法，定义所有微基站的平均分布密度为

首先，计算整个蜂窝小区中所有微基站的分布密度及小区平均分布密度，选出密度高于平均密度的基站，将它们的位置点坐标加入聚类中心候选集C。至此，在聚类中心候选集中，存在聚类中心较接近的情况，这不利于k-means 聚类，为进一步筛选，定义距离阈值为

其中，μ是调整聚类大小的比例系数，随基站密度动态变化，可设置为关联于实际应用场景范围、用户密度的系数函数，依照实际场景和经验调整系数。当聚类中心候选集中某2 个点坐标的距离小于距离阈值Rc时，需要对2 个点对应的微基站的分布密度进行比较，选取较大点进行保留，将较小点从聚类中心候选集中移除，如二者相等，则任意保留其中一个。遍历所有点之后，最终得到的聚类中心候选集中的坐标，即为k-means 聚类的初始聚类中心点的位置。根据初始聚类中心和微基站之间的距离，采用k-means 聚类算法最终得到基站簇的聚类结果。详细的聚类过程执行步骤如算法1 所示。

算法1改进k-means 基站分簇策略算法

初始化依据式(9)～式(11)计算每个微基站的局部分布密度λ'和平均分布密度；依据式(12)及实际需求，计算阈值距离Rc；微基站待选集F，聚类中心候选集C；

图2 展示了2 种不同数量微基站场景下，执行算法1 中改进k-means 基站分簇策略后的聚类结果示意。其中，微基站和用户皆按照HPPP 随机分布。由图2 可知，宏基站处在区域正中央，其近区域覆盖范围内的用户接收到的宏基站信号较强，故采取直接由宏基站服务的策略，微基站依据动态选取的聚类中心被划分为多个基站簇，除受宏基站服务的用户外，其余随机分布的用户按照基站簇的范围归入不同的基站簇并由该簇内的微基站服务。图2(a)和图2(b)分别展示了随机部署微基站的数量为63 个和243 个时的分簇划分情况。从图2 中可以看出，当微基站的数目变多时，聚类中心即基站簇的数目也在增加，这是因为所提基站分簇算法可以动态调整基站簇的数目，并且每个基站簇内的微基站数分布较平均。

图2 随机部署基站分簇示意

3.2 用户分组问题

由于存在频率复用，在每个基站簇内，同一频率下还是会存在很强的干扰。为了最大限度地降低簇内干扰，在基站簇内为用户分配使用正交的频率资源。但由于用户数目较多，为减少算法复杂度，本文提出一种基于谱聚类[23-24]的用户分组算法，其本质是一个切割无向权重图，强化子图内部相似度、弱化子图间相似度的过程，且其求取特征向量降维的过程常常用在高维聚类中，十分适用于本文的用户分组场景中，使干扰较小的用户成为一组，为不同的用户组分配正交的资源。

首先，在异构蜂窝网络中，以其中一个基站簇为例，基站簇中的所有微基站用集合Fc= {1,2,…,Fc}表示。将宏蜂窝用户和微蜂窝用户看作图的顶点，构造一个无方向权值连接图 G((V,E)，向量集合V= {v1,v2,…,vn}表示当前基站簇内的用户集合，E表示连接顶点的边的集合，即点与点之间的关联矩阵，本文根据基站簇内的用户之间的信道干扰代替传统的点点之间的欧氏距离建立边集。

假设用户a,b都受基站簇内微基站服务，首先定义用户a,b的相关信道损失值β分别为

其中，微基站i指代的是为用户传输信号的基站，微基站j指代的是基站簇中除传输信号基站外的其他基站，这些基站产生的信号会对用户产生干扰，pl为信道损失[25]。显然，相关信道损失值反映了微基站在基站簇中信道表现的情况，β值越小，代表传输有用信号的信道质量较好，有干扰的信道影响较小，更有利于信号的传输。

然后，需要建立关联矩阵，即构造一个无方向权值连接图G 的边集，利用提出的相关信道损失值β的概念，定义权重边值为

其中，w为谱聚类算法中相似度矩阵中元素。

根据式(15)，构建两用户之间的相似度关联矩阵

且规定相似度矩阵的每行元素的和为该顶点的度，故损失干扰图G 的度矩阵为，其中，，定义图G 的非规范化拉普拉斯矩阵为L=D−W，对矩阵L进行规范化处理，得到规范化拉普拉斯矩阵

最后，计算矩阵Lsym前K个最小特征值所对应的特征向量v={v1,v2,…,vK}，并定义v作为第一矩阵，即，接着规范化第一矩阵U1的每一行，得到第二矩阵

利用k-means 算法对矩阵U2进行聚类，得到用户组分组结果。至此，完成聚类分组层面的过程。详细的谱聚类过程执行步骤如算法2 所示。

算法2谱聚类用户分组策略算法

初始化计算基站簇内所有用户到所有基站的信道损耗pl，依据式(13)～式(16)初始化无方向权值连接图 G(U,E)；随机初始化m个聚类中心；

1) 依据式(17)计算得到规范化拉普拉斯矩阵Lsym；

2) 计算矩阵Lsym前K个最小特征值所对应的特征向量v={v1,v2,…,vK}；

4) 利用k-means 算法对矩阵U2进行聚类；

5) 重复执行步骤4)的k-means算法直至聚类中心不再发生变化；

6) 返回用户组聚类结果。

3.3 资源块分配问题

完成聚类分组层面的过程之后，将进行资源分配层面的步骤，首先要对正交的资源块进行合理的分配。本文采用贪婪算法的思想，依据信道增益为各个用户组分配满足其吞吐量最大的相互正交的资源块，最终得到整个系统的频率资源分配方案。详细的资源块分配过程执行步骤如算法3 所示。

算法3资源块分配策略算法

初始化按照用户组GU 中包含用户的数量进行用户组的降序排序，得到用户组排序集合；剩余资源块集合L；

3.4 功率分配问题

完成频率资源块分配后，虽然平均分配资源块功率简便易行，但在利用不均的资源块上分配相同的功率，无疑增加了功率的浪费，明显不能适合高能效的性能目标，因此本文以能量效率为目标，优化功率分配。由于超密集异构网络中的微基站数量众多，统一控制所有基站的功率分配是不切实际的。功率分配算法[26]虽能交替求解增广拉格朗日函数中的每个变量，解决单个基站能效目标函数中多变量的优化问题，较适合应用在分布式结构网络中，但是在集中覆盖的超密集网络功率分配问题上，集中控制的全局调控十分必要，对于整个网络的能效提升更加有效；拉格朗日乘子方法作为传统有效的凸优化解决方法，解决全局最优问题便捷，但无法直接移植应用在高维度的密集场景中，且现有研究尚未结合聚类方法应用在密集复杂的场景模型中。因此，本文通过结合前文聚类结果，利用拉格朗日乘子方法给每个基站簇分配功率以最大化其自身的能量效率，在降低总体复杂度的同时，提高整个系统的能效。

结合基站分簇的结果，以其中一个基站簇为例，在基站簇的范围内，所有的微基站用集合Fc={1,2,…,fc,…,Fc}表示，分配可用的资源块用集合 Kc= {1,2,…,kc,…,Kc}表示，所有的用户用集合Ic= {1,2,…,ic,…,Ic}表示。对于微基站fc复用资源块kc的用户ic，结合上文系统干扰模型可知，微基站fc的SINR 表示为

用户ic的传输速率为

基站簇内的总吞吐量为

其中，Pc是基站簇待分配功率的可行域。

在下行传输过程中，基站簇系统的总功率消耗可以定义为

因此，整个基站簇网络的能量效率可以定义为网络的总吞吐量与网络总功率消耗的比值，通过优化功率分配方案，可以将最大化能量效率的优化问题表示为P2。

其中，约束条件C1、C4 表示资源块仅能分配给一个用户，且一个用户只能被分配一个资源块；约束条件C2 表示被分配的功率不能是负值；约束条件C3 表示分配给所有用户的功率总和不能超过当前基站的负荷。

从结构中可以看出，P2 是一个混合整数非线性分数规划问题，难以在一个多项式时间中求解[27]。首先，本文采用Dinkelbach 算法[28]将能量效率的非凸优化问题转化为凸问题。定义q*为P2 的最优解，即则优化能效的P2 可以看作

当且仅当q=q*时，有

因此，问题P2 可以等同转化成一个减式形式问题P3。

记Dinkelbach 迭代的索引和最大迭代次数分别为n∈ {1,2,…,Iouter}和Iout。假设在第n次迭代中，计算的功率值和q值分别表示为和q(n)，定义拉格朗日函数为

根据KKT（Karush-Kuhn-Tucker）条件，可以求得最优解

拉格朗日乘子更新为

其中，τ∈ {1,2,…,Iinner}表示拉格朗日乘子的迭代次数，Iinner为拉格朗日对偶分解的最大迭代次数；δ表示迭代更新时每次变化的步长。具体功率分配算法过程如算法4 所示。

算法4基于Dinkelbach 和拉格朗日乘子方法的功率分配策略算法

初始化初始化外循环索引n，内循环索引τ,优化因子q(0)；拉格朗日乘子θ；最大迭代次数Iouter,Iinner；功率初值；收敛偏差 Δ1,Δ2；

4 复杂度分析

本文提出的能效优化算法由4 个部分组成，分别是微基站分簇过程、用户分组过程、资源块分配过程和功率分配过程。对于微基站分簇过程，采用改进的 k-means 算法，最大复杂度为O(2F2+FC nn)，其中，O(2F2)是最差情况下计算F个微基站分布密度、确定聚类中心过程的复杂度，O(FC nn) 是k-means 聚类算法的复杂度，Cn是基站聚类中心的数目，即基站簇的数目，n是k-means聚类算法的迭代次数。用户分组过程采用谱聚类算法，在每一个基站簇中，最大复杂度为O(K c2t)，其中Kc既是资源块的数目，也是用户组的数目，谱聚类算法只取前Kc最小特征值所对应的特征向量构建关系矩阵进行k-means 聚类，t是对应的迭代次数。资源块分配过程的最大复杂度为。功率分配过程的最大复杂度为O(FcK cIouterIinner)，其中，Iouter和Iinner分别为外循环和内循环的最大迭代次数。因此，整体上完成基站分簇，并在每个基站簇内分别完成资源分配最大化能量效率，所提资源分配方案的最大复杂度为。

对于整个异构蜂窝超密集网络，在不进行基站分簇以及用户分组的情况下，直接进行资源分配方案的最大复杂度应为O(FKI+FKIouterIinner)，其中，F≫Fc。因此可以看出，随着基站密度增加，尽管在本文所提方案中的基站分簇和用户分组过程引入了一些算法的复杂性，但它们实现了动态分配聚类中心，简化了网络分析拓扑结构，有效地弱化了同频干扰，并且降低了UDN 场景下资源分配的计算复杂性，基站密度越大，所带来的复杂度优化越明显。

5 仿真分析

本文进行了超密集异构蜂窝网络的仿真验证，对所提通过降低干扰和优化能效的资源分配方案的有效性进行了分析，在300 m×300 m 的仿真UDN覆盖范围中，经过多次仿真参数调试，最终确定了改进k-means 基站分簇算法中截断距离dtr和比例系数μ的取值，具体设置和环境参数取值如表1所示。

表1 仿真参数

本文提出的基于谱聚类的异构蜂窝超密集网络高能效资源分配方法包括基站分簇、用户分组、资源块分配、功率分配4 个过程，具体对应第3 节中所陈述的4 种算法，即算法1 改进k-means 基站分簇策略算法，算法2 谱聚类用户分组策略算法，算法3 资源块分配策略算法，算法4 基于Dinkelbach和拉格朗日乘子方法的功率分配策略算法。将所提方案与其他6 种资源分配方案进行对比，在单一环节上采用不同算法，从而形成差异的资源分配方案，比较不同算法在不同通信环节中的性能差异，具体资源分配方案如表2 所示。方案S2、S3 着重对比用户分组和资源块分配算法性能，方案S4、S5、S6、S7 对比了不同功率分配算法下的性能。其中，采用了文献[15]中的依照信道损失值建立用户间联系，利用k-means 对二级基站用户预分组算法（以下简称KMUG 算法）；文献[13]中的2 种对比算法，分别为直接随机为每个用户复用资源块的随机分配算法（以下简称RARB 算法）和将微基站可用功率平均等分给每个资源块的平均功率分配算法（以下简称AGPA 算法）；文献[26]中的基于交替方向乘子方法的资源块功率分配算法，本文场景中，在每个基站簇内以每个基站的能量效率为优化目标函数，交替求解增广拉格朗日函数中每个基站资源块上的功率（以下简称ADMM 算法）。

表2 资源分配方案

图3 给出了单个基站簇不同用户数目下分别采用谱聚类和k-means 聚类的基站平均分簇时间。随着基站簇内用户数目的不断增多，k-means 聚类算法的时间在不断增加，而本文的谱聚类算法在用户数目较多时也能保持高速分簇，但在用户数目相对较少时，每个用户的关联性不高，求解的特征向量矩阵相对复杂，故曲线上存在一个下降的趋势，随着用户数目增多，受限于地理位置，用户间的关联性越来越明显，曲线趋于稳定。这是因为谱聚类算法是一种基于图论的聚类方法，通过对样本数据的拉普拉斯矩阵的特征向量进行聚类，从而达到对样本数据聚类的目的，可以理解为将高维空间的数据映射到低维，然后在低维空间用其他聚类算法进行聚类，这种降维的方式在处理大数据时可以明显提高效率，大大缩短计算时间。

图3 用户分组时间与基站簇内用户个数的关系

平均功率分配状态下，图4 给出了在进行基站分簇和用户分组后不同微基站密度下的网络吞吐量。从图4 中可以看出，随着微基站密度的增大，网络的吞吐量基本呈上升趋势，这是因为布置大量的微基站可以有效兼顾每个用户，从而提高网络的吞吐量。同时，可以看到，所提的谱聚类用户分组算法在进行资源分配后，对吞吐量的提升明显优于k-means 聚类算法和随机分配算法。另外，方案S4 和S5 的曲线都要优于方案S6，这是因为用户分组在提升利用了信道损失构建关系矩阵，通过分组有效地降低了簇内干扰，提高了网络的吞吐量。方案S4 的曲线优于S5，这是由于谱聚类算法在处理稀疏矩阵时更能抓住数据特征，用户分组更加合理。

图4 网络吞吐量与基站密度的关系

为多方面验证所提算法的收敛性，图5 给出了所提功率分配算法过程中各基站簇与平均能量效率随迭代次数的变化情况。其中，C1～C8 对应基站簇的编号。图5(a)中每条曲线分别代表一个基站簇内的功率分配过程，可以看出，受基站分簇的影响，不同基站簇内的基站数和用户数的不同影响了该基站簇的能量效率的大小，但每个基站簇的能量效率都在5 次迭代左右可以达到收敛。图5(b)则是整个网络的平均能量效率随迭代次数的变化，同样可以看出，平均能量效率在5 次左右达到稳定，这也证实了本文提出的功率分配算法是收敛的。

图5 平均能量效率与迭代次数关系

图6～图8分别给出了不同对比方案的系统平均能量效率随基站密度的变化。从图6 中可以看出，S4、S5、S6 这3 条曲线都为下降趋势，这是因为在平均功率分配下，随着基站密度的增加，吞吐量的提升是有限的，而传输能耗和电路能耗也在大幅增加，结合图4 网络吞吐量与基站密度的关系，在不受功率分配算法影响时，网络吞吐量随着微基站密度的增长逐渐变化不是很明显，故在基站密度变化的整个过程，系统吞吐量的增益带来能量效率的增益无法补偿功耗增加带来的负面影响，引起了系统能量效率的降低，其中方案S4、S5 要优于方案S6，这是因为用户分组算法有效降低了簇内干扰，提高了网络速率，进而提高了能量效率，而谱聚类算法效果要优于k-means 聚类算法，故方案S4效果最好。

图6 方案S4、S5、S6 的网络平均能量效率与基站密度的关系

从图7 中可以看出，方案S1、S7 的曲线呈现波动的趋势，原因是本文所提算法中的自适应控制基站簇的数目变化时，影响了基站簇中基站和用户的数量，故呈现出的能量效率会有突然的变化，但由于无法补偿功耗不断增加带来的负面影响，总体上还是随着基站的密度呈现下降的趋势。S2 和S3则是呈现一种随基站簇数目略显波动的整体稳定趋势，这是因为在本文的仿真环境中，随着微基站密度的不断增大，基站间的干扰不断增强，吞吐量的提升就变得有限，功率分配算法也会接近优化能力的极限，导致能量效率不再上升，趋于稳定，同样，方案S1 与S7 在0.002 5 个/m2与0.0027 个/m2这2 个密度时，已经开始出现接近能力饱和的趋势，而方案S2 和S3 对应的资源块分配算法由于避免干扰的能力有限，相较S1 和S7 对应的谱聚类分组资源块分配算法提前达到了能力极限，并且随着微基站密度不断增加，所有方案算法上的优势最终会由于基站过于密集而弱化，能量效率会呈现出相近的状态，算法带来的优势不再明显。对比S1、S2、S3、S7 这4 条曲线，方案S1、S2、S7 在能量效率上相较S3 均有明显提升。这是因为功率分配算法不仅进一步降低了簇内基站的干扰提高了吞吐量，同时还节省了功率，进而提升了能量效率。从S1 和S7的曲线明显优于S2 可以看出，谱聚类用户分组算法的优势更加明显，而S1 的曲线随着基站密度的增加，逐渐接近并反超S7 曲线，这是因为ADMM算法虽能交替求解增广拉格朗日函数中的每个变量，解决单个基站能效目标函数中多变量的优化问题，但是因为每个基站的能量效率并不是面向全局调控的，所以在高基站密度下，其优化能效表现不如本文所提算法。

图8 将7 种资源分配方案的能效优化情况放在一起对比，可以明显看出，方案S1、S2、S3、S7这4 条曲线要远高于S4、S5、S6 这3 条曲线，随着微基站的密度越来越高，方案S1 的优化效果最佳，Small Cell 论坛中提出超密集网络的基站密度量化指标为室外场景中每平方千米部署150～1 000个小基站，对应的密度即0.000 15～0.001 个/m2。从图8 中可以明显看出，高于此范围时S1 方案的效果是最优的。除此之外，结合之前的结论，S1 方案对应的谱聚类用户分组方案，其在分组效率上也优于S2 方案对应的k-means 用户分组方案，因此，虽然随着基站密度增长，能量效率的优势不再明显，但是综合考虑能量效率和计算效率，S1 方案是更适合应用在高基站密度下的 UDN 场景的资源分配方案。

图9 和图10 分别给出了功率分配前后网络平均能效（λf= 0.002 5个/m2）的累计分布函数曲线。从图9 中可以看出，资源分配方案S4、S5 曲线在方案S6 右侧，这表明采用用户分组方案可以有效提高用户效率；方案S4 在最右侧也说明了谱聚类用户分组算法的通过有效降低簇内用户干扰，明显提高了网络的能量效率。

从图10 可以看出，在高密度的UDN 场景下，方案S1 能量效率提升的效果也要优于方案S2、S3和S7。同时，对比图9 中的数据可以看出，功率分配后网络平均能效要远优于功率分配之前的能效，这是因为所提功率算法通过为不同基站上的不同资源块分配恰当的功率，不仅降低了同资源块下的传输信号干扰，同时节省了功率，显著提高了能量效率。

图9 功率分配前网络平均能效的累计分布函数曲线

图10 功率分配后网络平均能效的累计分布函数曲线

算法复杂度和仿真结果分析表明，本文所提组合方案将资源分配过程中基站、用户、资源块3 个层面以及功率分配过程各环节的算法相结合解决NP-hard 问题，在结合基站分簇与用户分组降低算法复杂度和干扰的基础上，利用功率分配实现能效提升。具体到各环节，本文所提资源分配方案在UDN 模型中，利用改进的k-means 基站分簇算法实现了动态分配初始聚类中心和聚类大小，有效降低了资源分配的计算复杂性，并且基站密度越大，所带来的复杂度优化越明显；利用谱聚类用户分组的资源块分配算法，相较KMUG 用户分组算法有效改善了簇内干扰，极大提升了网络总吞吐量，并且谱聚类算法通过对样本数据的拉普拉斯矩阵的特征向量进行聚类，这种降维的思想大大节约了用户分组的时间，提高了算法效率；采用基于Dinkelbach的拉格朗日功率分配算法，合理分配各基站资源块上的发射功率，在节约功率消耗的同时，进一步削弱了同频干扰，在高基站密度下，较ADMM 和AGPA 功率分配算法明显提升了能量效率。但是，在动态调整基站簇大小时，会一定程度地影响基站簇中用户的数量，造成能量效率的波动，这需要在未来工作中进行改善。

6 结束语

本文研究面向能效最优的异构蜂窝超密集网络资源分配方案，建立了下行两层异构蜂窝超密集网络模型，将超密集网络资源分配这一非凸、非线性、多变量耦合的能效优化NP-hard 问题，拆分成了以弱化同频干扰的频谱资源分配子问题和最大能效的功率资源分配子问题。在频率资源分配方面，改进UDN 聚类分析模型，定义了基站分布密度，利用改进的k-means 算法为基站分簇，并结合信道损失构造干扰权重图，提出了基于谱聚类的基站簇内用户分组策略，为不同的用户组分配正交的资源，最大限度地降低簇间和簇内干扰。在功率资源分配方面，利用Dinkelbach 方法将目标函数转化为减数形式，创新性地将拉格朗日乘子法应用于大数量基站的功率与干扰特性的UDN 中，推导迭代求解公式，优化资源块分配功率，大大降低了同资源块下的传输信号干扰，在一定程度上提高了广泛部署微基站的能量效率，适合应用在高基站密度下的UDN 场景中。