# Underwater Electromagnetic Sensor Networks, Part II: Localization and Network Simulations
## 3 Algorithms for Self-Localization and Navigation-Aid Applications
### Self-Localization  
We propose a cooperative localization algorithm for nodes that do not know their own position, but can communicate with their neighbors to estimate their own coordinates. We refer to the set of nodes that have knowledge of their position as anchor nodes and denote them with \(\mathcal{N}_{a}\). Likewise, the set of nodes that do not know their position are denoted as \(\mathcal{N}_{u}\). We also have \(\mathcal{N}_{u}\cup\mathcal{N}_{u}=\mathcal{N}\). We refer to the nodes that are within radio reach of node \(i\) as neighbors and denote them with \(\mathcal{N}^{i}\). Note that the set of neighbors may include both nodes from \(\mathcal{N}_{a}\) and \(\mathcal{N}_{u}\).  
The localization algorithm should be performed only once, when the nodes come online, as an initial calibration step. We analyze its performance in terms of convergence and packet loss. The optimization problem we propose is given by:  
\[\begin{split}\min_{x_{i}\in\mathbb{R}^{2}}&\sum_{i \in\mathcal{N}_{a}}\sum_{j\in\mathcal{N}^{i}}(d_{ij}^{2}-\|x_{i}-x_{j}\|^{2})^ {2}=\\ \min_{x_{i}\in\mathbb{R}^{2}}&\sum_{i\in\mathcal{N} _{a}}\sum_{j\in\mathcal{N}^{i}}d_{ij}^{4}+\|x_{i}-x_{j}\|^{4}-2d_{ij}^{2}\|x_{ i}-x_{j}\|^{2}.\end{split} \tag{2}\]  
Problem (2) is nonconvex and can be solved using algorithms of the family of successive convex approximations, such as the one proposed in [15]. The methodology consists of an iterative procedure where a convex function is used to approximate the non-convex original objective in a local region around a temporary fixed point. The surrogate function retains the convex parts and linearizes the non-convex ones. The convexification is performed around a temporary pivotal point, which is updated in subsequent iteration steps. Specifically, the convex surrogate function for every node \(i\in\mathcal{N}_{u}\) is given by:  
\[\tilde{U}_{i}(x_{i},x^{k})=\sum_{j\in\mathcal{N}^{i}}d_{ij}^{4}+\|x_{i}-x_{j} ^{k}\|^{4}-4d_{ij}^{2}(x_{i}^{k}-x_{j}^{k})x_{i}+\frac{\tau}{2}\|x_{i}-x_{i}^ {k}\|^{2}, \tag{3}\]  
Figure 4: Histogram and normal distribution fit for the trace of measurements.  
where \(x^{k}=(x^{k}_{i})_{i\in\mathcal{N}_{u}}\) is the pivotal point, which is updated at different iteration steps, and \(\tau>0\) enforces strong duality. The complete set of instructions to solve Problem (2) is described in Algorithm 1. Note that every node needs to solve the following problem:  
\[\hat{x_{i}}(x^{k})=\min_{x_{i}}\quad\tilde{U}_{i}(x_{i},x^{k}) \tag{4}\]  
where we made it explicit that (4) is minimized only in \(x_{i}\) because the algorithm is solved in a distributed manner. Note also that the nodes only need to exchange their own estimates with their neighbors.  
```
1:Initialize \(x^{0}=(x_{i})_{i\in\mathcal{N}_{u}}\in\mathbb{R}^{2N_{u}}\). Set \(k\gets 0\).
2:repeat
3: For all \(i\in\mathcal{N}_{u}\), solve \(x^{k+1}_{i}\leftarrow\hat{x}_{i}(x^{k})\).
4: Exchange \(x^{k+1}_{i}\) with neighbors \(j\in\mathcal{N}^{i},\ \forall i\in\mathcal{N}_{u}\).
5: Set \(k\gets k+1\).
6:until stopping criteria is satisfied.
```  
**Algorithm 1** Network nodes' self-localization algorithm  
Problem (4) is strongly convex and can be solved using any convex optimization solver or, more efficiently, directly finding the solution to the Karush-Kuhn-Tucker (KKT) system of equations [16]. The complexity of this approach is that of finding the root of a strongly monotone function. Efficient methods such as the Newton-Raphson method can be employed to solve it. Although the computation may be more demanding than other approaches in the literature [17], it has the benefit of speeding-up the convergence rate and reducing the required number of messages between nodes. Finally, the algorithm is robust in the sense of converging to a stationary point of the non-convex Problem (2), even when some nodes may have an out of date pivotal point, as analyzed in [18].