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_7: The recent advances in MEMS, embedded systems and wireless communication technologies are making the realization and deployment of networked wireless microsensors a tangible task. In this paper we study node localization, a component technology that would enhance the effectiveness and capabilities of this new class of networks. The n-hop multilateration primitive presented here, enables ad-hoc deployed sensor nodes to accurately estimate their locations by using known beacon locations that are several hops away and distance measurements to neighboring nodes. To prevent error accumulation in the network, node locations are computed by setting up and solving a global non-linear optimization problem. The solution is presented in two computation models, centralized and a fully distributed approximation of the centralized model. Our simulation results show that using the fully distributed model, resource constrained sensor nodes can collectively solve a large non-linear optimization problem that none of the nodes can solve individually. This approach results in significant savings in computation and communication, that allows fine-grained localization to run on a low cost sensor node we have developed.
  @cite_8: A distributed algorithm for determining the positions of nodes in an ad-hoc, wireless sensor network is explained in detail. Details regarding the implementation of such an algorithm are also discussed. Experimentation is performed on networks containing 400 nodes randomly placed within a square area, and resulting error magnitudes are represented as percentages of each node’s radio range. In scenarios with 5 errors in distance measurements, 5 anchor node population (nodes with known locations), and average connectivity levels between neighbors of 7 nodes, the algorithm is shown to have errors less than 33 on average. It is also shown that, given an average connectivity of at least 12 nodes and 10 anchors, the algorithm performs well with up to 40 errors in distance measurements.
  @cite_39: We demonstrate that it is possible to achieve accurate localization and tracking of a target in a randomly placed wireless sensor network composed of inexpensive components of limited accuracy. The crucial enabler for this is a reasonably accurate local coordinate system aligned with the global coordinates. We present an algorithm for creating such a coordinate system without the use of global control, globally accessible beacon signals, or accurate estimates of inter-sensor distances. The coordinate system is robust and automatically adapts to the failure or addition of sensors. Extensive theoretical analysis and simulation results are presented. Two key theoretical results are: there is a critical minimum average neighborhood size of 15 for good accuracy and there is a fundamental limit on the resolution of any coordinate system determined strictly from local communication. Our simulation results show that we can achieve position accuracy to within 20 of the radio range even when there is variation of up to 10 in the signal strength of the radios. The algorithm improves with finer quantizations of inter-sensor distance estimates: with 6 levels of quantization position errors better than 10 are achieved. Finally we show how the algorithm gracefully generalizes to target tracking tasks.
  @cite_34: This paper studies the problem of determining the node locations in ad-hoc sensor networks. We compare three distributed localization algorithms (Ad-hoc positioning, Robust positioning, and N-hop multilateration) on a single simulation platform. The algorithms share a common, three-phase structure: (1) determine node-anchor distances, (2) compute node positions, and (3) optionally refine the positions through an iterative procedure. We present a detailed analysis comparing the various alternatives for each phase, as well as a head-to-head comparison of the complete algorithms. The main conclusion is that no single algorithm performs best; which algorithm is to be preferred depends on the conditions (range errors, connectivity, anchor fraction, etc.). In each case, however, there is significant room for improving accuracy and or increasing coverage.
  @cite_13: Many ad hoc network protocols and applications assume the knowledge of geographic location of nodes. The absolute position of each networked node is an assumed fact by most sensor networks which can then present the sensed information on a geographical map. Finding position without the aid of GPS in each node of an ad hoc network is important in cases where GPS is either not accessible, or not practical to use due to power, form factor or line of sight conditions. Position would also enable routing in sufficiently isotropic large networks, without the use of large routing tables. We are proposing APS --- a localized, distributed, hop by hop positioning algorithm, that works as an extension of both distance vector routing and GPS positioning in order to provide approximate position for all nodes in a network where only a limited fraction of nodes have self positioning capability.
summary: Perhaps a more practical and interesting case is when there is no central infrastructure. @cite_34 identifies a common three-phase structure of three, popular, distributed sensor-localization algorithms, namely robust positioning @cite_8 , ad-hoc positioning @cite_13 and N-hop multilateration @cite_7 . Table illustrates the structure of these algorithms. In the first phase, nodes share information to collectively determine the distances from each of the nodes to a number of anchors. Anchors are special nodes with a priori knowledge of their own position in some global coordinate system. In the second phase, nodes determine their position based on the estimated distances to the anchors provided by the first phase and the known positions of the anchors. In the last phase, the initial estimated positions are iteratively refined. It is empirically demonstrated that these simple three-phase distributed sensor-localization algorithms are robust and energy-efficient @cite_34 . However, depending on which method is used in each phase, there are different tradeoffs between localization accuracy, computation complexity and power requirements. In @cite_39 , a distributed algorithm-called the Gradient algorithm- was proposed; it is similar to ad-hoc positioning @cite_13 but uses a different method for estimating the average distance per hop.