基于改进智能水滴算法的多用户OFDMA系统资源分配*

刘紫燕，毛 攀，吴俊熊，冯 丽

(1.贵州大学 大数据与信息工程学院，贵阳 550025;2.国网重庆市电力公司，重庆 400014)

基于改进智能水滴算法的多用户OFDMA系统资源分配*

刘紫燕*1，毛 攀1，吴俊熊1，冯 丽2

(1.贵州大学 大数据与信息工程学院，贵阳 550025;2.国网重庆市电力公司，重庆 400014)

在正交频分多址(OFDMA)系统中，合理的资源分配对于提升系统的性能具有重要的意义。针对多用户OFDMA系统，对最大化系统容量为目标的资源分配算法进行研究，提出了一种基于智能水滴算法的无向全连通图资源分配模型，以无向全连通图的顶点集和边集来描述用户与子载波之间的匹配关系。在此基础上，进一步对智能水滴算法进行改进。仿真结果表明，在满足用户比例公平性的条件下，与蚁群算法相比，基于改进智能水滴算法的全连通图分配方案能够提高2.17%～4.91%的系统速率，同时具有更快的收敛速度，提高了系统性能。

正交频分多址；多用户；子载波分配；智能水滴算法；比例公平性

1 引 言

OFDMA技术，也被称为多用户正交频分复用(Orthogonal Frequency Division Multiplexing,OFDM)技术，是OFDM技术的拓展，是第四代无线通信多址接入的解决方案。OFDMA以其高数据速率接入系统特点而成为主流的多址接入技术，如IEEE802.11a/g的无线局域网接入系统、IEEE802.16a的固定无线宽带接入系统[1]。在传统的OFDM中，所有的子载波只供给单用户使用[2]，而OFDMA技术则是在同一时间将子载波分配给不同用户，使得多个用户能够同时传输数据，与单用户系统相比，大大提升了系统整体频谱利用率。

OFDMA系统中不同用户的子载波与功率分配问题一直是国内学者的研究热点。文献[3]提出了一种边缘自适应的迭代算法，在用户传输速率、误码率一定的条件下，使总的传输功率最小化。文献[4]提出了一种比特自适应的分配算法，在系统内总功率、误码率一定的条件下，使用户传输速率最大化。为了最大化系统总容量，该算法将子载波分配给最大增益的用户。文献[5]研究了D2D通信中的资源分配问题，提出了一种资源分配与功率控制相结合的方法，以提高系统的通信质量。但是上述文献均未考虑用户的比例公平性问题。文献[6]考虑了用户比例公平性，这是一种非常有用的服务等级分级，能够对不同需求的用户进行灵活的资源分配，在满足用户比例公平性条件下，使得系统的传输速率最大化，但是该文献提出的算法是一种线性非迭代的算法，为降低复杂度而牺牲了系统性能，分配结果并不理想。本文考虑了文献[6]的资源分配模型，利用改进的智能水滴算法，优化系统资源。

本文将智能水滴算法引入到OFDMA系统中，在考虑用户比例公平性条件下，提出了基于智能水滴算法的全连通图资源分配模型；在此基础上，对智能水滴算法进行改进；以用户传输速率为优化目标，利用改进智能水滴算法的优势，实现系统资源对不同用户的灵活分配，提升系统性能。该算法不受优化目标函数特性影响，能够实现快速寻优，算法简单，收敛速度快。

2 系统模型

考虑一个具有K个用户、N个子载波的OFDMA系统，假设每个用户都能获得完全的信道状态信息(Channel State Information,CSI)，每个子载波只分配给唯一用户。N个子载波由系统分配给K个用户，用户k(1≤k≤K)在子载波n(1≤n≤N)上分配到的功率为Pk,n。根据香农公式，可以计算用户k在子信道n上的信道容量rk,n：

(1)

式中：Γ=-ln(5BER)/1.6，Hk,n为用户k在子载波n上的信噪比。

系统容量最大化是指在满足系统总发射功率、误码率一定的条件下，通过对子载波、功率进行分配来达到最大化系统总容量。由于每个子载波只能分配给唯一用户，所以，引入子载波分配指标系数

(2)

