一种5G异构云无线接入网络的D2D资源分配算法*

张永棠，赵元成

(1.广东东软学院 计算机学院，广东 佛山 528225；2.南昌工程学院 江西省协同感知与先进计算技术研究所，南昌 330003)

0 引 言

网络规模的扩大和数据流量的增长对5G网络的发展和演进提出了一系列新的挑战。为了解决这些问题，异构云无线接入网(Heterogeneous Cloud Radio Access Network,H-CRAN)和设备到设备(Device-to-Device,D2D)通信结合是应对5G网络挑战的关键技术。

H-CRAN是一种结合了异构网络(Heterogeneous Network,HetNet)和云无线接入网络(Cloud Radio Access Network,C-RAN)优点的5G无线接入网络架构，通过异构大功率节点传输整个网络控制信号，提高网络的能量效率。

D2D通信是用户在不通过基站(Base Station,BS)的情况下直接通信，这可以减少BS上的负载，有效提高系统吞吐量、能源效率和频谱效率，符合5G网络的发展趋势。D2D通信需要共享宏用户设备(Macrouser Equipment，MUE)的资源。因此，如何配置资源可以提高网络中的系统吞吐量是近年来研究的一个重要问题。

随着5G网络的发展和演进，D2D通信技术被引入到HetNet中，解决H-CRAN网络中的基带处理单元(Base Band Unit,BBU)与射频拉远(Remote Radio Head,RRH)的链路受限问题[1-3]。文献[4]提出了一个静态博弈模型，并将其推广到一个重复博弈模型，基于这种重复模型，提出了一种基于基站与设备交互的资源分配协议。这是该领域的经典算法，现有的研究大多是基于该算法进行改进。

然而，已有的文献都是基于蜂窝网络架构对蜂窝用户和D2D用户的相互干扰和信道共享等问题进行研究，很少有文献论述基于D2D 复用 H-CRAN 网络场景下资源的分配方案，考虑整体系统的吞吐量。并且在已有文献中，都是将D2D的模式假设为确定的。但在实际环境中，通信信道的接入和释放都是随机的，干扰的约束条件是动态选择的。因此，本文将匹配理论应用于H-CRAN下的动态资源分配。为了达到最大系统吞吐量的目标，需要D2D和中继用户终端(Relay User Equipment,RUE)在保证所有用户服务质量(Quality of Service，QoS)要求的情况下找到适合频谱共享的MUE。该问题被认为是一个整数非线性规划(Integer Nonlinear Programming，INLP)问题。为了解决这个问题，本文将资源分配问题转化为一对一的匹配问题，一个D2D/RUE只允许共享一个MUE频谱资源，而一个MUE频谱资源只允许共享一个D2D/RUE。

本文工作的主要创新点：将婚姻匹配算法应用于资源分配问题，提出了一种资源分配算法来执行MUE与D2D/RUE之间的初始匹配;在初始匹配的基础上，提出了一种符合卡尔多-希克斯(Kaldor-Hicks)原则的资源交换策略，实现系统总体吞吐量的最大化，并通过仿真实验验证了该算法的有效性。

1 系统模型与问题表述

1.1 系统模型

H-CRAN系统的下行链路传输模型如图1所示。假设存在1个BS、N个 RRH、C个MUE、L对D2D、H个RUE，使用R={Rr|1≤r≤N},M={Mi|1≤i≤C},D={Dd|1≤d≤L},K={Kj|1≤j≤H}分别表示RRH、MUE、D2D和RUE的集合。此外，假设Hr是每个RRH中RUE的数目，且H=∑r∈NHr，Kr,j表示RRH中的第j个RUE。在本文中，假设L+H=C。

图1 系统模型

