鄧樂樂,周方明,趙璐璐,梁廣,余金培
(1 中國科學(xué)院微小衛(wèi)星創(chuàng)新研究院,上海 201203;2 中國科學(xué)院大學(xué),北京 100049)
全球?qū)Ш叫l(wèi)星系統(tǒng)(global navigation satellite system,GNSS)可為用戶提供全方位、高精度的導(dǎo)航及授時(shí)信息。隨著GNSS在智能設(shè)備及傳感器網(wǎng)絡(luò)中的普及,人們對GNSS接收機(jī)的性能及功耗要求更高。捕獲模塊作為GNSS信號接收中的關(guān)鍵步驟,運(yùn)算量大、資源消耗多,是影響接收機(jī)接收性能的重要因素。
GNSS一般采用擴(kuò)頻調(diào)制技術(shù),衛(wèi)星信號的捕獲需要進(jìn)行多個(gè)碼相位及大動態(tài)多普勒頻率的搜索,搜索量較大。傳統(tǒng)串行搜索方法,對信號所有可能的碼相位和頻率進(jìn)行二維搜索,運(yùn)算量大。因此,降低捕獲模塊運(yùn)算量是接收機(jī)性能優(yōu)化的關(guān)鍵。文獻(xiàn)[1]提出一種基于圓周移位的并行碼相位算法,將搜索中的多次快速傅里葉變換(fast Fourier transform,F(xiàn)FT)用計(jì)算量很小的頻譜搬移來代替,使運(yùn)算量大幅下降。文獻(xiàn)[2]在基于FFT的并行碼相位捕獲算法基礎(chǔ)上,提出稀疏傅里葉變換的方法,通過提高捕獲過程中相關(guān)運(yùn)算的效率,減少了運(yùn)算量。文獻(xiàn)[3]提出一種雙塊零擴(kuò)展截?cái)嘞嚓P(guān)的捕獲算法,根據(jù)復(fù)序列頻譜的非對稱性對信號進(jìn)行截?cái)囝A(yù)處理,同時(shí)結(jié)合雙塊零擴(kuò)展與圓周移位,減少了運(yùn)算量。
壓縮感知(compressed sensing,CS)是由Donoho[4]、Candes等[5]提出的一種新的信號處理方法。該方法充分利用信號的稀疏特性,可大大降低信號的采樣速率,為降低捕獲所需的運(yùn)算量提供了新途徑。壓縮感知用于GNSS信號捕獲的關(guān)鍵點(diǎn)主要在于:信號稀疏性和合適的測量重構(gòu)算法?;谶@2個(gè)關(guān)鍵點(diǎn),文獻(xiàn)[6]提出以C/A碼的正交基矩陣為稀疏域,利用卡爾曼濾波重構(gòu)信號的壓縮感知捕獲算法,但重構(gòu)過程復(fù)雜。文獻(xiàn)[7]提出基于峰值位置的壓縮感知方案,但稀疏矩陣存儲量巨大。文獻(xiàn)[8]將CS理論融入交錯(cuò)方向乘子法的框架,提出一種高效的并行捕獲算法。文獻(xiàn)[9]提出基于壓縮感知改進(jìn)的部分匹配濾波FFT算法,降低了運(yùn)算量和資源消耗,但沒有考慮低信噪比問題。
本文基于對GNSS信號稀疏性的分析,利用C/A碼構(gòu)造稀疏矩陣,提出一種基于奇異值分解的壓縮感知捕獲方法,該方法通過對高斯隨機(jī)測量矩陣進(jìn)行奇異值平均,使其列向量線性非相干性更好,能更好地測量信號,改進(jìn)后的測量矩陣測量所得的信號可保留更多信息,使得壓縮感知捕獲算法在較低信噪比條件下的捕獲性能得到提高。
壓縮感知過程有3個(gè)關(guān)鍵步驟:信號的稀疏表示、信號測量以及信號重構(gòu)。其中信號的稀疏性是壓縮感知應(yīng)用的前提。
當(dāng)長度為N的信號中只有K(K?N)個(gè)非零的值,或其他值都接近于零時(shí),我們認(rèn)為信號具有稀疏性,其稀疏度為K。但通常實(shí)際處理信號不稀疏,這就需要對原始信號進(jìn)行稀疏表示,即對原始信號進(jìn)行某種變換,變換到某個(gè)域,使其在該域的表示是稀疏的。
以全球定位系統(tǒng)(global positioning system,GPS)為例,GNSS信號由載波、測距碼和導(dǎo)航信息組成。在衛(wèi)星發(fā)射端,先將測距碼與導(dǎo)航信息調(diào)制為組合碼,再通過載波擴(kuò)頻調(diào)制形成最終信號。接收信號時(shí),射頻前端接收信號并采樣成為離散的中頻信號,然后進(jìn)行捕獲處理,中頻信號的數(shù)學(xué)表達(dá)式為
x(n)=AD(n)C(n)exp(j((wIF+wd)n+φ))+
v(n),n=0,1,…,N-1.
(1)
式中:A為信號幅度;D(n)為導(dǎo)航信息;C(n)為偽隨機(jī)的測距碼,即C/A碼;wIF為中頻頻率;φ為載波相位;wd表示衛(wèi)星與用戶終端相對運(yùn)動產(chǎn)生的多普勒頻移;v(n)為高斯白噪聲;N為信號長度。
C/A碼是碼率為1.023 Mbit/s的Gold碼,碼長為1 023。每個(gè)GPS衛(wèi)星有唯一的C/A碼,不同GPS衛(wèi)星的C/A碼相互正交,同一GPS衛(wèi)星的C/A碼及其循環(huán)移位序列也相互正交。衛(wèi)星接收信號本身并不具有稀疏性,但由于C/A碼良好的自相關(guān)性和互相關(guān)性,在碼相位搜索域上,只有本地偽碼相位與接收信號碼相位對齊時(shí)相關(guān)結(jié)果才具有峰值,因此其碼相關(guān)結(jié)果具有稀疏性,可選擇 C/A碼的循環(huán)移位矩陣作為信號的稀疏變換域[6]。
假設(shè)c(0)=[c0,c1,…,cN-1]∈N×1為任意GPS衛(wèi)星的C/A碼,將其循環(huán)移位i個(gè)碼片后,得到序列c(i)=[ci,ci+1,…cN-1,c0,…ci-1]∈N×1,i=0,1,…N-1。構(gòu)造稀疏矩陣如下:
(2)
vr(n),n=0,1,…,N-1.
(3)
(4)
信號的測量是進(jìn)行信號由高維到低維的映射,使用和稀疏矩陣G不相關(guān)的M×N(M?N)維的測量矩陣B對信號進(jìn)行壓縮采樣,定義壓縮比a=M/N。得到M×N維的測量序列:即
Y=Br.
(5)
測量矩陣B必須保證不會把2個(gè)不同的稀疏信號映射到同一個(gè)采樣集中,這就要求測量矩陣中任意M個(gè)列向量組成的矩陣行列式不為零,即為非奇異矩陣[10]。
滿足上述條件的矩陣可作為測量矩陣對矩陣進(jìn)行壓縮。目前測量矩陣主要有隨機(jī)矩陣、確定性矩陣和部分隨機(jī)矩陣等[11]。高斯隨機(jī)測量矩陣與大多數(shù)正交稀疏矩陣都不相關(guān),是壓縮感知中適應(yīng)性最廣的測量矩陣[10],但其自身的不確定性會造成捕獲結(jié)果的不確定性,使捕獲成功率下降。本文根據(jù)奇異值分解(singular value decomposition,SVD)[12]對其進(jìn)行改進(jìn)。
奇異值分解定理如下:設(shè)S是秩為z(0 (6) (7) 根據(jù)矩陣奇異值理論可知:矩陣奇異值代表矩陣中隱含的特征信息[13],且特征重要性和奇異值大小成正比。 幾何上來說SVD就是將一個(gè)復(fù)雜的空間變換分解為3個(gè)基本變換,V是旋轉(zhuǎn),Σ是縮放,U是投影。以二維矩陣的圖解為例,在圖1中:奇異值σi就是映射后的正交基ui的模的大小,即σi=|Svi|,向量ui為Svi方向上的單位向量。 圖1 奇異值分解圖解Fig.1 The diagram of singular value decomposition 結(jié)合矩陣?yán)碚摚娈愔郸襥衡量每個(gè)列向量對于S的權(quán)重,表示矩陣S對應(yīng)的第i個(gè)列向量在子空間的分布。矩陣S的z個(gè)奇異值的大小差距越小,則表明其列向量分布越分散,其線性獨(dú)立性越好,符合壓縮感知對于測量矩陣的要求。 1)生成高斯隨機(jī)測量矩陣BM×N i=1,2,…,M;j=1,2,…,N. (8) 2)對B進(jìn)行奇異值分解 (9) 3)對Σ對角線上的值求平均Mean=(σ1+σ2+…σM)/M;令 (10) 其中:σ′1=σ′2=…σ′M=Mean。 4)得到改進(jìn)的測量矩陣 (11) 得到新的測量矩陣之后,就可以利用式(5)對信號進(jìn)行測量,得到測量信號Y。 Y=Br=BGθ. (12) 其中,BG定義為感知矩陣A(M×N) A(M×N)=BG. (13) 信號的重構(gòu)是由測量信號Y及感知矩陣A求解稀疏信號θ的過程,這是一個(gè)求解欠定方程組的問題,在信號稀疏或可壓縮的前提下,求解欠定方程組的問題可轉(zhuǎn)化為最小l0范數(shù)問題。最小l0范數(shù)在一定條件下和最小l1范數(shù)具有等價(jià)性,可得到相同的解,則該問題可以轉(zhuǎn)化為最小l1范數(shù)下的最優(yōu)化問題[5] min‖θ‖1s.t.Aθ=Y. (14) 這樣的轉(zhuǎn)化使得問題變成了一個(gè)凸優(yōu)化問題,于是可以方便地化簡為線性規(guī)劃問題。常用的重構(gòu)算法有貪婪算法、凸優(yōu)化、迭代閾值等[16]。 利用測量信號Y及感知矩陣A(M×N)對信號進(jìn)行重構(gòu),基于信號捕獲的特殊性,重構(gòu)算法只需重構(gòu)稀疏度很小的稀疏信號,且主要關(guān)注峰值位置,可選擇計(jì)算量小、穩(wěn)定的正交匹配追蹤(orthogonal matching pursuit, OMP)算法[6]。 圖2 本文算法流程圖Fig.2 The algorithm flow chart of this paper 捕獲算法的計(jì)算復(fù)雜度主要是因?yàn)樾枰啻蜗嚓P(guān)運(yùn)算。本文算法的測量過程可視為由測量矩陣與輸入信號進(jìn)行相關(guān)運(yùn)算,測量矩陣的M個(gè)行向量可視為M個(gè)壓縮相關(guān)器,完成對輸入信號的相關(guān)運(yùn)算。因此在引入壓縮感知理論對傳統(tǒng)串行捕獲算法進(jìn)行改進(jìn)之后,在相關(guān)器數(shù)量上降低到1/a,同時(shí)數(shù)據(jù)量的降低也減少了寄存器等資源消耗和后續(xù)信號處理壓力。 捕獲中一周期信號的相關(guān)次數(shù)取決于碼相位搜索精度、頻率搜索步長及多普勒頻率搜索范圍3個(gè)值的大小。本文算法主要對信號碼域進(jìn)行壓縮,頻率點(diǎn)的搜索與傳統(tǒng)串行算法的搜索次數(shù)一致,所以簡化頻域搜索分析,主要以長度為N的信號為例進(jìn)行每個(gè)頻點(diǎn)的計(jì)算復(fù)雜度分析。 對于傳統(tǒng)串行的捕獲算法,在每個(gè)頻率點(diǎn)需要對碼相位偏移N次,每次偏移進(jìn)行一次N點(diǎn)相關(guān)計(jì)算并累加,一共需要N×N次乘法,N×(N-1)次加法,其算法復(fù)雜度為O(N2)。 對于本文算法,計(jì)算量主要由相關(guān)運(yùn)算及信號重構(gòu)產(chǎn)生。當(dāng)測量矩陣為M×N的矩陣時(shí),本文相關(guān)運(yùn)算需要M×N次乘法,M×(N-1)次加法,計(jì)算復(fù)雜度為O(MN)。OMP重構(gòu)算法的復(fù)雜度目前已有很多文獻(xiàn)進(jìn)行分析[17-18],其計(jì)算量約為O(KMN);最后關(guān)于測量矩陣改進(jìn)部分的計(jì)算量主要體現(xiàn)在奇異值分解,可提前計(jì)算存儲,對捕獲過程計(jì)算量不產(chǎn)生影響。所以壓縮感知算法的復(fù)雜度為O(KMN)。表1為各算法計(jì)算量對比。 表1 算法復(fù)雜度對比Table 1 Algorithm complexity comparison 對本文提出的基于奇異值分解的壓縮感知捕獲算法(SVD-CS)進(jìn)行仿真。模擬產(chǎn)生通過加性高斯白噪聲信道的接收信號,中頻頻率40 MHz,捕獲時(shí)假設(shè)信號降采樣到2.046 MHz,每次取2 046個(gè)點(diǎn)進(jìn)行相關(guān)運(yùn)算,隨機(jī)產(chǎn)生碼相位偏移及頻率偏移。捕獲中碼相位搜索步長設(shè)為半碼片。頻率搜索步長設(shè)為500 Hz,門限值Vt設(shè)為2。 圖3是信噪比為-15 dB,測量長度為512,重 圖3 本文算法捕獲結(jié)果Fig.3 The algorithm capture result in this paper 構(gòu)稀疏度設(shè)為10時(shí)本文算法的捕獲結(jié)果。捕獲結(jié)果出現(xiàn)明顯的峰值,表明捕獲到了信號。同時(shí),峰值位置對應(yīng)的多普勒頻率與碼相位結(jié)果與模擬接收信號的結(jié)果一致。結(jié)果表明,本文算法能成功捕獲信號。 圖4是同信噪比下,捕獲性能的分析與對比,以傳統(tǒng)高斯矩陣捕獲算法(GS-CS)[19]作為對照組,信噪比為-15 dB。(a)是測量長度M與捕獲成功率曲線圖,(b)是稀疏度K與捕獲成功率曲線圖,由仿真結(jié)果可知:在同信噪比下,SVD-CS算法在不同測量長度,不同稀疏度下捕獲結(jié)果均明顯優(yōu)于GS-CS算法,且測量長度越大捕獲結(jié)果越好,稀疏度越小捕獲結(jié)果越好。 圖4 捕獲性能對比Fig.4 Capture performance comparison 圖5是不同信噪比下,以傳統(tǒng)串行算法為對照組,GS-CS算法與本文SVD-CS算法的捕獲性能對比,本組仿真中稀疏度設(shè)為1。通過4組不同測量長度對比可知:在一定信噪比范圍內(nèi),不同測量長度本文算法的捕獲成功概率均有明顯提高,且壓縮比越大,提高越明顯,表明本文算法改進(jìn)的有效性。 圖5 不同算法捕獲結(jié)果對比Fig.5 Comparison of acquisition results of different algorithms 表2是不同信噪比下本文算法的最小測量長度Mmin仿真。Mmin定義為捕獲成功率能達(dá)到90%的最小測量長度。仿真表明該算法在一定信噪比下可以以較小的測量長度達(dá)到捕獲性能要求,且信號信噪比越高,算法減少運(yùn)算量的優(yōu)勢越明顯。 表2 最小測量長度Table 2 Minimum measurement length 基于GNSS信號的稀疏性,壓縮感知可用于信號捕獲,降低捕獲過程的運(yùn)算量,但其算法在低信噪比條件下的捕獲概率會有較大的降低。本文以提高捕獲概率為目標(biāo),從改進(jìn)測量矩陣出發(fā),提出一種基于奇異值分解的壓縮感知捕獲算法。首先基于GNSS信號稀疏性構(gòu)造稀疏矩陣;其次,對高斯隨機(jī)測量矩陣進(jìn)行奇異值平均,產(chǎn)生新的測量矩陣,最后利用稀疏矩陣和新的測量矩陣完成信號的壓縮感知捕獲。仿真結(jié)果驗(yàn)證了本文算法的有效性,在計(jì)算量略有增加的情況下,可明顯提高一定信噪比條件下壓縮感知捕獲算法的捕獲性能。2.2 信號重構(gòu)
2.3 算法框圖
3 仿真與分析
3.1 計(jì)算復(fù)雜度分析
3.2 仿真
4 總結(jié)