一种改进的多用户OFDM系统跨层分配优化算法

2016-12-01潘亚芹张丽张士兵

电信科学 2016年8期

关键词：多用户资源分配搜索算法

潘亚芹，张丽，张士兵

（南通大学电子信息学院，江苏南通 226001）

一种改进的多用户OFDM系统跨层分配优化算法

潘亚芹，张丽，张士兵

（南通大学电子信息学院，江苏南通 226001）

提出了一种多用户正交频分复用系统的跨层资源分配模型，结合了物理层中信道状态和媒体接入控制层中用户的队列信息，能更好地满足用户的服务质量要求。改进的混合优化算法结合了遗传算法与禁忌搜索算法的优点，并且对遗传算法的交叉因子进行改进，提高了全局搜索能力，能够更好地收敛于全局最优值，这样能更好地解决跨层资源分配问题。仿真结果表明，在此模型下利用改进的混合算法能有效地提高系统吞吐量，减小用户的平均时延，提高服务质量。

OFDM；跨层；资源分配；混合算法

1 引言

随着无线通信技术的发展，不断扩展的业务种类要求数据速率、带宽和 QoS（quality of service，服务质量）不断地增长。但是，由于无线信道存在着严重的多径衰落，这就在一定程度上限制了数据传输速率和用户QoS的提高。由于OFDM（orthogonal frequency division multiplexing，正交频分复用）技术具有高速传输的速率、抗多径衰落能力强以及抑制 ISI（inter symbol interference，符号间干扰）的优点，因此OFDM技术被看作无线通信系统中的关键技术。多用户OFDM系统是基于OFDM技术发展的，多用户OFDM系统把资源分配的方法分为静态资源分配方法和动态资源分配方法。静态资源分配方法是把固定的资源分配给不同的用户，而动态资源分配方法是根据各个用户自身的信道状态，自适应地把资源分配给用户，这样能更好地满足用户的要求，也能够使有限的资源得到充分的利用。

随着无线通信技术的快速发展，对传统分层结构的资源分配已经不能满足不同用户、不同业务以及高QoS的要求，还会因为资源分配时不进行变通而导致资源利用率低［1，2］。针对子载波、比特以及功率的分配采用的是自适应分配算法［3，4］，这种算法主要是在物理层上，首先假设一个确定的业务到达率，这就不能正确地反映出MAC（media access control，媒体接入控制）层实时队列的特征，而在实际过程中，数据和业务的到达都具有突发性和随机性。MAC层资源进行分组调度时设定物理信道是静态的，并且是没有差错的［5］，又因为无线信道的特性是时变、移动以及高误码率。因此，在进行无线资源分配时，仅仅考虑用户某种特定的需求而忽视无线信道的特点是很难满足用户需求的。相应地，只有在同时考虑用户的和无线信道的特性时才能使用户的需求得到最大的满足。所以，在无线通信中，跨层设计变得越来越重要。

跨层设计是建立在传统的分层结构上的，并不改变原有的分层结构，而是模糊化层与层之间的界限，把原来各层上相对独立的参数进行融合，在系统整体的约束条件下进行联合优化设计。在OSI 7层网络结构中，物理层和MAC层是相邻的两层，MAC层是数据链路层中更接近物理层的，所以对联合物理层与MAC层的跨层资源分配算法的研究也越来越多［6-8］，但是这些算法计算复杂度高且公平性较差。基于效用函数［9］的分配方法采用了数学优化方法来解决资源优化的分配，计算复杂度和求解难度都比较高。基于遗传算法的跨层资源分配［10］不但降低了计算的复杂性，而且还提高了系统的性能。由于遗传算法具有局部搜索能力差、爬山能力差以及容易陷入局部最优的缺点，使得遗传算法不能获得较好的资源分配方案。

禁忌搜索算法具有更好的局部搜索能力，而且收敛速度较快，能更好地收敛到全局最优解。所以遗传算法与禁忌搜索算法两者的结合能互相取长补短，提高算法的有效性。本文利用改进的混合遗传禁忌算法来解决跨层优化的问题，利用改进混合算法较好的全局搜索能力和更好地收敛到全局最优解的特点，提高多用户OFDM系统的性能。

