楊 峰，周 飛，潘麗麗，林靜然

(1.電子信息控制重點實驗室 成都 610036；2.電子科技大學(xué)信息與通信工程學(xué)院 成都 611731)

以GPS 為代表的衛(wèi)星導(dǎo)航系統(tǒng)可提供高精度全天候的導(dǎo)航定位和授時信息，被廣泛應(yīng)用于國防建設(shè)和國民經(jīng)濟的眾多領(lǐng)域[1]。近年來，隨著GPS 在移動和便攜智能終端中普及，人們對其接收模塊的功耗和成本提出了更高要求。在GPS 信號處理過程中，捕獲部分處理數(shù)據(jù)量大、消耗資源多，是影響接收模塊功耗和成本的重要因素[2-3]。因此，減少捕獲部分的數(shù)據(jù)量和運算量是進一步降低GPS 接收模塊功耗和成本的有效途徑，但這具有相當(dāng)?shù)碾y度。由于采用了基于C/A 碼的直接序列擴頻技術(shù)來保證遠距離傳輸?shù)目垢蓴_能力，GPS 信號帶寬相對較寬，導(dǎo)致接收端采樣率較高(十幾兆赫茲至幾十兆赫茲)。對看重低功耗和低成本的便攜式導(dǎo)航應(yīng)用而言，高采樣率為數(shù)據(jù)存儲和處理帶來了巨大負擔(dān)。另一方面，大多數(shù)傳統(tǒng)GPS信號捕獲算法都基于循環(huán)相關(guān)運算，通過遍歷所有可能的多普勒頻率和碼相位來完成信號粗同步，這也不可避免地導(dǎo)致了捕獲過程的大運算量。

為降低捕獲過程的數(shù)據(jù)量和運算量，人們進行了一系列研究。在基于時域相關(guān)的捕獲算法方面，通用策略是在數(shù)據(jù)壓縮的基礎(chǔ)上盡量合并相同的運算。例如，考慮到半碼片的捕獲精度已經(jīng)能夠滿足跟蹤處理的入鎖條件，很多算法都在相關(guān)運算之前按半碼片精度對數(shù)據(jù)進行“打包”，以降低捕獲過程的數(shù)據(jù)量。在此基礎(chǔ)上，文獻[4]通過數(shù)據(jù)重排處理，使得合并某些乘法運算成為可能，提高了相關(guān)運算的效率。文獻[5]提出了先疊加再相關(guān)的方法，減少了相關(guān)運算的次數(shù)。文獻[6]提出了基于兩級捕獲策略的XFAST 算法，第一級對長擴頻碼分段折疊進行粗捕，然后第二級確認具體的碼相位。文獻[7]提出了基于局部積分的并行捕獲算法，節(jié)省了運算資源。在頻域捕獲算法方面，基本考慮是將循環(huán)相關(guān)等效為卷積運算，然后利用FFT 快速算法降低運算量[8-9]。針對某些長擴頻碼系統(tǒng)，研究人員進一步利用匹配濾波器降低捕獲過程的運算量[10]。在數(shù)據(jù)壓縮方面，研究人員利用基于平均相關(guān)處理的數(shù)據(jù)壓縮技術(shù)[11-13]和由此改進而來的基于向上取整的壓縮采樣與冗余抗噪技術(shù)[14]，提出了高效的頻域捕獲算法。文獻[15]利用Walsh序列和Gold 序列的映射關(guān)系，提出了基于Walsh變換的快速捕獲算法。總體而言，上述算法都不同程度地降低了數(shù)據(jù)量和運算量，提高了捕獲效率。但是，這些算法在進行數(shù)據(jù)壓縮時，都無法突破半碼片捕獲精度的限制，即對于碼長1 023 的C/A碼，要實現(xiàn)半碼片捕獲精度至少需要2 046 個數(shù)據(jù)包。受此限制的影響，上述算法在運算量方面的改進也存在局限。

