A fully distributed deployment algorithm for underwater strong k -barrier coverage using mobile sensors

Abstract

Sensor barrier coverage has been recognized as an appropriate coverage model for intrusion detection, and many achievements have been obtained in two-dimensional terrestrial wireless sensor networks. However, the achievements based on two-dimensional assumption cannot be directly applied in three-dimensional application scenarios, for example, underwater wireless sensor networks. In this article, we aim to devise a fully distributed deployment algorithm for constructing maximum-level underwater strong k-barrier coverage with available mobile sensors in underwater environment to satisfy the requirement of underwater security-related applications. We first analyze how to form underwater strong one-barrier coverage with minimum mobile sensors, based on which we obtain the minimum number of sensors required for constructing underwater strong one-barrier coverage and the corresponding optimal final positions of these sensors. Then, we propose a fully distributed deployment algorithm for constructing maximum-level underwater strong k-barrier coverage with available mobile sensors in three-dimensional underwater environment. We show that the proposed algorithm has a guaranteed termination after a finite time and is able to self-heal the underwater strong k-barrier coverage to deal with sudden sensor failures. Experimental results validate our analysis and show that the proposed algorithm outperforms both Hungarian and HungarianK in terms of duration and achieves performance close to them with respect to several performance metrics.

Keywords

Wireless sensor networks underwater wireless sensor networks underwater sensor deployment distributed deployment algorithm underwater sensor barrier coverage

Introduction

Wireless sensor networks (WSNs) have many real-life applications such as environmental monitoring, battlefield surveillance, and intrusion detection. As an important problem in WSNs, barrier coverage is garnering more and more attention in recent years.^1–5 Compared with the area coverage problem, barrier coverage does not necessarily cover every point of the monitored region, but rather only needs to detect intruders that cross the border.⁴ Therefore, it is more cost-efficient for large-scale deployment of wireless sensors and has been widely employed in practical security-related applications, for example, international border surveillance, intrusion detection, and critical infrastructure protection.

Most existing works on barrier coverage assume that sensors are deployed in two-dimensional (2D) long thin belt region, where a barrier is a chain of sensors from one end of the deployment region to the other end with overlapping sensing zones of adjacent sensors. This assumption is reasonable in 2D terrestrial WSNs where the height of the network is usually negligible as compared with its length and width. However, the 2D assumption may not be appropriate when considering WSNs in three-dimensional (3D) application scenarios, for example, underwater wireless sensor networks (UWSNs), where the sensors are finally distributed over 3D underwater environment. As technology advances, efforts are currently underway to extend the applications of WSNs from 2D to 3D application scenarios, and many achievements have been obtained in 3D UWSNs.^6–9 In terms of sensor barrier coverage, an underwater sensor barrier has been considered for detecting submarine intrusion in marine environment.¹⁰

Compared with terrestrial WSNs, UWSNs have many differences in terms of topology, communication media, deployment, bandwidth, and so on. For example, the topology of terrestrial WSNs is generally static or low dynamic, while that of UWSNs is highly dynamic due to continual movement of nodes caused by water current. Sensor nodes in terrestrial WSNs communicate with each other by radio wave which is high frequency, while in UWSNs, sensor nodes generally communicate with each other by acoustic wave which is low frequency. Furthermore, different from the terrestrial WSNs where sensors are distributed in a 2D plane, in UWSNs (in this article, we only consider sensor barrier coverage in UWSNs where the sensors are deployed in 3D underwater environment), the sensors are distributed at different depths in 3D underwater environment. In this case, a sensor barrier is not a chain of sensors from one end of the deployment region to the other end with overlapping sensing zones of adjacent sensors any more. Instead, a sensor barrier deployed in underwater environment should be a set of sensors with overlapping sensing zones of adjacent sensors that covers an entire (curly) surface that cuts across the 3D underwater space.¹¹

In this article, we aim to devise a fully distributed deployment algorithm (FDDA) for constructing maximum-level underwater strong k-barrier coverage with available mobile sensors in underwater environment, to satisfy the requirement of underwater security-related applications. The notion of k-barrier coverage is first defined by Kumar et al.,¹² they introduced two types of k-barrier coverage including weak barrier coverage, which guarantees to detect intruders moving along congruent paths, and strong barrier coverage, which guarantees to detect intruders no matter what crossing paths they choose. Generally, a strong k-barrier coverage is constituted with k strong one-barrier coverage. In practical underwater environment, as the existence of sudden sensor failures and water current, which may lead a sensor to deviate from its desired position, a strong one-barrier coverage usually fails to provide adequate service quality. Hence, many real-life underwater applications require strong k-barrier coverage to guarantee their service quality.

The main contributions of this article can be outlined as follows:

We analyze how to form underwater strong one-barrier coverage with minimum mobile sensors, based on which we obtain the minimum number of sensors required for constructing underwater strong one-barrier coverage and derive the corresponding optimal final positions of these sensors.

Considering the fact that a strong k-barrier coverage consists of k strong one-barrier coverage, we propose a FDDA for constructing maximum-level underwater strong k-barrier coverage with available mobile sensors in underwater environment. The proposed algorithm can drive all mobile sensors distributed in underwater space automatically moving to desired positions and finally provide maximum-level underwater strong k-barrier coverage.

We evaluate the performance of the proposed algorithm by extensive experiments. Experimental results show that the proposed algorithm has a guaranteed termination after a finite time and is able to self-heal the underwater strong k-barrier coverage to deal with sudden sensor failures. Furthermore, the proposed algorithm outperforms both Hungarian and HungarianK in terms of duration and achieves performance close to them with respect to several performance metrics.

The rest of the article is organized as follows. Next section reviews the related work. In section “Network model and problem statement,” we explain the network model and provide the problem statement. Next, in section “Underwater strong one-barrier coverage,” we analyze how to form underwater strong one-barrier coverage with minimum sensors in underwater environment, and obtain the optimal final positions of sensors. Furthermore, in section “FDDA,” we propose a distributed algorithm named FDDA for constructing maximum-level underwater strong k-barrier coverage with available mobile sensors in underwater environment. Section “Performance evaluation” evaluates the performance of the proposed algorithm through extensive simulations, and finally, section “Conclusion” concludes the article.

Related work

As an important problem in WSNs, barrier coverage has been extensively studied in the past decades. Most existing works consider 2D barrier coverage in terrestrial WSNs, while only recently 3D barrier coverage in UWSNs has been studied. In the following, we review the works on 2D and 3D sensor barrier coverage.

2D sensor barrier coverage

The concept of barrier coverage first appeared in the context of many robot systems.¹³ Kumar et al.¹² developed theoretical foundations for laying barriers of wireless sensors. They defined two types of barrier coverage including weak barrier coverage, which guarantees to detect intruders moving along congruent paths, and strong barrier coverage, which guarantees to detect intruders no matter what crossing paths they choose. Chen et al.¹⁴ considered whether or not a sensor network provides barrier coverage, then introduced the concept of “quality of barrier coverage” and proposed an effective way to measure it, which can be helpful to evaluate the coverage quality of a deployed barrier coverage. Fan et al.¹⁵ studied the coverage of a line interval with a set of wireless sensors with adjustable coverage ranges. For the discrete variant, they presented a polynomial-time algorithm to compute the optimal solution, while for the continuous variant, they developed constant approximation algorithms when the cost for all sensors is proportional to $r^{κ}$ for some constant $κ \geq 1$ , where r is the covering radius corresponding to the chosen power. Liu et al.¹⁶ studied the strong barrier coverage of a randomly deployed sensor network on a long irregular strip region. They showed that in a rectangular area of width w and length l with the relation $w = Ω (\log l)$ , if the sensor density reaches a certain value, then there exist, with high probability, multiple disjoint sensor barriers across the entire length of the area such that intruders cannot cross the area undetected. On the contrary, if $w = o (\log l)$ , then with high probability there is a crossing path not covered by any sensor regardless of the sensor density. Chen et al.¹⁷ introduced a new coverage model called one-way barrier coverage, which requires that the network reports illegal intruders while ignores legal intruders. Yang and Qiao¹⁸ explored sensor collaborations and information fusion to improve the barrier coverage and to extend the sensor network lifetime. He et al.¹⁹ presented a condition under which line-based deployment is suboptimal and proposed a new deployment approach named curve-based deployment. Wang et al.^20,21 explored the effects of location errors on barrier coverage on a 2D plane by considering two scenarios (i.e. only stationary nodes have location errors, stationary and mobile nodes both have location errors) and proposed a fault-tolerant weighted barrier graph to model the barrier coverage formation problem. DeWitt and Shi²² incorporated energy harvesting into the barrier coverage problem and studied the lifetime issues of the k-barrier coverage problem for energy harvesting WSNs.

