Redundancy Model and Boundary Effects Based Coverage-Enhancing Algorithm for 3D Underwater Sensor Networks

Abstract

In the study of three-dimensional underwater sensor networks, the nodes would produce changes in perception range under the influence of environmental factors and their own hardware. Requesting all nodes completely isomorphic is unrealistic. Ignoring boundary effects usually causes the coverage effect of the actual deployment of networks to not reach the anticipated result. This paper firstly presents an underwater sensing model with normal distributed node sensing radius. Secondly, it gives the relationship between expected deployment quality and the number of nodes in the premise of considering boundary effects. Then, it deduces nodes’ redundancy formula based on the sensing model with normal distributed node sensing radius, making node could determine whether itself is a redundant node only based on the number of its neighbour nodes. Furthermore, this paper proposes a redundancy model and boundary effects based coverage-enhancing algorithm for three-dimensional underwater sensor networks (RBCT). Simulation results show that RBCT, compared to similar algorithms, has certain advantages in saving energy and enhancing coverage rate.

1. Introduction

Underwater wireless sensor network (UWSN) has drawn great attention over the recent years for its extensive application prospect in oceanographic hydrological data collection, marine pollution monitoring, marine disaster early-warning, and underwater military reconnaissance [1–8]. Before the emergence of wireless sensor networks (WSNs), underwater data perception and collection depend on costly wired network, while UWSN highly reduces the cost of these underwater applications. UWSN consists of nodes that are cooperatively monitoring in three-dimensional space. According to the three-dimensional UWSN model in [9] proposed by Tezcan et al., the architecture of UWSN consists of anchor, underwater sensor node, and buoy node. Figure 1 depicts the architecture of UWSN. Sensor devices are broadcasted to target area from aircraft or boat. As soon as it comes into contact with water, devices anchor is fixed on the location to avoid floating away with ocean current and deviating from monitoring area which occurred in the model proposed by Tezcan et al. At initial phase, sensor node and the buoy node float on the sea surface. In working phase, according to control algorithm, devices can adjust the length of cable between buoy node and underwater sensor node to deploy the underwater sensor to appointed depth. In the model proposed by Akyildiz et al. [10] and Heidemann et al. [11], underwater sensors anchor in the bottom of sea and communicate via acoustic link. However, in current technical conditions, un derwater acoustic link with narrow band width and high latency can easily be interfered by path loss, noise, multipath effect, and so forth [12, 13]. Therefore, we choose cable as communication medium between underwater sensor nodes and buoy nodes while nodes communicate with each other via wireless communication between buoy nodes. The wireless communication module of buoy nodes has multiple power levels to maintain different communication radius. Buoy can also equip locating device like GPS receiver and energy supply device like solar panel. When buoy receives data from underwater sensor node, it transmits them to base station on the sea or shore and then the data is forwarded to communication satellite, ground network, and terminal user.

Figure 1

Architecture of UWSN.

In WSN, coverage rate is an important indicator to network service quality which is the same in UWSN. Optimizing underwater sensor network coverage has important significance for rationally allocating network space resources, better achieving environmental perception and information acquisition task, and improving the network viability. Terrestrial wireless sensor networks have been studied extensively. In [14], Bai et al. propose and design a series of connected coverage models in three-dimensional wireless sensor networks with low connectivity and full coverage. In [15], Alam and Haas study truncated octahedron deployment strategy to monitor network coverage situation. However, there are little researches on three-dimensional underwater sensor networks. In [16], Alam and Haas point that an underwater sensor network can have significant height which makes it a three-dimensional network unlike a terrestrial network. There are many important sensor network design problems where the physical dimensionality of the network plays a significant role. One such problem is determining how to deploy minimum number of sensor nodes so that all points inside the network are within the sensing range of at least one sensor and all sensor nodes can communicate with each other, possibly over a multihop path. The solution to this problem depends on the ratio of the communication range and the sensing range of each sensor. Under sphere-based communication and sensing model, placing a node at the centre of each virtual cell created by truncated octahedron-based tessellation solves this problem when this ratio is greater than 1.7889. However, for smaller values of this ratio, the solution depends on how much communication redundancy the network needs. Alam and Haas provide solutions for both limited and full communication redundancy requirements. In [17], Akkaya and Newell propose a distributed node deployment scheme which can increase the initial network coverage in an iterative basis. Assuming that the nodes are initially deployed at the bottom of the water and can only move in vertical direction in 3D space, the idea is to relocate the nodes at different depths in order to reduce the sensing overlaps among the neighbouring nodes. The nodes continue to adjust their depths until there is no room for improving their coverage.

In consideration of energy limitation of nodes and the requirement of durability without energy supply, we make use of the redundancy of nodes and heuristic algorithm to make nodes switch to certain state in order to shut down nodes in turn with guaranteed service quality. As a result, node energy is conserved and network lifetime is prolonged. Most of the existing researches are based on the assumption that sensing radius of all nodes is the same while in practice radius varies due to nodes’ characteristics and environmental influence. This paper presents an underwater sensing model with normal distributed node sensing radius and analyzes the redundancy model of these nodes. Furthermore, this paper proposes RBCT algorithm combined with the virtual potential field algorithm to optimize the coverage of networks.

2. Network Model and Problem Description

2.1. Problem Formulation

The coverage enhancement problem of three-dimensional sensor networks can be described as follows. Given a three-dimensional target area, we should create a reasonable mathematical model to find out the relationship between expected deployment quality and the number of nodes in the premise of considering boundary effects. This mathematical model can be used to guide the deployment of nodes. After deployment of certain scale sensor nodes, the problem is how to adjust the nodes’ working conditions to maximize network survival time. When a certain number of nodes are working, the problem is how to adjust the depth of underwater sensor nodes by using coverage optimization algorithms to maximize coverage rate.

We assume that the underwater sensor network has the following properties. (1)

The distribution of underwater sensor nodes obeys Boolean sensing model. Underwater sensor node $S_{i}$ with sensing radius r is located in three-dimensional space Ω. When the distance between the target and $S_{i}$ is longer than r, the probability of target being detected by $S_{i}$ is 0; otherwise the probability is 1. Then the sensing area of $S_{i}$ is a sphere with center $S_{i}$ and radius r. This sphere is denoted as SD_i, which is composed of all points that satisfies (1). x represents point in the space. $D_{i x}$ represents the distance between point x and $S_{i}$ . Consider

