基于元啟發(fā)算法的純方位被動定位方法

趙偉康, 韓一娜, 楊益新, 劉清宇

?

基于元啟發(fā)算法的純方位被動定位方法

趙偉康1, 韓一娜1, 楊益新1, 劉清宇2

(1.西北工業(yè)大學(xué) 航海學(xué)院, 陜西 西安, 710072; 2.海軍研究院, 北京, 100073)

傳統(tǒng)的最小二乘的純方位被動定位方法雖然運算簡單, 但是定位結(jié)果不夠可靠?；诖? 文中探究了利用元啟發(fā)算法進行純方位被動定位的可能性, 構(gòu)建了相應(yīng)的數(shù)學(xué)模型, 給出了具體的算法。通過對比該方法與傳統(tǒng)方法的效果, 同時對該方法在水聲觀測環(huán)境下的應(yīng)用進行仿真, 得出該方法的定位效果相較傳統(tǒng)的最小二乘定位方法有顯著的優(yōu)勢。

純方位被動定位; 元啟發(fā)算法; 最小二乘法

0 引言

目前, 國內(nèi)外應(yīng)用元啟發(fā)算法進行無線定位優(yōu)化的研究主要集中在無線傳感器網(wǎng)絡(luò)(wireless sensor network, WSN)定位中, 文獻(xiàn)[1]通過改進差分進化算法以適用于WSN定位問題; 文獻(xiàn)[2]利用差分進化算法改進距離無關(guān)(range-free)定位中典型的DV-Hop算法; 文獻(xiàn)[3]使用粒子群算法進行WSN定位; 此外還有很多利用優(yōu)化算法進行定位優(yōu)化的研究[4-6]。以上的研究主要針對的是WSN中的自定位, 待定位對象是在網(wǎng)絡(luò)中活動的節(jié)點, 不涉及目標(biāo)的定位?；诖? 文中提出將元啟發(fā)算法應(yīng)用于非合作目標(biāo)的純方位被動定位, 以取代傳統(tǒng)的基于最小二乘的定位方法[7-8]。目標(biāo)定位問題本質(zhì)上是基于觀測數(shù)據(jù)的點估計, 在多傳感器聯(lián)合觀測的環(huán)境下, 目標(biāo)定位實際上是信息融合的過程[9-10], 在適當(dāng)?shù)慕：笤獑l(fā)算法能夠很好地完成目標(biāo)統(tǒng)計信息的融合, 給出可信的定位結(jié)果。

1 純方位被動定位問題及傳統(tǒng)解法

1.1 純方位被動定位問題

純方位被動定位問題指的是觀測區(qū)域分布著若干傳感器(在水聲環(huán)境下指的是水聲換能器基陣), 這些傳感器被動工作且只能返回目標(biāo)的方位估計(direction of arrival, DOA), 同時, 傳感器的性能指標(biāo)(即測量方差)、坐標(biāo)以及參考方向(對于水聲基陣即是基陣的朝向)均是已知的。

如圖1所示, 純方位被動定位問題即是要試圖在已知4個傳感器位置、傳感器測量誤差模型以及4個測量出來的方位的情況下估計出目標(biāo)的位置。對于純方位被動定位問題二維空間最少需要2個傳感器才能完成定位, 這時候的定位方法是交叉定位, 當(dāng)具有更多的傳感器時可以用它們提供的信息修正定位結(jié)果。

1.2 基于最小二乘的純方位定位方法

圖1中4個傳感器的觀測形成了由4條射線組成的射線簇, 這些射線兩兩相交。最小二乘法試圖在圖中找出關(guān)于4條射線距離的平方和最小的點, 可以證明這個點就是4條射線形成的不規(guī)則四邊形的重心, 該重心總是能用解析的形式表達(dá)出來。在文獻(xiàn)[3]中有詳細(xì)的三維條件下最小二乘交會被動定位方法的推導(dǎo)。這種方法的優(yōu)點是其結(jié)果是解析的, 將觀測結(jié)果代入相應(yīng)公式即可得到定位結(jié)果。但是其間忽略了2個問題: 首先是在多個傳感器性能差距比較明顯的時候, 該方法并沒有辦法區(qū)分它們, 性能差的傳感器攜帶了更少的目標(biāo)信息, 卻能無差別和性能優(yōu)的傳感器一起影響定位結(jié)果; 其次是某個點到觀測射線的距離并不能完整地表征該點成為目標(biāo)的可能性, 接近某個傳感器的點距離觀測射線的距離必然很短, 但是這并不能保證其成為目標(biāo)的概率很大。因此, 需要尋找到一種可以考慮到這2個問題的模型。