壓縮感知理論為進一步降低捕獲所需的數(shù)據(jù)量提供了新思路。區(qū)別于傳統(tǒng)數(shù)據(jù)壓縮方法，在壓縮感知理論中數(shù)據(jù)量不取決于信號帶寬或長度，而取決于信息在信號中的結(jié)構(gòu)[16-17]。這使得突破半碼片捕獲精度對數(shù)據(jù)量的限制成為可能。事實上，壓縮感知已經(jīng)在圖像處理、智能天線、認知無線電、超寬帶系統(tǒng)等領(lǐng)域受到關(guān)注，但其在衛(wèi)星導(dǎo)航中的研究還較少。在文獻[18]中，壓縮感知被用來解決GPS/SINS 組合導(dǎo)航中的融合濾波問題。該方法為壓縮感知在導(dǎo)航系統(tǒng)中的應(yīng)用提供了思路，但主要針對后續(xù)組合導(dǎo)航中Kalman 融合濾波的誤差均方矩陣計算而言，沒有涉及導(dǎo)航信號本身的處理。文獻[19]首次將壓縮感知理論用于導(dǎo)航信號捕獲，并提出了基于正交匹配追蹤法的捕獲算法，文獻[20]完成了該算法的具體實現(xiàn)工作。正交匹配追蹤法本質(zhì)上是一種貪婪算法，運算量較大且難以并行實現(xiàn)。文獻[21-22]利用Walsh-Hadamard 矩陣構(gòu)造壓縮測量矩陣，提出了雙階段GPS 信號壓縮感知捕獲算法。該算法具有和傳統(tǒng)相關(guān)捕獲算法相同的性能，但要求壓縮測量矩陣具有特殊的結(jié)構(gòu)。另外，由于需要進行雙階段的壓縮感知，該算法捕獲過程略顯復(fù)雜。文獻[23]則提出了基于稀疏傅里葉變換(sparse Fourier transform, SFT)的捕獲算法，它針對相關(guān)峰的稀疏特性，將SFT 技術(shù)引入頻域并行捕獲中，簡化基于FFT 的傳統(tǒng)頻域碼相位搜索算法。該算法運算量很低，效率非常高，但捕獲性能損失較大。

基于上述考慮，本文不再采用循環(huán)相關(guān)的捕獲方法，而是通過分析GPS 信號的稀疏性，利用正交的C/A 碼構(gòu)成基矩陣，以C/A 碼相位為稀疏系數(shù)，對GPS 信號進行近似稀疏表示，并在此基礎(chǔ)上建立GPS 信號捕獲的壓縮感知模型。其次，將GPS壓縮感知捕獲問題納入ADMM 的框架[24]，提出一種高效的并行捕獲算法。和現(xiàn)有GPS 信號壓縮感知捕獲算法相比，該算法將壓縮感知問題分解成多個相對獨立的子問題并行迭代求解，并且迭代的每一步都有簡單閉合解，因而具有很低的運算量，能夠高效地完成信號捕獲的任務(wù)。

1 GPS 信號稀疏表示

GPS 信號的C/A 碼是碼率為1.023 Mbps 的Gold碼，碼長N=1 023。不同衛(wèi)星的C/A 碼相互正交，同一衛(wèi)星的C/A 碼及其循環(huán)移位序列也相互正交。因此，C/A 碼及其循環(huán)移位序列可以構(gòu)成一個正交矩陣。將該正交矩陣作為變換基，就可以對GPS 信號進行稀疏表示。

假設(shè)g0=[g(0), g(1), ···, g(N?1)]T∈RN×1為任意滿足上述條件的Gold 碼，將g0循環(huán)移位m 個碼片后，得 到 序 列g(shù)m=[g(m), g(m+1), ···, g(N?1), g(0),g(1), ···, g(m?1)]T∈RN×1，m=0, 1, 2, ···, N?1, 則gm可以表示為：式中，G=[g0, g1, ···, gN?1]∈RN×N是由Gold 碼及其循環(huán)移位序列構(gòu)成的正交變換基矩陣；γm=[γ (0), γ(1), ···, γ (N?1)]T∈RN×1是變換系數(shù)向量。顯然，在γm中，除了γ (m)=1 外，其余系數(shù)都為0，即γm是稀疏向量。因此，GPS 中任意相位的Gold 碼序列都可以用式(1)進行稀疏表示。

