# Effective Passive Multitarget Localization Using Maximum Likelihood

Authors: Yasir Munir; Muhammad Umar Aftab; Danish Shehzad; Ali M. Aseere; Habib Shah
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Localization of multiple targets is a challenging task due to immense complexity regarding data fusion received at the sensors. In this context, we propose an algorithm to solve the problem for an unknown number of emitters without prior knowledge to address the data fusion problem. The proposed technique combines the time difference of arrival (TDOA) and frequency difference of arrival (FDOA) measurement data fusion which further uses the maximum likelihood of the measurements received at each sensor of the surveillance region. The measurement grids of the sensors are used to perform data association. The simulation results show that the proposed algorithm outperforms the multipass grid search and further effectively eliminated the ghost targets created due to the fusion of measurements received at each sensor. Moreover, the proposed algorithm reduces the computational complexity compared to other existing algorithms as it does not use repeated steps for convergence or any biological evolutions. Furthermore, the experimental testing of the proposed technique was executed successfully for tracking multiple targets in different scenarios passively.


---

## Body

## 1. Introduction

In the modern era of wireless technologies, the localization of the target sensors such as aircraft, ships, or unmanned vehicles is challenging. The challenge is magnified further when positions and velocities of sensor targets cannot be estimated precisely which results in the inaccuracy of sensor’s locations and massive consequences in the practical environment [1]. Most of the previous research studies utilized localization methods that mainly depend on the accuracy and robust estimation, in which the time difference of arrival (TDOA) has significant importance. This TDOA is based on receiving the same signal on different sensors or receivers varying in time. Further, it is used to calculate the difference in the signal’s arrival with respect to the reference sensor. Emitter devices have the benefit of providing the frequency difference of arrival (FDOA) which is the result of the relative motion of the source and the target, which improves the accuracy with the estimation of the velocity of the target [2]. Passive localization of a target or multiple targets has one advantage over active localization, that passive localization is stealth in nature, which localizes the target without letting the target know about the existence of the sensors.Consider passive localization using TDOA/FDOA measurement to initially estimate a single target and develop an algorithm to estimate multitargets. Compare the performances using different metrics, including geometric dilution of precision (GDOP) [3], measurement covariance, sensor’s self-navigation error, data-link transmission delay, and sensor geometry to help in better understanding of the research topic. Also, there is a need for a well-developed, efficient, and effective algorithm to localize the multitargets which should be able to deal with the complexity of the measurement fusion and localize multitargets and further track the targets without any prior information. So, consider the increasing interest to have such an algorithm that can localize the increasing number of emitter devices.A previous work using passive localization extensively focuses on a single target, whereas very few studies in the literature are found related to multitarget localization. Localization of multiple targets is very complicated and difficult to estimate their positions than a single target as sensors receive multiple signals, and it becomes a fusion of signals, therefore becoming complex to associate the exact signal to the target. It becomes worst in the presence of high noise. Also, the data reduction can cause the loss of possible target detection in a specific area due to noise [4].The localization problem is challenging. However, this problem can be solved using different approaches—the Taylor series [5] with a good initial guess. Chan and Ho [6] and Ho and Xu [7] proposed a two-step weighted least square (WLS) [8] and total least square and the semidefinite programming (SPD) [9] method based on ML, whereas localization of the target can also be achieved using a reconfigurable intelligent surface (RIS) supported with millimeter-wave multi-input multi-output radar system [10] and based on link analysis in passive UHF RFID to identify real targets and eliminate false targets [11].Sensor geometry along with the number of sensors is essential in localization. Strong sensor geometry results in a small GDOP [3] value and will cause low position uncertainty, where the number of sensors is the means of measurements. As the number of sensors increased, the estimate’s accuracy and efficiency increase, but the problem in localization is to decrease the number of sensors without decreasing the accuracy, or say reasonable accuracy should be maintained [12]. In the future, the proposed algorithm could be extended in vehicle identification using the RF signals for traffic surveillance [13, 14].The proposed algorithm is able to localize the unknown number of targets having the complexity of the multiple sensors with multiple grids; the algorithm is not complex as it is not using repeated steps for convergence, not using any biological evolutions used in the existing algorithms; in a single scan, it computed likelihood for all sensors using only one parameter grid and passes the results for multitarget estimation. It also eliminates the localization of the ghost target which becomes an issue when the measurement data fusion is received; here, we call them possible candidates when considering the combinations of the measurements from different sensors.This paper is organized to easily understand the research purpose from the background and primary literature to the research topic. Including the introduction, it is divided into five sections. The second section describes the related work to the proposed algorithm, while the third section explains the proposed algorithm step by step using mathematical equations and block diagrams. The fourth section shows the results of the algorithm, and the last section concludes this research paper.


## 2. Applications Using Maximum Likelihood for Multitargets