2 基于元啟發(fā)算法的純方位被動定位

2.1 元啟發(fā)算法概述

元啟發(fā)算法(meta-heuristic algorithm)是區(qū)別于精確算法(exact algorithm)的一類算法, 它能向一些復(fù)雜的優(yōu)化問題提供近似最優(yōu)解, 尤其是應(yīng)用于非凸的優(yōu)化問題。文中使用的元啟發(fā)算法為差分進化(differential evolution, DE)算法[11], 具有原理簡單、易于實現(xiàn)、全局尋優(yōu)能力較好和魯棒性強等特點, 因此在科學(xué)研究和工程應(yīng)用領(lǐng)域都得到了廣泛應(yīng)用。DE算法與其他類似功能的元啟發(fā)算法的區(qū)別在于其關(guān)注了變量之間的相關(guān)性, 比較契合文中的優(yōu)化情景。

2.2 數(shù)學(xué)模型

式(2)構(gòu)建了目標(biāo)關(guān)于傳感器的真實方位在已知觀測方位后的后驗分布, 為了構(gòu)建以目標(biāo)真實位置為參數(shù)的似然函數(shù), 還需要額外假設(shè)傳感器的有效測量距離為。

半徑存在的意義在于如果不約束傳感器測量的距離, 式(3)無法成為一個概率密度。對每個傳感器的的要求是, 其圓形觀測區(qū)域應(yīng)該能包括目標(biāo)的活動區(qū)域。

該概率密度在空間中的特點是射線上的概率密度相同, 其直觀表現(xiàn)如圖2所示。

圖2中目標(biāo)真實位置在(1000, 2000)處, 傳感器位于原點。為了后續(xù)的計算方便, 對概率密度取負(fù)對數(shù), 深紅色區(qū)域表示概率密度大。

當(dāng)多個傳感器作用于該區(qū)域時, 由于它們之間的觀測是相互獨立的, 因此整個區(qū)域中某個點的概率密度正比于它在每個傳感器上的概率密度的乘積, 即

將式(5)帶入式(3), 則在每個傳感器的有效測量范圍相同時, 有式(6)所示聯(lián)合似然函數(shù), 可以成為估計目標(biāo)位置的依據(jù)。

式(7)的目標(biāo)函數(shù)十分復(fù)雜, 它依賴于包括觀測集和傳感器性能的諸多變量, 最優(yōu)化問題最常見的對目標(biāo)函數(shù)偏導(dǎo)數(shù)求極值的方法并不適用, 因為該方法數(shù)學(xué)形式不僅極其復(fù)雜且涉及到超越方程的求解, 即該最優(yōu)化問題是找不到解析解的。另一個方法是網(wǎng)格搜索, 該方法較笨重, 無法同時滿足高搜索精度和低運算量的要求。對于這類最優(yōu)化問題, 元啟發(fā)算法提供了一個新的思路。

2.3 差分進化算法求解模型

常見的元啟發(fā)算法大多能在一定程度上解決非凸優(yōu)化問題。式(7)的目標(biāo)函數(shù)在圖3的情景中是一個凸函數(shù), 但在更為不規(guī)律的傳感器布局下, 無法保證其始終是凸函數(shù), 該函數(shù)局部最優(yōu)值的數(shù)量是可控的, 它受限于傳感器的規(guī)模。因此, 選擇使用差分進化算法來求解式(7)中的優(yōu)化問題, 它的差分算子和變異算子為算法提供了跳出局部最優(yōu)解而尋求全局最優(yōu)解的能力。

圖4表示差分進化算法的普遍流程。該優(yōu)化問題的目標(biāo)函數(shù)只有2個變量, 因此算法壓力并不大, 可以很快向全局最優(yōu)解收斂。差分進化算法在該問題中泛用性很強, 而且在觀測環(huán)境發(fā)生變化(傳感器位置漂移、傳感器發(fā)生更換和增減、觀測的背景噪聲變化等情況)時, 僅需要維護差分進化算法的適應(yīng)度函數(shù)(對于優(yōu)化問題即指優(yōu)化函數(shù)本身)。

3 算法仿真分析

