The sensor network localization, SNL, problem in embedding dimension r, consists of locating the positions of wireless sensors, given only the distances between sensors that are within radio range and the positions of a subset of the sensors (called anchors). Current solution techniques relax this problem to a weighted, nearest, (positive) semidefinite programming, SDP, completion problem, by using the linear mapping between Euclidean distance matrices, EDM, and semidefinite matrices. The resulting SDP is solved using primal-dual interior point solvers, yielding an expensive and inexact solution. This relaxation is highly degenerate in the sense that the feasible set is restricted to a low dimensional face of the SDP cone, implying that the Slater constraint qualification fails. Cliques in the graph of the SNL problem give rise to this degeneracy in the SDP relaxation. In this paper, we take advantage of the absence of the Slater constraint qualification and derive a technique for the SNL problem, with exact data, that explicitly solves the corresponding rank restricted SDP problem. No SDP solvers are used. For randomly generated instances, we are able to efficiently solve many huge instances of this NP-hard problem to high accuracy, by finding a representation of the minimal face of the SDP cone that contains the SDP matrix representation of the EDM. The main work of our algorithm consists in repeatedly finding the intersection of subspaces that represent the faces of the SDP cone that correspond to cliques of the SNL problem.
@cite_27: An adaptive rule-based algorithm, SpaseLoc, is described to solve localization problems for ad hoc wireless sensor networks. A large problem is solved as a sequence of very small subproblems, each of which is solved by semidefinite programming relaxation of a geometric optimization model. The subproblems are generated according to a set of sensor anchor selection rules. Computational results compared with existing approaches show that the SpaseLoc algorithm scales well and provides excellent localization accuracy.
@cite_7: 
@cite_6: An adaptive rule-based algorithm, SpaseLoc, is described to solve localization problems for ad hoc wireless sensor networks. A large problem is solved as a sequence of very small subproblems, each of which is solved by semidefinite programming relaxation of geometric optimization model. The subproblems are generated according to a set of sensor anchor selection rules and a priority list. Computational results compared with existing approaches show that the SpaseLoc algorithm scales well and provides excellent, positioning accuracy. A dynamic version of the SpaseLoc method is developed for estimating proving sensors locations in a real-time environment. The method uses dynamic distance measurement updates among sensors, and utilizes SpaseLoc for static sensor localization. Further computational results are presented, along with an application to bus transit systems. Ways to deploy sensor localization algorithms in clustered distributed environments are also studied, permitting application to arbitrarily large networks. In addition, we extend the algorithm to solving sensor localizations in 3D space. A preprocessor is developed to enable SpaseLoc: for localization of networks without absolute position information.* *Joint research conducted in the Dept of Management Science and Engineering, Stanford University.
@cite_27 @cite_6 propose the SpaseLoc heuristic. It is limited to @math and uses an solver for small localized subproblems. They then sew these subproblems together. So & Ye @cite_7 show that the problem of solving a noiseless with a unique solution can be phrased as an and thus can be solved in polynomial time. They also give an efficient criterion for checking whether a given instance has a unique solution for @math .