Few applications make use of maximum likelihood for tracking multiple targets. But there is not much in the literature. Following are the three optimization algorithms:(1)
Multipass grid (MPG)(2)
Genetic algorithm (GA)(3)
Directed subspace (DSS)All the above algorithms use a set of certain threshold measurements over several frames (data window length) from a detection processor. The time to calculate a track estimate is primarily a function of the maximization routine used on the LLR (Log-Likelihood Ratio). This, in short, depends upon the number of data frames involved in the estimate, the detections in each data frame, and the number of LLR calculations required by the maximization algorithm [15].The parameter space is the measurements comprised of bearing, range, range rate, and amplitude values. Dissimilarities in the dimensionality of the observation space, window length, detectorPfa, and target SNR (signal to noise ratio) are considered. Let us have a brief overview of each one by one.


### 2.1. Multipass Grid (MPG)

In this method,K steps are involved. A set of values ck are monotonically decreasing, here k=1,2,⋯,K, and are established with ck=1. A grid search is implemented over the parameter space using the artificially improved measurement noise standard deviations. The standard deviation of every measurement component is amplified by multiplying it by a parameter defined c1. From the grid search, the best value resulting is forwarded to a local optimization routine, for example, a Newton-Raphson or Davidon-Fletcher-Powell.During each successive step, the smaller and new values of measurement noise standard deviation are used. The local optimization routine is started in steps from the parameter value it had converged in the previous step [16]. Repeat the process until k=K at which the measurement noise standard deviations are restored to their actual value. Once it has converged by the local optimization routine at the final step, the track estimate is obtained [17].Using a multipass grid search has an advantage as it requires less computation than a comprehensive search. However, for the more composite difficulty, the multipass grid requires a large number of evaluations and additional calculations to achieve the results.


### 2.2. Genetic Algorithm (GA)

Over a discrete parameter space, a stochastic search is performed using a set of rules based on biological evolutionary development. Theory suggests that when using the GA, one is essentially searching more of the parameter space than that is reflected in the number of LLR evaluations corresponding to a purely random search computing up to the cube of the number of LLR evaluations used in the genetic search.Genetic algorithm is effective and capable of searching the global maximum which has been shown for a varied class of objective functions [18] and in many cases has performed the best of other optimization methods [19].In practice, the employment of GA is not able to find the global maximum with probability 1 of the random neutral function. Results in [20] show the asymptotic convergence beyond the critical population size. However, it is challenging to limit the essential population size in a particular problem. Table 1 lists the steps which are performed to generate one generation using a genetic algorithm [18].Table 1
Steps of genetic algorithm.
StepAction1Calculate the fitness function for every population fellow2Selection of the reproduction population3Selection of the reproduction population mates4Child population production (cloning or crossover)5Apply alterations to the child population6Trial experiment for convergence


### 2.3. Directed Subspace (DSS)

This algorithm is motivated by a methodology of using the data information of the measurements to guide the search. Directed subspace utilizes the measurement information itself to select and search regions of parameter space that might contain the LLR global maximum while avoiding those parameter space regions that cannot have this maximum.In many tracking applications, the space of measurements is defined as the subspace of the parameter space that can be of any dimensional measurement space. For example, range, range rate, and bearing become a 3-dimensional measurement space. Range and bearing can map to the Cartesian positions and range rate is a counterpart to radial velocity. Table2 lists the steps in the direct subspace algorithm search [19].Table 2
Steps of the direct subspace algorithm.
StepAction1Setting grid density for the free parameter(s)2Mapping one measurement to parameter space3Using the measurements, calculate LLR over the grid of free parameter(s)4Repeat steps 2 and 3 for all measurements in the data set5Forward the finest result in the local optimization routineOnce the LLR values are computed over the grid using the measurements, a local optimization algorithm [21] is used for the final converged parameter.


#### 2.3.1. Window-Based ML-PDA Algorithm

The window-based ML-PDA algorithm is developed in a way to use in real-time applications; to compute the track estimate, a subset of theNw most recent data frames is used [22]. When a new frame is received with data, the ML-PDA algorithm is recurred, as it adds the new data frame; the oldest data frame is removed from the data set, which creates a sliding window for localization and tracking update.The existing work requires a large number of evaluations and computations to achieve results where the employment of GA is not able to find the global maximum with probability 1 of random neutral function. It is challenging for existing work to limit the essential population size in a particular problem, whereas the proposed algorithm requires no convergence and less computation. Some of the productive work regarding the multitarget localization and object recognition algorithms are experimented using different distributed algorithms, and some of them are introduced for tracking of vehicles along with other items of interest [23–26].


## 2.1. Multipass Grid (MPG)