仿真分析分為兩部分, 第1部分比較在相同的觀測條件下文中方法和最小二乘法的性能; 第2部分是模擬該方法在分布式的水聲監(jiān)測網(wǎng)絡(luò)中的工作情況。

第1部分仿真對不同的傳感器測量標(biāo)準(zhǔn)差和不同的目標(biāo)位置使用2種方法進行定位運算。使用100次蒙特卡羅試驗的均方根誤差大小來衡量定位結(jié)果的優(yōu)劣

式(8)在統(tǒng)計意義上表達(dá)了定位的結(jié)果與真實位置的直線距離, 該值越小表示定位越準(zhǔn)確。表1為不同條件下2種算法的性能對比, 其中用LS代指最小二乘的方法, 用ML-DE代指文中提出的方法。

表1中每一個情況都是有代表性的, 它們分別是: 1) 傳感器性能好, 傳感器誤差相同, 目標(biāo)在觀測區(qū)域中央; 2) 傳感器性能較差, 傳感器誤差相同, 目標(biāo)在觀測區(qū)域中央; 3) 傳感器性能較好, 傳感器誤差有差異, 目標(biāo)在觀測區(qū)域中央; 4) 傳感器性能好, 傳感器誤差相同, 目標(biāo)偏離觀測區(qū)域中央; 5) 傳感器性能較差, 傳感器誤差不同, 目標(biāo)偏離觀測區(qū)域中央。根據(jù)結(jié)果可以看出,僅在各個傳感器性能相同且目標(biāo)與各傳感器距離相同時, 最小二乘方法的效果才能接近文中方法。在傳感器性能存在差異和目標(biāo)真實位置距離傳感器存在差異時, 最小二乘方法的效果明顯降低, 這是其數(shù)學(xué)模型中沒有考慮傳感器性能差異和目標(biāo)與傳感器距離導(dǎo)致的, 理論上在該方法中一個性能極差的傳感器能夠平等的和其他傳感器一起干預(yù)定位結(jié)果, 這違背了信息融合的原則。

表1 不同條件下2種算法的性能對比

第2部分仿真主要模擬該算法在水聲應(yīng)用背景下的定位效果。在水聲環(huán)境下被動測向的精度受到很多因素影響, 例如信噪比、陣列布局、目標(biāo)真實方位(端射方向的誤差明顯小于邊射方向)、陣元間時延測量的誤差, 以及DOA算法的選取都會影響對目標(biāo)的觀測模型。文中仿真考慮一種分布式的水聲監(jiān)測網(wǎng)絡(luò), 空間中存在大量獨立工作的傳感器節(jié)點, 每個傳感器節(jié)點僅有2個接收單元, 采用相位法測向, 即通過測量2個水聽器接收信號的相位差來解算目標(biāo)方位。這樣的傳感器節(jié)點單獨工作測向精度是不理想的, 無法達(dá)到陣元多孔徑大、搭載了更為復(fù)雜的DOA算法的水聲基陣的性能, 但是可以用多傳感器信息融合的收益來提高精度。

圖5體現(xiàn)了文中算法在水聲監(jiān)測網(wǎng)絡(luò)的效果。圖中分布有1個岸基節(jié)點和8個海上節(jié)點, 岸基節(jié)點測向精度較高, 方位估計偏差標(biāo)準(zhǔn)差為0.5o。海上節(jié)點標(biāo)準(zhǔn)差為2o。同時, 海上節(jié)點還存在自定位誤差, 協(xié)方差為diag([100,100])。使用文中方法對(2000, 2000) m處的目標(biāo)定位, 結(jié)果為(2062, 2055) m。

為了比較不同算法對該環(huán)境的定位誤差, 選擇主流的2種定位方法: 一種為正交向量估計器(orthogonal vectors, OV)的最小二乘方法和總體最小二乘方法(total least-squares, TLS)[12]。同樣使用均方根誤差衡量定位精度, 改變海上節(jié)點的測向標(biāo)準(zhǔn)差, 以上3種方法在不同測向精度下的表現(xiàn)如圖6所示。

圖6顯示了3種算法對位置(6000 m, 6000 m)和(10000 m,10000 m)目標(biāo)的定位效果。這2個位置分別代表了距離節(jié)點分布區(qū)域較近和較遠(yuǎn)的情況。在目標(biāo)距離傳感器節(jié)點較近時, 文中方法較其他2種方法的優(yōu)勢明顯, 而其他2種方法效果相當(dāng)。在目標(biāo)距離傳感器節(jié)點較遠(yuǎn)時, 3種方法的定位效果都有明顯下降, 這是純方位測量的固有特性, 此時文中方法依舊優(yōu)于其他2種方法。

