基于元啟發算法的純方位被動定位方法

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

?

基于元啟發算法的純方位被動定位方法

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

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

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

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

0 引言

目前, 國內外應用元啟發算法進行無線定位優化的研究主要集中在無線傳感器網絡(wireless sensor network, WSN)定位中, 文獻[1]通過改進差分進化算法以適用于WSN定位問題; 文獻[2]利用差分進化算法改進距離無關(range-free)定位中典型的DV-Hop算法; 文獻[3]使用粒子群算法進行WSN定位; 此外還有很多利用優化算法進行定位優化的研究[4-6]。以上的研究主要針對的是WSN中的自定位, 待定位對象是在網絡中活動的節點, 不涉及目標的定位?；诖? 文中提出將元啟發算法應用于非合作目標的純方位被動定位, 以取代傳統的基于最小二乘的定位方法[7-8]。目標定位問題本質上是基于觀測數據的點估計, 在多傳感器聯合觀測的環境下, 目標定位實際上是信息融合的過程[9-10], 在適當的建模后元啟發算法能夠很好地完成目標統計信息的融合, 給出可信的定位結果。

1 純方位被動定位問題及傳統解法

1.1 純方位被動定位問題

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

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

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

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

2 基于元啟發算法的純方位被動定位

2.1 元啟發算法概述

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

2.2 數學模型

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

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

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

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

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

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

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

2.3 差分進化算法求解模型

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

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

3 算法仿真分析

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

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

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

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

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

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

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

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

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

4 結束語

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

[1] 楊俊.差分進化算法的改進及在無線傳感器網絡定位問題中的應用[D].西安: 西安電子科技大學, 2015.

[2] 楊楚皙.基于差分進化的DV-Hop定位改進算法[D].吉林: 吉林大學, 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] 葉蓉, 趙靈鍇.基于蟻群粒子群混合的無線傳感器網絡定位算法[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] 孫美玲.基于遺傳算法的無線傳感器網絡節點自定位算法研究[D].青島: 中國石油大學, 2009.

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

[8] 樣柏勝.被動多傳感器探測目標跟蹤技術研究[D].西安: 西安電子科技大學, 2009.

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

[10] Mahler R P S.多源多目標統計信息融合[M].范紅旗,盧大威, 劉本源, 等譯.北京: 國防工業出版社, 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.

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

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

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

(責任編輯: 陳 曦)