基于改进遗传算法的D2D资源分配策略

安浩杰，彭 艺，刘煜恒，付晓霞

（昆明理工大学信息工程与自动化学院，昆明650500）

引 言

近些年，随着智能设备的发展以及5G时代的到来，用户对网络的速度和容量的要求也随之增高，从而对频谱资源的需求也越来越高。但是传统的蜂窝系统不允许终端设备直接通信，所有的通信数据都要经过蜂窝网络转发，效率和资源利用率都不高，已经无法满足用户日益增长的需求。D2D（Device to device）通信作为一种终端直通手段开始受到广泛的关注［1-3］。D2D技术不需要经过基站转发就能够实现距离较近的两个用户直接进行信息交换，因此有效地提高了通信效率、资源的使用效率以及系统吞吐量。D2D通信按照其复用蜂窝系统资源的方式可以分为正交通信和非正交通信两种模式。正交通信模式中蜂窝用户（Cellular-users，CU）设备与D2D设备频谱是正交的［4-7］，工作在此模式下的用户不会产生干扰，但是这种模式的资源利用率较低。非正交通信模式中CU设备与D2D用户的频谱是非正交的，这种模式下资源使用效率较高，但是由于D2D用户的位置是随机的并且在复用蜂窝系统资源的同时会带来严重的干扰［8-11］。因此干扰控制是D2D通信中的重要研究方向，而系统内的干扰和D2D的功率息息相关，因此可以通过调节发射功率来限制干扰［12］。

D2D用户的功率控制问题一直是近年来的研究热点。文献［13］提出一种启发式算法，当D2D和CU进行信道分配时，会优先满足CU的需要；文献［14］更近一步地对D2D的接入率同各设备之间信道增益的联系进行了分析，并提出了一种基于贪婪思想的启发式资源分配方法，提高了D2D的接入率及系统吞吐量；文献［15］把智能化算法即Q学习应用到D2D资源分配中，提出一种基于Q学习的联合资源分配和功率控制算法，把D2D发射端的功率控制问题转化为Q学习问题。在学习过程中，不断地动态调整发射功率，在保证服务质量（Quality-of-service，QoS）的同时最大化系统吞吐量；文献［16］在兼顾系统吞吐量和D2D对之间互相干扰的情况下，为了控制D2D用户的功率，提出了一种干扰避免与资源管理算法。以上所述文献能从不同方向解决D2D的资源分配问题，但是一般考虑的是CU和D2D只能一对一进行资源复用，这样就对D2D技术的发展有了局限性，没有使系统性能最大化。

因此，本文在当前研究的基础上，对于一个CU的信道资源可以与多个D2D对共用的通信场景，提出一种基于改进自适应遗传算法的资源分配策略。首先计算出能够保证用户QoS的D2D设备的发射功率，然后再利用改进的遗传算法根据适应度条件对这个范围内的候选功率进行测算，根据适应度进行取舍，从而选择出最优的发射功率。仿真结果表明，改进后的遗传算法相对于改进之前的标准遗传算法其信道利用率提高了大约14%。

1 系统模型及问题描述

1.1 系统模型

本文研究的是蜂窝小区场景下的D2D通信资源分配问题，图1为系统模型。由于D2D用户复用的是CU的上行链路资源，假设当前整个系统处于全负载状态，即所有的资源均被CU占用，且各个CU占用的资源相互正交不存在干扰。假设整个系统中的信道数为N，每个CU占有一个信道即CU的数目依然是N，同时还有M对D2D用户。用集合C={1，2，…，N}，D={1，2，…，M}分别表示CU集合和D2D用户集合，其中一个D2D对包含一个发射端和一个接收端。

根据文献［17］，CUi和D2D用户j的路径损耗（Path-loss，PL）分别为

式中：di表示CU到基站的距离，dj表示D2D对之间的距离，f表示系统的载波频率。

由文献［18］可以得知，信道增益是由路径损耗、多径衰落带来的快衰落以及阴影衰落带来的慢衰落构成。由此可知，信道增益为

式中：Γ为路径损耗常数，μ为快衰落增益因子，ξ为慢衰落增益因子，d为距离，τ为路径损耗指数。

