Abstract. Recently, a semidefinite programming (SDP) relaxation approach has been proposed to solve the sensor network localization problem. Although it achieves high accuracy in estimating the sensor locations, the speed of the SDP approach is not satisfactory for practical applications. In this paper we propose methods to further relax the SDP relaxation, more precisely, to relax the single semidefinite matrix cone into a set of small-size semidefinite submatrix cones, which we call a sub-SDP (SSDP) approach. We present two such relaxations. Although they are weaker than the original SDP relaxation, they retain the key theoretical property, and numerical experiments show that they are both efficient and accurate. The speed of the SSDP is even faster than that of other approaches based on weaker relaxations. The SSDP approach may also pave a way to efficiently solving general SDP problems without sacrificing the solution quality. Key words. sensor network localization, semidefinite programming, second-order cone programming, principal submatrix, chordal graph AMS subject classifications. 90C22, 49M20, 65K05 DOI. 10.1137/060669395 1. Introduction. There has been an increase in the use of ad hoc wireless sensor networks for monitoring environmental information (e.g., temperature, sound levels, and light) across an entire physical space, where the sensor network localization problem has received considerable attention recently. Typical networks of this type consist of a large number of densely deployed sensor nodes which gather local data and communicate with other nearby nodes. The sensor data from these nodes are relevant only if we know to what location they refer. Therefore knowledge of the node positions becomes imperative. The use of a GPS system could be a very expensive or otherwise impossible approach to this requirement. This problem is also related to other practical distance geometry problems. The mathematical model of the problem can be described as follows. There are n distinct sensor points in R d , whose locations are to be determined, and m other fixed points (called the anchor points), whose locations a 1 , a 2 , . . . , a m are known. The Euclidean distance d ij between the ith and jth sensor points is known if (i, j) ∈ N x , and the distanced ik between the ith sensor and kth anchor points is known if (i, k) ∈ N a . Usually, N x = {(i, j) : where r d is a fixed parameter called the radio range. The sensor network
For instance, semi-definite programming relaxation approaches and its extended approaches has been proposed to solve it REF .
Further relaxation of the semidefinite programming approach to sensor network localization
SIAM Journal on Optimization
Computer Science Mathematics