A Multiple Target Data Association Method for TDOA Passive

Localization Miao Feng 1 Key Laboratory of Underwater Acoustic Signal Processing of Ministry of Education Southeast University, Nanjing, 210096,China Shiliang FANG 2 Key Laboratory of Underwater Acoustic Signal Processing of Ministry of Education Southeast University, Nanjing ,210096,China Hongli Cao 3 Key Laboratory of Underwater Acoustic Signal Processing of Ministry of Education Southeast University, Nanjing ,210096,China

ABSTRACT To solve the problem of multi-target data association in an underwater acoustic passive positioning system, a new algorithm focused on data association of Time Difference of Arrival (TDOA) is studied. Firstly, the TDOA trajectory is modeled as a linear function. According to the continuous measurement values within a certain period, the expectation maximization algorithm based on the gaussian mixture model is used to fit the TDOA trajectory. Then TDOA measurements that come from the same acoustic source are associated based on zero cyclic sum condition. A quality factor is defined to measure the correct association probability. Finally, simulation results show that the method proposed in this paper can effectively solve the TDOA measurement association problem, and can be used for subsequent source locations. 1. INTRODUCTION

The localization of underwater acoustic sources is an active research field, which has been applied in the fields of marine environment detection and exploitation. Among them, there are many researches on multiple targets data association but mainly focus on using azimuth information obtained from direction finding to locate targets, while there are few researches on data association using TDOA directly. In terms of multi-target localization based on TDOA Claudio et al. employ the ROOT-MUSIC algorithm and estimate source positions by clustering of raw TDOA estimates [1]. This technique requires several frames of data to get a consistent cluster. Claudio et al. show

This work was supported in part by the Fundamental Research Funds for the Central Universities under Grant No. 2242021k30019, in part by the Belt and Road Fund on Water and Sustainability(Hydro-Lab, Hohai University & Nanjing Hydraulic Research Institute) under Grant No. 2021490811, and in part by the National Natural Science Funds of China under Grant Nos. 91938203. 1 230189078@seu.edu.cn, 2 slfang@seu.edu.cn, 3 honglicao@seu.edu.cn

that cluster centers are robust estimates of source locations. Lee et al. considered all delays corresponding to the threshold GCC-PHAT as candidates. A conditional data likelihood model based on a measurement hypothesis is implemented by the particle filter [2]. This method can be applied to initialize the source location. Scheuing and Yang [3] consider the conditions that TDOA from the same source must meet, such as the zero cycle sum condition and the grating condition, to eliminate invalid TDOA combinations before positioning.

This paper proposes an algorithm to locate multiple underwater targets. According to the time continuity of TDOA, the expectation maximization algorithm based on the Gaussian mixed model is used to fit the trajectory of TDOA measurement values among sensors. After obtaining multiple TDOA trajectories, it is required to correctly associate TDOA data with different sources for target positioning. The zero cyclic sum condition based on TDOA trajectory is used to evaluate the possibility that TDOA values of different sensor pairs are from the same target. According to the evaluation results, a method similar to DATMM is applied to associate multi-target TDOA [3].

2. SIGNAL MODEL

We assume N acoustic source targets and M sensors are distributed in a certain area, as shown in Figure 1. Assuming that there is no multipath effect caused by reflection, the signal received by the sensor u is given by

N

= = − + =  (1)

u u i i u i u i x t A S t n t u M 

, , 1 ( ) ( ) ( ) , 1,2,...,

where ( ) i S t is the signal of source i , , u i A is the attenuation factor from source i to sensor u , ( ) u n t

is the environmental noise. The TDOA between sensor u and sensor v for source i is

, , , uv i u i v i    = −

(2)

sensor u

, u i 

source

i

, v i 

, u j 

v

sensor

, v j 

, w i 

, w j 

source

j

w

sensor

Figure 1:Assuming N acoustic sources and M sensors

We use the classical GCC method to estimate the TDOA between sensor u and sensor v . Since there may be true peaks and spurious peaks at the same time due to the existence of noise, a conservative threshold is used to extract TDOA in order not to lose the true peaks.

1 ˆ ˆ { : } uv uv uv R    =  (3)

