Polynomial Time Approximation Algorithms for Localization Based on Unknown Signals

摘要

We consider the problem of anchor-free self-calibration of receiver locations using only the reception time of signals produced at unknown locations and time points. In our settings the receivers are synchronized, so the time differences of arrival (TDOA) of the signals arriving at the receivers can be calculated. Given the set of distinguishable time points for all receivers the task is to determine the positions of the receivers as well as the signal sources. We present the first polynomial time approximation algorithms for the minimum problem in the plane, in which the number of receivers is four, respectively the number of signals is three. For this, we first consider the problem that the time points of m signals are jittered by at most some ∈ ＞ 0. We provide an algorithm which tests whether n given receiver positions are feasible with respect to m unknown sender positions with a runtime of (Ο)(nm~2) and we provide an algorithm with run-time (Ο)(nm log m) which tests the feasibility of m given sender positions for n unknown sender positions. Using these tests, we can compute all possible receiver and signal source positions in time (Ο) ((2~(1/2)/∈)~(2n-3)n~2m), respectively (Ο) ((2~(1/2)/∈)~(2m-3)nm log m).