[ Article ]

The Journal of Korean Institute of Information Technology - Vol. 23, No. 10, pp.153-161

ISSN: 1598-8619 (Print) 2093-7571 (Online)

Print publication date 31 Oct 2025

Received 26 Sep 2025 Revised 13 Oct 2025 Accepted 16 Oct 2025

DOI: https://doi.org/10.14801/jkiit.2025.23.10.153

Optimal Ground-based Anchor Placement for Reference-Insensitive Linear Least Squares Multilateration

Jun-Sung Ko^*

; Sun-Phil Nah^**

; Cheol-Sun Park^**

; Won-Zoo Chung^***

*Korea University, M.S. Candidate, Dept. of Artificial Intelligence
**Agency for Defense Development, 3rd Research and Development Institute, Senior Researcher
***Korea University, Professor, Dept. of Artificial Intelligence

Correspondence to: Won-Zoo Chung Dept. of Artificial Intelligence, Korea University, Seoul, Korea Tel.: +82-2-3290-4845, Email: wchung@korea.ac.kr

Abstract

In this paper, we propose an optimal anchor placement method in ground-based multilateration systems using reference-independent least squares, which averages the target estimates from all possible reference anchor selections. Based on the reference-independent least squares solution and error variance analysis, we introduce a target-independent cost function for anchor placement under the practical assumption that all anchors are approximately the same distance from the target in ground-based systems. The optimal anchor placement for a given boundary is then obtained by minimizing the cost function via a heuristic search algorithm, such as the Modified Reinforcement Learning Algorithm (MORELA). Simulation results show that the estimated target position using the proposed anchor placement outperforms the positions estimated with randomly placed anchors within the given boundary in terms of Mean Squared Error (MSE).

초록

본 논문에서는 지상 센서 기반 다중측위(Multilateration) 시스템에서, 선택 가능한 모든 참조 앵커로부터 산출된 표적 위치 추정치를 평균화하는 참조 독립 최소제곱(Reference-independent least squares)을 이용하여 앵커 배치를 최적화하는 방법을 제안한다. 참조 독립 최소제곱해와 오차 분산 분석을 바탕으로 지상 기반 센서 시스템에서 모든 앵커가 표적과 거의 동일한 거리에 위치한다는 실용적 가정하에 앵커 배치를 위한 표적 독립적 비용함수를 도입한다. 이어서 주어진 경계 영역에서의 최적 앵커 배치는 MORELA(Modified Reinforcement Learning Algorithm)과 같은 휴리스틱 탐색 알고리즘을 통해 해당 비용을 최소화함으로써 도출된다. 시뮬레이션 결과, 제안한 앵커 배치를 사용하여 추정한 표적 위치는 평균제곱오차(MSE) 측면에서 주어진 경계 내에서 여러 무작위로 배치 시나리오보다 일관되게 우수함을 보였다.

Keywords:

localization, optimization, region constraint, sensor placement

Ⅰ. Introduction

Multilateration is a localization technique that estimates the position of an unknown target from the measured distances to a set of sensors (referred to as anchors) with known coordinates [1]. Several studies have investigated target position estimation from a set of quadratic equations derived from these distances [2]-[4]. Perhaps the most practical method is Linear Least Squares Multilateration (LLSM), which is based on linearizing the quadratic equations with respect to a chosen reference anchor [5].

The performance of LLSM is heavily influenced by the geometrical arrangement of anchors, and it often fails to accurately estimate a three-dimensional target position in ground-based systems where all anchors are confined to a two-dimensional plane. For example, in Unmanned Aerial Vehicle (UAV) localization, anchors are typically ground-based because deploying nodes at flight altitude is impractical (power/backhaul, maintenance aloft) and restricted by airspace safety and regulations [6][7]. Due to the practical importance of ground-based systems, several solutions have been proposed to adapt LLSM for such scenarios. One effective approach, described in [7], involves first estimating the x and y coordinates of the target using linear least squares, followed by solving a quadratic equation to determine the z coordinate.

