A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Reported precision <s> Many ad hoc network protocols and applications assume the knowledge of geographic location of nodes. The absolute location of each networked node is an assumed fact by most sensor networks which can then present the sensed information on a geographical map. Finding location 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. Location would also enable routing in sufficiently isotropic large networks, without the use of large routing tables. We are proposing APS - a distributed, hop by hop positioning algorithm, that works as an extension of both distance vector routing and GPS positioning in order to provide approximate location for all nodes in a network where only a limited fraction of nodes have self location capability. <s> BIB001 </s> A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Reported precision <s> 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. <s> BIB002 </s> A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Reported precision <s> We consider the problem of node positioning in ad-hoc networks. We propose a distributed, infrastructure-free positioning algorithm that does not rely on Global Positioning System (GPS). The algorithm uses the distances between the nodes to build a relative coordinate system in which the node positions are computed in two dimensions. The main contribution of this work is to define and compute relative positions of the nodes in an ad-hoc network without using GPS. We further explain how the proposed approach can be applied to wide area ad-hoc networks. <s> BIB003 </s> A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Reported precision <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> BIB004 </s> A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Reported precision <s> Position centric approaches, such as Cartesian routing, geographic routing, and the recently proposed trajectory based forwarding (TBF), address scalability issues in large ad hoc networks by using Euclidean space as a complementary name space. These approaches require. that nodes know their position in a common coordinate system. While a GPS receiver in each node would be ideal, in many cases an approximation algorithm is necessary for networks with only a few GPS enabled nodes. These algorithms however require collaboration of large portions of the network, thus imposing an overhead for nodes which do not need positioning, or are mobile. We propose Local Positioning System (LPS), a method that makes use of local node capabilities-angle of arrival, range estimations, compasses and accelerometers, in order to internally position only the groups of nodes involved in particular conversations. Localized positioning enables position centric uses, like discovery, flooding and routing in networks where global positioning is not available. <s> BIB005 </s> A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Reported precision <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> BIB006 </s> A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Reported precision <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> BIB007 </s> A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Reported precision <s> A novel task-oriented self-organization algorithm that accounts for mostly location-dependent tasks and heterogeneous sensors inherent in dense ad-hoc sensor systems is proposed. It forms a sensor group for an announced task by sequentially selecting the best matched sensors using a leader election algorithm and a residual task calculation algorithm. To improve the associated communication overhead, the sensor node location information is used in task broadcasting, thus confining the algorithm implementation to a dynamically maintained contributor group which comprises of those sensors which may contribute to the task. Sensor localization is based on a refinement of an algorithm in which utilizes only the neighborhood information of each sensor node corresponding to its each preset radio transmission power level. The proposed self-organization algorithm and how various system parameters affect its performance are examined via extensive simulations. In a densely deployed sensor system, when the refined localization scheme is demonstrated to achieve very good localization, the proposed self-organization algorithm consistently yields a sensor group that covers the announced task. <s> BIB008 </s> A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Reported precision <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> BIB009
The best result is reported by Savvides et al. in BIB004  . The testing setting is a network with 20% anchor nodes, more than six neighbors for each node, and the effective radio range is 15m. With multilateration localization method, the average error was 27.7mm with a standard deviation of 16mm. The simulation is based on the measurement noise parameters of a ultrasonic distance measurement system. The probability algorithm by Ramadurai et al.  shows a test-bed of 60m×60m, with 5 anchors and 8 normal nodes. The radio range is 20m. The average precision error is about 9.4m, which is 47% radio range. If the GPS position estimation error is around 5m, this means the probability approach is pretty good. The ad-hoc positioning system by Niculescu et al. BIB001 BIB005 considers both an isotropic and anisotropic topology with 100 nodes, and an average node degree of 7.6. The radio range is 10. The results show that the algorithm works better in isotropic topology. In isotropic environment, the error is about 35% radio range with 10% anchors density, and about 25% radio range under 20% anchors density. For anisotropic topology, the error is about 100% radio range for 10% anchors, and about 90% with 20% anchors. Robust algorithm by Savarese et al. BIB002 assumes an average connectivity level of 7 or higher, with an anchor density of more than 5%, a relatively consistent error level of less than 33% (radio range) is achieved. Convex positioning by Doherty et al.  does not provide similar precision estimation as the above algorithms, however, the research points out that the connectivity can improve precision dramatically, and the capability of variable radius radio transmission will help the localization precision. Multidimensional scaling algorithm (MDS) by X. Ji BIB007 did not specifically provide a quantitative value; however, the research showed that the algorithm is less dependent on the radio pattern and the special terrain topology. Also, it concluded that the algorithm can achieve good estimation for a network with only 10% anchor nodes. The advanced MDS algorithms in BIB009 give a relative bounded estimation error of 40% (in terms of radio range) for most network settings. Geometric grid overlaying (GGO) algorithm by Premaratne et al. BIB008 uses a test-bed of dense sensor system with very few reference nodes. For example, a 30×30 grid network contains 200 nodes (five anchor nodes), the localization accuracy of less than 15% of radio range can be achieved. Approximate Point-In-Triangulation Test (APIT) algorithm by He et al.  relies more on the received anchor information, with optimal estimation error of about 45% radio range in uniform deployment environment, and about 50% radio range in random deployed networks. The advantage of the APIT algorithm is that it is less affected by connectivity as long as a degree of six can be maintained. Also, APIT is independent on the topology, radio pattern and the range measurement errors. The Amorphous algorithm by Nagpal et al. BIB006 uses Kleinrock's formula  to estimate the average hop distance. For simulation run, four anchor nodes are placed at corner, and all others (total 200 sensors) are random placed in a square region of 6R×6R (R is the radio range). The simulation results show that position accuracy of 20% to 30% radio range can be achieved. Relative localization algorithms by Capkum et al. in BIB003 , and by Niculescu et al. in BIB005 construct a local positioning system that can provide sufficient location information and support network functions. Because of the relative nature of the algorithm, both systems did not provide similar localization precision as the absolute positioning algorithms. However, the simulation results show that precision of range measurement is critical to the relative localization algorithms. With the aid of angular measurements (even with high errors), the overall performance is enhanced.