基于奇異值分解的壓縮感知GNSS信號捕獲算法*

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

(1 中國科學院微小衛(wèi)星創(chuàng)新研究院，上海 201203；2 中國科學院大學，北京 100049)

全球?qū)Ш叫l(wèi)星系統(tǒng)(global navigation satellite system,GNSS)可為用戶提供全方位、高精度的導航及授時信息。隨著GNSS在智能設備及傳感器網(wǎng)絡中的普及，人們對GNSS接收機的性能及功耗要求更高。捕獲模塊作為GNSS信號接收中的關鍵步驟，運算量大、資源消耗多，是影響接收機接收性能的重要因素。

GNSS一般采用擴頻調(diào)制技術，衛(wèi)星信號的捕獲需要進行多個碼相位及大動態(tài)多普勒頻率的搜索，搜索量較大。傳統(tǒng)串行搜索方法，對信號所有可能的碼相位和頻率進行二維搜索，運算量大。因此，降低捕獲模塊運算量是接收機性能優(yōu)化的關鍵。文獻[1]提出一種基于圓周移位的并行碼相位算法，將搜索中的多次快速傅里葉變換(fast Fourier transform，F(xiàn)FT)用計算量很小的頻譜搬移來代替，使運算量大幅下降。文獻[2]在基于FFT的并行碼相位捕獲算法基礎上，提出稀疏傅里葉變換的方法，通過提高捕獲過程中相關運算的效率，減少了運算量。文獻[3]提出一種雙塊零擴展截斷相關的捕獲算法，根據(jù)復序列頻譜的非對稱性對信號進行截斷預處理，同時結合雙塊零擴展與圓周移位，減少了運算量。

壓縮感知(compressed sensing，CS)是由Donoho[4]、Candes等[5]提出的一種新的信號處理方法。該方法充分利用信號的稀疏特性，可大大降低信號的采樣速率，為降低捕獲所需的運算量提供了新途徑。壓縮感知用于GNSS信號捕獲的關鍵點主要在于：信號稀疏性和合適的測量重構算法?；谶@2個關鍵點，文獻[6]提出以C/A碼的正交基矩陣為稀疏域，利用卡爾曼濾波重構信號的壓縮感知捕獲算法，但重構過程復雜。文獻[7]提出基于峰值位置的壓縮感知方案，但稀疏矩陣存儲量巨大。文獻[8]將CS理論融入交錯方向乘子法的框架,提出一種高效的并行捕獲算法。文獻[9]提出基于壓縮感知改進的部分匹配濾波FFT算法，降低了運算量和資源消耗，但沒有考慮低信噪比問題。

本文基于對GNSS信號稀疏性的分析，利用C/A碼構造稀疏矩陣，提出一種基于奇異值分解的壓縮感知捕獲方法，該方法通過對高斯隨機測量矩陣進行奇異值平均，使其列向量線性非相干性更好，能更好地測量信號，改進后的測量矩陣測量所得的信號可保留更多信息，使得壓縮感知捕獲算法在較低信噪比條件下的捕獲性能得到提高。

1 GNSS信號稀疏性

壓縮感知過程有3個關鍵步驟：信號的稀疏表示、信號測量以及信號重構。其中信號的稀疏性是壓縮感知應用的前提。

當長度為N的信號中只有K(K?N)個非零的值，或其他值都接近于零時，我們認為信號具有稀疏性，其稀疏度為K。但通常實際處理信號不稀疏，這就需要對原始信號進行稀疏表示，即對原始信號進行某種變換，變換到某個域，使其在該域的表示是稀疏的。

以全球定位系統(tǒng)(global positioning system，GPS)為例，GNSS信號由載波、測距碼和導航信息組成。在衛(wèi)星發(fā)射端，先將測距碼與導航信息調(diào)制為組合碼，再通過載波擴頻調(diào)制形成最終信號。接收信號時，射頻前端接收信號并采樣成為離散的中頻信號，然后進行捕獲處理，中頻信號的數(shù)學表達式為

x(n)=AD(n)C(n)exp(j((wIF+wd)n+φ))+

v(n)，n=0,1,…，N-1.

(1)

式中：A為信號幅度；D(n)為導航信息；C(n)為偽隨機的測距碼，即C/A碼；wIF為中頻頻率；φ為載波相位；wd表示衛(wèi)星與用戶終端相對運動產(chǎn)生的多普勒頻移；v(n)為高斯白噪聲；N為信號長度。

