一种基于软件定义无线网络的三维D2D匹配算法

摘要

本发明提出了一种基于软件定义无线网络(SDWN)的三维D2D匹配算法，在软件定义网络和无线网络融合的架构下，通过控制器对全局网络中设备缓存信息的感知，对用户进行集中控制从而实现D2D全双工通信。本发明利用DAC(D2D‑aware caching)缓存策略和全双工D2D的特点，通过建立混合整数规划问题实现全网D2D用户传输速率最大化。算法先针对全双工D2D用户共享CUE用户频谱资源而带来的传输速率下降的问题，应用一种复杂度低、运算速度快的功率控制算法；再基于图论模型，构建了三维匹配算法来进行D2D全双工匹配和复用信道分配，实现一对一匹配。该算法区别于已有的基于价格的三维匹配算法，算法复杂度低，且实现效果略好。

说明书

技术领域

本发明属于在软件定义无线网络架构下的联合功率控制的三维D2D匹配算法，涉及SDWN架构、DAC缓存策略以及解决混合整数规划问题，具体表现在功率控制算法和基于超图模型的三维匹配算法。

背景技术

软件定义网络(SDN)是一种基于软件的网络技术，它倡导控制与数据的分离。软件定义网络架构将网络分为应用层、控制层、数据层。应用层通过北向接口向控制层提供开放的编程接口和网络视图，控制层包括控制器和网络操作系统，并通过南向接口控制数据层进行数据处理、转发和收集。控制平面与数据平面的解耦、开放的可编程接口、集中化的控制使软件定义网络技术在简化网络基础设施，提升网络管理效率方面具有独特优势。因此，学术界试图将内容中心网络和软件定义网络这两种网络架构相融合，以期创建既能高效管理，又能满足海量数据流量分发的网络架构。

将软件定义网络的设计思想引入到无线网络中，依据SDN基本特性，控制器利用网络的全局视图，可提取整个网络的全部信息来提高网络资源分配的有效性，然后可通过控制器中的模块运算来实现全网优化。

另一方面，尽管有大量的内容存储在核心网里，但实际上只有很小数量的较为流行的内容能被大部分移动数据用户请求，且这些内容遵循一定的内容流行度分布，大量研究表明其为Zipf分布。因为大部分的数据流量都是由于多次重复下载一些流行的内容，如流行的视频和音乐，因此研究人员将关注放在内容缓存以防止冗余流量产生。缓存一般有两种方式：一是边缘缓存，内容被存储在辅助节点上，比如小区基站，通过减少核心网络的传输来减轻小区的回程消耗；二是设备缓存，即内容存储在用户设备上，通过减少蜂窝传输来降低基站的负载，从而增加了蜂窝小区用户的速率，减少了基站的动态能量消耗。由于缓存的内容是即时提供的，且通过局部设备缓存的D2D通信，用户接受信号的延迟也会更低。

随着移动数据流量的增加，无线同频同时的全双工通信引发关注。相比半双工通信，全双工能潜在的提升一倍的频谱效率，实现更加灵活的频谱使用，同时降低端到端的时延。全双工D2D通信也有助于实现5G系统高频谱效率和高能量的需求。其信道增益、跳数增益、复用增益和双工增益可提高系统总体频谱效率并减少用户的能量消耗，其高效的频谱利用，可显著增加接入用户数，从而减少未来超密集网络中基站的部署密度，降低网络复杂度和成本。

基于同时同频收发的全双工通信可以进一步提升D2D通信的性能，但也给现有的网络带来了更加复杂的用户间干扰和自干扰，而干扰影响接受信号质量，如果不能得到有效控制，会严重损坏网络的总体性能和用户服务体验。因此，D2D资源优化配置和干扰管理机制一直是业界研究的重点。

发明内容

为了克服上述现有技术的缺点，本发明的目的在于提供一种基于软件定义无线网络的三维D2D匹配算法，在软件定义网络和无线网络融合的架构下，基于DAC设备缓存，对用户进行集中控制从而实现D2D全双工通信，本发明算法复杂度低，且实现效果好。

为了实现上述目的，本发明采用的技术方案是：

