Set-Membership Adaptive Localization Algorithm with Time-Varying Error Bounds for Underwater Wireless Sensor Networks

Abstract

This paper presents a set-membership adaptive localization algorithm with time-varying error bounds for underwater wireless sensor networks (UWSNs). In large-scale UWSNs, the nonstationary underwater environments, the insufficient prior information of hybrid noise, the small sample size of available distance measurements, and the node mobility all pose severe challenges for localization, and most current schemes are not applicable. Unlike most of the existing approaches, we tackle the multihop localization problem in a set-membership framework based on the consideration that the distance measurement uncertainty can be cast into an unknown but bounded (UBB) context. The principle of our scheme is firstly to use the bootstrap method to build confidence intervals and error bounds from a small sample set of distance measurements and then to determine the positions by a low-complexity interval analysis method as well as an adaptive localization update specification with time-varying error bounds. Simulation results show that our proposed scheme is an effective and efficient localization approach in large-scale UWSNs.

1. Introduction

Underwater wireless sensor networks (UWSNs) as new technologies have attracted a rapidly growing interest from researchers during the last few years. They brought us a new way to sense and monitor the extensive aqueous environment, which has significant advantages over traditional approaches, such as easy deployment, self-management, and no requirement for established infrastructure. Typically applications include but are not limited to naval surveillance, earthquake and tsunami forewarning, climate and ocean observation, and water pollution tracking. For most UWSNs applications, localization is a fundamental task which is required for data tagging, node tracking, and target detection, and it can be used for improving the performance of medium access and network protocols [1].

As we know, since radio and optical signals cannot travel far in adverse underwater environments due to the attenuation or scattering, acoustic communication emerges as the primary choice for underwater communications. Unlike radio propagation in terrestrial networks, underwater acoustic propagation possesses some unique characteristics, for example, long propagation delays, limited bandwidth, multipath interference, sound speed variation, high unreliability, low bit rate, Doppler effect, and so forth. These characteristics pose severe challenges towards the localization scheme using acoustic range measurements for large-scale UWSNs [2].

On the one hand, due to the low bandwidth of the acoustic channel, data rates are lower than they are in terrestrial WSNs. Generally, the data rates can be increased by shortening the communication ranges which means more sensor nodes will be required to maintain a certain level of connectivity and coverage. For the large-scale UWSNs, this situation will no doubt result in a greater extra cost. Fortunately, multihop localization methods can elegantly handle this situation without any additional requirements [3–7]. With the multihop approach, the ordinary nodes not only can directly measure the distance by short-range communications, but can-also infer the distances to nonneighboring anchors through approximating the length of the shortest path to the Euclidean distance. That means the ordinary nodes can complete the self-localization even if the UWSNs are deployed sparsely with few anchor nodes. Hence, the multihop localization approach is very suitable for large-scale UWSNs localization.

On the other hand, both the multipath effect and the sound speed variation can result in significantly biased range estimates, which further leads to degradation of localization accuracy. As we know, the direct path (i.e., line of sight) can be determined by the strongest signal or the first arrival signal in terrestrial WSNs. However it is not the case in UWSNs. Because the speed of underwater sound waves changes with different pressure, salinity, and temperature, the sound waves propagating along the curved path may arrive before those in the direct path. Therefore, the conventional ranging method based on either the first arrival or the strongest path is not applicable to UWSNs. The range measurements will be significantly biased. The authors discussed various bias models in [8], but none of them is applicable to underwater localization. In [9], the authors employed the well-known Gerchberg-Saxton algorithm to address the bias problem that stems from the multipath effect. But the approach is not directly applicable to UWSNs localization due to the bias being assumed to be the same for all the range measurements. In a recent paper [10], a centralized localization method (WGSA) has been proposed to identify the direct path from all paths by associating each path with a weighting factor. However, the precondition is that one of the multiple propagation paths must be the direct path, which is not always satisfied in many practical scenarios (e.g., in Rayleigh channels). Moreover, the centralized approach is not applicable to large-scale UWSNs either.

In addition, the uncertainty of multihop distance measurements is also an important influence on localization accuracy. Many researches have partly focused on this issue. 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. But these methods perform well only when the measurement sample size is large and the hypothesis that measurement noises obey Gaussian distribution is satisfied. However, since underwater environments are dynamic and inhomogeneous, it is infeasible to guarantee repeatable ranging conditions for reproducible measurements to obtain lots of available measurements samples even when cost is not a main concern. Moreover, it is clearly unreasonable to directly assume the distance bias corresponding to the propagation paths following normal distribution or other specific distributions unless we have enough a priori information. Unfortunately, it is too hard for us to get enough prior information and exact distribution characteristics in adverse underwater environments.

