5G通信中基于二分图匹配的链路均衡负载方法研究

龙舰涵 李 平

1(泸州职业技术学院电子工程学院 四川 泸州 646000)2(西南石油大学计算机科学学院 四川 成都 610500)

0 引 言

当前移动通信用户的总体规模和通信流量都在持续高速增长，4G-LTE通信技术由于受到整体框架体系的限制，在信道资源利用率、数据信息传输效率及频谱带宽使用等方面，都无法再为用户提供更好的服务体验，人类已经开始进入了5G通信时代。5G通信融合了新一代信号编码调制体系[1]、大规模MIMO[2]、高频段数据传输[3]、非正交多址接入[4]等先进的通信技术和理念，具有更大的网络数据吞吐量、更低的通信时延和更高的数据传输效率。5G通信支持超密集的异构网络框架[5]和无线自组织网络[6]，可以进一步提高对频谱的利用效率，降低通信网络的维护成本，还将极大地改善通信网络的健壮性，提升用户真实的使用体验。然而5G新技术的投入使用也会带来新的问题和挑战，由于采用了毫米波级别的通信技术[7]，需要实现跨频谱的信号传输，这对通信网络的均衡负载能力提出了更高的要求。此外，5G通信的用户基数和通信流量都远非4G网络可比，网络链路的密集程度更大[8]，同时对于数据传输的效率要求也更高，将会给网络整体容纳能力和通信链路的负载能力带来巨大压力。

目前，5G网络已经在我国部分一、二线城市试运行，在5G网络运行中也不同程度地出现链路负载不均衡的情况。网络通信中为了使网络资源得到更为充分的运用，往往会选择增加硬件资源的投入，但会导致网络成本增加及网络的可扩展性降低。对于网络均衡负载而言也可以采用，更优的方案是利用网络均衡算法增强资源调度的灵活性。5G通信中由于毫米波通信固有的缺陷，会导致现有通信网络分布不均匀、数据的动态传输出现大小流问题，影响网络通信的均衡负载。针对现有的这些通信链路负载不均衡和局部拥塞问题，所选择的解决方法大都是延续和优化原有4G-LTE网络均衡负载的解决方法，主要包括PSO均衡算法[9]、IsoRank算法[10]等。PSO均衡算法从底层的物理资源结构研究为出发点，考虑到底层节点资源的消耗与分配，以此来节省节点能耗增强网络性能。但在利用PSO算法寻找最优通信链路时，必须基于当前通信的实际情况，确定出不同链路之间的通信信号阈值范围[11]，如果阈值范围设定过大，直接会导致链路任务分配结果出现偏差，如果设定阈值范围过小，则会影响算法的整体效率；而IsoRank算法基于一种贪心的启发模式[12]，通过网络资源路径两两比对的方式实现全局范围内链路寻优，但该种算法的计算过程过于复杂，运算量极大，在实际应用中的效果要远差于理论研究。针对现有网络均衡负载方法在实用性上的不足，本文基于经典的匈牙利算法[13-14]，提出一种解决5G网络均衡负载的二分图匹配方案，以更合理地做好基站资源、小区资源和用户资源的合理分配，解决密集网络通信中链路拥塞和不均衡问题。

1 5G网络链路均衡负载管理与预测模型构建

作为一种重要的无线网络资源管理模式，链路均衡负载性能在5G网络时代具有更重要的意义。5G网络的密集程度和复杂程度要远远高于前几代通信网络，包括蜂窝网络、小区网络、局域网络以太网在内，共同形成了一种十分复杂的多协议异构网络，而且网络中通信链路众多、结构复杂、相互重叠，给毫米波大规模MIMO通信带来了极大的挑战。要确保5G通信网络的下行通信效率达到一种最优状态，必须要保证数据信息在无线蜂窝网络、局域网络、小区网络及各链路中保持一种相对负载均衡的状态[15-16]。由于采用了大规模MIMO的通信方式，5G网络的数据承载能力能够满足用户的高速通信需求，但如何在短时间内满足大量网络用户集中的数据上传与下载要求，将成为制约5G通信产业发展的主要难题之一。通信链路扩容需要大量的软硬件投入，在现阶段5G建设的初期无法实现，而如何利用现有网络资源有效实现网络均衡负载和调度方法，提高对资源的利用率，减少网络信道拥塞，将具有更重要的现实意义。在5G异构网络中基于经典匈牙利算法的网络均衡负载主要思想，是将全部网络节点按照最大负载能力设定一个阈值范围，并对这些网络节点进行实时监控，一旦识别出个别节点的负载能力已经超过了最大阈值范围，再按照重置分配方案重新分配网络资源和数据传输任务，以减轻超负荷通信网络节点的负载压力。