2 多用户OFDM系统跨层优化的系统模型

2.1 系统模型

多用户OFDM系统的跨层优化模型如图1所示。在此模型中，上层分组数据到达数据链路层之后，物理层根据MAC层用户的缓冲队列信息来决定资源如何分配。将用户缓冲队列的情况和子载波的信道状态信息输入调度器中，调度器根据这两种信息把不同用户的数据分配到物理层进行处理。这个跨层设计结合了物理层的信道信息和MAC层的用户队列信息，使多用户OFDM系统能更好地满足QoS的需求。

图1 多用户OFDM系统的跨层模型

2.2 MAC层的资源调度

假设多用户OFDM系统有K个用户，且每个用户的队列长度是相同的，M代表队列的最大长度，队列中的数据按照FIFO（first in first out，先进先出）方式进行传输。每个用户的业务数据到达缓冲区服从泊松分布，到达率为λk，传输周期为 Ts。在［tTs，（t+1）Ts］时间（即第 t个时隙）内，用户k传输业务的服务率为用户从基站发送的数据量rk（t），在第 t-1 个时隙内用户 k 到达的数据量是 Ak（t）。根据泊松分布的定义［11］可知：

由泊松分布的性质可知，第t-1个时隙内到达的分组数为：

其中，E{Ak（t）}为 Ak（t）的期望。所以用户 k 在 Ts时刻的队列长度 Qk（t）为：

用户队列模型如图2所示。

图2 用户队列模型

再根据排队论里的Little定理，用户k在t时刻的平均等待时间 wk（t）为：

在MAC层，用户时延和分组丢失率是重要的指标。若用户时延减小，则会减少分组丢失率和分组损耗，提高用户的 QoS。

2.3 PHY层的资源分配模型

图3给出了K个用户、N个子载波的多用户OFDM系统的跨层资源分配过程，同时考虑到MAC层的资源分组和物理层信道信息。物理层获得的信道状态为N×K的矩阵。代表时隙t时用户k在子载波n上的信道衰落。定义比特分配 Bt=，…），功率分配 Pt=（，…）。

跨层资源的分配问题可以通过构造效用函数得到更好的解决［12］。为简便起见，令瞬时队列长度为{qkt，k=1，…，K}，瞬时速率{rkt，k=1，…，K}，则效用函数 Ut为：

假设每个子载波上最多分配比特数为C，令fk（C）代表用户k采用了2C阶调制并且满足指定BER条件需要的SNR。

假设传输一个OFDM符号需要的功率为P，所以，跨层资源分配的问题可以描述为：

图3 多用户OFDM系统的跨层资源分配过程

3 基于改进的混合遗传禁忌算法的跨层资源分配

3.1 遗传算法与禁忌搜索算法原理

遗传算法是一种全局优化算法，其基本原理是模仿生物界中的“物竞天择、适者生存”的演化规律［13］。遗传算法［14］把问题参数编码为每个个体的染色体，再利用迭代方式进行选择、交叉和变异，来交换种群中每个染色体间的信息，最终生成的染色体是符合优化目标的。

遗传算法［15］的缺点是收敛速度慢和算法容易进入早熟的状态，而造成早熟的原因主要是两个：一是遗传算法中的交叉算子，交叉算子使得种群中的染色体之间具有局部的相似性，可能导致搜索停滞不前；二是遗传算法中的变异概率一般比较低，变异操作带来的种群多样性不够。这两点均导致了遗传算法的爬山能力比较差。

禁忌搜索算法扩展了局部搜索的能力，它模仿人类的记忆功能，使用禁忌表来封锁刚搜索过的区域来避免迂回搜索，如果禁忌区域中的某个个体达到一定的限制，则可以进行释放，因此可以保证搜索的多样性以及达到全局最优化。禁忌搜索算法的优点是具有较快的收敛速度，但是禁忌搜索算法的搜索性能很大程度上依赖于给定的初始解。一个较好的初始解能使禁忌搜索算法更快地收敛于全局最优解。

3.2 改进的混合遗传禁忌算法

