异构蜂窝网络中一种基于匈牙利算法的用户关联方法

苏恭超，陈 彬，林晓辉，王 晖，李乐民



异构蜂窝网络中一种基于匈牙利算法的用户关联方法

苏恭超1,2，陈 彬2，林晓辉2，王 晖2，李乐民1

(1. 电子科技大学通信与信息工程学院 成都 611731；2. 深圳大学现代通信与信息处理重点实验室 广东深圳 518060)

在异构蜂窝网络中使用传统的小区选择方法会导致宏基站和小基站的负载失衡，而与小基站关联的用户面临服务质量(QoS)的降低的问题。针对该问题，提出了一种基于效用函数最大化的用户与基站关联方法。该方法将用户与基站的关联过程建模为双目标优化问题并且线性化为系数可调的效用函数最大化问题，以实现基站负载均衡和用户QoS之间的折中。通过设计权值系数，将该效用函数最大化问题转化为基于二部图的最大匹配，并用匈牙利算法求得最优解。仿真结果表明，该方法实现了异构蜂窝网络中宏基站与小基站之间的负载均衡，并且通过系数调节，达到了基站负载均衡和用户QoS之间的折中。

二部图匹配; 用户关联; 异构网络; 匈牙利算法; 负载均衡

随着移动互联网的高速发展，不断增长的数据业务对蜂窝网络的容量和速率的要求逐渐增加。近年来，蜂窝网络架构逐渐向异构化方向演进，通过在宏基站覆盖区域内大量架设低功率低能耗的小基站(SBS)，形成异构网络(HetNets)[1]，为用户提供更多的频谱资源，从而提升用户速率和系统容量。

在传统的蜂窝网络中，终端用户仅和宏基站关联，由于宏基站数量有限，相邻小区间的干扰可控，因此终端用户通常通过测量各宏基站的参考信号功率来选择信号最强的基站并与之关联。然而由于宏基站的覆盖范围内有大量的低功率小基站存在，通过测量参考信号来选择小区基站，必然造成大量的用户仍然选择和大功率的宏基站关联，使得宏基站和小基站的负载呈现较大差异，从而导致大量的资源浪费。因此需要将终端用户主动的和小基站关联，实现宏基站和小基站之间的负载均衡，从而更有效地利用小基站的无线资源[2]。宏基站和大量的小基站共享频谱资源，在下行链路中宏基站将对与小基站关联的用户形成强烈的干扰，导致这些用户的信号与噪声加干扰比(signal to interference plus noise ratio, SINR)降低，从而降低服务质量。因此用户关联策略也应考虑到基站负载均衡和网络服务质量的折中。

近年来，异构蜂窝网络中的用户关联策略已成为学术界和业界研究的热点。一种较简单的方案是小区范围扩展[3]。终端用户所接收的来自小基站的参考信号功率被人为放大，使得更多的用户选择与小基站关联。然而功率放大系数难以确定最优值。文献[4-5]提出了一种求解对数效用函数最优化问题来获取最优关联策略的方法，通过松弛约束条件转化为凸优化问题并对其拉格朗日对偶问题求解。然而获取的最优解要求允许用户可以同时和多个基站关联，难以实现。另一类方法则是用组合优化的方法来求解[6-9]。文献[7-8]通过求解基于二分图的匹配问题来获取用户关联策略，然而其用户关联策略并非以基站负载均衡为目的。文献[9]提出用贪心算法来求解效用函数最大化问题的次优解，并指出效用函数的最大化问题可转换为基于二分图的匹配问题，但没有考虑基站负载均衡和网络服务质量的折中。

本文提出了一种负载均衡度可调的用户关联策略，将用户与基站的关联建模为可调系数的效用函数最优化问题，以达到基站负载均衡和网络服务质量的折中。通过将该效用函数最大化问题转化成一个基于二部图的最大匹配问题，利用匈牙利算法求得最优解。实验结果表明，这种方法和传统的基于最大SINR的用户关联策略相比，实现了宏基站与小基站之间的负载均衡，通过调节系数，达到了基站负载和用户QoS之间的折中。