\begin{matrix} S D_{i} = {x | x \in Ω, D_{i x} ⩽ r} . \end{matrix}

(1)

(2)

Sensing radius of underwater sensor nodes is normally distributed as $N (r_{0}, δ^{2})$ . $r_{0}$ is mean value of node sensing radius, also called rated sensing radius. $δ$ is standard deviation and $r_{0} \geq 3.3 δ$ to ensure sensing radius intensively distributed in $[0, 2 r_{0}]$ .

(3)

Length of the cable between underwater sensor node and buoy node is adjustable; namely, underwater sensor nodes can accurately move to appointed target location in vertical coordinate axis.

(4)

Each underwater sensor node only needs to know the relative position between itself and its neighbouring nodes, without the need to know the precise location by positioning devices.

In the ideal network model, all the underwater sensor nodes have the same rated sensing radius $r_{0}$ . But when they are deployed in practical environment, sensing radii of nodes may be influenced by their own characteristics or environmental factor and cause difference. Therefore, we assume that sensing radii of underwater sensor nodes are normally distributed as $r ~ N (r_{0}, δ^{2})$ . And parameter $r_{0}$ and δ are restricted to satisfy $r_{0} \geq 3.3 δ$ . So the probability of sensing radius within $(- \infty, 0)$ will be less than 0.0005. Due to symmetry of normal distribution, the probability of sensing radius within $[0, 2 r_{0}]$ will be larger than 0.9990. We can draw a conclusion that sensing radius of underwater nodes within $[0, 2 r_{0}]$ is a certain event.

2.2. Related Definition

Definition 1.

Neighbor nodes set $ψ_{i}$ : in WSNs, a pair of nodes is called neighbouring nodes in condition that their Euclidean distance $D_{i j}$ is shorter than twice the sensing radius r

\begin{matrix} ψ_{i} = {n_{j} | D_{i j} < 2 r_{s}, i \neq j} . \end{matrix}

(2)

Definition 2.

Coverage degree Cd(x): the number of nodes that covered point x is called the coverage degree of point x, denoted as Cd(x):

\begin{matrix} Cd (x) = | S C |, \\ S C = {S_{i} | S_{i} \in Ω, x \in S D_{i}} . \end{matrix}

(3)

Definition 3.

Coverage rate $C_{r}$ : the coverage rate of WSNs that are deployed in target area Ω is denoted as $C_{r}$ , defined as follows:

\begin{matrix} C_{r} = \frac{\int_{Ω} v (x) d x}{V (Ω)} . \end{matrix}

(4)

V (Ω)

is the volume of Ω and to any point x satisfies

x \in Ω

, and