In this method,K steps are involved. A set of values ck are monotonically decreasing, here k=1,2,⋯,K, and are established with ck=1. A grid search is implemented over the parameter space using the artificially improved measurement noise standard deviations. The standard deviation of every measurement component is amplified by multiplying it by a parameter defined c1. From the grid search, the best value resulting is forwarded to a local optimization routine, for example, a Newton-Raphson or Davidon-Fletcher-Powell.During each successive step, the smaller and new values of measurement noise standard deviation are used. The local optimization routine is started in steps from the parameter value it had converged in the previous step [16]. Repeat the process until k=K at which the measurement noise standard deviations are restored to their actual value. Once it has converged by the local optimization routine at the final step, the track estimate is obtained [17].Using a multipass grid search has an advantage as it requires less computation than a comprehensive search. However, for the more composite difficulty, the multipass grid requires a large number of evaluations and additional calculations to achieve the results.


## 2.2. Genetic Algorithm (GA)

Over a discrete parameter space, a stochastic search is performed using a set of rules based on biological evolutionary development. Theory suggests that when using the GA, one is essentially searching more of the parameter space than that is reflected in the number of LLR evaluations corresponding to a purely random search computing up to the cube of the number of LLR evaluations used in the genetic search.Genetic algorithm is effective and capable of searching the global maximum which has been shown for a varied class of objective functions [18] and in many cases has performed the best of other optimization methods [19].In practice, the employment of GA is not able to find the global maximum with probability 1 of the random neutral function. Results in [20] show the asymptotic convergence beyond the critical population size. However, it is challenging to limit the essential population size in a particular problem. Table 1 lists the steps which are performed to generate one generation using a genetic algorithm [18].Table 1
Steps of genetic algorithm.
StepAction1Calculate the fitness function for every population fellow2Selection of the reproduction population3Selection of the reproduction population mates4Child population production (cloning or crossover)5Apply alterations to the child population6Trial experiment for convergence


## 2.3. Directed Subspace (DSS)

This algorithm is motivated by a methodology of using the data information of the measurements to guide the search. Directed subspace utilizes the measurement information itself to select and search regions of parameter space that might contain the LLR global maximum while avoiding those parameter space regions that cannot have this maximum.In many tracking applications, the space of measurements is defined as the subspace of the parameter space that can be of any dimensional measurement space. For example, range, range rate, and bearing become a 3-dimensional measurement space. Range and bearing can map to the Cartesian positions and range rate is a counterpart to radial velocity. Table2 lists the steps in the direct subspace algorithm search [19].Table 2
Steps of the direct subspace algorithm.
StepAction1Setting grid density for the free parameter(s)2Mapping one measurement to parameter space3Using the measurements, calculate LLR over the grid of free parameter(s)4Repeat steps 2 and 3 for all measurements in the data set5Forward the finest result in the local optimization routineOnce the LLR values are computed over the grid using the measurements, a local optimization algorithm [21] is used for the final converged parameter.


### 2.3.1. Window-Based ML-PDA Algorithm

The window-based ML-PDA algorithm is developed in a way to use in real-time applications; to compute the track estimate, a subset of theNw most recent data frames is used [22]. When a new frame is received with data, the ML-PDA algorithm is recurred, as it adds the new data frame; the oldest data frame is removed from the data set, which creates a sliding window for localization and tracking update.The existing work requires a large number of evaluations and computations to achieve results where the employment of GA is not able to find the global maximum with probability 1 of random neutral function. It is challenging for existing work to limit the essential population size in a particular problem, whereas the proposed algorithm requires no convergence and less computation. Some of the productive work regarding the multitarget localization and object recognition algorithms are experimented using different distributed algorithms, and some of them are introduced for tracking of vehicles along with other items of interest [23–26].


## 2.3.1. Window-Based ML-PDA Algorithm

The window-based ML-PDA algorithm is developed in a way to use in real-time applications; to compute the track estimate, a subset of theNw most recent data frames is used [22]. When a new frame is received with data, the ML-PDA algorithm is recurred, as it adds the new data frame; the oldest data frame is removed from the data set, which creates a sliding window for localization and tracking update.The existing work requires a large number of evaluations and computations to achieve results where the employment of GA is not able to find the global maximum with probability 1 of random neutral function. It is challenging for existing work to limit the essential population size in a particular problem, whereas the proposed algorithm requires no convergence and less computation. Some of the productive work regarding the multitarget localization and object recognition algorithms are experimented using different distributed algorithms, and some of them are introduced for tracking of vehicles along with other items of interest [23–26].


## 3. Proposed Multitarget Localization and Tracking

