## 3 The Proposed Localization Algorithm
### Problem Statement  
Consider a two-dimensional region of space, where there is a sensor network given by a set of nodes \(N=\{N_{1},N_{2},\ldots,N_{m+n}\}\), which consists of m anchor nodes and \(n\) sensor nodes. The coordinates of these nodes can be described with definition (1):  
\[\mathbf{cor}(N_{p})=(x_{p},y_{p})^{\mathrm{T}},for\ p=1,...,m+n. \tag{1}\]  
In WSN \(N\), the positions of \(m\) anchor nodes \(N_{i}\in\boldsymbol{A}\), \(\boldsymbol{A}=\{N_{i}\,|\,i=1,\,...,\,m\}\) are known, while the positions of the \(n\) sensor nodes \(N_{j}\in\boldsymbol{B}\), \(\boldsymbol{B}=\{N_{j}\,|\,j=m+1,\,...,\,m+n\}\) are unknown. In the case of multi-hop networks, the hop counts between pair nodes are already known. The Euclidean distance from node \(N_{i}\) to \(N_{j}\) (\(i\
eq j\)) can be presented by Equation (2):  
\[d_{ij}=\|\mathbf{cor}(N_{i})-\mathbf{cor}(N_{j})\|=\sqrt{(x_{i}-x_{j})^{2}+(y_ {i}-y_{j})^{2}}. \tag{2}\]  
The hop counts from node \(N_{i}\) to \(N_{j}\) (\(i\
eq j\)) can be expressed as \(h_{ij}\). Taking Figure 1a as an example, in such a multi-hop network \(d_{ij}\) is proportional to \(h_{ij}\), i.e., \(d_{ij}\propto h_{ij}\). Thus, the localization problem can be formulated as:  
\[\begin{array}{l}\text{Estimate}\ \mathbf{cor}(N_{k}),\\ \text{Given}\ \mathbf{cor}(N_{i}),\ d_{ij},\text{ and }h_{kt},\end{array} \tag{3}\]  
where \(N_{i}\), \(N_{j}\in\boldsymbol{A}\), \(N_{k}\in\boldsymbol{B}\), and \(h_{kt}\) denotes the hop counts between node \(N_{k}\) and node \(N_{t}\) (\(N_{t}\in\boldsymbol{A}\cup\boldsymbol{B}\)). Assume that the distances and hop counts from \(N_{i}\) to other anchors can be represented by the vectors \(\mathbf{y}_{i}\) and \(\mathbf{x}_{i}\), respectively. Our aim is to learn a function \(f\): \(\mathbf{X}\mapsto\mathbf{Y}\) from \(m\) training data \(\{(\mathbf{x}_{i},\mathbf{y}_{i})\}_{i=1}^{m}\), where \(\mathbf{x}_{i}\in\mathbf{X}\) and \(\mathbf{y}_{i}\in\mathbf{Y}\). The input space \(\mathbf{X}\) (hops), is known as the dependent variable, and the output space \(\mathbf{Y}\) (distances) is the independent variable. The function \(f\) is represented by a linear model  
\[f(\mathbf{x})=\mathbf{w}^{\mathrm{T}}\mathbf{x}, \tag{4}\]  
where \(\mathbf{w}\) is a \(m\times 1\) vector that contains the coefficients of the linear function. Usually, linear least squares (LLS) is used to determine \(\mathbf{w}\). It uses the vertical distance between the observed values \(\mathbf{y}_{i}\) and the predictions \(f(\mathbf{x}_{i})\), which are known as the residuals \(\mathbf{r}_{i}=\mathbf{y}_{i}-f(\mathbf{x}_{i})=\mathbf{y}_{i}-\mathbf{w}^{ \mathrm{T}}\mathbf{x}_{i}\).  
In the LLS case, the sum of the squared residuals is minimized, which in matrix form is  
\[S(\mathbf{w})=(\mathbf{y}-\mathbf{X}\mathbf{w})^{\mathrm{T}}(\mathbf{y}- \mathbf{X}\mathbf{w}), \tag{5}\]  
with \(\mathbf{X}\) being the \(m\times m\) design matrix that combines all of the hop-count vectors, and the \(m\times 1\) vector \(\mathbf{y}\) combining the distance values:  
\[\mathbf{X}=\left[\begin{array}{cccc}x_{1,1}&x_{1,1}&\cdots&x_{1,m}\\ x_{2,1}&x_{2,2}&\cdots&x_{2,m}\\ \vdots&\vdots&\ddots&\vdots\\ x_{m,1}&x_{m,1}&\cdots&x_{m,m}\end{array}\right],\quad\mathbf{y}=\left[ \begin{array}{c}y_{1}\\ y_{2}\\ \vdots\\ y_{m}\end{array}\right], \tag{6}\]where each row corresponds to one input/output example. The coefficients could be optimized by minimizing Equation (5) as follows:  
\[\hat{\mathbf{w}}=\text{argmin}_{\mathbf{w}}(\mathbf{y}-\mathbf{Xw})^{\text{T}}( \mathbf{y}-\mathbf{Xw}). \tag{7}\]  
The minimizer of the problem (7) is  
\[\hat{\mathbf{w}}={\left(\mathbf{X}^{\text{T}}\mathbf{X}\right)}^{-1}\mathbf{X }^{\text{T}}\mathbf{y}. \tag{8}\]  
Thus, to make a prediction for a novel input \(\mathbf{x}^{\text{new}}\), we only need to know the model and its parameters \(\mathbf{w}\), which can be represented as  
\[\hat{\mathbf{w}}=\text{argmin}_{\mathbf{w}}(\mathbf{y}-\mathbf{Xw})^{\text{T}} (\mathbf{y}-\mathbf{Xw}). \tag{9}\]