基于并行蟻群算法的長基線定位方法?

張海如 汪 俊 王海斌

(中國科學(xué)院聲學(xué)研究所 聲場聲信息國家重點實驗室 北京 100190)

0 引言

目前，世界各國正積極實施“數(shù)字海洋”戰(zhàn)略。水下導(dǎo)航定位技術(shù)在“數(shù)字海洋”戰(zhàn)略中扮演著非常重要的角色。如何實現(xiàn)水下高精度導(dǎo)航定位已成為海洋開發(fā)與利用中最迫切的問題之一[1?3]。長基線(Long baseline,LBL)定位系統(tǒng)具有定位精度高、可靠性好、可進行大面積和深水海域的定位等優(yōu)點，獲得了國內(nèi)外該領(lǐng)域多個研究機構(gòu)的研究興趣。文獻[4]針對測量誤差影響全向聲吶浮標(biāo)目標(biāo)定位精度的問題，提出了采用總體最小二乘法對水下目標(biāo)進行定位，仿真結(jié)果表明該方法優(yōu)于求解定位方程組最小二乘解方法；文獻[5]將同步模式下的水下目標(biāo)定位問題簡化為求解矩陣方程的問題，即采用球面交會的方法對目標(biāo)進行定位，在此基礎(chǔ)上，分析了目標(biāo)測量深度誤差、基元測量時間誤差、基元位置測量誤差、聲速誤差等相關(guān)參數(shù)的測量誤差對定位精度的影響；文獻[6]提出了一種改進的水聲網(wǎng)絡(luò)定位算法，該算法在進行定位運算前先對原始數(shù)據(jù)進行降噪處理，以提升其抗噪能力，同時降低了計算結(jié)果的冗余性。上述研究中都是將水聲目標(biāo)導(dǎo)航定位問題抽象為求解矩陣方程最小二乘解的問題。然而，由于水下環(huán)境的復(fù)雜性，水聲目標(biāo)定位是帶約束條件的非線性優(yōu)化問題，約束條件包括：聲速誤差、航行噪聲、應(yīng)答器偏移和載體搖擺等。將帶約束條件的非線性優(yōu)化問題退化為求解矩陣方程最小二乘解的問題，雖然降低了問題求解的復(fù)雜度，但這是以降低水下目標(biāo)導(dǎo)航定位精度為代價的。隨著海洋相關(guān)的各種應(yīng)用領(lǐng)域中對水下目標(biāo)導(dǎo)航定位的精度要求越來越高，高精度時延估計和帶約束條件的非線性優(yōu)化技術(shù)成為水聲導(dǎo)航定位領(lǐng)域的研究熱點。

時延估計精度是影響定位誤差的關(guān)鍵指標(biāo)之一，如何提高時延估計精度，已經(jīng)成為該領(lǐng)域?qū)＜覀兊臒狳c研究問題。文獻[7]采用倒譜方法估計水聲信號的時延，實驗結(jié)果表明該方法適用于高信噪比條件，其時延估計精度優(yōu)于廣義互相關(guān)方法。文獻[8]采用Chan算法獲得的到達時間差(Time difference of arrival,TDOA)定位結(jié)果作為Taylor 算法的初始值，提高了基于Taylor 算法的TDOA 定位精度，并采用仿真實驗驗證了該方法的有效性。文獻[9]采用相關(guān)峰分辨和穩(wěn)定相關(guān)峰跟蹤相結(jié)合的方法，以消除近程TDOA 被動定位中互相關(guān)峰模糊問題，并通過海上實驗驗證了該方法的有效性。文獻[10]采用對數(shù)域同態(tài)濾波技術(shù)來降低多途對水聲信號時延估計的影響，該方法先將接收信號進行對數(shù)變換，然后將其與本地信號進行譜減處理，再對處理后的信號進行濾波消除噪聲分量和殘留信號分量，最后將處理后的信號變換到時域，以獲得時延值，實驗結(jié)果表明該方法時延估計精度優(yōu)于復(fù)倒譜估計法。但是由于該方法對信號進行處理過程中使用了譜減法，當(dāng)接收信號與本地信號存在較大頻移時，該方法無效。目前，絕大部分研究成果都是從提高時延估計精度的角度，提高LBL系統(tǒng)定位精度。但是，受水聲信道的多途特性影響，目標(biāo)信號的到達時刻具有測不準性，限制了LBL系統(tǒng)定位精度的進一步提高。

