基于改進(jìn)入侵雜草算法的多用戶檢測

國 強(qiáng)，張金程，周 凱

(哈爾濱工程大學(xué) 信息與通信工程學(xué)院，黑龍江 哈爾濱 150001)

0 引言

在DS-CDMA系統(tǒng)[1]中，由于擴(kuò)頻序列的非完全正交性、各用戶的隨機(jī)接入以及實(shí)際信道的異步傳輸?shù)仍?，使得用戶之間產(chǎn)生多址干擾。當(dāng)用戶數(shù)量達(dá)到一定程度，多址干擾成為主要的系統(tǒng)干擾，采用傳統(tǒng)檢測器(Conventional Detector，CD)會使系統(tǒng)容量降低，通信質(zhì)量下降，嚴(yán)重影響系統(tǒng)性能。多用戶檢測技術(shù)[2-3]是克服多址干擾的關(guān)鍵技術(shù)之一。最優(yōu)多用戶檢測器(Optimal Multi-user Detection，OMD)[4]雖然具有良好的檢測性能，但是其計(jì)算復(fù)雜度隨著用戶數(shù)的增加成指數(shù)增長，當(dāng)用戶數(shù)量較多時(shí)計(jì)算復(fù)雜度極高，工程上難以實(shí)現(xiàn)。DS-CDMA系統(tǒng)的多用戶檢測問題可以看作是一個(gè)組合優(yōu)化問題，通過智能算法來求解[5-8]。

入侵雜草算法(Invasive Weed Optimization，IWO)[9]是Mehrabian和Lucas在2006年提出的一種仿生優(yōu)化算法，模擬自然環(huán)境中雜草的生長擴(kuò)散過程，具有收斂速度快、魯棒性好、結(jié)構(gòu)簡單以及易于實(shí)現(xiàn)等特點(diǎn)[10]。IWO算法在多目標(biāo)優(yōu)化[11]、陣列天線稀布[10，12]和能源負(fù)荷動態(tài)調(diào)度[13]等領(lǐng)域得到廣泛應(yīng)用。這些應(yīng)用大多屬于連續(xù)空間或者整數(shù)空間優(yōu)化問題，而利用IWO算法求解二進(jìn)制離散空間問題的研究相對較少。

本文主要研究DS-CDMA系統(tǒng)的多用戶檢測，為解決最優(yōu)多用戶檢測器復(fù)雜度過高問題，引入入侵雜草優(yōu)化算法。并從抗多址干擾能力、抗遠(yuǎn)近效應(yīng)能力和收斂性等方面進(jìn)行仿真分析。

1 系統(tǒng)模型

1.1 同步DS-CDMA系統(tǒng)模型

假設(shè)一個(gè)具有K個(gè)用戶的DS-CDMA系統(tǒng)，所有用戶采用二進(jìn)制相移鍵控調(diào)制(Binary Phase Shift Keying，BPSK)，系統(tǒng)的信道噪聲為加性高斯白噪聲，在不考慮信道衰落和多徑效應(yīng)的情況下，假設(shè)捕獲跟蹤條件理想，即忽略載波調(diào)制解調(diào)，則通信系統(tǒng)接收端的信號模型為：

(1)

式中，SF表示擴(kuò)頻序列長度；Ak表示用戶k的信號幅度；bk表示用戶k發(fā)送的比特信息；Tb表示碼元間隔；T表示傳輸信息的周期間隔；τk表示用戶k的延時(shí)；n(t)表示均值為0，能量為σ2的加性高斯白噪聲；sk(t)表示用戶k的擴(kuò)頻序列，其波形是持續(xù)時(shí)間為Tb的矩形波，并且具有歸一化能量，即

(2)

若所有用戶的延時(shí)均為0，式(1)變?yōu)橥紻S-CDMA系統(tǒng)的信號模型，簡化擴(kuò)頻序列，則可表示為：

(3)

1.2 傳統(tǒng)檢測器

傳統(tǒng)檢測器，利用用戶的擴(kuò)頻序列對接收到的信號進(jìn)行相關(guān)接收。相關(guān)處理后的信號表示為：

(4)

