用于AIS实时信号稀疏表示的追踪算法研究

怀率恒， 张淑芳＊

（大连海事大学 信息科学技术学院，辽宁 大连 116026）

0 引 言

船舶自动识别系统（automatic identification system，AIS）由岸基设施和船载设备共同组成，是一种数字助航系统，可以实现识别船只、简化信息交流以及提供其他辅助信息以避免碰撞的发生等功能［1］.为了实现国际海事组织关于将来船舶应装备天基和陆基双备份定位系统以及为了沿海船舶航行安全将要使用陆基定位系统的迫切要求，Hu等利用已有AIS岸站进行定位，使其成为沿海船舶陆基无线定位系统，从而使船载AIS设备能够发挥通信和定位两种功能，称其为AIS自主定位系统［2］.然而现有的AIS本质上是一个通信系统，在最初的系统设计和建设中并没有考虑实现定位功能的要求，因此利用AIS岸站进行定位需要解决许多技术问题，载波的相位测量技术就是其中之一［3－6］.目前应用的定位系统的载波都是双相调制的同频载波，能够利用载波相位测量技术得到高精度的定位.但是AIS的载波根据通信的需求是双频点的高斯滤波最小移频键控（GMSK）调制方式，比同频双相调制要复杂，其非同频和非周期特性使得传统定位系统的载波跟踪测量方法不能应用于AIS信号.因此，需要一种新的针对AIS信号的载波测量技术，称之为AIS信号全息相关检测技术.由于AIS是一个实时系统，要测量其载波，首要的问题是要获得AIS信号在一定时间间隔内的全息数据.为了解决这个问题，本文将信号稀疏表示理论首次引入到实时信号处理领域.

Mallat和Zhang在1993年提出了信号在冗余字典上进行稀疏表示的思想［7］.所谓冗余字典是一个超完备的冗余函数库，信号在冗余字典上进行稀疏分解的结果是该信号的展开中只有少数的基函数具有比较大的非零系数，其他大部分基函数的系数等于零.这里的基函数就是字典中的元素，也被称为原子，因此该信号的主要特征就可以由少量原子来表示.

当前稀疏表示更多的是应用在图像处理领域，其处理时间相对于信号的实时处理而言，可以认为是后处理.本文的研究内容是将图像处理领域的方法引入到信号实时处理领域，主要的难点在于算法在不降低性能和精度的基础上，实现快速处理，满足信号实时处理要求.本文使用基追踪（basis pursuit，BP）和正交匹配追踪（orthogonal matching pursuit，OMP）算法，对基于 K 项奇异值分解（K-SVD）算法构造的冗余字典，获得AIS信号的稀疏表示，并且对比解调之后获得的AIS二进制序列，从信号处理时间、稀疏表示精度、解调误码率和受噪声影响等方面对比两种算法，为AIS信号的全息相关检测技术提供参考.

1 AIS信号稀疏表示原理

1.1 AIS信号模型

AIS自主定位系统由一个主AIS基站、多个从AIS基站和船载AIS设备组成，系统配置如图1所示.所有的AIS基站都需要时钟同步，主基站和从基站轮流发送信号，船载AIS设备接收来自基站的信号.

图1 AIS自主定位系统配置Fig.1 AIS autonomous positioning system configuration

由于AIS信号的调制方式是GMSK，其信号模型可以等价于GMSK信号模型，表示为

其中相位θ（t）如下式所示：

其中g（t）为高斯滤波器的矩形脉冲响应.

GMSK基带波形的信号特征完全由高斯滤波器确定，该高斯滤波器是一个单位脉冲响应服从高斯分布并且均值为0的低通滤波器，其单位脉冲响应为

其中δ2是高斯分布的方差.在信号处理领域，时间带宽积BT通常用来表征高斯滤波器，其中B为高斯滤波器3dB带宽，T是比特周期.BT和δ满足以下关系：

将式（4）代入式（3），可以得到单位脉冲响应的另一个表达式：

因此，从式（5）可以看出，GMSK通信系统中基带波形的信号特征仅与参数BT有关.国际电信联盟给出的建议书［8］规定，在AIS中，用于传输数据的GMSK调制器BT最大应为0.4，用于数据接收的GMSK解调器的BT最大应为0.5.为了统一计算，本文中的BT都设为0.3.建议书［8］还规定，AIS数据传输用24bits的训练序列开始，训练序列中包括一段同步比特，由交替的0和1组成，使用非归零反向编码，可以用1或0开始，如图2所示，图中纵坐标是归一化幅度.

