基于K-means与Gale-Shapley算法的D2D干扰管理方案

陈发堂，陈永钛，陈 峰，王 丹

重庆邮电大学通信与信息工程学院，重庆400065

设备间通信是一种不需要借助基站，让用户设备之间直接进行数据通信的通信模式[1]。随着当今通信需求的日益增长，设备到设备（device to device,D2D）通信技术作为一种可以增加蜂窝系统资源复用率和系统总速率的方法吸引了广泛的关注。该技术引入了4 种不同类型的增益[2]：设备间高度接近引起的比特率增益、蜂窝用户和D2D 用户之间同时复用资源引起而获得的复用增益、当经由传统蜂窝通信模式的接入点连接时，使用单个D2D 模式而不是使用单独的上下行链路资源而获得的跳数增益、D2D 用户拓宽了蜂窝网络的覆盖范围而获得的覆盖增益。在第三代合作伙伴计划（3rd generation partnership project,3GPP）中，D2D用户被分配用于接收调度分配的时间和频域资源池，采用共享载波的模式与蜂窝网络复用资源[3]。由于D2D 用户与蜂窝用户共享下行链路资源时会产生严重的带内泄露及远近效应，因此侧行链路共享载波时只能选择上行链路资源。然而链路资源的共享不可避免会产生D2D 用户与蜂窝用户间的干扰，同时多个D2D 用户复用一条通信链路时，设备之间也会产生干扰，严重影响通信质量和网络性能[4]。因此，考虑如何有效控制干扰的资源管理算法成为蜂窝网下D2D 通信的研究热点。

一个有效的解决办法便是通过功率控制进行干扰管理，文献[5] 提出了一种预定义的最大功率电平用于干扰管理，从而达到降低D2D 发射机干扰强度的目的，保证蜂窝用户的通信质量。同时，复杂的功率控制算法常用于最小化功率消耗或者最大化整个网络的容量，如文献[6] 提出了基于粒子群的功率控制方案，但该方案所提算法的复杂度并不能满足当前通信的需求且容易陷入局部最优解。除了功率控制的方法，另一个高效的算法便是设计一种智能的资源管理算法。考虑干扰抑制的信道分配算法是D2D 通信干扰管理问题领域中的研究热点[7]。文献[8] 提出了一种基于两阶段拍卖的公平资源分配算法，在第1 阶段以最小化总的系统干扰为条件进行用户匹配，第2 阶段根据竞标数值进行用户匹配更新及剩余用户分配；文献[9] 针对公平和受限的情况下分别提出了基于贪婪的资源分配算法；文献[10] 将最小背包算法与贪婪算法进行结合。文献[8-10] 仅针对单个D2D 用户与蜂窝用户复用上行链路资源的情况，不能解决有限频谱资源与用户更优通信质量之间的矛盾。文献[11] 提出了用于干扰管理的一种基于背包的干扰感知算法资源分配算法，然而该算法并不能让所有D2D 用户处于公平竞争的状态且在许多情况下不存在可行解；文献[12] 提出了复用强度因子的概念，先执行匈牙利算法进行初始分配，再根据复用强度因子将剩余的D2D 用户复用到信道中；文献[13]提出一种新的基于贪婪算法的信道分配算法，将信道分配问题转化为图着色的问题；文献[14]将超图理论运用到信道分配中，以协调用户之间的相互干扰。文献[12-14] 所提算法复杂度过高，不能满足用户高速移动下实时完成数据互通的需求。通过前人的研究可知图论是解决此类资源分配问题的有效工具，然而传统的基于图的资源管理算法并不能很好地满足当今用户与日俱增的通信需求。因此，如何优化传统的图理论算法以满足当下的需求值得深入研究。

针对上述情况的不足，本文提出一种基于K-means 与Gale-Shapley 算法的D2D 通信干扰管理资源分配算法。在进行资源共享前，首先对D2D 用户进行处理，以最小化系统干扰为条件进行分组，在保证用户正常通信质量的情况下实现系统干扰最小化，同时实现蜂窝用户与D2D 用户的多对一复用。完成分组后，实施基于Gale-Shapley 稳定匹配算法的信道分配方案，保证用户的公平性并实现系统容量最大化。与基于贪婪的图着色算法、随机算法和传统的图着色算法比较可得，本文所提算法相较随机算法和传统的图算法在系统容量方面有15%∼50% 的提升，与基于贪婪的图着色算法相比，本文所提算法在牺牲一定系统容量换取了更高效的干扰管理，保证整个蜂窝网络的正常工作。

