# Distributed Localization with Complemented RSS and AOA Measurements: Theory and Methods
## 4 Performance Analysis
### Analysis of Computational Complexity  
Here, we analyze the worst-case computational complexity of an algorithm. This is achieved by considering a fully connected network (i.e., the total number of neighbors of each target is assumed to be \(|\mathcal{E}_{i}|=N+(M-1)\), \(\forall i\in\mathcal{T}\)). In addition, the computational complexity of each algorithm is expressed as a function of the dominating terms (the smaller terms are disregarded), written as a function of \(|\mathcal{E}_{i}|\). The results of the considered algorithms are given in Table 2, where \(S_{\max}\), \(C_{\max}\), and \(T_{\max}\) are used to denote the maximum number of steps allowed in the bisection procedure in [68], the number of generated candidates and the number of iterations in [65], respectively. Furthermore, we also present the execution time of the considered algorithms, which is calculated as an average execution time per target to localize itself in the scenario where \(N=15\), \(M=50\), \(R=10\) m in \(M_{c}=100\) runs. The simulations were performed on the Intel(R)Core(TM) i7-4710 HQ CPU with 2.50 GHz and 16 GB RAM.  
One can see from Table 2 that the computational complexity of distributed algorithms depends mainly of the size of local neighborhood of a target, rather than on the size of the whole network (which is a characteristic of centralized ones). Furthermore, Table 2 exhibits that computational complexities of the SOCP approach in [61] and the MCMC-MH approach in [65] are the most burdensome ones. Although the complexity of MCMC-MH is actually linear in \(|\mathcal{E}_{i}|\), its execution time is higher by far than those of LLS and GTRS, and even that of SOCP. This can be explained by the fact that a high number of candidates is generated and evaluated in every step of MCMC-MH procedure, which even though not especially intensive in terms of computational cost, is very time-consuming as the number of candidates increases. Finally, one can see that LLS and GTRS approaches have linear computational complexity  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Algorithm** & **RSS** & **AOA** & \(\mathbf{P_{T}}\) & **Noise STD** \\ \hline SOCP & All nodes & Anchors & Not known/Known & Unknown \\ LLS & All nodes & All nodes & Known & Known \\ MCMC-MH & All nodes & Anchors & Known & Unknown \\ GTRS & All nodes & Anchors & Known & Unknown \\ \hline \hline \end{tabular}
\end{table}
Table 1: Summary of the main characteristics of the considered algorithms. SOCP = second-order cone programming; LLS = linear least squares; MCMC-MH = Markov chain Monte Carlo with Metropolis-Hastings.  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Algorithm** & **Complexity** & **Time (sec)** \\ \hline SOCP & \(\mathcal{O}\left(|\mathcal{E}_{i}|^{3.5}\right)\) & 0.66 \\ LLS & \(\mathcal{O}\left(|\mathcal{E}_{i}|\right)\) & 0.004 \\ MCMC-MH & \(\mathcal{O}\left(C_{\max}\times T_{\max}\times|\mathcal{E}_{i}|\right)\) & 1.2 \\ GTRS & \(\mathcal{O}\left(S_{\max}\times|\mathcal{E}_{i}|\right)\) & 0.005 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Analysis of computational complexity and average execution time.  
in \(|\mathcal{E}_{i}|\) and their time execution confirms that they might be suitable for real-time implementation, despite the fact that GTRS requires some iterations in the bisection procedure to reach its final solution.