基于交错方向乘子法的并行GPS信号捕获算法

杨 峰，周 飞，潘丽丽，林静然

(1.电子信息控制重点实验室 成都 610036；2.电子科技大学信息与通信工程学院 成都 611731)

以GPS 为代表的卫星导航系统可提供高精度全天候的导航定位和授时信息，被广泛应用于国防建设和国民经济的众多领域[1]。近年来，随着GPS 在移动和便携智能终端中普及，人们对其接收模块的功耗和成本提出了更高要求。在GPS 信号处理过程中，捕获部分处理数据量大、消耗资源多，是影响接收模块功耗和成本的重要因素[2-3]。因此，减少捕获部分的数据量和运算量是进一步降低GPS 接收模块功耗和成本的有效途径，但这具有相当的难度。由于采用了基于C/A 码的直接序列扩频技术来保证远距离传输的抗干扰能力，GPS 信号带宽相对较宽，导致接收端采样率较高(十几兆赫兹至几十兆赫兹)。对看重低功耗和低成本的便携式导航应用而言，高采样率为数据存储和处理带来了巨大负担。另一方面，大多数传统GPS信号捕获算法都基于循环相关运算，通过遍历所有可能的多普勒频率和码相位来完成信号粗同步，这也不可避免地导致了捕获过程的大运算量。

为降低捕获过程的数据量和运算量，人们进行了一系列研究。在基于时域相关的捕获算法方面，通用策略是在数据压缩的基础上尽量合并相同的运算。例如，考虑到半码片的捕获精度已经能够满足跟踪处理的入锁条件，很多算法都在相关运算之前按半码片精度对数据进行“打包”，以降低捕获过程的数据量。在此基础上，文献[4]通过数据重排处理，使得合并某些乘法运算成为可能，提高了相关运算的效率。文献[5]提出了先叠加再相关的方法，减少了相关运算的次数。文献[6]提出了基于两级捕获策略的XFAST 算法，第一级对长扩频码分段折叠进行粗捕，然后第二级确认具体的码相位。文献[7]提出了基于局部积分的并行捕获算法，节省了运算资源。在频域捕获算法方面，基本考虑是将循环相关等效为卷积运算，然后利用FFT 快速算法降低运算量[8-9]。针对某些长扩频码系统，研究人员进一步利用匹配滤波器降低捕获过程的运算量[10]。在数据压缩方面，研究人员利用基于平均相关处理的数据压缩技术[11-13]和由此改进而来的基于向上取整的压缩采样与冗余抗噪技术[14]，提出了高效的频域捕获算法。文献[15]利用Walsh序列和Gold 序列的映射关系，提出了基于Walsh变换的快速捕获算法。总体而言，上述算法都不同程度地降低了数据量和运算量，提高了捕获效率。但是，这些算法在进行数据压缩时，都无法突破半码片捕获精度的限制，即对于码长1 023 的C/A码，要实现半码片捕获精度至少需要2 046 个数据包。受此限制的影响，上述算法在运算量方面的改进也存在局限。

压缩感知理论为进一步降低捕获所需的数据量提供了新思路。区别于传统数据压缩方法，在压缩感知理论中数据量不取决于信号带宽或长度，而取决于信息在信号中的结构[16-17]。这使得突破半码片捕获精度对数据量的限制成为可能。事实上，压缩感知已经在图像处理、智能天线、认知无线电、超宽带系统等领域受到关注，但其在卫星导航中的研究还较少。在文献[18]中，压缩感知被用来解决GPS/SINS 组合导航中的融合滤波问题。该方法为压缩感知在导航系统中的应用提供了思路，但主要针对后续组合导航中Kalman 融合滤波的误差均方矩阵计算而言，没有涉及导航信号本身的处理。文献[19]首次将压缩感知理论用于导航信号捕获，并提出了基于正交匹配追踪法的捕获算法，文献[20]完成了该算法的具体实现工作。正交匹配追踪法本质上是一种贪婪算法，运算量较大且难以并行实现。文献[21-22]利用Walsh-Hadamard 矩阵构造压缩测量矩阵，提出了双阶段GPS 信号压缩感知捕获算法。该算法具有和传统相关捕获算法相同的性能，但要求压缩测量矩阵具有特殊的结构。另外，由于需要进行双阶段的压缩感知，该算法捕获过程略显复杂。文献[23]则提出了基于稀疏傅里叶变换(sparse Fourier transform, SFT)的捕获算法，它针对相关峰的稀疏特性，将SFT 技术引入频域并行捕获中，简化基于FFT 的传统频域码相位搜索算法。该算法运算量很低，效率非常高，但捕获性能损失较大。

