Multihops Fitting Approach for Node Localization in Underwater Wireless Sensor Networks

Abstract

Nodes in underwater wireless sensor networks (UWSNs) keep moving and dispersing due to force of water flow and aquatic creatures touching, and thus some isolated unknown nodes emerge. This type of isolated unknown nodes cannot directly communicate with enough beacons in their neighborhoods, which makes localizations for them disabled or the localization error unbearable. To this end, a multihops fitting localization approach is proposed in this paper. Firstly, some intermediate nodes between beacons and unknown nodes are set as routers to construct paths via a greedy method; then, the multihop paths are approximately fitted into straight lines; finally, the positions of unknown nodes can be estimated by trilateration. The proposed algorithm is analyzed and simulated in terms of localization error and error variance, and the results are proven preferable.

1. Introduction

Water covers more than 70 percent of the surface on the earth. In order to utilize the underwater resources, there is great interest in the exploration of underwater wireless sensor networks (UWSNs). UWSNs are regarded as extension of terrestrial wireless sensor networks, and they are composed of a large number of underwater sensors. This system can collect hydrologic data such as temperature, pressure, PH value, and salinity-alkalinity and so on; hence many applications can be made such as environment management, resources protection, hazard monitoring, and military detecting [1]. These applications are usually required to learn the coordinates of sensor nodes; accordingly, localization for unknown nodes in UWSNs is very important. There are three types of nodes in UWSNs: surface buoys, beacons, and unknown nodes. The given phenomenon is observed mostly by unknown nodes and beacon nodes, which are interconnected and are in charge of relaying the data to surface sinks. The architecture of UWSNs is depicted in Figure 1.

Figure 1

UWSN architecture.

(a) Surface buoys are equipped with GPS systems [2]; thus they can get their coordinates easily. Each buoy communicates with the beacon nodes using acoustic transceiver periodically and then sends messages including the information of its position and so on [3]. The acoustic communication can be available even in deep underwater [4].

(b) Beacon nodes mainly give help to estimating the coordinates of unknown nodes. They usually own more energy and larger communication ranges. Every unknown node keeps listening until more than 3 position messages from beacons have been received.

(c) Unknown nodes are generally used to gather interest data and are assumed to own limited battery energy, so they usually keep silent until they hear from beacon nodes by broadcasting messages [5]; then their coordinates are estimated approximatively.

In traditional 3D underwater localization algorithms, at least four beacons are necessary to locate one unknown sensor node's position (X coordinate, Y coordinate, and Z coordinate). It is assumed that all the underwater nodes including beacons and unknown nodes are equipped with pressure sensors so that the depths (Z coordinate) of the nodes can be acquired directly by USP [6]. Then we can use three beacons to finish the localization.

Underwater sensor nodes keep moving and diffusing due to water flowing or aquatic creatures touching after they are deployed [7], what produces some isolated nodes. These isolated nodes cannot search for enough beacons in their neighboring ranges and thus the localizations are disabled. There are two kinds of methods for this problem. The first one is called AUV-aided algorithm [8, 9], in which AUV travels to an area where isolated nodes exist and then it serves as a localization reference. However, this method cannot provide real-time localization, especially in large scale UWSNs, because the number of AUVs is scarce and they move slowly; the other is multihop localization algorithm, which takes intermediate nodes between beacons and unknown nodes as routers to transmit the coordinates from beacons. This method will be adopted and improved in the remaining part of this paper.

The remainder of the current study is organized as follows. Section 2 provides a brief overview of related work. In Section 3, we propose a multihop localization algorithm for UWSNs. Section 4 gives some mathematical analysis about the scheme of our research. In Section 5, the proposed algorithm is validated by simulations in terms of localization error and error variance. Section 6 is the conclusion.

This work is the extension of our early work [10]; the main differences between the two papers are as follows. (1) The algorithm is given additional explanation and is discussed from different cases; (2) the theoretical analysis of algorithm has been improved and extended; (3) more simulations have been done and supplied.

2. Related Work

The localization schemes of terrestrial sensor networks usually use radio wave to communicate among nodes. However, the radio wave underwater can propagate a very short distance, and the fact makes the existing terrestrial localization algorithms be not suitable for UWSNs. In UWSNs, sensor nodes communicate with each other by acoustic channels because sound is the only available medium for long distance transmission underwater [11–13]. In this section, we will briefly review some localization algorithms for UWSNs.

