懷率恒， 張淑芳＊

（大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院，遼寧 大連 116026）

0 引 言

船舶自動識別系統(tǒng)（automatic identification system，AIS）由岸基設(shè)施和船載設(shè)備共同組成，是一種數(shù)字助航系統(tǒng)，可以實現(xiàn)識別船只、簡化信息交流以及提供其他輔助信息以避免碰撞的發(fā)生等功能［1］.為了實現(xiàn)國際海事組織關(guān)于將來船舶應(yīng)裝備天基和陸基雙備份定位系統(tǒng)以及為了沿海船舶航行安全將要使用陸基定位系統(tǒng)的迫切要求，Hu等利用已有AIS岸站進行定位，使其成為沿海船舶陸基無線定位系統(tǒng)，從而使船載AIS設(shè)備能夠發(fā)揮通信和定位兩種功能，稱其為AIS自主定位系統(tǒng)［2］.然而現(xiàn)有的AIS本質(zhì)上是一個通信系統(tǒng)，在最初的系統(tǒng)設(shè)計和建設(shè)中并沒有考慮實現(xiàn)定位功能的要求，因此利用AIS岸站進行定位需要解決許多技術(shù)問題，載波的相位測量技術(shù)就是其中之一［3－6］.目前應(yīng)用的定位系統(tǒng)的載波都是雙相調(diào)制的同頻載波，能夠利用載波相位測量技術(shù)得到高精度的定位.但是AIS的載波根據(jù)通信的需求是雙頻點的高斯濾波最小移頻鍵控（GMSK）調(diào)制方式，比同頻雙相調(diào)制要復(fù)雜，其非同頻和非周期特性使得傳統(tǒng)定位系統(tǒng)的載波跟蹤測量方法不能應(yīng)用于AIS信號.因此，需要一種新的針對AIS信號的載波測量技術(shù)，稱之為AIS信號全息相關(guān)檢測技術(shù).由于AIS是一個實時系統(tǒng)，要測量其載波，首要的問題是要獲得AIS信號在一定時間間隔內(nèi)的全息數(shù)據(jù).為了解決這個問題，本文將信號稀疏表示理論首次引入到實時信號處理領(lǐng)域.

Mallat和Zhang在1993年提出了信號在冗余字典上進行稀疏表示的思想［7］.所謂冗余字典是一個超完備的冗余函數(shù)庫，信號在冗余字典上進行稀疏分解的結(jié)果是該信號的展開中只有少數(shù)的基函數(shù)具有比較大的非零系數(shù)，其他大部分基函數(shù)的系數(shù)等于零.這里的基函數(shù)就是字典中的元素，也被稱為原子，因此該信號的主要特征就可以由少量原子來表示.

當(dāng)前稀疏表示更多的是應(yīng)用在圖像處理領(lǐng)域，其處理時間相對于信號的實時處理而言，可以認為是后處理.本文的研究內(nèi)容是將圖像處理領(lǐng)域的方法引入到信號實時處理領(lǐng)域，主要的難點在于算法在不降低性能和精度的基礎(chǔ)上，實現(xiàn)快速處理，滿足信號實時處理要求.本文使用基追蹤（basis pursuit，BP）和正交匹配追蹤（orthogonal matching pursuit，OMP）算法，對基于 K 項奇異值分解（K-SVD）算法構(gòu)造的冗余字典，獲得AIS信號的稀疏表示，并且對比解調(diào)之后獲得的AIS二進制序列，從信號處理時間、稀疏表示精度、解調(diào)誤碼率和受噪聲影響等方面對比兩種算法，為AIS信號的全息相關(guān)檢測技術(shù)提供參考.

1 AIS信號稀疏表示原理

1.1 AIS信號模型

AIS自主定位系統(tǒng)由一個主AIS基站、多個從AIS基站和船載AIS設(shè)備組成，系統(tǒng)配置如圖1所示.所有的AIS基站都需要時鐘同步，主基站和從基站輪流發(fā)送信號，船載AIS設(shè)備接收來自基站的信號.

圖1 AIS自主定位系統(tǒng)配置Fig.1 AIS autonomous positioning system configuration

由于AIS信號的調(diào)制方式是GMSK，其信號模型可以等價于GMSK信號模型，表示為

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

其中g(shù)（t）為高斯濾波器的矩形脈沖響應(yīng).

GMSK基帶波形的信號特征完全由高斯濾波器確定，該高斯濾波器是一個單位脈沖響應(yīng)服從高斯分布并且均值為0的低通濾波器，其單位脈沖響應(yīng)為

其中δ2是高斯分布的方差.在信號處理領(lǐng)域，時間帶寬積BT通常用來表征高斯濾波器，其中B為高斯濾波器3dB帶寬，T是比特周期.BT和δ滿足以下關(guān)系：

將式（4）代入式（3），可以得到單位脈沖響應(yīng)的另一個表達式：

