蔡麗萍, 孫 莉, 李世寶, 陳海華, 龔 琛

(中國(guó)石油大學(xué)(華東)計(jì)算機(jī)與通信工程學(xué)院,青島 266580)

限定GA搜索空間的WSF求解算法①

蔡麗萍, 孫 莉, 李世寶, 陳海華, 龔 琛

(中國(guó)石油大學(xué)(華東)計(jì)算機(jī)與通信工程學(xué)院,青島 266580)

波達(dá)方向(DOA)估計(jì)在無(wú)線傳感器網(wǎng)絡(luò)中得到了廣泛的應(yīng)用,本文針對(duì)DOA中加權(quán)子空間擬合(WSF)算法多維非線性優(yōu)化計(jì)算量大的問(wèn)題,提出一種限定遺傳搜索空間的WSF求解算法.該方法將旋轉(zhuǎn)不變子空間(ESPRIT)與無(wú)偏估計(jì)量的理論最小誤差(TME)相結(jié)合來(lái)限定遺傳算法的搜索空間,通過(guò)縮短遺傳算法的基因長(zhǎng)度來(lái)降低加權(quán)子空間擬合算法的求解復(fù)雜度.仿真結(jié)果表明,該算法的估計(jì)性能與WSF基本相同,與其它的一些智能優(yōu)化算法相比,顯著的降低了算法的計(jì)算量.

波達(dá)方向估計(jì);加權(quán)子空間擬合;遺傳算法;計(jì)算復(fù)雜度;傳感器網(wǎng)絡(luò)

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)是由傳感、數(shù)據(jù)收集、處理和無(wú)線通信單元的低成本、小體積傳感器節(jié)點(diǎn)構(gòu)成的自組織網(wǎng)絡(luò),在特定的環(huán)境下自動(dòng)的完成制定任務(wù)的智能系統(tǒng).現(xiàn)在,無(wú)線傳感器網(wǎng)絡(luò)在醫(yī)療健康、生態(tài)環(huán)境監(jiān)測(cè)、軍事、智能交通控制等領(lǐng)域應(yīng)用比較廣泛[1,2].目標(biāo)跟蹤與定位成為當(dāng)前無(wú)線傳感器網(wǎng)絡(luò)的熱點(diǎn)問(wèn)題.

近年來(lái)基于無(wú)線傳感器網(wǎng)絡(luò)目標(biāo)定位的研究越來(lái)越多.比較常用的目標(biāo)定位的方法主要有到達(dá)時(shí)間(Time of Arrival,TOA)、到達(dá)時(shí)間差[3](Time Delay of Arrival,TDOA)、波達(dá)方向估計(jì)[4](Direction of Arrival,DOA)等定位方法.其中DOA估計(jì)的基本理論和基本算法已經(jīng)相當(dāng)成熟,而且被廣泛的應(yīng)用在雷達(dá)、聲納、醫(yī)學(xué)等許多的領(lǐng)域[5,6].基于子空間理論的加權(quán)子空間擬合(Weighted Subplace Fitting,WSF)算法[7]是DOA估計(jì)中的重要算法,該算法可以獲得比較精確的信號(hào)方向估計(jì)值,但是此算法的計(jì)算復(fù)雜度比較高,在實(shí)際中難以使用,因此,如何降低WSF算法的計(jì)算量的問(wèn)題已成為研究熱點(diǎn).

仿生學(xué)智能優(yōu)化算法通過(guò)模擬自然界生物的行為來(lái)解決復(fù)雜的優(yōu)化問(wèn)題,隨著優(yōu)化算法的不斷發(fā)展,這類優(yōu)化算法被應(yīng)用在對(duì)WSF算法的求解中.文獻(xiàn)[8]入連續(xù)蟻群優(yōu)化算法,通過(guò)利用算法中的信息量高斯概率分布函數(shù)求得全局最優(yōu)值,減少了WSF算法的計(jì)算量;文獻(xiàn)[9]利用人工蜂群優(yōu)化算法對(duì)WSF算法中多維非線性問(wèn)題進(jìn)行優(yōu)化,降低了WSF算法的計(jì)算復(fù)雜度;文獻(xiàn)[10]采用混合蛙跳(Shuffled Frog Leaping Algorithm,SFLA)算法求解WSF算法,進(jìn)而降低了WSF算法的運(yùn)算時(shí)間;文獻(xiàn)[11]在使用粒子群求解WSF算法的過(guò)程中,利用粒子群跟蹤算法,將目標(biāo)函數(shù)限定在一個(gè)很小的搜索空間內(nèi),減少了WSF算法的計(jì)復(fù)雜度.

