基于图着色的大规模MIMO系统中动态导频分配

樊自甫，胡 敏，李悦宁

(重庆邮电大学 下一代网络应用技术研究所，重庆 400065)

基于图着色的大规模MIMO系统中动态导频分配

樊自甫，胡 敏*，李悦宁

(重庆邮电大学 下一代网络应用技术研究所，重庆 400065)

针对大规模多输入多输出(MIMO)系统中存在的导频污染问题，提出一种基于图着色的动态导频分配方案。为了更加合理地分配导频、减小导频污染，首先，利用小区间协作，将不同小区的用户通过带权值的边相连来构建边权值干扰图，以此来描述多小区用户间的导频污染程度;然后，在传统的图着色理论基础上，利用相连用户边权值不同的特点，优先为受导频污染严重的用户分配导频资源。理论分析和仿真结果表明，所提的导频分配方案不同于现有的分布式导频分配方案，在考虑所有小区导频复用的情况下，基于图着色集中式地分配导频，能够减小小区间用户的干扰，提升大规模MIMO系统的上行可达和速率。

大规模多输入多输出；导频污染；导频分配；图着色；可达和速率

0 引言

近年来，大规模多输入多输出(Multiple-Input Multiple-Output, MIMO)技术已成为无线通信的研究热点[1]。所谓的大规模MIMO，即在基站处配置大量天线，通过增加空间自由度的方式来大幅地提高系统容量、频谱效率，降低能量消耗[2]。随着智能终端的迅速普及和无线数据业务需求的爆炸式增长，以支持高速率传输为目标的4G将难以满足未来无线通信的需求，因此，作为5G关键技术之一的大规模MIMO具有广阔的应用前景[3]。

大规模MIMO需要精确估计信道状态信息(Channel State Information, CSI)来实现其特有的优点。传统的CSI反馈量是随着天线数而线性增长的,而当基站处天线数目大量增加时，反馈所需的时间将远大于信道相干时间[4]，传统的信道状态信息反馈模式已无法适用，因此，目前仅考虑应用于时分双工(Time Division Duplex, TDD)系统运用于大规模MIMO，利用信道互易性来获得信道状态信息[5]。但是由于正交导频数量是有限的，所以不可避免地总是存在不同小区的导频复用，从而导致基站无法区分，即造成了所谓的“导频污染”(pilot contamination)现象[6-7]。

针对导频污染问题，文献[8-15]从导频分配的角度进行了深入研究。文献[8]提出了有效的导频时移方案，通过相邻小区间的异步传输来抑制导频污染，但存在导频与数据间相互干扰的问题;文献[9]利用用户的位置信息，提出了一种基于用户位置信息的导频分配方案，有效地减小了导频污染并提升了系统的上行和速率;文献[10]提出了一种基于博弈论的导频分配方案，该思路是把导频选择问题当作基站间的博弈，构建其潜在博弈模型，通过博弈理论证明该方案能明显减轻导频污染，虽然该方案改善了系统信道估计的精确度，但是运用于复杂场景中难以确定纳什均衡点;文献[11]考虑到实际通信系统中不同用户与基站之间的大尺度衰落系数不同的情况，利用目标小区与干扰小区间用户的信号干扰强度差对干扰小区进行分类，提出了一种动态导频分配方案来减轻导频污染，提升系统的下行平均可达和速率，虽然利用了小区间协作的优势，但该方案主要是针对目标小区性能提升，忽略了用户间导频污染程度不同的事实;文献[12]提出了一种智能导频分配方案来减轻导频污染，并有效地提升了目标小区中所有用户的上行信干噪比(Signal to Interference plus Noise Ratio, SINR) ，虽然考虑到不同用户与基站之间的信道质量可能不同的情况，但是该模型的应用场景有限;文献[13]提出了基于人工鱼群算法的导频分配方案来减小导频污染，突破局部最优解的限制，降低了算法的复杂度，提高了用户的平均可达速率，但是迭代次数较多;文献[14]利用注水算法对信道较好的用户分配干扰严重的导频，该方案提高了目标小区的和速率且复杂度低，有效地降低了导频污染;文献[15]提出了一种新型的导频分配方案，联合时域空域，对小区进行分组，最大最小化用户SINR。

本文考虑到不同用户导频污染程度不同的情况，利用小区间协作的优势，把导频分配问题制定为最大化上行平均可达速率的优化问题，基于传统图着色理论基础，优先为受导频污染严重的用户分配导频资源。仿真结果表明，相对于传统导频分配方案和文献[12]方案，本文方案提升了系统的上行可达和速率，获得了较好的性能。

