孙 明，吴仁超，徐耀群

(1.齐齐哈尔大学计算机与控制工程学院，黑龙江齐齐哈尔161006;2.哈尔滨商业大学系统工程研究所，哈尔滨150028)

OFDM是下一代无线通信标准的物理层核心接入方案[1].OFDM资源分配算法的选择会对系统性能有很大的影响.近年来，设计高效的OFDM资源分配算法已成为了无线通信领域的一个研究热点.为了满足各个用户的QoS需求，需要考虑到各个用户的信道状况和总功率预算，并以最佳用户体验作为目标.文献[2]中证明将每个子载波分配给信道状况最佳的用户，同时采用注水方法对功率进行分配，可得到最大的系统速率和.Wong在文献[3]中提出将功率平分到每个子载波上的低复杂度次优解方案.对于较大小区的OFDM资源分配问题，Bohge推荐使用动态分配算法[4].Kelly在文献[5]中提出基于对数的效用函数，并且证明了使用对数函数能够达到比例公平.Wang在文献[6]中研究了在各态历经信道中下行OFDM系统的资源分配，提出了随机对偶梯度算法.在每个用户速率阈值的要求下，为了实现用户速率加权和的最大化，Wang采用传统的注水算法，在功率乘子与子载波分配之间进行大量的相互迭代，并同时对用户速率阈值乘子进行调整[6].由于在功率乘子与子载波分配大量的相互迭代中，功率乘子与子载波分配都不是最优的，因此会影响用户速率阈值乘子调整的准确性.另外，Wang的算法对于用户速率阈值乘子的调整也只限于增加不满足用户的乘子的数值，从而没有严格满足KKT最优性条件.

在各态历经信道下，本文首先提出一种快速准确地同时定位最优功率乘子与最优子载波分配的新的注水方法，避免了功率乘子与子载波分配的相互迭代对用户速率阈值乘子调整的影响.为了在满足用户的速率阈值的要求下实现用户速率加权和的最大化，本文采用粒子群算法[7]调整速率阈值乘子，严格依照KKT最优性条件精准地定位最优解.对5用户32子载波的各态历经信道的多用户OFDM下行传输进行了仿真，实验结果证明，本文算法所求的用户速率加权和高于Wang的随机对偶梯度算法.

1 问题模型及分析

考虑非实时业务中各态历经信道的OFDM下行传输，j={1，…，J)为用户集合，k={1，…，K}为子载波集合，子载波k的传输功率为pk，子载波的总传输功率为pT.在一个完整的OFDM周期内，每个用户可以使用一个或以上的子载波进行传输，但一个子载波只可以分配给一个用户.pj，k表示子载波k分配给用户j时的功率.假定用户j在子载波k上的信道增益与噪声功率的比值γj，k可以被基站完全接收，用户j在子载波k上的传输速率为cj，k(p)=log2(1+pj，kγj，k).考虑各态历经信道，用户 j的平均最大可达速率为，平均总传输功率为.在每个用户有不同速率阈值要求的非实时业务中，多用户OFDM资源分配问题可描述为:在满足以下两个条件下，最大化用户速率加权和.

1)平均总传输功率之和等于总传输功率要求pT;

该多用户OFDM资源分配问题的数学模型可描述为[6]:

其中:wj表示非实时业务中用户j的速率权重.对式(1)构建Lagrange函数:

当前子载波分配{j*1(λ)，…，j*K(λ)}下的最优功率乘子λ*满足注水函数最优性条件(λ*)]=pT.

从链路质量指标函数(3)中可以看出由当前功率乘子根据链路质量函数指标最优性条件可以直接计算得到当前子载波分配.但在注水函数(4)中无法根据注水函数最优性条件直接计算得到当前子载波分配下的最优功率乘子.为了确定最优子载波分配和对应的最优功率乘子，Wang采用传统的注水算法，对功率乘子进行数值搜索并在功率乘子与子载波分配之间进行大量的相互迭代，直到发现满足链路质量指标最优性条件和注水函数最优性条件的最优子载波分配以及与之对应的最优功率乘子.由于子载波分配和功率乘子的相互迭代影响用户速率乘子的调整，所以会间接影响用户速率乘子的KKT最优性条件的满足.