1 系统模型与问题建模

考虑一个异构蜂窝网络的下行链路部分，该异构蜂窝网络包含宏基站和一系列小基站。假定在小区覆盖范围内总共有个基站和个用户。集合代表所有用户，集合代表所有基站。基站的传输功率为P。所有的基站均工作在同一频段并且频率复用系数为1。系统带宽为，信道取均值为1的瑞利衰落信道。

若用户与基站关联，则基站到用户的下行链路上的SINR可以表达为：

在后续的讨论中，假定信道带宽归一化为1。由于用户仅和单个基站关联，因此：

(3)

要获取用户与基站的关联策略，即求解关联策略变量，其为的矩阵，各元素取值为。一种常见的方法是将用户-基站关联过程建模为一个效用函数最大化问题[4]，其目标函数以用户速率为自变量，而与有关：

(5)

然而式(5)是一个组合优化问题并且是NP困难问题。用穷举法列出的所有可能取值需要的复杂度，而若将约束条件松弛为连续变量，则式(5)转为凸优化问题，但是约束条件导致所得的解要求一个用户同时与多个基站关联，并且所得的极值必然大于等于离散变量约束条件下的极值，因此是上限值。因此有必要考虑利用组合优化中的理论方法去求解该问题。同时，由于用户与小基站关联后导致用户SINR的降低，从而影响网络服务质量，因此所得出的用户关联策略应实现基站负载均衡和用户QoS之间的折中并且这种折中应当可以调整。

1.1 系数可调的效用函数最大化问题

为实现基站负载均衡，仍然保留对数函数作为效用函数。首先式(5)中的约束条件可以导出隐式约束条件：

注意到式(5)的目标函数可以写成：

(7)

对式(7)前半部分求极值，所得的最优解将导致用户和信号最强的基站关联(此时最大)。令，式(7)后半部分则可改写成，结合隐式约束条件，对归一化后则对该部分求极值转换为熵最大化问题[10]，所得的最优解将导致取均值，即用户在各基站之间均匀分布。因此可以将式(5)推广为一个双目标优化问题：

将式(8)线性化后，该优化问题表达为：

1.2 基于二部图的最优匹配

为使得用户和基站的关联符合匹配的定义，将基站用一个虚拟基站的集合来替代，由于基站最多与个用户关联，因此。此时基站与多个用户关联转化为每个用户与单个虚拟基站关联。因此基站和用户的关联，转化为二部图中的匹配，其中，边集中的边一端连接虚拟基站集合中的顶点，另一端连接用户集合中的顶点。图1说明了这种转换关系。

定理 1 假设有个用户和基站关联，则其权值之和等同于这个用户与中前个虚拟基站匹配的权值之和。

证明：由于基站与个用户关联，因此基站的负载。此时这个用户与基站关联的权值之和为。而若这个用户与中前个虚拟基站匹配，其权值之和：

(11)

文献[9]已证明若匹配的权值满足定理1的性质，则用户与基站之间的关联问题等价于用户与虚拟基站之间的最大匹配问题，因此有如下结论。

推论 1 式(9)等价于以下二部图最优匹配问题：

(12a)

(12b)

式(12)中，约束条件(12a)保证用户只与单个虚拟基站关联，约束条件(12b)保证虚拟基站最多只和一个用户关联。因此式(12)是一个二部图最大匹配问题，并且由于虚拟基站的数目大于用户数目，这种匹配是非完美匹配。

1.3 基于匈牙利算法的用户-基站关联

求解式(12)中的二部图最优匹配问题，可以使用文献[11]中提出的针对长方矩阵变量的匈牙利算法。匈牙利算法在求解二部图中的最优匹配时的复杂度为，，为2个集合的维数。由于式(12)中虚拟基站的数量为，因此匈牙利算法在求解式(12)时复杂度为，其复杂度仍远低于穷举法的复杂度。求出式(12)的解后，将矩阵按照列等分成部分，每部分为列，再观测矩阵第行第部分是否有1值，如果是则将置为1。遍历每行后即获得了用户与基站的关联。算法描述如下所示。

