## 2 Related Works
### Original DV-Hop Algorithm  
The DV-hop positioning algorithm is a distributed positioning method using the idea of distance vector routing and GPS positioning. The algorithm is not only simple but also has high positioning accuracy. The DV-hop algorithm has the following three stages.  
In the first stage, the location information packet of each anchor node in the network is broadcast to the neighboring nodes through itself by a typical distance vector exchange protocol, so that all nodes in the network can obtain the hop count information of the distance node.  
In the second phase, after the average per hop of each anchor node is obtained, it needs to be broadcast to other nodes in the network.  
\[\begin{cases}Hs_{i}=\frac{\sum_{i=2,i+j}^{m}h_{ij}d_{ij}}{\sum_{i=2,i+j}^{m}h _{ij}^{2}},\\ d_{ij}=\sqrt{(x_{i}-x_{j})^{2}+(y_{1}-y_{2})^{2}},\end{cases} \tag{15}\]  
where \(Hs_{i}\) represents the average distance per hop from all anchor nodes to the \(i\)th anchor node, \(h_{i,j}\) is the number of hops of anchor nodes \(i\) to \(j\), and \(d_{ij}\) is the distance between the anchor nodes \(i\) and \(j\).  
\[\begin{cases}Us_{i,u}=\lambda_{i,u}\times Hs_{i},\\ \lambda_{i,u}=\frac{h_{i,u}}{\sum_{k=1}^{M}h_{k,u}},\end{cases} \tag{16}\]  
where \(\lambda_{i,u}\) represents the weight of the average hop distance of anchor node \(i\), and \(h_{i}\) is the number of hops from anchor node \(i\) to an unknown node \(u\). \(Us_{u}\) represents the average distance of each hop from the unknown node \(u\) to the anchor node \(i\). Finally, the approximate distance \(\hat{d}_{i,u}\) of the anchor node \(i\) to the unknown node \(u\) can be found by Equation (17):  
\[\hat{d}_{i,u}=Us_{u}\times h_{i,u}. \tag{17}\]  
In the third stage, after calculating the distance between an unknown node and three or more anchor nodes by Equation (17), it is possible to calculate the unknown node position by trilateration or maximum likelihood estimation. Since the maximum likelihood of the estimation method is more accurate than the trilateration method in the positioning process, the simulation experiment carried out in this thesis uses the method of maximum likelihood estimation to locate the nodes, as shown in Figure 1. Next, we will introduce the node location method for maximum likelihood estimation.  
Figure 1: Maximum likelihood estimation localization method.  
Assuming that the unknown node coordinates are \((x,y)\), the coordinates of the anchor node \(AN_{i}\) are \((m_{i},\,n_{i})\) and the number of anchor nodes is \(k\). The solution formula for the unknown node position coordinate point is as follows:  
\[\begin{cases}(m_{1}-x)^{2}+(n_{1}-y)^{2}=&d_{1}^{2}\\ (m_{2}-x)^{2}+(n_{2}-y)^{2}=&d_{2}^{2}\\ \ldots\\ (m_{k}-x)^{2}+(n_{k}-y)^{2}=&d_{k}^{2}\end{cases} \tag{18}\]  
We expand on each equation of Equation (18), and then subtract the last equation from each formula to get Equation (19). Finally, we use Equations (20)-(23) to simplify the form of the matrix solution.  
\[\left\{\begin{array}{c}m_{1}^{2}-m_{k}^{2}+2(m_{1}-m_{k})x+n_{1}^{2}-n_{k}^{ 2}-2(n_{1}-n_{k})y=\hat{d}_{1}^{2}-\hat{d}_{k}^{2}\\ \\ m_{2}^{2}-m_{k}^{2}+2(m_{2}-m_{k})x+n_{2}^{2}-n_{k}^{2}-2(n_{2}-n_{k})y=\hat{ d}_{2}^{2}-\hat{d}_{k}^{2}\\ \\ \ldots\\ m_{k-1}^{2}-m_{k}^{2}+2(m_{k-1}-m_{k})x+n_{k-1}^{2}-n_{k}^{2}-2(n_{k-1}-n_{k}) y=\hat{d}_{k-1}^{2}-\hat{d}_{k}^{2}\end{array}\right. \tag{19}\]  
\[\mathbf{X}=\begin{bmatrix}x\\ y\end{bmatrix} \tag{20}\]  
\[\mathbf{A}=\begin{bmatrix}2(m_{1}-m_{k})&2(n_{1}-n_{k})\\ 2(m_{2}-m_{k})&2(n_{2}-n_{k})\\ \ldots\\ 2(m_{k-1}-m_{k})&2(n_{k-1}-n_{k})\end{bmatrix} \tag{21}\]  
\[\mathbf{B}=\begin{bmatrix}m_{1}^{2}+n_{1}^{2}-m_{k}^{2}-n_{k}^{2}+\hat{d}_{k} ^{2}-\hat{d}_{1}^{2}\\ m_{2}^{2}+n_{2}^{2}-m_{k}^{2}-n_{k}^{2}+\hat{d}_{k}^{2}-\hat{d}_{2}^{2}\\ \ldots\\ m_{k-1}^{2}+n_{k-1}^{2}-m_{k}^{2}-n_{k}^{2}+\hat{d}_{k}^{2}-\hat{d}_{k-1}^{2} \end{bmatrix} \tag{22}\]  
\[\mathbf{AX}=\mathbf{B}\quad\Rightarrow\quad\mathbf{X}=(\mathbf{A^{T}A})^{-1 }\mathbf{A^{T}B} \tag{23}\]