Sage Journals: Discover world-class research

Abstract

Underwater wireless sensor networks are the enabling technology for the aquatic environmental monitoring and exploring and have attracted much attention recently. Due to the highly hostile and unpredictable underwater environments, some beacon nodes tend to move or be damaged. Therefore, the unknown nodes will be positioned with larger error, which abases the value of data collected by sensor nodes. In order to solve the beacon error problem, this article proposes an error beacon filtering algorithm based on K-means clustering. First, the coordinate of each beacon is calculated through an improved trilateration method, and then the beacon with the maximum positioning error is filtered out via the K-means clustering algorithm. The remaining beacons repeat the above processes until the distance error of each beacon does not exceed a preset threshold. The analysis of simulation results indicates that the error beacons can be accurately found and filter out through our proposed error beacon filtering algorithm (based on K-means clustering), and thus the localization accuracy is enhanced. Besides, error beacon filtering algorithm also has a provable low complexity.

Keywords

Underwater wireless sensor networks error beacon filtering localization algorithm

Introduction

Underwater acoustic networks (underwater wireless sensor networks (UWSNs)) consist of abundant low-cost sensor nodes tied to underwater vehicles, and the nodes are deployed to monitor the underwater environment collaboratively over the interest area.¹ In order to explore the underwater world, UWSNs have attracted wide attention, and many specific applications have emerged, such as environmental monitoring, natural disaster prevention, and distributed tactical surveillance, where the node localization is always very significant.² If each sensor node cannot provide its accurate coordinate, the data collected by sensor nodes may give wrong interpretations for the physical events.³ However, the underwater environment is more complex than the terrestrial environment, and the underwater characteristics bring several new challenges as follows. (1) The nodes with limited batteries are more prone to be exhausted, so they should be recharged timely. Unfortunately, it is very hard to access underwater nodes.⁴ (2) Radio wave is not feasible underwater, because it requires a large antenna and a high transmission power, and thus the acoustic communication becomes the typical physical layer technology in UWSNs. Nevertheless, the acoustic channel is characterized by its limited bandwidth, high bit error rate, path loss, motion-induced Doppler shift, and so on.⁵ (3) Underwater sensor nodes are liable to move or be damaged^6,7 due to the water current caused by external forces such as earthquake, tide, wind velocity, underwater creature touch, or strong electromagnetic interference, which will lead to a dynamic network topology.⁸ All above unique characteristics are possible to result in the damage or inaccurate localization of beacon nodes.

Generally, a typical architecture for three-dimensional (3D) UWSNs is shown in Figure 1, where there are three types of nodes: surface buoys, beacon nodes, and ordinary sensor nodes.⁹ The surface buoys can get the coordinates from their equipped global positioning system (GPS). The beacon nodes are submerged underwater, and thus GPS is not feasible for beacon nodes. They should communicate with the surface buoys to obtain their X-Y plane coordinates (the Z-axis coordinates can be estimated via the pressure sensors). Besides, the beacon nodes also help ordinary sensor nodes do localizations. However, the localizations by beacons are usually unavailable due to the beacon damage (such as the hit from water current and the touch of underwater creatures) and signal interference in the underwater environment. Hence, some beacon nodes probably provide the inaccurate coordinate information for the localizations of ordinary nodes, and these beacon nodes are referred to as the error beacons. To this end, this work proposes an error beacon filtering algorithm (EBFA), which can effectively improve the localization accuracy through filtering out the error beacons.

Figure 1.

A typical architecture of UWSNs.

Several error beacon nodes which cannot provide accurate references for ordinary nodes should be filtered out to avoid the aggravation of localization error. However, it is very difficult to find the error beacon nodes because we usually have no pre-knowledge about the error ones, and thus the error beacon nodes can be filtered out according to the mutual localization results among all beacon nodes. This work is the extension of our early work,¹⁰ the main differences between the two papers are as follows: (1) the algorithm is given more illustrations, (2) the theoretical analysis of algorithm has been improved and extended, and (3) more simulations have been done and supplied.

Related works

Localization schemes have been extensively investigated in wireless sensor networks or UWSNs, and these schemes can be divided into two groups: anchor-based schemes and anchor-free schemes.¹¹ In the anchor-based schemes, the beacon nodes get their coordinates in advance through carrying GPS receiver or even they are artificially pre-configured. The beacon nodes broadcast periodically their coordinate information. Subsequently, the ordinary nodes estimate their coordinates by calculating the distances or angles to the nearest beacon nodes, especially, some measurement techniques such as received signal strength indicator (RSSI), time of arrival (TOA), and time difference of arrival (TDOA) are usually utilized in the process. Zhang et al.¹² proposed a multi-anchor nodes collaborative localization (MANCL) algorithm. First, the well-localized nodes within one hop are prone to become the reference nodes if the ordinary nodes cannot receive four beacon signals, and the selection criterion is related to the energy, trust value, and distance. Then, an improved Euclidean distance estimation method is adopted to localize the ordinary nodes. Finally, the remaining un-localized ordinary nodes complete their localizations with the help of two-hop anchor nodes.