據(jù)此可對捕獲過程中的GPS 信號進行稀疏表示。捕獲的實質(zhì)是進行多普勒頻率和C/A 碼相位二維搜索，根據(jù)相關(guān)峰位置獲得頻率和相位估計值。在對某顆GPS 衛(wèi)星的采樣信號進行載波(多普勒)剝離和半碼片數(shù)據(jù)打包等處理后，一個C/A 碼周期的信號可以表示為：

式中，由于進行半碼片打包，一個C/A 碼周期的序列長度為2N=2 046；ωd是GPS 信號的多普勒頻率；是 多普勒頻率估計值；是多普勒估計誤差；a、d 和? 分別表示GPS 信號的幅度、導(dǎo)航電文和載波初相，考慮到導(dǎo)航電文碼率較低、信號幅度變化緩慢，這里假設(shè)它們在捕獲處理的時間段內(nèi)恒定，表示為β=adexp(j?)；v(n)是噪聲項；c(n; ωd)表示多普勒為ωd時的C/A 碼序列的半碼片打包數(shù)據(jù)。

式中的近似處理考慮如下：在非高動態(tài)應(yīng)用中，多普勒頻率的范圍通常為[?5, 5] KHz，折算到C/A碼上約為[?3.24, 3.24] Hz。相對于1.023 M 的C/A碼碼率而言，這個多普勒頻率在1 ms 內(nèi)的影響可以忽略不計[2]。因此，式中有c(n; ωd)≈c(n; 0)。

定義c0=[c(0; 0), c(1; 0), ···, c(2N?1; 0)]T∈C2N×1。根據(jù)上面的分析，c0及其循環(huán)移位序列之間仍可以看作是近似正交的。令cm為c0循環(huán)移位m 個數(shù)據(jù)后的序列，即cm=[c(m; 0), c(m+1; 0), ···, c(2N?1; 0),c(0; 0), c(1; 0), ···, c(m?1; 0)]T∈R2N×1，m=0, 1, 2, ···,

2N?1。因此，在正確剝離載波和多普勒后，從任意碼相位開始的一個C/A 碼周期的信號都可以構(gòu)成 一 個 向 量，即 r(ωd)=[r(0; ωd), r(1; ωd), ···,r(2N?1; ωd)]T∈C2N×1，它可以寫成如下形式：

式中，C=[c0, c1, ···, c2N?1]∈C2N×2N為變換基矩陣；p(ωd)=β[p(0; ωd), p(1; ωd), ···, p(2N?1; ωd)]T∈C2N×1為多普勒估計準(zhǔn)確時的碼相位向量；v=[v(0), v(1),···, v(2N?1)]T∈C2N×1為噪聲向量。

顯然，如果多普勒頻率被成功剝離，則p(ωd)是一個稀疏向量，僅有少數(shù)較大的非零值，其峰值出現(xiàn)的地方為C/A 碼相位估計值。與之相對，如果多普勒估計值存在誤差，即，則中仍殘留有多普勒分量，的稀疏性就會受到影響。

2 壓縮感知捕獲模型

基于式(1)中GPS 信號的稀疏表示，可利用壓縮感知理論[16-17]完成對稀疏向量p(ωd)的估計，從而取代傳統(tǒng)捕獲算法中的循環(huán)相關(guān)運算。

使用和變換基矩陣C 不相關(guān)的觀測矩陣Ω∈CM×2N，M<<2N，對r(ωd)進行壓縮采樣，得到觀測序列：

式中， Θ= ?C∈CM×2N；u=Ωv。實際應(yīng)用中，觀測矩陣Ω 的選擇很多，常用的有隨機高斯矩陣、貝努利矩陣、隨機傅立葉矩陣等。

由于多普勒估計準(zhǔn)確時，p(ωd)為稀疏向量，可以通過求解如下優(yōu)化問題：

獲得p(ωd)的估計值。

基于上述模型，本文提出了基于壓縮感知的GPS 信號捕獲算法，其核心步驟為：

