Sage Journals: Discover world-class research

Abstract

The underwater wireless sensor networks composed of sensor nodes are deployed underwater for monitoring and gathering submarine data. Since the underwater environment is usually unpredictable, making the nodes move or be damaged easily, such that there are several vital objectives in the data forwarding issue, such as the delivery success rate, the error rate, and the energy consumption. To this end, we propose a data forwarding algorithm based on Markov thought, which logically transforms the underwater three-dimensional deployment model into a two-dimensional model, and thus the nodes are considered to be hierarchically deployed. The data delivery is then achieved through a “bottom to top” forwarding mode, where the delivery success rate is improved and the energy consumption is reduced because the established paths are more stable, and the proposed algorithm is self-adaptive to the dynamic routing loads.

Keywords

Data forwarding algorithm Markov model logical layering underwater wireless sensor networks load balancing

Introduction

With the rapid developments of sensor communications, the underwater sensor network technology has been paid more attention worldwide,¹ especially in China, which has a sea area larger than 3 million km², and thus underwater sensor network technology should be studied for various underwater applications, such as the submarine resource explorations and hydrological observations.

Underwater sensor nodes are usually deployed in a three-dimensional (3D) underwater space in a self-organized way.² The electromagnetic wave is not suitable for underwater communications, and thus the acoustic wave becomes the physical layer technology in underwater wireless sensor networks (UWSNs).³ As shown in Figure 1, there are two types of UWSN nodes: sensor nodes and the sink node.^4,5 The sink node floating on the water surface is responsible for collecting the sensed data which is forwarded from the bottom layer to the top layer hop by hop, and the data forwarding in UWSN can be mapped into a Markov process in this article. We propose the DFMT (Data Routing Algorithm based on Markov Model) which improves the delivery success rate and energy consumption. DFMT applies the Markov thought to establish a layered model, under which the data forwarding process can be efficiently controlled. The remainder of this article is organized as follows: in section “Related work,” related works are introduced; in section “DFMT forwarding model,” the logical layered model, the computation of forwarding probability, and load balancing mechanism are given; section “DFMT algorithm” describes the detailed steps of the DFMT algorithm and provides some mathematical analysis; and in section “Simulations,” the performance of the DFMT algorithm is proved by simulations.

Figure 1.

Model of an underwater sensor network.

Related work

Nowadays, many routing protocols have been proposed for sensor networks;^6–10 however, most of these routing protocols have not paid enough attention to some underwater issues such as the high error rate, node mobility, and node failure. Due to the influence of the underwater environmental factors, it is difficult to obtain the global topology for routings¹¹ and replenish underwater nodes with energy. Such that, how to improve the energy efficiency is an important issue in the routings.¹² Moreover, the 3D deployment should be considered in UWSNs, which makes the routing differs from the terrestrial ones.¹³

UWSN routing protocol also has been extensively studied,¹⁴ where a routing based on the node locations and the energy consumption of forwarding packets is proposed to ensure the delivery success rate, and the feedback information is exploited to monitor the network shallow as well. Tariq et al.¹⁵ propose a pressure sensor–based reliable (PSBR) routing protocol that introduces the fuzzy link-quality estimator (F-LQE) to utilize the reliable wireless links. To adapt to different node densities, an underwater sensor algorithm is presented¹⁶ based on the shortest-path-first principle, using nodes around the sink node to determine the forwarding node with some optimal conditions. Similarly, Zhang et al.¹⁷ propose an efficient wireless Routing protocol Based on Forward-cluster Forward gateway (FFBR), which provides the mechanisms of dynamic cluster election and reorganization, and FFBR can reduce the energy consumption of nodes and prolong the network lifetime.

Due to the higher error rate in underwater transmissions, the data delivery success rate should be improved through the maintenance and update of the established routing. Pompili et al.¹⁸ propose an algorithm based on the delay-insensitive and delay-sensitive applications, where each node selects its next-hop node according to the overhead, so that the effects of topology variations on the additional energy consumption can be reduced and the transmission efficiency can also be enhanced. Meanwhile, in order to ensure the stability, this algorithm is implemented through multiple packet switching, and thus a longer executed time is required. Accordingly, a depth-based routing (DBR)¹⁹ is proposed, and DBR selects the next-hop forwarding nodes according to the depth information of the last-hop node. However, DBR does not take into account the influence of the underwater environments. Furthermore, Ashrafuddin et al.²⁰ have carried out more considerations and improvements, and they have put forward an energy efficiency routing algorithm, where the residual energy of nodes, depth difference, and distance are applied to figure out a fitness value for the determinations. Nevertheless, the energy consumption is still unbearable due to the numerous interactions among nodes. Jafri et al.²² propose a threshold-optimized DBR protocol, where a weight is calculated based on depth and residual energy. The weight is taken as a reference for data forwarding.

