求解多輸入多輸出檢測新算法
——遺傳粒子群優(yōu)化

黑永強(qiáng) 李曉輝 易克初 郁光輝

(1.西安電子科技大學(xué)ISN國家重點實驗室，陜西 西安 710071； 2.深圳市中興通訊技術(shù)有限公司，廣東 深圳 518057)

1. 引 言

對于多輸入多輸出(MIMO)系統(tǒng)而言，最大似然譯碼(ML)是最佳的接收算法，但是其計算量隨發(fā)射天線數(shù)呈指數(shù)增長，這就大大限制了ML在實際系統(tǒng)中的應(yīng)用，因而尋找次優(yōu)的MIMO檢測算法一直是業(yè)內(nèi)探索的目標(biāo)。為了解決這一問題，學(xué)者提出了許多次優(yōu)的線性和非線性的算法[1-4]，然而這些算法難以取得較好的性能或者計算復(fù)雜度過高。目前基于凸優(yōu)化MIMO檢測算法引起了廣泛關(guān)注[5-7]，其主要原因是該方法能夠以較低的復(fù)雜度獲取較好的性能，然而如何保證目標(biāo)函數(shù)的凸性以及如何進(jìn)行合理的松弛則是該算法的一大難題。

近年來許多學(xué)者開始嘗試用進(jìn)化算法求解檢測問題，這主要是因為進(jìn)化算法具有簡單方便，運行速度快，實現(xiàn)簡潔，調(diào)整的參數(shù)少等優(yōu)勢。目前，這一方面的研究包括將離散粒子群算法、遺傳算法、克隆選擇算法等用于多用戶檢測問題[8-10]，但是上述研究中進(jìn)化算法僅適用于用戶配置單天線的狀況，而如何采用進(jìn)化算法求解多天線MIMO系統(tǒng)檢測問題則亟待進(jìn)一步研究。上述研究中僅注重將進(jìn)化算法應(yīng)用于檢測問題求解，而并未深入分析進(jìn)化機(jī)制的優(yōu)勢和缺陷，因而，求解檢測問題的性能將受限，如何設(shè)計出新的更加高效的進(jìn)化算法，能夠進(jìn)一步提高求解問題的效率，這正是研究的出發(fā)點。

首先將粒子群優(yōu)化算法(PSO)和遺傳算法(GA)應(yīng)用于求解MIMO系統(tǒng)檢測問題。在此基礎(chǔ)之上，提出新的遺傳粒子群優(yōu)化(GPSO)進(jìn)化算法以克服PSO算法和GA算法求解MIMO檢測問題的不足。新算法的求解思路是：將以MMSE估計的檢測符號集作為初始種群，并根據(jù)粒子的適應(yīng)度值將粒子分為精英粒子，次優(yōu)粒子以及糟糕粒子三部分，然后對于精英粒子和次優(yōu)粒子分別實施極值擾動和PSO進(jìn)化策略，而對糟糕粒子實施淘汰后并重新產(chǎn)生從而改善算法的進(jìn)化機(jī)制。仿真結(jié)果表明所提算法的有效性。

2. 系統(tǒng)模型

假定一個MIMO系統(tǒng)有Nt根發(fā)射天線和Nr根接收天線，MIMO系統(tǒng)相關(guān)信道模型如圖1所示。

圖1 MIMO系統(tǒng)相關(guān)信道模型

(1)

H=KRHCKT

(2)

式中:HC為不相關(guān)的復(fù)高斯變量信道矩陣；KT和KR分別滿足

(3)

在此相關(guān)信道模型假設(shè)下，接收到的信號復(fù)向量為

r=Hx+n

(4)

對于MIMO系統(tǒng)，最優(yōu)的最大似然檢測(ML)的輸出向量為

(5)

式中，Ω為星座符號集。但ML算法由于需要遍歷整個發(fā)射符號集空間，其復(fù)雜度O(ΩNt)為星座大小和天線數(shù)目的指數(shù)函數(shù)，因此，在實際中一般難以接受。