1 系统模型

系统模型如图1所示，考虑的是由L个小区组成的多小区多用户大规模系统，其中，每个小区由一个配备N根天线的基站和K(K≤N)个单天线用户组成。假定系统工作在TDD模式下，信道估计通过上行训练序列来获得，第j小区的用户k到第l小区的基站的信道模型为：

(1)

其中：h〈j,k〉,l表示N×K的小尺度衰落信道矩阵，其所有的元素是独立同分布的(Independently and Identically Distributed, IID)，且满足h〈j,k〉,l～CN(0,IN)；β〈j,k〉,l表示大尺度衰落系数，包括路径损耗和阴影衰落。β〈j,k〉,l可以表示为：

(2)

其中：r〈j,k〉,l表示第j小区的用户k到第l小区的基站之间的距离；α是路径损耗衰落系数；z〈j,k〉,l表示阴影衰落。

图1 大规模MIMO系统模型Fig. 1 System model of massive MIMO

(3)

(4)

(5)

(6)

其中：δ〈l,k〉表示小区内干扰和非相关噪声。于是，第l小区用户k的上行SINR(N→∞)为：

(7)

由式(7)可以看出，噪声和小尺度衰落效应会随着基站天线数趋于无穷而被平均掉，系统的SINR将只与β〈j,k〉,l有关。因此，导频污染是影响多小区大规模系统性能的瓶颈，在大尺度衰落系数β〈j,k〉,l确定的情况下，怎样选用导频便成为限制系统SINR的关键因素。

2 基于图着色的导频分配

与传统的随机导频分配方案不同的是，本文旨在最大化L个小区中所有KL用户的上行可达和速率。因此，可将优化问题建模如下：

(8)

(9)

穷举法是解决优化问题P2的直接方式，但是导频分配的计算复杂度较高[16]。基于此，本文提出一种近似最优的导频分配方案，首先对不同小区用户间的导频污染程度构建边权值干扰图，然后采用图着色方法对用户进行导频分配。

2.1 边权值干扰图

传统的导频分配方案是将一组正交导频序列随机分配给小区内的用户，该方案虽易于实施，但忽略了不同小区用户间导频污染程度不同的事实。从式(9)可以看出，在大规模MIMO系统中，系统的上行平均可达和速率与大尺度衰落系数β〈j,k〉,l密切相关，信道的性能主要受大尺度衰落系数的影响。另外，由式(2)可知，大尺度衰落系数和用户与基站之间的距离有关，当不同小区内的用户离基站越近，导频污染越严重，反之，导频污染的程度越小。因此，本文利用不同小区用户与基站间大尺度衰落不同的特点，考虑不同小区用户间导频污染程度不同的事实，对导频进行分配。

图2 不同小区的两个用户的导频污染程度关系Fig. 2 Relationship of pilot contamination between two users in different cells

为了简便，对于同一小区的不同用户相互连接，其边取值为-1，因此，可以构建一个边权值干扰图作为无向加权图G=(V,E)，如图3可知，其中,集合V中的顶点表示用户，集合E中边值表示导频污染的程度。

2.2 基于图着色的导频分配

为了获得导频开销与减小导频污染之间的折中，在导频资源有限的约束条件下，提出了基于图着色的导频分配方案来减小导频污染。受经典Dsatur算法[17]的启发，其思想是根据顶点的度数进行降序排序，尽可能地复用颜色对它们依次进行着色。基于图着色的导频分配是在边权值干扰图的基础上，针对具有较大权值连接的用户，因其受导频污染程度较大，优先为其分配导频。然而，与Dsatur算法中未连接的顶点分配相同颜色的思想不同的是，在边权值干扰图中，具有较小权值的不同小区的两个用户可能会分配相同的导频，其原因是在实际大规模MIMO系统中有限的导频资源的额外约束。因此，在颜色不足的约束下，所提的导频分配方案可视为经典Dsatur算法的特定变体。在数学上，所提的导频分配方案的伪代码如算法1。

图3 构建边权值干扰图Fig. 3 Constructing edge-weighted interference graph

算法1 基于图着色的导频分配算法。