The Markov thought has been applied into protocol designs of sensor networks or opportunistic networks, such as Tang et al.²¹ propose a multi-sensor fault detection method and detection mechanism based on a Markov model to predict the network faults through establishing a state transition matrix. Zou and Zhang²³ put forward a mobile node location prediction algorithm based on the multi-order Markov prediction model, which predicts the location information to collect the data and improves the dynamic network. As the continuous-time Markov framework introduced in Li et al.,²⁴ the data forwarding process is modeled and optimized, along with the constraint of energy consumption. In this article, a logical layered model is designed, and the data forwarding at different layers are mapped into several Markov states. Thus, the forwarding loads are expected to be reduced while delivery success rate is also ensured. Note that this article is an extended version of our conference paper titled “A Data Routing Algorithm Based on Markov Model in Underwater Wireless Sensor Networks,”²⁵ which has been accepted to be present at ICUWB 2016 (The 2016 IEEE International Conference on Ubiquitous Wireless Broadband). Compared with the ICUWB paper, the article has been improved significantly. In terms of original model, data packet format, algorithm steps, mathematical analysis, and simulations, this article is with great changes: first, the process description regarding the original model is provided with more details and analysis; second, the format of the data packets is defined, and how to apply the Markov thought into this research is deeply explained more specifically; third, we give more analysis for DFMT, such as the algorithm complexity and mathematical expectation; moreover, more related works have been introduced and analyzed for a more comprehensive review.

DFMT forwarding model

With regard to the Markov model, the future states depend on the current states rather than the past ones.

In DFMT, the state denotes the sequence number of layers, that is, the states are determined based on the depths. According to this model, a node decides on whether to forward a data packet on the basis of its current depth (current state). The data packet will be forwarded from the bottom to the top over time, and thus the past states (or futures states) indicate the higher depths (or lower depths) the data packets having been (or will be) forwarded to.

Logical layered model

In DFMT, the Markov state can be regarded as an association of the highest depth of all data forwarders. As shown in Figure 2, A to E are underwater sensor nodes, and J represents the sink node. The underwater space is layered logically based on the depth 2d, where d is obtained from equation (1)

d = ε \cdot \bar{H}

(1)

$\bar{H}$ denotes the average depth of deployed nodes in the space, and the value of $ε$ falls into the interval (0,1]. $\bar{H}$ is calculated as

\bar{H} = \frac{\sum_{i = 1}^{n} h_{i}}{n}

(2)

where the depth of each node is denoted as h₁, h₂, …, h_n. To simplify the analysis, the 3D model is first mapped into a two-dimensional (2D) model. As illustrated in Figure 2, the node A’s 3D coordinate and 2D coordinate are (x_A, y_A, z_A) and (x_A, z_A), respectively, indicating that the Y-axis coordinate is neglected in 2D coordinates. Then, the space is divided into some logical layers at the Z-axis. Taking the lth layer as an example to describe the logical layering process, as shown in Figure 3(a), the neighboring nodes of the lth layer in the ambient range d are C, D, E, F, implying that these nodes fall into the lth layer.

Figure 2.

A 3D model of underwater sensor network deployment.

Figure 3.

Logical layer divisions: (a) lth layer and (b) logical divisions.

The 2D coordinate of node C is marked as (x_C, y_C), and the lth layer coordinate in the depth direction is denoted as $y_{l} = ⌊ \frac{y_{C}}{2 d} ⌋$ , then the coordinate of the partitioned C is rewritten as (x_C, y_l). The 3D model of Figure 2 is divided according to the logical layer divisions, and the example division result is given in Figure 3(b).

The Markov chain {X_n, n ≥ 0} state space is defined as I = {A, B, C, D, E, F, G, H, J}, and n = 3, hence for X₁ = C, its past forwarding node X₀ belongs to the set I ₀ = {A, B} and its futures forwarding node X₂ belongs to the set I ₂ = {G, H}. Obviously, P{X₂ = i₂| X₁ = i₁, X₀ = i₀} = P{X₂ = i₂| X₁ = i₁}, i₀ ∈ I ₀, i₁ ∈ I ₁, i₂ ∈ I ₂. Thus, the following formula can be obtained