3) for=1～

Break

End if

End for

End for

4) 输出。

1.4 基于匈牙利算法的关联方案与凸优化-取整方案[4]和基于贪心算法的方案[9]的比较

由于式(9)等价于式(12)，用匈牙利算法求得的二部图匹配式(12)的最优解，也是组合优化问题式(9)的最优解。由于式(5)是式(9)的特例，文献[4-5]提出将约束条件松弛为，从而将式(5)转化为凸优化问题求解。由于等式约束条件的存在，对于用户，求得的最优解中可能存在多个。为保证用户和单个基站关联，文献[4-5]提出对最优解取整，即选取基站与用户关联，从而获得式(5)的一个可行解。然而，这种做法导致效用函数值降低，同时，如果最优解中存在和用户对应的多个相同的最大值，则这种取整的方案只能随机选取其中一个基站与用户关联。因此，文献[4-5]中使用的凸优化-取整方案获得了式(5)的次优解。另一方面，文献[9]中提出使用贪心算法求解式(5)，但只证明了贪心算法获得的解接近最优解，因此求出的解仍然是次优解。

2 仿真实验与结果分析

在仿真实验中，宏基站的覆盖区域设定为1 km2，其中有1个宏基站、5个小基站以及100个用户。宏基站位置居中，而小基站和用户位置按照均匀分布在覆盖区域内随机放置。宏基站和小基站的传输功率分别置为46 dBm和20 dBm，信道路径损耗设置为与距离相关，取值为(为距离)[4-5]。

a. 最大SINR关联

b.时凸优化-取整方案

c.时基于贪心算法的用户关联方案

d.时基于匈牙利算法的用户关联方案

图2 最大SINR和效用函数最大化下的用户-基站关联

可以看出，用匈牙利算法求得的用户关联策略与用凸优化-取整方法和用贪心算法求得的用户关联策略存在一定的差异。这是由于凸优化-取整方案和贪心算法求出的是式(9)的次优解，与通过匈牙利算法求出的最优解之间存在差异。图3给出了在不同的小基站数量下与宏基站关联的用户占全体用户的比例。与宏基站关联的用户数量，随小基站数量的增加而逐步降低。效用函数最大化框架下，与宏基站关联的用户显著少于最大SINR关联方案。基于匈牙利算法的关联方案下与宏基站关联的用户最少。基于贪心算法的方案和凸优化-取整方案下宏基站关联用户比例较接近于基于匈牙利算法的方案。

图4给出了最大SINR和不同系数下基于匈牙利算法的效用函数最大化关联策略中宏基站和小基站负载的对比。在最大SINR关联策略下，有约10%的用户与小基站关联。在效用函数最大化关联策略下与小基站关联的用户比率均有增加。当时，和小基站关联的用户比率超过50%。当时则更偏向于与最大SINR的基站关联，和小基站关联的用户比率更接近于最大SINR策略。而当时和小基站关联的用户比率位于前两者之间。这说明，通过调节系数的值，可以影响宏基站与小基站之间的负载均衡。

图4 不同基站-用户关联策略中与各类基站关联的用户比例

图5给出了不同的基站-用户关联策略下用户SINR均值的累积分布。可以看到最大SINR关联策略能为用户提供最高的SINR。采用效用函数最大化策略将用户关联至小基站后SINR均有所降低。当时超过40%的用户SINR降到0 dB以下。当时超过20%的用户 SINR降到0 dB以下，当时SINR在0 dB以下的用户比率约为10%。这说明调节系数后实现了基站负载均衡和用户SINR之间不同程度的折中。

图5 用户SINR均值的累积分布

3 结 束 语