因为一个资源可能被多个D2D用户复用，所以CU就会受到复用相同频谱资源的D2D用户的干扰，把βj，i作为复用指示因子，当D2D用户j复用CUi的频谱资源时βj，i为1，否则βj，i为0。因此CUi的SINR表示为

图1 系统模型Fig.1 System model

式中：PC表示CU的传输功率，为固定值；表示D2D用户复用CU信道资源时的传输功率；Gi，B，Gjs，B分别表示CU到BS的信道增益和D2D对发射端到BS的信道增益；表示噪声功率，表示满足CUi通信服务质量的最小SINR。

D2D用户j在被复用的CUi信道资源上的SINR为

式中：Gjs，jr表示D2D用户j的发射端到接收端的信道增益，Gi，js表示CUi到D2D用户j接收端的信道增益，Gls，jr表示D2D用户l发射 端对D2D用户j接收端的信道增益。

中庸思想是中国传统文化中人们认识世界、对待事物的基本方法之一，其“执两端而允中”的智慧对于华人的心理、思维和行为处事等各层面都有巨大而深远的影响(思维，1999)。探究中庸在当代的表现形式和运作规律，有助于更好理解人们的生活方式和行为处事方法，提升生活品质，促进社会和谐。

由香农公式可知，CUi和D2D用户j的传输速率（单位：bit/s）分别为

1.2 问题描述

若满足式（4）的条件则βj，i为1，根据式（4）此时D2D的最小发射功率应该满足

在对功率进行限制之后假设CU的信道资源都已经确定，在保证其QoS的条件下，将最大化系统吞吐量作为目标函数为D2D用户分配信道资源。根据式（6）和式（7），则目标函数与约束条件分别为

式中：Pmax表示D2D的最大发射功率，表示满足CUi通信服务质量的最小SINR，表示D2D的传输功率限制。其中，式（9）为最大化系统吞吐量的表达式，式（11）表示D2D的传输功率不应该超出限制阈值，式（12）表示一个D2D用户只能复用一个CU的资源，并且一个CU的资源可以被多个D2D复用。由式（9～12）可知，本文定义的目标函数和其约束条件属于混合整数非线性规划问题（Mixed-integer-non-linear-problem，MINLP）。

2 改进的自适应遗传算法

然而MINLP问题用一般的方法很难求得最优解，而标准遗传算法通过二进制编码寻找最优解，易陷入部分最优，并且存在算法搜索速度较慢、易早熟等缺点。采用实数方式进行编码的遗传算法能直接搜索解空间，与二进制编码相比更加的快速和准确，因此本文首先采用实数编码的方法，改进了交叉算子和遗传算子的计算方法，并引进精英保存方案避免破坏已经产生的较好个体，在整个限制区域内搜索最优解并确定D2D的最优发射功率。

其次，标准遗传算法中的交叉和变异算子均采用固定值。交叉率越大，进化速度越快，但是进化速度过快很容易把进化时产生的较好个体给破坏掉，容易让算法局部收敛；反之，交叉率越小，又会导致进化搜索过程缓慢甚至停滞。若变异率取值较大，就会使遗传算法变成随机算法，从而使得结果无法达到全局收敛；如果取值较小，就会使得种群产生全新个体的几率变小。因此，对于这两个算子的取值一定要符合进化的实际要求，标准遗传算法的交叉率一般取值在0.4～0.99这个范围内，变异率的取值在0.001～0.2范围内。针对交叉率和变异率的取值问题，本文结合改进粒子群算法中基于非线性动态的惯性权重策略对交叉率进行改进，改进的动态自适应交叉率Pc的表达式为

对于变异率，本文结合改进粒子群算法中基于反余弦策略的非线性学习因子思想来对变异率进行改进［19］，改进的动态自适应变异率Pm的表达式为

图2 自适应交叉率和变异率Fig.2 Adaptive crossover rate and mutation rate

由图2可知，本文设计的自适应交叉率和变异率均满足要求。而文中所说的精英保留方案其实就是择优而取即将每一轮新产生的高适应度个体同上一轮的高适应度个体进行比较，观察二者的适应值高低，若上一轮的适应值更高，则用上一轮的高适应度个体随机替换新一轮中的低适应度个体。精英保留使得最优个体免受遗传操作的破坏。因此，精英保留方案是保证算法收敛的重要方法。

