# 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
## 5 Computational Complexity

The Algorithm 1 is run for each sensor \(s_{i}\) and requires as input the set \(W_{i}=\{w_{j}:j\in\mathbf{\Omega}_{i}\}\) and the set of weights \(C_{i}=\{c_{j}\,:\,j\in\mathbf{\Omega}_{i}\cup\mathbf{B}\}\) computed in Equation (19). First, the computational cost incurred in the computation of the \(W_{i}\) and \(C_{i}\) will be determined. As each \(w_{j}\in W_{i}\) is computed as the average of the number of hops \(hops(j,k)\) between the sensor \(s_{j}\) and each anchor \(k\), then computing \(w_{j}\) takes \(O(|\mathbf{B}|)\) operations. On the other hand, the set \(W_{i}\) consists of \(|\mathbf{\Omega}_{i}|\) elements, therefore the cost to determine the set \(W_{i}\) is

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

Each weight \(c_{j}\in C_{i}\) is calculated by Equation (19) which depends on (17) corresponding to the median of a set \(E_{\mathbf{\Omega}_{i}}\) of size at most \(|\mathbf{\Omega}_{i}|\). It is well known [33] that the median of a set of size \(n\) can be computed in linear time \(O(n)\). Therefore, the computational cost to determine \(C_{i}\) is

\[\text{cost}(C_{i})=O(|\mathbf{\Omega}_{i}|+|\mathbf{B}|)=O(|\mathbf{\Omega}_{ i}|), \tag{30}\]

assuming that \(|\mathbf{B}|\leq|\mathbf{\Omega}_{i}|\). In the following, the computational cost of one iteration of the repeat/until block (from line 5 to 11) will be addressed. The most expensive steps are the calculus of the gradient \(\
abla F(\mathbf{\hat{p}}_{i})\) and the Hessian \(\mathbf{H}(\mathbf{\hat{p}}_{i})\), where each of them are computed in at most \(O(|\mathbf{\Omega}_{i}|+|\mathbf{B}|)=O(|\mathbf{\Omega}_{i}|)\). This is due to both the first and second partial derivatives (equations from (20) to (27)) are expressed as summation over the set \(\mathbf{\Omega}_{i}\cup\mathbf{B}\). Note that line 9 corresponds to solving a \(2\times 2\) linear system with a positive definite matrix with cost \(O(1)\). Summarizing, the cost of this loop block is

\[\text{cost}(\text{repeat/until})=O(n_{i}|\mathbf{\Omega}_{i}|), \tag{31}\]

where \(n_{i}\) is the number of iterations that the algorithm needed to convergence. Therefore, the total cost of the Algorithm 1 per sensor \(s_{i}\) is calculate as

\[\text{cost}(W_{i})+\text{cost}(C_{i})+\text{cost}(\text{repeat/until})=O(| \mathbf{\Omega}_{i}|\times|\mathbf{B}|)+O(n_{i}|\mathbf{\Omega}_{i}|). \tag{32}\]

Because Algorithm 1 is executed once for each sensor, it is obtained that

\[\text{final cost}=\sum_{i:\,s_{i}\in S}[O(|\mathbf{\Omega}_{i}|\times| \mathbf{B}|)+O(n_{i}|\mathbf{\Omega}_{i}|)]. \tag{33}\]

Based on the experimental analysis, \(|\mathbf{B}|=5\) and the body of the repeat until block is executed in 6 iterations (\(n_{i}=6\)) on average. Consequently, Equation (33) can be simplified to

\[\text{final cost}=\sum_{i:\,s_{i}\in S}[O(5|\mathbf{\Omega}_{i}|)+O(6|\mathbf{ \Omega}_{i}|)]=\sum_{i:\,s_{i}\in S}O(|\mathbf{\Omega}_{i}|). \tag{34}\]

As \(\sum_{i:\,s_{i}\in S}|\mathbf{\Omega}_{i}|=2|E|\), with \(|E|\) denoting the number of wireless connections, the final cost is a big-O of the number of connections in the network, implying that the algorithm scales linearly with respect to the total number of connections. ## 6 Range-Based Multi-Hop Network Performance

In large deployment scenarios with constrained radio range on sensor nodes, forming multi-hop networks, and unknown sensors far outnumber anchor nodes, the DV-Hop scheme represents a good approach to estimate distances among sensor nodes in a distributed manner [11; 13]. As is well known, a distance estimation between an anchor node and unknown sensor, at some hops of each other, normally could suffer from several error sources: the environmental itself, the ranging technique, and the localization algorithm, to name a few.