LTDA-MAC v2.0: Topology-Aware Unsynchronized Scheduling in Linear Multi-Hop UWA Networks ^†

Abstract

This paper investigates the use of underwater acoustic sensor networks (UASNs) for subsea asset monitoring. In particular, we focus on the use cases involving the deployment of networks with line topologies, e.g., for monitoring oil and gas pipelines. The Linear Transmit Delay Allocation MAC (LTDA-MAC) protocol facilitates efficient packet scheduling in linear UASNs without clock synchronization at the sensor nodes. It is based on the real-time optimization of a packet schedule for a given network deployment. In this paper, we present a novel greedy algorithm for real-time optimization of LTDA-MAC schedules. It produces collision-free schedules with significantly shorter frame duration, and is 2–3 orders of magnitude more computationally efficient than our previously proposed solution. Simulations of a subsea pipeline monitoring scenario show that, despite no clock synchronization, LTDA-MAC equipped with the proposed schedule optimization algorithm significantly outperforms Spatial TDMA.

1. Introduction

Underwater acoustic sensor networks (UASNs) are a key technology for monitoring the underwater environment, enabled by the recent developments in underwater acoustic modem technologies [1,2,3,4,5]. Acoustic waves are the preferred communication medium underwater, since they can propagate significantly further than electromagnetic and optical waves. However, acoustic communications are fundamentally limited by the slow sound propagation and low available bandwidth. These physical constraints present the need for Medium Access Control (MAC) protocols designed specifically for UASNs.

A major application area of UASNs is live monitoring of subsea oil and gas infrastructure, which may often involve sensor networks with line topologies, e.g., for leakage detection and corrosion monitoring in underwater pipelines [6,7]. In linear UASNs (LUASNs) the packets are routed via multiple hops between neighbouring nodes as shown in Figure 1. Typical connection ranges in LUASNs allow the nodes to communicate with their neighbours, but are short enough to avoid interference between nodes further apart. Such sparse node connectivity is highly suitable for spatial spectrum reuse, i.e., simultaneous packet scheduling in several parts of the network without collisions.

The state-of-the-art research on MAC protocols for UASNs with sparsely connected topologies (e.g., LUASNs) focuses on designing spatial reuse patterns of slots in TDMA schedules [9,10,11]. A significant drawback of TDMA-based protocols is the need for long guard intervals to account for the propagation delays, thus reducing the network throughput and increasing the packet latency [12]. They also require clock synchronization among the network nodes, which is more challenging in UASNs than in terrestrial networks [13,14]. As an alternative to deterministic schedule-based TDMA methods, communication networks often use contention-based MAC protocols [15,16,17,18,19] where nodes access a shared channel randomly on demand, based on a particular set of rules [20]. However, most conventional contention-based MAC protocols are highly inefficient in the underwater acoustic environment. For example, channel reservation based protocols waste a large part of channel capacity while the nodes are waiting for control signals to propagate through the slow acoustic medium to establish a communication link, e.g., Request-to-Send (RTS), Clear-to-Send (CTS), acknowledgements etc. These waiting times result in significant loss of throughput and poor channel utilization [13,15,16]. This paper focuses on the schedule-based MAC approach, as it is particularly well-suited for the linear network topologies, where the sparse node connectivity can be exploited to schedule simultaneous, spatially separated transmissions.

In [8] we proposed the Linear Transmit Delay Allocation MAC (LTDA-MAC) protocol that achieves high throughput in LUASNs via heuristic optimization of packet schedules that do not require clock synchronization at the network nodes. It works for arbitrary node connectivity/interference patterns, exploiting long propagation delays and topology sparsity specific to a given network deployment. The purpose of this paper is to report on a significant further development on LTDA-MAC: a novel greedy optimization algorithm that produces better scheduling solutions and dramatically reduces the computational cost compared with our previous method based on global optimization via a Genetic Algorithm (GA) and Particle Swarm Optimization (PSO).