4 結(jié)束語

提出了一種應(yīng)用于多傳感器被動定位的方法, 主要針對傳感器分布不固定, 傳感器之間性能差距較大的情景, 該方法的定位效果相對于傳統(tǒng)的最小二乘定位方法有顯著的優(yōu)勢。同時, 模擬了該方法在水聲環(huán)境下的應(yīng)用, 在配合水聲被動探測慣用的方法時, 可獲得可靠的定位效果。

[1] 楊俊.差分進化算法的改進及在無線傳感器網(wǎng)絡(luò)定位問題中的應(yīng)用[D].西安: 西安電子科技大學(xué), 2015.

[2] 楊楚皙.基于差分進化的DV-Hop定位改進算法[D].吉林: 吉林大學(xué), 2015.

[3] Li H, Xiong S W, Liu Y, et al.A Localization Algorithm in Wireless Sensor Networks Based on PSO[J].Computer Science, 2011, 6729: 200-206.

[4] Kannan A A, Mao G, Vucetic B.Simulated Anneaing Based Location in Wireless Sensor Network[C]//Proceedings of the 30th Annual IEEE Conference on Local Computer Net- works(LCN).Sydney: IEEE, 2005: 513-514.

[5] 葉蓉, 趙靈鍇.基于蟻群粒子群混合的無線傳感器網(wǎng)絡(luò)定位算法[J].計算機測量與控制, 2011, 19(3): 732-735.Ye Rong, Zhao Ling-kai.Localization Algorithm for Wireless Sensor Network Bosed on ACOPSO[J].Com-pu-ter Measurement & Control, 2011, 19(3): 732-735.

[6] 孫美玲.基于遺傳算法的無線傳感器網(wǎng)絡(luò)節(jié)點自定位算法研究[D].青島: 中國石油大學(xué), 2009.

[7] 譚維茜.多站純方位被動跟蹤粒子濾波算法研究[D].南京: 南京理工大學(xué), 2009.

[8] 樣柏勝.被動多傳感器探測目標(biāo)跟蹤技術(shù)研究[D].西安: 西安電子科技大學(xué), 2009.

[9] Stefano Coraluppi.Multistatic Sonar Localization[J].IEEE Journal of Oceanic Engineering, 2006, 31(4): 964-974.

[10] Mahler R P S.多源多目標(biāo)統(tǒng)計信息融合[M].范紅旗,盧大威, 劉本源, 等譯.北京: 國防工業(yè)出版社, 2013.

[11] Storn R, Price K.Differential Evolution-A Simple and Efficient Heuristic for Global Optimization over Conti-nuous Sp- ace[J].Journal of Global Optimization, 1997, 11(4): 341-359.

[12] Kutluyil Dogancay.Bearings-only Target Localization Using Total Least Squares[J].Signal Processing, 2005, 85(9): 1695-1710.

Bearing-Only Passive Location Based on Meta-Heuristic Algorithm

ZHAO Wei-kang1, HAN Yi-na1, YANG Yi-xin1, LIU Qing-yu2

(1.School of Marine and Technology, Northwestern Polytechnical University, Xi’an 710072, China; 2.Naval Research Academy, Beijing 100073, China)

Because the traditional bearings-only passive location approach based on the least square method cannot give much reliable location result, this paper explores the possibility of solving bearing-only passive location problem via the meta-heuristic algorithm, builds a corresponding mathematical model, and deduces a specific algorithm.Moreover, application of this method in underwater acoustic observation environment is simulated, and compared with traditional method.The result indicates that this method can achieve much better localization effect, compared with the traditional least square based passive location method.

bearings-only passive location; meta-heuristic algorithm; least square method

O229; TP301.6

A

2096-3920(2018)06-0623-05

10.11993/j.issn.2096-3920.2018.06.018

2016-11-19;

2016-12-18.

國家重點研發(fā)計劃(2016YFC1400200); 國家自然科學(xué)基金面上項目(61671388).

趙偉康(1995-), 男, 碩士, 主要研究方向為融合跟蹤算法。

趙偉康,韓一娜,楊益新,等.基于元啟發(fā)算法的純方位被動定位方法[J].水下無人系統(tǒng)學(xué)報, 2018, 26(6): 623-627.

(責(zé)任編輯: 陳 曦)