A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Propagation methods <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> Propagation methods <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> Propagation methods <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> BIB003
In this section, we will introduce the propagation method. • DV-Hop or Hop-Terrain propagation method: In this method, each node only communicates with its immediate neighbors as in distance vector routing. Starting from an anchor node, hop by hop information propagation allows a node to determine its distance, in hops, to that anchor. Note that during the message propagation, each node only maintains and rebroadcasts packets with the smallest number of hop counts. The minimum hop counts that nodes retain will eventually be the length of the shortest path to the anchor. The distance to the anchor nodes is determined as the product of the hop counts and the average hop distance. The average hop distance is determined by anchor nodes dynamically. When an anchor node receives a packet containing position information from other anchors, it can estimate the hop counts and the actual distance between them, and the average hop distance is obtained by averaging the distance with corresponding hop counts BIB001 . To avoid expensive flooding, a simple method of determining the average hop distance is to use the maximum radio range directly BIB002 . The advantage of the DV-Hop method is that it may allow fewer anchors for the initial estimation, and it work well in uniform networks. • DV-Distance or Sum-dist propagation method: This method works similarly to DVHop, the difference is that each node now measures the pair-wise distance between neighboring nodes. The hop by hop information propagation transmits the cumulative distance instead of hop counts. Same as DV-Hop method, each node only selects and rebroadcasts packets with minimum distance to the anchors. Compared with DV-Hop, to estimate nodes' position, this method is sensitive to measurement error because of the cumulative effect. However, this method is less coarse than the previous and may still perform well in randomly deployed networks. • Euclidean propagation method: This method is based on the local geometry of nodes around the anchor. It assumes that the network is densely populated. An anchor node initiates the propagation process by flooding its own position information in a beacon packet. Upon receiving the message, intermediate nodes can estimate their distance to the anchor and rebroadcast the message with added distance information of their own. If node (A) receives messages from two neighbors (B and C) coming from the same anchor (D), and if the two neighbors (B and C) are also neighbors with each other (shown in Figure 2 ), then a quadrilateral (ABDC) may be formed with the knowledge of all sides and one diagonal. Note that node A can estimate its distance to B and C; and the diagonal is the distance from B to C, which can be determined since B and C are neighbors. The determination of the other diagonal (AD) is trivial, and the diagonal is the distance from node A to anchor D. The algorithm allows all nodes to estimate their distance to the anchor node, and it works from the inner most circle to the faraway outside like a circular-wave form centered at that anchor. The advantage of this method is that it obtains precise distance estimation to the anchor node even under random deployment networks. However, it is complex and only works in high-density networks. Furthermore, the error from pair-wise distance estimation is cumulative. • Kleinrock's formula: Kleinrock and Silvester  showed that the average hop distance d hop for a dense network depends only on local neighborhood density N: Nagpal et al. measured the average hop distance with variance N over several simulations from a random source BIB003 . Results validate Kleinrock's formula that it slightly underestimates the measured average hop distance. Nagpal further noticed that N of 15 is a critical minimal threshold for achieving low errors in distance estimation.