遺傳(Genetic Algorithm,GA)算法由于發(fā)展成熟、結(jié)構(gòu)簡(jiǎn)單、全局搜索能力強(qiáng)等優(yōu)點(diǎn)在許多復(fù)雜的優(yōu)化問(wèn)題中得到廣泛的應(yīng)用.文獻(xiàn)[12]將GA算法應(yīng)用在網(wǎng)絡(luò)編碼優(yōu)化問(wèn)題中,通過(guò)修正GA算法的流程使得優(yōu)化算法的復(fù)雜度降低;文獻(xiàn)[13]利用GA算法,對(duì)采用多變量、高非線性的似然函數(shù)的DOA估計(jì)進(jìn)行求解,在保證全局收斂的同時(shí)降低了算法的復(fù)雜度;文獻(xiàn)[14]將GA算法直接應(yīng)用在對(duì)WSF算法的求解過(guò)程中,加快了WSF算法的收斂速度,減少了算法的計(jì)算量;文獻(xiàn)[15]將模擬退火思想融合到GA算法中,改善傳統(tǒng)GA算法的一些弊端,以降低WSF算法的計(jì)算復(fù)雜度.但是后前大多數(shù)是直接利用GA算法對(duì)WSF算法進(jìn)行求解,缺少針對(duì)WSF算法的特性對(duì)GA算法中的參數(shù)進(jìn)行修改,計(jì)算復(fù)雜度比較高.針對(duì)這一問(wèn)題,本文在WSF算法的求解空間中利用ESPRIT算法結(jié)合無(wú)偏估計(jì)量的理論最小誤差限定一個(gè)較小且包含全局最優(yōu)值的搜索空間,在此較小的空間中利用GA算法進(jìn)行求解,降低算法的計(jì)算復(fù)雜度.

1 數(shù)學(xué)模型

假設(shè)有q個(gè)遠(yuǎn)場(chǎng)窄帶信號(hào),入射到c個(gè)傳感器上,入射角分別為其中傳感器陣列之間的間距中心頻率的波長(zhǎng)則陣列輸出表示為:

關(guān)于陣列快拍數(shù)據(jù)的協(xié)方差矩陣為:

其中RS是信號(hào)協(xié)方差矩陣,RN是噪聲協(xié)方差矩陣.在具體的實(shí)現(xiàn)中,對(duì)R進(jìn)行特征值分解:

在理想情況下,當(dāng)估計(jì)信源與真實(shí)信源相等時(shí),可以得到:

當(dāng)噪聲存在時(shí),上式(4)不一定成立.為解決上述問(wèn)題,構(gòu)造一個(gè)擬合關(guān)系,找出一個(gè)矩陣T使式(4)成立,且兩者在最小二乘意義下擬合的最好,推廣到一般形式的加權(quán)子空間擬合問(wèn)題,即:

2 遺傳算法

遺傳算法具有很強(qiáng)的全局搜索性能,適合并行處理,在許多領(lǐng)域中得到了廣泛的應(yīng)用.圖1是遺傳算法的流程示意圖.

它是利用“優(yōu)勝劣汰,適者生存”的生物競(jìng)爭(zhēng)進(jìn)化理論,根據(jù)預(yù)先設(shè)定的目標(biāo)適應(yīng)度函數(shù),通過(guò)遺傳過(guò)程中的選擇、交叉、變異對(duì)個(gè)體進(jìn)行篩選,適應(yīng)度高的個(gè)體得以保留,形成的新群體既繼承上一代信息又優(yōu)于上一代.通過(guò)不斷的競(jìng)爭(zhēng)選擇,群體的適應(yīng)值得到改善,使得種群朝著有最優(yōu)解的方向進(jìn)化,通過(guò)不斷地繁衍進(jìn)化,進(jìn)而導(dǎo)群體逐漸逼近最優(yōu)解,直到滿足一定條件為止.

