基于混合蛙跳算法的多模盲均衡算法

郭業才，張苗青

（1.南京信息工程大學江蘇省氣象探測與信息處理重點實驗室，江蘇南京210044；2.江蘇省大氣環境與裝備技術協同創新中心，江蘇南京210044）

基于混合蛙跳算法的多模盲均衡算法

郭業才1，2，張苗青1

（1.南京信息工程大學江蘇省氣象探測與信息處理重點實驗室，江蘇南京210044；2.江蘇省大氣環境與裝備技術協同創新中心，江蘇南京210044）

針對常模盲均衡算法（CMA）收斂速度慢、收斂后穩態誤差大且存在盲相位的現象，提出了一種基于混合蛙跳算法的多模盲均衡算法（SFLA-MMA）。它結合了智能優化算法的基本思想，將個體自身的進化及個體間的社會行為等概念引入到盲均衡技術中。該算法將多模盲均衡算法（MMA）代價函數的倒數定義為混合蛙跳算法（SFLA）的適應度函數，將青蛙群體中青蛙個體的位置向量作為MMA的初始權向量；利用SFLA的全局信息共享機制和局部深度搜索能力，在全局范圍內搜索青蛙群體的最優位置向量并作為MMA的初始優化權向量。之后，通過MMA進行迭代，得到MMA的最優權向量。利用高階多模正交振幅調制（QAM）與正交相移鍵控（APSK）信號對該算法進行了仿真驗證。仿真結果表明，與CMA、MMA和基于粒子群算法的多模盲均衡算法（PSOMMA）相比，SFLA-MMA在均衡高階多模信號時收斂速度極快、穩態誤差最小、輸出信號星座圖最清晰。

信息處理技術；多模算法；混合蛙跳算法；智能優化算法；最優權向量

0 引言

在通信系統中，為了有效地消除有限帶寬和多徑傳播等引起的碼間干擾，接收端需要引入盲均衡技術。在盲均衡技術中，常模盲均衡算法（CMA）是使均衡器輸出信號星座點盡可能分布在一個半徑為RC（信號的統計模值）的圓上，從而不斷調整均衡器的權向量。CMA最大的優點在于它的代價函數只與接收序列的幅度有關，而與相位無關，所以CMA非常適用于常模信號。但是，對于具有不同模值的高階正交振幅調制（QAM）和正交相移鍵控（APSK）信號，其星座點分布在不同半徑的圓上，如果采用CMA進行均衡就會使輸出信號星座點趨于單一圓上，從而產生較大的誤差，甚至導致算法無效。近年，Yang等提出的多模盲均衡算法（MMA）［1］是對CMA的一種改進，主要思想是以判決輸出信號的模值作為圓的半徑，把星座圖分成多個區域，每個區域都有各自的誤差函數，從而將剩余誤差控制在較小的范圍內［2］。綜上所述，對于高階多模信號，MMA收斂性能與CMA相比有所提高，并且不需要相位旋轉器來消除相位模糊［3］，尤其對于非方形星座、密集型星座，MMA能夠更加充分地利用符號的統計特性。但是，MMA與CMA一樣存在模型誤差，其收斂速度及收斂后的剩余誤差仍不甚理想。

混合蛙跳算法（SFLA）［4］是一種受自然生物模仿啟示而產生的群體性協同搜索方法，本質上是一種概率搜索。該算法模擬青蛙的群體性覓食行為，按種群分類并進行信息傳遞，將局部深度搜索和全局信息交換相結合［5-6］，同時具備基于遺傳特性的模因演算法（MA）［7］和基于社會行為的粒子群算法（PSO）［8］二者的優點，達到了全局信息共享和局部開發能力的平衡。算法易于理解，容易實現，可操作性和魯棒性較強。

結合SFLA和MMA各自的特點，本文提出了一種基于混合蛙跳算法的多模盲均衡算法（SFLAMMA），其原理是利用SFLA快速搜索到一組適用于MMA算法的全局最優解，以此作為MMA的最優初始化權向量進行迭代，并進行了仿真驗證。

1 多模盲均衡算法

與CMA相比，MMA相當于在CMA的基礎上多加入了一個判決器，以決定誤差函數中模值的選取，如圖1所示。x（n）為均衡器的接收信號，wD（n）為橫向濾波器的權向量，z（n）為橫向濾波器的輸出，z（n）通過非線性系統g（·）得到估計信號^z（n），eD（n）為誤差信號，以上的n為數字信號的采樣點數。RS為采樣模值，RD為判決模值，虛線框內為MMA算法。

