基于分段替换的低复杂度降低OFDM峰均比算法

冯兴乐，梁中华，路 萍,2，宋 凡(. 长安大学信息工程学院 西安 70064；2. 清华大学苏州汽车研究院 江苏 苏州 25200 )



基于分段替换的低复杂度降低OFDM峰均比算法

冯兴乐1，梁中华1，路 萍1,2，宋 凡1
(1. 长安大学信息工程学院 西安 710064；2. 清华大学苏州汽车研究院 江苏 苏州 215200 )

【摘要】针对基于遗传算法(GA)的部分传输序列(PTS)方法在降低正交频分复用(OFDM)系统峰均比(PAPR)时存在避免早熟收敛和降低算法复杂度两项指标不能兼顾的问题，提出分段替换的降低OFDM峰均比算法。通过设置合理的门限值，减少不必要的搜索运算，降低算法复杂度；利用克隆种群和记忆种群相结合的分段替换染色体策略，提高优质种群利用率，加快收敛速度的同时避免早熟收敛。仿真结果表明，合理的门限值和分段替换染色体策略可以优化降低峰均比算法的性能。

关 键 词遗传算法; 正交频分复用; 峰均比; 部分传输序列; 分段替换策略

Low Complexity Algorithm Reducing Peak-Average-Power Ratio in OFDM System Based on Segment Replacement

FENG Xing-le1, LIANG Zhong-hua1, LU Ping1,2, and SONG Fan1
(1. School of Information Engineering, Chang’an University Xi’an 710064; 2. Suzhou Automotive Research Institute,Tsinghua University Suzhou Jiangsu 215200)

Abstract Based on segment replacement scheme, an improved genetic algorithm (GA) partial transmits sequence (PTS) is proposed. It can achieve a trade-off between overcoming premature and complexity reduction in the process of reducing peak-average-power ratio (PAPR) in an orthogonal frequency division multiplexing (OFDM) system. Appropriate threshold can reduce the unnecessary search operation and reduce the complexity of the algorithm. Combining the clone population and the memory population, the segment replacement strategy is proposed not only to improve the utilization of fine species, but also to avoid premature convergence. Simulation results illuminate that the reasonable threshold and segment replacement strategy can improve the optimize performance of the algorithm.

Key words genetic algorithms; orthogonal frequency division multiplexing; peak-average-power ratio; partial transmit sequence; segment replacement strategy

正交频分复用(OFDM)是一种将载波分割为若干相互正交的子载波，克服频率选择性衰落和窄带干扰的多载波调制技术。该技术在获得较高的频谱利用率的同时，较高的符号峰均比(PAPR)对功率放大器件的线性动态范围提出很高甚至无法满足的要求，因此，降低OFDM符号的PAPR成为该领域的主要研究课题之一。

在众多降低PAPR的方法中，最简单的数字限幅削峰技术，会带来额外的带外辐射和非线性失真。文献[1]中通过一种改进的限幅削峰滤波技术，以较低的算法复杂度降低峰均比，但无法解决带外失真和辐射的问题。基于多信号替换的选择映射和交织技术可实现无失真信号处理，文献[2]提出一种基于tone injection的方法，在一个扩张后的星座图中，用多个备选的星座点代表同一个发射数据，待傅里叶反变换(inverse discrete Fourier transform，IDFT)后选择PAPR较小的信号发射。基于统计概率的部分传输序列算法[3](PTS)尽管是一种无失真技术，但在旋转符号相位时需要多次快速傅里叶反变换(inverse fast Fourier transform，IFFT)运算以遍历所有的相位组合，其复杂度随子向量数呈指数增长，在工程中难以实现。文献[4]通过分区优化PTS中各子载波，减少多子载波系统的误码率，但是无法改善算法的复杂度。遗传算法(GA)是一种全局并行自适应搜索的方法，收敛精度依赖于迭代次数，但存在早熟收敛现象。为此，部分学者提出将GA算法和PTS相结合的GA-PTS算法[5-9]，此类算法又可细分为两类。一类以降低PAPR为目标，如文献[5]通过增加遗传算法中交叉操作的次数降低PAPR，该方法可扩大搜索广度，但增加了搜索次数。文献[6]利用GA-PTS计算最佳相位旋转向量，每次迭代时选出丢弃种群，并补充随机种群，增加搜索广度，但会增加复杂度。而在另一类以降低算法复杂度为目标的GA-PTS算法中，文献[7]在搜索结果满足预设精度时停止迭代，减少搜索次数，但会导致早熟收敛。文献[8]采用分组方式减少相位旋转向量的搜索个数，但分组方式不能自适应子载波的PAPR变化，缺乏普适性。文献[9]提出一种基于汉明距离和交叉变异的种群替换策略，避免无意义的搜索，减少搜索时间。文献[2]通过表格存储染色体的适应值，避免迭代过程中的重复计算，以此降低复杂度。文献[10]提出基于球形译码的搜索思路，缩小搜索范围。