Most localization algorithms for UWSNs can be roughly divided into two steps: (1) calculation of distance between unknown nodes and beacons; (2) implement of localization. Range-free protocols [14] and range-based protocols [15] are usually used in the first step. In [16], an improved DV-Hop localization method based on range-free is proposed, and it overcomes the bad localization accuracy. In range-based protocols, more accurate distance information is used for localization, such as Received Signal Strength Indicator (RSSI) [17], Time of Arrival (ToA) [18], Time Difference of Arrival (TDoA), and Angle of Arrival (AoA) [19]. In the second step, the most typical algorithm is trilateration [20], where the localizations of unknown nodes are supported by not less than three beacons [21]. Nevertheless, if unknown nodes cannot find enough beacons, then this algorithm will be disabled due to lacking of distance for localization.

Reference [22] applies a static path to improve the localization accuracy by considering the path of a mobile beacon and the deployment of beacons. This research suggests the determined static path provides higher localization accuracy than a random path or others, but the path interval abates localization accuracy greatly and the movement trajectory of mobile beacon nodes is almost unpredictable. In [23], authors assume a sparse UWSN where sensor nodes have poor connectivity with each other and then proposes an algorithm named Mobility Assisted MDS-MAP(P), which is based on Multidimensional Scaling (MDS). In this method, mobile sensor nodes keep moving and recording the distances to neighbor nodes at some intermediate locations, which provides extra range measurements. In [24], an Efficient Mobility Based Localization (EMBL) is proposed. During the localization process every node predicts its future mobility pattern according to its historical trajectory. The contacting with beacons is not necessary for isolated nodes due to mobility prediction. But nodes prediction has a poor accuracy when the underwater environment is extremely complex. Reference [25] employs intermediate nodes between beacons and unknown nodes as routers [26] to build a shortest path via greedy approach, as shown in Figure 2; the shortest path is approximately taken as a straight line linking unknown nodes and beacons. However, this algorithm manifests poor performance when the routers are too much. The problem of multihops localization has not been paid enough attention, and especially large error is easily produced by current multihops localization approaches. The traditional multihop localization methods using greedy arithmetic result in an unsatisfactory localization error, which motivates us to put forward the Multihops Fitting Localization Approach (MFLA).

Figure 2

Path selection.

3. Algorithm

Suppose that plenty of sensors nodes are deployed in 3D underwater cuboid space $\mathbf{D}\in \mathbf{I}{\mathbf{R}}^{\mathrm{3}}$ , the volume of which is $L\times W\times H$ . U, and B denote unknown nodes set and beacons set, respectively, where $\mathbf{U}=\{U_{\mathrm{1}},U_{\mathrm{2}},\dots ,U_m\}$ , $\mathbf{B}=\{B_{\mathrm{1}},B_{\mathrm{2}},\dots ,B_n\}$ . The number of unknown nodes and beacons are denoted as m, n, and $m+n$ is the total number of nodes. The coordinate of one node $V_i$ ( $V_i\in \mathbf{U}\mathbf{\cup }\mathbf{B}$ ) is marked as $(x_i,y_i,z_i)$ .

Each node has a rotatable acoustic transmitter and receiver. As shown in Figure 3, acoustic transmitter and receiver on nodes can rotate anticlockwise in the horizontal direction.

Figure 3

Rotatable acoustic transmitter and receiver.

MFLA will be executed when unknown nodes cannot find 3 neighboring beacons. Some intermediate nodes are employed to form a polygonal line from the unknown nodes to the nearest beacons; subsequently, this polygonal line is fitted (by a recursion of cosine computation) for trilateration localization. The detailed description and flowchart of MFLA are given as follows.

Step 1.

Each beacon (suppose $B_i$ ) broadcasts an $announce\_msg$ after a random backoff time. After reception of the message from $B_i$ , the unknown node (suppose $U_j$ ) replies a $reply\_msg$ . Thus the distance $\mathrm{d}\mathrm{i}\mathrm{s}(B_i,U_j)$ can be computed by measured time-of-arrival (TOA) [27]. In detail, the distance $\mathrm{d}\mathrm{i}\mathrm{s}(B_i,U_j)$ is calculated through the following formula [28]:

$$\begin{array}{l}\text{dis}\left(B_i,U_j\right)\\ =\left[\mathrm{1449.2}+\mathrm{4.623}t-\mathrm{0.0546}{t}^{\mathrm{2}}+\mathrm{1.391}\left(\sigma -\mathrm{35}\right)\right]\\ ·\left(T_r-T_s\right),\end{array}$$

(1)

where t is water temperature, σ is water salinity, $T_r$ is the sending time of beacon message from $B_i$ , and $T_s$ is the arrival time of message.