一种基于软件定义无线网络的三维D2D匹配算法，其特征在于，在软件定义网络和无线网络融合的SDWN(Software Defined Wireless Network)架构下，通过控制器对全局网络中设备缓存信息的感知，对用户进行集中控制从而实现D2D全双工通信，并利用DAC(D2D-aware caching)缓存策略和全双工D2D的特点，通过建立混合整数规划问题实现全网D2D用户传输速率最大化：

利用一种复杂度低、运算速度快的功率控制算法解决全双工D2D用户共享CUE用户频谱资源而带来的传输速率下降的问题；

基于图论模型构建三维匹配算法，进行D2D全双工匹配和复用信道分配，实现一对一匹配，达到全网优化。

所述SDWN架构分为两个部分：控制平面和数据平面，控制平面层设立了SDN控制器，该控制器利用网络的全局视图，可提取整个网络的全部信息来提高网络资源分配的有效性，然后通过控制器中的模块运算来实现全网优化；在数据平面层，以单蜂窝小区做为模型，根据用户缓存的内容以及请求的内容，可将用户进行匹配，进行D2D全双工通信。

所述DAC缓存策略，具体包括以下步骤：

3.1)假设用户请求的内容来自一个拥有L个文件的库，每个用户最多只能存储K个文件，K＜＜L，每个用户每次只能请求一个文件，且他们的请求服从齐夫定律：

其中，ξ为齐夫分布的流行度指数，描述了流行度分布的一个偏度，且取决于内容类型，则q_i就表示用户请求第i个文件的概率，j是一个量级数；

3.2)将库中L个文件的2K个最流行的内容分成数目相等的互补重叠的两个集合，定义为集合C_A和集合C_B，即每个集合有K个内容，并且集合C_A被请求的概率h_A和集合C_B中的内容被请求的概率h_B大致相等，记为

这两个集合以相等的概率即50％随机分布到各个用户，定义缓存用户为CU，定义存储集合C_A的用户为UE>B的用户为UE>

3.3)当一个UE A请求集合C_B且周围有UE>A，则两者可匹配，进行D2D全双工通信；

3.4)若周围没有满足条件的CU用户或以概率1-h_A-h_B请求文件，则接受来自基站的信号，即成为下行用户；

3.5)若请求自身缓存的内容，则不需要接受信号，即自主链接。

所述混合整数规划问题，具体包括以下步骤：

4.1)为了使所有的D2D对加权总和最大化，通过匹配方法来配对缓存用户，同时分配合适的频谱到相应传输链接中，即这是一个D2D对匹配联合信道分配的问题，为避免对蜂窝网络的过度干扰，对D2D传输进行功率控制，联合二进制决策变量和D2D对以及蜂窝用户(CUE)功率变量来优化系统性能：

4.2)首先，针对D2D用户共享CUE用户频谱资源而带来的传输速率下降的问题，利用功率控制算法，将混合整数规划问题分解成优化功率分配问题，并将非凸问题转变成容易解决的凸问题，使用迭代算法计算出问题的近似最优解；

4.3)其次，利用基于超图的三维匹配方法，进行D2D全双工匹配和复用信道分配，实现一对一匹配，以最大限度的提高D2D传输总速率。

定义超图HG＝(v,ε)，其中v为顶点集，ε为超边集，加权超图即每一个边e∈ε都有一个权值w(e)，本发明中，可匹配的缓存用户对和CUE用户表示为在超边的三个顶点，每一个超边都有一个权重值显示D2D传输速率；将超图HG＝(v,ε)转变成普通图G＝(v′,ε′)，其中，图G的每个顶点都是超图的三个顶点的集合，且都有一权值，表示D2D传输速率，而边ε′表示图G的两个顶点之间的非空集交集，即两个组合有一个或多个相同的元素，图G相当于由各个子图的交集组成，即G＝G₁∪G₂∪...∪G_n；

定义最大加权匹配集为Ω，最终目的是寻找最大加权值ω(Ω)，算法先从第一个子图开始，寻找其有最大权重的顶点到集合Ω，同时删除其余子图中的此顶点，以此类推，直到循环遍历完所有子图，则最后匹配结果即为集合Ω。