\begin{matrix} P {X_{n} = i_{n} | X_{1} = i_{1}, X_{2} = i_{2}, \dots, {X_{n}}_{- 1} = {i_{n}}_{- 1}} \\ = P {X_{n} = i_{n} | {X_{n}}_{- 1} = {i_{n}}_{- 1}}, i_{0} \in I_{0}, i_{1} \in I_{1}, \dots, i_{n} \in I_{n} \end{matrix}

(3)

where indicates a node will forward data to the nodes in its upper layers. Here is a case worth discussing, when logical layering has been finished, some nodes in upper layer may move to the location below the node due to mobility, which leads to data forwards to downward layer. The problem can be improved through reducing cycle time of logical layering, but energy consumption will undoubtedly increase greatly. In this article, therefore, the low probability event above is ignored.

Remarkably, the transfer from 3D model to 2D model is only logical; in other words, 2D model does not change actual deployment structure. To better apply the layered approach, such a transmission is proposed for forwarding based on Markov thought, where entire forwarding process can be controlled reasonably and performance can be enhanced. Accordingly, the mentioned transfer is rational and correct.

Forwarding probability

In the logical layered model, the data packet is forwarded from the bottom to the top according to levels of logical layers, and the optimal forwarding node is determined based on a forwarding priority, that is deduced from a calculated forwarding probability P_ij(n_t) as follows.

Definition 1

The conditional probability P_ij(n_t) =P{X_n_+ 1 = j|·X_n = i} is regarded as one-step transition probability of Markov chain at the time n_t. n_t belongs to the set {0, 1, …, n}, which indicates the transition probability is updated each time interval t.

The initial value of n_t is set 0 and is increased by 1 at each time interval t.

Definition 2

For any i, j∈ I , if P_ij(n_t) is irrelevant to the value of n_t, the Markov chain is a homogeneous Markov chain.

Therefore, the variations of the transition probabilities over time will be ignored and the transition probability is marked as P_ij.

Definition 3

The matrix P is composed of elements P_ij, which is considered as one-step probability matrix of Markov chain

