2. 泛网无线通信教育部重点实验室(北京邮电大学), 北京 100876
为了提高小区边缘用户的性能，提出了一种基于图论的考虑用户业务质量(QoS)的干扰协调方案.把无线资源分配问题映射成图论中的着色问题，同时考虑不同用户分到不同数量资源的场景，即一个点会需要不仅一种颜色的情况，引入了用户资源分配方式，并利用增强SEQ(sequential)着色算法解决该问题.仿真结果表明，提出的方案在不降低小区平均吞吐量的同时，能有效提升边缘用户的性能.
2. Key Laboratory of Universal Wireless Communication (Beijing University of Posts and Telecommunications
In order to improve the cell edge users' performance, a quality of service-aware inter-cell interference coordination method using a graph-based approach was proposed. Considering that the users may require a different quantity of physical resource blocks, the problem of assigning the radio resource to the users was modeled as the graph colouring. To solve the problem, an improve sequential colouring method for introducing resource allocation type was applied. Simulation shows that the proposed scheme could effectively increase the cell edge users' performance and the cell average throughout.
图论作为数学的一个分支，为很多问题提供了一种有效而系统的建模方式，很多问题都可以被转化为图论问题，然后用图论算法进行解决，其中通过将干扰协调技术和图论相结合来解决小区间的干扰问题，前人也做过一些研究[1-4].笔者提出了一个基于图论的干扰协调方案，与以往基于图论的算法不同的是，在着色时并没有给每个用户固定一定数量的资源或者追求使用最少数量的资源给所有用户着色，而是考虑了不同用户的业务质量(QoS, quality of service)需求，假设每个用户会分到不同数量的物理资源块(PRB, physical resource block)，并根据不同的资源分配方式进行调度.仿真结果显示提出的方案很好地改善了系统的性能.
1 系统模型这里考虑的是一个LTE多小区系统下行的场景，采用的是三扇区定向天线.端到端的链路损耗模型包括收发端的天线增益G、路径损耗L、阴影衰落损耗Sloss、人体损耗Bloss、天馈损耗Floss、穿透损耗Eloss，令链路损耗为Ploss，则有
|
(1) |
目标用户i在第n个子载波上的接收信号Y(n)如式(2) 所示：
|
(2) |
其中：X(j)(n)是用户j在第n个子载波上发送的符号，NI为干扰对象个数，Ptx(j)是一个资源元素(RE, resource element)的功率, Ploss(j)是第j个扇区到目标用户的链路损耗，参见式(1)，H(j)(n)为目标用户或者干扰用户在第n个子载波上的信道增益，U(i)(n)表示接收热噪声，模拟成0均值、方差为σ2的加性高斯白噪声.
2 干扰协调方案提出了一个基于图论着色的干扰协调方案.图论着色问题的基本思想是，在相连接的两个节点不能使用相同颜色这一前提下，使用尽可能少的颜色将图中所有的节点上完色.无线资源的分配问题显然可以建模成图论着色问题，把每个用户看成1个节点，把用户之间的干扰关系看成节点之间的边，如果两个用户之间干扰过大，则给这两个用户之间连上线，这样就可以建立1个干扰图，用户在进行资源分配时，就可以根据干扰图进行资源调度，进而避免干扰.不过考虑到实际情况，每个用户需要的PRB并不总是只有1个，而且每个用户对PRB有选择性的需求，因此，所提出的干扰协调方案的目的并不在于争取分配尽可能少的资源，而是考虑到了每个用户的QoS要求.整个方案主要包括干扰图建立、着色算法和考虑QoS的资源分配方法3部分.
2.1 干扰图建立对于用户u和v，若u和v之间存在干扰，则令用户之间的干扰eu, v=1，否则eu, v=0.小区间的干扰分为双向干扰和单向干扰，双向干扰表示两个用户彼此产生干扰，对于这类干扰要避免两个用户分到相同的资源，即eu, v=1；单向干扰表示其中一个用户对另一用户造成干扰，但反过来却没有产生干扰，这时候可令eu, v=0，同时对干扰用户进行功率控制.于是就可根据用户的位置信息，确定如下干扰情况：
1) 若u、v为同一个扇区内的用户，则eu, v=1；
2) 若u为扇区i中的用户，v为扇区j中的用户，分别计算用户u、v在两个扇区下的链路损耗Pu, i、Pu, j、Pv, i、Pv, j，链路损耗的计算参见式(1).
如果
|
(3) |
则eu, v=1；其中δth为阈值.
3) 其他情况下，eu, v=0，即忽略用户u和v之间的干扰.
2.2 着色算法着色的方法参考增强SEQ着色算法[5]，根据图中节点度由大到小的次序逐个给节点着色，如果有多个节点度相同的节点，则随机选择1个，也就是优先给干扰关系最复杂的用户分配资源.然后从该用户可用的资源集合中选择合适的资源分配给该用户，具体的分配方法参见第2.3节.每次分配完资源后，就把该点以及相连的边从图中去掉，然后重新计算未着色节点的度，继续给下一个用户分配资源，重复上述过程，直到所有用户都被遍历过.其中节点度表示与点相连的线的数目，用户的可用资源指从系统资源集合中去掉干扰用户的使用资源后剩下的资源.
2.3 考虑QoS的资源分配方法 2.3.1 用户所需PRB数的计算用户所需的PRB数目，根据用户各自的业务速率要求和当前时刻的无线信道质量(CQI, channel quality indicator)来确定，在t时刻用户n所需的PRB数目N[n][t]为
|
(4) |
其中：ηnt为用户n当前时刻对应的CQI编码效率，Mnt是用户n当前时刻对应的CQI调制阶数，Rnum表示一个PRB可用的RE数目，I是多天线发送数据时的层数，Bnt表示用户n在t时刻仍需发送的比特数，计算方法如下：
首先，设R为用户的速率要求，T(t)表示当前的传输时间间隔时刻，T(0) 表示用户业务发起时刻，Bnmac表示已正确发送的媒体接入控制层比特数，然后计算步骤如下.
① 计算B1=R(T(t)－T(0))－Bnmac；
② 如果B1≤0，Bnt=0；
③ 如果B1>0，则
a)计算α=lblbB1；
b)令B2=ceil(αR)；
c)如果B2<=B1，则Bnt=B2，否则Bnt=B1.
为防止Bnt值波动过大，导致计算的用户所需PRB数目过多，另一些用户分不到足够的PRB，步骤3对Bnt的值进行了控制.
2) 计算用户在子带上的优先级
确定用户在t时刻所需的PRB数之后，采用比例公平(PF, proportional fairness)算法的调度准则，计算用户在t时刻以及子带s上的优先级为M[t][s]，令一个子带的PRB数为4.
3) 根据资源分配方式的分配
在LTE协议[6]中定义了资源分配方式，下行有3种类型的资源分配方式，即Type0、Type1、Type2.下面结合资源分配方式和(2) 中计算的优先级给出具体的资源分配方法.
Type0：Type0以子带为单位分配资源.若4×(X-1) < N[n][t] < =4×X，从剩下的资源中，选出优先级最高的X个子带分给该用户，如果剩余子带数小于X，则将所有剩余子带分配给该用户.
Type1：Type1以PRB为单位分配资源.统计每个子带剩余资源中和优先级最大的N[n][t]个PRB，并将该N[n][t]个PRB分配给该用户.如果每个子带剩余资源数都小于N[n][t]，则统计所有剩余资源的和优先级，将和优先级最大的子带的剩余资源都分配给该用户.
Type2：从剩余资源中，统计出和优先级最大的连续N[n][t]个PRB，并将该N[n][t]个PRB分配给该用户.如果剩余资源中连续的PRB的个数m小于N[n][t]，则统计m个连续PRB的和优先级，并选出和优先级最高的连续资源段分给该用户.
根据用户的传输模式确定资源分配方式[6]，确定是Type2还是非Type2，对于未使用Type 2的用户，需要进一步根据用户所需的PRB个数判断是Type0还是Type1.如果用户所需的PRB个数小于1个子带的大小，则使用Type 1指示，否则使用Type 0指示.
资源分配方式的使用有助于对子带的完整利用，在确定了用户的资源分配方式后，即可按照各自的资源分配方式给用户分配PRB或者子带.
3 仿真结果和分析所提出的方案包括2个因素：基于图论着色的干扰协调和考虑用户QoS的资源分配方法.为了考察方案的有效性，仿真比较了4种方案下的不同性能，仿真方案包括：既考虑干扰协调又考虑QoS的资源分配(GraphPF)；只考虑QoS的资源分配(ReferPF)；只考虑干扰协调(SinglGraph)；经典的PF算法(SinglPF).其中SinglGraph和SinglPF假设每个用户只分配1个子带.
首先考察提出的GraphPF算法的性能与阈值δth的关系，阈值的大小会影响到小区边缘用户的性能，阈值取得过小，则在构建干扰图时，有些干扰大的用户将无法建立干扰关系，在给边缘用户分配资源时，会忽视这些强干扰用户的影响，进而影响到边缘用户的性能；若阈值取得过大，视作干扰源的用户过多，不仅算法计算的复杂度增加，而且在给用户分配资源时，可用资源的限制太大，可能会导致边缘用户分不到足够的资源，同样也会影响到边缘用户的性能，因此δth的取值是需要注意的.经过多次仿真分析，δth取值为20dB.因为取20dB时边缘用户的性能相对较高.
下面的仿真结果显示了4种方案下不同系统性能的比较. 图 1表示的是4种方案下用户信干燥比(SINR, signal to interference plus noise ratio)的累积分布函数(CDF, cumulative distribution function)曲线，SinglPF和SinglGraph方案每个用户只分配1个子带，降低了相邻小区间用户使用到相同频带的概率，边缘用户受到的干扰相对小的多，所以这两种方案的SINR性能较高，其中SinglGraph由于干扰本来就少，还采用了基于图论的干扰协调技术，因此它的SINR性能是最高的；ReferPF和GraphPF方案虽然采用了考虑QoS的资源分配方法，充分利用了资源，但也提高了相邻小区用户使用相同资源的概率，增加了干扰，不过，提出的方案GraphPF要远远优于ReferPF，这是因为GraphPF基于图论的着色原则，避免了小区边缘用户之间的干扰，提高了系统的性能，它的SINR性能和SinglPF差不多，边缘用户的SINR还略优于SinglPF, 这说明了干扰协调的有效性.
|
图 1 用户SINR累积分布函数 |
图 2表示的是不同方案下用户吞吐量的CDF曲线.由图中可以看到，在5%用户处，提出的方案GraphPF的性能要好于其他3种方案，与算法ReferPF相比，提高了约30%，不过中心用户的性能略低于ReferPF算法，从95%用户处的吞吐量看，大约降低了2.2%.原因在于，提出的算法给用户分配资源的顺序参照SEQ算法，根据干扰的复杂情况分配资源，也就是优先给边缘用户分配资源，然后才到中心用户，因为基于图论的算法对用户资源的分配限制较多，所以有可能会出现中心用户可用资源不足的情况.此外GraphPF和ReferPF的用户吞吐量性能普遍要高于SinglGraph和SinglPF，主要是因为前两种方案采用的调度方法考虑了用户QoS需求，并根据不同的资源分配方式分配资源，充分地利用了频带资源.
|
图 2 用户吞吐量累计分布函数 |
图 3表示的是不同方案下扇区的平均吞吐量，从图中可以看到，提出的基于图论算法的扇区平均吞吐量要高于其他方案，与ReferPF相比，提高了约7%，这要得益于边缘用户性能的提高，虽然中心用户的吞吐量有所下降，不过边缘用户的性能增益抵消了这部分的损失；与SinglPF和SinglGraph相比，扇区平均吞吐量提高了约31.66%和21.28%.
|
图 3 扇区平均吞吐量 |
提出了一个基于图论着色算法的干扰协调方案，通过增强SEQ着色算法确定用户的分配顺序，并应用了考虑用户QoS的资源分配方法，引入资源分配方式，用户可根据不同的资源分配方式分配资源，考察了不同用户在分到不同资源数目这一场景下的系统性能，结果表明，跟其他参考算法相比，提出的方案在提升边缘用户的性能的同时，还提高了小区平均吞吐量，获得了系统性能的改善.
| [1] | Yu-Jung C, Tao Zhifeng, Zhang Jinyun, et al. A Graph-based approach to multi-cell OFDMA downlink resource allocation[C]//Global Telecommunications Conference, IEEE GLOBECOM 2008. 2008: 1-6. |
| [2] | Chang Ry, Tao Zhifeng, Zhang Jinyun, et al. A graph approach to dynamic fractional frequency reuse (FFR) in Multi-Cell OFDMA networks[C]//Communications, 2009, ICC '09, IEEE International Conference on. 2009: 1-6. |
| [3] | Necker M C. Towards frequency reuse 1 cellular FDM/TDM systems[C]//Proceedings of the 9th ACM International Symposium on Modeling Analysis and Simulation of Wireless and Mobile Systems. 2006: 338-346. |
| [4] | Zhang Mingxi, Yuan Liu, Tao Meixia, et al. A graph approach for coordinated channel allocation in downlink multi-cell OFDMA networks[C]//Communication Technology and Application (ICCTA 2011), IET International Conference on. 2011: 238-242. |
| [5] | Werra D D. Heuristics for graph coloring[J]. Computational Graph Theory, 1989(3): 171–185. |
| [6] | 3GPP Std. TS36.213 V9.0.0. Evolved universal terrestrial radio access(E-UTRA); physical layer procedures[S]. 2010. |