面向蜂窝—D2D混合场景的双层博弈匹配算法

2018-02-01姚天张晖

电信科学 2018年1期

姚天，张晖

姚天，张晖

（南京邮电大学，江苏南京 210003）

随着无线技术的迅猛发展，无线接入网络进入新的阶段，即第五代（5G）移动通信系统阶段。多种技术场景并存的5G环境具有异构性和动态性的特点，对无线资源管理提出了严峻的挑战。如何实现网络资源与用户需求之间的最佳匹配变得尤为重要。因此，5G环境下无线资源匹配算法已成为当前研究热点。提出一种面向蜂窝—D2D混合场景的双层博弈匹配算法，建立基于用户体验质量的公平性匹配模型，采用双层的匹配博弈理论加以求解，通过仿真验证所提算法的有效性，结果证明了所提算法的可行性。

5G环境；蜂窝场景；D2D场景；资源匹配；匹配博弈

1 引言

在过去的数十年里，移动通信已经彻底地改变了人们的生活方式，但人们对于更高性能的移动通信系统的追求却从未止步。为了适应未来5G系统连续广域覆盖、热点高容量、低功耗大连接和低时延高可靠的技术场景，在移动物联网和互联网发展的驱动下，移动通信系统进入新的发展阶段，即第五代（5G）移动通信系统阶段[1-4]。

在移动通信系统应对多样化的业务需求和不断提升的速率要求时，频谱资源、能耗和部署成本等成为移动通信系统发展的主要制约条件。与此同时，5G移动通信系统具有动态性和异构性等特点，均对无线资源管理提出了严峻的挑战。因此，5G环境下无线资源管理问题成为当前无线通信领域中的研究热点。

无线资源管理问题本质上是指无线资源和用户的业务需求之间的匹配问题。无线资源的匹配算法可以分为3个层次：第一层业务侧优化算法，即通过降低用户体验质量，自适应地优化业务传输的指标要求，实现业务需求与给定网络资源的匹配，例如，参考文献[5]中提出了一种在带宽有限的情况下，根据不同用户的最低需求来调节用户的速率，寻求系统总体效用最大化的速率分配方案；第二层网络侧优化算法，是指通过对网络资源的最优匹配实现某种网络性能目标（吞吐量，系统传输时延），从而保障用户的业务需求，目前这一类匹配是研究的重点，以参考文献[6]中给出的算法为例，将系统吞吐量作为优化指标，采用联盟博弈算法来解决多个D2D用户和蜂窝用户的上行资源分配问题；第三层网络和业务匹配算法，通过从网络侧与业务侧的联合优化，以最小的资源量和最优的分配方式来保障用户的业务体验质量，参考文献[7]给出了根据网络状态适时调整传输负载，然后在满足传输时延要求的情况下，通过优化资源调度方案使系统总体效用最优化的算法。

本文研究的匹配算法属于第二层网络侧优化算法，对于5G环境下的信道分配问题，现有的研究主要采用凸优化算法[8]、贪心算法[9]和基于博弈论的算法[10-12]。其中基于博弈论的算法应用较为广泛，例如非合作博弈理论常被用于分布式地解决在D2D通信中的资源分配问题[13-15]，但从这个模型中得到纳什均衡是单边不稳定的。相比较而言，以匹配博弈理论为基础的资源分配提供了一种分布式自组织的双边稳定的匹配。匹配博弈理论最初用于经济学领域，用以解决如婚姻匹配、大学录取等双边的匹配问题[16]。随着匹配博弈理论的发展，越来越多的学者将其用于无线通信领域中，用以解决无线资源匹配问题[17]，突破了博弈论的很多局限性。

参考文献[18]提出了基于匹配博弈理论，为基站中蜂窝用户分配信道的算法。ZHOU Z Y等人[19]提出了基于博弈理论的D2D通信环境下以系统能耗作为优化指标，采用迭代的方法对频谱和功率进行联合分配的算法。而在参考文献[20]中，提出了一种以系统的吞吐量为优化指标，基于多对多匹配博弈理论的D2D用户信道分配算法。这些算法均提供了易于实现的架构，以解决NP难无线资源分配问题。