根据公式(1)，为达到系统容量最大化的资源分配算法的目标函数及其约束条件可以表示为

(3)

(4)

3 改进智能水滴算法的资源分配

3.1 智能水滴

智能水滴(Intelligent Water Drops,IWD)是2007年由Hamed Shah-Hosseini提出的，将自然界水滴的流动过程抽象成数学模型[7]。智能水滴具有两项基本属性：水滴所携带的泥土量soil(IWD)和水滴流动速度velocity(IWD)。水滴从位置i移动到位置j的过程中，其速度增量Δvelocity(IWD)是与位置i到位置j之间路径上泥土量soil(i,j)非线性相关，定义为

(5)

式中：soil(i,j)表示位置i到位置j之间路径上泥土量。在智能水滴算法开始之前，将所有路径泥土量初始化为Intsoil,av、bv、cv是用户定义的速度更新参数，通常取为av=1,bv=0.01,cv=1。

从位置i到位置j的过程中，水滴携带走的泥土量等于路径中所减少的泥土量，即

Δsoil(IWD)=Δsoil(i,j)。

(6)

水滴中的泥土增量Δsoil(IWD)与水滴从当前位置i移动到下一位置j所需的时间time(i,j)呈非线性反相关，其表达式为

(7)

式中：as、bs、cs是用户定义的泥土量更新参数，通常取as=1,bs=0.01,cs=1；

(8)

为水滴以velocity(IWD)从位置i到位置j的时间[8]，其中引入了反向启发函数(Heuristie undesirability,HUD)，HUD(i,j) 表示位置i与位置j之间的距离，在实际优化问题中则可表示优化目标适应度函数的倒数。

水滴经过之后，位置i到位置j间路径中所剩余的泥土量根据智能水滴所带走的泥土量Δsoil(i,j)来更新：

(9)

在下一次移动之前，水滴所携带的泥土量soil(IWD)按照公式(10)来更新：

soil(IWD)=soil(IWD)+Δsoil(IWD)。

(10)

所有水滴在每一次迭代结束后，选出一条最优的路径，以该路径的泥土量soil(i,j)为标准，将所有路径的泥土量依据式(11)进行全局更新：

(11)

式中：ρIWD是用户定义的泥土量全局更新参数，NIWD表示每次参与迭代的智能水滴的数目。

智能水滴在面对多条可选路径时，会更倾向选择泥土量较少的路径。p(i,j)表示智能水滴处于位置i时，以j作为下一位置的概率。其计算公式如下：

(12)

式中：L表示所有位置节点的个数；ε一般取0.001，防止函数f的分母为0；函数g(.)确保所有路径之间的泥土量为正数，g(.)表达式为

(13)

函数min(soil(i,j))表示水滴从当前位置i到所有下一位置节点的路径泥土量的最小值。

3.2 智能水滴算法改进方案

3.2.1 边缘选择

由于所有路径泥土量都初始化为Intsoil，导致在算法迭代初期，按照式(12)选择下一节点位置时，所有可选节点的概率相同，水滴将会随机选择下一位置节点。然而这种随机性会对下一次迭代产生影响，多次迭代后导致某一条路径泥土量显著减少，使得水滴陷入此条路径，算法陷入局部最优。针对这一缺陷，本文在式(12)的基础上增加一个启发条件：

(14)

式中：η(i,j)=1/HUD(i,j)表示优化目标函数的启发因子，在水滴移动过程中表示距离的倒数；参数α表示水滴在选择下一位置节点时，该路径上泥土量soil(i,j)在搜索过程中的重要程度；参数β则表示水滴在选择下一位置节点时，优化目标函数的启发因子在搜索过程中的重要程度。

3.2.2 路径泥土量限制

随着迭代次数的增加，当水滴频繁通过某一条路径时，该路径的泥土量会比其他路径上的泥土量少很多，导致水滴无法跳出当前路径而提前收敛。针对这一缺陷，本文参照文献[9]所提出的最大最小蚂蚁系统(Max-Min Ant System,MMAS)对路径上泥土量作最小约束：

soil(i,j)≥Smin,∀i,j∈{1,2,,…,NIWD},i≠j。

(15)