With the advances of technology, sensor mobility has been incorporated into sensor deployment framework,²³ which offers more flexibility for designing more efficient sensor deployment strategies to solve coverage problem in WSNs. Li and Shen⁴ studied the 2D MinMax barrier coverage problem of moving n sensors in a 2D plane to form a barrier coverage while minimizing the maximum sensor movement for the sake of balancing battery power consumption. He et al.²⁴ studied the cost-effective barrier coverage problem when there are not sufficient sensor resources. They first designed a periodic monitoring scheduling (PMS) algorithm and then proposed to jointly exploit sensor mobility and intruder arrival information to improve barrier coverage. Saipulla et al.²⁵ studied the barrier coverage of a WSN where sensors are deployed along lines with random offsets which follow normal distribution and are referred to as line-based normal random offset (LNRO). They established a tight lower bound for the existence of barrier coverage based on LNRO and also investigated the multiple lines deployment scenario and how barrier coverage depends on the distance between adjacent lines and the random offsets of sensors. Dobrev et al.²⁶ studied three optimization problems related to the movement of sensors to achieve weak barrier coverage, that is, minimizing the number of sensors moved, minimizing the average distance moved by the sensors, and minimizing the maximum distance moved by the sensors. Silvestri and Goss²⁷ proposed an original algorithm called MobiBar, which has the capability of constructing k-barrier coverage in WSNs, self-reconfiguration, and self-healing. Ban et al.²⁸ considered k-barrier coverage problem in 2D WSNs and devised an approximation algorithm called approximate to horizontal grid barrier (AHGB) to construct one-barrier efficiently. Furthermore, based on AHGB, a Divide and Conquer algorithm was proposed to construct k-barrier coverage for large-scale WSNs. Saipulla et al.²⁹ explored the fundamental limits of sensor mobility on barrier coverage and presented a sensor mobility scheme that constructs the maximum number of sensor barriers with the minimum sensor moving distance. Kong et al.³⁰ investigated the adaptive barrier coverage system which aims to adaptively maintain a sensor barrier coverage surrounding a dynamic zone in 2D WSNs by means of cloud computing.

3D sensor barrier coverage

There are only a handful of works that have considered 3D sensor barrier coverage. Barr et al.^10,11,31 considered constructing underwater sensor barriers to thwart illegal intrusion of submarines and devised a centralized approach and a decentralized approach to achieve this goal, respectively. However, both the centralized and decentralized approaches require one or several sensor nodes as leader to collect and propagate sensor positions. In this case, single point failure problem may not be avoid. Luo et al.³² proposed a novel floating 3D sensor networks for constructing underwater static sensor barrier by using moored nodes, which is a novel scheme, and by the proposed scheme, a more cost-efficient ocean barrier can be constructed. However, there are some limitations in monitoring flexibilities. Shen et al.³³ studied sensor barrier construction problem in underwater UWSNs. They derived the minimum number of sensors needed for an underwater sensor barrier and proposed an efficient centralized algorithm to construct underwater sensor barrier. However, the proposed centralized algorithm requires one sensor node as leader to undertake computing task, which may not avoid single point failure. In this work, we aim to devise a FDDA, which does not require any leader nodes to collect and propagate sensor positions, for constructing maximum-level underwater strong k-barrier coverage with available mobile sensors in underwater environment, and hope to provide insights into further researches in 3D WSNs.

Network model and problem statement

Network model

We model the underwater deployment region as a cuboid of size $l \times w \times h$ , where l, w, and h denote the length, width, and height of the cuboid, respectively. For the sake of clearness, we assume that the cuboid is located in a 3D Cartesian coordinate system with origin at the center point of the cuboid. Initially, n sensors are deployed in the cuboid where the sensor positions can follow any type of distribution, such as uniform distribution, Poisson distribution, and normal distribution, as shown in Figure 1. Similarly to most previous works in underwater sensor deployment, we assume that all the deployed sensors are able to identify their current locations by existing underwater localization algorithms,^9,34 and each sensor equipped with propelled equipment, for example, autonomous underwater vehicles (AUVs),^35,36 is able to relocate itself from its initial position to another specified position at a maximum speed of $V_{\max} (m / s)$ in underwater environment. We assume an ideal 0/1 sphere sensing model that an object within (outside) a sensor’s sensing sphere is detected by the sensor with probability 1 (0). In order to develop a more practical distributed deployment algorithm for constructing underwater strong k-barrier coverage with available mobile sensors, we consider the existence of possible position error bounded by a maximum error $ϵ_{\max}$ , the value of $ϵ_{\max}$ can be set according to the functional characteristics of specific sensor. Furthermore, we take into account sensor’s possible communication and sensing anisotropy and set $γ = \min {2 R_{s}^{\min}, R_{c}^{\min}} - 2 ϵ_{\max}$ , in which $R_{s}^{\min}$ and $R_{c}^{\min}$ denote the minimum sensing and communication radius of the sensors, respectively. This setting ensures that two adjacent sensors at a distance $γ$ from each other are able to communicate, and their sensing ranges intersect even if position error occurs among the sensors.

Figure 1.

Initially the sensors are deployed in the cuboid. Without loss of generality, we assume that an intruder’s traversing path is a continuously moving trajectory starting at the cuboid’s right face and ending at the opposite face.

We aim to develop a FDDA for underwater strong k-barrier coverage. No special node, such as a leader node or a central unit, is required, all sensors have to rely only on their local information to coordinate their movements. There is also no synchronization among sensors.

Without loss of generality, we assume that the illegal intruders to be detected by underwater sensor barrier move along the direction of cuboid length, as shown in Figure 1, the intruder’s traversing path, that is, the red lines, is a continuously moving trajectory starting at the cuboid’s right face and ending at the opposite face.

Problem statement

According to the aforementioned assumptions, the underwater deployment region is modeled as a cuboid of size $l \times w \times h$ , where l, w, and h denote the length, width, and height of the cuboid, respectively. The position of a point in the cuboid is denoted by coordinates $(x, y, z)$ , where x, y, and z are the x coordinate, y coordinate, and z coordinate of this point, respectively. We suppose that n mobile sensors $S = {s_{1}, s_{2}, \dots, s_{n}}$ is deployed in the cuboid with initial positions $p_{1}, p_{2}, \dots, p_{n}$ . Let $(x_{i}, y_{i}, z_{i})$ denote the coordinates of position $p_{i}$ of sensor $s_{i}$ .

The goal of our work is to devise a FDDA to drive the sensors to move to desired positions, and thus provide maximum-level underwater strong k-barrier coverage. Our problem is how to devise such a FDDA to achieve our goal.

Underwater strong one-barrier coverage

In 2D terrestrial WSNs, a sensor barrier is a chain of sensors from one end of the deployment region to the other end with overlapping sensing zones of adjacent sensors, and the existence of strong k-barrier coverage is equivalent to that of k node-disjoint paths between two vertices in a graph.¹² In other words, 2D k-barrier coverage is constituted with k node-disjoint paths. Notice that one node-disjoint path is actually one-barrier coverage in 2D terrestrial WSNs. Thus, in 2D case, strong k-barrier coverage is constituted with k strong one-barrier coverage, as shown in Figure 2.

Figure 2.

In 2D terrestrial WSNs, a strong k-barrier coverage is constituted with k strong one-barrier coverage (in this example, k = 3).¹²

In 3D UWSNs, a sensor barrier is a set of sensors with overlapping sensing zones of adjacent sensors that covers an entire (curly) surface that cuts across the 3D underwater space.¹¹ Similar to 2D case, an underwater strong k-barrier coverage is constituted with k underwater strong one-barrier coverage, as showed in Figure 3.

Figure 3.

In 3D UWSNs, an underwater strong k-barrier coverage is constituted with k underwater strong one-barrier coverage (in this example, k = 3).

For an underwater strong one-barrier coverage, it is clear that, to minimize the required mobile sensors, the sensors should be repositioned to a vertical plane parallel to the cuboid’s left face. We refer to an underwater strong one-barrier coverage covering such a vertical plane as a layer in this article. Consequently, a feasible approach for constructing an underwater strong k-barrier coverage is to construct it layer by layer. As shown in Figure 3, from left to right, we enumerate the sensor barriers b₀, b₁, b₂, . . ., where b₀ is base layer, and the indexes of the other layers increase with the distance from b₀. In the following, we analyze how to derive the minimum number of required sensors and the optimal final positions of sensors in each layer.