The anchor-free schemes¹³ determine the ordinary nodes’ coordinates through exploiting the connectivity or distance information among nodes, and thus the assistances of beacon nodes are unnecessary. The anchor-free schemes are especially suitable for the networks where nodes are hardly deployed, such as the battlefield environment or special warfare environment. Generally, the network protocol without beacon nodes is more complex than that with beacon nodes.

In addition, the anchor-based schemes can further be classified into the static beacon node localization and mobile beacon node localization. In Cheng et al.,¹⁴ an underwater positioning scheme (UPS) is proposed, where ordinary nodes record the receiving time of beacon messages, and then the time difference is transformed into the range distance after receiving four beacon messages. Finally, the ordinary nodes apply the trilateration method to estimate their own coordinates. UPS reduces the communication overhead and does not require the time synchronization, so the cost of UPS is relatively low. In Rahman et al.,¹⁵ with the help of a mobile beacon node, Cayley–Menger is used to determine the node coordinates. The distance between nodes is measured through combining the radio and acoustic signals which are free from the phenomenon of multi-path fading. In Zhang and Liang,¹⁶ the distance between nodes is calculated by a new ranging method named round-trip time of flight (RTOF), and then the ordinary nodes complete localizations using an improved particle swarm optimization (PSO) algorithm, which adds a Gaussian decreasing inertia weight and a kind of competition mechanism. This scheme can improve the localization accuracy and localization efficiency with less beacon nodes. Nonetheless, the above literatures do not take into account the mobility of underwater nodes, which are only applicable in static underwater networks.

The mobility issue in node localization has also been reviewed. Ojha and Misra¹⁷ used spatially correlated mobility pattern of UWSNs to estimate the node coordinates. In the initial stage of localization, there are only three beacon nodes. If an ordinary node cannot get enough information, it will assume that the node moves according to some specific rules, and the future coordinates can be easily predicted. When the ordinary nodes can communicate with at least three beacon nodes at the original and predicted positions, and then the coordinates of ordinary nodes can be determined. The outstanding advantage of this algorithm is that it is energy efficient as a result of the “silent localization.” In Zhu et al.,¹⁸ a localization scheme based on mobility prediction for UWSNs is introduced. The localization process is divided into two parts: the beacon nodes utilize the modified covariance algorithm to estimate their prediction models to reduce the position error, while the ordinary nodes choose the well-localized reference nodes to get their positions and speed by a node-selection strategy. The algorithm increases the localization coverage and decreases the localization error compared with scalable localization scheme with mobility prediction (SLMP) algorithm.¹⁹

But the prediction gives a poor accuracy especially when the underwater environment is hostile. A multi-hop location (MLA) in UWSNs is also proposed in Zhu et al.,²⁰ where the routing nodes are introduced to solve the problem of isolated nodes. First, the shortest paths from beacon nodes to ordinary nodes are found through a greedy approach. Subsequently, the shortest paths are fitted into a straight distance using the cosine method. Finally, the trilateration is repeatedly performed to localize the ordinary nodes. This algorithm has much higher localization accuracy than determined maximum likelihood (DML) algorithm.²¹

Some researchers also take notice of the measurement errors in localization process. Liu et al.²² combined the time synchronization and the node localization, which corrects the bias in the range estimation and improves the propagation delay in estimation when the stratification effect of underwater medium is considered. In addition, in order to further increase the localization accuracy, an advanced tracking algorithm interacting multiple model (IMM) is employed to handle the mobile case. Wu and Li²³ proposed an improved underwater acoustic network localization algorithm, which considers the measurement error caused by the sound velocity distortion and signal refraction. It uses an improved linear difference method to correct the measurement offset, which improves the localization accuracy. Simultaneously, a strategy similar to the greedy algorithm reduces the redundancy of the calculation results.

However, none of these works take the issue of error beacons into consideration. If beacon nodes move, its coordinate information will become obsolete or even wrong. Therefore, the ordinary nodes will be positioned more inaccurately under the assistance of these error beacons. To deal with the error beacon problem, this article proposes the EBFA based on K-means clustering. The coordinate of each beacon is calculated by an improved trilateration, and then the error beacons are filtered out by the K-means clustering algorithm.²⁴

EBFA based on K-means clustering

Suppose that plenty of sensors nodes are deployed in a 3D underwater space D∈IR³. A small part of beacon nodes provides error reference coordinates. Let BN denote the beacon nodes set, where BN = {b₁, b₂, …, b_n}. The number of the beacon nodes is n. Suppose that each node can transmit and receive messages with enough power and obtain the distance between nodes through RSSI.

Algorithm description

The EBFA based on K-means clustering will calculate the coordinate of each beacon by an improved trilateration, and then the distance differences exceeding a distance threshold are divided into two categories by K-means clustering method. Afterward, the beacon with the maximum positioning error is filtered out. All error beacons will be found until the distance differences are lower than the threshold. The following steps explain EBFA in detail:

Step 1. The first beacon b_i is selected randomly and five nearest beacons of b_i are found. Four of the nearest beacons will be used to position b_i, and this process will be repeated $C_{5}^{4}$ times ( $C_{5}^{4}$ denotes the number of combinations), which produces $C_{5}^{4}$ coordinate results of b_i. In detail, suppose b₁, b₂, b₃, and b₄ position b_i, then the coordinate of b_i is calculated as

$L_{b_{i}}^{b_{1}, b_{2}, b_{3}, b_{4}} = \frac{\frac{L_{b_{i}}^{b_{1}, b_{2}, b_{3}}}{d_{b_{i}}^{b_{1}, b_{2}, b_{3}}} + \frac{L_{b_{i}}^{b_{1}, b_{2}, b_{4}}}{d_{b_{i}}^{b_{1}, b_{2}, b_{4}}} + \frac{L_{b_{i}}^{b_{1}, b_{3}, b_{4}}}{d_{b_{i}}^{b_{1}, b_{3}, b_{4}}} + \frac{L_{b_{i}}^{b_{2}, b_{3}, b_{4}}}{d_{b_{i}}^{b_{2}, b_{3}, b_{4}}}}{\frac{1}{d_{b_{i}}^{b_{1}, b_{2}, b_{3}}} + \frac{1}{d_{b_{i}}^{b_{1}, b_{2}, b_{4}}} + \frac{1}{d_{b_{i}}^{b_{1}, b_{3}, b_{4}}} + \frac{1}{d_{b_{i}}^{b_{2}, b_{3}, b_{4}}}}$ (1)

where $L_{b_{i}}^{b_{1}, b_{2}, b_{3}} = (x_{i}^{b_{1}, b_{2}, b_{3}, b_{4}}, y_{i}^{b_{1}, b_{2}, b_{3}, b_{4}}, z_{i}^{b_{1}, b_{2}, b_{3}, b_{4}})$ represents the coordinate of b_i, and $d_{b_{i}}^{b_{1}, b_{2}, b_{3}}$ represents the mean distance from b₁, b₂, and b₃ to b_i.

Step 2. The distance difference between the estimated coordinate and real one of b_i is computed as

$Δ_{b_{i}}^{b_{1}, b_{2}, b_{3}, b_{4}} = \sqrt{{(x_{i}^{b_{1}, b_{2}, b_{3}, b_{4}} - x_{i})}^{2} + {(y_{i}^{b_{1}, b_{2}, b_{3}, b_{4}} - y_{i})}^{2} + {(z_{i}^{b_{1}, b_{2}, b_{3}, b_{4}} - z_{i})}^{2}}$ (2)

Moreover, each beacon should reserve a variable X[b_i] to record the number of found error beacons, and $X [b_{i}] \leftarrow 0$ initially.

Step 3. The distance differences exceeding a threshold will be divided into two categories: accurate and inaccurate, by the K-means clustering method (set K = 2).²⁵

Step 4. The localization results of a beacon are compared. If the beacon is considered inaccurate, then $X [b_{i}] \leftarrow X [b_{i}] + 1$ . The beacon with the maximum positioning error is filtered out and marked as an error beacon.

Step 5. Steps 1–4 are repeated until all distance differences are lower than the threshold after removing the found error beacons.

The following example describes the EBFA algorithm briefly. Suppose that there are 10 nodes b₁, b₂, …, b₁₀ and each node requires the localization. As shown in Figure 2, b₂, b₃, b₄, b₅, and b₆ position b₁, and b₅, b₆, b₇, b₈, and b₉ position b₂. The distance differences exceeding the threshold occur in the localization process of b₁ and b₂. The categories of beacons are shown in Table 1, where $Δ_{b_{i}}^{(\cdot)}$ denotes the distance difference between the estimated coordinate and real one, $and (\cdot)$ indicates the beacon set for the localization of beacon b_i. $δ$ is a predefined distance threshold, which is set according to the network environments. The value of X[b_i] is given in Table 2.

Figure 2.

Example diagram of node localization.

Table 1.

The diagram of beacons classification.

Beacon	Neighboring aided beacons	$Δ_{b_{i}}^{(\cdot)}$	$δ$	Accurate/inaccurate category
b ₁	b₂, b₃, b₄, b₅	11.5	0.5	Inaccurate category
	b₂, b₃, b₄, b₆	20.5	0.5	Inaccurate category
	b₂, b₃, b₅, b₆	0.25	0.5	$Δ_{b_{i}} \leq δ$
	b₂, b₄, b₅, b₆	0.15	0.5	$Δ_{b_{i}} \leq δ$
	b₃, b₄, b₅, b₆	0.6	0.5	Accurate category
b ₂	b₅, b₆, b₇, b₈	16.3	0.5	Inaccurate category
	b₅, b₆, b₇,b₉	22.4	0.5	Inaccurate category
	b₅, b₆, b₈, b₉	0.34	0.5	$Δ_{b_{i}} \leq δ$
	b₅, b₇, b₈, b₉	0.1	0.5	$Δ_{b_{i}} \leq δ$
	b₆, b₇, b₈, b₉	0.09	0.5	$Δ_{b_{i}} \leq δ$

Table 2.

The diagram of value of X[b_i].