為了進一步提高LBL 導(dǎo)航定位系統(tǒng)的定位精度，本文研究了利用同步信標(biāo)對目標(biāo)進行導(dǎo)航定位的問題，將水聲目標(biāo)導(dǎo)航定位問題抽象為帶約束條件的非線性優(yōu)化問題，論證了最優(yōu)化表達式參數(shù)求解過程與降低誤差源干擾的過程具有同一性，并采用并行蟻群算法(The parallel ant colony algorithm,PACA)求其最優(yōu)解，最后通過海試數(shù)據(jù)驗證該方法的有效性。

1 基于最優(yōu)化模型的LBL定位方法

LBL 定位系統(tǒng)由多個同步信標(biāo)構(gòu)成，信標(biāo)位于不同站點處，水下目標(biāo)通過接收多個信標(biāo)發(fā)射的導(dǎo)航信號，實現(xiàn)對自身的定位。令目標(biāo)在A點處的時刻收到站點i處在時刻發(fā)送的導(dǎo)航信號，A點和站點i的坐標(biāo)分別為(x,y)和(xi,yi)，A點與站點i之間的距離為ri，該時間段內(nèi)導(dǎo)航信號從站點i處傳播到A點的平均聲速為Ci，Ci的值根據(jù)發(fā)射和接收站點的水文環(huán)境參數(shù)信息通過KrakenC 計算得到[11]，目標(biāo)收到導(dǎo)航信號的站點數(shù)為N，A點為待求解位置，滿足方程組：

