基于遗传退火的密集D2D网络资源分配算法

汪汉新，李鹏威

(中南民族大学 电子信息工程学院，智能无线通信湖北省重点实验室，武汉 430074)

近年来，随着物联网和人工智能技术的发展，无线终端的数量越来越多.为了应对5G网络的增强移动宽带，大规模机器连接和高可靠低时延通信的挑战[1,2]，D2D(Device-to-Device)通信技术被广泛应用在5G场景中.然而，D2D用户复用蜂窝网络的频谱资源会带来严重的设备间干扰[3]，当D2D用户不断增多时，设备间干扰也随之增多，从而导致D2D用户接入率的降低.因此，如何有效的进行资源分配来提高D2D用户接入率成为一个急需解决的问题[4].

目前，人们主要通过模式选择、资源分配和功率控制等方法来减小设备间干扰以提高系统总吞吐量[5].文献[6]提出了使用贪婪算法提高系统的吞吐量，但该算法只允许一个D2D用户复用一个蜂窝信道.文献[7]提出了一种基于非合作博弈的D2D资源分配算法，D2D用户相互竞争以满足自己的服务质量(Quality of Service，QoS).文献[8]首先通过采用基于参数法的Dinkelbach算法来进行用户的功率分配，然后借助Kuhn-Munkres算法为D2D用户分配蜂窝频谱资源，提高了系统的能效.文献[9]提出了使用匈牙利算法进行资源分配来最大化系统吞吐量，但该算法只允许一个D2D用户复用一个信道.文献[10]使用最大权重二分匹配算法，在满足蜂窝用户信干噪比的前提下，提升系统公平性，并且允许一个D2D对使用多个信道.文献[11]提出了基于图着色算法的资源分配方案，该算法将资源分配问题转化为图着色问题，提高了系统吞吐量.文献[12]提出基于改进图着色算法(Improved Graph Color Algorithm，IGCA)的资源分配方案，该算法通过考虑以前被忽略的D2D对受到的微小干扰来构建干扰图，以进一步提高系统的吞吐量.文献[13]提出了超密集场景下基于图着色算法的资源分配方案，该方案首先判断用户使用D2D模式还是蜂窝模式，然后构建干扰图，最后通过图着色算法优先为D2D用户分配信道来进行资源分配，可以提高系统吞吐量.

以上文献针对的主要是非密集D2D网络中的资源分配问题，主要优化目标为提高吞吐量或提高能效，忽略了对D2D接入率的要求.为了在保证蜂窝用户QoS的情况下提升D2D用户的接入率，本文提出了基于遗传退火(Genetic Annealing Algorithm，GAA)的密集D2D网络资源分配算法[14,15].首先根据系统内的干扰情况建立干扰图，然后设计适应度函数以寻找适应度最大的信道分配方案.实验结果表明，本文算法可以在保证蜂窝用户QoS的前提下，提高系统总吞吐量和D2D接入率.

1 系统模型

本文主要研究单个蜂窝小区中D2D用户复用蜂窝用户上行链路信道资源的分配问题.假设该小区中共有M个蜂窝用户，N对 D2D用户，K个信道资源.集合C={C1,C2,…Ci,…CM},D={D1,D2,…Dj,…DN},K={1,2,…，k}分别代表蜂窝用户集合、D2D用户集合和信道集合.如图1所示，小区中有一个宏基站BS、一个蜂窝用户CU和两个D2D对用户，其中DTU代表D2D对的发射端，DRU代表D2D对的接收端.

图1 单蜂窝网络模型Fig.1 Single cellular network model

模型中主要存在三种干扰：D2D用户接收设备受到基站的干扰；蜂窝用户接收设备受到复用同样频谱资源的D2D用户发射设备的干扰；D2D用户接收设备受到其他D2D用户发射设备的干扰.这三种干扰皆为同频干扰.

假设蜂窝用户和D2D用户的功率分别设定为PC和PD，因此可得蜂窝用户C的信干噪比为

(1)

D2D用户Di的信干噪比为

SINRDj=

(2)

根据香农公式可以得到用户Ci和D2D用户Dj的吞吐量RCi和RDj分别为

RCi=Blog2(1+SINRCi),

(3)

RDj=Blog2(1+SINRDj),

(4)

其中B代表信道带宽.

2 问题规划及算法描述

2.1 干扰图的构建

为了对D2D资源分配问题进行求解，基于蜂窝用户和D2D用户之间的干扰关系，构建干扰图P=(V,E)，其中顶点集合V={V1,V2,…，Vv,…，VM+N}中的每一个顶点代表一个蜂窝用户或一个D2D用户对，边的集合E中的每一条边e(Vv,Vv′)代表顶点Vv受到顶点Vv′的干扰，边的大小代表干扰强度.边的公式为：

(5)