因此，從式（5）可以看出，GMSK通信系統(tǒng)中基帶波形的信號特征僅與參數(shù)BT有關(guān).國際電信聯(lián)盟給出的建議書［8］規(guī)定，在AIS中，用于傳輸數(shù)據(jù)的GMSK調(diào)制器BT最大應(yīng)為0.4，用于數(shù)據(jù)接收的GMSK解調(diào)器的BT最大應(yīng)為0.5.為了統(tǒng)一計算，本文中的BT都設(shè)為0.3.建議書［8］還規(guī)定，AIS數(shù)據(jù)傳輸用24bits的訓(xùn)練序列開始，訓(xùn)練序列中包括一段同步比特，由交替的0和1組成，使用非歸零反向編碼，可以用1或0開始，如圖2所示，圖中縱坐標(biāo)是歸一化幅度.

圖2 AIS信號訓(xùn)練序列Fig.2 Training sequence of AIS signal

1.2 稀疏表示理論

根據(jù)文獻［9］所述，信號的稀疏表示源于非線性逼近理論，可以總結(jié)為給定一個字典D＝｛di，i＝1，2，…，M｝，它的原子是張成整個希爾伯特空間的單位矢量，即RN＝span（D），MN.對于任意的信號x∈RN，在D中自適應(yīng)地選取K（KN）個原子對信號x作K項逼近：

其中Ik是di的下標(biāo)集合，α＝（α（1） …α（M））T是分解系數(shù)向量，逼近絕對誤差定義為εm＝ x－xK2.當(dāng)D 是正交基時，保留 α（i） 最大的K個原子，就得到了信號x的最佳K 項逼近.當(dāng)D是冗余字典時，式（6）有多個解，信號的稀疏表示就是從中選出K取值最小的即分解系數(shù)最稀疏的一組原子，這等同于解決0-范數(shù)問題，對于一個隨機的冗余字典來說，這是一個NP（non-deterministic polynomial）問題［9］.

1.3 基于K-SVD的冗余字典

矩陣的奇異值通常對應(yīng)于矩陣中隱藏的信息，重要性與奇異值的大小正相關(guān)，K-SVD算法正是基于這個概念.在AIS全息相關(guān)檢測中，需要獲得一段時間間隔內(nèi)的AIS信號，并且不能丟失信號的主要特征.K-SVD算法對于給定的一組訓(xùn)練信號，能夠自適應(yīng)地按照稀疏約束條件，根據(jù)訓(xùn)練信號提取其特征，訓(xùn)練出稀疏表示的冗余字典.其算法模型可以描述為

其中D為待訓(xùn)練的字典，Y為訓(xùn)練信號，X是稀疏系數(shù)，T0是稀疏度.

K-SVD能在不影響稀疏性限制的情況下保證均方誤差減小或者不變，迭代之后的均方誤差是單調(diào)遞減的，這也保證了K-SVD收斂于一個局部最小值，但是這并不代表K-SVD算法的收斂性是一定成立的，而是依賴于追蹤算法的收斂性.然而在T0足夠小的時候，BP和OMP算法都有非常好的表現(xiàn)，其收斂性是能夠保證的［10］.

2 追蹤算法

如1.2節(jié)所述，求解式（6）是一個NP問題.表面上看似乎是無望的，但是由于信號是稀疏的這個前提，這個問題是可以解決的.研究者提出了許多獲取信號稀疏逼近的追蹤算法，通常分為貪婪追蹤算法和凸松弛法［11］.貪婪追蹤算法的基本思想是每次迭代時求取一個局部最優(yōu)解，逐步逼近原始信號，主要代表有OMP算法.凸松弛法則是將非凸問題轉(zhuǎn)化為凸問題，并對其求解找到原信號的逼近，代表性的是BP算法.

2.1 BP算法

BP算法的基本思想是找到系數(shù)具有最小0-范數(shù)的信號表示，其求解模型可以描述為

由于對于式（8）的求解是一個NP問題，根據(jù)1-范數(shù)在一定條件下和0-范數(shù)具有等價性的條件，求解一個更加簡單的1-范數(shù)問題會得到同樣的解［12］.

這使得問題變成了一個凸優(yōu)化問題.由于式（9）中的X沒有非負約束，要將X變?yōu)閮蓚€非負變量u和v的差，即X＝u－v，這樣X既可以是正也可以是負，因此式（9）中的約束條件可以寫為D（u－義，式（9）中目標(biāo)函數(shù)可以寫為

因此，這個1-范數(shù)問題可以化簡為線性規(guī)劃問題：

1-范數(shù)的性質(zhì)決定了其無法分辨稀疏系數(shù)的位置，所以盡管整體上重構(gòu)信號在歐氏距離上是逼近原信號的，但是存在位置錯位的現(xiàn)象，從而出現(xiàn)一些不期望的人工效應(yīng).并且在1-范數(shù)的框架下，BP算法計算復(fù)雜度的量級在O（N3），這對于AIS實時信號處理，其運算時間需要進行實驗驗證.

2.2 OMP算法

匹配追蹤算法的本質(zhì)是以貪婪迭代算法的思想來選擇測量字典矩陣中的列向量.首先從字典矩陣D中選擇一個與原始信號Y最匹配的原子，構(gòu)建稀疏逼近，求出信號殘差；然后繼續(xù)選擇一個與信號殘差最匹配的原子，反復(fù)迭代；最后原始信號Y則可以由這些原子的線性組合和最后的殘差值來表示.如果最后的殘差值滿足預(yù)先設(shè)置的閾值，在可忽略的范圍內(nèi)，原始信號Y就可使用這些原子的線性組合來表示.