The minimum number of required sensors

As shown in Figure 3, an underwater strong one-barrier coverage finally completely covers a rectangle plane of size $w \times h$ , where w and h denote the width and the height of the cuboid, respectively, and the covered rectangle plane is parallel to the cuboid’s left face. Since the vertical projection of a sensor’s sensing sphere on a plane is a circle with radius r, where r is the sensor’s sensing radius, the minimum number of required sensors equals to the minimum number of circles with radius r required for completely covering a rectangle of size $w \times h$ .

In terms of the problem on the minimum number of circles required for completely covering a rectangle, Kershner³⁷ had proved that the regular triangular tessellation is the optimal tessellation, which makes a set of regular hexagons completely cover a 2D plane without any overlap, as shown in Figure 4. According to the context of our work, if we place a sensor in the center of each regular hexagon of circumradius r, where r is sensor’s sensing radius, the sensing range of all sensors will completely cover the rectangle. Consequently, we have Theorem 1 as follows.

Figure 4.

A rectangle that is completely covered by minimum regular hexagons.

Theorem 1

The minimum number of sensors with sensing radius r required for completely covering a rectangle of size $w \times h$ is

\begin{matrix} f_{s} (w, h, r) = ⌈ \frac{h}{r \times \sqrt{3}} ⌉ \times ⌈ \frac{⌈ \frac{2 \times (w - r)}{3 \times r} ⌉ + 1}{2} ⌉ \\ + (⌈ \frac{h - \frac{r \times \sqrt{3}}{2}}{r \times \sqrt{3}} ⌉ + 1) \times ⌊ \frac{⌈ \frac{2 \times (w - r)}{3 \times r} ⌉ + 1}{2} ⌋ \end{matrix}

(1)

Proof 1

As shown in Figure 4, given a rectangle of size $w \times h$ , in the length direction, we divide the rectangle into c columns, the first column width $a = r$ , the second $~ (c - 1) th$ column width $b = 3 \times r / 2$ , and the last column width is included in interval $(0, b]$ , then the number of columns is

\begin{matrix} f_{c} (w, r) = ⌈ \frac{2 \times (w - r)}{3 \times r} ⌉ + 1 \end{matrix}

(2)

In the width direction, the number of rows of odd-number columns is

\begin{matrix} f_{o} (h, r) = ⌈ \frac{h}{r \times \sqrt{3}} ⌉ \end{matrix}

(3)

The number of rows of even-number columns is

\begin{matrix} f_{e} (h, r) = ⌈ \frac{h - \frac{r \times \sqrt{3}}{2}}{r \times \sqrt{3}} ⌉ + 1 \end{matrix}

(4)

Combining equations (2)–(4), we obtain the minimum number of regular hexagons

\begin{matrix} f_{s} (w, h, r) = f_{o} (h, r) \times ⌈ \frac{f_{c} (w, r)}{2} ⌉ + f_{e} (h, r) \times ⌊ \frac{f_{c} (w, r)}{2} ⌋ \\ = ⌈ \frac{h}{r \times \sqrt{3}} ⌉ \times ⌈ \frac{⌈ \frac{2 \times (w - r)}{3 \times r} ⌉ + 1}{2} ⌉ \\ + (⌈ \frac{h - \frac{r \times \sqrt{3}}{2}}{r \times \sqrt{3}} ⌉ + 1) \times ⌊ \frac{⌈ \frac{2 \times (w - r)}{3 \times r} ⌉ + 1}{2} ⌋ \end{matrix}

(5)

The above derivation obtains the minimum number $f_{s} (w, h, r)$ of sensors required for completely covering a rectangle of size $w \times h$ . Therefore, for the underwater strong k-barrier coverage problem, the minimum number of required sensors in each layer is equal to $f_{s} (w, h, r)$ , and it is straightforward that the minimum number of sensors required for constructing underwater strong k-barrier coverage is equal to $k \times f_{s} (w, h, r)$ , where r is the sensor’s sensing radius, w and h are the width and height of the cuboid.

The optimal final positions of sensors

According to previous analysis, once we place a sensor in the center of each regular hexagon, the sensing range of all sensors will completely cover the rectangle. Actually, for each layer, the optimal final positions of sensors are the center points of regular hexagons, whose x coordinates equal to the layer’s x coordinate. In the following, we derive $y, z$ coordinates of each center point of regular hexagon.

As shown in Figure 4, we first obtain the y coordinate of each column via equation (6), where i denotes the $i th$ column