圖1 MMA盲均衡算法結構圖Fig.1 Structure diagram of MMA blind equalizer

MMA以LMS算法為模型，將橫向濾波器的輸出信號z（n）通過一個非線性系統g（·），得到估計信號，以此代替期望信號d（n），進而得到算法的誤差信號eD（n）.此外，為了使橫向濾波器的權系數趨于收斂，非線性函數g（·）需滿足（1）式。

式中:RD是對RS的判決結果，RS為

式中:E（·）表示求數學期望。

由圖1可知，MMA橫向濾波器輸出信號為

誤差信號為

因此，MMA代價函數定義為

由該代價函數的隨機梯度，可以得到MMA的權向量迭代公式。根據（3）式、（4）式和（5）式，JMMA（n）的隨機梯度為

那么，權向量的迭代公式為

式中:μD為MMA的迭代步長。

MMA根據判決模值RD調整誤差函數，這里以32-APSK信號為例。APSK星座圖可以被視為具有不同電平幅度的相移鍵控（PSK）信號的集合［9-10］，它又被稱為星形QAM，如圖2所示。圖2中，輸入信號星座點分布在3個半徑不同的圓上，其半徑對應于信號的模值；虛線所示的兩個同心圓是判決器的判決邊界條件，記為RB.兩個判決圓將星座空間分成了3個區域，分別對應3個誤差函數。

圖2 32-APSK信號的模值Fig.2 Modulus of 32-APSK

設接收信號是32-APSK信號，星座圖中RD所在圓的半徑按從小到大排列分別為RD1、RD2、RD3，判決圓半徑RB的下限為Rm，上限為Rb.

橫向濾波器輸出信號z（n）輸入判決器，由（2）式計算RS、比較其與判決邊界條件的關系，選取這一段信號的判決模值為

將（8）式代入（4）式，得到對于32-APSK的誤差函數為

對于不同的調制方式，判決器的判決規則也不盡相同。MMA能否有效地均衡主要取決于算法中的判決條件，即Rm、Rb的選取。

雖然MMA具有運算復雜度低、對于高階多模信號收斂速度快等優點，但由于其存在模型誤差，使得收斂后的剩余誤差較大，不利于信號的追蹤［11］。

2 混合蛙跳算法及其相關算法

SFLA是一類啟發式的智能優化算法，它通過某一個數學函數進行啟發式搜索，以尋求問題的最優解。下面先對其相關的模因演算法及PSO進行簡單介紹。

2.1 模因演算法

模因（Memetic）一詞是由meme而來，一般理解為“文化基因”，因此模因算法（MA）也稱為文化基因算法。對應于遺傳算法，MA模擬了人類文明的發展過程。它采用與遺傳算法相似的操作流程，并在此基礎上通過局部鄰域搜索使每次迭代的所有個體都達到局部最優，其流程如圖3所示。

實際上，MA并沒有具體的數學模型，它更多體現為一種思想或框架［12］。MA在搜索策略上具有較大的變通性，其全局搜索階段的進化算子和局部搜索時的個體學習可采用多種組合，各種常規或智能優化算法都可以納入到MA的框架中。SFLA就是基于MA的這個特點，結合PSO而產生的。

2.2 粒子群算法

PSO是一種模擬鳥類群體性覓食行為的啟發式全局優化算法。鳥群中的每只鳥都稱為“粒子”，它們同時具有速度和位置兩個特征，在解空間中以規定的規則移動，經過若干次迭代后得到所求問題的全局最優解。在每一次迭代中，粒子通過跟蹤兩個位置更新自己。一個是粒子自身所經歷的最好位置，即個體最好位置；另一個是群體中所有粒子所經歷過的最好位置，即全局最好位置。

圖3 MA流程圖Fig.3 Flowchart of MA

PSO的實現步驟如下［13］:

步驟1 參數初始化。對粒子群的隨機位置、速度及適應度函數等進行初始設定。

步驟2 計算每個粒子的適應度值。將每個粒子的初始位置暫時作為該粒子所經歷的最好位置Ypbest，將其中適應度值最大的粒子的位置Ygbest暫時作為全局所經歷的最好位置。

步驟3 對粒子的速度和位置進行更新。

式中:vk（d+1）和vk（d）分別表示粒子k第d次迭代中的當前速度和先前速度；Yk（d）為粒子k第d次迭代的位置；ω為慣性系數；c1和c2為加速常數；r1和r2分別為區間（0，1）上的兩個隨機數，且相互獨立。

