Accurate approximation algorithm for TOA-based maximum likelihood mobile location using semidefinite programming

The techniques of using wireless cellular networks to locate mobile stations have recently received considerable interest. This paper addresses the problem of maximum-likelihood (ML) location estimation using (uplink) time-of-arrival (TOA) measurements. Under the standard assumption of Gaussian TOA measurement errors, ML location estimation is a nonconvex optimization problem in which the presence of local minima makes the search of the globally optimal solution hard. To circumvent this difficulty, we propose to approximate the ML problem by relaxing it to a convex optimization problem, namely semidefinite programming. Simulation results indicate that this semidefinite relaxation location estimator provides mean square position error performance close to the Cramér-Rao lower bound for a wide range of TOA measurement error levels.