\begin{matrix} v (x) = {\begin{cases} 1, & Cd (x) ⩾ 1 \\ 0, & otherwise . \end{cases} \end{matrix}

(5)

3. Analysis on Coverage Quality and Nodes Deployment Density

Since the boundary effects will have a greater impact on nodes deployment, in this section, we will analyze the relationship between the number of nodes deployed randomly and the initial network coverage expectations under the premise of considering boundary effects.

To a random given node $S_{i}$ , the distance between $S_{i}$ and its nearest boundary of monitored region is defined as $d_{i}$ . The overlap area of a node's sensing area and monitored region is defined as $E f (d_{i})$ , which is also known as effective sensing area of node i. Therefore, if node $S_{i}$ satisfies $d_{i} \geq r$ , effective sensing area satisfies Ef $(d_{i}) = 4 π r_{i}^{3} / 3$ . If node $S_{i}$ satisfies $0 \leq d_{i} < r_{i}$ , effective sensing area satisfies $E f (d_{i}) < 4 π r_{i}^{3} / 3$ . Therefore, to a given $r_{0} > 0$ and monitored region Ω, Ω is divided into four areas as shown in Figure 2, namely, Ω(0), Ω(1), Ω(2), and Ω(3). Equation (6) shows the volume of these four areas:

\begin{array}{l} ∥ Ω (0) ∥ = (l - 2 r_{0}) (m - 2 r_{0}) (n - 2 r_{0}), \\ ∥ Ω (1) ∥ = 4 (l - 2 r_{0}) r_{0}^{2} + 4 (m - 2 r_{0}) r_{0}^{2} + 4 (n - 2 r_{0}) r_{0}^{2}, \\ ∥ Ω (2) ∥ = 8 r_{0}^{3}, \\ ∥ Ω (3) ∥ = 2 r_{0} (l - 2 r_{0}) (m - 2 r_{0}) + 2 r_{0} (l - 2 r_{0}) (n - 2 r_{0}) \\ + 2 r_{0} (n - 2 r_{0}) (m - 2 r_{0}) . \end{array}

(6)

Figure 2

Monitored region and related subregion.

Variable M represents the volume that is not covered by nodes in monitored region Ω:

\begin{matrix} M = \int_{Ω} χ (x) d x, \\ χ (x) = {\begin{cases} 1, & Cd (x) = 0 \\ 0, & Cd (x) \geq 1 . \end{cases} \end{matrix}

(7)

Using Fubini's theorem we obtain that

\begin{matrix} E (M) = \int_{Ω} E (χ (x)) d x . \end{matrix}

(8)

To a given random point $x \in Ω$ , $V (x)$ represents the sphere centered at x and with radius $r_{0}$ . If point x is covered, at least one underwater sensor node is in $V (x)$ ; so we obtain (9). Pr represents the probability of the event occurring. Consider

\begin{matrix} E {χ (x)} = Pr {x is not covered} . \end{matrix}

(9)

To a given random point $x \in Ω$ and underwater sensor node $S_{i}$ , the probability of x being covered by $S_{i}$ is defined as $p_{x i}$ . So the probability of x not being covered by $S_{i}$ is defined as $\bar{p_{x i}}$ . Shown in Figure 2, the location of $S_{i}$ to monitored region Ω has four possible results: (1) $S_{i}$ is located in Ω(0); (2) $S_{i}$ is located in Ω(1); (3) $S_{i}$ is located in Ω(2); (4) $S_{i}$ is located in Ω(3). The above four events are mutually exclusive events. Therefore, the probability $\bar{p_{x i}}$ of a random point $x \in Ω$ not being covered by node $S_{i}$ can be expressed as (10). $E_{V} [0]$ , $E_{V} [1]$ , $E_{V} [2]$ , and $E_{V} [3]$ represent the average volume of $E f (d_{i}$ ) when $S_{i}$ is located in Ω(0), Ω(1), Ω(2), and Ω(3). Consider

\begin{array}{l} \bar{p_{x i}} = 1 - p_{x i} = 1 - (\int_{Ω (0)} \frac{E_{V} [0]}{∥ Ω ∥} d x + \int_{Ω (1)} \frac{E_{V} [1]}{∥ Ω ∥} d x \\ + \int_{Ω (2)} \frac{E_{V} [2]}{∥ Ω ∥} d x + \int_{Ω (3)} \frac{E_{V} [3]}{∥ Ω ∥} d x) . \end{array}

(10)

When $S_{i}$ is located in Ω(0), the whole sensing area of $S_{i}$ is contained in monitored region Ω. Consider

\begin{matrix} E_{V} [0] = \frac{4 π r_{0}^{3}}{3} . \end{matrix}

(11)

When $S_{i}$ is located in Ω(1), there are two possible situations as shown in Figure 3. Figure 3 shows a cross-sectional view of node's sensing area and monitored region. Parameters a and b represent the distance between node and the two borders of monitored region in Ω(1). $E_{V} [1]$ can be expressed as in (12). $E_{V 1} [1]$ and $E_{V 2} [1]$ represent the average volume of $E f (d_{i})$ in situations 1 and 2.

Figure 3

Two situations of $S_{i}$ within Ω(1).

Situation 1. The distance between node and the corner of Ω(1) is shorter than $r_{0}$ .

Situation 2. The distance between node and the corner of Ω(1) is longer than $r_{0}$ . Consider

\begin{array}{l} E_{V} [1] = \frac{(1 / 3) π r_{0}^{3}}{r_{0}^{3}} E_{V 1} [1] + (1 - \frac{(1 / 3) π r_{0}^{3}}{r_{0}^{3}}) E_{V 2} [1] \\ = \frac{π}{3} E_{V 1} [1] + \frac{3 - π}{3} E_{V 2} [1] . \end{array}

(12)

We denote $V_{Ω_{1} (1)} (a, b)$ and $V_{Ω_{2} (1)} (a, b)$ as overlap volume of node sensing area and monitored region in situations 1 and 2, respectively. Consider

\begin{array}{l} V_{Ω_{1} (1)} (a, b) \\ = \frac{4 π r_{0}^{3}}{3} - \frac{π {(r_{0} - a)}^{2} (a + 2 r_{0})}{3} \\ - \int_{0}^{a + \sqrt{r_{0}^{2} - b^{2}}} {arccos [\frac{b}{\sqrt{r_{0}^{2} - {(a - x)}^{2}}}] [r_{0}^{2} - {(a - x)}^{2}] \\ - b \sqrt{r_{0}^{2} - b^{2} - {(a - x)}^{2}}} d x, \\ V_{Ω_{2} (1)} (a, b) = π {(r_{0} - x)}^{2} (\frac{2 r_{0} + x}{3}) \\ + π {(r_{0} - y)}^{2} (\frac{2 r_{0} + y}{3}), \\ E_{V 1} [1] = \frac{4}{π r_{0}^{2}} \int_{0}^{r_{0}} \int_{0}^{\sqrt{{r_{0}}^{2} - a^{2}}} V_{Ω_{1} (1)} (a, b) d a d b = \frac{π r_{0}^{3}}{4 - π}, \\ E_{V 2} [1] = \frac{92 π r_{0}^{3}}{4 - π} . \end{array}

(13)

$E_{V} [1]$ can be expressed as

\begin{matrix} E_{V} [1] = \frac{π^{2} r_{0}^{3}}{9} + \frac{π r_{0}^{3}}{18} . \end{matrix}

(14)

Since Ω(2) is only a small part of Ω, the probability that a node is located in Ω(2) is very small. Even if a node is located in Ω(2), the volume of Ω(2) which is not covered by node is very small compared to Ω. So its impact on the calculation results can be ignored. To simplify the calculations, we set $E_{V} [2] = r_{0}^{3}$ when $S_{i}$ is located in Ω(2).

Parameter a represents the distance between node $S_{i}$ within region Ω(3) and the closest border of monitored region Ω. The overlap region of node sensing area and monitored region is shown in Figure 4. $V_{Ω (3)} (a)$ represents the overlap region of node sensing area and Ω(3). Consider

\begin{array}{l} V_{Ω (3)} (a) = \frac{4 π r_{0}^{3}}{3} - π {(r_{0} - a)}^{2} (\frac{2 r_{0} - a}{3}) \\ E_{V} [3] = \frac{1}{r_{0}} \int_{0}^{r_{0}} V_{Ω (3)} (a) d a \\ = \frac{4 π r_{0}^{3}}{3} - \frac{1}{r_{0}} \int_{0}^{r_{0}} π {(r_{0} - a)}^{2} (\frac{2 r_{0} - a}{3}) d a \\ = \frac{13 π r_{0}^{3}}{12} . \end{array}

(15)

Figure 4

Node $S_{i}$ in Ω(3).

With $E_{V} [0]$ , $E_{V} [1]$ , $E_{V} [2]$ , and $E_{V} [3]$ , $\bar{p_{x i}}$ can be expressed as (16). To a given random underwater sensor node $S_{i}$ , we can obtain the expected volume of the overlap region of node sensing area and monitored region as shown in (17):

\begin{array}{l} \bar{p_{x i}} = 1 - (∥ Ω (0) ∥ \frac{4 π r_{0}^{3}}{3} \\ + ∥ Ω (1) ∥ (\frac{π^{2} r_{0}^{3}}{9} + \frac{π r_{0}^{3}}{18}) \\ + ∥ Ω (2) ∥ r_{0}^{3} + ∥ Ω (3) ∥ \frac{13 π r_{0}^{3}}{12}) \times {(l m n)}^{- 1}, \end{array}

(16)

\begin{array}{l} E [S_{i}] \\ = (∥ Ω (0) ∥ E_{V} [0] + ∥ Ω (1) ∥ E_{V} [1] + ∥ Ω (2) ∥ E_{V} [2] \\ + ∥ Ω (3) ∥ E_{V} [3]) \times {(∥ Ω ∥)}^{- 1} \\ = (\frac{4}{3} π r^{3} (l - 2 r) (m - 2 r) (n - 2 r) \\ + (\frac{π^{2} r^{3}}{9} + \frac{π r^{3}}{18}) \\ \times [4 (m - 2 r) r^{2} + 4 (n - 2 r) r^{2} + 4 (l - 2 r) r^{2}]) \\ \times {(l m n)}^{- 1} \\ + (8 r^{6} + \frac{13}{6} π r^{4} [(m - 2 r) (l - 2 r) \\ + (n - 2 r) (l - 2 r) \\ + (m - 2 r) (n - 2 r)]) \\ {\times (l m n)}^{- 1} . \end{array}

(17)

When the number of nodes deployed in Ω is N, we obtain

\begin{array}{l} E {χ (x)} = \prod_{i = 1}^{N} \bar{p_{x i}} = {(\bar{p_{x i}})}^{N}, \\ E (M) \\ = \int_{Ω} {(\bar{p_{x i}})}^{N} d x \\ = \int_{Ω} (1 - (∥ Ω (0) ∥ \frac{4 π r_{0}^{3}}{3} + ∥ Ω (1) ∥ \\ \times (\frac{π^{2} r_{0}^{3}}{9} + \frac{π r_{0}^{3}}{18}) + ∥ Ω (2) ∥ r_{0}^{3} \\ {+ ∥ Ω (3) ∥ \frac{13 π r_{0}^{3}}{12}) \times {(l m n)}^{- 1})}^{N} d x \\ = ∥ Ω ∥ (1 - (∥ Ω (0) ∥ \frac{4 π r_{0}^{3}}{3} \\ + ∥ Ω (1) ∥ (\frac{π^{2} r_{0}^{3}}{9} + \frac{π r_{0}^{3}}{18}) + ∥ Ω (2) ∥ r_{0}^{3} \\ {+ ∥ Ω (3) ∥ \frac{13 π r_{0}^{3}}{12}) \times {(l m n)}^{- 1})}^{N} . \end{array}

(18)

When N nodes are deployed in Ω, we use EDQ (expected deployment quality) to represent the expected deployment quality of the three-dimensional underwater sensor networks. Therefore, if EDQ is required to achieve a certain value in considering boundary effect, the number of nodes deployed in Ω should satisfy (20):

\begin{array}{l} EDQ = 1 - \frac{E (M)}{∥ Ω ∥} \\ = 1 - (1 - (∥ Ω (0) ∥ \frac{4 π r_{0}^{3}}{3} \\ + ∥ Ω (1) ∥ (\frac{π^{2} r_{0}^{3}}{9} + \frac{π r_{0}^{3}}{18}) \\ + ∥ Ω (2) ∥ r_{0}^{3} + ∥ Ω (3) ∥ \frac{13 π r_{0}^{3}}{12}) \\ {\times {(l m n)}^{- 1})}^{N}, \end{array}

(19)

\begin{array}{l} N \geq ln (1 - EDQ) \\ \times (ln [1 - ((‖ Ω (0) ‖ \frac{4 π r_{0}^{3}}{3} \\ + ‖ Ω (1) ‖ (\frac{π^{2} r_{0}^{3}}{9} + \frac{π r_{0}^{3}}{18}) \\ + ‖ Ω (2) ‖ r_{0}^{3} + ‖ Ω (3) ‖ \frac{13 π r_{0}^{3}}{12}) \\ {\times {(l m n)}^{- 1})])}^{- 1} . \end{array}

(20)

4. Redundancy Model Based Coverage-Enhancing Algorithm for 3D Underwater Sensor Networks

With the relationship of the number of underwater sensor nodes N and EDQ, we can deploy randomly a number of nodes more than the required number according to (19) and (20). The certain strategy can be used to adjust the working states and positions of some nodes in order to increase the lifetime and coverage rate of network. In this section, we propose a strategy based on redundancy of node. Each node firstly decides their working states according to redundancy. Then the working nodes use the virtual force algorithm to adjust their positions in the vertical direction.

4.1. Analysis on Node Redundancy

Definition 4.

Node redundancy ξ (i): to a random underwater sensor node $S_{i}$ , there is an overlap region of its sensing area and the sensing area of all its neighbouring nodes. The proportion of the overlap area to the sensing area of itself is called the redundancy of the node $S_{i}$ . $ξ (i)$ can be expressed as

\begin{matrix} ξ (i) = \frac{(⋃_{j \in ψ_{i}} S D_{j}) \cap S D_{i}}{S D_{i}} . \end{matrix}

(21)

To adjust the working states of nodes based on its redundancy, two problems should be solved. One is the criterion for determining whether a node is redundant, the other is how to schedule redundant node. This section is focused on the first problem and the other one will be discussed in the next section. One way to calculate the redundancy of node is using positioning devices to obtain location information. However, this approach is a huge burden for cost and energy consumption of networks. We build a probabilistic model. Node can calculate its redundancy based on the number of its neighbouring nodes using this probabilistic model. Then each node can determine whether it is a redundant node.

All nodes are randomly and uniformly deployed in monitored region Ω, so each node locates in a random point in Ω with probability $1 / ∥ Ω ∥$ . Given two underwater sensor nodes $S_{a}$ and $S_{b}$ , their maximum sensing radii are, respectively, marked as $r_{a}$ and $r_{b}$ . If there is overlap region in sensing area of $S_{a}$ and $S_{b}$ , $S_{b}$ needs to be located in the sphere where the center is $S_{a}$ and the radii is $r_{a} + r_{b}$ . If there is at least one point x in the sensing areas of $S_{a}$ and $S_{b}$ simulaneously, $S_{b}$ needs to be located in the sphere where the center is x and the radii is $r_{b}$ . If there is at least one point x in the sensing areas of $S_{a}$ and $S_{b}$ simultaneously, $S_{b}$ needs to be located in the sphere where centered x with radius $r_{b}$ . Therefore, the probability of that there is at least one point in the sensing areas of $S_{a}$ and $S_{b}$ simultaneously can be expressed as

\begin{matrix} p_{a b} = \frac{(4 / 3) π r_{b}^{3} \times 1 / ∥ Ω ∥}{(4 / 3) π {(r_{a} + r_{b})}^{3} \times 1 / ∥ Ω ∥} = \frac{r_{b}^{3}}{{(r_{a} + r_{b})}^{3}} . \end{matrix}

(22)

Sensing radii of $S_{a}$ and $S_{b}$ are normally distributed as $N (r_{0}, δ^{2})$ and $r_{0} \geq 3.3 δ$ , so the expected value of $p_{a b}$ can be expressed as

\begin{array}{l} E (p_{a b}) \\ = \frac{1}{2 π δ^{2}} \iint_{0}^{2 r_{0}} \frac{r_{b}^{3}}{{(r_{a} + r_{b})}^{3}} e^{- ({(r_{a} - r_{0})}^{2} + {(r_{b} - r_{0})}^{2}) / 2 δ^{2}} d r_{b} d r_{b} \\ = \frac{1}{4} - \frac{e^{- r_{0}}}{4} . \end{array}

(23)

The probability of event that there is overlap region in sensing area of $S_{a}$ and $S_{b}$ is denoted as $p_{a b}$ , so the opposite event that there is no overlap region in sensing area of $S_{a}$ and $S_{b}$ is denoted as $\bar{p_{a b}} = 1 - p_{a b}$ . If node $S_{a}$ has k neighbouring nodes, then the probability of a random point in sensing area of $S_{a}$ being covered by at least one of its k neighbouring nodes is denoted as $p_{a k}$ . So the probability of opposite event that any point in sensing area of $S_{a}$ not being covered by its k neighbouring nodes is denoted as $\bar{p_{a k}}$ . $\bar{p_{a k}}$ can be expressed as (24), so $p_{a k}$ can be expressed as (25)

\begin{matrix} \bar{p_{a k}} = {(\bar{p_{a b}})}^{k} = {(1 - p_{a b})}^{k}, \end{matrix}

(24)

\begin{matrix} p_{a k} = 1 - \bar{p_{a k}} = 1 - {(1 - p_{a b})}^{k} . \end{matrix}

(25)

Definition 5.

Redundant node: node $S_{i}$ is called redundant node in condition that its expected value of redundancy is greater than EDQ of network. It can be expressed as (26). Because when node $S_{i}$ satisfies (26), the proportion of overlap region in sensing area of $S_{i}$ to its neighbour nodes exceeds EDQ. If we let $S_{i}$ into sleep, the coverage rate of its original sensing area could also achieve EDQ:

\begin{matrix} E (ξ (i)) \geq EDQ . \end{matrix}

(26)

Based on the above analysis, we can know that node $S_{i}$ is redundant node when the number of neighbour nodes of $S_{i}$ satisfies

\begin{matrix} k \geq \frac{\ln (1 - EDQ)}{\ln (3 / 4 + (1 / 4) e^{- r_{0}})} . \end{matrix}

(27)

4.2. Node Scheduling Algorithm Based on Virtual Force

We have made a detailed analysis on virtual force of three-dimensional sensor networks in [18]. We will only illustrate some necessary concepts in this section. We point out in [18] that the coverage rate fluctuates significantly and nodes adjust location frequently in late stage of traditional coverage optimization algorithms. For these shortcomings, we improve the algorithm by using coverage impact factor and central computing nodes.

Definition 6.

Coverage impact factor: coverage impact factor $μ_{i}$ characterizes the impact on network coverage when the location of node $S_{i}$ is changed. We define it as follows. $C_{r}$ represents the current coverage rate. $C_{r}^{'}$ represents the coverage rate after changing the location of node $S_{i}$ . Consider

\begin{matrix} μ_{i} = {\begin{cases} 1, & C_{r}^{'} > C_{r} \\ 0, & C_{r}^{'} \leq C_{r} . \end{cases} \end{matrix}

(28)

We add some central computing nodes into the monitored region. All underwater sensor nodes should be within the communication ranges of central computing nodes. Underwater sensor nodes send their target location information to the nearest central computing node. The central computing nodes calculate the coverage impact factors of the nodes within their communication ranges once every slot time and send them to each underwater sensor node. Then each node decides whether to adjust its location based on the coverage impact factor. The number and positions of central computing nodes are determined according to the actual condition of application.

Node $S_{i}$ is under action of the repulsion of node $S_{j}$ which is defined in (29). $S_{i}$ is located at $S_{i}$ and $S_{j}$ is located at $S_{i}$ . $k$ represents the repulsion coefficient which is a positive constant. The resultant force of repulsion at $S_{i}$ is $\vec{F_{i}}$ . Consider

\begin{matrix} \vec{F_{i j}} = {\begin{cases} \frac{k}{{D_{i j}}^{2}} (\frac{S_{i} - S_{i}}{D_{i j}}), & D_{i j} < 2 r \\ 0, & D_{i j} \geq 2 r, \end{cases} \end{matrix}

(29)

\begin{matrix} \vec{F_{i}} = \sum_{S_{j} \in ψ_{i}} \vec{F_{i j}} . \end{matrix}

(30)

In UWSN, we can only adjust the length of cable between buoy node and underwater sensor node to change the location of underwater sensor nodes. The underwater sensor nodes can achieve coverage enhancement only by adjusting their location in the vertical direction. $\vec{F_{i}}$ and the moving distance of $S_{i}$ determine the target position of $S_{i}$ together. ${dis}_{\max}$ is denoted as the maximum single movement distance while the actual movement distance of the node dis_i satisfies (31). The nodes do not move at a fixed length in order to speed up the optimization. At the same time, we set a minimum single movement distance ${dis}_{\min}$ . When $di s_{i} < {dis}_{\min}$ , the virtual force suffered by $S_{i}$ reaches equilibrium and there is no need to adjust the location of $S_{i}$ any more. When all nodes in monitored region have reached equilibrium, we believe that the network has reached equilibrium and the algorithm would be terminated:

\begin{matrix} di s_{i} = \frac{∥ \vec{F_{i}} ∥}{∥ \vec{F_{i}} ∥ + 1} di s_{\max} . \end{matrix}

(31)

4.3. Algorithm Description

Based on the above analysis, to a given EDQ of 3D underwater sensor networks, we firstly calculate the minimum number of nodes N that need to be deployed according to (20). Then we randomly deploy more than N underwater sensor nodes in monitored region Ω. At this time, buoy nodes are randomly distributed on the surface area, and the length of cable between buoy nodes and underwater sensor nodes is random. After completion of the initial deployment, each node firstly collects the information of its neighbour nodes and determines whether it is a redundant node itself. If it is a redundant node, then the node will be set to sleep mode or does not change its working state. Then we use the virtual force algorithm to adjust the position of working nodes. After a round of adjustment, nodes (including those sleeping nodes) change their working states again according to the number of their neighbour nodes. Particularly, at this time we no longer use original EDQ as a factor to determine whether a node is redundant node in order to rapidly enhance the coverage rate of monitored area. We replace EDQ with coverage rate of monitored area as the judgment criteria. The nodes constantly circulate the above processes. Take node $S_{i}$ as an example; after completion of the initial deployment, RBCT algorithm is described as in Algorithm 1, where $A_{i}$ is the computing node nearest to underwater sensor node $S_{i}$ .

Algorithm 1

Input: information of $S_{i}$ and its neighbour nodes

Output: working state and final location information of $S_{i}$

(1) $t \leftarrow 0$ ; //initialization

(2) Set loop maximum $t_{\max}$ ;

(3) while ( $t < t_{\max}$ )

(4) Update current location information of $S_{i}$ ;

(5) Update the neighbour nodes set $ψ_{i}$ and the number k of $ψ_{i}$ ;

(6) Replay EDQ with current coverage rate of monitored area, and determine whether $S_{i}$ is a redundant node;

(7) if ( $S_{i}$ is a redundant node)

(8) Set $S_{i}$ into sleeping mode;

(9) else

(10) if ( $S_{i}$ is sleeping)

(11) Wake up $S_{i}$ ;

(12) $\vec{F_{i}} \leftarrow 0$ ;

(13) for ( $j = 0$ ; $j < k$ ; j++)

(14) Calculate the virtual repulsive force $\vec{F_{i j}}$ on node Si from $S_{j}$ ;

(15) $\vec{F_{i}} \leftarrow \vec{F_{i}} + \vec{F_{i j}}$ ;

(16) Calculate the moving distance $di s_{i}$ in the vertical direction and the target position $S_{i}^{'} (x^{'}, y^{'}, z^{'})$ of $S_{i}$ ;

(17) if $((di s_{i} > di s_{\min}) & & (S_{i}^{'} (x^{'}, y^{'}, z^{'}) \neq S_{i} (x, y, z)))$

(18) Send the target position $S_{i}^{'} (x^{'}, y^{'}, z^{'})$ of Si to its nearest computing node $A_{i}$ ;

(19) Wait to receive the coverage impact factor $μ_{i}$ from $A_{i}$ ;

(20) if ( $μ_{i} = 1$ )

(21) Move $S_{i}$ to the target position;

(22) else

(23) sleep( $Δ t$ );

(24) $t \leftarrow t + 1$ ;

(25) end;

RBCT algorithm is running on $A_{i}$ as in Algorithm 2.

Algorithm 2

Input: current location and target location information of all nodes within the communication range of $A_{i}$ ;

Output: coverage impact factor

(1) Get the initial location information of all nodes within communication range;

(2) Calculate the initial coverage rate $C_{r}$ of monitored region $Ω$ ;

(3) while (1)

(4) Update $C_{r}$ ;

(5) Receive target location information of all nodes within the communication range. We use node $S_{i}$ as an example;

(6) Calculate the coverage rate $C_{r}^{'}$ of monitored region $Ω$ after $S_{i}$ moving to target location;

(7) Calculate the coverage impact factor of $S_{i}$ ;

(8) Send the coverage impact factor $μ_{i}$ to $S_{i}$ ;

(9) sleep( $Δ t$ );

(10) end;

5. Algorithm Simulations and Performance Analysis

In this section, we firstly analyze the convergence of RBCT algorithm. Secondly, we use a specific case to illustrate the coverage enhancement effect to a three-dimensional sensor network. Finally, we compare RBCT algorithm with other similar algorithms by different values of key parameters. Specific values of parameters are shown in Table 1.

Table 1

Experiment parameters.

Target region	$30000 * 30000 * 30000$ m³
Distribution mode	Randomly distributed
Number of underwater sensor nodes N	200–500
Average maximum sensory radius $r_{0}$	2–3.5 km
Maximum single movement distance $di s_{\max}$	1–4 km
Factor of virtual repulsive force k	10
Expected deployment quality EDQ	0.4–0.8

5.1. Algorithm Convergence Analysis

We carry out a group of experiments with five kinds of EDQ so as to analyze RBCT algorithm convergence. To a given EDQ, we can calculate the number of nodes that need to be deployed through (20). According to every EDQ, we randomly produce 20 topological structures, respectively, and calculate the algorithm convergence times and average. Experimental data is shown in Table 2 with parameters $r_{0} = 3 km$ and ${dis}_{\max} = 3 km$ .

Table 2

Convergence analysis on experimental data.

EDQ	Number of nodes N	Initial coverage rate%	Ultimate coverage rate%	The number of loops
0.4	131	39.4	50.3	23.5
0.5	182	48.7	65.2	22.7
0.6	237	58.5	76.3	25.6
0.7	309	68.9	86.1	25.3
0.8	407	79.2	92.8	26.1

Based on the above analysis we can reach a conclusion that the convergence of RBCT algorithm, that is, the adjustment number of times, does not change conspicuously along with EDQ or N. The value ranges from 22 to 27; thus, RBCT algorithm can improve the coverage of monitored region in a short time and has a nice convergence.

5.2. Case Study

Figure 5 records the coverage curves of monitored region in experiments of algorithm convergence analysis. Figure 5 shows that due to the influence of RBCT algorithm, coverage rate is constantly improving. When the network reaches a steady state, coverage rates remain unchanged and RBCT algorithm ends. The coverage rates do not present a fluctuating state during the execution of RBCT algorithm since the introduction of coverage impact factor. By RBCT algorithm, the coverage rates are raised to 50.3%, 65.2%, 76.3%, 86.1%, and 92.8% without changing the number of initial nodes. We can know through (20) that at least 185, 272, 367, 498, and 661 nodes are separately needed to achieve thus coverage rate by the way of random deployment. It means that we have saved 54, 90, 130, 189, and 254 nodes, respectively. From this set of data we can see that the higher the EDQ, the larger the number of nodes that can be saved by RBCT algorithm. RBCT algorithm greatly reduces the cost and complexity of network.

Figure 5

Coverage curves in different scale of nodes.

In order to intuitively view the coverage condition of monitored region, we draw it graphically as shown in Figure 6. We take one random topology as study case when the number of nodes is 407. Figure 6 shows the projection of monitored region in the vertical direction. The initial coverage rate is basically consistent with EDQ and from Figure 6(a) we can see that overlap region and fade zone are significant in network for the randomness of deployment. By means of RBCT algorithm, redundant nodes change into sleeping mode, and then working nodes adjust their locations in the vertical direction. Proportion of fade zone is constantly reducing when RBCT algorithm is running. Finally, we reach the purpose of covering the maximum monitored region with minimal number of nodes, which is shown in Figure 6(c).

Figure 6

Coverage optimization under RBCT algorithm when $N = 407$ .

We carry out a group of experiments as the following to prove that RBCT algorithm can reduce the energy consumption of networks. We assume that the initial energy of each underwater sensor node is 100. If one node is in working state and does not need to adjust the position, then the energy consumption of this node is 1 within one time step. If one node is in sleeping state, then the energy consumption of this node is 0. The energy consumption of every position adjustment is 1. When the energy of a node is reduced to 0, the status of this node is marked as dead. If more than 10% of all nodes are marked as dead, we identify the network is paralyzed. We record the time from initial deployment of the nodes to the paralysis of network as the lifetime of network. We randomly produce 30 topological structures with $EDQ = 0.6$ . 10 of them execute RBCT algorithm and 10 of them execute PCPE algorithm proposed in [19]. We, respectively, record the lifetime of networks and average. Experimental results are shown in Figure 7. As shown in Figure 7, the lifetime of networks without optimization is longer than the other two, since the nodes only consume energy in communications without changing locations. RBCT algorithm reduces the lifetime of networks, but still better than the effect of PCPE algorithm. Coverage optimization algorithms improve the coverage rate of monitored region while reducing the lifetime of networks. The final coverage rates of monitored region are shown in Figure 8. We can see from Figure 8 that RBCT algorithm has the best effect on coverage rate of monitored region. Thus, RBCT algorithm improves the coverage rate with reducing the lifetime of networks for the price.

Figure 7

Effect on lifetime with different optimizations.

Figure 8

Effect on coverage rate with different optimizations.

5.3. Comparative Analysis of Algorithms

In this section, a series of simulation experiments are conducted to illustrate the effect on the performance of RBCT algorithm from the three key parameters. They are expected deployment quality of monitored region EDQ, average maximum sensory radius $r_{0}$ , and maximum single movement distance ${dis}_{\max}$ . We take PCPE algorithm and PFCEA algorithm proposed in [19, 20] as comparison algorithms. We compare RBCT algorithm to them and analyze their performances. We take a number of simulations for each set of parameters and record experimental data, respectively.

As shown in Figure 9, we conduct the simulation experiments with different EDQ. Other experimental parameters satisfy that $r_{0} = 3 km$ and ${dis}_{\max} = 3 km$ . In the simulation experiments of Figure 10, we use $r_{0}$ as variable parameter and other experimental parameters satisfy that $N = 300$ and ${dis}_{\max} = 3 km$ . We can see from the curves in Figures 9 and 10 that the effect on coverage rate from EDQ is similar to $r_{0}$ . It is because the greater the value of EDQ is, the larger the number of nodes in the initial deployment is. The shorter the $r_{0}$ is, the smaller the coverage area of a single node is. When ${dis}_{\max}$ is fixed, smaller value of EDQ and $r_{0}$ leads to smaller initial coverage rate. As the EDQ and $r_{0}$ increase, the value of ΔC _r and initial coverage rate increase together. However, when the value of variable parameters exceeds a certain limitation, the growth trend of ΔC _r and initial coverage rate will slow down. The reason is that the increase of EDQ and $r_{0}$ leads to a higher initial coverage rate and greatly decreases the probability that several communicational adjacent nodes form coverage fade zone which undoubtedly weakens the performance of RBCT algorithm.

Figure 9

Convergent curves with different EDQ.

Figure 10

Convergent curves with different $r_{0}$ .

As shown in Figures 11 and 12, we conduct the simulation experiments with different ${dis}_{\max}$ . Other experimental parameters satisfy that $N = 300$ and $r_{0} = 3 km$ . The experiment result shows that the greater the value of ${dis}_{\max}$ is, the smaller the value of $Δ C_{r}$ is. It should be noted that different ${dis}_{\max}$ will have a significant impact on the number of loops. As shown in Figure 12, in a certain range the smaller the value of ${dis}_{\max}$ is, the bigger the number of loops will be. In particular when the value of ${dis}_{\max}$ is less than 2 km, the algorithm loops increased dramatically, while the increase of network coverage optimization effect is not obvious. Thus, we should select an appropriate ${dis}_{\max}$ in practical applications to avoid slow convergence rate and a large number of nodes’ energy consumption.

Figure 11

Convergent curves with different ${dis}_{\max}$ .

Figure 12

Relationship between the number of loops and ${dis}_{\max}$ .

As can be seen from Figures 9 to 12 compared to PCPE algorithm and PFCEA algorithm, with the same parameter value, the proposed RBCT algorithm increases the coverage quality the most significant after the optimization of the initial deployment, which illustrates the superiority of this algorithm.

6. Conclusion

This paper derives the relationship between the number of nodes and the coverage quality of 3D underwater sensor network using mathematical analysis and proposes RBCT algorithm based on the redundancy model of nodes to improve the coverage of monitored region and prolong the lifetime of network. The coverage impact factor is introduced to reduce profitless movement and further improve coverage optimization. In simulation experiments, we firstly verify the convergence of the algorithm and then the effect on the algorithm from the key parameters and validity of RBCT are demonstrated by the comparisons among RBCT, PCPE, and PFCEA. The proposed algorithm effectively improves the coverage performance of network but many issues in this paper could be improved. We can see from the simulation experiments that the actual initial coverage rate of monitored region is still slightly lower than EDQ. It shows that the theoretical analysis of this paper could be improved which is for further study.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

The subject is sponsored by the National Natural Science Foundation of China (no. 61171053), Scientific & Technological Support Project (Industry) of Jiangsu Province (no. BE2012183), Natural Science Key Fund for Colleges and Universities in Jiangsu Province (11KJA520001, 12KJA520002), Science & Technology Innovation Fund for Higher Education Institutions of Jiangsu Province (CXZZ11-0409), Doctoral Fund of Ministry of Education of China (20113223110002), and the Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions (no. yx002001).

References

Heidemann

Stojanovic

Zorzi

Underwater sensor networks: Applications, advances and challenges

Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 2012 370 1958 158 175

2-s2.0-84855482959

10.1098/rsta.2011.0214

Amac Guvensan

Gokhan Yavuz

On coverage issues in directional sensor networks: a survey

Ad Hoc Networks 2011 9 7 1238 1255

2-s2.0-79958163700

10.1016/j.adhoc.2011.02.003

Pandey

Pompili

Distributed computing framework for underwater acoustic sensor networks

Proceedings of the IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS '13)

2013

318 320

Deshpande

Khuller

Malekian

Energy efficient monitoring in sensor networks

LATIN, 2008: Theoretical Informatics 2008

Berlin, Germany

Springer

436 448

Linfeng

A deployment algorithm for underwater sensor networks in ocean environment

Journal of Circuits, Systems and Computers 2011 20 6 1051 1066

2-s2.0-80155153046

10.1142/S021812661100775X

Junjie

Lijuan

Ruchuan

Improved virtual potential field algorithm based on probability model in three-dimensional directional sensor networks

International Journal of Distributed Sensor Networks 2012 21 6 45 53

Golen

E. F.

Mishra

Shenoy

An underwater sensor allocation scheme for a range dependent environment

Computer Networks 2010 54 3 404 415

2-s2.0-75949105882

10.1016/j.comnet.2009.09.016

Gharaibeh

K. M.

Yaqot

Target classification in wireless sensor network using particle swarm optimization (PSO)

Proceedings of the IEEE Sensors Applications Symposium (SAS '12)

February 2012

146 150

2-s2.0-84859046695

10.1109/SAS.2012.6166290

Tezcan

Cayirci

Coskun

A distributed scheme for 3D space coverage in tactical underwater sensor networks

Proceedings of the IEEE Military Communications Conference (MILCOM '04)

November 2004

697 703

2-s2.0-27744452344

10.

Akyildiz

I. F.

Pompili

Melodia

Underwater acoustic sensor networks: research challenges

Ad Hoc Networks 2005 3 3 257 279

2-s2.0-13944252629

10.1016/j.adhoc.2005.01.004

11.

Heidemann

Wills

Syed

Research challenges and applications for underwater sensor networking

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '06)

April 2006

228 235

2-s2.0-34250365027

12.

Zou

Zhao

Chen

A high-linearity energy-efficient CMOS PA for wireless environment monitoring

Proceedings of the IEEE 4th International Conference on Digital Manufacturing and Automation (ICDMA '13)

2013

32 35

13.

Cardei

Energy-efficient coverage problems in wireless ad-hoc sensor networks

Computer Communications 2006 29 4 413 420

2-s2.0-32644446747

10.1016/j.comcom.2004.12.025

14.

Bai

Zhang

Xuan

Jia

Full-coverage and k-connectivity (k =14, 6) three dimensional networks

Proceedings of the 28th IEEE Conference on Computer Communications (INFOCOM '09)

April 2009

388 396

2-s2.0-70349659608

10.1109/INFCOM.2009.5061943

15.

Alam

S. M.

Haas

Z. J.

Coverage and connectivity in three-dimensional networks

Proceedings of the 12th Annual International Conference on Mobile Computing and Networking (MOBICOM '06)

September 2006

ACM

346 357

2-s2.0-33751061514

16.

Alam

S. M. N.

Haas

Z. J.

Coverage and connectivity in three-dimensional underwater sensor networks

Wireless Communications and Mobile Computing 2008 8 8 995 1009

2-s2.0-54949134122

10.1002/wcm.661

17.

Akkaya

Newell

Self-deployment of sensors for maximized coverage in underwater acoustic sensor networks

Computer Communications 2009 32 7 1233 1244

2-s2.0-65649114733

10.1016/j.comcom.2009.04.002

18.

Huang

J.-J.

Sun

L.-J.

Wang

R.-C.

Huang

H.-P.

Virtual potential field and covering factor based coverage-enhancing algorithm for three-dimensional wireless sensor networks

Journal on Communications 2010 31 9 16 21

2-s2.0-78149490662

19.

Sheu

J.-P.

Lin

H.-F.

Probabilistic coverage preserving protocol with energy efficiency in wireless sensor networks

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '07)

March 2007

2633 2638

2-s2.0-36348967336

10.1109/WCNC.2007.489

20.

Tao

H.-D.

Liu

Virtual potential field based coverage-enhancing algorithm for directional sensor networks

Journal of Software 2007 18 5 1152 1163

2-s2.0-34347213027

10.1360/jos181152