P = [\begin{matrix} P_{11} & P_{12} & \dots \dots \\ P_{21} & P_{22} & \dots \dots \\ \dots \dots & \dots \dots & \dots \dots \end{matrix} \begin{matrix} P_{1 n} \\ P_{2 n} \\ \dots \dots \end{matrix}], {\begin{matrix} P_{ij} \geq 0, i, j \in I (4) \\ \sum_{j \in I} P_{ij} = 1, i \in I (5) \end{matrix}

The formula (5) represents the sum of probabilities that each node forwards to the upper layers is equal to 1.

If nodes are not adjacent, then P_ij is set 0. The nodes’ prior forwarding sequences can be obtained by P . At the end of each time interval, each node needs to update the prior forwarding sequence, that is, P will be updated at each time interval. The aforementioned forwarding probability is generated based on the distance between nodes. For example, in Figure 3(b), node C belongs to the second logical layer, and its forwarding sequence is expressed as I₂ = {G, H}.

Suppose L₁, L₂ are the distance from C to H and G, respectively, then we can get $P_{ch} = L_{2} / (L_{1} + L_{2})$ and $P_{cg} = L_{1} / (L_{1} + L_{2})$ . Thus, the forwarding probability P_ij is calculated as follows

P_{ij} = \frac{L^{(ij)}}{\sum_{j = 0}^{n^{(i)}} L_{j}}

(6)

where L^(ij) is acquired through the distance weight between nodes i, j, and a shorter distance gives rise to a higher weight. n⁽ⁱ⁾ is the number of nodes in the upper layer of node i. According to the generated forwarding probabilities, a one-step transition probability matrix P is constructed, and thus the prior forwarding sequence of node is also constituted. The data packets will be forwarded to the nodes with higher forwarding probabilities.

Load balancing

Load balancing is an important approach to reduce the energy consumption of nodes. Especially when the network scale is very large, some nodes may undertake heavy forwarding tasks, yet some other nodes seldom forward the received data packets, which will cause the unbalanced distribution of forwarding loads. Besides, in the logical layered model, the overload of all nodes in the forwarding sequence may lead to the network congestion as well.

Case I

In the case of unbalanced forwarding, the average load $\bar{s}$ of nodes in unit time interval is expressed as

\bar{S} = \frac{\sum_{k = j}^{j + N} T_{k}^{f}}{N \cdot E_{k}^{f}}

(7)

where $T_{k}^{f}$ represents the number of forwarded data packets in time interval k, $E_{k}^{f}$ represents the residual energy of the node at the time interval k, and N is the number of cycles that is required for the load prediction. $\bar{S}$ is related to the number of the forwarded data packets and the residual energy, which can be applied to predict whether the node has been overloaded. The load balancing process is described as follows: first, ${\bar{S}}_{\max}$ is set according to the configuration of nodes, when the forwarding node’s average load is larger than ${\bar{S}}_{\max}$ in the continuous N time intervals, and the forwarding node will send signal to the downward layer nodes. Suppose one node has been selected as the optimal forwarding node, it sends a response packet to nodes in last layer and then selects the optimal forwarding probability from these nodes. After that, the forwarding nodes will send the data packet to the node owning the smallest forwarding probability and then the node records the forwarding nodes in optimal forwarding sequence after receiving the data packet.

For example, in Figure 3(a), if node A owns the lowest forwarding probability, and the forwarding sequence of A is {C, F, D, E}, hence the optimal forwarding node of the sequence is C. If the average load of node C exceeds ${\bar{S}}_{\max}$ during N time intervals, then the forwarding sequence is re-marked as {C*, F, D, E} (C* indicates that C has been marked). Afterward, the node F will be elected as the next optimal forwarding node.

Case II

With regard to the case of network congestion, the problem can be solved if nodes can forward data packets to the adjacent area. As illustrated in Figure 4, assuming the communication distance between nodes is R. When node C’s forwarding sequence are all marked in region a and then node C has to forward the data packets to region b. Obviously, node C is unable to forward the data packet to the region b directly, so the data packet must be forwarded in an iterative way with the assistance of adjacent nodes deployed in the same layer. Assume that all nodes are on the same layer in the region a. Node E and node D are located in node C’s communication range. The forwarding node of node C is selected through the distance estimation as $\sqrt{{(x_{1} - x_{3})}^{2} - {(y_{1} - y_{3})}^{2}} > \sqrt{{(x_{2} - x_{3})}^{2} - {(y_{2} - y_{3})}^{2}}$ . Thus, node E is selected as the forwarding node. The above processes are repeated until the data packets are forwarded to the node H in the area b.

Figure 4.

Forwarding a data packet to adjacent region.

DFMT algorithm

In this part, we will explain the algorithm in detail. The flow chart of the algorithm is shown in Figure 5.

Figure 5.

Flow chart of DFMT algorithms.

Algorithm steps

Step 1. Assume that the coordinates of nodes are known, and then the nodes are sorted into logical layers. Each node broadcasts the data packets, which consist of the node ID (ID), the node layer (Layer), the amount of forwarding data packets at unit time interval (Transmission), the node’s residual energy (Energy), and the prior forwarding sequence (Priority), as shown in Figure 6.

Figure 6.

Data packet structure.

The prior forwarding sequence can be obtained in the step 2. The nodes update their layers and the prior forwarding sequences at the end of each time interval.

Step 2. Each node obtains a forwarding probability sequence including some upper nodes.

Step 3. When a node forwards data packets, it needs to query its optimal forwarding sequence to determine the optimal forwarding node. The forwarding process is repeated until the data are received by the sink node.

Due to the limited node energy, it is significant to constantly balance the energy consumption among nodes, and thus the network lifetime can be prolonged. The article adopts the load balancing method to avoid the excessive energy consumption on nodes. In the forwarding process, the current node’s prior forwarding sequence is considered independently, which tallies with the Markov thought.

Time complexity

The logical layer divisions need to traverse all nodes, so the time complexity reaches O(n). To compute the forwarding probabilities, the distance between nodes in the adjacent layers is first calculated, which is a twice loop and its time complexity is O(n²). Then, each node should generate a prior forwarding sequence, which can be obtained after this loop. However, the priority sequence should be sorted, so the time complexity is O(n³). Therefore, the time complexity of DFMT is O(n³).

Mathematical expectation analysis

Suppose the 2D coordinates of nodes obey the normal distribution: $X ~ N (μ_{1}, σ_{1}^{2})$ , $Y ~ N (μ_{2}, σ_{2}^{2})$ . Without loss of generality, X-axis is taken as example analysis, some nodes will be chosen if its coordinate falls into the range $[\bar{X} - \frac{S_{1}}{\sqrt{n}} t_{\frac{α}{2}}, \bar{X} + \frac{S_{1}}{\sqrt{n}} t_{\frac{α}{2}}]$ , which is derived from t distribution. S₁ is the unbiased estimation of variance σ₁, n represents the size of the sample space, and $\bar{X}$ is the average value of sample in the X-axis. Finally, the sensor node (x_i, y_i) is selected and y is the depth direction transformed from Z-axis in 3D model. Table 1 gives the mathematical expectation of parameters.

Table 1.

Parameter description.

Parameter	Description	Parameter	Description
$N (μ_{1}, σ_{1}^{2})$	Distribution of X value	$N (μ_{2}, σ_{2}^{2})$	Distribution of Y value
S	Unbiased estimate of variance	n	Size of sample space
$\bar{X}$	Average value of the sample in the x-axis	$\bar{Y}$	Average value of the sample in the y-axis
$\tilde{d}$	The value of d in the logical layered model	d_i	Transmission distance of the node i to the sink node
t_d	The forwarding delay	s_d	Underwater transmission rate of the data packet
e_t	Average transmission consumption of node	d_n	Transmission delay of the node
$\tilde{t}$	Forwarding probability between adjacent layers	sp	Delivery success rate of the node
${\bar{x}}_{i}$	The average value of the sample in the range $[\bar{X} - \frac{S_{1}}{\sqrt{n}} t_{\frac{α}{2}}, \bar{X} + \frac{S_{1}}{\sqrt{n}} t_{\frac{α}{2}}]$ in X-axis	${\bar{y}}_{i}$	The average value of the sample in the range $[\bar{Y} - \frac{S_{2}}{\sqrt{n}} t_{\frac{α}{2}}, \bar{Y} + \frac{S_{2}}{\sqrt{n}} t_{\frac{α}{2}}]$ in Y-axis
$\tilde{e}$	Transmission consumption in adjacent layer

The average transmission energy consumption e_t of the node is

e_{t} = \tilde{e} \cdot ⌈ \frac{y_{i}}{2 \tilde{d}} ⌉

(8)

Approximately, $⌈ \frac{y_{i}}{2 \tilde{d}} ⌉ \approx y_{i} / 2 \tilde{d}$ , so the energy consumption of each node is expressed as

E (e_{t}) = E (\frac{\tilde{e} \cdot y_{i}}{2 \tilde{d}}) = \frac{\tilde{e}}{2 \tilde{d}} E (y_{i}) = \frac{\tilde{e}}{2 \tilde{d}} \cdot \bar{y_{i}}

(9)

Formula (9) shows that the energy consumption of the node is related to the space size and the forwarding energy consumption. The transmission delay of the node d_n is

d_{n} = t_{d} \cdot ⌈ \frac{y_{i}}{2 \tilde{d}} ⌉ + D_{i} \cdot s_{d}

(10)

Thus, the mathematical expectation of the transmission delay can be obtained

\begin{matrix} E (d_{n}) = E (t_{d} \cdot ⌈ \frac{y_{i}}{2 \tilde{d}} ⌉ + D_{i} \cdot s_{d}) = E (t_{d} \cdot \frac{y_{i}}{2 \tilde{d}} + D_{i} \cdot s_{d}) \\ = \frac{t_{d}}{2 \tilde{d}} \cdot E (y_{i}) + D_{i} \cdot s_{d} = \frac{t_{d}}{2 \tilde{d}} \cdot \bar{y_{i}} + D_{i} \cdot s_{d} \end{matrix}

(11)

which indicates that the transmission delay is mainly influenced by the transmission distance and is proportional to the transmission distance. Furthermore, if the space size is enlarged, the transmission delay will grow. The forwarding probability between adjacent layers is denoted as $\tilde{t}$ , then the delivery success rate sp of the node is

sp = {(\tilde{t})}^{⌈ \frac{y_{i}}{2 \tilde{d}} ⌉}

(12)

To simplify the expression, let $u_{2} = \bar{Y} - \frac{S_{2}}{\sqrt{n}} t_{\frac{α}{2}}$ , $u_{1} = \bar{Y} + \frac{S_{2}}{\sqrt{n}} t_{\frac{α}{2}}$ , and thus the mathematical expectation of the delivery success rate is expressed as

\begin{matrix} E (sp) = E ({\tilde{t}}^{⌈ \frac{y_{i}}{2 \tilde{d}} ⌉}) = \int_{u_{2}}^{u_{1}} {\tilde{t}}^{\frac{y_{i}}{2 \tilde{d}}} \cdot \frac{1}{\sqrt{2 π} σ_{2}} e^{- \frac{{(y_{i} - μ_{2})}^{2}}{2 σ_{2}}} d y_{i} \\ = \frac{1}{\sqrt{2 π} σ_{2}} \int_{u_{2}}^{u_{1}} {\tilde{t}}^{\frac{y_{i}}{2 \tilde{d}}} \cdot e^{- \frac{{(y_{i} - μ_{2})}^{2}}{2 σ_{2}}} d y_{i} \\ = \int_{u_{2}}^{u_{1}} \frac{1}{\sqrt{2 π} σ_{2}} e^{\frac{y_{i}}{2 \tilde{d}} \ln \tilde{t} - \frac{{(y_{i} - μ_{2})}^{2}}{2 σ_{2}}} d y_{i} \\ = \frac{1}{\sqrt{2 π} σ_{2}} \int_{u_{2}}^{u_{1}} e^{\frac{y_{i}}{2 \tilde{d}} \ln \tilde{t} - \frac{{(y_{i} - μ_{2})}^{2}}{2 σ_{2}}} d y_{i} \end{matrix}

(13)

Formula (13) dictates that the delivery success rate is affected by the variance, which is related to stability of node distribution. When the stability of node distribution is improved and the variance reduces, the transmission success rate increases correspondingly, which means the variance and transmission success rate are inversely related.

Simulations

With the help of VS 2010, we mainly simulate acoustic waves to transmit data in different deployed space. The deployed environment is simulated as mentioned in section “Introduction.” DFMT is evaluated by observing the performance variation (such as the average transmission delay, the transmission energy consumption, and the delivery success rate) when adopting different model parameters (such as the space size and the number of nodes) and by comparing DFMT with other similar algorithms FFBR and DBR. Table 2 shows the values of the parameters.

Table 2.

Simulation parameters.

Parameter name	Value
Space size	800 × 800 × 800 m³
Number of nodes	30–80
Energy consumption of data transmission	80 µJ bit⁻¹
Energy of receiving data	5 µJ bit⁻¹
Initial energy of node	100 J
Length of data packet	100 bit

For the energy consumption $\bar{E}$ , in particular, the following formula is used for the calculation

\bar{E} = \frac{\sum_{n = 1}^{N} \frac{n_{s} E_{s} + n_{R} E_{R}}{n_{s} + n_{R}}}{N}

(14)

E_S and E_R, respectively, represent energy consumption of sending data and of receiving data in unit time interval; $n_{s}$ and $n_{R}$ , respectively, represent sending times and receiving times; and N represents total number of time intervals detected.

The influence of deployed space and node number

The average transmission delay is the average period from the generation of a data packet to the delivery at the sink node. The average energy consumption is the ratio of total energy consumption to the number of nodes. The delivery success rate is the ratio of the number of the delivered data packets to the total number of the generated data packets.

As shown in Figure 7, when the space size expands, more logical layers are created, meanwhile, the forwarding count, the forwarding distance, and the transmission delay will increase. However, the variation of the number of nodes in the same region has unobvious effect on the transmission delay, this is because the forwarding counts is stable when logical layer is certain.

Figure 7.

Average transmission delay.

In Figure 8, with the increase in the space size, the average energy consumption of nodes goes up. The reason is that the transmission distance between nodes grows. Nonetheless, the number of nodes has weak impact on the average energy consumption because the routing process is still stable. While the number of nodes increases, the route does not need to be re-established, which avoids the excessive overhead.

Figure 8.

Average energy consumption.

As depicted in Figure 9, with the increase in the space size, the delivery success rate descends slightly, which shows the space size has a slight influence on the delivery success rate. As the number of nodes rises up, the delivery success rate will increase as well. The phenomenon is reasonable because the node has more forwarding opportunities when the nodes are deployed more densely.

Figure 9.

Delivery success rate.

Average transmission delay

When the number of nodes varies from 30 to 80 by the step of 5, the average transmission delay is observed as Figure 10.

Figure 10.

Average transmission delay.

The transmission delay of DFMT is stable, which is attributed to the fact that the logical layered model can provide the stable routing. However, with the increase in the number of nodes, the transmission delay of DBR and FFBR has a downward trend and gradually remains stable. That is because DBR and FFBR are routing while route is set up at the same time, and fewer nodes causes spending more time to build the routing. Moreover, as the number of nodes grows, the time spent in building the routing is reduced, and thus the overall delay is decreased.

Average energy consumption of node transmission

In this simulation, the number of nodes varies from 30 to 80 and the average energy consumption is illustrated in Figure 11.

Figure 11.

Comparison of average transmission consumption.

DBR consumes much more energy than other algorithms. Because in DBR the node has to broadcast information and judge the candidate nodes after receiving response data packets, afterward, the suitable forwarding node is determined through comparing the depths of candidate nodes. Generally, the selection of candidate nodes consumes more energy consumption. Overall, the average energy consumption of DBR shows a decreased tendency, this is because more candidate nodes are closer to the sink node when the number of nodes increases. Consequently, the average forwarding counts and the overall energy consumption will descend.

The plots of FFBR and DFMT behave more stable. In FFBR, after the routing error happens, the average energy consumption of rebuilding the routing is relatively stable. In DFMT, the average forwarding number can be restricted in a reasonable range using the logical layered model, which also makes the average energy consumption stable.

Delivery success rate

The delivery success rate is tested and shown in Figure 12.

Figure 12.

Comparison of the delivery success rate.

DBR can achieve a high delivery success rate, because it takes substantial overhead to select the appropriate forwarding nodes, ensuring the data packet can be transmitted to the sink node steadily. In FFBR, fewer nodes bring a lower delivery success rate. On the contrary, with the increase in the number of nodes, the delivery success rate is significantly improved. This is because the algorithm is dependent on the node density. The routing process is easy to be invalid in the case of sparse deployment, but when the number of nodes increases, the delivery success rate rises prominently and stabilizes gradually.

When the number of nodes varies in the range of 30–60, the delivery success rate has an ascendant trend and then remains stable in DFMT. When deployment is sparse, the nodes will be deployed unevenly according to the load balancing mechanism; meanwhile, the delivery success rate is not relatively high. Nonetheless, with the increase in the number of nodes, the layered model will be more reasonable and balanced, which makes the delivery success rate increase and tend to be more stable.

Generally, although the delivery success rate of DFMT is affected by the deployment of nodes, it is still relatively stable and to be maintained at a fairly high level.

Conclusion

In order to improve the delivery success rate and the energy consumption, the DFMT protocol based on the Markov model is proposed. In the logical layered model, the average delivery failure rate can be effectively reduced. With regard to the energy consumption, it consumes less overhead to establish the routes through building the priority forwarding sequence.

The future research will focus on the update problem of the priority forwarding sequence in DFMT, that is, how to ensure that the routes are updated when the data packet is forwarded and how to balance the relation between the update and the forwarding so as to avoid delivery failure.

Footnotes

Academic Editor: Miguel Ardid

Declaration of conflicting interests

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

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported by National Natural Science Foundation of China under Grants Nos 61373139, 61373137, 61300239, and 71301081; Natural Science Foundation of Jiangsu Province under Grant No. BK2012833; and Postdoctoral Science Foundation of China under Grant Nos 2014M560379 and 2015T80484.

References

Guo

Luo

Hong

Research progress of underwater wireless sensor networks. J Comput Res Dev 2010; 47(3): 377–389.

Akyildiz

Pompili

Melodia

State of the art in protocol research for underwater acoustic sensor networks. ACM SIGMOBILE: Mob Comput Commun Rev 2007; 11(4): 11–22.

Akyildiz

Pompili

Melodia

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

Tan

Diamant

Seah

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

Zhu

Jiang

Peng

. Toward practical MAC design for underwater acoustic networks. IEEE T Mobile Comput 2013; 14(4): 872–886.

Saminathan

Karthik

Development of an energy efficient, secure and reliable wireless sensor networks routing protocol based on data aggregation and user authentication. Am J Appl Sci 2013; 10(8): 832–843.

Weng

Qin

Zhang

Toward in-band self-organization in energy-efficient MAC protocols for sensor networks. Telecommun Sci 2013; 26(4): 433–461 (in Chinese).

Gao

Wen

Zhao

. Design and optimization of a cross-layer routing protocol for multi-hop wireless sensor networks. In: Proceedings of 2013 international conference on sensor network security technology and privacy communication system, Harbin, China, 18–19 May 2013, pp.5–8. New York: IEEE.

Qian

Xie

. A sensor network routing protocol based on node residual energy. Adv Mat Res 2013; 816–817: 1081–1084.

10.

Sahu

A survey of wireless sensor network routing protocol and lifetime of sensor network. Int J Manag IT Eng 2013; 3(8): 188–205.

11.

Heidemann

Syed

. Underwater sensor networking: research challenges and potential applications. In: Proceedings of the IEEE wireless communications and networking conference (WCNC), Las Vegas, NV, 3–6 April 2006, pp.228–235. New York: IEEE.

12.

Wali

Hossain

Munasinghe

. RF based underwater wireless sensor network architectures for tracking intruders in 3D space. In: Proceedings of the 2015 IEEE international conference on telecommunications, Dhaka, Bangladesh, 26–28 December 2015. New York: IEEE.

13.

Pastor-Galán

Gutiérrez-Alonso

Murphy

. Three-dimensional and two-dimensional deployment analysis for underwater acoustic sensor networks. Gondwana Res 2009; 7(4): 778–790.

14.

Sun

Sang

An energy efficient routing protocol for underwater sensor networks. Acoust Tech 2007; 26(1): 134–136.

15.

Tariq

Latiff

Ayaz

. A Wahid, pressure sensor based reliable (PSBR) routing protocol for underwater acoustic sensor networks. Ad Hoc Sens Wirel Ne 2016; 32(3–4): 175–196.

16.

Zhong

Routing algorithm for underwater wireless sensor networks with different node densities. Comput Eng Appl J 2012; 48(28): 112–116.

17.

Zhang

Huang

Zhang

. An energy efficient routing protocol for underwater wireless sensor networks. J Comput Sci 2008; 35: 38–41.

18.

Pompili

Melodia

Akyildiz

. Routing algorithms for delay-insensitive and delay-sensitive applications in underwater sensor networks. In: Proceedings of the ACM international wireless communications and mobile computing conference, Vancouver, BC, Canada, 3–6 July 2006, pp.298–309. New York: ACM.

19.

Yan

Shi

Cui

. DBR: depth-based routing for underwater sensor networks (Lecture notes in computer science). In: Proceedings of the international conference on research in networking, Singapore, 5–9 May 2008, vol. 4982, pp.72–86. Berlin: Springer.

20.

Ashrafuddin

Islam

Mamun-Or-Rashid

Energy efficient fitness based routing protocol for underwater sensor network. Int J Intell Syst Appl 2013; 5(6): 61–69.

21.

Tang

Mechanism of multi sensor fault detection and diagnosis based on Markov prediction. Sens Syst 2014; 33(11): 52–55.

22.

Jafri

Ahmed

Javaid

. AMCTD: adaptive mobility of courier nodes in threshold-optimized DBR protocol for underwater wireless sensor networks. In: Proceedings of the 2013 8th international conference on broadband and wireless computing, Compiegne, 28–30 October 2013, pp.93–99. New York: IEEE.

23.

Zou

Zhang

. Position prediction social-relationship-based on multi-order Markov model. In: Proceedings of the third international conference on advanced cloud and big data (CBD 2015), Yangzhou, China, 30 October–1 November 2015.

24.

Jiang

Jin

. Energy-efficient optimal opportunistic forwarding for delay-tolerant networks. IEEE T Veh Technol 2010; 59(9): 4500–4512.

25.

Liu

. A data routing algorithm based on Markov model in underwater wireless sensor networks. In: Proceedings of the2016 IEEE international conference on ubiquitous wireless broadband, Nanjing, China, 16–19 October 2016.

A data forwarding algorithm based on Markov thought in underwater wireless sensor networks

Abstract

Keywords

Introduction

Related work

DFMT forwarding model

Logical layered model

Forwarding probability

Definition 1

Definition 2

Definition 3

Load balancing

Case I

Case II

DFMT algorithm

Algorithm steps

Time complexity

Mathematical expectation analysis

Simulations

The influence of deployed space and node number

Average transmission delay

Average energy consumption of node transmission

Delivery success rate

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References