多小区OFDMA系统基于罚函数-SA的资源分配算法

(华南理工大学 电子与信息学院，广州 510640)

1 引 言

无线通信技术的快速发展极大地改变了人们的生活，在有限的无线频谱资源条件下，要提供高速数据传输和服务更多用户，对现有技术是一项挑战。正交频分复用(Orthogonal Frequency Division Multiplexing,OFDM) 由于其特有的抗频率选择性衰落、抗符号间干扰的能力，能显著提高频谱利用率，被广泛应用于最新的通信系统中，如无线局域网(WLAN)、ADSL高速接入等。

在多用户系统中，多载波技术需要和其它多址技术结合以实现多用户复用。OFDMA系统将不同的子载波集分配给小区内各个用户。它不需要在用户之间设置保护频带，并且各个用户所使用的子载波也并不一定连续，而是允许以子载波为单位任意分配，因而具有比FDMA更高的灵活性。

目前，对OFDMA系统资源分配方面的研究大多只考虑单小区问题模型，A. Abrardo 等[1]虽然基于多小区进行研究，但是其初始分配仍是基于单小区进行。服务于多个基站的中央控制器根据现有反馈情况进行集中式资源分配，通过多分配算法将不符合多小区约束条件的载波从载波集中剔除后进行功率调整以满足吞吐量要求的方法来进行多小区资源分配。这样做虽然降低了算法复杂度，但是载波资源不能充分利用。

Ian C.Wong[2]等利用传统的两分法，将分配问题转化为子载波分配和功率分配两个子问题分别求解。这样将一个复杂的系统模型分割成两个相对简单的模型，这样的分配实际上只能得到一个次优的分配结果。

A. Gjendemsjφ[3-4]等在总功率一定的情况下，使得速率最大化的问题模型中证明采用离散功率的方法能够在不影响系统性能的前提下，极大地降低搜索复杂度。

针对多小区OFDMA系统资源分配问题，本文采用多小区多用户同时分配子载波和功率资源，在用户速率一定的情况下，尝试也将功率离散化，进行集中式资源分配以使问题模型达到最优。本文提出的问题模型，将某一约束条件转换为罚函数后，退化成NP难旅行商问题。因此本文进一步给出了改进的模拟退火算法进行求解，极大地提高了系统性能，简化了复杂度。

2 系统模型

本文所研究的OFDMA系统有一个中央控制器，对不同终端和基站之间的增益进行分析，统一管理多个小区的资源分配。考虑N个小区，小区集为C={1,2,…,K}，在小区k中有Uk个用户，用户集为Uk={1,2,…,nk}，载波集M={1,2,…,x}，离散功率集pm∈{q1,q2,…,qm}，因此我们定义一个新的的变量xi,j,m：

(1)

(2)

式中，pi表示第i个用户的传输功率值；Gi(j)表示将第j个载波分配给第i个用户后的信道增益，对于不在同一个小区使用分配相同子载波的用户对i而言也是属于干扰噪声；σ2表示其它所有的干扰和噪声。

在OFDMA系统中，业务的传输速率是通过分配一定数目的子载波和功率来保证的，由于系统的总吞吐量为所有实时业务的传输速率之和，因此针对实时业务的优化目标应该是保证传输速率要求的前提下最小化系统的发射功率，其目标函数为

(3)

为了减少小区内干扰，同一个小区内，每个载波只能分配给一个用户，可用式(4)表示：

(4)

对于某一给定的信噪比(SIR)，根据用户速率要求和信道条件状况，基站为每个用户设置了一个目标频谱效率η：

ηi=lb(1+SIRi)

(5)

此时就可以将每个用户分配的最大载波数ri与用户速率Ri相关联起来，如式(6)所示。若考虑公平性问题，只需令ri值相等：

ri=Ri/ηi

(6)

(7)

在实际应用中，为了尽量减少各个小区之间的干扰，对每个小区内所有用户功率具有一定的最大功率要求，如下所示：

(8)

综上所述，多小区OFDMA系统资源分配的优化目标是在满足速率约束以及最大功率要求的条件下，使所有用户的功率总和最小，如下所示：

(9)

(10)

(11)

(12)

(13)

(14)

xi,j,m∈{0,1}，∀i∈Uk,j∈M

(15)