在禁忌搜索与遗传算法的混合策略中，由于遗传算法的广域搜索能力较强，主要作为“主算法”；而禁忌搜索算法的局部搜索能力较强，所以作为“从算法”。本文运用的是引入禁忌搜索思想的遗传算法，这种混合策略把禁忌搜索算法的“禁忌”和“特赦”思想加入遗传算法中，对遗传算法的交叉因子进行一定的改进。并且在初始化种群中加入优秀基因，这样可以加快搜索过程。混合算法的选择策略是“精英保留”机制，主要是为了把性能较好的染色体直接保留到下一代。引入禁忌搜索思想后，不但可以保留性能较好的个体，而且禁忌区域还有记忆功能，这就限制了优良个体被替换的频率，能很好地改进搜索性能。

改进的混合遗传禁忌算法利用了禁忌搜索算法的局部搜索能力和“爬山”能力强的特点，与遗传算法的并行性和全局搜索能力相结合，因此具有收敛速度快、爬山能力强等优点。引入禁忌搜索的遗传算法流程如图4所示。

图4 引入禁忌搜索的遗传算法流程

3.3 跨层资源分配优化算法的实现

（1）编码

首先生成长度为N的一维数组，每个元素都对应OFDM系统的一个子载波，数组元素对应系统中的各个用户。每个数组就对应一种子载波分配方案。子载波分配情况如图5所示。

图5 子载波编码方式

（2）种群初始化

本文通过式（12）得到初始解：

式（12）表示把子载波 n分配给用户K*，其中，λk代表平均业务量，Qk代表用户队列长度。当每个子载波上分配的功率一定时，hn，k越大，子载波能发射的比特数就越多，Qk／λk相当于用户k的平均时延。这样就能产生一个较好的初始种群，能更好地满足用户的QoS。

（3）适应度函数

采用效用函数作为改进的混合遗传禁忌算法的适应度函数。

（4）选择

采用精英保留机制，将群体中适应度值按升序进行排列，选择适应度最高的Y个个体直接进入下一代，来进行下一步的操作。

（5）引入禁忌搜索的交叉

设禁忌表Tlist为空，长度为L。禁忌对象为染色体的基因，以每代中父代染色体平均适度值作为渴望水平。

禁忌交叉算子的操作过程大致如下。

步骤1 初始化禁忌表，禁忌长度为L，设为空。

步骤2 给每一个染色体产生一个0～1之间的随机数d，Pc为交叉概率，如果 d＜Pc，则选择其作为父代染色体，否则不会被选中。

步骤3 对每对父代染色体按交叉方法进行交叉操作，产生两个子代新个体。

步骤4 计算子代染色体的适应度值是否优于渴望水平。如果优于渴望水平，则进入下一代；否则就把该子代染色体放入禁忌表中，选择父代染色体进入下一代。

步骤5 判断是否达到最大交叉次数。若已经达到最大交叉次数，则退出循环；否则进入步骤2。

本处采用的交叉方法是均匀交叉，在群体中按交叉概率Pc随机选取两个个体，根据交叉概率Pc决定是否交叉，再随机选取交叉的长度，进行交叉。比如个体A（1100110110）、个体 B（0110100011），选择交叉位是第 2位以及交叉长度为4之后产生的两个新个体：个体A（1110110110）、个体 B（0100100011）。交叉之后的两个新个体进行禁忌搜索的判断，若新个体已经存在于Tlist表中，则跳过不再进行访问，这样避免重新访问已经访问过的个体，能更快地跳出局部最优解。

（6）变异

本文采用多点均匀变异，即以变异概率Pm随机指定某一位或某几位基因座上的基因做变异运算。对于个体A（1100110110），根据变异概率Pm随机选择变异位置第4位以及变异长度为4，则变异后A*为（1101001110）。Pm的取值一般在0.01～0.1，为了增加种群的多样性，本文把Pm调整到 0.2。

4 性能仿真