X[b₁]	X[b₂]	X[b₃]	X[b₄]	X[b₅]	X[b₆]	X[b₇]	X[b₈]	X[b₉]	X[b₁₀]
2	4	2	2	3	3	2	1	1	0

As is shown in Table 2, the value of X[b₂] is the maximum, so b₂ is marked as an error beacon. The remaining nine beacons repeat the process after removing b₂.

Time complexity of EBFA

The time complexity of EBFA is mainly contributed by the Step 1 to Step 4. The time complexity of Step 1 is $O (n^{2})$ ; the time complexity of Step 2 is $O (n)$ ; the sorting time complexity of Step 3 is $O (2 nt) ~ O (n)$ , where t is the count of iterations; and the time complexity of Step 4 is $O (n)$ . The time complexity of EBFA is $O (n^{2})$ , which is acceptable.

Mathematical analysis

In general, the deployment of sensor nodes tossed from the air to the ground obeys the normal distribution. Let X-coordinate, Y-coordinate, and Z-coordinate of the ordinary node obey the following distribution: $X - N (μ_{x}, δ_{x})$ , $Y - N (μ_{y}, δ_{y})$ , and $Z - N (μ_{z}, δ_{z})$ , respectively. The real coordinate and the estimated coordinate of the beacon node b_i are denoted by $(\bar{x_{i}}, \bar{y_{i}}, \bar{z_{i}})$ and $(x_{i}, y_{i}, z_{i})$ , respectively. The real distance and the estimated distance between beacons is $\bar{d_{i}}$ and $d_{i}$ , respectively. The impact of the error beacons is analyzed as follows.

First, the real coordinate of the localized node is calculated from the following equation set

