基于超图着色的D2D网络资源分配算法

陈雨洁，马彩虹

(武警工程大学 信息工程学院，陕西 西安 710086)

0 引 言

基于蜂窝网络的D2D通信被认为是5G系统中一种极具潜力的新型网络架构。通过允许两个相邻用户设备共享蜂窝用户设备的频谱资源直接进行通信，D2D通信能有效提高蜂窝网络的频谱利用率[1]。但如果通信资源分配不当，来自多方链路的干扰会使D2D通信带来的系统性能提升大打折扣，故合理的资源分配是D2D通信发挥优势的基础。文献[2-4]分别以系统吞吐量、能耗与中断概率、系统容量为改善指标，通过引入博弈论和模拟退火算法等思想，提出了有效的资源分配方案。

上述文献均是对LTE(long term evolution)系统中的正交频谱分配进行研究，但频率资源的有限性仍限制了系统容量和频谱利用率的进一步提升，故基于SCMA等非正交多址技术的D2D通信受到了广泛关注。文献[5]提出一种基于冲突图的资源分配方案，验证了结合SCMA的D2D通信相比LTE网络在系统和速率上可获得更大增益。文献[6,7]分别从码本的优化分配、码本和功率联合优化分配两个角度出发，给出了两种较好的资源分配方案。本文针对SCMA系统中的多小区网络场景，提出一种改进的超图着色算法完成D2D用户码本分配。考虑到传统超图着色法在多小区模型中构建超图的计算过于复杂，提出基于通信距离建立D2D用户的蜂窝复用备选集，并以此建立超图和进行着色。仿真结果表明所提算法能有效提升系统容量，且相比传统超图着色法复杂度更低。

1 系统模型

为缩小算法规模、降低系统复杂度，对本文研究的多小区场景进行预处理。首先根据邻接关系将系统中的小区划分为不同小区簇，簇内用户通过SCMA码本共享预分配的正交频谱。不同簇内的蜂窝用户使用相同资源，以此保证使用相同资源的用户间距离足够大，从而相比簇内相距较近的D2D链路干扰，簇间的蜂窝同频干扰可忽略不计。于是多小区异构网络中的资源分配问题转化到各小区簇内进行，由此控制了算法的规模。本文研究均基于该假设，所关注的多小区异构网络由一个小区簇内的多个相邻小区构成，且簇内所有蜂窝用户已完成资源分配，本文旨在对簇内D2D用户进行码本分配。

1.1 网络场景

考虑在SCMA系统中，一个蜂窝与D2D异构的多小区上行网络场景。

图1 系统模型

设信道为瑞利衰落模型，则各链路的增益可表示为

(1)

于是占用SCMA层k的蜂窝用户Un接收信号的信干噪比(SINR)为

(2)

复用k层SCMA码本资源的D2D对Dm接收信号的信干噪比(SINR)为

(3)

其中，Ck表示复用同一码本的蜂窝用户和D2D对的集合。

1.2 问题建模

为使系统吞吐量最大，要将网络中的蜂窝用户及D2D对合理的分配到各SCMA层。假设一个蜂窝用户或一个D2D对只占用一层SCMA资源，一个SCMA层最多可分配给一个蜂窝用户，则资源分配矩阵可表示为

(4)

式中： AN×K=[αn,k] (1≤n≤N，1≤k≤K) 表示蜂窝用户的码本分配矩阵，当SCMA层k分配给蜂窝用户Un时αn,k=1， 否则αn,k=0； BM×K=[βm,k] (1≤m≤M，1≤k≤K) 表示D2D对的码本分配矩阵，当SCMA层k分配给D2D对Dm时βm,k=1， 否则βm,k=0。

由此可得目标函数及限制条件为

(5)

式中：C1和C2限制了最低用户速率，即保证系统内所有用户均能正常通信，C3和C4限制了码本最多分配给一个蜂窝用户，每个蜂窝用户或D2D对最多占用一个码本资源。

从目标函数可以看出，系统吞吐量提升的关键在于优化信道分配变量，又注意到上述资源分配问题是具有非线性约束的NP-hard优化问题，而图着色是解决此类资源分配问题的近似且有效的方法。因此考虑将SCMA码本资源建模为K种不同颜色，N个蜂窝用户建模为N个(蜂窝)顶点，M个D2D对建模为平面中的M个(D2D)顶点，从而将信道分配问题被转化为具有固定颜色的顶点着色问题加以解决。

2 基于超图着色的资源分配算法

在多小区系统模型中，由于允许多用户复用同一SCMA码本，大部分通信用户会受到来自其它用户的干扰，包括两个用户间的成对干扰和多用户间的累积干扰。为了提升用户通信质量，更好地描述和控制链路间的复杂干扰，提出建立超图并利用图着色法进行码本分配。

2.1 超图模型

