鄧樂樂，周方明，趙璐璐，梁廣，余金培

(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)后的測量矩陣測量所得的信號可保留更多信息，使得壓縮感知捕獲算法在較低信噪比條件下的捕獲性能得到提高。

1 GNSS信號稀疏性

壓縮感知過程有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)

2 改進(jìn)的壓縮感知捕獲算法

2.1 基于奇異值分解的測量矩陣構(gòu)造

信號的測量是進(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)

2.2 信號重構(gòu)

信號的重構(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.3 算法框圖

圖2 本文算法流程圖Fig.2 The algorithm flow chart of this paper

3 仿真與分析

3.1 計(jì)算復(fù)雜度分析

捕獲算法的計(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

3.2 仿真

對本文提出的基于奇異值分解的壓縮感知捕獲算法(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

4 總結(jié)

基于GNSS信號的稀疏性，壓縮感知可用于信號捕獲，降低捕獲過程的運(yùn)算量，但其算法在低信噪比條件下的捕獲概率會有較大的降低。本文以提高捕獲概率為目標(biāo)，從改進(jìn)測量矩陣出發(fā)，提出一種基于奇異值分解的壓縮感知捕獲算法。首先基于GNSS信號稀疏性構(gòu)造稀疏矩陣；其次，對高斯隨機(jī)測量矩陣進(jìn)行奇異值平均，產(chǎn)生新的測量矩陣，最后利用稀疏矩陣和新的測量矩陣完成信號的壓縮感知捕獲。仿真結(jié)果驗(yàn)證了本文算法的有效性，在計(jì)算量略有增加的情況下，可明顯提高一定信噪比條件下壓縮感知捕獲算法的捕獲性能。