1 系统模型与问题规划

1.1 系统模型与信道模型

为更加直观地体现通信系统模型，我们考虑整个蜂窝网络由一个基站、N个蜂窝用户（以下简称CUE）和M个D2D 用户（以下简称DUE）组成，其中N={c1,c2,···,cn},n≤N，M={d1,d2,···,dm},m≤M。在这里DUE 一般由两部分组成，用dT 表示DUE的发射机，dR 表示DUE 的接收机。正交频分复用技术用于支持CUE 和DUE 的多址接入，其中有K条信道用于分配资源。在整个通信系统中，演进型基站（eNB）负责协调CUE 与DUE 之间的资源分配，用Pc表示CUE 的发射功率，Pd表示DUE 的发射功率。通过随机生成算法生成的蜂窝网络用户位置分布图如图1 所示。

图1 蜂窝网络用户位置分布图（N=10, M=20）Figure 1 Location map of cellular network users (N=10, M=20)

本文主要侧重于D2D 通信在蜂窝网络中上行链路的场景，当复用上行资源时，D2D 接收机会受到来自蜂窝用户的干扰，同时eNB 也会面临来自D2D 发射机的干扰。在本文描述的通信系统中，信道被建模为瑞利衰弱信道，因此各个信道响应都遵从独立且相同分布的高斯过程。在文献[15] 中描述了城市微系统（UMi）的路径损耗模型，本文借鉴使用的与距离相关的路径损耗模型如下

式中：d为不同设备之间的通信距离；fc为载波频率。

信道增益与干扰表示为信道损失与小尺度衰弱的乘积的形式

式中：PathLossa,b代表通信设备a 和通信设备b 之间的信道损失；ha,b表示通信设备a 和通信设备b 之间的小尺度衰弱。在接下来的公式中，Gc,eNB表示蜂窝用户与eNB 之间的信道增益，GdT,dR表示D2D 发射机与接收机之间的信道增益，GdT,eNB表示D2D 发射机对CUE在eNB 处的信道干扰，Gc,dR表示CUE 对DUE 在D2D 接收机的信道干扰，GdT′,dR表示D2D 用户之间的信道干扰。

1.2 问题规划

本文主要针对信道的分配问题，其中多个DUE 都会分配一个CUE，分配意味着DUE 与CUE 将会共享信道资源。我们的目标是在保证整个通信网络用户在正常工作的前提下，最大化整个系统的通信容量。当DUE 与CUE 共享信道资源时，不可避免会产生干扰，反之亦然。同时多个DUE 复用一条信道时，不同DUE 之间也会产生干扰，因此在eNB 处与DUE 接收机处的SINR 表达式为

式中：N0为噪声功率；I为相邻小区之间的干扰；是一个二进制变量，=0 表示该DUE不与该CUE 复用第k条信道，反之则代表复用该信道。

在整个通信网络中，干扰项主要由3 部分组成：

2）C2D 干扰项即式(4) 中的Gc,dRPc，这是CUE 在DUE 接收机处的干扰项，也可表达为蜂窝链路对D2D 链路的干扰；

整个蜂窝网络的通信链路及干扰示意如图2 所示。

图2 蜂窝异构网络中链路及干扰示意图Figure 2 Schematic diagram of link and interference in cellular heterogeneous network

根据香农公式可得整个通信网络的信道容量为

因此我们可以得到优化问题的目标函数及约束条件为(6)∼(9)

式(6) 为CUE 处的SINR 必须要大于门限值，在保证CUE 的正常工作的前提下与DUE共享信道资源；式(7) 为DUE 接收机处的SINR 必须要大于门限值，在保证DUE 正常工作的前提下尽可能多的复用多个DUE；式(8) 保证一条信道只能复用一个CUE，确保蜂窝用户之间不会互相干扰。

2 基于K-means 与Gale-Shapley 算法的D2D 干扰管理方案

在D2D 通信中，图论是对解决与蜂窝用户共享资源的一种非常有效的工具，然而传统的图论匹配算法仅支持一对一的匹配，而不能实现多对一的匹配，这对D2D 的发展造成极大的限制。为此，我们在进行匹配算法之前，先对DUE 进行预处理，采用K-means 聚类算法让DUE 成组，一个DUE 组与一个CUE 共享信道，这样既能运用图论的理论解决资源分配问题，又能够实现一对多的复用且保证用户间的公平性。

