Minimum Delay Multipath Routing Based on TDMA for Underwater Acoustic Sensor Network

Abstract

Multipath routing is an alternative routing technique, which uses redundant paths to deliver data from source to destination. Compared to single path routing protocols, it can address reliability, delay, and energy consumption issues. Thus, multipath routing is a potential technique to overcome the long propagation delay and adverse link condition in underwater environment. However, there are still some problems in multipath routing. For example, the multiple paths may interfere with each other and arouse large end-to-end delay difference amongst multiple paths. This paper proposes a novel multipath routing structure and a conflict-free algorithm based on TDMA scheme. The forwarding nodes are selected based on the propagation delay and location information. This special multiple routing structure not only can ensure parallel multiple transmission without collision, but also can get a small end-to-end delay difference amongst multiple paths. Simulation results show that the multipath routing scheme proposed in this paper outperforms the traditional strategy.

1. Introduction

Underwater acoustic sensor networks (UWSNs) enable a wide range of applications such as riser fatigue monitoring [1], marine information capturing, environment monitoring, and resources exploring in the ocean [2–4]. However, the characteristics of the underwater acoustic physical channels including limited bandwidth, high propagation delay, high Bit Error Rate (BER), and temporary loss of connectivity may result in high end-to-end delay and weak reliability in UWSNs.

There are mainly two types of routing techniques, single path routing and multiple path routing. Although many single path routing protocols have been proposed to adapt with underwater acoustic physical channels, they still do not efficiently satisfy the requirements of resource constraints in UWSNs. The problems of latency caused by low acoustic speed and retransmission and of reliability caused by link interrupt are still serious in the networks which are configured with a single routing protocol. Multipath routing is a promising solution because it can improve the channel utilization rate, reduce transmission delay, and balance the transmission load.

Multipath routing is an alternative routing technique, which uses redundant paths to deliver data from source to destination. Redundant paths can reduce link interruption risks, when it is combined with error recovery techniques, which can further improve reliability [5]. The automatic repeat request (ARQ) technique can be avoided in multipath routing, which can reduce the end-to-end delay. In addition, multipath routing can balance energy consumption among nodes, which can improve network lifetime.

The main disadvantage associated with the multipath routing manifests as the delay difference among the multiple paths, which arouse packet disordering problem at the receiver and reduce throughput in routing layer [6–8]. When the traffic is split into multiple paths, the packets delivered in multiple paths have different delays. Packets that arrived earlier have to wait for later packets in reordering buffers at the receiving destination for further processing. A successful transmission is decided by the packets with largest delay among multiple paths. Particularly, in underwater applications, the delay differential amongst multiple paths may be very large due to the large propagation delay. This paper is of interest to minimize the delay variance among the paths in use [7, 8]. Moreover, the multiple paths transmission may interfere with each other. Since the long propagation delay in underwater environment, it is difficult to achieve collision-free communications without sacrificing throughput [9].

In this paper, a novel multipath routing structure and a conflict-free algorithm based on TDMA scheme are proposed for UWSNs. The proposed multipath routing scheme allows communications in parallel; furthermore, it can get a small end-to-end delay differential amongst multiple paths. There are three paths from source to sink node constructed in our approach. The most important innovation is the multipath routing structure, which is a cross layer designing. The link scheduling in MAC layer takes the requirement of end-to-end delay in routing layer into consideration; meanwhile, the multipath routing structure in routing layer provides a simple and effective opportunity for collision-free link scheduling in MAC layer.

In addition, although TDMA-based protocols require time synchronization for transmission scheduling, in recent years, several works [10–12] have provided the time synchronization mechanisms for UWSNs. The dual-rate scheme proposed in [13] is employed for network location after the sensor nodes are deployed. The time synchronization method proposed in [12] can be applied smoothly in this paper. It has three phases. The propagation delays estimation of phase I can be achieved during network location. The initial clock skews and offsets estimated by linear regression technique in phase II are based on the time beacons exchange through the whole network. Then, the time beacons will be periodically broadcast to calibrate the estimates and further improve the synchronization, that is, phase III.

The rest of the paper is organized as follows. In Section 2, we briefly review some related work. Section 3 provides the network model. In Section 4, the minimum delay routing with M-Dijkstra algorithm is introduced. The multipath routing structure is described in Section 5. The solution of the conflict-free link scheduling is described in Section 6. The simulation results are shown in Section 7. Section 8 concludes this paper.

2. Related Work