式中，式(11)是个逻辑表达式，Q表示一个很大的数，表示如果载波没有分配给用户，它的功率值就一定为0。式(14)表示每个用户可以分配ri个子载波，每个子载波分配后，其功率也确定，是功率集中的某一值。由式(2)可知，式(12)是多小区分配必须要满足的信噪比要求，即分配必须满足式(16)所定义的信噪比要求：

(16)

式中，pi,m表示第i个用户分配了第m个离散功率，Gi(j)表示将第j个载波分配给第i个用户后的信道增益，不在同一个小区但却分配相同子载波j的用户对i而言也会产生干扰，B为信道带宽，N0为零均值热噪声功率谱密度。

3 罚函数-模拟退火算法

在式(9)～(15)定义的优化问题中，由于约束条件同时包含了其它小区的干扰情况，问题模型比一般的旅行商问题还要复杂许多。观察多小区模型可以发现，其相对于单小区而言，相当于增加了约束条件(12)。当罚函数充分大时，原约束非线性规划问题的全局极小点集与罚问题的全局极小点集相同[5]，因此我们可以采用将其变为单小区问题目标值的罚函数来进行简化。将约束问题放到目标函数之后，就可以使目标函数变为罚函数，此时目标函数变为

p(x,Mk)=f(x)+Mk{[min(0,g(x))]2}

(17)

(18)

式中，Mk是一个按一定步长变化的相对大的数。由于本文在数据很小的时候，也希望能够使得目标值尽量满足，所以式(17)的平方值在仿真过程中，依情况可以去掉。简化优化问题后，就可以采用本文所提出的改进的模拟退火算法来求解：

步骤1：初始值的选取：随机选择满足条件的一组值。具体方法为，确定不等式约束的下标集合，一个是已经满足的约束条件的集合Tk，另一个是尚未满足的约束条件的集合Sk。通过逐渐缩小Sk，增大Tk，最后使Tk包含所有约束条件，此时停止搜索。

步骤2：定解区域的确定。本文在仿真的过程中，就设置定解区域必须要满足约束条件，一旦不满足，就由于罚函数的存在，而使目标值很大，从而达到结果被摈弃的效果。

步骤3：内循环准则，包括新状态产生函数、新状态接受函数和内循环停止准则。为了确定新数据是否能够被接受，还需要选择一个适当的接受函数。

为了尽量简化算法模型，本文采用最简单的汉明距离的方法来产生新状态，若上一次产生的目标函数值比此次得出的目标函数值大，则接受新状态；新的目标函数值比较大，则根据Mentropolis法则以概率e(-Δf/tk)决定是否接受新解。一旦在此局部过程中，处于稳定状态，则跳出此次内循环。

本文中汉明距离并不是固定的，每次状态更新时，都会通过一个函数来判断采用的汉明距离。这样，整个状态产生函数简单而又不失一般性。

步骤4：外循环准则，包括退温函数和整个算法结束的准则。降温策略主要解决温度的下降速度问题。温度下降既不能太快也不能太慢，太快会导致解的质量下降，太慢会导致太长的运行时间，尤其对于问题规模较大时。

本文中退温函数采用常系数法，即tk+1=αtk,α∈(0,1)，其中α在0.8～0.99之间。该方法形式简单，而且对只要求寻找近似最优解的问题也足够有效，因而成为目前最常用的一种方法。α越趋近于1，意味着退温越慢，搜索次数越多，精确度也越高。一旦全局处于抽样稳定状态，结束整个算法，搜索到的能量最低态就是最优解。

原始的模拟退火算法流程可用图1表示，本文改进算法中的某些方法，如新状态产生的方法和退温函数等。在仿真过程中逐步调整参数，包括汉明距离、退温函数的常系数等，以达到最大化系统吞吐量的目的。

图1 模拟退火流程图Fig.1 Simulation annealing flow chart

4 仿真结果与分析

基于文中第2部分提出的系统模型，采用蒙特卡洛仿真方法来计算系统性能。为了更好地描述通用的蜂窝系统，我们采用文献[6]中的仿真参数。系统中总带宽为5 MHz，小区数为7，每个小区内用户数为16个，子载波总数为32，零均值热噪声功率谱密度N0为10-20。

为保证运算的收敛性，本文对内、外循环的最大搜索次数做了限定，一旦超过，则退出循环。内循环最大次数设置为500次，外循环最大次数设置为1 000次。

