用于AIS實(shí)時(shí)信號(hào)稀疏表示的追蹤算法研究

懷率恒， 張淑芳＊

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

0 引 言

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

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

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

1 AIS信號(hào)稀疏表示原理

1.1 AIS信號(hào)模型

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

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

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

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

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

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

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

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

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

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

1.2 稀疏表示理論

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

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

1.3 基于K-SVD的冗余字典

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

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

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

2 追蹤算法

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

2.1 BP算法

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

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

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

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

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

2.2 OMP算法

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

圖4 原始AIS信號(hào)與BP稀疏信號(hào)對(duì)比Fig.4 Comparison of original AIS signal and BP sparse signal

圖5 原始AIS信號(hào)與OMP稀疏信號(hào)對(duì)比Fig.5 Comparison of original AIS signal and OMP sparse signal

圖6 AIS二進(jìn)制消息與解調(diào)BP稀疏信號(hào)獲得的二進(jìn)制消息對(duì)比Fig.6 Comparison of AIS binary message and binary message from demodulated BP sparse signal

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

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

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

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

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

4 結(jié) 論

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

（2）BP算法的信號(hào)處理時(shí)間比OMP算法的信號(hào)處理時(shí)間長(zhǎng).

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

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