3. MIMO檢測問題求解

采用進(jìn)化算法求解MIMO系統(tǒng)檢測，首先需要解決以下兩個問題：

1) 所優(yōu)化的目標(biāo)函數(shù)是什么？

2) 如何定義進(jìn)化算法中的個體(優(yōu)化變量)？

(6)

則有下式成立

rp=Hpxp+np

(7)

3.1 PSO求解MIMO檢測問題

粒子群優(yōu)化算法(PSO)[12]，由Eberhart和Kennedy于1995年提出，是一種模擬自然界鳥類、魚群等尋找食物過程而提出的隨機(jī)搜索算法。粒子群算法是一種基于群體的優(yōu)化算法，其中每個粒子代表所研究問題的一個可行解,它具有位置和速度兩個基本特征。每個粒子在搜索空間中以一定的速度飛行，并根據(jù)對個體和集體飛行經(jīng)驗的綜合分析來動態(tài)調(diào)整其速度，然后更新個體當(dāng)前的位置，每個粒子根據(jù)下面兩個公式來更新自己的速度與位置

vi(τ+1)=wvi(τ)+c1r1(pbesti(τ)-xi(τ))+

c2r2(gbest(τ)-xi(τ))

xi(τ+1)=xi(τ)+vi(τ+1)

(8)

式中：pbesti(τ)和gbest(τ)分別表示個體極值和全局極值；c1和c2是加速度常數(shù)；r1和r2是服從[0,1]分布的隨機(jī)數(shù)；vi(τ)受限于[-VmaxVmax]；w是慣性常量。

圖2 粒子定義示意圖

圖2所示粒子采用浮點編碼的優(yōu)勢在于能夠有效擴(kuò)展算法的求解范圍，可以推廣到高階調(diào)制。此時，各浮點編碼元素可映射為最近的星座點。

適應(yīng)度函數(shù)定義：PSO算法通過適應(yīng)度函數(shù)來評估粒子的優(yōu)劣，根據(jù)粒子的定義，適應(yīng)度函數(shù)可以定義為:

(9)

適應(yīng)度函數(shù)值越小,則表明該粒子與最優(yōu)檢測向量之間的歐式距離越短，整個尋優(yōu)過程中的全局最優(yōu)粒子即代表PSO算法所得出的檢測向量。根據(jù)粒子和適應(yīng)度函數(shù)的定義并根據(jù)式(8)中的進(jìn)化過程，可以實現(xiàn)PSO算法求解MIMO系統(tǒng)檢測。

3.2 GA算法求解MIMO檢測問題

遺傳算法(GA)是一種基于生物遺傳和進(jìn)化機(jī)制的自適應(yīng)概率優(yōu)化技術(shù)[13]。它通過模擬自然選擇和遺傳中發(fā)生的選擇、交叉和變異等現(xiàn)象，從一個初始種群出發(fā)，經(jīng)過隨機(jī)選擇、交叉和變異操作，產(chǎn)生一群更適應(yīng)環(huán)境的個體，使群體進(jìn)化到搜索空間中越來越好的區(qū)域。經(jīng)過這樣一代又一代地不斷繁衍進(jìn)化，最后得到一群最適合環(huán)境的個體，從而求得問題的最優(yōu)解。

類似PSO算法檢測過程，采用GA算法求解MIMO系統(tǒng)檢測問題時，GA中的個體與PSO中的粒子相對應(yīng)，而適應(yīng)度函數(shù)則采用相同的定義，所不同的是PSO算法通過更新粒子的位置和速度來尋優(yōu)，而GA算法的尋優(yōu)則通過遺傳操作完成。GA求解MIMO檢測的基本過程如下：首先隨機(jī)初始產(chǎn)生Q個體，其中每一個體代表發(fā)送數(shù)據(jù)的一個估計值，然后計算個體的適應(yīng)度值，并根據(jù)適應(yīng)度值的優(yōu)劣選擇個體用于雜交。在每一代的進(jìn)化過程中，用于遺傳操作，即交叉、變異，生成下一代個體，也即子代。經(jīng)過若干代進(jìn)化之后，算法收斂于最好的個體，該個體作為GA算法所求出的最優(yōu)檢測解向量。GA算法求解MIMO檢測過程的關(guān)鍵步驟如圖3所示。