1)初始化捕獲參數(shù)，獲得隨機觀測矩陣Ω、基矩陣C 和混合矩陣Θ=ΩC；

2) Repeat；

該算法與傳統(tǒng)捕獲算法最大的差別是不再需要循環(huán)相關(guān)運算，而是通過求解(P1)獲得當(dāng)前多普勒頻率估計值對應(yīng)的相位估計結(jié)果，如步驟6)所示。與此同時，捕獲過程僅需要存儲維度為M 的向量， 而非維度為2N 的向量，這里有M<<2N。當(dāng)獲得所有多普勒估計值對應(yīng)的相位估計結(jié)果后，通過峰值檢測和計算峰均比來判斷是否成功捕獲到某顆衛(wèi)星的信號，并給出相應(yīng)的多普勒頻率和C/A 碼相位估計值。

由于l0范數(shù)項是非凸的，(P1)的求解十分復(fù)雜，常見處理方法是用l1范數(shù)來近似l0范數(shù)，即：

由此得到的(P2)為凸優(yōu)化問題，常見求解算法有基追蹤法、(正交)匹配追蹤法(orthogonal matching pursuit, OMP)、子空間追蹤法[16-17]等。除此之外，還可以通過軟件包(如CVX[24]等)直接求解。但是，上述一系列追蹤算法本質(zhì)上是貪婪搜索算法，計算復(fù)雜度偏高[17]，同時難以并行執(zhí)行(基于軟件包的方法同樣難以并行執(zhí)行)?？紤]到整個優(yōu)化問題維數(shù)較高，分布式的并行求解算法顯然更具吸引力。為此，本文將(P2)納入ADMM 的框架，提出一種高效的并行GPS 信號捕獲算法。

3 基于交錯方向乘子法的捕獲算法

在下面的討論中，考慮(P2)更一般的形式：

由于存在噪聲v[n]，(P2a)可能沒有可行解。為了完成捕獲，對(P2a)做如下變形，得到：

式中，λ>0 用于調(diào)節(jié)(P2a)求解過程中目標(biāo)函數(shù)和限制條件的權(quán)重。

使用增廣拉格朗日(augmented Lagrangian)方法[25]，(P2c)的最優(yōu)解可以通過求解如下問題獲得：

即φm∈C2N×1表 示Φ 的 第m 行，m=0, 1, ···,2N?1。則中的各元素可以并行計算，即：

同樣，利用一階最優(yōu)條件，有：

將式代入式有：

更新拉格朗日乘子η 同樣可以并行執(zhí)行，即：

因此，上述步驟6)可以利用基于ADMM 的并行迭代算法來完成，最終獲得C/A 碼相位估計值，算法的主要步驟如下所示。

1) 初始化ρ, λ, η(0)和, 計算Φ = (ΘHΘ+ρI)?1;

2) 重復(fù)

for m=0, 1,2,…, 2N?1, 并行執(zhí)行

end

for m=0, 1, 2, ···, 2N?1, 并行執(zhí)行

end

5) 更新 η(t+1):

form=1, 2, ···, 2N?1, 并行執(zhí)行

end

6) Until 迭代過程收斂；

ADMM 算法可以確保求得(P2b)的全局最優(yōu)解。由文獻[25]可知，如果(P2b)具有可行解，且ADMM 各個子問題都可以唯一地求解，則ADMM 迭代過程的每一個聚集點都是原問題的最優(yōu)解。由于(P2b)是一個無限制條件的凸優(yōu)化問題，因而必然具有可行解。同時，由于ADMM 迭代過程的每一個子問題均為強凸(strongly convex)的，因此，使用一階最優(yōu)條件可以唯一地獲得其最優(yōu)解。因此，本文提出的ADMM算法能夠獲得原問題的全局最優(yōu)解。