In conventional passive localization and tracking, localization of multiunknown targets is a hard problem. Unlike in single-target localization, sensors receive multiple measurements that depend on the number of targets in the specific region, which causes a problem for the receiver to associate measurements to the specific targets.Figure1 shows the arrangement of three sensors along with three targets in a surveillance region. Localization of multiple targets is complex due to the data association ambiguity; i.e., there is no information of which TDOA/FDOA measurement is associated with the specific target [27]. The more complex problem occurs when the measurements from the target are not received by the sensor, and there might be few measurements that are considered false. Such problems exist in a real scenario [17]. Receiving multiple measurements also creates ghost targets which become more challenging for the ghost targets in the surveillance region to be eliminated [28]. To solve this issue, an algorithm is proposed to address the data association ambiguity by using the maximum likelihood of the measurements, which is further processed to localize the multiple targets using the least number of sensors. Maximum likelihood estimation (MLE) is extensively used for a single target for minimizing the estimation problem [29]. Multiple grids are created considering the complexity of the multiple sensors, whereas the algorithm is not complex as it is not using repeated steps for convergence or any biological evolutions of a genetic algorithm [19].Figure 1
Multitarget scenario with three sensors and targets in a surveillance region.Consider the simplicity of this algorithm that is solving the fusion of measurements. Moreover, it can accurately localize the targets using a computed likelihood for all sensors. It has only one parameter grid and passes the results for multitarget estimation. Our proposed algorithm confirms the unknown number of targets that can be localized correctly when the number of false alarms is low and the high probability of detection.


### 3.1. Main Steps Summary

The proposed algorithm is divided into different steps to understand the functionality of this work in a significant way. Consider theN number of sensors SN positioned xN,yN in the 2-dimensional surveillance region that received M number of measurements from an unknown number of targets UM positioned xM,yM in 2 dimensions.


#### 3.1.1. First Step

This step involves the receiving of measurements and processing for the next step. In addition, each sensor receivesM measurements at a time, which is equal to N×M measurements, having MN possible combinations. Each possible combination is responsible for generating a candidate. Measurements can be written in vector form for each sensor.
(1)SN=m1N,m2N,m3N,⋯,mMN.Here,mMN=m~MN+nM, where m~MN=dM−dN.According to equation (1), m~MN is the Mth range difference measurement received by sensor N. dN is the range of the target at sensor N. Assume that the received measurements contain the measurement noise which is considered to be independent zero-mean Gaussian random noise nM~N0,σ2. To deal with the measurement association to the targets, it is essential to create the combination of all the measurements received on all the sensors and obtain the candidates from each combination as visualized in Figure 2, which can be written as
(2)Ck=mM1,mM3,⋯,mMN1×N.Figure 2
Graphical representation ofM measurements received at N sensors and possible combinations.Ck is the set of measurements that are associated with the kth candidate.Considering all the combinations, the possible candidate can be given by(3)Possiblecandidates=k=MN.


#### 3.1.2. Second Step

Sensors are placed in a surveillance region; a grid of measurements is created for each sensor before scanning so that it can monitor the region for targets. The grid depends on the defined surveillance region. To reduce the computation, a350km×350km surveillance region is considered. This means each grid for a specific sensor is 350km×350km. In an example considering 3 sensors, each is having a grid of measurements between different points that are shown in Figure 3.Figure 3
Graphical representation of measurement grids for three sensors.Each grid of the sensor can be written as(4)SGi=m0,0im1,0i⋯m350,0im0,1im1,1i⋯m350,1i⋮⋮⋱⋮m0,350im1,350i⋯m350,350i,where SGi is a grid of measurements for ith sensor of the surveillance region and mx,yi is the measurement at ith sensor received from the x,y location in the region.


#### 3.1.3. Third Step

It is considered that each sensor receives only one measurement maximum produced by each target at a particular time instant under consideration. For every measurement received at the sensor, the likelihood is measured with respect to the specific sensor’s grid created in step 2.The individual likelihood at sensori as a result of associating the Mth measurement with location X. The likelihood function is given by
(5)LiXk=12πσ2exp−12σ2Ck−SGi′Ck−SGi,where LiXk is the likelihood of the kth measurement set at the ith sensor in (5). If the likelihood of the received measurement is more than the threshold, this likelihood result is shortlisted along with all the associated measurements of different sensors for each grid. To associate and localize the presence of the target, it is assumed that the maximum likelihood for all sensors is greater than the probability ξ, that is,
(6)MLS1&MLS2&⋯&MLSN>ξ.Here, the valueξ is critical in precising the candidates to be shortlisted in the next steps; its value results in a narrow and wide likelihood curve. MLSN is the maximum likelihood of Nth sensor. Shortlisted measurements are forwarded to the next step.


#### 3.1.4. Fourth Step

The shortlisted likelihood measurements are used to estimate the positionsXest for each measurement using a weighted least square (WLS). Meanwhile, for each candidate measurement Ck, using the WLS candidate position Xc is estimated, where SN is the positions of the sensors in 2-D xN,yN; UM is the position of the targets in 2-D xM,yM; m~MN is the Mth measurement received by sensor N without noise; nM is the zero-mean Gaussian random noise of Mth measurement nM~N0,σ2; Ck is the set of measurements belonging to the kth candidate; k=MN, where N is the number of sensors and M is the number of targets; SGi is the grid of measurements of surveillance area at ith sensor; mx,yi=ux,y−Si; mx,yi is the measurement value in between the ith sensor and (x,y) location of the monitoring area; ux,y is the instantaneous value for the grid at (x,y) in 2-D; LiXk is the likelihood of the kth measurement at ith sensor; MLSi is maximum likelihood of the ith sensor; XC is the position in (x,y) of candidate measurements Ck using WLS; and Xest is the position in (x,y) of shortlisted measurements by ML using WLS.