上述模型為二維平面導(dǎo)航定位模型，當(dāng)導(dǎo)航定位距離與海深的比值大于100 時，按照二維平面和三維球面兩種導(dǎo)航定位模型計算得到的兩點間距離之差小于2 m，由此導(dǎo)致的定位誤差與測時、聲速估計等其他原因?qū)е碌亩ㄎ徽`差相比要小1～2 個數(shù)量級，因此可以忽略不計。上述模型適用于淺海遠距離導(dǎo)航定位求解。

在矩陣方程組(1)中，由于GPS 接收模塊存在定位誤差，會導(dǎo)致站點i的坐標(biāo)(xi,yi)存在誤差；由于信道起伏、多途以及噪聲干擾等原因，會導(dǎo)致導(dǎo)航信號最佳到達時刻存在估計誤差；由于收發(fā)系統(tǒng)的同步誤差，會導(dǎo)致導(dǎo)航信號發(fā)送時刻和到達時刻存在測量誤差；由于水聲信道的非均勻性，采用發(fā)射和接收站點的水文環(huán)境參數(shù)信息，估計收發(fā)站點之間的平均聲速Ci存在較大誤差，并且聲速估計誤差引起的測距誤差會隨著距離的增大而增大。由于上述各種誤差源的存在，直接采用矩陣方程組(1)的最小二乘解作為目標(biāo)位置信息存在較大的定位誤差。

為了進一步提高導(dǎo)航定位系統(tǒng)的定位精度，本節(jié)將矩陣方程組(1)轉(zhuǎn)化為帶約束條件的非線性優(yōu)化問題：

其中，?x、?y和?ri是目標(biāo)函數(shù)中參數(shù)x、y和ri的調(diào)整量；Xmax、Ymax和Rmax是目標(biāo)函數(shù)中參數(shù)x、y和ri的最大調(diào)整量。求解式(2)過程中，三個參數(shù)、和Ci的各自誤差都作用在參數(shù)ri上，構(gòu)成綜合誤差?ri，通過對參數(shù)ri的調(diào)整可以同時降低收發(fā)系統(tǒng)同步誤差、測時誤差以及聲速估計誤差對定位精度的影響，而且需要調(diào)整的參數(shù)個數(shù)得到有效的降低，有利于提高目標(biāo)函數(shù)求解效率。求解式(2)所示的最優(yōu)化問題，即可得到目標(biāo)位置的最優(yōu)估計值。

2 PACA求解目標(biāo)位置信息

由于求解目標(biāo)位置信息的目標(biāo)函數(shù)表達式(2)是比較復(fù)雜的多極值問題，不能用解析法對其進行求解，本文采用迭代搜索的方法求其最優(yōu)解或者近似最優(yōu)解，這類逼近真實解的近似解在工程項目中仍具有現(xiàn)實意義[12]。蟻群算法[13]是一種啟發(fā)式算法，該算法本身具有隨機性，當(dāng)前，其收斂性還沒有嚴格的數(shù)學(xué)證明，但是大量實踐表明其在求解最優(yōu)化問題中性能優(yōu)異，已成為一種高效的最優(yōu)化問題求解工具。為了求解表達式(2)中的目標(biāo)位置信息的最優(yōu)解或者近似最優(yōu)解，設(shè)計了并行蟻群算法(PACA)，避免單次求解獲得較差的局部最優(yōu)解；同時，PACA在蟻群算法的基礎(chǔ)上進行改進，采用變步長搜索，以兼顧蟻群算法的求解效率和求解精度，即先采用較大步長搜索粗略解，隨著迭代次數(shù)的增加逐步縮小步長，以搜索精細解。PACA 系統(tǒng)框圖如圖1所示，即：同時且獨立啟動Q個子系統(tǒng)對表達式(2)進行求解，將各個子系統(tǒng)求解結(jié)果代入表達式(2)，從中選取最優(yōu)解，該最優(yōu)解作為目標(biāo)位置的最優(yōu)估計值。

圖1 PACA 用于LBL 定位的系統(tǒng)框圖Fig.1 PACA system block diagram for LBL positioning

PACA 的各個子系統(tǒng)求解表達式(2)中的目標(biāo)位置信息的最優(yōu)解或者近似最優(yōu)解，其實現(xiàn)步驟如下：

步驟1 算法初始化。求解方程組(1)獲得參數(shù)x、y的初值；最大迭代次數(shù)為Nmax；初始迭代次數(shù)為Num = 0；每一代蟻群的個體數(shù)為P；目標(biāo)函數(shù)求解精度閾值為θ。模型求解的收斂速度與適應(yīng)度函數(shù)所對應(yīng)的組合優(yōu)化參數(shù)的個數(shù)有關(guān)，組合優(yōu)化參數(shù)個數(shù)越少，收斂速度越快，模型求解所需迭代次數(shù)越少。本文適應(yīng)度函數(shù)中組合優(yōu)化參數(shù)個數(shù)為3，組合優(yōu)化參數(shù)規(guī)模較小，通常迭代求解30 次后，適應(yīng)度函數(shù)能收斂到穩(wěn)定殘差。

步驟2 計算下一代搜索路徑。下一代搜索路徑更新公式為

其中，wh為移動權(quán)重，h為迭代次數(shù)標(biāo)記，?xh、?yh和?ri,h為移動方向向量，xh、yh和ri,h為當(dāng)前一代參數(shù)值，xh+1、yh+1和ri,h+1為下一代參數(shù)值。為了加快收斂速度，同時保證計算精度，采用變步長搜索wx,h= (1?Num/Nmax)Xmax、wy,h=

移動方向矩陣為

其中，?xh、?yh和?ri,h中各個元素均為±1 之間的隨機數(shù)。

步驟3 計算適應(yīng)度函數(shù)，更新最優(yōu)解。將步驟2 中當(dāng)前一代中每一個體代入表達式(2)，計算當(dāng)前一代最優(yōu)解。

步驟4 判斷迭代是否停止。如果迭代次數(shù)達到Nmax，或者當(dāng)前最優(yōu)適應(yīng)度函數(shù)值小于θ，則停止迭代，目標(biāo)定位結(jié)果為當(dāng)前最優(yōu)解；否則，返回執(zhí)行步驟2。

上述算法時間復(fù)雜度分析：PACA 的單個子系統(tǒng)求解表達式(2)中的目標(biāo)位置信息的最優(yōu)解或者近似最優(yōu)解的時間復(fù)雜度為O(Nmax·P ·n2)[14]，其中n為適應(yīng)度函數(shù)所對應(yīng)的組合優(yōu)化參數(shù)的個數(shù)，本應(yīng)用中n= 3。在本應(yīng)用中，由于組合優(yōu)化參數(shù)規(guī)模較小，其計算效率較高。

3 海試數(shù)據(jù)驗證及結(jié)果分析

為了驗證PACA用于LBL定位的性能，本文將該方法定位結(jié)果與求解方程組(1)獲得的定位結(jié)果進行對比分析。實驗海區(qū)距離岸邊約60 海里，水深30～50 m，泥沙底質(zhì)。整個實驗為一個航次，采用雙船作業(yè)，其中科學(xué)三號為接收船，金星二號為發(fā)射船。在本次實驗中，由于只有一艘發(fā)射船發(fā)射導(dǎo)航信號，發(fā)射船需要機動才能在不同位置發(fā)射導(dǎo)航信號，因此接收船需要等待一定的時間才能收到發(fā)射船在多個不同位置發(fā)射的導(dǎo)航信號。在此期間，接收船采用船首拋錨方法，并通過GPS接收模塊來獲知本船的位置漂移。在本次實驗中，接收船和發(fā)射船的位置分布如圖2所示，在圖2中接收船在坐標(biāo)原點(站點M)處拋錨，站點M用“O”表示；發(fā)射船分別位于站點1、站點2、站點3 和站點4，其中，在站點1、站點2 和站點3 采用定點吊放聲源發(fā)射導(dǎo)航信號，發(fā)射船在站點4 從L1 運動到L2 采用拖曳聲源連續(xù)發(fā)射導(dǎo)航信號，以便于驗證不同距離定位精度，站點4包含436個測點。在本次實驗中，由于海深只有30～50 m，而導(dǎo)航距離在30 km 以上，因此將測量得到的聲傳播距離直接作為其在平面坐標(biāo)系上的投影距離，由此導(dǎo)致的定位誤差與測時、聲速估計等其他原因?qū)е碌亩ㄎ徽`差相比要小兩個數(shù)量級以上，因此可以忽略不計。

