# Efficient Distributed Method for NLOS Cooperative Localization in WSNs
## 2 Problem Formulation
### Convex Relaxation  
The method in Reference [35] provided two bounds of \(d_{i,j}\) in NLOS environments. The upper bound is  
\[u_{i,j}=r_{i,j}+2\sigma_{i,j}\geq d_{i,j} \tag{4}\]  
the lower bound is  
\[l_{i,j}=r_{i,j}-4\sigma_{i,j}\leq d_{i,j} \tag{5}\]  
For the single-constraint case, the upper and lower bounds provide an annular feasible region. Heuristic localization estimation lies on the circle with a radius of \((u_{i,j}+l_{i,j})/2\). Hence, the optimization problem of cooperative localization in an NLOS environment is modified as:  
\[\hat{\mathbf{X}}_{s}=\underset{\mathbf{X}_{s}}{\text{argmin}}\sum_{(i,j)\in\mathcal{Z }_{S}\cup\mathcal{Z}_{A}}\frac{1}{2}\left(\|\mathbf{x}_{i}-\mathbf{x}_{j}\|-\frac{1}{ 2}(l_{i,j}+u_{i,j})\right)^{2} \tag{6}\]  
This model takes NLOS impact into account and uses heuristic points \((u_{i,j}+l_{i,j})/2\) to replace range measurements \(r_{i,j}\). In severe environments where most connections are NLOS, range measurements may contain much false information and, thus, cannot directly be used as distance metrics. In Model (6), the bounds can neutralize most NLOS errors in range measurements. However, Problem (6) is nonconvex. In this paper, we propose a tight relaxation method rather than SDP. We used projection relaxation to obtain the convex envelope of the original nonconvex problem. The theoretical derivation is given as follows.  
First, we rewrote the fundamental part of Problem (6) in the form of a squared distance of the projection on a certain set by using Cauchy-Schwartz inequality.  
The proof is given as follows:  
If \(\|\mathbf{b}\|=d_{0}\), we have  
\[\begin{split}(\|\mathbf{a}\|-d_{0})^{2}&=\|\mathbf{a}\|^{ 2}-2\|\mathbf{a}\|\|\mathbf{b}\|+\|\mathbf{b}\|^{2}\\ &\leq\|\mathbf{a}\|^{2}-2\mathbf{a}^{\text{T}}\mathbf{b}+\|\mathbf{b}\|^{2}\\ &=\|\mathbf{a}-\mathbf{b}\|^{2}\end{split} \tag{7}\]  
Then, function  
\[f(\mathbf{a},d)=(\|\mathbf{a}\|-d_{0})^{2} \tag{8}\]  
can be rewritten as  
\[f(\mathbf{a},d)=\underset{\|\mathbf{b}\|=d_{0}}{\inf}\|\mathbf{a}-\mathbf{b}\|^{2}=\text{ dist}^{2}(\mathbf{a},\text{B}) \tag{9}\]  
where \(\text{B}=\{\mathbf{b}\|\|\mathbf{b}\|=d_{0}\}\) is a nonconvex set. Hence, the original problem can be written in a simpler form:  
\[\text{min}\ \sum_{(i,j)\in\mathcal{Z}_{S}\cup\mathcal{Z}_{A}}\frac{1}{2}\text{ dist}^{2}(\mathbf{x}_{i}-\mathbf{x}_{j},\text{B}_{i,j}) \tag{10}\]  
where set \(\text{B}_{i,j}\) is a spherical surface depending on the bounds, i.e., \(\text{B}_{i,j}=\{\mathbf{b}|\|\mathbf{b}\|=\frac{1}{2}(l_{i,j}+u_{i,j})\}\).  
A feasible approach is to find the convex envelope by relaxing constraint \(\|\mathbf{b}\|=d_{0}\) to \(\|\mathbf{b}\|\leq d_{0}\). Therefore, we obtained the convex form based on Function (8).  
\[\tilde{f}(\mathbf{a},d)=\inf_{\|\mathbf{b}\|\leq d_{0}}\|\mathbf{a}-\mathbf{b}\|^{2}=\text{dist}^ {2}\left(\mathbf{a},C\right) \tag{11}\]  
where \(\text{C}=\{\mathbf{b}\|\|\mathbf{b}\|\leq\text{d}\}\) is the convex hull of the non-convex set B.  
According to Equation (11), we could establish the convex model corresponding to Problem (10):  
\[\min\;\sum_{(i,j)\in\mathcal{Z}_{\mathcal{S}}\cup\mathcal{Z}_{\mathcal{A}}} \frac{1}{2}\text{dist}^{2}(\mathbf{x}_{i}-\mathbf{x}_{j},\text{C}_{i,j}) \tag{12}\]  
where \(\text{C}_{i,j}=\{\mathbf{b}\|\|\mathbf{b}\|\leq\frac{1}{2}(l_{i,j}+u_{i,j})\}\) is a convex set.