摘 要:針對多輸入、多輸出(MIMO)系統(tǒng)中計算最優(yōu)多用戶檢測指數(shù)的復(fù)雜度問題，提出利用遺傳算法進行MIMO多用戶檢測方案，并從組合優(yōu)化的角度，提出一種基于改進遺傳算法的MIMO多用戶檢測算法-IGA-MUD。仿真表明，IGA-MUD的性能大大優(yōu)于ZF和MMSE算法，在獲取接近最大似然檢測性能的同時，顯著降低了算法的復(fù)雜度。

關(guān)鍵詞:MIMO;多用戶檢測;遺傳算法;IGA-MUD

中圖分類號:TN911 文獻標(biāo)識碼:A

文章編號:1004-373X(2010)05-001-04

Multi-user Detection Algorithm for MIMO System Based on Improved Genetic Algorithm

SHEN Yafeng，LIU Yi，ZHANG Hailin

(State Key Laboratory of ISN，Xidian University，Xi′an，710071，China)

Abstract:Computation complexity of the optimal multi-user detection in Multiple-input Multiple-output(MIMO) system is exponential.In order to reduce the complexity，a new suboptimum multi-user detection algorithm named Improved Genetic Algorithm Multi-User Detection(IGA-MUD) is proposed.The new algorithm uses an improved genetic algorithm with combinatorial optimization.Simulation results show that the performance is improved significantly over ZF and MMSE.IGA-MUD can achieve a near-optimum performance with significantly lower computational complexity.

Keywords:MIMO;multi-user detection;genetic algorithm;IGA-MUD

0 引 言

新一代移動通信(Beyond 3G/4G)，可以提供高達100 Mb/s的數(shù)據(jù)傳輸速率，以支持新業(yè)務(wù)的不斷涌現(xiàn)。如何在有限的頻譜資源上實現(xiàn)高速率和大容量是未來移動通信系統(tǒng)的關(guān)鍵因素之一。MIMO(Multiple-input Multiple-output)技術(shù)利用多個天線實現(xiàn)多發(fā)多收，充分開發(fā)空間資源，可以成倍地提高信道容量，同時也可以提高信道的可靠性，降低誤碼率。多用戶檢測技術(shù)與MIMO結(jié)合可以進一步提高傳輸效率。但是在MIMO系統(tǒng)多用戶檢測的研究上，盡管全空間最大似然(ML)檢測能獲取最優(yōu)的檢測性能，但由于其算法復(fù)雜度太高，一直無法實際應(yīng)用，于是研究復(fù)雜度較低，性能接近ML的次優(yōu)多用戶檢測算法具有重要意義。在各種檢測方法中，MMSE(Minimum Mean Square Error，最小均方誤差)算法，ZF(Zero Forcing，迫零)算法以及文獻提出的基于QR分解MIMO檢測算法都在犧牲了一定性能的情況下降低了復(fù)雜度。近幾年來，遺傳算法在復(fù)雜優(yōu)化問題求解和工業(yè)工程領(lǐng)域應(yīng)用方面，取得了一些令人信服的結(jié)果，引起了很多人的關(guān)注。文獻研究了CDMA系統(tǒng)使用遺傳算法進行多用戶檢測的性能。本文在假設(shè)沒有信道編碼的前提下，重點分析了基于V-BLAST的MIMO上行系統(tǒng)中多用戶檢測技術(shù)，提出利用遺傳算法進行MIMO多用戶檢測，避免了直接使用最大似然帶來算法復(fù)雜度的巨大增加，與傳統(tǒng)的多用戶檢測算法相比較，提高了檢測性能。仿真結(jié)果表明，IGA-MUD(Improved Genetic Algorithm Multi-User Detection)在保證獲得接近最佳ML檢測性能的同時，計算復(fù)雜度比ML最優(yōu)多用戶檢測方法有明顯的降低。

1 系統(tǒng)模型

采用V-BLAST的MIMO系統(tǒng)上行信道結(jié)構(gòu)，如圖1所示。

圖1 MIMO上行多用戶系統(tǒng)

假定有M個用戶，每個用戶1根發(fā)射天線，N根接收天線，發(fā)射信號為x=(x1，x2，…，xM)T，第m根發(fā)射天線上的星座點集合為sm(1≤m≤M)，則接收信號為:

r=∑Mm=1Hmxm+n

(1)

式中:接收到的信號r=(r1，r2，…，rN)T，rn為第n根天線上的接收信號(1≤n≤N);Hm表示對第m個用戶而言的MIMO信道，H=(H1，H2，…，HM)，Hm=(h(1，m)，h(2，m)，…，h(N，m))，其中h(i，j)表示第j個發(fā)射天線到第i個接收天線的信道矢量，其獨立地服從復(fù)高斯分布的信道矩陣(均值為0，方差為1);n為高斯白噪聲向量(均值為0，方差σ2n由歸一化信噪比確定)。

假設(shè)已知接收端為理想信道，對于ML檢測，就是要求解:

=arg{minx∈s1×s2×…×sM‖r-Hx‖}

(2)

對于線性檢測，就是要求解:

=arg{minx∈s1×s2×…×sM‖Gr-x‖}

(3)

式中:G的取值因不同的線性檢測方法而變，對于ZF檢測，G=(HHH)-1HH;對于MMSE檢測，G=(HHH+1/γI)-1HH，γ表示信噪比，I表示單位陣。

2 本文算法IGA-MUD分析

2.1 基本遺傳算法SGA

SGA(Simple Genetic Algorithm)基本框架如下，其流程圖如圖2所示。

(1) 遺傳代數(shù)計數(shù)器初始化:Y←1;每一代群體中的個體數(shù)為X，遺傳代數(shù)為N。

(2) 隨機產(chǎn)生初始群體P(Y)。

(3) 評價群體P(Y)的適應(yīng)度。

(4) 對群體P(Y)中的個體進行選擇配對。

(5) 個體交叉重組操作:P′(Y)←P(Y)。

(6) 個體變異操作:P″(Y)←P′(Y)。

(7) 評價群體P″(Y)的適應(yīng)度。

(8) 個體選擇，復(fù)制操作:

P(Y+1)←

(9) 終止條件判斷。若不滿足終止條件，則轉(zhuǎn)到第(4)步，繼續(xù)進行遺傳操作過程;若滿足終止條件，則輸出當(dāng)前最優(yōu)個體，算法結(jié)束。

遺傳算法(Genetic Algorithm)是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法，其選擇、交叉、變異等運算都是以一種概率的方式來進行的，雖然這種概率特性會使群體中產(chǎn)生一些適應(yīng)度不高的個體，但是這個群體每次都按照優(yōu)勝劣汰的規(guī)則將適應(yīng)度較高的個體更多地遺傳到下一代，新的群體中總會更多地產(chǎn)生出許多優(yōu)良個體，最終在群體中將會得到一個最優(yōu)良的個體，它將以概率1收斂于問題的最優(yōu)解。

圖2 SGA流程圖

2.2 基于改進遺傳算法的MIMO多用戶檢測算法

ML是遍歷所有的向量星座來尋找合適的向量，這在天線數(shù)目較多時是一個非常困難的任務(wù)，需要巨大的搜索判決運算，所以可以利用遺傳算法來解決這個問題?；谧畲笏迫粶?zhǔn)則的最優(yōu)判決準(zhǔn)則式(4)可以作為IGA-MUD的目標(biāo)函數(shù)，由于最大似然判決式(2)是求解目標(biāo)函數(shù)的最小值，而標(biāo)準(zhǔn)遺傳算法要求的適應(yīng)度函數(shù)為非負的，因此要求得適應(yīng)度函數(shù)值最大的最優(yōu)個體。所以必須將目標(biāo)函數(shù)轉(zhuǎn)化為適應(yīng)度函數(shù)，采用式(5)建構(gòu)IGA-MUD的適應(yīng)度函數(shù)f(Y，X)為:

Ω(x)=‖r-Hx‖

(4)

f(Y，X)=max{Ω(x)}-Ω(x(Y，X))+c

(5)

式中:max{Ω(x)}表示所有個體目標(biāo)函數(shù)值中那個最大值;Ω(x(Y，X))表示第Y代的第X個個體目標(biāo)函數(shù)值;c是一個較小的正數(shù)，保證了適應(yīng)度函數(shù)f(Y，X)非負，并且把原來的最小值問題轉(zhuǎn)換為IGA-MUD可實現(xiàn)的最大值問題。