本文提出了一种系数可调的效用函数最大化策略来实现异构蜂窝网络中用户与宏基站和小基站的关联。将效用函数最大化问题转化为基于二部图的最优匹配，并利用匈牙利算法求得最优解，确保每个用户仅和单个基站关联，易于实现。实验结果表明通过本文提出的方法所获得的基站-用户关联，实现了宏基站与小基站之间的负载均衡，并且通过调节参数在基站负载均衡和用户QoS之间取得折中。

[1] ANDREWS J G. Seven ways that HetNets are a cellular paradigm shift[J]. IEEE Communications Magazine, 2013, 51(3): 136-144.

[2] ANDREWS J G, SINGH S, YE Qiao-yang, et alAn overview of load balancing in HetNets: Old myths and open problems[J]. IEEE Communications Magazine, 2014, 52(4): 18-25.

[3] DAMNJANOVIC A, MONTOJO J, WEI Yong-bin, et al. A survey on 3GPP heterogeneous networks[J]. IEEE Wireless Communications Magazine, 2011, 18(3): 10-21.

[4] YE Qiao-yang, RONG Bei-yu, CHEN Yu-dong, et al. User association for load balancing in heterogeneous cellular networks[J]. IEEE Transactions on Wireless Communications, 2013, 12(6): 2706-2716.

[5] SHEN Kai-ming, YU Wei. Downlink cell association optimization for heterogeneous networks via dual coordinate descent[C]//Proceedings of IEEE Int. Conf. on Acoustics, Speech and Signal Processing. Vancouver, BC, Canada: IEEE, 2013: 4779-4783.

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

[7] MISHRA S, RANGENENI S, MURTHY C. Exploiting an optimal user association strategy for interference management in HetNets[J]. IEEE Communications Letter, 2014, 18(10): 1799-1802.

[8] TAEJOON K, DONG Miao-miao. An iterative Hungarian method to joint relay selection and resource allocation for D2D communications[J]. IEEE Wireless Communication Letters, 2014, 3(6): 625-628.

[9] PRASAD N, ARSLAN M, RANGARAJAN S. Exploiting cell dormancy and load balancing in LTE HetNets: Optimizing the proportional fairness utility[J]. IEEE Transactions on Communications, 2014, 62(10): 3706-3722.

[10] BOYD S, VANDENBERGHE L. Convex optimization[M]. Cambridge: Cambridge University Press, 2004.

[11] BOURGEOIS F, LASSALLE J C. An extension of the Munkres algorithm for the assignment problem to rectangular matrices[J]. Communications of the ACM, 1971, 14(12): 802-804.

编 辑 叶 芳

User Association in Heterogeneous Cellular Networks Via the Hungarian Method

SU Gong-chao1,2, CHEN Bin2, LIN Xiao-hui2, WANG Hui2, and LI Le-min1

(1. School of Communication and Information Engineering, University of Electronic Science and Technology of China Chengdu 611731; 2. Key Lab of Advanced Communications and Information Processing, Shenzhen University Shenzhen Guangdong 518060)

In heterogeneous cellular networks, traditional user association schemes based on reference signal power result in load imbalances between macro cell base stations (MBSs) and small cell base stations (SBSs). Meanwhile, offloading users to SBSs face the quality of service (QoS) degradation. In this paper, we propose a utility maximization framework to address the user association problem. In order to strike a tradeoff between load balancing and user QoS experiences, a bi-criterion optimization problem is formulated to solve the user association problem. The bi-criterion optimization problem is then linearized as a utility maximization problem with a tunable parameter. In addition, we show that the utility maximization problem can be reformulated as a maximum bi-partite matching problem and can be solved in polynomial time by using the Hungarian method. Simulation results show that our proposed method achieves load balancing and can strike tradeoffs between load balancing and user QoS by tuning the optimization parameter.

bipartite matching; cell association; heterogeneous networks; Hungarian method; load balancing

TN92

A

10.3969/j.issn.1001-0548.2017.02.005

2015-07-01；

2016-01-14

国家自然科学基金(61301182, 61372078, 61171071)；国家973项目(2013CB329103)

苏恭超(1979-)，男，博士，主要从事无线通信方面的研究.