#### 3.1.5. Fifth Step

The generated position of candidatesXC and the shortlisted likelihood measurements Xest in step 4 are compared in a way that, for each candidate, the root mean square (RMS) value is calculated to each of the shortlisted likelihood measurements and search for the minimum value of RMS, if the minimum value is found as per the threshold β set for accuracy.
(7)RMS=XC−Xest<β.In equation (7), if for specific XC the above condition satisfies, then it is shortlisted and Xest is associated with the XC candidate by assigning a tag number, which helps to count the number and increment the index number of XC and forwarded to step 6.


#### 3.1.6. Sixth Step

Shortlisted results can have duplicate measurements that produce the same result. These duplicate measurements are removed, which improves the computation and takes an average of all the shortlisted results associated withXC, and the process is repeated according to the number of targets localized.
(8)Tj=1L∑i=1LXestji.Tj is the jth target localized, L is the count of shortlisted associated measurements, and Xestji is the shortlisted measurements associated with a jth target.


### 3.2. Algorithm Procedure

The algorithm steps are explained in the last section, and its procedure is explained in Table3. The proposed algorithm reduces the computation to localize and track the multiple targets and also reduces the complexity as compared to the existing work whereas the result produced using the proposed algorithm is effective and efficient as shown in the simulation section.Table 3
Proposed algorithm procedure.
StepAction1Obtain the possible candidates using the received measurements2Generate the grids for each sensor of the surveillance region3Shortlist the maximum-likelihood of the measurements4Using WLS to estimate the positions of the candidate and shortlisted measurements5Find the nearest measurement to candidates for potential targets6Remove duplicates, and average all estimates with the same tags7Repeat steps 3 to 6 for tracking for static sensors, otherwise repeat steps 2 to 6


## 3.1. Main Steps Summary

The proposed algorithm is divided into different steps to understand the functionality of this work in a significant way. Consider theN number of sensors SN positioned xN,yN in the 2-dimensional surveillance region that received M number of measurements from an unknown number of targets UM positioned xM,yM in 2 dimensions.


### 3.1.1. First Step

This step involves the receiving of measurements and processing for the next step. In addition, each sensor receivesM measurements at a time, which is equal to N×M measurements, having MN possible combinations. Each possible combination is responsible for generating a candidate. Measurements can be written in vector form for each sensor.
(1)SN=m1N,m2N,m3N,⋯,mMN.Here,mMN=m~MN+nM, where m~MN=dM−dN.According to equation (1), m~MN is the Mth range difference measurement received by sensor N. dN is the range of the target at sensor N. Assume that the received measurements contain the measurement noise which is considered to be independent zero-mean Gaussian random noise nM~N0,σ2. To deal with the measurement association to the targets, it is essential to create the combination of all the measurements received on all the sensors and obtain the candidates from each combination as visualized in Figure 2, which can be written as
(2)Ck=mM1,mM3,⋯,mMN1×N.Figure 2
Graphical representation ofM measurements received at N sensors and possible combinations.Ck is the set of measurements that are associated with the kth candidate.Considering all the combinations, the possible candidate can be given by(3)Possiblecandidates=k=MN.


### 3.1.2. Second Step

Sensors are placed in a surveillance region; a grid of measurements is created for each sensor before scanning so that it can monitor the region for targets. The grid depends on the defined surveillance region. To reduce the computation, a350km×350km surveillance region is considered. This means each grid for a specific sensor is 350km×350km. In an example considering 3 sensors, each is having a grid of measurements between different points that are shown in Figure 3.Figure 3
Graphical representation of measurement grids for three sensors.Each grid of the sensor can be written as(4)SGi=m0,0im1,0i⋯m350,0im0,1im1,1i⋯m350,1i⋮⋮⋱⋮m0,350im1,350i⋯m350,350i,where SGi is a grid of measurements for ith sensor of the surveillance region and mx,yi is the measurement at ith sensor received from the x,y location in the region.


### 3.1.3. Third Step

It is considered that each sensor receives only one measurement maximum produced by each target at a particular time instant under consideration. For every measurement received at the sensor, the likelihood is measured with respect to the specific sensor’s grid created in step 2.The individual likelihood at sensori as a result of associating the Mth measurement with location X. The likelihood function is given by
(5)LiXk=12πσ2exp−12σ2Ck−SGi′Ck−SGi,where LiXk is the likelihood of the kth measurement set at the ith sensor in (5). If the likelihood of the received measurement is more than the threshold, this likelihood result is shortlisted along with all the associated measurements of different sensors for each grid. To associate and localize the presence of the target, it is assumed that the maximum likelihood for all sensors is greater than the probability ξ, that is,
(6)MLS1&MLS2&⋯&MLSN>ξ.Here, the valueξ is critical in precising the candidates to be shortlisted in the next steps; its value results in a narrow and wide likelihood curve. MLSN is the maximum likelihood of Nth sensor. Shortlisted measurements are forwarded to the next step.