基于上述考虑，本文不再采用循环相关的捕获方法，而是通过分析GPS 信号的稀疏性，利用正交的C/A 码构成基矩阵，以C/A 码相位为稀疏系数，对GPS 信号进行近似稀疏表示，并在此基础上建立GPS 信号捕获的压缩感知模型。其次，将GPS压缩感知捕获问题纳入ADMM 的框架[24]，提出一种高效的并行捕获算法。和现有GPS 信号压缩感知捕获算法相比，该算法将压缩感知问题分解成多个相对独立的子问题并行迭代求解，并且迭代的每一步都有简单闭合解，因而具有很低的运算量，能够高效地完成信号捕获的任务。

1 GPS 信号稀疏表示

GPS 信号的C/A 码是码率为1.023 Mbps 的Gold码，码长N=1 023。不同卫星的C/A 码相互正交，同一卫星的C/A 码及其循环移位序列也相互正交。因此，C/A 码及其循环移位序列可以构成一个正交矩阵。将该正交矩阵作为变换基，就可以对GPS 信号进行稀疏表示。

假设g0=[g(0), g(1), ···, g(N−1)]T∈RN×1为任意满足上述条件的Gold 码，将g0循环移位m 个码片后，得 到 序 列gm=[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 码及其循环移位序列构成的正交变换基矩阵；γm=[γ (0), γ(1), ···, γ (N−1)]T∈RN×1是变换系数向量。显然，在γm中，除了γ (m)=1 外，其余系数都为0，即γm是稀疏向量。因此，GPS 中任意相位的Gold 码序列都可以用式(1)进行稀疏表示。

据此可对捕获过程中的GPS 信号进行稀疏表示。捕获的实质是进行多普勒频率和C/A 码相位二维搜索，根据相关峰位置获得频率和相位估计值。在对某颗GPS 卫星的采样信号进行载波(多普勒)剥离和半码片数据打包等处理后，一个C/A 码周期的信号可以表示为：

式中，由于进行半码片打包，一个C/A 码周期的序列长度为2N=2 046；ωd是GPS 信号的多普勒频率；是 多普勒频率估计值；是多普勒估计误差；a、d 和ϕ 分别表示GPS 信号的幅度、导航电文和载波初相，考虑到导航电文码率较低、信号幅度变化缓慢，这里假设它们在捕获处理的时间段内恒定，表示为β=adexp(jϕ)；v(n)是噪声项；c(n; ωd)表示多普勒为ωd时的C/A 码序列的半码片打包数据。

式中的近似处理考虑如下：在非高动态应用中，多普勒频率的范围通常为[−5, 5] KHz，折算到C/A码上约为[−3.24, 3.24] Hz。相对于1.023 M 的C/A码码率而言，这个多普勒频率在1 ms 内的影响可以忽略不计[2]。因此，式中有c(n; ωd)≈c(n; 0)。

定义c0=[c(0; 0), c(1; 0), ···, c(2N−1; 0)]T∈C2N×1。根据上面的分析，c0及其循环移位序列之间仍可以看作是近似正交的。令cm为c0循环移位m 个数据后的序列，即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 码周期的信号都可以构成 一 个 向 量，即 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为多普勒估计准确时的码相位向量；v=[v(0), v(1),···, v(2N−1)]T∈C2N×1为噪声向量。

显然，如果多普勒频率被成功剥离，则p(ωd)是一个稀疏向量，仅有少数较大的非零值，其峰值出现的地方为C/A 码相位估计值。与之相对，如果多普勒估计值存在误差，即，则中仍残留有多普勒分量，的稀疏性就会受到影响。

2 压缩感知捕获模型

基于式(1)中GPS 信号的稀疏表示，可利用压缩感知理论[16-17]完成对稀疏向量p(ωd)的估计，从而取代传统捕获算法中的循环相关运算。

使用和变换基矩阵C 不相关的观测矩阵Ω∈CM×2N，M<<2N，对r(ωd)进行压缩采样，得到观测序列：

式中， Θ= ΩC∈CM×2N；u=Ωv。实际应用中，观测矩阵Ω 的选择很多，常用的有随机高斯矩阵、贝努利矩阵、随机傅立叶矩阵等。

由于多普勒估计准确时，p(ωd)为稀疏向量，可以通过求解如下优化问题：

获得p(ωd)的估计值。

基于上述模型，本文提出了基于压缩感知的GPS 信号捕获算法，其核心步骤为：

1)初始化捕获参数，获得随机观测矩阵Ω、基矩阵C 和混合矩阵Θ=ΩC；