圖1 遺傳算法的流程示意圖

3 限定遺傳搜索空間的WSF求解算法

3.1 遺傳算法搜索空間

3.1.1 定位搜索空間

旋轉(zhuǎn)不變子空間(Estimation of signal parameters via rotational invariance techniques,ESPRIT)算法通過(guò)計(jì)算可以直接得到信號(hào)的方向信息,不存在譜峰搜索的步驟,計(jì)算復(fù)雜度遠(yuǎn)低于WSF算法,但是該算法的精度較低.因?yàn)镋SPRIT算法和WSF算法都是對(duì)DOA估計(jì)求解,所以ESPRIT算法的解在WSF算法的全局最優(yōu)解附近.因此,選用ESPRIT算法的解為中心縮小本文中遺傳算法的搜索空間,加快算法收斂,進(jìn)而降低算法的計(jì)算復(fù)雜度.

ESPRIT算法求解DOA是利用子陣間的旋轉(zhuǎn)不變性,對(duì)于同一個(gè)信號(hào)的兩個(gè)子陣X1、X2對(duì)應(yīng)的陣列流型矩陣A1、A2之間存在一個(gè)旋轉(zhuǎn)不變關(guān)系,由式(5)可以得知兩個(gè)子信號(hào)的空間關(guān)系:

就能夠獲得信號(hào)的入射角信息.

3.1.2 確定基因長(zhǎng)度

在本文中,通過(guò)對(duì)確定的合適搜索空間進(jìn)行編碼,進(jìn)而確定GA算法的基因長(zhǎng)度.

為了讓GA算法更快地搜索出WSF算法的精確解,本文以ESPRIT算法的值為中心選取一個(gè)搜索空間.在保證一定精度的情況下,如果搜索空間選取的過(guò)大,此時(shí)GA算法需要選取初始種群中個(gè)體的種類較多,基因長(zhǎng)度會(huì)變長(zhǎng),計(jì)算復(fù)雜度較高.如果搜索空間選取的太小可能不包含全局最優(yōu)值,雖然GA算法選取的初始種群中個(gè)體的種類較少,基因長(zhǎng)度會(huì)變短,算法需要執(zhí)行到設(shè)定的遺傳代數(shù)才可能停止計(jì)算,計(jì)算時(shí)間較長(zhǎng),復(fù)雜度升高.因此,一個(gè)合適的搜索空間對(duì)初始種群和基因長(zhǎng)度的選取非常重要.

無(wú)偏估計(jì)量的理論最小誤差(Theoretical Minimum Error,TME)可以為DOA無(wú)偏估計(jì)量的方差確定一個(gè)下界,TME的大小與SNR和快拍數(shù)有關(guān).將放大μ倍的TME作為搜索空間的半邊長(zhǎng),用來(lái)確定GA算法初始種群的基因長(zhǎng)度.搜索空間的邊長(zhǎng)可以表示為2μ*TME.隨著信號(hào)信噪比的降低,ESPRIT算法的均方誤差會(huì)逐漸升高,與算法需要求得的全局最優(yōu)值相差較大,但是搜索空間應(yīng)該包含全局最優(yōu)解,所以搜索空間的放大倍數(shù)μ也需要適當(dāng)?shù)脑黾?因此GA算法初始種群的基因長(zhǎng)度需根據(jù)信噪比的變化進(jìn)行調(diào)整.

初始化空間可表示為:

如果選取的搜索空間包含全局最優(yōu)解且空間相對(duì)較小,此時(shí)GA算法的基因長(zhǎng)度最合適,并且能夠產(chǎn)生比較優(yōu)良的初始種群個(gè)體,算法可以在較短的時(shí)間內(nèi)搜索出全局最優(yōu)值.

3.2 限定遺傳搜索空間的WSF求解算法步驟

通過(guò)上文3.1節(jié)確定合適的搜索空間,在此確定空間的基礎(chǔ)上通過(guò)入GA算法對(duì)WSF算法進(jìn)行求解.