圖3 GA算法求解MIMO檢測關(guān)鍵步驟流程

3.3 GPSO算法求解MIMO檢測問題

PSO算法通過進(jìn)化過程經(jīng)驗記憶以及粒子之間的信息共享發(fā)揮作用，因而PSO算法具有很強(qiáng)的全局搜索能力，但由于所有的粒子都參與每一代進(jìn)化未免會導(dǎo)致進(jìn)化效率的降低。相反，GA在每一代中通過不斷選擇優(yōu)秀的個體而丟棄質(zhì)量較差的個體來完成進(jìn)化，故GA算法具有很強(qiáng)的局部搜索能力，但GA算法中個體之間缺乏信息交互，因此，其全局尋優(yōu)能力較弱以及收斂速度較慢。利用GA和PSO算法的各自優(yōu)勢，給出一種融合GA和PSO進(jìn)化機(jī)制的新遺傳粒子群進(jìn)算法，并將其應(yīng)用于求解MIMO系統(tǒng)檢測，下文將給出算法的詳細(xì)求解過程。

根據(jù)中債資信地方政府及城投行業(yè)研究團(tuán)隊對2016年政府類投融資平臺-江蘇篇調(diào)研結(jié)果知，截止2015年末，江蘇省政府債務(wù)率68.5%，債務(wù)風(fēng)險總體可控，江蘇省內(nèi)融資平臺直接間接融資渠道較為通暢，2015年融資成本較此前明顯降低，綜合融資成本6%-8%之間。2017年后江蘇省融資平臺逐漸出現(xiàn)融資難、成本高。

初始化：初始化種群選取合適與否將直接關(guān)系到進(jìn)化算法的迭代次數(shù)與收斂速度，如果采用常規(guī)的隨機(jī)產(chǎn)生初始種群，則算法求解檢測的計算效率很難保證。為了解決這一問題,采用接收信號MMSE估計值rMMSE作為初始種群，從而加快新算法尋找最優(yōu)解的速率。

rMMSE=Gp·rp

(10)

粒子評估：在進(jìn)化過程中，粒子的質(zhì)量難免會有優(yōu)劣之分。借鑒GA算法個體評估原理，將對每一代進(jìn)化的粒子根據(jù)適應(yīng)度值進(jìn)行排序，然后將這些粒子進(jìn)行劃分為三部分：精英粒子、次優(yōu)粒子、以及糟糕粒子，并對這些粒子分別采取各自的尋優(yōu)策略。

xg+1(τ+1)=xg(τ)+(1-rd[1-

(τ/T)])vg+1(τ)

(11)

從式(11)中可看出，在搜索初期，對于較小的rd值時，精英粒子相對擾動空間較大；而在搜索后期，τ接近于T時，精英粒子在較小的空間內(nèi)擾動。式(11)中自適應(yīng)的調(diào)節(jié)精英粒子的變化范圍能夠保證停滯的精英粒子可以重新激活，并以更高的概率去尋找全局最優(yōu)值。

為了便于分析，圖4給出新算法進(jìn)化機(jī)制的關(guān)鍵步驟。

圖4 GPSO進(jìn)化算法關(guān)鍵步驟流程

采用上述進(jìn)化機(jī)制，GPSO算法求解MIMO檢測問題的關(guān)鍵步驟如下：

step 1 設(shè)粒子群規(guī)模為Q，根據(jù)式(10)初始化粒子種群，并隨機(jī)產(chǎn)生各粒子的速度。

step 2 根據(jù)式(9)計算粒子的適應(yīng)度函數(shù)，找出個體極值和全局極值。

step 3 對于精英粒子，根據(jù)式(11)實施增強(qiáng)極值擾動。

step 4 對于次優(yōu)粒子，根據(jù)式(8)實施改進(jìn)PSO進(jìn)化。