Therefore, we introduce herein a set-membership multihop localization algorithm to address the problem caused by biased range measurements with unknown distribution. Set-membership is a well-known estimation approach based on the hypothesis that the noise is unknown but bounded (UBB noise). It is aimed at determining a feasible set which contains all admissible solutions [11]. In practical scenarios, it is a natural choice to assume the distance measurement uncertainty bounded in a certain interval rather than consider it as normal distribution. Conventional set-membership methods assume that the error bound is known and usually choose one prespecified error bound. However, in underwater, the known error bound may change with time due to the time-variability in underwater medium. In such cases, choosing one prespecified error bound value c is unreliable and has the risk of overbounding or underbounding, where the former could produce a loose intersection and the latter could result in a void admissible space. This makes the conventional set-membership methods with one fixed error-bound specification become improper. To resolve this problem, we propose a time-varying error bound specification for UWSN localization which can be derived based on the bootstrap approach. The principle of our algorithm is using the bootstrap method to build time-varying error bounds from a small sample set of distance measurements and to estimate the coordinates by set-membership estimation and interval analysis method.

This paper is organized as follows: Section 2 introduces the related works. Section 3 presents in detail the set-membership adaptive localization method. Section 4 evaluates the performance of our algorithm through experiments, and Section 5 concludes this paper.

2. Related Works

DV-distance and DV-hop algorithms, as the origination of multihop localization schemes for WSNs, are proposed in [3]. In both algorithms, each anchor node broadcasts a message to its immediate neighbor nodes firstly. Then, the message is propagated in a controlled flood manner so that each ordinary node can estimate the lengths of the shortest paths to anchor nodes. When the ordinary node obtains the estimates to enough anchor nodes, its position can be calculated. Specifically, the DV-hop algorithm is performed in three phases. In the first phase, each ordinary node communicates with its neighbor node to exchange a classical distance vector so that all ordinary nodes could obtain the distance in hops to the anchor nodes. In the second phase, the method calculates the average distance of a hop with the distance and hops information between each pair of anchor nodes. Hence, the ordinary nodes could compute the distance to anchor nodes with the hop count between them. In the last phase, localization algorithm such as trilateration is performed to calculate the ordinary nodes' coordinate with the distance information obtained by the second phase. Although DV-hop method could provide approximate position for ordinary nodes where few nodes have self-localization capability, its drawback is that this method only works effectively in isotropic networks. The process of DV-distance is similar to DV-hop, the only difference is that DV-distance utilizes the distance information obtained by signal strength to position instead of the hop information in DV-hop. In addition, DV-distance is more grained than DV-hop.

Wang and Xiao [4] presented an improved multihop algorithm called i-Multihop which has a higher computational complexity. At the beginning, the upper bound constraints are used to filter out the incorrect distance estimations, and the estimated position is pinpointed to the intersection constrained by the correct distances. And then, the distance fitting is used to fit correct distance measurements, which makes the final estimated position out of the effect by the layout of anchor nodes. The authors in [5] proposed three multihop localization schemes based on least squares and multilateration, namely, Taylor-LS, weighted Taylor based least squares and constrained total least squares, respectively. Additionally, a generalized Cramér-Rao lower bound is developed to analyze the performance of multihop localization approaches. In [6], the Monte Carlo localization (MCL), a dynamic localization scheme, has been proposed. In [7], a multihop algorithm that incorporates the distance estimation bias has been presented, which is based on the discovery that the multihop distance errors obey normal distribution with variable biases.

Most of the above schemes considered the measurement uncertainty as normal distribution even zero-mean normal distribution noise, but it is not always the case in severe underwater environments. Set-membership techniques have been utilized to tackle the localization problems due to the absence of a priori information.

Authors in [12] proposed an approach which dealt with the localization of AUVs in set-membership framework. Considering the multipath effect, the discussion and implementation in this paper both referred to the shallow water case. Although this algorithm had a similar performance compared with the triangulation, it could guarantee the regions to which the vehicle belongs with few prior knowledge. Taking account of the three main limitations of traditional localization methods in two-dimensional environment, authors in [13] proposed a novel localization method based on interval analysis. This method bypassed the complicated and time-consuming data-association step, extended the problem to nonlinear context, and handled the outliers effectively. Jaulin in [14] proposed a new observer which had three advantages over traditional methods. First of all, this observer was robust to outliers; in addition, it could deal with the state equations in a nonlinear system; finally, it had a good real-time characteristic. This method also had some limitations: firstly, it would lose the precision in continuous system; secondly, the maximum number of outliers must be satisfied; otherwise, it might return an empty set; thirdly, this method could not be applied to complex system because its time complexity had an exponential relation to the number of state variables.