While optimal anchor placement for LLSM has been studied, most research relies on Cramér-Rao lower bound (CRLB) analysis across various scenarios. Previous works on optimal anchor placement can be categorized into three groups: bearing-based studies that use only angle-of-arrival information [8]-[10] unconstrained range-based studies that assume no spatial limits [11]-[13] and boundary-constrained studies that incorporate physical deployment limits [3],[14][15]. All of these works assume prior knowledge of the target position. Moreover, performance depends on the choice of reference anchor, which itself depends on the target position. Therefore, it is desirable to design an anchor placement strategy that is optimal on average for arbitrarily positioned targets and reference anchors, without requiring prior target position knowledge.

In this paper, we propose a strategy for optimal anchor placement in ground-based LLSM that eliminates the need for prior knowledge of the target position and the selection of a specific reference anchor. To achieve insensitivity to the choice of reference anchor, we compute the averaged target estimation across all reference anchors [5] and analyze the associated error variances.

Given the characteristics of ground-based multilateration, we assume the target’s height is sufficiently large, rendering the contributions of the x and y coordinates to the error variance negligible. Leveraging this assumption, we derive a target-independent cost function for optimal anchor placement. However, systematically identifying the optimal anchor configuration that minimizes this cost function remains challenging, particularly for arbitrary anchor placement boundaries.

To address this, we employ a heuristic search method, specifically the Modified Reinforcement Learning Algorithm (MORELA), which is grounded in reinforcement learning principles [16], to find anchor placements that minimize the cost function for a given boundary.

Simulation results demonstrate that the target positions estimated using our proposed anchor placement strategy significantly outperform those derived from randomly placed anchors, achieving lower mean squared error (MSE) across various anchor boundary configurations.

Ⅱ. Ground-based Anchor Placement Optimization

2.1 System model

Consider N anchors deployed in the x-y plane with known positions $a i = x i, y i, 0 T$ , for $i = 1, …, N$ , and a target with unknown position $t = x t, y t, z t T$ .Multilateration estimates the target position using noisy distance measurements from the target to each anchor, expressed as

d^i = a i - t + ε i, f o r i = 1, …, N

(1)

where ε_i denotes i.i.d. zero-mean Gaussian noise with variance σ².

In linear least squares multilateration (LLSM), linearization of Eq. (1) is performed by subtracting the distance $d^r$ from a chosen reference anchor a_r from all other $d^i$ . The performance of LLSM depends on the reference anchor selection, with the anchor closest to the target typically yielding the lowest mean squared error (MSE). Since the target position is unknown, [13] proposes averaging the target estimates obtained by using each anchor as the reference. The averaged target estimate is derived by solving the least-squares equation:

x^t, y^t, 0 T = 12 A † b

(2)

where $⋅ †$ denotes the pseudo-inverse, A is an $N 2 × 3$ matrix with rows $x i - x j, y i - y j, z i - z j$ for $1 ≤ i < j ≤ N$ , and b is an $N 2 × 1$ vector with entries $d^j 2 - d^i 2 + a i 2 - a j 2$ .

As shown in Eq. (3), the z-coordinate of the target can be obtained by averaging the distances from all anchors.

z^t = 1 N ∑ i = 1 N d^i 2 - x^t - x i 2 - y^t - y i 2

(3)

To analyze the error variance, we solve Eq. (2) explicitly. Let $x : = x 1, …, x N T$ and $y : = y 1, …, y N T$ represent the vectors of the anchors’ x and y coordinates, respectively. The sample means and variances are defined in Eqs. (4)~(7).

x - : = 1 N ∑ i = 1 N x i, y - : = 1 N ∑ i = 1 N y i

(4)

S x : = 1 N - 1 ∑ i = 1 N x i - x - 2

(5)

S y : = 1 N - 1 ∑ i = 1 N y i - y - 2

(6)

S x y : = 1 N - 1 ∑ i = 1 N x i - x - y i - y -