式(5)中，第一个式子表示两个蜂窝设备使用正交的信道，它们之间不存在干扰，第二个式子表示一个通信链路不存在自身干扰，因此它们相应的边的权值为零，其余三个式子分别表示D2D用户对蜂窝用户的干扰，不同D2D对间的干扰以及蜂窝用户对D2D用户的干扰.

2.2 问题规划与可行解

假设基站了解所有终端状态及链路信息，小区处于满载状态，且每个蜂窝用户占用不同的信道资源.本文的目的是找到最优的D2D信道分配方案，从而提高D2D接入率.基于干扰图可以将信道分配问题建模为如下的目标函数：

(6)

SINRCi≥SINRCthreshold,∀Ci∈C,

(7)

(8)

xi,j∈{0,1},

(9)

X∈{0,1}N×K,

(10)

式(6)表示优化目标为将受干扰最大的D2D对的干扰值最小化，其中，Vj代表一个D2D用户，Vv代表一个蜂窝用户或一个D2D对，e(Vv,Vv′)代表顶点Vv受到顶点Vv′的干扰值.式(7)表示蜂窝用户的信干噪比要大于门限值，式(8)表示多个D2D用户可以复用一个信道资源，式(9)表示第j个D2D用户复用第i个蜂窝用户的信道资源，式(10)为问题(6)的一个可行解，当xi,j=1时X的第j行第i列为1，当xi,j=0时X的第j行第i列为0，X的行代表某一个D2D对复用的信道，列代表某一个信道被哪些D2D对复用.

可行解X表示一个D2D用户的信道分配方案.为了便于算法的求解，将可行解X由矩阵转化为集合G={G1,…，Gn,…，GN}Gn∈{1,…，i,…,M}，其中Gn=i代表第n个D2D用户复用第i个蜂窝用户的信道.

2.3 适应度函数的设计

2.4 遗传算法的改进

2.4.1 种群初始化的改进

经典遗传算法的初始化过程是在解空间中随机产生种群规模数量的点，然后将这些点作为初始种群.这种做法对多峰复杂函数来说，如果后续遗传算子操作不当很容易使算法出现早熟现象.出现早熟，一般是由于算法没找到解空间中最优解所在的波峰，或者处于最优解所在波峰的较低位置进而被进化淘汰.因此为了能更大概率的找到最优解，避免出现早熟现象，本文使用联赛选择方法进行种群初始化，具体做法为：按一般种群初始化方法随机生成P个个体；计算个体适应度，并按照个体适应度进行排序；选取适应度最高的一个个体作为初始种群的成员；重复上述步骤直至选出P个个体作为初始种群.

2.4.2 选择算子的改进

在遗传进化的初期通常会产生一些适应度很大的个体，按照传统的轮盘赌方法选择个体，这些个体由于竞争力大会被大量选中，造成种群基因多样性降低，导致算法易陷入局部最优解.因此本文对其进行了改进，具体做法为：将种群中的个体按照适应度进行排序；按照传统轮盘赌方法从种群中选择一个个体作为父代，并将该个体从种群中移走；重复上述步骤直到产生P个父代个体.

2.5 基于遗传退火的密集D2D网络的资源分配算法

本文将遗传退火算法用于寻找最优的D2D资源分配方案，其中一个个体即为一个资源分配方案，个体中的一个基因代表一个D2D用户的信道复用方案.

算法具体步骤如下：

(1)根据干扰图构建D2D用户的候选信道，当D2D用户和蜂窝用户的距离小于20 m时，则D2D用户不能复用该信道.

(2)种群初始化

(3)精英保留，将P/5的个体直接复制到子代.

(4)进行改进的选择操作，选择出4P/5个个体.

(5)对(4)中选择的个体依据交叉概率随机选择一个基因位进行单点交叉，生成2P/5个子代.

(6)对(5)中产生的个体进行变异操作 依据变异概率对新产生的子代进行变异操作，具体操作为对个体基因选取随机位数，对选取出的基因依概率PV在[1-k]中随机选取一个值代替旧的基因，生成新的2P/5个子代.

(7)对产生的新一代种群进行适应度排序，并保留适应度最高的个体.判断该个体中蜂窝用户是否满足最低信干噪比，如果不满足，则删除复用该信道的受到干扰值最大的D2D用户，重复该步直到蜂窝用户满足最低信干噪比.

(8)对(7)中适应度最高的个体进行模拟退火操作，生成新个体并计算其适应度.并判断新个体中蜂窝用户是否满足最低信干噪比，执行如步骤(7)中相同的步骤.

(9)比较(7)和(8)中产生的两个个体的适应度，适应度高的个体作为最优个体进行保存.

(10)收敛条件判定.对最优个体进行判定，若它的个体适应度函数满足条件或达到最大迭代次数就输出最优解，否则返回第3步继续进行循环.

3 仿真分析