为了验证本文提出的算法性能，利用MATLAB软件进行了实验仿真。仿真中，考虑多用户OFDM系统的带宽为1 MHz，子载波为128个，总功率P=1。信道采用瑞利衰落模型，每个用户的分组数据到达服从泊松分布，业务数据到达率 λk取值范围为 5～30 kbit／s，Ts取值为 2 ms，每个OFDM符号内允许最大传输比特数C为4，每个数据分组长度M=200 bit。信道的噪声功率谱密度N0为10-8，误码率BER≤10-3。混合遗传禁忌算法的参数设定：最大迭代次数D为100，种群规模为S为 100，交叉概率Pc=0.9，变异概率Pm=0.2。

图6是多用户OFDM系统在用户数K=4时，比较遗传算法与本文提出的改进混合遗传禁忌算法的收敛曲线。从图6中可以看出，在相同的迭代次数下，本文提出的改进混合算法能获得较大的效用函数值，也就是说，在发射功率相同的情况下，本文提出的算法能够发射更多比特数据。从图6还能看出，本文提出的改进混合遗传禁忌算法在开始时就能得到较优解，随着迭代次数的增加，效用函数值也有所提高，能够更快地收敛于全局最优解，也就是用户能发送的信息总量。

图6 遗传算法与改进的混合遗传禁忌算法收敛性能比较

图7比较了3种算法的平均时延，在用户数不断增加的情况下，本文提出算法的系统时延要低于其他两种算法的系统时延。

图7 3种算法的平均时延比较

本文提出的改进混合遗传禁忌的算法复杂度主要集中在遗传算法中的选择、禁忌交叉和变异中，个体的适应度函数选择的是效用函数，复杂度为O（N），一个种群中含有 S个个体，复杂度为 SO（N），经过选择之后的复杂度为（1-Y／S）O（S2）。禁忌交叉步骤的复杂度为 SO（N），变异操作的复杂度为 SO（N），所以本文提出的改进混合算法总的复杂度为 D［3SO（N）+（1-Y／S）O（S2）］。对于线性算法 LP，Karmarkar算法［17］的时间复杂度是 O（n3.5L），其中，L 代表线性方程组的输入规模，n代表变量的个数。由此可以看出，LP的复杂度比混合遗传禁忌算法大。

由图8可知用户数为4时，线性算法、遗传算法以及改进的混合遗传禁忌算法下每个用户的分组丢失率。本文提出的改进混合算法的分组丢失率略低于遗传算法和线性算法的分组丢失率，而且混合遗传禁忌算法的复杂度也低于前两种算法。

图8 3种算法的用户分组丢失率

5 结束语

本文研究了多用户OFDM系统中的跨层资源分配问题，结合了物理层的信道状态信息和MAC层的队列状态信息，并利用改进的混合遗传禁忌算法进行优化，利用遗传算法全局搜索能力强和禁忌搜索算法局部能力强进行互补，使得算法的性能得到提高。仿真结果表明，本文提出的改进混合算法与线性算法和遗传算法相比，可以提高系统的吞吐量且减小用户的平均时延，还能更好地满足用户的QoS要求。

［1］SHAKKOTTAIST，RAPPAPORTS，KARLSSON PC.Cross-layer design for wireless networks ［J］. IEEE Communications Magazine，2003，41（10）：74-80.

［2］ GOLDSMITH A J，WICKER SB.Designchallengesfor energy-constrained Ad Hoc wireless networks ［J］.IEEE Transactions on Wireless Communications，2002，9（4）：8-27.

［3］TANG M，WANG X.Joint subcarrier and power allocation with threshold in cooperative multiuser networks ［J］.High Technology Letters，2011，17（4）：360-365.

［4］LI M，WANG X，ZHANG H.Resource allocation with subcarrier cooperation in OFDM-based wireless multicast system ［C］／／2011 IEEE 73rd Vehicular Technology Conference，May 15-18，2011，Budapest，Hungary.New Jersey：IEEE Press，2011：1-5.

［5］ YU X， NAVARATAM P， MOESSNER K.Distributed interference-aware admission control with soft resource allocation for hybrid MAC in wireless mesh networks ［C］／／2012 IEEE InternationalConference on Communications，June 10-15，2012，Ottawa，ON，Canada.New Jersey：IEEE Press，2012：455-460.