### 3.1.4. Fourth Step

The shortlisted likelihood measurements are used to estimate the positionsXest for each measurement using a weighted least square (WLS). Meanwhile, for each candidate measurement Ck, using the WLS candidate position Xc is estimated, where SN is the positions of the sensors in 2-D xN,yN; UM is the position of the targets in 2-D xM,yM; m~MN is the Mth measurement received by sensor N without noise; nM is the zero-mean Gaussian random noise of Mth measurement nM~N0,σ2; Ck is the set of measurements belonging to the kth candidate; k=MN, where N is the number of sensors and M is the number of targets; SGi is the grid of measurements of surveillance area at ith sensor; mx,yi=ux,y−Si; mx,yi is the measurement value in between the ith sensor and (x,y) location of the monitoring area; ux,y is the instantaneous value for the grid at (x,y) in 2-D; LiXk is the likelihood of the kth measurement at ith sensor; MLSi is maximum likelihood of the ith sensor; XC is the position in (x,y) of candidate measurements Ck using WLS; and Xest is the position in (x,y) of shortlisted measurements by ML using WLS.


### 3.1.5. Fifth Step

The generated position of candidatesXC and the shortlisted likelihood measurements Xest in step 4 are compared in a way that, for each candidate, the root mean square (RMS) value is calculated to each of the shortlisted likelihood measurements and search for the minimum value of RMS, if the minimum value is found as per the threshold β set for accuracy.
(7)RMS=XC−Xest<β.In equation (7), if for specific XC the above condition satisfies, then it is shortlisted and Xest is associated with the XC candidate by assigning a tag number, which helps to count the number and increment the index number of XC and forwarded to step 6.


### 3.1.6. Sixth Step

Shortlisted results can have duplicate measurements that produce the same result. These duplicate measurements are removed, which improves the computation and takes an average of all the shortlisted results associated withXC, and the process is repeated according to the number of targets localized.
(8)Tj=1L∑i=1LXestji.Tj is the jth target localized, L is the count of shortlisted associated measurements, and Xestji is the shortlisted measurements associated with a jth target.


## 3.1.1. First Step

This step involves the receiving of measurements and processing for the next step. In addition, each sensor receivesM measurements at a time, which is equal to N×M measurements, having MN possible combinations. Each possible combination is responsible for generating a candidate. Measurements can be written in vector form for each sensor.
(1)SN=m1N,m2N,m3N,⋯,mMN.Here,mMN=m~MN+nM, where m~MN=dM−dN.According to equation (1), m~MN is the Mth range difference measurement received by sensor N. dN is the range of the target at sensor N. Assume that the received measurements contain the measurement noise which is considered to be independent zero-mean Gaussian random noise nM~N0,σ2. To deal with the measurement association to the targets, it is essential to create the combination of all the measurements received on all the sensors and obtain the candidates from each combination as visualized in Figure 2, which can be written as
(2)Ck=mM1,mM3,⋯,mMN1×N.Figure 2
Graphical representation ofM measurements received at N sensors and possible combinations.Ck is the set of measurements that are associated with the kth candidate.Considering all the combinations, the possible candidate can be given by(3)Possiblecandidates=k=MN.


## 3.1.2. Second Step

Sensors are placed in a surveillance region; a grid of measurements is created for each sensor before scanning so that it can monitor the region for targets. The grid depends on the defined surveillance region. To reduce the computation, a350km×350km surveillance region is considered. This means each grid for a specific sensor is 350km×350km. In an example considering 3 sensors, each is having a grid of measurements between different points that are shown in Figure 3.Figure 3
Graphical representation of measurement grids for three sensors.Each grid of the sensor can be written as(4)SGi=m0,0im1,0i⋯m350,0im0,1im1,1i⋯m350,1i⋮⋮⋱⋮m0,350im1,350i⋯m350,350i,where SGi is a grid of measurements for ith sensor of the surveillance region and mx,yi is the measurement at ith sensor received from the x,y location in the region.


## 3.1.3. Third Step

It is considered that each sensor receives only one measurement maximum produced by each target at a particular time instant under consideration. For every measurement received at the sensor, the likelihood is measured with respect to the specific sensor’s grid created in step 2.The individual likelihood at sensori as a result of associating the Mth measurement with location X. The likelihood function is given by
(5)LiXk=12πσ2exp−12σ2Ck−SGi′Ck−SGi,where LiXk is the likelihood of the kth measurement set at the ith sensor in (5). If the likelihood of the received measurement is more than the threshold, this likelihood result is shortlisted along with all the associated measurements of different sensors for each grid. To associate and localize the presence of the target, it is assumed that the maximum likelihood for all sensors is greater than the probability ξ, that is,
(6)MLS1&MLS2&⋯&MLSN>ξ.Here, the valueξ is critical in precising the candidates to be shortlisted in the next steps; its value results in a narrow and wide likelihood curve. MLSN is the maximum likelihood of Nth sensor. Shortlisted measurements are forwarded to the next step.