3.2.1 算法的步驟

限定GA搜索空間的WSF求解算法的設(shè)計(jì)步驟如下:

1)計(jì)算ESPRIT的解和TME.根據(jù)信噪比的不同確定TME的放大倍數(shù),由式(12)劃分出搜索空間的大小.

2)初始化種群.產(chǎn)生第一代個(gè)體,在經(jīng)過(guò)1)步確定的搜索空間中,為了避免隨機(jī)方式產(chǎn)生初始種群分布的不均勻,本文采用單元分布法,在搜索空間中根據(jù)種群的大小按照一定的單元選取種群的個(gè)體.

上式中θi是變量θ的第i個(gè)取值點(diǎn).對(duì)取得的m個(gè)點(diǎn)采用十進(jìn)制的編碼方式產(chǎn)生初始種群.

3)適應(yīng)值計(jì)算.選用上式(7)作為適應(yīng)度函數(shù),計(jì)算群體中個(gè)體的的適應(yīng)值.

4)選擇操作.選擇父代種群個(gè)體要進(jìn)行的操作.在實(shí)驗(yàn)中,采用最優(yōu)值保存策略和比例選擇法相結(jié)合,父代個(gè)體按適應(yīng)度大小排序,然后根據(jù)最優(yōu)保存策略,父代個(gè)體中適應(yīng)值較高的個(gè)體替換適應(yīng)值較低的個(gè)體,不進(jìn)行5)步的操作直接遺傳到子代.利用比例選擇法選出父代中適應(yīng)值較低的個(gè)體進(jìn)行5)步操作.

5)交叉和變異操作.通過(guò)該操作增加種群的多樣性.在實(shí)驗(yàn)中,分別采用的是單點(diǎn)交叉和基本位變異的方法.

6)迭代終止.若群體中個(gè)體的平均適應(yīng)值趨于穩(wěn)定或者達(dá)到設(shè)定的最大迭代次數(shù),則停止迭代,輸出算法的最優(yōu)值;如果不滿足終止條件,則返回第3)步繼續(xù)進(jìn)行迭代過(guò)程.

4 仿真性能分析

仿真模型:陣元數(shù) M=16,陣元間距Δ=λ/2,其中λ是均勻線陣列接收信號(hào)的波長(zhǎng),信號(hào)的采樣頻率是1500 Hz,快拍數(shù)是100.本實(shí)驗(yàn)中遺傳算法的參數(shù)的設(shè)置分別是:N=20,Pc=0.6,Pm=0.01.傳統(tǒng)的遺傳算法:N=100,Pc=0.6,Pm=0.01.有4個(gè)遠(yuǎn)場(chǎng)窄帶信號(hào)源,入射角度分別是:-10°、15°、30°、45°.

為了證明本算法的有效性,在實(shí)驗(yàn)中將本文算法與其他常見(jiàn)的優(yōu)化算法:傳統(tǒng)的GA算法、MUSIC算法等進(jìn)行算法性能上的比較.以下所有結(jié)果均為1000次實(shí)驗(yàn)下的平均值.

圖2(a)、(b)分別是在4信源,SNR=-10 dB、0 dB和10 dB下,μ的取值對(duì)算法精度和算法時(shí)間的影響.從圖中可以看出,當(dāng)μ大于2時(shí),μ的取值對(duì)算法的精度影響較小,此時(shí)搜索空間的大小包含全局最優(yōu)值,隨著μ取值的增加,GA算法初始種群中選取的個(gè)體種類較多,算法基因長(zhǎng)度變長(zhǎng),計(jì)算復(fù)雜度較高.當(dāng)μ小于2時(shí),μ的取值對(duì)算法的影響較大,此時(shí)搜索空間的大小可能不包含全局最優(yōu)值,雖然GA算法的初始種群中產(chǎn)生個(gè)體的種類較少,基因長(zhǎng)度較短,但是算法執(zhí)行到設(shè)定的次數(shù)也不一定找到全局最優(yōu)值,計(jì)算復(fù)雜度較高.當(dāng)μ等于2時(shí),GA的搜索空間恰好包含全局最優(yōu)值,GA算法的基因長(zhǎng)度比較合適,此時(shí)算法復(fù)雜度較低.