本文在传统GA-PTS的基础上，借鉴进化种群分组的思想，提出一种克隆种群和记忆种群相结合的分段替换策略的遗传算法部分传输序列算法(segment replacement genetic algorithm PTS，SRGA-PTS)。主要思想是在PTS运算时，对满足PAPR门限值的符号不旋转相位以降低复杂度。另外，在迭代搜索最佳染色体的过程中，将当前种群分为3部分，分别进行保留、替换和丢弃操作。在替换过程中，充分结合克隆种群和记忆种群的优点，在提高优质种群利用率，加快收敛速度的同时，扩大有效搜索范围，避免早熟收敛，达到种群搜索广度和优质染色体利用率的折中。

在本文中，PTS算法中所指的相位旋转向量就GA算法中的染色体，为统一起见，本文统一用染色体术语。

1 系统模型

在多载波调制系统中，第k时刻的时域信号x[ k ]由N个频域信号经过子载波调制后组成：

式中，max{⋅}表示选取向量中的取值最大的元素；E{⋅}表示向量均值。

图1　PTS算法模型

PTS算法模型如图1所示，该算法的核心是对多个子载波进行非均匀相位旋转，避免多个同相子载波叠加而导致较高的PAPR。工作流程如下：

4) 为实现时域符号的相位旋转，需要一个长度为V的染色体向量其中的取值限于相位旋转集合为可能的相位数，这样，遍历所有相位组合后的候选染色体集合包括种可能，所有染色体集合为

5) 第k次迭代时，时域符号x乘以bl，得到一组峰均比较低的时域符号y，作为PTS的输出，有：

量化反映染色体bl性能的适应值定义为：

2 基于分段替换的SRGA-PTS算法

2.1 设计思想

GA-PTS算法的核心是通过GA算法确定一个最佳染色体bopt，将其应用到PTS中降低PAPR。传统GA的出发点是通过不断迭代，染色体基因之间的交叉和变异，找到适应值更高的染色体。然而，在迭代前期，选择操作使得几个适应值较高的染色体在种群中占有很高的比例，种群的多样性受到抑制，搜索范围变小，容易得到局部最优解，即产生早熟现象；在迭代后期，种群之间具有极高的相似度，会造成进化停滞。

为避免上述情况，部分学者提出一些改进的GA-PTS算法。如文献[6]在每次迭代时会保留适应值高的种群，并以新的随机种群替换适应值低的种群。该方法以增加新鲜种群，扩大搜索范围为代价，解决早熟收敛的问题。文献[9]的替换策略是基于汉明距离确定的优秀种群，利用交叉迭代的方法产生新种群，以此替换适应值低的种群。该方法的核心是提高优质种群的使用率，缩小搜索范围，降低复杂度，但过度依赖优质种群会限制种群多样性，导致早熟收敛。上述文献尽管在某些方面能够取得一些改进，但都不能兼顾避免早熟收敛和降低算法复杂度两项指标。

本文提出的SRGA-PTS的设计初衷就是通过设定合理的停止搜索最佳染色体的门限值，设计分段替换染色体基因的策略，找到能够刚好将PAPR降低到门限值以下的染色体。在保证性能的同时减少不必要的搜索，达到种群搜索广度和优质染色体利用率的折中。

2.2 SRGA-PTS算法流程