3. Set-Membership Adaptive Localization Algorithm Based on Time-Varying Error Bounds

3.1. Set-Membership Approach and Problem Statement

Consider a UWSN consisting of m anchors with known positions and n ordinary nodes which need to be localized. The communication radius of ordinary nodes is R. The coordinates of node $N_i$ can be described by ${\mathbf{X}}_i={[x_i,y_i,z_i]}^T\in {\mathbf{R}}^3$ , $i=\mathrm{1,2},\dots ,m+n$ . Under the UBB noise context, the distance measurements from the ordinary node $N_o$ to anchor node $N_i$ can be described as $d_{oi}=D_{oi}+e_{oi}$ , where $D_{oi}={\parallel {\mathbf{X}}_o-{\mathbf{X}}_i\parallel }_2$ is the Euclidean distance, and $e_{oi}$ is considered as the UBB noise, bounded in a certain constant $|e_{oi}|<c$ , which accounts for all the uncertainties, for example, the ambient noise, multihop errors, and so forth. As a bonus, both the anchor position uncertainty which is commonly neglected and the uncertainty due to node possible dynamic movement which is influenced by waves and current can be treated as additional uncertainty. Then the localization issues can be tackled in a set-membership framework.

According to the set-membership estimation theory, the desired position estimate is guaranteed to be bounded by an admissible space known as feasible set:

$$\begin{array}{cc}& \mathbf{F}\left(\mathbf{x}\right)=\bigcap _{i=1}^k\left\{x\in {\mathbf{R}}^3:d_{oi}-c\le {\parallel {\mathbf{X}}_o-{\mathbf{X}}_i\parallel }_2\le d_{oi}+c\right\},\end{array}$$

(1)

where ${\mathbf{X}}_i$ is the coordinates of the ith anchor node with measured distance $d_{oi}$ to the ordinary node $N_o$ , where $i=\mathrm{1,2},\dots ,k$ .

As shown in Figure 1(a), the anchor nodes $N_i$ and $N_j$ are neighbouring anchors for $N_o$ . The feasible set $\mathbf{F}\mathbf{\left(}\mathbf{x}\mathbf{\right)}$ can be defined as the intersection of all the spherical caps. The centre of the spherical cap is the location of the anchor node. The internal and external radii are $r_{ao}=d_{ao}-c$ and $R_{ao}=d_{ao}+c$ , respectively. If $N_i$ is a multihop anchor node for $N_o$ , as shown in Figure 1(b), $N_o$ can receive $N_i^{\prime }$ coordinates through multihop information exchange and infers the multihop distance by approximating the length of the shortest path to the Euclidean distance. Assume that the shortest path passes the ordinary node $N_k$ ; then, the external radius can be inferred by ${(d}_{ik}+c)+{(d}_{ko}+c)$ , that is, $R_{io}=d_{ik}+d_{ko}+2c$ . Since $N_o$ is not in the communication range of $N_i$ , the Euclidean distance between them is bigger than R. Consequently, the internal radius can be defined as the communication rang R.

Figure 1

Feasible set of ordinary node $N_o$ (top view).

Clearly, the thickness of each spherical cap, that is, the admissible space, is particularly relevant to the bound value c, and the geometrical shape of $\mathbf{F}\mathbf{\left(}\mathbf{x}\mathbf{\right)}$ is commonly very complicated. It should be remarked that the foregoing situations raise two interesting problems which can influence the localization performance.

Firstly, conventional set-membership approaches commonly consider the error bound c as the necessary prior condition, and the performance of these techniques critically depends on the fixed error bound specification. However, for UWSNs localization, the error bound is very difficult to obtain in practice due to the lack of knowledge of the underwater environment and its dynamics. Even if we obtained the “true” bound constant c through extensive experiments, the known error bound would possibly change with time when the communication environments are highly dynamic, and the measured noise in the system is time varying. In such cases, the selection of an appropriate error bound is further complicated, and the risk of overbounding (when the error bound is larger than the actual one) or underbounding (when the error bound is smaller than the actual one) is significantly increased, leading to performance degradation.