式中，nk為信道噪聲經(jīng)過匹配濾波器k后的剩余噪聲；MAIk為干擾用戶對期望用戶產(chǎn)生的多址干擾；ρjk為用戶j和用戶k擴(kuò)頻序列的歸一化互相關(guān)系數(shù)。

(5)

對相關(guān)處理后的信息進(jìn)行硬判決，得到：

bk=sign(yk) 。

(6)

1.3 最優(yōu)多用戶檢測器

最優(yōu)多用戶檢測算法的基本思想是充分利用所有用戶信息，對用戶信號進(jìn)行聯(lián)合檢測，相當(dāng)于用戶比特信息先驗(yàn)概率相等條件下的最大似然序列檢測，性能能夠接近單用戶系統(tǒng)。檢測得到的結(jié)果要使式(7)的似然函數(shù)最大化。

(7)

經(jīng)過推導(dǎo)，上式可等效為使式(8)最大化。

(8)

式中，H=ARA，A為以用戶幅度為元素的對角陣。

OMD檢測器的運(yùn)算復(fù)雜度為O(2k)，與用戶數(shù)量成指數(shù)關(guān)系。當(dāng)用戶數(shù)較多時(shí)，以現(xiàn)有的硬件水平難以實(shí)現(xiàn)。

2 基本的入侵雜草優(yōu)化算法

入侵雜草優(yōu)化算法是模擬自然界中雜草的繁殖、擴(kuò)散和消亡的過程而得到的一種尋優(yōu)算法。其中每一個(gè)雜草代表要求解問題的一個(gè)可行解，子代雜草為雜草通過空間擴(kuò)散得到的新解。在尋優(yōu)過程中，雜草根據(jù)自身適應(yīng)度值的大小產(chǎn)生一定數(shù)量的種子，種子以正態(tài)分布的步長分布在父代雜草的周圍區(qū)域，成長為代雜草。在每一級迭代中，通過比較所有父代雜草和子代雜草的適應(yīng)度值，保留適應(yīng)度好的雜草進(jìn)行下一代繁殖擴(kuò)散。其過程主要包括3個(gè)步驟[10]：

① 種子繁殖。雜草xi根據(jù)其適應(yīng)能力產(chǎn)生不同數(shù)量的種子，適應(yīng)度值好的雜草產(chǎn)生較多的種子，適應(yīng)度值差的雜草產(chǎn)生較少的種子。對于求解最大化問題，生成種子的數(shù)量根據(jù)式(9)確定：

(9)

式中，f(xi)表示雜草xi的適應(yīng)度值；fmax和fmin表示當(dāng)前迭代中所有種子的最大適應(yīng)值和最小適應(yīng)值；Smax和Smin表示一個(gè)種子能夠產(chǎn)生的最大種子數(shù)量和最小種子數(shù)量。

② 空間擴(kuò)散。種子按照均值為0、標(biāo)準(zhǔn)差為σ正態(tài)分布步長生長成雜草，分布在父代雜草的周圍空間。每一代標(biāo)準(zhǔn)差σiter的大小按照式(10)確定：

(10)

式中，iter表示當(dāng)前的迭代次數(shù)；itermax表示最大的迭代次數(shù)；σini和σfin表示標(biāo)準(zhǔn)差的初始值和最終值(一般初始值大于最終值)；n是非線性調(diào)和因子，通常情況下n=3[14]。

雜草i產(chǎn)生的第s個(gè)種子的位置可以表示為：

(11)

③競爭排除。在種子的繁殖擴(kuò)散過程中，當(dāng)雜草的數(shù)量達(dá)到最大種群規(guī)模Pmax后，將父代雜草和子代雜草按適應(yīng)度值大小進(jìn)行排序，保留適應(yīng)值較好的Pmax個(gè)雜草，淘汰其余的雜草。

3 基于改進(jìn)IWO算法的多用戶檢測

3.1 改進(jìn)的IWO算法

3.1.1 映射函數(shù)

