Abstract
For large-scale underwater wireless sensor networks (UWSNs) with a minority of anchor nodes, multihop localization is a popular scheme for determining the geographical positions of normal nodes. However, existing multihop localization studies have considered the anchor positions to be free of errors, which is not a valid assumption in practice. In this paper, the problems existing in nonlinear least square-based node self-localization schemes are analyzed, and the biased distribution characteristic of multihop distance estimation errors is pointed out. Then, the orthogonal regression method is employed for the localization of normal nodes in the presence of anchor position errors. In particular, the influences of errors in independent variables and biases in dependent variables on node coordinate estimation are taken into account simultaneously. Extensive simulation results illustrate the robustness and effectiveness of our method.
1. Introduction
Underwater wireless sensor networks (UWSNs) have attracted a rapidly growing interest from researchers during the last few years. Due to the advantages of easy deployment, self-management, and no requirement for infrastructure, UWSNs can be applied to a wide range of aspects, such as naval surveillance, earthquake and tsunami forewarning, climate and ocean observation, and water pollution tracking. In these applications, each node needs to collaborate with others in sensing events of interest by exchanging acquired data. To make the data collected from sensor nodes meaningful, the positions of related nodes are often required. In recent years, various node localization algorithms for UWSNs have been proposed and a comprehensive survey of them is provided in [1–3] and the references therein.
The task of WSNs node localization is to determine the positions of normal nodes based on the knowledge of anchor positions and internode distance measurements. Currently, most UWSNs localization studies assume the anchor positions are perfectly known and only take the distance estimation errors into account. This, however, is not the case for UWSNs in practice due to the complex environments [4]. Since the positions of anchor nodes are often obtained through GPS receiver or manual configuration in fixed places, they usually suffer from some uncertainties. A typical example is in climate and ocean observation, some anchor nodes may be moved by water. In such cases, the anchor positions may subject to errors. Therefore, finding the positions of normal nodes in UWSNs with the use of inaccurate anchor positions is an important and challenging research topic [5–7].
In addition, the uncertainty of multihop distance measurements is also an important influence on localization accuracy [8–11]. Most of the existing approaches considered the distance measurements affected by the normal distribution noise and determined the distances uncertainty through Monte Carlo analysis or other conventional statistical techniques [12, 13]. But these methods perform well only when the measurement sample size is large and the hypothesis that measurement noises obey Gaussian distribution is satisfied.
In this paper, we mainly concentrate on the scenarios of multihop localization. We first point out the main problems existing in traditional multihop localization schemes, which are lack of considering the errors in independent variables and the biases in dependent variables. Through theoretical and empirical analysis, we learn that multihop distance estimation errors are distributed with various biases. We then construct a 3D multihop localization model based on the idea of orthogonal regression and give the simplified scheme for solving the optimum value of node coordinates. The final simulation results indicate that our method is robust against both anchor position errors and ranging errors.
The remainder of this paper is organized as follows. Section 2 formulates the multihop localization problem. Section 3 presents the details of our method. Section 4 evaluates the performance of our method through simulations. And, finally, Section 5 concludes this paper.
2. Problem Formulation
2.1. Multihop Localization Framework
As can be seen from Figure 1, the coordinates of normal node

Node multihop localization.
Through the multihop information exchange,
A direct and commonly used method for solving the unknown parameter
2.2. Discussion of NLSE Method
When the position information provided by anchor nodes is accurate and
In the geometry sense, the objective of NLSE is to minimize the sum of squares of vertical distances from the data points to the fitting curve (or curved surface). It only takes account of the errors in dependent variables, while ignoring the errors in independent variables. When both kinds of errors exist simultaneously, the fitting results and stability of NLSE are relatively poor. As discussed in the previous section, the anchor positions are inaccurate. For model (2), these inaccuracies reflect in the independent variables. If we do not address this issue, we cannot get credible localization results.
In multihop scenarios, there are two sources of distance estimation errors.
Random Errors. Due to the environment noise, the distance measurements between pairs of neighboring nodes suffer from certain random uncertainties, namely, random errors (or ranging errors). According to experimental results, the random errors are normal distributions. This can be further explained by invoking the central limit theorem. System Errors. By approximating the length of the shortest path to the Euclidean distance, multihop localization schemes can infer the distances between any pairs of nonneighboring nodes, which causes the system errors (or multihop cumulative errors). Since the system errors are affected by the bending degrees of broken lines, they are usually larger than the ranging errors, especially in irregular networks. In this paper, the random and system errors are called collectively multihop distance estimation errors.
In most WSNs localization studies, the distribution of ranging errors ε is assumed to be unbiased. In fact, it is not the case. Even if ε follows the ideal zero-mean normal distribution, the mean of multihop distance estimation errors e may not be equal to zero, which is proved by the empirical results in the following section. Therefore, when we estimate the coordinates of normal nodes, the distance estimation bias should not be ignored.
2.3. Analysis of Distance Estimation Bias
In this part, we give an empirical analysis of multihop distance estimation bias (the mean of multihop distance estimation errors) for 3D UWSNs. In simulation experiments, sensor nodes with adjustable communication range R are randomly distributed in a
Figure 2 shows the statistical results of multihop distance estimation bias (b) that is normalized by R with different network connectivity and λ. Both network connectivity and λ have some effect on bias b, among which the former affects the most. Since the broken line is always longer than direct one, the multihop distance estimation errors usually experience a positive bias. When the network connectivity is small, the approximation between the length of the shortest path and the Euclidean distance is the main source of distance estimation errors, and the value of bias b is bigger. In contrast, if nodes are densely deployed, an approximately straight multihop path is likely to exist between pairwise nodes. Then, b usually has a smaller value. With the increase of λ, the influence of ranging errors on multihop distance estimation rises, and the bias b gradually decreases to the mean of ranging errors. Generally, b is no more than half of nodes’ communication radius R.