The rest of the paper is organized as follows: Section 2 presents the details of LTDA-MAC and our proposed schedule optimization algorithm, Section 3 discusses the simulation results, and Section 4 concludes the paper.

2. Linear TDA-MAC

The TDA-MAC protocol [21] was originally designed to facilitate centralized packet scheduling in single-hop UASNs, i.e., where multiple sensor nodes are connected to a single master node. It was then extended to support dual-hop topologies in [22] and line network topologies in [8]. Its key differentiating feature compared with other schedule-based MAC protocols is that it does not require clock synchronization at the sensor nodes. Instead, the times of transmissions are determined locally at the nodes, based on the node-specific delays between receiving a request packet and transmitting their data packets.

In this paper we focus on unsynchronized scheduling in LUASNs using the LTDA-MAC protocol [8]—a protocol designed specifically for networks with line topologies. Figure 1 depicts an example of a LUASN. Every sensor node only uses two connections—a node one hop closer to the sink node (up the chain) and a node one hop further down the chain. The job of a sensor node is to transmit its own packets up the chain and forward data packets from sensor nodes down the chain.

Figure 2 depicts an LTDA-MAC schedule, in this particular example based on one-hop interference range among the sensor nodes. In addition to scheduling their own data transmissions, Nodes 1 and 2 are responsible for forwarding the packets between the sink node and the other nodes down the chain. The LTDA-MAC schedule is defined by the delays between sensor nodes receiving a request (REQ) packet and transmitting a data packet. For a network comprising $N_{\mathrm{sn}}$ sensor nodes, the transmit delays that define an LTDA-MAC schedule can be expressed by a triangular matrix:

$${\mathit{T}}_{\mathbf{tx}}=\left[\begin{array}{cccc}{T}_{\mathrm{tx}}[1,1]& T_{\mathrm{tx}}[1,2]& \cdots & T_{\mathrm{tx}}[1,N_{\mathrm{sn}}]\\ ⌀& T_{\mathrm{tx}}[2,2]& \cdots & T_{\mathrm{tx}}[2,N_{\mathrm{sn}}]\\ ⋮& ⋮& \ddots & ⋮\\ ⌀& ⌀& \cdots & T_{\mathrm{tx}}[N_{\mathrm{sn}},N_{\mathrm{sn}}]\end{array}\right],$$

(1)

where $T_{\mathrm{tx}}[i,i]$ is the transmit delay assigned to node i for sending its own data packets, $T_{\mathrm{tx}}[i,j]$ ($i<j$) is the transmit delay assigned to node i for forwarding data packets originating at node j.

2.1. LTDA-MAC Schedule Optimization

Deriving an LTDA-MAC schedule for a given LUASN deployment requires a joint optimization of $N_{\mathrm{sn}}(N_{\mathrm{sn}}+1)/2$ values in ${\mathit{T}}_{\mathbf{tx}}$ that minimize the frame duration:

$$\min {\tau }_{\mathrm{frame}}\left(𝓝,{\mathit{T}}_{\mathbf{tx}}\right)$$

(2a)

$$\mathrm{s.t.}{n}_{\mathrm{col}}(𝓝,{\mathit{T}}_{\mathbf{tx}},{\tau }_{\mathrm{g}})=0,$$

(2b)

where ${\tau }_{\mathrm{frame}}\left(𝓝,{\mathit{T}}_{\mathbf{tx}}\right)$ is defined as the time between the sink node sending the initial REQ packet and receiving the final data packet, $n_{\mathrm{col}}(𝓝,{\mathit{T}}_{\mathbf{tx}},{\tau }_{\mathrm{g}})$ is the number of collisions caused by the transmitted/received packets overlapping in time at any node, ${\tau }_{\mathrm{g}}$ is the desired guard interval specifying the minimum allowed time separation between scheduled packets, and $𝓝$ is a representation of a given network topology described below.

