An Outer Approximate Approach to TOA-Based Multiple Source Localization Proble

Source localization is an important research topic and has various applications such as position location in cellular networks, missile guidance systems, emergency response and target tracking. Moving beyond the widely studied single source localization (SSL) problem, the multiple sources localization (MSL) problem which is a mixed integer, nonconvex problem is paid less of attention due to the computational complexity and non-convex property. As the large number source localization problem has wide applications, it is worth to study how to solve this kind of problem efficiently. Consider 1st order method (Taylor-series expansion) cannot guarantee to get the global optimal solution of a non-convex problem, and semidefinite relaxation (SDR) cannot anticipate the rank of the related optimal solution equals 1, so these methods provide limited performance.;Motivated by this, we propose an outer approximate approach (OAA) method to solve this time of arrival based multiple sources localization (TOA-MSL) problem. We show that through some relaxations and constructing specific bounds to semidefinite variables, we get a mixed integer (MI), semidefinite program (SDP), second order cone program (SOCP) problem which can be solved efficiently by the OAA method with non-exponential complexity.;Especially, using the property of disordered-TOA to construct a tight upper bound to the diagonal variables of the SDPs, numerical results show that only a few iteration steps of the OAA algorithm can get the optimal integer solution for the noisy case. We show that if the number of the sensors M is no less than max (L + 1, K!( L -- 1) + 1), the locations of the sources is in the convex hull constructed by the sensors and sources location matrix s ∈ RLxM is full of row rank, then the solution of the TOA is unique. Assume the locations of the source is in the convex hull constructed by the sensors, L = 2 or 3, then we only need L sensors' information to fix the unique source localization.;In order to improve the computational complexity of solving the mix-integer (MI) subproblem, we compared the performance of several commercial solvers such as CPLEX, MOSEK and GUROBI (CPLEX and GUROBI use interior point method based branch and bound method to solve the mixed integer problem). GUROBI has higher computational efficiency to solve the MI subproblem. The performance of handle the SDP subproblem, MOSEK is better than others.;We then derive the Cramer-Rao Lower Bound (CRLB) for the TOA-MSL problem and numerical results show that the OAA algorithm achieves the CRLB accuracy if the TOA measurements are subject to small Gaussian-distributed errors. We then apply the OAA method to solve the TDOA-MSL problem, numerical experiments are presented to corroborate our theoretical results. For the TOA-MSL problem we prove that the SDR variable D in the relaxed problem is equivalent to the original variable d, and the SDR variable X is partially equivalent to the original variable x.;Outer approximation approach method is not only used to solve the above MSL problem but also can be used to solve general problem with mixed integer, SDP, and SOCP.