基于分治貪心思想的聯合多站目標關聯定位

王冠群， 張春華，3， 張舒然

(1.中國科學院 聲學研究所， 北京 100190； 2.中國科學院 先進水下信息技術重點實驗室， 北京 100190；3.中國科學院大學， 北京 100049；4.中國船舶工業系統工程研究院， 北京 100036)

0 引言

在水下低信噪比環境中，單一傳感器無法提供全面、準確的目標信息，難以實現準確的區域預警。分布式多傳感器網絡系統[1-3]作為新興手段，能夠提供多角度、多維度的目標觀測信息，是當前研究的熱點，但是多傳感器觀測也帶來了信息冗余和計算開銷等一系列難題[4]。多站方位量測目標關聯定位技術，也被稱為被動交叉定位技術[5-8]，是傳感器網絡系統中應用最廣泛的技術之一，特別是在復雜的水下環境中，很難通過其他屬性對目標進行有效的區分，而隨著高分辨率目標方位譜估計方法[9-11]的不斷出現，使得基于方位量測的水下目標關聯定位方法的應用研究[12]具有更大優勢。

對于目標定位問題，解決方法可以分為兩大類：一是最大似然估計法[13]，通過建立目標的聯合似然函數并求取最大估計值來獲得空間中的最優估計；二是通過建立偽線性方程組，并通過最小二乘算法[14]獲取近似最優解。這兩類方法的定位精度均建立在準確的數據關聯之上，由于量測- 目標之間的未知對應關系，導致上述定位方法不能直接應用，否則會產生虛假交點，因此數據關聯是定位過程的前提和基礎，也是研究的重點。目前常用的關聯方法包括最小距離法、最大似然法、周期譜相關法[15]，但它們或有效性低，或計算復雜，或存在需要目標先驗信息等缺點[16]。為了改善這些問題，姜亦武等[17]在最小距離交叉定位方法的基礎上，通過設置最小距離門限來剔除虛假交點，提高關聯效率和準確率。蔣維特等[18]提出一種基于距離的二次聚類方法，通過聚類方式改善了最小距離法關聯正確率低的缺點，同時減少了計算量，并且適用于傳感器漏檢的場景。竇麗華等[19]在概率思想基礎上提出一種新的改進單親遺傳數據關聯方法，將后驗概率的極大值求解問題轉化為求解特殊的指派問題，并通過遺傳算法來進行搜索優化，提高了目標關聯正確率和算法的收斂速度。李猛等[20]提出一種基于角度傳感器網絡的目標關聯定位方法，給出了存在量測誤差下目標定位概率的推導，實現在有限計算量下的虛假點剔除，提高了目標關聯的正確率和定位的可靠性。

傳統的多站方位量測目標關聯定位方法將關聯和定位拆成兩個獨立的計算過程，然后分別得到最優估計。這種分步處理并取局部最優的方式，在低檢測率、強虛警的水下環境中，存在目標定位精度不高、關聯正確率低等問題。為了提高水下多站多目標關聯定位技術的關聯正確率和目標定位精度，同時降低算法的計算開銷，本文提出一種基于分治貪心思想的多站關聯定位方法。首先根據分治思想[21]，采用最小距離原則選取每條方位線上的真實交點集合；然后根據貪心思想，對所有的交點集合進行合并，在集合合并的過程中，通過定位過程和關聯過程之間的反復驗證，從而保證了目標關聯的準確率和定位精度；最后根據關聯關系，對相互互斥的目標量測集合進行組合，并選取聯合關聯概率最大的多目標量測集合作為最后的輸出。仿真及試驗結果表明，在滿足一定虛警和漏檢的前提下，本文方法具有很高的關聯正確率和目標定位精度，并且算法的計算量適中，適用于實際水下場景。

1 數學模型