但是，上述参考文献提出的算法中，没有考虑5G蜂窝—D2D混合场景下同时为蜂窝用户和D2D用户分配信道的问题，同时它们大多都是以系统的吞吐量为优化指标，且没有考虑到用户的公平性问题。而5G环境下，作为关键技术之一的D2D通信技术在提高系统容量和频率利用率的同时，也为蜂窝用户引进了干扰，极大地提高了不同用户信道分配的复杂度。同时，5G通信系统以用户体验为导向，一味追求系统的吞吐量已不再适用，因此本文提出了一种面向蜂窝—D2D混合场景的双层博弈匹配算法，建立了基于体验质量（QoE）的公平性匹配模型。

2 网络场景

图1 蜂窝—D2D混合场景系统模型

3 模型构建

由于5G系统是以用户体验为导向的，在该模型中采用QoE作为优化指标，用满意度效用函数来描述具有不同的速率需求的用户的QoE，即定义如下：

其中，表示单个用户的吞吐量，req表示用户基本速率需求；r表示用户饱和速率需求，r表示使用户满意度下降所对应的速率初始值，为斜率参数。对于每个用户来讲，req、r、r和均可能不同。显然，QoE指标由两部分组成：第一部分表明（以用户基本速率需求为基准）当吞吐量越大，用户需求越能得到满足，相应的QoE越大；第二部分表明随着吞吐量增大，用户需求已经完全满足（达到饱和），以用户饱和速率需求为基准，再行增加吞吐量，已无法提升用户体验，反而会造成成本提高，故相应的QoE将会变小。可以看出，上述定义能够准确地描述吞吐量与QoE的关系。

限制条件C1和C2限制CU和DU必须满足其SINR的要求，C3表明x,j的值只能是0或者1，C4表明每个CU的信道最多能被max个DU复用，这个条件可以限制每个CU的信道上的干扰，同时减少执行的复杂度，C5限制条件是考虑到用户的公平性，保证每个DU和CU所获得的体验质量都能达到它们的最低限度，以防出现信道分配严重不均的情况。

4 双层博弈匹配算法求解

在5G环境下的蜂窝—D2D混合场景中，存在两种干扰，即DU复用CU的资源块对CU造成的干扰和复用同一个CU资源块的DU之间产生的干扰，使DU和CU的匹配结果相互影响，极大地增加了信道分配问题的复杂度。因此，本文提出了一种易操作的双层博弈匹配算法，将这个复杂的信道分配问题简化为两层问题来解决，即第一层：CU分配信道，基于多对一匹配博弈理论，采用蜂窝用户的信道分配算法求解；第二层：DU复用CU的资源块，基于多对多匹配博弈理论，采用D2D用户的信道分配算法求解。最后再采用迭代的方法分别解决第一层和第二层，即用双层博弈匹配算法求解该复杂的信道分配问题。

对于上述涉及多个对象相互作用的问题，匹配博弈理论是一种有效的工具。因此，分别建立基于考虑已存匹配的多对一匹配博弈理论，其中玩家是CU和信道代理商，和考虑已存匹配的多对多匹配博弈理论，其中玩家是DU和信道协调器。整个双层博弈匹配算法的架构如图2所示。接下来，将分析上述两层问题的求解过程。

图2 算法整体匹配架构

4.1 蜂窝用户的信道分配算法

定义4 （稳定）匹配中不存在阻塞个体和阻塞对。

CU的信道分配方案步骤如下。

步骤1 初始化：建立初始的匹配状态。

4.2 D2D用户的信道分配算法

接下来，考虑建立D2D用户对（DU）和资源块RB之间的多对多匹配模型。在网络中，CU和DU通过共享频谱资源来提高频谱和能量的利用效率，但D2D通信会为蜂窝引进新的干扰。多个DU可以复用同一个信道，一个DU也可以同时复用多个信道。因此，利用同一个信道的DU和CU之间存在干扰，利用同一个信道的DU之间也会存在干扰，基于已存匹配的多对多匹配博弈理论来解决DU的信道分配的问题。

这一类型的匹配叫做考虑已存匹配的匹配博弈算法，即每个个体有一个建立在对方个体上的动态偏好列表，这与传统上个体拥有固定的偏好列表的匹配算法不同[23]。在这个匹配模型中，偏好列表是在某一匹配状态时，根据DU和RB的效用值建立的。