更新后粒子的位置為

步驟4 將Yk（d+1）的適應度值與Ypbest的適應度值進行比較，若較大，則將Yk（d+1）作為該粒子當前的最優位置。

步驟5 將Yk（d+1）的適應度值與Ygbest的適應度值進行比較，若較大，則將Yk（d+1）作為當前的全局最優位置。

步驟6 判斷是否滿足結束條件。若完成，輸出最優解，否則轉至步驟3.

2.3 混合蛙跳算法

SFLA模擬青蛙群體覓食行為中信息傳遞的過程，根據每只青蛙位置的不同，將它們分為多個子種群。同一子種群內進行局部深度搜索，距離食物最遠的青蛙會根據種群內距離食物最近的青蛙提供的信息調整自身位置，向食物靠近［14］。每隔一段時間，所有種群會進行全局的信息交流，并根據當前青蛙的位置重構種群。這樣的局部搜索與全局信息交換更替進行，直至找到食物［6］。

SFLA可以分為4部分來實現［15］，整體流程如圖4所示，具體步驟如下:

1）初始化。

步驟1 初始化種群解（青蛙）的總數F，子種群個數m，每個子種群中解的個數k，解的維數S，子種群局部搜索次數N，混合迭代次數G，解的最大移動步長Dmax，適應度函數fitness等參數。

步驟2 在可行解區域內，隨機生成F個解，組成初始種群X=［X1，X2，…，XF］，并計算每個解的適應度值fitness（X）.

圖4 SFLA流程圖Fig.4 Flowchart of SFLA

2）子種群的劃分。

步驟3 根據適應度對種群中的所有解降序排列，記錄適應度最大的解Xg，暫時作為整個種群中的最優解，即全局最優解。

步驟4 將排序后的解按照下述方式分成m個子種群，每個子種群中含有k個解。

第1個解被放入第1個子種群，第2個解被放入第2個子種群，一直到第m個解被放入第m個子種群。接著，第m+1個解又被放入第1個子種群，依次類推，直至將所有解分配完畢。

步驟5 記錄下每個子種群中具有最大適應度值和最小適應度值的解，分別記為Xb和Xw，簡稱為最優解和最差解，暫時作為該子種群的最優解和最差解。

3）局部搜索。

步驟6 在各個子種群中，通過（13）式更新該子種群中的最差解。解的移動步長為

式中:rand為（0，1）之間的一個隨機數；t為局部搜索次數，t=1，2，…，N.更新后最差解為

式中:|D（t）|≤Dmax.

步驟7 在各子種群中，將Xw（t+1）的適應度與Xw（t）的適應度進行比較。若較大，則用Xw（t+1）代替原有的Xw（t），轉入步驟9；否則，由（14）式計算最差解Xw的移動步長

步驟9 判斷是否完成了預定的局部搜索次數。若完成，進入混合運算，否則轉至步驟6.

4）混合運算。

步驟10 將所有子種群的解重新混合。

步驟11 判斷是否完成了預定的混合迭代次數。若完成，輸出最優解，否則轉至步驟3.

3 基于SFLA的多模盲均衡算法

將SFLA引入到MMA中，以搜索全局最優的MMA均衡器初始權向量，從而提高盲均衡算法的收斂速度并減小穩態剩余誤差，使均衡具有良好且穩定的效果。SFLA-MMA的基帶等效模型如圖5所示，s（n）為發送信號，Nn（n）為高斯白噪聲。

圖5 SFLA-MMA基帶等效模型Fig.5 Baseband equivalent model of SFLA-MMA

在SFLA中，設隨機產生的初始青蛙種群為X=［X1，X2，…，XF］，其中每只青蛙的初始位置Xi（1≤i≤F）對應均衡器的一個權向量，經過多次局部搜索和混合迭代，最終找到距離食物最近的那個位置向量，這個過程類似于盲均衡算法通過多次迭代，尋找代價函數最小值時的最優權向量。

SFLA-MMA的核心是將MMA代價函數的倒數作為SFLA的適應度函數，即

式中:Xi表示F只青蛙中第i只的位置向量。

SFLA-MMA通過搜索適應度函數的全局極大值點來尋找種群中青蛙的最佳位置向量，并將它作為MMA的初始權向量。

4 仿真實驗與分析