\begin{matrix} f_{y} (w, r, i) = {\begin{matrix} \frac{r}{2}, & i = 0 \\ \frac{r}{2} + \frac{i \times r}{2}, & \frac{r}{2} + \frac{(f_{c} (w, r) - 1) \times r}{2} < w \\ w, & \frac{r}{2} + \frac{(f_{c} (w, r) - 1) \times r}{2} \geq w \end{matrix} \end{matrix}

(6)

Then we get the z coordinate of each point row by row. For odd-number columns, h denotes the cuboid height, r denotes the sensing radius, j denotes the $j th$ row, and $0 \leq j < ⌈ (h - (r \times \sqrt{3} / 2)) / r \times \sqrt{3} ⌉ + 1$ , we have

\begin{matrix} f_{z} (w, r, j) = h - \frac{r \times \sqrt{3}}{2} - j \times r \times \sqrt{3} \end{matrix}

(7)

For even-number columns, h denotes the cuboid height, r denotes sensor’s sensing radius, j denotes the $j th$ row, and $0 \leq j < ⌈ h / r \times \sqrt{3} ⌉$ , we have

\begin{matrix} f_{z} (w, r, j) = h - j \times r \times \sqrt{3} \end{matrix}

(8)

Combining equations (7) and (8), we have

\begin{matrix} f_{z} (w, r, j) = {\begin{matrix} h - \frac{r \times \sqrt{3}}{2} - j \times r \times \sqrt{3}, odd number columns \\ h - j \times r \times \sqrt{3}, even number columns \end{matrix} \end{matrix}

(9)

Finally, by combining the layer’s x coordinate, we obtain the optimal final positions $(x, f_{y} (w, r, i), f_{z} (w, r, j))$ of sensors in each layer.

FDDA

In this section, we propose a fully FDDA for constructing maximum-level underwater strong k-barrier coverage with available mobile sensors.

Main idea

The main idea of the proposed algorithm is to construct underwater strong k-barrier coverage layer by layer. For the sake of clearness, we introduce two important concepts. One is constructed layer, on which no sensor has adjacent vacant positions resided on the same layer as itself, in other words, this layer has been constructed. The other is constructing layer, on which there are still some vacant positions to be occupied by sensors, in other words, this layer is being constructed. Since underwater strong k-barrier coverage is to be constructed layer by layer, there is only one constructing layer at the same time during the construction process. For example, base layer $b_{0}$ is the constructing layer at the beginning, and after the construction of $b_{0}$ is completed, $b_{0}$ becomes a constructed layer and layer $b_{1}$ is the constructing layer, and so on. As shown in Figure 9(d), from left to right, $b_{0}$ and $b_{1}$ are constructed layers, and $b_{2}$ is the constructing layer. Furthermore, we refer to the sensors resided on constructed layer and constructing layer as fixed sensors, while the sensors not already resided on constructed layers or constructing layer are referred to as movable sensors. A fixed sensor cannot move any more, but a movable sensor can move freely in the underwater space according to its local information. In order to make each movable sensor move orderly to avoid collision as much as possible, and reduce the complexity of the proposed algorithm to ensure that the proposed algorithm performs efficiently, we set a movable sensor’s movement route as follows. If a movable sensor $s_{i}$ with initial position $(x_{s}, y_{s}, z_{s})$ intends to move to position $(x_{e}, y_{e}, z_{e})$ , it first moves to position $(x_{s}, y_{e}, z_{e})$ by means of parallel moving, which means that a sensor moves on a plane parallel to the base layer (i.e. the sensor’s x coordinate will not be changed in the moving process), then moves to position $(x_{e}, y_{e}, z_{e})$ by means of vertical moving, which means that a sensor moves along a straight line perpendicular to the base layer. Nevertheless, in rare circumstances, a sensor moving by means of parallel moving may still collide with other sensors moving by means of parallel or vertical moving. Fortunately, the sensors can avoid collision by existing approaches³⁸; hence, we will not discuss the collision avoidance among sensors in deep in this work.

Furthermore, in order to finally create a single connected barrier component (i.e. an UWSN) to satisfy the management requirement of application, we set the distance between adjacent sensors as $γ$ , which means the distance between two adjacent layers is also $γ$ , this setting ensures that two adjacent sensors at a distance $γ$ from each other are able to communicate, and their sensing ranges intersect, even if position error occurs among the sensors.

The proposed algorithm provides the interleaved execution of three main activities, namely, vertical movement, vacant position processing, and parallel movement. Before starting the execution of the three main activities, each sensor performs an initial movement aiming to move to the closest centerline, which is perpendicular to the base layer and pass through the hexagon center point of each layer, as shown in Figure 5.

Figure 5.

The centerlines are perpendicular to the base layer and pass through the hexagon center points in each layer. As shown in this figure, the red dash lines are centerlines.

Initial movement

In order to make each movable sensor move orderly in underwater space, and thus ensure that the proposed algorithm performs effectively and efficiently, each sensor initially moves to the centerline closest to itself by means of parallel moving. It is worth noting that after the initial movement, all sensors are on the centerlines, and by executing the proposed algorithm, each sensor only moves along the centerline or moves to another centerline by means of parallel moving. We will obtain a sensor’s closest centerline in the next subsection.

Vertical movement

The vertical movement activity is twofold. On one hand, in order to increase the connectivity of the network, each movable sensor moves toward base layer by means of vertical moving if it has no sensor in radio proximity, which is resided on the same centerline and closer to base layer than itself. The movement is stopped as soon as such a sensor is found or the base layer is reached. On the other hand, to ensure that all sensors can finally move their desired positions, each movable sensor with a distance less than $γ$ from a fixed sensor moves toward the opposite direction of the base layer until the distance not less than $γ$ . By vertical movement, a movable sensor connects with other sensors to form a network component and thus prevent it from becoming an isolated sensor. Moreover, sensors in the same network component can communicate with each other by means of a multi-hop manner.

Vacant position processing

There are three aspects in vacant position processing. First, to notify the other sensors of the vacant positions resided on the constructing layer, each sensor periodically detects and broadcasts its adjacent vacant positions resided on the same layer as itself in the network. Second, each sensor receives and processes the vacant positions broadcasted by other sensors. It is worth noting that, in order to manage the vacant positions resided on the constructing layer, each sensor maintains a vacant position queue, where the vacant positions are sorted by the distance between vacant position and the sensor in an ascending order. Finally, by leveraging the data cached in vacant position queue, a sensor makes its movement decision.

Parallel movement

In this activity, a movable sensor first confirms whether it is closest to the vacant position at the head of its vacant position queue. If it is the closest one, it moves to the desired position by means of parallel moving then starts the vertical movement activity. If otherwise, it terminates this activity and gives start to the vertical movement activity. The approach to find the closest vacant position for a movable sensor will be given in the next subsection.

Details of the proposed algorithm

In this subsection, we describe the details of the proposed algorithm FDDA. We first show the detail of the initial movement, and then present the details of three main activities of FDDA. Figure 6 shows a flowchart of these activities.

Figure 6.

Flowchart of the initial movement and the proposed algorithm executed by a sensor s with initial position $(x, y, z)$ .

Initial movement

Initial movement is significant since it places the sensors in an orderly manner on the centerlines and thus ensures that the proposed algorithm performs effectively and efficiently. For each sensor, the key to initial movement is to find the centerline closest to it. According to the previous analysis, the centerlines are perpendicular to the base layer and pass through the hexagon center points in each layer, where the positions $(x, f_{y} (w, r, i), f_{z} (w, r, j))$ of the hexagon center points can be obtained via equations (6) and (9). In the following, we describe how to obtain the centerline closest to a sensor $s_{i}$ .

As shown in Algorithm 1, for a sensor $s_{i}$ with initial position $(x_{i}, y_{i}, z_{i})$ , it first obtains the position list of the hexagon center points by function $getHexagonCenterPoints (w, h, r)$ , which obtains the y coordinate $f_{y} (w, r, i)$ and z coordinate $f_{z} (w, r, j)$ of each hexagon center point in vertical plane $x_{i}$ via equations (6) and (9), respectively. Then it calculates the distance between sensor $s_{i}$ and each hexagon center point $(x_{i}, f_{y} (w, r, i), f_{z} (w, r, j))$ . Obviously, a minimum distance between sensor $s_{i}$ and point $(x_{i}, f_{y} (w, r, i'), f_{z} (w, r, j'))$ will be obtained; the minimum distance is the distance between sensor $s_{i}$ and the centerline closest to it. Thus, we obtain the centerline closest to sensor $s_{i}$

\begin{matrix} (\begin{matrix} y = f_{y} (w, r, i') \\ z = f_{z} (w, r, j') \end{matrix} \end{matrix}

(10)

Algorithm 1: Initial movement performed by sensor $s_{i}$
1: $L_{hcp} \leftarrow getHexagonCenterPoints (w, h, r)$ ; 2: $hexagonNum = len (L_{hcp})$ ; 3: $d_{\min} = 2 * l$ ; 4: $p_{target} = NULL$ ; 5: for $i = 0 \to hexagonNum - 1$ do 6: $d_{tmp} = distance (L_{hcp} [i], s_{i})$ ; 7: if $d_{tmp} < d_{\min}$ then 8: $d_{\min} = d_{tmp}$ ; 9: $p_{target} = L_{hcp} [i]$ ; 10: end if 11: end for 12: move to target position $p_{target}$ ; 13: start vertical movement; 14: return;

Algorithm 1: Initial movement performed by sensor

s_{i}

L_{hcp} \leftarrow getHexagonCenterPoints (w, h, r)

;
2:

hexagonNum = len (L_{hcp})

;
3:

d_{\min} = 2 * l

;
4:

p_{target} = NULL

;
5: for

i = 0 \to hexagonNum - 1

do
6:

d_{tmp} = distance (L_{hcp} [i], s_{i})

;
7: if

d_{tmp} < d_{\min}

then
8:

d_{\min} = d_{tmp}

;
9:

p_{target} = L_{hcp} [i]

;
10: end if
11: end for
12: move to target position

p_{target}

;
13: start vertical movement;
14: return;

Once a sensor $s_{i}$ with position $(x_{i}, y_{i}, z_{i})$ finds the centerline closest to it, it starts to move to the centerline by means of parallel moving until it reaches target position $(x_{i}, f_{y} (w, r, i'), f_{z} (w, r, j'))$ , and then performs the proposed algorithm by starting vertical movement activity.

According to the pseudocode of Algorithm 1, its computational complexity is proportional to the number hexagonNum of hexagon center points in a layer, while $hexagonNum = C \times n$ , where C is a real constant and n is the number of available mobile sensors. Therefore, the computational complexity of Algorithm 1 is $O (n)$ . Since there is no message exchange in the initial movement, we do not consider its message complexity.

Vertical movement

The goal of vertical movement is to increase network connectivity, to avoid the presence of isolated sensors and to ensure that all sensors can finally move to their desired positions. Since all sensors are on the centerlines perpendicular to the base layer after initial movement, and the vertical movement requires the sensors to move along the centerlines in the moving process, each sensor only needs to consider sensors in radio proximity (i.e. the sensors with a distance less than $γ$ from it), which are resided on the same centerline and closer to base layer with respect to itself.

The vertical movement is based on the following described protocol. As shown in Algorithm 2, for a sensor $s_{i}$ , we refer to $C (s_{i})$ as a set of sensors in the sensor’s radio proximity and resided on the same centerline and closer to base layer with respect to itself. If $C (s_{i}) = \emptyset$ , it moves toward the base layer along the centerline until $C (s_{i}) \neq \emptyset$ or it reaches the base layer. If otherwise $C (s_{i}) \neq \emptyset$ , it checks whether $C (s_{i})$ contains fixed sensors. If $C (s_{i})$ contains fixed sensors, it moves toward the opposite direction of the base layer until $C (s_{i})$ does not contain fixed sensor any more. If otherwise $C (s_{i})$ does not contain fixed sensors, it keeps on its current position. It is worth noting that moving a sensor $s_{i}$ to the opposite direction of the base layer, when it finds that $C (s_{i})$ contains fixed sensors, ensures that all sensors can finally move to their desired positions even if they are all initially placed on base layer.

Algorithm 2: Vertical movement performed by sensor $s_{i}$
1: while $C (s_{i}) = \emptyset$ and $s_{i}$ does not reach the base-layer do 2: sensor $s_{i}$ moves toward base-layer along the centerline; 3: end while 4: if $C (s_{i}) \neq \emptyset$ then 5: if $C (s_{i})$ contains fixed sensors then 6: while distance between $s_{i}$ and fixed sensors $< γ$ do 7: sensor $s_{i}$ moves toward the opposite direction of base-layer along the centerline; 8: end while 9: else 10: keep on current position; 11: end if 12: end if 13: if $VP (s_{i}) \neq \emptyset$ then 14: $p_{0} = VP (s_{i}) [0]$ 15: if $s_{i} . x = p_{0} . x$ then 16: broadcast PO message; 17: end if 18: end if 19: start vacant position processing; 20: return;

Algorithm 2: Vertical movement performed by sensor

s_{i}

1: while

C (s_{i}) = \emptyset

and

s_{i}

does not reach the base-layer do
2: sensor

s_{i}

moves toward base-layer along the centerline;
3: end while
4: if

C (s_{i}) \neq \emptyset

then
5: if

C (s_{i})

contains fixed sensors then
6: while distance between

s_{i}

and fixed sensors

< γ

do
7: sensor

s_{i}

moves toward the opposite direction of base-layer along the centerline;
8: end while
9: else
10: keep on current position;
11: end if
12: end if
13: if

VP (s_{i}) \neq \emptyset

then
14:

p_{0} = VP (s_{i}) [0]

15: if

s_{i} . x = p_{0} . x

then
16: broadcast PO message;
17: end if
18: end if
19: start vacant position processing;
20: return;

Finally, if sensor $s_{i}$ has reached the constructing layer, it broadcasts a PO (position occupation) message, which contains sensor ID, timestamp, and its current position information, in the network to remind other sensors to remove this position from their vacant position queues, if their queue contains this position. And then, it gives start to the vacant position processing. If otherwise, it starts the vacant position processing without broadcasting a PO message. We will describe the notion of vacant position queue in the next subsection.

According to the pseudocode of Algorithm 2, its computational complexity is related to a sensor’s movement distance. In the worst case, a sensor may move from the right face to the left face of the cuboid, we assume that it stops to check the conditions at line 1 and line 6 every M meters, thus the while loop in Algorithm 2 may be executed at most $l / M$ . Therefore, the computational complexity of Algorithm 2 is $O (⌈ l / M ⌉)$ . For the message complexity, since a PO message broadcasted at line 16 may be relayed by at most $n - 1$ sensors, the message complexity of Algorithm 4 is $O (n)$ .

Vacant position processing

Vacant position processing involves three aspects, namely, vacant position broadcasting, vacant position receiving, and vacant position leveraging. A sensor keeps on its current position while performing this activity, it first periodically broadcasts and receives vacant position message with a duration time $T_{br}$ , then makes a movement decision according to the data cached in its vacant position queue. The detailed protocol of the vacant position processing is described as follows.

As shown in Algorithm 3, for a sensor $s_{i}$ with a vacant position queue $VP (s_{i})$ (initially $VP (s_{i}) = \emptyset$ ), it first broadcasts a VP (Vacant Position) message containing sensor ID, timestamp, and its adjacent vacant positions resided on the same layer as itself in the network, then it waits for the expiration of its timeout $T_{rcv}$ to receive VP message and PO message broadcasted by other sensors. Notice that we assume the proposed algorithm is implemented over a communication protocol stack which handles possible transmission errors and message losses by means of timeout and retransmission mechanisms, and each sensor keeps track of the VP messages and PO messages sent so far to avoid multiple retransmissions and multiple processing by checking the unique message mark consisting of sensor ID and timestamp. When sensor $s_{i}$ receives a VP message, it checks the cardinality of $VP (s_{i})$ . If $| VP (s_{i}) | = 0$ , the vacant positions are put into $VP (s_{i})$ . If otherwise, it compares the x coordinate of vacant position with that of one sensor in $VP (s_{i})$ , if larger, these vacant positions are omitted; if equal, these vacant positions are inserted into $VP (s_{i})$ ; if smaller, it sets $VP (s_{i}) = \emptyset$ and puts these vacant positions into $VP (s_{i})$ . Similarly, when sensor $s_{i}$ receives a PO message containing position p (p is a vacant position before being occupied), it removes p from its vacant position queue if p is in the queue.

Algorithm 3: Vacant position processing performed by sensor $s_{i}$
1: $t_{start} = time ()$ ; 2: while $time () < t_{start} + T_{rcv}$ do 3: broadcast VP message; 4: receive PO and VP message; 5: if $\| VP (s_{i}) \| = 0$ then 6: put vacant positions in VP into $VP (s_{i})$ ; 7: else 8: $x_{\min} = VP (s_{i}) [0]$ ; 9: if the x-coordinate of vacant position in VP $= x_{\min}$ then 10: put vacant positions in VP into $VP (s_{i})$ ; 11: else if the x-coordinate of vacant position in VP < $x_{\min}$ then 12: $VP (s_{i}) = \emptyset$ ; 13: put vacant positions in VP into $VP (s_{i})$ ; 14: else 15: omit the VP message; 16: end if 17: end if 18: sleep( $T_{sleep}$ ); 19: end while 20: if $VP (s) \neq \emptyset$ then 21: $p_{0} = VP (s_{i}) [0]$ ; 22: if $s_{i} . x \leq p_{0} . x$ then 23: keep current position ( $s_{i}$ is a fixed sensor); 24: sleep a random time in $(0, T_{md}]$ ; 25: start the vacant position processing; 26: return; 27: end if 28: else 29: start parallel movement ( $s_{i}$ is a movable sensor); 30: return; 31: end if

Algorithm 3: Vacant position processing performed by sensor

s_{i}

t_{start} = time ()

;
2: while

time () < t_{start} + T_{rcv}

do
3: broadcast VP message;
4: receive PO and VP message;
5: if

| VP (s_{i}) | = 0

then
6: put vacant positions in VP into

VP (s_{i})

;
7: else
8:

x_{\min} = VP (s_{i}) [0]

;
9: if the x-coordinate of vacant position in VP

= x_{\min}

then
10: put vacant positions in VP into

VP (s_{i})

;
11: else if the x-coordinate of vacant position in VP <

x_{\min}

then
12:

VP (s_{i}) = \emptyset

;
13: put vacant positions in VP into

VP (s_{i})

;
14: else
15: omit the VP message;
16: end if
17: end if
18: sleep(

T_{sleep}

);
19: end while
20: if

VP (s) \neq \emptyset

then
21:

p_{0} = VP (s_{i}) [0]

;
22: if

s_{i} . x \leq p_{0} . x

then
23: keep current position (

s_{i}

is a fixed sensor);
24: sleep a random time in

(0, T_{md}]

;
25: start the vacant position processing;
26: return;
27: end if
28: else
29: start parallel movement (

s_{i}

is a movable sensor);
30: return;
31: end if

By means of the above protocol, each sensor maintains a vacant position queue, where vacant positions are all resided on the constructing layer (the vacant positions resided on the constructing layer have the smallest x coordinate, and consequently, they are finally cached in vacant position queue according to the above protocol) and sorted by the distance between vacant position and the sensor in an ascending order.

After the expiration of time $T_{rcv}$ , sensor $s_{i}$ determines whether it is a movable sensor or a fixed sensor by the following protocol. Sensor $s_{i}$ first obtains the constructing layer’s x coordinate by returning the first element’s x coordinate from its vacant position queue, then it compares the constructing layer’s x coordinate with its, if larger, sensor $s_{i}$ is a fixed sensor resided on constructed layer; if equal, sensor $s_{i}$ is a fixed sensor resided on the constructing layer; if smaller, sensor $s_{i}$ is a movable sensor. Then, according to this determination, sensor $s_{i}$ makes its movement decision as follows.

If sensor $s_{i}$ is a fixed sensor, it keeps its current position and waits a random timeout in the interval $(0, T_{md}]$ to restart the vacant position processing activity. If otherwise, sensor $s_{i}$ is a movable sensor, it terminates this activity and starts the parallel movement activity.

It is worth noting that, in real-life applications, we can optimize the vacant position broadcast through following two strategies to reduce the communication cost caused by broadcast.

Once a sensor $s_{i}$ confirmed that it is a fixed sensor resided on constructed layer, it stops relaying the VP message. This strategy ensures that a sensor’s VP message is only broadcasted in its belonged network component, and thus reduces the size of each sensor’s vacant position queue to improve the proposed algorithm efficiency.

Once a sensor $s_{i}$ confirmed that it is a movable sensor, it stops broadcasting its VP message until it becomes a fixed sensor. This strategy greatly reduces the number of VP messages broadcasted in the network.

According to the pseudocode of Algorithm 3, its computational complexity is related to two parameters, $T_{rcv}$ and $T_{sleep}$ in the while loop at line 2, and the operation at lines 6, 10, and 13. It is clear that the computational complexity of Algorithm 3 is $O (n \times ⌈ T_{rcv} / T_{sleep} ⌉)$ . For the message complexity, since a sensor may receive at most $n - 1$ VP/PO messages broadcasted by the other $n - 1$ sensors, the message complexity of Algorithm 3 is $O (n)$ .

Parallel movement

From the perspective of reducing energy consumption, a movable sensor prefers to move to a vacant position closest to itself. As the previous description, the vacant positions in a sensor’s vacant position queue are ordered by the distance between vacant position and the sensor in an ascending order. It is clear that, for sensor $s_{i}$ , the closest vacant position is $v p_{0}$ with position $(x_{vp 0}, y_{vp 0}, z_{vp 0})$ at the head of its vacant position queue $VP (s_{i})$ . Nevertheless, position $(x_{vp 0}, y_{vp 0}, z_{vp 0})$ may also be the closest vacant position of the other movable sensors. In this case, a vacant position should be filled by the sensor closest to it to reduce the total energy consumption of all sensors. Therefore, in this activity, a movable sensor should first confirm whether it is closest to the vacant position at the head of its vacant position queue. If it is the closest one, it starts to move to its desired position by means of parallel moving. If otherwise, it terminates this activity and gives start to the vertical movement activity. In the following, we describe the detailed protocol.

As shown in Algorithm 4, for a movable sensor $s_{i}$ with coordinates $(x_{i}, y_{i}, z_{i})$ , it broadcasts a CC (Confirm the Closest) message containing sensor ID, timestamp, the vacant position vp with coordinates $(x_{vp}, y_{vp}, z_{vp})$ and the distance between sensor $s_{i}$ and the vacant position vp, and then waits for the expiration of its timeout $T_{cc}$ . When the other sensors receive the CC message, they check whether they are closer to position vp than sensor $s_{i}$ , if closer, they broadcast a CCack message containing CC’s original content. If otherwise, they omit this CC message. If, while waiting for the expiration of its timeout $T_{cc}$ , sensor $s_{i}$ receives a CCack message, it terminates this parallel movement activity and starts vertical movement activity. After the expiration of a timeout $T_{cc}$ , sensor $s_{i}$ moves to position $(x_{i}, y_{vp}, z_{vp})$ by means of parallel moving. Once sensor $s_{i}$ reaches position $(x_{i}, y_{vp}, z_{vp})$ , it gives start to the vertical movement. Similar to the vacant position processing activity, we assume that each sensor keeps track of the CC/CCack messages sent so far to avoid multiple retransmissions and multiple processing by checking the unique message mark consisting of sensor ID and timestamp. Furthermore, to improve the performance of the proposed algorithm, we configure that a fixed sensor does not relay CC/CCack message to ensure that a sensor’s CC/CCack message is only broadcasted in the sensor’s belonged network component.

Algorithm 4: Parallel movement performed by sensor $s_{i}$
1: $t_{start} = time ()$ ; 2: broadcast CC message; 3: while $time () < t_{start} + T_{cc}$ do 4: if received CCack message then 5: start vertical movement; 6: return; 7: end if 8: sleep( $T_{sleep}$ ); 9: end while 10: $vp = VP (s_{i}) [0]$ ; 11: move to position $(x_{i}, y_{vp}, z_{vp})$ by means of parallel moving, where $x_{i}$ denotes the x-coordinate of sensor $s_{i}$ , $y_{vp}$ and $z_{vp}$ denote the y-coordinate and z-coordinate of vp, respectively; 12: start vertical movement; 13: return;

Algorithm 4: Parallel movement performed by sensor

s_{i}

t_{start} = time ()

;
2: broadcast CC message;
3: while

time () < t_{start} + T_{cc}

do
4: if received CCack message then
5: start vertical movement;
6: return;
7: end if
8: sleep(

T_{sleep}

);
9: end while
10:

vp = VP (s_{i}) [0]

;
11: move to position

(x_{i}, y_{vp}, z_{vp})

by means of parallel moving, where

x_{i}

denotes the x-coordinate of sensor

s_{i}

y_{vp}

and

z_{vp}

denote the y-coordinate and z-coordinate of vp, respectively;
12: start vertical movement;
13: return;

According to the pseudocode of Algorithm 2, its computational complexity is related to two parameters, $T_{cc}$ and $T_{sleep}$ , in the while loop at line 3. Obviously, the computational complexity of Algorithm 2 is $O ⌈ (T_{cc} / T_{sleep}) ⌉$ . For the message complexity, since a CC/CCack message may be relayed by at most $n - 1$ sensors, the message complexity of Algorithm 2 is $O (n)$ .

Performance evaluation

In this section, we evaluate the performance of the proposed algorithm FDDA through simulations. We first validate that the proposed algorithm has a guaranteed termination that all sensors stop moving after a finite time and provide maximum-level underwater strong k-barrier coverage in three representative scenarios. Then we show that the proposed algorithm has the capability of self-healing. Finally, we compare FDDA with Hungarian algorithm³⁹ which obtains the optimal total movement distance of all sensors, and HungarianK,³¹ which consumes less computation time than Hungarian. The simulation parameters are described as follows.

Considering that the average ocean depth is 3795 m,⁴⁰ and some commercial magnetic sensors can detect submarines at distances of several hundred meters.¹¹ We assume that the underwater space where the underwater strong k-barrier coverage to be constructed is a cuboid of length $l = 4200 m$ , width $w = 4000 m$ , and height $h = 3800 m$ , respectively. We set $R_{s}^{\min}$ , $R_{c}^{\min}$ , $ϵ_{\max}$ and $V_{\max}$ to $200 m$ , $420 m$ , $10 m$ , and $2 m / s$ , respectively. Under this setting, the proposed algorithm works with $γ = 380 m$ , and each layer needs at least 161 sensors according to equation (1).

Guaranteed termination

The proposed algorithm has no special requirements for the initial deployment of the sensors, they can be initially deployed in any area of the cuboid. For clearness, we classify the initial deployment of sensors into three representative scenarios, namely, global deployment where the sensors are initially deployed throughout the cuboid, local deployment where the sensors are initially deployed in local area of the cuboid, and point deployment where the sensors are initially placed at a point in the cuboid (although, in real-life applications, it is impossible to make all sensors gather at one geographic position, in order to provide insights into this extreme scenario, we consider the point deployment scenario as well). In each scenario, 500 sensors are initially randomly deployed in the cuboid. In this subsection, we validate that all sensors stop moving after a finite time and finally provide maximum-level underwater strong k-barrier coverage in the three representative scenarios.

In the first scenario, the sensors are initially randomly deployed throughout the cuboid, as shown in Figure 7(a). Each sensor starts the proposed algorithm after completing its initial movement. It is worth noting that the sensors are independent of each other and perform the proposed algorithm asynchronously. By vertical movement, the sensors move toward the base layer and form several network components by connecting to each other. The sensors in different network components construct underwater strong k-barrier coverage simultaneously. Figure 7(b)–(d) shows the different instants obtained by the proposed algorithm, which show that, by executing the proposed algorithm, the sensors construct underwater strong k-barrier coverage layer by layer. Finally, Figure 7(e) shows that all sensors stop moving after a finite time, and the sensors finally provide maximum-level underwater strong k-barrier coverage, that is, k = 3.

Figure 7.

In the first scenario, the sensors are initially deployed throughout the cuboid. By executing the proposed algorithm, all sensors stop moving after a finite time, and the sensors finally provide maximum-level underwater strong k-barrier coverage, that is, k = 3: (a) initial deployment, (b) constructing layer b₀, (c) constructing layer b₁, (d) constructing layer b₂, and (e) all sensors stop moving at time 3696 s.

Figure 8(a) shows the initial deployment of sensors in the second scenario, Figure 8(b)–(d) shows the different instants obtained by the proposed algorithm in the second scenario, while Figure 8(e) shows that all sensors stop moving after a finite time, and the sensors finally provide maximum-level underwater strong k-barrier coverage, that is, k = 3. Different from the first scenario, where all sensors move toward the base layer to construct the underwater strong k-barrier layer by layer, in the second scenario, there are some sensors that move toward the opposite direction of the base layer in the construction process, Figure 8(b)–(d) clearly shows this behavior of the sensors. In Figure 8(b), base layer b₀ is the constructing layer, a set of movable sensors, which detect that there are fixed sensors in their radio proximity, move toward the opposite direction of the base layer until they reach layer b₁. Likewise, in Figure 8(c) and (d), a set of sensors move to layer b₂ and layer b₃, and thus complete the construction of underwater strong k-barrier coverage.

Figure 8.

In the second scenario, the sensors are initially deployed in local area of the cuboid. By executing the proposed algorithm, all sensors stop moving after a finite time, and the sensors finally provide maximum-level underwater strong k-barrier coverage, that is, k = 3: (a) initial deployment, (b) constructing layer b₀, (c) constructing layer b₁, (d) constructing layer b₂, and (e) all sensors stop moving at time 1673 s.

Figure 9(a) shows the initial deployment of sensors in the third scenario, where all sensors are placed at a point in the cuboid. By executing the proposed algorithm, the sensors move toward the base layer one by one, and then complete the construction of the underwater strong k-barrier coverage layer by layer. Figure 9(b)–(d) shows the different instants obtained by the proposed algorithm, while Figure 9(e) shows that all sensors stop moving after a finite time, and the sensors finally provide maximum-level underwater strong k-barrier coverage, that is, k = 3. Different from the first two scenarios where the sensors form several network components by vertical movement, there are only one network component in this scenario that makes the proposed algorithm in this scenario spend more time than the first two scenarios.

Figure 9.

In the third scenario, the sensors are initially placed at a point in the cuboid. By executing the proposed algorithm, all sensors stop moving after a finite time, and the sensors finally provide maximum-level underwater strong k-barrier coverage, that is, k = 3: (a) initial deployment, (b) constructing layer b₀, (c) constructing layer b₁, (d) constructing layer b₂, and (e) all sensors stop moving at time 6526 s.

Self-healing capability

In this subsection, we aim to validate whether the proposed algorithm is able to self-heal underwater strong k-barrier to deal with sudden sensor failures.

In real-life underwater applications, some sensors may suddenly cease to work due to malfunction or an attack, which makes the deployed sensors unable to provide maximum-level underwater strong k-barrier coverage. In this simulation, we consider such a scenario after final deployment, 500 sensors provide maximum-level underwater strong k-barrier coverage (i.e. k = 3), but a set of sensors suddenly stop working thanks to an attack, which makes the remaining sensors unable to provide maximum-level underwater strong k-barrier coverage. We assume that a sensor is able to detect faults of its adjacent sensors resided on the same layer as itself. According to previous description, the position of the malfunction sensor will be recognized as a vacant position by its adjacent sensors, and as a result, this vacant position will finally be broadcasted in the network according to the protocol described in Algorithm 3.

Without loss of generality, we assume that 11 failure sensors are on the edge of the barrier for clear presentation, as shown in Figure 10(a). The remaining deployed sensors only provide strong one-barrier coverage after an attack. By executing the proposed algorithm, a set of adequate sensors automatically move to the desired positions, and heal the underwater strong k-barrier layer by layer. Finally, the remaining 489 sensors provide maximum-level underwater strong k-barrier coverage again, that is, k = 3. Figure 10(b)–(d) shows the different instants of the self-healing process.

Figure 10.

By self-healing, a set of adequate sensors move to their desired positions, finally the deployed sensors provide maximum-level strong k-barrier coverage again, that is, k = 3: (a) a collection of sensors stop working due to an attack, which makes the deployed sensors only provide strong one-barrier coverage in this example, (b) layer b₀ is healed, (c) layer b₁ is healed, (d) layer b₂ is healing, and (e) the deployed sensors provide maximum-level underwater strong k-barrier coverage, that is, k = 3.

Comparison with other algorithms

As far as we know, the proposed algorithm FDDA is the first FDDA for constructing maximum-level underwater strong k-barrier coverage with available mobile sensors. To evaluate the performance of FDDA, we compare it with a classic centralized approach, namely, Hungarian algorithm,³⁹ which minimizes the total movement distance of all sensors, and HungarianK¹¹ consumes less computation time than Hungarian. We assume that all sensors are initially randomly deployed throughout the underwater space. The number of available sensors ranges from 100 to 800 with an increment of 100 each time. Four performance metrics are considered in the simulation experiments, namely, average movement distance of each sensor, maximum movement distance of all sensors, total movement distance of all sensors, and duration of the construction of underwater strong k-barrier coverage.

Figure 11 shows the average movement distance achieved by FDDA, Hungarian, and HungarianK. Three algorithms show that the average movement distance decreases with the increasing number of sensors. This is because more sensors locate closer to their final positions as the number of sensors increases. Although, in Hungarian algorithm, each sensor moves from its initial position to its final position along a straight line that minimizes its movement distance, the average movement distance of Hungarian algorithm is only 28% lower than that of the proposed algorithm FDDA.

Figure 11.

Average movement distance versus number of sensors.

Figure 12 shows the maximum movement distance of all sensors achieved by FDDA, Hungarian, and HungarianK. Three algorithms show a gentle decreasing behavior of the maximum movement distance as the number of sensors increases. This is because more sensors locate closer to their final positions as the number of sensors increases. HungarianK obtains a best result which is about 35% lower maximum movement distance than FDDA, this is because under HungarianK algorithm each sensor moves from its initial position to its final position along a straight line, while most of the sensors in the proposed algorithm FDDA move to their final positions by means of vertical or parallel moving according to their movement decisions, which makes them move along zigzag route.

Figure 12.

Maximum movement distance versus number of sensors.

For the total movement distance of all sensors, although the Hungarian algorithm is the optimal solution that achieves the minimum total movement distance, the proposed algorithm FDDA also presents an acceptable result, as shown in Figure 13, the optimal total movement distance of Hungarian algorithm is only 28% lower than that of FDDA.

Figure 13.

Total movement distance versus number of sensors.

The duration depicts the length of the time that the construction of the underwater strong k-barrier coverage continues. For Hungarian and HungarianK, the duration includes the computing time consumed by the central unit to assign a final position per sensor, and movement time consumed by all sensors to move from their initial positions to their final positions along a straight line. While for FDDA, the duration mainly includes the movement time consumed by all sensors to move from their initial positions to their final positions along a zigzag route. As shown in Figure 14, the durations of Hungarian and HungarianK increase sharply as the number of sensors increases, while the increase in the duration of FDDA is relatively flat. This is because the optimal computational complexity of Hungarian algorithm is $O (n^{3})$ , while the time complexity of FDDA is $O (n)$ , the increase in the number of sensors leads to an exponential increase in computing time of Hungarian algorithm. It is worth noting that the duration of Hungarian and HungarianK are a little less than that of FDDA when the number of sensors is less than 450, this is because, in this case, the central unit of the Hungarian and HungarianK only consumes relatively little time, while the maximum movement distance of FDDA is larger than that of Hungarian and HungarianK, which results in more time needed for the proposed algorithm to move the sensors to their desired positions. In general, the proposed algorithm outperforms Hungarian and HungarianK in terms of duration.

Figure 14.

Duration time versus number of sensors.

Conclusion

In this article, we devised a FDDA for constructing maximum-level underwater strong k-barrier coverage with available mobile sensors in 3D underwater environment. We first analyzed how to form underwater strong one-barrier coverage with minimum mobile sensors, based on which we obtained the minimum number of sensors required for constructing underwater strong one-barrier coverage and the corresponding optimal final positions of these sensors. Then, we proposed a FDDA for constructing maximum-level underwater strong k-barrier coverage with available mobile sensors in 3D underwater environment. By extensive experiments, we showed that the proposed algorithm has a guaranteed termination that all sensors stop moving after a finite time and provide maximum-level underwater strong k-barrier coverage, and the proposed algorithm is able to self-heal the underwater strong k-barrier coverage to deal with sudden sensor failures. Experimental results showed that the proposed algorithm outperforms both Hungarian and HungarianK in terms of duration and achieves performance close to them with respect to three performance metrics, namely, average movement distance of each sensor, maximum movement distance of all sensors, and total movement distance of all sensors.

Footnotes

Handling Editor: Feng Hong

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 work was supported in part by Major Omnibus Reform Project (Information and Computing Science) of China under Grant No. 82616611, National Science Foundation of China under Grant Nos 61373158 and 61671213, Guangzhou Key Lab of Body Data Science under Grant No. 201605030011.

ORCID iD

Weiqiang Shen

References

Gong

Zhang

Cochran

et al . Optimal placement for barrier coverage in bistatic radar sensor networks. IEEE ACM T Network 2016; 24(1): 259–271.

Nguyen

So-In

Distributed deployment algorithm for barrier coverage in mobile sensor networks. IEEE Access 2018; 6: 21042–21052.

Cheng

Wang

CW.

The target-barrier coverage problem in wireless sensor networks. IEEE T Mobile Comput 2018; 17(5): 1216–1232.

Shen

. Minimizing the maximum sensor movement for barrier coverage in the plane. In: 2015 IEEE conference on computer communications (INFOCOM 2015), Kowloon, Hong Kong, 26 April–1 May 2015, pp.244–252. New York: IEEE.

Wang

Liao

Cao

et al . Achieving k-barrier coverage in hybrid directional sensor networks. IEEE T Mobile Comput 2014; 13(7): 1443–1455.

Kulhandjian

Melodia

Koutsonikolas

CDMA-based analog network coding for underwater acoustic sensor networks. IEEE T Wirel Commun 2015; 14(11): 6495–6507.

Khan

Ali

Rahman

et al . Co-EEORS: cooperative energy efficient optimal relay selection protocol for underwater wireless sensor networks. IEEE Access 2018; 6: 28777–28789.

Jiang

Han

Zhu

et al . A trust cloud model for underwater wireless sensor networks. IEEE Commun Mag 2017; 55(3): 110–116.

Das

Thampi

SM.

Fault-resilient localization for underwater sensor networks. Ad Hoc Netw 2017; 55: 132–142.

10.

Barr

Liu

Wang

Underwater sensor barriers with auction algorithms. In: Proceedings of the 18th international conference computer communications and networks, San Francisco, CA, 3–6 August 2009, pp.1–6. New York: IEEE.

11.

Barr

Wang

Liu

An efficient method for constructing underwater sensor barriers. J Commun 2011; 6(5): 370–383.

12.

Kumar

Lai

Arora

Barrier coverage with wireless sensors. In: Proceedings of the 11th annual international conference on mobile computing and networking (MOBICOM 2005), Cologne, 28 August–2 September 2005, pp.284–298. New York: ACM.

13.

Gage

DW.

Command control for many-robot systems. DTIC technical report, DTIC, Fort Belvoir, VA, June 1992.

14.

Chen

Lai

Xuan

. Measuring and guaranteeing quality of barrier-coverage in wireless sensor networks. In: Proceedings of the 9th ACM international symposium on mobile ad hoc networking and computing (MobiHoc 2008), Hong Kong, China, 26–30 May 2008, pp.421–430. New York: ACM.

15.

Fan

Sun

et al . Barrier coverage by sensors with adjustable ranges. ACM T Sensor Network 2014; 11(1): 14.

16.

Liu

Dousse

Wang

et al . Strong barrier coverage of wireless sensor networks. In: Proceedings of the 9th ACM international symposium on mobile ad hoc networking and computing (MobiHoc 2008), Hong Kong, China, 26–30 May 2008, pp.411–420. New York: ACM.

17.

Chen

Lai

et al . One-way barrier coverage with wireless sensors. In: 30th IEEE international conference on computer communications, joint conference of the IEEE computer and communications societies (INFOCOM 2011), Shanghai, China, 10–15 April 2011, pp.626–630. New York: IEEE.

18.

Yang

Qiao

Barrier information coverage with wireless sensors. In: 28th IEEE international conference on computer communications, joint conference of the IEEE computer and communications societies (INFOCOM 2009), Rio de Janeiro, Brazil, 19–25 April 2009, pp.918–926. New York: IEEE.

19.

Gong

Zhang

et al . Barrier coverage in wireless sensor networks: from lined-based to curve-based deployment. In: Proceedings of the IEEE INFOCOM 2013, Turin, 14–19 April 2013, pp.470–474. New York: IEEE.

20.

Wang

Chen

Cao

et al . Achieving location error tolerant barrier coverage for wireless sensor networks. Comput Netw 2017; 112: 314–328.

21.

Wang

Chen

Cao

et al . Fault tolerant barrier coverage for wireless sensor networks. In: 2014 IEEE conference on computer communications (INFOCOM 2014), Toronto, ON, Canada, 27 April–2 May 2014, pp.1869–1877. New York: IEEE.

22.

DeWitt

Shi

Barrier coverage in energy harvesting sensor networks. Ad Hoc Netw 2016; 56: 72–83.

23.

Yang

Qiao

. Multi-round sensor deployment for guaranteed barrier coverage. In: 29th IEEE international conference on computer communications, joint conference of the IEEE computer and communications societies (INFOCOM 2010), San Diego, CA, 14–19 March 2010, pp.2462–2470. New York: IEEE.

24.

Chen

et al . Cost-effective barrier coverage by mobile sensor networks. In: Proceedings of the IEEE INFOCOM 2012, Orlando, FL, 25–30 March 2012, pp.819–827. New York: IEEE.

25.

Saipulla

Westphal

Liu

et al . Barrier coverage of line-based deployed wireless sensor networks. In: Proceedings of the IEEE INFOCOM 2009, Rio de Janeiro, Brazil, 19–25 April 2009, pp.127–135. New York: IEEE.

26.

Dobrev

Kranakis

Krizanc

et al . Weak coverage of a rectangular barrier. CoRR 2017, https://arxiv.org/abs/1701.07294

27.

Silvestri

Goss

Mobibar: an autonomous deployment algorithm for barrier coverage with mobile sensors. Ad Hoc Netw 2017; 54: 111–129.

28.

Ban

Yang

Jiang

et al . Energy-efficient algorithms for k-barrier coverage in mobile sensor networks. Int J Comput Commun 2010; 5(5): 616–624.

29.

Saipulla

Liu

Xing

et al . Barrier coverage with sensors of limited mobility. In: Proceedings of the 11th ACM international symposium on mobile ad hoc networking and computing (MobiHoc 2010), Chicago, IL, 20–24 September 2010, pp.201–210. New York: ACM.

30.

Kong

Lin

Xie

et al . Adaptive barrier coverage using software defined sensor networks. IEEE Sens J 2016; 16(20): 7364–7372.

31.

Barr

Liu

Wang

. Barrier coverage for underwater sensor networks. In: 2008 IEEE military communications conference (MILCOM 2008), San Diego, CA, 16–19 November 2008, pp.1–7. New York: IEEE.

32.

Luo

Hong

Ocean barrier: a floating intrusion detection ocean sensor networks. In: 2016 12th international conference on mobile ad-hoc and sensor networks (MSN), Hefei, China, 16–18 December 2016, pp.390–394. New York: IEEE.

33.

Shen

Zhang

Chen

et al . An efficient algorithm for constructing underwater sensor barrier. In: International conference on communications and networking in China, Xi’an, China, 10–12 October 2017, pp.153–164. Cham: Springer.

34.

Isik

Akan

OB.

A three dimensional localization algorithm for underwater acoustic sensor networks. IEEE T Wirel Commun 2009; 8(9): 4457–4463.

35.

Xie

Yan

Receding horizon formation tracking control of constrained underactuated autonomous underwater vehicles. IEEE T Ind Electron 2017; 64(6): 5004–5013.

36.

Chen

Zhu

A novel cooperative hunting algorithm for inhomogeneous multiple autonomous underwater vehicles. IEEE Access 2018; 6: 7818–7828.

37.

Kershner

The number of circles covering a set. Am J Math 1939; 61(3): 665–671.

38.

Ganesan

Chitre

Brekke

Robust underwater obstacle detection and collision avoidance. Auton Robot 2016; 40(7): 1165–1185.

39.

Kuhn

HW.

The hungarian method for the assignment problem. Nav Res Logist Q 1955; 2(1–2): 83–97.

40.

Rafferty

JP.

Oceans and oceanography. Chicago, IL: Britannica Educational Publishing, 2010.