受到住房分配问题的启发，提出一种将其拓展为多对多的匹配博弈算法。和传统的延迟接受算法不同，本算法允许两个D2D用户对直接交换各自的资源块。为了更好地描述双方偏好的相互作用关系，定义交换匹配的概念如下：

基于交换匹配的概念，交换阻塞对定义如下。

定义6 （交换阻塞对）（D,D′）是一个交换阻塞对，当且仅当：

交换操作是在交换阻塞对之间进行的，条件（1）表明交换阻塞对（D,D）进行交换操作之后，参与交换的个体包括资源块和D2D用户对的效用不能降低；条件（2）表明至少一个个体的效用在交换之后效用会提高。值得注意的是，空穴的效用和与空穴相匹配的个体无需考虑这两个条件。

DU的信道分配方案具体步骤如下。

步骤1 建立初始的匹配状态，每个DU为其匹配的RB分配能量。

步骤4 每个资源块RB根据自己的偏好列表，同意最偏好的用户的建立交换对的请求，拒绝其他的用户。

步骤5 更新匹配状态，同时更新与每个资源块匹配的DU个数。

步骤6 返回步骤1，直到系统中没有交换阻塞对，即得到稳定的匹配。

4.3 算法流程

结合以上CU和DU的信道分配方案，完整的蜂窝—D2D混合环境下双层博弈匹配的算法流程如下。

步骤2 如果迭代次数不大于最大匹配次数，即≤max时，执行步骤3，否则执行步骤4。

步骤4 根据步骤1匹配结果，利用DU信道匹配方案，更新分配向量；返回步骤2。

步骤5 得到稳定的匹配结果。

综上所述，本文提出的双层博弈匹配算法的匹配流程如图3所示。

图3 算法的匹配流程

5 仿真验证

为了验证本文提出的双层博弈匹配算法的有效性，用MATLAB语言编写了本文算法的验证程序。在本仿真模型中，以50 m为半径的圆形区域内随机分布CU和DU，DU的接收端和发送端之间的最大距离为20 m。其他系统仿真参数如下：算法最大迭代次数max=20；路径衰减指数=4；路径衰减常数=10−2；DU发送端最大发送功率P=23 dBm；CU最大发送功率Q=23 dBm；信道带宽=180 kHz；信道噪声功率0=−114 dBm；每个DU用户最大复用用户信道数为2。

图4（a）表示信道数为6、DU个数为2时系统总体效用QoE随CU个数（cu）的变化曲线。从中看出，随着蜂窝用户数的增加，系统总体效用也增加。图4（b）表示CU个数为4、DU个数为3时系统总体效用QoE随信道个数（channel）的变化。从中看出，随着信道个数的增加，系统总体效用也不断增加。而且，由图4可以看出，本文算法随着迭代次数的增加最后趋于稳定。

图4 本文算法性能随参数的变化曲线

接下来，将从有效性、稳定性、收敛性和复杂性几个方面分别将本文提出的双层博弈匹配的匹配算法（下文简称双层博弈匹配算法）与随机匹配算法和最优化匹配算法进行比较，分析本文提出的双层博弈算法的性能。

随机匹配算法以式（2）为优化模型，不考虑用户公平性，采用两两随机匹配的方法求解相应模型。最优化匹配算法以吞吐量为优化目标构建最优化模型，不考虑用户公平性，采用多对多匹配博弈理论求解相应模型[20]。3种算法的比较指标均采用本文定义的用户QoE指标。

图5 3种算法的性能比较

（1）有效性

本文的算法是以QoE为指标进行匹配优化的，将该算法与随机匹配和最优化匹配算法两种方法相比较。在图5（a）中，在DU个数为2、信道数为10时，比较CU个数变化后，每种算法的对应的QoE效用值。在图5（b）中，当CU个数为4、信道数为8时，比较DU个数变化后，每种算法对应的QoE效用值。由于最优化匹配算法不考虑用户公平性，能够实现总体吞吐量的最大化。在某些情况下（QoE指标与总吞吐量呈递增关系时），最优化匹配算法性能更优（如图5（a）第二个点）；但在大多数情况下（QoE指标与总吞吐量并不是简单的递增关系），而且双层博弈匹配算法是直接优化QoE指标，故双层博弈匹配算法性能将更优。由图5（a）和图5（b）可以看出，双层博弈匹配算法性能整体优于随机匹配算法和最优化匹配算法。