假設存在一個水下傳感器網絡系統來實現多目標定位過程，目標數目為D，節點數L，在某個觀測時刻，假設所有節點的量測集合為Z1∶L={Z1,…,Zl,…,ZL}，l為節點編號，節點l的觀測集合為Zl={Zl,1,…,Zl,nl,…,Zl,Nl}，nl=1,…,Nl表示節點l所獲得的目標量測編號。假設節點和目標的位置分別為Xl=[xl,yl]T、Xd=[xd,yd]T，d∈[1,D]，xl、yl和xd、yd分別為節點和目標的東向坐標和北向坐標，并假設目標d相對于節點l的方位角為θl,d，則對于任意目標d均滿足如下方程：

(1)

由于節點觀測誤差的存在，即Z=θ+V，θ為理想方位角，V為節點觀測誤差，節點方位量測Z與理想方位角θ之間無法直接建立一一對應的關系，因此基于多站方位量測的目標定位過程必然需要分解為關聯和定位兩個步驟。如圖1所示，在區域內布放3個探測節點，并實現對空間中的2個目標進行關聯定位過程。

圖1 基于多站方位量測的目標關聯定位示意圖Fig.1 Target association and positioning based on multi-station bearing measurement

2 算法原理

2.1 基于分治思想的最優交點集合選取

1)按照順序求取所有的方位線交點{Kl1nl1,l2nl2}|?l1,l2∈[1,L]，其中下標表示該交點由節點l1的Zl1,nl1號方位線與節點l2的Zl2,nl2號方位線相交產生。

2)對于任意一條方位量測線Zl0,nl0，選取該方位線上相鄰距離相對較短的M條線段，并尋找線段對應的方位線集合；例如交點Kl0nl0,l1nl1和Kl0nl0,l2nl2之間所夾的線段，與之對應的方位線集合為Wl0,l1,l2={Zl0,nl0,Zl1,nl1,Zl2,nl2}。

3)由于方位線集合中包含3個元素，可通過定位方法給出與該方位線集合相對應的目標位置估計，并計算目標d的關聯似然概率為

(2)

2.2 基于貪心思想的量測集合合并

對于任意由真實目標產生的方位量測，在理想條件下，該方位線上最優交點集合對應的方位線集合Wl0,l1,l2={Zl0,nl0,Zl1,nl1,Zl2,nl2}，必然為該目標所對應的方位量測全集的子集。由于很難通過尋找全局最優方式獲得真實目標的量測全集，通過對不同節點上的方位線集合Wl0,l1,l2進行合并也不乏是一種次優的處理方式。為了避免集合合并時的組合爆炸問題，本文基于貪心思想提出一種集合合并方法，該方法通過順序處理所有節點，將尋找全局最優問題分解成一系列局部最優選取過程來解決。為了方便理解，圖2中給出該方法的簡要流程示意。圖2中，?表示空集，l、l′∈[0，L]，l≠l′.

圖2 基于貪心思想的集合合并方法示意Fig.2 Set merging method based on greedy thought

如圖2所示，該方法按節點順序進行集合的合并，同時在合并前判斷是否滿足以下原則：

1)原集合所包含的方位量測是否已經遍歷所有節點；如果是，則不需要將原集合與并入集合進行合并(其中，前l個節點的已合并集合稱為原集合，節點l+1的方位量測集合稱為并入集合)。

2)原集合和并入集合之間是否存在互斥現象；如果是，則不能與并入集合進行合并(互斥現象是指在兩個集合的并集中，來自同一節點的量測數量大于1)。

最大長度Q的選擇對算法的復雜度和關聯正確率至關重要；當參數Q較大時，意味著保留更多的次優方位線集合，必然能夠提高目標關聯正確率，同時也增加了算法復雜度；當Q較小時，則結果相反。因此需要進行折中選擇，即在保證關聯正確率前提下，盡量降低算法的復雜度。實際情況下，可以考慮設置Q的值在目標數D的2～3倍之間；目標數D未知時，可以考慮用各觀測節點量測數的平均值來代替目標數D.

2.3 基于貪心思想的量測總集劃分

圖3 基于貪心思想的量測總集劃分Fig.3 Set division method based on greedy thought

(3)

3 計算機仿真

3.1 算法驗證

