黑永強(qiáng) 李曉輝 易克初 郁光輝
(1.西安電子科技大學(xué)ISN國家重點(diǎn)實(shí)驗(yàn)室,陜西 西安 710071; 2.深圳市中興通訊技術(shù)有限公司,廣東 深圳 518057)
對(duì)于多輸入多輸出(MIMO)系統(tǒng)而言,最大似然譯碼(ML)是最佳的接收算法,但是其計(jì)算量隨發(fā)射天線數(shù)呈指數(shù)增長(zhǎng),這就大大限制了ML在實(shí)際系統(tǒng)中的應(yīng)用,因而尋找次優(yōu)的MIMO檢測(cè)算法一直是業(yè)內(nèi)探索的目標(biāo)。為了解決這一問題,學(xué)者提出了許多次優(yōu)的線性和非線性的算法[1-4],然而這些算法難以取得較好的性能或者計(jì)算復(fù)雜度過高。目前基于凸優(yōu)化MIMO檢測(cè)算法引起了廣泛關(guān)注[5-7],其主要原因是該方法能夠以較低的復(fù)雜度獲取較好的性能,然而如何保證目標(biāo)函數(shù)的凸性以及如何進(jìn)行合理的松弛則是該算法的一大難題。
近年來許多學(xué)者開始嘗試用進(jìn)化算法求解檢測(cè)問題,這主要是因?yàn)檫M(jìn)化算法具有簡(jiǎn)單方便,運(yùn)行速度快,實(shí)現(xiàn)簡(jiǎn)潔,調(diào)整的參數(shù)少等優(yōu)勢(shì)。目前,這一方面的研究包括將離散粒子群算法、遺傳算法、克隆選擇算法等用于多用戶檢測(cè)問題[8-10],但是上述研究中進(jìn)化算法僅適用于用戶配置單天線的狀況,而如何采用進(jìn)化算法求解多天線MIMO系統(tǒng)檢測(cè)問題則亟待進(jìn)一步研究。上述研究中僅注重將進(jìn)化算法應(yīng)用于檢測(cè)問題求解,而并未深入分析進(jìn)化機(jī)制的優(yōu)勢(shì)和缺陷,因而,求解檢測(cè)問題的性能將受限,如何設(shè)計(jì)出新的更加高效的進(jìn)化算法,能夠進(jìn)一步提高求解問題的效率,這正是研究的出發(fā)點(diǎn)。
首先將粒子群優(yōu)化算法(PSO)和遺傳算法(GA)應(yīng)用于求解MIMO系統(tǒng)檢測(cè)問題。在此基礎(chǔ)之上,提出新的遺傳粒子群優(yōu)化(GPSO)進(jìn)化算法以克服PSO算法和GA算法求解MIMO檢測(cè)問題的不足。新算法的求解思路是:將以MMSE估計(jì)的檢測(cè)符號(hào)集作為初始種群,并根據(jù)粒子的適應(yīng)度值將粒子分為精英粒子,次優(yōu)粒子以及糟糕粒子三部分,然后對(duì)于精英粒子和次優(yōu)粒子分別實(shí)施極值擾動(dòng)和PSO進(jìn)化策略,而對(duì)糟糕粒子實(shí)施淘汰后并重新產(chǎn)生從而改善算法的進(jìn)化機(jī)制。仿真結(jié)果表明所提算法的有效性。
假定一個(gè)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è)下,接收到的信號(hào)復(fù)向量為
r=Hx+n
(4)
對(duì)于MIMO系統(tǒng),最優(yōu)的最大似然檢測(cè)(ML)的輸出向量為
(5)
式中,Ω為星座符號(hào)集。但ML算法由于需要遍歷整個(gè)發(fā)射符號(hào)集空間,其復(fù)雜度O(ΩNt)為星座大小和天線數(shù)目的指數(shù)函數(shù),因此,在實(shí)際中一般難以接受。
采用進(jìn)化算法求解MIMO系統(tǒng)檢測(cè),首先需要解決以下兩個(gè)問題:
1) 所優(yōu)化的目標(biāo)函數(shù)是什么?
2) 如何定義進(jìn)化算法中的個(gè)體(優(yōu)化變量)?
(6)
則有下式成立
rp=Hpxp+np
(7)
粒子群優(yōu)化算法(PSO)[12],由Eberhart和Kennedy于1995年提出,是一種模擬自然界鳥類、魚群等尋找食物過程而提出的隨機(jī)搜索算法。粒子群算法是一種基于群體的優(yōu)化算法,其中每個(gè)粒子代表所研究問題的一個(gè)可行解,它具有位置和速度兩個(gè)基本特征。每個(gè)粒子在搜索空間中以一定的速度飛行,并根據(jù)對(duì)個(gè)體和集體飛行經(jīng)驗(yàn)的綜合分析來動(dòng)態(tài)調(diào)整其速度,然后更新個(gè)體當(dāng)前的位置,每個(gè)粒子根據(jù)下面兩個(gè)公式來更新自己的速度與位置
vi(τ+1)=wvi(τ)+c1r1(pbesti(τ)-xi(τ))+
c2r2(gbest(τ)-xi(τ))
xi(τ+1)=xi(τ)+vi(τ+1)
(8)
式中:pbesti(τ)和gbest(τ)分別表示個(gè)體極值和全局極值;c1和c2是加速度常數(shù);r1和r2是服從[0,1]分布的隨機(jī)數(shù);vi(τ)受限于[-VmaxVmax];w是慣性常量。
圖2 粒子定義示意圖
圖2所示粒子采用浮點(diǎn)編碼的優(yōu)勢(shì)在于能夠有效擴(kuò)展算法的求解范圍,可以推廣到高階調(diào)制。此時(shí),各浮點(diǎn)編碼元素可映射為最近的星座點(diǎn)。
適應(yīng)度函數(shù)定義:PSO算法通過適應(yīng)度函數(shù)來評(píng)估粒子的優(yōu)劣,根據(jù)粒子的定義,適應(yīng)度函數(shù)可以定義為:
(9)
適應(yīng)度函數(shù)值越小,則表明該粒子與最優(yōu)檢測(cè)向量之間的歐式距離越短,整個(gè)尋優(yōu)過程中的全局最優(yōu)粒子即代表PSO算法所得出的檢測(cè)向量。根據(jù)粒子和適應(yīng)度函數(shù)的定義并根據(jù)式(8)中的進(jìn)化過程,可以實(shí)現(xiàn)PSO算法求解MIMO系統(tǒng)檢測(cè)。
遺傳算法(GA)是一種基于生物遺傳和進(jìn)化機(jī)制的自適應(yīng)概率優(yōu)化技術(shù)[13]。它通過模擬自然選擇和遺傳中發(fā)生的選擇、交叉和變異等現(xiàn)象,從一個(gè)初始種群出發(fā),經(jīng)過隨機(jī)選擇、交叉和變異操作,產(chǎn)生一群更適應(yīng)環(huán)境的個(gè)體,使群體進(jìn)化到搜索空間中越來越好的區(qū)域。經(jīng)過這樣一代又一代地不斷繁衍進(jìn)化,最后得到一群最適合環(huán)境的個(gè)體,從而求得問題的最優(yōu)解。
類似PSO算法檢測(cè)過程,采用GA算法求解MIMO系統(tǒng)檢測(cè)問題時(shí),GA中的個(gè)體與PSO中的粒子相對(duì)應(yīng),而適應(yīng)度函數(shù)則采用相同的定義,所不同的是PSO算法通過更新粒子的位置和速度來尋優(yōu),而GA算法的尋優(yōu)則通過遺傳操作完成。GA求解MIMO檢測(cè)的基本過程如下:首先隨機(jī)初始產(chǎn)生Q個(gè)體,其中每一個(gè)體代表發(fā)送數(shù)據(jù)的一個(gè)估計(jì)值,然后計(jì)算個(gè)體的適應(yīng)度值,并根據(jù)適應(yīng)度值的優(yōu)劣選擇個(gè)體用于雜交。在每一代的進(jìn)化過程中,用于遺傳操作,即交叉、變異,生成下一代個(gè)體,也即子代。經(jīng)過若干代進(jìn)化之后,算法收斂于最好的個(gè)體,該個(gè)體作為GA算法所求出的最優(yōu)檢測(cè)解向量。GA算法求解MIMO檢測(cè)過程的關(guān)鍵步驟如圖3所示。
圖3 GA算法求解MIMO檢測(cè)關(guān)鍵步驟流程
PSO算法通過進(jìn)化過程經(jīng)驗(yàn)記憶以及粒子之間的信息共享發(fā)揮作用,因而PSO算法具有很強(qiáng)的全局搜索能力,但由于所有的粒子都參與每一代進(jìn)化未免會(huì)導(dǎo)致進(jìn)化效率的降低。相反,GA在每一代中通過不斷選擇優(yōu)秀的個(gè)體而丟棄質(zhì)量較差的個(gè)體來完成進(jìn)化,故GA算法具有很強(qiáng)的局部搜索能力,但GA算法中個(gè)體之間缺乏信息交互,因此,其全局尋優(yōu)能力較弱以及收斂速度較慢。利用GA和PSO算法的各自優(yōu)勢(shì),給出一種融合GA和PSO進(jìn)化機(jī)制的新遺傳粒子群進(jìn)算法,并將其應(yīng)用于求解MIMO系統(tǒng)檢測(cè),下文將給出算法的詳細(xì)求解過程。
根據(jù)中債資信地方政府及城投行業(yè)研究團(tuán)隊(duì)對(duì)2016年政府類投融資平臺(tái)-江蘇篇調(diào)研結(jié)果知,截止2015年末,江蘇省政府債務(wù)率68.5%,債務(wù)風(fēng)險(xiǎn)總體可控,江蘇省內(nèi)融資平臺(tái)直接間接融資渠道較為通暢,2015年融資成本較此前明顯降低,綜合融資成本6%-8%之間。2017年后江蘇省融資平臺(tái)逐漸出現(xiàn)融資難、成本高。
初始化:初始化種群選取合適與否將直接關(guān)系到進(jìn)化算法的迭代次數(shù)與收斂速度,如果采用常規(guī)的隨機(jī)產(chǎn)生初始種群,則算法求解檢測(cè)的計(jì)算效率很難保證。為了解決這一問題,采用接收信號(hào)MMSE估計(jì)值rMMSE作為初始種群,從而加快新算法尋找最優(yōu)解的速率。
rMMSE=Gp·rp
(10)
粒子評(píng)估:在進(jìn)化過程中,粒子的質(zhì)量難免會(huì)有優(yōu)劣之分。借鑒GA算法個(gè)體評(píng)估原理,將對(duì)每一代進(jìn)化的粒子根據(jù)適應(yīng)度值進(jìn)行排序,然后將這些粒子進(jìn)行劃分為三部分:精英粒子、次優(yōu)粒子、以及糟糕粒子,并對(duì)這些粒子分別采取各自的尋優(yōu)策略。
xg+1(τ+1)=xg(τ)+(1-rd[1-
(τ/T)])vg+1(τ)
(11)
從式(11)中可看出,在搜索初期,對(duì)于較小的rd值時(shí),精英粒子相對(duì)擾動(dòng)空間較大;而在搜索后期,τ接近于T時(shí),精英粒子在較小的空間內(nèi)擾動(dòng)。式(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檢測(cè)問題的關(guān)鍵步驟如下:
step 1 設(shè)粒子群規(guī)模為Q,根據(jù)式(10)初始化粒子種群,并隨機(jī)產(chǎn)生各粒子的速度。
step 2 根據(jù)式(9)計(jì)算粒子的適應(yīng)度函數(shù),找出個(gè)體極值和全局極值。
step 3 對(duì)于精英粒子,根據(jù)式(11)實(shí)施增強(qiáng)極值擾動(dòng)。
step 4 對(duì)于次優(yōu)粒子,根據(jù)式(8)實(shí)施改進(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)的檢測(cè)結(jié)果。
采用第1部分描述的MIMO相關(guān)信道模型Nt=4,Nr=4。為了驗(yàn)證所提算法的有效性,仿真中同時(shí)引入了ZF算法、MMSE算法、最大似然(ML)算法。另外,PSO算法、GA算法和GPSO算法三種算法的公共參數(shù)如下:種群規(guī)模Q=80,最大迭代次數(shù)T=10。對(duì)于PSO,慣性常數(shù)w在[0.9,0.4]區(qū)間內(nèi)線性遞減,加速度常數(shù)c1=c2=2。對(duì)于遺傳算法選取變異概率和交叉概率分別為0.05和0.8,其他參數(shù)均與PSO算法相同。而所提算法中的粒子淘汰率pt=0.5.
實(shí)驗(yàn)1分析比較GPSO算法和經(jīng)典的檢測(cè)算法以及進(jìn)化算法的誤碼性能
圖5 比較GPSO算法和經(jīng)典算法誤碼性能曲線
圖5比較了GPSO算法和經(jīng)典檢測(cè)算法的誤碼性能。由圖5可知,最大似然檢測(cè)算法(ML)是最優(yōu)的,但是其指數(shù)復(fù)雜度也是最高的。GPSO算法相比較其他算法獲得一定的信噪比增益,當(dāng)種群數(shù)目由Q=50增加到Q=80,誤碼性能得到了明顯的改善。而MMSE算法相對(duì)于ZF算法有一定的增益,這是因?yàn)镸MSE算法相比ZF算法增加了接收SNR的估計(jì)。ZF算法的性能優(yōu)于QR算法在于前者可以使得天線之間的干擾迫零,然而迫零矩陣引入了對(duì)噪聲的放大,因此,其誤碼性能也較差。QR檢測(cè)算法受誤差傳播的影響故其誤碼性能最差。
圖6比較了所提算法以及另外兩種進(jìn)化算法的誤碼率曲線。需要指出的是圖6中三種檢測(cè)算法均采用MMSE估計(jì)值作為初始種群。可以看出,GPSO檢測(cè)算法的性能要明顯優(yōu)于PSO檢測(cè)算法和GA檢測(cè)算法,從而體現(xiàn)出所提算法所采用進(jìn)化機(jī)制的有效性。這也同樣說明PSO和GA算法的進(jìn)化機(jī)制均存在一定缺陷。另外PSO檢測(cè)算法誤碼性能要優(yōu)于GA檢測(cè)算法,這是因?yàn)橄啾菺A算法,PSO算法具有更強(qiáng)的全局尋優(yōu)能力。另外,可以看出,隨著種群數(shù)目Q的增加,三種算法的誤碼性能均得到一定的改善。
圖6 比較GPSO算法和進(jìn)化算法誤碼性能曲線
實(shí)驗(yàn)2分析迭代次數(shù)和粒子數(shù)目對(duì)GPSO算法誤碼性能的影響
圖7 迭代次數(shù)對(duì)GPSO算法誤碼性能影響曲線
圖7給出了迭代次數(shù)對(duì)GPSO算法誤碼性能影響曲線??梢钥闯?,隨著迭代次數(shù)的增加,誤碼性能逐步得到改善。其原因在于,在進(jìn)化的過程中隨著迭代次數(shù)的增加不斷能夠發(fā)現(xiàn)更優(yōu)的粒子。但是隨著迭代次數(shù)的進(jìn)一步增加,誤碼率改善效果逐漸變得不明顯,比如圖中10次迭代相比較5次迭代所得增益沒有5次迭代相比較1次迭代所得增益的效果顯著。因此,在實(shí)際系統(tǒng)中可以根據(jù)需求來確定進(jìn)化過程所需的最大迭代次數(shù)。
圖8給出粒子數(shù)目對(duì)GPSO算法誤碼性能影響的曲線。由圖可知,粒子數(shù)目越多,GPSO算法下的誤碼率曲線就越接近ML算法誤碼率曲線。這是因?yàn)楦鄶?shù)目的粒子參與進(jìn)化,必然導(dǎo)致算法尋找到最優(yōu)解的概率增加,因而誤碼性能得到改善。對(duì)比圖7和圖8可以發(fā)現(xiàn),誤碼性能的改善既可以通過增加進(jìn)化的迭代次數(shù)也可以通過加大粒子種群的數(shù)目來獲得,因此,在實(shí)際系統(tǒng)中,可以根據(jù)要求合理地選取這兩個(gè)參數(shù)。
圖8 粒子數(shù)目對(duì)GPSO算法誤碼性能影響曲線
實(shí)驗(yàn)3所提算法計(jì)算復(fù)雜度分析與比較
由第一節(jié)可知,ML算法由于需要遍歷所有可能的發(fā)射序列,其復(fù)雜度大小為Q(ΩNt)。這在發(fā)射天線數(shù)目較多或者采用較高的調(diào)制方式時(shí),令人無法接受。相比較ML算法,ZF、MMSE算法能夠顯著降低算法的復(fù)雜度,大小近似為O(Nr3),其中Nr為接收天線數(shù)目,但是ZF、MMSE算法復(fù)雜度降低是以性能損失為代價(jià)的。
對(duì)于上文所給出的三種算法,假定種群數(shù)目P,每個(gè)粒子處于D維空間及最大迭代數(shù)目為T。初始化粒子群以及計(jì)算適應(yīng)度函數(shù)值大概需要的計(jì)算復(fù)雜度為O(PD),另外對(duì)于更新全局極值,個(gè)體極值以及每個(gè)粒子其位置和速度所需要的復(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算法的整體計(jì)算復(fù)雜度為:O(T(2P+2PD))。對(duì)于GA而言,遺傳操作的三個(gè)關(guān)鍵算子選擇、交叉、變異的時(shí)間復(fù)雜度分別為:O(P),O(PD)和O(PD),因此,GA算法總的時(shí)間復(fù)雜度為O(T(P+3PD))。對(duì)于所提算法而言,初始化種群個(gè)體所需的計(jì)算復(fù)雜度近似為O(Nr2),而粒子的適應(yīng)度值進(jìn)行排序引入的額外復(fù)雜度為O(P),每個(gè)粒子附近的次優(yōu)粒子的更新需要的復(fù)雜度為O(P),因此,所提算法的計(jì)算復(fù)雜度為O(T(4P+PD)+Nr2)。忽略系數(shù)影響的條件下,PSO算法、GA算法以及所提算法的計(jì)算復(fù)雜度分別可以近似O(TPD),O(TPD),O(TPD+Nr2).根據(jù)選取粒子或個(gè)體的定義可知,P,D,T均隨著發(fā)射空間維數(shù)Nt的增加而線性增加,則三種算法的復(fù)雜度分別近似為O(Nt3),O(Nt3),O(Nt3+Nr2).可見,相比ML算法,三種算法具有較低的復(fù)雜度;而考慮到獲得相同的性能前提下所提算法所需迭代次數(shù)要少于PSO算法,因此,所提算法的計(jì)算復(fù)雜度相對(duì)于PSO算法以及GA算法基本上相差不大。
提出了一種求解MIMO系統(tǒng)檢測(cè)新算法:遺傳粒子群優(yōu)化算法,新算法通過有效地融合GA和PSO進(jìn)化機(jī)制,從而加快了算法的求解效率。仿真結(jié)果表明:所提算法應(yīng)用于MIMO系統(tǒng)檢測(cè)十分有效,在種群規(guī)模Q=80和最大迭代次數(shù)T=10時(shí),相比最大似然檢測(cè)算法在誤碼率為10-2時(shí)SNR相差約為2 dB。而與基于PSO檢測(cè)算法和基于GA檢測(cè)算法相比,在相同的種群數(shù)目和迭代次數(shù)下,能夠獲得更好的誤碼性能。有望將所提算法進(jìn)一步推廣應(yīng)用于多用戶MIMO檢測(cè)場(chǎng)景[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é)報(bào),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é)報(bào), 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é)報(bào), 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)