2.1 基于K-means 的用户分组算法

在利用K-means 算法实现用户分组前，首先进行蜂窝网络用户位置随机生成算法，使所有用户在限定范围内随机分布于小区中且DUE 的发射机与接收机距离限定在50 m 以内。

1）随机选取N个DUE 坐标作为初始聚类中心µ=µ1,µ2,···,µN；

为使该算法收敛，定义损失函数：

在K-means 用户分组算法中，最终优化目标为

假设当前目标没有达到最小值，可以通过固定每个分组的聚类中心µj，调整每个DUE的所属的分组φ(i) 来让目标函数减少，同样也可以固定φ(i)，调整每个分组的聚类中心达到最终优化目标。当目标收敛到最小值时，完成用户分组。通过分析等式(1) 与(4) 可得，通过K-means 算法，能够使D2D 用户得到有效分组。同时，将该分组算法与后续的Gale-Shapley算法结合使用，使得在获得系统容量提升的同时，能够有效降低用户之间的干扰影响。

2.2 基于Gale-Shapley 的资源分配算法

Gale-Shapley 资源分配算法的核心思想在于偏好表的建立。偏好表为两组待匹配的样本组中每个样本对别的组别中各个样本的喜好程度，例如样本组中1 号样本的偏好表为{3,1,2,4,5}，则表示该样本对对方样本组的样本最优先匹配意愿为3 号样本，其次为1 号样本，以此类推。在本文中，样本组分别为CUE：c1,c2,···,cn,n≤N及DUE组：j1,j2,···,jn,n≤N。CUE 样本组与DUE 组样本组建立的偏好表分别记为CU_LIKE与DU_LIKE。通过Gale-Shapley 匹配算法，根据双方偏好表的选择实现CUE 与DUE 组的匹配，最大化通信系统容量。

结合K-means 算法与Gale-Shapley 算法，本文设计的D2D 通信干扰管理方案如下：

步骤1初始化参数，随机生成CUE 与DUE 的坐标位置，设置各用户的发射功率，根据式(1) 计算路径损失并根据式(2) 计算各用户到eNB 的信道增益；从DUE 坐标点中随机选取N个点作为聚类中心；确定迭代次数x。

步骤2预分组过程，计算DUE 各点到聚类中心的距离，进行D2D 用户分组过程。在完成一轮分组之后，更新聚类中心点位置，重新执行步骤2，直到不再改变或者达到最大迭代次数停止。

步骤3对组成员进行筛选，根据式(1)∼(4)，为保证用户正常通信质量，对DUE 组用户进行筛选，让每组D2D 用户与蜂窝用户匹配进行SINR 的计算，如若存在某一设备的SINR小于门限值，则剔除D2D 组成员干扰贡献值最大成员，重新计算每个设备的SINR 直至所有设备均满足式(6)∼(7)。

步骤4建立Gale-Shapley 算法偏好表，将蜂窝用户和D2D 用户划分为两个点集合，同时建立蜂窝用户和D2D 用户组的偏好程度表，用于存储双方用户相互之间的偏好程度。通过分析式(3)∼(4)，将作为确定CUE 偏好表的依据，Gc,dRPc作为确定DUE偏好表的依据，建立CUE 偏好表和DUE 组偏好表，作为匹配算法的匹配依据。

步骤5执行Gale-Shapley 稳定匹配算法，轮询蜂窝用户，若当前蜂窝用户已有配对对象则跳过轮询，否则会根据当前轮询用户的偏好表，向偏好程度排位靠前的D2D 用户发起配对请求。如果当前D2D 用户未完成匹配则两者结成配对，否则被选择的D2D 用户将会根据自身偏好表选择配对对象。若发起请求的蜂窝用户在偏好表中的位置比当前已配对的蜂窝用户靠前，则被选择的D2D 用户会与之前匹配的蜂窝用户解除匹配，与当前轮询蜂窝用户匹配；反之则会拒绝配对请求，被拒绝的蜂窝用户会加入到下一轮次的轮询中。不断遍历剩余蜂窝用户，直至所有蜂窝用户完成配对或者当前配对阵容不再改变，算法终止。

