A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Range-free algorithms <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> BIB001 </s> A survey and comparison on localisation algorithms for wireless ad hoc networks <s> Range-free algorithms <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> BIB002
Range-free localization algorithms do not assume the range measurement capability so as to estimate distance between communicating nodes. However, in order to determine the node's location, each node still needs to use some mechanism to estimate the relative distance to anchors. One approach is the use of the Kleinrock's formula (section 2.3.1}), which estimates the average hop distance only based on local neighborhood density in a uniformly deployed network. Consequently, if a prior knowledge of the local neighborhood density is given, the average hop distance can be calculated and then any range-based method in section 2.4 can be used. Nagpal et al. BIB001  use multilateration to estimate the nodes' position, and it is called Amorphous localization algorithm. However, Kleirock's formula can only be used in densely deployed networks. For more general networks, special transmitters may be used to assist the localization procedure. For example, Premaratne et al. in BIB002 assumes that anchors can transmit radio signals with multiple level transmission powers. And in  , He et al. uses highpowered transmitters. These two transmission methods will let anchors cover much larger areas. Consequently, with these special transmitters, an anchor can send beacon packets directly to normal nodes that are far away from the anchor itself. When a normal node obtains enough information about the surrounding anchor nodes, Premaratne's method allows the normal node to estimate its position by grid overlaying all possible regions it may reside in. We call this method geometric grid overlaying (GGO). In contrast, He's method isolates the area into multiple triangular regions and use approximate point-in-triangulation Test (APIT) to obtain the position estimates. In the following sections, we will introduce these two methods.