(7)

Using the definitions in Eqs. (4)~(7), the estimation errors for the target coordinates x and y are derived as shown in Eqs. (8) and (9).

x^t - x t = 1 N - 1 ∑ i = 1 N K x, i d i ε i + 12 ε i 2 S x S y - S x y 2

(8)

y^t - y t = 1 N - 1 ∑ i = 1 N K y, i d i ε i + 12 ε i 2 S x S y - S x y 2

(9)

where

d i : = a i - t

(10)

K x, i : = S y x - - x i - S x y y - - y i

(11)

K y, i : = S x y - - y i - S x y x - - x i

(12)

In Eqs. (10)~(12), d_i represents the true distance between the i-th anchor and the target, while K_x_,i and K_y_,i denote geometric coefficients that depend on the sample variances and covariance of the anchor positions. Note that Eqs. (13)~(15), the summation of K_x_,i and K_y_,i over all anchors are zero, and their squared sums are proportional to the spatial variances of the anchor distribution.

∑ i = 1 N K x, i = ∑ i = 1 N K y, i = 0

(13)

∑ i = 1 N K x, i 2 = N - 1 S y S x S y - S x y 2

(14)

∑ i = 1 N K y, i 2 = N - 1 S x S x S y - S x y 2

(15)

So the error variances of the estimators are presented in Eqs. (16)~(18). Note that Eq. (16), (17) are unbiased.

E x : = E x^t - x t 2 = 1 N - 1 2 ∑ i = 1 N K x, i 2 d i 2 σ 2 + σ 4 2 S x S y - S x y 2 2

(16)

E y : = E y^t - y t 2 = 1 N - 1 2 ∑ i = 1 N K y, i 2 d i 2 σ 2 + σ 4 2 S x S y - S x y 2 2

(17)

E z : = E z^t - z t 2 ≈ 1 N 2 z t 2 ∑ i = 1 N d i 2 σ 2 + x t - x i 2 E x + y t - y i 2 E y f o r z t ≫ 1

(18)

2.2 Cost function for optimal anchor placement

The variances E_x and E_y depend on both the target position and anchor placement. Since E_z is a weighted sum of E_x and E_y, we aim to minimize E_x + E_y. But there still remains a significant challenge: designing an anchor layout that is optimal for a target at an unknown location.

To overcome this dependency, our primary goal is to derive a cost function that is independent of the target’s coordinates. To eliminate the target-dependent $d^i$ terms, we introduce a practical assumption common in many ground-based systems, which we term the Equidistance Assumption. We assume that the target’s height z_t is sufficiently large ( $z t ≫ x t, y t$ ), meaning the target’s altitude is significantly greater than its horizontal displacement relative to the geometric center of the anchor array. Under this assumption, the range from the target to each ground-based anchor becomes dominated by the altitude component z_t.

In the case, as shown in Eq. (19), the differences in ranges among the anchors become negligible and the range from the target to each anchor can be approximated as a constant value d_i ≈ d_j.

d i = z t 2 + x i - x t 2 + y i - y t 2 ≈ z t 2 + x i - x t 2 + y i - y t 2 = d j

(19)

This allowing us to set $d^i = d$ for all $i = 1, …, N .$ Substituting the approximation in Eq. (19) into the variance expression yields Eq. (20). This makes the error variances independent of the target position:

E x = d 2 σ 2 + σ 4 2 N - 1 2 ∑ i = 1 N K x, i 2 S x S y - S x y 2 2 = d 2 σ 2 + σ 4 2 N - 1 S y S x S y - S x y 2

(20)

Based on Eq. (20), we define the cost function for optimal anchor placement as in Eq. (21). This cost function represents the normalized sum of E_x and E_y.

C x, y : = N - 1 d 2 σ 2 + σ 4 2 E x + E y = S x + S y S x S y - S x y 2

(21)

This can be rewritten as Eq. (22), where ρ_xy is the sample Pearson correlation coefficient.