本文在MATLAB仿真平台对算法进行仿真，重复执行100次，然后对结果取平均值，每一次算法执行过程中蜂窝用户和D2D用户都随机分布在小区中，D2D用户间的距离随机产生，并限定在20 m以内.本文在保证蜂窝用户QoS的前提下对随机分配算法(Random Algorithm，RA)、改进的图着色算法IGCA和遗传退火算法GAA进行了对比.GAA中的参数设置为：种群规模P=100，交叉概率PC=0.8，变异概率PV=0.1，最大迭代次数为500，初始温度T0=100，结束温度T1=0.01，减温系数为0.99，每个温度的迭代次数为100.实验参数如表1所示.

表1 实验参数Tab.1 Experimental parameters

3.1 吞吐量仿真

图2描述的是蜂窝用户数量M为10和信道数量K为10时，系统总吞吐量与D2D对总数量之间的关系图.

图2 M=10，K=10时系统总吞吐量随D2D对数量的变化图Fig.2 The total system throughput vs. the number of D2D at M=10 and K=10

如图2所示，GAA与IGCA、RA相比，系统总吞吐量平均增幅为6.2%和21.8%.当D2D对总数量小于30时，三种算法的总吞吐量都在增加，但随着D2D对总数量逐渐增多，系统总吞吐量增加速度逐渐变缓.这是因为信道资源有限，D2D对数量越多，占用同一信道的D2D对也随之增多，导致系统中干扰也变多.当D2D对数量超过30时，GAA的系统总吞吐量继续增加，IGCA和RA的系统总吞吐量却发生下降.这是因为IGCA是通过为每一个D2D对寻找其最优信道，不断迭代得到信道分配方案，当D2D用户数量过多时，会有过多的D2D用户选择最优信道，导致干扰增大，系统总吞吐量降低；RA是由于信道随机分配，可能导致过多的D2D对选择同一信道，系统中干扰增大，导致系统总吞吐量降低.

3.2 D2D接入率仿真

图3描述的是蜂窝用户数量M为10和信道数量K为10时，D2D对接入率与D2D对总数量之间的关系图.

图3 M=10，K=10时D2D接入率随D2D对数量的变化图Fig.3 D2D access rate vs. the number of D2D at M=10 and K=10

如图3所示，GAA与IGCA、RA相比，D2D用户接入率平均增幅为14.7%和44.5%.这是因为IGCA是为每个D2D对寻找最优信道，这会导致所有D2D对都去选择最优信道，而部分通信状况不好的D2D对无法找到满足QoS的信道；而GAA将受到干扰最大的D2D对的干扰值作为适应度函数对解进行选择，即只关注通信状况最差的D2D对，只要使它满足该D2D对的QoS，则所有D2D对都能满足QoS，这样能更好的提升D2D对接入数量；RA则是因为信道分配的随机性使得D2D对无法满足QoS.

3.3 设备吞吐量的累积分布函数仿真

从图4可以看出，GAA约有91%的设备吞吐量超过2.5bit/s/hz，而IGCA和RA约占70%、54%.这是因为IGCA中一部分D2D用户选择了最优的信道，导致部分D2D用户无法找到能满足QoS的信道；GAA中D2D用户选择的信道满足QoS即可，而不一定是最优信道，使得一部分通信状况差的用户也可以找到满足QoS的信道；RA是因为随机分配信道使得部分D2D用户无法满足QoS.

图4 M=10，K=10，N=40时设备吞吐量的累积分布函数Fig.4 Cumulative distribution function of device throughput atM=10 and K=10

3.4 复杂度分析

本文的GAA首先要计算蜂窝用户和D2D用户的干扰矩阵，因此构建干扰图的复杂度为O[(M+N)^2].如果遗传算法的迭代次数为q，退火算法的温度控制外循环次数假定为a,在每个特定温度下内循环次数为b，那么遗传退火算法的复杂度就是O[q*a*b].因此，当(M+N)的值足够大时，GAA的总复杂度为O[(M+N)^2]，而IGCA的复杂度为O[N*(M+N)^2]，显然GAA的复杂度是低于IGCA的.综上所述，GAA更适合于高密集D2D网络场景.

4 结语

为了提高系统总吞吐量和D2D接入率，降低用户之间的干扰，本文提出了基于遗传退火的密集D2D网络资源分配算法.首先分析了系统中存在的三种干扰，并依据干扰情况构建出小区内用户之间的干扰图；然后根据干扰图构建出D2D用户的候选信道集合，并将受到干扰最大的D2D用户的干扰值作为代价函数，通过遗传退火算法寻找适应度最高的解方案；最后进行了仿真实验.仿真结果表明，本文提出的算法可以在有效提高系统总吞吐量的同时，还可以提高D2D用户的接入率.本文只考虑了在单小区场景下的信道分配问题，未考虑功率分配以及小区间的干扰问题，下一步将联合功率分配对多小区场景下的资源分配问题展开深入研究.