step 5 淘汰適應(yīng)度值較低的粒子，并重新隨機(jī)產(chǎn)生新的粒子以彌補(bǔ)空缺。

step 6 重復(fù)step3 ～step5步,直到滿足性能要求或達(dá)到預(yù)先設(shè)定最大迭代次數(shù)T。

step 7 輸出全局極值以及相應(yīng)的檢測結(jié)果。

4. 實驗結(jié)果分析

采用第1部分描述的MIMO相關(guān)信道模型Nt=4,Nr=4。為了驗證所提算法的有效性，仿真中同時引入了ZF算法、MMSE算法、最大似然(ML)算法。另外，PSO算法、GA算法和GPSO算法三種算法的公共參數(shù)如下：種群規(guī)模Q=80，最大迭代次數(shù)T=10。對于PSO，慣性常數(shù)w在[0.9，0.4]區(qū)間內(nèi)線性遞減，加速度常數(shù)c1=c2=2。對于遺傳算法選取變異概率和交叉概率分別為0.05和0.8，其他參數(shù)均與PSO算法相同。而所提算法中的粒子淘汰率pt=0.5.

實驗1分析比較GPSO算法和經(jīng)典的檢測算法以及進(jìn)化算法的誤碼性能

圖5 比較GPSO算法和經(jīng)典算法誤碼性能曲線

圖5比較了GPSO算法和經(jīng)典檢測算法的誤碼性能。由圖5可知，最大似然檢測算法(ML)是最優(yōu)的，但是其指數(shù)復(fù)雜度也是最高的。GPSO算法相比較其他算法獲得一定的信噪比增益，當(dāng)種群數(shù)目由Q=50增加到Q=80，誤碼性能得到了明顯的改善。而MMSE算法相對于ZF算法有一定的增益，這是因為MMSE算法相比ZF算法增加了接收SNR的估計。ZF算法的性能優(yōu)于QR算法在于前者可以使得天線之間的干擾迫零，然而迫零矩陣引入了對噪聲的放大，因此，其誤碼性能也較差。QR檢測算法受誤差傳播的影響故其誤碼性能最差。

圖6比較了所提算法以及另外兩種進(jìn)化算法的誤碼率曲線。需要指出的是圖6中三種檢測算法均采用MMSE估計值作為初始種群。可以看出，GPSO檢測算法的性能要明顯優(yōu)于PSO檢測算法和GA檢測算法，從而體現(xiàn)出所提算法所采用進(jìn)化機(jī)制的有效性。這也同樣說明PSO和GA算法的進(jìn)化機(jī)制均存在一定缺陷。另外PSO檢測算法誤碼性能要優(yōu)于GA檢測算法，這是因為相比GA算法，PSO算法具有更強(qiáng)的全局尋優(yōu)能力。另外，可以看出，隨著種群數(shù)目Q的增加，三種算法的誤碼性能均得到一定的改善。

圖6 比較GPSO算法和進(jìn)化算法誤碼性能曲線

實驗2分析迭代次數(shù)和粒子數(shù)目對GPSO算法誤碼性能的影響

圖7 迭代次數(shù)對GPSO算法誤碼性能影響曲線

圖7給出了迭代次數(shù)對GPSO算法誤碼性能影響曲線?？梢钥闯?，隨著迭代次數(shù)的增加，誤碼性能逐步得到改善。其原因在于，在進(jìn)化的過程中隨著迭代次數(shù)的增加不斷能夠發(fā)現(xiàn)更優(yōu)的粒子。但是隨著迭代次數(shù)的進(jìn)一步增加，誤碼率改善效果逐漸變得不明顯，比如圖中10次迭代相比較5次迭代所得增益沒有5次迭代相比較1次迭代所得增益的效果顯著。因此，在實際系統(tǒng)中可以根據(jù)需求來確定進(jìn)化過程所需的最大迭代次數(shù)。