式中：Smin为路径泥土量的最小值，NIWD为智能水滴的数目。Smin的取值按照文献[10]中的渐进估计方法来计算：

(16)

式中：Pbest为用户定义的限定参数。在每一次通过式(9)～(10)对路径泥土量更新时，必须确保泥土量满足式(15)的最小泥土量限制条件。若有soil(i,j)

3.3 改进智能水滴的资源分配

3.3.1 无向全连通图模型

智能水滴算法的模型具有路径选择特性，一般用来解决路由选择、路径规划等难题[11]，而式(3)旨在解决一定约束条件下，系统资源的最佳组合方案。为了描述这个问题，我们将该资源分配问题抽象成一个无向的全连通图，智能水滴在图中各顶点之间的遍历路径，即是系统资源的分配结果。

在该无向全连通图中，K个顶点代表K个用户，顶点之间相连接的N条边代表N个子载波。表达式(i,j)n用来描述用户与子载波之间的对应关系以及分配顺序，表示子载波n分配给用户i，用户j等待分配。图1所示为3个用户、N个子载波的全连通图模型，其中U1、U2、U3三个顶点分别代表3个用户，节点之间连接的N条无向边代表可供分配的N个子载波。

图1 子载波分配全连通模型图Fig.1 Full connection graph subcarrier allocation scheme

水滴在连通图中遍历各顶点的路径选择方案，即是子载波的分配方案。图2是图1在确定用户分配顺序的前提下的展开图形，其中Ukn表示子载波n分配给用户k。值得注意的是，图2只是一种可能的分配顺序。由于不同的分配顺序会产生不同的结果，在实际的计算中需要由智能水滴根据路径自主选择用户的分配顺序，以达到全局优化的目的。

图2 全连通图的路径表示Fig.2 Path representation of full connection graph

3.3.2 子载波分配流程

OFDMA系统资源分配的基本流程为：通过改进的智能水滴算法完成系统子载波的分配，然后在此子载波分配方案的基础上利用迭代注水算法完成系统的功率分配。具体步骤如下：

Step 1 初始化soil(i,j)=Intsoil，水滴数目NIWD=K，循环次数Iter=Itermax。

Step 2 将NIWD个水滴置于图1所示的连通图模型顶点，初始化水滴前进的速度、泥土量参数。

Step 3-1 初始化禁忌列表，将所有子载波置于可分配状态。

Step 3-2 结合禁忌表，按照式(3)、(13)、(14)计算水滴在当前位置i时所有可供选择的子载波的概率，同时选择概率最大的子载波n作为该用户的分配方案。

Step 3-3 将子载波n置于禁忌表并更新，表示该子载波已被用户占用。

Step 3-4 按照式(9)、(15)更新水滴经过子载波n的泥土量。

Step 3-5 按照式(10)更新水滴自身含有的泥土量。

Step 3-6 水滴经过子载波n到达下一节点j，置i=j。

Step 3-7 重复Step 3-2～Step 3-6，直至水滴遍历所有节点，单个水滴的循环结束。

Step 4 当前迭代结束，计算NIWD个水滴中最优方案，按照式(11)、(15)对所有子载波的泥土量进行全局更新。

Step 5 若满足Iter

4 仿真结果与分析

为了验证本文所提出的资源分配算法对多用户OFDMA系统性能的改善，下面在MATLAB 2014b平台上进行仿真分析。仿真系统的信道模型采用具有6条多径的频率选择性瑞利信道，其最大时延拓展为5 μs，最大多普勒频移为30 Hz。信道状态信息更新周期为0.5 ms，系统总发射功率为1 W，总带宽为8 MHz，总子载波数为64，子信道的平均信噪比为38 dB，系统用户数目从2～18间距为2取10组，对于不同用户的公平性，设置权重为1、2、4，其分布比例为0.5、0.3、0.2[12]。智能水滴算法参数设置如表1所示。

表1 智能水滴算法参数设置Tab.1 Values of intelligent water drops algorithm

为了验证本文算法的性能，本文仿真对比了其他两种资源分配方案：文献[6]中的线性非迭代算法分配方案和蚁群算法(Ant Colony Optimization,ACO)分配方案。