假定网络中的N个蜂窝用户已完成码本分配，接下来只需进行D2D对的码本分配，因此超图建立过程中只需考虑D2D接收端受到的干扰。设X={x1,…,xM+N} 为超图H中的所有顶点元素(即所有蜂窝用户和D2D对)，则H={e1,…,eL}, 其中e1,…,eL为X中顶点所构成干扰边的集合。具体的，对D2D用户对Dm，干扰边建立原则为

于是满足式(6)的蜂窝用户Un和满足式(7)的D2D对Di与D2D对Dm构成2超边(包含两个顶点的超边)，满足式(8)的多个D2D对或满足式(9)蜂窝用户Un、D2D对Di与D2D对Dm构成3超边(包含3个顶点的超边)，某一顶点所在干扰边的数量称为该顶点的干扰度[10]。图2为超图模型示例。

图2 超图模型

利用关联矩阵可以方便表示超图中的干扰情况，图2中超图的关联矩阵I为

其中，行数表示顶点数，列数表示超边数。超边e1中包含4、5、6这3个顶点，对应矩阵中元素(4，1)、(5，1)、(6，1)为1，且由图2可知3个顶点的干扰度分别为3、2、2。

完成超图构建后即可通过图着色进行码本资源分配。在着色过程中将K个SCMA码本看作K种不同颜色，由于蜂窝用户已经完成了资源分配，即蜂窝顶点已着色只需对D2D顶点着色。于是依据构建的超图中，同一超边所包含顶点不能着相同颜色的原则，按照干扰度从大到小的顺序依次为D2D顶点着色，直到所有顶点着色完毕或没有可用的颜色为止，颜色相同的顶点即为复用同一码本的用户。

2.2 蜂窝复用备选集构建

超图着色算法主要包括超图构建和超图着色两个步骤，但由于本文考虑的是多小区场景，直接构建超图所涉及链路多，计算量大，算法复杂度过高，因此通过为D2D对建立基于距离的蜂窝复用候选集，在保证D2D用户通信质量的同时集简化超图结构，降低算法复杂度。

考虑蜂窝用户对复用其码本的D2D对的干扰，要使D2D对Di能正常通信，其信干比应满足

SINRDi≥η0

(10)

式中：η0为D2D用户接收信号的信干比门限。

于是根据式(1)可推导出

(11)

由于信道增益是一个随机过程，对式(11)两边同时求期望可得

(12)

(13)

于是满足式(13)的蜂窝用户可作为Di的复用备选对象。构建复用备选集的具体过程如算法1所示。

算法1：复用备选集建立算法

输入：UN，DM(UN为蜂窝用户集合，DM为D2D对集合)

输出：M个蜂窝复用备选集{OM}

(1)n=1(n为当前判断的蜂窝用户)

(2)m=1(m为需要建立蜂窝复用备选集的D2D对序号)

(3)Om=∅(Om为第m个D2D对的蜂窝复用备选集)

(4)对第n个蜂窝用户Un和第m个D2D对Dm， 判断是否满足式 (13) 条件

(5)如果 满足

Om=Om∪Un

否则

n=n+1

(6)如果 n≤N

转向执行 (4)

否则

转向执行 (7)

(7)m=m+1

(8)如果 m≤M

转向执行 (4)

否则

转向执行 (9)

(9)结束

2.3 超图构建

根据网络中通信链路间的干扰关系可建立一个描述各类干扰的超图，由于本文算法只考虑D2D对的码本分配，故构建超图时只考虑D2D用户所受干扰。

对D2D用户来说干扰对象包括两类，复用码本对应的蜂窝用户和共享同一码本的其它D2D用户。由于复用备选集限制了D2D用户的复用对象，因此只需考虑备选集中蜂窝用户及备选集中包含相同蜂窝用户的D2D对造成的干扰。基于上述干扰对象，D2D用户所受干扰的类型又分两种，二个用户间的成对干扰和多用户间的累积干扰，对复用备选集中的蜂窝用户，D2D用户与其可能存在成对干扰；对复用备选集中的蜂窝用户和备选集中包含相同蜂窝用户的D2D对，D2D用户与其可能构成累积干扰。为了便于判断干扰的建立，构造一个描述复用关系的集合 {Sn}(n=1,2,…,N)， Sn={Un,Dm,…,Di} (Un为蜂窝用户， Dm,…,Di为备选集中包括Un的D2D对的集合)。超图构建的具体过程如算法2所示。

算法2：超图构建算法

输入：DM，{SN}，{OM}(DM为D2D对集合，{SN}为描述复用关系的集合，{OM}为蜂窝复用备选集)

输出：超图关联矩阵I

(1)m=1(m为当前考虑干扰边建立的D2D对序号)

(2)n=1(n为当前判断复用关系集合中干扰的序号)

(3)如果 Om∩Sn=∅

转向执行 (4)

否则

转向执行 (8)

(4)对Sn中的蜂窝用户Un或D2D对Di， 根据式 (6) 或式 (7) 判断其对Dm的干扰是否满足干扰边建立条件