SGA應(yīng)用在多用戶檢測中，由于被搜索的空間非常大，而導(dǎo)致其收斂速度較慢，收斂過早、進化速度緩慢、尋找到次優(yōu)解而不是最優(yōu)解、存在容易陷入局部最優(yōu)等問題，因此需要對SGA基本遺傳算法進行改進。

對基本遺傳算法進行改進后的MIMO多用戶檢測算法——IGA-MUD，其具體實現(xiàn)如下(見圖3):

(1) 編碼和種群初始化

在IGA-MUD中，需要將種群中的個體用染色體來表達，一般來說可以采用0 和1 兩個整數(shù)組成的二進制符號串表示。對于MIMO多用戶檢測問題，染色體由星座符號組成，基因單元為星座點，種群中個體i可以表示為xi=(x1，x2，…，xM)，個體長度即為用戶數(shù)M。通常SGA是在解空間中隨機選擇X個個體作為初始化種群的。對于MIMO多用戶檢測問題，為了加快收斂速度和減小計算復(fù)雜度，IGA-MUD將傳統(tǒng)檢測器的輸出作為一個初始染色體，初始種群的所有個體都通過對此初始染色體基因的隨機變異(從0~1或相反)來得到。仿真結(jié)果表明，在基于V-BLAST的MIMO上行信道系統(tǒng)中，運用基本的QR分解所得到的各個用戶的檢測向量，以此作為遺傳算法的一個初始染色體可以得到很好的性能。

圖3 IGA-MUD第Y代種群的進化過程

(2) 根據(jù)各個個體的適應(yīng)度值f(Y，X)，從上一代種群中選擇出適應(yīng)度較高的個體遺傳到下一代種群中。SGA采用的是輪盤賭選擇方法，適應(yīng)度大的個體可能被選擇多次，而適應(yīng)度小的個體可能被淘汰;IGA-MUD結(jié)合最優(yōu)保存策略的進化模型加以改進，加快了IGA-MUD的收斂速度。

最優(yōu)保存策略進化模型的具體過程是:

① 找出當(dāng)前種群中max f(Y，X)適應(yīng)度最高的個體xbest和min f(Y，X)適應(yīng)度最低的個體xworst。

② 當(dāng)前種群中最佳個體的適應(yīng)度比總的迄今為止的最好個體的適應(yīng)度還要高，則以當(dāng)前種群中的最佳個體作為新的迄今為止的最好個體。

③ 用xbest迄今為止的最好個體替換掉xworst當(dāng)前種群中的最差個體。

(3) 交叉是IGA-MUD中最主要的操作，通過交叉可以得到新一代的個體，新個體組合了其父輩個體的特性。交叉體現(xiàn)了信息交換的思想，它將種群內(nèi)各個個體隨機搭配成對，對每一對個體，以某種概率(稱為交叉概率Pc)交換他們之間的部分數(shù)據(jù)。交叉的方法有單點交叉和多點交叉，其中比較好的方法是均勻交叉，即兩個配對個體的每一個基因座上的基因都以相同的交叉概率進行交換，從而形成兩個新的個體。在進行均勻交叉配對時，隨機生成一個與個體等長度的二進制交叉掩碼序列，兩個個體在掩碼序列元素為“1”的對應(yīng)位置交換元素，而在掩碼序列元素為“0”的位置不發(fā)生交換。實驗結(jié)果表明，使用均勻交叉后，IGA-MUD的檢測性能優(yōu)于SGA的性能，如圖4所示。

(4) 變異是對種群中每一個個體，以某一概率(稱為變異概率Pm)改變某一個或某一些基因座上的基因值作為其他的等位基因。均勻變異UM(Uniform Mutation)操作采用符合某一范圍內(nèi)均勻分布的隨機數(shù)，以某一較小的概率來替換個體編碼串中各個基因座上的原有基因值，使得搜索點可以在整個搜索空間內(nèi)自由移動。

圖4 均勻交叉示例

