求解多輸入多輸出檢測新算法
——遺傳粒子群優化

黑永強 李曉輝 易克初 郁光輝

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

1. 引 言

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

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

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

2. 系統模型

假定一個MIMO系統有Nt根發射天線和Nr根接收天線，MIMO系統相關信道模型如圖1所示。

圖1 MIMO系統相關信道模型

(1)

H=KRHCKT

(2)

式中:HC為不相關的復高斯變量信道矩陣；KT和KR分別滿足

(3)

在此相關信道模型假設下，接收到的信號復向量為

r=Hx+n

(4)

對于MIMO系統，最優的最大似然檢測(ML)的輸出向量為

(5)

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

3. MIMO檢測問題求解

采用進化算法求解MIMO系統檢測，首先需要解決以下兩個問題：

1) 所優化的目標函數是什么？

2) 如何定義進化算法中的個體(優化變量)？

(6)

則有下式成立

rp=Hpxp+np

(7)

3.1 PSO求解MIMO檢測問題

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

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

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

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

(8)

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

圖2 粒子定義示意圖

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

適應度函數定義：PSO算法通過適應度函數來評估粒子的優劣，根據粒子的定義，適應度函數可以定義為:

(9)

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

3.2 GA算法求解MIMO檢測問題

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

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

圖3 GA算法求解MIMO檢測關鍵步驟流程

3.3 GPSO算法求解MIMO檢測問題

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

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

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

rMMSE=Gp·rp

(10)

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

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

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

(11)

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

為了便于分析，圖4給出新算法進化機制的關鍵步驟。

圖4 GPSO進化算法關鍵步驟流程

采用上述進化機制，GPSO算法求解MIMO檢測問題的關鍵步驟如下：

step 1 設粒子群規模為Q，根據式(10)初始化粒子種群，并隨機產生各粒子的速度。

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

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

step 4 對于次優粒子，根據式(8)實施改進PSO進化。

step 5 淘汰適應度值較低的粒子，并重新隨機產生新的粒子以彌補空缺。

step 6 重復step3 ～step5步,直到滿足性能要求或達到預先設定最大迭代次數T。

step 7 輸出全局極值以及相應的檢測結果。

4. 實驗結果分析

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

實驗1分析比較GPSO算法和經典的檢測算法以及進化算法的誤碼性能

圖5 比較GPSO算法和經典算法誤碼性能曲線

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

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

圖6 比較GPSO算法和進化算法誤碼性能曲線

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

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

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

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

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

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

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

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

5. 結 論

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

[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系統中K-best球形譯碼算法研究[J].電波科學學報，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] 芮賢義, 金榮洪, 耿軍平.相關MIMO信道下空間分集系統中多用戶分集性能[J]. 電波科學學報, 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] 曾二林, 朱世華, 廖學文. 基于自適應空分復用的分組多用戶分集方案[J]. 電波科學學報, 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)