Localization of ambiguously identifiable wireless agents: complexity analysis and efficient algorithms

摘要

In the localization of wireless agents, ambiguous measurements have significant implications regarding the complexity and quality of the agents’ positioning. Ambiguous measurements occur, for example, in multiple source localization (MSL), in which the goal is to localize the sources of signals, although the signals themselves cannot be used to differentiate among their sources. The indifferentiability of the sources results in a combinatorial optimization problem that must be solved before a localization result can be obtained. Similar effects arise, for example, in the localization of highly resource-limited wireless agents that are subject to severe size and energy constraints, meaning that neither unique identification sequences (CDMA) nor unique frequency or time resources (FDMA, TMDA) can be used. This application scenario constitutes a more general and complex joint problem of localization and ambiguity resolution that also encompasses MSL. In this work, we focus on this more general problem and its corresponding application case while maintaining applicability to the MSL problem. More precisely, we prove the N P $mathcal {NP}$ -hardness of the joint localization and ambiguity resolution problem and derive a solution framework that facilitates a comprehensive and concise formulation thereof. Thereby, we derive a minimum mean square error (MMSE)-optimal algorithm based on mixed-integer nonlinear programming and propose a relaxation of the problem with the aim of reducing the computational complexity. Additionally, simplifications are derived for the case in which bidirectional measurements are available or enforced, e.g., by the applied communication or ranging protocol.