对于一些中型企业，在发展中已经形成较为科学的结构来进行经营活动，企业间部门的分化和权责范围非常的明确，这种经营方式能够有效对增加企业的管理效率和各方面工作的执行力度。但是一些企业在管理中，没有协调好各个部门之间的关系，使得部门之间的难以进行通力合作，在现金流的反应上，就会使得部门都开始向企业讨要过多的备用金。对于企业的经营发展而言，这种方式不仅仅会让企业的备用金过多，造成企业经营利润下井，同时这种方式也会让企业的资金管理混乱，不利于企业的长期发展。

输入k=1,2,…,K,L,S,β〈j,k〉,l；

输出 导频分配{φ〈l,k〉}。

1)

计算ω〈l,k〉,〈j,k〉值，构建加权干扰图G=(V,E)；

2)

初始化{φ〈l,k〉}=0；

3)

选择ω〈l,k〉,〈j,k〉值最大的边所对应的不同小区的两个用户：

4)

选中的两个用户分别分配导频：

φ〈l1,k1〉=1，φ〈l2,k2〉=2

5)

定义Ω={〈l1,k1〉,〈l2,k2〉}

6)

while ∃φ〈l,k〉=0 do

7)

8)

9)

构建最优导频集：Λ={s:∀k,φ〈j0,k〉≠s,1≤s≤S}

10)

11)

12)

Ω=Ω∩{〈l0,k0〉}

假设所有小区使用同一组正交导频，基于图着色的导频分配主要包括三个部分：初始化、用户选择和导频分配。首先对加权干扰图进行初始化(步骤3)～5))，在无向加权图中选择ω〈l,k〉,〈j,k〉值最大的边所对应的不同小区的两个用户，即用户〈l1,k1〉和〈l2,k2〉。在步骤4)中，对上述所选择的两个用户分别分配φ1和φ2。于是，在步骤5)中，将它们分配完导频的用户添加到Ω集中作为Ω的初始化。之后，再选择剩下未分配导频的用户对它们依次分配导频，直到所有的用户被分配导频，即不存在φ〈l,k〉=0的情况。

用户选择(步骤7)和8))。在步骤7)中，为了选择用户，本文引入了一个优先参数δ〈l,k〉，以此来定义用户〈l,k〉与其他在Ω中的用户所连接的边权值的总和。于是，在步骤8)中，除去Ω集中所分配的用户，选择δ〈l,k〉值最大所对应的用户〈l0,k0〉。

导频分配(步骤9)～12))。本文基于图着色的导频分配方案是从可用的导频资源中选择引起导频污染程度最小的导频分配给用户〈l0,k0〉。具体地，在步骤9)中构建最优导频集Λ，其中包含第l0小区中未被使用的导频，以确保同一小区不存在导频复用。于是，在步骤10)中，假定用户〈l0,k0〉分配导频φs，本文定义了λs来表示在Ω集中含导频φs的用户与用户〈l0,k0〉的导频污染程度，即使用某导频的次数。最后，在步骤11)中，最小的λs值所对应的导频将被分配给用户〈l0,k0〉，之后，在步骤12)中，将分配好导频的用户〈l0,k0〉添加到Ω集中。以此类推，直到所有的用户分配相应的导频。

3 仿真结果与分析

本章利用蒙特卡罗法对所提的基于图着色的导频分配方案进行仿真分析。仿真中考虑的是由L个小区组成的蜂窝系统，每个小区包含K个单天线用户和配备N根天线的基站。其中，用户的位置在它们相应的小区中随机生成，同时，大尺度衰落系数β〈j,k〉,l通过式(2)随机生成。目前大多数文献都是针对目标小区的情况，其中文献[12]考虑了不同用户与基站之间信道质量不同的因素，而本方案是在文献[12]的基础上，有别于只针对目标小区的情形，将其运用到所有小区，应用场景更大，提高整体的系统性能，所以仿真中将所提方案与随机导频分配方案和文献[12]中的导频分配方案对比其优劣性。系统的参数归纳为表1所示。

表1 仿真参数Tab. 1 Simulation parameters

图4为用户上行平均可达速率随平均发射功率的变化，其中，正交导频数S=8，天线数M=100。从图4中可以看出，随着平均发射功率ρ的不断增加，所考虑的导频分配方案的用户上行平均可达速率会逐渐增大，并且在平均功率值较小时，增长的速率比较快，而在平均功率值较大时，增长速率变得相对平稳。同时可以发现，与文献[12]中的导频分配方案相比，本文所提的导频分配方案的上行可达速率提升了近0.12 b/(s·Hz)，而相比随机导频分配方案，所提方案获得了较大的提升。