Step 2.

All neighboring beacons of $U_j$ will be recorded as a beacon set $bec\_list(U_j)$ .

Step 3.

If $|bec\_list(U_j)|\ge \mathrm{3}$ , the coordinate of $U_j$ will be computed via trilateration localization; else go to Step 4.

Step 4.

Suppose $U_j$ satisfies $|bec\_list(U_j)|<\mathrm{3}$ ; then $U_j$ broadcasts an $inquire\_msg$ to neighboring unknown nodes. This message will be forwarded until all unknown nodes have received one copy. Every receiver will forward $inquire\_msg$ provided that it has not received before, so this forwarding manner is a kind of flooding. Receivers answer $U_j$ with their beacon sets via a directed diffusion way [29]; after that, information of other beacons is obtained by $U_j$ ; thus the routing paths from new beacons to $U_j$ can be calculated at $U_j$ , as shown in Figure 4. Then intermediate nodes record the intersection angles between receivers and senders. In Figure 4, the antenna of $U_j$ rotates to a particular direction to receive the $announce\_msg$ from $B_i$ ; afterwards, $U_j$ sends a $reply\_msg$ . The receiving time and sending time (denoted as $t_{\mathrm{1}}$ and $t_{\mathrm{2}}$ , resp.) will also be recorded by $U_j$ . Then, $U_j$ rotates its antenna to communicate with $U_k$ , and the rotating angle will be taken as the intersection angle between $B_i$ and $U_k$ . The structure of $bec\_list$ is shown as Table 1.

Besides, an example for routing formation is given in Figure 5. Neighboring beacons (at least 3) will be found by a greedy method, and routing table can be produced. The path from $B_{\mathrm{1}}$ to $U_{\mathrm{1}}$ is $B_{\mathrm{1}}\to I_{\mathrm{1}}\to I_{\mathrm{2}}\to I_{\mathrm{4}}\to U_{\mathrm{1}}$ , and the path from $B_{\mathrm{2}}$ to $U_{\mathrm{1}}$ is $B_{\mathrm{2}}\to I_{\mathrm{3}}\to I_{\mathrm{4}}\to U_{\mathrm{1}}$ .

Table 1

Structure of $$bec\_list$$ .

Field	Description
$$Bec\_ID$$	Identifier of beacons
X	Coordination of x axis
Y	Coordination of y axis
Z	Coordination of z axis
Distance	Distance from it to beacons
Router_set	Intermediate nodes between it and beacons

Figure 4

Polygonal line paths.

Figure 5

Example of routing formation.

Step 5.

A path with minimum hops from an unknown node $U_m$ to a remote beacon $B_i$ (as shown in Figure 4) is selected. We define an intermediate node as $I_k$ ; moreover, $B_i$ always is the $I_{\mathrm{1}}$ ; The distance between $I_{k-\mathrm{1}}$ and $I_k$ is, namely, $d^{(B_i,U_m)}(k-\mathrm{1},k)$ ;   ${\theta }^{(B_i,U_m)}(k)$ denotes the interior angle between $d^{(B_i,U_m)}(k-\mathrm{1},k)$ and $d^{(B_i,U_m)}(k,k+\mathrm{1})$ ; $d^{(B_i,U_m)}(k-\mathrm{1},k+\mathrm{1})$ is a fitted straight line between $I_{k-\mathrm{1}}$ and $I_{k+\mathrm{1}}$ . The computation of interior angle should be discussed from the following cases.

Case 1.

When $k=\mathrm{2}$ , $d^{(B_i,U_m)}(i,k)$ can be obtained directly.

Case 2.

When $k=\mathrm{3}$ , as shown in Figure 6, if ${\theta }^{(B_i,U_m)}(k-\mathrm{1})<\pi$ then there will be $d^{(B_i,U_m)}(i,k)=\{d^{(B_i,U_m)}(i,k-\mathrm{1}{)}^{\mathrm{2}}+d^{(B_i,U_m)}(k-\mathrm{1},k{)}^{\mathrm{2}}-\mathrm{2}{d}^{(B_i,U_m)}(i,k-\mathrm{1})·d^{(B_i,U_m)}(k-\mathrm{1},k)·\mathrm{c}\mathrm{o}\mathrm{s}\hspace{0.17em}{\theta }^{(B_i,U_m)}(k-\mathrm{1}){\}}^{\mathrm{1}/\mathrm{2}}$ ; else if ${\theta }^{(B_i,U_m)}(k-\mathrm{1})\ge \pi$ then $d^{(B_i,U_m)}(i,k)=\{d^{(B_i,U_m)}(i,k-\mathrm{1}{)}^{\mathrm{2}}+d^{(B_i,U_m)}(k-\mathrm{1},k{)}^{\mathrm{2}}$  −  $\mathrm{2}{d}^{(B_i,U_m)}(i,k-\mathrm{1})·d^{(B_i,U_m)}(k-\mathrm{1},k)·\mathrm{c}\mathrm{o}\mathrm{s}\hspace{0.17em}(\mathrm{2}\pi -{\theta }^{(B_i,U_m)}(k-\mathrm{1})){\}}^{\mathrm{1}/\mathrm{2}}$ .