為了驗證本文方法的有效性，進行計算機仿真。設置探測節點數為4，相鄰節點間距為4 km，并呈正方形拓撲結構放置。每個節點對區域內的目標進行獨立觀測，同時假設所有節點的目標檢測概率均為Pd，虛警概率均服從期望值為λ的泊松分布，經過節點獨立檢測后，單節點探測系統會輸出一系列方位量測信息，包括目標量測和虛警雜波，其中假設所有單節點探測系統的角度探測誤差均服從均值為0°、方差為σ2的高斯分布，虛警雜波在觀測范圍(-π rad,π rad]內服從均勻分布。為了更全面地反映本文方法的關聯性能，下面分別設置3個不同的仿真場景。

3.1.1 場景1：低雜波雙目標場景

假設在水下探測區域內存在2個靜止目標，位置分別為[500 m，-1 500 m]、[-500 m，800 m]，假設探測節點的目標檢測率為0.9，虛警期望為1，測向誤差為1°.探測節點以及目標位置布置場景示意如圖4所示。由于目標漏檢、目標虛警以及節點角度探測誤差的存在，導致方位量測不能與目標完美對應，因此需要借助關聯定位方法來給出最優的目標位置估計。

圖4 探測節點以及目標位置布置場景1Fig.4 Detecting nodes and target locations in Scenario 1

圖5所示為本文方法對2個目標的關聯定位結果，在定位過程中采用最小二乘算法，并且假設目標數未知，設置本文方法中的參數為M=3，Q=10，I=5.從圖5中可以看出，在該仿真條件下本文方法能夠準確地估計出空間中的目標個數，其目標定位誤差約為30 m，表明該方法在低雜波、少量目標場景下能夠實現有效的目標關聯定位過程。

圖5 場景1目標關聯定位結果Fig.5 Target association and positioning results in Scenario 1

3.1.2 場景2：高雜波雙目標場景

場景2中除了提高雜波的密度以外(假設虛警期望為10)，其他場景參數設置與場景1相同。設置參數為M=5，Q=10，I=5，圖6～圖9分別為場景示意和目標關聯定位結果。

圖6 探測節點以及目標位置布置場景2(無明顯虛假焦點)Fig.6 Detecting nodes and target locations in Scenario 2(without obvious false focus)

圖7 場景2目標關聯定位結果(無明顯虛假焦點)Fig.7 Targets association and positioning results in Scenario 2 (without obvious false focus)

圖8 探測節點以及目標位置布置場景2(存在明顯虛假焦點)Fig.8 Detecting nodes and target locations in Scenario 2(with obvious false focus)

圖9 場景2目標關聯定位結果(存在明顯虛假焦點)Fig.9 Target association and positioning results in Scenario 2 (with obvious false focus)

對比圖6～圖9可以看出，在高雜波、少量目標場景下，本文方法能夠對真實目標進行正確關聯，并輸出準確的定位估計結果，但是由于目標數目未知，容易出現虛假關聯目標(見圖9)。分析圖8可知，在高雜波、少量目標場景下，各觀測節點的雜波容易匯聚成虛假焦點(見圖8)，從而導致出現虛假關聯目標。

3.1.3 場景3：高雜波密集目標場景

場景3中假設在水下探測區域內存在6個靜止目標，目標位置在場景中隨機分布，假設探測節點的目標檢測率為0.9，虛警期望為5，測向誤差為1°.設置參數為M=5，Q=20，I=10，圖10、圖11分別為場景示意和目標關聯定位結果。

圖10 探測節點以及目標位置布置場景3Fig.10 Dectecting nodes and target locations in Scenario 3

圖11 場景3目標關聯定位結果Fig.11 Target association and positioning results in Scenario 3

觀察圖10、圖11可以看出，在高雜波密集目標場景下，本文方法能夠對大部分目標進行正確關聯，并輸出準確的定位估計結果，但是也正是由于虛假焦點的存在(見圖10)，導致少部分目標出現錯誤關聯(見圖11)。因此也從側面反映出本文方法在高雜波、密集目標并且存在虛假焦點的情況下，存在目標錯誤關聯的潛在風險。