图2 AIS信号训练序列Fig.2 Training sequence of AIS signal

1.2 稀疏表示理论

根据文献［9］所述，信号的稀疏表示源于非线性逼近理论，可以总结为给定一个字典D＝｛di，i＝1，2，…，M｝，它的原子是张成整个希尔伯特空间的单位矢量，即RN＝span（D），MN.对于任意的信号x∈RN，在D中自适应地选取K（KN）个原子对信号x作K项逼近：

其中Ik是di的下标集合，α＝（α（1） …α（M））T是分解系数向量，逼近绝对误差定义为εm＝ x－xK2.当D 是正交基时，保留 α（i） 最大的K个原子，就得到了信号x的最佳K 项逼近.当D是冗余字典时，式（6）有多个解，信号的稀疏表示就是从中选出K取值最小的即分解系数最稀疏的一组原子，这等同于解决0-范数问题，对于一个随机的冗余字典来说，这是一个NP（non-deterministic polynomial）问题［9］.

1.3 基于K-SVD的冗余字典

矩阵的奇异值通常对应于矩阵中隐藏的信息，重要性与奇异值的大小正相关，K-SVD算法正是基于这个概念.在AIS全息相关检测中，需要获得一段时间间隔内的AIS信号，并且不能丢失信号的主要特征.K-SVD算法对于给定的一组训练信号，能够自适应地按照稀疏约束条件，根据训练信号提取其特征，训练出稀疏表示的冗余字典.其算法模型可以描述为

其中D为待训练的字典，Y为训练信号，X是稀疏系数，T0是稀疏度.

K-SVD能在不影响稀疏性限制的情况下保证均方误差减小或者不变，迭代之后的均方误差是单调递减的，这也保证了K-SVD收敛于一个局部最小值，但是这并不代表K-SVD算法的收敛性是一定成立的，而是依赖于追踪算法的收敛性.然而在T0足够小的时候，BP和OMP算法都有非常好的表现，其收敛性是能够保证的［10］.

2 追踪算法

如1.2节所述，求解式（6）是一个NP问题.表面上看似乎是无望的，但是由于信号是稀疏的这个前提，这个问题是可以解决的.研究者提出了许多获取信号稀疏逼近的追踪算法，通常分为贪婪追踪算法和凸松弛法［11］.贪婪追踪算法的基本思想是每次迭代时求取一个局部最优解，逐步逼近原始信号，主要代表有OMP算法.凸松弛法则是将非凸问题转化为凸问题，并对其求解找到原信号的逼近，代表性的是BP算法.

2.1 BP算法

BP算法的基本思想是找到系数具有最小0-范数的信号表示，其求解模型可以描述为

由于对于式（8）的求解是一个NP问题，根据1-范数在一定条件下和0-范数具有等价性的条件，求解一个更加简单的1-范数问题会得到同样的解［12］.

这使得问题变成了一个凸优化问题.由于式（9）中的X没有非负约束，要将X变为两个非负变量u和v的差，即X＝u－v，这样X既可以是正也可以是负，因此式（9）中的约束条件可以写为D（u－义，式（9）中目标函数可以写为

因此，这个1-范数问题可以化简为线性规划问题：

1-范数的性质决定了其无法分辨稀疏系数的位置，所以尽管整体上重构信号在欧氏距离上是逼近原信号的，但是存在位置错位的现象，从而出现一些不期望的人工效应.并且在1-范数的框架下，BP算法计算复杂度的量级在O（N3），这对于AIS实时信号处理，其运算时间需要进行实验验证.

2.2 OMP算法

匹配追踪算法的本质是以贪婪迭代算法的思想来选择测量字典矩阵中的列向量.首先从字典矩阵D中选择一个与原始信号Y最匹配的原子，构建稀疏逼近，求出信号残差；然后继续选择一个与信号残差最匹配的原子，反复迭代；最后原始信号Y则可以由这些原子的线性组合和最后的残差值来表示.如果最后的残差值满足预先设置的阈值，在可忽略的范围内，原始信号Y就可使用这些原子的线性组合来表示.