Figure 6

Computation of interior angle ( $k=\mathrm{3}$ ).

Case 3.

When $k>\mathrm{3}$ , there will be four different conditions of interior angles (Figure 7), which is marked as ${\delta }^{(B_i,U_m)}(k-\mathrm{1})$ :

$(\mathrm{a})$ if ${\theta }^{(B_i,U_m)}(k-\mathrm{2})<\pi ,{\theta }^{(B_i,U_m)}(k-\mathrm{1})<\pi$ , then ${\delta }^{(B_i,U_m)}(k-\mathrm{1})={\theta }^{(B_i,U_m)}(k-\mathrm{1})-{\alpha }^{(B_i,U_m)}(k-\mathrm{1})$ ;

$(\mathrm{b})$ if ${\theta }^{(B_i,U_m)}(k-\mathrm{2})<\pi ,{\theta }^{(B_i,U_m)}(k-\mathrm{1})\ge \pi$ , then ${\delta }^{(B_i,U_m)}(k-\mathrm{1})=\mathrm{2}\pi -{\theta }^{(B_i,U_m)}(k-\mathrm{1})+{\alpha }^{(B_i,U_m)}(k-\mathrm{1})$ ;

$(\mathrm{c})$ if ${\theta }^{(B_i,U_m)}(k-\mathrm{2})\ge \pi ,{\theta }^{(B_i,U_m)}(k-\mathrm{1})<\pi$ , then ${\delta }^{(B_i,U_m)}(k-\mathrm{1})={\theta }^{(B_i,U_m)}(k-\mathrm{1})+{\alpha }^{(B_i,U_m)}(k-\mathrm{1})$ ;

$(\mathrm{d})$ else if ${\theta }^{(B_i,U_m)}(k-\mathrm{2})\ge \pi ,{\theta }^{(B_i,U_m)}(k-\mathrm{1})\ge \pi$ , then ${\delta }^{(B_i,U_m)}(k-\mathrm{1})=\mathrm{2}\pi -{\theta }^{(B_i,U_m)}(k-\mathrm{1})-{\alpha }^{(B_i,U_m)}(k-\mathrm{1})$ . Moreover, the computation of ${\alpha }^{(B_i,U_m)}(k-\mathrm{1})$ can be given as ${\alpha }^{\left(B_i,U_m\right)}(k-\mathrm{1})$  =  $\arccos \hspace{0.17em}((d^{\left(B_i,U_m\right)}(i,k-1{)}^2+d^{\left(B_i,U_m\right)}(k-2,k-1{)}^2{d}^{\left(B_i,U_m\right)}(i,k-2{)}^2)/(2·d^{\left(B_i,U_m\right)}\left(i,k-1\right)·d^{\left(B_i,U_m\right)}(k-2,k-1)))$ . Therefore,

$$\begin{array}{l}{d}^{(B_i,U_m)}(i,k)=\{d^{(B_i,U_m)}{(k-1,k)}^2+d^{(B_i,U_m)}{(i,k-1)}^2\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}-2.d^{(B_i,U_m)}(k-1,k)\cdot d^{(B_i,U_m)}(i,k-1)\hfill \\ \hspace{0.17em}\cdot cos{\delta }^{(B_i,U_m)}(k-1){\}}^{1/2}\hfill \end{array}$$

(2)

Figure 7

Computation of interior angle ( $k>\mathrm{3}$ ).

Step 6.

Trilateration method is applied to locate the unknown node.

The execution flowchart of MFLA is given as Figure 8.

Figure 8

Flowchart of MFLA.

4. Mathematical Analysis

4.1. Distance Error

