A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Algorithm optimization <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> Algorithm optimization <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 optimization <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> BIB003
Along the study, we also tested some of the introduced algorithms, including multidimensional algorithm (MDS) and multilateration algorithm. During simulation, we found that the following optimizations may be important: First, the placement of the anchor nodes can heavily influence the algorithms' performance. As stated in BIB001 , most anchor nodes should be placed on the perimeter of the network. In  , Doherty also shows that with as few as four known positions placed around the perimeter of the network, the estimate will result in smaller errors. Again, in BIB002 , four anchor nodes are manually placed at the corner of the simulation area. The perimeter deployment is important for the multidimensional scaling algorithm (MDS) because the algorithm only estimates those positions along a propagation path, with a constraint that the starting point and ending points of the path should both be anchor nodes. In most cases, the nodes around perimeter will never get their position predicted, or some special propagation methods will have to be used in order to involve them into the routing paths. Though it is not discussed in BIB003  , we believe that the perimeter deployment should also be important for the APIT and GGO algorithms. Second, the combination of some algorithms may produce better performance. The improvement includes higher precision, less processing time and more estimation coverage. For example, for MDS algorithm, even with perimeter deployment strategy, it may still not be able to predict all normal nodes' position. In this case, multilateration algorithm can simply be activated by those nodes that need their positions. After the initial MDS algorithm, those normal nodes, which did not get position predicted, may have already had information about anchor nodes and also their neighboring nodes. Consequently, the execution of multilateration algorithm will not cause much overhead in terms of communication. Third, the radio constraints model is important for most localization algorithms. Applying the radio constraints to the iterative refinement phase increases the convergence speed in general.