考虑到5G通信中密集蜂窝异构无线网络的通信场景，全部的单播通信行为[17]均由临近的基站负责载波资源的发送与调配，在单基站能够覆盖的网络范围内假定有m个5G通信用户和n个与之相对于的D2D用户(终端直通用户)[18]，那么此时在该小区内蜂窝网络通信用户使用基于正交的载波链路进行通信，在这种一对一的载波模式下，网络链路的信道增益情况用zk,j表示为：

(1)

式中：η表示通信中的路径损耗；α表示通信链路的信道衰落系数；d表示临近基站与5G用户之间的最短距离；i、j分别表示D2D模式中的第i个通信网络用户和第j通信网络用户；k为在第k个小区内收到的干扰信道增益符号。5G通信网络中链路载波上下行管理模型如图1所示。

图1 上下行网络通信资源载波分配管理模型

正常信道增益与干扰信道增益的定义结果如表1所示。

表1 5G通信中信道增益结果符号定义与表示

信干噪比是指系统接收到的期望信号强度与干扰信号强度的比值，在特定的阈值条件下信干噪比的值越大，链路均衡负载的效果越好。用户i在小区k内收到通信链路传输过来的信干噪比表示为：

(2)

F(κi,κj)=ξ(κi,κj)-c(κi,κj)

(3)

式中：ξ(κi,κj)表示用户i在小区内的收益增量总值；c(κi)表示为通信成本。这时在k小区的5G网络均衡负载均衡管理模型表示为：

(4)

式中：χ0表示高信噪比条件下模型常数项；λ1和λ2为在区间(0,1)范围内变化的实数。在相邻小区内网络信干噪比值越低，会对本小区的通信造成更强的干扰。利用式(3)中的效用函数，进而链路负载均衡管理模型即可预测出小区范围内每个用户所需要的网络资源，再基于优化的二分图匹配算法，改善网络用户与邻近基站之间网络资源匹配程度和一一对应程度，即可以充分利用现有5G网络资源，改善用户的使用体验和工作效率。

2 基于二分图匹配的5G网络链路均衡负载方案

2.1 基于二分图匹配的虚拟顶点转换

针对密集异构的5G网络场景，利用通信链路效用函数和链路均衡负载管理模型，预测出网络用户所需要带宽资源，在均衡负载管理中将5G网络资源与用户的通信要求进行合理匹配至关重要。为此本文采用了匹配性能更好的二分图模拟算法，平衡已有的网络资源与小区用户之间通信的实际通信需求，并通过增加虚拟数据顶点的方式平衡网络性能，并提高与改善5G通信系统数据吞吐量及对5G网络资源利用率。基于经典匈牙利算法，给定一个无向图G=(D,E)，其中：D为顶点的集合；E为顶点对应的边的集合。将顶点集合D按照以下条件划分为两个集合D1和D2：

(5)

