Accurate target localization is a cornerstone technology underpinning a myriad of applications, including navigation systems, augmented reality, integrated sensing and communication (ISAC), and the Internet of Things (IoT) [1]- [7]. The ability to precisely determine the position of targets in various environments is essential for enhancing the functionality, safety, and efficiency of these systems. Extensive research has been conducted on received signal strength (RSS), angle of arrival (AOA), time of arrival (TOA), and time difference of arrival (TDOA) based localization techniques. Among them, those leveraging signal propagation delays have garnered significant attention due to their high precision and reliability, particularly when combined with wide-band probing signals [3], [6], [7].
Delay-based localization problems can be broadly classified into active and passive categories based on the target attribution. Active target localization involves targets that actively emit signals, typically in the form of mobile wireless devices. These active emitters are easily detectable by surrounding sensors, facilitating straightforward localization [4], [8]- [15]. As active localization techniques require the participation of devices (targets), some works considered the cooperation among targets/agents so that the localization performance can be more robust [16]- [18]. In contrast, passive target localization involves locating silent targets that do not transmit signals. This is achieved by using external signals that illuminate targets, which then reflect these signals back to the sensors [19]- [27]. Passive localization is more vulnerable to multipath effects, especially when there exist multiple targets. In multipath environments, signals can travel along multiple paths due to reflections, blockage, or scattering by environmental obstacles. Unlike active targets, which can emit signals with unique radio frequency signatures that help receivers distinguish among multiple targets, passive targets always have identical signal signatures. Consequently, the multipath effect introduces severe challenges in signal interpretation, including but not limited to the inference of the unknown number of multiple targets, the identification between line-of-sight (LOS) and non-line-of-sight (NLOS) measurements, and the measurement-to-target association (MTA) problem [3]. These limitations highlight the need for more robust and scalable solutions capable of handling the intricacies of passive multitarget localization in dynamic and obstructed environments.
Mitigating the adverse effects of multipath propagation on localization remains a critical challenge in wireless communication and sensing systems. The problem was addressed in [10], [12], [14], which employ active signal transmission from targets and rely on heterogeneous measurements (e.g., TOA and RSS). In [28], [29], the target extracts range information from broadcasts by anchor nodes for self-localization. As such, these techniques do not apply to passive localization. Recent years have witnessed a surge of interest in datadriven learning-based localization in NLOS environments. Approaches include the use of convolutional neural networks [30], [31] and semi-supervised learning to directly estimate and compensate for UWB ranging errors [32]. Additionally, graph neural networks have also been explored for cooperative localization [33]. A common thread in these methods is their reliance on large labeled datasets for supervised or semsupervised training. While powerful, this dependency limits their adaptability and requires costly recalibration for new deployments.
In our previous work [21], we introduced a type-based clustering algorithm (TCA) for locating multiple passive tar-gets in multipath environments. TCA leverages the geometric representation that each LOS/NLOS measurement represents a circle centered on the corresponding sensor. Intersection points of circles from different sensors are categorized into multiple types, forming a unique clustering pattern that helps distinguish LOS from NLOS measurements. TCA then employs a two-stage search process to assign measurements to corresponding targets based on the clustering pattern. However, for easy exposition, TCA was introduced under the following simplifying conditions: (i) every target-sensor pair has a LOS path (i.e., no blockage occurs), and (ii) the number of targets is known in advance. A solution to the problem involving an unknown target number in TCA was proposed in [34]. Nevertheless, that solution is also based on the assumption that LOS measurements from all sensors are available.
Passive target location with blockage or missing LOS measurements was investigated in [24], [27]. These works considered a setup with multiple transmitters (TXs) and multiple receivers (RXs), which form a distributed radar system. The authors proposed an iterative likelihood-based screening method, which, along with a user-selected threshold, was utilized to determine which range measurements are LOS. The method sequentially examines each range measurement until all TX-RX measurements are exhausted. While this approach can tolerate missing LOS measurements by adjusting a tolerance parameter, it often produces clustered estimates for each target. Moreover, the performance is sensitive to the choice of the likelihood threshold. Specifically, to reduce the probability of misclassifying a LOS measurement as a NLOS measurement, a high threshold is desired, which however increases the probability of false alarm and also the computational overhead.
This paper extends the work in [21] and proposes a new algorithm for LOS measurement identification without the limitations of TCA. To cope with sensor blockage, we classify targets into different levels. A level-l target is blocked from l out of the total N sensors. Clearly, a level-0 target can be directly identified by the original TCA. For a level-l target with l ≥ 0, since there exists one and only one subset of N -l sensors that have unblocked LOS observations of the target, we can examine each size-(N -l) subset of the sensors one by one, and apply TCA to find the subset with unblocked measurements. Based on this idea, we propose a hierarchical TCA, referred to as HiTCA, which employs a multi-level search strategy, with each designed to identify one specific level of targets. These searches can be performed in parallel across various levels, which enables the algorithm to efficiently identify targets with different numbers of LOS path blockages. Moreover, to address the uncertainty of the target number, the proposed approach extends the original TCA by leveraging inherent characteristics to classify and filter search results. Specifically, there is a clear distinction between clusters of intersection points associated with targets and those with nontargets. This marked difference in the intersection pattern manifests as an "elbow", which we exploit to provide a reliable estimate of the target count.
We validate the effectiveness of the proposed method through extensive numerical simulations, comparing its per- formance with existing peer techniques. Our results show that the new approach is adaptable to diverse and unpredictable operational settings, delivering reliable localization accuracy for multiple passive targets in the presence of LOS blockages. Compared to the learning/model based approches, our proposed HiTCA algorithm circumvents the fundamental requirement of training data or complex models. By leveraging geometric principles in a completely unsupervised manner, it offers a robust solution for multi-target localization and blockage mitigation, providing a practical alternative for scenarios where extensive training data collection is infeasible. The remainder of this paper is organized as follows: Section II outlines the system model underlying our proposed method. Section III details the geometric clustering scheme and the necessary preliminaries. Section IV presents a brief review of the fundamental concepts and limitations of the previous work. Section V introduced details of the proposed algorithm. Section VI presents the simulation results and advantages of our approach. Finally, Section VII concludes the paper with a summary of contributions.
Consider the problem of locating multiple targets in a twodimensional surveillance area. Assume there are K targets with unknown coordinates p k , k = 1, . . . , K, which need to be located. Each target is passive, meaning it does not emit any RF signal. N active sensors are deployed in the area with coordinates a n , n = 1, . . . , N . Each sensor transmits a unique probing signal and uses the echoes to infer the target locations. Aside from the targets, the environment also contains J scatterers at unknown locations s j , j = 1, . . . , J , which are of no interest but may interfere with the sensor measurements of the targets. Specifically, by cross-correlating the echo with the transmitted signal [35], each sensor can measure the round-trip time delays of target echoes via lineof-sight (LOS) propagation paths as well as non-line-of-sight (NLOS) paths due to the scatterers (see Fig. 1). We assume that the scatterers are fixed and part of the environment, such that direct echoes from the scatterers can be removed from the sensor observations through an environmental calibration step. Once the targets enter the environment, they will interact with the scatterers. Such interactions will lead to additional echoes, which are accounted for as NLOS target signals. Therefore, we only need to consider LOS and NLOS sensor measurements associated with the targets.
It is customary to convert the delays into range measurements. Let r n,k denote the LOS range measurement of sensor n of target k, which can be expressed as
where τ n,k denotes the corresponding delay measurement, c the speed of light, and ε n,k the measurement noise. Similarly, the NLOS range measurement obtained by sensor n of target k via scatterer j can be expressed as
(2) Although the method proposed in this work does not rely on a specific noise distribution, for analysis, we assume that the measurement noise follows a normal distribution with zero mean and variance σ 2 , i.e., ε ∼ N (0, σ 2 ). Moreover, target echoes that pass through more than one scatterer are neglected, as their signal strength is significantly weakened by multiple reflections.
Given a mixed set of LOS and NLOS measurements for all targets as described in (1) and 2, a sensor alone can neither distinguish if a measurement is LOS or NLOS, nor can it determine which target contributes to that measurement. The problem of interest is to leverage sensor collaboration to label each measurement as LOS or NLOS and, moreover, separate the LOS measurements into distinct groups associated with different targets. Without prior knowledge of the scatterers, NLOS measurements are in general not useful for locating the targets [3], [7], [36].
In our previous work [21], we introduced a type-based clustering algorithm (TCA) to identify LOS measurements under two conditions: (a) the number of targets K is known; and (b) no LOS measurement is missing, i.e., each sensor's observations contain a LOS range measurement of each target. In practical scenarios, however, the exact number of targets is often unknown. Additionally, the LOS range measurements, which are essential for accurate localization, cannot always be guaranteed due to obstacles obstructing the direct path between the sensor and the target. To address the above limitations, this paper aims to develop a more robust LOS path identification algorithm to cope with more challenging scenarios where the number K of targets is unknown and some LOS measurements are missing. In particular, it is unknown which sensors lack LOS measurements and which targets are associated with the missing data. Finally, it is worth noting that J, the number of scatterers, is assumed unknown in this work and also in [21]. Illustration of LOS measurements (circles in solid lines) and NLOS measurements (circles in dashed lines), centered at three sensors (the triangles). The intersection points of LOS circles (red points) are clustered near the target and form a TIP set. On the contrary, the set of points 4, 6, and 7 is an example of a non-TIP set.
Based on the signal model in Section II, each range measurement can be viewed as a circle centered at the corresponding sensor, with the radius equal to the measured range. Depending on the type of measurement, a circle may be referred to as a LOS circle or a NLOS circle, as shown in Fig. 2.
For a multi-sensor system, the LOS circles centered at different sensors intersect precisely at the target's location when the range measurements are noise-free. With noise, the intersections of LOS circles are clustered near the target, e.g., points 1, 2, and 3 in Fig. 2. Such a set of intersection points produced by LOS circles associated with the same target is a target intersection point (TIP) set. Naturally, there is a one-to-one correspondence between TIP sets and targets. On the contrary, other intersections (non-TIPs) such as points 4 to 8 in Fig. 2, created by either NLOS circles only or between LOS and NLOS circles, do not share this pattern. Our proposed algorithm aims to identify the TIP sets associated with the targets in the surveillance area. Since the process relies on intersection points of circles, a closed-form solution for computing these points is included in Appendix A for easy reference.
The distribution of intersection points plays an important role in our proposed algorithm. Here we define a metric, spread, to quantify how close the intersection points of a point set are distributed. Let U m denote a set of intersection points, where m is the cardinality of the set, i.e., m = |U m |. The spread of the point set U m , denoted by s(U m ), is the mean of the squared distances between the points and their geometric center, namely
where x i represents the coordinates of the i-th point in U m , while x is the mean of all points' coordinates, i.e., the geometric center of the point set. If a point set has a large spread, its points are dispersed. For the example of Fig. 2, the spread of the TIP set is significantly smaller than that of other non-TIP sets.
Our algorithm examines all sets of intersection points in the plane and selects the ones that meet certain conditions of the TIP sets (detailed in Section V). Among the conditions, a critical one is related to the spread, which can be employed to eliminate unlikely candidates, i.e., point sets with a large spread, to reduce the search complexity. It is clear from (3) that s(U m q ) for a specific point set U m is bounded by the largest term ∥x i -x∥ 2 among all points in the the point set U m . For a TIP set, its geometric center x converges to the true target location p as m increases. It is therefore meaningful to use the maximum deviation from p, i.e., max i ∥x i -p∥ 2 , as a threshold to eliminate point sets with a spread larger than this threshold. Since the intersection point x i is random due to measurement noise, we can use the maximum average deviation max i E(∥x i -p∥ 2 ) as the threshold instead. In Appendix B, we show that for a given pair of sensors, the average deviation max i E(∥x i -p∥ 2 ) peaks when the target lies at the intersection of the surveillance area's boundary and the line passing through the two sensors. In particular, we have the following bound:
where D denotes the maximum distance between the midpoint of two sensors and the boundary of the surveillance area, d the distance between the two sensors, and σ 2 the noise variance.
Our proposed algorithm relies on the intersections of LOS circles. However, the presence of noise may cause two LOS circles to cease to intersect. This phenomenon is referred to as point loss. To remedy this issue, we propose the following point recovery procedure:
1) If a pair of circles associated with two different sensors intersect with each other, no action is needed. 2) If two circles associated with different sensors do not intersect with each other, increase the radius of each circle by κ, leading to a pair of expanded circles. Additionally, create a pair of shrunk circles by decreasing the radius of each circle by κ. 3) Calculate the intersection points (if existing) of the two pairs of extended/shrunk circles. The average of the coordinates of corresponding intersection points is taken as the location of the recovered point, representing the intersection point of the two original circles. A probabilistic analysis in Appendix C shows that point loss is caused by measurement noise and occurs more frequently as the noise level increases. Hence, κ should be selected based on the noise level and is typically set between σ 2 and 2σ, where σ denotes the noise standard deviation. Using the analysis in Appendix C. Table I compares the probability of LOS circles failing to intersect before and after applying the proposed recovery method in a setup with K = 4 targets, where κ = 2σ with σ = 0.5. Both theoretical calculation and
TABLE I COMPARISON OF PROBABILITY OF NON-INTERSETING LOS CIRCLES Target #1 #2 #3 #4 Before point recovery 5.0e-1 4.2e-1 3.7e-1 3.0e-1 After point recovery 2.3e-3 1.3e-3 8.4e-4 4.0e-4
Monte Carlo simulation yield consistent results, demonstrating that the proposed recovery method effectively reduces the likelihood of point loss.
This work builds upon the original TCA algorithm introduced in [21]. Specifically, given the mixture of LOS/NLOS measurements in ( 1) and ( 2) of K targets, TCA identifies the LOS measurements which can be used to locate the targets.
In the following, we first briefly review some key concepts employed by TCA and further elaborate on its limitations.
Each range measurement obtained by sensor a n , n = 1, • • • , N, defines a circle centered at a n . The set of circles centered at the n-th sensor is called a circle set, denoted by C n . An intersection point is produced exclusively by two circles from two different circle sets. The pair of circles creating the intersection point are referred to as its parents. For an intersection point with parents from C n1 and C n2 , the intersection point is labeled as type (n 1 , n 2 ), where n 1 and n 2 range from 1 to N with n 1 ̸ = n 2 , since concentric circles do not intersect. In TCA, individual points are less of a concern compared to the characteristics of a cluster of points. Herein, for a point set U m of cardinality m, the parents of all points in U m form the parent set of U m , denoted by P(U m ).
These concepts lead to the definition of the type set. All intersection points of the same type form a type set T n1,n2 , i.e.,
A straightforward conclusion is that, for a N -sensor network, there are N (N -1)/2 different types.
A fundamental assumption of TCA is that each sensor has LOS measurements for all targets, implying that there is no sensor-target blockage and no missing LOS measurements. Under this assumption, each TIP set, corresponding to a distinct target, consists of exactly N (N -1)/2 intersection points from all N (N -1)/2 types. The parent set of a TIP set represents the LOS measurements associated with the target. We denote the TIP sets by V k for k = 1, . . . , K, which share the following useful properties [21]:
), where U N (N -1)/2 denote any non-TIP set of cardinality N (N -1)/2.
The TCA algorithm was designed to search for the candidate sets of intersection points that satisfy Properties 4.1 to 4.4. Based on Property 4.1, TCA retains only those point sets of N (N -1)/2 points that belong to N (N -1)/2 different types. This also guarantees that each such point set has N different parents, which satisfies Property 4.2. Thus, TCA's performance crucially depends on these structures of TIP sets, i.e., the availability of all LOS measurements. If some LOS paths of a target are blocked by obstacles in the surveillance area, the corresponding sensors will have fewer than N LOS measurements for that target. This will violate Property 4.2, and further lead to the disruption of Property 4.1. In conclusion, the original TCA cannot correctly identify all TIP sets when some LOS measurements are missing.
Another limitation of TCA is the reliance on the prior knowledge of the target number K. Even if all LOS measurements are present and thus TCA can identify candidate point sets that meet Properties 4.1 to 4.3, there are non-TIP sets that also meet these properties. Since points in these non-TIP sets are not clustered and thus have a larger spread, by assuming K is known, TCA applies Property 4.4 and selects the K point sets that have the smallest spread as the final TIP sets. In practice, however, the number of targets present in the scene may not be available in advance.
To address the above limitations, we propose a more robust solution for LOS path identification next.
Before diving into the details, we briefly explain the main idea of the proposed algorithm, termed hierarchical TCA (HiTCA) for brevity. To handle sensor blockage, targets are grouped into distinct levels. Specifically, a target is labeled as a level-l target, l = 0, 1, . . . , L, if l out of the total N sensors are blocked from that target, where L denotes the maximum number of sensors that may be blocked from any target. A sensor that is (or is not) blocked from a target is called an ineffective (or effective) sensor for that target. It is assumed that N ≥ L + 3 so that there are at least 3 effective sensors for each target, which is required to ensure the target can be uniquely located on the plane. Clearly, a level-0 target has no ineffective sensors and thus can be identified by the original TCA. In contrast, a level-l target (l ̸ = 0) cannot be directly identified by TCA due to the presence of l ineffective sensors. However, if supplied with range measurements from only the N l ≜ N -l effective sensors, TCA can also identify a level-l target. The challenge is that we do not know in advance which sensors are effective or ineffective.
To address the above challenge, HiTCA employs a multilevel search strategy, with each designed to identify one specific level of targets. These searches can be performed in parallel across levels. Specifically, the level-l search consists of executing a truncated TCA algorithm (detailed in Algorithm 1) for a total of N N l times, each time using range measurements from a distinct N l -sensor subset of the total N sensors. Among these N N l executions, only one involves N l effective sensors, which is expected to yield candidate TIP sets with a smaller spread than those produced by the other N N l -1 executions, as each of the latter involves some ineffective sensors. These candidate sets with a smaller spread correspond to the TIP sets for the level-l targets. It should be noted that, while this strategy involves enumeration, L can be made relatively small in practice through strategically placing/selecting sensors to avoid those with poor coverages (e.g., sensors located in corners). Consequently, N l is usually close to N , limiting the complexity caused by the enumeration. Although the multi-level search strategy is conceptually simple, several issues need to be addressed. A notable one is that the search process produces many candidate TIP sets with overlapping intersection points or, equivalently, overlapping parent sets (cf. Section IV). To address this, we propose in-level and cross-level deduplication processes to eliminate overlapping sets produced by searches within the same level and across different levels. Additionally, we propose an elbow detection process to select the best TIP candidates when K, the number of targets, is unknown. Fig. 3 depicts the block diagram that provides an overview of the architecture of HiTCA. Next, we discuss the main components in details, followed by a brief discussion on target localization using the TIP sets identified by HiTCA.
As explained earlier, the first step of the level-l search consists of executing the truncated TCA algorithm N N l times, each involving N l unique sensors' range measurements and their corresponding intersection points. The truncated TCA consists of the first part the original TCA [21], which examines the given intersection points and identifies points sets that satisfy Properties 4.1 and 4.2 as candidates for TIP sets. Unlike TCA, which uses the knowledge of K to finalize TIP set selection, truncated TCA defers the task to subsequent stages of the HiTCA algorithm. The detailed steps of the N l -sensor truncated TCA are listed in Algorithm 1.
The candidate sets, produced by the level-l search, all satisfy Properties 4.1 and 4.2, although not all of them are TIP sets. They can be classified into 6 cases, which are illustrated in Fig. 4 with N l = 3. Specifically, Case (i) contains all TIP sets produced by intersections of LOS circles, while Cases (ii)-(v) represent the four possible cases of non-TIP candidate sets , q = 1, • • • , J N l (N l -1)/2 1 Initialization:
12 Stage-2 Search:
13 Rename the remaining type sets T n1,n2 , n 1 ≥ 2, n 2 ≥ 3 as a single-indexed set sequence , contains N l (N l -1)/2 points from N l (N l -1)/2 different types, where q denotes the q-th candidate set from the level-l search. Since the candidate sets corresponding to Cases (ii)-(v) are non-TIP sets, they do not meet Property 4.3, i.e.,
where K l represents the number of category-l targets and V l k the TIP set of a level-l target. Since the TIP set (Case (i)) has the smallest spread, Cases (ii)-(v) can be excluded by comparing their spread. Algorithm 2 performs the elimination by comparing two different candidate sets Algorithm 2: In-Level Deduplication
The remaining set S is renamed as S * . Reorder the sets in S * in ascending spread
that have overlapping parent sets and discarding the one with a larger spread. The comparison and elimination process repeats until all remaining candidate sets meet Property 4.3.
It is noted that the above process cannot distinguish Case (vi) from Case (i), since the former involves no LOS circles and, consequently, its candidate sets do not overlap with Case (i)'s candidate sets. The problem can be addressed by elbow detection discussed next.
To separate Case (vi) from Case (i), we employ Property 4.4, which states that Case (i) candidate sets, i.e., TIP sets, have a smaller spread among all cases. As an illustration, Fig. 5 depicts the average spread of 5 candidate sets in a scenario with 5 sensors and 3 targets under different noise levels σ. These candidate sets, obtained after in-level deduplication, include only TIP sets (indexed 1 to 3) and non-TIP candidate sets in Case (vi) (indexed 4 and 5). It is observed that TIP sets exhibit a smaller spread, whereas Case (vi) candidate sets show a sharp increase in spread, with the transition forming a distinct "elbow."
We next introduce a method to identify the TIP sets via elbow detection, which checks whether the candidate set lies in the "flat" region of the elbow, as illustrated in Fig. 5. If it does, the set is accepted as a TIP set; otherwise, it is rejected. Specifically, suppose M l candidates are obtained after inlevel deduplication of the level-l search. These candidate sets, ordered by increasing spread, are denoted as U * 1 , . . . , U * M l . For the k-th candidate set U * 1 , the spread standard deviation is defined as
where s(U ) denotes the spread of the point set U and µ k denotes the mean of the first k point sets' spread:
If the first k candidate sets are TIP sets, their spreads are expected to be similar, leading to a small ζ k . However, if U * k is a non-TIP set, its large spread will cause ζ k to increase. So by comparing ζ k against a threshold η, the elbow can be detected. As indicated in Fig. 5, the elbow threshold is dependent on the noise level σ. Empirical studies suggest η = c 1 σ + c 2 σ 2 , with the constants set as
The above comparison is performed iteratively, increasing
k is rejected, all remaining candidate sets are automatically rejected. In the special case where M l = 1, the selection criterion is skipped since there are no other candidate sets for comparison.
A step-by-step summary of the above elbow detection method is shown in Algorithm 3. Up to this point, the level-l search is complete.
A level-l search consists of three processing blocks, namely the truncated TCA, in-level deduplication, and elbow detection as described earlier. HiTCA employs L + 1 such searches, for l = 0, . . . , L, which produce a pool of candidate TIP sets. However, this pool contains redundant sets due to overlaps among results from different search levels. This occurs because
the level-l search produces not only the TIP sets of level-l targets, but also subsets of the TIP sets of targets from all lower levels, i.e., from level 0 through l -1. To see this, consider a level-0 target that has already been identified in the level-0 search. By design, the range measurements for this level-0 target are also processed by the level-1 search,foot_0 which picks N -1 out of N sensors by enumeration and, for each combination, tests if the selected sensors are effective (cf. Section V-A). The result is inevitably positive since all N sensors are effective for a level-0 target. As a result, the level-1 search generates N partial TIP sets, each representing a subset of the target's full TIP set already obtained in the level-0 search.
To eliminate the above redundancy, we propose a cross-level deduplication method, detailed in Algorithm 4, which rejects the TIP sets that overlap (in terms of their parent sets) with any lower-level TIP sets.
After cross-level deduplication, the surviving candidate TIP sets undergo an additional screening using the elbow detection method of Section V-D. While this step typically does not alter the result, it helps to remove rare outliers. With all previous methods integrated, the complete HiTCA algorithm is summarized in Algorithm 5.
The outputs of HiTCA are TIP set estimates of all targets. Note that there is a one-to-one correspondence between TIP sets and the targets. Therefore, once TIP set estimates are obtained, the multi-target localization problem is simplified as the localization of individual targets. For a TIP set corresponding to a level-l target p k , its parent set contains (N -l) circles whose radii are regarded as LOS range measurements. Denote Algorithm 4: Cross-Level Deduplication Input: Candidate sets from all search levels { Ṽl q , q = 1, 2, Similar to [21], we employ the range-based least squares (R-LS) estimator [37], which determines the target location by (R-LS) : min
The proposed HiTCA begins by computing circle intersections. Suppose there are N sensors, each having M range measurements. For simplicity, we assume M is constant for each sensor. Each measurement represents either a LOS or NLOS circle. All intersections between circles centered at different sensors must be evaluated, leading to a computational cost of O(N (N -1)M 2 /2), which simples to O(N 2 M 2 ).
We next examine the complexity of HiTCA, which is summarized in Algorithm 5. The algorithm contains two loops, each iteration sequentially executing Algorithms 1 to 3. First, consider the complexity of Algorithm 1, which consists of a Stage-1 search and a Stage-2 search. Stage-1 contains N l -2 iterations, each iteration having a complexity of O(2Q t M 2 t), where Q t denotes the number of candidate sets retained after the t-th iteration. Q t is dependent on the spread threshold and may vary over iterations. For simplicity, we replace it with a constant upperbound Q, which leads to a total complexity
It is easy to see that the complexity of Algorithms 2 and 3 is negligible compared to that of Algorithm 1. Now referring to the listing of Algorithm 5, HiTCA executes Algorithms 1 to 3 for a total of (L + 1) N N l times through its inner and outer loops. So the total complexity is
, which can be simplified as O(QM 2 N L+4 ). With a proper choice of the spread threshold γ, we have Q ≈ K. So the complexity of HiTCA can be expressed as O(KM 2 N L+4 ), which is polynomial in the number of sensors N , the number of measurements M per sensor, and the number of targets.
In this section, experimental results are presented to compare the performance of HiTCA with the original TCA, the sequential clustering algorithm (SCA) [27], and a clairvoyant method, which employs the true LOS measurements for target localization, in various setups and across different noise levels. To better illustrate the localization performance, the methods are also compared with the Cramer-Rao lower bound (CRLB) [7]. All methods included in the comparison are only employed for the identification of LOS measurements, which are fed into the R-LS estimator [37] for target location estimation.
To compare their performance, the first performance metric is the mean squared error (MSE)
where K is the number of true targets, I the number of independent trials, and p(i) k the coordinates of the location estimate of the target at p k in the i-th trial. Note that for both SCA and HiTCA, K is unknown, and these algorithms may over-or under-estimate K. The event where an algorithm produces estimates more than the target number is referred to as an overestimation. In this case, the estimates are grouped based on the nearest distance criterion relative to the K true target locations. Then the geometric center of each group is taken as the final location estimate for that target. On the other hand, the event where the number of estimates after grouping is less than the true target number K is referred to as an underestimation. When underestimation occurs, (9) is no longer meaningful. To address this issue, we employ another performance metric, the probability of underestimation P u , which is defined as the ratio of the number of missed targets (misclassifying LOS measurements as NLOS measurements) and the total target number across all I trials. The lower the probability of underestimation is, the better the algorithm behaves.
The surveillance area is a 400 × 400 square area centered at (0, 0) on the plane. The system has N = 7 sensors uniformly distributed on a circle centered at (0, 0) with a radius of 160. The environment contains J = 2 scatterers located at (200.00, 125.88) T and (-200.00, 162.32) T on the border of the square. K = 3 targets are distributed inside the surveillance area. We consider two different cases when the sensors are free of blockage and, respectively, when any sensors may be blocked from any target with a blockage probability ρ n,k . We assume a target is blocked from at most two sensors, i.e., L = 2, in the simulations. The measurement noises are independent and identically distributed Gaussian random variables with zero mean and variance σ 2 . The spread threshold γ is set according to (4). We set κ = 2σ for point recovery. For the elbow threshold η, we choose c 1 = 3 and c 2 = 1.2. At each noise level σ, 500 independent trials are tested. In the following, four scenarios are considered in comparison:
1) Fixed target locations with no blockage, i.e., ρ n,k = 0.
2) Fixed target locations with partial blockage ρ n,k = 0.1.
3) Random target locations with no blockage ρ n,k = 0. 4) Random target locations with partial blockage ρ n,k = 0.1.
Firstly, Scenario 1 invovles K = 3 targets loat (-110.98 -163.82) T , (117.62, -24.89) T , and (154.07, -17.86) T . Fig. 6 shows that the clairvoyant method, which employs true LOS measurements for localization, achieves the CRLB at all noise levels. The proposed HiTCA and the original TCA (provided with the exact knowledge of K) outperform the SCA and are close to the clairvoyant method except when σ is large. It is seen that HiTCA slightly outperforms TCA at high noise levels, which might appear unexpected since there is no blockage in Scenario 1. The better performance of HiTCA is obtained at a cost of underestimation. Specifically, Fig. 6(b) shows that HiTCA, which needs to estimate K, has a non-negligible probability of underestimation P u at high noise levels. TCA is free of this problem as it uses the true K for clustering. Nonetheless, HiTCA still outperforms SCA in terms of P u at high σ.
Scenario 2 uses the same fixed target positions along with blockage probability ρ n,k = 0.1. It is easy to show that for the considered system with N = 7 sensors, there is about 0.9 N ≈ 48% chance for a target to be a level-0 target, about N 1 × 0.9 (N -1) × 0.1 ≈ 37% chance to be a level-1 target, and about N 2 × 0.9 (N -2) × 0.1 2 ≈ 12% chance to be a level-2 target. Because the original TCA cannot handle partially blocked LOS measurements, it fails in most cases. Fig. 7(a) shows that HiTCA is significantly more accurate than SCA in MSE across all noise levels. Similar to the clairvoyant method, HiTCA achieves the CRLB except at σ = 5 dB. In Fig. 7(b), HiTCA also maintains a substantially lower P u compared to SCA.
Scenario 3 considers a more challenging setup where three targets are randomly distributed within the surveillance area in each trial. As shown in Fig. 8, HiTCA remains reliable, maintaining performance near the clairvoyant method and surpassing SCA in MSE at all noise levels, while retaining a lower P u than SCA.
TABLE II PROBABILITY THAT A TARGET IS NOT LOCATABLE WITH DIFFERENT SCALES OF SENSORS ρ 0.1 0.3 0.5 0.7 N = 3 2.71e -1 6.57e -1 8.75e -1 9.73e -1 N = 5 8.6e -3 1.63e -1 5.0e -1 8.37e -1 N = 7 1.77e -4 2.88e -2 2.27e -1 6.47e -1 N = 9 3.0e -6 4.3e -3 8.9e -2 4.63e -1
Fig. 9 depicts the results for Scenario 4. As in Scenario 2, TCA fails due to LOS path blockages. HiTCA exhibits some performance loss relative to the blockage-free Scenario 3 but continues to outperform SCA across all noise levels.
To demonstrate the scalability of HiTCA in realistic indoor and outdoor environments, we next examine the impact of the blockage probability ρ n,k , which can vary widely, especially in urban or indoor settings. For simplicity we assume ρ n,k = ρ, ∀n, ∀k. We analyze the probability that HiTCA fails to locate a target as a function of both the number of sensors N and the blockage probability ρ n,k . Because trilateration requires at least three LOS range measurements, i.e., three circles centered at distinct sensors whose pairwise intersections yield a unique point, a target is locatable when at least three LOS measurements are available. For a system consisting of N ≥ 3 sensors with a blockage probability ρ, the probability that fewer than three sensors obtain LOS measurements for a given target is given by
Table II lists the success probability of HiTCA for increasing values of ρ and N . As expected, this probability declines sharply as N increases. This result suggests that the performance and robustness of the algorithm can be enhanced by scaling up the network size in a difficult environment with significant blockage.
We examined LOS path identification for passive multitarget localization in multipath environments. To address LOS path blockage, a HiTCA algorithm was proposed based on the idea of classifying the targets into different levels. HiTCA employs a multi-level search strategy for LOS measurement identification. To reduce the complexity, HiTCA uses a threshold determined from the average deviation of a TIP set. To handle the uncertainty of the target number, deduplication and elbow detection are integrated into the algorithm to eliminate redundant estimates of target locations and provide a reliable inference of the target number. Simulation results demonstrate that HiTCA consistently delivers high localization accuracy across various setups, outperforming peer algorithms used for comparison. Additional validation experiments using realworld measurement data can be considered in future work. -25 -20 -15 -10 -5 0 5 Noise Level (dB) 10 -2 10 0 10 2 MSE -25 -20 -15 -10 -5 0 5 Noise Level (dB) 0 0.1 0.2 0.3 0.4 0.5 0.6 Probability of underestimation P u (a) (b) Fig. 7. Scenario 2: Target locations are fixed with ρ n,k = 0.1. (a) MSE. (b) Probability of underestimation Pu. -25 -20 -15 -10 -5 0 5 Noise Level (dB) 10 -2 10 0 10 2 MSE -25 -20 -15 -10 -5 0 5 Noise Level (dB) 0 0.1 0.2 0.3 0.4 Probability of underestimation P u (a) (b) Fig. 8. Scenario 3: Target locations are randomly generated with ρ n,k = 0. (a) MSE. (b) Probability of underestimation Pu. with its center located at point B = (x b , y b ). Let d denote the distance between A and B d = |AB| = (x b -x a ) 2 + (y b -y a ) 2 . (11) Suppose d ≤ r a + r b . Then circles A and B intersect at points C and D. Let
and the coordinates of the intersection points C and D are given by [38] x
APPENDIX B STATISTICAL CHARACTERIZATION OF SPREAD Fig. 10(a) depicts a target at location P , LOS circles centered at sensors A and B, and their intersections. The noisy range measurements can be written as
where R a and R b denote the noise-free target range with respect to sensor A and B, while ε a and ε b represent the measurement noise terms. Note that the noise can be either positive or negative. For illustration, the intersection P 1 of the noisy LOS circles shown in Fig. 10(a) represents one possible intersection scenario when ε a and ε b are positive. Our goal is to first calculate the point deviation in terms of the squared distance |P P 1 | 2 and then its maximum average value. Consider a coordinate system taking A as the origin and the line of AB as the x-axis. Let |AB| = d. By the law of sines
where
And since
the coordinates of point P are thus given by
Similarly
where
Thus
It is difficult to determine the maximum average value of |P P 1 | 2 due to its nonlinear form. We resort to computer simulation. Specifically. Similarly, in △P BP 1 we have
By combining ( 27) and ( 28) and using the substitutions, along with ( 18) and ( 19), for d = R a + R b we have
where the approximation is obtained by ignoring the quadratic noise terms. For Case (b) with d = R a -R b , it can be shown that
Similarly, for Case (c) with d = R b -R a , we have
The results ( 29), (30), and (31) hold only when the two noisy LOS circles intersect, which respectively require the measurement noises ε a and ε b to satisfy the condition ε a + ε b ≥ 0, ε b -ε a ≥ 0, and ε a -ε b ≥ 0. Recall that a ε b are independent and identically distributed random variables following N (0, σ 2 ). Therefore, let ε s1 ≜ ε a +ε b , ε s2 ≜ ε b -ε a , and ε s3 ≜ ε a -ε b , and they all follow N (0, 2σ 2 ). Note that in all three cases, the circles intersect only when ε s ≥ 0. Under this condition, ε s is a positive half-normal distribution. Therefore,
In practice, we usually have D > √ 2d, in which case (35) is larger than (33) and is therefore used as the threshold for eliminating candidate sets that are unlikely TIP sets.
We provide here a probabilistic analysis of point loss and the recovery method proposed in Section III-C. For a target located at p k , we first determine the probability of two LOS circles associated with the target not intersecting due to noise. Suppose the centers of the two LOS circles are a i and a j . Similar to (1), the radii of these circles can be written as
r j,k = ∥p k -a j ∥ + ε j .
Let d i,j = ∥a j -a i ∥. The LOS circles will not intersect if and only if one of the following inequalities is met
among which (38) corresponds to the case of external separation, while (39) represents the case of internal separation. Without loss of generality, assume r i,k > r j,k . Then (38) and (39) can be rewritten as
Since ε i and ε j are independent and identically distributed (cf. Section II), their joint probability density function can be expressed as
Hence the probability of two circles being externally or internally separated can be expressed as
v i,j ≜ εi-εj >hi,j p(ε i , ε j )dε i dε j = Φ -
where Φ(•) is the cumulative distribution function (CDF) of the standard normal distribution. Since the external and internal separations are mutually exclusive, the probability p i,j of two LOS circles not intersecting with each other is given by p i,j = u i,j + v i,j .
In Section III-C, we proposed a recovery method by increasing/decreasing the radii of a pair of non-intersecting circles by κ. Similar to (38) and (39), the extended circles will not intersect if and only if one of the following conditions holds:
r i,k -2κ -r j,k > d i,j .
Clearly, the probability of the two extended LOS circles not intersecting is
Alternatively, after a TIP set is identified, its range measurements could be excluded from higher-level searches to prevent cross-level redundancy from happening. However, we find that allowing such redundancy is more beneficial, as it aids in the elbow detection described in Section V-D. Specifically, this redundancy generates more candidate TIP sets within the flat region of the elbow (cf. Fig.5), which enhances the ability to accurately detect the rising edge of the elbow.