OMP算法继承了匹配追踪算法原子选择的思想，但是为了克服匹配追踪算法的非最优性问题，其每次迭代过程中均对选择的原子进行施密特正交化，从而保证了每次迭代之后的残差与选中的原子都是正交的.这样就避免了重复选择，保证了迭代的最优性，同时减少了迭代次数，在精度要求相同的情况下，加快了收敛速度.OMP算法计算复杂度的量级是O（NK2）.

OMP算法的求解模型跟式（8）描述的BP算法一样.算法中当前残差r的定义如下：

其中X代表由当前字典中的原子得到的原信号的近似解.当残差或稀疏度达到要求的时候，迭代停止.

3 实验结果及分析

通过仿真AIS信号来对比两种追踪算法的性能.如图3所示，在AIS默认传输分组中，数据部分的长度为168bits，以此为例产生64组长度为168bits的AIS信号作为训练数据.AIS是一个实时系统，信号处理的时间必须满足要求，AIS中使用帧的概念，一帧的时长等于1min，分成2 250个时隙，一个时隙的时长约为26.7ms.因此要获取AIS信号的数据，对其进行稀疏表示必须在一个时隙之内完成［8］.本文中实验平台的硬件条件是Intel Core i7-6700CPU＠3.40GHz、16GB内存.

图3 AIS信号结构Fig.3 Structure of AIS signal

图4 和5分别给出了原始AIS信号与使用BP和OMP算法获得的稀疏信号的对比图，截取了前2ms的波形.考虑到噪声的影响，信噪比设置为10dB.图6和7则是AIS二进制消息与从两种稀疏信号解调获得的二进制消息的对比图.4幅图中的纵坐标是归一化幅度，红色实线代表的是原始信号，蓝色虚线代表的是得到的信号.

图4 原始AIS信号与BP稀疏信号对比Fig.4 Comparison of original AIS signal and BP sparse signal

图5 原始AIS信号与OMP稀疏信号对比Fig.5 Comparison of original AIS signal and OMP sparse signal

图6 AIS二进制消息与解调BP稀疏信号获得的二进制消息对比Fig.6 Comparison of AIS binary message and binary message from demodulated BP sparse signal

图7 AIS二进制消息与解调OMP稀疏信号获得的二进制消息对比Fig.7 Comparison of AIS binary message and binary message from demodulated OMP sparse signal

可以看出，图4中蓝色虚线代表的信号与红色实线代表的信号的重合程度是高于图5中的.为了使观察结果趋于稳定，重复实验500次，比较两种算法的运算时间和稀疏表示精度，得到BP算法的用时为24.4ms，精度用均方根误差来表示是0.016；OMP算法的用时为13.9ms，精度是0.25.从实验结果可以看出，由于BP算法的运算复杂度比OMP算法的运算复杂度高，相应的其运算时间也比较长，两种算法的运算时间都满足AIS实时信号处理的时间要求.BP算法的稀疏表示精度高于OMP算法的稀疏表示精度.从图6和7可看出，图6中解调之后的二进制码与原二进制码只有一个不同，而图7中有11个不同.同样的，重复实验500次，比较两种算法的解调之后的误码率，得到BP算法的误码率是0.6%，OMP算法的误码率是7.7%.AIS应用的是循环冗余校验，可以接受的误码率是10%左右［13］.

表1给出了在信噪比不同的情况下，两种算法的误码率.

表1 不同信噪比下误码率Tab.1 Bit error rate under different SNRs

从表1可以看出，在不同信噪比的条件下，BP算法的误码率都低于OMP算法的误码率，但是BP算法的误码率随着信噪比的降低而变化的程度是要高于OMP算法的，这说明BP算法对噪声的变化更敏感.

4 结 论

（1）对基于K-SVD算法构造的冗余字典，相比使用OMP算法获得的AIS信号的稀疏表示，使用BP算法获得的AIS信号的稀疏表示具有更好的精度.

（2）BP算法的信号处理时间比OMP算法的信号处理时间长.

（3）在相同的噪音条件下，BP算法的误码率低于OMP算法的误码率，但是其对噪声的变化更敏感.

（4）AIS是一个实时系统，算法计算的简单快速显得尤为重要，运算时间的多少也代表着算法的可操作性和实现的复杂程度.因此重构算法在保证算法性能的基础上，计算复杂度应尽可能的低.从这一点上来说，OMP算法比BP算法更适合于AIS自主定位系统.