Secondly, the complicated geometrical shape of $\mathbf{F}\mathbf{\left(}\mathbf{x}\mathbf{\right)}$ makes the exact computation infeasible due to the limited computational ability of ordinary nodes. This is particularly relevant for low complexity estimation problems encountered in UWSNs applications, where the sensors have limited signal processing capabilities, and power consumption is of central importance. This problem suggests the procedure of determining locations to guarantee reduced computational complexity and good localization performance.

3.2. Bootstrap Based CI and Error Bounds Estimation

Based on the consideration that it is not feasible to obtain a lot of available distance measurements sample and exact distributions of hybrid measured noise for conventional statistical methods, we adopt a bootstrap approach to build a confidence interval and error bound online. Bootstrap was originally introduced by Efron in [15] and used to address CI estimate for statistics based on independent and identically distributed (i.i.d.) random variable from some unknown distribution $F(\mu ,\sigma )$ [16]. The advantage of this method is that it does not require any modeling or assumptions on the data.

The basic concept of bootstrap is to produce a large number of independent bootstrap distance estimates by resampling the original distance estimate; that is, $X=(d_1,d_2,\dots ,d_n)$ which consists of n measurements at random from unknown probability distribution $F(\mu ,\sigma )$ .

A bootstrap resample $X^{*}=(d_1^{*},d_2^{*},\dots ,d_n^{*})$ is obtained as a random sample of size n randomly drawn with replacement from the original measurement set X. Sample X has true mean θ; drawing various other samples X from the distribution F, their means will present distribution $\widehat{\theta }$ . The distribution of real estimated mean $\widehat{\theta }$ is approximated by the distribution of pseudoestimated mean ${\widehat{\theta }}^{*}$ from bootstrap resample $X^{*}$ .

Let $X=(d_1,d_2,\dots ,d_n)$ represent the set of the distance measurements corresponding to the multiple propagation paths. Using the nonparametric percentile bootstrap method on this set, we generate B resamples, $X_j^{*}=(d_{1j}^{*},\dots ,d_{nj}^{*})$ , $j=1,\dots ,B$ . And then, we calculate the mean of all measurements in $X_j^{*}$ to obtain ${\widehat{\theta }}_{X_j^{*}}^{*}$ given by

$$\begin{array}{cc}& {\widehat{\theta }}_{X_j^{*}}^{*}=\frac{1}{N}\sum _{k=1}^N{d}_{kj}^{*},\end{array}$$

(2)

where N is commonly smaller than 5 (which is a reasonable value and common situation in UWSNs localization), and $j=1,\dots ,B$ . The means of this distribution are given as

$$\begin{array}{cc}& {\widehat{\theta }}_X^{*}=\frac{1}{B}\sum _{j=1}^B{\widehat{\theta }}_{X_j^{*}}^{*}.\end{array}$$

(3)

We sort bootstrap estimates ${\widehat{\theta }}_{X_j^{*}}^{*}$ in an ascending order. Let the sorted distance be given by

$$\begin{array}{cc}& {\widehat{\theta }}_{X_{\left(1\right)}^{*}}^{*}\le {\widehat{\theta }}_{X_{\left(2\right)}^{*}}^{*}\le {\widehat{\theta }}_{X_{\left(3\right)}^{*}}^{*}\le \cdots \le {\widehat{\theta }}_{X_{\left(B-1\right)}^{*}}^{*}\le {\widehat{\theta }}_{X_{\left(B\right)}^{*}}^{*}.\end{array}$$

(4)

The desired $100·(1-\alpha )\%$ nonparametric CI for the distance is given by $({\widehat{\theta }}_{X(Q_1)}^{*},{\widehat{\theta }}_{X(Q_2)}^{*})$ , where $Q_1$ is the integer part of $B\alpha /2$ , $Q_2=B-Q_1+1$ , and $Q_3$ is the integer part of $B/2$ .

Furthermore, note that

$$\begin{array}{cc}& {\widehat{\theta }}_{X\left(Q_1\right)}^{*}=\frac{1}{N}\sum _{k=1}^N{d}_{k,Q_1}^{*},\\ {\widehat{\theta }}_{X\left(Q_2\right)}^{*}=\frac{1}{N}\sum _{k=1}^N{d}_{k,Q_2}^{*},\\ {\widehat{\theta }}_{X\left(Q_3\right)}^{*}=\frac{1}{N}\sum _{k=1}^N{d}_{k,Q_3}^{*}.\end{array}$$

(5)

$Q_1$ , $Q_2$ , and $Q_3$ are referred to as the upper, lower, and middle points, respectively.