同時，本文提出的ADMM 算法具有可分解的結(jié)構(gòu)，特別適合分布式并行實現(xiàn)，能夠提高算法效率。如圖1 所示，整個捕獲算法可以由2N 個捕獲通道并行執(zhí)行，同時需要一個數(shù)據(jù)通道負責(zé)數(shù)據(jù)收集和分發(fā)。具體而言，每一輪ADMM 迭代分為4 個階段。在階段1，通道m(xù) 更新在階段2，通道m(xù) 更新；在階段3，通道m(xù) 更新；在階段4，通道m(xù) 將和傳送給數(shù)據(jù)通道，數(shù)據(jù)通道收集整理這些數(shù)據(jù)，獲得和 η(t+1)，并將它們廣播給2N 個捕獲通道。然后轉(zhuǎn)入階段1，開始下一輪ADMM 迭代。

注意到在算法并行迭代的每一步都有簡單閉合解，因而運算量很低。根據(jù)上述分析，ADMM算法每輪迭代的運算量為O((2N)2)，并行執(zhí)行過程中單個通道的運算量為O(2N)。OMP 算法每輪迭代的平均運算量為O(N3)，主要用于求解最小二乘問題，同時，OMP 算法難以并行執(zhí)行。因此，本文提出的ADMM 算法比OMP 算法更高效。

4 計算機仿真

簡便起見，使用僅包含1 顆GPS 衛(wèi)星信號的數(shù)據(jù)進行仿真測試。該衛(wèi)星為2 號星，半碼片的C/A 碼相位為201，多普勒頻率為1 KHz，信號強度為?125 dBm。

圖2 為ADMM 算法的典型收斂曲線，此時壓縮比為M/(2N)=0.7，即一次捕獲利用了2 046×0.7≈1 432 個數(shù)據(jù)包，等效的采樣頻率為1.432 MHz。圖中的結(jié)果表明，在各種懲罰因子取值下，ADMM算法的迭代過程都能快速收斂。一般經(jīng)過50 輪迭代后，ADMM 捕獲算法收斂。

圖3所示為ADMM 算法的典型捕獲結(jié)果。在多普勒頻率和C/A 相位的二維平面上，出現(xiàn)了明顯的相關(guān)峰，表明捕獲到了2 號星的信號。同時，相關(guān)峰出現(xiàn)的位置對應(yīng)的多普勒頻率為1 000 Hz，C/A 碼相位為201，與預(yù)設(shè)值相同，實現(xiàn)正確捕獲。

圖4為各種捕獲算法在不同信號強度下的捕獲概率對比。參與比較的算法有：1) 傳統(tǒng)時域循環(huán)相關(guān)算法；2) 基于OMP 的捕獲算法，它利用OMP算法求解壓縮感知捕獲問題(P1)，詳見文獻[19-20]；3) 基于SFT 的頻譜捕獲算法，詳見文獻[23]；4)本文的基于ADMM 的捕獲算法。圖中結(jié)果表明，基于壓縮感知的捕獲算法能夠在低于Nyquist 采樣頻率時完成GPS 信號的捕獲，代價是捕獲概率略有下降。與之相對，此時傳統(tǒng)的時域循環(huán)相關(guān)算法幾乎不能進行捕獲。一般而言，采樣頻率越高(使用的數(shù)據(jù)量越多，壓縮率越高)，捕獲概率越高。在3 種壓縮感知捕獲算法中，基于ADMM的捕獲算法和基于OMP 的捕獲算法性能接近，優(yōu)于基于SFT 的捕獲算法。與基于OMP 的捕獲算法相比，本文提出的基于ADMM 的捕獲算法運算量更低，且算法具有可分解結(jié)構(gòu)，十分利于并行實現(xiàn)，使得算法的效率進一步提升，因而實用性更強。

5 結(jié) 束 語

本文提出了一種基于ADMM 的并行GPS 信號捕獲算法。基于GPS 信號在相關(guān)域的稀疏特性，該算法利用C/A 序列構(gòu)造正交基，對GPS 信號進行稀疏表示，據(jù)此完成了基于壓縮感知的GPS 信號捕獲問題建模。為了高效地求解該問題，本文將該其納入ADMM 算法框架，提出一種高效的并行捕獲算法。在該算法中，原壓縮感知問題被分解成多個相對獨立的子問題并行迭代求解，并且迭代的每一步都有簡單閉合解，因而具有很低的運算量。仿真結(jié)果驗證了該算法的正確性和有效性。