假设BS将频谱资源分配给MUE。为了解决频谱资源不足的问题，D2D和RUE需要共享MUE的资源。为了便于讨论，D2D对和RUE被视为同一类型的用户，它们被统一地表示为V，且V={Vn|1≤n≤L+H}。假设一个MUE的频谱资源可以由一个D2D/RUE共享，而一个D2D/RUE只能共享一个MUE频谱资源。也就是说，这个问题可以看作是一对一的资源分配问题，为D2D对和RUES进行合理的资源分配，以达到最大系统吞吐量的目标。所有资源由BS统一分配。

为了更好地描述资源分配问题，使用二进制数xr,i,j表示Mi的频谱资源是否分配给Kr,j，二进制数yd,i表示Mi的频谱资源是否分配给Dd。在该模型中，假设功率为常数。当被DR共享时，信干噪比(Signal-to-Interference plus Noise Ratio,SINR)和可达数据率分别为

(1)

ζi=Wilb(1+Φi)。

(2)

当RUE共享的频谱资源为Mi时，Kr,j的信噪比和可达数据率分别为

(3)

ζr,j,i=Wilb(1+Φr,j,i)。

(4)

当D2D对共享的频谱资源为Mi时，Dd的信噪比和可达数据率分别为

(5)

ζd,i=Wilb(1+Φd,i)。

(6)

式中：Wi为Mi的带宽，σ2为加性高斯白噪声的功率。

1.2 问题描述

资源分配的目的是将资源合理地分配给D2D和RUE，以实现资源共享，提高系统吞吐量。因此，在进行资源分配时，需要满足基本的QoS要求，控制用户集V对MUE的干扰程度。

最大吞吐量问题可以表述为[5]

(7)

s.t.

(8)

(9)

(10)

(11)

(12)

(13)

式(7)～(13)约束条件构造的问题是一个INLP问题。当H-CRAN中涉及的RRH、RUE、MUE、D2D等用户数变大时，问题将变得难以求解，这是NP复杂问题。基于本文提出的目标，下一节将提出一种资源交换策略来有效地解决这个问题。

2 资源分配问题求解

本节解释如何使用资源交换策略来解决资源分配问题，以最大化系统吞吐量。该方法遵循卡尔多-希克斯原理[6]。

2.1 初始资源分配算法

这里把资源分配问题看作是一对一的匹配博弈，一个用户Mi对应一个用户Vn。首先，进行初步的资源分配，得到Mi与Vn之间的初始匹配；然后，在初始匹配的基础上，通过资源交换策略使系统吞吐量最大化。初始匹配可以在一定程度上减少资源交换操作的数量。

定义1(匹配u) 假设有两个集合M和V，元素分别由Mi(1≤i≤C)和Vn(1≤n≤L+H)表示。如果Vn向Mi提出一个匹配请求，并且Mi接受这个提议，则Vn和Mi是一个匹配对，其数学方式表示为Mi=u(Vn)和Vn=u(Mi)。

目标是完成双方一对一的匹配。首先，根据偏好值建立双向偏好列表，首选项值取决于用户吞吐量。根据偏好列表，集合V中的用户依次向集合M中的用户提出匹配请求。当用户Vn共享Mi资源时，由用户Vn和Mi生成的偏好值分别由等式(14)和(15)计算:

Pn,i=Wilb(1+Φn,i)，

(14)

Pi,n=Wilb(1+Φi)。

(15)

所有偏好值的计算、偏好列表的建立和信息的传播都是由BS来统一分配的。

定义2(偏好算子≻) 如果在用户Vn的偏好列表中，Mp的偏好值高于Mq，即相比于Mq，Vn更愿意匹配Mp，数学方式表示为

Mp≻vnMqPn,p>Pn,q。

(16)

同理，如果在用户Mi的偏好列表中，Vm的偏好值高于Vn，即相比于Vn，Mi更愿意匹配Vm，数学方式表示为

Vm≻miVnPm,i>Pn,i。

(17)

根据盖尔-沙普利(Gale-shapely，GS)[7]婚姻稳定匹配算法，本文提出了一种基于偏好列表的婚姻匹配算法。在模型中，根据方程(14)和(15)建立偏好列表，并利用婚姻匹配算法(算法1)的思想对M和V的集合进行初始匹配。算法1的伪代码如下：