圖2 μ取值對(duì)算法的影響

圖3(a)、(b)分別是在4個(gè)信源下,SNR從-10 dB～20 dB變化時(shí),本文算法與WSF算法和MUSIC算法的計(jì)算精度在非相干和相干信號(hào)實(shí)驗(yàn)下的比較結(jié)果,從實(shí)驗(yàn)結(jié)果中可以看出,無(wú)論是相干還是非相干的情況,本文算法與WSF算法計(jì)算精度相當(dāng),當(dāng)信噪比較低時(shí),該算法的計(jì)算精度遠(yuǎn)遠(yuǎn)優(yōu)于MUSIC算法.

表1是在SNR=0 dB、不同信源下,本文算法與傳統(tǒng)GA算法、AM算法在保證精度相同時(shí)的計(jì)算時(shí)間.由表1可知,隨著信號(hào)數(shù)量的增加,所有算法的計(jì)算時(shí)間都會(huì)升高.AM算法在求解最優(yōu)值時(shí)是將一個(gè)多維問(wèn)題轉(zhuǎn)化成多個(gè)一維問(wèn)題,隨著信源數(shù)量的增加,計(jì)算時(shí)間呈指數(shù)增長(zhǎng).傳統(tǒng)的GA算法的計(jì)算時(shí)間小于AM算法,但是計(jì)算復(fù)雜度仍然較高.本文算法有效的減小了GA算法的搜索空間,在計(jì)算過(guò)程中,減少了GA算法的基因長(zhǎng)度和遺傳代數(shù),算法的計(jì)算復(fù)雜度更低.

圖4是在4個(gè)信源的情況下,SNR從-10 dB～20 dB變化時(shí),保證WSF算法的精度不變,本文算法與傳統(tǒng)GA算法、AM算法的計(jì)算時(shí)間的對(duì)比,從圖3可以看出,無(wú)論是相干信號(hào)(b)還是非相干信號(hào)(a),隨著信噪比的增加,算法的計(jì)算時(shí)間在緩慢的減少,但是AM算法的計(jì)算時(shí)間遠(yuǎn)遠(yuǎn)大于其它兩種算法,GA算法的計(jì)算時(shí)間雖然小于AM算法,但是仍大于本文算法.

圖3 4信源算法的估計(jì)精度

表1 不同信源算法的計(jì)算時(shí)間

5 結(jié)論

WSF算法的估計(jì)性能雖優(yōu)于其它一些子空間分解類算法,但是由于該算法存在多維非線性搜索問(wèn)題,計(jì)算量較大.本文針對(duì)WSF算法求解復(fù)雜度高的問(wèn)題,利用ESPRIT算法和無(wú)偏估計(jì)量的理論最小誤差確定GA算法搜索空間的位置和初始空間的大小,提出了一種限定GA搜索空間的加權(quán)子空間擬合算法.從仿真結(jié)果可以看出,本文算法在保證WSF算法的優(yōu)良性能的同時(shí),降低WSF算法的計(jì)算復(fù)雜度.尤其是在多信源的條件下,相比使用常規(guī)的GA算法直接求解,計(jì)算效率大幅度的提升.

圖4 4信源算法的計(jì)算時(shí)間

1 徐立鋒.基于無(wú)線傳感器網(wǎng)絡(luò)技術(shù)在交通信息采集系統(tǒng)的應(yīng)用.計(jì)算機(jī)應(yīng)用與軟件,2012,29(4):236–241,262.

2 王驥,林杰華,謝仕義.基于無(wú)線傳感網(wǎng)絡(luò)的環(huán)境監(jiān)測(cè)系統(tǒng).傳感技術(shù)學(xué)報(bào),2015,24(11):1732–1740.[doi:10.3969/j.issn.1004-1699.2015.11.026]

3 Yu Y,Silverman HF.An improved TDOA-based location estimation algorithm for large aperture microphone arrays.Proc.of IEEE International Conference on Acoustics,Speech,and Signal Processing,2004.Montreal,Que,Canada.2004,4.iv-77-iv-80.