Many multipath routing protocols have been proposed in the literary [5–9, 14–25] of wireless sensor networks. Most multipath mechanisms are believed to improve the reliability of networks; some of them also are related to energy saving and latency. The problem of delay difference amongst multiple paths is presented in [7, 8, 26]. The problem that multiple paths interfere with each other is proposed in [9, 14–16]. Among the possible variants, there are two ways of effecting disjoint multipath routing (MPR) in multihop networks: (1) each packet is sent along different disjoint routes; (2) multiple copies of a data packet are transmitted simultaneously along multiple disjoint routes from a source to a destination [17]. Meanwhile, there are two multipath structure: (1) single destination node and (2) multidestination node. Then, we briefly review some related works based on the routing structure and transmission scheme for our further discussion.

The multisink structure is studied in [18–21, 26]. The proposal [19] proposes a virtual sink architecture, which allows sensor node to transmit data to one or more sinks to increase reliability and is considered retransmitting a packet simultaneously instead of sequentially. The protocol [18] takes the noise attenuation into account and proposes a new asymmetric multipath division communications (AMDC) mechanism to improve reliability and energy efficiency in wireless sensor networks. The communication space is divided into multiple layers to initialize the tree-based multipath. The layers with low noise attenuation have a long transmission distance. The network proposed in [20] is a harbor monitoring network, with the task to detect outbound surface boats. In order to cope with noise originating from the boat propellers, the network proposes a multipath routing with multisink (buoy and ships) against excessive packet losses in the presence of strong jamming. The protocol [26] uses an angle based flooding architecture, in which multisinks are anchored on the water's surface to collect data packets. This architecture is not only helpful to increase the data delivery ratios, but also able to increase the network lifetime by reducing the energy consumption of the nodes around the sinks.

The following protocols presented all use single sink. The protocols [5, 22–24] are proved to improve the reliability of networks. The protocol [5] proposes a new multipath power control transmission (MPT) scheme, which can guarantee certain end-to-end packet error rate while achieving a good balance between the overall energy efficiency and the end-to-end packet delay. The proposal [22] combines network coding and multipath routing to improve reliability. The protocol [23] proposes an error recovery scheme based on Reed Solomon (RS) codes and multipath routing. The protocol [24] presents network coding based reliable disjoint and braided multipath routing (NC-RMR) for sensor networks.

The approaches [7, 16, 25] are put forward to deal with the end-to-end delay problem. The approach [25] improves multipath Dijkstra algorithm for path selection, which can build several node-disjoint or link-disjoint multipaths. The protocol [16] utilizes the multiple paths between the source and sink to provide a solution satisfying the delay requirements of different traffic types. It use “priority level slicing” to gain a plain view of the connectivity graph. The multipath routing is simplified to multiple parallel single path routing instead. The proposal [7] considers the problem of minimizing delay difference amongst paths utilized for concurrent multipath routing.

The protocols [9, 14, 15] are proposed to set up interference-free multiple paths. The protocol [9] proposed a multipath routing protocol that causes little interference to one another. The node floods a path discovery packet and waits for path reply packets. Before forwarding a path reply to the source, every relay checks if some of its neighbors have already transmitted a path reply for the same path discovery sequence number and source-destination pair. The proposal [15] attempts to find two collision-free routes using constrained and power adjusted flooding and then transmits data with minimum power needed through power control component of the protocol. The protocol [14] which extends the proposal [15] introduces a geographic energy-aware noninterfering multipath (GEAM) routing scheme which divides the whole network topology into many districts and simultaneously forwards data through these districts without interfering with each other to achieve interference-free transmissions.

This paper focuses on the problem of end-to-end delay difference amongst multiple paths. The proposed multipath routing has single source and destination, and multiple copies of a data packet are transmitted simultaneously along multiple disjoint routes from the source to the destination the same as some of the previous literature. However, there are still some unique techniques different from the previous ones. The contention-free MAC protocol (TDMA) is applied in this paper, while all the previous research employs contention-based MAC protocols. This paper highlights routing structure in multipath routing which is rarely mentioned. The main difference is that a cross layer designing is introduced to overcome the multipath interference problem and end-to-end delay difference problem.

3. Network Model

We model a typical, nonmobile underwater acoustic sensor network designed to sense information and forward it to a remote user through a sink node. All nodes are moored in the sea. Each underwater node has a single, half-duplex transducer. DPSK modulation is used in physical layer. In MAC layer, TDMA scheme is employed.

An underwater sensor network can be represented by a directed graph model $G=(V,E)$ , where $V=\{v_1,\dots ,v_n\}$ is the set of nodes and $E=\{e_1,\dots ,e_n\}$ is the set of directed links. Assume that $s_i$ represents start transmission time of link $e_i$ , $p_i$ is propagation of link $e_i$ , ${\Delta }_i$ means transmission delay of link $e_i$ , and $T_f$ represents a frame length.