输入:所有用户V的偏好列表ξ和所有用户M的偏好列表ϑ

输出:初始匹配u

1 设置不匹配用户Vn∈V列表ΩV和不匹配用户Mi∈M列表ΩM；

2 whileΩV≠∅ do

3 ifu(Mi)=∅ then

4Mi=u(Vn),Vn=u(Mi);

5ΩM=ΩMMi,Ωv=ΩvVn;

6 else

7 ifVn≻miu(Mi) then

8Ωv=Ωv∪u(Mi),Mi=u(Vn);

9Vn=u(Mi),Ωv=ΩvVn;

10 else

11Mi拒绝Vn，并保持u(Mi);

12Vn在偏好列表中的寻找下一个匹配项;

13 end if

14 end if

15 end while

16 输出匹配项u

该算法主要思想是：用户Vn向用户Mi发送请求，并且Mi在Vn偏好列表中具有最高的偏好值，如果Mi没有伴侣，Mi接受Vn；如果Mi有伴侣，Mi判断用户Vn偏好值是否高于其现有伴侣，如果它更高，那么Mi接受Vn，否则Mi拒绝Vn；只要Vn被拒绝，Vn就可以向其首选项列表中的下一个用户发出请求，直到用户集V中的所有用户都得到一个伴侣，算法结束。

2.2 配对博弈的交换策略

算法1的执行可以对M和V的集合进行初始匹配。在此基础上，提出一种遵循卡尔多-希克斯原理[8]的资源交换方法，实现系统吞吐量的最大化。

定义3(Kaldor-Hicks原理) Kaldor-Hicks意味着第三方的总成本不超过交易的总收益。也就是说，从结果中获得的收益可以完全补偿所遭受的损失。

本文中，在资源交换策略不影响其他匹配对的前提下，参与资源交换的部分用户(如D2D/RUE/MUE)降低了整体吞吐量，部分用户增加了交换后的吞吐量。只要增加的吞吐量足以补偿减少的吞吐量，并且系统的总吞吐量增加，则认为它就达到了Kaldor-Hicks。Kaldor Hicks实际上是总体吞吐量的最大化标准[9]。

资源交换必须满足以下条件：交换后仍保证MUE的QoS要求;除了参与交换的对之外，其他匹配对的吞吐量不应受到影响;交换后必须增加系统吞吐量。

交换资源方法要求首先找到一组可以交换资源的用户。集合中的每个用户都需要满足这样的条件，即它们必须更喜欢另一个用户的伴侣(至少有一个用户在同一个集合中)才能比原来的伴侣更好。例如，u(Vm)≻vnu(Vn)表示Vn更喜欢Vm的伴侣，而不是其原始伴侣。为了更方便表达，Vm被称为Vn的合作对象。如果V1是V2的合作对象，V2是V3的合作对象，…，Vn-1是Vn的合作对象，V1,V2,V3,…,Vn-1,Vn构成一个可以交换资源的集合。然后，V1的资源可以移交给V2，V2的资源可以移交给V3，…，Vn-1的资源可以移交给Vn。从上面可以看出，当用户交换资源的方向可以形成循环时，则可以进行交换操作。

本文提出一种求图中最大环的启发式算法[8]，通过构造图和查找循环[10]两个步骤来求解用户资源交换问题。考虑到吞吐量最大化的目的不是在图中找到最大环路，而是在资源交换之后依次找到能够最大化系统吞吐量的环路。因此，需要根据一定的规则建立构造图。首先，以集合V中的所有用户作为图的顶点，为用户找到合作对象，并建立从用户到他们的合作对象的有向边，从而创建了一个有向图；然后，在有向图中找到所有现有的循环，并形成一个集合E；最后，根据上述资源交换方法进行资源交换，在资源交换后选择符合Kaldor-Hicks原理的循环，并根据系统吞吐量的改进程度对这些选定的循环进行排序。根据贪心策略，找到吞吐量改善最大的循环作为交换资源的第一个循环。在此之后，依次选择的循环需要满足两个条件(一是它与以前选择的循环没有公共顶点；二是在剩余的环路中，存在能够最大限度地提高系统吞吐量的环路)，直到没有循环可供选择。