图3比较了改进的智能水滴算法(Imp-IWD)、传统智能水滴算法(IWD)、蚁群算法(Ant)、线性非迭代算法(Linear)对多用户OFDMA系通过进行资源分配时，系统总传输速率。可以看出，改进智能水滴算法优于其他算法，能够提高2.17%～4.91%的系统传输速率；传统智能水滴算法易陷入局部最优而导致结果不理想，这种劣势在用户数目较多的时候尤为显著。同时可以看出，系统吞吐量随用户数增加而提高，这是得益于用户增益的影响，在实际通信系统中提高系统容量的效果更显著。

图3 不同用户数目下系统的传输速率Fig.3 Transmission rate of system with different number of users

图4比较了当系统用户数目为10的时候，单个用户的频谱效率。可以看出，与其他算法相比，改进后的智能水滴算法能够获得较高的频谱效率。

图4 不同用户的频谱效率Fig.4 Spectrum efficiency of different users

图5比较了系统用户为18时，不同算法在迭代寻优中的收敛过程。可以看出，改进后的智能水滴算法具有寻优效果好、速度快的优点，这是由于本文在传统智能水滴的基础上做了路劲路径选择以及泥土更新上的改进；传统智能水滴陷入局部最优后，无法跳出循环，导致收敛于一个较优解。

图5 不同算法的收敛性Fig.5 Convergence of different algorithms

图6比较了不同算法的CPU运行时间，可以看出，3种群智能算法中，改进的智能水滴算法具有一定的优势，这是由于算法本身具有较低复杂的特性所决定的。而文献[5]中的线性非迭代算法占用了较少的CPU资源，其代价是在一定程度上牺牲了系统的性能。

图6 不同算法的平均CPU时间对比Fig.6 Average CPU time of different algorithms

图7比较了用户数为18时，不同分配算法对用户比例公平性的归一化结果。其中“Weight”表示不同用户的标准权重，柱状图中不同算法对其的逼近程度表示该算法对比例公平性的满足程度。可以看出，改进的智能水滴算法能够较好满足用户比例公平性条件。

图7 不同算法满足用户的比例公平性Fig.7 Proportional fairness of different algorithms

5 结束语

本文针对多用户OFDMA系统，研究了在比例公平条件下最大化用户传输速率为目标的资源分配问题。根据信道具有频率选择性衰落的特性，提出了基于改进智能水滴算法的资源分配模型。该模型将系统中的用户以及子载波抽象为全连通图中的顶点集与边集，同时用改进智能水滴算法实现模型的求解。仿真结果表明，与线性非迭代算法、蚁群算法分配方案相比，本文提出的改进智能水滴算法资源分配方案更优，收敛速度更快。该算法为多用户OFDMA系统的资源分配提供了一种优化解决方案。

文中的资源分配是分为两个独立的阶段，即先进行子载波分配，然后依据此分配结果再用注水算法进行功率分配。进一步可研究子载波与功率的联合分配问题，建立一个子载波与功率同时优化求解的资源分配模型。

[1] COOKLEV T. Air interface for fixed broadband wireless access systems[M]// Wireless communication standards:a study of IEEE 802.11TM,802.15TM,and 802.16TM.New York:John Wiley & Sons,Inc.,2011:225-333.

[2] 叶兰兰. 多用户OFDMA系统中资源分配算法研究[D].杭州：中国计量学院,2014. YE Lanlan.The research of resource allocation algorithm in multi-user OFDMA system[D].Hangzhou:China Jiliang University,2014.(in Chinese)

[3] WONG C Y,CHENG R S,LATAIEF K B,et al. Multiuser OFDM with adaptive subcarrier,bit,and power allocation[J].IEEE Journal on Selected Areas in Communications,1999,17(10):1747-1758.

[4] JANG J,LEE K B.Transmit power adaptation for multiuser OFDM systems[J].IEEE Journal on Selected Areas in Communications,2003,21(2):171-178.

[5] 王蓉,江帆,许腾驹,等. D2D通信中一种资源分配与功率控制结合的方案[J].电讯技术,2016,56(3):295-301. WANG Rong,JIANG Fan,XU Tengju,et al.A joint method of resource allocation and power control for device - to - device(D2D) communication[J].Telecommunication Engineering,2016,56(3):295- 301.(in Chinese)