本文提出的新的注水方法，在面对任何子载波分配时，都可以直接计算得到当前子载波分配下的满足注水函数最优性条件的最优功率乘子，使得传统注水算法中子载波分配与功率乘子之间的大量相互迭代变成有限的精确的相互迭代.另外，由于子载波分配和与之对应的最优功率乘子之间相互迭代有着明确目标，所以可以在发现最优子载波分配和对应的最优功率乘子后展开对用户速率乘子调整.采用新的注水方法取代传统的注水算法，不仅可以降低子载波分配与功率乘子之间的相互迭代的计算量，还可避免由于非最优子载波和非最优功率乘子对用户速率乘子的调整而影响KKT最优性条件的满足.

2 新注水方法

新注水方法在面对不同的子载波分配方案时都可以快速地满足注水函数的功率完全分配.新注水方法不仅对瞬时的信道质量有效，同样适用于各态历经信道.在子载波分配完毕之后由小到大排序到注水门槛集合中.令1/λln2不断增大，使其在两个相邻的注水门槛组成注水门槛区间依次取值.具体如下:

对于瞬时的信道，在0到K之间确定I*使得pT(λ)的取值范围包含 pT.根据式(8)，由 I=I*，pT(λ)=pT，可以得出最优功率乘子.对于各态历经信道，将不同信道的所有注水门槛统一到一个总注水门槛集合里，这个集合中注水门槛有NK个.在0～NK之间确定I*使得 Eγ[pT(λ)]的取值范围包含 pT.根据式(6)，由 I=I*，Eγ[pT(λ)]=pT可以得出最优功率乘子

无论对于瞬时的信道还是各态历经信道，新的注水方法都保证所有子载波都具有相同的功率乘子，并且能对总功率在子载波中进行完全分配，即最优功率分配.

3 KKT最优性条件的分析

KKT最优性条件能够保证拉格朗日的最优性[7].对于速率阈值限制的Lagrange乘子u=0的情况，采用新注水方法可以得到在没有速率阈值限制下最大化用户速率加权和的用户速率c*=(c1*，…).令表示速率阈值限制.基于c*与的广义关系，在具有速率阈值限制的最大化速率加权和问题中，对速率阈值限制乘子和用户速率满足KKT最优性条件的分析如下:

3)若c*与之间没有广义不等的关系，就必须通过调整速率阈值乘子可以使用户速率与速率阈值乘子满足KKT最优性条件:若＞0则uj1＞0;若~cj2＞则 uj2=0，其中={c1，…，cJ}为满足KKT最优性条件的用户速率，j1称为不满足用户，j2称为满足用户，(j1，j2∈J).

从KKT最优性条件中可以看出，调节所有不满足用户的速率阈值乘子使它们的速率达到阈值并且在正向趋向阈值，并且将满足用户的速率阈值乘子保持为零.

从c*与的比较中挑选出所有不满足用户作为初始不满足用户集合，调整初始不满足用户集合中所有用户的速率阈值限制乘子，使得初始不满足用户集合中所有用户的速率达到阈值并且在正向趋向阈值.初始调整完毕后，由于对用户速率阈值乘子的调整会影响到其他用户的速率，所以一些原来满足用户有可能会变成不满足用户，这些用户是隐藏不满足用户，必须将新出现的隐藏不满足用户加入到不满足用户集合.对新的不满足用户集合中的所有用户再次进行上述的速率阈值限制乘子调整，直到不再出现隐藏不满足用户.对于一直满足要求的用户，速率阈值限制乘子始终保持为零.

4 粒子群搜索Lagrange乘子算法

在c*与之间没有广义不等的关系的情况下，本文通过粒子群搜索所有用户的速率阈值限制乘子以不断修正不满足用户集合，发现最优速率阈值限制乘子，使得用户速率与速率阈值限制乘子都满足KKT最优性条件.

粒子群算法是近年来被广泛关注的一种全局智能优化算法[8－9].在使用粒子群搜索用户的速率阈值限制乘子时，粒子群中的每个粒子的位置都是用户的速率阈值限制乘子决策空间s中的一个解，每个粒子都会根据自己和同伴的经验来调整自己的位置.

