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

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

(中國石油大學(華東)計算機與通信工程學院,青島 266580)

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

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

(中國石油大學(華東)計算機與通信工程學院,青島 266580)

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

波達方向估計;加權子空間擬合;遺傳算法;計算復雜度;傳感器網絡

無線傳感器網絡(Wireless Sensor Network,WSN)是由傳感、數據收集、處理和無線通信單元的低成本、小體積傳感器節點構成的自組織網絡,在特定的環境下自動的完成制定任務的智能系統.現在,無線傳感器網絡在醫療健康、生態環境監測、軍事、智能交通控制等領域應用比較廣泛[1,2].目標跟蹤與定位成為當前無線傳感器網絡的熱點問題.

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

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

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

1 數學模型

假設有q個遠場窄帶信號,入射到c個傳感器上,入射角分別為其中傳感器陣列之間的間距中心頻率的波長則陣列輸出表示為:

關于陣列快拍數據的協方差矩陣為:

其中RS是信號協方差矩陣,RN是噪聲協方差矩陣.在具體的實現中,對R進行特征值分解:

在理想情況下,當估計信源與真實信源相等時,可以得到:

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

2 遺傳算法

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

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

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

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

3.1 遺傳算法搜索空間

3.1.1 定位搜索空間

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

ESPRIT算法求解DOA是利用子陣間的旋轉不變性,對于同一個信號的兩個子陣X1、X2對應的陣列流型矩陣A1、A2之間存在一個旋轉不變關系,由式(5)可以得知兩個子信號的空間關系:

就能夠獲得信號的入射角信息.

3.1.2 確定基因長度

在本文中,通過對確定的合適搜索空間進行編碼,進而確定GA算法的基因長度.

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

無偏估計量的理論最小誤差(Theoretical Minimum Error,TME)可以為DOA無偏估計量的方差確定一個下界,TME的大小與SNR和快拍數有關.將放大μ倍的TME作為搜索空間的半邊長,用來確定GA算法初始種群的基因長度.搜索空間的邊長可以表示為2μ*TME.隨著信號信噪比的降低,ESPRIT算法的均方誤差會逐漸升高,與算法需要求得的全局最優值相差較大,但是搜索空間應該包含全局最優解,所以搜索空間的放大倍數μ也需要適當的增加,因此GA算法初始種群的基因長度需根據信噪比的變化進行調整.

初始化空間可表示為:

如果選取的搜索空間包含全局最優解且空間相對較小,此時GA算法的基因長度最合適,并且能夠產生比較優良的初始種群個體,算法可以在較短的時間內搜索出全局最優值.

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

通過上文3.1節確定合適的搜索空間,在此確定空間的基礎上通過入GA算法對WSF算法進行求解.

3.2.1 算法的步驟

限定GA搜索空間的WSF求解算法的設計步驟如下:

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

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

上式中θi是變量θ的第i個取值點.對取得的m個點采用十進制的編碼方式產生初始種群.

3)適應值計算.選用上式(7)作為適應度函數,計算群體中個體的的適應值.

4)選擇操作.選擇父代種群個體要進行的操作.在實驗中,采用最優值保存策略和比例選擇法相結合,父代個體按適應度大小排序,然后根據最優保存策略,父代個體中適應值較高的個體替換適應值較低的個體,不進行5)步的操作直接遺傳到子代.利用比例選擇法選出父代中適應值較低的個體進行5)步操作.

5)交叉和變異操作.通過該操作增加種群的多樣性.在實驗中,分別采用的是單點交叉和基本位變異的方法.

6)迭代終止.若群體中個體的平均適應值趨于穩定或者達到設定的最大迭代次數,則停止迭代,輸出算法的最優值;如果不滿足終止條件,則返回第3)步繼續進行迭代過程.

4 仿真性能分析

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

為了證明本算法的有效性,在實驗中將本文算法與其他常見的優化算法:傳統的GA算法、MUSIC算法等進行算法性能上的比較.以下所有結果均為1000次實驗下的平均值.

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

圖2 μ取值對算法的影響

圖3(a)、(b)分別是在4個信源下,SNR從-10 dB～20 dB變化時,本文算法與WSF算法和MUSIC算法的計算精度在非相干和相干信號實驗下的比較結果,從實驗結果中可以看出,無論是相干還是非相干的情況,本文算法與WSF算法計算精度相當,當信噪比較低時,該算法的計算精度遠遠優于MUSIC算法.

表1是在SNR=0 dB、不同信源下,本文算法與傳統GA算法、AM算法在保證精度相同時的計算時間.由表1可知,隨著信號數量的增加,所有算法的計算時間都會升高.AM算法在求解最優值時是將一個多維問題轉化成多個一維問題,隨著信源數量的增加,計算時間呈指數增長.傳統的GA算法的計算時間小于AM算法,但是計算復雜度仍然較高.本文算法有效的減小了GA算法的搜索空間,在計算過程中,減少了GA算法的基因長度和遺傳代數,算法的計算復雜度更低.

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

圖3 4信源算法的估計精度

表1 不同信源算法的計算時間

5 結論

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

圖4 4信源算法的計算時間

1 徐立鋒.基于無線傳感器網絡技術在交通信息采集系統的應用.計算機應用與軟件,2012,29(4):236–241,262.

2 王驥,林杰華,謝仕義.基于無線傳感網絡的環境監測系統.傳感技術學報,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雷達發射功率聚焦的角度估計算法研究.電子與信息學報,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 焦亞萌,黃建國,韓晶.基于連續蟻群優化算法的小快拍加權子空間擬合快速算法.電子與信息學報,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跟蹤方法.系統工程與電子技術,2009,31(9):2046–2049.

12 鄧亮,趙進,王新.基于遺傳算法的網絡編碼優化.軟件學報,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 申冰,周群.一種基于遺傳算法的加權子空間求解法.航天電子對抗,2007,23(3):51–53,60.

15 賈偉娜,劉順蘭.模擬退火遺傳算法在DOA估計技術中的應用.計算機工程與應用,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求解算法.計算機系統應用,2017,26(9):170–175.http://www.c-sa.org.cn/1003-3254/5952.html

① 基金項后:中國自然科學基金青年基金(61601519);青島市科技創新計劃(2014-1-45);青島市科技創新計劃(15-9-80-jch);中央高校研究基金(15CX05025A)

2016-12-28;采用時間:2017-01-18