Source-linked AI summary
Dynamic Sensor Pairing for TDOA-Based Target Tracking via mixed-integer Second-Order Cone Programming
Ryosuke Ikura, Junya Hara, Hiroshi Higashi, Yuichi Tanaka
TL;DR
Fixed sensor-pair designs do not adapt to a moving target’s current estimated position, despite the importance of sensor-target geometry for TDOA tracking. This paper selects pairs dynamically by optimizing a Fisher-information criterion through a MISOCP. It reports the lowest tracking error among degree-constrained methods across three noise models, with exact solutions for networks of up to 50 sensors within one second per time step.
Problem
Existing pairing designs fix active pairs in advance, although the best sensor-target geometry changes as the target moves.
Source: §1 · p. 1Method
At each time step, the method maximizes a Fisher-information criterion using pairs selected at the previous position estimate, reformulating the combinatorial problem as a MISOCP for globally optimal pairing.
Source: §1 · p. 1, §3.2 · p. 2, Step 2: Three-Scalar Parameterization · p. 3Results
Across three noise models, the proposed method achieves the lowest RMSE among degree-constrained methods and remains within a factor of 1.6 of the all-pairs reference while activating a fifth of candidate pairs.
Source: §1 · p. 1, §4.2 · p. 4Takeaways & Limitations
The exact pairing solution is obtained within one second per time step for networks of up to 50 sensors.
Source: §5 · p. 4, §4.2 · p. 4The selection assumes that the target moves smoothly between consecutive time steps.
Source: §3.1 · p. 2
Abstract
from arXiv · showhide
We propose a sensor pairing method for online target tracking based on time-difference-of-arrival (TDOA) measurements through a sensor network. Existing pairing designs fix active sensor pairs in advance. In online tracking, however, adapting the pairing to the current target estimate maintains a favorable sensor-target geometry around it. We select $K$ pairs at each time step to maximize a Fisher information matrix (FIM) criterion under a communication-degree constraint. The original combinatorial problem is cast as a mixed-integer second-order cone program. We solve it at every time step to obtain a globally optimal pairing. Experiments under various noise settings show that the proposed method obtains the lowest tracking error among the methods under the same communication-degree constraint.
1. INTRODUCTION
Online TDOA tracking must choose a limited set of sensor pairs as the target moves, because localization accuracy depends on sensor-target geometry. The proposed method adapts pairs to the current estimate and solves the selection problem globally at each time step.
1. INTRODUCTION
- TDOA measures arrival-time differences across sensors without requiring synchronization between the target and network, making it suitable for non-cooperative targets.By contrast, time-of-arrival requires known transmission time, while received signal strength requires path-loss model calibration.Source: §1 · p. 1
- A communication budget limits active pairs and each sensor’s communication degree, while using all candidate pairs consumes bandwidth and battery.The selected pairs therefore affect position-estimation accuracy within a constrained network.Source: §1 · p. 1
- Existing designs fix pairs offline, although the best sensor-target geometry changes as the target moves and noisy TDOA hyperbolas affect localization accuracy.Prior pairing methods optimize an accuracy criterion over the surveillance region, including a greedy design.Source: §1 · p. 1
- The method maximizes the determinant of the Fisher information matrix at the previous position estimate, updating active pairs as the target moves under a smooth-motion assumption.For planar tracking, the criterion has a second-order cone representation, yielding a MISOCP with a globally optimal solution.Source: §1 · p. 1
- Across three noise models, the proposed method achieves lower tracking error than existing methods and solves each pairing step exactly within one second for networks of up to 50 sensors.The experiments use synthetic sensor networks and compare against static and baseline dynamic selection.Source: §1 · p. 1
2. PRELIMINARIES
The preliminaries model planar single-target TDOA measurements with position-dependent noise and define the Fisher information used to evaluate sensor-pair choices.
2. PRELIMINARIES
- For a sensor pair, the noiseless TDOA depends on the target and sensor positions, with propagation speed set to 1 without loss of generality.The setup is two-dimensional and considers a single target.Source: §2 · p. 2
- The measurement noise is modeled as Gaussian with variance that can grow with target-to-sensor distance; η = 0 gives uniform noise and η = 2 gives distance-dependent noise.κ sets the noise level, and measurement pairs have independent noise.Source: §2 · p. 2
- The Fisher information matrix accounts for position sensitivity in both the measurement mean and covariance, and maximizing its determinant tightens the estimation-error bound.The bound is the inverse Fisher information matrix at the true position.Source: §2 · p. 2
3. DYNAMIC SENSOR PAIRING FOR TARGET TRACKING
The method updates active TDOA sensor pairs at each time step, choosing them using the previous target estimate. It formulates this choice as a constrained FIM optimization and reformulates it as a MISOCP for online tracking.
3. DYNAMIC SENSOR PAIRING FOR TARGET TRACKING
- At each time step, the system activates selected pairs, collects their TDOA measurements, updates the target-position estimate, and repeats the process.The pairing is determined before measurements are collected for that step.Source: §3 · p. 2
3.1. Formulation of Sensor Pairing Problem
- Assuming smooth target motion, the method evaluates the FIM at the previous position estimate and selects pairs using the D-optimality criterion.The FIM at the previous estimate is treated as a good approximation of the FIM at the true position.Source: §3.1 · p. 2
- The pairing selects exactly K candidate pairs while limiting each sensor’s degree to Dmax, reflecting communication constraints.Sensor networks are represented as graphs, with sensors as nodes and candidate pairs as edges.Source: §3.1 · p. 2
3.2. Problem Reformulation
- The combinatorial selection is reformulated as a MISOCP, and the online procedure solves it at each step before activating the chosen pairs and estimating the target position.The reformulation uses an indicator vector for pair selection and the node-edge incidence matrix to express sensor degrees.Source: §3.2 · pp. 2–3
Step 2: Three-Scalar Parameterization
The three-scalar parameterization expresses the determinant objective through quantities linear in the pair-selection vector, enabling a second-order cone formulation. The resulting MISOCP has a global optimum when a feasible pairing exists, and the tracking section reports its evaluation setup.
Step 2: Three-Scalar Parameterization
- The determinant objective becomes a quadratic form in three scalars that are linear in the pair-selection vector, enabling its hypograph to be represented by a second-order cone constraint.Maximizing the auxiliary variable γ maximizes the determinant.Source: Step 2: Three-Scalar Parameterization · p. 3
- A branch-and-bound solver returns a global optimum of the pairing problem whenever a feasible pairing exists.The formulation is a MISOCP with a linear objective and binary selection variables.Source: Step 2: Three-Scalar Parameterization · p. 3
3.3. Application to Online Tracking
- Table 1 reports tracking RMSE as mean ± standard deviation over 50 trials for three noise models, with lower values better.The setup uses N = 10 sensors, K = 9 active pairs, and Dmax = 5; bold marks the best degree-constrained method in each column.Source: Table 1 · p. 3
- Fig. 2 depicts position error over time and compares the true and estimated trajectories in one distance-dependent-noise trial.The setup uses N = 10, K = 9, and Dmax = 5.Source: Figure 2 · p. 3
4. EXPERIMENTS
Synthetic-network experiments compare tracking accuracy and pairing time under communication constraints. The proposed method has the lowest RMSE among degree-constrained methods across three noise models and computes pairings quickly for networks up to 50 sensors.
4.1. Setting
- The synthetic experiments use randomly placed sensors, a randomly wandering target, K = 9 pairs and Dmax = 5, comparing static, nearest-edge, random, and all-pairs selections over three noise settings.Each method is tested for 50 time steps over 50 trials; NLOS obstructions are unknown to the system, testing robustness to a misspecified noise model.Source: §4.1 · pp. 3–4
4.2. Results
- Across all three noise models, the proposed method has the lowest RMSE among degree-constrained methods, reaching within a factor of 1.6 of the all-pairs reference while activating a fifth of candidate pairs.The all-pairs reference ignores the maximum-degree constraint.Source: §4.2 · p. 4, §4.1 · p. 4
- Nearest-edge selection leads static pairing under distance-dependent noise but trails it under uniform noise; under NLOS, the proposed method remains best among degree-constrained methods despite a misspecified variance model.Obstructed-link bias violates the zero-mean Gaussian assumption behind the FIM.Source: §4.2 · p. 4, §4.1 · p. 4
- In one distance-dependent-noise trial, the proposed method's position error stays small through the trajectory while other degree-constrained methods sometimes produce large errors.Figure 2 reports position error at each time step.Source: §4.2 · p. 4
- With distance-dependent noise, tracking RMSE is plotted against active-pair count; the proposed method's advantage over static design widens as K decreases.The figure uses N = 10 and Dmax = 5; beyond K = N − 1, the dotted segment repeats the static-design value.Source: §4.2 · p. 4, Figure 3 · p. 4
- For networks up to N = 50, pairing takes under 300 ms on average and under 1000 ms in the worst case; the proposed method and brute-force search obtain the same optimal value in measured instances.The paper notes that TDOA systems typically operate with periods of 450 to 1000 ms.Source: §4.2 · p. 4, Figure 4 · p. 4
5. CONCLUSION
The conclusion presents dynamic, communication-constrained TDOA sensor pairing as a globally optimized method that achieves the lowest tracking error among degree-constrained methods across three noise models.
5. CONCLUSION
- At each tracking step, the method selects TDOA sensor pairs under cardinality and maximum-degree constraints by maximizing FIM D-optimality at the previous position estimate.The estimate is used under the assumption that the target moves smoothly over time.Source: §5 · p. 4
- The pairing problem is exactly a MISOCP, yielding a globally optimal pairing within every tracking step.Source: §5 · p. 4
- Simulations report the lowest tracking error among degree-constrained methods across three noise models, with the optimum obtained within one second per step for networks up to 50 sensors.Source: §5 · p. 4