Then, we show how single-hop scheduling delay occurs in TDMA scheme in Figure 1 for two different scenarios, A (Figure 1(a)) and B (Figure 1(b)). We align the time axis to the beginning of the data subframe to simplify exposition. In scenario A, as $s_j>s_i+p_i+{\Delta }_i$ , a packet sent from $v_k$ to $v_m$ experiences the scheduling delay of $s_j-s_i+p_i+{\Delta }_i$ . In scenario B, as $s_j<s_i+p_i+{\Delta }_i$ , when the packet arrives at $v_l$ , it has to wait for additional time to transmit until the transmitting slot belongs to $e_j$ in the next frame. In this case, the scheduling delay from $v_k$ to $v_m$ is $s_j-s_i+p_i+{\Delta }_i+T_f$ . Although the analysis model has been proposed in [27], it does not consider the propagation delay.

Figure 1

Single-hop delay in two different scenarios.

Suppose a path from source to the destination is $\rho =\{e_1,e_k\cdots e_n\}$ ; the delay on the path is $\Phi (\rho )$ :

$$\begin{array}{c}\Phi \left(\rho \right)={\displaystyle \sum }_{i=1}^{n-1}{d}_{e_i,e_{i+1}}+p_n+{\Delta }_n,\end{array}$$

(1)

$$\begin{array}{c}{d}_{e_i,e_{i+1}}=\left\{\begin{array}{cc}{s}_{i+1}-s_i,\hfill & r_i<s_{i+1};\hfill \\ s_{i+1}-s_i+T_f,\hfill & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{s},\hfill \end{array}\right.\end{array}$$

(2)

where $d_{e_i,e_{i+1}}$ is scheduling delay occurring between links $e_i$ and $e_{i+1}$ and $r_i=s_i+{\Delta }_i+p_i$ represents the arrival time of signals from link $e_i$ .

The problem of minimizing end-to-end delay difference amongst multiple paths addressed in this paper can be express as

$$\begin{array}{c}\mathrm{M}\mathrm{i}\mathrm{n}\hspace{1em}\mu \end{array}$$

(3)

$$\begin{array}{c}\mathrm{s}.\mathrm{t}\hspace{1em}\max \left(\Phi \left({\rho }_i\right)\right)-\min \left(\Phi \left({\rho }_i\right)\right)\le \mu \end{array}$$

(4)

$$\begin{array}{c}\hspace{1em}\max \left\{\Phi \left({\rho }_i\right)\right\}\le {\Phi }_{\mathrm{m}\mathrm{a}\mathrm{x}}\end{array}$$

(5)

$$\begin{array}{c}\hspace{1em}2\le i\le N_{\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}},\end{array}$$

(6)

where $N_{\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}}$ is the amount of multipaths in the network.

The objective of (5) is to restrict the end-to-end delay to meet the requirement of a specified throughput (a small end-to-end delay leads to high throughput). It can be seen from (1) that the frame length $T_f$ has great influence on the scheduling delay. In order to minimize the end-to-end delay, we suggest that the links cannot access the channel before receiving data from the last hop. In this paper, we do not give certain μ and ${\Phi }_{\mathrm{m}\mathrm{a}\mathrm{x}}$ , which is another complex problem that should take topology control and power control into consideration. The objective of (3) is to minimize the delay difference amongst the routing paths. We focus our attention on establishing an efficient multipath routing to achieve objective of (3) as far as possible.

4. M-Dijkstra Algorithm

Minimizing delay difference amongst paths for concurrent multipath routing is NP-hard [8]. We firstly propose a practical heuristic approach based on traditional shortest routes algorithm, Dijkstra algorithm. Dijkstra algorithm [28] is used to calculate the shortest paths from a vertex to the others. It is basically and widely used to search the shortest routes in routing selection.

A network with $6$ nodes and $8$ directed links is shown in Figure 2(a), where $v_1$ is source node and $v_6$ is destination node. In Figure 2(a), the vertices are nodes and the edges are links. In order to better describe the method, the link map in Figure 2(a) is expressed in another way as shown in Figure 2(b). In Figure 2(b), the vertices are links except source and destination node, and the edges are scheduling delays. Inspired by M-Dijkstra algorithm proposed in [25], we put forward an improved M-Dijkstra algorithm to search several minimum delay paths from source to the others with the routing metric of delay constraint.

Figure 2

(a) Connectivity graph with $6$ nodes and $8$ directed links. (b) Multipath routing from node $v_1$ to node $v_6$ .

The delay cost on the edges in Figure 2(b) is the scheduling delay $d_{e_i,e_j}$ , which is decided by a certain a scheduling order S. The scheduling order S gives the time slot of each link for channel access. The cost on edges between the source node and first forwarding link is $0$ . The cost on the edges between the last forwarding link and destination node is sum of propagation delay and transmission delay of the last forwarding link; in Figure 2(b), they are $p_7+{\Delta }_7$ and $p_8+{\Delta }_8$ . Several shortest paths between source to destination node can be found by the following steps. Step one, calculate the delay cost $d_{e_i,e_j}$ on the edges using (3) with the scheduling order S. Step two, choose the shortest path by Dijkstra algorithm and label the vertexes that have been selected. Step three, search another shortest path among the unlabelled vertexes. Then, repeat step three, and several shortest paths can be found by improved M-Dijkstra.