${\begin{matrix} {(x - \bar{x_{a}})}^{2} + {(y - \bar{y_{a}})}^{2} + {(z - \bar{z_{a}})}^{2} = {\bar{d_{a}}}^{2} \\ {(x - \bar{x_{b}})}^{2} + {(y - \bar{y_{b}})}^{2} + {(z - \bar{z_{b}})}^{2} = {\bar{d_{b}}}^{2} \\ {(x - \bar{x_{c}})}^{2} + {(y - \bar{y_{c}})}^{2} + {(z - \bar{z_{c}})}^{2} = {\bar{d_{c}}}^{2} \end{matrix}$ (3)

where a, b, and c are the aided beacons. $(\bar{x_{a}}, \bar{y_{a}}, \bar{z_{a}})$ denotes the real coordinate of the beacon a, and $\bar{d_{a}}$ is the real distance from a to the coordinate $(x, y, z)$ (the coordinate of the localized node). Thus, the real coordinate of the localized nodes is expressed as

$(\begin{matrix} x \\ y \\ z \end{matrix}) = {\bar{A}}^{- 1} (\bar{B} + \bar{D})$ (4)

where $\bar{A} = (\begin{matrix} 2 (\bar{x_{a}} - \bar{x_{c}}) & 2 (\bar{y_{a}} - \bar{y_{c}}) & 2 (\bar{z_{a}} - \bar{z_{c}}) \\ 2 (\bar{x_{b}} - \bar{x_{c}}) & 2 (\bar{y_{b}} - \bar{y_{c}}) & 2 (\bar{z_{b}} - \bar{z_{c}}) \\ 2 (\bar{x_{a}} - \bar{x_{b}}) & 2 (\bar{y_{a}} - \bar{y_{b}}) & 2 (\bar{z_{a}} - \bar{z_{b}}) \end{matrix})$ , $\bar{B} = (\begin{matrix} {\bar{x_{a}}}^{2} - {\bar{x_{c}}}^{2} + {\bar{y_{a}}}^{2} - {\bar{y_{c}}}^{2} + {\bar{z_{a}}}^{2} - {\bar{z_{c}}}^{2} \\ {\bar{x_{b}}}^{2} - {\bar{x_{c}}}^{2} + {\bar{y_{b}}}^{2} - {\bar{y_{c}}}^{2} + {\bar{z_{b}}}^{2} - {\bar{z_{c}}}^{2} \\ {\bar{x_{c}}}^{2} - {\bar{x_{b}}}^{2} + {\bar{y_{a}}}^{2} - {\bar{y_{b}}}^{2} + {\bar{z_{a}}}^{2} - {\bar{z_{b}}}^{2} \end{matrix})$ , and $\bar{D} = (\begin{matrix} {\bar{d_{c}}}^{2} - {\bar{d_{a}}}^{2} \\ {\bar{d_{c}}}^{2} - {\bar{d_{b}}}^{2} \\ {\bar{d_{b}}}^{2} - {\bar{d_{a}}}^{2} \end{matrix})$ . $\bar{D}$ indicates that the localization results are related with the distance. $\bar{A}$ and $\bar{B}$ show the localization results are also related with the coordinates of aided beacons. To simplify the formulations, let $\bar{A} = (\begin{matrix} a_{1} & b_{1} & c_{1} \\ a_{2} & b_{2} & c_{2} \\ a_{3} & b_{3} & c_{3} \end{matrix})$ , then we obtain that

${\bar{A}}^{- 1} = \frac{{\bar{A}}^{*}}{| \bar{A} |} = \frac{1}{| \bar{A} |} (\begin{matrix} b_{2} c_{3} - c_{2} b_{3} & c_{1} b_{3} - b_{1} c_{3} & b_{1} c_{2} - c_{1} b_{2} \\ c_{2} a_{3} - a_{2} c_{3} & a_{1} c_{3} - c_{1} a_{3} & a_{2} c_{1} - a_{1} c_{2} \\ a_{2} b_{3} - b_{2} a_{3} & b_{1} a_{3} - a_{1} b_{3} & a_{1} b_{2} - a_{2} b_{1} \end{matrix})$

where $| \bar{A} | = a_{1} (b_{2} c_{3} - c_{2} b_{3}) - a_{2} (b_{1} c_{3} - c_{1} b_{3}) + a_{3} (b_{1} c_{2} - c_{1} b_{2})$ .

The error from trilateration algorithm executions should be taken into account. Set $\bar{d_{i}} = d_{i} + ξ_{id}$ (i = a, b, c), hence the measured coordinate of the localized nodes is calculated as $(\begin{matrix} \bar{x} \\ \bar{y} \\ \bar{z} \end{matrix}) = {\bar{A}}^{- 1} (\bar{B} + D)$ . Therefore, the localization error of trilateration algorithm is

$(\begin{matrix} Δ \bar{x} \\ Δ \bar{y} \\ Δ \bar{z} \end{matrix}) = (\begin{matrix} \bar{x} \\ \bar{y} \\ \bar{z} \end{matrix}) - (\begin{matrix} x \\ y \\ z \end{matrix}) = {\bar{A}}^{- 1} (\bar{B} + D) - {\bar{A}}^{- 1} (\bar{B} + \bar{D}) = {\bar{A}}^{- 1} (D - \bar{D})$ (5)

Moreover, the localization error is expressed by the scalar ER_f

$E R_{f} = Δ {\bar{x}}^{2} + Δ {\bar{y}}^{2} + Δ {\bar{z}}^{2}$ (6)

Formula (6) transforms the localization error into a scalar, and then the error can be analyzed from each axis. Let $\bar{x_{i}} = x_{i} + ξ_{ix}$ , $\bar{y_{i}} = y_{i} + ξ_{iy}$ , and $\bar{z_{i}} = z_{i} + ξ_{iz}$ (i = a, b, c). Thus, the measured coordinate of localized nodes is expressed as $(\begin{matrix} x' \\ y' \\ z' \end{matrix}) = A^{- 1} (B + D)$ . Therefore, the localization error is written as

$(\begin{matrix} Δ x' \\ Δ y' \\ Δ z' \end{matrix}) = (\begin{matrix} x' \\ y' \\ z' \end{matrix}) - (\begin{matrix} x \\ y \\ z \end{matrix}) = A^{- 1} (B + D) - {\bar{A}}^{- 1} (\bar{B} + \bar{D})$ (7)

Then the localization error expressed by the scalar $E R_{s}$ is rewritten as $E R_{s} = Δ x'^{2} + Δ y'^{2} + Δ z'^{2}$ .The sign of $E R_{s} - E R_{f}$ are discussed from Case I and Case II.

Case I. If $ξ_{ix} = ξ_{iy} = ξ_{iz} = 0$ , one gets $E R_{s} - E R_{f} = 0$ easily;

Case II. If $ξ_{ix} \neq 0$ , $ξ_{iy} \neq 0$ , and $ξ_{iz} = 0$ , then $A = \bar{A} + (\begin{matrix} 2 (ξ_{c x} - ξ_{a x}) & 2 (ξ_{c y} - ξ_{a y}) & 0 \\ 2 (ξ_{c x} - ξ_{b x}) & 2 (ξ_{c y} - ξ_{b y}) & 0 \\ 2 (ξ_{b x} - ξ_{a x}) & 2 (ξ_{b y} - ξ_{a y}) & 0 \end{matrix}) = (\begin{matrix} m_{1} & e_{1} & 0 \\ m_{2} & e_{2} & 0 \\ m_{3} & e_{3} & 0 \end{matrix}),$ $D = \bar{D} + G = \bar{D} + (\begin{matrix} {ξ_{cd}}^{2} - 2 \bar{d_{c}} ξ_{cd} + 2 \bar{d_{a}} ξ_{ad} - {ξ_{ad}}^{2} \\ {ξ_{cd}}^{2} - 2 \bar{d_{c}} ξ_{cd} + 2 \bar{d_{b}} ξ_{bd} - {ξ_{bd}}^{2} \\ {ξ_{bd}}^{2} - 2 \bar{d_{b}} ξ_{bd} + 2 \bar{d_{a}} ξ_{ad} - {ξ_{ad}}^{2} \end{matrix})$ , and $B = \bar{B} + F = \bar{B} + (\begin{matrix} {ξ_{a x}}^{2} - 2 \bar{x_{a}} ξ_{a x} + 2 \bar{x_{c}} ξ_{c x} - {ξ_{c x}}^{2} + 2 \bar{y_{a}} ξ_{a y} + 2 \bar{y_{c}} ξ_{c y} - {ξ_{c y}}^{2} \\ {ξ_{b x}}^{2} - 2 \bar{x_{b}} ξ_{b x} + 2 \bar{x_{c}} ξ_{c x} - {ξ_{c x}}^{2} + 2 \bar{y_{b}} ξ_{b y} + 2 \bar{y_{c}} ξ_{c y} - {ξ_{c y}}^{2} \\ {ξ_{a x}}^{2} - 2 \bar{x_{a}} ξ_{a x} + 2 \bar{x_{b}} ξ_{b x} - {ξ_{b x}}^{2} + 2 \bar{y_{b}} ξ_{b y} + 2 \bar{y_{c}} ξ_{c y} - {ξ_{c y}}^{2} \end{matrix}) .$

B is transformed into the sum of the real beacon value $\bar{B}$ and the beacon error F. D is transformed into the sum of the real distance value $\bar{D}$ and the distance error G. In order to facilitate the analysis, $\bar{B} + \bar{D}$ and $F + G$ are jointly analyzed. Define $\bar{B} + \bar{D} = (\begin{matrix} n_{1} \\ n_{2} \\ n_{3} \end{matrix})$ and $F + G = (\begin{matrix} f_{1} + g_{1} \\ f_{2} + g_{2} \\ f_{3} + g_{3} \end{matrix})$ , so Formula (7) can be rewritten as

$(\begin{matrix} Δ x' \\ Δ y' \\ Δ z' \end{matrix}) = A^{- 1} (B + D) - {\bar{A}}^{- 1} (\bar{B} + \bar{D}) = A^{- 1} (\bar{B} + \bar{D} + F + G) - {\bar{A}}^{- 1} (\bar{B} + \bar{D})$ (8)

Furthermore, $E R_{s} - E R_{f}$ can be expressed as $(Δ x'^{2} - Δ {\bar{x}}^{2}) + (Δ y'^{2} - Δ {\bar{y}}^{2}) + (Δ z'^{2} - Δ {\bar{z}}^{2})$ . To observe the sign of $E R_{s} - E R_{f}$ , $(Δ x')^{2} - (Δ \bar{x})^{2}$ , $(Δ y')^{2} - (Δ \bar{y})^{2}$ , and $(Δ z')^{2} - (Δ \bar{z})^{2}$ are verified respectively in the Appendix 1. Without loss of generality, the error from Y-axis and Z-axis is ignored temporarily, and thus there are $g_{2} = g_{3} = 0, n_{2} = n_{3} = 0, and f_{2} = f_{3} = 0$ , then there is $Δ x'^{2} - Δ {\bar{x}}^{2} > 0$ , $Δ y'^{2} - Δ {\bar{y}}^{2} > 0$ , and $Δ z'^{2} - Δ {\bar{z}}^{2} > 0$ , the derivation and proof of which are also given in the Appendix 1.

Therefore, $E R_{s} - E R_{f} \geq 0$ . That is, the localization error with error beacons is higher than that without error beacons which have been filtered out.

Simulations

EBFA is evaluated by observing the performance variation when adopting different model parameters (such as the number of beacon nodes and the number of error beacons) and by comparing EBFA with other algorithms. Table 3 shows the values of the parameters.

Table 3.

Simulation parameters.

Parameter	Description	Value
$\| D \|$	Deployment space	$100 m \times 100 m \times 100 m$
N	Number of nodes	300
n	Number of beacon nodes	60
K	Number of categories	2
rate	Proportion of error beacon nodes in beacon nodes	20%
$R C_{\max}$	Maximum communication range	10 m
$δ$	Distance threshold	5 m
Count	Number of execution times	100

The accurate discovery of the error beacons is extremely critical to the localization accuracies of ordinary nodes. This simulation measures the number of found error beacons with different number of beacon nodes. As shown in Figure 3, three plots (the proportion is assigned as 20%, 30%, and 40%, respectively) are observed. The plot with a larger rate is higher than the other plots because there are more error beacon nodes to be found. Besides, the number of found error beacons also grows with the increase in the total number of beacon nodes and the proportion of error beacon nodes. When the number of real error beacons is fixed, more beacons will bring more accurate judgments for the error beacons, and thus more error beacons can be found. However, when there are excessive error beacons, the number of found error beacons is much different from the number of real error beacons. When the proportion is set 20% and the number of beacons reaches 60, the number of found error beacons (about 13) is approximately equal to the number of real error beacons (60 × 20% = 12), which indicates that EBFA can effectively detect almost all error beacons especially when the number of beacon nodes and the proportion of error beacons are not very large.

Figure 3.

Number of found error beacons versus rates of error beacons.

In Figure 4, the variance metric denotes the stability of the number of found error beacons. The variance is expressed as $\sum_{i = 1}^{count} (a [i] - (\sum_{j = 1}^{count} a [j] / count))^{2} / count$ , where count is the number of execution times, and a[i] is the number of found error beacons at the ith execution. The plot with a larger rate has a sharper fluctuation than the others, which is attributed to the fact that the variable number of the found error beacons becomes larger when there are more error beacons. Moreover, more error beacons give rise to a larger localization error of ordinary nodes as well. Note that some of the error beacons are still not being detected, especially when the number of beacon nodes becomes larger, which is attributed to the random deployment of beacons and the original localization error.

Figure 4.

Variance versus number of beacons.

In EBFA, the error beacons are filtered out according to a distance threshold, that is, the beacons with larger localization error are excluded. Therefore, the value of threshold has a significant influence on the performance of EBFA. Both Figures 5 and 6 illustrate the impacts of the threshold when rate is set 20%. In Figure 5, it can be found that when the threshold is set 10, the number of found error beacons is approximately equal to the number of real error beacons because the proper setting of threshold helps EBFA to find the error beacon nodes accurately. Nevertheless, when the threshold is too small, some accurate beacons are also mistakenly labeled as the error beacons. Moreover, when the threshold is too large, most of the error beacons are not found because EBFA cannot differentiate the accurate beacons and error beacons by a large threshold. Consequently, the proper setting of the threshold is important to the EBFA performance.

Figure 5.

Found error beacons versus distance threshold.

Figure 6.

Variance versus different thresholds.

As depicted in Figure 6, the threshold has an obvious impact on the variance number of found error nodes as well. In general, with the increase in the number of beacon nodes, the plots of variance continue to rise up. When the threshold is 5, the variance number is larger than the others, this is because the number of found error beacons is larger, and thus the deployment of error beacons becomes more random accordingly.

Figure 7 compares the number of found beacons of EBFA, Centroid, and Trilateration. Apparently, EBFA overcomes Centroid and Trilateration absolutely. In Centroid, almost all nodes are labeled invalid. This is because Centroid has a stricter requirement for the node distribution and it assumes that the nodes obey the uniform distribution, which does not tally with the random deployment in our simulations. Therefore, it is hard to find error beacons exactly. In Trilateration, all nodes involved in localization will be marked as error beacons provided that this localization result is wrong. Hence, some of the error beacons cannot be found. In EBFA, most of the error beacons can be found in an iterative way, and probabilities of falsely marking the beacon nodes are very small, but the found error beacons are usually a bit more than the real ones. The reason is that some accurate beacons served for the localizations of the neighboring error beacons are also prone to be regarded as the error beacons.

Figure 7.

Comparisons of the number of found beacons and found error beacons: (a) number of found beacons and (b) number of found error beacons.

As shown in Figure 8, the localization error denotes the coordinate derivations of ordinary nodes from the beacon localizations. The results indicate that EBFA can achieve the lowest localization error after effectively filtering most of the error beacons. Moreover, the scalability of EBFA is also better than those of the other two algorithms, this is because the proportion of the number of found error beacons stays the same approximately, as shown in Figure 3.

Figure 8.

Localization error comparisons.

In summary, when the proper distance threshold is set, EBFA can accurately filter out most of the error beacons, which effectively improve the localization accuracy of ordinary nodes. Moreover, EBFA performs a favorable scalability with the number of beacon nodes. Moreover, there may be some gaps from theory algorithms to practical application, and EBFA should be improved the practicality according to the test feedbacks in actual UWSN systems.

Conclusion

This article explores the problem of error beacons filtering. The error beacons will be found in an iterative way based on an improved trilateration and the K-means clustering method, that is, the error beacon nodes are filtered out according to the mutual localization results among all beacon nodes. Simulation results demonstrate that the EBFA can accurately find the error beacons with low complexity.

This work is based on the assumption that the number of error beacon nodes is fewer compared with the number of all beacon nodes. The probabilities of finding the error beacon nodes will become smaller when the proportion of error beacon nodes becomes larger. Our future work will focus on the issue that how to revise the coordinate of error beacons such that they can still be available for coordinate references.

Footnotes

Academic Editor: Miguel Ardid

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research,authorship,and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research,authorship,and/or publication of this article: This research was supported by the National Natural Science Foundation of China under grant nos. 61373139,61373137,61300239,and 71301081;Natural Science Foundation of Jiangsu Province under grant nos BK2012833,BK20130877,and BK20141429;China Postdoctoral Science Foundation under grant nos 2014M560379,2014M551635,and 2015T80484;Scientific and Technological Support Project (Society) of Jiangsu Province under grant no. BE2013666;Scientific and Technological Support Project (Society) of Lianyungang under grant no. SH1306;and Postdoctoral Science Foundation of Jiangsu Province under grant no. 1302085B.

References

Akyildiz

Pompili

Melodia

Underwater acoustic sensor networks: research challenges. Ad Hoc Netw 2005; 3(3): 257–279.

Lee

Kim

Localization with a mobile beacon in underwater sensor networks. In: Proceedings of the 2010 IEEE/IFIP 8th international conference on embedded and ubiquitous computing (EUC), Hong Kong, 11–13 December 2010, pp.316–319. New York: IEEE.

Tan

H-P

Diamant

Seah

WKG

. A survey of techniques and challenges in underwater localization. J Ocean Eng 2011; 38(14): 1663–1676.

Bhuvaneswari

PTV

Karthikeyan

Jeeva

. An efficient mobility based localization in underwater sensor networks. In: Proceedings of the 2012 fourth international conference on computational intelligence and communication networks, Mathura, India, 3–5 November 2012, pp.90–94. New York: IEEE.

Khan

Zhou

. Modeling of acoustic propagation channel in underwater wireless sensor networks. In: Proceedings of the 2014 2nd international conference on systems and informatics (ICSAI), Shanghai, China, 15–17 November 2014, pp.586–590. New York: IEEE.

Akyildiz

Pompili

Melodia

Challenges for efficient communication in underwater acoustic sensor networks. ACM SIGBED Rev 2004; 1: 3–8.

Waldmeyer

Tan

H-P

Seah

WKG

. Multi-stage AUV-aided localization for underwater wireless sensor networks. In: Proceedings of the IEEE workshops of international conference on advanced information networking and applications, Biopolis, Singapore, 22–25 March 2011, pp.908–913. New York: IEEE.

Debont

Jamshaid

Shihada

. Event localization in underwater wireless sensor networks using monitoring courses. In: Proceedings of the 2012 1st IEEE international conference on communications in China, Beijing, China, 15–17 August 2012, pp.769–774. New York: IEEE.

Zhou

Chen

. An area localization scheme for large scale underwater wireless sensor networks. In: Proceedings of the 2009 WRI international conference on communications and mobile computing, Yunnan, China, 6–8 January 2009, pp.543–547. New York: IEEE.

10.

Liu

Guo

. Error beacon filtering algorithm based on K-means clustering for underwater wireless sensor networks. In: Proceedings of the 8th IEEE international conference on communication software and networks (ICCSN), Beijing, China, 4–6 June 2016. New York: IEEE.

11.

Misra

Ojha

Mondal

Game-theoretic topology control for opportunistic localization in sparse underwater sensor networks. IEEE T Mobile Comput 2015; 14(5): 990–1003.

12.

Zhang

Han

Jiang

. A collaborative localization algorithm for underwater acoustic sensor networks. In: Proceedings of the 2014 international conference on computing, management and telecommunications (ComManTel), Da Nang, Vietnam, 27–29 April 2014, pp.211–216. New York: IEEE.

13.

Guo

Liu

YT.

Location for anchor-free underwater sensor networks. J Electr Comput Eng 2013; 39(6): 1812–1821.

14.

Cheng

Shu

Liang

. Silent positioning in underwater acoustic sensor networks. IEEE T Veh Technol 2008; 57(3): 1756–1766.

15.

Rahman

Muthukkumarasamy

Sithirasenan

. Coordinates determination of submerged sensors using Cayley-Menger determinant. In: Proceedings of the 2013 IEEE international conference on distributed computing in sensor systems (DCOSS), Cambridge, MA, 20–23 May 2013, pp.466–471. New York: IEEE.

16.

Zhang

Liang

. A kind of nodes localization method for three-dimensional UWSNs. In: Proceedings of the 2015 34th Chinese control conference (CCC), Hangzhou, China, 28–30 July 2015, pp.7765–7770. New York: IEEE.

17.

Ojha

Misra

. MobiL: a 3-dimensional localization scheme for mobile underwater sensor networks. In: Proceedings of the 2013 national conference on communications (NCC), New Delhi, India, 15–17 February 2013, pp.1–5. New York: IEEE.

18.

Zhu

Jian

. A distributed localization scheme based on mobility prediction for underwater wireless sensor networks. In: Proceedings of the 26th Chinese control and decision conference (CCDC), Changsha, China, 31 May–2 June 2014, pp.4863–4867. New York: IEEE.

19.

Zhou

Peng

Cui

. Scalable localization with mobility prediction for underwater sensor networks. IEEE T Mobile Comput 2011; 10(3): 335–348.

20.

Zhu

Guan

Liu

. A multi-hop localization algorithm in underwater wireless sensor networks. In: Proceedings of the 2014 sixth international conference on wireless communication and signal processing (WCSP), Hefei, China, 23–25 October 2014, pp.1–6. New York: IEEE.

21.

Heiko

Norman

Jochen

. Distance-based distributed multi-hop localization in mobile wireless sensor networks, http://page.mi.fu-berlin.de/eke/will09FGSN.pdf

22.

Liu

Wang

Cui

. A joint time synchronization and localization design for mobile underwater sensor networks. IEEE T Mobile Comput 2016; 15: 530–543.

23.

An improved underwater acoustic network localization algorithm. China Commun 2015; 12(3): 77–83.

24.

Ribas

Colonna

Figueiredo

. Similarity clustering for data fusion in wireless sensor networks using k-means. In: Proceedings of the 2012 international joint conference on neural networks (IJCNN), Brisbane, QLD, Australia, 10–15 June 2012, pp.1–7. New York: IEEE.

25.

Kanungo

Mount

Netanyah

NS.

An efficient k-means clustering algorithm: analysis and implementation. IEEE T Pattern Anal 2002; 24(7): 881–892.