2) Repeat；

该算法与传统捕获算法最大的差别是不再需要循环相关运算，而是通过求解(P1)获得当前多普勒频率估计值对应的相位估计结果，如步骤6)所示。与此同时，捕获过程仅需要存储维度为M 的向量， 而非维度为2N 的向量，这里有M<<2N。当获得所有多普勒估计值对应的相位估计结果后，通过峰值检测和计算峰均比来判断是否成功捕获到某颗卫星的信号，并给出相应的多普勒频率和C/A 码相位估计值。

由于l0范数项是非凸的，(P1)的求解十分复杂，常见处理方法是用l1范数来近似l0范数，即：

由此得到的(P2)为凸优化问题，常见求解算法有基追踪法、(正交)匹配追踪法(orthogonal matching pursuit, OMP)、子空间追踪法[16-17]等。除此之外，还可以通过软件包(如CVX[24]等)直接求解。但是，上述一系列追踪算法本质上是贪婪搜索算法，计算复杂度偏高[17]，同时难以并行执行(基于软件包的方法同样难以并行执行)。考虑到整个优化问题维数较高，分布式的并行求解算法显然更具吸引力。为此，本文将(P2)纳入ADMM 的框架，提出一种高效的并行GPS 信号捕获算法。

3 基于交错方向乘子法的捕获算法

在下面的讨论中，考虑(P2)更一般的形式：

由于存在噪声v[n]，(P2a)可能没有可行解。为了完成捕获，对(P2a)做如下变形，得到：

式中，λ>0 用于调节(P2a)求解过程中目标函数和限制条件的权重。

使用增广拉格朗日(augmented Lagrangian)方法[25]，(P2c)的最优解可以通过求解如下问题获得：

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

同样，利用一阶最优条件，有：

将式代入式有：

更新拉格朗日乘子η 同样可以并行执行，即：

因此，上述步骤6)可以利用基于ADMM 的并行迭代算法来完成，最终获得C/A 码相位估计值，算法的主要步骤如下所示。

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

2) 重复

for m=0, 1,2,…, 2N−1, 并行执行

end

for m=0, 1, 2, ···, 2N−1, 并行执行

end

5) 更新 η(t+1):

form=1, 2, ···, 2N−1, 并行执行

end

6) Until 迭代过程收敛；