4 Jian M,Kot AC,Er MH.DOA estimation of speech source with microphone arrays.Proc.of IEEE International Symposium on Circuits and Systems.Monterey,CA,Canada.1998.293–296.

5 黃中瑞,張劍云,周青松.雙基地MIMO雷達(dá)發(fā)射功率聚焦的角度估計(jì)算法研究.電子與信息學(xué)報(bào),2015,37(10):2314–2320.

6 Li YX,Gu SN,Zheng NE.MIMO radar transmit beampattern design for DOA estimation with sidelobe suppression.International Journal of Antennas and Propagation,2016,2016:1512843.

7 Viberg M,Ottersten B,Kailath T.Detection and estimation in sensor arrays using weighted subspace fitting.IEEE Trans.on Signal Proc.,1991,39(11):2436–2449.[doi:10.1109/78.97999]

8 焦亞萌,黃建國(guó),韓晶.基于連續(xù)蟻群優(yōu)化算法的小快拍加權(quán)子空間擬合快速算法.電子與信息學(xué)報(bào),2011,33(4):972–976.

9 Zhang ZC,Lin J,Shi YW.Joint angle-frequency estimation based on WSF using artificial bee colony algorithm.Proc.of 2013 International Conference on Information Science and Technology (ICIST).Yangzhou,China.2013.1312–1315.

10 Zhang ZC,Yu XH,Sun HX.Weighted subspace fitting DOA estimation based on shuffled frog leaping algorithm.Applied Mechanics and Materials,2013,411-414:1049–1052.[doi:10.4028/www.scientific.net/AMM.411-414]

11 刁鳴,袁熹,高洪元,等.一種新的基于粒子群算法的DOA跟蹤方法.系統(tǒng)工程與電子技術(shù),2009,31(9):2046–2049.

12 鄧亮,趙進(jìn),王新.基于遺傳算法的網(wǎng)絡(luò)編碼優(yōu)化.軟件學(xué)報(bào),2009,20(8):2269–2279.

13 Li M,Lu Y.Genetic algorithm based maximum likelihood DOA estimation.RADAR 2002.Edinburgh,UK.2002.502–506.

14 申冰,周群.一種基于遺傳算法的加權(quán)子空間求解法.航天電子對(duì)抗,2007,23(3):51–53,60.

15 賈偉娜,劉順蘭.模擬退火遺傳算法在DOA估計(jì)技術(shù)中的應(yīng)用.計(jì)算機(jī)工程與應(yīng)用,2014,50(12):266–270.[doi:10.3778/j.issn.1002-8331.1206-0247]

WSF Solving Algorithm Based on Limited GA Search Space

CAI Li-Ping,SUN Li,LI Shi-Bao,CHEN Hai-Hua,GONG Chen
(College of Computer and Communication Engineering,China University of Petroleum,Qingdao 266580,China)

The direction of arrival estimation has been widely employed in Wireless Sensor Networks.This paper proposes a Weighted Subspace Fitting algorithm which can largely reduce the computation amount when doing highdimensional non-linear optimization by limiting the genetic searching space.This method uses rotation invariant subspace and unbiased estimator of the theoretical minimum error to limit the search space and the complexity of WSF algorithm is reduced by shortening the genetic length of genetic algorithm.The simulation results show that this algorithm has the same performance as the WSF algorithm.Compared with other intelligent optimization algorithms,the proposed algorithm significantly reduces the computational complexity of the algorithm.

DOA estimation;weighted subspace fitting;genetic algorithm;computational complexity;wireless sensor networks

蔡麗萍,孫莉,李世寶,陳海華,龔琛.限定GA搜索空間的WSF求解算法.計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(9):170–175.http://www.c-sa.org.cn/1003-3254/5952.html

① 基金項(xiàng)后:中國(guó)自然科學(xué)基金青年基金(61601519);青島市科技創(chuàng)新計(jì)劃(2014-1-45);青島市科技創(chuàng)新計(jì)劃(15-9-80-jch);中央高校研究基金(15CX05025A)

2016-12-28;采用時(shí)間:2017-01-18