本发明在SDWN架构下的算法流程，具体包括以下步骤：

5.1)SDWN架构下数据平面中基站(BS)收集小区内所有用户信息以及信道信息，并发送到控制平面的D2D匹配模块中的功率控制模块中进行功率控制分配计算；

5.2)SDWN的控制平面中功率控制模块把所有功率分配信息反馈给同样是控制平面的D2D匹配模块进行D2D匹配以及信道分配计算；

5.3)控制平面的D2D匹配模块将计算好的匹配信息发送到数据平面中基站中，再由基站进行最终的用户D2D全双工通信与信道分配。

本发明算法区别于已有的基于价格的三维匹配算法等，算法复杂度低，且实现效果略好。

附图说明

图1为软件定义无线网络架构图；

图2为基于超图的加权三维匹配图；

图3为在SDWN架构下的算法流程图；

图4为流行度指数ξ与缓存命中率的相关关系仿真图；

图5为用户缓存不同文件数K，缓存用户数N与D2D总速率之间的关系仿真图。

具体实施方式

下面结合附图和实施例详细说明本发明的实施方式。

本发明提出了一种基于软件定义无线网络(SDWN)的三维D2D匹配算法，在软件定义网络和无线网络融合的SDWN架构下，通过控制器对全局网络中设备缓存信息的感知，对用户进行集中控制从而实现D2D全双工通信。本发明利用DAC(D2D-aware caching)缓存策略和全双工D2D的特点，通过建立混合整数规划问题实现全网D2D用户传输速率最大化。先针对全双工D2D用户共享CUE用户频谱资源而带来的传输速率下降的问题，应用一种复杂度低、运算速度快的功率控制算法；再基于图论模型，构建了三维匹配算法来进行D2D全双工匹配和复用信道分配，实现一对一匹配，具体地：

1、系统模型

如图1所示，SDWN架构分为两个部分：控制平面和数据平面。

1)控制平面层

控制平面层设立了SDN控制器，该控制器包含了一系列模块，如本发明能用到的资源分配模块以及D2D匹配模块等。依据SDN基本特性，控制器利用网络的全局视图，可提取整个网络的全部信息来提高网络资源分配的有效性，然后可通过控制器中的模块运算来实现全网优化。

在控制平面中设计并提出了反馈控制回路，控制器首先通过基站收集全网信息，将信息发送到功率控制模块，在此执行功率控制算法。其中，功率控制模块包含在D2D匹配模块中，将功率优化信息发送到D2D匹配模块中进行匹配和优化，最后再将结果发回给基站部署。

2)数据平面层

OpenFlow协议部署在数据平面的基站(Base Station-BS)中，用来支持控制器和基站之间的信息交互。

在数据平面中，为了简化，不考虑小区之间的相互干扰，以单蜂窝小区做为模型。在蜂窝小区中随机分布着M个上行蜂窝用户(CUE)，定义为CUE＝{CUE₁,...,CUE_k...,CUE_M}，N个缓存用户(Cache>1,...,CU_n...,CU_N}。根据CU用户缓存的内容以及请求的内容，可将CU用户进行D2D匹配，从而进行全双工通信。D2D对需要复用CUE用户的信道资源，每个CUE占用一个信道，相互之间无干扰，且每个D2D对最多占用一个信道，每个信道最多被一个D2D对占用。

2、DAC缓存策略

假设用户请求的内容来自一个拥有L个文件的库，每个用户最多只能存储K(K＜＜L)个文件，每个用户每次只能请求一个文件，且他们的请求服从齐夫定律：

其中，ξ为齐夫分布的流行度指数，描述了流行度分布的一个偏度，且取决于内容类型。一般的，ξ在0.5到1.5之间。

根据DAC缓存策略，将库中L个文件的2K个最流行的内容分成数目相等的互补重叠的两个集合，定义为集合C_A和集合C_B，即每个集合有K个内容，并且两个集合中的内容被请求的概率(和)大致相等，记为

这两个集合以相等的概率(1/2)随机分布到各个用户，即CU用户。定义存储集合C_A的用户为UE>B的用户为UE>