在IGA-MUD中，將其改進為CNUM (Closest-Neighbor Uniform Mutation)，即限定用戶突變的方向為最近的星座點，且突變到這些限定的星座點的概率相同。改進后加快了IGA-MUD的收斂速度。

(5) 若滿足收斂條件，達到預(yù)先設(shè)定的遺傳代數(shù)Y=N，則IGA-MUD結(jié)束，否則轉(zhuǎn)(2)。

IGA-MUD所得到的最優(yōu)個體，即為MIMO多用戶檢測得到的各個用戶的信號向量。需要指出的是，IGA-MUD是把不同用戶的信號聯(lián)合檢測，而傳統(tǒng)的SIC和PIC多用戶檢測器則是通過與其他用戶干擾抵消，實現(xiàn)各個用戶信號的估計，因此IGA-MUD在不同用戶的信號檢測之間沒有錯誤的繁殖，提高了多用戶的檢測性能。

3 算法復(fù)雜度分析

對以上提出的IGA-MUD進行計算復(fù)雜度分析，假設(shè)所采用的調(diào)制方式對應(yīng)的符號數(shù)為N，用戶數(shù)為M，則最優(yōu)最大似然檢測方法是對NM種可能解進行完全搜索，計算復(fù)雜度為O(NM)，隨著用戶數(shù)M的增長成指數(shù)增長。

對于IGA-MUD，其計算復(fù)雜度主要由搜索的個體數(shù)目決定。當(dāng)種群遺傳進化代數(shù)為Y，每代種群含X個個體時，共有X×Y個個體被代入適應(yīng)度函數(shù)進行適應(yīng)度評價，其計算復(fù)雜度為O(X×Y)，與遺傳進化代數(shù)呈線性增長關(guān)系。另外，IGA-MUD還有選擇、交叉和變異的附加操作。在算法的每一代，需要產(chǎn)生X次選擇操作，還需要進行PcX/2次交叉操作以及進行PmX(2K+1)M 次變異操作(這里(2K+1)M是解的維數(shù));將這幾個部分相加，乘Y，再除以(2K+1)M，則選擇、交叉和變異的計算復(fù)雜度為O(X×Y)。顯然X和Y的選擇由解空間規(guī)模N(2K+1)M決定，這里設(shè)X=a(2K+1)M，Y=b(2K+1)M(a 和b是與解的維數(shù)相關(guān)的兩個正常數(shù))。因此對于一個給定的幀長度2K+1，IGA-MUD的計算復(fù)雜度為O(M2)。顯然當(dāng)用戶數(shù)較多時，將在很大程度上減少計算時間。通過設(shè)置不同的種群遺傳進化代數(shù)和種群個體數(shù)目，系統(tǒng)可進一步在性能與復(fù)雜度之間進行有效配置。

4 仿真結(jié)果

仿真中采用基于V-BLAST的MIMO上行信道系統(tǒng)，假定各個用戶的信道矩陣Hm由獨立同分布的復(fù)高斯隨機變量組成，均值為零，方差為1。噪聲為高斯白噪聲，均值為0，方差σ2n由歸一化信噪比確定。仿真信噪比范圍為0~16 dB，每隔2 dB仿真一次。IGA-MUD的參數(shù)如下:交叉概率Pc=0.9(采用均勻交叉)，變異概率Pm=0.1。圖5給出了QPSK調(diào)制方式下，4根發(fā)射天線(每個用戶1根)和4根接收天線，4個用戶時，種群大小X=20，IGA-MUD在不同遺傳代數(shù)時的檢測性能曲線，并給出相同條件下ML，MMSE，ZF，QR的檢測性能曲線。圖6給出了QPSK調(diào)制方式下，6根發(fā)射天線(每個用戶1根)和6根接收天線，6個用戶時，種群大小X=70，IGA-MUD在不同遺傳代數(shù)時的檢測性能曲線，并給出相同條件下ML，MMSE，ZF，QR的檢測性能曲線。

圖5 4個用戶MIMO系統(tǒng)運用IGA-MUD

性能曲線與傳統(tǒng)檢測算法性能曲線比較

圖6 6個用戶MIMO系統(tǒng)運用IGA-MUD

性能曲線與傳統(tǒng)檢測算法性能曲線比較