圖2 接收船和發(fā)射船的位置分布Fig.2 Position distribution of receiving and launching vessels

本實驗選取圖2所示的站點1、站點2、站點3和站點4 作為發(fā)射位置，對接收船進行定位，由于站點4 包含436 個測點，實驗獲得436 個定位結(jié)果。PACA 求解最優(yōu)化表達式(2)的相關(guān)參數(shù)值初始化如下：參數(shù)x、y和ri的最大調(diào)整量Xmax= 50、Ymax= 50 和Rmax= 40；求解表達式(2)的子系統(tǒng)數(shù)Q=10；各子系統(tǒng)的最大迭代次數(shù)為Nmax=50，每一代蟻群的子個體數(shù)為P= 40，θ= 500。對站點4 的第1 個發(fā)射點，PACA 的第一個子系統(tǒng)求解表達式(2)對應(yīng)的目標(biāo)函數(shù)收斂曲線如圖3所示。由聲學(xué)方法得到的接收船位置與由接收船GPS 接收模塊得到的真實位置之間的誤差如圖4所示，其中，虛線為求解方程組(1)獲得的定位結(jié)果對應(yīng)的定位誤差曲線，實線為PACA 方法求解最優(yōu)化表達式(2)的定位結(jié)果對應(yīng)的定位誤差曲線。

圖3表明PACA 方法求解表達式(2)所示的最優(yōu)化問題具有較好的收斂性。在圖4所示的定位誤差曲線對比圖中，采用計算矩陣方程的最小二乘解的定位方法，其定位誤差的最大值為147.13 m、最小值為47.60 m、平均值為81.37 m；采用PACA 求解最優(yōu)化表達式(2)的定位方法，其定位誤差的最大值為104.35 m、最小值為7.09 m、平均值為50.46 m。上述實驗結(jié)果表明，采用PACA 求解最優(yōu)化表達式(2)的定位方法，通過在目標(biāo)位置的最小二乘解和收發(fā)點的距離估計值附近啟發(fā)式搜索，能降低收發(fā)系統(tǒng)同步誤差、測時誤差、聲速估計誤差等對適應(yīng)度函數(shù)的干擾，能對適應(yīng)度函數(shù)起到優(yōu)化作用，進而提高目標(biāo)定位精度；蟻群算法求解最優(yōu)化表達式(2)可能獲得局部最優(yōu)解，采用PACA 方法獲得的目標(biāo)位置估計值更接近適應(yīng)度函數(shù)的全局最優(yōu)解。由于單個子系統(tǒng)求解表達式(2)的收斂速度較快，迭代20 次左右即可獲得平穩(wěn)殘差。當(dāng)并行子系統(tǒng)數(shù)Q較小時，可以采用Q次單個子系統(tǒng)串行求解的方法來等效并行求解；當(dāng)并行子系統(tǒng)數(shù)Q較大時，為了提高目標(biāo)定位的實時性，可以采用GPU 系統(tǒng)進行并行運算。

圖3 收斂曲線Fig.3 Convergence curve

圖4 定位結(jié)果誤差曲線的對比Fig.4 Comparison of the error curve of the location result

4 結(jié)論

本文將LBL 水聲導(dǎo)航定位問題抽象為帶約束條件的非線性優(yōu)化問題，并采用PACA求其最優(yōu)解。采用定位方程組的最小二乘解作為系統(tǒng)的初始值，降低了最優(yōu)解的搜索區(qū)間，能提高系統(tǒng)求解效率；與采用單獨的蟻群算法求解相比，采用PACA 進行求解，能降低算法本身可能陷入局部最優(yōu)解的影響，有利于提高解的精度和穩(wěn)定性；采用PACA 進行目標(biāo)函數(shù)求解的過程中，令其搜索步長隨著迭代次數(shù)的增加逐漸減小，既能提高算法迭代收斂速度，又能保證解的精確度。海試數(shù)據(jù)處理結(jié)果表明，與傳統(tǒng)的求解定位方程組的最小二乘解相比，本文方法平均定位誤差降低了30 m，能有效降低各個誤差源對水聲目標(biāo)導(dǎo)航定位精度的影響。