在无向图结构中任一条边都满足e=(di,dj)∈D，且di∈D1，dj∈D2，集合D1和D2为顶点互补的子集。按照目标小区内用户的带宽需求与网络链路的负载情况，构建带有权重比例关系的二分图结构G=(H,D,E)，其中集合H和集合D是具有互补性关系的子集，H={h1,h2,…,hm}，D={d1,d2,…,dn}。对于任意的一个集合元素hi和dj，赋予顶点之间的边一个权重ωij，此时在5G网络中链路均衡问题就可以通过二分图模型转换为顶点集合元素的匹配问题。二分图模型还要求满足条件|H|=|D|，但在实际的网络资源匹配中小区用户数与总体网络链路的数据通常不相等，必须对经典的二分图算法进行优化和转换，假定|H|<|D|，就需要在H集合中增加|D|-|H|个虚拟顶点，虚拟顶点集合Q={q1,q2,…,qa}，其中|D|-|H|=a，二分图匹配的转换过程如图2所示。

图2 二分图虚拟顶点的转换过程

2.2 基于二分图的极大匹配

在给定的无向图G=(D,E)中，边集合M的任意两条边都不依附于同一个顶点，如果要实现边的极大匹配，可以通过增加已有边的匹配边数实现，选择这样的边数最大的子集称为图的最大匹配问题。如果一个匹配中，图中的每个顶点都与图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。二分图经过虚拟转换后，顶点集合数量与集合D的数量保持一致，经过优化后的二分图结构G′满足如下条件：

G′=H∪QG′∈(D,E)

(6)

(7)

(8)

5G网络中用户i与小区j组成的每一条边所占权重比例关系矩阵可以表示为：

(9)

采用基于二分图算法的5G网络资源匹配法，需要保证构建的集合中顶点数量相等，一般通过虚拟顶点的方式保证通信系统结构的稳定，这样才能够保证用户与小区资源之间的一对一匹配关系。利用链路均衡负载管理模型得到的网络资源匹配预估结果，优化和扩展原有的二分图结构，计算权重值和矩阵表达式，并对矩阵ωT的行元素和列元素进行初始化处理，得到k行n列权值不为零的矩阵：

(10)

计算矩阵的权值比例关系，如果矩阵中的任一个元素ωij的值为gx(i)+gy(i)，即可以实现矩阵匹配的最优化，并按照矩阵列和行的对应关系均衡小区内部用户与基站之间的链路均衡负载关系。在5G通信网络条件下，通信功能不仅限于传统小容量、高延时的通信场景，还要满足用户大容量多点通信的要求，最大限度地降低通信网络延迟。5G网络下的通信是一种动态、高速通信，对于通信网络的链路性能有着更高的要求。为更精确地预测网络链路的负载情况，需要首先通过网络链路模型预测出用户所需要的网络资源及小区资源的利用效率，在均衡网络负载的过程中实现小区基站、网络链路与用户之间的均衡负载。

3 仿真验证与性能评估

3.1 仿真模型搭建与仿真参数设置

为验证文中提出基于二分图匹配均衡负载方法的性能，在MATLAB仿真平台搭建仿真环境，在仿真场景中共设置了8个5G通信基站，其他的移动用户终端在小区范围内均匀布置，为保证实验测试的公平性，依据频谱的空闲时间，随机生成通信频谱。本文所搭建仿真系统的参数配置如表2所示。

表2 仿真参数设置

在本文建立的5G仿真网络中，基于二分图匹配的链路均衡机制流程如表3所示。

算法1基于二分图匹配的仿真流程

1. 系统初始化并设置小区基站数和用户数

2. 根据已有网络节点生成拓扑结构

3. 执行主循环程序，并对小区用户位置和基站位置赋值，明确通信网络的链路关系

4. 根据对小区链路资源占用的预估，计算用户数据传输中的信干噪比值和判决效用函数值

5. 根据hod值的更新结果，输出结果

6. if(nueinbs=ueinbs)

7. 系统链路性能指数输出

8. else

9. 重复步骤5、步骤6

10. end if

11.uen=max输出最优的网络链路负载匹配结果

3.2 链路均衡负载方法的性能比较