在64-QAM和32-APSK兩種調制方式下，對SFLA-MMA進行仿真實驗驗證，并與CMA，MMA進行比較。為了驗證將SFLA與PSO引入到MMA均衡性能，現采用第3節的思想構建一種基于PSO的多模盲均衡算法，即PSO-MMA.并將（15）式作為它的適應度函數進行仿真。

1）SFLA-MMA仿真參數。種群總數F=50，子種群個數m=5，每個子種群內青蛙的個數k=10，解的維數S=11，局部搜索次數N=20，混合迭代次數G=10，最大位移步長Dmax=0.01.

2）PSO-MMA仿真參數。種群總數R=50，慣性系數ω=1.2，加速常數c1=c2=2，迭代次數Q=50.

3）其他參數。信道h=［0.965 6 -0.090 6 0.057 8 0.236 8］，接收信噪比SNR=30 dB，均衡器采用11階橫向抽頭結構，CMA和MMA的中心抽頭系數初始化為1，其他抽頭系數初始化為0，所有仿真的最大迭代次數均為iter=1×104，Monte Carlo次數均為M=3×103.

實驗1 在64-QAM調制下，CMA和MMA的迭代步長均為1×10-6，SFLA-MMA和PSO-MMA的迭代步長均為1×10-7，仿真結果如圖6所示。

圖6 64-QAM仿真結果Fig.6 Simulation results of 64-QAM signals

實驗2 在32-APSK調制下，CMA和MMA的迭代步長均為1×10-5，SFLA-MMA和PSO-MMA的迭代步長均為5×10-6，仿真結果如圖7所示。

表1為兩個實驗在相同的信噪比下，收斂迭代次數與穩態誤差的統計表。

圖6、圖7及表1表明，在64-QAM調制方式下，SFLA-MMA的收斂速度較MMA提高了將近2.5倍，穩態誤差降低了15 dB；在32-APSK調制方式下，SFLA-MMA的收斂速度較MMA提高了約6倍，穩態誤差降低了14 dB.兩種調制方式的輸出星座圖中，SFLA-MMA及PSO-MMA的輸出星座圖明顯比CMA和MMA清晰且緊湊，沒有出現相互混疊的情況。這是因為CMA和MMA的穩態誤差會隨調制階數的提高而越來越大，而SFLA-MMA的穩態誤差受調制階數的影響很小。所以對于高階多模信號，SFLA-MMA的優勢十分明顯。因此，對于高階多模信號的均衡，SFLA-MMA具有更快的收斂速度和更小的穩態誤差。

圖7 32-APSK仿真結果Fig.7 Simulation results of the 32-APSK signals

表1 不同調制方式下各算法的收斂迭代次數與穩態誤差統計值Tab.1 Convergence iteration times and steady-state errors for each algorithm with different modulation methods

5 結論

本文提出的基于SFLA的MMA，克服了傳統的盲均衡算法收斂速度慢、穩態誤差大及盲相位問題，提高了均衡性能。仿真結果表明，對于高階多模64-QAM和32-APSK信號，SFLA-MMA與傳統的CMA和MMA相比，具有更快的收斂速度和更低的穩態誤差。

（

）

［1］ Yang J，Werner J J，Dumont G A.The multimodulus blind equal-ization and its generalized algorithm［J］.IEEE Journal on Selected Areas in Communications，2002，20（5）:997-1014.

［2］ GAO Yuan，QIU Xin-yun.A new variable step size CMA blind equalization algorithm［C］∥IEEE Chinese Control and Decision Conference.Taiyuan，China:IEEE，2012:315-317.

［3］ Jenq-Tay Yuan.Equalization and carrier phase recovery of CMA and MMA in blind adaptive receivers［J］.IEEE Transactions on Signal Processing，2010，58（6）:3206-3217.

［4］ Java Ebrahimi，Seyed Hossein Hosseinian，Gevorg B Gharehpetian.Unit commitment problem solution using shuffled frog leaping algorithm［J］.IEEE Transactions on Power System，2011，26（2）: 573-581.

［5］ Amiri B，Fathian M，Maroosi A.Application of shuffled frog-leaping algorithm on clustering［J］.International Journal of Advanced Manufacturing Technology，2009，45（1/2）:199-209.

［6］ 駱劍平，李霞，陳泯融.混合蛙跳算法的Markov模型及其收斂性分析［J］.電子學報，2010，38（12）:2875-2880. LUO Jian-ping，Li Xia，CHEN Min-rong.The Markov model of shuffled frog leaping algorithm and its convergence analysis［J］. Acta Electronica Sinica，2010，38（12）:2875-2880.（in Chinese）