## 3.1.4. Fourth Step

The shortlisted likelihood measurements are used to estimate the positionsXest for each measurement using a weighted least square (WLS). Meanwhile, for each candidate measurement Ck, using the WLS candidate position Xc is estimated, where SN is the positions of the sensors in 2-D xN,yN; UM is the position of the targets in 2-D xM,yM; m~MN is the Mth measurement received by sensor N without noise; nM is the zero-mean Gaussian random noise of Mth measurement nM~N0,σ2; Ck is the set of measurements belonging to the kth candidate; k=MN, where N is the number of sensors and M is the number of targets; SGi is the grid of measurements of surveillance area at ith sensor; mx,yi=ux,y−Si; mx,yi is the measurement value in between the ith sensor and (x,y) location of the monitoring area; ux,y is the instantaneous value for the grid at (x,y) in 2-D; LiXk is the likelihood of the kth measurement at ith sensor; MLSi is maximum likelihood of the ith sensor; XC is the position in (x,y) of candidate measurements Ck using WLS; and Xest is the position in (x,y) of shortlisted measurements by ML using WLS.


## 3.1.5. Fifth Step

The generated position of candidatesXC and the shortlisted likelihood measurements Xest in step 4 are compared in a way that, for each candidate, the root mean square (RMS) value is calculated to each of the shortlisted likelihood measurements and search for the minimum value of RMS, if the minimum value is found as per the threshold β set for accuracy.
(7)RMS=XC−Xest<β.In equation (7), if for specific XC the above condition satisfies, then it is shortlisted and Xest is associated with the XC candidate by assigning a tag number, which helps to count the number and increment the index number of XC and forwarded to step 6.


## 3.1.6. Sixth Step

Shortlisted results can have duplicate measurements that produce the same result. These duplicate measurements are removed, which improves the computation and takes an average of all the shortlisted results associated withXC, and the process is repeated according to the number of targets localized.
(8)Tj=1L∑i=1LXestji.Tj is the jth target localized, L is the count of shortlisted associated measurements, and Xestji is the shortlisted measurements associated with a jth target.


## 3.2. Algorithm Procedure

The algorithm steps are explained in the last section, and its procedure is explained in Table3. The proposed algorithm reduces the computation to localize and track the multiple targets and also reduces the complexity as compared to the existing work whereas the result produced using the proposed algorithm is effective and efficient as shown in the simulation section.Table 3
Proposed algorithm procedure.
StepAction1Obtain the possible candidates using the received measurements2Generate the grids for each sensor of the surveillance region3Shortlist the maximum-likelihood of the measurements4Using WLS to estimate the positions of the candidate and shortlisted measurements5Find the nearest measurement to candidates for potential targets6Remove duplicates, and average all estimates with the same tags7Repeat steps 3 to 6 for tracking for static sensors, otherwise repeat steps 2 to 6


## 4. Simulations