3.2 性能分析

為了進一步分析本文方法的關聯定位性能，選用文獻[18]中的關聯定位方法作為對比方法；該方法基于二次聚類思想，并采用最小距離法則尋找最優關聯關系，以實現目標關聯定位過程。由于這兩種方法本質上更側重于關聯技術的創新，先對兩種方法的關聯正確概率進行對比分析。

在仿真場景1的基礎上，針對不同參數影響，分別進行100次蒙特卡洛實驗。為了方便統計關聯正確率，在計算過程中假設目標數已知，此時對于真實目標只存在正確關聯和錯誤關聯兩種狀態，排除了因目標數目估計錯誤所導致的關聯正確率難以統計的情況，仿真結果如表1～表3所示(除表中可變參數外，其他參數與場景1中參數一致)。

表1 不存在漏檢和虛警時關聯正確率仿真結果對比Tab.1 Comparison of simulated results without missingdetection and false alarm

表2 只有虛警時關聯正確率仿真結果對比Tab.2 Comparison of simulated results with only false alarm

表3 同時存在虛警和漏檢時關聯正確率仿真結果對比Tab.3 Comparison of simulated results with missingdetection and false alarm

從表1～表3中可知：相對于文獻[18]方法，本文方法在存在角度誤差、虛警及漏檢時的目標正確關聯概率均優于文獻[18]方法；在不存在漏檢時，本文方法的關聯正確率均能保持在90%以上；在同時存在虛警和漏檢時，本文方法仍能保證70%以上的關聯正確率，而文獻[18]方法的關聯正確率隨虛警概率增大而迅速下降，最終導致方法失效。這是因為在建立關聯關系的過程中，文獻[18]方法僅采用最小距離法則，而本文方法同時結合最小距離法則和最大似然法則，因此本文方法具有更高的關聯正確率以及寬容性。同時，由于本文方法采用貪心思想簡化關聯搜索過程，將原本全排列的整體尋優過程簡化為線性連續的局部尋優過程，因此大大減少了計算量。

在進行多站多目標關聯定位時，目標的關聯正確率同樣受多目標的相對空間位置影響；當多個目標相距較遠時，節點的目標量測相對分離，關聯正確率也相對較高，隨著多目標之間的間距縮小，節點的目標量測相互靠近重疊，甚至會導致目標漏檢，則此時關聯正確率必然下降。下面在場景1的基礎上，對多目標間相對位置變化時兩種方法目標關聯性能進行仿真分析。在定位過程中采用最小二乘算法，設置本文方法的參數為M=3，Q=10，I=5，目標檢測率為0.9，虛警期望為1，測向誤差為1°.

圖12所示為探測節點以及目標位置變化場景示意，場景中假設目標2位置不變，目標1逐漸向目標2靠近。目標間距變化時，兩種關聯定位方法的仿真結果如表4所示。觀察表4可知：兩種方法的關聯正確率均隨著目標間距離縮小而下降，但是相對于文獻[18]方法，本文方法的目標正確關聯概率相對較高，且仍能保證70%以上的關聯正確率。

圖12 探測節點以及目標位置變化Fig.12 Dectecting nodes and change of target locations

表4 目標間距變化時關聯正確率仿真結果對比

由于本文方法和文獻[18]方法的創新之處更側重于關聯技術，并且均能與不同的定位方法進行組合，因此下面就結合兩種不同的定位技術對目標定位精度展開討論。表5所示為組合方法與其編號的對應關系。

圖13所示為表5中4種組合方法在不同角度觀測誤差下，100次蒙特卡洛仿真后的目標平均定位精度結果。圖5中假設不存在目標漏檢和虛警雜

圖13 不同方法組合時的目標定位精度分析Fig.13 Positioning accuracy with the combination of different methods

表5 組合方法與其編號對應關系Tab.5 Correspondence between algorithm and number