［7］ Eusuff M M，Lansey K E.Optimization of water distribution network design using shuffled frog leaping algorithm［J］.Journal of Water Resources Planning and Management，2003，129（3）: 210-225.

［8］ 陳杰，潘峰，王光輝.粒子群優化算法在動態優化中的研究現狀［J］.智能系統學報，2009，4（3）:189-198. CHEN Jie，PAN Feng，WANG Guang-hui.Review of the PSO research in dynamic environment［J］.CAAI Transactions on Intelligent Systems，2009，4（3）:189-198.（in Chinese）

［9］ Yao M，Zhang Q T.Diversity reception of DAPSK over generalized fading channels［J］.IEEE Transactions on Wireless Communications，2005，4（4）:1834-1845.

［10］ Christian Hager，Alex Alvarado.Design of APSK constellations for coherent optical channels with Nonlinear Phase Noise［J］. IEEE Transactions on Communication，2013，61（8）:3362-3373.

［11］ 郭業才.模糊小波神經網絡盲均衡理論、算法與實現［M］.北京:科學出版社，2011:48-52. GUO Ye-cai.The theory，algorithm and implement of fuzzy wavelet neural network blind equalization［M］.Beijing:Science press，2011:48-52.（in Chinese）

［12］ 段海濱，張翔銀，徐春芳.仿生智能計算［M］.北京:科學出版社，2011:130-136. DUAN Hai-bin，ZHANG Xiang-yin，XU Chun-fang.Bio-inspired computing［M］.Beijing:Science Press，2011:130-136.（in Chinese）

［13］ Li Chang-he，Yang Sheng-xiang.A self-learning particle swarm optimizer for global optimization problems［J］.IEEE Transactions on Systems，2012，42（3）:627-646.

［14］ Elbeltagi E，Hegazy T，Grierson D.Comparison among five evolutionary-based optimization algorithm［J］.Advanced Engineering Informatics，2005，19（1）:43-53.

［15］ Eusuff M，Lansey K，Pasha F.Shuffled frog leaping algorithm:a memetic meta-heuristic for discrete optimization［J］.Engineering Optimization，2006，38（2）:129-154

A Multi-modulus Blind Equalization Algorithm Based on Shuffled Frog Leaping Algorithm

GUO Ye-cai1，2，ZHANG Miao-qing2
（1.Jiangsu Key Laboratory of Meteorological Observation and Information Processing，Nanjing University of Information Science&Technology，Nanjing 210044，Jiangsu，China；2.Jiangsu Collaborative Innovation Center on Atmospheric Environment and Equipment，Nanjing 210044，Jiangsu，China）

For slow convergence speed，large steady mean square error（MSE），and blind phase of the constant modulus blind equalization algorithm（CMA），a multi-modulus blind equalization algorithm based on shuffled frog leaping algorithm（SFLA-MMA）is proposed，which combines the basic idea of intelligent optimization algorithm and introduces the individual own evolution and social behavior among individuals into the blind equalization technology.In the proposed algorithm，the reciprocal of the cost function of multi-modulus blind equalization algorithm（MMA）is defined as the fitness function of the shuffled frog leaping algorithm（SFLA），the position vector of the frog individual in the frog group is re-garded as the initial weight vector of MMA.The optimum location vector of the frog groups is searched using the global information sharing mechanism and local depth search ability of SFLA，and used as the initial optimum weight vector of the MMA.The optimal weight vector of MMA is obtained by updating the weight vector of MMA.The proposed SFLA-MMA is simulated with the higher-order multi-modulus QAM and APSK signals.The simulation results show that，compared with CMA，MMA，and the multi-modulus blind equalization algorithm based on particle swarm optimization algorithm（PSO-MMA），the proposed SFLA-MMA has the fastest convergence speed，the smallest MSE，and the clearest constellations of output signals.

information processing technology；multi-modulus algorithm；shuffled frog leaping algorithm；intelligence optimization algorithm；optimal weight vector

TN911.7

A

1000-1093（2015）07-1280-08

10.3969/j.issn.1000-1093.2015.07.017

2014-09-12

全國優秀博士論文作者專項資金項目（200753）；江蘇省高校自然科學基金項目（13KJA510001）；高校科研成果產業化推進項目（JHB 2012-9）；江蘇省高校“信息與通信工程”優勢學科建設工程項目（2014年）

郭業才（1962—），男，教授，博士生導師。E-mail:guo-yecai@163.com；張苗青（1986—），男，碩士研究生。E-mail:nidecc@gmail.com