# LTDA-MAC v2.0: Topology-Aware Unsynchronized Scheduling in Linear Multi-Hop UWA Networks +
## 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.