基于交錯(cuò)方向乘子法的并行GPS信號(hào)捕獲算法

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

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

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

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

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

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

1 GPS 信號(hào)稀疏表示

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

假設(shè)g0=[g(0), g(1), ···, g(N?1)]T∈RN×1為任意滿足上述條件的Gold 碼，將g0循環(huán)移位m 個(gè)碼片后，得 到 序 列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ìn)行稀疏表示。

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

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

式中的近似處理考慮如下：在非高動(dòng)態(tài)應(yīng)用中，多普勒頻率的范圍通常為[?5, 5] KHz，折算到C/A碼上約為[?3.24, 3.24] Hz。相對(duì)于1.023 M 的C/A碼碼率而言，這個(gè)多普勒頻率在1 ms 內(nèi)的影響可以忽略不計(jì)[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 個(gè)數(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。因此，在正確剝離載波和多普勒后，從任意碼相位開(kāi)始的一個(gè)C/A 碼周期的信號(hào)都可以構(gòu)成 一 個(gè) 向 量，即 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為多普勒估計(jì)準(zhǔn)確時(shí)的碼相位向量；v=[v(0), v(1),···, v(2N?1)]T∈C2N×1為噪聲向量。

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

2 壓縮感知捕獲模型

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

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

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

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

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

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

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

2) Repeat；

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

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

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

3 基于交錯(cuò)方向乘子法的捕獲算法

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

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

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

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

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

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

將式代入式有：

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

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

1) 初始化ρ, λ, η(0)和, 計(jì)算Φ = (Θ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 迭代過(guò)程收斂；

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

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

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

4 計(jì)算機(jī)仿真

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

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

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

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

5 結(jié) 束 語(yǔ)

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