综上论述，本文设计算法的计算流程如图3所示。

3 仿真结果及性能分析

3.1 仿真参数

为验证本文提出算法的有效性，使用M ATLAB进行仿真分析。本次仿真的蜂窝系统设为半径500 m的正六边形区域，系统中CU和D2D随机分布于其中，其中为了保证QoS，D2D对之间的距离限制在50 m内。主要的仿真参数如表1所示。

图3 自适应遗传算法流程图Fig.3 Flow chart of adaptive genetic algorithm

3.2 复杂度和仿真结果分析

3.2.1 复杂度分析

除系统性能外，算法的复杂度也是体现算法优劣的重要指标。在此，分析改进的自适应遗传算法对整体复杂度的影响。假设种群大小为N，迭代T次，并且计算适应值所需的时间复杂度是O(t)，那么改进的自适应遗传算法的时间复杂度就是O(N×T×t)。由于算法只是改进了交叉和变异两个算子，因此与标准遗传算法相比，需要相同的复杂度。虽然和标准遗传算法相比，本文算法的复杂度没有降低，但是系统性能得到了优化，因此优于标准遗传算法。

3.2.2 仿真结果

为了验证本文算法的性能，在仿真参数设置相同的前提下，将本文所提算法与以下3种算法的性能进行了比较：改进之前的标准遗传算法以及两种经典算法即文献［9］提出的启发式算法和随机算法。为了便于比较本文将对比算法进行了多对一情况下的仿真。随机算法就是将D2D发射功率在不超过最大值的前提下随机选择。

表1 主要仿真参数Table 1 Main simulation parameters

在不同的D2D对数条件下，其信道利用率的变化曲线如图4所示。由图可见随着D2D对的增加，系统的信道利用率呈下降趋势，这是因为随着D2D对数的增加D2D对以及CU和D2D之间的干扰越来越复杂，从而导致信道利用率下降。在相同条件下，本文算法分别比标准遗传算法、启发式算法和随机算法的信道利用率提高了14%、19%、27%。

图4 信道利用率变化曲线Fig.4 Channel utilization curves

对于不同的D2D用户数目，4种算法的D2D资源分配策略的系统吞吐量变化曲线如图5所示。图5描述的是当CU的数量是50的时候，4种算法的系统吞吐量随着D2D对数量不断增加的变化趋势。并且因为4种算法都能实现多个D2D用户复用一个频谱资源，因此随着D2D对数量的增加，系统吞吐量也随之不断增加。但是当D2D对的数量超过10之后，吞吐量的增加速度就逐渐降低，这是因为随着用户数目的增多，系统内的干扰也在增加，因此增长趋势逐渐放缓。

为了测试本文方案下的D2D用户的通信质量，采用累计分布函数图描述4种资源分配算法的系统吞吐量的分布情况。4种资源管理方案下D2D用户的系统吞吐量累计分布函数图的变化趋势如图6所示，从图6中的曲线趋势可以看出本文算法在取同一CDF的情况下系统吞吐量明显优于另外3种算法的系统吞吐量，说明系统性能得到了提高。

综上所述，本文所提改进的遗传算法能够解决标准遗传算法搜索速度慢、易早熟以及容易陷入局部最优解等问题，能够有效提升系统性能。

图5 系统吞吐量变化曲线Fig.5 System throughput change curves

图6 系统平均吞吐量的累积分布函数Fig.6 Cumulative distribution function of the average throughput of the system

4 结束语

本文针对D2D用户在复用蜂窝系统资源时带来的干扰和资源分配问题，提出一种基于改进自适应遗传算法的资源分配策略，该方案在保证QoS的条件下通过寻找D2D用户的最优发射功率，达到降低系统干扰和吞吐量最大化的目的。因为本文是针对多个D2D用户能复用同一CU资源的情况下对比以往的CU与单个D2D对共享资源的情况，资源利用率得到了提升。并且在与其他3种优化方法进行对比测试后，由仿真结果可以看出本文算法明显优于对比算法，能有效地提高信道利用率和系统吞吐量。