Firstly, assume that the real distance between node $I_{k-\mathrm{1}}$ and node $I_k$ within one hop is $d^{(B_i,U_m)}(k-\mathrm{1},k)$ and the estimated distance is $d^{\prime (B_i,U_m)}(k-\mathrm{1},k)$ . This error can be considered as a result of underwater acoustic transmission, and larger distance will lead to a larger error. Thus, $\Delta d^{(B_i,U_m)}(k-\mathrm{1},k)$ is linearly correlated with $d^{(B_i,U_m)}(k-\mathrm{1},k)$ approximately. A factor variable $\varepsilon \hspace{0.17em}\hspace{0.17em}(\varepsilon \in (-\mathrm{1,1}))$ is introduced to analyze a deviation distance $\Delta d^{(B_i,U_m)}(k-\mathrm{1},k)$ , and there are $\Delta d^{(B_i,U_m)}(k-\mathrm{1},k)=|d^{(B_i,U_m)}(k-\mathrm{1},k)-d^{\prime (B_i,U_m)}(k-\mathrm{1},k)|$ and $\Delta d^{(B_i,U_m)}(k-\mathrm{1},k)=\varepsilon ·d^{(B_i,U_m)}(k-\mathrm{1},k)$ . So one can get

$$\begin{array}{cc}& d^{\prime \left(B_i,U_m\right)}\left(k-\mathrm{1},k\right)=\left(\mathrm{1}+\varepsilon \right)·d^{\left(B_i,U_m\right)}\left(k-\mathrm{1},k\right).\end{array}$$

(3)

4.2. Multihops Fitting Error

The fitting error should also be discussed from the following cases.

Case 1.

When $k=\mathrm{2}$ , $d^{\prime (B_i,U_m)}(\mathrm{1,2})$ is apparently expressed as

$$\begin{array}{cc}& d^{\prime \left(B_i,U_m\right)}\left(\mathrm{1,2}\right)=\left(\mathrm{1}+\varepsilon \right)·d^{\left(B_i,U_m\right)}\left(\mathrm{1,2}\right).\end{array}$$

(4)

Case 2.

When $k=\mathrm{3}$ ,

$$\begin{array}{l}{d}^{\prime (B_i,U_m)}(1,3)=(1+\varepsilon )\cdot [d^{(B_i,U_m){(1,2)}^2}\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+d^{(B_i,U_m)}{(2,3)}^2-2\cdot d^{(B_i,U_m)}(1,2)\cdot d^{(B_{i,U_m})}(2,3)\hfill \\ \hspace{0.17em}\cdot cos{\theta }^{(B_i,U_m)}(2){]}^{1/2}.\hfill \end{array}$$

(5)

Because $\pi /\mathrm{3}\le {\theta }^{(B_i,U_m)}(\mathrm{2})\le \pi$ , therefore $-\mathrm{1}\le \mathrm{c}\mathrm{o}\mathrm{s}\hspace{0.17em}{\theta }^{(B_i,U_m)}(\mathrm{2})\le \mathrm{1}/\mathrm{2}$ .

Furthermore, there is $-d^{(B_i,U_m)}(\mathrm{1,2})d^{(B_i,U_m)}(\mathrm{2,3})\le -\mathrm{2}{d}^{(B_i,U_m)}(\mathrm{1,2})d^{(B_i,U_m)}(\mathrm{2,3})\mathrm{c}\mathrm{o}\mathrm{s}\hspace{0.17em}{\theta }^{(B_i,U_m)}(\mathrm{2})$  ≤  $\mathrm{2}{d}^{(B_i,U_m)}(\mathrm{1,2})d^{(B_i,U_m)}(\mathrm{2,3})$ ; then obviously there is

$$\begin{array}{l}{\{d^{(B_i,U_m)}(1,2)d^{(B_i,U_m)}(2,3)\}}^{1/2}\le \{d^{(B_i,U_m){(1,2)}^2}\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+d^{(B_i,U_m)}{(2,3)}^2\hfill \\ \begin{array}{l}\hspace{0.17em}-2d^{(B_i,U_m)}(1,2)d^{(B_i,U_m)}(2,3)cos{\theta }^{(B_i,U_m)}(2){\}}^{1/2}\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\le d^{(B_i,U_m)}(1,2)+d^{(B_i,U_m)}(2,3).\end{array}\hfill \end{array}$$

(6)

Therefore,

$$\begin{array}{l}(1+\varepsilon )\cdot \{d^{(B_i,U_m)}{(1,2)}^2+d^{(B_i,U_m)}{(2,3)}^2\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}-d^{(B_i,U_m)}(1,2)\cdot d^{(B_i,U_m)}(2,3){\}}^{1/2}\le {d^{\prime }}^{(B_i,U_m)}(1,3)\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\le (1+\varepsilon )\cdot \{d^{(B_i,U_m)}(1,2)+d^{(B_i,U_m)}(2,3)\}\hfill \end{array}$$