波，并假設目標關聯錯誤時的定位誤差上限為1 km，即定位誤差超過1 km時按1 km進行統計。分析可知，當節點的角度觀測誤差較小時，本文方法與對比方法的關聯正確率都較高，因此影響定位精度的主要因素就是搭載的定位方法。由于基于最大似然思想的定位方法在理論上能給出系統的最優估計，而基于最小二乘算法的定位方法則是將非線性的定位方程改寫成偽線性的方程組并求取次優解，原則上最大似然算法的定位方法的定位精度要高于最小二乘算法的定位方法。隨著節點的角度觀測誤差增大，由關聯錯誤會導致定位精度迅速下滑，并逐漸成為影響定位精度的主導因素，而在同等條件下，本文方法的關聯正確率優于對比方法，定位精度也相對更高。

4 試驗驗證

利用2020年11月在浙江省千島湖進行的分布式多節點聯合處理試驗來驗證本文方法性能。試驗中采用3條懸浮在水中的水平陣對試驗區域內的合作聲源進行探測。在某觀測時間段內，取時長為10 s的觀測數據進行處理，期間合作聲源目標相對處于靜止狀態。通過對該時間段內探測節點、合作聲源的全球定位系統信息進行提取，其位置關系如圖14所示。

對試驗時間內陣列的接收信號進行目標方位譜估計(包括常規波束形成、高分辨譜估計方法)，各個接收陣在10 s觀測時間內的方位歷程圖如圖15所示。對場景中的目標進行閾值檢測，并根據陣列姿態信息對目標檢測結果進行空間上的校正，以獲得各個觀測節點的方位量測結果，如圖16所示。

圖15 兩種不同方法的方位譜估計結果Fig.15 DOA results of two different methods

圖16 節點、目標、方位量測間相對關系Fig.16 Relative relationship among node，target and azimuth measurement

利用本文方法加上最小二乘算法(即表5中組合方法2)來實現目標關聯定位過程，結果如圖17所示。從圖17中可以看出，利用本文方法在實際水下環境中能夠實現有效的目標關聯定位過程。

圖17 試驗中目標關聯定位結果Fig.17 Target association and positioning results in experiment

為了統計分析本文方法的實際關聯定位性能，對109 s觀測時間內的接收數據進行滑動積分和閾值檢測處理。實際處理時每幀的積分時長為10 s，幀與幀之間的滑動長度為1 s，即第n幀的積分時間段為[n-1 s,n+9 s]，n=1,2,…,100. 各節點方位歷程圖如圖18所示。在觀測時間內，目標和觀測節點均處于靜止狀態，通過閾值檢測和空間校正，以獲得各個觀測節點的方位量測結果，如圖19所示，圖中縱軸為大地坐標系下的角度(即以正北為0°，按順時針為正)。

圖18 兩種不同方法的方位譜估計結果Fig.18 DOA results of two different methods

用圖19中的目標方位檢測結果作為關聯定位方法的輸入來分析本文方法在實際環境下的目標關聯定位性能，并同樣選擇文獻[18]方法進行對比分析，結果如表6所示。從表6中可以看出：在實際單目標場景中，兩種方法均有良好的關聯定位性能，且目標定位誤差與節點平均間距之比均小于4%. 對比兩種方法的平均單幀運算時間，可以看出本文方法的運算速度更快，計算量更小。

圖19 各節點方位檢測結果Fig.19 DOA results of nodes

表6 目標定位結果分析Tab.6 Analysis of target positioning results

5 結論

本文針對多站多目標關聯定位問題，提出一種基于分治貪心思想的多站關聯定位方法。該方法先根據分治思想并采用最小距離原則選取每條方位線上的真實交點集合；再根據貪心思想對所有的交點集合進行合并，以及目標量測集合間的組合，并選取聯合關聯概率最大的多目標量測集合作為最優的關聯定位估計結果。仿真結果表明，在一定虛警率和漏檢情況下，本文方法有很高的關聯正確率和定位精度，同時利用貪心思想降低了計算復雜度，適用于實際水下場景。仿真結果及湖試數據均驗證了該關聯定位方法的有效性。