图4 用户上行平均可达速率随平均发射功率的变化Fig. 4 Change of average user uplink achievable rate with average transmit power

图5为用户上行可达速率的累积分布函数，其中正交导频数S=20，天线数M=128。从图5中可以看出，在正交导频数多于每小区内用户数时，所提的导频分配方案的系统性能优于随机导频分配方案和文献[12]中的导频分配方案，并且本文所提的方案与文献[12]中导频分配方案的性能间隔近似为0.28 b/(s·Hz)。

图6为用户上行信干噪比的累积分布函数，其中正交导频数S=12，天线数M=256。从图6中可以看出，虽然文献[12]中导频分配的性能高于随机分配导频方案，但是低于所提的导频分配方案，这是因为文献[12]中的导频方案是保证目标小区中用户分配导频资源的公平性，而所提的方案是考虑所有小区中导频复用的情况。因此本文所提方案是考虑不同小区用户间导频污染程度不同情况，集中式地分配导频给所有小区的用户，应用场景更加广泛。

图5 用户上行可达速率的累积分布函数Fig. 5 Cumulative distribution function of user’s uplink achievable rate

图6 用户上行信干噪比的累积分布函数Fig. 6 Cumulative distribution function of user’s uplink SINR

4 结语

本文针对大规模MIMO系统导频污染问题，提出了一种基于图着色的导频分配方案来提升系统的上行可达和速率，同时减小多小区间的导频污染。通过构建边权值干扰图，在传统图着色理论基础上，集中式地优先分配导频资源给受导频污染严重的用户。通过仿真结果可以发现，本方案在考虑不同小区用户间导频污染程度不同的情况下，提高了系统可达和速率，降低了用户间的干扰。由于小区协作的工作方式获取导频分配信息的开销大，在下一步的工作中，将考虑利用经济学的思想，提出基于博弈论的导频分配方案。

References)

[1] LARSSON E G, EDFORS O, TUFVESSON F, et al. Massive MIMO for next generation wireless systems [J]. IEEE Communications Magazine, 2014, 52(2): 186-195.

[2] RUSEK F, PERSSON D, LAU B K, et al. Scaling up opportunities and challenges with very large arrays [J]. IEEE Signal Process Magazine, 2013, 30(1): 40-60.

[3] 张中山,王兴,张成勇,等.大规模MIMO关键技术及应用[J].中国科学:信息科学,2015,45(9):1095-1110.(ZHANG Z S, WANG X, ZHANG C Y, et al. Massive MIMO technology and challenges [J]. SCIENTIA SINICA Informationis, 2015, 45(9): 1095-1110.)

[4] CHOI J, CHANCE Z, LOVE D J, et al. Noncoherent trellis coded quantization: a practical limited feedback technique for massive MIMO systems [J]. IEEE Transactions on Communications, 2013, 61(12): 5016-5029.

[5] OSSEIRAN A, BOCCARDI F, BRAUN V, et al. Scenarios for 5G mobile and wireless communications: the vision of the METIS project [J]. IEEE Communications Magazine, 2014, 52(5): 26-35.

[6] ELIJAH O, LEOW C Y, RAHMAN T A, et al. A comprehensive survey of pilot contamination in massive — 5G system [J]. IEEE Communications Surveys & Tutorials, 2016, 18(2): 905-923.

[7] UPADHYA K, VOROBYOV S A, VEHKAPERA M. Superimposed pilots are superior for mitigating pilot contamination in massive [J]. IEEE Transactions on Signal Processing, 2017, 65(11): 2917-2932.

[8] FERNANDES F, ASHIKHMIN A, MARZETTA T L. Inter-cell interference in noncooperative TDD large scale antenna systems [J]. IEEE Journal on Selected Areas in Communications. 2013, 31(2): 192-201.

[9] AKBAR N, YAN S H, YANG N, et al. Mitigating pilot contamination through location-aware pilot assignment in massive networks [C]// Proceedings of the 2016 IEEE Globecom Workshops. Piscataway, NJ: IEEE, 2016: 1-6.

[10] AHMADI H, FARHANG A, MARCHETTI N, et al. A game theoretic approach for pilot contamination avoidance in massive MIMO [J] IEEE Wireless Communications Letters, 2016, 5(1): 12-15.

