2. DV-Hop Algorithm
Nath et al. [15] propose this algorithm. It has three steps. In the first step of the algorithm, all the anchor nodes flood the information about its location and their identification with their one-hop distant nodes only. After this, every node of the network spread out this information further by incrementing the hop count value by one to their immediate neighbours. Likewise, the whole network gets the hop count value for their neighbours. If at any instant a node receives again the information about the same node then it (i.e. receiver node) compares the hop count value with the previous value and makes the due changes in its routing table.
In the second step, each anchor node, say \({}^{\prime}p^{\prime}\), calculates its average hop size \(H_{\text{siz}e_{p}}\) by using the equation (1).
\begin{equation} H_{\text{siz}e_{p}}=\frac{\sum_{s\epsilon(A_{n}-p)}\sqrt{\left(x_{p}-\ x_{s}\right)^{2}+\left(y_{p}-\ y_{s}\right)^{2}}}{\sum_{s\epsilon(A_{n}-p)}H_{\text{coun}t_{\text{ps}}}};\ \forall\ p\neq s\ and\ p,s\ \epsilon\ A_{n}\ (1)\ \ \ \ \nonumber \\ \end{equation}
where \(H_{\text{coun}t_{\text{ps}}}\) is a minimum number of hop count between two anchor nodes \({}^{\prime}p^{{}^{\prime}},\) \({}^{\prime}s^{\prime}\) from the available anchor nodes set \(A_{n}\); and\(\left(x_{p},\ y_{p}\right),\ (x_{s},\ y_{s})\) are the coordinates of \({}^{\prime}p^{{}^{\prime}},\) \({}^{\prime}s^{\prime}\) respectively. Every anchor node spread out its average hop size value in the network. Now after obtaining average hop size value, an unknown node \((U)\) calculates its distance \((d_{i})\)from respective anchor node \((p)\) by using equation (2).
\begin{equation} \ \begin{matrix}d_{i}=H_{\text{siz}e_{p}}\times H_{\text{coun}t_{\text{pU}}};\ \forall i\epsilon A_{n}&(2)\\ \end{matrix}\nonumber \\ \end{equation}
In the third step of this algorithm, an unknown node \((U)\) estimates its location \((x,\ y)\) by using the distance equation (3).
\begin{equation} \begin{matrix}{(x_{i}-x)}^{2}+{(y_{i}-y)}^{2}={d_{i}}^{2};\ \forall i\epsilon A_{n}&(3)\\ \end{matrix}\nonumber \\ \end{equation}
where \(d_{i}\) is a distance calculated by \({}^{\prime}U^{\prime}\) from the equation (2) with respect to anchor nodes \(i=1,\ 2,\ \ldots,\ m\) located at\(\left(x_{i},\ y_{i}\right)\).
Further, the equation (3) is converted into a linear set of equations by subtracting all its equations of (3) by anyone equation from it, which yields equation (4).
\begin{equation} \begin{matrix}\left(x_{i}^{2}+y_{i}^{2}\right)-\left(x_{m}^{2}+x_{m}^{2}\right)-2\left(\left(x_{i}-x_{m}\right)x+\left(y_{i}-y_{m}\right)y\right)=d_{i}^{2}-d_{m}^{2}&(4)\\ \end{matrix}\nonumber \\ \end{equation}
The equation (4) can be rewritten in a matrix form of \(PQ=R\), where\(Q^{{}^{\prime}}=\par \begin{bmatrix}x&y\\ \end{bmatrix}\) \(and\ P,R\) are –
\begin{equation} \begin{matrix}P=2\begin{bmatrix}\begin{matrix}\left(x_{1}-x_{m}\right)\\ \left(x_{2}-x_{m}\right)\\ \begin{matrix}\vdots\\ {(x}_{m-1}-x_{m})\\ \end{matrix}\\ \end{matrix}&\begin{matrix}\left(y_{1}-y_{m}\right)\\ {(y}_{2}-y_{m})\\ \begin{matrix}\vdots\\ {(y}_{m-1}-y_{m})\\ \end{matrix}\\ \end{matrix}\\ \end{bmatrix},&R=&\begin{bmatrix}x_{1}^{2}+y_{1}^{2}-{(x}_{m}^{2}+y_{m}^{2})-d_{1}^{2}+d_{m}^{2}\\ x_{2}^{2}+y_{2}^{2}-{(x}_{m}^{2}+y_{m}^{2})-d_{2}^{2}+d_{m}^{2}\\ \begin{matrix}\vdots\\ x_{m-1}^{2}+y_{m-1}^{2}-{(x}_{m}^{2}+y_{m}^{2})-d_{m-1}^{2}+d_{m}^{2}\\ \end{matrix}\\ \end{bmatrix}\\ \end{matrix}\nonumber \\ \end{equation}
Now, by applying the least square method the value of\(Q={(P^{{}^{\prime}}P)}^{-1}P^{{}^{\prime}}R\) is obtained and the algorithm reveals the location of the unknown node\({}^{\prime}U^{\prime}\).