It is useful to reduce the delay difference if the scheduling order is carefully arranged; however, it is very difficult to balance the relationship between the average end-to-end delay and delay difference problem well.

5. Min-Delay Routing

5.1. Regular Topological Structure

Suppose the network is constructed by some square cells. The network nodes are located at the apex of the square as shown in Figure 3. The side length is a. There are three paths from source node $v_1$ to destination node $v_{14}$ . Also ${\rho }_1=\{e_1,e_4,e_7,e_{10},e_{13}\}$ , ${\rho }_2=\{e_2,e_5,e_8,e_{11},e_{14}\}$ , and ${\rho }_3=\{e_3,e_6,e_9,e_{12},e_{15}\}$ . The network selects TDMA and unicast transmission on MAC layer.

Figure 3

Regular topological structure: black solid line is communication links; red dotted line represents interference.

In order to reduce delay difference among the three paths, the links in the same hop are advised to transmit in parallel. Because of broadcast nature of wireless channels, the links may interfere with each other. Whenever the receptions of any two packets partially are superimposed at the receiver, the packets are assumed to collide and be lost. In this paper, a novel link scheduling scheme is proposed to deal with the problems. We take links $e_4,e_5,e_6$ as an example to illustrate how the link scheduling scheme operates.

$$\begin{array}{c}{s}_4+p_4+{\Delta }_4<s_5+p_{35}^{\prime },\end{array}$$

(7)

$$\begin{array}{c}{s}_4+p_4+{\Delta }_4<s_6+p_{45}^{\prime },\end{array}$$

(8)

$$\begin{array}{c}{s}_5+p_5+{\Delta }_5<s_4+p_{26}^{\prime },\end{array}$$

(9)

$$\begin{array}{c}{s}_5+p_5+{\Delta }_5<s_6+p_{46}^{\prime },\end{array}$$

(10)

$$\begin{array}{c}{s}_6+p_6+{\Delta }_6<s_5+p_{37}^{\prime },\end{array}$$

(11)

$$\begin{array}{c}{s}_6+p_6+{\Delta }_6<s_4+p_{27}^{\prime },\end{array}$$

(12)

where $p_{ij}^{\prime }$ represents propagation of interference signals from node $v_i$ to node $v_j$ .

Equations (7)-(8) make the data stream from link $e_4$ reach its destination before the interference signals from links $e_5$ and $e_6$ arrive. Similarly, (9)-(10) make the data stream from link $e_5$ reach its destination before the interference signals from links $e_4$ and $e_6$ arrive. Equations (11)-(12) make the data stream from link $e_6$ reach its destination before the interference signals from links $e_4$ and $e_5$ arrive.

Suppose the start transmission time of links in the same hop among different paths at the same time $s_4=s_5=s_6$ . In order to satisfy the equations above, the transmission delay of the links should meet $\{{\Delta }_4,{\Delta }_5,{\Delta }_6\}<(\sqrt{2}-1)a$ . In other words, if the transmission delay of the links satisfies the condition $\{{\Delta }_{3i+1},{\Delta }_{3i+2},{\Delta }_{3i+3}\}<(\sqrt{2}-1)a$ , $0<i<4$ in Figure 3, and the start transmission times of links in the same hop among different paths are the same, the multiple links in the same hop can transmit in parallel without interference.

5.2. Random Topological Structure

Influenced by the current, the network nodes deployed in underwater cannot always maintain a regular topological structure. In this paper, a practical proposal is proposed to construct multipath routing. The forwarding node selection consists of two parts, the selection of first-hop forwarding nodes and the selection of the remaining hops forwarding nodes. A schematic drawing of forwarding nodes selection in random topological structure is shown in Figure 4.

Figure 4

(a) The first-hop forwarding nodes selection diagram. (b) The remaining hops forwarding node selection diagram.

5.2.1. First-Hop Forwarding Nodes

The first-hop forwarding nodes selection process is shown in Figure 4(a). Give a routing vector $\overrightarrow{v_1{v}_n}$ , where $v_1$ is the source node and $v_n$ is the sink node; the network region is divided into two zones by the routing vector $\overrightarrow{v_1{v}_n}$ , upper zone and bottom zone. There are three paths in the network. The first forwarding node $v_2$ of the first path is selected in the upper zone, the first forwarding node $v_4$ of the third path is selected in the bottom zone, and the first forwarding node $v_3$ of the second path is selected near the routing vector $\overrightarrow{v_1{v}_n}$ .