3 仿真结果与分析

为了验证所提算法的性能，本文用Matlab R2020a 进行仿真。在小区半径为200 m 的蜂窝小区中，随机生成蜂窝用户与D2D 用户的位置。为保证仿真结果的可靠性，本文采用Monte Carlo 方法重复执行算法2 000 次，最后取平均值作为最终的仿真结果进行性能分析，具体仿真环境的参数设置如表1 所示。

表1 仿真参数Table 1 Simulation parameters

采用K-means 算法来完成用户分组，进行干扰管理，此算法复杂度为O(n ∗l ∗k ∗m)，其中n为样本点数，l为迭代次数，k为簇的数目，m为样本维度，因此该算法复杂度可简化为O(M)。在完成DUE 分组之后执行Gale-Shapley 算法完成DUE 组与CUE 共享信道资源，实现多对一复用，此算法复杂度为O(N2)。因此本文总的时间复杂度为O(M+N2)。

为了验证所提算法的性能，将基于Gale-Shapley 算法的D2D 干扰管理资源分配算法与基于贪婪的图着色算法（GGC）、随机算法（RA）和传统的图着色算法（GC）进行比较。同时为了更好的评估算法的公平性，采用Jain’s fairness 指数[16]来衡量各算法的性能，通过分析该公式可知随着该系数值的增加，算法的公平性越高，以此来确定设备是否获得了系统资源的公平共享。

在蜂窝用户数量为10 的情况下，不同算法在D2D 对数目逐渐增加的情况下对系统容量的影响如图3 所示。通过分析可得，本文所提算法在D2D 对数量小于20 时，系统容量远大于其余3 种算法的系统容量。当D2D 对数量大于20 时，所提算法与GC 和RA 算法相比，系统容量仍有较大的提升，与GGC 相比系统容量有所下降，原因是本文在满足蜂窝网络中所有用户通信质量的同时，为保证公平性，尽可能让更多的DUE 能够复用上行链路的资源所致。

图3 D2D 对数量对系统容量在不同算法下的影响(N=10)Figure 3 Impact of D2D pair quantity on system capacity under different algorithms (N=10)

图4 分析比较了各算法的Jain’s fairness 指数。通信链路在受到强干扰时，会极大地限制整个系统容量，因此分析各用户之间的干扰影响尤其重要。通过分析图4 可得，本文所提的算法实现较高的Jain’s fairness 指数，这是由于本文在用户分组阶段以最小化组别累计干扰值为目标，且在进行复用匹配时，旨在最小化整体干扰的情况下尽可能提升整个蜂窝网络的系统容量。与其余3 个算法相比，本文所提算法有较大的提升，可见本文所提算法的优越性。

图4 D2D 对Jain’s fairness 指数在不同算法下的影响(N=10)Figure 4 Impact of D2D pair quantity on Jain’s fairness index under different algorithms(N=10)

图5 分析了本文所提算法中蜂窝数量对整个系统容量的影响。通过逐渐递增蜂窝用户的数量，分别在DUE 对数量为30、40 和50 的情况下，研究了蜂窝用户数量对系统容量的影响。由图可得在3 种不同的情况下，蜂窝用户的数量与系统容量成正相关，随着蜂窝用户数量的增加，整个蜂窝网络的系统容量也稳定增加，确保本算法的可靠性。

图5 本文所提算法中蜂窝用户数量对系统容量的影响Figure 5 Impact of the number of cellular users on the system capacity in the proposed algorithm

4 结语

本文所提出的基于K-means 与Gale-Shapley 算法的D2D 干扰管理方案能够在蜂窝用户与D2D 用户共享信道资源的场景下，实现整体干扰最小化和系统容量最大化。以往的信道资源分配算法往往是在完成一对一复用之后再通过其他方式实现多对一复用，而本文所提算法为实现整个蜂窝网络整体干扰最小，在进行信道资源共享前，先对D2D 用户进行分组处理，保证D2D 用户公平性的同时以最小化蜂窝网络整体干扰为条件完成分组，最后实施稳定匹配算法以最大化整个蜂窝系统的通信容量。通过与基于贪婪的图着色算法、随机算法和传统图着色算法相比较，本文在干扰管理方面性能表现出色，且算法复杂度仅为O(M+N2)，能够满足D2D 用户在高速移动的场景下的通信需求。