[11] 方昕,张建锋,曹海燕,等.大规模系统中动态导频分配[J].电子与信息学报,2016,38(8):1901-1907.(FANG X, ZHANG J F, CAO H Y, et al. Dynamic pilot allocation in massive MIMO system[J]. Journal of Electronics & Information Technology, 2016, 38(8): 1901-1907.)

[12] ZHU X D, WANG Z C, DAI L L,et al. Smart pilot assignment for massive MIMO [J]. IEEE Communications Letters, 2015, 19(9): 1644-1647.

[13] ZHANG B, BAI Z Q, LI J H, et al. Artificial fish swarm algorithm based pilot allocation in massive MIMO system [C]// Proceedings of the 2016 16th International Symposium on Communications and Information Technologies. Piscataway, NJ: IEEE, 2016: 82-86.

[14] ZHOU Z, WANG D. Pilot scheduling based on water-filling algorithm in massive MIMO [C]// Proceedings of the 2016 6th International Conference on Electronics Information and Emergency Communication. Piscataway, NJ: 2016: 89-92.

[15] WANG P B, ZHAO C L, ZHANG Y J, et al. A novel pilot assignment approach for pilot decontaminating in massive MIMO systems [C]// Proceedings of the 2017 IEEE Wireless Communications and Networking Conference. Piscataway, NJ: IEEE, 2017: 1-6.

[16] ALKHALED M, ALSUSA E, HAMDI K A. Adaptive pilot allocation algorithm for pilot contamination mitigation in TDD massive MIMO systems [C]// Proceedings of the 2017 IEEE Wireless Communications and Networking Conference. Piscataway, NJ: IEEE, 2017: 1-6.

[17] UYGUNGELEN S, AUER G, BHARUCHA Z. Graph-based dynamic frequency reuse in femtocell networks [C]// Proceedings of the 2011 IEEE 73rd Vehicular Technology Conference. Piscataway, NJ: IEEE, 2011: 1-6.

This work is partially supported by the National Natural Science Foundation of China (11502039), the Science and Technology Research Project of Chongqing Municipal Education Commission (KJ1600424), the Doctoral Scientific Research Foundation of Chongqing University of Posts and Telecommunications (A2015- 41), the Youth Science Foundation of Chongqing University of Posts and Telecommunications (A2015- 62).

FANZifu, born in 1977, M. S., associate professor. His research interests include next generation network technology, management decision.

HUMin, born in 1992, M. S. candidate. Her research interests include massive multiple input multiple output.

LIYuening, born in 1991, M. S. candidate. His research interests include energy harvesting.

DynamicpilotallocationbasedongraphcoloringinmassiveMIMOsystems

FAN Zifu, HU Min*, LI Yuening

(InstituteofNextGenerationNetworkandApplicationTechnology,ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China)

Aiming at the pilot contamination problem in massive Multiple-Input Multiple-Out (MIMO) systems, a dynamic pilot allocation scheme based on graph coloring was proposed. To allocate pilot more reasonably and mitigate pilot contamination, firstly, an edge-weighted interference graph based on cooperation among cells was constructed to describe the strength of pilot contamination among multi-cell users, whereby two users in different cells were connected by a weighted edge. Then, based on the traditional graph coloring theory, pilot resources were allocated preferentially to users who were heavily polluted by the characteristics of different weighted edge for connected users. The theoretical analysis and simulation results show that, compared with existing distributed pilot allocation scheme, the proposed pilot allocation scheme can reduce the inter-cell interference and enhance the uplink achievable sum rate by considering pilot reuse of all cells and centralized pilot allocation mechanism based on graph coloring.

Massive Multiple-Input Multiple-Output(MIMO); pilot contamination; pilot allocation; graph coloring; achievable sum rate

2017- 06- 30;

2017- 09- 02。

国家自然科学基金资助项目(11502039);重庆市教委科学技术研究项目(KJ1600424);重庆邮电大学博士科研启动基金资助项目(A2015- 41);重庆邮电大学青年科学基金资助项目(A2015- 62)。

樊自甫(1977—)，男，安徽舒城人，副教授，硕士，主要研究方向：下一代网络技术、管理决策； 胡敏(1992—)，女，湖北潜江人，硕士研究生，主要研究方向：大规模多输入多输出； 李悦宁(1991—)，男，重庆人，硕士研究生，主要研究方向：能量采集。

1001- 9081(2017)12- 3356- 05

10.11772/j.issn.1001- 9081.2017.12.3356

(*通信作者电子邮箱humincqupt@163.com)

TN929.5

A