(7)

Case 3.

When $k=\mathrm{4}$ , the first recursion is

$$\begin{array}{l}{d^{\prime }}^{(B_i,U_m)}(1,4)=\{{(1+\varepsilon )}^2\cdot d^{(B_i,U_m)}{(3,4)}^2\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+{d^{\prime }}^{(B_i,U_m)}{(1,3)}^2-2(1+\varepsilon )\cdot d^{(B_i,U_m)}(3,4)\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\cdot {d^{\prime }}^{(B_i,U_m)}(1,3)\cdot cos{\delta }^{(B_i,U_m)}(3){\}}^{1/2}\hfill \end{array}$$

(8)

Because the following inequality certainly holds,

$$\begin{array}{l}-1\le cos{\delta }^{(B_i,U_m)}(3)\le \frac{1}{2}(1+\varepsilon )\cdot \{d^{(B_i,U_m)}{(1,2)}^2\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+d^{(B_i,U_m)}{(2,3)}^2-d^{(B_i,U_m)}(1,2)d^{(B_i,U_m)}(2,3){\}}^{1/2}\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\le {d^{\prime }}^{(B_i,U_m)}(1,3)\le (1+\varepsilon )\cdot \{d^{(B_i,U_m)}(1,2)\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+d^{(B_i,U_m)}(2,3)\},\hfill \end{array}$$

(9)

which derives