1)当一个UE A请求集合C_B且周围有UE>A，则可进行D2D全双工通信；

2)若周围没有满足条件的CU用户或以概率1-h_A-h_B请求文件，则其接受来自基站的信号，即成为下行用户；

3)若请求自身缓存的内容，则不需要接受信号，即自主链接。

根据以上DAC缓存策略，定义UE>B的用户集合为UE B当中请求集合C_A的用户集合为当满足一定的通信距离条件时，RB和RA可以匹配进行全双工D2D匹配。

3、数据层平面模型

在数据平面中，定义了CUE＝{CUE₁,...,CUE_k...,CUE_M}个蜂窝上行用户，再者，根据上述DAC缓存策略，能够进行匹配组成全双工D2D通信的CU用户为UE>B的用户以及UE B当中请求集合C_A的用户

假设CUE的信道分配已经提前预定好，每个CUE占用一个信道，即信道CH_k分配给CUE_k，相互之间并无干扰。每个D2D对最多占用一个信道，且每个信道最多被一个D2D对占用。以下介绍在全双工D2D通信下的优化功率分配算法。

在每个D2D对中，两个全双工D2D用户同时刻同频率发送和接受信号，因此会彼此产生自干扰。另外，在同一信道中，D2D对和CUE之间存在共信道干扰，如图1所示。与半双工D2D的蜂窝系统相比，全双工D2D系统的干扰模型更加复杂。基站将接受到D2D对的两个用户的联合信道干扰。与此同时，每个D2D用户都受到来自CUE的信道干扰和来自其传输天线的自干扰。

假设RB_i与RA_j能组成D2D对，且与CUE_k共享信道CH_k。D2D用户RB_i(RA_j)接受来自RA_j(RB_i)信号，全双工传输引起的自干扰以及来自CUE_k的干扰。因此RB_i与RA_j在信道CH_k的信干噪比(SINR)为：

其中，表示RB_i、RA_j传输功率，表示CUE_k的传输功率，β₁与β₂为自干扰系数，表示RB_i与RA_j之间的信道增益，表示CUE_k到RB_i的干扰信道，表示CUE_k到RA_j的干扰信道，N₀表示高斯白噪声。

根据香农理论，D2D对在信道CH_k可获得的总的传输速率为：

基站将接受来自CUE_k的信号以及来自D2D对RB_i、RA_j的干扰。因此基站在信道CH_k的SINR为：

其中，表示CUE_k与BS之间的信道增益，表示RB_i到BS的干扰信道，表示RA_j到BS的干扰信道。

同样的，可获得的传输速率为：

4、问题模型构建

本发明的目的是通过D2D技术来满足用户需求，同时最大化D2D链接的传输速率。将D2D对传输速率作为目标函数：

其中，ρ_ij为二进制参数，当RB_i与RA_j之间的距离在d_max范围内，则为1，否则为0。

为了使所有的D2D对加权总和最大化，本发明应用了一种有效的匹配方法来配对RB与RA，同时分配合适的频谱到此传输链接中，即这是一个D2D对匹配联合信道分配的问题。同时，为了避免对蜂窝网络的过度干扰，应对D2D传输进行功率控制。

定义二进制变量X＝{x_i,j,k}为D2D对匹配以及信道配对情况，当x_i,j,k＝1表示复用CH_k的RB_i与RA_j建立D2D对成功。联合二进制决策变量x_i,j,k和功率变量来优化系统性能。构建了混合整数规划模型：

P1:

s.t.:C1:

C2:

C3:

C4:

条件C1表示D2D对的传输功率范围，并且保证不会超过最大值条件C2保证CUE传输功率不会超过最大值条件C3保证蜂窝链接的QoS要求，条件C4的三个不等式表示每个RB_i最多只能匹配一个RA_j，反之亦然，同时每一个信道最多只能分配给一对D2D。

5、D2D对匹配以及信道分配算法

1)功率控制算法

为了解决P1混合整数规划问题，将P1进行分解，首先解决优化功率分配的问题。对每一对复用CUE_k的RB_i、RA_j，有

P2:

s.t.:C1:

C2:

C3:

P2是非凸问题，因此将非凸问题转变成容易解决的凸问题。

首先，将条件C3转变成

其中，

为了满足最大化D2D速率，蜂窝用户的功率是越小越好，因为这样产生的干扰也相对较小，但同时要满足CUE的QoS，因此可直接取下界，即

将转变成如下形式：

其中

另则D2D传输功率将转变为

则可将问题P2简化成问题P3形式

P3:

s.t.:C1：

可以看出问题P3的条件C1与C2都是线性的，但是效用函数依然为非凹的，所以问题P3依然是非凸的。根据引理1来解决P3问题，引理1的证明在附录A。

引理1：定义R(z)＝log₂(1+z)，z≥0，则一给定正值z₀∈[0，∞)为R(z)的下界

R(z,z₀)＝alog₂z+b

其中

基于引理1，定义满足问题P3的条件C1，C2的功率为将转变为

其中，a₁、b₁及a₂、b₂分别为的相关下界系数，因此问题P3可转换成：

P4:

s.t.:C1：

C2：

使用对数变换将问题P4转变成如下形式：

P5:

s.t.:C1：

C2：

其中

问题P5是P4的等式转变，解决P5就相当于解决P4。因此，我们有以下两个定理。

定理1：问题P5是一个凹函数，且条件C1与C2为凸约束条件的，因此问题P5是严格的凸优化问题，所以可由标准的算法解决。证明在附录B。

定理2：可以证明，问题P4求得的传输速率优于带进的传输速率。定义为问题4的最优解，则会有证明在附录C。

具体算法如图3所示。

附录A：

引理1的证明：

有

当有z＝z₀，

f(z)的最小值为

所以有f(z)＝R(z)-R(z,z₀)＝log₂(1+z)-(alog₂z+b)≥0，因此，R(z)≥R(z,z₀)，引理1证明完成。

附录B：

的凹性是由和的凹性决定的。因此推导其黑塞矩阵，发现其都是严格的正定矩阵。因此和都是凸的，得到是凹函数，且所有的约束条件都是凸性条件，推导出问题P5是严格的凸优化问题。

附录C：

基于引理1，可以得到

第一个不等式表明是的下界，第二个不等式表明为问题P4的最优解。

2)基于超图的三维匹配算法

以最大化全网D2D传输速率为目标，将制定基于缓存的RA、RB用户进行D2D匹配以及可复用的信道分配。定义可配对的RA、RB用户以及CUE用户的所有可能潜在组合为集合Φ＝{(i,j,k)}，意味着RB_i与RA_j匹配成D2D对并复用CUE_k信道资源，则可以构造一个加权的三维匹配图，基于设备缓存提出了基于超图的三维匹配方法以最大限度的提高D2D传输总速率。如图2所示。

定义超图HG＝(v,ε)，其中v为顶点集，ε为超边集。加权超图意思是每一个边e∈ε都有一个权值w(e)。超边可以定义为顶点的非空集合，顶点的数量即为超边的基数。如果每个超边都有相同的基数n，则定义此超图为n-uniform。RB用户、RA用户和CUE用户可以表示为在超边的三个顶点，每一个超边都有一个权重值显示D2D传输速率，由功率控制算法得出。因此，基于设备缓存的D2D匹配与信道分配可以被表述为加权3-uniform超图。

超图HG的匹配结果为超边的子集，且没有超边包含相同的顶点，即满足一对一匹配条件，匹配的基数就是匹配边的数目。一个加权超图HG的多维最大加权匹配就是图HG的匹配超边的子集。在本发明中，目标就是解决3维最大加权匹配。

首先，将超图HG＝(v,ε)转变成G＝(v′,ε′)，其中，图G的每个顶点都是超图的三个顶点的集合，而边ε′为顶点v′之间的所有交集。在加权3-uniform超图中，HG的超边就相当于图G的顶点，因此，图G的每一个顶点都有一权值，代表此匹配的D2D传输速率。定义最大加权匹配集为Ω，Ω为所有组合(i，j，k)的子集，本发明就是要寻找一个具有最大加权值ω(Ω)的独立集。如图2所示，加权图G的顶点都是所有潜在组合Φ＝{(i,j,k)}，意味着RB_i与RA_j匹配成D2D对并复用CUE_k信道资源，则每个顶点都有权值。G的边表示两个顶点之间的非空集交集，即两个组合有一个或多个相同的元素。在这种情况下，图G就相当于由各个子图的交集组成，即G＝G₁∪G₂∪...∪G_n。功率分配算法的目的是寻找最大加权值ω(Ω)，如下所示：