[6] WONG I C,SHEN Z,EVANS B L,et al. A low complexity algorithm for proportional resource allocation in OFDMA systems[C]//Proceedings of 2004 IEEE Workshop on Signal Processing Systems(SIPS 2004).Austin,TX:IEEE,2004:1-6.

[7] SHAH-HOSSEINI H.Problem solving by intelligent water drops[C]//Proceedings of 2007 IEEE Congress on Evolutionary Computation.Singapore:IEEE,2007:3226-3231.

[8] XING B,GAO W J. Intelligent water drops algorithm[M]// Innovative computational intelligence:a rough guide to 134 clever algorithms.Heidelberg,Berlin:Springer International Publishing,2014:365-373.

[9] STUTZLE T,HOOS H. Max-min ant system[J].Future Generation Computer Systems,2015,16:889-914.

[10] DIEU P D. Asymptotical estimation of some characteristics of finite graphs[J].Molecular Ecology,2015,24(7):1596-1610.

[11] 马竹根. 智能水滴算法研究[J].计算机与数字工程,2014,42(6):964-968. MA Zhugen.Summary on intelligent water drops algorithm[J].Computer and Digital Engineering,2014,42(6):964-968.(in Chinese)

[12] WU Q,CHEN W,TAO M,et al. Resource allocation for joint transmitter and receiver energy efficiency maximization in downlink OFDMA systems[J].IEEE Transactions on Communications,2015,63(2):416-430.

Resource Allocation with Improved Intelligent Water Drops Algorithm in Multi-user OFDMA System

LIU Ziyan1,MAO Pan1,WU Junxiong1,FENG Li2
(1.College of Big Data and Information Engineering,Guizhou University,Guiyang 550025,China;2.State Grid Chongqing Electric Power Company,Chongqing 400014,China)

Reasonable resource allocation for orthogonal frequency division multiple access(OFDMA) systems plays an important role in enhancing system performance.For a multi-user OFDMA system,the resource allocation algorithm with maximizing system capacity as target is researched deeply. And then,a resource allocation model of undirected full connection graph on intelligent drops algorithm is proposed,and the matching relationship can be expressed through vertices and edges sets of undirected full connection graph. Finally,the intelligent water drops algorithm is further improved. The simulation results indicate that under the condition of meeting user proportion fairness,compared with ant colony algorithm,the proposed full connection graph resource allocation scheme based on improved intelligent water drops algorithm can increase system rate of 2.17%～4.91%.At the same time,it is in possession of faster convergence speed and enhances system performance.

orthogonal frequency division multiple access(OFDMA);multi-user;subcarrier allocation;intelligent water drops algorithm;proportional fairness

2016-06-27；

2016-09-21 Received date:2016-06-27；Revised date：2016-09-21

国家自然科学基金资助项目(61263005)

10.3969/j.issn.1001-893x.2017.02.007

刘紫燕，毛攀，吴俊熊,等.基于改进智能水滴算法的多用户OFDMA系统资源分配[J].电讯技术，2017,57(2):161-166.[LIU Ziyan,MAO Pan,WU Junxiong,et al.Resource allocation with improved intelligent water drops algorithm in multi-user OFDMA system[J].Telecommunication Engineering,2017,57(2):161-166.]

TN929.5

A

1001-893X(2017)02-0161-06

刘紫燕(1977—)，女，贵州都匀人，2000年于贵州大学获硕士学位，现为副教授、硕士生导师，主要研究方向为无线通信、嵌入式通信、下一代通信系统；

Email:leizy@sina.com

毛 攀(1991—)，男，湖北黄冈人，2014年于贵州大学获学士学位，现为硕士研究生，主要研究方向为协作通信技术；

Email:comm539@126.com

吴俊熊(1991—)，男，贵州遵义人,2014年于武汉理工大学获学士学位，现为硕士研究生，主要研究方向为图像处理；

冯 丽(1975—)，女，贵州贵阳人，2005年于浙江大学获博士学位，现为高级工程师，主要研究方向为智能控制。

*通信作者：leizy@sina.com Corresponding author：leizy@sina.com