在標(biāo)準(zhǔn)的IWO算法中，種子的擴(kuò)散空間是圍繞在父代雜草周圍的高斯分布。在調(diào)制方式為BPSK的DS-CDMA系統(tǒng)中所傳輸?shù)男畔閧-1，+1}，所以標(biāo)準(zhǔn)IWO算法中的擴(kuò)散方式不能直接應(yīng)用于二進(jìn)制雜草個(gè)體的擴(kuò)散，需要通過恰當(dāng)?shù)姆绞竭M(jìn)行映射，把擴(kuò)散值轉(zhuǎn)換成雜草某一維度的變異概率。

(12)

式中，sigmokd(x)=1/(1+e-1)。

由映射產(chǎn)生的變異概率，得到該維度的變異標(biāo)志flag，表示為：

(13)

式中，rand為(0，1)之間的隨機(jī)數(shù)。

則其子代雜草第k維的值為：

(14)

3.1.2 改進(jìn)的標(biāo)準(zhǔn)差變化曲線

在標(biāo)準(zhǔn)的IWO算法中，正態(tài)分布的標(biāo)準(zhǔn)差按式(10)計(jì)算，從圖1可以看出隨著進(jìn)化代數(shù)的增加，標(biāo)準(zhǔn)變化曲線下降緩慢。若最大迭代次數(shù)為30代，則當(dāng)?shù)螖?shù)達(dá)到25時(shí)，標(biāo)準(zhǔn)差才能接近最小值。在二進(jìn)制多用戶檢測系統(tǒng)的進(jìn)化前期，較大的標(biāo)準(zhǔn)差可以使子代雜草分布在距離父代雜草較遠(yuǎn)的位置，即子代雜草與父代雜草的漢明距離比較大，有利于全局搜索。但是在進(jìn)化中后期，種群分布在最優(yōu)解的附近，較大的變異概率不利于提高尋優(yōu)精度。為此設(shè)置標(biāo)準(zhǔn)差的變化曲線如式(15)所示，圖1中改進(jìn)變化曲線為其示意圖?？梢钥闯觯倪M(jìn)的進(jìn)化曲線在進(jìn)化前期可以使算法在整個(gè)空間進(jìn)行全局搜索，之后迅速在較小區(qū)域進(jìn)行局部搜索。

σiter=tanh(-iter+4)+2.5。

(15)

圖1 正態(tài)分布標(biāo)準(zhǔn)差變化曲線

3.2 基于改進(jìn)IWO算法的多用戶檢測器

改進(jìn)IWO算法的多用戶檢測器步驟：

① 參數(shù)設(shè)置。設(shè)置種群的初始規(guī)模和最大規(guī)模；種子繁殖的最大數(shù)量和最小數(shù)量等參數(shù)。

② 種群初始化。為了保證初始種群的多樣性，采用均勻分布方式產(chǎn)生初始種群，使初始雜草隨機(jī)分布在整個(gè)搜索空間。

③ 根據(jù)式(8)計(jì)算每個(gè)種子的適應(yīng)度值，按照式(9)計(jì)算每一個(gè)雜草產(chǎn)生種子的數(shù)量，完成種子繁殖。

④ 通過雜草擴(kuò)散的正態(tài)分布標(biāo)準(zhǔn)差，計(jì)算每一維度的擴(kuò)散值，通過式(12)得到變異概率，產(chǎn)生變異標(biāo)志，然后進(jìn)行維度變異、完成空間擴(kuò)散。

⑤ 計(jì)算子代雜草的適應(yīng)度值，和父代雜草一起進(jìn)行排序，進(jìn)行競爭排除，淘汰較差個(gè)體。

⑥ 判斷是否到達(dá)結(jié)束條件。若滿足結(jié)束條件，則輸出用戶的估計(jì)值；否則繼續(xù)執(zhí)行步驟③。

4 仿真分析

假設(shè)一個(gè)用戶數(shù)為10的同步DS-CDMA系統(tǒng)，采用BPSK調(diào)制，擴(kuò)頻序列采用長度為31的Gold碼，最大歸一化互相關(guān)系數(shù)為9/31。為了方便討論，假定系統(tǒng)具有嚴(yán)格的功率控制，擴(kuò)頻序列和用戶幅度估計(jì)準(zhǔn)確。