图1中PTS算法流程的核心在于利用旋转向量来改变OFDM符号中各子载波信号的相位，其关键是最优染色体的选取。本文提出的SRGA-PTS算法的创新点在于分段替换策略，具体流程如图2所示。

首先随机生成L个染色体作为初始种群，初始种群规模越大，优化效果越好，复杂度越高。本文中种群规模候选集为

图2　SRGA算法流程图

在迭代过程中，满足以下条件之一，则终止迭代搜索，输出bopt。1) 计算种群中染色体的适应值，符号的PAPR小于门限值；2) 迭代次数超过最大迭代次数Imax；3) 连续迭代Isucc期间的适应值的变化范围小于0.05 dB。

若不满足终止条件，则进行染色体选择操作，按式(6)计算当前种群的适应值，降序排列后按一定的比例将种群分为3部分，不同的份额比例设置将影响性能，在下节的仿真实验中，将加以对比分析。

A类：适应值最高的精英种群，所占份额为α%，保留到下次迭代过程中；B类：适应值中等的待替换种群，所占份额为β%，将被A类种群和记忆种群的染色体所替换；C类：适应值最低的丢弃种群，所占份额为γ%，将模拟自然死亡后抛弃，并用随机生成的新种群代替。

对A类种群，分别以交叉概率Pcross和变异概率Pmut对所有染色体进行交叉和变异操作[7]。

B类种群的克隆替换过程如图3所示。在每次迭代过程中，都存在记忆种群和克隆种群。记忆种群保存了每次迭代产生的适应值最高的一个染色体，也就是说，记忆种群的规模在不断扩大。

首先，本次迭代得到的A类种群与记忆种群中的当前最佳染色体(即在记忆种群中适应值最高的染色体)进行比较，并按相似度降序排列，相似度最高的前β份额染色体进行变异处理，根据动态克隆策略[11]组成克隆种群。SRGA算法将克隆种群和记忆种群放到一起，形成备选种群集合，并取适应值较高的那部分替换B类种群。

图3　分段替换策略示意图

3 实验结果与分析

本文在MATLAB7.0中实现SRGA-PTS算法，仿真参数：QPSK调制，N=128，V=8，L=40，T=10，过采样率为4。GA算法中，采用轮盘赌选择、单点交叉、单点变异操作。具体的操作步骤参见文献[6]。交叉和变异概率设定Pcross=0.7和Pmut=0.3，最大迭代次数Imax=5，连续迭代次数Isucc=3。

用互补累积概率(CCDF)表示优化后符号的PAPR超过门限值的概率，有：

本文算法中影响性能的主要因素包括：1) PAPR门限值；2) 分段替换策略中3类型种群份额划分。下面通过分析仿真实验结果，分别讨论两指标对算法性能的影响以及与其他算法的比较。

3.1 PAPR门限值对算法性能的影响：

在以降低PAPR为目标的GA-PTS算法中，设置合理的门限值至关重要。一方面，在实际系统中，降低PAPR的目的是使合成符号的功率峰值在放大器的线性工作范围之内，PAPR并不是越低越好，因此理论上可参考器件线性工作时所能够承受的最高PAPR值来设置门限值ξ[10]。另一方面，若门限值设置过低，尽管可以更好地降低PAPR，但会造成GA算法难以收敛，增加复杂度。下节的仿真实验将比较不同门限值对应的迭代次数和复杂度。

图4是不同门限值对应的CCDF曲线图，由图可知，门限值越高，需要优化处理的符号数减少，收敛速度越快，降低PAPR效果不明显。门限值越低，需要优化处理的符号越多，算法越难找到最优解，收敛速度慢，复杂度增加(如ξ= 6.0 dB)。

图4　不同门限值对应的CCDF

从图5可以看出，ξ越小，在最优解邻域内的符号数量越多，算法优化性能越好。又由表1可知，ξ越小，在寻求最优解时需要更多的次数，复杂度越高，收敛速度越慢，ξ小到一定程度时算法复杂度急剧增加。