從圖5、圖6可以看出，IGA-MUD的檢測性能與傳統(tǒng)檢測器相比，得到了很大的提高，整個系統(tǒng)的性能隨遺傳代數(shù)的增加有所提高，并且接近ML多用戶檢測器的性能，而且復(fù)雜度與ML相比有了明顯的降低。在相同誤比特率時，IGA-MUD與MMSE相比較，檢測性能至少提高了8 dB;隨著信噪比的增加，IGA-MUD繼續(xù)保持優(yōu)于其他檢測算法。通過設(shè)置不同的種群遺傳進化代數(shù)和種群個體數(shù)目，系統(tǒng)可進一步在性能與復(fù)雜度之間進行有效配置。

由圖5可見，在QPSK調(diào)制方式下，4個用戶時，IGA-MUD在種群個體數(shù)X=20，遺傳進化代數(shù)Y=6時的檢測性能已經(jīng)比MMSE，ZF，QR有了很大的改善，接近ML算法的性能。此時，IGA-MUD的計算復(fù)雜度為O(X×Y)，也就是120;ML算法的復(fù)雜度為O(NM)，也就是256。可以看出，IGA-MUD的復(fù)雜度要小得多。從圖6可以看出，在QPSK調(diào)制方式下，6個用戶時，IGA-MUD在種群個體數(shù)X=70，遺傳進化代數(shù)Y=12時，IGA-MUD的復(fù)雜度只需要X×Y=840就可以接近ML的性能，而此時ML的復(fù)雜度卻為NK=46=4 096。因此，當(dāng)用戶數(shù)量較大時，IGA-MUD的復(fù)雜度與ML相比較要小得多。

5 結(jié) 語

提出了一種基于改進遺傳算法的MIMO多用戶檢測算法IGA-MUD，將遺傳算法用于MIMO多用戶檢測，并對SGA進行了改進，IGA-MUD在性能上與SGA(基本遺傳算法)相比較有明顯的改進，是一種有效可行的多用戶檢測算法。IGA-MUD避免了直接使用最大似然算法帶來運算復(fù)雜度的增加，顯著降低了算法的復(fù)雜度。仿真結(jié)果表明，在垂直分層空時碼系統(tǒng)中，對于4個用戶和6個用戶的上行MIMO多用戶系統(tǒng)，其計算復(fù)雜度明顯低于ML最優(yōu)多用戶檢測算法，而且其性能接近ML的性能，與ZF，MMSE多用戶檢測算法相比較，性能得到了顯著的提高。

參 考 文 獻

Verdu S.Multiuser Detection [M].Cambridge:Cambridge Univ.Press，1998.

Li Zi，Cai Yueming，Ni Mingfang.Low Complexity MIMO Detection Based on Branch and Bound Algorithm.The 18th Annual IEEE International Symposium on Personal，Indoor and Mobile Radio Communications[C].2007.

Hanzo L，Munster M，Choi B J，et al.OFDM and MC-CDMA for Broadband Multi-user Communications，WLANs and Broadcasting [M].IEEE Press/Wiley，2003.

Jankiraman，Mohinder.Space-time Codes and MIMO Systems [M].Boston:Artech House INC，2004.

Wubben D，Bohnke R，Rinas J，et al.Efficient Algorithm for Decoding Layered Space-Time Codes[J].IEE Electronic Letters，2001，37(22):1 348-1 350.

Wang Zhongpeng.A Hybrid Receiver Combining QR and PIC Based on MIMO Frequency Channels.Wireless Communications，Networking and Mobile Computing[C].2008.

Hanzo L，Yang L L，Kuan E L，et al.Single- and Multi-Carrier DS-CDMA:Multi-user Detection，Space-time Spreading，Synchronisation and Standards [M].IEEE Press-John Wiley Sons Ltd.，2003.

Ergun C，Hacioglu K.Multi-user Detection using a Genetic Algorithm in CDMA Communications Systems[J].IEEE Trans.on Commun.，2000，48(8):1 374-1 383.

Wu X，Chuah T C，Sharif B S，et al.Adaptive Robust Detection for CDMA using a Genetic Algorithm[J].Inst.Electr.Eng.Communications，2003，150(10):437-444.