where uv R is generalized cross correlation and 1  is the threshold. Usually, the number of TDOA extracted is greater than the number of targets. 3. MULTIPLE TARGET TDOA DATA ASSOCIATION

Due to the influence of environmental noise and measurement error, the TDOA measurement is not always accurate, and the corresponding relationship between TDOA measurements and specific target is ambiguous in the case of multiple targets. Considering these two factors, multi-target localization is divided into two parts. The first step is to find the correct TDOA trajectory, and the second step is to associate multiple TDOA trajectories obtained in the first step with the target.

3.1. TDOA Trajectories Fitting of Multiple Sources

Studies show [4] that although sometimes there is no peak at the real TDOA, the distribution of the real peak is relatively stable over a period, while the spurious peak caused by noise is randomly distributed, as shown in Figure 2 and Figure 3. Hence, although not all the TDOA values we extracted in the previous section are correct, we can still use the time stability of the real TDOA peak to extract the TDOA trajectory as a whole.

Figure 2: Cross-correlation between sensors Figure 3: TDOA trajectory

We model the TDOA trajectory as a linear function which is a valid approximation in the case of slow target movement or short time interval:

, 1,2,..., , 1,2,..., k k j k z a x b k K j L  = + + = = (4)

where k a and k b are the parameters of th k TDOA trajectory,  is random noise, K is the number of trajectories and L is the length of the data. Without loss of generality, we assume that the TDOA measured noise is Gaussian noise, which obeys distribution:

2



− − = (5)

2 ( )

x

k

2 1 ( | , )

 

2 2

k P x e

k

k k



2

Then the noise of TDOA trajectories of different targets can be regarded as the Gaussian Mixture Model (GMM), and the expectation maximization (EM) algorithm is used to fit TDOA trajectories of multiple targets[5]. EM algorithm is an iterative optimization strategy[6], which is the maximum likelihood estimation of probability model parameters with hidden variables. Each iteration contains E-step and M-step as follows

• Initialize model parameters 0  • E-step: based on the current parameters, calculate the probability that each data j comes from a submodel k

• M-step: calculate the model parameters of the new iteration

• Repeat the calculation of E-step and M-step until convergence 1 i i    + −  .

Corresponding to the TDOA trajectory model proposed in (4), parameters need to be initialized are

2 0 ( , , , ) k k k k a b   = . k  is the probability that the observed data j x belongs to the k th submodel

K

=  =  (10)

k k k  

1 0 , 1

( | ) j k x   is the distributed density function of the k th submodel

2

− − − = (11)

2 ( )

z a x b

j k j k

2 1 ( | )

k x e   

2

k

j k



2

Different from general GMM model parameters, i a is need to be calculated here. According to the least square principle, it can be obtained by

− = 

( ) L



x z a

j j k jk j k L

=

1

(12)





2 1

x

j jk j

=

3.2. TDOA Data Association

For the same acoustic source, the TDOA between different sensors at the same time should satisfy the zero cyclic sum condition

, , , , , , , , , ( ) ( ) ( ) 0 uv i v i u i u i v i v i i i u i              + + = − + − + − = (13)

where { , , } {1,2,..., } u v M  is the subset of sensors. Therefore, for any three sensors, if TDOA can be observed, we use the zero cyclic condition to determine whether they belong to the same target. It’s important to note that the sum does not always exactly equal to 0 in practice because TDOA estimates are quantized and noisy. In addition, the zero cyclic sum condition is necessary but not sufficient, so it is easy to misjudge by using a single moment point. In this paper, we use TDOA measurements of the entire trajectory to replace a single moment point in (13).

, , , , uv i uv i v i u i    = + + = T T T T 0 (14)

T uv i uv i t uv i t uv i t    = T are the TDOA measurements at all times along the trajectory.

1 2 , , , , , , , [ , ,..., ] L

where

A method similar to DATEMM [5] is used to carry out data association for TDOA. Firstly, find all approximately TDOA triples and select the one with the highest quality as the initial triple. Then, find all possible fourth nodes and extend the initial triple to TDOA graph as complete as possible. From the unused TDOA triples, continue to select a triple with the highest quality as the initial triple for the next TDOA graph, and repeat the above steps until the remaining TDOA triples are not related. Different from DATEMM, the quality value Q is defined by (15) in this paper and

