A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Algorithm comparison <s> 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. <s> BIB001 </s> A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Algorithm comparison <s> 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. <s> BIB002 </s> A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Algorithm comparison <s> Sensor Positioning is a fundamental and crucial issue for sensor network operation and management. In the paper, we first study some situations where most existing sensor positioning methods tend to fail to perform well, an example being when the topology of a sensor network is anisotropic. Then, we explore the idea of using dimensionality reduction techniques to estimate sensors coordinates in two (or three) dimensional space, and we propose a distributed sensor positioning method based on multidimensional scaling technique to deal with these challenging conditions. Multidimensional scaling and coordinate alignment techniques are applied to recover positions of adjacent sensors. The estimated positions of the anchors are compared with their true physical positions and corrected. The positions of other sensors are corrected accordingly. With iterative adjustment, our method can overcome adverse network and terrain conditions, and generate accurate sensor position. We also propose an on demand sensor positioning method based on the above method. <s> BIB003
In this section, we will briefly compare all range-based localization algorithms in term of terrain dependence, radio pattern requirement, range estimation error, and others. • Terrain effects on distance measurement methods: Different environment has different signal attenuation factor, so the radio transmission range and node's connectivity are dependent on the operating environment. For all radio propagation methods, only Euclidean method offers predictable performance across unpredictable conditions. Other methods (like DV-based methods and Kleinrock's formula) behave well only in isotropic topology, however they are less complex. • Radio Pattern dependence: Convex algorithm and Probability localization algorithms assume perfect circular radio pattern, while others rely less on this assumption. • Range error sensitivity: to estimate the distance between nodes, The DV-hop propagation scheme and the Kleinrock's formula do not require the range measurement. In other words, if distance between communicating neighbors can be measured accurately, Euclidean propagation method provides precise range estimates. For the localization algorithms, Probability algorithm, Convex algorithm and MDS algorithms (including its advanced derivatives) are relatively less sensitive to the range measurement errors. Probability algorithm is based on the probability distribution of the signal strength, and it picks only those coordinates with highest probability as final estimates. Convex algorithm uses global constraints that can potentially minimize the measurement errors. MDS algorithms base on the anchors positions, and by using iteration or simulated annealing techniques, the position estimates can converge to the true position optimally. • Density requirement: the density includes both anchors' density and overall nodes' connectivity. Most algorithms assume a high density and fully connected network. For simulation runs, most algorithms use connection degree of 7.5 (in term of neighbors per node) and above. For example, BIB001 found that a minimum connectivity of 9.0 is required for DV-hop and Sum-dist propagation methods. For Kleinrock's formula to work, the local density (in term of all nodes within unity area) of 10~15 is necessary BIB002 . More anchors will generally help the performance of localization algorithms; however, too many anchors will cause more interference. BIB003 found that about 10% anchor nodes is good enough to get minimum error estimation. Pure increment of anchors will not bring much improvement in position estimation. • Communication cost: communication occurs mostly at the first step and the third step. In first step, anchor nodes broadcast their position information to the network, and at the third step, each normal node advertises its position estimates to their neighbors. The Convex and MDS algorithms mostly rely on the first step communication, thus they are communication efficient. Different from these two methods, other algorithms have to rely on the extensive communication with neighbors in order to collect further constraints for refinement. • Precision: The precision can be evaluated in two phases: phase 1 corresponds to the range estimation in radio propagation step, and the phase 2 corresponds to the position estimation and refinement steps. [29] and BIB001 compared various propagation methods. The accuracy is measured against the anchor fraction (or anchor density). It is found that Euclidean method achieves higher accuracy when the anchor density increases. And DV-based methods perform better when the anchor density is low. However, only Euclidean can work in anisotropic topology. The localization accuracy of the localization algorithms is dependent on the anchor density, the range measurement performance and the connectivity condition. Lower range estimation error, higher connectivity and higher anchor density will give better estimates for all algorithms. It is further found that the MDS algorithm tends to generate more accurate position estimates at less dense networks, where small number of nodes are deployed. We will provide the precision for all algorithms from their original research in section 6.1. In addition, we will compare the estimation performance of a set of representative algorithms in section 6.2.