Bias b versus network connectivity and λ.
3. Orthogonal Regression Method
We denote the declared position of anchor node
In the framework of MLE, the value of weights
3.1. Determination of Feasible Region
As seen from Figure 1, the feasible region of
However, the intersection among several spheres is difficult to be determined because of its irregular shape. In addition, due to the combined uncertainties in anchor positions and multihop distance estimations, the K spheres may not have intersection. So the calculation of feasible region can be classified into two cases.
We denote There may be no intersection among all bounding spheres in the first case. So we let the communication distance R be the radius; then the bounding spheres are all having intersection. We still use the expression in the first case and it only has to change
After getting the range of
3.2. Simplified Methods for Solving CWOR
Based in model (3), the objective function consists of
Firstly, set
The gradient of
The detailed procedures of solving the optimal value
Then, we get the estimated coordinates of normal node
3.3. Discussion of Our Method
In the framework of MLE, the proposed method for node coordinate estimation is suboptimal because of our approximation of
Relationship among threshold τ, localization error, and computation cost.
4. Performance Evaluation
In this section, we conduct simulations to study the performance of our proposed method. To reduce the influence of outliers, we take the average of 100 simulation runs as the final data points. The default simulation parameters are shown in Table 2. We mainly discuss the Average Localization Errors (ALE) under different network connectivity and standard deviation. The ALE is normalized by the communication radius R:
Default simulation parameters.
4.1. Impact of Anchor Position Errors
Figure 3 shows the statistics for performance of two methods with different standard deviation σ of anchor position errors.

ALE versus σ of anchor position errors.
As seen from Figure 3, the standard deviation σ has certain effect on both methods, among which NLSE is the most affected. Compared with NLSE, our method can improve the localization accuracy by at least 14% in each case. When
4.2. Impact of Ranging Errors
Figure 4 shows the comparison results of ALE under different standard deviations λ of ranging errors. With the increase of λ, the accuracies of both methods drop gradually.

ALE versus standard deviation of ranging errors.
When
4.3. Comparison under Anisotropic Network
In this part, we discuss the topology adaptabilities of NLSE and our method. Figure 5 shows a typical anisotropic network in which 200 nodes are randomly deployed in a C-shape spatial area. Its network connectivity is 12. Figure 6 shows the accuracy comparison results of two methods under the C-shape networks.

Anisotropic network (C-shape).

Performance comparison under C-shape network.
Since the shortest path between distant nodes in irregular networks is generally more winding than that in uniform networks, the ALE of both methods are bigger than those in Figure 3. However, our method always performs much better than NLSE. For example, the ALE of our method with
4.4. Impact of Network Connectivity
In this subsection, we simulate an improved localization algorithm named Taylor-LS for comparison and analyze the performance of ALE with different network connectivity [9]. We control the network connectivity by changing the transmission range while keeping the area of deployment the same. Figure 7 plots the relationship between the ALE and network connectivity.

ALE versus network connectivity.
We can observe that the ALE of our scheme decreases significantly with the increase of network connectivity when the anchor percentage is 10%. It should be noted that our scheme can achieve relatively high localization accuracy even with low network connectivity. This indicates the good localization performance of our proposed scheme in sparse region.
5. Conclusions
Due to the uncertainties in anchor positions and the bias in multihop estimative distances, the UWSNs multihop localization needs to take both the independent variable errors and the dependent variable biases into account. In this paper, we address these issues and give an anchor position error-tolerant multihop localization method based on the orthogonal regression for UWSNs. Through extensive simulations, we demonstrate that the proposed method can give more accurate results in various environments. In most cases, compared with the conventional nonlinear least square methods that ignore anchor position errors and distance estimation biases, our method could improve the localization accuracy by at least 10%. In irregular networks, the advantage of our method is more obvious. On the basis of improving the tolerance capability to anchor position errors, how to reduce the adverse influence of anchor ratio and anchor placement on multihop localization is a main topic of our further study.
Footnotes
Appendix
Conflict of Interests
The authors declare that there is no conflict of interests regarding the publication of this paper.
Acknowledgments
The authors are grateful to the anonymous reviewers for their industrious work and insightful comments. This work is supported by National Natural Science Foundation of China under Grant nos. 61001138 and 61201317.