在循环中用户的资源交换完成后，参与交换的每个用户将获得一个新的可共享资源。也就是说，形成了新的匹配。根据原始偏好列表和新的匹配，重构有向图，直到在形成的图中找不到循环，停止资源交换，形成最终的匹配。资源交换算法(算法2)伪代码如下：

输入:基于算法1的初始匹配u

输出:最终匹配u′

1 根据上述规则，建立基于匹配u的图G;

2 ifG≐∅

3u′=u;

4 else

5 { for 所有顶点的Γi∈G

6 { whileΓi未被访问 do

7 访问Γi;

9 { while 合作对象 do

10 { if(Γnext没有被访问)

11 访问next(Γnext);

12 else if(Γnext被访问&&Γnext=Γi)

13 找到一个循环e;

14E=E∪{e};

15 else

16 continue;}}}}

17 forei∈E

18 {选择交换资源后吞吐量提升最大的环作为交换的第一循环;

19 按吞吐量改进顺序选择另一个循环，该循环与已选择的循环没有相同的顶点;

20 建立一个新的匹配u′

21u=u′;}

22 根据新的匹配重复步骤1～16。

该方法提高了参与交换的用户Vn的吞吐量，但对用户Mi吞吐量的影响是不确定的。不同用户共享MUE的资源，会对其造成不同程度的干扰，MUE的吞吐量可能下降，也可能上升，需要应用Kaldor-Hicks来确保系统吞吐量的提高。因此，本文提出的交换策略，只要增加的吞吐量足以补偿减少的吞吐量和总体吞吐量的增加就允许交换，符合Kaldor-Hicks原则。

2.3 复杂度分析

不失一般性，认为H≈N>C。假设a1、a2分别表示算法1和算法2在收敛前的迭代次数。根据2.2节的交换策略，每一次用户资源交换后，算法2都会被重新执行一次，直至集合V中的所有用户为节点的图G中找不到循环，即找不到被移出的MUE。可以看出，在最坏的情况下，集合V需要被简化H次，则算法2需要被执行a1·a2·H次，每次执行算法2的运算复杂度为O(H(NC)3)。因此，采用本文提出的资源匹配方案，获得系统吞吐量的最大化的整体复杂度近似表示为O(a1·a2·H2(NC)3)。

3 仿真验证及结果分析

3.1 仿真设计

根据图1的系统模型，部署了H-CRAN下行传输场景。其中，BS放置在半径为500 m的仿真场景中心，坐标是(0,0)；场景中随机分布D2D、RUE和MUE，每个用户的位置不重叠。为了便于讨论，假设D2D与RUE之和等于MUE的数目。所有实验结果取100次试验的平均值，并将本文算法与文献[3]、文献[4]、随机接入算法的仿真结果进行比较。实验参数如表1所列。

表1 部分仿真参数设置

3.2 仿真结果分析

图2展示了三种算法在不同用户数的情况下生成的用户集V的吞吐量，可以看出，随机接入的性能最差且曲线平坦。由于在随机接入中，没有采用有效的主动策略来提高系统的吞吐量，并且系统的带宽限制了系统的吞吐量，因此，只要系统带宽保持不变，用户集V产生的吞吐量之和本质上是相同的，而受用户数的数量影响非常小，几乎可以忽略。

图2 用户集V的总吞吐量