The angle factor is defined as $\alpha =\left(\overrightarrow{v_1{v}_n}·\overrightarrow{v_4{v}_2}\right)/\left(\left|\overrightarrow{v_1{v}_n}\right|·\left|\overrightarrow{v_4{v}_2}\right|\right)$ ; it is the cosine of angle between vector $\overrightarrow{v_1{v}_n}$ and vector $\overrightarrow{v_4{v}_2}$ . The vertical distance factor is defined as $d=\left|\overrightarrow{v_1{v}_3}\right|·\sqrt{1-{\beta }^2}$ ; it is the vertical distance from node $v_3$ to the vector $\overrightarrow{v_1{v}_n}$ . $\beta =\left(\overrightarrow{v_1{v}_n}·\overrightarrow{v_1{v}_3}\right)/\left(\left|\overrightarrow{v_1{v}_n}\right|·\left|\overrightarrow{v_1{v}_3}\right|\right)$ is the cosine of angle between vector $\overrightarrow{v_1{v}_n}$ and vector $\overrightarrow{v_1{v}_3}$ . The selected forwarding node for the first hop of the first path and the third path should minimize the angle factor α. The first-hop forwarding node of the second path should minimize the vertical distance factor d.

5.2.2. The Remaining Hops Forwarding Nodes

The remaining hops forwarding nodes selection process is shown in Figure 4(b). Give the perpendicular bisector $l_{\overrightarrow{v_4{v}_2}}^{\perp }$ for vector $\overrightarrow{v_4{v}_2}$ . It also divides the network region into two zones similar to the routing vector $\overrightarrow{v_1{v}_n}$ . The second-hop forwarding node of the first path should be selected in the upper zone; the second-hop forwarding node of the third path should be selected in the bottom zone. Meanwhile, the second-hop forwarding node of the first path and the third path should also minimize the angle factor α. Then, the selection of the remaining hop forwarding nodes in first path and third path follows the above process. The selection of the remaining hop forwarding node of second path is the same as its process of the first hop.

The process of forwarding nodes selection will stop until the forwarding node in the same hop of the three path can reach the sink node.

5.2.3. Direction Factor

In order to avoid roundabout route, it is necessary to add a direction factor to make the routing pipeline point to the sink node straightly. The direction factor consisted of transmission radius R and coordinate increment factor $I_x$ . The transmission radius R is defined to control the hop count in the network. In this paper, we do not discuss the issue of the optimal hop count for the network. This issue can be found in [29]. The coordinate increment factor $I_x$ is defined to ensure that the x-coordinate of the node in $i+1$ hop and i hop should satisfy $x_{v_{i+1}}>x_{v_i}+I_x$ .

Moreover, it is a node-disjoint scheme; all the forwarding nodes should only belong to one path and the forward nodes of the second path should be selected prior to the others, which is useful for link independence.

6. Link Scheduling for Noninterference Multipath Routing

6.1. Basic Idea of Multipath Routing Structure

The basic idea of the multipath routing structure is based on perpendicular bisector as shown in Figure 5. Line $l_{\overrightarrow{v_4{v}_2}}^{\perp }$ is the perpendicular bisector of vector $\overrightarrow{v_4{v}_2}$ . It divided the zone into two parts. When the next forwarding node is at the perpendicular bisector such as $v_6$ , the distances between $v_6$ and $v_2$ and $v_4$ are always equal, $\left|\overrightarrow{v_2{v}_6}\right|=\left|\overrightarrow{v_4{v}_6}\right|$ . When the forwarding nodes are in one side of the perpendicular bisector, there always is a distance difference. If the next forwarding node is in the upper zone such as $v_5$ , let vector $\overrightarrow{v_a{v}_5}$ be perpendicular to vector $\overrightarrow{v_4{v}_2}$ , so $v_a$ is also in the upper zone, and we have $\left|\overrightarrow{v_4{v}_a}\right|>\left|\overrightarrow{v_a{v}_2}\right|$ . Then, It can be seen that $\left|\overrightarrow{v_4{v}_5}\right|>\left|\overrightarrow{v_2{v}_5}\right|$ . In the same case, when the forwarding node $v_7$ is in the bottom zone, we have $\left|\overrightarrow{v_2{v}_7}\right|>\left|\overrightarrow{v_4{v}_7}\right|$ .

Figure 5

Perpendicular bisector structure.

Based on (7)–(12), if the transmission delays satisfy the condition $\{{\Delta }_2,{\Delta }_4\}\le \min \{|\overrightarrow{v_4{v}_5}|-|\overrightarrow{v_2{v}_5}|,|\overrightarrow{v_2{v}_7}|-|\overrightarrow{v_4{v}_7}|\}$ and the start transmission times of node $v_2$ and node $v_4$ are the same, the destination node $v_5$ and node $v_7$ can successfully receive the signals without any interference. Sometimes, the delay difference between the links is very small; the network topology cannot provide sufficient time for transmission. It can be solved by rate control and multiple transmission in single hop.