$$\begin{array}{l}\left(1+\varepsilon \right)\cdot \{d^{\left(B_i,U_m\right)}{\left(1,2\right)}^2+d^{\left(B_i,U_m\right)}{\left(2,3\right)}^2\hfill \\ +d^{\left(B_i,U_m\right)}{\left(3,4\right)}^2-d^{\left(B_i,U_m\right)}\left(1,2\right)\cdot d^{\left(B_i,U_m\right)}\left(2,3\right)\hfill \\ -d^{\left(B_i,U_m\right)}\left(1,2\right)\cdot d^{\left(B_i,U_m\right)}\left(3,4\right)-d^{\left(B_i,U_m\right)}\left(2,3\right)\hfill \\ {\cdot d^{\left(B_i,U_m\right)}\left(3,4\right)\}}^{1/2}\le d^{\text{'}\left(B_i,U_m\right)}\left(1,4\right)\le \left(1+\varepsilon \right)\hfill \\ \cdot \left\{d^{\left(B_i,U_m\right)}\left(1,2\right)+d^{\left(B_i,U_m\right)}\left(2,3\right)+d^{\left(B_i,U_m\right)}\left(3,4\right)\right\}.\hfill \end{array}$$

(10)

Case 4.

When $k=\kappa >\mathrm{4}$ , then the kth recursion

$$\begin{array}{l}\left(1+\varepsilon \right)\cdot \{\sum _{k=2}^{\kappa }{d}^{\left(B_i,U_m\right)}{\left(k-1,k\right)}^2-d^{\left(B_i,U_m\right)}\left(m-1,m\right)\hfill \\ {\cdot \sum _{k=2}^{\kappa }{d}^{\left(B_i,U_m\right)}\left(k-1,k\right)\}}^{1/2}\le d^{\text{'}\left(B_i,U_m\right)}\left(1,\kappa \right)\le (1\hfill \\ +\varepsilon )\cdot \sum _{k=2}^{\kappa }{d}^{\left(B_i,U_m\right)}\left(k-1,k\right),\hfill \end{array}$$

(11)

where $m\in [k+\mathrm{1},\kappa ]$ .

4.3. Localization Error

Trilateration is the most common approach for getting a coordinate. Suppose three beacon nodes are $(x_{\mathrm{1}}^a,y_{\mathrm{1}}^a,z_{\mathrm{1}}^a),(x_{\mathrm{2}}^a,y_{\mathrm{2}}^a,z_{\mathrm{2}}^a),(x_{\mathrm{3}}^a,y_{\mathrm{3}}^a,z_{\mathrm{3}}^a)$ . A real coordinate of one unknown node is marked as $(x_k,y_k,z_k)$ , and its estimated coordinate is $(x_k^{\prime },y_k^{\prime },z_k^{\prime })$ . As mentioned in Section 4.2, the distances of fitting straight lines from the unknown node to three beacon nodes are denoted as $d_{\mathrm{1}}^{\prime (B_i,U_m)}(i,k),d_{\mathrm{2}}^{\prime (B_i,U_m)}(i,k),d_{\mathrm{3}}^{\prime (B_i,U_m)}(i,k)$ . Then, because the Z coordinate can be got by underwater pressure directly, we can obtain a group of mathematic relationships by using trilateration method:

$$\begin{array}{cc}& {\left(x_k^{\prime }-x_{\mathrm{1}}^a\right)}^{\mathrm{2}}+{\left(y_k^{\prime }-y_{\mathrm{1}}^a\right)}^{\mathrm{2}}=d_{\mathrm{1}}^{\prime \left(B_i,U_m\right)}{\left(i,k\right)}^{\mathrm{2}},\\ {\left(x_k^{\prime }-x_{\mathrm{2}}^a\right)}^{\mathrm{2}}+{\left(y_k^{\prime }-y_{\mathrm{2}}^a\right)}^{\mathrm{2}}=d_{\mathrm{2}}^{\prime \left(B_i,U_m\right)}{\left(i,k\right)}^{\mathrm{2}},\\ {\left(x_k^{\prime }-x_{\mathrm{3}}^a\right)}^{\mathrm{2}}+{\left(y_k^{\prime }-y_{\mathrm{3}}^a\right)}^{\mathrm{2}}=d_{\mathrm{3}}^{\prime \left(B_i,U_m\right)}{\left(i,k\right)}^{\mathrm{2}},\end{array}$$

(12)

which can be derived as

$$\begin{array}{l}{x}_k^{\prime }\\ =\frac{\left\{\left\{{x_{\mathrm{1}}^a}^{\mathrm{2}}+{y_{\mathrm{1}}^a}^{\mathrm{2}}-d_{\mathrm{1}}^{\prime \left(B_i,U_m\right)}{\left(i,k\right)}^{\mathrm{2}}\right\}·\left(y_{\mathrm{2}}^a-y_{\mathrm{3}}^a\right)-\left\{{x_{\mathrm{2}}^a}^{\mathrm{2}}-{y_{\mathrm{2}}^a}^{\mathrm{2}}-d_{\mathrm{2}}^{\prime \left(B_i,U_m\right)}{\left(i,k\right)}^{\mathrm{2}}\right\}·\left(y_{\mathrm{1}}^a-y_{\mathrm{3}}^a\right)+\left\{{x_{\mathrm{3}}^a}^{\mathrm{2}}+{y_{\mathrm{3}}^a}^{\mathrm{2}}-d_{\mathrm{3}}^{\prime \left(B_i,U_m\right)}{\left(i,k\right)}^{\mathrm{2}}\right\}·\left(y_{\mathrm{1}}^a-y_{\mathrm{2}}^a\right)\right\}}{\mathrm{2}\left\{\left(x_{\mathrm{1}}^a-x_{\mathrm{3}}^a\right)·\left(y_{\mathrm{1}}^a-y_{\mathrm{3}}^a\right)-\left(x_{\mathrm{2}}^a-x_{\mathrm{3}}^a\right)·\left(y_{\mathrm{1}}^a-y_{\mathrm{3}}^a\right)\right\}},\\ y_k^{\prime }\\ =\frac{\left\{\left\{{x_{\mathrm{1}}^a}^{\mathrm{2}}+{y_{\mathrm{1}}^a}^{\mathrm{2}}-d_{\mathrm{1}}^{\prime \left(B_i,U_m\right)}{\left(i,k\right)}^{\mathrm{2}}\right\}·\left(x_{\mathrm{2}}^a-x_{\mathrm{3}}^a\right)-\left\{{x_{\mathrm{2}}^a}^{\mathrm{2}}+{y_{\mathrm{2}}^a}^{\mathrm{2}}-d_{\mathrm{2}}^{\prime \left(B_i,U_m\right)}{\left(i,k\right)}^{\mathrm{2}}\right\}·\left(x_{\mathrm{1}}^a-x_{\mathrm{3}}^a\right)+\left\{{x_{\mathrm{3}}^a}^{\mathrm{2}}+{y_{\mathrm{3}}^a}^{\mathrm{2}}-d_{\mathrm{3}}^{\prime \left(B_i,U_m\right)}{\left(i,k\right)}^{\mathrm{2}}\right\}·\left(x_{\mathrm{1}}^a-x_{\mathrm{2}}^a\right)\right\}}{\mathrm{2}\left\{\left(y_{\mathrm{1}}^a-y_{\mathrm{3}}^a\right)·\left(x_{\mathrm{1}}^a-x_{\mathrm{3}}^a\right)-\left(y_{\mathrm{2}}^a-y_{\mathrm{3}}^a\right)·\left(x_{\mathrm{1}}^a-x_{\mathrm{3}}^a\right)\right\}}.\end{array}$$

(13)

5. Simulations

MFLA is evaluated by observing the performance (localization error) variation when adopting different model parameters (such as the number of nodes, the number of beacons, and value of ɛ). Table 2 shows the values of parameters, which will be adopted for simulations unless otherwise specified. The localization error is calculated as follows:

$$\begin{array}{cc}& \text{error}=\frac{{\sum }_{k=\mathrm{1}}^m\sqrt{{\left(x_k-x_k^{\prime }\right)}^{\mathrm{2}}+{\left(y_k-y_k^{\prime }\right)}^{\mathrm{2}}}}{m·\sqrt{L^{\mathrm{2}}+W^{\mathrm{2}}}}.\end{array}$$

(14)

Table 2

Simulation parameters.

Parameter	Description	Value
$$\left|\mathbf{D}\right|$$	Deployment space	100 m × 100 m × 100 m
m	Number of unknown nodes	100
n	Number of beacon nodes	10
$${\mathrm{R}\mathrm{C}}_{\mathrm{m}\mathrm{a}\mathrm{x}}$$	Maximum communication radius	10 m
t	Water temperature	20°C
σ	Water salinity	3.5%
ε	Error factor	0.1

5.1. Impact of Multihops Fitting

Figure 9 illustrates the impact of multihops fitting on localization error. MFLA adopts multihops fitting method, and it is obvious that the plot with fitting is much lower than the one without fitting. This is because distance in localization without fitting is obtained via calculating the distance summation of multihops simply, and so localization error is greatly influenced by distribution of intermediate nodes, especially when routing path is serrated. The localization error is largely determined by distance error, and distance error will be reduced after multiple curves fitting; thus localization error is observably decreased. Moreover, the error of algorithm without fitting gradually becomes small with the increase of node quantity. This mechanism is attributed to the fact that when node deployment is more dense the multihop paths will be more inclined to appear as a straight line; hence the plot is more stable. With regard to the plot with fitting, straight distance is derived by multihops’ recursive fitting, so localization error has little relation with node quantity. In Figure 10, the error variances of two methods are provided. the plot of algorithm without fitting has a larger variance than the other because the distances by fitting are more close to real ranges.

Figure 9

Error comparison of MFLA and trilateration.

Figure 10

Variance comparison of MFLA and trilateration.

5.2. Impacts of the Number of Nodes and Error Factor

As shown in Figure 11(a), it is distinct that localization error is diminishing with the growth of beacon nodes from 6 to 12. Besides, as the number of unknown beacons grows, the localization error is also decreasing generally. This phenomenon reflects that MFLA is scalable with the number of nodes. In addition, it is found that the reduction of localization error is not linear to the increase of unknown nodes, which is also reflected in Figure 11(b). The reason is that the probability of unknown nodes’ neighboring beacons less than 3 is also reduced; thus the effect of fitting is weakened and localization accuracy is raising up accordingly. In Figure 12, localization error is observed when error factor ɛ is changing from 0.02 to 0.12. It shows the plot of larger ɛ is higher than others, which tallies with the conclusion of theoretical analysis.

Figure 11

Localization error of MFLA versus m and n.

Figure 12

Localization error of MFLA versus ɛ.

In Figures 13 and 14, three observations are made: ( $\mathrm{a}$ ) error variance decreases with the increase of m. This mechanism is attributed to the fact that more unknown nodes are beneficial to the multihops fittings, and more accurate distances will be achieved; ( $\mathrm{b}$ ) larger n gives rise to smaller error variance because more suitable beacons for localization can be found when more beacons exist in UWSNs; ( $\mathrm{c}$ ) when error factor ɛ becomes larger it is obvious that variance grows up as well.

Figure 13

Error variance versus m and n.

Figure 14

Error variance versus ɛ.

5.3. Comparisons

To make more comparisons, we compare MFLA with other algorithms (DV-Hop, trilateration, and Centroid). From Figure 15, MFLA outperforms other algorithms in terms of localization error. The reason is that MFLA adopts multihops fitting for distance estimation; thus coordinates of unknown nodes are calculated more precisely when neighboring beacons are less than 3.

Figure 15

Comparisons of different algorithms.

6. Conclusions

In this paper a multihops localization algorithm for underwater sensor networks is proposed to provide localization for isolated unknown nodes. The mathematical analysis and simulations are carried out, which indicate that MFLA can improve the positioning accuracy of nodes in severe environments efficiently.