text: We consider the problem of localizing wireless devices in an ad-hoc network embedded in a d-dimensional Euclidean space. Obtaining a good estimation of where wireless devices are located is crucial in wireless network applications including environment monitoring, geographic routing and topology control. When the positions of the devices are unknown and only local distance information is given, we need to infer the positions from these local distance measurements. This problem is particularly challenging when we only have access to measurements that have limited accuracy and are incomplete. We consider the extreme case of this limitation on the available information, namely only the connectivity information is available, i.e., we only know whether a pair of nodes is within a fixed detection range of each other or not, and no information is known about how far apart they are. Further, to account for detection failures, we assume that even if a pair of devices is within the detection range, it fails to detect the presence of one another with some probability and this probability of failure depends on how far apart those devices are. Given this limited information, we investigate the performance of a centralized positioning algorithm MDS-MAP introduced by , and a distributed positioning algorithm, introduced by , called HOP-TERRAIN. In particular, for a network consisting of n devices positioned randomly, we provide a bound on the resulting error for both algorithms. We show that the error is bounded, decreasing at a rate that is proportional to R Rc, where Rc is the critical detection range when the resulting random network starts to be connected, and R is the detection range of each device.
  @cite_41: We consider the problem of positioning a cloud of points in the Euclidean space ℝ d , using noisy measurements of a subset of pairwise distances. This task has applications in various areas, such as sensor network localization and reconstruction of protein conformations from NMR measurements. It is also closely related to dimensionality reduction problems and manifold learning, where the goal is to learn the underlying global geometry of a data set using local (or partial) metric information. Here we propose a reconstruction algorithm based on semidefinite programming. For a random geometric graph model and uniformly bounded noise, we provide a precise characterization of the algorithm’s performance: in the noiseless case, we find a radius r 0 beyond which the algorithm reconstructs the exact positions (up to rigid transformations). In the presence of noise, we obtain upper and lower bounds on the reconstruction error that match up to a factor that depends only on the dimension d, and the average degree of the nodes in the graph.
  @cite_28: We consider a problem of considerable practical interest: the recovery of a data matrix from a sampling of its entries. Suppose that we observe m entries selected uniformly at random from a matrix M. Can we complete the matrix and recover the entries that we have not seen? We show that one can perfectly recover most low-rank matrices from what appears to be an incomplete set of entries. We prove that if the number m of sampled entries obeys m >= C n^ 1.2 r log n for some positive numerical constant C, then with very high probability, most n by n matrices of rank r can be perfectly recovered by solving a simple convex optimization program. This program finds the matrix with minimum nuclear norm that fits the data. The condition above assumes that the rank is not too large. However, if one replaces the 1.2 exponent with 1.25, then the result holds for all values of the rank. Similar results hold for arbitrary rectangular matrices as well. Our results are connected with the recent literature on compressed sensing, and show that objects other than signals and images can be perfectly reconstructed from very limited information.
  @cite_9: Calibration of ultrasound tomography devices is a challenging problem and of highly practical interest in medical and seismic imaging. This work addresses the position calibration problem in circular apertures where sensors are arranged on a circular ring and act both as transmitters and receivers . We introduce a new method of calibration based on the timeof-flight (ToF) measurements between sensors when the enclo sed medium is homogeneous. Knowing all the pairwise ToFs, one can find the positions of the sensors using multi-di mensional scaling (MDS) method. In practice, however, we are facing two major sources of loss. One is due to the transitional behaviour of the sensors, which makes the ToF measurements for close-by sensors unavailable. The other is due to the random malfunctioning of the sensors, that leads to random missing ToF measurements. On top of the missing entries, since in practice the impulse response of the piezoelectric and the time origin in the measurement procedure are not present, a time mismatch is also added to the measurements. In this work, we first show that a matrix defined from all the ToF measurements is of rank at most four. In order to estimate the structured and random missing entries, utilizing the fact that the matrix in question is shown to be low-rank, we apply a state-of-the-art low-rank matrix completion algorithm. Then we use MDS in order to find the correct positions of the sensors. To confirm the function ality of our method in practice, simulations mimicking the measurements of an ultrasound tomography device are performed.
  @cite_36: Given a matrix M of low-rank, we consider the problem of reconstructing it from noisy observations of a small, random subset of its entries. The problem arises in a variety of applications, from collaborative filtering (the 'Netflix problem') to structure-from-motion and positioning. We study a low complexity algorithm introduced by Keshavan, Montanari, and Oh (2010), based on a combination of spectral techniques and manifold optimization, that we call here OPTSPACE. We prove performance guarantees that are order-optimal in a number of circumstances.
  @cite_17: This paper focuses on the principled study of distance reconstruction for distance-based node localization. We address an important issue in node localization by showing that a highly incomplete set of inter-node distance measurements obtained in ad-hoc node deployments carries sufficient information for the accurate reconstruction of the missing distances, even in the presence of noise and sensor node failures. We provide an efficient and provably accurate algorithm for this reconstruction, and we show that the resulting error is bounded, decreasing at a rate that is inversely proportional to radicn, the square root of the number of nodes in the region of deployment. Although this result is applicable to many localization schemes, in this paper we illustrate its use in conjunction with the popular multidimensional scaling algorithm. Our analysis reveals valuable insights and key factors to consider during the sensor network setup phase, to improve the quality of the position estimates
summary: Of particular interest are the two new results on the performance of sensor localization algorithms. In @cite_41 , proposes a new reconstruction algorithm based on semidefinite programming where they could establish lower and upper bounds on the reconstruction errors of their algorithm. Similarly, in @cite_9 , due to new advances in matrix completion methods @cite_28 , the authors analyse the performance of OptSpace @cite_36 , a novel matrix completion algorithm, in localizing the sensors. Interestingly, they did not need to adhere to the assumptions made by @cite_17 . However, they have a restrictive assumption about the topology of the network, specifically, sensors are scattered inside an annulus.