（2）收敛性和稳定性

6 结束语

本文基于匹配博弈理论，结合5G环境的特点，提出了蜂窝—D2D混合场景下面向QoE的双层博弈匹配算法，将复杂的信道分配问题分层进行解决。首先，建立了第一层蜂窝用户信道分配算法，然后建立了第二层D2D用户信道分配算法，从而形成整个算法解决所有用户信道分配的问题。这个过程中充分考虑了用户的公平性和用户之间复杂的干扰问题，同时改进了系统最优化目标函数，即效用函数，不再是一味追求高吞吐量，而是考虑用户的体验质量。本文算法是基于匹配博弈理论，因此匹配的结果是双边稳定的，而且该算法不是集中式算法，而是分布式的，不依赖于参与匹配的终端和系统的拓扑结构，具有很好的有效性、收敛性和可行性。

[1] GE X, TU S, MAO G, et al. 5G ultra-dense cellular networks[J]. IEEE Wireless Communications, 2016, 23(1): 72-79.

[2] 陈晓贝, 魏克军. 全球5G研究动态和标准进展[J]. 电信科学, 2015, 31(5): 16-19.

CHEN X B, WEI K J. Global research and standardization progress of 5G [J]. Telecommunications Science, 2015, 31(5): 16-19.

[3] 杨峰义, 张建敏, 谢伟良, 等. 5G蜂窝网络架构分析[J]. 电信科学, 2015, 31(5): 52-62.

YANG F Y, ZHANG J M, XIE W L, et al. Analysis of 5G cellular network architecture [J]. Telecommunications Science, 2015, 31(5): 52-62.

[4] 王胡成, 徐晖, 程志密, 等. 5G网络技术研究现状和发展趋势[J]. 电信科学, 2015, 31(9): 156-162.

WANG H C, XU H, CHENG Z M, et al. Current research and development trend of 5G network technologies [J]. Telecommunications Science, 2015, 31(9): 156-162.

[5] TAN L, ZHU Z, GE F, et al. Utility maximization resource allocation in wireless networks: methods and algorithms[J]. IEEE Transactions on Systems Man & Cybernetics Systems, 2015, 45(7): 1018-1034.

[6] LI Y，JIN D. Coalitional games for resource allocation in the device-to-device uplink underlaying cellular networks[J]. IEEE Transactions on Communications, 2014, 13(7): 3965-3977.

[7] ZUO S, HOU I H, LIU T, et al. Joint rate control and scheduling for real-time wireless networks[J]. IEEE Transactions on Wireless Communications, 2017, 12(1):1-10.

[8] LIANG Y S, CHUNG W H, NI G K, et al. Resource allocation with interference avoidance in OFDMA femtocell networks[J]. IEEE Transactions on Vehicular Technology, 2012, 61(5): 2243-2255.

[9] NGO D T, KHAKUREL S, LE-NGOC T. Joint subchannel assignment and power allocation for OFDMA femtocell networks[J]. IEEE Transactions on Wireless Communication, 2014, 13(1): 342-355.

[10] WANG C, LIU Y, TAO M, et al. Stackelberg game for spectrum reuse in the two-tier LTE femtocell network[C]//Wireless Communications and Networking Conference, April 07-10, 2013, Shanghai, China. Piscataway: IEEE Press, 2013: 1888-1892.

[11] SUN Y, WANG J, SUN F, et al. Energy-aware joint user scheduling and power control for two-tier femtocell networks: a hierarchical game approach[J]. IEEE Systems Journal, 2016.

[12] SUN Y, WANG J, SUN F, et al. Local altruistic coalition formation game for spectrum sharing and interference management in hyper-dense cloud-RANs[J]. IET Communications, 2016, 10(15): 1914-1921.

[13] SONG L, HAN Z, XU C. Resource management for device-to- device underlay communication[M]. New York: Springer, 2014.