C/A碼是碼率為1.023 Mbit/s的Gold碼，碼長為1 023。每個GPS衛(wèi)星有唯一的C/A碼，不同GPS衛(wèi)星的C/A碼相互正交，同一GPS衛(wèi)星的C/A碼及其循環(huán)移位序列也相互正交。衛(wèi)星接收信號本身并不具有稀疏性，但由于C/A碼良好的自相關性和互相關性，在碼相位搜索域上，只有本地偽碼相位與接收信號碼相位對齊時相關結果才具有峰值，因此其碼相關結果具有稀疏性,可選擇 C/A碼的循環(huán)移位矩陣作為信號的稀疏變換域[6]。

假設c(0)=[c0,c1,…，cN-1]∈N×1為任意GPS衛(wèi)星的C/A碼，將其循環(huán)移位i個碼片后，得到序列c(i)=[ci,ci+1,…cN-1,c0,…ci-1]∈N×1，i=0,1,…N-1。構造稀疏矩陣如下：

(2)

vr(n)，n=0,1,…，N-1.

(3)

(4)

2 改進的壓縮感知捕獲算法

2.1 基于奇異值分解的測量矩陣構造

信號的測量是進行信號由高維到低維的映射，使用和稀疏矩陣G不相關的M×N(M?N)維的測量矩陣B對信號進行壓縮采樣，定義壓縮比a=M/N。得到M×N維的測量序列：即

Y=Br.

(5)

測量矩陣B必須保證不會把2個不同的稀疏信號映射到同一個采樣集中，這就要求測量矩陣中任意M個列向量組成的矩陣行列式不為零，即為非奇異矩陣[10]。

滿足上述條件的矩陣可作為測量矩陣對矩陣進行壓縮。目前測量矩陣主要有隨機矩陣、確定性矩陣和部分隨機矩陣等[11]。高斯隨機測量矩陣與大多數(shù)正交稀疏矩陣都不相關，是壓縮感知中適應性最廣的測量矩陣[10]，但其自身的不確定性會造成捕獲結果的不確定性，使捕獲成功率下降。本文根據(jù)奇異值分解(singular value decomposition，SVD)[12]對其進行改進。

奇異值分解定理如下：設S是秩為z(0

(6)

(7)

根據(jù)矩陣奇異值理論可知：矩陣奇異值代表矩陣中隱含的特征信息[13]，且特征重要性和奇異值大小成正比。

幾何上來說SVD就是將一個復雜的空間變換分解為3個基本變換，V是旋轉，Σ是縮放，U是投影。以二維矩陣的圖解為例，在圖1中：奇異值σi就是映射后的正交基ui的模的大小，即σi=|Svi|，向量ui為Svi方向上的單位向量。

圖1 奇異值分解圖解Fig.1 The diagram of singular value decomposition

結合矩陣理論，奇異值σi衡量每個列向量對于S的權重，表示矩陣S對應的第i個列向量在子空間的分布。矩陣S的z個奇異值的大小差距越小，則表明其列向量分布越分散，其線性獨立性越好，符合壓縮感知對于測量矩陣的要求。

1)生成高斯隨機測量矩陣BM×N

i=1,2,…，M;j=1,2,…，N.

(8)

2)對B進行奇異值分解

(9)

3)對Σ對角線上的值求平均Mean=(σ1+σ2+…σM)/M；令

(10)

其中：σ′1=σ′2=…σ′M=Mean。

4)得到改進的測量矩陣

(11)

得到新的測量矩陣之后，就可以利用式(5)對信號進行測量，得到測量信號Y。

Y=Br=BGθ.

(12)

其中，BG定義為感知矩陣A(M×N)

A(M×N)=BG.

(13)

2.2 信號重構

信號的重構是由測量信號Y及感知矩陣A求解稀疏信號θ的過程，這是一個求解欠定方程組的問題，在信號稀疏或可壓縮的前提下，求解欠定方程組的問題可轉化為最小l0范數(shù)問題。最小l0范數(shù)在一定條件下和最小l1范數(shù)具有等價性,可得到相同的解，則該問題可以轉化為最小l1范數(shù)下的最優(yōu)化問題[5]

min‖θ‖1s.t.Aθ=Y.

(14)

這樣的轉化使得問題變成了一個凸優(yōu)化問題,于是可以方便地化簡為線性規(guī)劃問題。常用的重構算法有貪婪算法、凸優(yōu)化、迭代閾值等[16]。

利用測量信號Y及感知矩陣A(M×N)對信號進行重構，基于信號捕獲的特殊性，重構算法只需重構稀疏度很小的稀疏信號，且主要關注峰值位置，可選擇計算量小、穩(wěn)定的正交匹配追蹤(orthogonal matching pursuit, OMP)算法[6]。

