基于分段替換的低復雜度降低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]中通過一種改進的限幅削峰濾波技術，以較低的算法復雜度降低峰均比，但無法解決帶外失真和輻射的問題?；诙嘈盘柼鎿Q的選擇映射和交織技術可實現無失真信號處理，文獻[2]提出一種基于tone injection的方法，在一個擴張后的星座圖中，用多個備選的星座點代表同一個發射數據，待傅里葉反變換(inverse discrete Fourier transform，IDFT)后選擇PAPR較小的信號發射?；诮y計概率的部分傳輸序列算法[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)；中央高?；究蒲袠I務費專項資金(CHD2012TD011, 310824152010, 0009-2014G1241043)

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

中圖分類號TN929.5

文獻標志碼A

doi:10.3969/j.issn.1001-0548.2016.01.009