圖8給出粒子數(shù)目對GPSO算法誤碼性能影響的曲線。由圖可知，粒子數(shù)目越多，GPSO算法下的誤碼率曲線就越接近ML算法誤碼率曲線。這是因為更多數(shù)目的粒子參與進(jìn)化，必然導(dǎo)致算法尋找到最優(yōu)解的概率增加，因而誤碼性能得到改善。對比圖7和圖8可以發(fā)現(xiàn)，誤碼性能的改善既可以通過增加進(jìn)化的迭代次數(shù)也可以通過加大粒子種群的數(shù)目來獲得，因此，在實際系統(tǒng)中，可以根據(jù)要求合理地選取這兩個參數(shù)。

圖8 粒子數(shù)目對GPSO算法誤碼性能影響曲線

實驗3所提算法計算復(fù)雜度分析與比較

由第一節(jié)可知，ML算法由于需要遍歷所有可能的發(fā)射序列，其復(fù)雜度大小為Q(ΩNt)。這在發(fā)射天線數(shù)目較多或者采用較高的調(diào)制方式時，令人無法接受。相比較ML算法，ZF、MMSE算法能夠顯著降低算法的復(fù)雜度，大小近似為O(Nr3)，其中Nr為接收天線數(shù)目，但是ZF、MMSE算法復(fù)雜度降低是以性能損失為代價的。

對于上文所給出的三種算法，假定種群數(shù)目P，每個粒子處于D維空間及最大迭代數(shù)目為T。初始化粒子群以及計算適應(yīng)度函數(shù)值大概需要的計算復(fù)雜度為O(PD)，另外對于更新全局極值，個體極值以及每個粒子其位置和速度所需要的復(fù)雜度分別可以近似為O(P),O(P)和O(PD)。因此，PSO算法每一代進(jìn)化過程中其關(guān)鍵步驟所需的復(fù)雜度為O(PD)+O(P)+O(P)+O(PD)=O(2P+2PD).從而PSO算法的整體計算復(fù)雜度為：O(T(2P+2PD))。對于GA而言，遺傳操作的三個關(guān)鍵算子選擇、交叉、變異的時間復(fù)雜度分別為：O(P),O(PD)和O(PD)，因此，GA算法總的時間復(fù)雜度為O(T(P+3PD))。對于所提算法而言，初始化種群個體所需的計算復(fù)雜度近似為O(Nr2)，而粒子的適應(yīng)度值進(jìn)行排序引入的額外復(fù)雜度為O(P)，每個粒子附近的次優(yōu)粒子的更新需要的復(fù)雜度為O(P)，因此，所提算法的計算復(fù)雜度為O(T(4P+PD)+Nr2)。忽略系數(shù)影響的條件下，PSO算法、GA算法以及所提算法的計算復(fù)雜度分別可以近似O(TPD),O(TPD),O(TPD+Nr2).根據(jù)選取粒子或個體的定義可知，P，D，T均隨著發(fā)射空間維數(shù)Nt的增加而線性增加，則三種算法的復(fù)雜度分別近似為O(Nt3),O(Nt3),O(Nt3+Nr2).可見，相比ML算法，三種算法具有較低的復(fù)雜度；而考慮到獲得相同的性能前提下所提算法所需迭代次數(shù)要少于PSO算法，因此，所提算法的計算復(fù)雜度相對于PSO算法以及GA算法基本上相差不大。

5. 結(jié) 論

提出了一種求解MIMO系統(tǒng)檢測新算法：遺傳粒子群優(yōu)化算法，新算法通過有效地融合GA和PSO進(jìn)化機(jī)制，從而加快了算法的求解效率。仿真結(jié)果表明：所提算法應(yīng)用于MIMO系統(tǒng)檢測十分有效，在種群規(guī)模Q=80和最大迭代次數(shù)T=10時，相比最大似然檢測算法在誤碼率為10-2時SNR相差約為2 dB。而與基于PSO檢測算法和基于GA檢測算法相比，在相同的種群數(shù)目和迭代次數(shù)下，能夠獲得更好的誤碼性能。有望將所提算法進(jìn)一步推廣應(yīng)用于多用戶MIMO檢測場景[14-15]，而如何進(jìn)一步改善算法的進(jìn)化機(jī)制則是今后研究的內(nèi)容。