本文所提算法的性能明显优于文献[4]算法，因为本文算法在资源交换操作中考虑了用户Vn∈V的吞吐量，只有在Vn吞吐量增加时才允许资源交换操作，该策略保证了用户集V的吞吐量增加。除随机算法生成的曲线外，其余两条曲线均呈上升趋势。由于带宽的限制，随着用户数量的增加，最终区域变平。与文献中的算法相比，本文算法总吞吐量均得到了提高，较文献[4]提高了约15%，随着用户数量的增加，较文献[11]的优势更加明显。因此，该算法在提高用户集V的吞吐量方面具有较好的性能。

图3展示了三种算法在不同用户数情况下产生的系统吞吐量，可见由于缺乏主动策略和系统带宽的限制，随机算法的性能仍然是最差的。与文献[4]算法相比，本文算法在提高系统吞吐量方面有更好的性能，系统吞吐量提高了约8%。由于本文算法中使用了Kaldor-Hicks，保证了每次交换资源时系统吞吐量的提高。与文献[11]对比，在D2D用户对数量比较少的时候，该算法略有不足，但是随着用户对数量的增加，该算法的优势开始显现。因此，本文算法在系统吞吐量方面有较好的实验结果。

图3 系统的吞吐量

图4展示了D2D传输功率对总吞吐量的影响，可以看出，随着D2D用户的功率增大，三种算法的总吞吐量都是呈上升趋势;当功率达到50 dBm时，文献[4]和随机接入算法的吞吐量最终趋于平缓，这是由于传输功率的增加会引起D2D用户之间的干扰也增大，最终导致平缓。本文算法以及采用了动态穷举的文献[11]算法均获得了较高的吞吐量，并且随着传输功率的增加，本文算法的优势更加明显，证明了本文算法采用的资源交换分配方案能有效解决D2D用户之间的干扰，承受较大传输功率的通信，使频谱的利用率得到提高。

图4 传输功率与吞吐量的关系

图5展示了D2D用户链路间距对吞吐量的影响，可以看出，在D2D传输功率保持不变的情况下，吞吐量与D2D用户链路间距是成反比的。随着链路间距的增大，文献[4]和随机接入算法的性能下降非常明显，而本文算法虽有下降，但是下降程度较缓。随着D2D用户链路间距的增加，本文算法的吞吐量优于文献[11]。这一结果进一步验证了本文算法具有较强抗信道干扰能力。

图5 用户链路间距与吞吐量的关系

为了验证本文提出的资源分配方案具有均衡性和稳定性，对RRH与BS分别按3∶7、7∶3两种不同的混合接入策略，以及用户全部接入RRH和用户全部接入BS两种极端情况进行实验，并与文献[4]、文献[11]进行对比。图6展示了D2D用户的平均收益及迭代次数的关系，可以看出，两种全部接入的极端情况，用户平均收益都是非常低，并且是完全均衡的；文献[4]和文献[11]的用户平均收益明显好于两种极端接入，但还是低于本文算法的通信效率。

图6 用户平均收益与迭代次数的关系

此外，本文算法用户可以按照最合适的比例选择混合接入，提高用户的平均收益。在博弈达到均衡之前，用户收益曲线会有一些振荡，这是因偏好值计算及偏好列表更新引起的；经过不断迭代逐渐趋向博弈均衡，获得最优的收益，本文算法的两种比例接入均达到了均衡，并且明显优于其他算法。此时的迭代次数约10次，并且本文算法的收敛速度优于文献[11]，进一步验证了本文算法的复杂度较低。

4 结 论

由于5G H-CRAN频谱资源的不足，导致D2D共享出现信号干扰问题。为了解决此问题，本文运用婚姻匹配算法来解决5G H-CRAN下的D2D资源分配，提出了一种新的算法来执行MUE与D2D/RUE之间的初始匹配，由BS将频谱资源分配给MUE，然后将D2D和RUE合理共享MUE的资源，实现一对一的初始匹配。在初始匹配的基础上，提出了一种符合卡尔多-希克斯原则的资源交换策略，实现系统总体吞吐量的最大化。仿真结果表明，该算法对系统的吞吐量、用户平均增益都有明显的提高，具有算法复杂度低、收敛速度快等优点。