# A Weighted and Distributed Algorithm for Range-Based Multi-Hop Localization Using a Newton Method
## 4 A Robust and Distributed Localization Algorithm Based on the Newton Method
Furthermore, the network topology, integrated to the other aforementioned factors, can generate abnormal errors (i.e., outliers) on distance estimates; the latter can bring with them large errors on distance estimates where most localization algorithms do not behave well. To evaluate the accuracy iterations performance of algorithms, two kind of topologies are recreated as shown Figure 1. As can be observed, both networks are connected (i.e., non-isolated sensor nodes), and anchor nodes are distributed around a circle shape Figure 1a (anisotropic network) or inside of a square area Figure 1b (isotropic network). It must be remarked that anchor nodes are located in a non-collinear pattern distribution. The system test has 10 setup networks for each topology with fixed positions of sensor and anchor nodes, and the degree of network connectivity is given by the radio range in sensor and anchor nodes, assumed homogeneous. There are two levels of degree connectivity given by different radio ranges (R = 35 m and R = 45 m). Therefore, for each radio range, 10 networks are created for each topology. As proposed in [34], the noisy distances between a sensor \(s_{i}\) and its neighbors are computed as

\[r_{ij}=\left\|\mathbf{u}_{i}-\mathbf{u}_{j}\right\|\cdot\max\{0,1+\chi\cdot nf \},\ \ \forall j\in\Omega_{i}, \tag{35}\]

Figure 1: Multi-hop WSN topologies, where each connected network contains 95 unlocalized sensors and five anchor nodes. (**a**) Anisotropic circular connected network with sensor and anchor nodes randomly distributed in a circular shape. (**b**) Isotropic uniform distributed network with sensor and anchor nodes randomly distributed over a square area of 40,000 m\({}^{2}\). where \(\chi\sim\mathcal{N}(0,\,1)\) represents a normal distributed random variable and \(nfe\in[0,1]\) is the standard deviation of the distance error. This is equivalent to

\[\text{cost}(W_{i})=O(|\mathbf{\Omega}_{i}|\times|\mathbf{B}|). \tag{29}\]0

that can be rewritten as

\[\text{cost}(W_{i})=O(|\mathbf{\Omega}_{i}|\times|\mathbf{B}|). \tag{29}\]1

which is similar to the additive noise model in (8). In order to obtain noisy distances contaminated with outliers, a parameter \(\Theta\) (percentage of outliers) is used to randomly select a subset of distances. Each distance in the subset is modified by a scalar parameter \(\rho\) as follows:

\[\text{cost}(W_{i})=O(|\mathbf{\Omega}_{i}|\times|\mathbf{B}|). \tag{29}\]2

where the parameter \(\rho\) is defined as

\[\rho= \begin{cases}5,&\text{if}\quad\max[0,1+\chi\cdot nfe]\geq 1,\\ \frac{1}{5},&\text{if}\quad\max[0,1+\chi\cdot nfe]<1,\end{cases}  \tag{39}\]

For each sensor \(s_{i}\) an initial estimated position is calculated as the average of the \(M\) anchor positions plus a random perturbation as follows:

\[\frac{1}{M}\sum_{k=1}^{M}(x_{N+k}+v_{i,k},\,y_{N+k}+v_{i,k}), \tag{40}\]

where \(v_{i,k},i=1,\ldots,N,k=1,\ldots,M\) is a \(N\times M\) sample of a random variable with Gaussian distribution \(\mathcal{N}(0,\,1)\). The root mean square error (RMSE) metric is employed to evaluate errors on position estimates of the unknown sensors for the network \(t\), where \(t=1,\ldots,10\), and finally the average RMSE (\(RMSE\)) is calculated as follows:

\[RMSE \tag{41}\]

In Equation (41), \(\left\|\cdot\right\|\) is the two-norm, \(\mathbf{p}_{i}^{t}\) and \(\mathbf{u}_{i}^{t}\) represent the position estimate of sensor \(s_{i}\) and its true position for the network \(t\), respectively, and \(N\) is the number of unknown sensors. Figure 2 shows the methodology used for the algorithms to evaluate accuracy and number of iterations. There are two ranges of connectivity for testing (R = 35 m and R = 45 m), two levels of noise (\(nfe=0.1\) and \(nfe=0.3\)), and six scales of outliers (\(\Theta\in\{\)0%, 10%, 20%, 30%, 40%, 50%\(\}\)). The box on the left side, in Figure 2, has four possible combinations between R and \(nfe\) values. For each one of the four combinations, 30 evaluation processes are generated as shown the box on the right side.