Finally, we can obtain the interval

$$\begin{array}{cc}& \left[{\widehat{\theta }}_{\text{lower}},{\widehat{\theta }}_{\text{upper}}\right]=\left[{\widehat{\theta }}_{X\left(Q_1\right)}^{*},{\widehat{\theta }}_{X\left(Q_2\right)}^{*}\right]\end{array}$$

(6)

as the CI of distance corresponding to confidence level $1-\alpha$ . Median point ${\widehat{\theta }}_{X(Q_3)}^{*}\cong {\widehat{\theta }}_X^{*}$ is almost identical to the mean. The upper, middle, and lower points are used by the algorithm to estimate the CIs for the distance, respectively. For $\alpha =\mathrm{0.05}$ and $B=1000$ , we can get $Q_1=25$ , $Q_2=976$ , and $Q_3=500$ . And the CI corresponding to confidence level 95% can be described as $[{\widehat{\theta }}_{X(25)}^{*},{\widehat{\theta }}_{X(976)}^{*}]$ .

On this basis, we can utilize the CI of multipath measured distance from $N_o$ to $N_i$ instead of the point estimate of distance, that is, $[{\widehat{d}}_{{oi}_{\text{lower}}},{\widehat{d}}_{{oi}_{\text{upper}}}]$ . Then the feasible set can be rewritten as

$$\begin{array}{cc}& S\left(x\right)=\bigcap _{i=1}^k\left\{{\widehat{d}}_{{oi}_{\text{lower}}}\le {\parallel X_o-X_i\parallel }_2\le {\widehat{d}}_{{oi}_{\text{upper}}}\right\}.\end{array}$$

(7)

We can see that the desired position estimate is guaranteed to be bounded by an admissible space with corresponding internal and external radii $r_{oi}={\widehat{d}}_{{oi}_{\text{lower}}}$ and $R_{oi}={\widehat{d}}_{{oi}_{\text{upper}}}$ , respectively. At the same time, the error bound ${\gamma }_{oi}$ can be denoted as:

$$\begin{array}{cc}& {\gamma }_{oi}={\widehat{d}}_{{oi}_{\text{upper}}}-{\widehat{d}}_{{oi}_{\text{lower}}}.\end{array}$$

(8)

3.3. Determination of Coordinates

As mentioned before, the complex geometrical shape of $S(x)$ results in a high computational complexity. To reduce the computational burden, boxes are utilized to approximate the irregular intersection of all feasible solutions. For each anchor ordinary pair, their admissible space represents a region between two boxes of length $\sqrt{2}{r}_{oi}$ and $2R_{oi}$ , respectively. Then, the interval analysis method will be utilized to determine the positions of ordinary nodes.

As we know, the interval analysis is usually used to model quantities that vary around a central value within certain bounds. With simple operations, the interval analysis allows to consistently deal with problems involving interval data. Based on the interval analysis theory, the CI of measured distance from $N_o$ to $N_i$ $[{\widehat{d}}_{{oi}_{\text{lower}}},{\widehat{d}}_{{oi}_{\text{upper}}}]$ can be denoted by ${\vartheta }^I=[{{\vartheta }^I}^{-},{{\vartheta }^I}^{+}]$ , where ${\vartheta }^I$ is a closed and connected subset of R, ${{\vartheta }^I}^{-}$ and ${{\vartheta }^I}^{+}$ are the minimal and maximal bounds of ${\vartheta }^I$ , respectively. Set theory operations, such as intersection, can be applied to intervals. Consider two intervals ${\vartheta }_{o1}^I$ and ${\vartheta }_{o2}^I$ ; their intersection is always an interval which can be denoted as

$$\begin{array}{cc}& {\vartheta }_{o1}^I\cap {\vartheta }_{o2}^I=\left[\left\{\vartheta \mid \vartheta \in {\vartheta }_{o1}^I,\vartheta \in {\vartheta }_{o2}^I\right\}\right].\end{array}$$

(9)

The intersection can be computed by

$$\begin{array}{cc}& {\vartheta }_{o1}^I\cap {\vartheta }_{ao2}^I=\left[\max \left\{{{\vartheta }_{o1}^I}^{-},{{\vartheta }_{o2}^I}^{-}\right\},\min \left\{{{\vartheta }_{o1}^I}^{+},{{\vartheta }_{o2}^I}^{+}\right\}\right].\end{array}$$

(10)

Therefore, the feasible set $S(x)$ of ordinary node $N_a$ can be rewritten as

