A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Figure 1 Radio communication constraints <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> BIB001 </s> A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Figure 1 Radio communication constraints <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> BIB002 </s> A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Figure 1 Radio communication constraints <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> BIB003
• Hop-count method in BIB001 , in this method, if a node receives multiple packets from the same anchor node, it maintains and rebroadcasts the one with the least hop counts while ignoring all the rest. This optimization will eventually lead to a shortest path to the anchors. • Time stamp method BIB002 , in which a time to live (TTL) stamp is appended to each beacon packet. Out-dated packets are dropped silently. To estimate the distance to anchor nodes, several different methods have been proposed. Based on the local neighborhood density, in  Kleinrock and Silvester provided a formula for the average distance between nodes. We present later this formula as Kleinrock's formula. Based on the information flooding, Niculescu BIB002 presented three methods: DV-Hop propagation method, DV-Distance method and Euclidean method. These methods are commonly used in many localization algorithms. For example, method Hop-Terrain by Savarese is similar to DV-Hop BIB002 ; and method Sumdist by Savvides is essentially the DV-Distance method BIB003 . In the next section, we will briefly introduce these radio propagation methods.