图2为本文提出的罚函数-模拟退火算法在各个不同的频谱效率下的收敛情况。由于运算过程是程序自动控制，所以迭代次数在频谱效率不同的情况下也会有所不同。

在搜索最优解的过程中，模拟退火除了可以接受优化解外，还用了一个随机接受准则(Metropolis)有限地接受恶化解，并使接受恶化解的概率慢慢趋于零，这使得算法有可能从局部最优解中跳出，尽可能找到全局最优解，并保证了算法的收敛性。此算法可用Markoff链的遍历理论来给它以数学上的描述。理论已证明：只要初始温度足够高，退火过程足够慢，模拟退火以概率1收敛到全局最优解。

图2 不同频谱效率下的迭代曲线Fig.2 Iteration numbers with different spectral efficiency

图3和图4比较了文献[1]中多分配算法及本文提出的算法两者的性能。离散功率的取值范围是本文仿真的关键，在(0，pmaxk)间进行等间隔取值和指数间隔取值，并进行对比。发现等间隔取值可以获得更好的吞吐量。本文中的仿真图都是等间隔功率取值与多分配进行对比的结果，图中所采用离散功率个数为32个。

图3 不同频谱效率下系统传输总功率Fig.3 Total power in different spectral efficiency

图4 不同频谱效率下平均用户吞吐量Fig.4 User throughput in different spectral efficiency

多分配算法是在单小区的基础上关闭某些载波并进行功率调整来达到满足公式(16)中所示的信噪比的要求，这必然造成载波资源的浪费。从图3可以看出，本文提出的算法计算出的系统总功率相比较于多分配算法有所增加，原因在于多分配算法是以牺牲部分资源为代价的，即被关闭的载波将不再被分配。本文采用的罚函数-SA算法充分利用载波资源，从图4可以看出，本文提出的罚函数模拟退火算法相对于多分配算法，吞吐量可以提高大约30%。

仿真参数调整过程中，在用户数为16的情况下，每小区内最大功率必须大于0.5 W，否则，多分配算法也无法得到分配结果。本文仿真考虑公平性原则，所以分配给每个用户的载波数是相同的。退温函数常系数α一般情况下取0.9，退温精度得到保证的同时也可以减少运算次数。仿真过程偶尔会出现曲线不太平滑的情况，通过采用多次运算取平均值的方法来达到平滑效果。

5 结 论

由于载波功率等无线资源是非常宝贵的，所以必须充分利用。归结起来，本文的目的就是在速率一定的情况下，对载波和功率资源进行分配，使系统总体功率达到最小。在对多个小区的功率和载波同时分配时，问题模型复杂性相对单小区大大提升。本文采用两个创新性的方法来简化多小区资源分配问题，一是通过功率离散化，二是通过引入罚函数，使得问题模型的求解可以采用改进的模拟退火算法。离散化的功率的设置范围、方法和个数是本仿真的重点。本文提出的罚函数改进模拟退火算法每用户平均吞吐量相对多分配提升大约30%的性能，功率离散化的优越性得到很大的体现，有很高的研究价值。多小区系统性能是当前无线通信研究的重点，所以我们后续的工作将是针对用户数不断增加来研究单位功率吞吐量的变化情况。

参考文献：

[1] Abrardo A,Alessandro A,Detti P,et al.Radio resource allocation problem for OFDMA cellular systems[J].Computer and Operations Research,2009,36 (5) :1572-1581.

[2] Wong C I,Shen Z,Evans L B,et al. A low complexity Algorithm for proportional resource allocation in OFDMA systems[C]//Proceedings of IEEE Workshop on Signal Processing Systems(SIPS04).[S.l.]:IEEE,2004:1-6.

[3] Gjendemsjφ A, Gesbert D,φien G E,et al.Optimal power allocation and scheduling for two cell capacity maximization[C]//Proceedings of 2006 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks.[S.l.]:IEEE,2006:1-6.

[4] Gjendemsjφ A,Gesbert D, φien E G,et al.Binary power control for sum rate maximization over multiple interfering links[J].IEEE Transactions on Wireless Communication, 2008,7(8):3164-3173.

[5] Fiacco V A,McCormick P G.Nonlinear programming:sequential unconstained minimization techniques[M].Mclean,Virginia:Research Analysis Corporation,1990.

[6] 3GPP TR25.814 V7.0.0,Physical layer aspects for evolved Universal Terrestrial Radio Access (UTRA)(Release7)[S].