6.2. Link Scheduling

Our previous work [30, 31] has proposed a link scheduling method for underwater acoustic sensor networks. This paper also follows the link scheduling model in [30]. The proposed model employs correlation matrix to describe the conflicts relationship among links and uses propagation delay to generate conflict matrix for collision detection. The correlation matrix B is a $n\times m$ matrix, where n is the number of nodes and m is the number of links:

$$\begin{array}{c}B={\left(b_{ij}\right)}_{n\times m}\in {\left\{-2,-\mathrm{1,0},1\right\}}^{n\times m},\\ b_{ij}=\left\{\begin{array}{cc}1,\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}{v}_i\hspace{0.17em}\hspace{0.17em}\mathrm{i}\mathrm{s}\hspace{0.17em}\hspace{0.17em}\mathrm{t}\mathrm{h}\mathrm{e}\hspace{0.17em}\hspace{0.17em}\mathrm{s}\mathrm{o}\mathrm{u}\mathrm{r}\mathrm{c}\mathrm{e}\hspace{0.17em}\hspace{0.17em}\mathrm{o}\mathrm{f}\hspace{0.17em}\hspace{0.17em}{e}_j,\hfill \\ -1,\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}{v}_i\hspace{0.17em}\hspace{0.17em}\mathrm{i}\mathrm{s}\hspace{0.17em}\hspace{0.17em}\mathrm{t}\mathrm{h}\mathrm{e}\hspace{0.17em}\hspace{0.17em}\mathrm{d}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\hspace{0.17em}\hspace{0.17em}\mathrm{o}\mathrm{f}\hspace{0.17em}\hspace{0.17em}{e}_j\hfill \\ -2,\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}{v}_i\hspace{0.17em}\hspace{0.17em}\mathrm{i}\mathrm{s}\hspace{0.17em}\hspace{0.17em}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{f}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{d}\hspace{0.17em}\hspace{0.17em}\mathrm{b}\mathrm{y}\hspace{0.17em}\hspace{0.17em}{e}_j\hfill \\ 0,\hfill & \mathrm{e}\mathrm{l}\mathrm{s}\mathrm{e}.\hfill \end{array}\right.\end{array}$$

(13)

The start transmission time $s_i$ and signals arrival time $s_i+p_i$ are introduced to the conflict matrix C to replace the elements 1, −1, and $-2$ in the correlation matrix B. The conflict-free condition is (14). All details about the link scheduling model can be found in [31]. Consider

$$\begin{array}{c}\left|C_{ij}-C_{ik}\right|\ge \Delta +g,\hspace{1em}i\in n,\hspace{0.17em}\hspace{0.17em}j,k\in m\\ \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}\left(b_{ij},b_{ik}\right)\in \left\{\left(-1,-1\right),\left(-1,-2\right),\left(-\mathrm{1,1}\right),\left(\mathrm{1,1}\right)\right\}.\end{array}$$

(14)

The link scheduling process includes three parts, respectively, the first hop, 2 to $n-1$ hops, and the last hop. The link scheduling algorithm is shown in Algorithm 1, where $\mathrm{s}\mathrm{l}$ represents slot length; we have $\mathrm{s}\mathrm{l}=\Delta +g$ ; g is guard interval for time synchronization. Assume that all the transmission delays are equal to Δ, which is decided by the distance difference of links between path one and path three. H is total number of hops of multipath routing. $s_i$ represents the slot position for link $e_i$ in the frame; the start transmission time is $s_i\ast \mathrm{s}\mathrm{l}$ .

Algorithm 1: Link scheduling.

Input:

   $B_{n\times m}$ , $C_{n\times m}$ , $\mathrm{\Delta }$ , $\mathrm{s}\mathrm{l}$

Process:

(1)  while   $k<H+1$   do

(2)  if   $k==1$   then

(3)    $[a,b]$  =  sort [propogation of links in the first hop]

(4)    $$\mathrm{\hspace{0.17em}\hspace{0.17em}}{s}_{b\left(3-i+1\right)}=i-1$$

(5)   hoplength =  $[s_1\ast \mathrm{s}\mathrm{l}+p_1+\mathrm{\Delta },s_3\ast \mathrm{s}\mathrm{l}+p_3+\mathrm{\Delta }]$

(6)    $s_{\mathit{3}\ast k+\mathit{1}}=s_{\mathit{3}\ast k+\mathit{3}}$  = ceil ( $\max (\mathrm{h}\mathrm{o}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h})$ /sl)