為了驗(yàn)證基于改進(jìn)IWO(Improved IWO，IIWO)算法多用戶檢測器的有效性，使用CD檢測器、解相關(guān)檢測器(De-correlation Detector，DEC)、OMD檢測器、基于基本遺傳算法(Genetic Algorithm，GA)、基本PSO算法和基本IWO算法的多用戶檢測器進(jìn)行對比。GA的種群規(guī)模設(shè)置為10，交叉概率設(shè)置為0.8，變異概率設(shè)置為0.05；PSO多用戶檢測器的參數(shù)設(shè)置參考文獻(xiàn)[15]，種群規(guī)模設(shè)置為10，加速度因子分別設(shè)置為2，最大加速度設(shè)置為6；IWO算法的最大種群規(guī)模設(shè)置為5，雜草產(chǎn)生的最大種子數(shù)量為4，最小數(shù)量為0，初始標(biāo)準(zhǔn)差為4，最終標(biāo)準(zhǔn)差為1.5，非線性調(diào)和因子為3；IIWO算法的最大種群規(guī)模設(shè)置為5，雜草產(chǎn)生的最大種子數(shù)量為4，最小數(shù)量為0，標(biāo)準(zhǔn)差按式(15)變化。智能算法的最大迭代次數(shù)設(shè)置為30。

仿真實(shí)驗(yàn)1：檢測器在不同信噪比下的誤碼率如圖2所示。從圖中可以看出，在上述參數(shù)設(shè)置下，IWO和IIWO檢測器接近OMD檢測器的性能，而信噪比大于8 dB時(shí)，PSO和GA檢測器在30次迭代內(nèi)未尋找到最優(yōu)解。

圖2 檢測性能隨信噪比變化情況

仿真實(shí)驗(yàn)2：為了驗(yàn)證算法的抗遠(yuǎn)近效應(yīng)能力，假設(shè)除用戶1外其他用戶的信息幅度為1，信噪比為8 dB，用戶1與其他用戶的幅度比A1/Ai從0.1～10變化。所有用戶的平均誤碼率如圖3所示。從圖中可以看出，IIWO檢測器的誤碼率比DEC檢測器約低1.5 dB，具有良好的抗遠(yuǎn)近效應(yīng)能力。

仿真實(shí)驗(yàn)3：為了驗(yàn)證算法的收斂特性，設(shè)置信噪比為8 dB，最大進(jìn)化代數(shù)為30。不同檢測器的平均誤碼率隨進(jìn)化代數(shù)的變化情況如圖4所示。由圖4中可以看出，IIWO檢測器的收斂性能明顯優(yōu)于PSO檢測器、IWO檢測器和GA檢測器，在進(jìn)化代數(shù)為10時(shí)，即可找到最優(yōu)解。

仿真實(shí)驗(yàn)4：為驗(yàn)證檢測器性能隨用戶數(shù)量的變化情況，設(shè)信噪比為8 dB，最大進(jìn)化代數(shù)為30。所有用戶的平均誤碼率變化情況如圖5所示?？梢钥闯觯琁IWO算法的誤碼率最低。

圖3 不同檢測器抗遠(yuǎn)近效應(yīng)能力對比

圖4 不同檢測器收斂性能對比

圖5 檢測性能隨用戶數(shù)量變化情況

5 結(jié)束語

為了將入侵雜草優(yōu)化算法應(yīng)用于多用戶檢測，本文在算法中引入映射函數(shù)，針對基本正態(tài)分布標(biāo)準(zhǔn)差收斂速度慢的問題，提出改進(jìn)的標(biāo)準(zhǔn)差變化曲線。仿真結(jié)果表明，該方法在抗多址干擾、抗遠(yuǎn)近效應(yīng)能力方面接近最優(yōu)多用戶檢測；收斂速度優(yōu)于基本GA，PSO，IWO算法；當(dāng)用戶數(shù)量變化時(shí)，檢測性能優(yōu)于CD、DEC和其他3種基于智能算法的檢測器；而且計(jì)算復(fù)雜度要明顯低于OMD檢測器。下一步將研究IWO算法與其他智能算法相結(jié)合的多用戶檢測器，進(jìn)一步提高檢測器的收斂速度和魯棒性。