OMP算法繼承了匹配追蹤算法原子選擇的思想，但是為了克服匹配追蹤算法的非最優(yōu)性問題，其每次迭代過程中均對選擇的原子進行施密特正交化，從而保證了每次迭代之后的殘差與選中的原子都是正交的.這樣就避免了重復(fù)選擇，保證了迭代的最優(yōu)性，同時減少了迭代次數(shù)，在精度要求相同的情況下，加快了收斂速度.OMP算法計算復(fù)雜度的量級是O（NK2）.

OMP算法的求解模型跟式（8）描述的BP算法一樣.算法中當(dāng)前殘差r的定義如下：

其中X代表由當(dāng)前字典中的原子得到的原信號的近似解.當(dāng)殘差或稀疏度達到要求的時候，迭代停止.

3 實驗結(jié)果及分析

通過仿真AIS信號來對比兩種追蹤算法的性能.如圖3所示，在AIS默認傳輸分組中，數(shù)據(jù)部分的長度為168bits，以此為例產(chǎn)生64組長度為168bits的AIS信號作為訓(xùn)練數(shù)據(jù).AIS是一個實時系統(tǒng)，信號處理的時間必須滿足要求，AIS中使用幀的概念，一幀的時長等于1min，分成2 250個時隙，一個時隙的時長約為26.7ms.因此要獲取AIS信號的數(shù)據(jù)，對其進行稀疏表示必須在一個時隙之內(nèi)完成［8］.本文中實驗平臺的硬件條件是Intel Core i7-6700CPU＠3.40GHz、16GB內(nèi)存.

圖3 AIS信號結(jié)構(gòu)Fig.3 Structure of AIS signal

圖4 和5分別給出了原始AIS信號與使用BP和OMP算法獲得的稀疏信號的對比圖，截取了前2ms的波形.考慮到噪聲的影響，信噪比設(shè)置為10dB.圖6和7則是AIS二進制消息與從兩種稀疏信號解調(diào)獲得的二進制消息的對比圖.4幅圖中的縱坐標(biāo)是歸一化幅度，紅色實線代表的是原始信號，藍色虛線代表的是得到的信號.

圖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二進制消息與解調(diào)BP稀疏信號獲得的二進制消息對比Fig.6 Comparison of AIS binary message and binary message from demodulated BP sparse signal

圖7 AIS二進制消息與解調(diào)OMP稀疏信號獲得的二進制消息對比Fig.7 Comparison of AIS binary message and binary message from demodulated OMP sparse signal

可以看出，圖4中藍色虛線代表的信號與紅色實線代表的信號的重合程度是高于圖5中的.為了使觀察結(jié)果趨于穩(wěn)定，重復(fù)實驗500次，比較兩種算法的運算時間和稀疏表示精度，得到BP算法的用時為24.4ms，精度用均方根誤差來表示是0.016；OMP算法的用時為13.9ms，精度是0.25.從實驗結(jié)果可以看出，由于BP算法的運算復(fù)雜度比OMP算法的運算復(fù)雜度高，相應(yīng)的其運算時間也比較長，兩種算法的運算時間都滿足AIS實時信號處理的時間要求.BP算法的稀疏表示精度高于OMP算法的稀疏表示精度.從圖6和7可看出，圖6中解調(diào)之后的二進制碼與原二進制碼只有一個不同，而圖7中有11個不同.同樣的，重復(fù)實驗500次，比較兩種算法的解調(diào)之后的誤碼率，得到BP算法的誤碼率是0.6%，OMP算法的誤碼率是7.7%.AIS應(yīng)用的是循環(huán)冗余校驗，可以接受的誤碼率是10%左右［13］.

表1給出了在信噪比不同的情況下，兩種算法的誤碼率.

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

從表1可以看出，在不同信噪比的條件下，BP算法的誤碼率都低于OMP算法的誤碼率，但是BP算法的誤碼率隨著信噪比的降低而變化的程度是要高于OMP算法的，這說明BP算法對噪聲的變化更敏感.

4 結(jié) 論

（1）對基于K-SVD算法構(gòu)造的冗余字典，相比使用OMP算法獲得的AIS信號的稀疏表示，使用BP算法獲得的AIS信號的稀疏表示具有更好的精度.

（2）BP算法的信號處理時間比OMP算法的信號處理時間長.

（3）在相同的噪音條件下，BP算法的誤碼率低于OMP算法的誤碼率，但是其對噪聲的變化更敏感.

（4）AIS是一個實時系統(tǒng)，算法計算的簡單快速顯得尤為重要，運算時間的多少也代表著算法的可操作性和實現(xiàn)的復(fù)雜程度.因此重構(gòu)算法在保證算法性能的基礎(chǔ)上，計算復(fù)雜度應(yīng)盡可能的低.從這一點上來說，OMP算法比BP算法更適合于AIS自主定位系統(tǒng).