2.3 算法框圖

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

3 仿真與分析

3.1 計算復雜度分析

捕獲算法的計算復雜度主要是因為需要多次相關運算。本文算法的測量過程可視為由測量矩陣與輸入信號進行相關運算，測量矩陣的M個行向量可視為M個壓縮相關器，完成對輸入信號的相關運算。因此在引入壓縮感知理論對傳統(tǒng)串行捕獲算法進行改進之后，在相關器數(shù)量上降低到1/a，同時數(shù)據(jù)量的降低也減少了寄存器等資源消耗和后續(xù)信號處理壓力。

捕獲中一周期信號的相關次數(shù)取決于碼相位搜索精度、頻率搜索步長及多普勒頻率搜索范圍3個值的大小。本文算法主要對信號碼域進行壓縮，頻率點的搜索與傳統(tǒng)串行算法的搜索次數(shù)一致，所以簡化頻域搜索分析，主要以長度為N的信號為例進行每個頻點的計算復雜度分析。

對于傳統(tǒng)串行的捕獲算法，在每個頻率點需要對碼相位偏移N次，每次偏移進行一次N點相關計算并累加，一共需要N×N次乘法，N×(N-1)次加法，其算法復雜度為O(N2)。

對于本文算法，計算量主要由相關運算及信號重構產(chǎn)生。當測量矩陣為M×N的矩陣時，本文相關運算需要M×N次乘法，M×(N-1)次加法，計算復雜度為O(MN)。OMP重構算法的復雜度目前已有很多文獻進行分析[17-18]，其計算量約為O(KMN)；最后關于測量矩陣改進部分的計算量主要體現(xiàn)在奇異值分解，可提前計算存儲，對捕獲過程計算量不產(chǎn)生影響。所以壓縮感知算法的復雜度為O(KMN)。表1為各算法計算量對比。

表1 算法復雜度對比Table 1 Algorithm complexity comparison

3.2 仿真

對本文提出的基于奇異值分解的壓縮感知捕獲算法(SVD-CS)進行仿真。模擬產(chǎn)生通過加性高斯白噪聲信道的接收信號，中頻頻率40 MHz，捕獲時假設信號降采樣到2.046 MHz，每次取2 046個點進行相關運算，隨機產(chǎn)生碼相位偏移及頻率偏移。捕獲中碼相位搜索步長設為半碼片。頻率搜索步長設為500 Hz，門限值Vt設為2。

圖3是信噪比為-15 dB，測量長度為512，重

圖3 本文算法捕獲結果Fig.3 The algorithm capture result in this paper

構稀疏度設為10時本文算法的捕獲結果。捕獲結果出現(xiàn)明顯的峰值，表明捕獲到了信號。同時，峰值位置對應的多普勒頻率與碼相位結果與模擬接收信號的結果一致。結果表明，本文算法能成功捕獲信號。

圖4是同信噪比下，捕獲性能的分析與對比，以傳統(tǒng)高斯矩陣捕獲算法(GS-CS)[19]作為對照組，信噪比為-15 dB。(a)是測量長度M與捕獲成功率曲線圖，(b)是稀疏度K與捕獲成功率曲線圖，由仿真結果可知：在同信噪比下，SVD-CS算法在不同測量長度，不同稀疏度下捕獲結果均明顯優(yōu)于GS-CS算法，且測量長度越大捕獲結果越好，稀疏度越小捕獲結果越好。

圖4 捕獲性能對比Fig.4 Capture performance comparison

圖5是不同信噪比下，以傳統(tǒng)串行算法為對照組，GS-CS算法與本文SVD-CS算法的捕獲性能對比，本組仿真中稀疏度設為1。通過4組不同測量長度對比可知：在一定信噪比范圍內(nèi)，不同測量長度本文算法的捕獲成功概率均有明顯提高，且壓縮比越大，提高越明顯，表明本文算法改進的有效性。

圖5 不同算法捕獲結果對比Fig.5 Comparison of acquisition results of different algorithms

表2是不同信噪比下本文算法的最小測量長度Mmin仿真。Mmin定義為捕獲成功率能達到90%的最小測量長度。仿真表明該算法在一定信噪比下可以以較小的測量長度達到捕獲性能要求，且信號信噪比越高，算法減少運算量的優(yōu)勢越明顯。

表2 最小測量長度Table 2 Minimum measurement length

4 總結

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