A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Range-based algorithms <s> 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. <s> BIB001 </s> A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Range-based algorithms <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> BIB002 </s> A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Range-based algorithms <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 </s> A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Range-based algorithms <s> We propose reliable and precise distributed localization algorithms for wireless networks, iterative multidimensional scaling (IT-MDS) and simulated annealing multidimensional scaling (SA-MDS). We use only radio communication constraints to infer a node's distances, and uniquely combine a multidimensional scaling algorithm (MDS) with a lateration algorithm. We analytically establish the upperbound on the estimation error. The proposed techniques can estimate all nodes' positions, even with limited and imprecise network knowledge. Analysis and test runs show that the proposed methods are independent of the topology randomness and the range measurement errors. We attempt to bound the localization imprecision. Simulation results yield an average estimation error of about 25% of radio transmission range. The highest estimation error observed is 40% radio range for most networks. <s> BIB004
Range-based localization algorithms assume all nodes can measure relative distance (or angle) between directly connected nodes in the network. These algorithms mainly focus on static networks with a set of anchor nodes having a priori knowledge of their own positions. Generally, the range-based localization algorithms contain three steps: 1. Through broadcast, each node measures the pair-wise distance (or angle) with each other, and furthermore it can estimate the distance to anchor nodes; 2. Each normal node derives a position based on the anchors' position information; 3. Iteratively refine the position estimation with the constraints of neighbors' information. Various localization algorithms may use different communication methods, and apply special estimation approaches under unique constraints. Doherty et al. provided Convex Position Estimation method  and proposed a set of convex constraint models. The constraint models are general guidelines for all other algorithms BIB001  . Specially, the range-based algorithms can be classified into these categories: BIB003  , and it advanced derivatives by Biaz et al. BIB004 . Note that the first approach is a centralized algorithm. However, the convex constraint models are general and useful for other algorithms. We will start from the constraint models and introduce all algorithms accordingly. Langendoen et al. made an excellent comparison in BIB002 for methods 2, 3, and 4, so we will not explore these methods in detail. In the following sections, we will first introduce various range measurement techniques, and then present the localization algorithms in details.