先在相同的仿真网络环境下，对比不同的链路均衡负载方法的Jain氏负载公平性均衡指数变化情况及系统资源利用率的大小。当5G网络小区内的通信用户总体数量持续增加，通信链路的负载情况也会随之出现同步涨落的现象，进而导致网络节点和通信链路出现负载不均衡的情况发生，个别用户的通信质量也会得不到保证，Jain氏公平性均衡指数是衡量网络负载公平性的重要指标之一(指数值通常的取值范围在(0.5,1.0)之间，指数值越高表明公平性越好)，该指数可以用j(xi)来表示：

(11)

在本文仿真环境下不同链路均衡负载方法的Jain氏公平性均衡指数变化情况如图3所示。

图3 Jain氏公平性指数随用户数的变化情况

当小区内用户数量增加时，不可避免地会导致Jain氏公平性均衡指数出现降低的趋势，用户之间会出现一种通信链路资源的竞争，这也是采取链路均衡负载算法控制网络节点和链路出现拥塞的原因。由于二分图匹配方法采用了基于最大相似度的二分图匹配矩阵，从行向量和列向量两个角度同步计算用户之间、用户与基站之间的链路负载情况，因此具有更好的链路资源分配效果，当小区内的用户数量达到峰值140时，公平指数仍旧可以控制在0.9左右，明显优于传统PSO的73%和IsoRank算法的74%，可以更好地维持链路的相对公平。

5G网络的系统容量主要指基站与用户之间、用户与用户之间链路容量的总和。分析各种不同链路均衡负载方法控制下仿真网络的系统容量变化，如图4所示。

图4 不同链路均衡负载方法下系统容量的变化情况

由于在仿真系统中采用了均衡负载机制，能够使小区内通信质量较差的用户得到更多的网络资源，但3种均衡方法的效率是不一致的，在二分图匹配均衡负载方法控制下，仿真系统的容量提升更快，系统资源的利用效率更高。在不同系统容量及3种链路资源负载均衡方法下，对网络带宽资源利用效率数据统计，结果如表4所示。

表4 资源利用效率

本文选取的评价5G通信网络中链路均衡负载方法的性能指标还包括通信业务的阻塞率，该指标对于衡量5G异构网络的均衡性、稳定性、链路均衡度水平至关重要。针对于实时的通信业务，异构网络系统的业务阻塞率如图5、图6所示，5G通信业务的阻塞率越低，表明链路均衡算法的性能越好。

图5 实时业务下各均衡方法的通信阻塞率

图6 非实时业务下各均衡方法的通信阻塞率

实时业务条件下，当小区内通信业务的用户数量超过100时，系统由于业务繁忙开始出现阻塞现象，但在基于二分图匹配的链路均衡算法下系统阻塞率变化幅度要更小，网络延迟相对于传统方法更低；而在非实时5G通信业务条件下，本文方法的优势更为明显。

在非实时业务条件下IsoRank算法和PSO算法分别在超过40个用户和50个用户时，就开始陆续出现通信阻塞，表明非实时业务对于通信链路不均衡的影响较为严重；而非实时通信业务对于二分图匹配均衡负载方法的影响程度较低，与实时业务的影响相近，这证明二分图匹配方法的适用范围更大，可以适合多场景的5G异构网络链路负载均衡应用。

4 结 语

5G网络条件下通信链路的密集程度更大，在高容量、高负载的网络环境下更容易导致网络链路负载不均衡和网络节点的数据拥塞，这将在很大程度上降低5G用户的网络使用体验。为满足用户更高、更快及更低延迟的实时通信要求，本文提出一种基于二分图匹配的网络链路均衡负载方法，利用二分图在顶点与侧边优化匹配等方面的优势，提升5G网络中通信链路均衡负载性能。链路均衡负载技术是5G通信的核心技术之一，只有在网络均衡负载的前提下，大规模MIMO和毫米波通信才具有实际的意义。随着5G用户数量的增加，二分图匹配算法的迭代次数也会呈几何数量级增加，会给虚拟顶点的选择与权重矩阵的构建带来一些新的问题，因此必须不断地优化模型效用函数性能和降低算法的复杂程度，以更好地应对用户数量的增长和网络链路密集程度的提高。