(7)   Conflict Detection [ $B(\mathit{1}\to \mathit{3}\ast k+\mathit{3},\mathrm{e}\mathrm{x}\mathrm{p}\mathrm{c}\mathrm{e}\mathrm{t}(\mathit{3}\ast k+\mathit{2})),C,\left\{\mathit{3}\ast k+\mathit{1,3}\ast k+\mathit{3}\right\}$ ]

(8)    $\mathrm{\hspace{0.17em}\hspace{0.17em}}{s}_{3\ast k+2}=\mathrm{c}\mathrm{e}\mathrm{i}\mathrm{l}((s_2\ast \mathrm{s}\mathrm{l}+p_2+\mathrm{\Delta })/\mathrm{s}\mathrm{l})$

(9)   Conflict Detection [ $B(\mathit{1}:\mathit{3}\ast k+\mathit{3}),C,\mathit{3}\ast k+\mathit{2}$ ]

(10)     $k=k+1$

(11)   else if   $k==H$   then

(12)     $\mathrm{\hspace{0.17em}\hspace{0.17em}}[a,b]$  = sort [propogation of links in the last hop]

(13)    hoplength =  $[s_{3\ast (k-1)+1}\ast \mathrm{s}\mathrm{l}+p_{3\ast (k-1)+1}+\mathrm{\Delta },s_{3\ast (k-1)+2}\ast \mathrm{s}\mathrm{l}+p_{3\ast (k-1)+2}+\mathrm{\Delta },s_{3\ast (k-1)+3}\ast \mathrm{s}\mathrm{l}+p_{3\ast (k-1)+3}+\mathrm{\Delta }]$

(14)     $s_{3\ast k+b(3-i+1)}$  = ceil ( $\max (\mathrm{h}\mathrm{o}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h})$ / $\mathrm{s}\mathrm{l}$ ) + ( $i-1$ )

(15)     $k=k+1$

(16)   else

(17)    hoplength =  $[s_{3\ast (k-1)+1}\ast \mathrm{s}\mathrm{l}+p_{3\ast (k-1)+1}+\mathrm{\Delta },s_{3\ast (k-1)+3}\ast \mathrm{s}\mathrm{l}+p_{3\ast (k-1)+3}+\mathrm{\Delta }]$

(18)     $s_{3\ast k+1}=s_{3\ast k+3}$  = ceil ( $\max (\mathrm{h}\mathrm{o}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h})$ / $\mathrm{s}\mathrm{l}$ )

(19)    Conflict Detection [ $B(\mathit{1}\to \mathit{3}\ast k+\mathit{3},\mathrm{e}\mathrm{x}\mathrm{p}\mathrm{c}\mathrm{e}\mathrm{t}(\mathit{3}\ast k+\mathit{2})),C,\left\{\mathit{3}\ast k+\mathit{1,3}\ast k+\mathit{3}\right\}$ ]

(20)     $s_{3\ast k+2}$  = ceil $((s_{3\ast (k-1)+2}\ast \mathrm{s}\mathrm{l}+p_{3\ast (k-1)+2}+\mathrm{\Delta })/\mathrm{s}\mathrm{l})$

(21)    Conflict Detection [ $B,C,\mathit{3}\ast k+\mathit{2}$ ]

(22)     $k=k+1$

(23)   end if

(24)  end while

The first part of link scheduling algorithm is for the three links belonging to first hop in the multipath routing (lines 2–10). In order to minimize end-to-end delay, the link with higher propagation delay will be scheduled at first. There is a gap with a slot length among the three links.

The second part of link scheduling algorithm is for the $2$ to $n-1$ hops in the multipath routing (lines 17–22). According to the analysis of delay in Section 2, the start transmission time of the links in current hop should be after the packet from the last hop has been received. The links in the first path and third path will be scheduled at the same time to ensure conflict-free parallel communication.

The third part of link scheduling algorithm is for the last hop (lines 11–15). The link with higher propagation delay will be scheduled firstly. Then, take the conflict detection algorithm until all links will be scheduled.

6.3. Conflict Detection

Due to the special multipath structure and reasonable assumptions of start transmission time, when the transmission delay is carefully selected, the links ( $2$ to $n-1$ hops) of the first path and the third path can transmit in parallel without interference, which can neglect conflict avoidance in link scheduling algorithm. However, conflict detection algorithm should be taken into considered in link scheduling algorithm for the second path. The conflict detection algorithm is shown in Algorithm 2.

Algorithm 2: Conflict detection.

Input:

   $B_{n\times m}$ , $C_{n\times m}$ , $\mathrm{s}\mathrm{l}$ , i

Process:

(1)  $k=\mathrm{T}\mathrm{U}\mathrm{R}\mathrm{E}$