由上可知，在设置门限值时，ξ太高会降低算法的优化性能，ξ太低易导致算法复杂度增加，甚至不收敛。设置合理的门限值既可以改变算法的收敛速度和复杂度，也可以改善算法的优化性能。一方面，若优化后的符号峰均比分布能够完全落在放大器的线性放大范围内时，主要考虑门限值对算法复杂度的影响。因此若系统对算法复杂度要求较高时，建议选择线性放大区间较大的放大器，这样可以设定较高的门限值，以便降低算法复杂度。另一方面，在放大器线性放大区间有限的系统中，必须设定较低的门限值，才能满足降低峰均比的要求，但算法复杂度会响应增加。根据本文仿真结果，建议门限值动态调整范围为7 dB±0.5 dB。

图5　不同门限值下的PAPR概率分布

表1　不同门限值下的算法复杂度

3.2 种群分类份额划分对算法性能的影响

本文设计分段策略的初衷是通过控制精英种群和替换种群的规模调节收敛的速度，扩大丢弃种群的规模防止算法早熟，进而达到优化算法性能的效果。但如何划分A、B和C类型种群份额是一个关键因素，采用克隆种群和记忆种群相结合的方法，对中等适应值的染色体进行动态克隆替换，达到种群搜索广度和优质染色体利用率的折中，找到刚好将PAPR降低到门限值以下的染色体，兼顾降低复杂度和避免早熟收敛的目标。下面比较α、β和γ在不同取值条件下的算法性能和复杂度。

图6和图7分别为ξ=7.0 dB时不同种群份额对应的CCDF图，可以看出，不同的份额对算法性能的影响有限。图6和图7中的拐点1、2、3对应的纵坐标值表示不同分段比例下早熟的符号出现的概率，拐点对应的坐标值越小，表示出现早熟现象的概率越小，反之亦然。由图可知在A类种群数量保持不变时，B类和C类种群份额的差距越大，优化性能越好。在C类种群数量保持不变时，A类和B类种群份额越接近，优化效果越好。

图6　A类份额固定不变，B、C变化

图7　C类份额固定不变，A、B类变化

由表2可以看出在ξ不变的情况下，不同的分段份额对算法的复杂度影响不大，故在分段时无需考虑算法复杂度。为了保证精英种群的优势，在算法中规定B类种群的数量要小于A类种群，因此，本文建议的分段份额分别为A(α%=50%)，B(β%=40%)，C(γ%=10%)。

表2　不同种群份额划分下的算法复杂度

综上所述，通过设置合理的门限值和不同的种群划分份额可以提高收敛速度、避免早熟，达到优化系统性能的效果。上述分析根据仿真结果给出了相应的建议值。

3.3 复杂度比较

本文相对其他的遗传算法而言设置了一个门限值，在算法中，达到门限值要求的符号立刻停止搜索，这样处理之后在保证峰均比降低的同时，减少了不必要的搜索运算，降低了算法的复杂度。文献[9]中的MDGA算法通过最小汉明距替换策略来搜索最优种群，没有有效减少搜索深度，使得搜索半径变大，增加了算法的复杂度。文献[13]中的ABC-PTS算法在寻找最优向量时需要搜索足够的次数才能得到最优解向量，增加了算法的复杂度。

表3中，W=2为可供选择的向量因子，M=8为分割的子向量数，L=40，P=40分别为种群规模，T=10，G=20分别为子代数量，S=40为蜂群的群体数量，K=20为最大的进化数。

通过上述对比可知，本文算法通过设置合理的门限值，在搜索最优种群的过程中，当适应值达到门限值的要求时停止搜索，减少了不必要的搜索运算，很好地改善了同类算法复杂度高的缺点，兼顾了高算法性能和低复杂度的要求。

表3　各种不同算法复杂度的比较

4 结 束 语

本文在传统GA-PTS的基础上，借鉴进化种群分组的思想，提出了一种基于门限值的分段替换策略的SRGA-PTS算法。该算法可以通过设置不同的门限值和种群分段比例来优化算法性能。仿真结果显示，在种群划分份额固定的情况下，设置不同的门限值可以有效地控制算法的复杂度；在门限值相同的情况下，设置不同的种群划分份额可以有效的控制算法的收敛速度，避免早熟，并根据仿真结果给出了门限值和种群份额的建议值。该算法可以在避免早熟和降低算法复杂度两项指标中寻求一种平衡，既能满足优化的需求，又能使算法尽快收敛，降低算法的复杂度。