ADMM 算法可以确保求得(P2b)的全局最优解。由文献[25]可知，如果(P2b)具有可行解，且ADMM 各个子问题都可以唯一地求解，则ADMM 迭代过程的每一个聚集点都是原问题的最优解。由于(P2b)是一个无限制条件的凸优化问题，因而必然具有可行解。同时，由于ADMM 迭代过程的每一个子问题均为强凸(strongly convex)的，因此，使用一阶最优条件可以唯一地获得其最优解。因此，本文提出的ADMM算法能够获得原问题的全局最优解。

同时，本文提出的ADMM 算法具有可分解的结构，特别适合分布式并行实现，能够提高算法效率。如图1 所示，整个捕获算法可以由2N 个捕获通道并行执行，同时需要一个数据通道负责数据收集和分发。具体而言，每一轮ADMM 迭代分为4 个阶段。在阶段1，通道m 更新在阶段2，通道m 更新；在阶段3，通道m 更新；在阶段4，通道m 将和传送给数据通道，数据通道收集整理这些数据，获得和 η(t+1)，并将它们广播给2N 个捕获通道。然后转入阶段1，开始下一轮ADMM 迭代。

注意到在算法并行迭代的每一步都有简单闭合解，因而运算量很低。根据上述分析，ADMM算法每轮迭代的运算量为O((2N)2)，并行执行过程中单个通道的运算量为O(2N)。OMP 算法每轮迭代的平均运算量为O(N3)，主要用于求解最小二乘问题，同时，OMP 算法难以并行执行。因此，本文提出的ADMM 算法比OMP 算法更高效。

4 计算机仿真

简便起见，使用仅包含1 颗GPS 卫星信号的数据进行仿真测试。该卫星为2 号星，半码片的C/A 码相位为201，多普勒频率为1 KHz，信号强度为−125 dBm。

图2 为ADMM 算法的典型收敛曲线，此时压缩比为M/(2N)=0.7，即一次捕获利用了2 046×0.7≈1 432 个数据包，等效的采样频率为1.432 MHz。图中的结果表明，在各种惩罚因子取值下，ADMM算法的迭代过程都能快速收敛。一般经过50 轮迭代后，ADMM 捕获算法收敛。

图3所示为ADMM 算法的典型捕获结果。在多普勒频率和C/A 相位的二维平面上，出现了明显的相关峰，表明捕获到了2 号星的信号。同时，相关峰出现的位置对应的多普勒频率为1 000 Hz，C/A 码相位为201，与预设值相同，实现正确捕获。

图4为各种捕获算法在不同信号强度下的捕获概率对比。参与比较的算法有：1) 传统时域循环相关算法；2) 基于OMP 的捕获算法，它利用OMP算法求解压缩感知捕获问题(P1)，详见文献[19-20]；3) 基于SFT 的频谱捕获算法，详见文献[23]；4)本文的基于ADMM 的捕获算法。图中结果表明，基于压缩感知的捕获算法能够在低于Nyquist 采样频率时完成GPS 信号的捕获，代价是捕获概率略有下降。与之相对，此时传统的时域循环相关算法几乎不能进行捕获。一般而言，采样频率越高(使用的数据量越多，压缩率越高)，捕获概率越高。在3 种压缩感知捕获算法中，基于ADMM的捕获算法和基于OMP 的捕获算法性能接近，优于基于SFT 的捕获算法。与基于OMP 的捕获算法相比，本文提出的基于ADMM 的捕获算法运算量更低，且算法具有可分解结构，十分利于并行实现，使得算法的效率进一步提升，因而实用性更强。

5 结 束 语

本文提出了一种基于ADMM 的并行GPS 信号捕获算法。基于GPS 信号在相关域的稀疏特性，该算法利用C/A 序列构造正交基，对GPS 信号进行稀疏表示，据此完成了基于压缩感知的GPS 信号捕获问题建模。为了高效地求解该问题，本文将该其纳入ADMM 算法框架，提出一种高效的并行捕获算法。在该算法中，原压缩感知问题被分解成多个相对独立的子问题并行迭代求解，并且迭代的每一步都有简单闭合解，因而具有很低的运算量。仿真结果验证了该算法的正确性和有效性。