[14] LIU J, KATO N, MA J, et al. Device-to-device communication in LTE-Advanced networks: a survey[J]. IEEE Communications Surveys & Tutorials, 2017, 17(4):1923-1940.

[15] ZHOU Z, DONG M, OTA K, et al. Game-theoretic approach to energy-efficient resource allocation in device-to-device underlay communications[J]. Communications IET, 2014, 9(3): 375-385.

[16] GALE D, SHAPLEY L S. College admissions and the stability of marriage[J]. American Mathematical Monthly, 2013, 120(5): 386-391.

[17] GU Y, SAAD W, BENNIS M, et al. Matching theory for future wireless networks: fundamentals and applications[J]. IEEE Communications Magazine, 2015, 53(5): 52-59.

[18] ELHAJJ A M, DAWY Z, SAAD W. A stable matching game for joint uplink/downlink resource allocation in OFDMA wireless networks[C]//2012 IEEE Internation al Conference on Communications, Jun 10-15, 2012, Otlawa, ON, Canada. Piscataway: IEEE Press, 2012: 5354-5359.

[19] ZHOU Z Y, MA G, DONG M, et al. Iterative energy-efficient stable matching approach for context-aware resource allocation in D2D communications[J]. IEEE Access, 2016(4): 6181-6196.

[20] ZHAO J, LIU Y, CHAI K K, et al. Many-to-many matching with externalities for device-to-device communications[J]. IEEE Wireless Communications Letters, 2016, 6(1): 3452-3458.

[21] LONG C, ZHAO H, BAO L, et al. Resource allocation algorithm based on stable matching in hierarchical cognitive radio networks[J]. Journal of Electronics & Information Technology, 2016, 38(11): 123-128.

[22] HOLFELD B, JORSWIECK E. On stable many-to-many matching for distributed medium access with reuse of spectral resources[C]//The 20th International ITG Worksnop on Smakt Antennad (WSA 2016), March 09-11, 2016, Munich, Germany. Berlin: VDE Uerlag, 2016: 536-543.

[23] GU Y, ZHANG Y, PAN M, et al. Matching and cheating in device to device communications underlying cellular networks[J]. IEEE Journal on Selected Areas in Communications, 2015, 33(10): 2156-2166.

A bilevel game matching algorithm in cellular-D2D hybrid scenario

YAO Tian, ZHANG Hui

Nanjing University of Posts and Telecommunications, Nanjing 210003, China

With the rapid development of wireless technologies, wireless access networks enter the 5G system phase. 5G environment with various technical scenarios is heterogeneous and dynamic, causing great challenges for wireless resource management. Hence, it is significant to achieve the optimal matching between network resources and user demands. Therefore, wireless resource matching algorithms in 5G environment have become one of the hottest research directions. A bilevel game matching algorithm in cellular-D2D hybrid scenario was proposed: a QoE based matching model considering user fairness was constructed, the bilevel matching game theory was used to solve this optimization problem, and the effectiveness of proposed algorithm was verified through simulations.

5G environment, cellular scenario, D2D scenario, resource matching, matching game

TN915

10.11959/j.issn.1000−0801.2018027

2017−06−13；

2017−11−17

张晖, zhhjoice@126.com

国家自然科学基金资助项目 (No.61471203)；江苏省“六大人才高峰”项目（No.RJFW-024）；江苏省“青蓝工程”项目(No.2016); 南京邮电大学“1311”人才计划基金资助项目(No.2015)；通信与网络技术国家工程研究中心开放课题(No.TXKY17002)；江苏省计算机信息处理技术重点实验室开放课题(No.KJS1518)；国家科技重大专项基金资助项目(No.2012ZX03001008-003)

The National Natural Science Foundation of China (No.61471203), Six Talent Peaks Project of Jiangsu Province (No.RJFW-024), “Qing Lan Project” of Jiangsu Province(No.2016), “1311 Talent Program” of NJUPT(No.2015), Open Project of National Engineering Research Center of Communications and Networking(No.TXKY17002), Open Project of Jiangsu Provincial Key Laboratory for Computer Information Processing Technology(No.KJS1518), National Science & Technology Major Project (No.2012ZX03001008-003)

姚天(1995−)，女，南京邮电大学硕士生，主要研究方向为5G资源配置。