Source-linked AI summary
TDOA-Based Online Target Tracking with Simultaneous Sensor Pairing and Relocation
Ryosuke Ikura, Junya Hara, Hiroshi Higashi, Yuichi Tanaka
TL;DR
Existing designs optimize sensor pairing or sensor relocation while fixing the other, although both choices matter to TDOA tracking accuracy. This paper alternates between pairing and relocation updates under a Fisher-information D-optimality criterion. Simulations report improved tracking accuracy over alternative methods within practical online computation time.
Problem
Method
The method alternates between sensor pairing via MISOCP and sensor relocation via majorization-minimization to optimize a Fisher-information D-optimality criterion.
Source: §1 · p. 1, §4.2 · p. 3Results
Takeaways & Limitations
The proposed simultaneous optimization improves tracking accuracy compared with methods optimizing pairing or relocation alone, while remaining practical for online tracking.
Source: §1 · p. 1, §6 · p. 4The paper omits convergence analysis of the solver in this version, stating it will be provided in the journal version.
Source: §5.1 · p. 3
Abstract
from arXiv · showhide
We propose a target tracking method for mobile sensor networks (MSNs) based on time difference-of-arrival (TDOA). Target tracking using an MSN requires reorganizing sensor pairs and relocating sensor positions to obtain TDOAs with higher quality. Existing studies only consider either one while fixing the other, which may limit the tracking accuracy. We address this limitation by simultaneously solving sensor pairing and relocation. We formulate the problem as a maximization of the determinant of the Fisher information matrix, and decompose the problem into two subproblems to solve them alternately. Sensor pairing is solved by a mixed-integer second-order cone program algorithm, and sensor relocation is solved by majorization-minimization. Experimental results show that the proposed method obtains lower tracking error than existing designs with a practical computation time.
1. INTRODUCTION
TDOA supports tracking when targets and sensors are unsynchronized, but measurement quality depends on which sensor pairs are active and where sensors are positioned. The paper jointly optimizes pairing and relocation, reporting lower time-averaged RMSE than methods optimizing either choice alone, with practical online computation time.
1. INTRODUCTION
- TDOA is the difference in signal arrival times at two sensors; only a subset of pairs is activated because measuring every pair may be impractical in energy use and communication overhead.TDOA measurements support localization when targets and sensors operate asynchronously.Source: §1 · p. 1
- TDOA tracking must address both hardware noise, such as clock jitter, and geometry-induced noise, such as multipath effects.The paper describes both noise sources as additive white Gaussian noise, with geometry-induced noise variance proportional to target-to-sensor distances.Source: §1 · p. 1
- TDOA-based tracking has measurement-acquisition and target-localization phases; localization uses measured TDOAs and a maximum-likelihood estimator.Sensors may be relocated and their connections reorganized during measurement acquisition.Source: §1 · p. 1
- Existing pairing and relocation approaches optimize one choice while fixing the other, motivating simultaneous optimization because tracking accuracy depends on both sensor pairs and sensor positions.Pairing methods keep sensor positions fixed, while relocation methods keep pairs fixed.Source: §1 · p. 1
- The method jointly optimizes sensor pairing and relocation by maximizing the D-optimality criterion of the Fisher information matrix, alternating between a MISOCP pairing solver and majorization-minimization relocation under movement constraints.The criterion is evaluated at the current target position.Source: §1 · p. 1
- The proposed method achieves lower time-averaged RMSE than methods optimizing only sensor pairing or only relocation, with practical computation time for online tracking.The introduction reports these results in simulations.Source: §1 · p. 1
2. PRELIMINARIES
The preliminaries define the noiseless pairwise TDOA and model observations with independent Gaussian noise. They then relate target-position estimation accuracy to the Fisher information matrix and its Cramér–Rao bound.
2. PRELIMINARIES
- For a pair connecting sensors i and j, the noiseless TDOA is the difference in target-to-sensor distances divided by propagation speed c.The paper sets c = 1 without loss of generality.Source: §2 · p. 1
- The observation model assumes AWGN independent across pairs, with a variance component that grows with target-to-sensor distances.The model combines fixed-variance noise and distance-dependent noise.Source: §2 · pp. 1–2
- For active pairs, the TDOA covariance is diagonal under the independent-noise assumption, and the Fisher information matrix characterizes position-estimation accuracy.The FIM is given by the Slepian–Bangs formula because both the mean and covariance depend on target position.Source: §2 · p. 2
- Maximizing an optimality criterion of the Fisher information matrix is equivalent to minimizing a lower bound on the variance of an unbiased position estimator.The passage identifies this bound as the Cramér–Rao bound.Source: §2 · p. 2
3. RELATED WORK
Prior sensor-pairing designs select pairs with sensor positions fixed, while relocation designs move sensors with pairs fixed. The paper identifies their unresolved interaction: preferred pairs depend on positions, and preferred positions depend on active pairs.
3. RELATED WORK
- Static pairing minimizes the ROI-averaged determinant of the Cramér–Rao bound and fixes pairs during tracking, whereas dynamic pairing reselects pairs to minimize the bound at the current estimate.Both approaches assume fixed sensor positions.Source: §3 · p. 2
- Relocation updates sensor positions under movement constraints by minimizing the trace of the Cramér–Rao bound, while keeping sensor pairs unchanged during tracking.The cited method updates positions at each time.Source: §3 · p. 2
- Existing designs leave the combined problem unresolved because the best sensor pairs vary with sensor positions, and the best positions depend on the active pairs.Source: §3 · p. 2
4. SIMULTANEOUS PAIRING AND RELOCATION FOR TARGET TRACKING
The method jointly selects active sensor pairs and relocates sensors at each time step to maximize localization information. It alternates between pairing and relocation subproblems under sensing and movement constraints.
4. SIMULTANEOUS PAIRING AND RELOCATION FOR TARGET TRACKING
- The online loop uses previous sensor positions and target estimates to choose new pairs and positions, acquire TDOAs, and estimate the current target position.The operations repeat each time step, assuming the target moves only a limited distance between consecutive slots.Source: §4 · p. 2
4.1. Formulation of Simultaneous Optimization Problem
- At each time step, the design selects K sensor pairs and sensor positions to maximize the determinant of the Fisher information matrix at the previous target estimate.The optimization keeps the active-pair count, movement, region, and keep-out constraints in force.Source: §4.1 · pp. 2–3
4.2. Solver
- Because the joint problem is non-convex, the method alternates between optimizing pair selection with positions fixed and sensor positions with pairs fixed.The pairing subproblem is formulated as a MISOCP solved to a global optimum by branch-and-bound.Source: §4.2 · p. 3
- For fixed pairs, relocation minimizes the non-convex objective using majorization-minimization and feasible-set projection.Each iteration minimizes a quadratic upper bound after a gradient step, then projects onto the feasible set.Source: §4.2 · p. 3
- The alternating algorithm returns the updated pairs and positions after its objective-change stopping test, and is guaranteed to converge to a critical point.The relocation majorization parameter is initialized from the gradient magnitude and doubled until the stated condition is satisfied.Source: §4.2 · p. 3
- The relocation projection handles the keep-out disk by projecting onto the feasible region and, when needed, selecting a nearest point on its boundary.If that boundary point is outside the movement-and-region set, the method compares feasible boundary intersections.Source: §4.2 · p. 3
5. EXPERIMENTS
The experiments compare tracking accuracy and optimization time across active-pair budgets and noise models. The proposed method performs better than other methods except All pairs, with an accuracy advantage at small K and practical per-frame runtime.
5.1. Setting
- Simulations use 12 randomly placed sensors and one target in a 1,000 m square, with 200 independent runs averaged for each method.The target is tracked for 100 frames; sensors move at most 2 m per frame, and K is swept from 11 to 66 under two noise regimes.Source: §5.1 · pp. 3–4
- The paper omits convergence analysis because of space limitations and defers it to the journal version.Source: §5.1 · p. 3
5.2. Results
- The proposed method has lower time-averaged RMSE than all other methods except All pairs, especially at small K, and approaches All pairs around K ≈40–50.Fig. 2 compares accuracy across K under distance-dependent and uniform noise; lower RMSE is better.Source: §5.2 · p. 4, Figure 2 · p. 4
- Proposed-method optimization time exceeds the baselines’ mean per-frame times but remains significantly shorter than the 0.25 s control frame.The reported cost is mean per-frame optimization time.Source: §5.1 · p. 3, §5.2 · p. 4, Figure 2 · p. 4
- In a K = 11 trial, sensors move toward the target only when involved in an active pair, while sensors far from its path remain inactive.Fig. 3 shows snapshots at t = 25, 50, and 75 under distance-dependent noise.Source: §5.2 · p. 4, Figure 3 · p. 4
6. CONCLUSION
The conclusion presents simultaneous sensor pairing and relocation for TDOA-based online tracking. Simulations show improved accuracy over alternative methods within practical online-tracking time.
6. CONCLUSION
- The method alternates a MISOCP for sensor pairing with majorization-minimization for relocation under a D-optimality criterion on the FIM.Source: §6 · p. 4