C x, y = 1 S x + 1 S y 1 - ρ x y 2,

(22)

The cost function C(x,y) is minimized when x and y are uncorrelated(ρ_xy = 0) and the variances S_x and S_y are maximized.

However, it is difficult to find an analytic solution for x and y minimizing C(x,y) when x and y are constrained within a given region. Hence, we propose using a heuristic search algorithm. Among various heuristic approaches, we employ the Modified Reinforcement Learning Algorithm(MORELA)[16], a metaheuristic global optimization method that avoids local minima by iteratively focusing its search on promising regions of the solution space. Other heuristic algorithms—such as genetic algorithms, simulated annealing, and QPSO—have yielded essentially the same anchor placements.

Ⅲ. Experimental Results

In this section, we assess the optimality of the proposed anchor placement for a given region by evaluating the total estimation error variance $E : = E x + E y + E z$ through numerical simulations. The proposed placements are compared with random anchor placements within a given region, tested across seven target positions on a circle at height 3: t₁ = [0,0,3]^T and t_k = [cos(2π(k-2)/6), sin(2π(k-2)/6), 3]^T for k = 2, …, 7.

The optimal anchor placement is determined using MORELA, with a learning rate of α = 0.8, a discount factor of γ = 0.2, T = 2000 iterations, and K = 20 sub-environments. The initial exploration range is set to 1.0 and decays by a factor of β = 0.99 per iteration. A minimum distance of d_min = 0.1 between anchors ensures distinct placements.

All measured distances are corrupted by additive i.i.d. Gaussian noise with zero mean and a standard deviation of σ = 0.01. One million Monte Carlo trials are conducted for each anchor placement to compute the error variance. Given the impracticality of evaluating the error variance performance for all possible anchor placements within a region, we compare the proposed method with randomly selected anchor placements. We evaluate 2,000 random anchor placement sets per region: 1,000 within the region (including the boundary) and 1,000 on the boundary, since optimal placements tend to lie on the boundary. The regions considered are:

1. Circle: $x, y x 2 + y 2 ≤ 1$
2. Square: $x, y - 1 ≤ x, y ≤ 1$
3. Pentagon: A pentagon with vertices $c o s ⁡ 2 π k / 5, s i n ⁡ 2 π k / 5 k = 0,1, …, 4$
4. Non-Convex Pentagon: A pentagon with vertices $c o s ⁡ 2 π k / 5, s i n ⁡ 2 π k / 5 k = 0,1, …, 3$ and (0,0)

Fig. 1, 2, 3 and 4 illustrate the proposed optimal anchor placements for various numbers of anchors ( $N = 3, …, 6$ ) deployed in the four regions described above. For the unit circle, optimal placements maximize S_x and S_y to 1 and minimize S_xy to 0. In polygonal regions, some anchors are positioned near vertices to maximize S_x and S_y while minimizing S_xy.

Fig. 1.

Proposed anchor placements in the unit circle

Fig. 2.

Proposed anchor placements in the square

Fig. 3.

Proposed anchor placements in the pentagon

Fig. 4.

Proposed anchor placements in the non-convex pentagon

We examined how the target altitude affects localization error for a single off-center target $t = 0.95,0, z t T$ while keeping the six ground anchors fixed on the unit circle in the proposed placement. We swept $z t ∈ 0.2,0.3,0.5,0.7,1.0,1.5,2.0,3.0$ and compared the proposed layout for N=6 against Random-Best (best of 100 random layouts under the same constraints). Fig. 5 shows MSE versus altitude. From about z_t = 2 onward (i.e., z_t ≥ the maximum inter-anchor distance), the equi-distance assumption is valid and for z_t < 2, the assumption starts failing.

Fig. 5.

MSE versus target altitude zt. Proposed (red) vs. Random-Best (blue)