The flowchart of the proposed localization and tracking scenario with details is described in Figure4. To better understand the algorithm, simulation is performed in MATLAB to explain the methodology and compare it with existing methods. For simulation, three sensors and six targets were considered in 2-dimensional space. We consider two targets and repeat this step for three to six targets. The surveillance region is defined to be 350 km by 350 km considering far-field targets. Tables 4 and 5 show the positions and velocities of the sensors and targets, respectively, where the sensors are considered to be static, and both targets are moving with constant speed.Figure 4
Flow diagram of proposed algorithm for multitarget localization and tracking.Table 4
Multitarget algorithm—sensor positions and velocity.
SensorsPositionVelocityX (km)Y (km)Ẋ (m/s)Ẏ (m/s)Sensor 17520000Sensor 2502500Sensor 311210000Table 5
Multitarget algorithm—target positions and velocity.
TargetPositionVelocityX (km)Y (km)Ẋ (m/s)Ẏ (m/s)Target 1300190-20-15Target 2200300-20-15Target 3250150-20-15Target 4300300-20-15Target 530050-20-15Target 6250250-20-15The three sensors and two targets can generate a maximum of eight candidates that can be the potential targets. Using equation (3), it is explained in Figure 5 with the green points:
(9)k=MN=23=8, as k is the number of possible candidates. So, at this point, eight measurements are received by all the sensors and grids of the surveillance region are created and the further likelihood of the measurement is calculated.Figure 5
Candidate positions for two targets.The computation increases as the value increases which depends on the number of targets and sensors. Figure6 shows the curves for all the individual likelihood without any condition of threshold comparison. In Figure 6, the blue box represents the reference sensor. The past algorithm used the grid with different dimensions of the parameter, whereas our algorithm can localize using only a single dimension of parameter measurement. A multidimensional parameter grid can produce more accurate results as it has more information to process, next. Figure 7 shows the result of the localized target areas in the surveillance region. The localized areas can have an additional area other than the actual target due to the measurement noise in the received measurements.Figure 6
Likelihood curves of received measurements.Figure 7
Shortlisted likelihood measurements (red).Figure8 shows the results of the maximum likelihood of the measurements in red, these are the shortlisted measurements, and the rest of the measurements which do not satisfy the condition are discarded. Furthermore, the accuracy of the localization for the unknown targets depends on the thresholds, which are adjusted by performing multiple runs and compare the results to get more accuracy. β is set to 200 meters, and ξ is equal to 0.5. Both can be varied depending on the results and monitoring environment.Figure 8
Localization of two targets using TDOA/FDOA.Figure9 shows the localization of two targets, and Figure 10 is the zoomed plots, in which the algorithm is not only able to localize the targets but also can rectify the ghost created in the maximum likelihood process.Figure 9
Two localized targets (dense black) with candidates (green).Figure 10
Zoomed at one target estimates (black asterisk).If the sensors are not moving, the measurement grid will not be regenerated. On the other hand, if sensors are in motion, the sensor’s measurement grid has to regenerate continuously to estimate the high position accuracy of the targets. The increase in the received measurements indicates an increased number of targets, which causes an increase in the possible candidates also. Figure11 shows the localization of three targets with a different number of possible candidates in each plot, and Figure 12 shows the localization of five targets. Once the locations are localized, the proposed algorithm can be used in a simulation to track the targets which are successfully tested using two targets.Figure 11
Localization using the algorithm for three targets.Figure 12
Localization using the algorithm for five targets.If the sensors are not moving, the measurement grid will not be regenerated. On the other hand, if sensors are in motion, the sensor’s measurement grid has to regenerate continuously to estimate the high position accuracy of the targets. The increase in the received measurements indicates an increased number of targets, which causes an increase in the possible candidates also. Figure11 shows the localization of three targets with a different number of possible candidates in each plot, and Figure 12 shows the localization of five targets. Once the locations are localized, the proposed algorithm can be used in a simulation to track the targets which are successfully tested using two targets.Once the algorithm runs and localizes the targets, the procedure is repeated for newly received measurements on different sensors and localize the targets again and keep track of old and new shortlisted measurements which provides the complete track of targets. Figures13 and 14 show the results in which their updated positions are tracked using maximum likelihood, where Figure 13 shows the scenario of intersecting two targets and Figure 14 shows the simple scenario of two targets moving in the straight path.Figure 13
Tracking of two moving targets intersecting at a point.Figure 14
Tracking of two moving targets in parallel.The proposed algorithm does not have any window size, as it gives a different approach to solve the multitarget localization problem. To compare the proposed algorithm’s performance to other algorithms, i.e., multipass grid search and directed subspace search, we consider the results from [26] and calculate the mean runtime of the simulation of the single estimate for window size Nw from 5 to 10. The results show in Figure 15 [26] that the proposed algorithm (red curve) performed better than multipass grid search overall but for directed subspace search, the proposed algorithm results better after Nw=8. Directed subspace is ineffective due to a search in a specific area. Further, in Table 6, the simulation shows that the runtime of the proposed algorithm increased very slightly and gradually.Figure 15
Single estimate mean runtime with one standard deviation in 2-D measurement space.Table 6
Runtime for different window sizes of the proposed algorithm.
Window sizeNw5678910Algorithm runtime (s)5.235.475.65.816.066.26In a single scan, this algorithm as compared to other existing work can localize and track the unknown number of targets without repeated steps for convergence or biological evolution. Hence, the proposed algorithm is effective and simple to implement as compared to the existing work which reduces the computation.


## 5. Concluding Remarks

This research proposed an algorithm based on TDOA/FDOA and optimization of the shortlisted measurement. This proposed technique provides localization and tracking of multitargets using the maximum likelihood of the measurement and further addresses the data association problem of the received measurements and targets.This algorithm can localize the unknown number of targets having the complexity of multiple sensors with multiple grids. The proposed algorithm reduces complexity as it does not use repeated steps for convergence and any biological evolutions. A single scan computes the likelihood for all sensors using only one parameter grid and passes the results for multitarget estimation.It also reduces the localization of the ghost target by eliminating the data fusion issue. Therefore, this method will be the best-suited candidate when considering the combinations of the measurements from different sensors. In the future, an improvement can be made in the algorithm by considering multiparameter approach and including the maximum likelihood of those measurements to increase the position accuracy. Also, this algorithm can work in meters for considerably distant fields. Other optimization models can be combined to authenticate the algorithm’s efficiency and effectiveness.



---

*Source: 6567346-2021-11-30.xml*