用于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自主定位系統.