［6］SONG G，LI Y，ZHENG H.Joint channel-aware and queue-aware data scheduling in multiple shared wireless channels［C］／／IEEE Wireless Communications and Networking Conference，March 21-25，2004，Atlanta，USA.New Jersey：IEEE Press，2004：1939-1944.

［7］ WEIC，PINGYF，ZHIGC.Waterfillingincellar：theoptimal power allocation policy with channel and buffer state information ［C］／／IEEE International Conference on Communications，May 16-20，2005，Seoul，Korea.New Jersey：IEEE Press，2005：537-541.

［8］ SUN Y，YU L，ZHANG J.Joint MAC-PHY layer resource allocation algorithm based on triangle module operator for multi-service OFDM system［J］.Procedia Environmental Sciences，2011，10（1）：163-169.

［9］ KUO W H，LIAO W.Utility-based resource allocation in wireless networks ［J］.IEEE Transactions on Wireless Communications，2007，6（10）：3600-3606.

［10］郁宇，周武旸.OFDMA系统中基于遗传算法的资源分配［J］.计算机仿真，2008，25（5）：143-146.YU Y，ZHOU W Y.Resource allocation for OFDMA system based on genetic algorithm［J］.Computer Simulation，2008，25（5）：143-146.

［11］赵芝卫，张琳.一种新的 OFDMA系统功率与比特分配算法［J］.通信技术，2011，44（5）：31-33.ZHAO Z W，ZHANG L.A new power and bit allocation algorithm for OFDMA systems［J］.Communications Technology，2011，44（5）：31-33.

［12］SONG G，LI Y.Cross-layer optimization for OFDM wireless networks-part I：theoretical framework ［J］.IEEE Transactions on Wireless Communications，2005（4）：614-624.

［13］MENG Q C，FENG T J，CHEN Z.Genetic algorithms encoding study and a sufficient convergence condition of GAs ［C］／／1999 IEEE International Conference on Systems， Man， and Cybernetics，Oct 12-15，1999，Tokyo，Japan.New Jersey：IEEE Press，1999：649-652.

［14］王凌.智能优化算法及其应用［M］.北京：清华大学出版社，2001.WANG L.Intelligent optimization algorithm and application ［M］.Beijing：Tsinghua University Press，2001.

［15］雷英杰，张善文，李续武，等.遗传算法工具箱及应用［M］.西安：西安电子科技大学出版社，2004.LEI Y J，ZHANG S W，LI X W，et al.Genetic algorithm toolbox and application ［M］.Xi’an：Xi’an University of Electronic Science and Technology Press，2004.

［16］徐伟尧.OFDMA系统中资源分配方案的研究［J］.广东通信技术，2010（9）：39-43.XU W Y.Research on resource allocation scheme in OFDMA system ［J］.Guangdong Communication Technology，2010 （9）：39-43.

［17］RUDAN J，SZEDERKENYI G，HANGOS K M.Efficient computation of alternative structures for large kinetic systems using linear programming［J］.Communications in Mathematical and in Computer Chemistry，2014，71（1）：71-92.

An improved optimization algorithm in cross-layer allocation for multi-user OFDM system

PAN Yaqin，ZHANG Li，ZHANG Shibing
School of Electronics and Information，Nantong University，Nantong 226001，China

A cross-layer resource allocation model in multiuser OFDM system was proposed，which combined the channel state in physical layer and the user’s queue in MAC layer.The proposed hybrid optimization algorithm made use of the advantages of genetic algorithm and tabu search algorithm to improve the crossover of genetic algorithm.It would improve the global search ability，converge to the global optimal value faster，solve the cross-layer resource allocation problem more effectively and meet the user’s quality of service better.The simulation results show that the improved hybrid algorithm increases the throughput，reduces the average delay and improves the QoS of the system.

OFDM，cross-layer，resource allocation，hybrid algorithm

s：The National Natural Science Foundation of China（No.61371112），Application Basic Research Project of Transportation Department（No.2014319813220）

TN914

10.11959／j.issn.1000-0801.2016188

2016-01-22；

2016-07-08

张士兵，zhangshb@ntu.edu.cn

国家自然科学基金资助项目（No.61371112）；交通运输部应用基础研究项目（No.2014319813220）