$$\begin{array}{cc}& {\Omega }_o=\bigcap _{i=1}^k\left\{\vartheta \in {\vartheta }^I:{\vartheta }_{oi}^I=\left[{{\vartheta }_{oi}^I}^{-},{{\vartheta }_{oi}^I}^{+}\right]\right\}.\end{array}$$

(11)

Clearly, the intersection of all subfeasible set ${\vartheta }_{oi}^I$ is a set of boxes. Regarding the coordinates of all subboxes' centers as samples of ${\mathit{X}}_o$ , we can get a sample set

$$\begin{array}{cc}& \Omega =\left\{{\mathrm{\Theta }}_1,{\mathrm{\Theta }}_2,\dots ,{\mathrm{\Theta }}_n\right\};\end{array}$$

(12)

the centre of ${\mathrm{\Theta }}_n$ can be found by ${\vartheta }_n^{*}=({\vartheta }^{-}+{\vartheta }^{+})/2$ .

The optimum point estimate, that is, the desired coordinates, can be obtained by

$$\begin{array}{cc}& {\widehat{X}}_o=\hspace{0.17em}\arg \underset{X_o}{\min }\hspace{1em}\sum _i^k{\left({\parallel {\vartheta }_n^{*}-X_i\parallel }_2-d_{oi}\right)}^2\\ \hspace{0.17em}\text{subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\hspace{1em}{X}_o\in S\left(x\right).\end{array}$$

(13)

Finally, the coordinates can be given as

$$\begin{array}{cc}& {\widehat{X}}_o={\left[{\widehat{\vartheta }}_n^{*}\left(1\right),{\widehat{\vartheta }}_n^{*}\left(2\right),{\widehat{\vartheta }}_n^{*}\left(3\right)\right]}^T.\end{array}$$

(14)

3.4. Set-Membership Adaptive Localization with Time-Varying Error Bounds

By the foregoing procedure, we can obtain the location estimation at one point in time. Conventional localization algorithms commonly repeat the localizing process and update the locations with a prespecified time interval and a fixed error bound specification. To achieve good convergence and reduced localization burden, resolve the problem of overbounding or underbounding in the meanwhile, we propose an adaptive step size with time-varying error bound specification for each update.

We can rewrite the set-membership feasible set model of ordinary node $N_o$ as

$$\begin{array}{cc}& {\mathbf{W}}_o=\bigcap \left\{w\in {\mathbf{R}}^3:{\mathrm{\Psi }}^{-}\le \left|{\mathbf{H}}^T{\mathbf{W}}_o\right|\le {\mathrm{\Psi }}^{+}\right\},\end{array}$$

(15)

where ${\mathbf{W}}_o={[{\mathbf{X}}_1{\mathbf{X}}_2\cdots {\mathbf{X}}_{n+m}]}^T$ represents the location of all sensor nodes, ${\mathrm{\Psi }}^{\mathbf{-}}$ is a column vector including all the lower bounds of the distance estimation, and ${\mathrm{\Psi }}^{\mathbf{+}}$ is the vector corresponding to the upper bounds of CI. Define $h_{ij}$ as an $(n+m)\times 1$ vector whose ith element is 1 and jth element is −1, such that $h_{ij}^T{\mathbf{W}}_o\mathbf{=}{\mathbf{X}}_i-{\mathbf{X}}_j$ . Then let H be a matrix formed by stacking the row vectors $h_{ij}^T$ on top of each other, where the value corresponding to $N_o$ is 1, and the numbers corresponding to the anchors are all −1.

At time n and for the kth anchor node, constraint set $S_{o,k}(n)$ is defined as the set of all $W_o(n)$ that satisfies (15) for the pairs ( ${\mathrm{\Psi }}_{o,k}(n)$ , $H_{o,k}^T(n)$ ):

$$\begin{array}{cc}& S_{o,k}\left(n\right)=\left\{{\mathrm{\Psi }}_{o,k}^{-}\left(n\right)\le \left|H_{o,k}^T\left(n\right)W_o\left(n\right)\right|\le {\mathrm{\Psi }}_{o,k}^{+}\left(n\right)\right\}.\end{array}$$

(16)

If we consider the instant n as the initial time, we can obtain the ${\widehat{X}}_o$ , ${{\vartheta }^I}^{-}$ , ${{\vartheta }^I}^{+}$ as the initial conditions through the bootstrap approach.

Clearly, at time n, $\mathrm{\Psi }(n)$ , ${\mathbf{W}}_o(n)$ , and $\mathbf{H}(n)$ satisfy the following formulation:

$$\begin{array}{cc}& {\mathrm{\Psi }}^{-}\left(n\right)\le \left|{\mathbf{H}}^T\left(n\right){\mathbf{W}}_o\left(n\right)\right|\le {\mathrm{\Psi }}^{+}\left(n\right).\end{array}$$

(17)

And at the same time, the error bound ${\mathbf{\gamma }}_o(n)$ can be denoted as

$$\begin{array}{cc}& {\mathit{\gamma }}_o\left(n\right)={\mathrm{\Psi }}^{+}\left(n\right)-{\mathrm{\Psi }}^{-}\left(n\right).\end{array}$$

(18)

Then, the set-membership adaptive algorithm with time-varying error bounds can be described as follows.

For the next time instant $n+1$ , if

$$\begin{array}{cc}& {\mathrm{\Psi }}^{-}\left(n+1\right)\le \left|{\mathbf{H}}^T\left(n\right){\mathbf{W}}_o\left(n+1\right)\right|\le {\mathrm{\Psi }}^{+}\left(n+1\right),\end{array}$$

(19)

then

$$\begin{array}{cc}& {\mathbf{W}}_o\left(n+1\right)={\mathbf{W}}_o\left(n\right),\end{array}$$

(20)

and no parameter update is needed.

Otherwise, ${\mathbf{W}}_o(n+1)$ is found by

$$\begin{array}{cc}& \min {\left|{\mathbf{W}}_o\left(n+1\right)-{\mathbf{W}}_o\left(n\right)\right|}^2,\\ {\mathrm{\Psi }}^{-}\left(n+1\right)\le \left|{\mathbf{H}}^T\left(n+1\right){\mathbf{W}}_o\left(n+1\right)\right|\le {\mathrm{\Psi }}^{+}\left(n+1\right),\end{array}$$

(21)

where

$$\begin{array}{cc}& {\mathbf{e}}_o\left(n+1\right)=\widehat{\mathrm{\Psi }}\left(n+1\right)-\left|{\mathbf{H}}^T\left(n\right){\mathbf{W}}_o\left(n+1\right)\right|,\\ {\mathbf{\gamma }}_o\left(n+1\right)={\mathrm{\Psi }}^{+}\left(n+1\right)-{\mathrm{\Psi }}^{-}\left(n+1\right).\end{array}$$

(22)

By choosing an appropriate step size such that ${\mathbf{e}}_o(n+1)$ lies on the closest boundary of ${\mathbf{W}}_o(n+1)$ and considering a time-varying error bound ${\mathbf{\gamma }}_o(n+1)$ , we can obtain the following data-dependent update rule and adaptive step size:

$$\begin{array}{cc}& {\mathbf{W}}_o\left(n+1\right)={\mathbf{W}}_o\left(n\right)+{\mu }_w\left(n+1\right){{\mathbf{e}}_o}^{\mathbf{*}}\left(n+1\right)\mathbf{H}\left(n+1\right)\\ {\mu }_w\left(n+1\right)=\{\begin{array}{cc}\frac{1}{{\mathbf{H}}^H\left(n+1\right)\mathbf{H}\left(n+1\right)}\left(1-\frac{{\mathbf{\gamma }}_o\left(n+1\right)}{{{\mathbf{e}}_o}^{*}\left(n+1\right)}\right),\hfill & \hfill \\ \hspace{1em}\hspace{1em}\text{if}\hspace{0.17em}\hspace{0.17em}\left|{{\mathbf{e}}_o}^{*}\left(n+1\right)\right|>{\mathit{\gamma }}_o\left(n+1\right).\hfill & \hfill \\ 0,\hspace{1em}\text{otherwise}.\hfill & \hfill \end{array}\end{array}$$

(23)

4. Performance Evaluation

In this section, we conduct extensive simulations to evaluate the performance of our proposed localization algorithm. All simulations are run in MatLab R2012a. To reduce the influence of outliers, we take the average of 100 simulation runs as the final data points.

4.1. Simulation Settings

In our simulation experiments, 100 nodes with adjustable transmission range R are randomly distributed in a large-scale three-dimensional region with a size of $3000\times 3000\times 300$ (see Figure 2). We control the density and connectivity of the network by changing the communication range while keeping the deployment region the same. For comparison with classical approaches and showing the performance of our algorithm in non-Gaussian noises context, the measurement noise has been assumed to follow Rayleigh distribution, with two percent of real distances as the standard deviations. Besides our scheme, we also simulate the DV-distance localization scheme [3] and a set-membership underwater localization approach which is almost the same as [12] for comparison.

Figure 2

Topology of large-scale UWSNs.

We mainly consider three performance metrics: localization coverage, localization error, and localization complexity. Localization coverage is the ratio of the localized nodes to the total sensor nodes. Localization error is defined as the average distance between the estimated positions and the real positions of all nodes. As in [17–19], for our simulations, we normalize this absolute localization error to the node's communication range R. The analysis of localization complexity mainly focuses on the communication cost and computation complexity.

4.2. Localization Coverage

In this subsection, we analyze the performance of localization coverage with different network connectivity. Figure 3 shows the performance of localization coverage with changing network connectivity while anchor percentage is 10%. We can observe that our localization coverage increases monotonically with the connectivity ranging from 4 to 13. But when the connectivity reaches a high value, the coverage rate becomes relatively large and will not change much after that. For example, when the network connectivity is 8, the localization coverage becomes 95% and then changes slower. The reason is that when the network connectivity reaches a certain point, most nodes can get enough anchor nodes by multihop approach and localize themselves. Compared with the results of DV-distance, we can achieve better performance in terms of localization coverage, especially in low network connectivity.

Figure 3

Localization coverage versus network connectivity.

4.3. Localization Error

Figure 4 shows the localization error which is normalized by R with the changing network connectivity in different error distributions. Specifically, the measurement noise has been assumed to follow Rayleigh distribution, with five percent of real distances as the standard deviations. This is a reasonable assumption and can be satisfied by the existing distance measurement technologies when suffering of multiple adverse factors. Compared with the DV-distance scheme, our scheme can always achieve much higher localization accuracy. Particularly in large-scale and sparse network with smaller connectivity and anchor percentage, our proposed method can get a higher average localization accuracy.

Figure 4

Localization error versus network connectivity.

Figure 5 plots the relationship between the average localization error and the varying standard deviations of noise distribution. Besides our scheme, we also simulate a set-membership localization approach [12] for comparison which employs a fixed error bound specification. We can observe that the average localization error of our scheme decreases significantly with the increase of network connectivity. And it can be seen that our scheme outperforms the common set-membership method in both cases. It indicates that our scheme is less affected by the variation of distributions. 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.

Figure 5

Localization error versus different distribution.

4.4. Localization Complexity

In this subsection, we analyze the localization complexity of the schemes which mainly focuses on the communication cost and computation complexity. For a network with m anchor nodes and n ordinary nodes, the overall communication complexity of our scheme is $O(mn)$ . Firstly our scheme needs the m times flooding initiated by m anchors to make the ordinary nodes know their hop counts, whose overhead is $O(mn)$ . Besides the flooding, our scheme requires each anchor to propagate its hop counts to three or four hops' neighboring nodes by a confined flooding. This also has the overhead of $O(mn)$ . The communication complexity of DV-distance is equal to that of our scheme. But when the algorithms need more distance samples for parametric statistics or location refinement, our scheme can achieve much lower communication cost compared with DV-distance. This is due to the fact that our scheme obtained lots of distance samples by bootstrap resampling approach rather than repeating communication with anchors which introduces a large communication cost for DV-distance. This characteristic is particularly important when the network is sparse. Of course, in this case, the computation complexity of our scheme will be larger than DV-distance because the resampling process is necessary when the original distance sample size is very small. For example, if there are only 6 effective distance measurement samples, our scheme needs to resample at least B times (>1000) for estimating the parameter and constructing the CI. Thus the computation complexity of our scheme is $O(BN)$ . Fortunately, in our scheme the location estimate can be obtained by simple enumeration instead of complex matrix arithmetic. And compared with the communication cost, the computation cost of our method is moderate and acceptable.

5. Conclusions

In this paper, we present a novel multihop localization algorithm with time-varying error bounds which is based on the bootstrap method and interval analysis approach for large scale UWSNs. In the first phase, the nonparametric bootstrap method is utilized to build a confidence interval of the distance from a small sample set of available measurements with unknown noise distributions. And then we adopt interval analysis approach to estimate the positions of ordinary nodes. On that basis, we integrate an adaptive localization update specification with time-varying error bounds to resolve the problem of overbounding or underbounding and to achieve good convergence and reduced localization burden. The simulation results demonstrate that our algorithm can get high localization coverage and accuracy while resisting against the variation of unknown noise distributions. Compared with the traditional method DV-distance, the proposed method can greatly improve the average localization accuracy.