参 考 文 献

[1] ZHU Xiao-dong, PAN Wen-sheng, LI Hong, et al. Simplified approach to optimized iterative clipping and filtering for PAPR reduction of OFDM signals[J]. IEEE Transactions on Communications, 2013, 61(5): 1891-1901.

[2] SHIGEI N, MIYAJIMA H, OZONO K. Acceleration of genetic algorithm for peak power reduction of OFDM signal [J]. IAENG International Journal of Computer Science, 2011, 38(1): 32-37.

[3] DUANMU C J, CHEN H T. Reduction of the PAPR in OFDM systems by intelligently applying both PTS and SLM algorithms[J]. Wireless Personal Communications, 2014, 74(2): 849-863.

[4] LI Li, QU Dai-ming, JIANG Tao. Partition optimization in LDPC-Coded OFDM systems with PTS PAPR reduction[J]. IEEE Transactions on Vehicular Technology, 2014, 61(8): 4108-4113.

[5] LIANG H Y, CHEN Y R, HUANG Y F. A modified genetic algorithm PTS technique for PAPR reduction in OFDM systems[C]//The 15th Asia-Pacific Conference on Communications. Shanghai: IEEE, 2009: 170-173.

[6] PRADABPET C, YOSHIZAWA S, MIYANNAGA Y. Phase rotation optimization in hybrid of PTS-CAPPR method by GA for PAPR reduction in OFDM systems[C] //International Conference on Green Circuits and Systems. Shanghai : IEEE, 2010: 703-708.

[7] LIXIA M, MURRORI M, POPESCU V. PAPR reduction in multi-carrier modulations using genetic algorithms[C]// International Conference on Optimization of Electrical and Electronic Equipment. Basov: IEEE, 2010: 938-942.

[8] 杨霖, 张帅, 王小波, 等. 改进的GA-PTS降低OFDM峰均比[J]. 电子科技大学学报, 2013, 42(3): 338-344. YANG Lin, ZHANG Shuai, WANG Xiao-bo, et al. Improved GA-PTS method for reducing PAPR of OFDM[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(3): 338-344.

[9] ZHANG Y, NI Q, CHEN H H, et al. An intelligent genetic algorithm for PAPR reduction in a multi-carrier CDMA wireless system[C]//IEEE Wireless Communications and Mobile Computing Conference. Crete Island: IEEE, 2008: 1052-1057.

[10] YANG L, CHEN R S, SIU Y M. An efficient sphere decoding approach for PTS assisted PAPR reduction of OFDM signals[J]. AEU-International Journal of Electronics and Communications, 2007, 61(10): 684-688.

[11] 洪露, 龚成龙, 王经卓. 噪声环境下精英克隆选择算法的收敛性分析[J]. 控制理论与应用, 2013, 30(11): 1457-1461. HONG Lu, GONG Cheng-long, WANG Jing-zhuo. Convergence analysis of elitist clonal selection algorithm in noisy environment[J]. Control Theory & Applications, 2013, 30(11): 1457-1461.

[12] JAYALATH A D S, TELLAMBURA C. Adaptive PTS approach for reduction of peak-to-average power ratio of OFDM signal[J]. Electronics Letters, 2000, 36(14): 1226-1228.

[13] WANG Ya-jun, CHEN Wen , TELLAMBURA C . A PAPR reduction method based on artificial Bee colony algorithm for OFDM signals[J]. Wireless Communications, 2010, 10(9): 2994-2999.

编 辑 漆 蓉

作者简介：冯兴乐(1971 − )，男，博士，教授，主要从事通信信号处理、智能交通方面的研究.

基金项目：国家863项目(2012AA112308)；国家自然科学基金(61271262)；陕西省自然科学基金(2015JM6310)；中央高校基本科研业务费专项资金(CHD2012TD011, 310824152010, 0009-2014G1241043)

收稿日期：2014 − 09 − 04；修回日期：2015 − 07 − 09

中图分类号TN929.5

文献标志码A

doi:10.3969/j.issn.1001-0548.2016.01.009