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.
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.
@cite_7 @cite_8 @cite_39 @cite_34 @cite_13
1602370902 1485071356 1581621714 2116790923 2166237942
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. Evolving networks of ad-hoc wireless sensing nodes rely heavily on the ability to establish position information. The algorithms presented herein rely on range measurements between pairs of nodes and the a priori coordinates of sparsely located anchor nodes. Clusters of nodes surrounding anchor nodes cooperatively establish confident position estimates through assumptions, checks, and iterative refinements. Once established, these positions are propagated to more distant nodes, allowing the entire network to create an accurate map of itself. Major obstacles include overcoming inaccuracies in range measurements as great as spl plusmn 50 , as well as the development of initial guesses for node locations in clusters with few or no anchor nodes. Solutions to these problems are presented and discussed, using position error as the primary metric. Algorithms are compared according to position error, scalability, and communication and computational requirements. Early simulations yield average position errors of 5 in the presence of both range and initial position inaccuracies. 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 nodes 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. It is often useful to know the geographic positions of nodes in a communications network, but adding GPS receivers or other sophisticated sensors to every node can be expensive. We present an algorithm that uses connectivity information who is within communications range of whom to derive the locations of the nodes in the network. The method can take advantage of additional information, such as estimated distances between neighbors or known positions for certain anchor nodes, if it is available. The algorithm is based on multidimensional scaling, a data analysis technique that takes O(n3) time for a network of n nodes. Through simulation studies, we demonstrate that the algorithm is more robust to measurement error than previous proposals, especially when nodes are positioned relatively uniformly throughout the plane. Furthermore, it can achieve comparable results using many fewer anchor nodes than previous methods, and even yields relative coordinates when no anchor nodes are available. 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.