(2)  $s_i$  = current start slot position of the links in the same hop

(3)  while   $k==\mathrm{T}\mathrm{U}\mathrm{R}\mathrm{E}$   do

(4)  if  link i satisfy (14)  then

(5)    link i have been scheduled, updata C

(6)     $k=\mathrm{F}\mathrm{A}\mathrm{L}\mathrm{S}\mathrm{E}$

(7)  else

(8)     $s_i=s_i+\mathrm{s}\mathrm{l}$

(9)  end if

(10)  end while

The initial slot position of the links in the second path is the same as the others in the same hop. If the signals transmitted in the second path conflict with other links, with a slot length increment, perform the conflict detection algorithm until there is no conflict.

7. Simulation Result

OPNET simulator is used to evaluate the performance of different heuristics. To simulate acoustic channels, we have extended OPNET with spherical path loss and Thorp attenuation [32]. In the simulations, there are $40$ sensor nodes randomly deployed in a network of 3 km × 3 km, containing a single source and sink deployed on the bottom of water. The whole network load follows the poisson distribution.

There are two power control models employed in this paper. The fixed power control model is used for determining transmission distance R in forwarding node selection process and the adaptive power control model is used in data transmission. The adaptive power control model follows the physical model and assumes the transmission power is equal to the minimum transmission power [33], which means that a correct reception cannot tolerate any interference from other links. The transmission power is the minimum power that meets the communication threshold of signal to noise $\mathrm{S}\mathrm{N}{\mathrm{R}}_{\mathrm{t}\mathrm{h}}=10\hspace{0.17em}\mathrm{d}\mathrm{B}$ . The ambient noise PSD is 46 dB, which is a common value when the carrier frequency is 10 KHz [33]. The propagation speed is 1500 m/s, the transmission rate is 2.5 kbps, and the length of a data packet is 800 bits. The minimum transmission delay of the simulation topology is 0.4 s and the guard interval 0.2 s, so the slot length is 0.6 s. The simulation lasts 2 hours.

7.1. Multipath Routing Structure

The simulation results of multipath routing structure are shown in Figures 6 and 7. There are three disjoint paths from source node to sink node in the network. When the transmission radius is $R=1000\hspace{0.17em}\mathrm{m}$ , the multipath routing can be formed by $5$ hops as shown in Figure 6. When the transmission radius is $R=2000\hspace{0.17em}\mathrm{m}$ , the multipath routing can be formed only by $3$ hops as shown in Figure 7. Because of the coordinate increment factor $I_x$ , there are no roundabout links existing in the multipath structure.

Figure 6

Multipath routing structure ( $R=1000\hspace{0.17em}\mathrm{m},\hspace{0.17em}\hspace{0.17em}{\Delta }_x=10\hspace{0.17em}\mathrm{m}$ ).

Figure 7

Multipath routing structure ( $R=2000\hspace{0.17em}\mathrm{m},\hspace{0.17em}\hspace{0.17em}{\Delta }_x=10\hspace{0.17em}\mathrm{m}$ ).

7.2. Network Throughput

Figure 8 shows the network throughput of the M-Dijkstra algorithm and Min-delay multipath routing. It can be seen from the simulation results that the Min-delay multipath routing outperforms M-Dijkstra algorithm in the network throughput. The maximum throughput of M-Dijkstra algorithm is only 0.06 packets/s, while the maximum throughput of Min-delay multipath routing can reach 0.15 packets/s.

Figure 8

Network throughput of the two heuristics strategies.

7.3. Average End-to-End Delay and Delay Difference

Figure 9 shows the three-path delay of the two heuristics strategies. The three paths constructed by the two strategies can achieve almost the same delay difference. The packets delivered along the three paths of the two strategies can reach the sink node at almost the same time; however, the Max-Min delay difference of the Min-delay routing is 1.01 s which is smaller than 1.67 s occurring in the M-Dijkstra algorithm. The simulation results of Max-Min delay difference of the two heuristics strategies are shown in Figure 10. It can be found in Figure 10 that the average end-to-end delay of Min-delay multipath routing is more excellent than M-Dijkstra algorithm.

Figure 9

Three-path delay of the two heuristics strategies.

Figure 10

Average end-to-end delay and delay Difference.

8. Conclusion

Multipath routing is an effective technique to deal with instability underwater channel. This paper proposes a novel multipath routing scheme, named Min-delay routing. The multipath routing structure and conflict-free link scheduling algorithm based on TDMA scheme are combined to overcome the multipath interference problem and end-to-end delay difference problem. Compared to the traditional multipath technology based on Dijkstra algorithm, the proposed Min-delay routing not only can guarantee network throughput, but also lowers average end-to-end delay and Max-Min delay difference amongst multiple paths. Our future work will focus on the power control and rate control problem for UWSNs.