[1] WUBBEN D, BOHNKE R,RINAS I. Efficient algorithm for decoding layered space-time codes [J]. IEE Electronics Letter, 2001, 37(22):1348-1350.

[2] ZHANG J K, ALEKSANDAR K, MAX W. Equal-diagonal qr decomposition and its application to precoder dsign for successive cancellation detection. ieee transactions on information theory [J].2005, 51(1):154-172.

[3] 林 云，王 宇. MIMO系統(tǒng)中K-best球形譯碼算法研究[J].電波科學(xué)學(xué)報，2009, 24(1):141-147.

LIN Yun, WANG Yu. Study on K-best sphere decoding algorithm in MIMO system [J]. Chinese Journal of Radio Science, 2009, 24(1): 144-147. (in Chinese)

[4] SHEN C, ZHANG H R, LIN D. Detection algorithm improving VBLAST performance over error propagation [J].IEEE Electronics Letters, 2003, 39(6):1007-1008.

[5] SIDIROPOULOS N D, LUO Z Q. A semidefinite relaxation approach to mimo detection for high-order qam constellations [J]. IEEE Signal Processing Letters, 2006, 13(9):525-528.

[6] WEI C H, CHANG T H, MA W K. A linear fractional semidefinite relaxed ML approach to blind detection of 16-QAM orthogonal space-time block codes communications[C]//IEEE International Conference on Communications (ICC), BeiJing, 2008, 790-794.

[7] MA W K, SU C C, JALDEN J. Some results on 16-QAM MIMO detection using semidefinite relaxation[C]// IEEE International Conference on Acoustics, Speech and Signal Processing, 2008, USA, 2673-2676.

[8] BASHIR S, KHAN A A, SHAH S I. An application of ga for symbol detection in MIMO communication systems[C]//Third International Conference on Natural Computation, Hainan, China, 2007, 404-410.

[9] GAO H Y,PAN W Z. Multiuser detector based on discrete particle swarm optimization algorithm [J]. Journal of Harbin Institute of Technology, 2005, 37(9): 1303-1306.

[10] XU Yaohua, HU Yanjun. Research of ecologic system optimization algorithms for multiuser detection in CD MA communication systems [J]. Journal of Electronics and Information Technology, 2006,28(11):2111-2115.

[11] KLAUS I P, ANDERSEN J B. A Stochastic Multiple-Input-Multiple-Output Radio Channel Model for Evaluation of Space-Time Coding Algorithms[C]∥ IEEE 52nd Vehicular Technology Conference, USA, 2000, 893-897.

[12] KNENEDY J , EBERHART R. Particle swarm optimization [C]//IEEE Conference Proceedings of the International Conference on Neural Networks. Piscataway, USA,1995, 1942-1948.

[13]SAMII Y R, MICHIELSSEN E. Electromagnetic Optimization by Genetic Algorithms [M]. New York: Wiley, 1999.

[14] 芮賢義, 金榮洪, 耿軍平.相關(guān)MIMO信道下空間分集系統(tǒng)中多用戶分集性能[J]. 電波科學(xué)學(xué)報, 2008, 23(5):937-941.

RUI Xianyi, JIN Ronghong, GENG Junping. Performance of multiuser diversity in a spatial diversity system under MIMO correlated channels[J]. Chinese Journal of Radio Science,2008,23(5):937-941. (in Chinese)

[15] 曾二林, 朱世華, 廖學(xué)文. 基于自適應(yīng)空分復(fù)用的分組多用戶分集方案[J]. 電波科學(xué)學(xué)報, 2007, 22(3):424-429.

CENG Erlin, ZHU Shihua, LIAO Xuewen. A grouped multi-user diversity scheme based on adaptive space division multiplexing [J]. Chinese Journal of Radio Science, 2007, 22(3): 424-429. (in Chinese)