We define the network deployment parameters as a tuple $𝓝=\{\mathit{I},{\mathit{T}}_{\mathbf{p}},{\tau }_{\mathrm{rp}},{\tau }_{\mathrm{dp}}\}$, where $\mathit{I}$ is the interference matrix, ${\mathit{T}}_{\mathbf{p}}$ is the matrix of propagation delays between every pair of nodes, and ${\tau }_{\mathrm{rp}}$ and ${\tau }_{\mathrm{dp}}$ are the REQ and data packet duration, respectively. $\mathit{I}$ and ${\mathit{T}}_{\mathbf{p}}$ are computed by the master node during the network discovery stage, and can then be periodically updated based on the timing of received data packets. This process is appropriate for tracking the topology of a quasi-stationary UASN, as described in [21]. $\mathit{I}$ and ${\mathit{T}}_{\mathbf{p}}$ are $N\times N$ matrices, where $N=1+N_{\mathrm{sn}}$ is the total number of nodes, including one master (sink) node and $N_{\mathrm{sn}}$ sensor nodes. $\mathit{I}$ is a binary matrix, where $I[i,j]=1$ if node j can interfere with node i, and $I[i,j]=0$ otherwise. $T_{\mathrm{p}}[i,j]$ is the propagation delay from node i to node j.

The number of packet collisions in a candidate LTDA-MAC schedule $n_{\mathrm{col}}(𝓝,{\mathit{T}}_{\mathbf{tx}},{\tau }_{\mathrm{g}})$ depends on the specific pattern of interfering links, propagation delays and packet durations, different for every network deployment. We found it intractable to solve this optimization problem analytically for an arbitrary network topology $𝓝$ (a formal proof of complexity of this problem is a subject of further work). Therefore, in [8] we proposed a heuristic “simulation-in-the-loop” optimization algorithm comprising two stages: (1) GA for initial coarse optimization, (2) PSO for converging on a locally optimal solution. There, the packet collision constraint (2b) is evaluated algorithmically by calculating the Tx and Rx times of every packet in a single frame. If any pair of Tx/Rx packets overlaps in time at the same node, or is separated by less than ${\tau }_{\mathrm{g}}$, a collision is detected and $n_{\mathrm{col}}(𝓝,{\mathit{T}}_{\mathbf{tx}},{\tau }_{\mathrm{g}})$ is incremented. The drawback of this approach is its need to evaluate many candidate solutions before converging. The purpose of this paper is to propose an alternative heuristic optimization algorithm that produces better LTDA-MAC schedule solutions and that is significantly more computationally efficient.

2.2. Greedy Optimization Algorithm

The high computational complexity of the GA + PSO method proposed in [8] stems from the need to minimize a nonlinear discontinuous objective function in $N_{\mathrm{sn}}(N_{\mathrm{sn}}+1)/2$ dimensions, resulting in a vast non-convex solution space. To reduce the computational cost of LTDA-MAC schedule optimization we propose a new greedy algorithm that iterates over every Tx delay in ${\mathit{T}}_{\mathbf{tx}}$ and chooses a locally optimal value for it in isolation. To ensure that valid LTDA-MAC schedules are produced by such an iterative greedy optimization approach, we impose the following constraints on the Tx delays.

Firstly, the minimum transmit delay assigned to node n for transmitting its own data packet is:

$$\forall n\in \{1..N_{\mathrm{sn}}\},T_{\mathrm{m}}[n,n]=\left\{\begin{array}{cc}{\tau }_{\mathrm{rp}}+2{\tau }_{\mathrm{g}},\hfill & n<N_{\mathrm{sn}}\hfill \\ {\tau }_{\mathrm{g}},\hfill & n=N_{\mathrm{sn}},\hfill \end{array}\right.$$

(3)

where $T_{\mathrm{m}}[i,j]$ is the minimum transmit delay that can be assigned to node i for transmitting a packet generated by node j. The above constraint ensures that those nodes that need to forward a REQ packet further down the chain, have time to do it before transmitting their data packet up the chain.

Secondly, the minimum transmit delay for forwarding other nodes’ packets is defined as follows:

$$\begin{array}{c}\forall n,k\in \{1..N_{\mathrm{sn}}\},k>n,\hfill \\ T_{\mathrm{m}}[n,k]=2\left({\tau }_{\mathrm{p}}[n+1]+{\tau }_{\mathrm{g}}\right)+{\tau }_{\mathrm{rp}}+{\tau }_{\mathrm{dp}}+T_{\mathrm{tx}}[n+1,k],\hfill \end{array}$$

(4)

where ${\tau }_{\mathrm{p}}\left[i\right]$ is the propagation delay on the $i^{\mathrm{th}}$ link between adjacent nodes of the linear network topology, i.e., $\forall i\in \{1..N_{\mathrm{sn}}\},{\tau }_{\mathrm{p}}\left[i\right]=T_{\mathrm{p}}[i,i+1]$.

The above constraint ensures that a node cannot forward a data packet from another node before actually receiving it. Note that in this paper all values in ${\mathit{T}}_{\mathbf{tx}}$ are relative to the time of the REQ packet reception, i.e., $T_{\mathrm{tx}}[i,j]$ is defined as the time between node i receiving a REQ packet and transmitting the data packet generated by node j. This is different to the original definition of ${\mathit{T}}_{\mathbf{tx}}$ in [8]. This new definition decouples the Tx delays assigned to multiple nodes for forwarding the same data packet up the chain, and enables our proposed greedy algorithm to optimize them in isolation.

Our proposed greedy optimization method is shown in Algorithm 1. It iterates over every value in ${\mathit{T}}_{\mathbf{tx}}$ in the order that maximizes the chances of scheduling simultaneous spatially separated transmissions. For every Tx delay $T_{\mathrm{tx}}[i,j]$, the algorithm starts by evaluating the LTDA-MAC schedule using $T_{\mathrm{tx}}[i,j]=T_{\mathrm{m}}[i,j]$, i.e., the minimum possible value according to (3) and (4). If there are collisions in the schedule, $T_{\mathrm{tx}}[i,j]$ is incremented by ${\tau }_{\mathrm{step}}$, and the schedule is evaluated again. This incremental search continues until the schedule is collision-free. In the experiments reported in this paper the value of ${\tau }_{\mathrm{step}}$ was set to ${\tau }_{\mathrm{guard}}/2$ which achieved a good trade-off between the algorithm’s ability to find good solutions and its computational cost. Incorporating more sophisticated variable step methods is a subject of further work.

Algorithm 1 The proposed greedy optimization algorithm for LTDA-MAC scheduling

1:  Create $𝓝$ via initial network discovery 2:  Set the desired guard interval ${\tau }_{\mathrm{g}}$ and time step ${\tau }_{\mathrm{step}}$ 3:  Initialize collision-free schedule ${\mathit{T}}_{\mathbf{tx}}$ using (5) 4:  for $i\in \{1..N_{\mathrm{sn}}\}$ do 5:   for $n\in \{1..(N_{\mathrm{sn}}-i+1)\}$ do 6:    Calculate the packet index $k=n+i-1$ 7:    Calculate $T_{\mathrm{m}}[n,k]$ using (3) if $n=k$, or (4) if $n\ne k$ 8:    Initialize Tx delay: $T_{\mathrm{tx}}[n,k]=T_{\mathrm{m}}[n,k]$ 9:    while $n_{\mathrm{col}}\left(𝓝,{\mathit{T}}_{\mathbf{tx}},{\tau }_{\mathrm{g}}\right)>0$ do 10:     Increment Tx delay: $T_{\mathrm{tx}}[n,k]\leftarrow T_{\mathrm{tx}}[n,k]+{\tau }_{\mathrm{step}}$ 11:    end while 12:   end for 13:  end for

The Tx delay matrix is initialized as follows:

$$\forall n,k\in \{1..N_{\mathrm{sn}}\},k\ge n,T_{\mathrm{tx}}[n,k]=\left(N_{\mathrm{sn}}n+k\right)T_{\mathrm{large}},$$

(5)

where $T_{\mathrm{large}}$ is an arbitrarily long time interval, e.g., we use $T_{\mathrm{large}}={10}^6$, that makes sure that the initial Tx delay matrix is collision-free. It also allows every Tx delay in ${\mathit{T}}_{\mathbf{tx}}$ to be optimized separately and replace its initial arbitrary value without affecting the rest of the schedule.

3. Simulation Results

3.1. Simulation Setup

This section evaluates the performance of the LTDA-MAC protocol equipped with the proposed schedule optimization algorithm applied to the pipeline monitoring scenarios considered in [8], similar to that depicted in Figure 1. The maximum sea depth is 500 m. The pipeline at 480 m depth is connected to the platform at the sea surface through a riser, whose shape is modeled as a quarter-circle. Two different pipeline lengths are simulated: 2 km and 20 km. Initially, 11 nodes (1 sink + 10 sensor nodes) are spread across the length of the pipeline at equidistant points. Afterwards, 50 sets of node positions are generated to include random horizontal perturbations (0–20 m and 0–200 m for the two scenarios, respectively) in random directions from the initial equidistant points. This approach yields a statistical spread of channel conditions with variations in received signal and interference power, thus providing statistically more valid results. The wideband multipath channel with 24 kHz centre frequency and 7.2 kHz bandwidth was modeled using the BELLHOP beam tracing method described in [23]. Without loss of generality, these simulations use a threshold for interfering link detection of 0 dB Signal-to-Noise Ratio (SNR), i.e., all links with SNR ≥ 0 dB were marked with 1 in the interference matrix $\mathit{I}$, while all of the wanted links in the linear topology also have SNR > 0 dB. The SNR is calculated using the analytical ambient noise model with 10 m/s wind speed and 0.5 shipping activity factor [23]. The other parameters for the 2 km and 20 km pipeline scenarios, respectively, are:

• 140 dB re $\mathsf{\mu }$Pa${}^2$m${}^2$ source level, 200 ms data packets, 50 ms REQ packets, 25 ms guard interval;
• 170 dB re $\mathsf{\mu }$Pa${}^2$m${}^2$ source level, 500 ms data packets, 100 ms REQ packets, 100 ms guard interval.

3.2. Discussion

Figure 3 compares the LTDA-MAC schedules derived by the greedy algorithm proposed in this paper with those derived by our previously proposed GA + PSO method [8]. The parameters of the GA and PSO algorithms are:

• GA: population size—500, mutation rate—0.1, 80% scattered crossover, 1000 generations limit;
• PSO: swarm size—500, minimum neighbourhood fraction—0.1, adaptive inertia range—[0.05, 0.8], 1000 iterations limit.

These parameters were empirically found to produce the best performance in our previous study in [8], by providing a large enough population/swarm to explore the high-dimensional solution space, and to enable a sufficient number of GA generations and PSO iterations to find good suboptimal solutions.

This section also provides a baseline comparison with the Spatial TDMA approach (STDMA) [10,11], tailored to the linear network scenario studied in this paper. An STDMA frame comprises a sequence of synchronized time slots for collision-free multiple access. To avoid inter-slot interference, the slot duration is:

$${\tau }_{\mathrm{slot}}={\tau }_{\mathrm{dp}}+\underset{\begin{array}{c}I[i,j]=1\end{array}}{max}\left\{T_{\mathrm{p}}[i,j]\right\}+{\tau }_{\mathrm{g}},$$

(6)

which ensures that no packets transmitted in a given TDMA slot are received at any node in the subsequent slot. The spatial reuse pattern is achieved by computing a binary $N_{\mathrm{sn}}\times L$ matrix indicating which node transmits in which time slot, such that L (the number of slots) is minimized with no collisions. The STDMA frame length is then calculated as: ${\tau }_{\mathrm{frame}}=L{\tau }_{\mathrm{slot}}$.

Figure 3 shows that the new heuristic optimization algorithm proposed in this paper derives packet schedules with shorter frame duration than the GA + PSO method and the STDMA protocol (despite the latter benefiting from clock synchronization), thus achieving higher network throughput of the LTDA-MAC protocol in both simulated scenarios. Furthermore, the proposed greedy algorithm is more reliable than GA + PSO, because the former is a deterministic method that does not rely on randomly generating and mutating candidate solutions. Therefore, the statistical spread of the results achieved by the greedy algorithm is significantly smaller, and is caused only by the perturbations in the simulated network topologies, rather than the random number generator seed (like GA, PSO and similar methods). The significant difference in the optimization performance between the proposed greedy algorithm and the GA + PSO method is due to the inherently discontinuous and high-dimensional nature of the optimization problem, where treating the entire scheduling problem as a “black box” makes it very challenging for a heuristic algorithm such as GA or PSO to find good solutions. In contrast, the new greedy algorithm deconstructs the problem into a series of much simpler problems, minimizing every transmit delay in isolation, thus resulting in much better performance. Figure 4 gives examples of the LTDA-MAC schedules derived for the 2 km and 20 km pipeline scenarios, showcasing the topology-aware spatial reuse of resources achieved by the LTDA-MAC protocol employing the proposed schedule optimization algorithm.

In addition to the notable improvement in the algorithm performance shown in Figure 3,

Table 1. Number of schedule evaluations (M—million) and computer runtime of the proposed greedy optimization algorithm, compared with the GA + PSO method.

Metric	Scenario	Algorithm Performance
		(Mean 5th–95th Percentile Range)
		GA + PSO	Greedy
Num. evals	2 km pipeline	(0.99M 0.90M–1M)	3402 (2871–4212)
	20 km pipeline	0.99M (0.89M–1M)	821 (754–827)
Runtime, sec	2 km pipeline	424 (337–489)	1.1 (0.91–1.4)
	20 km pipeline	384 (312–454)	0.27 (0.25–0.34)

highlights the significant reduction in the computational cost of the greedy optimization algorithm compared with our previously proposed GA + PSO method. The number of schedule evaluations before finding a solution is reduced by 2–3 orders of magnitude, thus reducing the computer runtime from several minutes to approximately 1 s or less. The runtime figures were obtained by executing the algorithms in MATLAB R2018a as single-core jobs on the standard node of the Viking computing cluster at University of York: Intel Xeon 6138 2.0 GHz, Centos Linux 7.3.

4. Conclusions

The LTDA-MAC protocol facilitates efficient packet scheduling in LUASNs without the need for synchronized clocks at the network nodes. The key part of the LTDA-MAC protocol is the real-time application of a heuristic optimization algorithm to produce a packet schedule with spatial spectrum reuse tailored to the given deployment scenario. In this paper, we proposed a new greedy optimization algorithm for deriving LTDA-MAC packet schedules that produces reliably better solutions and is 2–3 orders of magnitude more computationally efficient than our previous GA + PSO optimization method. Simulations of LUASNs deployed on 2 km and 20 km underwater pipelines showed that LTDA-MAC can exploit long propagation delays and the interference pattern in a given network deployment to considerably improve the network throughput, compared with the conventional STDMA approach, despite the lack of clock synchronization in LTDA-MAC. Continuing from our previous work on single-hop and dual-hop TDA-MAC, LTDA-MAC equipped with the new greedy schedule optimization algorithm is a key step in our further work on TDA-MAC for unsynchronized scheduling in UASNs with general multi-hop topologies.