4. SIMULATIONS

4.1. Simulation Settings

A simulation is performed on the lake with three acoustic sources and ten sensors. Table 1 shows the position of sensors, and Table 2 shows the motion parameters of sources. The acoustic signal is modeled as ship radiated noise, and the signal sampling rate is 5000Hz.

Table 1: The position of sensors

Source# 1 2 3 4 5 6 7 8 9 10

X/ m 1000 1000 1000 0 0 0 0 -1000 -1000 -1000

Y/ m 1000 0 -1000 1500 500 -500 -1500 1000 0 -1000

Table 2: The motion parameters of sources

Source 1 Source 2 Source 3

Position/ m (480,1100) (830,-720) (-330,990)

Direction/ ° 80 180 -120

Velocity/ kn 4 3 2

4.2. Simulation Results

The TDOA trajectory fitting results of sensor 1 and sensor 5 are shown in Figure 4. Figure (b) is the partial enlargement of TDOA trajectory in Figure (a). It can be clearly noticed that EM algorithm can accurately extract multiple TDOA trajectories. We also observed in the simulation that EM algorithm is sensitive to the initial parameters, which can be solved by selecting the best result from multiple initializations.

The proposed method successfully associates TDOA data with the target. Figure 5 is the correlation result, and the edge value in the figure is the TDOA value at the initial time.

(a) (b) Figure 4:The TDOA trajectory fitting . (a)Three sources. (b)The first source

2

1

1 2

-0.4581 -0.45

-0.29

-0.63

0.06

0.27 -0.08

0.48 0.49 0.44

0.39

-0.26 -0.74 -0.35

0.09

-0.16

0.18

0.01

4 5

3 6

5

4

-0.09

-1.01

-0.39

-0.18

-0.71 -0.57

-0.04 -0.05 -0.40

-0.54

-0.66

-0.47

-0.42

-0.81

-0.35

-0.47

-0.24

9

8 9

8

7 10

Graph Ⅰ Graph Ⅱ Graph Ⅲ

Figure 5:TDOA graphs

5. CONCLUSIONS

This paper presented a target association algorithm based on TDOA trajectory. In this algorithm, the EM algorithm based on the Gaussian mixture model is firstly used to fit TDOA trajectory, and the fitted trajectory is associated with the target according to the zero cyclic sum condition. Finally an effective TDOA graph is obtained. Simulation results show that the algorithm has higher correlation accuracy than the method using a single point in time.

6. REFERENCES

1. E. D. Di Claudio, R. Parisi & G. Orlandi. Multi-source localization in reverberant environments

by root-music and clustering. IEEE International Conference on Acoustics, Speech, and Signal Processing, pp. 921-924. Istanbul, Turkey, Jun2000. 2. Lee.Y,Wada,TS & Juang. Multiple acoustic source localization based on multiple hypotheses

testing using particle approach. 2010 IEEE International Conference on Acoustics, Speech and Signal Processing , pp. 2722-2725. Dallas, TX, Mar2010. 3. Scheuing, J. & Yang, B. Disambiguation of TDOA estimation for multiple sources in

reverberant environments. IEEE Transactions on Audio Speech and Language Processing, 16(8) , 1479–1489 (2008). 4. An, L., Chen, L. J. & Fang, S. L. Investigation on correlation peaks ambiguity and ambiguity

elimination algorithm in underwater acoustic passive localization. Journal of Electronics & Information Technology , 35(12) , 2948–2953 (2013). 5. Liu, Y., Li, P. & Sheng, J. S. A multi-target tracks fitting algorithm based on expectation

maximization. Shipboard Electronic Countermeasure, 43(6) , 65–68 (2020). 6. A. P. Dempster, N. M. Laird & D. B. Rubin. Maximun likelihood from incomplete data via EM

algorithm. Journal of the Royal Statistical Society Series B-Methodological , 39 (1) , 1-38(1977). 7. Sundar, H. Sreenivas, TV & Seelamantula, CS. TDOA-Based Multiple Acoustic Source

Localization Without Association Ambiguity. IEEE-ACM Transactions on Audio Speech and Language Processing, 26(11) , 1976–1990 (2018).