1.初始化:令l＝0，设问题的初始值为误差ε＞0；

2.迭代

3.l＝l+1；

4.

5.计算相应的系数

6.求解凸优化问题P5并获得最优解

7.将进行指数变换，求得问题P4的最优解

8.直到

9.迭代结束

10.返回

算法先从第一个子图开始，寻找其有最大权重的顶点到集合Ω，同时删除其余子图中的此顶点。以此类推，直到循环遍历完所有子图，则最后匹配结果即为集合Ω。

3)复杂度分析

将对基于超图的三维匹配算法与基于价格的三维匹配算法进行分析与对比。由于两种算法的主要区别在于最终的匹配方法，因此只考虑此部分的时间复杂度(着重循环次数)。

已知RB用户数为N₁，RA用户数为N₂，CUE用户数为M。在基于价格的三维匹配算法中，每一个RB用户匹配其最想匹配的RB和CUE单元块的复杂度为其中为基于步长s而提升价格后的最终迭代次数，因此此算法匹配过程的复杂度为(N₂≥M)或者(M≥N₂)。在基于超图的三维匹配算法中，匹配算法主要集中在算法2中的step2部分，由算法可知，要实现一对一匹配结果，则最多能产生min(N₁,N₂,M)个子图，算法循环每个子图从而找寻最大权重顶点，因此此算法匹配过程的复杂度为O(min(N₁,N₂,M))。可以看出，基于超图的三维匹配算法计算量较小。

6、SDWN下的算法流程

算法流程如图3所示，具体操作过程如下所示：

1)BS收集小区内用户信息以及信道信息发送到控制平面的D2D匹配模块的功率控制模块中进行算法1的功率分配计算。

2)功率控制模块把信息反馈给D2D匹配模块进行算法2的D2D匹配以及信道分配计算。

3)D2D匹配模块发送控制信息到基站进行最终的用户D2D匹配与信道分配。

7、仿真实验

通过仿真研究了基于超图的三维D2D匹配以及信道分配算法的性能，并且与基于价格的三维匹配算法和随机匹配算法进行比较，仿真结果表明本发明构建的算法相较于其他两个算法能达到较好的效果。部分仿真参数如下表所述。

定义缓存命中率为自身设备中导致缓存命中的请求百分比。图4为流行度指数ξ与缓存命中率的相关关系。

由以下D2D匹配和信道分配算法：

可知，当设备缓存文件数K越大，则缓存命中率就越大，且随着ξ的增大，缓存命中率也越大，但都不超过0.5，满足了齐夫定律。

图5仿真了用户缓存不同文件数K的情况下，缓存用户数N与D2D总速率之间的关系。令蜂窝用户M＝8，流行度指数ξ＝1.0。当设备缓存文件数为100时，明显比K＝50时D2D总速率大，但是当K＝200时，D2D总速率却又比K＝100时小，比K＝50时大。因为由图4可知，当K＝200时，自我缓存命中率就越大，缓存用户并不需要D2D链接就可进行自我链接满足需求，因此D2D匹配数少，从而总速率也会较小。结论就是随着设备缓存文件数越大，用户请求的内容属于集合C_A和集合C_B的概率就大，因此D2D匹配通信的可能性就越大，则D2D总速率就越大；但当用户缓存文件数足够大时，用户请求的内容属于自身缓存的内容就越大，则需要D2D匹配通信的情况就相对少些，因此D2D总速率就会稍小。

总之，本发明提出了一种基于软件定义无线网络(SDWN)的三维D2D匹配算法，在软件定义网络和无线网络融合的架构下，基于DAC设备缓存，对用户进行集中控制从而实现D2D全双工通信，本发明算法复杂度低，且实现效果好。