Fig. 6, 7, 8, and 9 present the total variance E for each target $t 1, ⋯, t 7$ of the proposed optimal anchor placements for various numbers of anchors ( $N = 3, …, 6$ ) in the four regions. The label `Avg' denotes the average variance across all targets. Red solid lines represent the total variance of the proposed anchor placements, while blue lines denote random placements. Although some random placements may outperform the proposed ones for specific targets (e.g., Fig. 6(a)), the proposed placements consistently achieve the lowest average error variance across all targets.

Fig. 6.

Target estimate error variance performance in the unit circle: proposed versus randomly selected

Fig. 7.

Target estimate error variance performance in the square: proposed versus randomly selected

Fig. 8.

Target estimate error variance performance in the pentagon: proposed versus randomly selected

Fig. 9.

Target estimate error variance performance in the non-convex: proposed versus randomly selected.

Ⅳ. Conclusion

The proposed optimal anchor placement strategy, developed without prior knowledge of the target position under the equidistance assumption, provides optimal anchor positions for ground-based multilateration. Simulation results confirm that the optimal anchor placement, obtained using the MORELA heuristic search algorithm, consistently achieves lower mean squared error (MSE) in target position estimates compared with random anchor placements. As future work, we will validate the proposed approach in real-world settings. We plan to implement a prototype and run field trials in representative environments to assess accuracy and robustness.

Acknowledgments

This study was supported by the Agency for Defense Development, Republic of Korea (Grant No. 915087201)

References

A. N. Bishop, B. Fidan, B. D. O. Anderson, P. N. Pathirana, and K. Doğançay, "Optimality analysis of sensor-target geometries in passive localization: Part 2 – Time-of-arrival based localization", Proc. 3rd International Conference on Intelligent Sensors, Sensor Networks and Information Processing (ISSNIP), Melbourne, VIC, Australia, pp. 13-18, Dec. 2007. [https://doi.org/10.1109/ISSNIP.2007.4496812]
A. N. Bishop, B. Fidan, B. D. O. Anderson, K. Doğançay, and P. N. Pathirana, "Optimality analysis of sensor-target localization geometries", Automatica, Vol. 46, No. 3, pp. 479–492, Mar. 2010. [https://doi.org/10.1016/j.automatica.2009.12.003]
M. Sadeghi, F. Behnia, and R. Amiri, "Optimal sensor placement for 2-D range-only target localization in constrained sensor geometry", IEEE Transactions on Signal Processing, Vol. 68, pp. 2316-2327, Apr. 2020. [https://doi.org/10.1109/TSP.2020.2985645]
S. Xu, Y. Ou, and X. Wu, "Optimal sensor placement for 3-D time-of-arrival target localization", IEEE Transactions on Signal Processing, Vol. 67, No. 20, pp. 5018-5031, Oct. 2019. [https://doi.org/10.1109/TSP.2019.2932872]
Y. Wang, F. Zheng, M. Wiemeler, W. Xiong, and T. Kaiser, "Reference selection for hybrid TOA/RSS linear least squares localization", Proc. IEEE 78th Vehicular Technology Conference (VTC Fall), Las Vegas, USA, pp. 1-5, Sep. 2013. [https://doi.org/10.1109/VTCFall.2013.6692388]
K.-H. Kim, N.-J. Park, H.-G. Lee, and H.-S. Ahn, "3-D localization with coplanar anchors", IEEE Communications Letters, Vol. 27, No. 1, pp. 110-114, Jan. 2023. [https://doi.org/10.1109/LCOMM.2022.3216030]
M. Khalaf-Allah, "Novel solutions to the three-anchor ToA-based three-dimensional positioning problem", Sensors, Vol. 21, No. 21, Art. No. 7325, Nov. 2021. [https://doi.org/10.3390/s21217325]
S. Nardone, A. Lindgren, and K. Gong, "Fundamental properties and performance of conventional bearings-only target motion analysis", IEEE Transactions on Automatic Control, Vol. 29, No. 9, pp. 775-787, Sep. 1984. [https://doi.org/10.1109/TAC.1984.1103664]
I. Kadar, "Optimum geometry selection for sensor fusion", Proc. SPIE Signal Processing, Sensor Fusion, and Target Recognition VII, Orlando, FL, USA, Vol. 3374, pp. 96-107, Apr. 1998. [https://doi.org/10.1117/12.327141]
A. G. Dempster, "Dilution of precision in angle-of-arrival positioning systems", Electronics Letters, Vol. 42, No. 5, pp. 291-292, Mar. 2006. [https://doi.org/10.1049/el:20064410]
S. Martínez and F. Bullo, "Optimal sensor placement and motion coordination for target tracking", Automatica, Vol. 42, No. 4, pp. 661-668, Apr. 2006. [https://doi.org/10.1016/j.automatica.2005.12.018]
S. B. Chaudhry, V. C. Hung, R. K. Guha, and K. O. Stanley, "Pareto-based evolutionary computational approach for wireless sensor placement", Engineering Applications of Artificial Intelligence, Vol. 24, No. 3, pp. 409-425, Apr. 2011. [https://doi.org/10.1016/j.engappai.2010.07.007]
E. Tzoreff and A. J. Weiss, "Path design for best emitter location using two mobile sensors", IEEE Transactions on Signal Processing, Vol. 65, No. 20, pp. 5249-5261, Oct. 2017. [https://doi.org/10.1109/TSP.2017.2728504]
Y. Liang and Y. Jia, "Constrained optimal placements of heterogeneous range/bearing/RSS sensor networks for source localization with distance-dependent noise", IEEE Geoscience and Remote Sensing Letters, Vol. 13, No. 11, pp. 1611-1615, Nov. 2016. [https://doi.org/10.1109/LGRS.2016.2597960]
M. Sadeghi, F. Behnia, and R. Amiri, "Optimal geometry analysis for TDOA-based localization under communication constraints", IEEE Transactions on Aerospace and Electronic Systems, Vol. 57, No. 6, pp. 3096-3106, Dec. 2021. [https://doi.org/10.1109/TAES.2021.3069269]
C. Ozan, O. Baskan, and S. Haldenbilen, "A novel approach based on reinforcement learning for finding global optimum", Open Journal of Optimization, Vol. 6, No. 2, pp. 65-84, Jun. 2017. [https://doi.org/10.4236/ojop.2017.62006]

Authors

Jun-Sung Ko

2021. 2 : B.S. degree, Dept. of Information and Computer Engineering, Dankook University

2024. 2 ~ Present: MS candidate, Dept. of Artificial Intelligence, Korea University

Research interests : Optimization, Reinforcement Learning

Sun-Phil Nah

1985. 2 : B.S. degree, Dept. of Computer Engineering, Chungnam National University

1987. 2 : M.S. degree, Dept. of Computer Engineering, Chungnam National University

1991. 2 ~ Present : Senior Researcher, Agency for Defense Development (ADD)

Research interests : Acoustic Signal Processing

Cheol-Sun Park

1989. 2 : B.S. degree, Dept. of Electronic Engineering, Kyonggi University

1991. 2 : M.S. degree, Dept. of Electronic Engineering, Inha University

2007. 2 : Ph.D. degree, Dept. of Information and Computer Engineering, Chungnam National University

1991. 2 ~ Present : Senior Researcher, Agency for Defense Development (ADD)

Research interests : Communication Signal Processing, Sensor Array Signal Processing

Won-Zoo Chung

1989. 2 : B.S. degree, Dept. of Mathematics, Korea University

1999. 5 : M.S. degree, Dept. of Electrical and Computer Engineering, Cornell University

2003. 5 : Ph.D. degree, Dept. of Electrical and Computer Engineering, Cornell University

2008. 3 ~ 2020. 3 : Professor, Dept. of Computer Science, Korea University

2020. 3 ~ Present : Professor, Dept. of Artificial Intelligence, Korea University

Research interests : Artificial Intelligence, Quantization