(5)如果 满足

Dm分别与Un或Di构成2超边

否则

转向执行 (6)

(6)对Sn中的蜂窝用户Un、 D2D对Di或D2D对Di、 Dj， 根据式 (8) 或式 (9) 判断其对Dm的干扰是否满足干扰边建立条件

(7)如果 满足

Dm分别与Un、 Di或Di、 Dj构成3超边

否则 转向执行(8)

(8)n=n+1

(9)如果 n≤N

转向执行 (3)

否则 转向执行 (10)

(10)m=m+1

(11)如果 m≤M

转向执行 (3)

否则 转向执行 (12)

(12)结束

2.4 超图着色算法

由于蜂窝用户已完成码本分配，故蜂窝顶点已着色。根据超图计算所有D2D顶点的干扰度，并按照由大到小的顺序依次为其着色(同一超边所连接的顶点不能着相同颜色)，直到所有顶点着色完毕，具体过程如算法3所示。

算法3：超图着色算法

输入：UN，DM，{OM}，I(UN为蜂窝用户集合，DM为D2D对集合，{OM}为蜂窝复用备选集，I为超图关联矩阵)

输出：D2D对码本分配方案

(1)根据关联矩阵求出所有D2D顶点的干扰度

(2)m=1(m为当前进行着色的D2D对序号)

(3)选择所有D2D对DM中具有最小干扰度的Dm

(4)根据关联矩阵I， 判断Dm对应Om中的蜂窝用户Un与Dm所属超边中的其它D2D对是否着相同颜色

(5)如果 是

将Un从Om中删除

否则 给Dm着Un相同颜色

(6)判断Om是否为空集

(7)如果 是

Dm保持静默并将其从DM中删除，转向执行 (8)

否则 对Om中的下一个蜂窝用户执行 (4)

(8)判断DM是否为空集

(9)如果 是

转向执行 (10)

否则 转向执行 (3)

(10)结束

3 仿真分析

3.1 仿真参数

针对多小区蜂窝上行链路设置仿真参数见表1。

表1 仿真参数

3.2 仿真结果

图3为一次仿真中的用户分布，在坐标轴上建立了一个包括3个蜂窝小区、30个蜂窝用户和45个D2D对的网络场景。基站位于各小区中心，蜂窝及D2D对在小区中随机分布，系统内用户通过36个正交的SCMA码本复用9个正交的时频资源。

图3 仿真场景示例

接下来将本文算法分别与传统超图着色法[11]、随机选择算法和图着色法[12]进行对比。为了更好地体现D2D用户接入数的变化，后续仿真结果中横坐标均设置为D2D对与蜂窝用户数量之比，蜂窝用户数为30。

图4 干扰边判断次数对比

其次比较了4种算法下D2D用户的接入数。如图5所示，随着网络中D2D对的增加，4种算法下D2D链路数均有增加，且从斜率变化可以看出，本文算法对系统容量的提升最为明显。同时，起初几条曲线间差距较小，但随着用户的进一步密集化，本文算法的D2D链路建立优势逐渐显现，这是由于多小区覆盖的用户可选择多个小区中的码本资源进行复用，解决了小区边缘用户因距离远、受干扰严重导致无法建立D2D链路的问题，从而有效提升了系统容量。

图5 系统容量对比

最后比较了4种算法下信道吞吐量的累积分布函数和系统和速率如图6、图7所示。当D2D对数量为60时，由图6可知本文算法下约88%的信道吞吐量达到4×106bit/s以上，而随机选择算法、图着色法和传统超图着色法分别只有84%、72%和61%，可见本文算法在一定程度上提升了信道吞吐量。由图7则可以看出，本文算法提升系统和速率的性能明显优于其它3种算法，同样随着D2D对数量的增加差距逐渐拉大。这是因为在用户密集分布的场景中，本文算法不仅能保证用户通信质量还能扩大系统容量，故而有效提升了系统吞吐量，且不同于其它3条曲线趋于收敛的走势，本文算法对系统和速率的增益还有一定上升空间，也充分说明了本文算法在多小区、多用户的场景中具备良好的性能。

图6 信道吞吐量累计分布函数对比

图7 系统和速率对比

4 结束语

在SCMA系统中，由于蜂窝用户和多个D2D对共享相同码本资源，故用户间存在严重干扰，本文要解决的就是通过合理的SCMA码本分配，在控制干扰的同时有效提升系统容量的问题。为了更好建模蜂窝与D2D异构网络，达到全局最优，在多小区蜂窝上行链路的场景中建立系统模型和目标函数，而后针对直接利用超图着色算法会导致的超图复杂度高、着色过程计算量大等问题，提出建立蜂窝复用候选集简化超图构建过程，从而在控制D2D用户所受干扰的同时简化了算法，提升了系统容量和通信和速率。最后通过仿真验证了本文算法的有效性。