以用户的速率阈值限制乘子x为目标向量，在决策空间s中随机生成初始种群，种群规模为I.根据已知的不满足用户集合，规定决策空间s中所有不满足用户的速率阈值限制乘子的统一下限为零，统一上限为U，所有满足要求的用户的阈值乘子始终保持为零.

在t时刻，第i(i=1，…，I)个粒子的位置为xi(t)，飞行速度为vi(t)，它在飞行过程中本身到达过的最好位置为pbi(t)，所有粒子在飞行过程中到达的最好位置为gb(t).第t+1时刻，第i个粒子根据式(8)、(9)更新自己的速度与位置:

其中:ω为惯性权重，控制当前速度对下一刻速度的影响;c1和c2为学习因子;r1和r2是(0，1)上的随机数.

由于速率阈值乘子的可行解是非负数，所以粒子位置存在正向边界.粒子的最佳位置由适应度函数决定.第i个粒子在t时刻的适应度函数fi(t)如下:

其中:D为不满足用户的个数，对于不满足用户集合中的所有用户，ci，d(t)为第d个不满足用户的t时刻的速率，d为第d个不满足用户的速率阈值，wd为第d个不满足用户的速率权重.适应度函数的目的是满足所有不满足用户的速率超过速率阈值下使所有不满足用户的速率在正向趋向各自的阈值.所以粒子适应度函数值越小，代表着由这个粒子的位置对应的用户速率对KKT最优性条件的满足程度越高，粒子的位置越优.

在t时刻，第i个粒子的最好位置pbi(t)，所有粒子最好位置gb(t)，可由式(12)、(13)计算得到.

粒子群搜索Lagrange乘子的算法流程可描述为:

Step1求解无速率阈值的最优方案，发现初始不满足用户集合.令速率阈值限制的乘子集合u=0，根据新的注水方法得到在没有速率阈值限制下最大化用户速率加权和的用户速率c*=(c1*，…，若c*与之间没有广义不等的关系，则将无速率阈值限制的最大化速率加权和的最优解中的所有不满足用户作为初始不满足用户集合.

Step2利用粒子群算法搜索用户的速率阈值限制乘子.由不满足用户集合确定决策空间s，生成用户的速率阈值限制乘子的初始种群.根据新的注水方法得到该种群中每个粒子对应的用户速率，并计算出粒子的适应度函数，根据适应度函数，粒子更新自己的速度与位置，展开了在决策空间s中对最优位置的搜索.搜索完毕后，生成新的用户速率.

Step3发现完整的不满足用户集合，得到满足速率阈值的最优解.不断对比新生成的用户速率和速率阈值限制，完整不满足用户集合，保证所有用户的速率都超过速率阈值.根据完整的不满足用户集合，得到满足速率阈值限制下最大的用户速率加权和.

5 KKT最优性分析与比较

Wang的随机对偶梯度算法[6]原理上是次梯度算法，它同时对功率乘子与速率阈值乘子以及子载波分配进行迭代调整.该算法使速率阈值乘子和子载波分配按照链路质量指标函数最优性条件和注水函数最优性条件缓慢逼近于最优子载波分配和最优功率乘子;在此同时，增加不满足用户的速率阈值乘子，使其速率增长逼近各自对应的速率阈值，并且保持当前满足用户的功率阈值乘子不变.由于随机对偶梯度算法不能快速求解最优功率乘子，并且只能缓慢逼近最优功率乘子和最优子载波分配，因此会影响用户速率乘子对KKT最优性条件的满足.另外，随机对偶梯度算法只是使每个用户的速率达到阈值，缺乏使其在正向趋向阈值的整体调节措施.由上述可知，随机对偶梯度算法在真正意义上不满足KKT最优性条件.

根据本文提出的新注水方法可以直接计算得到当前子载波分配下的最优功率乘子，确定了子载波分配与功率乘子之间的相互迭代的目标，从而避免了非最优功率乘子和非最优子载波分配对用户速率阈值乘子搜索的影响.另外，粒子群搜索Lagrange乘子算法可以使不满足用户速率阈值乘子的调整具有了整体性，更加符合KKT最优性条件.

6 仿真实验

假设一个5用户OFDM下行传输系统的频选无线各态历经信道，总带宽为1MHz，有32个子载波，噪声能量密度为10－8，包括了2个独立生成的信道，用户的信道增益服从Rayleigh分布，信道增益期望为Eγ=(0.3，0.7).在该5用户OFDM下行传输，用户数J=5，子载波数N=32，各态历经信中总注水门槛数NK=64.在每个OFDM周期中的传输速率权重 w=(25，25，20，15，15)，速率阈值为=(40，40，25，10，10)，总功率限制为 1Wett.

首先利用新注水方法结合粒子群搜索Lagrange乘子算法对用户速率加权和进行最大化.取粒子群参数ω=1，r1=r2=1.8，，决策空间 s中不满足用户的速率阈值限制乘子的统一上限U=采用新注水方法结合粒子群搜索 Lagrange乘子算法求得的结果，如表1所示.

表1 新注水方法结合粒子群搜索Lagrange乘子算法的求解结果

然后，采用文献[6]的随机对偶梯度算法对用户速率加权和进行最大化，得到的满足速率阈值限制下的最大用户速率加权和，如表2所示.

表2 随机对偶梯度算法求解结果

在表1、2中，c*是在没有速率阈值限制下最大化用户速率加权和的用户速率，~c则是由基于粒子群搜索速率阈值Lagrange乘子得出的是满足速率阈值限制下最大的用户速率加权和的用户速率.wc*是在没有速率阈值限制下最大化用户速率加权和，~wc则是满足速率阈值限制下最大的用户速率加权和.在仿真过程中，用户4和用户5是初始阶段的不满足用户，用户3则是隐藏不满足用户，用户3、用户4和用户5组成了完整不满足用户.

在表1中，新注水方法结合粒子群搜索Lagrange乘子算法将用户3、用户4和用户5组成了完整不满足用户集合，并保持用户1和用户2等满足用户的速率阈值乘子始终为零，通过粒子群算法使完整不满足用户集合的用户速率达到并且从正向逼近其速率阈值，最终得到5个用户的速率加权和总和为5.503 9×103.在表2中，随机对偶梯度算法使用户3、用户4以及用户5的速率达到其阈值但没有从正向逼近其速率阈值，最终得到5个用户的速率加权和总和为5.499 5×103.通过以上分析比较不难看出，新注水方法结合粒子群搜索Lagrange乘子算法得到的速率加权总和高于随机对偶梯度算法.

7 结语

在各态历经信道下，本文提出了一种快速准确地定位最优子载波分配与最优功率乘子的新注水方法，并使用新注水方法结合粒子群算法搜索Lagrange乘子并最大化用户速率加权和.与随机对偶梯度算法相比，本算法能更好地满足KKT最优性条件.仿真结果证明了本算法能够在满足速率阈值的限制下得到更大的用户速率加权和.

[1]3rd Generation Partnership Project，Technical Specification Group Radio Access Network;Physical layer aspects for evolved Universal Terrestrial Radio Access(UTRA)，3GPP Std[S].TR 25.814 v.7.0.0，2006.

[2]YIN H，LIU H.An efficient multiuser loading algorithm for OFDM－based broadband wireless systems[C]//San Francisco:Global Telecommunications Conference，2000.103 － 107.

[3]WONG I C，SHEN Z，B L EVANS，et al.A low complexity algorithm for proportional resource allocation in OFDMA systems[C]//Proc IEEE Workshop on Signal Processing Systems，2004.1－6.

[4]BOHGE M，GROSS J，WOLISZ A.The potential of dynamic power and sub－carrier assignments in multi－user OFDM－FDMA cells[C]//Proc.Global Telecommunications Conference，St.Louis，MO，2005(5):2932 －2936.

[5]KELLY F P.Charging and rate control for elastic traffic [J].Europe Trans.on Telecommun，1997(8):33 －37.

[6]WANG X，GIANNAKIS G B.Resource allocation for wireless multiuser OFDM networks[J].IEEE Trans.on Information Theory，2011，57(7):4359－4372.

[7]任 新.基于进化算法和 KKT条件的正交频多用技术(OFDM)资源优化分配方案设计[J].科学技术与工程，2013，36(13):10828－10833.

[8]高春涛.粒子群优化算法及其应用[J].哈尔滨商业大学学报:自然科学版，2010，26(4):442－445.

[9]徐耀群，王长举.一种万有引力优化算法及其收敛性分析[J].哈尔滨商业大学学报:自然科学版，2013，29(1):63－67.