## 3 Localization Algorithms in WSNs
### Range Free Localization Algorithm
#### 3.1.1 Hop Count Based  
Almost all the range free localization techniques mainly use hop count based information to calculate the position. DV-Hop [52] and Centroid [36] are the pioneering approaches of this type. Centroid is designed for sensor nodes which have at least three neighbor anchor nodes. Assume that the sensor node \(N\) has three neighbor anchors \(A_{1}\), \(A_{2}\), \(A_{3}\), whose coordinates are \((x_{1},y_{1})\), \((x_{2},y_{2})\), and \((x_{3},y_{3})\), and all nodes have equal communication range. The principle of Centroid is to regard the central point Ncentroid of anchors as the estimated position. The position of Ncentroid, denoted as (xcentroid, ycentroid) could be calculated as \((xcentroid,ycentroid)=((x_{1}+x_{2}+x_{3})/3,(y_{1}+y_{2}+y_{3})/3)\). Centroid has very low communication and computation cost, and can get relatively good accuracy when the distribution of anchors is regular. However, when the distribution of anchors is not even, the estimated position derived from the Centroid algorithm will be inaccurate. On the other hand, the hop count based method DV-Hop and hop-terrain [66] requires small number of anchors. DV-Hop plays an essential role in many localization methods to give primal distance estimation from sensor nodes to anchor nodes. DV-Hop propagates distance estimation among anchor nodes represented by number of hops throughout a WSN. Anchor nodes can then estimate the average distance of each hop, with which each sensor node calculates its estimated distances to anchor nodes. By multilateration, the location is then calculated as follows:  
Let \((x,y)\) be the unknown node \(D^{\prime}\)s location and \((x_{i},y_{i})\) be the known location of the \(i^{\prime}th\) anchor node receiver. Let's say the \(i^{\prime}th\) anchor node distance to unknown nodes are \(d_{i}\) and the total number of anchors deployed in the network is n. Then, here is the following formula for calculating location in range free localization [63]. \[A=-2\times \begin{pmatrix}x_{1}-x_{n}&y_{1}-y_{n}\\ x_{2}-x_{n}&y_{2}-y_{n}\\ \vdots&\vdots\\ x_{n-1}-x_{n}&y_{n-1}-y_{n}\end{pmatrix}  \tag{3}\]\[B= \begin{pmatrix}d_{1}^{2}-d_{n}^{2}-x_{1}^{2}+x_{n}^{2}-y_{1}^{2}+y_{n}^{2}\\ d_{2}^{2}-d_{n}^{2}-x_{2}^{2}+x_{n}^{2}-y_{2}^{2}+y_{n}^{2}\\ \vdots\\ d_{n-1}^{2}-d_{n}^{2}-x_{n-1}^{2}+x_{n}^{2}-y_{n-1}^{2}+y_{n}^{2}\end{pmatrix}  \tag{4}\]  
\[P= \begin{pmatrix}x\\ y\end{pmatrix}  \tag{5}\]  
where, \(P=(A^{T}A)^{-1}A^{T}B\). However, DV-Hop requires not only uniformly deployed WSNs but also the same attenuation of signal strength in all directions. To modify the disadvantage of existing DV-Hop localization algorithm, the relevant literature proposed many improved algorithms based on the following metric:  
**Improvement based on average hop distance:** In the randomly deployed node density and connectivity of the network, there are many works that modified the average hop distance between anchor nodes to improve the position estimation accuracy [67; 68; 69; 70]. Such as [67], it improved the location accuracy by modifying the network average hop distance based on minimum mean square error criteria as \(HopSize_{i}^{N}=\frac{\sum_{j\
eq i}h_{ij}d_{ij}}{\sum_{j\
eq i}h_{ij}^{2}}\). Where \(d_{ij}\) is the straight line distance between anchor nodes \(i\) and \(j\), \(h_{j}\) is the hop segment number between anchor nodes \(i\) and \(j\). Another algorithm such as [68], it calculated the error \(e^{ij}\) as \(e^{ij}=d_{est}^{i,j}-d_{true}^{i,j}\), where \(d_{est}^{i,j}\) is the estimated distance between anchor nodes \(i\) and \(j\), \(d_{true}^{i,j}\) is the Euclidean distance between anchors \(i\) and \(j\).